{"thread":{"id":"55009","subject":"[PATCH 1/1] ls-refs.c: minimize number of refs visited","startedAt":"2021-01-19T18:27:13Z","lastAt":"2021-01-20T11:34:09Z","messageCount":8,"participants":["Jacob Vosmaer","Taylor Blau","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"414688","messageId":"20210119144251.27924-2-jacob@gitlab.com","threadId":"55009","inReplyTo":"20210119144251.27924-1-jacob@gitlab.com","subject":"[PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-19T14:42:51Z","receivedAt":"2021-01-19T18:27:13Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"The previous implementation of ls-refs would perform exactly one ref\nwalk, matching each ref against the prefixes (if any) provided by the\nuser. This can be expensive if there are a lot of refs and the user\nonly cares about a small subset of them.\n\nIn this patch we analyze the prefixes provided by the user and build a\nminimal set of disjoint prefixes that contains all of them. We then do\na ref walk for each of these minimal prefixes.\n\nIt is tempting to have just one strvec for the prefixes and use it\nboth for matching and for iterating. But every time I tried that, it\nmade things more complicated. I settled on leaving the existing ref\nmatching (using &data.prefixes) alone, and I added a new layer around\nit for the ref walk optimization (using &iter_prefixes).\n\nThis commit also fixes a bug in ls-refs.c that was not triggered\nbefore: we were using a strvec set to zero, which is not how you are\nsupposed to initialize a strvec. We now call strvec_init after zeroing.\n\nSigned-off-by: Jacob Vosmaer <jacob@gitlab.com>\n---\n ls-refs.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 62 insertions(+), 1 deletion(-)\n\ndiff --git a/ls-refs.c b/ls-refs.c\nindex a1e0b473e4..6d5f0c769a 100644\n--- a/ls-refs.c\n+++ b/ls-refs.c\n@@ -84,12 +84,44 @@ static int ls_refs_config(const char *var, const char *value, void *data)\n \treturn parse_hide_refs_config(var, value, \"uploadpack\");\n }\n \n+static int cmp_prefix(const void *a_, const void *b_){\n+\tconst char *a = *(const char **)a_;\n+\tconst char *b = *(const char **)b_;\n+\treturn strcmp(a, b);\n+}\n+\n+static void deduplicate_prefixes(struct strvec *prefixes) {\n+\tint i;\n+\n+\tQSORT(prefixes->v, prefixes->nr, cmp_prefix);\n+\n+\tfor (i = 1; i < prefixes->nr;) {\n+\t\tconst char *p = prefixes->v[i];\n+\n+\t\t/*\n+\t\t * If p is \"refs/foobar\" and its predecessor is \"refs/foo\" then we should\n+\t\t * drop p, both to avoid sending duplicate refs to the user, and to avoid\n+\t\t * doing unnecessary work.\n+\t\t */\n+\t\tif (starts_with(p, prefixes->v[i - 1])) {\n+\t\t\tMOVE_ARRAY(&prefixes->v[i], &prefixes->v[i + 1], prefixes->nr - (i + 1));\n+\t\t\tprefixes->v[prefixes->nr - 1] = p;\n+\t\t\tstrvec_pop(prefixes);\n+\t\t} else {\n+\t\t\ti++;\n+\t\t}\n+\t}\n+}\n+\n int ls_refs(struct repository *r, struct strvec *keys,\n \t    struct packet_reader *request)\n {\n \tstruct ls_refs_data data;\n+\tstruct strvec iter_prefixes = STRVEC_INIT;\n+\tconst char **p;\n \n \tmemset(&data, 0, sizeof(data));\n+\tstrvec_init(&data.prefixes);\n \n \tgit_config(ls_refs_config, NULL);\n \n@@ -109,8 +141,37 @@ 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+\n+\t/*\n+\t * Try to create a minimal disjoint set of prefixes that\n+\t * contains everything the user wants to see, but that lets us\n+\t * avoid a full ref walk. If the repo has a lot of refs and\n+\t * the user only wants to see refs/heads and refs/tags,\n+\t * it is faster to do two small walks of refs/heads and\n+\t * refs/tags instead of one big walk of all of refs/.\n+\t */\n+\tfor (p = data.prefixes.v; *p; p++) {\n+\t\tif (starts_with(*p, \"refs/\")) {\n+\t\t\tstrvec_push(&iter_prefixes, *p);\n+\t\t} else { /* full ref walk in pathological cases like \"\" */\n+\t\t\tstrvec_push(&iter_prefixes, \"refs/\");\n+\t\t}\n+\t}\n+\n+\tif (!iter_prefixes.nr) /* full ref walk when there are no prefixes */\n+\t\tstrvec_push(&iter_prefixes, \"refs/\");\n+\n+\tdeduplicate_prefixes(&iter_prefixes);\n+\n+\tfor (p = iter_prefixes.v; *p; p++) {\n+\t\tstruct strbuf buf = STRBUF_INIT;\n+\t\tstrbuf_addf(&buf, \"%s%s\", get_git_namespace(), *p);\n+\t\tfor_each_fullref_in(buf.buf, send_ref, &data, 0);\n+\t\tstrbuf_release(&buf);\n+\t}\n+\n \tpacket_flush(1);\n \tstrvec_clear(&data.prefixes);\n+\tstrvec_clear(&iter_prefixes);\n \treturn 0;\n }\n-- \n2.30.0\n\n"},{"id":"414689","messageId":"20210119144251.27924-1-jacob@gitlab.com","threadId":"55009","inReplyTo":null,"subject":"[PATCH 0/1] ls-refs.c: minimize number of refs visited","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-19T14:42:50Z","receivedAt":"2021-01-19T18:27:13Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"The back story of this patch is in\nhttps://gitlab.com/gitlab-com/gl-infra/scalability/-/issues/746; it\ncomes down to: we have a repo with 500,000 refs of which only 50,000\nare visible. Having ls-refs iterate through all the refs adds\nconsiderable overhead.\n\nThis patch reduces the number of refs visited by replacing one ref\nwalk over refs/ with multiple ref walks over the prefixes the user\nrequested via ref-prefix. In the case the user did not use ref-prefix\nwe fall back to the walk over all of refs/.\n\nJacob Vosmaer (1):\n  ls-refs.c: minimize number of refs visited\n\n ls-refs.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 62 insertions(+), 1 deletion(-)\n\n-- \n2.30.0\n\n"},{"id":"414691","messageId":"YAcE/dTuOB9PbGQU@nand.local","threadId":"55009","inReplyTo":"20210119144251.27924-2-jacob@gitlab.com","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-19T16:12:45Z","receivedAt":"2021-01-19T18:27:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Jacob,\n\nOn Tue, Jan 19, 2021 at 03:42:51PM +0100, Jacob Vosmaer wrote:\n> The previous implementation of ls-refs would perform exactly one ref\n> walk, matching each ref against the prefixes (if any) provided by the\n> user. This can be expensive if there are a lot of refs and the user\n> only cares about a small subset of them.\n>\n> In this patch we analyze the prefixes provided by the user and build a\n> minimal set of disjoint prefixes that contains all of them. We then do\n> a ref walk for each of these minimal prefixes.\n\nThis reminds me of b31e2680c4 (ref-filter.c: find disjoint pattern\nprefixes, 2019-06-26), where we solved a very similar problem for 'git\nfor-each-ref'. The difference here is that we are operating on a set of\nprefixes, not a set of refs.\n\nBut, I think that we could get pretty far by treating the prefixes as\nrefs so that we can call ref-filter.c:find_longest_prefixes(). For its\npurposes, it doesn't really care about whether or not the arguments\nactually are references. It simply returns the longest common prefix\namong all of its arguments (delimited by '/' characters).\n\n> It is tempting to have just one strvec for the prefixes and use it\n> both for matching and for iterating. But every time I tried that, it\n> made things more complicated. I settled on leaving the existing ref\n> matching (using &data.prefixes) alone, and I added a new layer around\n> it for the ref walk optimization (using &iter_prefixes).\n\nI think the implementation in b31e2680c4 deals with this nicely: it\ntakes a pointer to a strvec and dumps prefixes in there.\n\n> This commit also fixes a bug in ls-refs.c that was not triggered\n> before: we were using a strvec set to zero, which is not how you are\n> supposed to initialize a strvec. We now call strvec_init after zeroing.\n\nGood.\n\n> Signed-off-by: Jacob Vosmaer <jacob@gitlab.com>\n> ---\n>  ls-refs.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n>  1 file changed, 62 insertions(+), 1 deletion(-)\n>\n> diff --git a/ls-refs.c b/ls-refs.c\n> index a1e0b473e4..6d5f0c769a 100644\n> --- a/ls-refs.c\n> +++ b/ls-refs.c\n> @@ -84,12 +84,44 @@ static int ls_refs_config(const char *var, const char *value, void *data)\n>  \treturn parse_hide_refs_config(var, value, \"uploadpack\");\n>  }\n>\n> +static int cmp_prefix(const void *a_, const void *b_){\n> +\tconst char *a = *(const char **)a_;\n> +\tconst char *b = *(const char **)b_;\n> +\treturn strcmp(a, b);\n> +}\n> +\n> +static void deduplicate_prefixes(struct strvec *prefixes) {\n> +\tint i;\n> +\n> +\tQSORT(prefixes->v, prefixes->nr, cmp_prefix);\n> +\n> +\tfor (i = 1; i < prefixes->nr;) {\n> +\t\tconst char *p = prefixes->v[i];\n> +\n> +\t\t/*\n> +\t\t * If p is \"refs/foobar\" and its predecessor is \"refs/foo\" then we should\n> +\t\t * drop p, both to avoid sending duplicate refs to the user, and to avoid\n> +\t\t * doing unnecessary work.\n> +\t\t */\n> +\t\tif (starts_with(p, prefixes->v[i - 1])) {\n> +\t\t\tMOVE_ARRAY(&prefixes->v[i], &prefixes->v[i + 1], prefixes->nr - (i + 1));\n> +\t\t\tprefixes->v[prefixes->nr - 1] = p;\n> +\t\t\tstrvec_pop(prefixes);\n> +\t\t} else {\n> +\t\t\ti++;\n> +\t\t}\n> +\t}\n> +}\n> +\n\nIndeed, this and the below code are very reminiscent of b31e2680c4. So,\nI wonder if it's possible to use the existing implementation rather than\nimplement what is roughly the same thing twice.\n\nBelow is a completely untested patch to try and reuse the code from\nb31e2680c4. (It compiles, but that's the extent of my guarantees about\nit ;-).) It's all smashed into one huge patch, so if you're happy with\nthe direction I'll take care of cleaning it up. The new function in\nref-filter.h really belongs in refs.h, but I left the implementation in\nref-filter.c to avoid creating more noise in the diff.\n\nLet me know what you think.\n\nThanks,\nTaylor\n\n--- >8 ---\n\nSubject: [PATCH] ls-refs: iterate longest common refs prefix\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\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\ndiff --git a/ls-refs.c b/ls-refs.c\nindex 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 \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+\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;\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 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 \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 cb,\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+\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, prefix->string);\n+\t\tret = for_each_fullref_in(buf.buf, cb, 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 /*\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 \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 +2050,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/ref-filter.h b/ref-filter.h\nindex 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 \t\t\t\t      const char *refname,\n \t\t\t\t      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+\t\t\t\t const char **patterns,\n+\t\t\t\t each_ref_fn cb,\n+\t\t\t\t void *cb_data,\n+\t\t\t\t int broken);\n+\n #endif /*  REF_FILTER_H  */\n--\n2.30.0.138.g6d7191ea01\n\n"},{"id":"414741","messageId":"YAdjBC7z2eE1Z0uk@coredump.intra.peff.net","threadId":"55009","inReplyTo":"20210119144251.27924-2-jacob@gitlab.com","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-19T22:53:56Z","receivedAt":"2021-01-19T22:55:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 03:42:51PM +0100, Jacob Vosmaer wrote:\n\n> The previous implementation of ls-refs would perform exactly one ref\n> walk, matching each ref against the prefixes (if any) provided by the\n> user. This can be expensive if there are a lot of refs and the user\n> only cares about a small subset of them.\n> \n> In this patch we analyze the prefixes provided by the user and build a\n> minimal set of disjoint prefixes that contains all of them. We then do\n> a ref walk for each of these minimal prefixes.\n\nThanks for posting this. I have a vague recollection that we considered\nthis either when we did the for-each-ref prefixes, or when we added\nls-refs prefixes, but I can't seem to find either. At any rate, at\nGitHub we haven't generally found it to be a problem because our\nhorrifically-large repos tend to be aggregated alternates repos, not the\nones people serve upload-pack out of (though I did just time it, and\nsome of our largest repos should save a few hundred milliseconds per\nadvertisement, which is certainly not nothing).\n\nI do think we should reuse the code from ref-filter, as Taylor showed.\n\n> This commit also fixes a bug in ls-refs.c that was not triggered\n> before: we were using a strvec set to zero, which is not how you are\n> supposed to initialize a strvec. We now call strvec_init after zeroing.\n\nGood catch. It didn't matter until now because nobody relied on having a\nNULL entry when no prefix had been added (instead, they always iterated\nover prefixes->nr). IMHO that is worth fixing as a separate commit.\n\n-Peff\n"},{"id":"414744","messageId":"YAdkg7ZijzfB8eMc@nand.local","threadId":"55009","inReplyTo":"YAdjBC7z2eE1Z0uk@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:00:19Z","receivedAt":"2021-01-19T23:02:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Jan 19, 2021 at 05:53:56PM -0500, Jeff King wrote:\n> Thanks for posting this. I have a vague recollection that we considered\n> this either when we did the for-each-ref prefixes, or when we added\n> ls-refs prefixes, but I can't seem to find either. At any rate, at\n> GitHub we haven't generally found it to be a problem because our\n> horrifically-large repos tend to be aggregated alternates repos, not the\n> ones people serve upload-pack out of (though I did just time it, and\n> some of our largest repos should save a few hundred milliseconds per\n> advertisement, which is certainly not nothing).\n\nGreat on all counts!\n\n> > This commit also fixes a bug in ls-refs.c that was not triggered\n> > before: we were using a strvec set to zero, which is not how you are\n> > supposed to initialize a strvec. We now call strvec_init after zeroing.\n>\n> Good catch. It didn't matter until now because nobody relied on having a\n> NULL entry when no prefix had been added (instead, they always iterated\n> over prefixes->nr). IMHO that is worth fixing as a separate commit.\n\nYeah. Even after calling it out as such myself, I promptly forgot it\nwhen preparing the first patch I sent back to Jacob!\n\nI didn't pull it out into its own patch, and rather folded it in to my\n2/2. It has a small call-out of its own, but if you'd prefer it by\nitself, I'm happy to resubmit it with that change included.\n\n> -Peff\n\nThanks,\nTaylor\n"},{"id":"414748","messageId":"YAdnB3Qy46qQ2to4@coredump.intra.peff.net","threadId":"55009","inReplyTo":"YAdkg7ZijzfB8eMc@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-19T23:11:03Z","receivedAt":"2021-01-19T23:15:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 19, 2021 at 06:00:19PM -0500, Taylor Blau wrote:\n\n> > Good catch. It didn't matter until now because nobody relied on having a\n> > NULL entry when no prefix had been added (instead, they always iterated\n> > over prefixes->nr). IMHO that is worth fixing as a separate commit.\n> \n> Yeah. Even after calling it out as such myself, I promptly forgot it\n> when preparing the first patch I sent back to Jacob!\n> \n> I didn't pull it out into its own patch, and rather folded it in to my\n> 2/2. It has a small call-out of its own, but if you'd prefer it by\n> itself, I'm happy to resubmit it with that change included.\n\nIt's not a _huge_ deal to me, but I think it is slightly nicer as a\nseparate patch. Plus it can easily be credited to Jacob, so at least he\ngets some authorship credit out of this. :)\n\n-Peff\n"},{"id":"414784","messageId":"CADMWQoOzD0xF4PSAUo2qXp62-tTJX4DhquFZxFjfdQmy+7j+6g@mail.gmail.com","threadId":"55009","inReplyTo":"YAdnB3Qy46qQ2to4@coredump.intra.peff.net","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-20T10:40:31Z","receivedAt":"2021-01-20T11:33:44Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"On Wed, Jan 20, 2021 at 12:11 AM Jeff King <peff@peff.net> wrote:\n> It's not a _huge_ deal to me, but I think it is slightly nicer as a\n> separate patch. Plus it can easily be credited to Jacob, so at least he\n> gets some authorship credit out of this. :)\n\nThanks, I'm fine either way. Just remember that the other changes in\nls-refs.c depend on that strvec_init, so if we split it out, we need\nto remember / maintain that (order) dependency.\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().\n\nI also think we could. But as I alluded to in my original commit\nmessage, I don't like how complicated that gets. I find it easier to\nconvince myself in the current form that the longest prefix code\nselects _enough_ prefixes, which is a weaker property than \"selects\nexactly the right prefixes\".\n\nJacob\n"},{"id":"414785","messageId":"CADMWQoMHUwJcR5T8H048BgsLCd8-_yg8d8Dj-ojYV31pUmhw4w@mail.gmail.com","threadId":"55009","inReplyTo":"CADMWQoOzD0xF4PSAUo2qXp62-tTJX4DhquFZxFjfdQmy+7j+6g@mail.gmail.com","subject":"Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited","fromName":"Jacob Vosmaer","fromEmail":"jacob@gitlab.com","sentAt":"2021-01-20T10:44:19Z","receivedAt":"2021-01-20T11:34:09Z","isPatch":true,"sender":{"key":"jacob@gitlab.com","avatar":"https://avatars.githubusercontent.com/u/1336311?v=4"},"body":"On Wed, Jan 20, 2021 at 11:40 AM Jacob Vosmaer <jacob@gitlab.com> wrote:\n> I also think we could. But as I alluded to in my original commit\n> message, I don't like how complicated that gets. I find it easier to\n> convince myself in the current form that the longest prefix code\n> selects _enough_ prefixes, which is a weaker property than \"selects\n> exactly the right prefixes\".\n\nBy which I mean to say I think we should keep the current form, with\nthe final authoritative ref matching pass.\n\nJacob\n"}]}