{"thread":{"id":"63065","subject":"[PATCH 0/2] refs: a couple of --exclude fixes","startedAt":"2025-03-06T01:19:49Z","lastAt":"2025-03-07T23:58:27Z","messageCount":17,"participants":["Taylor Blau","Patrick Steinhardt","Junio C Hamano","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"513627","messageId":"cover.1741223981.git.me@ttaylorr.com","threadId":"63065","inReplyTo":null,"subject":"[PATCH 0/2] refs: a couple of --exclude fixes","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T01:19:47Z","receivedAt":"2025-03-06T01:19:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This short patch series fixes a couple of quirk's with the --exclude\nfeature in for-each-ref (and the corresponding low level bits in the\nreftable and packed backend).\n\nThe issue described and fixed in the second patch was reported by SURA\nhere[1]. While working on that issue, I noticed a separate issue that\nmerited fixing in its own patch, which precedes the fix I intended to\nwrite ;-).\n\nThanks in advance for your review!\n\n[1]: https://lore.kernel.org/git/CAD6AYr-ZC32VNfUfMB63H-rQRfTdV=VQfBm67i2mG+6GDCNxkQ@mail.gmail.com/\n\nTaylor Blau (2):\n refs.c: remove empty '--exclude' patterns\n refs.c: unify '--exclude' behavior between files and packed backends\n\n refs.c | 20 ++++++++++++++++++++\n t/t1419-exclude-refs.sh | 12 +++++++++++-\n 2 files changed, 31 insertions(+), 1 deletion(-)\n\n\nbase-commit: 6a64ac7b014fa2cfa7a69af3c253bcd53a94b428\n-- \n2.49.0.rc1.2.g7e6a5e020ba\n"},{"id":"513628","messageId":"c3b5ca597330275391704a0653398ee28f911fc1.1741223981.git.me@ttaylorr.com","threadId":"63065","inReplyTo":"cover.1741223981.git.me@ttaylorr.com","subject":"[PATCH 1/2] refs.c: remove empty '--exclude' patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T01:19:50Z","receivedAt":"2025-03-06T01:19:52Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\nexcluded pattern(s), 2023-07-10), the packed-refs backend learned how to\nconstruct \"jump lists\" to avoid enumerating sections of the packed-refs\nfile that we know the caller is going to throw out anyway.\n\nThis process works by finding the start- and end-points (that is, where\nin the packed-refs file corresponds to the range we're going to ignore)\nfor each exclude pattern, then constructing a jump list based on that.\nAt enumeration time we'll consult the jump list to skip past everything\nin the range(s) found in the previous step, saving time when excluding a\nlarge portion of references.\n\nBut when there is a --exclude pattern which is just the empty string,\nthe behavior is a little funky. When we try and exclude the empty\nstring, the matched range covers the entire packed-refs file, meaning\nthat we won't output any packed references. But the empty pattern\ndoesn't actually match any references to begin with! For example, on my\ncopy of git.git I can do:\n\n $ git for-each-ref '' | wc -l\n 0\n\nSo \"git for-each-ref --exclude=''\" shouldn't actually remove anything\nfrom the output, and ought to be equivalent to \"git for-each-ref\". But\nit's not, and in fact:\n\n $ git for-each-ref | wc -l\n 2229\n $ git for-each-ref --exclude='' | wc -l\n 480\n\nBut why does the '--exclude' version output only some of the references\nin the repository? Here's a hint:\n\n $ find .git/refs -type f | wc -l\n 480\n\nIndeed, because the files backend doesn't implement[^1] the same jump\nlist concept as the packed backend we get the correct result for the\nloose references, but none of the packed references.\n\nSince the empty string exclude pattern doesn't match anything, we can\ndiscard them before the packed-refs backend has a chance to even see it\n(and likewise for reftable, which also implements a similar concept\nsince 1869525066 (refs/reftable: wire up support for exclude patterns,\n2024-09-16)).\n\nThis approach (copying only some of the patterns into a strvec at the\nrefs.c layer) may seem heavy-handed, but it's setting us up to fix\nanother bug in the following commit where the fix will involve modifying\nthe incoming patterns.\n\n[^1]: As noted in 59c35fac54. We technically could avoid opening and\n enumerating the contents of, for e.g., \"$GIT_DIR/refs/heads/foo/\" if\n we knew that we were excluding anything under the 'refs/heads/foo'\n hierarchy. But the --exclude stuff is all best-effort anyway, since\n the caller is expected to cull out any results that they don't want.\n\nNoticed-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n refs.c | 16 ++++++++++++++++\n t/t1419-exclude-refs.sh | 10 ++++++++++\n 2 files changed, 26 insertions(+)\n\ndiff --git a/refs.c b/refs.c\nindex 91da5325d7..17d3840aff 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1699,6 +1699,20 @@ struct ref_iterator *refs_ref_iterator_begin(\n \t\tenum do_for_each_ref_flags flags)\n {\n \tstruct ref_iterator *iter;\n+\tstruct strvec normalized_exclude_patterns = STRVEC_INIT;\n+\n+\tif (exclude_patterns) {\n+\t\tfor (size_t i = 0; exclude_patterns[i]; i++) {\n+\t\t\tconst char *pattern = exclude_patterns[i];\n+\t\t\tsize_t len = strlen(pattern);\n+\t\t\tif (!len)\n+\t\t\t\tcontinue;\n+\n+\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t}\n+\n+\t\texclude_patterns = normalized_exclude_patterns.v;\n+\t}\n \n \tif (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n \t\tstatic int ref_paranoia = -1;\n@@ -1719,6 +1733,8 @@ struct ref_iterator *refs_ref_iterator_begin(\n \tif (trim)\n \t\titer = prefix_ref_iterator_begin(iter, \"\", trim);\n \n+\tstrvec_clear(&normalized_exclude_patterns);\n+\n \treturn iter;\n }\n \ndiff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\nindex c04eeb7211..fd58260a24 100755\n--- a/t/t1419-exclude-refs.sh\n+++ b/t/t1419-exclude-refs.sh\n@@ -155,4 +155,14 @@ test_expect_success 'meta-characters are discarded' '\n \tassert_no_jumps perf\n '\n \n+test_expect_success 'empty string exclude pattern is ignored' '\n+\tgit update-ref refs/heads/loose $(git rev-parse refs/heads/foo/1) &&\n+\n+\tfor_each_ref__exclude refs/heads \"\" >actual 2>perf &&\n+\tfor_each_ref >expect &&\n+\n+\ttest_cmp expect actual &&\n+\tassert_no_jumps perf\n+'\n+\n test_done\n-- \n2.49.0.rc1.2.g7e6a5e020ba\n\n"},{"id":"513629","messageId":"7e6a5e020bad14b782a8c85518289220579fae64.1741223981.git.me@ttaylorr.com","threadId":"63065","inReplyTo":"cover.1741223981.git.me@ttaylorr.com","subject":"[PATCH 2/2] refs.c: unify '--exclude' behavior between files and packed backends","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T01:19:53Z","receivedAt":"2025-03-06T01:19:55Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In the packed-refs backend, our implementation of '--exclude' (dating\nback to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\nexcluded pattern(s), 2023-07-10)) considers, for example:\n\n $ git for-each-ref --exclude=refs/heads/ba\n\nto exclude \"refs/heads/bar\", \"refs/heads/baz\", and so on.\n\nThe files backend, which does not implement '--exclude' (and relies on\nthe caller to cull out results that don't match) naturally will\nenumerate \"refs/heads/bar\" and so on.\n\nSo in the above example, 'for-each-ref' will try and see if\n\"refs/heads/ba\" matches \"refs/heads/bar\" (since the files backend simply\nenumerated every loose reference), and, realizing that it does not\nmatch, output the reference as expected. (A caller that did want to\nexclude \"refs/heads/bar\" and \"refs/heads/baz\" might instead run \"git\nfor-each-ref --exclude='refs/heads/ba*'\").\n\nThis can lead to strange behavior, like seeing a different set of\nreferences advertised via 'upload-pack' depending on what set of\nreferences were loose versus packed.\n\nSo there is a subtle bug with '--exclude' which is that in the\npacked-refs backend we will consider \"refs/heads/bar\" to be a pattern\nmatch against \"refs/heads/ba\" when we shouldn't. Likewise, the reftable\nbackend (which in this case is bug-compatible with the packed backend)\nexhibits the same broken behavior.\n\nThere are a few ways to fix this. One is to tighten the rules in\ncmp_record_to_refname(), which is used to determine the start/end-points\nof the jump list used by the packed backend. In this new \"strict\" mode,\nthe comparison function would handle the case where we've reached the\nend of the pattern by introducing a new check like so:\n\n while (1) {\n if (*r1 == '\\n')\n return *r2 ? -1 : 0;\n if (!*r2)\n if (strict && *r1 != '/') /* <- here */\n return 1;\n return start ? 1 : -1;\n if (*r1 != *r2)\n return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;\n r1++;\n r2++;\n }\n\n(eliding out the rest of cmp_record_to_refname()). Equivalently, we\ncould teach refs/packed-backend::populate_excluded_jump_list() to append\na trailing '/' if one does not already exist, forcing an exclude pattern\nlike \"refs/heads/ba\" to only match \"refs/heads/ba/abc\" and so forth.\n\nBut since the same problem exists in reftable, we can fix both at once\nby performing this pre-processing step one layer up in refs.c at the\ncommon entrypoint for the two, which is 'refs_ref_iterator_begin()'.\n\nSince that solution is both the simplest and only requires modification\nin one spot, let's normalize exclude patterns so that they end with a\ntrailing slash. This causes us to unify the behavior between all three\nbackends.\n\nThere is some minor test fallout in the \"overlapping excluded regions\"\ntest, which happens to use 'refs/ba' as an exclude pattern, and expects\nreferences under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\nhierarchies to be excluded from the results.\n\nBut that test fallout is expected, because the test was codifying the\nbuggy behavior to begin with, and should have never been written that\nway.\n\nReported-by: SURA \nHelped-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n refs.c | 6 +++++-\n t/t1419-exclude-refs.sh | 2 +-\n 2 files changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 17d3840aff..2d9a1b51f4 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin(\n \t\t\tif (!len)\n \t\t\t\tcontinue;\n \n-\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t\tif (pattern[len - 1] == '/')\n+\t\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t\telse\n+\t\t\t\tstrvec_pushf(&normalized_exclude_patterns, \"%s/\",\n+\t\t\t\t\t pattern);\n \t\t}\n \n \t\texclude_patterns = normalized_exclude_patterns.v;\ndiff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\nindex fd58260a24..d955cf9541 100755\n--- a/t/t1419-exclude-refs.sh\n+++ b/t/t1419-exclude-refs.sh\n@@ -101,7 +101,7 @@ test_expect_success 'adjacent, non-overlapping excluded regions' '\n \n test_expect_success 'overlapping excluded regions' '\n \tfor_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf &&\n-\tfor_each_ref refs/heads/foo refs/heads/quux >expect &&\n+\tfor_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n \n \ttest_cmp expect actual &&\n \tassert_jumps 1 perf\n-- \n2.49.0.rc1.2.g7e6a5e020ba\n"},{"id":"513634","messageId":"Z8lhKT2KuM3VJ7d-@pks.im","threadId":"63065","inReplyTo":"7e6a5e020bad14b782a8c85518289220579fae64.1741223981.git.me@ttaylorr.com","subject":"Re: [PATCH 2/2] refs.c: unify '--exclude' behavior between files and packed backends","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-03-06T08:47:37Z","receivedAt":"2025-03-06T08:47:47Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Mar 05, 2025 at 08:19:53PM -0500, Taylor Blau wrote:\n\nNit: I'd reword the commit subject to not only talk about \"files\" and\n\"packed\" backends. Or maybe not mention the backend at all, as it is the\nsame bug for every backend that implements excludes. Something like\n\"refs: stop matching non-directory prefixes in exclude patterns\", for\nexample.\n\n[snip]\n> But since the same problem exists in reftable, we can fix both at once\n> by performing this pre-processing step one layer up in refs.c at the\n> common entrypoint for the two, which is 'refs_ref_iterator_begin()'.\n> \n> Since that solution is both the simplest and only requires modification\n> in one spot, let's normalize exclude patterns so that they end with a\n> trailing slash. This causes us to unify the behavior between all three\n> backends.\n\nNice.\n\n> There is some minor test fallout in the \"overlapping excluded regions\"\n> test, which happens to use 'refs/ba' as an exclude pattern, and expects\n> references under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\n> hierarchies to be excluded from the results.\n\nYup, I noticed that this test is asserting the broken behaviour.\n\n> diff --git a/refs.c b/refs.c\n> index 17d3840aff..2d9a1b51f4 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin(\n> \t\t\tif (!len)\n> \t\t\t\tcontinue;\n> \n> -\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n> +\t\t\tif (pattern[len - 1] == '/')\n> +\t\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n> +\t\t\telse\n> +\t\t\t\tstrvec_pushf(&normalized_exclude_patterns, \"%s/\",\n> +\t\t\t\t\t pattern);\n> \t\t}\n> \n> \t\texclude_patterns = normalized_exclude_patterns.v;\n\nThis looks exactly as expected.\n\n> diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\n> index fd58260a24..d955cf9541 100755\n> --- a/t/t1419-exclude-refs.sh\n> +++ b/t/t1419-exclude-refs.sh\n> @@ -101,7 +101,7 @@ test_expect_success 'adjacent, non-overlapping excluded regions' '\n> \n> test_expect_success 'overlapping excluded regions' '\n> \tfor_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf &&\n> -\tfor_each_ref refs/heads/foo refs/heads/quux >expect &&\n> +\tfor_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n> \n> \ttest_cmp expect actual &&\n> \tassert_jumps 1 perf\n\nI was wondering whether this still tests the right thing. But the ranges\nstill are overlapping, as \"refs/heads\" and \"refs/heads/baz\" are. So\njudging by the test description it seems to still do what's advertised.\n\nPatrick\n"},{"id":"513672","messageId":"Z8m3Mo+3l0IxzyOH@nand.local","threadId":"63065","inReplyTo":"Z8lhKT2KuM3VJ7d-@pks.im","subject":"Re: [PATCH 2/2] refs.c: unify '--exclude' behavior between files and packed backends","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T14:54:42Z","receivedAt":"2025-03-06T14:54:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Mar 06, 2025 at 09:47:37AM +0100, Patrick Steinhardt wrote:\n> On Wed, Mar 05, 2025 at 08:19:53PM -0500, Taylor Blau wrote:\n>\n> Nit: I'd reword the commit subject to not only talk about \"files\" and\n> \"packed\" backends. Or maybe not mention the backend at all, as it is the\n> same bug for every backend that implements excludes. Something like\n> \"refs: stop matching non-directory prefixes in exclude patterns\", for\n> example.\n\nFair enough.\n\n> > diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\n> > index fd58260a24..d955cf9541 100755\n> > --- a/t/t1419-exclude-refs.sh\n> > +++ b/t/t1419-exclude-refs.sh\n> > @@ -101,7 +101,7 @@ test_expect_success 'adjacent, non-overlapping excluded regions' '\n> >\n> > test_expect_success 'overlapping excluded regions' '\n> > \tfor_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf &&\n> > -\tfor_each_ref refs/heads/foo refs/heads/quux >expect &&\n> > +\tfor_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n> >\n> > \ttest_cmp expect actual &&\n> > \tassert_jumps 1 perf\n>\n> I was wondering whether this still tests the right thing. But the ranges\n> still are overlapping, as \"refs/heads\" and \"refs/heads/baz\" are. So\n> judging by the test description it seems to still do what's advertised.\n\nThat's not quite true. for_each_ref__exclude treats its first argument\nas the positive half of the query, and the remaining arguments as\nexclusions. So the only excluded regions here are \"refs/heads/ba\" and\n\"refs/heads/baz\", which were overlapping prior to this patch but aren't\nanymore.\n\nSo this test isn't quite doing what it says it is anymore, and should\nreally be called \"non-directory excluded regions\" or similar. But we\nshould still have a separate test that does cover excluded regions,\nwhich needs a new layer underneath some hirearchy, e.g., having\n\"refs/heads/bar/x/...\" and \"refs/heads/bar\" as the excluded regions.\n\nI adjusted those and will push out a new version with the results\nshortly. Thanks for reading closely.\n\nThanks,\nTaylor\n"},{"id":"513712","messageId":"cover.1741275245.git.me@ttaylorr.com","threadId":"63065","inReplyTo":"cover.1741223981.git.me@ttaylorr.com","subject":"[PATCH v2 0/2] refs: a couple of --exclude fixes","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T15:34:44Z","receivedAt":"2025-03-06T15:34:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is a small reroll of my series to fix a couple of quirks with the\n--exclude pattern matching.\n\nThe changes since last time are fairly minor: the second patch's subject\nline was reworded (thanks to a suggestion by Patrick). Likewise, its\ntest script changed slightly to reflect that \"refs/heads/ba\" and\n\"refs/heads/bar\" are no longer considered overlapping regions.\n\nFor convenience, a range-diff is below. Thanks again for your review\n:-).\n\nTaylor Blau (2):\n refs.c: remove empty '--exclude' patterns\n refs.c: stop matching non-directory prefixes in exclude patterns\n\n refs.c | 20 ++++++++++++++++++++\n t/t1419-exclude-refs.sh | 26 ++++++++++++++++++++++++--\n 2 files changed, 44 insertions(+), 2 deletions(-)\n\nRange-diff against v1:\n1: c3b5ca5973 = 1: c3b5ca5973 refs.c: remove empty '--exclude' patterns\n2: 7e6a5e020b ! 2: 67c8c5f797 refs.c: unify '--exclude' behavior between files and packed backends\n @@ Metadata\n Author: Taylor Blau \n\n ## Commit message ##\n - refs.c: unify '--exclude' behavior between files and packed backends\n + refs.c: stop matching non-directory prefixes in exclude patterns\n\n In the packed-refs backend, our implementation of '--exclude' (dating\n back to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\n @@ Commit message\n\n But that test fallout is expected, because the test was codifying the\n buggy behavior to begin with, and should have never been written that\n - way.\n + way. Split that into its own test (since the range is no longer\n + overlapping under the stricter interpretation of --exclude patterns\n + presented here). Create a new test which does have overlapping\n + regions by using a refs/heads/bar/4/... hierarchy and excluding both\n + \"refs/heads/bar\" and \"refs/heads/bar/4\".\n\n Reported-by: SURA \n Helped-by: Jeff King \n @@ refs.c: struct ref_iterator *refs_ref_iterator_begin(\n \t\texclude_patterns = normalized_exclude_patterns.v;\n\n ## t/t1419-exclude-refs.sh ##\n +@@ t/t1419-exclude-refs.sh: test_expect_success 'setup' '\n + \t\t\techo \"create refs/heads/$name/$i $base\" || return 1\n + \t\tdone || return 1\n + \tdone >in &&\n ++\tfor i in 5 6 7\n ++\tdo\n ++\t\techo \"create refs/heads/bar/4/$i $base\" || return 1\n ++\tdone >>in &&\n + \techo \"delete refs/heads/main\" >>in &&\n +\n + \tgit update-ref --stdin actual 2>perf &&\n -\tfor_each_ref refs/heads/foo refs/heads/quux >expect &&\n +\tfor_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n ++\n ++\ttest_cmp expect actual &&\n ++\tassert_jumps 1 perf\n ++'\n ++\n ++test_expect_success 'overlapping excluded regions' '\n ++\tfor_each_ref__exclude refs/heads refs/heads/bar refs/heads/bar/4 >actual 2>perf &&\n ++\tfor_each_ref refs/heads/baz refs/heads/foo refs/heads/quux >expect &&\n\n \ttest_cmp expect actual &&\n \tassert_jumps 1 perf\n\nbase-commit: 6a64ac7b014fa2cfa7a69af3c253bcd53a94b428\n--\n2.49.0.rc1.2.g67c8c5f7978\n"},{"id":"513713","messageId":"c3b5ca597330275391704a0653398ee28f911fc1.1741275245.git.me@ttaylorr.com","threadId":"63065","inReplyTo":"cover.1741275245.git.me@ttaylorr.com","subject":"[PATCH v2 1/2] refs.c: remove empty '--exclude' patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T15:34:48Z","receivedAt":"2025-03-06T15:34:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\nexcluded pattern(s), 2023-07-10), the packed-refs backend learned how to\nconstruct \"jump lists\" to avoid enumerating sections of the packed-refs\nfile that we know the caller is going to throw out anyway.\n\nThis process works by finding the start- and end-points (that is, where\nin the packed-refs file corresponds to the range we're going to ignore)\nfor each exclude pattern, then constructing a jump list based on that.\nAt enumeration time we'll consult the jump list to skip past everything\nin the range(s) found in the previous step, saving time when excluding a\nlarge portion of references.\n\nBut when there is a --exclude pattern which is just the empty string,\nthe behavior is a little funky. When we try and exclude the empty\nstring, the matched range covers the entire packed-refs file, meaning\nthat we won't output any packed references. But the empty pattern\ndoesn't actually match any references to begin with! For example, on my\ncopy of git.git I can do:\n\n $ git for-each-ref '' | wc -l\n 0\n\nSo \"git for-each-ref --exclude=''\" shouldn't actually remove anything\nfrom the output, and ought to be equivalent to \"git for-each-ref\". But\nit's not, and in fact:\n\n $ git for-each-ref | wc -l\n 2229\n $ git for-each-ref --exclude='' | wc -l\n 480\n\nBut why does the '--exclude' version output only some of the references\nin the repository? Here's a hint:\n\n $ find .git/refs -type f | wc -l\n 480\n\nIndeed, because the files backend doesn't implement[^1] the same jump\nlist concept as the packed backend we get the correct result for the\nloose references, but none of the packed references.\n\nSince the empty string exclude pattern doesn't match anything, we can\ndiscard them before the packed-refs backend has a chance to even see it\n(and likewise for reftable, which also implements a similar concept\nsince 1869525066 (refs/reftable: wire up support for exclude patterns,\n2024-09-16)).\n\nThis approach (copying only some of the patterns into a strvec at the\nrefs.c layer) may seem heavy-handed, but it's setting us up to fix\nanother bug in the following commit where the fix will involve modifying\nthe incoming patterns.\n\n[^1]: As noted in 59c35fac54. We technically could avoid opening and\n enumerating the contents of, for e.g., \"$GIT_DIR/refs/heads/foo/\" if\n we knew that we were excluding anything under the 'refs/heads/foo'\n hierarchy. But the --exclude stuff is all best-effort anyway, since\n the caller is expected to cull out any results that they don't want.\n\nNoticed-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n refs.c | 16 ++++++++++++++++\n t/t1419-exclude-refs.sh | 10 ++++++++++\n 2 files changed, 26 insertions(+)\n\ndiff --git a/refs.c b/refs.c\nindex 91da5325d7..17d3840aff 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1699,6 +1699,20 @@ struct ref_iterator *refs_ref_iterator_begin(\n \t\tenum do_for_each_ref_flags flags)\n {\n \tstruct ref_iterator *iter;\n+\tstruct strvec normalized_exclude_patterns = STRVEC_INIT;\n+\n+\tif (exclude_patterns) {\n+\t\tfor (size_t i = 0; exclude_patterns[i]; i++) {\n+\t\t\tconst char *pattern = exclude_patterns[i];\n+\t\t\tsize_t len = strlen(pattern);\n+\t\t\tif (!len)\n+\t\t\t\tcontinue;\n+\n+\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t}\n+\n+\t\texclude_patterns = normalized_exclude_patterns.v;\n+\t}\n \n \tif (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n \t\tstatic int ref_paranoia = -1;\n@@ -1719,6 +1733,8 @@ struct ref_iterator *refs_ref_iterator_begin(\n \tif (trim)\n \t\titer = prefix_ref_iterator_begin(iter, \"\", trim);\n \n+\tstrvec_clear(&normalized_exclude_patterns);\n+\n \treturn iter;\n }\n \ndiff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\nindex c04eeb7211..fd58260a24 100755\n--- a/t/t1419-exclude-refs.sh\n+++ b/t/t1419-exclude-refs.sh\n@@ -155,4 +155,14 @@ test_expect_success 'meta-characters are discarded' '\n \tassert_no_jumps perf\n '\n \n+test_expect_success 'empty string exclude pattern is ignored' '\n+\tgit update-ref refs/heads/loose $(git rev-parse refs/heads/foo/1) &&\n+\n+\tfor_each_ref__exclude refs/heads \"\" >actual 2>perf &&\n+\tfor_each_ref >expect &&\n+\n+\ttest_cmp expect actual &&\n+\tassert_no_jumps perf\n+'\n+\n test_done\n-- \n2.49.0.rc1.2.g67c8c5f7978\n\n"},{"id":"513714","messageId":"67c8c5f797833a9a35f4805059d7e759020f54bd.1741275245.git.me@ttaylorr.com","threadId":"63065","inReplyTo":"cover.1741275245.git.me@ttaylorr.com","subject":"[PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-06T15:34:53Z","receivedAt":"2025-03-06T15:34:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In the packed-refs backend, our implementation of '--exclude' (dating\nback to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\nexcluded pattern(s), 2023-07-10)) considers, for example:\n\n $ git for-each-ref --exclude=refs/heads/ba\n\nto exclude \"refs/heads/bar\", \"refs/heads/baz\", and so on.\n\nThe files backend, which does not implement '--exclude' (and relies on\nthe caller to cull out results that don't match) naturally will\nenumerate \"refs/heads/bar\" and so on.\n\nSo in the above example, 'for-each-ref' will try and see if\n\"refs/heads/ba\" matches \"refs/heads/bar\" (since the files backend simply\nenumerated every loose reference), and, realizing that it does not\nmatch, output the reference as expected. (A caller that did want to\nexclude \"refs/heads/bar\" and \"refs/heads/baz\" might instead run \"git\nfor-each-ref --exclude='refs/heads/ba*'\").\n\nThis can lead to strange behavior, like seeing a different set of\nreferences advertised via 'upload-pack' depending on what set of\nreferences were loose versus packed.\n\nSo there is a subtle bug with '--exclude' which is that in the\npacked-refs backend we will consider \"refs/heads/bar\" to be a pattern\nmatch against \"refs/heads/ba\" when we shouldn't. Likewise, the reftable\nbackend (which in this case is bug-compatible with the packed backend)\nexhibits the same broken behavior.\n\nThere are a few ways to fix this. One is to tighten the rules in\ncmp_record_to_refname(), which is used to determine the start/end-points\nof the jump list used by the packed backend. In this new \"strict\" mode,\nthe comparison function would handle the case where we've reached the\nend of the pattern by introducing a new check like so:\n\n while (1) {\n if (*r1 == '\\n')\n return *r2 ? -1 : 0;\n if (!*r2)\n if (strict && *r1 != '/') /* <- here */\n return 1;\n return start ? 1 : -1;\n if (*r1 != *r2)\n return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;\n r1++;\n r2++;\n }\n\n(eliding out the rest of cmp_record_to_refname()). Equivalently, we\ncould teach refs/packed-backend::populate_excluded_jump_list() to append\na trailing '/' if one does not already exist, forcing an exclude pattern\nlike \"refs/heads/ba\" to only match \"refs/heads/ba/abc\" and so forth.\n\nBut since the same problem exists in reftable, we can fix both at once\nby performing this pre-processing step one layer up in refs.c at the\ncommon entrypoint for the two, which is 'refs_ref_iterator_begin()'.\n\nSince that solution is both the simplest and only requires modification\nin one spot, let's normalize exclude patterns so that they end with a\ntrailing slash. This causes us to unify the behavior between all three\nbackends.\n\nThere is some minor test fallout in the \"overlapping excluded regions\"\ntest, which happens to use 'refs/ba' as an exclude pattern, and expects\nreferences under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\nhierarchies to be excluded from the results.\n\nBut that test fallout is expected, because the test was codifying the\nbuggy behavior to begin with, and should have never been written that\nway. Split that into its own test (since the range is no longer\noverlapping under the stricter interpretation of --exclude patterns\npresented here). Create a new test which does have overlapping\nregions by using a refs/heads/bar/4/... hierarchy and excluding both\n\"refs/heads/bar\" and \"refs/heads/bar/4\".\n\nReported-by: SURA \nHelped-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n refs.c | 6 +++++-\n t/t1419-exclude-refs.sh | 16 ++++++++++++++--\n 2 files changed, 19 insertions(+), 3 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 17d3840aff..2d9a1b51f4 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin(\n \t\t\tif (!len)\n \t\t\t\tcontinue;\n \n-\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t\tif (pattern[len - 1] == '/')\n+\t\t\t\tstrvec_push(&normalized_exclude_patterns, pattern);\n+\t\t\telse\n+\t\t\t\tstrvec_pushf(&normalized_exclude_patterns, \"%s/\",\n+\t\t\t\t\t pattern);\n \t\t}\n \n \t\texclude_patterns = normalized_exclude_patterns.v;\ndiff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\nindex fd58260a24..04797aee59 100755\n--- a/t/t1419-exclude-refs.sh\n+++ b/t/t1419-exclude-refs.sh\n@@ -46,6 +46,10 @@ test_expect_success 'setup' '\n \t\t\techo \"create refs/heads/$name/$i $base\" || return 1\n \t\tdone || return 1\n \tdone >in &&\n+\tfor i in 5 6 7\n+\tdo\n+\t\techo \"create refs/heads/bar/4/$i $base\" || return 1\n+\tdone >>in &&\n \techo \"delete refs/heads/main\" >>in &&\n \n \tgit update-ref --stdin actual 2>perf &&\n-\tfor_each_ref refs/heads/foo refs/heads/quux >expect &&\n+\tfor_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n+\n+\ttest_cmp expect actual &&\n+\tassert_jumps 1 perf\n+'\n+\n+test_expect_success 'overlapping excluded regions' '\n+\tfor_each_ref__exclude refs/heads refs/heads/bar refs/heads/bar/4 >actual 2>perf &&\n+\tfor_each_ref refs/heads/baz refs/heads/foo refs/heads/quux >expect &&\n \n \ttest_cmp expect actual &&\n \tassert_jumps 1 perf\n-- \n2.49.0.rc1.2.g67c8c5f7978\n"},{"id":"513721","messageId":"xmqqjz92hxxi.fsf@gitster.g","threadId":"63065","inReplyTo":"67c8c5f797833a9a35f4805059d7e759020f54bd.1741275245.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-03-06T17:27:21Z","receivedAt":"2025-03-06T17:27:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> So there is a subtle bug with '--exclude' which is that in the\n> packed-refs backend we will consider \"refs/heads/bar\" to be a pattern\n> match against \"refs/heads/ba\" when we shouldn't. Likewise, the reftable\n> backend (which in this case is bug-compatible with the packed backend)\n> exhibits the same broken behavior.\n> ...\n> There is some minor test fallout in the \"overlapping excluded regions\"\n> test, which happens to use 'refs/ba' as an exclude pattern, and expects\n> references under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\n> hierarchies to be excluded from the results.\n>\n> ... test (since the range is no longer\n> overlapping under the stricter interpretation of --exclude patterns\n> presented here).\n\nThe code change, reasoning, and the tests look all good. It just\nleaves a bit awkward aftertaste.\n\nIn general, I think our \"we have a tree-like structure with patterns\nto match paths\" code paths, like pathspec matching, are structured\nin such a way that the low level is expected to merely cull\ncandidates early as a performance optimization measure (in other\nwords, they are allowed false positives and say something matches\nwhen they do not, but not allowed false negatives) and leave the\nupper level to further reject the ones that do not match the\npattern. If packed-refs backend was too loose in its matching and\nerroneously considered that refs/heads/bar matched refs/heads/ba\npattern, I would naïvely expect that the upper layer would catch and\nreject that refs/heads/bar as not matching.\n\nApparently that was not happening and that is why we need this fix?\n\nIs the excluded region optimization expected to be powerful enough\nto cover all our needs so that we do not need to post-process what\nit passes?\n\nThanks. \n"},{"id":"513739","messageId":"Z8q99U9u6HQvHXFT@pks.im","threadId":"63065","inReplyTo":"xmqqjz92hxxi.fsf@gitster.g","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-03-07T09:35:49Z","receivedAt":"2025-03-07T09:35:57Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Mar 06, 2025 at 09:27:21AM -0800, Junio C Hamano wrote:\n> Taylor Blau writes:\n> \n> > So there is a subtle bug with '--exclude' which is that in the\n> > packed-refs backend we will consider \"refs/heads/bar\" to be a pattern\n> > match against \"refs/heads/ba\" when we shouldn't. Likewise, the reftable\n> > backend (which in this case is bug-compatible with the packed backend)\n> > exhibits the same broken behavior.\n> > ...\n> > There is some minor test fallout in the \"overlapping excluded regions\"\n> > test, which happens to use 'refs/ba' as an exclude pattern, and expects\n> > references under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\n> > hierarchies to be excluded from the results.\n> >\n> > ... test (since the range is no longer\n> > overlapping under the stricter interpretation of --exclude patterns\n> > presented here).\n> \n> The code change, reasoning, and the tests look all good. It just\n> leaves a bit awkward aftertaste.\n> \n> In general, I think our \"we have a tree-like structure with patterns\n> to match paths\" code paths, like pathspec matching, are structured\n> in such a way that the low level is expected to merely cull\n> candidates early as a performance optimization measure (in other\n> words, they are allowed false positives and say something matches\n> when they do not, but not allowed false negatives) and leave the\n> upper level to further reject the ones that do not match the\n> pattern. If packed-refs backend was too loose in its matching and\n> erroneously considered that refs/heads/bar matched refs/heads/ba\n> pattern, I would naïvely expect that the upper layer would catch and\n> reject that refs/heads/bar as not matching.\n\nI think you've swapped things around a bit by accident. The problem is\nthat the patterns were being matched too loosely by the underlying\nbackends, which had the consequence that the backends marked too many\nrefs as excluded. As a result, those reference won't ever be yielded to\nthe upper layer at all. So the upper layer doesn't even have a chance to\ncorrect such a mistake at all: it cannot correct what it doesn't know.\n\nThere isn't really a way to implement such a safety net, either (or at\nleast I cannot think of any): the whole point of making backends handle\nthe exclude patterns is that they can skip whole regions entirely and\nnot even try to read them.\n\n> Apparently that was not happening and that is why we need this fix?\n> \n> Is the excluded region optimization expected to be powerful enough\n> to cover all our needs so that we do not need to post-process what\n> it passes?\n\nNo, it's not. But we can only correct false negatives, not false\npositives:\n\n - A false negative is a ref that matches an exclude pattern but that\n we yield regardless from the backend, and those do get handled by\n the upper layer.\n\n - A false positive is a ref that does not match an exclude pattern but\n is still treated as matching by the backend. We thus don't yield\n them, and thus the upper layer cannot rectify the bug.\n\nThe fix at hand fixes false positives.\n\nWhat makes me feel a bit uneasy is that for the \"files\" backend the\noptimization depends on the packed state, which is quite awkward overall\nas our tests may not uncover issues only because we didn't pack refs. I\ndon't really see a way to address this potential test gap generically\nthough.\n\nThe \"reftable\" backend doesn't have the same issue as it does not have\nthe same split between packed and loose refs, so the optimization always\nkicks in.\n\nPatrick\n"},{"id":"513783","messageId":"xmqq7c50g32y.fsf@gitster.g","threadId":"63065","inReplyTo":"Z8q99U9u6HQvHXFT@pks.im","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-03-07T17:31:17Z","receivedAt":"2025-03-07T17:31:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> I think you've swapped things around a bit by accident. The problem is\n> that the patterns were being matched too loosely by the underlying\n> backends, which had the consequence that the backends marked too many\n> refs as excluded.\n\nOK, I agree it is confusing. As a selection mechanism for refs to\nbe shown or processed, exclusion should be \"we omit it because we\nclearly know this one should not be in the final result, but we may\npass questionable ones, relying on our caller to have the final\nsay\". As a selection mechanism for refs to be excluded, the logic\nshould be the other way around, so false positive and false negative\nare going to be swapped. We want the exclusion at the lower layer\nto only say \"this ref clearly matches with given exclusion pattern\",\nbut we used to claim matches for refs that shouldn't match.\n\nOK. Thanks for straightening me out.\n\n> What makes me feel a bit uneasy is that for the \"files\" backend the\n> optimization depends on the packed state, which is quite awkward overall\n> as our tests may not uncover issues only because we didn't pack refs. I\n> don't really see a way to address this potential test gap generically\n> though.\n\nTrue. An obvious optimization for \"files\" _might_ be to lazily walk\nthe directory hierarchy and skip recursive readdir when a directory\nclearly matches the given exclusion pattern, but the result of such\nan optimization (in other words, what would seep through the sieve)\nto be filtered out at the upper layer would be different from what\nthe \"packed-refs\" backend does for its optimization, and they would\nbe different for reftable or any other future backends.\n\nBut I think that is the nature of lower-level optimization---each\nbackend takes advantage of intimately knowing how it organizes the\nunderlying data, and how they can omit without looking into a bulk\nof the section of data deeply would be different.\n\nThanks.\n\n\n\n"},{"id":"513800","messageId":"CABPp-BFn0wht71rM1bE1ABpa6Rn6QRrcVrbN0fhcwprbm+T39Q@mail.gmail.com","threadId":"63065","inReplyTo":"67c8c5f797833a9a35f4805059d7e759020f54bd.1741275245.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-03-07T21:31:31Z","receivedAt":"2025-03-07T21:31:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Mar 6, 2025 at 7:34 AM Taylor Blau wrote:\n>\n> In the packed-refs backend, our implementation of '--exclude' (dating\n> back to 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\n> excluded pattern(s), 2023-07-10)) considers, for example:\n>\n> $ git for-each-ref --exclude=refs/heads/ba\n>\n> to exclude \"refs/heads/bar\", \"refs/heads/baz\", and so on.\n>\n> The files backend, which does not implement '--exclude' (and relies on\n> the caller to cull out results that don't match) naturally will\n> enumerate \"refs/heads/bar\" and so on.\n>\n> So in the above example, 'for-each-ref' will try and see if\n> \"refs/heads/ba\" matches \"refs/heads/bar\" (since the files backend simply\n> enumerated every loose reference), and, realizing that it does not\n> match, output the reference as expected. (A caller that did want to\n> exclude \"refs/heads/bar\" and \"refs/heads/baz\" might instead run \"git\n> for-each-ref --exclude='refs/heads/ba*'\").\n>\n> This can lead to strange behavior, like seeing a different set of\n> references advertised via 'upload-pack' depending on what set of\n> references were loose versus packed.\n>\n> So there is a subtle bug with '--exclude' which is that in the\n> packed-refs backend we will consider \"refs/heads/bar\" to be a pattern\n> match against \"refs/heads/ba\" when we shouldn't. Likewise, the reftable\n> backend (which in this case is bug-compatible with the packed backend)\n> exhibits the same broken behavior.\n\nYuck; nice to see this being addressed.\n\n> There are a few ways to fix this. One is to tighten the rules in\n> cmp_record_to_refname(), which is used to determine the start/end-points\n> of the jump list used by the packed backend. In this new \"strict\" mode,\n> the comparison function would handle the case where we've reached the\n> end of the pattern by introducing a new check like so:\n>\n> while (1) {\n> if (*r1 == '\\n')\n> return *r2 ? -1 : 0;\n> if (!*r2)\n> if (strict && *r1 != '/') /* <- here */\n> return 1;\n> return start ? 1 : -1;\n> if (*r1 != *r2)\n> return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;\n> r1++;\n> r2++;\n> }\n>\n> (eliding out the rest of cmp_record_to_refname()). Equivalently, we\n> could teach refs/packed-backend::populate_excluded_jump_list() to append\n> a trailing '/' if one does not already exist, forcing an exclude pattern\n> like \"refs/heads/ba\" to only match \"refs/heads/ba/abc\" and so forth.\n>\n> But since the same problem exists in reftable, we can fix both at once\n> by performing this pre-processing step one layer up in refs.c at the\n> common entrypoint for the two, which is 'refs_ref_iterator_begin()'.\n>\n> Since that solution is both the simplest and only requires modification\n> in one spot, let's normalize exclude patterns so that they end with a\n> trailing slash. This causes us to unify the behavior between all three\n> backends.\n\n:-)\n\n> There is some minor test fallout in the \"overlapping excluded regions\"\n> test, which happens to use 'refs/ba' as an exclude pattern, and expects\n> references under the \"refs/heads/bar/*\" and \"refs/heads/baz/*\"\n> hierarchies to be excluded from the results.\n>\n> But that test fallout is expected, because the test was codifying the\n> buggy behavior to begin with, and should have never been written that\n> way. Split that into its own test (since the range is no longer\n> overlapping under the stricter interpretation of --exclude patterns\n> presented here). Create a new test which does have overlapping\n> regions by using a refs/heads/bar/4/... hierarchy and excluding both\n> \"refs/heads/bar\" and \"refs/heads/bar/4\".\n\nAlways nice to see tests corrected.\n\n> Reported-by: SURA \n> Helped-by: Jeff King \n> Signed-off-by: Taylor Blau \n> ---\n> refs.c | 6 +++++-\n> t/t1419-exclude-refs.sh | 16 ++++++++++++++--\n> 2 files changed, 19 insertions(+), 3 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index 17d3840aff..2d9a1b51f4 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin(\n> if (!len)\n> continue;\n>\n> - strvec_push(&normalized_exclude_patterns, pattern);\n> + if (pattern[len - 1] == '/')\n> + strvec_push(&normalized_exclude_patterns, pattern);\n> + else\n> + strvec_pushf(&normalized_exclude_patterns, \"%s/\",\n> + pattern);\n\nDoesn't this mean that if the user requested to exclude\n\"refs/heads/bar\" and \"refs/heads/bar\" exists, that we won't exclude it\nbecause it doesn't have a trailing slash?\n\nFrom reading other comments in this thread, I guess that ends up being\nokay, because we only promise to filter out what we can cheaply\nfilter, and we rely on our caller to double-check everything and do\nthe real filtering.\n\n...but it gives me some ugly dir.c vibes, reminding me of 95c11ecc73f2\n(Fix error-prone fill_directory() API; make it only return matches,\n2020-04-01) and a slew of related bugs preceding it. Granted, dir.c\nhad this tri-state to deal with (tracked, untracked-but-ignored,\nuntracked-and-not-ignored) and simplifying of whole directories, which\ndon't apply here, so maybe the similarity of\n\"fast-filtering-only-and-rely-on-caller\" won't be a problem since the\nupper level filtering is so much more straightforward.\n\nShould this at least be called out in the commit message, though?\n\n> }\n>\n> exclude_patterns = normalized_exclude_patterns.v;\n> diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\n> index fd58260a24..04797aee59 100755\n> --- a/t/t1419-exclude-refs.sh\n> +++ b/t/t1419-exclude-refs.sh\n> @@ -46,6 +46,10 @@ test_expect_success 'setup' '\n> echo \"create refs/heads/$name/$i $base\" || return 1\n> done || return 1\n> done >in &&\n> + for i in 5 6 7\n> + do\n> + echo \"create refs/heads/bar/4/$i $base\" || return 1\n> + done >>in &&\n> echo \"delete refs/heads/main\" >>in &&\n>\n> git update-ref --stdin @@ -99,9 +103,17 @@ test_expect_success 'adjacent, non-overlapping excluded regions' '\n> esac\n> '\n>\n> -test_expect_success 'overlapping excluded regions' '\n> +test_expect_success 'non-directory excluded regions' '\n> for_each_ref__exclude refs/heads refs/heads/ba refs/heads/baz >actual 2>perf &&\n> - for_each_ref refs/heads/foo refs/heads/quux >expect &&\n> + for_each_ref refs/heads/bar refs/heads/foo refs/heads/quux >expect &&\n> +\n> + test_cmp expect actual &&\n> + assert_jumps 1 perf\n> +'\n> +\n> +test_expect_success 'overlapping excluded regions' '\n> + for_each_ref__exclude refs/heads refs/heads/bar refs/heads/bar/4 >actual 2>perf &&\n> + for_each_ref refs/heads/baz refs/heads/foo refs/heads/quux >expect &&\n>\n> test_cmp expect actual &&\n> assert_jumps 1 perf\n> --\n> 2.49.0.rc1.2.g67c8c5f7978\n\nOther than the one surprise noted above, looks good to me.\n"},{"id":"513801","messageId":"CABPp-BE3u=YVCU20Bz4jZc90DkmArE=v02WjOzr-uO6kV6Zfng@mail.gmail.com","threadId":"63065","inReplyTo":"c3b5ca597330275391704a0653398ee28f911fc1.1741275245.git.me@ttaylorr.com","subject":"Re: [PATCH v2 1/2] refs.c: remove empty '--exclude' patterns","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-03-07T21:32:49Z","receivedAt":"2025-03-07T21:33:01Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Mar 6, 2025 at 7:34 AM Taylor Blau wrote:\n>\n> In 59c35fac54 (refs/packed-backend.c: implement jump lists to avoid\n> excluded pattern(s), 2023-07-10), the packed-refs backend learned how to\n> construct \"jump lists\" to avoid enumerating sections of the packed-refs\n> file that we know the caller is going to throw out anyway.\n>\n> This process works by finding the start- and end-points (that is, where\n> in the packed-refs file corresponds to the range we're going to ignore)\n> for each exclude pattern, then constructing a jump list based on that.\n> At enumeration time we'll consult the jump list to skip past everything\n> in the range(s) found in the previous step, saving time when excluding a\n> large portion of references.\n>\n> But when there is a --exclude pattern which is just the empty string,\n> the behavior is a little funky. When we try and exclude the empty\n> string, the matched range covers the entire packed-refs file, meaning\n> that we won't output any packed references. But the empty pattern\n> doesn't actually match any references to begin with! For example, on my\n> copy of git.git I can do:\n>\n> $ git for-each-ref '' | wc -l\n> 0\n>\n> So \"git for-each-ref --exclude=''\" shouldn't actually remove anything\n> from the output, and ought to be equivalent to \"git for-each-ref\". But\n> it's not, and in fact:\n>\n> $ git for-each-ref | wc -l\n> 2229\n> $ git for-each-ref --exclude='' | wc -l\n> 480\n>\n> But why does the '--exclude' version output only some of the references\n> in the repository? Here's a hint:\n>\n> $ find .git/refs -type f | wc -l\n> 480\n>\n> Indeed, because the files backend doesn't implement[^1] the same jump\n> list concept as the packed backend we get the correct result for the\n> loose references, but none of the packed references.\n>\n> Since the empty string exclude pattern doesn't match anything, we can\n> discard them before the packed-refs backend has a chance to even see it\n> (and likewise for reftable, which also implements a similar concept\n> since 1869525066 (refs/reftable: wire up support for exclude patterns,\n> 2024-09-16)).\n>\n> This approach (copying only some of the patterns into a strvec at the\n> refs.c layer) may seem heavy-handed, but it's setting us up to fix\n> another bug in the following commit where the fix will involve modifying\n> the incoming patterns.\n>\n> [^1]: As noted in 59c35fac54. We technically could avoid opening and\n> enumerating the contents of, for e.g., \"$GIT_DIR/refs/heads/foo/\" if\n> we knew that we were excluding anything under the 'refs/heads/foo'\n> hierarchy. But the --exclude stuff is all best-effort anyway, since\n> the caller is expected to cull out any results that they don't want.\n>\n> Noticed-by: Jeff King \n> Signed-off-by: Taylor Blau \n> ---\n> refs.c | 16 ++++++++++++++++\n> t/t1419-exclude-refs.sh | 10 ++++++++++\n> 2 files changed, 26 insertions(+)\n>\n> diff --git a/refs.c b/refs.c\n> index 91da5325d7..17d3840aff 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -1699,6 +1699,20 @@ struct ref_iterator *refs_ref_iterator_begin(\n> enum do_for_each_ref_flags flags)\n> {\n> struct ref_iterator *iter;\n> + struct strvec normalized_exclude_patterns = STRVEC_INIT;\n> +\n> + if (exclude_patterns) {\n> + for (size_t i = 0; exclude_patterns[i]; i++) {\n> + const char *pattern = exclude_patterns[i];\n> + size_t len = strlen(pattern);\n> + if (!len)\n> + continue;\n> +\n> + strvec_push(&normalized_exclude_patterns, pattern);\n> + }\n> +\n> + exclude_patterns = normalized_exclude_patterns.v;\n> + }\n>\n> if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n> static int ref_paranoia = -1;\n> @@ -1719,6 +1733,8 @@ struct ref_iterator *refs_ref_iterator_begin(\n> if (trim)\n> iter = prefix_ref_iterator_begin(iter, \"\", trim);\n>\n> + strvec_clear(&normalized_exclude_patterns);\n> +\n> return iter;\n> }\n>\n> diff --git a/t/t1419-exclude-refs.sh b/t/t1419-exclude-refs.sh\n> index c04eeb7211..fd58260a24 100755\n> --- a/t/t1419-exclude-refs.sh\n> +++ b/t/t1419-exclude-refs.sh\n> @@ -155,4 +155,14 @@ test_expect_success 'meta-characters are discarded' '\n> assert_no_jumps perf\n> '\n>\n> +test_expect_success 'empty string exclude pattern is ignored' '\n> + git update-ref refs/heads/loose $(git rev-parse refs/heads/foo/1) &&\n> +\n> + for_each_ref__exclude refs/heads \"\" >actual 2>perf &&\n> + for_each_ref >expect &&\n> +\n> + test_cmp expect actual &&\n> + assert_no_jumps perf\n> +'\n> +\n> test_done\n> --\n> 2.49.0.rc1.2.g67c8c5f7978\n\nMakes sense...but doesn't the second patch also fix this issue without\nthe first patch being needed?\n"},{"id":"513819","messageId":"Z8uDMHclfE+KqBMz@nand.local","threadId":"63065","inReplyTo":"CABPp-BE3u=YVCU20Bz4jZc90DkmArE=v02WjOzr-uO6kV6Zfng@mail.gmail.com","subject":"Re: [PATCH v2 1/2] refs.c: remove empty '--exclude' patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-07T23:37:20Z","receivedAt":"2025-03-07T23:37:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 07, 2025 at 01:32:49PM -0800, Elijah Newren wrote:\n> Makes sense...but doesn't the second patch also fix this issue without\n> the first patch being needed?\n\nIt does, but the mechanism is pretty round-about. (From a quick glance\nwe'll turn the empty pattern \"\" into \"/\" which won't match anything, and\nthus won't contribute to the jump list).\n\nBut there are a couple of reasons to keep this patch. Most importantly,\nit hardens us against potential future regressions here with the empty\npattern. And it makes dealing with that case much more explicit by\nthrowing those patterns out before they make their way to the backends\ninstead of the quirk above.\n\nThanks,\nTaylor\n"},{"id":"513820","messageId":"Z8uEd926AFgA7HlC@nand.local","threadId":"63065","inReplyTo":"xmqq7c50g32y.fsf@gitster.g","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-07T23:42:47Z","receivedAt":"2025-03-07T23:42:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 07, 2025 at 09:31:17AM -0800, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n>\n> > I think you've swapped things around a bit by accident. The problem is\n> > that the patterns were being matched too loosely by the underlying\n> > backends, which had the consequence that the backends marked too many\n> > refs as excluded.\n>\n> OK, I agree it is confusing. As a selection mechanism for refs to\n> be shown or processed, exclusion should be \"we omit it because we\n> clearly know this one should not be in the final result, but we may\n> pass questionable ones, relying on our caller to have the final\n> say\". As a selection mechanism for refs to be excluded, the logic\n> should be the other way around, so false positive and false negative\n> are going to be swapped. We want the exclusion at the lower layer\n> to only say \"this ref clearly matches with given exclusion pattern\",\n> but we used to claim matches for refs that shouldn't match.\n>\n> OK. Thanks for straightening me out.\n\nYes, Patrick is exactly right here. Thanks, Patrick, for beating me to\nthe punch ;-).\n\n> > What makes me feel a bit uneasy is that for the \"files\" backend the\n> > optimization depends on the packed state, which is quite awkward overall\n> > as our tests may not uncover issues only because we didn't pack refs. I\n> > don't really see a way to address this potential test gap generically\n> > though.\n>\n> True. An obvious optimization for \"files\" _might_ be to lazily walk\n> the directory hierarchy and skip recursive readdir when a directory\n> clearly matches the given exclusion pattern, but the result of such\n> an optimization (in other words, what would seep through the sieve)\n> to be filtered out at the upper layer would be different from what\n> the \"packed-refs\" backend does for its optimization, and they would\n> be different for reftable or any other future backends.\n\nI had considered doing this back when I wrote 59c35fac54\n(refs/packed-backend.c: implement jump lists to avoid excluded\npattern(s), 2023-07-10).\n\nBut I decided against it for a couple of reasons. First, it's a little\nmore complicated than the packed backend's implementation, since we have\nto consider the additional context of what layer of the $GIT_DIR/refs\ndirectory we're in to construct the full prefix in order to even perform\nthe match.\n\nBut the second reason was that we should never have so many loose\nreferences sitting around for this optimization to even matter. If we're\nin a case where it does, then the repository in question should \"git\npack-refs --all\" to take advantage of the optimization.\n\n> But I think that is the nature of lower-level optimization---each\n> backend takes advantage of intimately knowing how it organizes the\n> underlying data, and how they can omit without looking into a bulk\n> of the section of data deeply would be different.\n\nYep.\n\nThanks,\nTaylor\n"},{"id":"513821","messageId":"Z8uFcvHRcBExhjNS@nand.local","threadId":"63065","inReplyTo":"CABPp-BFn0wht71rM1bE1ABpa6Rn6QRrcVrbN0fhcwprbm+T39Q@mail.gmail.com","subject":"Re: [PATCH v2 2/2] refs.c: stop matching non-directory prefixes in exclude patterns","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-03-07T23:46:58Z","receivedAt":"2025-03-07T23:47:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Mar 07, 2025 at 01:31:31PM -0800, Elijah Newren wrote:\n> > diff --git a/refs.c b/refs.c\n> > index 17d3840aff..2d9a1b51f4 100644\n> > --- a/refs.c\n> > +++ b/refs.c\n> > @@ -1708,7 +1708,11 @@ struct ref_iterator *refs_ref_iterator_begin(\n> > if (!len)\n> > continue;\n> >\n> > - strvec_push(&normalized_exclude_patterns, pattern);\n> > + if (pattern[len - 1] == '/')\n> > + strvec_push(&normalized_exclude_patterns, pattern);\n> > + else\n> > + strvec_pushf(&normalized_exclude_patterns, \"%s/\",\n> > + pattern);\n>\n> Doesn't this mean that if the user requested to exclude\n> \"refs/heads/bar\" and \"refs/heads/bar\" exists, that we won't exclude it\n> because it doesn't have a trailing slash?\n>\n> >From reading other comments in this thread, I guess that ends up being\n> okay, because we only promise to filter out what we can cheaply\n> filter, and we rely on our caller to double-check everything and do\n> the real filtering.\n>\n> ...but it gives me some ugly dir.c vibes, reminding me of 95c11ecc73f2\n> (Fix error-prone fill_directory() API; make it only return matches,\n> 2020-04-01) and a slew of related bugs preceding it. Granted, dir.c\n> had this tri-state to deal with (tracked, untracked-but-ignored,\n> untracked-and-not-ignored) and simplifying of whole directories, which\n> don't apply here, so maybe the similarity of\n> \"fast-filtering-only-and-rely-on-caller\" won't be a problem since the\n> upper level filtering is so much more straightforward.\n>\n> Should this at least be called out in the commit message, though?\n\nYeah, I think that we don't have a tri-state here to deal with as was\nthe case in 95c11ecc732 makes this a little easier to reason about.\n\nAnd you're right: if we have a pattern like \"refs/heads/bar\" and we see\na leaf in our reference hierarchy called \"refs/heads/bar\", the packed\nbackend will not exclude it.\n\nThis is OK because the exclude pattern stuff is all considered\n\"best-effort\" and callers are expected to do their own filtering. Note\nthat the exclude patterns (at least in the packed backend) don't know\nhow to handle meta-characters (there's a big comment in\nrefs/packed-backend.c explaining why). So we can't guarantee the absence\nof false positives without performing the same post-processing as the\ncaller would.\n\nEven prior to this commit, a literal match in the excluded patterns\nwould result in a region whose start- and end-points are the same, and\nwe'd throw it out before it made its way into the jump list.\n\nThanks,\nTaylor\n"},{"id":"513822","messageId":"CABPp-BG_mXT1fv0G2QXJg4WJuVZcWbPHG_9VQ8Szf8Ges4fGJw@mail.gmail.com","threadId":"63065","inReplyTo":"Z8uDMHclfE+KqBMz@nand.local","subject":"Re: [PATCH v2 1/2] refs.c: remove empty '--exclude' patterns","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-03-07T23:58:16Z","receivedAt":"2025-03-07T23:58:27Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Mar 7, 2025 at 3:37 PM Taylor Blau wrote:\n>\n> On Fri, Mar 07, 2025 at 01:32:49PM -0800, Elijah Newren wrote:\n> > Makes sense...but doesn't the second patch also fix this issue without\n> > the first patch being needed?\n>\n> It does, but the mechanism is pretty round-about. (From a quick glance\n> we'll turn the empty pattern \"\" into \"/\" which won't match anything, and\n> thus won't contribute to the jump list).\n\nHow is that round-about? The whole point of patch 2 is to stop\nmatching on excludes as a prefix unless that prefix is a directory\nname, right? To me, patch 1 merely looks like a special case of patch\n2.\n\n> But there are a couple of reasons to keep this patch. Most importantly,\n> it hardens us against potential future regressions here with the empty\n> pattern.\n\nI'm fine with leaving the patch in place, since it doesn't hurt\nanything. And if the empty pattern is especially problematic, I can\nsee this logic.\n\n> And it makes dealing with that case much more explicit by\n> throwing those patterns out before they make their way to the backends\n> instead of the quirk above.\n\nI don't understand this reason, though. It feels to me like the\ndesign behind patch 2 rather than a \"quirk\"...but maybe the fact that\npatch 2 doesn't exclude \"refs/heads/bar\" (at the low-level) even when\nthat exact string is given as an exclude was unintentional or\nsomething? If it was an intentional part of patch 2 (as I assumed\nwhile reading it), then I don't see how patch 2 excluding the empty\nstring exclude is a \"quirk\". Am I missing something?\n\n(Not that it matters, since I'm fine with keeping the patch for your\nfirst reason, I'm just curious...)\n"}]}