{"thread":{"id":"55010","subject":"[PATCH 0/2] ls-refs: only traverse through longest common ref prefix","startedAt":"2021-01-19T18:29:47Z","lastAt":"2021-01-25T01:36:12Z","messageCount":27,"participants":["Taylor Blau","Jacob Vosmaer","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"414696","messageId":"cover.1611080326.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com","subject":"[PATCH 0/2] ls-refs: only traverse through longest common ref prefix","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T18:19:08Z","receivedAt":"2021-01-19T18:29:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is a series inspired by Jacob Vosmaer's recent patch to only traverse once\nthrough the longest common prefix of given ref-prefixes in ls-refs.\n\nInstead of a hand-rolled implementation, this uses the one written back in\nb31e2680c4 (ref-filter.c: find disjoint pattern prefixes, 2019-06-26). The first\npatch exposes that algorithm in refs.h, and the second patch uses the new\nfunction.\n\nIf Jacob is happy with this direction, I'd suggest that we use this series as a\nreplacement for his patch.\n\nThanks in advance for your review.\n\nTaylor Blau (2):\n refs: expose 'for_each_fullref_in_prefixes'\n ls-refs.c: traverse longest common ref prefix\n\n ls-refs.c | 6 +++-\n ref-filter.c | 74 ++------------------------------------------\n refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n refs.h | 7 +++++\n 4 files changed, 101 insertions(+), 73 deletions(-)\n\n--\n2.30.0.138.g6d7191ea01\n"},{"id":"414697","messageId":"fb8681d12864d724108c524834f9498d91e270e6.1611080326.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611080326.git.me@ttaylorr.com","subject":"[PATCH 2/2] ls-refs.c: traverse longest common ref prefix","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T18:19:17Z","receivedAt":"2021-01-19T18:30:14Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"ls-refs performs a single revision walk over the whole ref namespace,\nand sends ones that match with one of the given ref prefixes down to the\nuser.\n\nThis can be expensive if there are many refs overall, but the portion of\nthem covered by the given prefixes is small by comparison.\n\nTo attempt to reduce the difference between the number of refs\ntraversed, and the number of refs sent, only traverse references which\nare in the longest common prefix of the given prefixes. This is very\nreminiscent of the approach taken in b31e2680c4 (ref-filter.c: find\ndisjoint pattern prefixes, 2019-06-26) which does an analogous thing for\nmulti-patterned 'git for-each-ref' invocations.\n\nThe only difference here is that we are operating on ref prefixes, which\ndo not necessarily point to a single reference. That is just fine, since\nall we care about is finding the longest common prefix among prefixes\nwhich can be thought of as refspecs for our purposes here.\n\nSimilarly, for_each_fullref_in_prefixes may return more results than the\ncaller asked for (since the longest common prefix might match something\nthat a longer prefix in the same set wouldn't match) but\nls-refs.c:send_ref() discards such results.\n\nThe code introduced in b31e2680c4 is resilient to stop early (and\nreturn a shorter prefix) when it encounters a metacharacter (as\nmentioned in that patch, there is some opportunity to improve this, but\nnobody has done it).\n\nThere are two remaining small items in this patch:\n\n - If no prefixes were provided, then implicitly add the empty string\n (which will match all references).\n\n - Since we are manually munging the prefixes, make sure that we\n initialize it ourselves (previously this wasn't necessary since the\n first strvec_push would do so).\n\nOriginal-patch-by: Jacob Vosmaer \nSigned-off-by: Taylor Blau \n---\n ls-refs.c | 6 +++++-\n 1 file changed, 5 insertions(+), 1 deletion(-)\n\ndiff --git a/ls-refs.c b/ls-refs.c\nindex a1e0b473e4..eaaa36d0df 100644\n--- a/ls-refs.c\n+++ b/ls-refs.c\n@@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys,\n \tstruct ls_refs_data data;\n \n \tmemset(&data, 0, sizeof(data));\n+\tstrvec_init(&data.prefixes);\n \n \tgit_config(ls_refs_config, NULL);\n \n@@ -109,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys,\n \t\tdie(_(\"expected flush after ls-refs arguments\"));\n \n \thead_ref_namespaced(send_ref, &data);\n-\tfor_each_namespaced_ref(send_ref, &data);\n+\tif (!data.prefixes.nr)\n+\t\tstrvec_push(&data.prefixes, \"\");\n+\tfor_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v,\n+\t\t\t\t send_ref, &data, 0);\n \tpacket_flush(1);\n \tstrvec_clear(&data.prefixes);\n \treturn 0;\n-- \n2.30.0.138.g6d7191ea01\n"},{"id":"414699","messageId":"d4c8d059f676764a1eb1eaed718c93564aabfa37.1611080326.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611080326.git.me@ttaylorr.com","subject":"[PATCH 1/2] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T18:19:13Z","receivedAt":"2021-01-19T18:30:15Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This function was used in the ref-filter.c code to find the longest\ncommon prefix of among a set of refspecs, and then to iterate all of the\nreferences that descend from that prefix.\n\nThe subsequent patch will want to use that same code from ls-refs, so\nprepare by exposing and moving it to refs.c. Since there is nothing\nspecific to the ref-filter code here (other than that it was previously\nthe only caller of this function), this really belongs in the more\ngeneric refs.h header.\n\nSigned-off-by: Taylor Blau \n---\n ref-filter.c | 74 ++------------------------------------------\n refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n refs.h | 7 +++++\n 3 files changed, 96 insertions(+), 72 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex aa260bfd09..f918f00151 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1929,64 +1929,6 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n \treturn match_pattern(filter, refname);\n }\n \n-static int qsort_strcmp(const void *va, const void *vb)\n-{\n-\tconst char *a = *(const char **)va;\n-\tconst char *b = *(const char **)vb;\n-\n-\treturn strcmp(a, b);\n-}\n-\n-static void find_longest_prefixes_1(struct string_list *out,\n-\t\t\t\t struct strbuf *prefix,\n-\t\t\t\t const char **patterns, size_t nr)\n-{\n-\tsize_t i;\n-\n-\tfor (i = 0; i < nr; i++) {\n-\t\tchar c = patterns[i][prefix->len];\n-\t\tif (!c || is_glob_special(c)) {\n-\t\t\tstring_list_append(out, prefix->buf);\n-\t\t\treturn;\n-\t\t}\n-\t}\n-\n-\ti = 0;\n-\twhile (i < nr) {\n-\t\tsize_t end;\n-\n-\t\t/*\n-\t\t* Set \"end\" to the index of the element _after_ the last one\n-\t\t* in our group.\n-\t\t*/\n-\t\tfor (end = i + 1; end < nr; end++) {\n-\t\t\tif (patterns[i][prefix->len] != patterns[end][prefix->len])\n-\t\t\t\tbreak;\n-\t\t}\n-\n-\t\tstrbuf_addch(prefix, patterns[i][prefix->len]);\n-\t\tfind_longest_prefixes_1(out, prefix, patterns + i, end - i);\n-\t\tstrbuf_setlen(prefix, prefix->len - 1);\n-\n-\t\ti = end;\n-\t}\n-}\n-\n-static void find_longest_prefixes(struct string_list *out,\n-\t\t\t\t const char **patterns)\n-{\n-\tstruct strvec sorted = STRVEC_INIT;\n-\tstruct strbuf prefix = STRBUF_INIT;\n-\n-\tstrvec_pushv(&sorted, patterns);\n-\tQSORT(sorted.v, sorted.nr, qsort_strcmp);\n-\n-\tfind_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);\n-\n-\tstrvec_clear(&sorted);\n-\tstrbuf_release(&prefix);\n-}\n-\n /*\n * This is the same as for_each_fullref_in(), but it tries to iterate\n * only over the patterns we'll care about. Note that it _doesn't_ do a full\n@@ -1997,10 +1939,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\t\t\t void *cb_data,\n \t\t\t\t int broken)\n {\n-\tstruct string_list prefixes = STRING_LIST_INIT_DUP;\n-\tstruct string_list_item *prefix;\n-\tint ret;\n-\n \tif (!filter->match_as_path) {\n \t\t/*\n \t\t * in this case, the patterns are applied after\n@@ -2024,16 +1962,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\treturn for_each_fullref_in(\"\", cb, cb_data, broken);\n \t}\n \n-\tfind_longest_prefixes(&prefixes, filter->name_patterns);\n-\n-\tfor_each_string_list_item(prefix, &prefixes) {\n-\t\tret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n-\t\tif (ret)\n-\t\t\tbreak;\n-\t}\n-\n-\tstring_list_clear(&prefixes, 0);\n-\treturn ret;\n+\treturn for_each_fullref_in_prefixes(NULL, filter->name_patterns,\n+\t\t\t\t\t cb, cb_data, broken);\n }\n \n /*\ndiff --git a/refs.c b/refs.c\nindex 13dc2c3291..0b5a68588f 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1546,6 +1546,93 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)\n \treturn refs_for_each_rawref(get_main_ref_store(the_repository), fn, cb_data);\n }\n \n+static int qsort_strcmp(const void *va, const void *vb)\n+{\n+\tconst char *a = *(const char **)va;\n+\tconst char *b = *(const char **)vb;\n+\n+\treturn strcmp(a, b);\n+}\n+\n+static void find_longest_prefixes_1(struct string_list *out,\n+\t\t\t\t struct strbuf *prefix,\n+\t\t\t\t const char **patterns, size_t nr)\n+{\n+\tsize_t i;\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tchar c = patterns[i][prefix->len];\n+\t\tif (!c || is_glob_special(c)) {\n+\t\t\tstring_list_append(out, prefix->buf);\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\n+\ti = 0;\n+\twhile (i < nr) {\n+\t\tsize_t end;\n+\n+\t\t/*\n+\t\t* Set \"end\" to the index of the element _after_ the last one\n+\t\t* in our group.\n+\t\t*/\n+\t\tfor (end = i + 1; end < nr; end++) {\n+\t\t\tif (patterns[i][prefix->len] != patterns[end][prefix->len])\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tstrbuf_addch(prefix, patterns[i][prefix->len]);\n+\t\tfind_longest_prefixes_1(out, prefix, patterns + i, end - i);\n+\t\tstrbuf_setlen(prefix, prefix->len - 1);\n+\n+\t\ti = end;\n+\t}\n+}\n+\n+static void find_longest_prefixes(struct string_list *out,\n+\t\t\t\t const char **patterns)\n+{\n+\tstruct strvec sorted = STRVEC_INIT;\n+\tstruct strbuf prefix = STRBUF_INIT;\n+\n+\tstrvec_pushv(&sorted, patterns);\n+\tQSORT(sorted.v, sorted.nr, qsort_strcmp);\n+\n+\tfind_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);\n+\n+\tstrvec_clear(&sorted);\n+\tstrbuf_release(&prefix);\n+}\n+\n+int for_each_fullref_in_prefixes(const char *namespace,\n+\t\t\t\t const char **patterns,\n+\t\t\t\t each_ref_fn fn, void *cb_data,\n+\t\t\t\t unsigned int broken)\n+{\n+\tstruct string_list prefixes = STRING_LIST_INIT_DUP;\n+\tstruct string_list_item *prefix;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tint ret = 0, namespace_len;\n+\n+\tfind_longest_prefixes(&prefixes, patterns);\n+\n+\tif (namespace)\n+\t\tstrbuf_addstr(&buf, namespace);\n+\tnamespace_len = buf.len;\n+\n+\tfor_each_string_list_item(prefix, &prefixes) {\n+\t\tstrbuf_addf(&buf, \"%s\", prefix->string);\n+\t\tret = for_each_fullref_in(buf.buf, fn, cb_data, broken);\n+\t\tif (ret)\n+\t\t\tbreak;\n+\t\tstrbuf_setlen(&buf, namespace_len);\n+\t}\n+\n+\tstring_list_clear(&prefixes, 0);\n+\tstrbuf_release(&buf);\n+\treturn ret;\n+}\n+\n static int refs_read_special_head(struct ref_store *ref_store,\n \t\t\t\t const char *refname, struct object_id *oid,\n \t\t\t\t struct strbuf *referent, unsigned int *type)\ndiff --git a/refs.h b/refs.h\nindex ff05d2e9fe..e88a794ee6 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -347,6 +347,13 @@ int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,\n int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data,\n \t\t\tunsigned int broken);\n \n+/**\n+ * iterate all refs which are descendent from the longest common prefix among\n+ * the list \"patterns\".\n+ */\n+int for_each_fullref_in_prefixes(const char *namespace, const char **patterns,\n+\t\t\t\t each_ref_fn fn, void *cb_data,\n+\t\t\t\t unsigned int broken);\n /**\n * iterate refs from the respective area.\n */\n-- \n2.30.0.138.g6d7191ea01\n\n"},{"id":"414700","messageId":"CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com","threadId":"55010","inReplyTo":"YAcE/dTuOB9PbGQU@nand.local","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-19T17:42:56Z","receivedAt":"2021-01-19T18:42:57Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"Hi Taylor,\n\nThanks for your reply. That sounds like a great idea!\n\nOn Tue, Jan 19, 2021 at 5:12 PM Taylor Blau wrote:\n> But, I think that we could get pretty far by treating the prefixes as\n> refs so that we can call ref-filter.c:find_longest_prefixes(). For its\n> purposes, it doesn't really care about whether or not the arguments\n> actually are references. It simply returns the longest common prefix\n> among all of its arguments (delimited by '/' characters).\n\nWhat does \"delimited by /\" mean?\n\nWithout really understanding the longest common prefix code in\nref-filter.c, my intuitive concern is that the specifics of glob\nmatching and special treatment of '/' may bite us. I suppose we'll be\nfine because ls-refs has its own matching logic. So long as\nfor_each_fullref_in_prefixes yield enough prefixes, the end result\nwould remain the same.\n\nThe question is then, does for_each_fullref_in_prefixes yield\neverything we need?\n\nI think my approach would be to expose the new\nfor_each_fullref_in_prefixes iterator you propose through test-tool,\nand unit test it so we can be sure it handles both contexts\n(for-each-refs with globs and special '/', and ls-refs without any\nspecial character behavior) correctly.\n\nI may be overly cautious here, take this with a grain of salt because\nI am not an experienced Git contributor. On that topic, apologies if\nI'm botching my inline replies in this email.\n\nRegarding your patch: it works correctly and as fast as expected for\nmy development \"many refs\" test case. Yay! It also segfaults and fails\nsome tests but see my comments below.\n\nAll in all: thanks, great idea, yes we should reuse, I only lack\nconfidence on correctness because I don't fully grasp your\nlongest-common-prefix algorithm yet.\n\nCheers, Jacob\n\n\n> --- >8 ---\n>\n> Subject: [PATCH] ls-refs: iterate longest common refs prefix\n>\n> Signed-off-by: Taylor Blau \n> ---\n> ls-refs.c | 4 +++-\n> ref-filter.c | 46 ++++++++++++++++++++++++++++++++--------------\n> ref-filter.h | 10 ++++++++++\n> 3 files changed, 45 insertions(+), 15 deletions(-)\n>\n> diff --git a/ls-refs.c b/ls-refs.c\n> index a1e0b473e4..6a3e11d45c 100644\n> --- a/ls-refs.c\n> +++ b/ls-refs.c\n> @@ -6,6 +6,7 @@\n> #include \"ls-refs.h\"\n> #include \"pkt-line.h\"\n> #include \"config.h\"\n> +#include \"ref-filter.h\"\n>\n> /*\n> * Check if one of the prefixes is a prefix of the ref.\n> @@ -109,7 +110,8 @@ int ls_refs(struct repository *r, struct strvec *keys,\n> die(_(\"expected flush after ls-refs arguments\"));\n>\n> head_ref_namespaced(send_ref, &data);\n> - for_each_namespaced_ref(send_ref, &data);\n> + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v,\n> + send_ref, &data, 0);\n\nRemember to add that strvec_init(&data.prefixes) I talked about in my\ncommit message, or you get a segfault.\n\nYou also need: if (!data.prefixes.nr) strvec_push(&data.prefixes, \"refs/\");\n\nWithout it, the \"ls-refs without ref-prefix\" scenario fails.\n\n> packet_flush(1);\n> strvec_clear(&data.prefixes);\n> return 0;\n> diff --git a/ref-filter.c b/ref-filter.c\n> index aa260bfd09..c34bf34d06 100644\n> --- a/ref-filter.c\n> +++ b/ref-filter.c\n> @@ -1987,6 +1987,36 @@ static void find_longest_prefixes(struct string_list *out,\n> strbuf_release(&prefix);\n> }\n>\n> +int for_each_fullref_in_prefixes(const char *namespace,\n> + const char **patterns,\n> + each_ref_fn cb,\n> + void *cb_data,\n> + int broken)\n> +{\n> + struct string_list prefixes = STRING_LIST_INIT_DUP;\n> + struct string_list_item *prefix;\n> + struct strbuf buf = STRBUF_INIT;\n> + int ret = 0, namespace_len;\n> +\n> + find_longest_prefixes(&prefixes, patterns);\n> +\n> + if (namespace)\n> + strbuf_addstr(&buf, namespace);\n> + namespace_len = buf.len;\n> +\n> + for_each_string_list_item(prefix, &prefixes) {\n> + strbuf_addf(&buf, prefix->string);\n\nMissing format string \"%s\".\n\n\n> + ret = for_each_fullref_in(buf.buf, cb, cb_data, broken);\n> + if (ret)\n> + break;\n> + strbuf_setlen(&buf, namespace_len);\n> + }\n> +\n> + string_list_clear(&prefixes, 0);\n> + strbuf_release(&buf);\n> + return ret;\n> +}\n> +\n> /*\n> * This is the same as for_each_fullref_in(), but it tries to iterate\n> * only over the patterns we'll care about. Note that it _doesn't_ do a full\n> @@ -1997,10 +2027,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> void *cb_data,\n> int broken)\n> {\n> - struct string_list prefixes = STRING_LIST_INIT_DUP;\n> - struct string_list_item *prefix;\n> - int ret;\n> -\n> if (!filter->match_as_path) {\n> /*\n> * in this case, the patterns are applied after\n> @@ -2024,16 +2050,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> return for_each_fullref_in(\"\", cb, cb_data, broken);\n> }\n>\n> - find_longest_prefixes(&prefixes, filter->name_patterns);\n> -\n> - for_each_string_list_item(prefix, &prefixes) {\n> - ret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n> - if (ret)\n> - break;\n> - }\n> -\n> - string_list_clear(&prefixes, 0);\n> - return ret;\n> + return for_each_fullref_in_prefixes(NULL, filter->name_patterns,\n> + cb, cb_data, broken);\n> }\n>\n> /*\n> diff --git a/ref-filter.h b/ref-filter.h\n> index feaef4a8fd..f666a0fb49 100644\n> --- a/ref-filter.h\n> +++ b/ref-filter.h\n> @@ -146,4 +146,14 @@ struct ref_array_item *ref_array_push(struct ref_array *array,\n> const char *refname,\n> const struct object_id *oid);\n>\n> +/**\n> + * iterate all refs which descend from the longest common prefix among\n> + * \"patterns\".\n> + */\n> +int for_each_fullref_in_prefixes(const char *namespace,\n> + const char **patterns,\n> + each_ref_fn cb,\n> + void *cb_data,\n> + int broken);\n> +\n> #endif /* REF_FILTER_H */\n> --\n> 2.30.0.138.g6d7191ea01\n>\n"},{"id":"414702","messageId":"YAcuUDqfvKzfHFMb@nand.local","threadId":"55010","inReplyTo":"CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T19:09:04Z","receivedAt":"2021-01-19T19:12:07Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jan 19, 2021 at 06:42:56PM +0100, Jacob Vosmaer wrote:\n> Hi Taylor,\n>\n> Thanks for your reply. That sounds like a great idea!\n>\n> On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau wrote:\n> > But, I think that we could get pretty far by treating the prefixes as\n> > refs so that we can call ref-filter.c:find_longest_prefixes(). For its\n> > purposes, it doesn't really care about whether or not the arguments\n> > actually are references. It simply returns the longest common prefix\n> > among all of its arguments (delimited by '/' characters).\n>\n> What does \"delimited by /\" mean?\n\nAh, I just meant that it looks for the longest common prefix where it\nwill only split at '/' characters. But, that's not right at all:\nfind_longest_prefixes_1() will happily split anywhere there is a\ndifference.\n\n> Without really understanding the longest common prefix code in\n> ref-filter.c, my intuitive concern is that the specifics of glob\n> matching and special treatment of '/' may bite us. I suppose we'll be\n> fine because ls-refs has its own matching logic. So long as\n> for_each_fullref_in_prefixes yield enough prefixes, the end result\n> would remain the same.\n\nRight. We can ignore the concern about '/' (seeing my comment above),\nand note that find_longest_prefixes_1() breaks on glob metacharacters,\nso we'll only match or overmatch the desired set (and we'll never\nundermatch).\n\nI made sure to write in the second patch downthread that\nls-refs.c:send_ref() correctly handles receiving too many refs (and it\ndiscards ones that it doesn't want).\n\n> The question is then, does for_each_fullref_in_prefixes yield\n> everything we need?\n\nFor the reasons above, yes: it will.\n\n> I think my approach would be to expose the new\n> for_each_fullref_in_prefixes iterator you propose through test-tool,\n> and unit test it so we can be sure it handles both contexts\n> (for-each-refs with globs and special '/', and ls-refs without any\n> special character behavior) correctly.\n>\n> I may be overly cautious here, take this with a grain of salt because\n> I am not an experienced Git contributor. On that topic, apologies if\n> I'm botching my inline replies in this email.\n\nI do appreciate your caution, but I'm not sure exposing a test-tool is\nnecessary, since we already test this behavior extensively in t6300 (and\nnow t5701, t5702 and t5704, too).\n\n> Regarding your patch: it works correctly and as fast as expected for\n> my development \"many refs\" test case. Yay! It also segfaults and fails\n> some tests but see my comments below.\n>\n> All in all: thanks, great idea, yes we should reuse, I only lack\n> confidence on correctness because I don't fully grasp your\n> longest-common-prefix algorithm yet.\n\n:-). Thanks for the pointers on the spots that I had missed (as I\nmentioned, I only compiled it before sending, so having an additional\nset of more careful eyes was quite helpful).\n\n\nThanks,\nTaylor\n"},{"id":"414731","messageId":"YAdWNgF75QEYFLA7@coredump.intra.peff.net","threadId":"55010","inReplyTo":"YAcuUDqfvKzfHFMb@nand.local","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T21:59:18Z","receivedAt":"2021-01-19T22:02:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 02:09:04PM -0500, Taylor Blau wrote:\n\n> > What does \"delimited by /\" mean?\n> \n> Ah, I just meant that it looks for the longest common prefix where it\n> will only split at '/' characters. But, that's not right at all:\n> find_longest_prefixes_1() will happily split anywhere there is a\n> difference.\n\nRight. We thought in early revisions of the ref-filter work that we\nmight have to split on path components, but it turns out that the\nunderlying ref code is happy to take arbitrary prefixes. And it's that\ncode which defines our strategy; Even if the ls-refs code wanted to\nallow only full path components, it should be using the limiting from\nfor_each_ref_in() only as an optimization, and applying its own\nfiltering to the output.\n\n> > Without really understanding the longest common prefix code in\n> > ref-filter.c, my intuitive concern is that the specifics of glob\n> > matching and special treatment of '/' may bite us. I suppose we'll be\n> > fine because ls-refs has its own matching logic. So long as\n> > for_each_fullref_in_prefixes yield enough prefixes, the end result\n> > would remain the same.\n> \n> Right. We can ignore the concern about '/' (seeing my comment above),\n> and note that find_longest_prefixes_1() breaks on glob metacharacters,\n> so we'll only match or overmatch the desired set (and we'll never\n> undermatch).\n> \n> I made sure to write in the second patch downthread that\n> ls-refs.c:send_ref() correctly handles receiving too many refs (and it\n> discards ones that it doesn't want).\n\nYeah, I think the glob-handling is OK for that reason. We'd have a\nsmaller prefix, which means seeing more refs. So it's never a\ncorrectness issue, but only a potential optimization one (we consider\nmore refs in ls-refs.c than we might otherwise). But I think even that s\nimpossible, because the glob characters are not valid in refnames. So we\nwould never see one at all in a string which is meant to be a pure\nprefix.\n\n> > I think my approach would be to expose the new\n> > for_each_fullref_in_prefixes iterator you propose through test-tool,\n> > and unit test it so we can be sure it handles both contexts\n> > (for-each-refs with globs and special '/', and ls-refs without any\n> > special character behavior) correctly.\n> >\n> > I may be overly cautious here, take this with a grain of salt because\n> > I am not an experienced Git contributor. On that topic, apologies if\n> > I'm botching my inline replies in this email.\n> \n> I do appreciate your caution, but I'm not sure exposing a test-tool is\n> necessary, since we already test this behavior extensively in t6300 (and\n> now t5701, t5702 and t5704, too).\n\nAgreed. test-tool is fine when we have no way to easily feed data to a\nunit. But in this case, the prefix code is easy to test via the\nfor-each-ref plumbing. We'd want to make sure the new setting in ls-refs\nis covered, too, but I agree that t5701 covers that well (regular\nfetches make sure we don't send too few refs, but those ones check that\nwe limited the refs in the expected way).\n\n-Peff\n"},{"id":"414734","messageId":"YAdaAsP6vCQla/Ar@coredump.intra.peff.net","threadId":"55010","inReplyTo":"YAdWNgF75QEYFLA7@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T22:15:30Z","receivedAt":"2021-01-19T22:22:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 04:59:18PM -0500, Jeff King wrote:\n\n> > > What does \"delimited by /\" mean?\n> > \n> > Ah, I just meant that it looks for the longest common prefix where it\n> > will only split at '/' characters. But, that's not right at all:\n> > find_longest_prefixes_1() will happily split anywhere there is a\n> > difference.\n> \n> Right. We thought in early revisions of the ref-filter work that we\n> might have to split on path components, but it turns out that the\n> underlying ref code is happy to take arbitrary prefixes. And it's that\n> code which defines our strategy; Even if the ls-refs code wanted to\n> allow only full path components, it should be using the limiting from\n> for_each_ref_in() only as an optimization, and applying its own\n> filtering to the output.\n\nHaving now looked carefully at the ls-refs code, it's a pure\nprefix-match, too. So I think we _could_ rely on for_each_fullref_in()\nreturning us the correct full results, and not checking it further in\nsend_ref(). But I kind of like keeping it there as an extra check (and\none which could in theory grow more logic later).\n\n-Peff\n"},{"id":"414735","messageId":"YAdb6GmVXWLEGkP1@nand.local","threadId":"55010","inReplyTo":"YAdaAsP6vCQla/Ar@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T22:23:36Z","receivedAt":"2021-01-19T22:24:48Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jan 19, 2021 at 05:15:30PM -0500, Jeff King wrote:\n> On Tue, Jan 19, 2021 at 04:59:18PM -0500, Jeff King wrote:\n>\n> > > > What does \"delimited by /\" mean?\n> > >\n> > > Ah, I just meant that it looks for the longest common prefix where it\n> > > will only split at '/' characters. But, that's not right at all:\n> > > find_longest_prefixes_1() will happily split anywhere there is a\n> > > difference.\n> >\n> > Right. We thought in early revisions of the ref-filter work that we\n> > might have to split on path components, but it turns out that the\n> > underlying ref code is happy to take arbitrary prefixes. And it's that\n> > code which defines our strategy; Even if the ls-refs code wanted to\n> > allow only full path components, it should be using the limiting from\n> > for_each_ref_in() only as an optimization, and applying its own\n> > filtering to the output.\n>\n> Having now looked carefully at the ls-refs code, it's a pure\n> prefix-match, too. So I think we _could_ rely on for_each_fullref_in()\n> returning us the correct full results, and not checking it further in\n> send_ref(). But I kind of like keeping it there as an extra check (and\n> one which could in theory grow more logic later).\n\nHmm. What if the caller asks for:\n\n ref-prefix refs/tags/a\n ref-prefix refs/tags/b\n\n?\n\nThe LCP between those two is refs/tags, so send_ref() will presumably\nget lots of reuslts that it doesn't care about (assuming there are tags\nbesides a and b).\n\nThanks,\nTaylor\n"},{"id":"414740","messageId":"YAdik+z5yj2XU0ti@coredump.intra.peff.net","threadId":"55010","inReplyTo":"YAdb6GmVXWLEGkP1@nand.local","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T22:52:03Z","receivedAt":"2021-01-19T22:53:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 05:23:36PM -0500, Taylor Blau wrote:\n\n> > Having now looked carefully at the ls-refs code, it's a pure\n> > prefix-match, too. So I think we _could_ rely on for_each_fullref_in()\n> > returning us the correct full results, and not checking it further in\n> > send_ref(). But I kind of like keeping it there as an extra check (and\n> > one which could in theory grow more logic later).\n> \n> Hmm. What if the caller asks for:\n> \n> ref-prefix refs/tags/a\n> ref-prefix refs/tags/b\n> \n> ?\n> \n> The LCP between those two is refs/tags, so send_ref() will presumably\n> get lots of reuslts that it doesn't care about (assuming there are tags\n> besides a and b).\n\nOh, you're right, of course. Ignore me. :)\n\n-Peff\n"},{"id":"414743","messageId":"YAdkVkXOnpDy28h2@coredump.intra.peff.net","threadId":"55010","inReplyTo":"YAdik+z5yj2XU0ti@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T22:59:34Z","receivedAt":"2021-01-19T23:01:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 05:52:04PM -0500, Jeff King wrote:\n\n> On Tue, Jan 19, 2021 at 05:23:36PM -0500, Taylor Blau wrote:\n> \n> > > Having now looked carefully at the ls-refs code, it's a pure\n> > > prefix-match, too. So I think we _could_ rely on for_each_fullref_in()\n> > > returning us the correct full results, and not checking it further in\n> > > send_ref(). But I kind of like keeping it there as an extra check (and\n> > > one which could in theory grow more logic later).\n> > \n> > Hmm. What if the caller asks for:\n> > \n> > ref-prefix refs/tags/a\n> > ref-prefix refs/tags/b\n> > \n> > ?\n> > \n> > The LCP between those two is refs/tags, so send_ref() will presumably\n> > get lots of reuslts that it doesn't care about (assuming there are tags\n> > besides a and b).\n> \n> Oh, you're right, of course. Ignore me. :)\n\nActually, I am not sure that we would look for \"refs/tags/\" in that case\n(I did a quick test and we do not seem to). Which makes sense, as it is\ncheaper to find the \"a\" and \"b\" hierarchies separately if there is a\nvery big \"refs/tags/c\" hierarchy.\n\nBut I agree that this is a good reason that callers should consider it\nas an optimization which could return more results than expected.\n\n-Peff\n"},{"id":"414745","messageId":"YAdlGMv3EC1ORUew@nand.local","threadId":"55010","inReplyTo":"YAdkVkXOnpDy28h2@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T23:02:48Z","receivedAt":"2021-01-19T23:04:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jan 19, 2021 at 05:59:34PM -0500, Jeff King wrote:\n> Actually, I am not sure that we would look for \"refs/tags/\" in that case\n> (I did a quick test and we do not seem to). Which makes sense, as it is\n> cheaper to find the \"a\" and \"b\" hierarchies separately if there is a\n> very big \"refs/tags/c\" hierarchy.\n\nAh, makes sense. Thanks for double checking.\n\n> But I agree that this is a good reason that callers should consider it\n> as an optimization which could return more results than expected.\n\nYep. Even though I couldn't quite remember when the algorithm would\nsplit without looking more closely, I made sure to document that it\niterates *all* references that are descendent of the LCP of its\narguments.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"414750","messageId":"YAdmtgUPiGUaXiRX@coredump.intra.peff.net","threadId":"55010","inReplyTo":"fb8681d12864d724108c524834f9498d91e270e6.1611080326.git.me@ttaylorr.com","subject":"Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T23:09:42Z","receivedAt":"2021-01-19T23:22:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 01:19:17PM -0500, Taylor Blau wrote:\n\n> To attempt to reduce the difference between the number of refs\n> traversed, and the number of refs sent, only traverse references which\n> are in the longest common prefix of the given prefixes. This is very\n> reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find\n> disjoint pattern prefixes, 2019-06-26) which does an analogous thing for\n> multi-patterned 'git for-each-ref' invocations.\n> \n> The only difference here is that we are operating on ref prefixes, which\n> do not necessarily point to a single reference. That is just fine, since\n> all we care about is finding the longest common prefix among prefixes\n> which can be thought of as refspecs for our purposes here.\n\nThis second paragraph confused me. Aren't the inputs to for-each-ref\nalso prefixes?\n\nI guess they require an explicit '*', but fundamentally it's the same\nconcept (and certainly they are not just single references).\n\n> Similarly, for_each_fullref_in_prefixes may return more results than the\n> caller asked for (since the longest common prefix might match something\n> that a longer prefix in the same set wouldn't match) but\n> ls-refs.c:send_ref() discards such results.\n\nBased on my other poking, I'm not entirely sure that we can return too\nmany results. But I do think it's worth keeping the caller more careful.\n\n> The code introduced in b31e2680c4 is resilient to stop early (and\n> return a shorter prefix) when it encounters a metacharacter (as\n> mentioned in that patch, there is some opportunity to improve this, but\n> nobody has done it).\n\nI agree that is how b31e2680c4 works, but we don't care about that\nbehavior here, since we have strict prefixes. Isn't the argument we need\nto make the other way? I.e., that stopping early on a metacharacter will\nnot hurt us. Because at worst we return too many results (hey, there's a\ncase!) and because we would not expect metacharacters in the prefixes\nanyway, as they are illegal in refnames.\n\n> There are two remaining small items in this patch:\n> \n> - If no prefixes were provided, then implicitly add the empty string\n> (which will match all references).\n\nI wonder if for_each_fullref_in_prefixes() should do that, since that is\nexactly what the other caller does, too. OTOH, maybe it is better to\nmake the callers be more explicit. In which case should it maybe BUG()\non an empty set of prefixes, rather than letting the caller assume some\nbehavior?\n\n> - Since we are manually munging the prefixes, make sure that we\n> initialize it ourselves (previously this wasn't necessary since the\n> first strvec_push would do so).\n\nI think this was an existing bug (that we were just lucky it was\nimpossible to trigger, because nobody looked for the NULL sentinel), and\nwould make more sense as a separate fix.\n\n-Peff\n"},{"id":"414764","messageId":"YAdwvzQCGc5TfXTF@nand.local","threadId":"55010","inReplyTo":"YAdmtgUPiGUaXiRX@coredump.intra.peff.net","subject":"Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T23:52:31Z","receivedAt":"2021-01-19T23:53:38Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jan 19, 2021 at 06:09:42PM -0500, Jeff King wrote:\n> On Tue, Jan 19, 2021 at 01:19:17PM -0500, Taylor Blau wrote:\n>\n> > To attempt to reduce the difference between the number of refs\n> > traversed, and the number of refs sent, only traverse references which\n> > are in the longest common prefix of the given prefixes. This is very\n> > reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find\n> > disjoint pattern prefixes, 2019-06-26) which does an analogous thing for\n> > multi-patterned 'git for-each-ref' invocations.\n> >\n> > The only difference here is that we are operating on ref prefixes, which\n> > do not necessarily point to a single reference. That is just fine, since\n> > all we care about is finding the longest common prefix among prefixes\n> > which can be thought of as refspecs for our purposes here.\n>\n> This second paragraph confused me. Aren't the inputs to for-each-ref\n> also prefixes?\n>\n> I guess they require an explicit '*', but fundamentally it's the same\n> concept (and certainly they are not just single references).\n\nYeah, that is the point that I was trying to make. But re-reading this\npatch after knowing that it confused you, I think the clearest way to\nmake that point is to drop that second paragraph entirely.\n\n> > Similarly, for_each_fullref_in_prefixes may return more results than the\n> > caller asked for (since the longest common prefix might match something\n> > that a longer prefix in the same set wouldn't match) but\n> > ls-refs.c:send_ref() discards such results.\n>\n> Based on my other poking, I'm not entirely sure that we can return too\n> many results. But I do think it's worth keeping the caller more careful.\n\nIt can return more results, but I don't think that my writing in\nb31e2680c4 is particularly clear. Here's an example, though. Say I ask\nfor `git for-each-refs 'refs/tags/a/*' 'refs/tags/a/b/c'`. The LCP of\nthat is definitely \"refs/tags/a\", which might traverse other stuff like\n\"refs/tags/a/b/d\", which wouldn't get matched by either.\n\n> > The code introduced in b31e2680c4 is resilient to stop early (and\n> > return a shorter prefix) when it encounters a metacharacter (as\n> > mentioned in that patch, there is some opportunity to improve this, but\n> > nobody has done it).\n>\n> I agree that is how b31e2680c4 works, but we don't care about that\n> behavior here, since we have strict prefixes. Isn't the argument we need\n> to make the other way? I.e., that stopping early on a metacharacter will\n> not hurt us. Because at worst we return too many results (hey, there's a\n> case!) and because we would not expect metacharacters in the prefixes\n> anyway, as they are illegal in refnames.\n\nYeah, thinking on it more I agree that's the argument we should be\nmaking here. I updated the patch to reflect it.\n\n> > There are two remaining small items in this patch:\n> >\n> > - If no prefixes were provided, then implicitly add the empty string\n> > (which will match all references).\n>\n> I wonder if for_each_fullref_in_prefixes() should do that, since that is\n> exactly what the other caller does, too. OTOH, maybe it is better to\n> make the callers be more explicit. In which case should it maybe BUG()\n> on an empty set of prefixes, rather than letting the caller assume some\n> behavior?\n\nHmm. I don't feel strongly either way, but I think that the BUG is\nprobably the most sensible option.\n\n> > - Since we are manually munging the prefixes, make sure that we\n> > initialize it ourselves (previously this wasn't necessary since the\n> > first strvec_push would do so).\n>\n> I think this was an existing bug (that we were just lucky it was\n> impossible to trigger, because nobody looked for the NULL sentinel), and\n> would make more sense as a separate fix.\n\nRight. I'll make sure to pull this one out into a separate patch and\ncredit Jacob with authorship.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"414766","messageId":"YAd0kyBP8LRSEBYw@coredump.intra.peff.net","threadId":"55010","inReplyTo":"YAdwvzQCGc5TfXTF@nand.local","subject":"Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-20T00:08:51Z","receivedAt":"2021-01-20T00:10:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 06:52:31PM -0500, Taylor Blau wrote:\n\n> > I guess they require an explicit '*', but fundamentally it's the same\n> > concept (and certainly they are not just single references).\n> \n> Yeah, that is the point that I was trying to make. But re-reading this\n> patch after knowing that it confused you, I think the clearest way to\n> make that point is to drop that second paragraph entirely.\n\nSounds good.\n\n> > Based on my other poking, I'm not entirely sure that we can return too\n> > many results. But I do think it's worth keeping the caller more careful.\n> \n> It can return more results, but I don't think that my writing in\n> b31e2680c4 is particularly clear. Here's an example, though. Say I ask\n> for `git for-each-refs 'refs/tags/a/*' 'refs/tags/a/b/c'`. The LCP of\n> that is definitely \"refs/tags/a\", which might traverse other stuff like\n> \"refs/tags/a/b/d\", which wouldn't get matched by either.\n\nI thought that would be matched by refs/tags/a/*, but it looks like\nfor-each-ref treats \"*\" as matching only a single path component. So\nreally just:\n\n git for-each-ref refs/tags/*\n\nrequires extra filtering already. But AFAICT none of that is true for\nls-refs, which is strictly prefix matching already.\n\n-Peff\n"},{"id":"414788","messageId":"CADMWQoO+163mJBXctb+GHFebGCbKQRPAtMJ676_GwfEt-BedAw@mail.gmail.com","threadId":"55010","inReplyTo":"fb8681d12864d724108c524834f9498d91e270e6.1611080326.git.me@ttaylorr.com","subject":"Re: [PATCH 2/2] ls-refs.c: traverse longest common ref prefix","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-20T11:00:56Z","receivedAt":"2021-01-20T11:51:35Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"On Tue, Jan 19, 2021 at 7:19 PM Taylor Blau wrote:\n>\n> ls-refs performs a single revision walk over the whole ref namespace,\n> and sends ones that match with one of the given ref prefixes down to the\n> user.\n>\n> This can be expensive if there are many refs overall, but the portion of\n> them covered by the given prefixes is small by comparison.\n>\n> To attempt to reduce the difference between the number of refs\n> traversed, and the number of refs sent, only traverse references which\n> are in the longest common prefix of the given prefixes. This is very\n> reminiscent of the approach taken in b31e2680c4 (ref-filter.c: find\n> disjoint pattern prefixes, 2019-06-26) which does an analogous thing for\n> multi-patterned 'git for-each-ref' invocations.\n>\n> The only difference here is that we are operating on ref prefixes, which\n> do not necessarily point to a single reference. That is just fine, since\n> all we care about is finding the longest common prefix among prefixes\n> which can be thought of as refspecs for our purposes here.\n>\n> Similarly, for_each_fullref_in_prefixes may return more results than the\n> caller asked for (since the longest common prefix might match something\n> that a longer prefix in the same set wouldn't match) but\n> ls-refs.c:send_ref() discards such results.\n>\n> The code introduced in b31e2680c4 is resilient to stop early (and\n> return a shorter prefix) when it encounters a metacharacter (as\n> mentioned in that patch, there is some opportunity to improve this, but\n> nobody has done it).\n>\n> There are two remaining small items in this patch:\n>\n> - If no prefixes were provided, then implicitly add the empty string\n> (which will match all references).\n>\n> - Since we are manually munging the prefixes, make sure that we\n> initialize it ourselves (previously this wasn't necessary since the\n> first strvec_push would do so).\n>\n> Original-patch-by: Jacob Vosmaer \n> Signed-off-by: Taylor Blau \n> ---\n> ls-refs.c | 6 +++++-\n> 1 file changed, 5 insertions(+), 1 deletion(-)\n>\n> diff --git a/ls-refs.c b/ls-refs.c\n> index a1e0b473e4..eaaa36d0df 100644\n> --- a/ls-refs.c\n> +++ b/ls-refs.c\n> @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys,\n> struct ls_refs_data data;\n>\n> memset(&data, 0, sizeof(data));\n> + strvec_init(&data.prefixes);\n>\n> git_config(ls_refs_config, NULL);\n>\n> @@ -109,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys,\n> die(_(\"expected flush after ls-refs arguments\"));\n>\n> head_ref_namespaced(send_ref, &data);\n> - for_each_namespaced_ref(send_ref, &data);\n> + if (!data.prefixes.nr)\n> + strvec_push(&data.prefixes, \"\");\n\nThe old code, with for_each_namespaced_ref, would walk\n\"${NAMESPACE}refs/\". The new code would walk \"${NAMESPACE}\" because\nwe're pushing \"\" onto data.prefixes. So if there is anything in the\nnamespace that does not start with \"refs/\" it will get yielded.\n\nDoes that matter?\n\n> + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v,\n> + send_ref, &data, 0);\n> packet_flush(1);\n> strvec_clear(&data.prefixes);\n> return 0;\n> --\n> 2.30.0.138.g6d7191ea01\n"},{"id":"414804","messageId":"5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611158549.git.me@ttaylorr.com","subject":"[PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T16:04:25Z","receivedAt":"2021-01-20T16:06:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Jacob Vosmaer \n\nCorrectly initialize the \"prefixes\" strvec using strvec_init() instead\nof simply zeroing it via the earlier memset().\n\nThere's no way to trigger a crash, since the first 'ref-prefix' command\nwill initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()'\n(the alloc and nr variables are already zero'd, so the call to\nALLOC_GROW is valid).\n\nIf no \"ref-prefix\" command was given, then the call to\n'ls-refs.c:ref_match()' will abort early after it reads the zero in\n'prefixes->nr'. Likewise, strvec_clear() will only call free() on the\narray, which is NULL, so we're safe there, too.\n\nBut, all of this is dangerous and requires more reasoning than it would\nif we simply called 'strvec_init()', so do that.\n\nSigned-off-by: Jacob Vosmaer \nSigned-off-by: Taylor Blau \n---\n ls-refs.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/ls-refs.c b/ls-refs.c\nindex a1e0b473e4..367597d447 100644\n--- a/ls-refs.c\n+++ b/ls-refs.c\n@@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys,\n \tstruct ls_refs_data data;\n \n \tmemset(&data, 0, sizeof(data));\n+\tstrvec_init(&data.prefixes);\n \n \tgit_config(ls_refs_config, NULL);\n \n-- \n2.30.0.138.g6d7191ea01\n\n"},{"id":"414805","messageId":"b97dfb706fe7a94381a978fa9678dde0738106c2.1611158549.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611158549.git.me@ttaylorr.com","subject":"[PATCH v2 3/3] ls-refs.c: traverse prefixes of disjoint \"ref-prefix\" sets","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T16:04:30Z","receivedAt":"2021-01-20T16:07:07Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"ls-refs performs a single revision walk over the whole ref namespace,\nand sends ones that match with one of the given ref prefixes down to the\nuser.\n\nThis can be expensive if there are many refs overall, but the portion of\nthem covered by the given prefixes is small by comparison.\n\nTo attempt to reduce the difference between the number of refs\ntraversed, and the number of refs sent, only traverse references which\nare in the longest common prefix of the given prefixes. This is very\nreminiscent of the approach taken in b31e2680c4 (ref-filter.c: find\ndisjoint pattern prefixes, 2019-06-26) which does an analogous thing for\nmulti-patterned 'git for-each-ref' invocations.\n\nThe callback 'send_ref' is resilient to ignore extra patterns by\ndiscarding any arguments which do not begin with at least one of the\nspecified prefixes.\n\nSimilarly, the code introduced in b31e2680c4 is resilient to stop early\nat metacharacters, but we only pass strict prefixes here. At worst we\nwould return too many results, but the double checking done by send_ref\nwill throw away anything that doesn't start with something in the prefix\nlist.\n\nFinally, if no prefixes were provided, then implicitly add the empty\nstring (which will match all references) since this matches the existing\nbehavior (see the \"no restrictions\" comment in \"ls-refs.c:ref_match()\").\n\nOriginal-patch-by: Jacob Vosmaer \nSigned-off-by: Taylor Blau \n---\n ls-refs.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/ls-refs.c b/ls-refs.c\nindex 367597d447..eaaa36d0df 100644\n--- a/ls-refs.c\n+++ b/ls-refs.c\n@@ -110,7 +110,10 @@ int ls_refs(struct repository *r, struct strvec *keys,\n \t\tdie(_(\"expected flush after ls-refs arguments\"));\n \n \thead_ref_namespaced(send_ref, &data);\n-\tfor_each_namespaced_ref(send_ref, &data);\n+\tif (!data.prefixes.nr)\n+\t\tstrvec_push(&data.prefixes, \"\");\n+\tfor_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v,\n+\t\t\t\t send_ref, &data, 0);\n \tpacket_flush(1);\n \tstrvec_clear(&data.prefixes);\n \treturn 0;\n-- \n2.30.0.138.g6d7191ea01\n"},{"id":"414806","messageId":"bda314fe7ae1629ba068a0c4ada9b6adc20576eb.1611158549.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611158549.git.me@ttaylorr.com","subject":"[PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T16:04:21Z","receivedAt":"2021-01-20T16:07:18Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This function was used in the ref-filter.c code to find the longest\ncommon prefix of among a set of refspecs, and then to iterate all of the\nreferences that descend from that prefix.\n\nA future patch will want to use that same code from ls-refs.c, so\nprepare by exposing and moving it to refs.c. Since there is nothing\nspecific to the ref-filter code here (other than that it was previously\nthe only caller of this function), this really belongs in the more\ngeneric refs.h header.\n\nThe code moved in this patch is identical before and after, with the one\nexception of renaming some arguments to be consistent with other\nfunctions exposed in refs.h.\n\nSigned-off-by: Taylor Blau \n---\n ref-filter.c | 74 ++------------------------------------------\n refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n refs.h | 9 ++++++\n 3 files changed, 98 insertions(+), 72 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex aa260bfd09..f918f00151 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1929,64 +1929,6 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n \treturn match_pattern(filter, refname);\n }\n \n-static int qsort_strcmp(const void *va, const void *vb)\n-{\n-\tconst char *a = *(const char **)va;\n-\tconst char *b = *(const char **)vb;\n-\n-\treturn strcmp(a, b);\n-}\n-\n-static void find_longest_prefixes_1(struct string_list *out,\n-\t\t\t\t struct strbuf *prefix,\n-\t\t\t\t const char **patterns, size_t nr)\n-{\n-\tsize_t i;\n-\n-\tfor (i = 0; i < nr; i++) {\n-\t\tchar c = patterns[i][prefix->len];\n-\t\tif (!c || is_glob_special(c)) {\n-\t\t\tstring_list_append(out, prefix->buf);\n-\t\t\treturn;\n-\t\t}\n-\t}\n-\n-\ti = 0;\n-\twhile (i < nr) {\n-\t\tsize_t end;\n-\n-\t\t/*\n-\t\t* Set \"end\" to the index of the element _after_ the last one\n-\t\t* in our group.\n-\t\t*/\n-\t\tfor (end = i + 1; end < nr; end++) {\n-\t\t\tif (patterns[i][prefix->len] != patterns[end][prefix->len])\n-\t\t\t\tbreak;\n-\t\t}\n-\n-\t\tstrbuf_addch(prefix, patterns[i][prefix->len]);\n-\t\tfind_longest_prefixes_1(out, prefix, patterns + i, end - i);\n-\t\tstrbuf_setlen(prefix, prefix->len - 1);\n-\n-\t\ti = end;\n-\t}\n-}\n-\n-static void find_longest_prefixes(struct string_list *out,\n-\t\t\t\t const char **patterns)\n-{\n-\tstruct strvec sorted = STRVEC_INIT;\n-\tstruct strbuf prefix = STRBUF_INIT;\n-\n-\tstrvec_pushv(&sorted, patterns);\n-\tQSORT(sorted.v, sorted.nr, qsort_strcmp);\n-\n-\tfind_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);\n-\n-\tstrvec_clear(&sorted);\n-\tstrbuf_release(&prefix);\n-}\n-\n /*\n * This is the same as for_each_fullref_in(), but it tries to iterate\n * only over the patterns we'll care about. Note that it _doesn't_ do a full\n@@ -1997,10 +1939,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\t\t\t void *cb_data,\n \t\t\t\t int broken)\n {\n-\tstruct string_list prefixes = STRING_LIST_INIT_DUP;\n-\tstruct string_list_item *prefix;\n-\tint ret;\n-\n \tif (!filter->match_as_path) {\n \t\t/*\n \t\t * in this case, the patterns are applied after\n@@ -2024,16 +1962,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\treturn for_each_fullref_in(\"\", cb, cb_data, broken);\n \t}\n \n-\tfind_longest_prefixes(&prefixes, filter->name_patterns);\n-\n-\tfor_each_string_list_item(prefix, &prefixes) {\n-\t\tret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n-\t\tif (ret)\n-\t\t\tbreak;\n-\t}\n-\n-\tstring_list_clear(&prefixes, 0);\n-\treturn ret;\n+\treturn for_each_fullref_in_prefixes(NULL, filter->name_patterns,\n+\t\t\t\t\t cb, cb_data, broken);\n }\n \n /*\ndiff --git a/refs.c b/refs.c\nindex 13dc2c3291..0b5a68588f 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1546,6 +1546,93 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)\n \treturn refs_for_each_rawref(get_main_ref_store(the_repository), fn, cb_data);\n }\n \n+static int qsort_strcmp(const void *va, const void *vb)\n+{\n+\tconst char *a = *(const char **)va;\n+\tconst char *b = *(const char **)vb;\n+\n+\treturn strcmp(a, b);\n+}\n+\n+static void find_longest_prefixes_1(struct string_list *out,\n+\t\t\t\t struct strbuf *prefix,\n+\t\t\t\t const char **patterns, size_t nr)\n+{\n+\tsize_t i;\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tchar c = patterns[i][prefix->len];\n+\t\tif (!c || is_glob_special(c)) {\n+\t\t\tstring_list_append(out, prefix->buf);\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\n+\ti = 0;\n+\twhile (i < nr) {\n+\t\tsize_t end;\n+\n+\t\t/*\n+\t\t* Set \"end\" to the index of the element _after_ the last one\n+\t\t* in our group.\n+\t\t*/\n+\t\tfor (end = i + 1; end < nr; end++) {\n+\t\t\tif (patterns[i][prefix->len] != patterns[end][prefix->len])\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tstrbuf_addch(prefix, patterns[i][prefix->len]);\n+\t\tfind_longest_prefixes_1(out, prefix, patterns + i, end - i);\n+\t\tstrbuf_setlen(prefix, prefix->len - 1);\n+\n+\t\ti = end;\n+\t}\n+}\n+\n+static void find_longest_prefixes(struct string_list *out,\n+\t\t\t\t const char **patterns)\n+{\n+\tstruct strvec sorted = STRVEC_INIT;\n+\tstruct strbuf prefix = STRBUF_INIT;\n+\n+\tstrvec_pushv(&sorted, patterns);\n+\tQSORT(sorted.v, sorted.nr, qsort_strcmp);\n+\n+\tfind_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);\n+\n+\tstrvec_clear(&sorted);\n+\tstrbuf_release(&prefix);\n+}\n+\n+int for_each_fullref_in_prefixes(const char *namespace,\n+\t\t\t\t const char **patterns,\n+\t\t\t\t each_ref_fn fn, void *cb_data,\n+\t\t\t\t unsigned int broken)\n+{\n+\tstruct string_list prefixes = STRING_LIST_INIT_DUP;\n+\tstruct string_list_item *prefix;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tint ret = 0, namespace_len;\n+\n+\tfind_longest_prefixes(&prefixes, patterns);\n+\n+\tif (namespace)\n+\t\tstrbuf_addstr(&buf, namespace);\n+\tnamespace_len = buf.len;\n+\n+\tfor_each_string_list_item(prefix, &prefixes) {\n+\t\tstrbuf_addf(&buf, \"%s\", prefix->string);\n+\t\tret = for_each_fullref_in(buf.buf, fn, cb_data, broken);\n+\t\tif (ret)\n+\t\t\tbreak;\n+\t\tstrbuf_setlen(&buf, namespace_len);\n+\t}\n+\n+\tstring_list_clear(&prefixes, 0);\n+\tstrbuf_release(&buf);\n+\treturn ret;\n+}\n+\n static int refs_read_special_head(struct ref_store *ref_store,\n \t\t\t\t const char *refname, struct object_id *oid,\n \t\t\t\t struct strbuf *referent, unsigned int *type)\ndiff --git a/refs.h b/refs.h\nindex ff05d2e9fe..c5fd35487d 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -347,6 +347,15 @@ int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,\n int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data,\n \t\t\tunsigned int broken);\n \n+/**\n+ * iterate all refs in \"patterns\" by partitioning patterns into disjoint sets\n+ * and iterating the longest-common prefix of each set.\n+ *\n+ * callers should be prepared to ignore references that they did not ask for.\n+ */\n+int for_each_fullref_in_prefixes(const char *namespace, const char **patterns,\n+\t\t\t\t each_ref_fn fn, void *cb_data,\n+\t\t\t\t unsigned int broken);\n /**\n * iterate refs from the respective area.\n */\n-- \n2.30.0.138.g6d7191ea01\n\n"},{"id":"414807","messageId":"cover.1611158549.git.me@ttaylorr.com","threadId":"55010","inReplyTo":"cover.1611080326.git.me@ttaylorr.com","subject":"[PATCH v2 0/3] ls-refs: traverse prefixes of disjoint \"ref-prefix\" sets","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T16:04:13Z","receivedAt":"2021-01-20T16:09:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is a reroll of the series I sent yesterday to traverse the\nlongest-common prefixes of disjoint sets containing the ref-prefix\narguments to ls-refs.\n\nNot much has changed last time, except some clarification about what\n'for_each_fullref_in_prefixes()' can yield, and splitting out the last\npatch into one from Jacob and one from me. I've forged his sign-off\nsince it contains his original code, but it includes a new patch\ndescription from me.\n\nJacob Vosmaer (1):\n ls-refs.c: initialize 'prefixes' before using it\n\nTaylor Blau (2):\n refs: expose 'for_each_fullref_in_prefixes'\n ls-refs.c: traverse prefixes of disjoint \"ref-prefix\" sets\n\n ls-refs.c | 6 +++-\n ref-filter.c | 74 ++------------------------------------------\n refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n refs.h | 9 ++++++\n 4 files changed, 103 insertions(+), 73 deletions(-)\n\nRange-diff against v1:\n1: d4c8d059f6 ! 1: bda314fe7a refs: expose 'for_each_fullref_in_prefixes'\n @@ Commit message\n common prefix of among a set of refspecs, and then to iterate all of the\n references that descend from that prefix.\n\n - The subsequent patch will want to use that same code from ls-refs, so\n + A future patch will want to use that same code from ls-refs.c, so\n prepare by exposing and moving it to refs.c. Since there is nothing\n specific to the ref-filter code here (other than that it was previously\n the only caller of this function), this really belongs in the more\n generic refs.h header.\n\n + The code moved in this patch is identical before and after, with the one\n + exception of renaming some arguments to be consistent with other\n + functions exposed in refs.h.\n +\n Signed-off-by: Taylor Blau \n\n ## ref-filter.c ##\n @@ refs.h: int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,\n \t\t\tunsigned int broken);\n\n +/**\n -+ * iterate all refs which are descendent from the longest common prefix among\n -+ * the list \"patterns\".\n ++ * iterate all refs in \"patterns\" by partitioning patterns into disjoint sets\n ++ * and iterating the longest-common prefix of each set.\n ++ *\n ++ * callers should be prepared to ignore references that they did not ask for.\n + */\n +int for_each_fullref_in_prefixes(const char *namespace, const char **patterns,\n +\t\t\t\t each_ref_fn fn, void *cb_data,\n-: ---------- > 2: 5fc081b2d5 ls-refs.c: initialize 'prefixes' before using it\n2: fb8681d128 ! 3: b97dfb706f ls-refs.c: traverse longest common ref prefix\n @@ Metadata\n Author: Taylor Blau \n\n ## Commit message ##\n - ls-refs.c: traverse longest common ref prefix\n + ls-refs.c: traverse prefixes of disjoint \"ref-prefix\" sets\n\n ls-refs performs a single revision walk over the whole ref namespace,\n and sends ones that match with one of the given ref prefixes down to the\n @@ Commit message\n disjoint pattern prefixes, 2019-06-26) which does an analogous thing for\n multi-patterned 'git for-each-ref' invocations.\n\n - The only difference here is that we are operating on ref prefixes, which\n - do not necessarily point to a single reference. That is just fine, since\n - all we care about is finding the longest common prefix among prefixes\n - which can be thought of as refspecs for our purposes here.\n -\n - Similarly, for_each_fullref_in_prefixes may return more results than the\n - caller asked for (since the longest common prefix might match something\n - that a longer prefix in the same set wouldn't match) but\n - ls-refs.c:send_ref() discards such results.\n -\n - The code introduced in b31e2680c4 is resilient to stop early (and\n - return a shorter prefix) when it encounters a metacharacter (as\n - mentioned in that patch, there is some opportunity to improve this, but\n - nobody has done it).\n -\n - There are two remaining small items in this patch:\n -\n - - If no prefixes were provided, then implicitly add the empty string\n - (which will match all references).\n -\n - - Since we are manually munging the prefixes, make sure that we\n - initialize it ourselves (previously this wasn't necessary since the\n - first strvec_push would do so).\n + The callback 'send_ref' is resilient to ignore extra patterns by\n + discarding any arguments which do not begin with at least one of the\n + specified prefixes.\n +\n + Similarly, the code introduced in b31e2680c4 is resilient to stop early\n + at metacharacters, but we only pass strict prefixes here. At worst we\n + would return too many results, but the double checking done by send_ref\n + will throw away anything that doesn't start with something in the prefix\n + list.\n +\n + Finally, if no prefixes were provided, then implicitly add the empty\n + string (which will match all references) since this matches the existing\n + behavior (see the \"no restrictions\" comment in \"ls-refs.c:ref_match()\").\n\n Original-patch-by: Jacob Vosmaer \n Signed-off-by: Taylor Blau \n\n ## ls-refs.c ##\n -@@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys,\n - \tstruct ls_refs_data data;\n -\n - \tmemset(&data, 0, sizeof(data));\n -+\tstrvec_init(&data.prefixes);\n -\n - \tgit_config(ls_refs_config, NULL);\n -\n @@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys,\n \t\tdie(_(\"expected flush after ls-refs arguments\"));\n\n--\n2.30.0.138.g6d7191ea01\n"},{"id":"414851","messageId":"YAiK4U1KnjPtWFN6@coredump.intra.peff.net","threadId":"55010","inReplyTo":"bda314fe7ae1629ba068a0c4ada9b6adc20576eb.1611158549.git.me@ttaylorr.com","subject":"Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-20T19:56:17Z","receivedAt":"2021-01-20T19:57:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 20, 2021 at 11:04:21AM -0500, Taylor Blau wrote:\n\n> This function was used in the ref-filter.c code to find the longest\n> common prefix of among a set of refspecs, and then to iterate all of the\n> references that descend from that prefix.\n> \n> A future patch will want to use that same code from ls-refs.c, so\n> prepare by exposing and moving it to refs.c. Since there is nothing\n> specific to the ref-filter code here (other than that it was previously\n> the only caller of this function), this really belongs in the more\n> generic refs.h header.\n> \n> The code moved in this patch is identical before and after, with the one\n> exception of renaming some arguments to be consistent with other\n> functions exposed in refs.h.\n\nThe other non-identical thing is that it handles a namespace parameter\n(which is good, but an obvious non-movement).\n\n-Peff\n"},{"id":"414853","messageId":"YAiLXUDTdMpdGG5b@coredump.intra.peff.net","threadId":"55010","inReplyTo":"5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-20T19:58:21Z","receivedAt":"2021-01-20T20:01:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 20, 2021 at 11:04:25AM -0500, Taylor Blau wrote:\n\n> From: Jacob Vosmaer \n> \n> Correctly initialize the \"prefixes\" strvec using strvec_init() instead\n> of simply zeroing it via the earlier memset().\n> \n> There's no way to trigger a crash, since the first 'ref-prefix' command\n> will initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()'\n> (the alloc and nr variables are already zero'd, so the call to\n> ALLOC_GROW is valid).\n\nFor people not familiar with strvec, I think there's a missing bit of\nexplanation between those two paragraphs: an initialized strvec does not\npoint to NULL, but to a dummy array with a single NULL value in it. That\nexplains why it might crash. :)\n\nThat nit (and the one I mentioned in the previous patch) aside, these\npatches look good to me (and I am OK with or without the nits\naddressed).\n\n-Peff\n"},{"id":"414856","messageId":"YAiOx3km0WoZliYj@nand.local","threadId":"55010","inReplyTo":"YAiK4U1KnjPtWFN6@coredump.intra.peff.net","subject":"Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T20:12:55Z","receivedAt":"2021-01-20T20:14:10Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Jan 20, 2021 at 02:56:17PM -0500, Jeff King wrote:\n> On Wed, Jan 20, 2021 at 11:04:21AM -0500, Taylor Blau wrote:\n> > The code moved in this patch is identical before and after, with the one\n> > exception of renaming some arguments to be consistent with other\n> > functions exposed in refs.h.\n>\n> The other non-identical thing is that it handles a namespace parameter\n> (which is good, but an obvious non-movement).\n\nAck; I knew that I forgot to mention something. Thanks for pointing it\nout here. (Since you seem to be OK with this patch even without this\nmention, I'll avoid sending another revision).\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"414857","messageId":"YAiO4Ez5x/ycZ5l+@nand.local","threadId":"55010","inReplyTo":"YAiLXUDTdMpdGG5b@coredump.intra.peff.net","subject":"Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-20T20:13:20Z","receivedAt":"2021-01-20T20:14:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Jan 20, 2021 at 02:58:21PM -0500, Jeff King wrote:\n> That nit (and the one I mentioned in the previous patch) aside, these\n> patches look good to me (and I am OK with or without the nits\n> addressed).\n\nThanks, as always, for your review :-).\n\nThanks,\nTaylor\n"},{"id":"414863","messageId":"CADMWQoNH+1MRGYsrJjHTUqhyYMHb9XP5-dQ3KHLT2qNVGGtttA@mail.gmail.com","threadId":"55010","inReplyTo":"5fc081b2d554db305400ec52fac8683a3ed59597.1611158549.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-20T21:50:22Z","receivedAt":"2021-01-20T22:30:56Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"As the person whose name is on the \"From:\" line, I approve. And thanks!\n\nOn Wed, Jan 20, 2021 at 5:04 PM Taylor Blau wrote:\n>\n> From: Jacob Vosmaer \n>\n> Correctly initialize the \"prefixes\" strvec using strvec_init() instead\n> of simply zeroing it via the earlier memset().\n>\n> There's no way to trigger a crash, since the first 'ref-prefix' command\n> will initialize the strvec via the 'ALLOC_GROW' in 'strvec_push_nodup()'\n> (the alloc and nr variables are already zero'd, so the call to\n> ALLOC_GROW is valid).\n>\n> If no \"ref-prefix\" command was given, then the call to\n> 'ls-refs.c:ref_match()' will abort early after it reads the zero in\n> 'prefixes->nr'. Likewise, strvec_clear() will only call free() on the\n> array, which is NULL, so we're safe there, too.\n>\n> But, all of this is dangerous and requires more reasoning than it would\n> if we simply called 'strvec_init()', so do that.\n>\n> Signed-off-by: Jacob Vosmaer \n> Signed-off-by: Taylor Blau \n> ---\n> ls-refs.c | 1 +\n> 1 file changed, 1 insertion(+)\n>\n> diff --git a/ls-refs.c b/ls-refs.c\n> index a1e0b473e4..367597d447 100644\n> --- a/ls-refs.c\n> +++ b/ls-refs.c\n> @@ -90,6 +90,7 @@ int ls_refs(struct repository *r, struct strvec *keys,\n> struct ls_refs_data data;\n>\n> memset(&data, 0, sizeof(data));\n> + strvec_init(&data.prefixes);\n>\n> git_config(ls_refs_config, NULL);\n>\n> --\n> 2.30.0.138.g6d7191ea01\n>\n"},{"id":"415031","messageId":"xmqqczxw5pf1.fsf@gitster.c.googlers.com","threadId":"55010","inReplyTo":"bda314fe7ae1629ba068a0c4ada9b6adc20576eb.1611158549.git.me@ttaylorr.com","subject":"Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-23T02:59:30Z","receivedAt":"2021-01-23T03:00:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> This function was used in the ref-filter.c code to find the longest\n> common prefix of among a set of refspecs, and then to iterate all of the\n> references that descend from that prefix.\n>\n> A future patch will want to use that same code from ls-refs.c, so\n> prepare by exposing and moving it to refs.c. Since there is nothing\n> specific to the ref-filter code here (other than that it was previously\n> the only caller of this function), this really belongs in the more\n> generic refs.h header.\n>\n> The code moved in this patch is identical before and after, with the one\n> exception of renaming some arguments to be consistent with other\n> functions exposed in refs.h.\n>\n> Signed-off-by: Taylor Blau \n> ---\n> ref-filter.c | 74 ++------------------------------------------\n> refs.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n> refs.h | 9 ++++++\n> 3 files changed, 98 insertions(+), 72 deletions(-)\n\nIt is amusing that even to a change that is supposedly \"expose\nexisting functionality by moving code around\" and nothing else,\nwe can introduce new glitches.\n\n> diff --git a/refs.c b/refs.c\n> index 13dc2c3291..0b5a68588f 100644\n> --- a/refs.c\n> +++ b/refs.c\n> ...\n> +\tfor_each_string_list_item(prefix, &prefixes) {\n> +\t\tstrbuf_addf(&buf, \"%s\", prefix->string);\n\n\t\tstrbuf_addstr(&buf, prefix->string);\n\nCaught by\n\nhttps://github.com/git/git/runs/1752536671?check_suite_focus=true#step:4:63\n\nI'll apply the fix suggested by Coccinelle on my end, so there is no\nneed to send an updated version just for this one.\n\nThanks.\n"},{"id":"415072","messageId":"xmqqpn1v4jxo.fsf@gitster.c.googlers.com","threadId":"55010","inReplyTo":"cover.1611158549.git.me@ttaylorr.com","subject":"Re: [PATCH v2 0/3] ls-refs: traverse prefixes of disjoint \"ref-prefix\" sets","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-23T17:55:31Z","receivedAt":"2021-01-23T17:56:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Here is a reroll of the series I sent yesterday to traverse the\n> longest-common prefixes of disjoint sets containing the ref-prefix\n> arguments to ls-refs.\n>\n> Not much has changed last time, except some clarification about what\n> 'for_each_fullref_in_prefixes()' can yield, and splitting out the last\n> patch into one from Jacob and one from me. I've forged his sign-off\n> since it contains his original code, but it includes a new patch\n> description from me.\n\nOh boy I feel behind, but finally I had managed to block time to\nread through the two iterations of discussion on this topic without\nleaving my desk once, and it was a pleasant read.\n\nThank you to all three of you.\n"},{"id":"415188","messageId":"YA4gTWgMVnQyVT/I@nand.local","threadId":"55010","inReplyTo":"xmqqczxw5pf1.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-25T01:35:09Z","receivedAt":"2021-01-25T01:36:12Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Jan 22, 2021 at 06:59:30PM -0800, Junio C Hamano wrote:\n> Caught by\n>\n> https://github.com/git/git/runs/1752536671?check_suite_focus=true#step:4:63\n>\n> I'll apply the fix suggested by Coccinelle on my end, so there is no\n> need to send an updated version just for this one.\n\nOof. How embarrassing. I'm well aware of the existence of\nstrbuf_addstr() -- there's even a caller just below the line I changed!\n-- but clearly wasn't thinking when I wrote this patch.\n\nThanks for cleaning it up.\n\nThanks,\nTaylor\n"}]}