Re: find 'breadth first' option

[Bernhard Voelker]

[adding the 'bug-findutils' ML again]

Please keep the discussion on the public mailing list, as others can also read 
it, thanks.

On 10/17/19 9:05 AM, address@hidden wrote:
> On 10/16/19 18:14, "Bernhard Voelker" <address@hidden> wrote:
>> On 10/16/19 4:54 PM, address@hidden wrote:
>>> I've been looking for a breadth-first search option for the find command, 
but found none. Is there anyone ?
>>> If no, would it be possible to add it ?
>> no, find(1) processes the directory hierarchy as provided by gnulib's FTS 
module,
>> or alternatively with -depth.
>>
>> For the results of the search, this should not matter ... well, for the order
>> of the output, it obviously does.
>>
>> If you would want to process each directory level first, and then go down,
>> then I suggest to use the "decorate-sort-undecorate" approach by printing
>> the current depth (%d), then sort by that, and finally remove the depth
>> from the input during the subsequent, actual processing, e.g.:
>>
>>     $ find . -printf '%d %p\0' \
>>         | LC_ALL=C sort -z -k1,1n \
>>         | xargs -0 \
>>             sh -c '\
>>               while [ $# -gt 0 ]; do \
>>                 d="${1%% *}"; \
>>                 e="${1#* }"; \
>>                 shift 1; \
>>                 echo "processing (depth $d): entry: \"${e}\""; \
>>               done' sh
>>     processing (depth 0): entry: "."
>>     processing (depth 1): entry: "./a"
>>     processing (depth 2): entry: "./a/b"
>>     processing (depth 2): entry: "./a/f"
>>     processing (depth 3): entry: "./a/b/c"
>>     processing (depth 3): entry: "./a/b/e"
>>     processing (depth 3): entry: "./a/f/g"
>>     processing (depth 3): entry: "./a/f/h"
>>
>> As the need for such breadth-first processing seems to be quite
>> seldom, and one can work around this with an approach like the
>> above, I currently wouldn't see a reason to add this (or another)
>> traversal algorithm to find(1).
>
> Hello Bernhard,

Hi Francois,

> Thank you for your answer.
>
> I tried your solution, it works. I also found other ones in forums where 
people look for a bds option of find.
> On the other hand (I don't mean to be harsh, please forgive me if I'm), it is 
not very elegant.

I see it completely different: actually this _is_ elegant:
it combines the tools according to the UNIX philosophy, i.e., one tool for one 
purpose.
It does not make sense to put all features into all tools, especially if 
there's already
a way to work around it with some easy piping data into another tool.

Admittedly, the shell script in the latter part looks a bit complex, but this 
was just
to demonstrate what that part should do ... we still don't know your actual use 
case.

> Breadth first is kind of the symetric method of depth first, and find would 
gain in symetry completeness with a bfs like option.
> Unless it would break the code or too complicated ? What do you think ?

The 'find -depth' option does not work like a 100% depth-first algorithm.
Instead, if just ensures, that leaves are processed earlier than their
parents:

  $ find -depth
  ./a/f/g
  ./a/f/h
  ./a/f
  ./a/b/c
  ./a/b/e
  ./a/b
  ./a
  .

There could be any strategy added to walk the tree, but this would add
much bloat to the code.  Look at the code: having the regular and
the -depth alternatives make this matter already complex enough.

You didn't mention it yet - apart from something like "would be nice" -,
so what would be an actual use case for a true depth-first or breadth-first
strategy?

> Regards :-)
> Francois

Have a nice day,
Berny