According to http://dlang.org/phobos/std_file.html :

depth
Spans the directory depth-first, i.e. the content of any subdirectory is spanned before that subdirectory itself. Useful e.g. when recursively deleting files.

breadth
Spans the directory breadth-first, i.e. the content of any subdirectory is spanned right after that subdirectory itself.

That's not what breadth-first means at all. See http://en.wikipedia.org/wiki/Tree_traversal which has the correct definition: breadth-first means ALL directories at one level are returned before ANY child of ANY directory is considered.

Wikipedia uses the terms preorder and postorder for what's intended here, but those are a bit obtuse. Something like parentFirst and childrenFirst would get the message across clearly.

I don't much mind what the names change to, but the current completely wrong situation really irks me! Deprecate it at once! :P

Ben :)

On 9/16/12, Ben Davis <entheh@cantab.net> wrote:
> According to http://dlang.org/phobos/std_file.html :
>
> depth
> Spans the directory depth-first, i.e. the content of any subdirectory is
> spanned before that subdirectory itself. Useful e.g. when recursively
> deleting files.
>
> breadth
> Spans the directory breadth-first, i.e. the content of any subdirectory
> is spanned right after that subdirectory itself.

I don't understand why "depth" is used in the first place. If you have "shallow" then the opposite of that is "deep", not "depth". I always make that typo when using spanmode.

On 9/16/12 2:57 PM, Ben Davis wrote:
> According to http://dlang.org/phobos/std_file.html :
>
> depth
> Spans the directory depth-first, i.e. the content of any subdirectory is
> spanned before that subdirectory itself. Useful e.g. when recursively
> deleting files.
>
> breadth
> Spans the directory breadth-first, i.e. the content of any subdirectory
> is spanned right after that subdirectory itself.
>
> That's not what breadth-first means at all. See
> http://en.wikipedia.org/wiki/Tree_traversal which has the correct
> definition: breadth-first means ALL directories at one level are
> returned before ANY child of ANY directory is considered.
>
> Wikipedia uses the terms preorder and postorder for what's intended
> here, but those are a bit obtuse. Something like parentFirst and
> childrenFirst would get the message across clearly.
>
> I don't much mind what the names change to, but the current completely
> wrong situation really irks me! Deprecate it at once! :P
>
> Ben :)

What would be an example illustrating that "breadth" is doing the wrong thing?

Andrei

> What would be an example illustrating that "breadth" is doing the wrong thing?
>
> Andrei

Linux 64bit:

import std.file;
import std.stdio;

void main() {
    mkdir("a");
    mkdir("a/b");
    mkdir("a/c");
    mkdir("a/c/z");
    std.file.write("a/1.txt", "");
    std.file.write("a/2.txt", "");
    std.file.write("a/b/1.txt", "");
    std.file.write("a/b/2.txt", "");
    std.file.write("a/c/1.txt", "");
    std.file.write("a/c/z/1.txt", "");
    foreach(string file; dirEntries("a/", SpanMode.breadth))
        writeln(file);

    rmdirRecurse("a");
    // Expected Approximation
    // a/2.txt
    // a/1.txt
    // a/b
    // a/c
    // a/c/1.txt
    // a/c/z
    // a/c/z/1.txt
    // a/b/1.txt
    // a/b/2.txt
    //
    // Actual
    // a/c
    // a/c/z
    // a/c/z/1.txt
    // a/c/1.txt
    // a/b
    // a/b/2.txt
    // a/b/1.txt
    // a/2.txt
    // a/1.txt
}

On 17-Sep-12 09:30, Jesse Phillips wrote:
>
>> What would be an example illustrating that "breadth" is doing the
>> wrong thing?
>>
>> Andrei
>

Shouldn't be hard to add "true" breadth first then.
Since it's a stack based visitation one just needs to instead use queue (FIFO) and change code so that it puts all directories on given level into the queue and only then picks next one from queue.

>      // Expected Approximation
>      // a/2.txt
>      // a/1.txt
>      // a/b
>      // a/c
>      // a/c/1.txt
>      // a/c/z
>      // a/c/z/1.txt
>      // a/b/1.txt
>      // a/b/2.txt
>      //
>      // Actual
>      // a/c
>      // a/c/z
>      // a/c/z/1.txt
>      // a/c/1.txt
>      // a/b
>      // a/b/2.txt
>      // a/b/1.txt
>      // a/2.txt
>      // a/1.txt

P.S. Sorry for pinging you by mail.
Damn Thunderbird UI caught me by surprise again :(

-- 
Dmitry Olshansky

On 9/17/12 1:30 AM, Jesse Phillips wrote:
>
>> What would be an example illustrating that "breadth" is doing the
>> wrong thing?
>>
>> Andrei
>
> Linux 64bit:
>
> import std.file;
> import std.stdio;
>
> void main() {
> mkdir("a");
> mkdir("a/b");
> mkdir("a/c");
> mkdir("a/c/z");
> std.file.write("a/1.txt", "");
> std.file.write("a/2.txt", "");
> std.file.write("a/b/1.txt", "");
> std.file.write("a/b/2.txt", "");
> std.file.write("a/c/1.txt", "");
> std.file.write("a/c/z/1.txt", "");
> foreach(string file; dirEntries("a/", SpanMode.breadth))
> writeln(file);
>
> rmdirRecurse("a");
> // Expected Approximation
> // a/2.txt
> // a/1.txt
> // a/b
> // a/c
> // a/c/1.txt
> // a/c/z
> // a/c/z/1.txt
> // a/b/1.txt
> // a/b/2.txt
> //
> // Actual
> // a/c
> // a/c/z
> // a/c/z/1.txt
> // a/c/1.txt
> // a/b
> // a/b/2.txt
> // a/b/1.txt
> // a/2.txt
> // a/1.txt
> }
>

Thanks, that does seem to be a bug. Please make sure it's in bugzilla. Probably the best way to go is to adjust the behavior so it matches the specification.

Andrei

On Monday, 17 September 2012 at 18:20:55 UTC, Andrei Alexandrescu wrote:

> Thanks, that does seem to be a bug. Please make sure it's in bugzilla. Probably the best way to go is to adjust the behavior so it matches the specification.
>
> Andrei

I should have noted that I'm using ReiserFS, as it use to fail completely to span subdirs in the past. Anyway. Testing on windows shows a smaller issue.

http://d.puremagic.com/issues/show_bug.cgi?id=8680

Files show before spanning but directories are shown before spanning itself.

a/1.txt
a/2.txt
a/b
a/b\1.txt
a/b\2.txt
a/c
a/c\1.txt
a/c\z
a/c\z\1.txt

I have a feeling most people have missed the point here. Thanks for the example - it's a good one to work with. The 'expected approximation' was a bit of a mix of traversal strategies, so I've snipped it out below and put my own examples. Hope this helps clarify what I was getting at:

On 17/09/2012 06:30, Jesse Phillips wrote:
>
>> What would be an example illustrating that "breadth" is doing the
>> wrong thing?
>>
>> Andrei
>
> Linux 64bit:
>
> import std.file;
> import std.stdio;
>
> void main() {
>      mkdir("a");
>      mkdir("a/b");
>      mkdir("a/c");
>      mkdir("a/c/z");
>      std.file.write("a/1.txt", "");
>      std.file.write("a/2.txt", "");
>      std.file.write("a/b/1.txt", "");
>      std.file.write("a/b/2.txt", "");
>      std.file.write("a/c/1.txt", "");
>      std.file.write("a/c/z/1.txt", "");
>      foreach(string file; dirEntries("a/", SpanMode.breadth))
>          writeln(file);
>
>      rmdirRecurse("a");
[snip]

Here are the CORRECT tree traversal patterns:

Breadth-first (probably never required):
a/b
a/c
a/1.txt
a/2.txt
a/b/1.txt
a/b/2.txt
a/c/z
a/c/1.txt
a/c/z/1.txt
Defining property: number of /'s increases monotonically. Note how the deeper you go, the more spread out the children become. It's ALL children, then ALL grandchildren, then ALL great-grandchildren, etc.

I wouldn't bother implementing breadth-first. It's doubtful that anyone would want it, surely...?

Depth-first search has two useful variants, preorder and postorder.

Preorder depth-first (currently wrongly called SpanMode.breadth):
a/b
a/b/1.txt
a/b/2.txt
a/c
a/c/z
a/c/z/1.txt
a/c/1.txt
a/1.txt
a/2.txt
Defining property: every directory is immediately followed by all its children.

Postorder depth-first (currently only called SpanMode.depth):
a/b/1.txt
a/b/2.txt
a/b
a/c/z/1.txt
a/c/z
a/c/1.txt
a/c
a/1.txt
a/2.txt
Defining property: every directory is immediately *preceded* by all its children.

Going back to the 'actual' output you quoted:

>      // Actual
>      // a/c
>      // a/c/z
>      // a/c/z/1.txt
>      // a/c/1.txt
>      // a/b
>      // a/b/2.txt
>      // a/b/1.txt
>      // a/2.txt
>      // a/1.txt

This looks like a preorder depth-first iteration (albeit with child order reversed at each level). The implementation is correct in that it matches the spec as documented. The problem is that the spec is using the term 'breadth' wrongly.

Here is what I would do to fix it (sorry if I got the syntax wrong):

enum SpanMode {
  shallow,
  preorder,
  postorder;

  @deprecated alias preorder breadth;
  @deprecated alias postorder depth;
}

I initially said that possibly preorder and postorder weren't clear, but they grew on me very quickly. I think people could learn that "preorder means parents first" or "preorder is the one I usually want". Also, these are the standard terms (refer to the Wikipedia link), so once you know them, you can use them for everything, both in and outside of :D.

Thanks,

Ben :)

On 17/09/2012 19:15, Dmitry Olshansky wrote:
>
> On 17-Sep-12 09:30, Jesse Phillips wrote:
>  >
>  >> What would be an example illustrating that "breadth" is doing the
>  >> wrong thing?
>  >>
>  >> Andrei
>  >
>
> Shouldn't be hard to add "true" breadth first then.
> Since it's a stack based visitation one just needs to instead use queue
> (FIFO) and change code so that it puts all directories on given level
> into the queue and only then picks next one from queue.

Yeah, I think that would work for true breadth-first. :)

Doubt anyone actually needs that though...?

On 17/09/2012 19:47, Jesse Phillips wrote:
> On Monday, 17 September 2012 at 18:20:55 UTC, Andrei Alexandrescu wrote:
>
>> Thanks, that does seem to be a bug. Please make sure it's in bugzilla.
>> Probably the best way to go is to adjust the behavior so it matches
>> the specification.
>>
>> Andrei
>
> I should have noted that I'm using ReiserFS, as it use to fail
> completely to span subdirs in the past. Anyway. Testing on windows shows
> a smaller issue.
>
> http://d.puremagic.com/issues/show_bug.cgi?id=8680
>
> Files show before spanning but directories are shown before spanning
> itself.
>
> a/1.txt
> a/2.txt
> a/b
> a/b\1.txt
> a/b\2.txt
> a/c
> a/c\1.txt
> a/c\z
> a/c\z\1.txt

These results also show a correct preorder depth-first search.

The bug report as it stands is misleading; should I post a follow-up on the bug tracker, or should we close it and start again?