[Issue 8680] SpanMode.breadth is incorrectly named and implementation fails in Linux

[d-bugmail at puremagic.com]

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



--- Comment #10 from entheh at cantab.net 2012-09-22 07:09:23 PDT ---
(In reply to comment #9)
> listdir was deprecated for a very good reason. Would you now kindly consider
> the steps to fold this into a Range.

Oh wow, I didn't realise dirEntries supported bidirectional iteration. That's
interesting. A reverse breadth-first iteration would be a special thing to try
and implement, and I can't see it usefully doing anything other than
precalculating the lot. Reversing the order of files in a shallow iteration is
of questionable use if the sorting of entries isn't defined anyway (I suppose
only if you rely on the order being consistent and call it twice). Reversing
preorder and postorder depth-first will give you postorder and preorder
respectively (along with a reversed child ordering which is meaningless as
above). I wonder if anyone has actually used the reversibility of dirEntries?

If we had the sorting option, here's how I'd see it working (for forward
iteration):
- Always lazily iterate the recursion into subdirectories.
- When sorting is not requested, also lazily iterate each directory's direct
contents.
- When sorting IS requested, each directory's direct contents will need
requesting in a block - OR alternatively, the sort is specified as a set of
parameters which are passed directly to the underlying OS (if the underlying OS
has the corresponding options of course), and then it can still be done lazily.
Actually I have no idea if the current implementations are able to be lazy
within a single directory.

The 'Finish reporting each directory's contents before processing its children'
option (weaker than breadth-first) will not impede laziness, but will require
the directory's subdirectories to be buffered up and remembered (if they aren't
already precalculated).

As for the reverse iteration option - I can see that it was easy to implement
for the existing depth-first options, but it would be annoying to implement for
breadth-first. While it's not impossible to implement, I would view it as
acceptable for reverse breadth-first to be defined as a runtime error.

I don't think I can convert this to code without knowing how the underlying API
looks. I have a feeling it would have to be done separately for different OS's.
But it should be trivial - my main goal was to define the behaviour precisely
enough to avoid misunderstanding, which I think we've done with the latest
pseudocode? You didn't say explicitly if you want both the options I suggested,
but I guess you like the first one (where you buffer up a directory's
subdirectories and then process them once you've finished that directory's
direct contents)?

What I can do is propose an API that I think covers all the use cases:

enum SpanMode {
  shallow,                  ///f1, d1, d2, f2
  depthFirstPreorder,       ///f1, d1, d1/sd, d1/sd/sf, d2, d2/sd, d2/sd/sf, f2
  depthFirstPostorder,      ///f1, d1/sd/sf, d1/sd, d1, d2/sd/sf, d2/sd, d2, f2
  contiguousLevelsPreorder, ///f1, d1, d2, f2, d1/sd, d1/sd/sf, d2/sd, d2/sd/sf
  contiguousLevelsPostorder,///d1/sd/sf, d1/sd, d2/sd/sf, d2/sd, f1, d1, d2, f2
  breadthFirst,             ///f1, d1, d2, f2, d1/sd, d2/sd, d1/sd/sf, d2/sd/sf

  //This syntax apparently isn't supported yet...
  @deprecated breadth = depthFirstPreorder,
  @deprecated depth = depthFirstPostorder,
}

///If supplied, levelSorter is applied to the whole result in case of
'shallow',
///otherwise each 'shallow' result computed internally along the way.
///Note that supplying a levelSorter may impede the algorithm's laziness.

auto dirEntries(string path, SpanMode mode, bool followSymlink = true, void
delegate(T[]) levelSorter = null);  //T being string or DirEntry, ideally put
in caller's control if possible

> We can implement any traversal with shallow, why bother adding depth and
> breadth or anything else?
> 
> I'm very glade you have brought up the naming and implementation issue as I am
> relying on a behavior which isn't defined, and now I can plan to correct this.
> But it would be nice if the standard library included the use case I would be
> using.

Agreed, provided it can be done in a way that's simple to understand. I shied
away from it earlier because I couldn't think of decent names and I thought it
would do more harm than good if the names were bad. But I think
contiguousLevels is clear.

> > For the sorting case, I was merely suggesting that the sort could be put
> > in the user's control, so they can sort alphabetically or by timestamp or
> > however they want.
> 
> With those examples I see this as a very useful addition. Just not supporting
> the traversal I use.

Incorporated above :)

> > So the above options can be reversed in all possible permutations to give what
> > you want here.
> 
> And that is even easier if the traversal is already a range.

Well you say that, but... foreach_reverse simultaneously reverses the file
order in addition to the preorder/postorder distinction, and you might only
want to reverse one of those properties. I'm not sure people will realistically
use foreach_reverse very much (except maybe with SpanMode.shallow and a sorter,
or on an OS that provides useful sorting by default).

> This argument applies to so many languages that I hope you reconsider your
> position "it can be done with primitives already." Why did you use foreach? Do
> we really need the function we have goto.

No, my point was that features are only valuable if they're easy to understand,
and I was merely struggling to think of an API that made them easy to
understand. :)

(Poor devs who end up fixing this bug - it now contains a very long discussion
and a multitude of separate requests, from 'names are wrong' to several new
feature requests! Sorry ><)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------