Hi,
Long time user, first time GNU contributor (I think). I'm submitting patches
to add a sort option to find. It will cause find to sort files by name within
each directory before processing them.
As I wrote in the info page, "the -s option is more efficient than piping
large amounts of output of find into the sort command, and it produces output
incrementally rather than buffering it all. It's also more convenient when
the output of a find command isn't line-oriented or the lines don't start
with the filenames."
This is not a new idea. It's been in this project's TODO file in the context
of updatedb since the year 2000. FreeBSD has included the -s flag in its man
page for find since FreeBSD 3.1 [1], which was released in 1999. Mac OS X
picked it up from FreeBSD.
Sorting has also been proposed previously on this mailing list. Phil Miller
submitted a patch in 2014 that used `-sort` as a predicate [2][3]. After some
discussion about sorting directories by inode, Phil's proposal appears to
have fallen through.
My proposal uses `-s` as a global option instead of Phil's `-sort` predicate.
The advantages of `-s` are (a) compatibility with BSD and Mac OS X and
(b) allowing users to easily create a shell alias for `find -s`.
One thing I didn't do is update the `oldfind` command to respect `-s`. It
looked like that would require a non-trivial change. Is `oldfind` still used?
Another thing is I didn't do is update the `updatedb.sh` script to take
advantage of `find -s`. I wanted to see if this change would be accepted
first. I also wasn't sure if testing for `find -s` should happen at
build-time (like `sort -z`) or at run-time.
Please see the attached patches:
[PATCH 1/3] Add find -s (sort) global option
[PATCH 2/3] find: Update docs for -s (sort)
[PATCH 3/3] find: Add test for sort
I'll reply to this email with the patches too, and hopefully one of those
options will be readable to you all. Apologies in advance if I and/or GMail
mess that up.
Thanks for your feedback,
Diego
[1] https://www.freebsd.org/cgi/man.cgi?query=find&manpath=FreeBSD+3.1-RELEASE
[2] https://lists.gnu.org/archive/html/findutils-patches/2014-12/msg00005.html
[3] https://lists.gnu.org/archive/html/findutils-patches/2015-01/msg00003.html
From 882a6b0f36ae78252e1a384414a9728e07017ab7 Mon Sep 17 00:00:00 2001
From: Diego Ongaro <[email protected]>
Date: Tue, 18 Aug 2020 16:51:53 -0700
Subject: [PATCH 2/3] find: Update docs for -s (sort)
---
TODO | 12 ++----------
doc/find.texi | 24 ++++++++++++++++++++++--
find/find.1 | 12 +++++++++++-
3 files changed, 35 insertions(+), 13 deletions(-)
diff --git a/TODO b/TODO
index 6f0a5536..3760b7f4 100644
--- a/TODO
+++ b/TODO
@@ -5,16 +5,8 @@
* man page for frcode
Perhaps a better description in texi pages as well.
-* Add option for find to sort output in lexical order for use for updatedb
[email protected] (Olivier) made the following suggestion:
-
-As I was running thru the code looking for the bug I wondered why the updatedb
-has to use sort...
-why not add an option to find that sorts the output in lexical order?
-my point is:
-- sort on a big list is costly (here we do locate on big big file system)
-- find may (in theory) sort incrementally very easily by sorting only the current
-directory entries before recursion
+* Make updatedb use find -s (sort) where available, as suggested by
[email protected] (Olivier) long ago.
* Include example of use of updatedb in documentation.
Use something close to the Debian daily cron job.
diff --git a/doc/find.texi b/doc/find.texi
index ce63ca52..ebc8f8ee 100644
--- a/doc/find.texi
+++ b/doc/find.texi
@@ -3258,7 +3258,7 @@ discussed in this manual.
@section Invoking @code{find}
@example
-find @r{[-H] [-L] [-P] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@dots{}@r{]} @r{[}@var{expression}@r{]}
+find @r{[-H] [-L] [-P] [-s] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@dots{}@r{]} @r{[}@var{expression}@r{]}
@end example
@code{find} searches the directory tree rooted at each file name
@@ -3266,7 +3266,7 @@ find @r{[-H] [-L] [-P] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@
the tree.
The command line may begin with the @samp{-H}, @samp{-L}, @samp{-P},
-@samp{-D} and @samp{-O} options. These are followed by a list of
+@samp{-s}, @samp{-D} and @samp{-O} options. These are followed by a list of
files or directories that should be searched. If no files to search
are specified, the current directory (@file{.}) is used.
@@ -3330,6 +3330,26 @@ broken), it falls back on using the properties of the symbolic link
itself. @ref{Symbolic Links} for a more complete description of how
symbolic links are handled.
+The @samp{-s} option causes @code{find} to process files within each directory
+in sorted order by name, as defined by the current locale. Without this,
+@code{find} processes files in unspecified order.
+
+The exact ordering is determined by the @code{LC_COLLATE} setting in the
+current locale. To sort by byte order, use @code{LC_COLLATE=C}.
+
+The @samp{-s} option is more efficient than piping large amounts of output of
+@code{find} into the @code{sort} command, and it produces output incrementally
+rather than buffering it all. It's also more convenient when the output of a
+@code{find} command isn't line-oriented or the lines don't start with the
+filenames.
+
+Note that the output of @code{find} with @samp{-s} may differ from that of
+piping into the @code{sort} command. For example, @code{sort} isn't aware that
+``/'' separates directories and may ouptut ``foo.baz'' before ``foo/bar''
+(depending on the locale). However, @code{find} with @samp{-s} will always
+process ``foo'' and its children first, since the name of the directory ``foo''
+always sorts before the name ``foo.baz``.
+
@node Warning Messages
@subsection Warning Messages
diff --git a/find/find.1 b/find/find.1
index 45895158..ca65d0ff 100644
--- a/find/find.1
+++ b/find/find.1
@@ -53,11 +53,12 @@ instead, anyway).
This manual page talks about `options' within the expression list.
These options control the behaviour of
.B find
-but are specified immediately after the last path name. The five
+but are specified immediately after the last path name. The six
`real' options
.BR \-H ,
.BR \-L ,
.BR \-P ,
+.BR \-s ,
.B \-D
and
.B \-O
@@ -214,6 +215,10 @@ is, any symbolic links appearing after
on the
command line will be dereferenced, and those before it will not).
+.IP \-s
+Process files within each directory in sorted order by name, as defined by the
+current locale. Without this, \fBfind\fR processes files in unspecified order.
+
.IP "\-D debugopts"
Print diagnostic information; this can be helpful to diagnose problems
with why
@@ -1992,6 +1997,10 @@ interpret the response to
.BR \-ok ,
the interpretation of any bracket expressions in the pattern will be
affected by `LC_COLLATE'.
+With the
+.B \-s
+option, the `LC_COLLATE` environment variable will also affect the order that
+files are processed within each directory.
.IP LC_CTYPE
This variable affects the treatment of character classes used in
@@ -2381,6 +2390,7 @@ exit status was unaffected by the failure of
.TS
l l l .
Feature Added in Also occurs in
+\-s unreleased BSD
\-newerXY 4.3.3 BSD
\-D 4.3.1
\-O 4.3.1
--
2.27.0
From 0547be3d63e59b4d364f77ee977acbe985d13139 Mon Sep 17 00:00:00 2001
From: Diego Ongaro <[email protected]>
Date: Tue, 18 Aug 2020 16:50:00 -0700
Subject: [PATCH 1/3] Add find -s (sort) global option
This commit contains just the code changes for ftsfind. Docs and tests to
follow.
---
find/defs.h | 5 +++++
find/ftsfind.c | 7 ++++++-
find/util.c | 8 +++++++-
3 files changed, 18 insertions(+), 2 deletions(-)
diff --git a/find/defs.h b/find/defs.h
index 4cba5b45..71a622e1 100644
--- a/find/defs.h
+++ b/find/defs.h
@@ -554,6 +554,11 @@ enum DebugOption
struct options
{
+ /* If true, process files within each directory in the order defined by
+ * LC_COLLATE. If false (default), follow default FTS order.
+ */
+ bool sort;
+
/* If true, process directory before contents. True unless -depth given. */
bool do_dir_first;
/* If true, -depth was EXPLICITLY set (as opposed to having been turned
diff --git a/find/ftsfind.c b/find/ftsfind.c
index 783148c5..aa27666c 100644
--- a/find/ftsfind.c
+++ b/find/ftsfind.c
@@ -34,6 +34,7 @@
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
+#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
@@ -514,6 +515,10 @@ consider_visiting (FTS *p, FTSENT *ent)
}
}
+static int compare(FTSENT const **a, FTSENT const **b) {
+ assert ((*a)->fts_parent == (*b)->fts_parent);
+ return strcoll((*a)->fts_name, (*b)->fts_name);
+}
static bool
@@ -547,7 +552,7 @@ find (char *arg)
if (options.stay_on_filesystem)
ftsoptions |= FTS_XDEV;
- p = fts_open (arglist, ftsoptions, NULL);
+ p = fts_open (arglist, ftsoptions, options.sort ? compare : NULL);
if (NULL == p)
{
error (0, errno, _("cannot search %s"),
diff --git a/find/util.c b/find/util.c
index 71db7f1c..805851a3 100644
--- a/find/util.c
+++ b/find/util.c
@@ -167,7 +167,7 @@ usage (int status)
#define HTL(t) fputs (t, stdout);
fprintf (stdout, _("\
-Usage: %s [-H] [-L] [-P] [-Olevel] [-D debugopts] [path...] [expression]\n"),
+Usage: %s [-H] [-L] [-P] [-s] [-Olevel] [-D debugopts] [path...] [expression]\n"),
program_name);
HTL (_("\n\
@@ -944,6 +944,11 @@ process_leading_options (int argc, char *argv[])
/* Meaning: never dereference symbolic links (default). */
set_follow_state (SYMLINK_NEVER_DEREF);
}
+ else if (0 == strcmp ("-s", argv[i]))
+ {
+ /* Meaning: sort files by name within each directory */
+ options.sort = true;
+ }
else if (0 == strcmp ("--", argv[i]))
{
/* -- signifies the end of options. */
@@ -1034,6 +1039,7 @@ set_option_defaults (struct options *p)
p->warnings = false;
}
+ p->sort = false;
p->do_dir_first = true;
p->explicit_depth = false;
p->maxdepth = p->mindepth = -1;
--
2.27.0
From 39022119b2ffa04ff8bac4667cc4af7e80929a54 Mon Sep 17 00:00:00 2001
From: Diego Ongaro <[email protected]>
Date: Tue, 18 Aug 2020 16:52:20 -0700
Subject: [PATCH 3/3] find: Add test for sort
---
tests/find/sorted.sh | 80 ++++++++++++++++++++++++++++++++++++++++++++
tests/local.mk | 1 +
2 files changed, 81 insertions(+)
create mode 100644 tests/find/sorted.sh
diff --git a/tests/find/sorted.sh b/tests/find/sorted.sh
new file mode 100644
index 00000000..5a1b5fa5
--- /dev/null
+++ b/tests/find/sorted.sh
@@ -0,0 +1,80 @@
+#!/bin/sh
+# Verify that find -s sorts the paths by name.
+
+# Copyright (C) 2020 Free Software Foundation, Inc.
+
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/tests/init.sh"; fu_path_prepend_
+print_ver_ find
+
+touch 6253 0812 2790 6311 1958 0211 8704 4019 5408 1001 8501
+mkdir 6331 1239 8506 0496 3663 4040 0327 5338 2465 2749 7012
+touch 6331.{7271,9632,3176,7771,2154}
+touch 6331/{5562,4722,7458,5517,2390}
+mkdir 6331.{9616,3834,4639,2832,0804}
+mkdir 6331/{5961,1694,2227,0628,1041}
+
+find -s > sorted
+
+cat <<_EOD_ > expout || framework_failure_
+.
+./0211
+./0327
+./0496
+./0812
+./1001
+./1239
+./1958
+./2465
+./2749
+./2790
+./3663
+./4019
+./4040
+./5338
+./5408
+./6253
+./6311
+./6331
+./6331/0628
+./6331/1041
+./6331/1694
+./6331/2227
+./6331/2390
+./6331/4722
+./6331/5517
+./6331/5562
+./6331/5961
+./6331/7458
+./6331.0804
+./6331.2154
+./6331.2832
+./6331.3176
+./6331.3834
+./6331.4639
+./6331.7271
+./6331.7771
+./6331.9616
+./6331.9632
+./7012
+./8501
+./8506
+./8704
+./sorted
+_EOD_
+
+compare expout sorted || fail=1
+
+Exit $fail
diff --git a/tests/local.mk b/tests/local.mk
index 13782d86..0d87d099 100644
--- a/tests/local.mk
+++ b/tests/local.mk
@@ -117,6 +117,7 @@ all_tests = \
tests/find/refuse-noop.sh \
tests/find/debug-missing-arg.sh \
tests/find/used.sh \
+ tests/find/sorted.sh \
tests/xargs/verbose-quote.sh \
$(all_root_tests)
--
2.27.0
