Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited

From: Taylor Blau <[email-masked]>
Date: Tue, 19 Jan 2021 14:09:04 -0500

On Tue, Jan 19, 2021 at 06:42:56PM +0100, Jacob Vosmaer wrote:
> Hi Taylor,
>
> Thanks for your reply. That sounds like a great idea!
>
> On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau <[email-masked]> wrote:
> > But, I think that we could get pretty far by treating the prefixes as
> > refs so that we can call ref-filter.c:find_longest_prefixes(). For its
> > purposes, it doesn't really care about whether or not the arguments
> > actually are references. It simply returns the longest common prefix
> > among all of its arguments (delimited by '/' characters).
>
> What does "delimited by /" mean?

Ah, I just meant that it looks for the longest common prefix where it
will only split at '/' characters. But, that's not right at all:
find_longest_prefixes_1() will happily split anywhere there is a
difference.

> Without really understanding the longest common prefix code in
> ref-filter.c, my intuitive concern is that the specifics of glob
> matching and special treatment of '/' may bite us. I suppose we'll be
> fine because ls-refs has its own matching logic. So long as
> for_each_fullref_in_prefixes yield enough prefixes, the end result
> would remain the same.

Right. We can ignore the concern about '/' (seeing my comment above),
and note that find_longest_prefixes_1() breaks on glob metacharacters,
so we'll only match or overmatch the desired set (and we'll never
undermatch).

I made sure to write in the second patch downthread that
ls-refs.c:send_ref() correctly handles receiving too many refs (and it
discards ones that it doesn't want).

> The question is then, does for_each_fullref_in_prefixes yield
> everything we need?

For the reasons above, yes: it will.

> I think my approach would be to expose the new
> for_each_fullref_in_prefixes iterator you propose through test-tool,
> and unit test it so we can be sure it handles both contexts
> (for-each-refs with globs and special '/', and ls-refs without any
> special character behavior) correctly.
>
> I may be overly cautious here, take this with a grain of salt because
> I am not an experienced Git contributor. On that topic, apologies if
> I'm botching my inline replies in this email.

I do appreciate your caution, but I'm not sure exposing a test-tool is
necessary, since we already test this behavior extensively in t6300 (and
now t5701, t5702 and t5704, too).

> Regarding your patch: it works correctly and as fast as expected for
> my development "many refs" test case. Yay! It also segfaults and fails
> some tests but see my comments below.
>
> All in all: thanks, great idea, yes we should reuse, I only lack
> confidence on correctness because I don't fully grasp your
> longest-common-prefix algorithm yet.

:-). Thanks for the pointers on the spots that I had missed (as I
mentioned, I only compiled it before sending, so having an additional
set of more careful eyes was quite helpful).

Thanks,
Taylor