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

From: Taylor Blau <me@ttaylorr.com>
Date: Jan 19, 2021, 19:09 UTC
Message-ID: <YAcuUDqfvKzfHFMb@nand.local>
In-Reply-To: <CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com>

On Tue, Jan 19, 2021 at 06:42:56PM +0100, Jacob Vosmaer wrote:

Show 12 quoted lines

> Hi Taylor,
>
> Thanks for your reply. That sounds like a great idea!
>
> On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau <me@ttaylorr.com> 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.

Show 6 quoted lines

> 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.

Show 9 quoted lines

> 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).

Show 7 quoted lines

> 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