Re: [PATCH 12/16] mktree: use iterator struct to add tree entries to index

[Victoria Dye <vdye@github.com>]

Patrick Steinhardt wrote:
> On Tue, Jun 11, 2024 at 06:24:44PM +0000, Victoria Dye via GitGitGadget wrote:
>> From: Victoria Dye <vdye@github.com>
>>
>> Create 'struct tree_entry_iterator' to manage iteration through a 'struct
>> tree_entry_array'. Using an iterator allows for conditional iteration; this
>> functionality will be necessary in later commits when performing parallel
>> iteration through multiple sets of tree entries.
>>
>> Signed-off-by: Victoria Dye <vdye@github.com>
>> ---
>>  builtin/mktree.c | 40 +++++++++++++++++++++++++++++++++++++---
>>  1 file changed, 37 insertions(+), 3 deletions(-)
>>
>> diff --git a/builtin/mktree.c b/builtin/mktree.c
>> index 12f68187221..bee359e9978 100644
>> --- a/builtin/mktree.c
>> +++ b/builtin/mktree.c
>> @@ -137,6 +137,38 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
>>  	QSORT_S(arr->entries, arr->nr, ent_compare, &ignore_mode);
>>  }
>>  
>> +struct tree_entry_iterator {
>> +	struct tree_entry *current;
>> +
>> +	/* private */
>> +	struct {
>> +		struct tree_entry_array *arr;
>> +		size_t idx;
>> +	} priv;
>> +};
>> +
>> +static void init_tree_entry_iterator(struct tree_entry_iterator *iter,
>> +				     struct tree_entry_array *arr)
>> +{
>> +	iter->priv.arr = arr;
>> +	iter->priv.idx = 0;
>> +	iter->current = 0 < arr->nr ? arr->entries[0] : NULL;
>> +}
> 
> Nit: Same comment as before, I think these should rather be named
> `tree_entry_iterator_init()` and `tree_entry_iterator_advance()`.

That works for me. I'm not attached to the naming convention I used and your
justification for changing it in [1] is reasonable.

[1] https://lore.kernel.org/git/ZmltDQ5SlVvrEDGP@tanuki/

>> +/*
>> + * Advance the tree entry iterator to the next entry in the array. If no entries
>> + * remain, 'current' is set to NULL. Returns the previous 'current' value of the
>> + * iterator.
>> + */
>> +static struct tree_entry *advance_tree_entry_iterator(struct tree_entry_iterator *iter)
>> +{
>> +	struct tree_entry *prev = iter->current;
>> +	iter->current = (iter->priv.idx + 1) < iter->priv.arr->nr
>> +			? iter->priv.arr->entries[++iter->priv.idx]
>> +			: NULL;
>> +	return prev;
>> +}
> 
> I think it's somewhat confusing to have this return a different value
> than `current`. When I call `next()`, then I expect the iterator to
> return the next item. And after having called `next()`, I expect that
> the current value is the one that the previous call to `next()` has
> returned.

I do see how it's confusing. I was attempting to mimic the various
array/stack "pop" methods throughout the codebase (which return the "popped"
value while moving the stack pointer), but that doesn't really work here
with an iterator. 

The only real benefit of this was that it simplified a loop somewhere later
on, but not by a ton. I'll drop the 'tree_entry *' return value from the
method and access 'iter->current' directly where it's needed.

> To avoid confusion, I'd propose to get rid of the `current` member
> altogether. It's not needed as we already save the current index and
> avoids the confusion.

The idea of the iterator is to have callers only ever reference the
'current' value to avoid needing to deal with the array & current index
directly; I find that it majorly simplifies the parallel iteration through
the base tree and entry array in [2]. IOW, in a language with support for
it, 'idx' would be private & 'current' would be public. So I would like to
keep the 'current' value as the publicly-accessible way of interacting with
the iterator (although, as mentioned above, I'm happy to drop it from the
'advance' method return value).

[2] https://lore.kernel.org/git/df0c50dfea3cb77e0070246efdf7a3f070b2ad97.1718130288.git.gitgitgadget@gmail.com/

> 
> Patrick