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

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 [off-list ref] wrote:

quoted

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