# [PATCH 0/2] ls-refs: only traverse through longest common ref prefix 27 messages from 2021-01-19 to 2021-01-25. Participants: Taylor Blau, Jacob Vosmaer, Jeff King, Junio C Hamano. Thread: https://gitlist.dev/t/55010 ## Taylor Blau, 2021-01-19 18:19 Subject: [PATCH 0/2] ls-refs: only traverse through longest common ref prefix Message-ID: URL: https://gitlist.dev/e/cover.1611080326.git.me%40ttaylorr.com In-Reply-To: ``` Here is a series inspired by Jacob Vosmaer's recent patch to only traverse once through the longest common prefix of given ref-prefixes in ls-refs. Instead of a hand-rolled implementation, this uses the one written back in b31e2680c4 (ref-filter.c: find disjoint pattern prefixes, 2019-06-26). The first patch exposes that algorithm in refs.h, and the second patch uses the new function. If Jacob is happy with this direction, I'd suggest that we use this series as a replacement for his patch. Thanks in advance for your review. Taylor Blau (2): refs: expose 'for_each_fullref_in_prefixes' ls-refs.c: traverse longest common ref prefix ls-refs.c | 6 +++- ref-filter.c | 74 ++------------------------------------------ refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++ refs.h | 7 +++++ 4 files changed, 101 insertions(+), 73 deletions(-) -- 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-19 18:19 Subject: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Message-ID: URL: https://gitlist.dev/e/fb8681d12864d724108c524834f9498d91e270e6.1611080326.git.me%40ttaylorr.com In-Reply-To: ``` ls-refs performs a single revision walk over the whole ref namespace, and sends ones that match with one of the given ref prefixes down to the user. This can be expensive if there are many refs overall, but the portion of them covered by the given prefixes is small by comparison. To attempt to reduce the difference between the number of refs traversed, and the number of refs sent, only traverse references which are in the longest common prefix of the given prefixes. This is very reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find disjoint pattern prefixes, 2019-06-26) which does an analogous thing for multi-patterned 'git for-each-ref' invocations. The only difference here is that we are operating on ref prefixes, which do not necessarily point to a single reference. That is just fine, since all we care about is finding the longest common prefix among prefixes which can be thought of as refspecs for our purposes here. Similarly, for_each_fullref_in_prefixes may return more results than the caller asked for (since the longest common prefix might match something that a longer prefix in the same set wouldn't match) but ls-refs.c:send_ref() discards such results. The code introduced in b31e2680c4 is resilient to stop early (and return a shorter prefix) when it encounters a metacharacter (as mentioned in that patch, there is some opportunity to improve this, but nobody has done it). There are two remaining small items in this patch: - If no prefixes were provided, then implicitly add the empty string (which will match all references). - Since we are manually munging the prefixes, make sure that we initialize it ourselves (previously this wasn't necessary since the first strvec_push would do so). Original-patch-by: Jacob Vosmaer Signed-off-by: Taylor Blau --- ls-refs.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/ls-refs.c b/ls-refs.c index a1e0b473e4..eaaa36d0df 100644 --- a/ls-refs.c +++ b/ls-refs.c @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys, struct ls_refs_data data; memset(&data, 0, sizeof(data)); + strvec_init(&data.prefixes); git_config(ls_refs_config, NULL); @@ -109,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys, die(_("expected flush after ls-refs arguments")); head_ref_namespaced(send_ref, &data); - for_each_namespaced_ref(send_ref, &data); + if (!data.prefixes.nr) + strvec_push(&data.prefixes, ""); + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v, + send_ref, &data, 0); packet_flush(1); strvec_clear(&data.prefixes); return 0; -- 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-19 18:19 Subject: [PATCH 1/2] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/d4c8d059f676764a1eb1eaed718c93564aabfa37.1611080326.git.me%40ttaylorr.com In-Reply-To: ``` This function was used in the ref-filter.c code to find the longest common prefix of among a set of refspecs, and then to iterate all of the references that descend from that prefix. The subsequent patch will want to use that same code from ls-refs, so prepare by exposing and moving it to refs.c. Since there is nothing specific to the ref-filter code here (other than that it was previously the only caller of this function), this really belongs in the more generic refs.h header. Signed-off-by: Taylor Blau --- ref-filter.c | 74 ++------------------------------------------ refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++ refs.h | 7 +++++ 3 files changed, 96 insertions(+), 72 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index aa260bfd09..f918f00151 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -1929,64 +1929,6 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname) return match_pattern(filter, refname); } -static int qsort_strcmp(const void *va, const void *vb) -{ - const char *a = *(const char **)va; - const char *b = *(const char **)vb; - - return strcmp(a, b); -} - -static void find_longest_prefixes_1(struct string_list *out, - struct strbuf *prefix, - const char **patterns, size_t nr) -{ - size_t i; - - for (i = 0; i < nr; i++) { - char c = patterns[i][prefix->len]; - if (!c || is_glob_special(c)) { - string_list_append(out, prefix->buf); - return; - } - } - - i = 0; - while (i < nr) { - size_t end; - - /* - * Set "end" to the index of the element _after_ the last one - * in our group. - */ - for (end = i + 1; end < nr; end++) { - if (patterns[i][prefix->len] != patterns[end][prefix->len]) - break; - } - - strbuf_addch(prefix, patterns[i][prefix->len]); - find_longest_prefixes_1(out, prefix, patterns + i, end - i); - strbuf_setlen(prefix, prefix->len - 1); - - i = end; - } -} - -static void find_longest_prefixes(struct string_list *out, - const char **patterns) -{ - struct strvec sorted = STRVEC_INIT; - struct strbuf prefix = STRBUF_INIT; - - strvec_pushv(&sorted, patterns); - QSORT(sorted.v, sorted.nr, qsort_strcmp); - - find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr); - - strvec_clear(&sorted); - strbuf_release(&prefix); -} - /* * This is the same as for_each_fullref_in(), but it tries to iterate * only over the patterns we'll care about. Note that it _doesn't_ do a full @@ -1997,10 +1939,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, void *cb_data, int broken) { - struct string_list prefixes = STRING_LIST_INIT_DUP; - struct string_list_item *prefix; - int ret; - if (!filter->match_as_path) { /* * in this case, the patterns are applied after @@ -2024,16 +1962,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, return for_each_fullref_in("", cb, cb_data, broken); } - find_longest_prefixes(&prefixes, filter->name_patterns); - - for_each_string_list_item(prefix, &prefixes) { - ret = for_each_fullref_in(prefix->string, cb, cb_data, broken); - if (ret) - break; - } - - string_list_clear(&prefixes, 0); - return ret; + return for_each_fullref_in_prefixes(NULL, filter->name_patterns, + cb, cb_data, broken); } /* diff --git a/refs.c b/refs.c index 13dc2c3291..0b5a68588f 100644 --- a/refs.c +++ b/refs.c @@ -1546,6 +1546,93 @@ int for_each_rawref(each_ref_fn fn, void *cb_data) return refs_for_each_rawref(get_main_ref_store(the_repository), fn, cb_data); } +static int qsort_strcmp(const void *va, const void *vb) +{ + const char *a = *(const char **)va; + const char *b = *(const char **)vb; + + return strcmp(a, b); +} + +static void find_longest_prefixes_1(struct string_list *out, + struct strbuf *prefix, + const char **patterns, size_t nr) +{ + size_t i; + + for (i = 0; i < nr; i++) { + char c = patterns[i][prefix->len]; + if (!c || is_glob_special(c)) { + string_list_append(out, prefix->buf); + return; + } + } + + i = 0; + while (i < nr) { + size_t end; + + /* + * Set "end" to the index of the element _after_ the last one + * in our group. + */ + for (end = i + 1; end < nr; end++) { + if (patterns[i][prefix->len] != patterns[end][prefix->len]) + break; + } + + strbuf_addch(prefix, patterns[i][prefix->len]); + find_longest_prefixes_1(out, prefix, patterns + i, end - i); + strbuf_setlen(prefix, prefix->len - 1); + + i = end; + } +} + +static void find_longest_prefixes(struct string_list *out, + const char **patterns) +{ + struct strvec sorted = STRVEC_INIT; + struct strbuf prefix = STRBUF_INIT; + + strvec_pushv(&sorted, patterns); + QSORT(sorted.v, sorted.nr, qsort_strcmp); + + find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr); + + strvec_clear(&sorted); + strbuf_release(&prefix); +} + +int for_each_fullref_in_prefixes(const char *namespace, + const char **patterns, + each_ref_fn fn, void *cb_data, + unsigned int broken) +{ + struct string_list prefixes = STRING_LIST_INIT_DUP; + struct string_list_item *prefix; + struct strbuf buf = STRBUF_INIT; + int ret = 0, namespace_len; + + find_longest_prefixes(&prefixes, patterns); + + if (namespace) + strbuf_addstr(&buf, namespace); + namespace_len = buf.len; + + for_each_string_list_item(prefix, &prefixes) { + strbuf_addf(&buf, "%s", prefix->string); + ret = for_each_fullref_in(buf.buf, fn, cb_data, broken); + if (ret) + break; + strbuf_setlen(&buf, namespace_len); + } + + string_list_clear(&prefixes, 0); + strbuf_release(&buf); + return ret; +} + static int refs_read_special_head(struct ref_store *ref_store, const char *refname, struct object_id *oid, struct strbuf *referent, unsigned int *type) diff --git a/refs.h b/refs.h index ff05d2e9fe..e88a794ee6 100644 --- a/refs.h +++ b/refs.h @@ -347,6 +347,13 @@ int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix, int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data, unsigned int broken); +/** + * iterate all refs which are descendent from the longest common prefix among + * the list "patterns". + */ +int for_each_fullref_in_prefixes(const char *namespace, const char **patterns, + each_ref_fn fn, void *cb_data, + unsigned int broken); /** * iterate refs from the respective area. */ -- 2.30.0.138.g6d7191ea01 ``` ## Jacob Vosmaer, 2021-01-19 17:42 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/CADMWQoPREhirr%2BRJPkJJV2U%2B8VG%3DDFotvTBCDSXFhn-3pn2X-A%40mail.gmail.com In-Reply-To: ``` Hi Taylor, Thanks for your reply. That sounds like a great idea! On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau 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? 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. The question is then, does for_each_fullref_in_prefixes yield everything we need? 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. 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. Cheers, Jacob > --- >8 --- > > Subject: [PATCH] ls-refs: iterate longest common refs prefix > > Signed-off-by: Taylor Blau > --- > ls-refs.c | 4 +++- > ref-filter.c | 46 ++++++++++++++++++++++++++++++++-------------- > ref-filter.h | 10 ++++++++++ > 3 files changed, 45 insertions(+), 15 deletions(-) > > diff --git a/ls-refs.c b/ls-refs.c > index a1e0b473e4..6a3e11d45c 100644 > --- a/ls-refs.c > +++ b/ls-refs.c > @@ -6,6 +6,7 @@ > #include "ls-refs.h" > #include "pkt-line.h" > #include "config.h" > +#include "ref-filter.h" > > /* > * Check if one of the prefixes is a prefix of the ref. > @@ -109,7 +110,8 @@ int ls_refs(struct repository *r, struct strvec *keys, > die(_("expected flush after ls-refs arguments")); > > head_ref_namespaced(send_ref, &data); > - for_each_namespaced_ref(send_ref, &data); > + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v, > + send_ref, &data, 0); Remember to add that strvec_init(&data.prefixes) I talked about in my commit message, or you get a segfault. You also need: if (!data.prefixes.nr) strvec_push(&data.prefixes, "refs/"); Without it, the "ls-refs without ref-prefix" scenario fails. > packet_flush(1); > strvec_clear(&data.prefixes); > return 0; > diff --git a/ref-filter.c b/ref-filter.c > index aa260bfd09..c34bf34d06 100644 > --- a/ref-filter.c > +++ b/ref-filter.c > @@ -1987,6 +1987,36 @@ static void find_longest_prefixes(struct string_list *out, > strbuf_release(&prefix); > } > > +int for_each_fullref_in_prefixes(const char *namespace, > + const char **patterns, > + each_ref_fn cb, > + void *cb_data, > + int broken) > +{ > + struct string_list prefixes = STRING_LIST_INIT_DUP; > + struct string_list_item *prefix; > + struct strbuf buf = STRBUF_INIT; > + int ret = 0, namespace_len; > + > + find_longest_prefixes(&prefixes, patterns); > + > + if (namespace) > + strbuf_addstr(&buf, namespace); > + namespace_len = buf.len; > + > + for_each_string_list_item(prefix, &prefixes) { > + strbuf_addf(&buf, prefix->string); Missing format string "%s". > + ret = for_each_fullref_in(buf.buf, cb, cb_data, broken); > + if (ret) > + break; > + strbuf_setlen(&buf, namespace_len); > + } > + > + string_list_clear(&prefixes, 0); > + strbuf_release(&buf); > + return ret; > +} > + > /* > * This is the same as for_each_fullref_in(), but it tries to iterate > * only over the patterns we'll care about. Note that it _doesn't_ do a full > @@ -1997,10 +2027,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, > void *cb_data, > int broken) > { > - struct string_list prefixes = STRING_LIST_INIT_DUP; > - struct string_list_item *prefix; > - int ret; > - > if (!filter->match_as_path) { > /* > * in this case, the patterns are applied after > @@ -2024,16 +2050,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, > return for_each_fullref_in("", cb, cb_data, broken); > } > > - find_longest_prefixes(&prefixes, filter->name_patterns); > - > - for_each_string_list_item(prefix, &prefixes) { > - ret = for_each_fullref_in(prefix->string, cb, cb_data, broken); > - if (ret) > - break; > - } > - > - string_list_clear(&prefixes, 0); > - return ret; > + return for_each_fullref_in_prefixes(NULL, filter->name_patterns, > + cb, cb_data, broken); > } > > /* > diff --git a/ref-filter.h b/ref-filter.h > index feaef4a8fd..f666a0fb49 100644 > --- a/ref-filter.h > +++ b/ref-filter.h > @@ -146,4 +146,14 @@ struct ref_array_item *ref_array_push(struct ref_array *array, > const char *refname, > const struct object_id *oid); > > +/** > + * iterate all refs which descend from the longest common prefix among > + * "patterns". > + */ > +int for_each_fullref_in_prefixes(const char *namespace, > + const char **patterns, > + each_ref_fn cb, > + void *cb_data, > + int broken); > + > #endif /* REF_FILTER_H */ > -- > 2.30.0.138.g6d7191ea01 > ``` ## Taylor Blau, 2021-01-19 19:09 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAcuUDqfvKzfHFMb%40nand.local In-Reply-To: ``` 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 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 ``` ## Jeff King, 2021-01-19 21:59 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdWNgF75QEYFLA7%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 02:09:04PM -0500, Taylor Blau wrote: > > 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. Right. We thought in early revisions of the ref-filter work that we might have to split on path components, but it turns out that the underlying ref code is happy to take arbitrary prefixes. And it's that code which defines our strategy; Even if the ls-refs code wanted to allow only full path components, it should be using the limiting from for_each_ref_in() only as an optimization, and applying its own filtering to the output. > > 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). Yeah, I think the glob-handling is OK for that reason. We'd have a smaller prefix, which means seeing more refs. So it's never a correctness issue, but only a potential optimization one (we consider more refs in ls-refs.c than we might otherwise). But I think even that s impossible, because the glob characters are not valid in refnames. So we would never see one at all in a string which is meant to be a pure prefix. > > 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). Agreed. test-tool is fine when we have no way to easily feed data to a unit. But in this case, the prefix code is easy to test via the for-each-ref plumbing. We'd want to make sure the new setting in ls-refs is covered, too, but I agree that t5701 covers that well (regular fetches make sure we don't send too few refs, but those ones check that we limited the refs in the expected way). -Peff ``` ## Jeff King, 2021-01-19 22:15 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdaAsP6vCQla%2FAr%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 04:59:18PM -0500, Jeff King wrote: > > > 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. > > Right. We thought in early revisions of the ref-filter work that we > might have to split on path components, but it turns out that the > underlying ref code is happy to take arbitrary prefixes. And it's that > code which defines our strategy; Even if the ls-refs code wanted to > allow only full path components, it should be using the limiting from > for_each_ref_in() only as an optimization, and applying its own > filtering to the output. Having now looked carefully at the ls-refs code, it's a pure prefix-match, too. So I think we _could_ rely on for_each_fullref_in() returning us the correct full results, and not checking it further in send_ref(). But I kind of like keeping it there as an extra check (and one which could in theory grow more logic later). -Peff ``` ## Taylor Blau, 2021-01-19 22:23 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdb6GmVXWLEGkP1%40nand.local In-Reply-To: ``` On Tue, Jan 19, 2021 at 05:15:30PM -0500, Jeff King wrote: > On Tue, Jan 19, 2021 at 04:59:18PM -0500, Jeff King wrote: > > > > > 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. > > > > Right. We thought in early revisions of the ref-filter work that we > > might have to split on path components, but it turns out that the > > underlying ref code is happy to take arbitrary prefixes. And it's that > > code which defines our strategy; Even if the ls-refs code wanted to > > allow only full path components, it should be using the limiting from > > for_each_ref_in() only as an optimization, and applying its own > > filtering to the output. > > Having now looked carefully at the ls-refs code, it's a pure > prefix-match, too. So I think we _could_ rely on for_each_fullref_in() > returning us the correct full results, and not checking it further in > send_ref(). But I kind of like keeping it there as an extra check (and > one which could in theory grow more logic later). Hmm. What if the caller asks for: ref-prefix refs/tags/a ref-prefix refs/tags/b ? The LCP between those two is refs/tags, so send_ref() will presumably get lots of reuslts that it doesn't care about (assuming there are tags besides a and b). Thanks, Taylor ``` ## Jeff King, 2021-01-19 22:52 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdik%2Bz5yj2XU0ti%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 05:23:36PM -0500, Taylor Blau wrote: > > Having now looked carefully at the ls-refs code, it's a pure > > prefix-match, too. So I think we _could_ rely on for_each_fullref_in() > > returning us the correct full results, and not checking it further in > > send_ref(). But I kind of like keeping it there as an extra check (and > > one which could in theory grow more logic later). > > Hmm. What if the caller asks for: > > ref-prefix refs/tags/a > ref-prefix refs/tags/b > > ? > > The LCP between those two is refs/tags, so send_ref() will presumably > get lots of reuslts that it doesn't care about (assuming there are tags > besides a and b). Oh, you're right, of course. Ignore me. :) -Peff ``` ## Jeff King, 2021-01-19 22:59 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdkVkXOnpDy28h2%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 05:52:04PM -0500, Jeff King wrote: > On Tue, Jan 19, 2021 at 05:23:36PM -0500, Taylor Blau wrote: > > > > Having now looked carefully at the ls-refs code, it's a pure > > > prefix-match, too. So I think we _could_ rely on for_each_fullref_in() > > > returning us the correct full results, and not checking it further in > > > send_ref(). But I kind of like keeping it there as an extra check (and > > > one which could in theory grow more logic later). > > > > Hmm. What if the caller asks for: > > > > ref-prefix refs/tags/a > > ref-prefix refs/tags/b > > > > ? > > > > The LCP between those two is refs/tags, so send_ref() will presumably > > get lots of reuslts that it doesn't care about (assuming there are tags > > besides a and b). > > Oh, you're right, of course. Ignore me. :) Actually, I am not sure that we would look for "refs/tags/" in that case (I did a quick test and we do not seem to). Which makes sense, as it is cheaper to find the "a" and "b" hierarchies separately if there is a very big "refs/tags/c" hierarchy. But I agree that this is a good reason that callers should consider it as an optimization which could return more results than expected. -Peff ``` ## Taylor Blau, 2021-01-19 23:02 Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited Message-ID: URL: https://gitlist.dev/e/YAdlGMv3EC1ORUew%40nand.local In-Reply-To: ``` On Tue, Jan 19, 2021 at 05:59:34PM -0500, Jeff King wrote: > Actually, I am not sure that we would look for "refs/tags/" in that case > (I did a quick test and we do not seem to). Which makes sense, as it is > cheaper to find the "a" and "b" hierarchies separately if there is a > very big "refs/tags/c" hierarchy. Ah, makes sense. Thanks for double checking. > But I agree that this is a good reason that callers should consider it > as an optimization which could return more results than expected. Yep. Even though I couldn't quite remember when the algorithm would split without looking more closely, I made sure to document that it iterates *all* references that are descendent of the LCP of its arguments. > -Peff Thanks, Taylor ``` ## Jeff King, 2021-01-19 23:09 Subject: Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Message-ID: URL: https://gitlist.dev/e/YAdmtgUPiGUaXiRX%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 01:19:17PM -0500, Taylor Blau wrote: > To attempt to reduce the difference between the number of refs > traversed, and the number of refs sent, only traverse references which > are in the longest common prefix of the given prefixes. This is very > reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find > disjoint pattern prefixes, 2019-06-26) which does an analogous thing for > multi-patterned 'git for-each-ref' invocations. > > The only difference here is that we are operating on ref prefixes, which > do not necessarily point to a single reference. That is just fine, since > all we care about is finding the longest common prefix among prefixes > which can be thought of as refspecs for our purposes here. This second paragraph confused me. Aren't the inputs to for-each-ref also prefixes? I guess they require an explicit '*', but fundamentally it's the same concept (and certainly they are not just single references). > Similarly, for_each_fullref_in_prefixes may return more results than the > caller asked for (since the longest common prefix might match something > that a longer prefix in the same set wouldn't match) but > ls-refs.c:send_ref() discards such results. Based on my other poking, I'm not entirely sure that we can return too many results. But I do think it's worth keeping the caller more careful. > The code introduced in b31e2680c4 is resilient to stop early (and > return a shorter prefix) when it encounters a metacharacter (as > mentioned in that patch, there is some opportunity to improve this, but > nobody has done it). I agree that is how b31e2680c4 works, but we don't care about that behavior here, since we have strict prefixes. Isn't the argument we need to make the other way? I.e., that stopping early on a metacharacter will not hurt us. Because at worst we return too many results (hey, there's a case!) and because we would not expect metacharacters in the prefixes anyway, as they are illegal in refnames. > There are two remaining small items in this patch: > > - If no prefixes were provided, then implicitly add the empty string > (which will match all references). I wonder if for_each_fullref_in_prefixes() should do that, since that is exactly what the other caller does, too. OTOH, maybe it is better to make the callers be more explicit. In which case should it maybe BUG() on an empty set of prefixes, rather than letting the caller assume some behavior? > - Since we are manually munging the prefixes, make sure that we > initialize it ourselves (previously this wasn't necessary since the > first strvec_push would do so). I think this was an existing bug (that we were just lucky it was impossible to trigger, because nobody looked for the NULL sentinel), and would make more sense as a separate fix. -Peff ``` ## Taylor Blau, 2021-01-19 23:52 Subject: Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Message-ID: URL: https://gitlist.dev/e/YAdwvzQCGc5TfXTF%40nand.local In-Reply-To: ``` On Tue, Jan 19, 2021 at 06:09:42PM -0500, Jeff King wrote: > On Tue, Jan 19, 2021 at 01:19:17PM -0500, Taylor Blau wrote: > > > To attempt to reduce the difference between the number of refs > > traversed, and the number of refs sent, only traverse references which > > are in the longest common prefix of the given prefixes. This is very > > reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find > > disjoint pattern prefixes, 2019-06-26) which does an analogous thing for > > multi-patterned 'git for-each-ref' invocations. > > > > The only difference here is that we are operating on ref prefixes, which > > do not necessarily point to a single reference. That is just fine, since > > all we care about is finding the longest common prefix among prefixes > > which can be thought of as refspecs for our purposes here. > > This second paragraph confused me. Aren't the inputs to for-each-ref > also prefixes? > > I guess they require an explicit '*', but fundamentally it's the same > concept (and certainly they are not just single references). Yeah, that is the point that I was trying to make. But re-reading this patch after knowing that it confused you, I think the clearest way to make that point is to drop that second paragraph entirely. > > Similarly, for_each_fullref_in_prefixes may return more results than the > > caller asked for (since the longest common prefix might match something > > that a longer prefix in the same set wouldn't match) but > > ls-refs.c:send_ref() discards such results. > > Based on my other poking, I'm not entirely sure that we can return too > many results. But I do think it's worth keeping the caller more careful. It can return more results, but I don't think that my writing in b31e2680c4 is particularly clear. Here's an example, though. Say I ask for `git for-each-refs 'refs/tags/a/*' 'refs/tags/a/b/c'`. The LCP of that is definitely "refs/tags/a", which might traverse other stuff like "refs/tags/a/b/d", which wouldn't get matched by either. > > The code introduced in b31e2680c4 is resilient to stop early (and > > return a shorter prefix) when it encounters a metacharacter (as > > mentioned in that patch, there is some opportunity to improve this, but > > nobody has done it). > > I agree that is how b31e2680c4 works, but we don't care about that > behavior here, since we have strict prefixes. Isn't the argument we need > to make the other way? I.e., that stopping early on a metacharacter will > not hurt us. Because at worst we return too many results (hey, there's a > case!) and because we would not expect metacharacters in the prefixes > anyway, as they are illegal in refnames. Yeah, thinking on it more I agree that's the argument we should be making here. I updated the patch to reflect it. > > There are two remaining small items in this patch: > > > > - If no prefixes were provided, then implicitly add the empty string > > (which will match all references). > > I wonder if for_each_fullref_in_prefixes() should do that, since that is > exactly what the other caller does, too. OTOH, maybe it is better to > make the callers be more explicit. In which case should it maybe BUG() > on an empty set of prefixes, rather than letting the caller assume some > behavior? Hmm. I don't feel strongly either way, but I think that the BUG is probably the most sensible option. > > - Since we are manually munging the prefixes, make sure that we > > initialize it ourselves (previously this wasn't necessary since the > > first strvec_push would do so). > > I think this was an existing bug (that we were just lucky it was > impossible to trigger, because nobody looked for the NULL sentinel), and > would make more sense as a separate fix. Right. I'll make sure to pull this one out into a separate patch and credit Jacob with authorship. > -Peff Thanks, Taylor ``` ## Jeff King, 2021-01-20 00:08 Subject: Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Message-ID: URL: https://gitlist.dev/e/YAd0kyBP8LRSEBYw%40coredump.intra.peff.net In-Reply-To: ``` On Tue, Jan 19, 2021 at 06:52:31PM -0500, Taylor Blau wrote: > > I guess they require an explicit '*', but fundamentally it's the same > > concept (and certainly they are not just single references). > > Yeah, that is the point that I was trying to make. But re-reading this > patch after knowing that it confused you, I think the clearest way to > make that point is to drop that second paragraph entirely. Sounds good. > > Based on my other poking, I'm not entirely sure that we can return too > > many results. But I do think it's worth keeping the caller more careful. > > It can return more results, but I don't think that my writing in > b31e2680c4 is particularly clear. Here's an example, though. Say I ask > for `git for-each-refs 'refs/tags/a/*' 'refs/tags/a/b/c'`. The LCP of > that is definitely "refs/tags/a", which might traverse other stuff like > "refs/tags/a/b/d", which wouldn't get matched by either. I thought that would be matched by refs/tags/a/*, but it looks like for-each-ref treats "*" as matching only a single path component. So really just: git for-each-ref refs/tags/* requires extra filtering already. But AFAICT none of that is true for ls-refs, which is strictly prefix matching already. -Peff ``` ## Jacob Vosmaer, 2021-01-20 11:00 Subject: Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Message-ID: URL: https://gitlist.dev/e/CADMWQoO%2B163mJBXctb%2BGHFebGCbKQRPAtMJ676_GwfEt-BedAw%40mail.gmail.com In-Reply-To: ``` On Tue, Jan 19, 2021 at 7:19 PM Taylor Blau wrote: > > ls-refs performs a single revision walk over the whole ref namespace, > and sends ones that match with one of the given ref prefixes down to the > user. > > This can be expensive if there are many refs overall, but the portion of > them covered by the given prefixes is small by comparison. > > To attempt to reduce the difference between the number of refs > traversed, and the number of refs sent, only traverse references which > are in the longest common prefix of the given prefixes. This is very > reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find > disjoint pattern prefixes, 2019-06-26) which does an analogous thing for > multi-patterned 'git for-each-ref' invocations. > > The only difference here is that we are operating on ref prefixes, which > do not necessarily point to a single reference. That is just fine, since > all we care about is finding the longest common prefix among prefixes > which can be thought of as refspecs for our purposes here. > > Similarly, for_each_fullref_in_prefixes may return more results than the > caller asked for (since the longest common prefix might match something > that a longer prefix in the same set wouldn't match) but > ls-refs.c:send_ref() discards such results. > > The code introduced in b31e2680c4 is resilient to stop early (and > return a shorter prefix) when it encounters a metacharacter (as > mentioned in that patch, there is some opportunity to improve this, but > nobody has done it). > > There are two remaining small items in this patch: > > - If no prefixes were provided, then implicitly add the empty string > (which will match all references). > > - Since we are manually munging the prefixes, make sure that we > initialize it ourselves (previously this wasn't necessary since the > first strvec_push would do so). > > Original-patch-by: Jacob Vosmaer > Signed-off-by: Taylor Blau > --- > ls-refs.c | 6 +++++- > 1 file changed, 5 insertions(+), 1 deletion(-) > > diff --git a/ls-refs.c b/ls-refs.c > index a1e0b473e4..eaaa36d0df 100644 > --- a/ls-refs.c > +++ b/ls-refs.c > @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys, > struct ls_refs_data data; > > memset(&data, 0, sizeof(data)); > + strvec_init(&data.prefixes); > > git_config(ls_refs_config, NULL); > > @@ -109,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys, > die(_("expected flush after ls-refs arguments")); > > head_ref_namespaced(send_ref, &data); > - for_each_namespaced_ref(send_ref, &data); > + if (!data.prefixes.nr) > + strvec_push(&data.prefixes, ""); The old code, with for_each_namespaced_ref, would walk "${NAMESPACE}refs/". The new code would walk "${NAMESPACE}" because we're pushing "" onto data.prefixes. So if there is anything in the namespace that does not start with "refs/" it will get yielded. Does that matter? > + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v, > + send_ref, &data, 0); > packet_flush(1); > strvec_clear(&data.prefixes); > return 0; > -- > 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-20 16:04 Subject: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Message-ID: <5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com> URL: https://gitlist.dev/e/5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me%40ttaylorr.com In-Reply-To: ``` From: Jacob Vosmaer Correctly initialize the "prefixes" strvec using strvec_init() instead of simply zeroing it via the earlier memset(). There's no way to trigger a crash, since the first 'ref-prefix' command will initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()' (the alloc and nr variables are already zero'd, so the call to ALLOC_GROW is valid). If no "ref-prefix" command was given, then the call to 'ls-refs.c:ref_match()' will abort early after it reads the zero in 'prefixes->nr'. Likewise, strvec_clear() will only call free() on the array, which is NULL, so we're safe there, too. But, all of this is dangerous and requires more reasoning than it would if we simply called 'strvec_init()', so do that. Signed-off-by: Jacob Vosmaer Signed-off-by: Taylor Blau --- ls-refs.c | 1 + 1 file changed, 1 insertion(+) diff --git a/ls-refs.c b/ls-refs.c index a1e0b473e4..367597d447 100644 --- a/ls-refs.c +++ b/ls-refs.c @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys, struct ls_refs_data data; memset(&data, 0, sizeof(data)); + strvec_init(&data.prefixes); git_config(ls_refs_config, NULL); -- 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-20 16:04 Subject: [PATCH v2 3/3] ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets Message-ID: URL: https://gitlist.dev/e/b97dfb706fe7a94381a978fa9678dde0738106c2.1611158549.git.me%40ttaylorr.com In-Reply-To: ``` ls-refs performs a single revision walk over the whole ref namespace, and sends ones that match with one of the given ref prefixes down to the user. This can be expensive if there are many refs overall, but the portion of them covered by the given prefixes is small by comparison. To attempt to reduce the difference between the number of refs traversed, and the number of refs sent, only traverse references which are in the longest common prefix of the given prefixes. This is very reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find disjoint pattern prefixes, 2019-06-26) which does an analogous thing for multi-patterned 'git for-each-ref' invocations. The callback 'send_ref' is resilient to ignore extra patterns by discarding any arguments which do not begin with at least one of the specified prefixes. Similarly, the code introduced in b31e2680c4 is resilient to stop early at metacharacters, but we only pass strict prefixes here. At worst we would return too many results, but the double checking done by send_ref will throw away anything that doesn't start with something in the prefix list. Finally, if no prefixes were provided, then implicitly add the empty string (which will match all references) since this matches the existing behavior (see the "no restrictions" comment in "ls-refs.c:ref_match()"). Original-patch-by: Jacob Vosmaer Signed-off-by: Taylor Blau --- ls-refs.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/ls-refs.c b/ls-refs.c index 367597d447..eaaa36d0df 100644 --- a/ls-refs.c +++ b/ls-refs.c @@ -110,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys, die(_("expected flush after ls-refs arguments")); head_ref_namespaced(send_ref, &data); - for_each_namespaced_ref(send_ref, &data); + if (!data.prefixes.nr) + strvec_push(&data.prefixes, ""); + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v, + send_ref, &data, 0); packet_flush(1); strvec_clear(&data.prefixes); return 0; -- 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-20 16:04 Subject: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/bda314fe7ae1629ba068a0c4ada9b6adc20576eb.1611158549.git.me%40ttaylorr.com In-Reply-To: ``` This function was used in the ref-filter.c code to find the longest common prefix of among a set of refspecs, and then to iterate all of the references that descend from that prefix. A future patch will want to use that same code from ls-refs.c, so prepare by exposing and moving it to refs.c. Since there is nothing specific to the ref-filter code here (other than that it was previously the only caller of this function), this really belongs in the more generic refs.h header. The code moved in this patch is identical before and after, with the one exception of renaming some arguments to be consistent with other functions exposed in refs.h. Signed-off-by: Taylor Blau --- ref-filter.c | 74 ++------------------------------------------ refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++ refs.h | 9 ++++++ 3 files changed, 98 insertions(+), 72 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index aa260bfd09..f918f00151 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -1929,64 +1929,6 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname) return match_pattern(filter, refname); } -static int qsort_strcmp(const void *va, const void *vb) -{ - const char *a = *(const char **)va; - const char *b = *(const char **)vb; - - return strcmp(a, b); -} - -static void find_longest_prefixes_1(struct string_list *out, - struct strbuf *prefix, - const char **patterns, size_t nr) -{ - size_t i; - - for (i = 0; i < nr; i++) { - char c = patterns[i][prefix->len]; - if (!c || is_glob_special(c)) { - string_list_append(out, prefix->buf); - return; - } - } - - i = 0; - while (i < nr) { - size_t end; - - /* - * Set "end" to the index of the element _after_ the last one - * in our group. - */ - for (end = i + 1; end < nr; end++) { - if (patterns[i][prefix->len] != patterns[end][prefix->len]) - break; - } - - strbuf_addch(prefix, patterns[i][prefix->len]); - find_longest_prefixes_1(out, prefix, patterns + i, end - i); - strbuf_setlen(prefix, prefix->len - 1); - - i = end; - } -} - -static void find_longest_prefixes(struct string_list *out, - const char **patterns) -{ - struct strvec sorted = STRVEC_INIT; - struct strbuf prefix = STRBUF_INIT; - - strvec_pushv(&sorted, patterns); - QSORT(sorted.v, sorted.nr, qsort_strcmp); - - find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr); - - strvec_clear(&sorted); - strbuf_release(&prefix); -} - /* * This is the same as for_each_fullref_in(), but it tries to iterate * only over the patterns we'll care about. Note that it _doesn't_ do a full @@ -1997,10 +1939,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, void *cb_data, int broken) { - struct string_list prefixes = STRING_LIST_INIT_DUP; - struct string_list_item *prefix; - int ret; - if (!filter->match_as_path) { /* * in this case, the patterns are applied after @@ -2024,16 +1962,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, return for_each_fullref_in("", cb, cb_data, broken); } - find_longest_prefixes(&prefixes, filter->name_patterns); - - for_each_string_list_item(prefix, &prefixes) { - ret = for_each_fullref_in(prefix->string, cb, cb_data, broken); - if (ret) - break; - } - - string_list_clear(&prefixes, 0); - return ret; + return for_each_fullref_in_prefixes(NULL, filter->name_patterns, + cb, cb_data, broken); } /* diff --git a/refs.c b/refs.c index 13dc2c3291..0b5a68588f 100644 --- a/refs.c +++ b/refs.c @@ -1546,6 +1546,93 @@ int for_each_rawref(each_ref_fn fn, void *cb_data) return refs_for_each_rawref(get_main_ref_store(the_repository), fn, cb_data); } +static int qsort_strcmp(const void *va, const void *vb) +{ + const char *a = *(const char **)va; + const char *b = *(const char **)vb; + + return strcmp(a, b); +} + +static void find_longest_prefixes_1(struct string_list *out, + struct strbuf *prefix, + const char **patterns, size_t nr) +{ + size_t i; + + for (i = 0; i < nr; i++) { + char c = patterns[i][prefix->len]; + if (!c || is_glob_special(c)) { + string_list_append(out, prefix->buf); + return; + } + } + + i = 0; + while (i < nr) { + size_t end; + + /* + * Set "end" to the index of the element _after_ the last one + * in our group. + */ + for (end = i + 1; end < nr; end++) { + if (patterns[i][prefix->len] != patterns[end][prefix->len]) + break; + } + + strbuf_addch(prefix, patterns[i][prefix->len]); + find_longest_prefixes_1(out, prefix, patterns + i, end - i); + strbuf_setlen(prefix, prefix->len - 1); + + i = end; + } +} + +static void find_longest_prefixes(struct string_list *out, + const char **patterns) +{ + struct strvec sorted = STRVEC_INIT; + struct strbuf prefix = STRBUF_INIT; + + strvec_pushv(&sorted, patterns); + QSORT(sorted.v, sorted.nr, qsort_strcmp); + + find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr); + + strvec_clear(&sorted); + strbuf_release(&prefix); +} + +int for_each_fullref_in_prefixes(const char *namespace, + const char **patterns, + each_ref_fn fn, void *cb_data, + unsigned int broken) +{ + struct string_list prefixes = STRING_LIST_INIT_DUP; + struct string_list_item *prefix; + struct strbuf buf = STRBUF_INIT; + int ret = 0, namespace_len; + + find_longest_prefixes(&prefixes, patterns); + + if (namespace) + strbuf_addstr(&buf, namespace); + namespace_len = buf.len; + + for_each_string_list_item(prefix, &prefixes) { + strbuf_addf(&buf, "%s", prefix->string); + ret = for_each_fullref_in(buf.buf, fn, cb_data, broken); + if (ret) + break; + strbuf_setlen(&buf, namespace_len); + } + + string_list_clear(&prefixes, 0); + strbuf_release(&buf); + return ret; +} + static int refs_read_special_head(struct ref_store *ref_store, const char *refname, struct object_id *oid, struct strbuf *referent, unsigned int *type) diff --git a/refs.h b/refs.h index ff05d2e9fe..c5fd35487d 100644 --- a/refs.h +++ b/refs.h @@ -347,6 +347,15 @@ int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix, int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data, unsigned int broken); +/** + * iterate all refs in "patterns" by partitioning patterns into disjoint sets + * and iterating the longest-common prefix of each set. + * + * callers should be prepared to ignore references that they did not ask for. + */ +int for_each_fullref_in_prefixes(const char *namespace, const char **patterns, + each_ref_fn fn, void *cb_data, + unsigned int broken); /** * iterate refs from the respective area. */ -- 2.30.0.138.g6d7191ea01 ``` ## Taylor Blau, 2021-01-20 16:04 Subject: [PATCH v2 0/3] ls-refs: traverse prefixes of disjoint "ref-prefix" sets Message-ID: URL: https://gitlist.dev/e/cover.1611158549.git.me%40ttaylorr.com In-Reply-To: ``` Here is a reroll of the series I sent yesterday to traverse the longest-common prefixes of disjoint sets containing the ref-prefix arguments to ls-refs. Not much has changed last time, except some clarification about what 'for_each_fullref_in_prefixes()' can yield, and splitting out the last patch into one from Jacob and one from me. I've forged his sign-off since it contains his original code, but it includes a new patch description from me. Jacob Vosmaer (1): ls-refs.c: initialize 'prefixes' before using it Taylor Blau (2): refs: expose 'for_each_fullref_in_prefixes' ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets ls-refs.c | 6 +++- ref-filter.c | 74 ++------------------------------------------ refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++ refs.h | 9 ++++++ 4 files changed, 103 insertions(+), 73 deletions(-) Range-diff against v1: 1: d4c8d059f6 ! 1: bda314fe7a refs: expose 'for_each_fullref_in_prefixes' @@ Commit message common prefix of among a set of refspecs, and then to iterate all of the references that descend from that prefix. - The subsequent patch will want to use that same code from ls-refs, so + A future patch will want to use that same code from ls-refs.c, so prepare by exposing and moving it to refs.c. Since there is nothing specific to the ref-filter code here (other than that it was previously the only caller of this function), this really belongs in the more generic refs.h header. + The code moved in this patch is identical before and after, with the one + exception of renaming some arguments to be consistent with other + functions exposed in refs.h. + Signed-off-by: Taylor Blau ## ref-filter.c ## @@ refs.h: int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix, unsigned int broken); +/** -+ * iterate all refs which are descendent from the longest common prefix among -+ * the list "patterns". ++ * iterate all refs in "patterns" by partitioning patterns into disjoint sets ++ * and iterating the longest-common prefix of each set. ++ * ++ * callers should be prepared to ignore references that they did not ask for. + */ +int for_each_fullref_in_prefixes(const char *namespace, const char **patterns, + each_ref_fn fn, void *cb_data, -: ---------- > 2: 5fc081b2d5 ls-refs.c: initialize 'prefixes' before using it 2: fb8681d128 ! 3: b97dfb706f ls-refs.c: traverse longest common ref prefix @@ Metadata Author: Taylor Blau ## Commit message ## - ls-refs.c: traverse longest common ref prefix + ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets ls-refs performs a single revision walk over the whole ref namespace, and sends ones that match with one of the given ref prefixes down to the @@ Commit message disjoint pattern prefixes, 2019-06-26) which does an analogous thing for multi-patterned 'git for-each-ref' invocations. - The only difference here is that we are operating on ref prefixes, which - do not necessarily point to a single reference. That is just fine, since - all we care about is finding the longest common prefix among prefixes - which can be thought of as refspecs for our purposes here. - - Similarly, for_each_fullref_in_prefixes may return more results than the - caller asked for (since the longest common prefix might match something - that a longer prefix in the same set wouldn't match) but - ls-refs.c:send_ref() discards such results. - - The code introduced in b31e2680c4 is resilient to stop early (and - return a shorter prefix) when it encounters a metacharacter (as - mentioned in that patch, there is some opportunity to improve this, but - nobody has done it). - - There are two remaining small items in this patch: - - - If no prefixes were provided, then implicitly add the empty string - (which will match all references). - - - Since we are manually munging the prefixes, make sure that we - initialize it ourselves (previously this wasn't necessary since the - first strvec_push would do so). + The callback 'send_ref' is resilient to ignore extra patterns by + discarding any arguments which do not begin with at least one of the + specified prefixes. + + Similarly, the code introduced in b31e2680c4 is resilient to stop early + at metacharacters, but we only pass strict prefixes here. At worst we + would return too many results, but the double checking done by send_ref + will throw away anything that doesn't start with something in the prefix + list. + + Finally, if no prefixes were provided, then implicitly add the empty + string (which will match all references) since this matches the existing + behavior (see the "no restrictions" comment in "ls-refs.c:ref_match()"). Original-patch-by: Jacob Vosmaer Signed-off-by: Taylor Blau ## ls-refs.c ## -@@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys, - struct ls_refs_data data; - - memset(&data, 0, sizeof(data)); -+ strvec_init(&data.prefixes); - - git_config(ls_refs_config, NULL); - @@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys, die(_("expected flush after ls-refs arguments")); -- 2.30.0.138.g6d7191ea01 ``` ## Jeff King, 2021-01-20 19:56 Subject: Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/YAiK4U1KnjPtWFN6%40coredump.intra.peff.net In-Reply-To: ``` On Wed, Jan 20, 2021 at 11:04:21AM -0500, Taylor Blau wrote: > This function was used in the ref-filter.c code to find the longest > common prefix of among a set of refspecs, and then to iterate all of the > references that descend from that prefix. > > A future patch will want to use that same code from ls-refs.c, so > prepare by exposing and moving it to refs.c. Since there is nothing > specific to the ref-filter code here (other than that it was previously > the only caller of this function), this really belongs in the more > generic refs.h header. > > The code moved in this patch is identical before and after, with the one > exception of renaming some arguments to be consistent with other > functions exposed in refs.h. The other non-identical thing is that it handles a namespace parameter (which is good, but an obvious non-movement). -Peff ``` ## Jeff King, 2021-01-20 19:58 Subject: Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Message-ID: URL: https://gitlist.dev/e/YAiLXUDTdMpdGG5b%40coredump.intra.peff.net In-Reply-To: <5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com> ``` On Wed, Jan 20, 2021 at 11:04:25AM -0500, Taylor Blau wrote: > From: Jacob Vosmaer > > Correctly initialize the "prefixes" strvec using strvec_init() instead > of simply zeroing it via the earlier memset(). > > There's no way to trigger a crash, since the first 'ref-prefix' command > will initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()' > (the alloc and nr variables are already zero'd, so the call to > ALLOC_GROW is valid). For people not familiar with strvec, I think there's a missing bit of explanation between those two paragraphs: an initialized strvec does not point to NULL, but to a dummy array with a single NULL value in it. That explains why it might crash. :) That nit (and the one I mentioned in the previous patch) aside, these patches look good to me (and I am OK with or without the nits addressed). -Peff ``` ## Taylor Blau, 2021-01-20 20:12 Subject: Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/YAiOx3km0WoZliYj%40nand.local In-Reply-To: ``` On Wed, Jan 20, 2021 at 02:56:17PM -0500, Jeff King wrote: > On Wed, Jan 20, 2021 at 11:04:21AM -0500, Taylor Blau wrote: > > The code moved in this patch is identical before and after, with the one > > exception of renaming some arguments to be consistent with other > > functions exposed in refs.h. > > The other non-identical thing is that it handles a namespace parameter > (which is good, but an obvious non-movement). Ack; I knew that I forgot to mention something. Thanks for pointing it out here. (Since you seem to be OK with this patch even without this mention, I'll avoid sending another revision). > -Peff Thanks, Taylor ``` ## Taylor Blau, 2021-01-20 20:13 Subject: Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Message-ID: URL: https://gitlist.dev/e/YAiO4Ez5x%2FycZ5l%2B%40nand.local In-Reply-To: ``` On Wed, Jan 20, 2021 at 02:58:21PM -0500, Jeff King wrote: > That nit (and the one I mentioned in the previous patch) aside, these > patches look good to me (and I am OK with or without the nits > addressed). Thanks, as always, for your review :-). Thanks, Taylor ``` ## Jacob Vosmaer, 2021-01-20 21:50 Subject: Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Message-ID: URL: https://gitlist.dev/e/CADMWQoNH%2B1MRGYsrJjHTUqhyYMHb9XP5-dQ3KHLT2qNVGGtttA%40mail.gmail.com In-Reply-To: <5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com> ``` As the person whose name is on the "From:" line, I approve. And thanks! On Wed, Jan 20, 2021 at 5:04 PM Taylor Blau wrote: > > From: Jacob Vosmaer > > Correctly initialize the "prefixes" strvec using strvec_init() instead > of simply zeroing it via the earlier memset(). > > There's no way to trigger a crash, since the first 'ref-prefix' command > will initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()' > (the alloc and nr variables are already zero'd, so the call to > ALLOC_GROW is valid). > > If no "ref-prefix" command was given, then the call to > 'ls-refs.c:ref_match()' will abort early after it reads the zero in > 'prefixes->nr'. Likewise, strvec_clear() will only call free() on the > array, which is NULL, so we're safe there, too. > > But, all of this is dangerous and requires more reasoning than it would > if we simply called 'strvec_init()', so do that. > > Signed-off-by: Jacob Vosmaer > Signed-off-by: Taylor Blau > --- > ls-refs.c | 1 + > 1 file changed, 1 insertion(+) > > diff --git a/ls-refs.c b/ls-refs.c > index a1e0b473e4..367597d447 100644 > --- a/ls-refs.c > +++ b/ls-refs.c > @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys, > struct ls_refs_data data; > > memset(&data, 0, sizeof(data)); > + strvec_init(&data.prefixes); > > git_config(ls_refs_config, NULL); > > -- > 2.30.0.138.g6d7191ea01 > ``` ## Junio C Hamano, 2021-01-23 02:59 Subject: Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/xmqqczxw5pf1.fsf%40gitster.c.googlers.com In-Reply-To: ``` Taylor Blau writes: > This function was used in the ref-filter.c code to find the longest > common prefix of among a set of refspecs, and then to iterate all of the > references that descend from that prefix. > > A future patch will want to use that same code from ls-refs.c, so > prepare by exposing and moving it to refs.c. Since there is nothing > specific to the ref-filter code here (other than that it was previously > the only caller of this function), this really belongs in the more > generic refs.h header. > > The code moved in this patch is identical before and after, with the one > exception of renaming some arguments to be consistent with other > functions exposed in refs.h. > > Signed-off-by: Taylor Blau > --- > ref-filter.c | 74 ++------------------------------------------ > refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++ > refs.h | 9 ++++++ > 3 files changed, 98 insertions(+), 72 deletions(-) It is amusing that even to a change that is supposedly "expose existing functionality by moving code around" and nothing else, we can introduce new glitches. > diff --git a/refs.c b/refs.c > index 13dc2c3291..0b5a68588f 100644 > --- a/refs.c > +++ b/refs.c > ... > + for_each_string_list_item(prefix, &prefixes) { > + strbuf_addf(&buf, "%s", prefix->string); strbuf_addstr(&buf, prefix->string); Caught by https://github.com/git/git/runs/1752536671?check_suite_focus=true#step:4:63 I'll apply the fix suggested by Coccinelle on my end, so there is no need to send an updated version just for this one. Thanks. ``` ## Junio C Hamano, 2021-01-23 17:55 Subject: Re: [PATCH v2 0/3] ls-refs: traverse prefixes of disjoint "ref-prefix" sets Message-ID: URL: https://gitlist.dev/e/xmqqpn1v4jxo.fsf%40gitster.c.googlers.com In-Reply-To: ``` Taylor Blau writes: > Here is a reroll of the series I sent yesterday to traverse the > longest-common prefixes of disjoint sets containing the ref-prefix > arguments to ls-refs. > > Not much has changed last time, except some clarification about what > 'for_each_fullref_in_prefixes()' can yield, and splitting out the last > patch into one from Jacob and one from me. I've forged his sign-off > since it contains his original code, but it includes a new patch > description from me. Oh boy I feel behind, but finally I had managed to block time to read through the two iterations of discussion on this topic without leaving my desk once, and it was a pleasant read. Thank you to all three of you. ``` ## Taylor Blau, 2021-01-25 01:35 Subject: Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Message-ID: URL: https://gitlist.dev/e/YA4gTWgMVnQyVT%2FI%40nand.local In-Reply-To: ``` On Fri, Jan 22, 2021 at 06:59:30PM -0800, Junio C Hamano wrote: > Caught by > > https://github.com/git/git/runs/1752536671?check_suite_focus=true#step:4:63 > > I'll apply the fix suggested by Coccinelle on my end, so there is no > need to send an updated version just for this one. Oof. How embarrassing. I'm well aware of the existence of strbuf_addstr() -- there's even a caller just below the line I changed! -- but clearly wasn't thinking when I wrote this patch. Thanks for cleaning it up. Thanks, Taylor ```