bugfindutils - Bugs: bug #26281, find -depth sometimes visits nodes...

 
 

bug #26281: find -depth sometimes visits nodes in the wrong order

Submitter:  James Youngman <jay>
Submitted:  Tue 21 Apr 2009 09:44:40 PM UTC
   
 
Category:  find Severity:  4 - Important
Item Group:  Wrong result Status:  Invalid
Privacy:  Public Assigned to:  jay
Originator Name:  Michael Tautschnig Open/Closed:  Closed
Release:  4.4.0 Fixed Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 05 Jul 2009 05:45:43 PM UTC, comment #4: 

This isn't a bug.

James Youngman <jay>
Group administrator
Mon 27 Apr 2009 01:33:12 PM UTC, comment #3: 

Hi James,

It looks to me like find/fts are doing just what is required.
I.e,. processing all entries in a directory before processing the directory itself.

It's easier to see with an example like this, where directories are actually processed:

find . -depth \( -name Makefile.am -or -type d \) -print

With that, you can see that no Makefile.am file name is printed before the name of its containing directory.  That's all that matters.  There is no other guarantee.

Jim Meyering <meyering>
Tue 21 Apr 2009 10:56:34 PM UTC, comment #2: 

There is a second alternative interpretation of events, I think.   The POSIX description for -depth is:

-depth
    The primary shall always evaluate as true; it shall cause descent of the directory hierarchy to be done so that all entries in a directory are acted on before the directory itself. If a -depth primary is not specified, all entries in a directory shall be acted on after the directory itself. If any -depth primary is specified, it shall apply to the entire expression even if the -depth primary would not normally be evaluated.


One reading of this is that the paragraph above only requires that "dir/m4/Makefile.am"  and "dir/Makefile.am" are both processed before "dir" itself, but that no guarantee need be made about the relative ordering of the visits to the two files.


James Youngman <jay>
Group administrator
Tue 21 Apr 2009 10:41:44 PM UTC, comment #1: 

It appears that find is using gnulib's ftp() implementation in a way that isn't guaranteed to order visits to files and subdirectories in any given order.  FTS_D and FTS_DP can be used to consider subdirectores before parent directories, but this does not guarantee anything about the relative ordering of return of files in the parent directory, as compared to sudirectories in that parent.  

Here is an illustration of a possible execution of
"find dir -depth -name Makefile.am -print". 

The table has 3 columns.   The first is the value of fts_info when fts_read returns.  The second is the filename (fts_info->fts_path).   The third is PRINT if the -print succeeds there.

FTS_D     dir
FTS_NSOK  dir/foo
FTS_NSOK  dir/Makefile.am  PRINT
FTS_D     dir/m4
FTS_NSOK  dir/m4/Makefile.am PRINT
FTS_DP    dir/m4
FTS_NSOK  dir/bar
FTS_DP    dir

So here, find will print ...
  dir/Makefile.am
  dir/m4/Makefile.am
... when clearly the user expected the opposite order.

The correct approach may well be simply to pass an appropriate comparison function to fts_open, so that files are visited last in -depth traversals.  From my reading of the documentation FTS_NSOK is never returned for directories, which would be a required property in order for this strategy to work.

James Youngman <jay>
Group administrator
Tue 21 Apr 2009 09:44:40 PM UTC, original submission:  

See also Debian bug 524994.

$ /home/james/source/GNU/findutils/git/gnu/compile/64/find/find . -depth -name Makefile.am
./xargs/testsuite/Makefile.am
./xargs/Makefile.am
./tests/Makefile.am
./lib/Makefile.am
./locate/testsuite/Makefile.am
./locate/Makefile.am
./doc/Makefile.am
./gnulib/lib/Makefile.am
./gnulib/Makefile.am
./find/testsuite/Makefile.am
./find/Makefile.am
./build-aux/Makefile.am
./Makefile.am
./m4/Makefile.am
~/source/GNU/findutils/git/gnu/findutils$ /home/james/source/GNU/findutils/git/gnu/compile/64/find/find --version
find (GNU findutils) 4.4.1-git
Copyright (C) 2007 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Eric B. Decker, James Youngman, and Kevin Dalley.
Built using GNU gnulib version e5573b1bad88bfabcda181b9e0125fb0c52b7d3b
Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS() CBO(level=0)



James Youngman <jay>
Group administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by meyering (Posted a comment)
  • -email is unavailable- added by jay (Submitted the item)
  • -email is unavailable- added by jay (Downstream bug)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-07-10 jay Open/ClosedOpen Closed
    2009-07-05 jay StatusIn Progress Invalid
    2009-04-21 jay Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code