Re: [PATCH 09/13] refs: introduce an iterator interface

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: May 31, 2016, 08:45 UTC
Message-ID: <574D4F42.3090807@alum.mit.edu>
In-Reply-To: <xmqqr3ci7o73.fsf@gitster.mtv.corp.google.com>

On 05/31/2016 08:10 AM, Junio C Hamano wrote:

Show 20 quoted lines

> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> This commit introduces a new iteration primitive for references: a
>> ref_iterator. A ref_iterator is a polymorphic object that a reference
>> storage backend can be asked to instantiate. There are three functions
>> that can be applied to a ref_iterator:
>>
>> * ref_iterator_advance(): move to the next reference in the iteration
>> * ref_iterator_abort(): end the iteration before it is exhausted
>> * ref_iterator_peel(): peel the reference currently being looked at
> 
> This part looked somewhat strange in that it makes "peel" sound
> something very special.  Even though I understand why, it made me
> feel uneasy.  I do not think of another operation like peel that may
> want to have such a specialized helper, so I'll let it pass, but the
> primary uneasiness I felt comes from the fact that "iterator-peel"
> is not an essential service of the API that needs for correctness,
> but is a pure optimization (i.e. you could grab a ref from the
> normal iterator call, and then ask "please peel this ref" to the
> usual ref API that does not know anything about iteration).

I agree that this is inelegant. The underlying reason is that the iterator embodies both the iteration and also the reference currently being iterated over. So ref_iterator_advance() and ref_iterator_abort() are really iterator methods, whereas ref_iterator_peel() is really a method on the current reference. For that matter, the refname etc fields are conceptually parts of the current reference, too, not of the iteration.

One of my many coding spikes tried to separate the two concepts by having the iterator give back a separate object representing the reference. That object would have had a peel() method. But I wasn't happy with that approach:

* Anything that made it look like the reference object had a lifetime
independent of that of the iterator seemed like asking for trouble.

* The peel() method would probably have to be a real method that knows
where the reference came from (as opposed to a simple function) because
of things like prefix_ref_iterator, where the refname stored in the
ref_iterator might have had its prefix stripped off.

The complexity level was getting beyond what I felt was tenable in C, so I made the compromise that you see.

If I had more time I'd do some benchmarking to see whether the "peeling" optimization is really still needed. It comes from the days when references were stored in giant lists. Now that we store refs in tries, and each level gets sorted as part of the iteration anyway, the lookup might be fast enough that nobody would care.

> [...]

Michael