Re: [RFC PATCH 3/6] dir-iterator: refactor dir_iterator_advance()

[Plato Kiorpelidis <kioplato@gmail.com>]

On 22/04/11 02:26PM, Phillip Wood wrote:
> Hi Plato
> 
> On 10/04/2022 12:18, Plato Kiorpelidis wrote:
> > Simplify dir_iterator_advance by switch from iterative to recursive
> > implementation. In each recursive step one action is performed.
> > 
> > This makes dir-iterator easier to work with, understand and introduce
> > new functionality.
> 
> I think that this message could explain a bit more about why it is necessary
> to use a recursive approach. As we are implementing an iterator we cannot
> keep state in the stack between iterations so how does using recursive
> approach help us?

It's not necessary from a functioning perspective. This iterator works on tree
like structures (exception cyclic symlinks), performing pre-order and post-order
traversal on some vertices, in our case directories. Traditionally, these
operations, i.e. pre-order, in-order, post-order, in textbooks, lectures and
online sources are implemented recursively and not iteratively. Therefore it
helps reduce mental load for the reader, since it's easier to follow as it
reminds of the same code paradigm, e.g. post-order:
  * Recurse left child
  * Recurse right child
  * Visit subroot

In general, graph algorithms are more readable when implemented recursively.
In each recursive step a set of instructions are executed and recursion lays out
the code in such a way that these instructions stand out symmetrically for each
recursive step.

As a result, recursive dir-iterator is more maintainable, as its code structure
is more similar to other graph algorithms and to what we're already used to,
than its iterative implementation.

A nice side effect of recursion is that it requires one less indentation depth.
This further simplifies the code.

> I reviewed this series as a way to learn the directory iterator code as I'd
> not looked at it before. Having read the existing code I think the it is
> fairly easy to follow. I'm not sure the changes here improve that. I also
> found these changes harder to follow because they renamed existing functions
> and variables in addition to moving the code around.

Michael Haggerty said that dir-iterator code is quite intricate[1], I agree and
tried to simplify it. My conversion from iterative to recursive implementation
tries to deal with this problem. The proposed advantages are specified above.

> In order in implement returning the directory name after its contents I
> think all we need is to remember whether we've returned the name when we
> readdir() returns NULL so we don't pop it too soon. It's not clear that we
> need a lot of refactoring to do that, especially as the patches you linked
> to in the cover letter seem to avoid that.

It's one more thing we need to keep track of, that's not required and can be
avoided. It further tangles the code, introducing more cases. The recursive
implementation that I propose, does not need to keep track of this information.
Probably there's an equal iterative implementation that also does not need to
keep track of this information.


[1]: https://public-inbox.org/git/7a665631-da6a-4b9f-b9e7-750f2504eccd@alum.mit.edu/

Thanks,
Plato

> Best Wishes
> 
> Phillip
> 
> > [...]