{"thread":{"id":"65776","subject":"[PATCH v2 0/2] Reuse --contains traversal results","startedAt":"2026-06-09T02:36:42Z","lastAt":"2026-07-16T09:19:26Z","messageCount":25,"participants":["Tamir Duberstein","Karthik Nayak","Jeff King","Kristofer Karlsson","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"544998","messageId":"20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com","threadId":"65776","inReplyTo":null,"subject":"[PATCH v2 0/2] Reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-09T02:36:33Z","receivedAt":"2026-06-09T02:36:42Z","isPatch":true,"body":"The memoized traversal used by git tag avoids repeating graph walks for\nrefs with shared history. Extend it to the other ref-filter users after\nmaking the existing traversal safe for cycles introduced by replacement\nrefs.\n\nSigned-off-by: Tamir Duberstein \n\n---\nChanges in v2:\n- Split cycle handling into a preparatory patch.\n- Exercise cycle handling through the existing git tag path.\n- Move perf result verification out of setup.\n- Link to v1: https://patch.msgid.link/20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com\n\n---\nTamir Duberstein (2):\n commit-reach: handle cycles in contains walk\n ref-filter: memoize --contains with generations\n\n commit-reach.c | 43 ++++++++++++++++++++++++++++++------\n commit-reach.h | 10 ++++++++-\n t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n t/t7004-tag.sh | 21 ++++++++++++++++++\n 5 files changed, 137 insertions(+), 8 deletions(-)\n---\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nchange-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n\nBest regards,\n-- \nTamir Duberstein \n\n"},{"id":"544999","messageId":"20260608-ref-filter-memoized-contains-v2-1-e72720344a7c@gmail.com","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com","subject":"[PATCH v2 1/2] commit-reach: handle cycles in contains walk","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-09T02:36:34Z","receivedAt":"2026-06-09T02:36:44Z","isPatch":true,"body":"git tag --contains uses a memoized traversal that assumes commit\nancestry is acyclic. Replacement refs can violate that assumption,\ncausing the traversal to revisit a commit already on its stack\nindefinitely.\n\nMark commits while they are active. If the traversal encounters an\nactive commit, discard the cache because it cannot distinguish answers\nproduced by the interrupted walk. Then fall back to the cycle-safe\nreachability walk for that candidate.\n\nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 30 ++++++++++++++++++++++++++----\n commit-reach.h | 3 ++-\n t/t7004-tag.sh | 21 +++++++++++++++++++++\n 3 files changed, 49 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..65b618959b 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -708,7 +708,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \n /*\n * Test whether the candidate is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n+ * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n+ * inconclusive.\n */\n static enum contains_result contains_test(struct commit *candidate,\n \t\t\t\t\t const struct commit_list *want,\n@@ -744,7 +745,7 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n }\n \n static enum contains_result contains_tag_algo(struct commit *candidate,\n-\t\t\t\t\t const struct commit_list *want,\n+\t\t\t\t\t struct commit_list *want,\n \t\t\t\t\t struct contains_cache *cache)\n {\n \tstruct contains_stack contains_stack = { 0, 0, NULL };\n@@ -765,6 +766,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tif (result != CONTAINS_UNKNOWN)\n \t\treturn result;\n \n+\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n \tpush_to_contains_stack(candidate, &contains_stack);\n \twhile (contains_stack.nr) {\n \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n@@ -776,8 +778,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\t\tcontains_stack.nr--;\n \t\t}\n \t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful yes/no.\n+\t\t * A parent may have just been popped and marked, or may still\n+\t\t * be active when replacement refs create a cycle.\n \t\t */\n \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n \t\tcase CONTAINS_YES:\n@@ -787,13 +789,33 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\tcase CONTAINS_NO:\n \t\t\tentry->parents = parents->next;\n \t\t\tbreak;\n+\t\tcase CONTAINS_IN_PROGRESS:\n+\t\t\t/*\n+\t\t\t * Partial negative answers are not safe across a cycle.\n+\t\t\t * Discard them and use the cycle-safe reachability walk.\n+\t\t\t */\n+\t\t\tgoto cycle;\n \t\tcase CONTAINS_UNKNOWN:\n+\t\t\t*contains_cache_at(cache, parents->item) =\n+\t\t\t\tCONTAINS_IN_PROGRESS;\n \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n \t\t\tbreak;\n \t\t}\n \t}\n \tfree(contains_stack.contains_stack);\n \treturn contains_test(candidate, want, cache, cutoff);\n+\n+cycle:\n+\tfree(contains_stack.contains_stack);\n+\tclear_contains_cache(cache);\n+\tinit_contains_cache(cache);\n+\n+\tresult = repo_is_descendant_of(the_repository, candidate, want);\n+\tif (result < 0)\n+\t\texit(128);\n+\t*contains_cache_at(cache, candidate) =\n+\t\tresult ? CONTAINS_YES : CONTAINS_NO;\n+\treturn result ? CONTAINS_YES : CONTAINS_NO;\n }\n \n int commit_contains(struct ref_filter *filter, struct commit *commit,\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..f908d305b1 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -73,7 +73,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n enum contains_result {\n \tCONTAINS_UNKNOWN = 0,\n \tCONTAINS_NO,\n-\tCONTAINS_YES\n+\tCONTAINS_YES,\n+\tCONTAINS_IN_PROGRESS\n };\n \n define_commit_slab(contains_cache, enum contains_result);\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex d918005dd9..1ed91bb66e 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1611,6 +1611,27 @@ test_expect_success 'checking that first commit is in all tags (hash)' '\n \ttest_cmp expected actual\n '\n \n+test_expect_success 'tag --contains handles cyclic replacement histories' '\n+\tfirst=$(git rev-parse HEAD~2) &&\n+\tsecond=$(git rev-parse HEAD~) &&\n+\tthird=$(git rev-parse HEAD) &&\n+\ttest_when_finished \"\n+\t\tgit replace -d $first\n+\t\tgit replace -d $third\n+\t\tgit tag -d cycle-a cycle-b\n+\t\" &&\n+\tgit tag cycle-a \"$first\" &&\n+\tgit tag cycle-b \"$third\" &&\n+\tgit replace --graft \"$first\" \"$third\" \"$second\" &&\n+\tgit replace --graft \"$third\" \"$first\" &&\n+\tcat >expected <<-\\EOF &&\n+\tcycle-a\n+\tcycle-b\n+\tEOF\n+\tgit tag --contains=\"$second\" --list \"cycle-*\" >actual &&\n+\ttest_cmp expected actual\n+'\n+\n # other ways of specifying the commit\n test_expect_success 'checking that first commit is in all tags (tag)' '\n \tcat >expected <<-\\EOF &&\n\n-- \n2.54.0.501.g0fb508de08\n\n"},{"id":"545000","messageId":"20260608-ref-filter-memoized-contains-v2-2-e72720344a7c@gmail.com","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com","subject":"[PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-09T02:36:35Z","receivedAt":"2026-06-09T02:36:46Z","isPatch":true,"body":"git branch and git for-each-ref call repo_is_descendant_of() for\neach candidate selected by --contains or --no-contains. Each call\nstarts a new graph walk, so refs with shared history repeatedly\ntraverse the same commits.\n\nffc4b8012d (tag: speed up --contains calculation, 2011-06-11)\nintroduced a depth-first walk for git tag that caches positive and\nnegative answers across candidates. ee2bd06b0f (ref-filter: implement\n'--contains' option, 2015-07-07) preserved both implementations when\nref-filter learned --contains.\n\nThe memoized walk is not always faster. Without generation numbers,\na negative check can walk to the root even when the breadth-first\nmerge-base walk finds a nearby divergence. With generation numbers,\nthe depth-first walk can stop below the oldest target while still\nreusing answers across candidates.\n\nKeep the existing memoized selection for git tag. Select it for other\nref-filter callers when generation numbers are enabled, and retain\nthe breadth-first walk otherwise.\n\nWhen generation numbers are unavailable, repo_is_descendant_of() can\nreturn -1 if ancestry cannot be read. The ref-filter Boolean interface\ntreated that error as a match. Check it and exit instead. The memoized\npath already dies on the same parse failure, so both selected paths now\nfail rather than return a result.\n\nAdd p1500 cases for up to 8,192 packed refs along one first-parent\nhistory and for sibling refs near the tip with generation numbers\nforced off.\n\nOn a checkout with 62,174 remote-tracking refs and generation numbers\nenabled, I ran:\n\n hyperfine --warmup 0 --runs 3 \\\n --command-name parent \\\n '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n --command-name this-commit \\\n '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n\nThe results were:\n\n parent this commit\n elapsed 104.365 s 467.7 ms\n user 93.702 s 220.2 ms\n system 0.723 s 182.7 ms\n\nThe wall-time standard deviations were 11.356 seconds and 133.8\nmilliseconds, respectively. Separate runs without redirection produced\nthe same output with SHA-256\n2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n\nBoth revisions were built with the default -O2 flags using Apple\nclang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)\nwith a 16-core Apple M4 Max (12 performance and four efficiency\ncores) and 128 GB RAM.\n\nLink: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\nLink: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\nLink: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\nLink: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\nSuggested-by: Jeff King \nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 13 +++++++++--\n commit-reach.h | 7 ++++++\n t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n 4 files changed, 88 insertions(+), 3 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 65b618959b..83a48004ef 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n+\tint result;\n+\n+\tif (!list)\n+\t\treturn 1;\n+\tif (filter->with_commit_tag_algo ||\n+\t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n-\treturn repo_is_descendant_of(the_repository, commit, list);\n+\n+\tresult = repo_is_descendant_of(the_repository, commit, list);\n+\tif (result < 0)\n+\t\texit(128);\n+\treturn result;\n }\n \n int can_all_from_reach_with_flag(struct object_array *from,\ndiff --git a/commit-reach.h b/commit-reach.h\nindex f908d305b1..da6796a354 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -79,6 +79,13 @@ enum contains_result {\n \n define_commit_slab(contains_cache, enum contains_result);\n \n+/*\n+ * Return whether \"commit\" is a descendant of any commit in \"list\". An empty\n+ * list matches.\n+ *\n+ * The memoized traversal records answers in \"cache\" for one fixed \"list\".\n+ * Clear it before changing the list.\n+ */\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache);\n \ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex 5b23ce5db9..99b54e274b 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -32,12 +32,47 @@ test_expect_success 'setup' '\n \t\techo \"X:$line\" >>test-tool-tags || return 1\n \tdone &&\n \n-\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit rev-list --first-parent --max-count=8192 HEAD >contains-commits &&\n+\ttest_file_not_empty contains-commits &&\n+\tgit update-ref refs/contains-perf-base \"$(tail -n 1 contains-commits)\" &&\n+\tawk \"{\n+\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n+\t}\" contains-commits |\n+\t\tgit update-ref --stdin &&\n+\tgit pack-refs --include \"refs/contains-perf/*\" &&\n+\n+\ttree=$(git rev-parse HEAD^{tree}) &&\n+\tbase=$(git rev-parse HEAD) &&\n+\ttarget=$(echo target | git commit-tree \"$tree\" -p \"$base\") &&\n+\tgit update-ref refs/contains-diverged/target \"$target\" &&\n+\tfor i in $(test_seq 1 4)\n+\tdo\n+\t\tcommit=$(echo candidate-$i |\n+\t\t\tgit commit-tree \"$tree\" -p \"$base\") &&\n+\t\tgit update-ref refs/contains-diverged/candidate-$i \"$commit\" ||\n+\t\treturn 1\n+\tdone &&\n+\n+\tcommit=$(git commit-tree \"$tree\") &&\n \tgit update-ref refs/heads/disjoint-base $commit &&\n \n \tgit commit-graph write --reachable\n '\n \n+test_expect_success 'verify contains results' '\n+\tgit for-each-ref --contains=refs/contains-perf-base \\\n+\t\trefs/contains-perf/ >actual &&\n+\ttest_line_count = $(wc -l expect &&\n+\tGIT_TEST_COMMIT_GRAPH=0 \\\n+\t\tgit -c core.commitGraph=false for-each-ref \\\n+\t\t\t--format=\"%(refname)\" \\\n+\t\t\t--contains=refs/contains-diverged/target \\\n+\t\t\trefs/contains-diverged/ >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_perf 'ahead-behind counts: git for-each-ref' '\n \tgit for-each-ref --format=\"%(ahead-behind:HEAD)\" --stdin /dev/null\n+'\n+\n+test_perf 'contains without generations: divergent refs' '\n+\tGIT_TEST_COMMIT_GRAPH=0 \\\n+\t\tgit -c core.commitGraph=false for-each-ref \\\n+\t\t\t--contains=refs/contains-diverged/target \\\n+\t\t\trefs/contains-diverged/ >/dev/null\n+'\n+\n test_perf 'is-base check: test-tool reach (refs)' '\n \ttest-tool reach get_branch_base_for_tip commit &&\n+\tbroken=$(git hash-object -t commit -w commit) &&\n+\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n+\tfor option in --contains --no-contains\n+\tdo\n+\t\ttest_must_fail git for-each-ref \"$option=HEAD\" \\\n+\t\t\trefs/heads/missing-parent >out 2>err &&\n+\t\ttest_must_be_empty out &&\n+\t\ttest_grep \"parse commit $MISSING\" err ||\n+\t\treturn 1\n+\tdone\n+'\n+\n test_expect_success 'ahead-behind requires an argument' '\n \ttest_must_fail git for-each-ref \\\n \t\t--format=\"%(ahead-behind)\" 2>err &&\n\n-- \n2.54.0.501.g0fb508de08\n\n"},{"id":"545131","messageId":"CAOLa=ZRFSuGrqFXhTuQ7Dk5GCQQGHom++78xwONoiNdt1h_gWQ@mail.gmail.com","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-2-e72720344a7c@gmail.com","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2026-06-10T11:47:17Z","receivedAt":"2026-06-10T11:47:18Z","isPatch":true,"body":"Tamir Duberstein writes:\n\n> git branch and git for-each-ref call repo_is_descendant_of() for\n> each candidate selected by --contains or --no-contains. Each call\n> starts a new graph walk, so refs with shared history repeatedly\n> traverse the same commits.\n>\n> ffc4b8012d (tag: speed up --contains calculation, 2011-06-11)\n> introduced a depth-first walk for git tag that caches positive and\n> negative answers across candidates. ee2bd06b0f (ref-filter: implement\n> '--contains' option, 2015-07-07) preserved both implementations when\n> ref-filter learned --contains.\n>\n> The memoized walk is not always faster. Without generation numbers,\n> a negative check can walk to the root even when the breadth-first\n> merge-base walk finds a nearby divergence. With generation numbers,\n> the depth-first walk can stop below the oldest target while still\n> reusing answers across candidates.\n>\n> Keep the existing memoized selection for git tag. Select it for other\n> ref-filter callers when generation numbers are enabled, and retain\n> the breadth-first walk otherwise.\n>\n> When generation numbers are unavailable, repo_is_descendant_of() can\n> return -1 if ancestry cannot be read. The ref-filter Boolean interface\n> treated that error as a match. Check it and exit instead. The memoized\n> path already dies on the same parse failure, so both selected paths now\n> fail rather than return a result.\n>\n> Add p1500 cases for up to 8,192 packed refs along one first-parent\n> history and for sibling refs near the tip with generation numbers\n> forced off.\n>\n> On a checkout with 62,174 remote-tracking refs and generation numbers\n> enabled, I ran:\n>\n> hyperfine --warmup 0 --runs 3 \\\n> --command-name parent \\\n> '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n> --command-name this-commit \\\n> '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n>\n> The results were:\n>\n> parent this commit\n> elapsed 104.365 s 467.7 ms\n> user 93.702 s 220.2 ms\n> system 0.723 s 182.7 ms\n>\n> The wall-time standard deviations were 11.356 seconds and 133.8\n> milliseconds, respectively. Separate runs without redirection produced\n> the same output with SHA-256\n> 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n>\n> Both revisions were built with the default -O2 flags using Apple\n> clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)\n> with a 16-core Apple M4 Max (12 performance and four efficiency\n> cores) and 128 GB RAM.\n>\n> Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n> Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\n> Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n> Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\n> Suggested-by: Jeff King \n> Signed-off-by: Tamir Duberstein \n> ---\n> commit-reach.c | 13 +++++++++--\n> commit-reach.h | 7 ++++++\n> t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n> t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n> 4 files changed, 88 insertions(+), 3 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 65b618959b..83a48004ef 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> int commit_contains(struct ref_filter *filter, struct commit *commit,\n> \t\t struct commit_list *list, struct contains_cache *cache)\n> {\n> -\tif (filter->with_commit_tag_algo)\n> +\tint result;\n> +\n> +\tif (!list)\n> +\t\treturn 1;\n> +\tif (filter->with_commit_tag_algo ||\n> +\t generation_numbers_enabled(the_repository))\n\nWhat's stopping us from dropping `filter->with_commit_tag_algo`\ncompletely and then doing?\n\n if (generation_numbers_enabled(the_repository))\n return contains_algo(commit, list, cache) == CONTAINS_YES;\n return repo_is_descendant_of(the_repository, commit, list);\n\n[snip]\n"},{"id":"545133","messageId":"CAJ-ks9ku=-675naKESOJJxOo0b5BmoH7=76aKZXXmUHM+=ZV0w@mail.gmail.com","threadId":"65776","inReplyTo":"CAOLa=ZRFSuGrqFXhTuQ7Dk5GCQQGHom++78xwONoiNdt1h_gWQ@mail.gmail.com","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-10T12:20:49Z","receivedAt":"2026-06-10T12:21:27Z","isPatch":true,"body":"On Wed, Jun 10, 2026 at 4:47 AM Karthik Nayak wrote:\n>\n> Tamir Duberstein writes:\n>\n> > git branch and git for-each-ref call repo_is_descendant_of() for\n> > each candidate selected by --contains or --no-contains. Each call\n> > starts a new graph walk, so refs with shared history repeatedly\n> > traverse the same commits.\n> >\n> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11)\n> > introduced a depth-first walk for git tag that caches positive and\n> > negative answers across candidates. ee2bd06b0f (ref-filter: implement\n> > '--contains' option, 2015-07-07) preserved both implementations when\n> > ref-filter learned --contains.\n> >\n> > The memoized walk is not always faster. Without generation numbers,\n> > a negative check can walk to the root even when the breadth-first\n> > merge-base walk finds a nearby divergence. With generation numbers,\n> > the depth-first walk can stop below the oldest target while still\n> > reusing answers across candidates.\n> >\n> > Keep the existing memoized selection for git tag. Select it for other\n> > ref-filter callers when generation numbers are enabled, and retain\n> > the breadth-first walk otherwise.\n> >\n> > When generation numbers are unavailable, repo_is_descendant_of() can\n> > return -1 if ancestry cannot be read. The ref-filter Boolean interface\n> > treated that error as a match. Check it and exit instead. The memoized\n> > path already dies on the same parse failure, so both selected paths now\n> > fail rather than return a result.\n> >\n> > Add p1500 cases for up to 8,192 packed refs along one first-parent\n> > history and for sibling refs near the tip with generation numbers\n> > forced off.\n> >\n> > On a checkout with 62,174 remote-tracking refs and generation numbers\n> > enabled, I ran:\n> >\n> > hyperfine --warmup 0 --runs 3 \\\n> > --command-name parent \\\n> > '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n> > --command-name this-commit \\\n> > '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n> >\n> > The results were:\n> >\n> > parent this commit\n> > elapsed 104.365 s 467.7 ms\n> > user 93.702 s 220.2 ms\n> > system 0.723 s 182.7 ms\n> >\n> > The wall-time standard deviations were 11.356 seconds and 133.8\n> > milliseconds, respectively. Separate runs without redirection produced\n> > the same output with SHA-256\n> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n> >\n> > Both revisions were built with the default -O2 flags using Apple\n> > clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)\n> > with a 16-core Apple M4 Max (12 performance and four efficiency\n> > cores) and 128 GB RAM.\n> >\n> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n> > Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\n> > Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n> > Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\n> > Suggested-by: Jeff King \n> > Signed-off-by: Tamir Duberstein \n> > ---\n> > commit-reach.c | 13 +++++++++--\n> > commit-reach.h | 7 ++++++\n> > t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n> > t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n> > 4 files changed, 88 insertions(+), 3 deletions(-)\n> >\n> > diff --git a/commit-reach.c b/commit-reach.c\n> > index 65b618959b..83a48004ef 100644\n> > --- a/commit-reach.c\n> > +++ b/commit-reach.c\n> > @@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> > int commit_contains(struct ref_filter *filter, struct commit *commit,\n> > struct commit_list *list, struct contains_cache *cache)\n> > {\n> > - if (filter->with_commit_tag_algo)\n> > + int result;\n> > +\n> > + if (!list)\n> > + return 1;\n> > + if (filter->with_commit_tag_algo ||\n> > + generation_numbers_enabled(the_repository))\n>\n> What's stopping us from dropping `filter->with_commit_tag_algo`\n> completely and then doing?\n>\n> if (generation_numbers_enabled(the_repository))\n> return contains_algo(commit, list, cache) == CONTAINS_YES;\n> return repo_is_descendant_of(the_repository, commit, list);\n\nJeff raised this distinction during the v1 review:\n\nhttps://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net/\n\n`with_commit_tag_algo` preserves the existing behavior of `git tag` when\ngeneration numbers are unavailable. `git tag --contains` has used the\nmemoized walk since ffc4b8012d (tag: speed up --contains calculation,\n2011-06-11). Dropping the flag would send it back through repeated\n`repo_is_descendant_of()` walks in repositories without usable generation\nnumbers.\n\nThe condition in v2 implements the rule discussed there: retain the\nexisting memoized path for `git tag`, and use it for other ref-filter\ncallers when generation numbers make the depth-first walk reliably\nadvantageous.\n\nThis is probably my fault for breaking the threading between this and\nv1. Sorry about that.\n"},{"id":"545248","messageId":"20260611072942.GG2191159@coredump.intra.peff.net","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-1-e72720344a7c@gmail.com","subject":"Re: [PATCH v2 1/2] commit-reach: handle cycles in contains walk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-06-11T07:29:42Z","receivedAt":"2026-06-11T07:29:43Z","isPatch":true,"body":"On Mon, Jun 08, 2026 at 07:36:34PM -0700, Tamir Duberstein wrote:\n\n> @@ -744,7 +745,7 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n> }\n> \n> static enum contains_result contains_tag_algo(struct commit *candidate,\n> -\t\t\t\t\t const struct commit_list *want,\n> +\t\t\t\t\t struct commit_list *want,\n> \t\t\t\t\t struct contains_cache *cache)\n\nOK, we must lose the const here because repo_is_descendant_of() does not\nhave it. We could add const to that function, though that cascades down\nto a few other helpers (see below). I'm not sure if that is making the\nworld a better place, or if it is just const pedantry.\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5df471a313..8cede01f01 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -563,7 +563,7 @@ int repo_get_merge_bases(struct repository *r,\n */\n int repo_is_descendant_of(struct repository *r,\n \t\t\t struct commit *commit,\n-\t\t\t struct commit_list *with_commit)\n+\t\t\t const struct commit_list *with_commit)\n {\n \tif (!with_commit)\n \t\treturn 1;\n@@ -955,11 +955,12 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \treturn result;\n }\n \n-int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n+int can_all_from_reach(const struct commit_list *from,\n+\t\t const struct commit_list *to,\n \t\t int cutoff_by_min_date)\n {\n \tstruct object_array from_objs = OBJECT_ARRAY_INIT;\n-\tstruct commit_list *from_iter = from, *to_iter = to;\n+\tconst struct commit_list *from_iter = from, *to_iter = to;\n \tint result;\n \ttimestamp_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;\n \ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..76e82f827e 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -37,7 +37,7 @@ int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result)\n \n int repo_is_descendant_of(struct repository *r,\n \t\t\t struct commit *commit,\n-\t\t\t struct commit_list *with_commit);\n+\t\t\t const struct commit_list *with_commit);\n int repo_in_merge_bases(struct repository *r,\n \t\t\tstruct commit *commit,\n \t\t\tstruct commit *reference);\n@@ -93,7 +93,8 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t unsigned int assign_flag,\n \t\t\t\t timestamp_t min_commit_date,\n \t\t\t\t timestamp_t min_generation);\n-int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n+int can_all_from_reach(const struct commit_list *from,\n+\t\t const struct commit_list *to,\n \t\t int commit_date_cutoff);\n \n \n> +cycle:\n> +\tfree(contains_stack.contains_stack);\n> +\tclear_contains_cache(cache);\n> +\tinit_contains_cache(cache);\n> +\n> +\tresult = repo_is_descendant_of(the_repository, candidate, want);\n> +\tif (result < 0)\n> +\t\texit(128);\n\nWe are feeding the whole initial \"want\" list, so we should get a correct\nanswer regardless of how far we got into the cycle, which would run into\nproblems (e.g., if the cycle existed only on some branch of the\nhistory). But going back to the initial list will always be correct.\nGood.\n\nTwo small points, though.\n\nOne, the call to init_contains_cache() is redundant here; the clear\nfunction is documented as making things ready for use (it's a little\nhard to grep for, due to macros, but the docs are in commit-slab.h).\nIt's probably not hurting anything.\n\nTwo, the call to exit(128) is unusual for our code base (I'd guess it\nwas cribbed off of the top-level exits in builtin/pull.c). We'd usually\ndie() instead. Even if repo_is_descendant_of() produced its own error\nmessage, it may be useful to mention that we were falling back to it due\nto a cycle.\n\nBut even better is if we can return the error up the stack. We do not\nreturn errors from contains_tag_algo() currently, but it has only one\ncaller. And that caller may also directly return the result of\nrepo_is_descendant_of(). So could we just pass that along?\n\nPerhaps not. Looking at the callers of commit_contains(), they treat the\nresult as a pure boolean. So probably calling die() is reasonable, and\nwe already do so via parse_commit_or_die() elsewhere in the algorithm.\nThat does leave a potential lurking bug for the non-tag-algo code path.\n\n> +\t*contains_cache_at(cache, candidate) =\n> +\t\tresult ? CONTAINS_YES : CONTAINS_NO;\n> +\treturn result ? CONTAINS_YES : CONTAINS_NO;\n\nSo we actually cache our discovered value. Cute, and it might save us\nfrom hitting the cycle again, though not always. E.g., two candidates A\nand B share a parent P, and the cycle starts at P but does not include A\nor B. We discover the cycle and cache the value for A, but discover it\nagain for B.\n\nWe do lose all of the existing non-cycle cached values when we call\nclear_contains_cache(). But we have to at least clear out all of the\nIN_PROGRESS commits. It is hard to care too much about optimizing the\noutcome for this case which we expect to happen approximately never.\nSo I think doing the simplest correct thing is OK.\n\n> +test_expect_success 'tag --contains handles cyclic replacement histories' '\n> +\tfirst=$(git rev-parse HEAD~2) &&\n> +\tsecond=$(git rev-parse HEAD~) &&\n> +\tthird=$(git rev-parse HEAD) &&\n> +\ttest_when_finished \"\n> +\t\tgit replace -d $first\n> +\t\tgit replace -d $third\n> +\t\tgit tag -d cycle-a cycle-b\n> +\t\" &&\n\nWe usually &&-chain the commands inside test_when_finished. If they\nfail, the test harness will note this and complain (if the test was not\notherwise failing). It's usually not a big deal either way, though\nsometimes it can catch silly mistakes (e.g., if you wrote $second\ninstead of $third and the \"replace -d\" is quietly doing nothing at all).\n\nI'm a little surprised that the chainlint checker doesn't catch this,\nbut I guess it doesn't know to recurse into the snippet handed to\ntest_when_finished. It probably is not really worth the trouble to teach\nit to do so.\n\nOtherwise the test looks good to me.\n\n-Peff\n"},{"id":"545250","messageId":"CAOLa=ZSezQOj56-TezVaAcisUyczxhJmu4VghyFBHcBB_mKJ2A@mail.gmail.com","threadId":"65776","inReplyTo":"CAJ-ks9ku=-675naKESOJJxOo0b5BmoH7=76aKZXXmUHM+=ZV0w@mail.gmail.com","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2026-06-11T08:16:52Z","receivedAt":"2026-06-11T08:16:53Z","isPatch":true,"body":"Tamir Duberstein writes:\n\n> On Wed, Jun 10, 2026 at 4:47 AM Karthik Nayak wrote:\n>>\n>> Tamir Duberstein writes:\n>>\n>> > git branch and git for-each-ref call repo_is_descendant_of() for\n>> > each candidate selected by --contains or --no-contains. Each call\n>> > starts a new graph walk, so refs with shared history repeatedly\n>> > traverse the same commits.\n>> >\n>> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11)\n>> > introduced a depth-first walk for git tag that caches positive and\n>> > negative answers across candidates. ee2bd06b0f (ref-filter: implement\n>> > '--contains' option, 2015-07-07) preserved both implementations when\n>> > ref-filter learned --contains.\n>> >\n>> > The memoized walk is not always faster. Without generation numbers,\n>> > a negative check can walk to the root even when the breadth-first\n>> > merge-base walk finds a nearby divergence. With generation numbers,\n>> > the depth-first walk can stop below the oldest target while still\n>> > reusing answers across candidates.\n>> >\n>> > Keep the existing memoized selection for git tag. Select it for other\n>> > ref-filter callers when generation numbers are enabled, and retain\n>> > the breadth-first walk otherwise.\n>> >\n>> > When generation numbers are unavailable, repo_is_descendant_of() can\n>> > return -1 if ancestry cannot be read. The ref-filter Boolean interface\n>> > treated that error as a match. Check it and exit instead. The memoized\n>> > path already dies on the same parse failure, so both selected paths now\n>> > fail rather than return a result.\n>> >\n>> > Add p1500 cases for up to 8,192 packed refs along one first-parent\n>> > history and for sibling refs near the tip with generation numbers\n>> > forced off.\n>> >\n>> > On a checkout with 62,174 remote-tracking refs and generation numbers\n>> > enabled, I ran:\n>> >\n>> > hyperfine --warmup 0 --runs 3 \\\n>> > --command-name parent \\\n>> > '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n>> > --command-name this-commit \\\n>> > '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n>> >\n>> > The results were:\n>> >\n>> > parent this commit\n>> > elapsed 104.365 s 467.7 ms\n>> > user 93.702 s 220.2 ms\n>> > system 0.723 s 182.7 ms\n>> >\n>> > The wall-time standard deviations were 11.356 seconds and 133.8\n>> > milliseconds, respectively. Separate runs without redirection produced\n>> > the same output with SHA-256\n>> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n>> >\n>> > Both revisions were built with the default -O2 flags using Apple\n>> > clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)\n>> > with a 16-core Apple M4 Max (12 performance and four efficiency\n>> > cores) and 128 GB RAM.\n>> >\n>> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n>> > Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\n>> > Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n>> > Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\n>> > Suggested-by: Jeff King \n>> > Signed-off-by: Tamir Duberstein \n>> > ---\n>> > commit-reach.c | 13 +++++++++--\n>> > commit-reach.h | 7 ++++++\n>> > t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n>> > t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n>> > 4 files changed, 88 insertions(+), 3 deletions(-)\n>> >\n>> > diff --git a/commit-reach.c b/commit-reach.c\n>> > index 65b618959b..83a48004ef 100644\n>> > --- a/commit-reach.c\n>> > +++ b/commit-reach.c\n>> > @@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n>> > int commit_contains(struct ref_filter *filter, struct commit *commit,\n>> > struct commit_list *list, struct contains_cache *cache)\n>> > {\n>> > - if (filter->with_commit_tag_algo)\n>> > + int result;\n>> > +\n>> > + if (!list)\n>> > + return 1;\n>> > + if (filter->with_commit_tag_algo ||\n>> > + generation_numbers_enabled(the_repository))\n>>\n>> What's stopping us from dropping `filter->with_commit_tag_algo`\n>> completely and then doing?\n>>\n>> if (generation_numbers_enabled(the_repository))\n>> return contains_algo(commit, list, cache) == CONTAINS_YES;\n>> return repo_is_descendant_of(the_repository, commit, list);\n>\n> Jeff raised this distinction during the v1 review:\n>\n> https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net/\n>\n> `with_commit_tag_algo` preserves the existing behavior of `git tag` when\n> generation numbers are unavailable. `git tag --contains` has used the\n> memoized walk since ffc4b8012d (tag: speed up --contains calculation,\n> 2011-06-11). Dropping the flag would send it back through repeated\n> `repo_is_descendant_of()` walks in repositories without usable generation\n> numbers.\n>\n\nI did read that, my question is on top of that. Do we also want to use\nthe non-memoized walk for 'git tag' when there are no generation numbers\navailable or does that not work? If not, we should mention that too in\nthe commit message.\n\n> The condition in v2 implements the rule discussed there: retain the\n> existing memoized path for `git tag`, and use it for other ref-filter\n> callers when generation numbers make the depth-first walk reliably\n> advantageous.\n>\n> This is probably my fault for breaking the threading between this and\n> v1. Sorry about that.\n"},{"id":"545251","messageId":"20260611082244.GH2191159@coredump.intra.peff.net","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-2-e72720344a7c@gmail.com","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-06-11T08:22:44Z","receivedAt":"2026-06-11T08:22:45Z","isPatch":true,"body":"On Mon, Jun 08, 2026 at 07:36:35PM -0700, Tamir Duberstein wrote:\n\n> The wall-time standard deviations were 11.356 seconds and 133.8\n> milliseconds, respectively. Separate runs without redirection produced\n> the same output with SHA-256\n> 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n\nHeh. Without the original repo, this sha256 hash is meaningless to us,\nisn't it? Ditto for the sha1 the earlier command.\n\n> int commit_contains(struct ref_filter *filter, struct commit *commit,\n> \t\t struct commit_list *list, struct contains_cache *cache)\n> {\n> -\tif (filter->with_commit_tag_algo)\n> +\tint result;\n> +\n> +\tif (!list)\n> +\t\treturn 1;\n> +\tif (filter->with_commit_tag_algo ||\n> +\t generation_numbers_enabled(the_repository))\n> \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> -\treturn repo_is_descendant_of(the_repository, commit, list);\n> +\n> +\tresult = repo_is_descendant_of(the_repository, commit, list);\n> +\tif (result < 0)\n> +\t\texit(128);\n> +\treturn result;\n\nThere's a little more going on here than I expected from the commit\nmessage. Is it important for us to short-circuit the empty list and just\nreturn 1? Or did the existing helper functions already handle that?\n\nLooking at contains_tag_algo(), I think it would actually return\nCONTAINS_NO here (though I didn't test it). So this is actually a change\nin behavior for \"git tag\" if that's correct. I doubt it is triggerable\nin practice, though, as we would simply never call commit_contains() in\nthe first place with an empty list. But if we are going to add in this\nlogic, I think it makes sense to do so as a separate commit (describing\nwhat it is doing and why it's not (yet) a triggerable bug).\n\nChecking the result of repo_is_descendant_of() makes sense, as discussed\nearlier. But probably that should come as its own patch, since it's an\nindependent bug-fix. I'm also tempted to say it should call die()\ninstead of a direct exit, though it does look like the error exit paths\nfrom repo_is_descendant_of() would all have produced their own messages.\n\n\nAnd one side note. While looking at the implementation of\nrepo_is_descendant_of(), I did notice something curious: it also\nswitches algorithms based on the presence of generation numbers! So it\nshould also be cutting off the traversal early when possible. But I\nguess its main problem is that we call it independently for each\ncandidate, so it may traverse the same (useful) stretch of history\nmultiple times.\n\nSo probably an alternative approach to this patch would be feeding all\nof the candidates at once, the way we do with reach_filter() via\nfilter_refs(). I'm not sure if we have the right functions available for\nthat (naively, --contains and --merged are inversions of each other, so\nswapping the arguments to tips_reachable_from_bases() might work, but I\ndidn't think very hard on it).\n\nI wonder if that might perform better or worse. I'm content to leave it\nfor another day, though, as switching to the memoizing depth-first algo\nhere is a pretty easy change.\n\n> -\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n> +\tgit rev-list --first-parent --max-count=8192 HEAD >contains-commits &&\n> +\ttest_file_not_empty contains-commits &&\n> +\tgit update-ref refs/contains-perf-base \"$(tail -n 1 contains-commits)\" &&\n> +\tawk \"{\n> +\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n> +\t}\" contains-commits |\n> +\t\tgit update-ref --stdin &&\n> +\tgit pack-refs --include \"refs/contains-perf/*\" &&\n\nMy head almost exploded reading the embedded quoting in that awk\ninvocation. But I can't think offhand of a better way to do it. You\ncan't use test_seq because it needs both the number and the original\nstring. You can do it with sed, but it probably ends up even more\nunreadable.\n\nBut OK, we are making a bunch of refs based on first-parent history.\n\n> +\ttree=$(git rev-parse HEAD^{tree}) &&\n> +\tbase=$(git rev-parse HEAD) &&\n> +\ttarget=$(echo target | git commit-tree \"$tree\" -p \"$base\") &&\n> +\tgit update-ref refs/contains-diverged/target \"$target\" &&\n> +\tfor i in $(test_seq 1 4)\n> +\tdo\n> +\t\tcommit=$(echo candidate-$i |\n> +\t\t\tgit commit-tree \"$tree\" -p \"$base\") &&\n> +\t\tgit update-ref refs/contains-diverged/candidate-$i \"$commit\" ||\n> +\t\treturn 1\n> +\tdone &&\n\nAnd then a few candidate refs that are not reachable from other refs, or\nfrom each other. OK.\n\nI think you could just write:\n\n git commit-tree HEAD^{tree} -p HEAD\n\ninstead of doing separate rev-parses, but it's probably not a big deal\neither way.\n\n> +test_expect_success 'verify contains results' '\n> +\tgit for-each-ref --contains=refs/contains-perf-base \\\n> +\t\trefs/contains-perf/ >actual &&\n> +\ttest_line_count = $(wc -l +\n> +\techo refs/contains-diverged/target >expect &&\n> +\tGIT_TEST_COMMIT_GRAPH=0 \\\n> +\t\tgit -c core.commitGraph=false for-each-ref \\\n> +\t\t\t--format=\"%(refname)\" \\\n> +\t\t\t--contains=refs/contains-diverged/target \\\n> +\t\t\trefs/contains-diverged/ >actual &&\n> +\ttest_cmp expect actual\n> +'\n\nThis is a funny test to have in the middle of a perf script (which\nhardly anybody ever runs). If we are concerned about the correctness,\nshould this be in a non-perf test script? Though I'd imagine something\nlike it is already covered there.\n\nThere's a lot of subtlety in what we're verifying, too. In the first\nhalf, we are checking that all of the commits in contains-perf contain\nthe base. And that base is the final element of the contains-commits\nlist. Which made me wonder what happens in a branch history, since that\nlist is linearized. But because we used --first-parent to generate it,\nit _is_ linear, and the results work out. So OK, I don't think it's\nwrong, but I am struggling to understand the meaning of the test.\n\nThe second half is just checking that...the other refs which are not\ncontained in \"target\" are not mentioned? OK, but why do it only with\ncommit graphs off. Why not both off and on? Again, I'm not sure I\nunderstand what we're trying to focus on here.\n\n> +test_perf 'contains: git for-each-ref --contains' '\n> +\tgit for-each-ref --contains=refs/contains-perf-base \\\n> +\t\trefs/contains-perf/ >/dev/null\n> +'\n\nYay, actual perf tests. Here we have a ton of matches, and they all walk\nover the same chunk of history. Should get much faster, though it's\nmostly a synthetic test.\n\nFor --merged, we already have separate tests with each of for-each-ref,\nbranch, and tag. Should we have the same here for --contains? And should\nwe be using the input repo data, rather than our synthetic test? It is\nnice to show off the performance with the synthetic test, but ultimately\nthe point of the perf suite is feeding it real workloads and looking for\nregressions.\n\n> +test_perf 'contains without generations: divergent refs' '\n> +\tGIT_TEST_COMMIT_GRAPH=0 \\\n> +\t\tgit -c core.commitGraph=false for-each-ref \\\n> +\t\t\t--contains=refs/contains-diverged/target \\\n> +\t\t\trefs/contains-diverged/ >/dev/null\n> +'\n\nOK, and this one should find that most of them are not contained, but\nthe depth-first algorithm could walk all the way down to the roots. But\nwe don't run it at all, since we disable commit graphs!\n\nSo what are we trying to measure here? If it left commit graphs enabled,\nI think we could demonstrate that using the depth-first algorithm with\ngeneration numbers does not make anything _worse_. I.e., that\nfor-each-ref and branch did not regress from the change.\n\n> +test_expect_success 'missing ancestors are reported by contains filters' '\n> +\ttest_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n> +\t{\n> +\t\techo \"tree $(git rev-parse HEAD^{tree})\" &&\n> +\t\techo \"parent $MISSING\" &&\n> +\t\tgit cat-file commit HEAD |\n> +\t\t\tsed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n> +\t\techo &&\n> +\t\techo \"missing parent\"\n> +\t} >commit &&\n> +\tbroken=$(git hash-object -t commit -w commit) &&\n> +\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n> +\tfor option in --contains --no-contains\n> +\tdo\n> +\t\ttest_must_fail git for-each-ref \"$option=HEAD\" \\\n> +\t\t\trefs/heads/missing-parent >out 2>err &&\n> +\t\ttest_must_be_empty out &&\n> +\t\ttest_grep \"parse commit $MISSING\" err ||\n> +\t\treturn 1\n> +\tdone\n> +'\n\nThis is a great thing to test, but probably should be pulled out into\na separate patch along with the fix to check the return code.\n\nThe commit construction looks OK, and is nicer than corrupting the\nrepository by deleting a real object. Given that we are pulling the\nidents from an existing commit, it might be simpler to just use the\nwhole commit as a template, like:\n\n git cat-file commit HEAD |\n sed \"s/^parent /parent $MISSING/\"\n\nbut it may be a matter of taste.\n\n-Peff\n"},{"id":"545312","messageId":"CAJ-ks9mYkiUo0_=JJGJtRnFBb4u8v_d2-mytydbJOeuoKbfOiA@mail.gmail.com","threadId":"65776","inReplyTo":"CAOLa=ZSezQOj56-TezVaAcisUyczxhJmu4VghyFBHcBB_mKJ2A@mail.gmail.com","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-11T20:10:30Z","receivedAt":"2026-06-11T20:11:10Z","isPatch":true,"body":"On Thu, Jun 11, 2026 at 1:16 AM Karthik Nayak wrote:\n>\n> Tamir Duberstein writes:\n>\n> > On Wed, Jun 10, 2026 at 4:47 AM Karthik Nayak wrote:\n> >>\n> >> Tamir Duberstein writes:\n> >>\n> >> > git branch and git for-each-ref call repo_is_descendant_of() for\n> >> > each candidate selected by --contains or --no-contains. Each call\n> >> > starts a new graph walk, so refs with shared history repeatedly\n> >> > traverse the same commits.\n> >> >\n> >> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11)\n> >> > introduced a depth-first walk for git tag that caches positive and\n> >> > negative answers across candidates. ee2bd06b0f (ref-filter: implement\n> >> > '--contains' option, 2015-07-07) preserved both implementations when\n> >> > ref-filter learned --contains.\n> >> >\n> >> > The memoized walk is not always faster. Without generation numbers,\n> >> > a negative check can walk to the root even when the breadth-first\n> >> > merge-base walk finds a nearby divergence. With generation numbers,\n> >> > the depth-first walk can stop below the oldest target while still\n> >> > reusing answers across candidates.\n> >> >\n> >> > Keep the existing memoized selection for git tag. Select it for other\n> >> > ref-filter callers when generation numbers are enabled, and retain\n> >> > the breadth-first walk otherwise.\n> >> >\n> >> > When generation numbers are unavailable, repo_is_descendant_of() can\n> >> > return -1 if ancestry cannot be read. The ref-filter Boolean interface\n> >> > treated that error as a match. Check it and exit instead. The memoized\n> >> > path already dies on the same parse failure, so both selected paths now\n> >> > fail rather than return a result.\n> >> >\n> >> > Add p1500 cases for up to 8,192 packed refs along one first-parent\n> >> > history and for sibling refs near the tip with generation numbers\n> >> > forced off.\n> >> >\n> >> > On a checkout with 62,174 remote-tracking refs and generation numbers\n> >> > enabled, I ran:\n> >> >\n> >> > hyperfine --warmup 0 --runs 3 \\\n> >> > --command-name parent \\\n> >> > '\"$parent\" branch -r --contains c78ae85f3ce7e >/dev/null' \\\n> >> > --command-name this-commit \\\n> >> > '\"$this\" branch -r --contains c78ae85f3ce7e >/dev/null'\n> >> >\n> >> > The results were:\n> >> >\n> >> > parent this commit\n> >> > elapsed 104.365 s 467.7 ms\n> >> > user 93.702 s 220.2 ms\n> >> > system 0.723 s 182.7 ms\n> >> >\n> >> > The wall-time standard deviations were 11.356 seconds and 133.8\n> >> > milliseconds, respectively. Separate runs without redirection produced\n> >> > the same output with SHA-256\n> >> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n> >> >\n> >> > Both revisions were built with the default -O2 flags using Apple\n> >> > clang 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6)\n> >> > with a 16-core Apple M4 Max (12 performance and four efficiency\n> >> > cores) and 128 GB RAM.\n> >> >\n> >> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\n> >> > Link: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\n> >> > Link: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\n> >> > Link: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\n> >> > Suggested-by: Jeff King \n> >> > Signed-off-by: Tamir Duberstein \n> >> > ---\n> >> > commit-reach.c | 13 +++++++++--\n> >> > commit-reach.h | 7 ++++++\n> >> > t/perf/p1500-graph-walks.sh | 49 +++++++++++++++++++++++++++++++++++++++++-\n> >> > t/t6301-for-each-ref-errors.sh | 22 +++++++++++++++++++\n> >> > 4 files changed, 88 insertions(+), 3 deletions(-)\n> >> >\n> >> > diff --git a/commit-reach.c b/commit-reach.c\n> >> > index 65b618959b..83a48004ef 100644\n> >> > --- a/commit-reach.c\n> >> > +++ b/commit-reach.c\n> >> > @@ -821,9 +821,18 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> >> > int commit_contains(struct ref_filter *filter, struct commit *commit,\n> >> > struct commit_list *list, struct contains_cache *cache)\n> >> > {\n> >> > - if (filter->with_commit_tag_algo)\n> >> > + int result;\n> >> > +\n> >> > + if (!list)\n> >> > + return 1;\n> >> > + if (filter->with_commit_tag_algo ||\n> >> > + generation_numbers_enabled(the_repository))\n> >>\n> >> What's stopping us from dropping `filter->with_commit_tag_algo`\n> >> completely and then doing?\n> >>\n> >> if (generation_numbers_enabled(the_repository))\n> >> return contains_algo(commit, list, cache) == CONTAINS_YES;\n> >> return repo_is_descendant_of(the_repository, commit, list);\n> >\n> > Jeff raised this distinction during the v1 review:\n> >\n> > https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net/\n> >\n> > `with_commit_tag_algo` preserves the existing behavior of `git tag` when\n> > generation numbers are unavailable. `git tag --contains` has used the\n> > memoized walk since ffc4b8012d (tag: speed up --contains calculation,\n> > 2011-06-11). Dropping the flag would send it back through repeated\n> > `repo_is_descendant_of()` walks in repositories without usable generation\n> > numbers.\n> >\n>\n> I did read that, my question is on top of that. Do we also want to use\n> the non-memoized walk for 'git tag' when there are no generation numbers\n> available or does that not work? If not, we should mention that too in\n> the commit message.\n\nWe should keep the memoized walk for git tag. In git.git, with commit\ngraphs disabled, hyperfine measured:\n\n git -c core.commitGraph=false tag --contains HEAD~200\n git -c core.commitGraph=false for-each-ref \\\n --contains HEAD~200 refs/tags/\n\nat 478.9 ms and 4.861 s, respectively. The second command takes the\nnon-memoized path, so memoization is about 10 times faster for this\nworkload. I added the rationale to the commit message in v3.\n"},{"id":"545320","messageId":"CAJ-ks9=E-0W2igNWFRqXVA0XCkjfqWPHbQeXRDL07QZN7m0juw@mail.gmail.com","threadId":"65776","inReplyTo":"20260611072942.GG2191159@coredump.intra.peff.net","subject":"Re: [PATCH v2 1/2] commit-reach: handle cycles in contains walk","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T02:40:18Z","receivedAt":"2026-06-12T02:40:57Z","isPatch":true,"body":"On Thu, Jun 11, 2026 at 12:29 AM Jeff King wrote:\n>\n> On Mon, Jun 08, 2026 at 07:36:34PM -0700, Tamir Duberstein wrote:\n>\n> > @@ -744,7 +745,7 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n> > }\n> >\n> > static enum contains_result contains_tag_algo(struct commit *candidate,\n> > - const struct commit_list *want,\n> > + struct commit_list *want,\n> > struct contains_cache *cache)\n>\n> OK, we must lose the const here because repo_is_descendant_of() does not\n> have it. We could add const to that function, though that cascades down\n> to a few other helpers (see below). I'm not sure if that is making the\n> world a better place, or if it is just const pedantry.\n\nI left the signature change local rather than propagating const\nthrough the other reachability helpers.\n\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 5df471a313..8cede01f01 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -563,7 +563,7 @@ int repo_get_merge_bases(struct repository *r,\n> */\n> int repo_is_descendant_of(struct repository *r,\n> struct commit *commit,\n> - struct commit_list *with_commit)\n> + const struct commit_list *with_commit)\n> {\n> if (!with_commit)\n> return 1;\n> @@ -955,11 +955,12 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> return result;\n> }\n>\n> -int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> +int can_all_from_reach(const struct commit_list *from,\n> + const struct commit_list *to,\n> int cutoff_by_min_date)\n> {\n> struct object_array from_objs = OBJECT_ARRAY_INIT;\n> - struct commit_list *from_iter = from, *to_iter = to;\n> + const struct commit_list *from_iter = from, *to_iter = to;\n> int result;\n> timestamp_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;\n> timestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n> diff --git a/commit-reach.h b/commit-reach.h\n> index 3f3a563d8a..76e82f827e 100644\n> --- a/commit-reach.h\n> +++ b/commit-reach.h\n> @@ -37,7 +37,7 @@ int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result)\n>\n> int repo_is_descendant_of(struct repository *r,\n> struct commit *commit,\n> - struct commit_list *with_commit);\n> + const struct commit_list *with_commit);\n> int repo_in_merge_bases(struct repository *r,\n> struct commit *commit,\n> struct commit *reference);\n> @@ -93,7 +93,8 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> unsigned int assign_flag,\n> timestamp_t min_commit_date,\n> timestamp_t min_generation);\n> -int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> +int can_all_from_reach(const struct commit_list *from,\n> + const struct commit_list *to,\n> int commit_date_cutoff);\n>\n>\n> > +cycle:\n> > + free(contains_stack.contains_stack);\n> > + clear_contains_cache(cache);\n> > + init_contains_cache(cache);\n> > +\n> > + result = repo_is_descendant_of(the_repository, candidate, want);\n> > + if (result < 0)\n> > + exit(128);\n>\n> We are feeding the whole initial \"want\" list, so we should get a correct\n> answer regardless of how far we got into the cycle, which would run into\n> problems (e.g., if the cycle existed only on some branch of the\n> history). But going back to the initial list will always be correct.\n> Good.\n>\n> Two small points, though.\n>\n> One, the call to init_contains_cache() is redundant here; the clear\n> function is documented as making things ready for use (it's a little\n> hard to grep for, due to macros, but the docs are in commit-slab.h).\n> It's probably not hurting anything.\n>\n> Two, the call to exit(128) is unusual for our code base (I'd guess it\n> was cribbed off of the top-level exits in builtin/pull.c). We'd usually\n> die() instead. Even if repo_is_descendant_of() produced its own error\n> message, it may be useful to mention that we were falling back to it due\n> to a cycle.\n\nI removed the redundant initialization and replaced exit(128) with\ndie(), adding context that the failure occurred after detecting a\ncycle.\n\n>\n> But even better is if we can return the error up the stack. We do not\n> return errors from contains_tag_algo() currently, but it has only one\n> caller. And that caller may also directly return the result of\n> repo_is_descendant_of(). So could we just pass that along?\n>\n> Perhaps not. Looking at the callers of commit_contains(), they treat the\n> result as a pure boolean. So probably calling die() is reasonable, and\n> we already do so via parse_commit_or_die() elsewhere in the algorithm.\n> That does leave a potential lurking bug for the non-tag-algo code path.\n\nI traced the callers. Returning an error from commit_contains() would\nonly move the fatal check into apply_ref_filter(): its NULL return\nalready means “filtered out”, filter_and_format_refs() returns void, and\nthe branch caller ignores filter_refs()'s return value. Propagating the\nerror to the command would require changing that whole chain, and none\nof the commands can recover from an unreadable commit.\n\nThe series therefore makes both cases fail explicitly. Patch 1 calls\ndie() if the cycle fallback cannot read the ancestry. Patch 3 calls\ndie() when the ordinary non-memoized walk returns -1.\n\n>\n> > + *contains_cache_at(cache, candidate) =\n> > + result ? CONTAINS_YES : CONTAINS_NO;\n> > + return result ? CONTAINS_YES : CONTAINS_NO;\n>\n> So we actually cache our discovered value. Cute, and it might save us\n> from hitting the cycle again, though not always. E.g., two candidates A\n> and B share a parent P, and the cycle starts at P but does not include A\n> or B. We discover the cycle and cache the value for A, but discover it\n> again for B.\n>\n> We do lose all of the existing non-cycle cached values when we call\n> clear_contains_cache(). But we have to at least clear out all of the\n> IN_PROGRESS commits. It is hard to care too much about optimizing the\n> outcome for this case which we expect to happen approximately never.\n> So I think doing the simplest correct thing is OK.\n>\n> > +test_expect_success 'tag --contains handles cyclic replacement histories' '\n> > + first=$(git rev-parse HEAD~2) &&\n> > + second=$(git rev-parse HEAD~) &&\n> > + third=$(git rev-parse HEAD) &&\n> > + test_when_finished \"\n> > + git replace -d $first\n> > + git replace -d $third\n> > + git tag -d cycle-a cycle-b\n> > + \" &&\n>\n> We usually &&-chain the commands inside test_when_finished. If they\n> fail, the test harness will note this and complain (if the test was not\n> otherwise failing). It's usually not a big deal either way, though\n> sometimes it can catch silly mistakes (e.g., if you wrote $second\n> instead of $third and the \"replace -d\" is quietly doing nothing at all).\n\nFixed in v3.\n\n\n\n\n>\n> I'm a little surprised that the chainlint checker doesn't catch this,\n> but I guess it doesn't know to recurse into the snippet handed to\n> test_when_finished. It probably is not really worth the trouble to teach\n> it to do so.\n>\n> Otherwise the test looks good to me.\n>\n> -Peff\n"},{"id":"545321","messageId":"CAJ-ks9=hiEaHyXP-sxYyeLc0Ky5Tw7dfOWiFAqb+A2274ECyZA@mail.gmail.com","threadId":"65776","inReplyTo":"20260611082244.GH2191159@coredump.intra.peff.net","subject":"Re: [PATCH v2 2/2] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T02:40:23Z","receivedAt":"2026-06-12T02:41:01Z","isPatch":true,"body":"On Thu, Jun 11, 2026 at 1:22 AM Jeff King wrote:\n>\n> On Mon, Jun 08, 2026 at 07:36:35PM -0700, Tamir Duberstein wrote:\n>\n> > The wall-time standard deviations were 11.356 seconds and 133.8\n> > milliseconds, respectively. Separate runs without redirection produced\n> > the same output with SHA-256\n> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.\n>\n> Heh. Without the original repo, this sha256 hash is meaningless to us,\n> isn't it? Ditto for the sha1 the earlier command.\n\nYeah, AI slop. Removed.\n\n>\n> > int commit_contains(struct ref_filter *filter, struct commit *commit,\n> > struct commit_list *list, struct contains_cache *cache)\n> > {\n> > - if (filter->with_commit_tag_algo)\n> > + int result;\n> > +\n> > + if (!list)\n> > + return 1;\n> > + if (filter->with_commit_tag_algo ||\n> > + generation_numbers_enabled(the_repository))\n> > return contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> > - return repo_is_descendant_of(the_repository, commit, list);\n> > +\n> > + result = repo_is_descendant_of(the_repository, commit, list);\n> > + if (result < 0)\n> > + exit(128);\n> > + return result;\n>\n> There's a little more going on here than I expected from the commit\n> message. Is it important for us to short-circuit the empty list and just\n> return 1? Or did the existing helper functions already handle that?\n>\n> Looking at contains_tag_algo(), I think it would actually return\n> CONTAINS_NO here (though I didn't test it). So this is actually a change\n> in behavior for \"git tag\" if that's correct. I doubt it is triggerable\n> in practice, though, as we would simply never call commit_contains() in\n> the first place with an empty list. But if we are going to add in this\n> logic, I think it makes sense to do so as a separate commit (describing\n> what it is doing and why it's not (yet) a triggerable bug).\n>\n> Checking the result of repo_is_descendant_of() makes sense, as discussed\n> earlier. But probably that should come as its own patch, since it's an\n> independent bug-fix. I'm also tempted to say it should call die()\n> instead of a direct exit, though it does look like the error exit paths\n> from repo_is_descendant_of() would all have produced their own messages.\n\nI dropped the empty-list change. The error check is now a separate\npatch and uses die().\n\n>\n>\n> And one side note. While looking at the implementation of\n> repo_is_descendant_of(), I did notice something curious: it also\n> switches algorithms based on the presence of generation numbers! So it\n> should also be cutting off the traversal early when possible. But I\n> guess its main problem is that we call it independently for each\n> candidate, so it may traverse the same (useful) stretch of history\n> multiple times.\n>\n> So probably an alternative approach to this patch would be feeding all\n> of the candidates at once, the way we do with reach_filter() via\n> filter_refs(). I'm not sure if we have the right functions available for\n> that (naively, --contains and --merged are inversions of each other, so\n> swapping the arguments to tips_reachable_from_bases() might work, but I\n> didn't think very hard on it).\n\nI tried the suggested argument swap, but tips_reachable_from_bases()\nonly reports whether a tip is reachable from any base. It cannot report\nwhich candidate refs contain a target, which is what --contains needs.\nI did not find an existing batched reachability helper that returns\nthose per-candidate answers.\n\n>\n> I wonder if that might perform better or worse. I'm content to leave it\n> for another day, though, as switching to the memoizing depth-first algo\n> here is a pretty easy change.\n>\n> > - commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n> > + git rev-list --first-parent --max-count=8192 HEAD >contains-commits &&\n> > + test_file_not_empty contains-commits &&\n> > + git update-ref refs/contains-perf-base \"$(tail -n 1 contains-commits)\" &&\n> > + awk \"{\n> > + printf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n> > + }\" contains-commits |\n> > + git update-ref --stdin &&\n> > + git pack-refs --include \"refs/contains-perf/*\" &&\n>\n> My head almost exploded reading the embedded quoting in that awk\n> invocation. But I can't think offhand of a better way to do it. You\n> can't use test_seq because it needs both the number and the original\n> string. You can do it with sed, but it probably ends up even more\n> unreadable.\n>\n> But OK, we are making a bunch of refs based on first-parent history.\n>\n> > + tree=$(git rev-parse HEAD^{tree}) &&\n> > + base=$(git rev-parse HEAD) &&\n> > + target=$(echo target | git commit-tree \"$tree\" -p \"$base\") &&\n> > + git update-ref refs/contains-diverged/target \"$target\" &&\n> > + for i in $(test_seq 1 4)\n> > + do\n> > + commit=$(echo candidate-$i |\n> > + git commit-tree \"$tree\" -p \"$base\") &&\n> > + git update-ref refs/contains-diverged/candidate-$i \"$commit\" ||\n> > + return 1\n> > + done &&\n>\n> And then a few candidate refs that are not reachable from other refs, or\n> from each other. OK.\n>\n> I think you could just write:\n>\n> git commit-tree HEAD^{tree} -p HEAD\n>\n> instead of doing separate rev-parses, but it's probably not a big deal\n> either way.\n>\n> > +test_expect_success 'verify contains results' '\n> > + git for-each-ref --contains=refs/contains-perf-base \\\n> > + refs/contains-perf/ >actual &&\n> > + test_line_count = $(wc -l > +\n> > + echo refs/contains-diverged/target >expect &&\n> > + GIT_TEST_COMMIT_GRAPH=0 \\\n> > + git -c core.commitGraph=false for-each-ref \\\n> > + --format=\"%(refname)\" \\\n> > + --contains=refs/contains-diverged/target \\\n> > + refs/contains-diverged/ >actual &&\n> > + test_cmp expect actual\n> > +'\n>\n> This is a funny test to have in the middle of a perf script (which\n> hardly anybody ever runs). If we are concerned about the correctness,\n> should this be in a non-perf test script? Though I'd imagine something\n> like it is already covered there.\n\nI deleted that block rather than moving it. It only rechecked ordinary\n--contains semantics already covered by t3201, t6302, and t7004; with\nGIT_TEST_COMMIT_GRAPH=1, those tests exercise the newly selected\nmemoized path for branch and for-each-ref.\n\nThe series adds functional tests for the behavior that is actually new:\nt7004 covers cyclic replacement histories, and t6301 covers unreadable\nancestry. The p1500 additions now measure performance only.\n\n>\n> There's a lot of subtlety in what we're verifying, too. In the first\n> half, we are checking that all of the commits in contains-perf contain\n> the base. And that base is the final element of the contains-commits\n> list. Which made me wonder what happens in a branch history, since that\n> list is linearized. But because we used --first-parent to generate it,\n> it _is_ linear, and the results work out. So OK, I don't think it's\n> wrong, but I am struggling to understand the meaning of the test.\n>\n> The second half is just checking that...the other refs which are not\n> contained in \"target\" are not mentioned? OK, but why do it only with\n> commit graphs off. Why not both off and on? Again, I'm not sure I\n> understand what we're trying to focus on here.\n>\n> > +test_perf 'contains: git for-each-ref --contains' '\n> > + git for-each-ref --contains=refs/contains-perf-base \\\n> > + refs/contains-perf/ >/dev/null\n> > +'\n>\n> Yay, actual perf tests. Here we have a ton of matches, and they all walk\n> over the same chunk of history. Should get much faster, though it's\n> mostly a synthetic test.\n>\n> For --merged, we already have separate tests with each of for-each-ref,\n> branch, and tag. Should we have the same here for --contains? And should\n> we be using the input repo data, rather than our synthetic test? It is\n> nice to show off the performance with the synthetic test, but ultimately\n> the point of the perf suite is feeding it real workloads and looking for\n> regressions.\n\nI added p1500 cases for all three frontends using refs from the input\nrepository, while retaining the synthetic shared-history case.\n\n>\n> > +test_perf 'contains without generations: divergent refs' '\n> > + GIT_TEST_COMMIT_GRAPH=0 \\\n> > + git -c core.commitGraph=false for-each-ref \\\n> > + --contains=refs/contains-diverged/target \\\n> > + refs/contains-diverged/ >/dev/null\n> > +'\n>\n> OK, and this one should find that most of them are not contained, but\n> the depth-first algorithm could walk all the way down to the roots. But\n> we don't run it at all, since we disable commit graphs!\n>\n> So what are we trying to measure here? If it left commit graphs enabled,\n> I think we could demonstrate that using the depth-first algorithm with\n> generation numbers does not make anything _worse_. I.e., that\n> for-each-ref and branch did not regress from the change.\n\nThe divergent-ref test did not exercise the changed path, so I removed\nit.\n\n>\n> > +test_expect_success 'missing ancestors are reported by contains filters' '\n> > + test_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n> > + {\n> > + echo \"tree $(git rev-parse HEAD^{tree})\" &&\n> > + echo \"parent $MISSING\" &&\n> > + git cat-file commit HEAD |\n> > + sed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n> > + echo &&\n> > + echo \"missing parent\"\n> > + } >commit &&\n> > + broken=$(git hash-object -t commit -w commit) &&\n> > + git update-ref refs/heads/missing-parent \"$broken\" &&\n> > + for option in --contains --no-contains\n> > + do\n> > + test_must_fail git for-each-ref \"$option=HEAD\" \\\n> > + refs/heads/missing-parent >out 2>err &&\n> > + test_must_be_empty out &&\n> > + test_grep \"parse commit $MISSING\" err ||\n> > + return 1\n> > + done\n> > +'\n>\n> This is a great thing to test, but probably should be pulled out into\n> a separate patch along with the fix to check the return code.\n\nDone in v3.\n\n\n\n\n>\n> The commit construction looks OK, and is nicer than corrupting the\n> repository by deleting a real object. Given that we are pulling the\n> idents from an existing commit, it might be simpler to just use the\n> whole commit as a template, like:\n>\n> git cat-file commit HEAD |\n> sed \"s/^parent /parent $MISSING/\"\n>\n> but it may be a matter of taste.\n>\n> -Peff\n"},{"id":"545322","messageId":"20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com","threadId":"65776","inReplyTo":"20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com","subject":"[PATCH v3 0/3] Reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T03:00:12Z","receivedAt":"2026-06-12T03:00:22Z","isPatch":true,"body":"git tag uses a memoized traversal for --contains, while git branch\nand git for-each-ref repeat a reachability walk for each ref. Reuse\nthe memoized traversal when generation numbers can bound the walk.\n\nThe first patch makes the memoized traversal handle replacement\ncycles. The last makes the non-memoized path report reachability\nerrors.\n\nSigned-off-by: Tamir Duberstein \n\n---\nChanges in v3:\n- Split missing-ancestor error handling into its own patch.\n- Use die() for reachability errors, remove redundant cache setup, and\n chain cycle-test cleanup.\n- Drop the unrelated empty-target-list behavior change.\n- Explain why git tag retains memoization without generation numbers.\n- Add p1500 coverage for all three frontends and a shared-history\n case.\n- Remove correctness checks from p1500 and drop output hashes.\n- Link to v2: https://patch.msgid.link/20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com\n\nChanges in v2:\n- Split cycle handling into a preparatory patch.\n- Exercise cycle handling through the existing git tag path.\n- Move perf result verification out of setup.\n- Link to v1: https://patch.msgid.link/20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com\n\n---\nTamir Duberstein (3):\n commit-reach: handle cycles in contains walk\n ref-filter: memoize --contains with generations\n commit-reach: die on contains walk errors\n\n commit-reach.c | 40 ++++++++++++++++++++++++++++++++++------\n commit-reach.h | 3 ++-\n t/perf/p1500-graph-walks.sh | 28 +++++++++++++++++++++++++++-\n t/t6301-for-each-ref-errors.sh | 22 ++++++++++++++++++++++\n t/t7004-tag.sh | 21 +++++++++++++++++++++\n 5 files changed, 106 insertions(+), 8 deletions(-)\n---\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nchange-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n\nBest regards,\n-- \nTamir Duberstein \n\n"},{"id":"545323","messageId":"20260611-ref-filter-memoized-contains-v3-1-b26af3dba285@gmail.com","threadId":"65776","inReplyTo":"20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com","subject":"[PATCH v3 1/3] commit-reach: handle cycles in contains walk","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T03:00:13Z","receivedAt":"2026-06-12T03:00:25Z","isPatch":true,"body":"The memoized contains traversal used by git tag assumes that commit\nancestry is acyclic. Replacement refs can violate that assumption,\ncausing it to keep pushing an already active commit until memory is\nexhausted.\n\nMark commits while they are active. If the traversal encounters an\nactive commit, discard the cache and retry the candidate with the\ncycle-safe reachability walk. Cache the candidate's result so a later\nwalk that reaches it can reuse the answer. Die if the fallback cannot\nread ancestry.\n\nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 29 +++++++++++++++++++++++++----\n commit-reach.h | 3 ++-\n t/t7004-tag.sh | 21 +++++++++++++++++++++\n 3 files changed, 48 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..1d34d66fe8 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -708,7 +708,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \n /*\n * Test whether the candidate is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n+ * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n+ * inconclusive.\n */\n static enum contains_result contains_test(struct commit *candidate,\n \t\t\t\t\t const struct commit_list *want,\n@@ -744,7 +745,7 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta\n }\n \n static enum contains_result contains_tag_algo(struct commit *candidate,\n-\t\t\t\t\t const struct commit_list *want,\n+\t\t\t\t\t struct commit_list *want,\n \t\t\t\t\t struct contains_cache *cache)\n {\n \tstruct contains_stack contains_stack = { 0, 0, NULL };\n@@ -765,6 +766,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tif (result != CONTAINS_UNKNOWN)\n \t\treturn result;\n \n+\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n \tpush_to_contains_stack(candidate, &contains_stack);\n \twhile (contains_stack.nr) {\n \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n@@ -776,8 +778,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\t\tcontains_stack.nr--;\n \t\t}\n \t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful yes/no.\n+\t\t * A parent may have just been popped and marked, or may still\n+\t\t * be active when replacement refs create a cycle.\n \t\t */\n \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n \t\tcase CONTAINS_YES:\n@@ -787,13 +789,32 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\tcase CONTAINS_NO:\n \t\t\tentry->parents = parents->next;\n \t\t\tbreak;\n+\t\tcase CONTAINS_IN_PROGRESS:\n+\t\t\t/*\n+\t\t\t * Partial negative answers are not safe across a cycle.\n+\t\t\t * Discard them and use the cycle-safe reachability walk.\n+\t\t\t */\n+\t\t\tgoto cycle;\n \t\tcase CONTAINS_UNKNOWN:\n+\t\t\t*contains_cache_at(cache, parents->item) =\n+\t\t\t\tCONTAINS_IN_PROGRESS;\n \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n \t\t\tbreak;\n \t\t}\n \t}\n \tfree(contains_stack.contains_stack);\n \treturn contains_test(candidate, want, cache, cutoff);\n+\n+cycle:\n+\tfree(contains_stack.contains_stack);\n+\tclear_contains_cache(cache);\n+\n+\tresult = repo_is_descendant_of(the_repository, candidate, want);\n+\tif (result < 0)\n+\t\tdie(_(\"failed to check reachability after detecting a cycle\"));\n+\t*contains_cache_at(cache, candidate) =\n+\t\tresult ? CONTAINS_YES : CONTAINS_NO;\n+\treturn result ? CONTAINS_YES : CONTAINS_NO;\n }\n \n int commit_contains(struct ref_filter *filter, struct commit *commit,\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..f908d305b1 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -73,7 +73,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n enum contains_result {\n \tCONTAINS_UNKNOWN = 0,\n \tCONTAINS_NO,\n-\tCONTAINS_YES\n+\tCONTAINS_YES,\n+\tCONTAINS_IN_PROGRESS\n };\n \n define_commit_slab(contains_cache, enum contains_result);\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex d918005dd9..4044bab006 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1611,6 +1611,27 @@ test_expect_success 'checking that first commit is in all tags (hash)' '\n \ttest_cmp expected actual\n '\n \n+test_expect_success 'tag --contains handles cyclic replacement histories' '\n+\tfirst=$(git rev-parse HEAD~2) &&\n+\tsecond=$(git rev-parse HEAD~) &&\n+\tthird=$(git rev-parse HEAD) &&\n+\ttest_when_finished \"\n+\t\tgit replace -d $first &&\n+\t\tgit replace -d $third &&\n+\t\tgit tag -d cycle-a cycle-b\n+\t\" &&\n+\tgit tag cycle-a \"$first\" &&\n+\tgit tag cycle-b \"$third\" &&\n+\tgit replace --graft \"$first\" \"$third\" \"$second\" &&\n+\tgit replace --graft \"$third\" \"$first\" &&\n+\tcat >expected <<-\\EOF &&\n+\tcycle-a\n+\tcycle-b\n+\tEOF\n+\tgit tag --contains=\"$second\" --list \"cycle-*\" >actual &&\n+\ttest_cmp expected actual\n+'\n+\n # other ways of specifying the commit\n test_expect_success 'checking that first commit is in all tags (tag)' '\n \tcat >expected <<-\\EOF &&\n\n-- \n2.54.0.548.gbe7bb2469c\n\n"},{"id":"545324","messageId":"20260611-ref-filter-memoized-contains-v3-2-b26af3dba285@gmail.com","threadId":"65776","inReplyTo":"20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com","subject":"[PATCH v3 2/3] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T03:00:14Z","receivedAt":"2026-06-12T03:00:28Z","isPatch":true,"body":"git branch and git for-each-ref run a separate reachability walk for\neach ref considered by --contains and --no-contains. Refs with shared\nhistory therefore traverse the same commits repeatedly.\n\ngit tag instead uses a depth-first walk that caches results across\nrefs. That walk can perform poorly without generation numbers: a\nnegative check may walk to the root instead of stopping at a nearby\ndivergence. Generation numbers let it stop below the oldest target.\n\nUse the memoized walk for all ref-filter callers when generation\nnumbers are available. Keep git tag on its existing path without\ngenerations. Caching still helps when many tags share deep history:\nffc4b8012d (tag: speed up --contains calculation, 2011-06-11) reduced\ngit tag --contains HEAD~200 in linux-2.6 from 15.417 to 5.329 seconds.\n\nThe new shared-history perf test improves from 0.72 to 0.03 seconds. In\na repository with 62,174 remote-tracking refs, running:\n\n git branch -r --contains c78ae85f3ce7e\n\nimproves from 104.365 seconds to 468 milliseconds.\n\nLink: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/\nLink: https://lore.kernel.org/r/20230324191009.GA536967@coredump.intra.peff.net\nLink: https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/\nLink: https://lore.kernel.org/r/20260608223430.GA340696@coredump.intra.peff.net\nLink: https://lore.kernel.org/r/CAOLa=ZSezQOj56-TezVaAcisUyczxhJmu4VghyFBHcBB_mKJ2A@mail.gmail.com\nSuggested-by: Jeff King \nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 3 ++-\n t/perf/p1500-graph-walks.sh | 28 +++++++++++++++++++++++++++-\n 2 files changed, 29 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 1d34d66fe8..572d2d47ff 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -820,7 +820,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n+\tif (filter->with_commit_tag_algo ||\n+\t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex 5b23ce5db9..d167b4f7e1 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -32,7 +32,16 @@ test_expect_success 'setup' '\n \t\techo \"X:$line\" >>test-tool-tags || return 1\n \tdone &&\n \n-\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit rev-list --first-parent --max-count=8192 HEAD >contains-commits &&\n+\ttest_file_not_empty contains-commits &&\n+\tgit update-ref refs/contains-perf-base \"$(tail -n 1 contains-commits)\" &&\n+\tawk \"{\n+\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n+\t}\" contains-commits |\n+\t\tgit update-ref --stdin &&\n+\tgit pack-refs --include \"refs/contains-perf/*\" &&\n+\n+\tcommit=$(git commit-tree HEAD^{tree}) &&\n \tgit update-ref refs/heads/disjoint-base $commit &&\n \n \tgit commit-graph write --reachable\n@@ -62,6 +71,23 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD /dev/null\n+'\n+\n test_perf 'is-base check: test-tool reach (refs)' '\n \ttest-tool reach get_branch_base_for_tip \nLink: https://lore.kernel.org/r/20260611072942.GG2191159@coredump.intra.peff.net\nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 8 +++++++-\n t/t6301-for-each-ref-errors.sh | 22 ++++++++++++++++++++++\n 2 files changed, 29 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 572d2d47ff..af5563d70f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -820,10 +820,16 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n+\tint result;\n+\n \tif (filter->with_commit_tag_algo ||\n \t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n-\treturn repo_is_descendant_of(the_repository, commit, list);\n+\n+\tresult = repo_is_descendant_of(the_repository, commit, list);\n+\tif (result < 0)\n+\t\tdie(_(\"failed to check reachability\"));\n+\treturn result;\n }\n \n int can_all_from_reach_with_flag(struct object_array *from,\ndiff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh\nindex e06feb06e9..72b27c8be3 100755\n--- a/t/t6301-for-each-ref-errors.sh\n+++ b/t/t6301-for-each-ref-errors.sh\n@@ -52,6 +52,28 @@ test_expect_success 'Missing objects are reported correctly' '\n \ttest_must_be_empty brief-err\n '\n \n+test_expect_success 'missing ancestors are reported by contains filters' '\n+\ttest_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n+\t{\n+\t\techo \"tree $(git rev-parse HEAD^{tree})\" &&\n+\t\techo \"parent $MISSING\" &&\n+\t\tgit cat-file commit HEAD |\n+\t\t\tsed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n+\t\techo &&\n+\t\techo \"missing parent\"\n+\t} >commit &&\n+\tbroken=$(git hash-object -t commit -w commit) &&\n+\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n+\tfor option in --contains --no-contains\n+\tdo\n+\t\ttest_must_fail git for-each-ref \"$option=HEAD\" \\\n+\t\t\trefs/heads/missing-parent >out 2>err &&\n+\t\ttest_must_be_empty out &&\n+\t\ttest_grep \"parse commit $MISSING\" err ||\n+\t\treturn 1\n+\tdone\n+'\n+\n test_expect_success 'ahead-behind requires an argument' '\n \ttest_must_fail git for-each-ref \\\n \t\t--format=\"%(ahead-behind)\" 2>err &&\n\n-- \n2.54.0.548.gbe7bb2469c\n\n"},{"id":"545344","messageId":"CAL71e4PRqN9iPCzvgwC1Vtj-kzn4Udv+v1LTFSUXtGnC5KGrpA@mail.gmail.com","threadId":"65776","inReplyTo":"20260611-ref-filter-memoized-contains-v3-1-b26af3dba285@gmail.com","subject":"Re: [PATCH v3 1/3] commit-reach: handle cycles in contains walk","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-12T06:53:41Z","receivedAt":"2026-06-12T06:53:53Z","isPatch":true,"body":"On Fri, 12 Jun 2026 at 05:00, Tamir Duberstein wrote:\n>\n> The memoized contains traversal used by git tag assumes that commit\n> ancestry is acyclic. Replacement refs can violate that assumption,\n> causing it to keep pushing an already active commit until memory is\n> exhausted.\n>\n\nThe cycle detection itself makes sense, but would it be simpler to\njust die() when a cycle is found rather than falling back to a\nsecond reachability walk?\n\nA cycle in the commit graph means replacement refs are\nmisconfigured. The existing code already loops forever when it\nhits one, so detecting and dying is strictly an improvement. The\nfallback adds a second codepath through the function, discards all\ncached results (so later candidates redo work), and papers over\nwhat is really a broken invariant.\n\ndo_lookup_replace_object() already dies when replacement refs\nchain deeper than MAXREPLACEDEPTH (which covers cycles), so the\nexisting contract treats this as a fatal configuration error.\nparse_commit_or_die() sets the same precedent within the walk\nitself.\n\nKristofer\n"},{"id":"545421","messageId":"CAJ-ks9n4461G-Me+1rf0ZgrC15ZW+1b1xcip=11e8=S=OjOuiQ@mail.gmail.com","threadId":"65776","inReplyTo":"CAL71e4PRqN9iPCzvgwC1Vtj-kzn4Udv+v1LTFSUXtGnC5KGrpA@mail.gmail.com","subject":"Re: [PATCH v3 1/3] commit-reach: handle cycles in contains walk","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T21:26:04Z","receivedAt":"2026-06-12T21:26:41Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 2:53 AM Kristofer Karlsson wrote:\n>\n> On Fri, 12 Jun 2026 at 05:00, Tamir Duberstein wrote:\n> >\n> > The memoized contains traversal used by git tag assumes that commit\n> > ancestry is acyclic. Replacement refs can violate that assumption,\n> > causing it to keep pushing an already active commit until memory is\n> > exhausted.\n> >\n>\n> The cycle detection itself makes sense, but would it be simpler to\n> just die() when a cycle is found rather than falling back to a\n> second reachability walk?\n>\n> A cycle in the commit graph means replacement refs are\n> misconfigured. The existing code already loops forever when it\n> hits one, so detecting and dying is strictly an improvement. The\n> fallback adds a second codepath through the function, discards all\n> cached results (so later candidates redo work), and papers over\n> what is really a broken invariant.\n>\n> do_lookup_replace_object() already dies when replacement refs\n> chain deeper than MAXREPLACEDEPTH (which covers cycles), so the\n> existing contract treats this as a fatal configuration error.\n> parse_commit_or_die() sets the same precedent within the walk\n> itself.\n\nYes. The test creates an ancestry cycle through replacement commit\nparents, so MAXREPLACEDEPTH does not catch this particular cycle. But I\nagree with the design conclusion: the history is malformed and the\nfallback only adds complexity.\n\nDone in v4.\n\nThanks!\n"},{"id":"545423","messageId":"20260612-ref-filter-memoized-contains-v4-0-5ed39fd001dd@gmail.com","threadId":"65776","inReplyTo":"20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com","subject":"[PATCH v4 0/3] Reuse --contains traversal results","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T21:49:11Z","receivedAt":"2026-06-12T21:49:19Z","isPatch":true,"body":"git tag uses a memoized traversal for --contains, while git branch\nand git for-each-ref repeat a reachability walk for each ref. Reuse\nthe memoized traversal when generation numbers can bound the walk.\n\nThe first patch makes the memoized traversal reject cyclic replacement\nhistories. The last makes the non-memoized path report reachability\nerrors.\n\nSigned-off-by: Tamir Duberstein \n\n---\nChanges in v4:\n- Die on cyclic ancestry instead of retrying another reachability walk.\n- Update the cycle test and credit Kristofer Karlsson.\n- Remove unexplained links to review messages.\n- Link to v3: https://patch.msgid.link/20260611-ref-filter-memoized-contains-v3-0-b26af3dba285@gmail.com\n\nChanges in v3:\n- Split missing-ancestor error handling into its own patch.\n- Use die() for reachability errors, remove redundant cache setup, and\n chain cycle-test cleanup.\n- Drop the unrelated empty-target-list behavior change.\n- Explain why git tag retains memoization without generation numbers.\n- Add p1500 coverage for all three frontends and a shared-history\n case.\n- Remove correctness checks from p1500 and drop output hashes.\n- Link to v2: https://patch.msgid.link/20260608-ref-filter-memoized-contains-v2-0-e72720344a7c@gmail.com\n\nChanges in v2:\n- Split cycle handling into a preparatory patch.\n- Exercise cycle handling through the existing git tag path.\n- Move perf result verification out of setup.\n- Link to v1: https://patch.msgid.link/20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com\n\n---\nTamir Duberstein (3):\n commit-reach: reject cycles in contains walk\n ref-filter: memoize --contains with generations\n commit-reach: die on contains walk errors\n\n commit-reach.c | 23 ++++++++++++++++++-----\n commit-reach.h | 3 ++-\n t/perf/p1500-graph-walks.sh | 28 +++++++++++++++++++++++++++-\n t/t6301-for-each-ref-errors.sh | 22 ++++++++++++++++++++++\n t/t7004-tag.sh | 18 ++++++++++++++++++\n 5 files changed, 87 insertions(+), 7 deletions(-)\n---\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nchange-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1\n\nBest regards,\n-- \nTamir Duberstein \n\n"},{"id":"545424","messageId":"20260612-ref-filter-memoized-contains-v4-1-5ed39fd001dd@gmail.com","threadId":"65776","inReplyTo":"20260612-ref-filter-memoized-contains-v4-0-5ed39fd001dd@gmail.com","subject":"[PATCH v4 1/3] commit-reach: reject cycles in contains walk","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T21:49:12Z","receivedAt":"2026-06-12T21:49:21Z","isPatch":true,"body":"The memoized contains traversal used by git tag assumes that commit\nancestry is acyclic. Replacement refs can violate that assumption,\ncausing it to keep pushing an already active commit until memory is\nexhausted.\n\nMark commits while they are active and die if the traversal encounters\nan active commit. Other failures in this walk already die through\nparse_commit_or_die(); using a second reachability walk would only add\na separate policy for malformed history.\n\nSuggested-by: Kristofer Karlsson \nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 12 +++++++++---\n commit-reach.h | 3 ++-\n t/t7004-tag.sh | 18 ++++++++++++++++++\n 3 files changed, 29 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..e1bedc596d 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -708,7 +708,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \n /*\n * Test whether the candidate is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n+ * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n+ * inconclusive.\n */\n static enum contains_result contains_test(struct commit *candidate,\n \t\t\t\t\t const struct commit_list *want,\n@@ -765,6 +766,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tif (result != CONTAINS_UNKNOWN)\n \t\treturn result;\n \n+\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n \tpush_to_contains_stack(candidate, &contains_stack);\n \twhile (contains_stack.nr) {\n \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n@@ -776,8 +778,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\t\tcontains_stack.nr--;\n \t\t}\n \t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful yes/no.\n+\t\t * A parent may have just been popped and marked, or may still\n+\t\t * be active when replacement refs create a cycle.\n \t\t */\n \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n \t\tcase CONTAINS_YES:\n@@ -787,7 +789,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \t\tcase CONTAINS_NO:\n \t\t\tentry->parents = parents->next;\n \t\t\tbreak;\n+\t\tcase CONTAINS_IN_PROGRESS:\n+\t\t\tdie(_(\"commit ancestry contains a cycle\"));\n \t\tcase CONTAINS_UNKNOWN:\n+\t\t\t*contains_cache_at(cache, parents->item) =\n+\t\t\t\tCONTAINS_IN_PROGRESS;\n \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n \t\t\tbreak;\n \t\t}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..f908d305b1 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -73,7 +73,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n enum contains_result {\n \tCONTAINS_UNKNOWN = 0,\n \tCONTAINS_NO,\n-\tCONTAINS_YES\n+\tCONTAINS_YES,\n+\tCONTAINS_IN_PROGRESS\n };\n \n define_commit_slab(contains_cache, enum contains_result);\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex d918005dd9..67309494d2 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1611,6 +1611,24 @@ test_expect_success 'checking that first commit is in all tags (hash)' '\n \ttest_cmp expected actual\n '\n \n+test_expect_success 'tag --contains rejects cyclic replacement histories' '\n+\tfirst=$(git rev-parse HEAD~2) &&\n+\tsecond=$(git rev-parse HEAD~) &&\n+\tthird=$(git rev-parse HEAD) &&\n+\ttest_when_finished \"\n+\t\tgit replace -d $first &&\n+\t\tgit replace -d $third &&\n+\t\tgit tag -d cycle-a cycle-b\n+\t\" &&\n+\tgit tag cycle-a \"$first\" &&\n+\tgit tag cycle-b \"$third\" &&\n+\tgit replace --graft \"$first\" \"$third\" \"$second\" &&\n+\tgit replace --graft \"$third\" \"$first\" &&\n+\ttest_must_fail git tag --contains=\"$second\" --list \"cycle-*\" \\\n+\t\t>/dev/null 2>err &&\n+\ttest_grep \"fatal: commit ancestry contains a cycle\" err\n+'\n+\n # other ways of specifying the commit\n test_expect_success 'checking that first commit is in all tags (tag)' '\n \tcat >expected <<-\\EOF &&\n\n-- \n2.54.0.548.gbe7bb2469c\n\n"},{"id":"545425","messageId":"20260612-ref-filter-memoized-contains-v4-2-5ed39fd001dd@gmail.com","threadId":"65776","inReplyTo":"20260612-ref-filter-memoized-contains-v4-0-5ed39fd001dd@gmail.com","subject":"[PATCH v4 2/3] ref-filter: memoize --contains with generations","fromName":"Tamir Duberstein","fromEmail":"tamird@gmail.com","sentAt":"2026-06-12T21:49:13Z","receivedAt":"2026-06-12T21:49:23Z","isPatch":true,"body":"git branch and git for-each-ref run a separate reachability walk for\neach ref considered by --contains and --no-contains. Refs with shared\nhistory therefore traverse the same commits repeatedly.\n\ngit tag instead uses a depth-first walk that caches results across\nrefs. That walk can perform poorly without generation numbers: a\nnegative check may walk to the root instead of stopping at a nearby\ndivergence. Generation numbers let it stop below the oldest target.\n\nUse the memoized walk for all ref-filter callers when generation\nnumbers are available. Keep git tag on its existing path without\ngenerations. Caching still helps when many tags share deep history:\nffc4b8012d (tag: speed up --contains calculation, 2011-06-11) reduced\ngit tag --contains HEAD~200 in linux-2.6 from 15.417 to 5.329 seconds.\n\nThe new shared-history perf test improves from 0.72 to 0.03 seconds. In\na repository with 62,174 remote-tracking refs, running:\n\n git branch -r --contains c78ae85f3ce7e\n\nimproves from 104.365 seconds to 468 milliseconds.\n\nSuggested-by: Jeff King \nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 3 ++-\n t/perf/p1500-graph-walks.sh | 28 +++++++++++++++++++++++++++-\n 2 files changed, 29 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex e1bedc596d..18fcd69113 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -805,7 +805,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n+\tif (filter->with_commit_tag_algo ||\n+\t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex 5b23ce5db9..d167b4f7e1 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -32,7 +32,16 @@ test_expect_success 'setup' '\n \t\techo \"X:$line\" >>test-tool-tags || return 1\n \tdone &&\n \n-\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit rev-list --first-parent --max-count=8192 HEAD >contains-commits &&\n+\ttest_file_not_empty contains-commits &&\n+\tgit update-ref refs/contains-perf-base \"$(tail -n 1 contains-commits)\" &&\n+\tawk \"{\n+\t\tprintf \\\"update refs/contains-perf/%04d %s\\\\n\\\", NR, \\$1\n+\t}\" contains-commits |\n+\t\tgit update-ref --stdin &&\n+\tgit pack-refs --include \"refs/contains-perf/*\" &&\n+\n+\tcommit=$(git commit-tree HEAD^{tree}) &&\n \tgit update-ref refs/heads/disjoint-base $commit &&\n \n \tgit commit-graph write --reachable\n@@ -62,6 +71,23 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD /dev/null\n+'\n+\n test_perf 'is-base check: test-tool reach (refs)' '\n \ttest-tool reach get_branch_base_for_tip \nSigned-off-by: Tamir Duberstein \n---\n commit-reach.c | 8 +++++++-\n t/t6301-for-each-ref-errors.sh | 22 ++++++++++++++++++++++\n 2 files changed, 29 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 18fcd69113..37b66b6b21 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -805,10 +805,16 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n+\tint result;\n+\n \tif (filter->with_commit_tag_algo ||\n \t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n-\treturn repo_is_descendant_of(the_repository, commit, list);\n+\n+\tresult = repo_is_descendant_of(the_repository, commit, list);\n+\tif (result < 0)\n+\t\tdie(_(\"failed to check reachability\"));\n+\treturn result;\n }\n \n int can_all_from_reach_with_flag(struct object_array *from,\ndiff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh\nindex e06feb06e9..72b27c8be3 100755\n--- a/t/t6301-for-each-ref-errors.sh\n+++ b/t/t6301-for-each-ref-errors.sh\n@@ -52,6 +52,28 @@ test_expect_success 'Missing objects are reported correctly' '\n \ttest_must_be_empty brief-err\n '\n \n+test_expect_success 'missing ancestors are reported by contains filters' '\n+\ttest_when_finished \"git update-ref -d refs/heads/missing-parent\" &&\n+\t{\n+\t\techo \"tree $(git rev-parse HEAD^{tree})\" &&\n+\t\techo \"parent $MISSING\" &&\n+\t\tgit cat-file commit HEAD |\n+\t\t\tsed -n -e \"/^author /p\" -e \"/^committer /p\" &&\n+\t\techo &&\n+\t\techo \"missing parent\"\n+\t} >commit &&\n+\tbroken=$(git hash-object -t commit -w commit) &&\n+\tgit update-ref refs/heads/missing-parent \"$broken\" &&\n+\tfor option in --contains --no-contains\n+\tdo\n+\t\ttest_must_fail git for-each-ref \"$option=HEAD\" \\\n+\t\t\trefs/heads/missing-parent >out 2>err &&\n+\t\ttest_must_be_empty out &&\n+\t\ttest_grep \"parse commit $MISSING\" err ||\n+\t\treturn 1\n+\tdone\n+'\n+\n test_expect_success 'ahead-behind requires an argument' '\n \ttest_must_fail git for-each-ref \\\n \t\t--format=\"%(ahead-behind)\" 2>err &&\n\n-- \n2.54.0.548.gbe7bb2469c\n\n"},{"id":"546709","messageId":"xmqqqzlpulkp.fsf@gitster.g","threadId":"65776","inReplyTo":"20260612-ref-filter-memoized-contains-v4-0-5ed39fd001dd@gmail.com","subject":"Re: [PATCH v4 0/3] Reuse --contains traversal results","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-29T20:40:38Z","receivedAt":"2026-06-29T20:40:41Z","isPatch":true,"body":"Tamir Duberstein writes:\n\n> git tag uses a memoized traversal for --contains, while git branch\n> and git for-each-ref repeat a reachability walk for each ref. Reuse\n> the memoized traversal when generation numbers can bound the walk.\n>\n> The first patch makes the memoized traversal reject cyclic replacement\n> histories. The last makes the non-memoized path report reachability\n> errors.\n\nThis unfortunately hasn't heard any responses since June 12th. Are\nthere remaining issues with it? Or do people fundamentally have\nobjections against this change? Or things are too busy in general\nthat there are more patches than there are folks willing to review\nthem?\n\n"},{"id":"548385","messageId":"20260716090525.GA1196203@coredump.intra.peff.net","threadId":"65776","inReplyTo":"20260612-ref-filter-memoized-contains-v4-1-5ed39fd001dd@gmail.com","subject":"Re: [PATCH v4 1/3] commit-reach: reject cycles in contains walk","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-16T09:05:25Z","receivedAt":"2026-07-16T09:05:34Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 05:49:12PM -0400, Tamir Duberstein wrote:\n\n> @@ -708,7 +708,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n> \n> /*\n> * Test whether the candidate is contained in the list.\n> - * Do not recurse to find out, though, but return -1 if inconclusive.\n> + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if\n> + * inconclusive.\n> */\n> static enum contains_result contains_test(struct commit *candidate,\n> \t\t\t\t\t const struct commit_list *want,\n\nThis hunk is a good cleanup, but unrelated to the patch at hand.\n\nWe used to return a bare -1, then that became CONTAINS_UNKNOWN in\na0262c51d0 (ref-filter: use contains_result enum consistently,\n2017-03-09). And then that value changed to 0 in a91aca44bf (ref-filter:\nuse separate cache for contains_tag_algo, 2017-03-09) when we started\nusing a slab.\n\nSo the code is correct and the comment is wrong, and it is worth\nupdating. I was just surprised to find it here.\n\n> @@ -765,6 +766,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> \tif (result != CONTAINS_UNKNOWN)\n> \t\treturn result;\n> \n> +\t*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;\n> \tpush_to_contains_stack(candidate, &contains_stack);\n> \twhile (contains_stack.nr) {\n> \t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n> @@ -776,8 +778,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> \t\t\tcontains_stack.nr--;\n> \t\t}\n> \t\t/*\n> -\t\t * If we just popped the stack, parents->item has been marked,\n> -\t\t * therefore contains_test will return a meaningful yes/no.\n> +\t\t * A parent may have just been popped and marked, or may still\n> +\t\t * be active when replacement refs create a cycle.\n> \t\t */\n> \t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n> \t\tcase CONTAINS_YES:\n> @@ -787,7 +789,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> \t\tcase CONTAINS_NO:\n> \t\t\tentry->parents = parents->next;\n> \t\t\tbreak;\n> +\t\tcase CONTAINS_IN_PROGRESS:\n> +\t\t\tdie(_(\"commit ancestry contains a cycle\"));\n> \t\tcase CONTAINS_UNKNOWN:\n> +\t\t\t*contains_cache_at(cache, parents->item) =\n> +\t\t\t\tCONTAINS_IN_PROGRESS;\n> \t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n> \t\t\tbreak;\n> \t\t}\n\nNice, this looks cleanly done.\n\n> +test_expect_success 'tag --contains rejects cyclic replacement histories' '\n> +\tfirst=$(git rev-parse HEAD~2) &&\n> +\tsecond=$(git rev-parse HEAD~) &&\n> +\tthird=$(git rev-parse HEAD) &&\n> +\ttest_when_finished \"\n> +\t\tgit replace -d $first &&\n> +\t\tgit replace -d $third &&\n> +\t\tgit tag -d cycle-a cycle-b\n> +\t\" &&\n> +\tgit tag cycle-a \"$first\" &&\n> +\tgit tag cycle-b \"$third\" &&\n> +\tgit replace --graft \"$first\" \"$third\" \"$second\" &&\n> +\tgit replace --graft \"$third\" \"$first\" &&\n> +\ttest_must_fail git tag --contains=\"$second\" --list \"cycle-*\" \\\n> +\t\t>/dev/null 2>err &&\n> +\ttest_grep \"fatal: commit ancestry contains a cycle\" err\n> +'\n\nLikewise the test looks good.\n\n-Peff\n"},{"id":"548387","messageId":"20260716091822.GA1212956@coredump.intra.peff.net","threadId":"65776","inReplyTo":"20260612-ref-filter-memoized-contains-v4-3-5ed39fd001dd@gmail.com","subject":"Re: [PATCH v4 3/3] commit-reach: die on contains walk errors","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-16T09:18:22Z","receivedAt":"2026-07-16T09:18:24Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 05:49:14PM -0400, Tamir Duberstein wrote:\n\n> int commit_contains(struct ref_filter *filter, struct commit *commit,\n> \t\t struct commit_list *list, struct contains_cache *cache)\n> {\n> +\tint result;\n> +\n> \tif (filter->with_commit_tag_algo ||\n> \t generation_numbers_enabled(the_repository))\n> \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> -\treturn repo_is_descendant_of(the_repository, commit, list);\n> +\n> +\tresult = repo_is_descendant_of(the_repository, commit, list);\n> +\tif (result < 0)\n> +\t\tdie(_(\"failed to check reachability\"));\n> +\treturn result;\n\nMakes sense. And we can see from the test that repo_is_descendant_of()\nwill already have printed the real reason for the error.\n\n-Peff\n"},{"id":"548388","messageId":"20260716091924.GB1212956@coredump.intra.peff.net","threadId":"65776","inReplyTo":"xmqqqzlpulkp.fsf@gitster.g","subject":"Re: [PATCH v4 0/3] Reuse --contains traversal results","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-16T09:19:24Z","receivedAt":"2026-07-16T09:19:26Z","isPatch":true,"body":"On Mon, Jun 29, 2026 at 01:40:38PM -0700, Junio C Hamano wrote:\n\n> Tamir Duberstein writes:\n> \n> > git tag uses a memoized traversal for --contains, while git branch\n> > and git for-each-ref repeat a reachability walk for each ref. Reuse\n> > the memoized traversal when generation numbers can bound the walk.\n> >\n> > The first patch makes the memoized traversal reject cyclic replacement\n> > histories. The last makes the non-memoized path report reachability\n> > errors.\n> \n> This unfortunately hasn't heard any responses since June 12th. Are\n> there remaining issues with it? Or do people fundamentally have\n> objections against this change? Or things are too busy in general\n> that there are more patches than there are folks willing to review\n> them?\n\nThe last one. ;)\n\nI think the direction is good and the patches themselves look fine. The\nonly nit I had was that there's an unrelated (but good) comment cleanup\nin patch 1. That could be split into its own patch, but I am also fine\nto declare victory on v4.\n\n-Peff\n"}]}