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

 
 

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

Submitted by:  James Youngman <jay>
Submitted on:  Tue 21 Apr 2009 09:44:40 PM UTC  
 
Category: findSeverity: 4 - Important
Item Group: Wrong resultStatus: Invalid
Privacy: PublicAssigned to: James Youngman <jay>
Originator Name: Michael TautschnigOpen/Closed: Closed
Release: 4.4.0Fixed Release: None

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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

This isn't a bug.

James Youngman <jay>
Project AdministratorIn charge of this item.
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>
Project AdministratorIn charge of this item.
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>
Project AdministratorIn charge of this item.
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>
Project AdministratorIn charge of this item.

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 10 Jul 2009 09:09:43 AM UTCjayOpen/ClosedOpen=>Closed
    Sun 05 Jul 2009 05:45:43 PM UTCjayStatusIn Progress=>Invalid
    Tue 21 Apr 2009 09:44:40 PM UTCjayCarbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1