Re: [RFC PATCH 3/6] dir-iterator: refactor dir_iterator_advance()
- From
- Plato Kiorpelidis <kioplato@gmail.com>
- Date
- Apr 27, 2022, 14:32 UTC
- Message-ID
- <20220427143206.6cqksztbk4exift3@compass>
- In-Reply-To
- <35160d46-d337-2110-f968-238abb7e9f0e@gmail.com>
On 22/04/11 02:26PM, Phillip Wood wrote:
Show 13 quoted lines
> 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.
Show 5 quoted lines
> 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.
Show 5 quoted lines
> 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
Show 5 quoted lines
> Best Wishes > > Phillip > > > [...]