Re: [PATCH] ref-filter: format iteratively with lexicographic refname sorting

> On Wed, Oct 16, 2024 at 10:48:28PM -0400, Jeff King wrote:
>> On Wed, Oct 16, 2024 at 06:11:47PM -0400, Taylor Blau wrote:
>>
>> > On Wed, Oct 16, 2024 at 08:00:30AM +0200, Patrick Steinhardt wrote:
>> > > But there is one exception here where we _can_ get away with sorting
>> > > refs while streaming: ref backends sort references returned by their
>> > > iterators in lexicographic order. So if the following conditions are all
>> > > true we can do iterative streaming:
>> > >
>> > >   - The caller uses at most a single name pattern. Otherwise we'd have
>> > >     to sort results from multiple invocations of the iterator.
>> > >
>> > >   - There must be at most a single sorting specification, as otherwise
>> > >     we're not using plain lexicographic ordering.
>> > >
>> > >   - The sorting specification must use the "refname".
>> > >
>> > >   - The sorting specification must not be using any flags, like
>> > >     case-insensitive sorting.
>> >
>> > Perhaps a niche case, but what about ancient packed-refs files that were
>> > written before the 'sorted' capability was introduced?
>>
>> We should be OK there. In that case we actually read in and sort the
>> packed-refs entries ourselves. We have to, since we do an in-order merge
>> with the loose refs while iterating.
>>
>> I do think this optimization is worth doing, and not a problem with our
>> current backends. The biggest worries would be:
>>
>>   1. Some new ref backend that doesn't return sorted results. I find
>>      this unlikely, and anyway it's easily caught by having coverage in
>>      the test suite (which I assume we already have, but I didn't look).
>
> My assumption is that a ref iterator that _isn't_ sorted would lead to
> undesirable behaviour. I'd be surprised if git-show-ref(1) started to
> show refs in a random order. So we have essentially baked the
> requirement that ref iterators return refs in lexicographic order into
> our codebase already.
>
>>   2. Some new flag combination that requires disabling the optimization,
>>      and which must be dealt with in the code. This seems unlikely to me
>>      but not impossible. I think enabling the optimization is worth it,
>>      though.
>
> And this part is an issue with or without my patch. The logic we have
> in the ref-filter API is quite fragile, and everybody who wants to add
> some new flags must remember to update `can_do_iterative_format()`. I'm
> not really a huge fan of that, but on the other hand the subsystem does
> not change all that frequently anyway.
>
>> > >     to sort results from multiple invocations of the iterator.
>>
>> I think this part is erring on the cautious side, as we can often
>> collapse these into a single iteration due to the ref-prefix work. It
>> may be OK to keep using the slower code here if multiple patterns aren't
>> commonly used, but I'd suspect that:
>>
>>   git for-each-ref --sort=refname refs/heads refs/tags
>>
>> could benefit.
>
> Mh. So we do end up using `refs_for_each_fullref_in_prefixes()`, which
> may or may not end up collapsing the prefixes. We do sort and dedup the
> prefixes via `find_longest_prefixes()`, so we don't have to worry about
> e.g. `git for-each-ref refs/tags refs/heads refs/tags`.
>