fts: Document this module

fts: Document this module

[Bruno Haible]

The 'fts' module was not documented in the documentation, so far.


2023-01-19  Bruno Haible  <bruno@clisp.org>

	fts: Document this module.
	* doc/glibc-headers/fts.texi: Mention the 'fts' module.
	* doc/glibc-functions/fts_children.texi: Likewise.
	* doc/glibc-functions/fts_close.texi: Likewise.
	* doc/glibc-functions/fts_open.texi: Likewise.
	* doc/glibc-functions/fts_read.texi: Likewise.
	* doc/glibc-functions/fts_set.texi: Likewise.

diff --git a/doc/glibc-functions/fts_children.texi b/doc/glibc-functions/fts_children.texi
index 12ec251f31..0a43e2621f 100644
--- a/doc/glibc-functions/fts_children.texi
+++ b/doc/glibc-functions/fts_children.texi
@@ -4,18 +4,18 @@
 
 Documentation:@* @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts_children.3.html,,man fts_children}
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This function is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
 @item
-This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
-@item
 On platforms where @code{off_t} is a 32-bit type, this function may not
 correctly report the size of files or block devices larger than 2 GB and
 may not work correctly on huge directories larger than 2 GB@.  Also, on
diff --git a/doc/glibc-functions/fts_close.texi b/doc/glibc-functions/fts_close.texi
index ff5bebe84b..6cd4439fbe 100644
--- a/doc/glibc-functions/fts_close.texi
+++ b/doc/glibc-functions/fts_close.texi
@@ -4,15 +4,15 @@
 
 Documentation:@* @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts_close.3.html,,man fts_close}
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This function is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
-@item
-This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
diff --git a/doc/glibc-functions/fts_open.texi b/doc/glibc-functions/fts_open.texi
index 9142e288bf..4d1ce289d5 100644
--- a/doc/glibc-functions/fts_open.texi
+++ b/doc/glibc-functions/fts_open.texi
@@ -4,15 +4,15 @@
 
 Documentation:@* @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts_open.3.html,,man fts_open}
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This function is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
-@item
-This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
diff --git a/doc/glibc-functions/fts_read.texi b/doc/glibc-functions/fts_read.texi
index a0faa77d7f..7737d096cc 100644
--- a/doc/glibc-functions/fts_read.texi
+++ b/doc/glibc-functions/fts_read.texi
@@ -4,18 +4,18 @@
 
 Documentation:@* @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts_read.3.html,,man fts_read}
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This function is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
 @item
-This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
-@item
 On platforms where @code{off_t} is a 32-bit type, this function may not
 correctly report the size of files or block devices larger than 2 GB and
 may not work correctly on huge directories larger than 2 GB@.  Also, on
diff --git a/doc/glibc-functions/fts_set.texi b/doc/glibc-functions/fts_set.texi
index 47f645401e..297ceb476f 100644
--- a/doc/glibc-functions/fts_set.texi
+++ b/doc/glibc-functions/fts_set.texi
@@ -4,15 +4,15 @@
 
 Documentation:@* @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts_set.3.html,,man fts_set}
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This function is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
-@item
-This function is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
diff --git a/doc/glibc-headers/fts.texi b/doc/glibc-headers/fts.texi
index 4fe6714e60..f725d8cf1c 100644
--- a/doc/glibc-headers/fts.texi
+++ b/doc/glibc-headers/fts.texi
@@ -11,15 +11,15 @@ Documentation:
 @uref{https://www.kernel.org/doc/man-pages/online/pages/man3/fts.3.html,,man fts}.
 @end itemize
 
-Gnulib module: ---
+Gnulib module: fts
 
 Portability problems fixed by Gnulib:
 @itemize
+@item
+This header file is missing on some platforms:
+AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize
 
 Portability problems not fixed by Gnulib:
 @itemize
-@item
-This header file is missing on some platforms:
-AIX 5.1, HP-UX 11, IRIX 6.5, Solaris 11.3, mingw, MSVC 14.
 @end itemize

Re: fts: Document this module

[Simon Josefsson via Gnulib discussion list]

[-- Attachment #1: Type: text/plain, Size: 559 bytes --]

Bruno Haible <bruno@clisp.org> writes:

> The 'fts' module was not documented in the documentation, so far.

The gnulib fts is different from glibc API, and they can return
different results when called the same way.  See end of earlier thread
here:

https://lists.gnu.org/archive/html/bug-gnulib/2021-07/msg00070.html

I'm not sure what could be done.  Perhaps adding a sentence to the
gnulib documentation stating that the gnulib fts is not a drop-in
replacement for missing fts functionality but a separate implementation
with different behaviour.

/Simon

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 255 bytes --]

Re: fts: Document this module

[Bruno Haible]

> The gnulib fts is different from glibc API, and they can return
> different results when called the same way.  See end of earlier thread
> here:
> 
> https://lists.gnu.org/archive/html/bug-gnulib/2021-07/msg00070.html

Thanks for the heads-up, Simon.

> I'm not sure what could be done.  Perhaps adding a sentence to the
> gnulib documentation stating that the gnulib fts is not a drop-in
> replacement for missing fts functionality but a separate implementation
> with different behaviour.

I'm not sure about what to write either. Jim or Paul, what should we state
— either in the 'fts' module description, or in the .texi documentation?

Bruno

Re: fts: Document this module

[Paul Eggert]

On 1/19/23 15:41, Bruno Haible wrote:
> Jim or Paul, what should we state
> — either in the 'fts' module description, or in the .texi documentation?

The quick thing is to say in both that the description/documentation is 
incomplete, and that people need to read the source code.

Jim may be able to fill in a bit here, since I think he wrote most of 
that stuff. (I haven't checked this though; sorry, I'm a bit crunched 
for time today.)

Re: fts: Document this module

[Jim Meyering]

On Thu, Jan 19, 2023 at 7:05 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
>
> On 1/19/23 15:41, Bruno Haible wrote:
> > Jim or Paul, what should we state
> > — either in the 'fts' module description, or in the .texi documentation?
>
> The quick thing is to say in both that the description/documentation is
> incomplete, and that people need to read the source code.
>
> Jim may be able to fill in a bit here, since I think he wrote most of
> that stuff. (I haven't checked this though; sorry, I'm a bit crunched
> for time today.)

Thanks for caring/documenting. Here's a quick summary (for more
detail, see the comments in fts_.h).

This started when I found glibc's fts was insufficiently robust to
meet GNU rm's needs (rm was merely the first user; now, many others
use it):
- O(N^2) behavior in the number of file name components due to cycle detection
- max hierarchy depth was 64k due to type of fts_level being a "short"
- subject to O(N^2) effects for directories with many entries (poor
locality of reference, for which the fix was to process entries in
sorted-inode order (per a heuristic), delaying any "stat" until
operating on the entry)

Re fts's cycle detection:
- contrast glibc's O(depth) time algorithm vs our O(1) implementation
- our cheap-but-lazy O(1)-memory approach is ok for most applications, but
- there's an optional, slightly more costly detect-ASAP approach required for du
    (uses O(max-depth-of-hierarchy) memory)


Fixing those things required ABI changes and nontrivial redesign.