[PATCH] ref-filter: reuse --contains traversal results

[PATCH] ref-filter: reuse --contains traversal results

[Tamir Duberstein]

git branch and git for-each-ref call repo_is_descendant_of() for each
candidate selected by --contains or --no-contains. Each call starts a
new graph walk, so refs with shared history repeatedly traverse the same
commits.

ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced
the tag traversal that caches positive and negative answers across
candidates. ee2bd06b0f (ref-filter: implement '--contains' option,
2015-07-07) preserved the branch and tag implementations when ref-filter
learned --contains. 008ed7df930 (tag.c: use the correct algorithm for
the '--contains' option, 2015-10-18) noted that they should be unified.

Use the memoized traversal for every ref-filter contains check and
remove the implementation selector. The cache records answers for one
fixed target list, so document that callers must clear it before
changing the list.

The memoized depth-first walk assumes acyclic ancestry, but replacement
refs can create cycles. Track commits while they are on the walk. If a
cycle is found, discard partial cache entries and use
repo_is_descendant_of() for that candidate.

The branch and for-each-ref path passed repo_is_descendant_of() through
a Boolean interface. In configurations where it returned -1 for missing
ancestry, ref-filter treated the error as "contains". The memoized path
instead fails when ancestry cannot be parsed, as git tag already did.
During review of the 2018 reachability series, making parse failures
fatal was explicitly deferred because that series was intended to
preserve behavior. Unifying the implementations now makes all callers
fail consistently instead of preserving that accidental Boolean
interpretation.

The added p1500 case uses up to 8,192 packed refs along one first-parent
history. It improves from 0.68 to 0.03 seconds.

On a checkout with 62,174 remote-tracking refs, I ran:

    hyperfine --warmup 0 --runs 3 \
        --command-name parent \
        '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
        --command-name this-commit \
        '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'

The results were:

             parent       this commit
  elapsed    104.365 s     467.7 ms
  user        93.702 s     220.2 ms
  system       0.723 s     182.7 ms

The wall-time standard deviations were 11.356 seconds and 133.8
milliseconds, respectively, for a 223x speedup. Both commands produced
output with SHA-256
2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.

Both revisions were rebuilt with the default -O2 flags using Apple clang
21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a
16-core Apple M4 Max (12 performance and four efficiency cores) and 128
GB RAM.

Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/
Link: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/
Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/
Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 builtin/tag.c                  |  1 -
 commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------
 commit-reach.h                 | 15 ++++++++++----
 ref-filter.c                   |  6 ++++--
 ref-filter.h                   |  7 +++----
 t/helper/test-reach.c          | 10 ++--------
 t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-
 t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++
 t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++
 t/t6600-test-reach.sh          |  6 ++----
 10 files changed, 117 insertions(+), 36 deletions(-)

diff --git a/builtin/tag.c b/builtin/tag.c
index d51c2e3349..9f34d948d4 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,
 
 	if (verify_ref_format(format))
 		die(_("unable to parse format string"));
-	filter->with_commit_tag_algo = 1;
 	filter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);
 
 	free(to_free);
diff --git a/commit-reach.c b/commit-reach.c
index 9b3ea46d6f..6e599a3670 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -6,7 +6,6 @@
 #include "decorate.h"
 #include "hex.h"
 #include "prio-queue.h"
-#include "ref-filter.h"
 #include "revision.h"
 #include "tag.h"
 #include "commit-reach.h"
@@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
 
 /*
  * Test whether the candidate is contained in the list.
- * Do not recurse to find out, though, but return -1 if inconclusive.
+ * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if
+ * inconclusive.
  */
 static enum contains_result contains_test(struct commit *candidate,
 					  const struct commit_list *want,
@@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta
 	contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
 }
 
-static enum contains_result contains_tag_algo(struct commit *candidate,
-					      const struct commit_list *want,
-					      struct contains_cache *cache)
+static enum contains_result contains_algo(struct commit *candidate,
+					  struct commit_list *want,
+					  struct contains_cache *cache)
 {
 	struct contains_stack contains_stack = { 0, 0, NULL };
 	enum contains_result result;
@@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 	if (result != CONTAINS_UNKNOWN)
 		return result;
 
+	*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;
 	push_to_contains_stack(candidate, &contains_stack);
 	while (contains_stack.nr) {
 		struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
@@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 			contains_stack.nr--;
 		}
 		/*
-		 * If we just popped the stack, parents->item has been marked,
-		 * therefore contains_test will return a meaningful yes/no.
+		 * A parent may have just been popped and marked, or may still
+		 * be active when replacement refs create a cycle.
 		 */
 		else switch (contains_test(parents->item, want, cache, cutoff)) {
 		case CONTAINS_YES:
@@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 		case CONTAINS_NO:
 			entry->parents = parents->next;
 			break;
+		case CONTAINS_IN_PROGRESS:
+			/*
+			 * Partial negative answers are not safe across a cycle.
+			 * Discard them and use the cycle-safe reachability walk.
+			 */
+			goto cycle;
 		case CONTAINS_UNKNOWN:
+			*contains_cache_at(cache, parents->item) =
+				CONTAINS_IN_PROGRESS;
 			push_to_contains_stack(parents->item, &contains_stack);
 			break;
 		}
 	}
 	free(contains_stack.contains_stack);
 	return contains_test(candidate, want, cache, cutoff);
+
+cycle:
+	free(contains_stack.contains_stack);
+	clear_contains_cache(cache);
+	init_contains_cache(cache);
+
+	result = repo_is_descendant_of(the_repository, candidate, want);
+	if (result < 0)
+		exit(128);
+	*contains_cache_at(cache, candidate) =
+		result ? CONTAINS_YES : CONTAINS_NO;
+	return result ? CONTAINS_YES : CONTAINS_NO;
 }
 
-int commit_contains(struct ref_filter *filter, struct commit *commit,
-		    struct commit_list *list, struct contains_cache *cache)
+int commit_contains(struct commit *commit, struct commit_list *list,
+		    struct contains_cache *cache)
 {
-	if (filter->with_commit_tag_algo)
-		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
-	return repo_is_descendant_of(the_repository, commit, list);
+	if (!list)
+		return 1;
+	return contains_algo(commit, list, cache) == CONTAINS_YES;
 }
 
 int can_all_from_reach_with_flag(struct object_array *from,
diff --git a/commit-reach.h b/commit-reach.h
index 3f3a563d8a..144dc56275 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -5,7 +5,6 @@
 #include "commit-slab.h"
 
 struct commit_list;
-struct ref_filter;
 struct object_id;
 struct object_array;
 
@@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
 enum contains_result {
 	CONTAINS_UNKNOWN = 0,
 	CONTAINS_NO,
-	CONTAINS_YES
+	CONTAINS_YES,
+	CONTAINS_IN_PROGRESS
 };
 
 define_commit_slab(contains_cache, enum contains_result);
 
-int commit_contains(struct ref_filter *filter, struct commit *commit,
-		    struct commit_list *list, struct contains_cache *cache);
+/*
+ * Return whether "commit" is a descendant of any commit in "list". An empty
+ * list matches.
+ *
+ * "cache" records answers for one fixed "list". Clear it before changing the
+ * list.
+ */
+int commit_contains(struct commit *commit, struct commit_list *list,
+		    struct contains_cache *cache);
 
 /*
  * Determine if every commit in 'from' can reach at least one commit
diff --git a/ref-filter.c b/ref-filter.c
index 1da4c0e60d..7788147959 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,
 			return NULL;
 		/* We perform the filtering for the '--contains' option... */
 		if (filter->with_commit &&
-		    !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))
+		    !commit_contains(commit, filter->with_commit,
+				     &filter->internal.contains_cache))
 			return NULL;
 		/* ...or for the `--no-contains' option */
 		if (filter->no_commit &&
-		    commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))
+		    commit_contains(commit, filter->no_commit,
+				    &filter->internal.no_contains_cache))
 			return NULL;
 	}
 
diff --git a/ref-filter.h b/ref-filter.h
index 120221b47f..9e14afca9c 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -73,10 +73,9 @@ struct ref_filter {
 	struct commit_list *reachable_from;
 	struct commit_list *unreachable_from;
 
-	unsigned int with_commit_tag_algo : 1,
-		match_as_path : 1,
-		ignore_case : 1,
-		detached : 1;
+	unsigned int match_as_path : 1,
+		     ignore_case : 1,
+		     detached : 1;
 	unsigned int kind,
 		lines;
 	int abbrev,
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index 5d86a96c17..82235f713e 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -6,7 +6,6 @@
 #include "gettext.h"
 #include "hex.h"
 #include "object-name.h"
-#include "ref-filter.h"
 #include "setup.h"
 #include "string-list.h"
 #include "tag.h"
@@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)
 
 		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
 	} else if (!strcmp(av[1], "commit_contains")) {
-		struct ref_filter filter = REF_FILTER_INIT;
 		struct contains_cache cache;
 		init_contains_cache(&cache);
 
-		if (ac > 2 && !strcmp(av[2], "--tag"))
-			filter.with_commit_tag_algo = 1;
-		else
-			filter.with_commit_tag_algo = 0;
-
-		printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
+		printf("%s(_,A,X,_):%d\n", av[1],
+		       commit_contains(A, X, &cache));
 		clear_contains_cache(&cache);
 	} else if (!strcmp(av[1], "get_reachable_subset")) {
 		const int reachable_flag = 1;
diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
index 5b23ce5db9..ac68fdbacd 100755
--- a/t/perf/p1500-graph-walks.sh
+++ b/t/perf/p1500-graph-walks.sh
@@ -5,6 +5,8 @@ test_description='Commit walk performance tests'
 
 test_perf_large_repo
 
+contains_ref_limit=8192
+
 test_expect_success 'setup' '
 	git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs &&
 	sort -r allrefs | head -n 50 >refs &&
@@ -32,10 +34,25 @@ test_expect_success 'setup' '
 		echo "X:$line" >>test-tool-tags || return 1
 	done &&
 
+	git rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&
+	contains_ref_count=$(wc -l <contains-commits) &&
+	test "$contains_ref_count" -gt 0 &&
+	contains_base=$(tail -n 1 contains-commits) &&
+	export contains_base &&
+	awk "{
+		printf \"update refs/contains-perf/%04d %s\\n\", NR, \$1
+	}" contains-commits |
+		git update-ref --stdin &&
+	git pack-refs --include "refs/contains-perf/*" &&
+
 	commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&
 	git update-ref refs/heads/disjoint-base $commit &&
 
-	git commit-graph write --reachable
+	git commit-graph write --reachable &&
+
+	git for-each-ref --contains="$contains_base" \
+		refs/contains-perf/ >actual &&
+	test_line_count = $contains_ref_count actual
 '
 
 test_perf 'ahead-behind counts: git for-each-ref' '
@@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '
 	xargs git tag --merged=HEAD <tags
 '
 
+test_perf 'contains: git for-each-ref --contains' '
+	git for-each-ref --contains="$contains_base" \
+		refs/contains-perf/ >/dev/null
+'
+
 test_perf 'is-base check: test-tool reach (refs)' '
 	test-tool reach get_branch_base_for_tip <test-tool-refs
 '
diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh
index e06feb06e9..169cc70c23 100755
--- a/t/t6301-for-each-ref-errors.sh
+++ b/t/t6301-for-each-ref-errors.sh
@@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '
 	test_must_be_empty brief-err
 '
 
+test_expect_success 'missing ancestors are reported by contains filters' '
+	test_when_finished "git update-ref -d refs/heads/missing-parent" &&
+	{
+		echo "tree $(git rev-parse HEAD^{tree})" &&
+		echo "parent $MISSING" &&
+		git cat-file commit HEAD |
+			sed -n -e "/^author /p" -e "/^committer /p" &&
+		echo &&
+		echo "missing parent"
+	} >commit &&
+	broken=$(git hash-object -t commit -w commit) &&
+	git update-ref refs/heads/missing-parent "$broken" &&
+	test_must_fail git for-each-ref --contains=HEAD \
+		refs/heads/missing-parent >out 2>err &&
+	test_must_be_empty out &&
+	test_grep "unable to parse commit $MISSING" err
+'
+
 test_expect_success 'ahead-behind requires an argument' '
 	test_must_fail git for-each-ref \
 		--format="%(ahead-behind)" 2>err &&
diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
index 7f060d97bf..423505d1fb 100755
--- a/t/t6302-for-each-ref-filter.sh
+++ b/t/t6302-for-each-ref-filter.sh
@@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '
 	test_cmp expect actual
 '
 
+test_expect_success 'contains handles cyclic replacement histories' '
+	one=$(git rev-parse one) &&
+	three=$(git rev-parse three) &&
+	test_when_finished "
+		git replace -d $one
+		git replace -d $three
+		git tag -d cycle-a cycle-b
+	" &&
+	git tag cycle-a "$one" &&
+	git tag cycle-b "$three" &&
+	git replace --graft "$one" "$three" two &&
+	git replace --graft "$three" "$one" &&
+	cat >expect <<-\EOF &&
+	refs/tags/cycle-a
+	refs/tags/cycle-b
+	EOF
+	git for-each-ref --format="%(refname)" --contains=two \
+		"refs/tags/cycle-*" >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success '%(color) must fail' '
 	test_must_fail git for-each-ref --format="%(color)%(refname)"
 '
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..1ecc2571c2 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '
 	X:commit-9-3
 	EOF
 	echo "commit_contains(_,A,X,_):1" >expect &&
-	test_all_modes commit_contains &&
-	test_all_modes commit_contains --tag
+	test_all_modes commit_contains
 '
 
 test_expect_success 'commit_contains:miss' '
@@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '
 	X:commit-9-3
 	EOF
 	echo "commit_contains(_,A,X,_):0" >expect &&
-	test_all_modes commit_contains &&
-	test_all_modes commit_contains --tag
+	test_all_modes commit_contains
 '
 
 test_expect_success 'rev-list: basic topo-order' '

---
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1

Best regards,
--  
Tamir Duberstein <tamird@gmail.com>

Re: [PATCH] ref-filter: reuse --contains traversal results

[Karthik Nayak]

[-- Attachment #1: Type: text/plain, Size: 17907 bytes --]

Tamir Duberstein <tamird@gmail.com> writes:

> git branch and git for-each-ref call repo_is_descendant_of() for each
> candidate selected by --contains or --no-contains. Each call starts a
> new graph walk, so refs with shared history repeatedly traverse the same
> commits.
>
> ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced
> the tag traversal that caches positive and negative answers across
> candidates. ee2bd06b0f (ref-filter: implement '--contains' option,
> 2015-07-07) preserved the branch and tag implementations when ref-filter
> learned --contains. 008ed7df930 (tag.c: use the correct algorithm for
> the '--contains' option, 2015-10-18) noted that they should be unified.
>

Nicely explained. We should've merged this long ago, so this is a
worthwhile change.

> Use the memoized traversal for every ref-filter contains check and
> remove the implementation selector. The cache records answers for one
> fixed target list, so document that callers must clear it before
> changing the list.
>
> The memoized depth-first walk assumes acyclic ancestry, but replacement
> refs can create cycles. Track commits while they are on the walk. If a
> cycle is found, discard partial cache entries and use
> repo_is_descendant_of() for that candidate.
>
> The branch and for-each-ref path passed repo_is_descendant_of() through
> a Boolean interface. In configurations where it returned -1 for missing
> ancestry, ref-filter treated the error as "contains". The memoized path
> instead fails when ancestry cannot be parsed, as git tag already did.
> During review of the 2018 reachability series, making parse failures
> fatal was explicitly deferred because that series was intended to
> preserve behavior. Unifying the implementations now makes all callers
> fail consistently instead of preserving that accidental Boolean
> interpretation.
>
> The added p1500 case uses up to 8,192 packed refs along one first-parent
> history. It improves from 0.68 to 0.03 seconds.
>
> On a checkout with 62,174 remote-tracking refs, I ran:
>
>     hyperfine --warmup 0 --runs 3 \
>         --command-name parent \
>         '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
>         --command-name this-commit \
>         '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'
>
> The results were:
>
>              parent       this commit
>   elapsed    104.365 s     467.7 ms
>   user        93.702 s     220.2 ms
>   system       0.723 s     182.7 ms
>
> The wall-time standard deviations were 11.356 seconds and 133.8
> milliseconds, respectively, for a 223x speedup. Both commands produced
> output with SHA-256
> 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.
>
> Both revisions were rebuilt with the default -O2 flags using Apple clang
> 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a
> 16-core Apple M4 Max (12 performance and four efficiency cores) and 128
> GB RAM.
>
> Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/
> Link: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/
> Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/
> Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> ---
>  builtin/tag.c                  |  1 -
>  commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------
>  commit-reach.h                 | 15 ++++++++++----
>  ref-filter.c                   |  6 ++++--
>  ref-filter.h                   |  7 +++----
>  t/helper/test-reach.c          | 10 ++--------
>  t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-
>  t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++
>  t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++
>  t/t6600-test-reach.sh          |  6 ++----
>  10 files changed, 117 insertions(+), 36 deletions(-)
>
> diff --git a/builtin/tag.c b/builtin/tag.c
> index d51c2e3349..9f34d948d4 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,
>
>  	if (verify_ref_format(format))
>  		die(_("unable to parse format string"));
> -	filter->with_commit_tag_algo = 1;

We were selectively using the algo for `git tag`, like mentioned I guess
we'll entirely remove `with_commit_tag_algo` below somewhere

>  	filter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);
>
>  	free(to_free);
> diff --git a/commit-reach.c b/commit-reach.c
> index 9b3ea46d6f..6e599a3670 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -6,7 +6,6 @@
>  #include "decorate.h"
>  #include "hex.h"
>  #include "prio-queue.h"
> -#include "ref-filter.h"
>  #include "revision.h"
>  #include "tag.h"
>  #include "commit-reach.h"
> @@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
>
>  /*
>   * Test whether the candidate is contained in the list.
> - * Do not recurse to find out, though, but return -1 if inconclusive.
> + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if
> + * inconclusive.

Okay so the code does return CONTAINS_UNKNOWN which is an enum beginning
at 0, so this makes sense.

>   */
>  static enum contains_result contains_test(struct commit *candidate,
>  					  const struct commit_list *want,
> @@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta
>  	contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
>  }
>
> -static enum contains_result contains_tag_algo(struct commit *candidate,
> -					      const struct commit_list *want,
> -					      struct contains_cache *cache)
> +static enum contains_result contains_algo(struct commit *candidate,
> +					  struct commit_list *want,
> +					  struct contains_cache *cache)
>  {
>  	struct contains_stack contains_stack = { 0, 0, NULL };
>  	enum contains_result result;
> @@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
>  	if (result != CONTAINS_UNKNOWN)
>  		return result;
>
> +	*contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;
>  	push_to_contains_stack(candidate, &contains_stack);
>  	while (contains_stack.nr) {
>  		struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
> @@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
>  			contains_stack.nr--;
>  		}
>  		/*
> -		 * If we just popped the stack, parents->item has been marked,
> -		 * therefore contains_test will return a meaningful yes/no.
> +		 * A parent may have just been popped and marked, or may still
> +		 * be active when replacement refs create a cycle.
>  		 */
>  		else switch (contains_test(parents->item, want, cache, cutoff)) {
>  		case CONTAINS_YES:
> @@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
>  		case CONTAINS_NO:
>  			entry->parents = parents->next;
>  			break;
> +		case CONTAINS_IN_PROGRESS:
> +			/*
> +			 * Partial negative answers are not safe across a cycle.
> +			 * Discard them and use the cycle-safe reachability walk.
> +			 */
> +			goto cycle;
>

If I understand this correctly, we now use CONTAINS_IN_PROGRESS to
showcase a commit for which we still don't have a result. Since any
commit with UNKNOWN will start a recursive search through its parents.

So with this if we encounter a CONTAINS_IN_PROGRESS while recursion,
this would indicate that we hit a cyclic graph and so go to the fallback
of using repo_is_descendant_of(). So this avoids an infinite recursion
in such instances. Makes sense.

>  		case CONTAINS_UNKNOWN:
> +			*contains_cache_at(cache, parents->item) =
> +				CONTAINS_IN_PROGRESS;
>  			push_to_contains_stack(parents->item, &contains_stack);
>  			break;
>  		}
>  	}
>  	free(contains_stack.contains_stack);
>  	return contains_test(candidate, want, cache, cutoff);
> +
> +cycle:
> +	free(contains_stack.contains_stack);
> +	clear_contains_cache(cache);
> +	init_contains_cache(cache);
> +
> +	result = repo_is_descendant_of(the_repository, candidate, want);
> +	if (result < 0)
> +		exit(128);
> +	*contains_cache_at(cache, candidate) =
> +		result ? CONTAINS_YES : CONTAINS_NO;
> +	return result ? CONTAINS_YES : CONTAINS_NO;
>  }
>
> -int commit_contains(struct ref_filter *filter, struct commit *commit,
> -		    struct commit_list *list, struct contains_cache *cache)
> +int commit_contains(struct commit *commit, struct commit_list *list,
> +		    struct contains_cache *cache)
>  {
> -	if (filter->with_commit_tag_algo)
> -		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
> -	return repo_is_descendant_of(the_repository, commit, list);
> +	if (!list)
> +		return 1;
> +	return contains_algo(commit, list, cache) == CONTAINS_YES;
>  }
>
>  int can_all_from_reach_with_flag(struct object_array *from,
> diff --git a/commit-reach.h b/commit-reach.h
> index 3f3a563d8a..144dc56275 100644
> --- a/commit-reach.h
> +++ b/commit-reach.h
> @@ -5,7 +5,6 @@
>  #include "commit-slab.h"
>
>  struct commit_list;
> -struct ref_filter;
>  struct object_id;
>  struct object_array;
>
> @@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
>  enum contains_result {
>  	CONTAINS_UNKNOWN = 0,
>  	CONTAINS_NO,
> -	CONTAINS_YES
> +	CONTAINS_YES,
> +	CONTAINS_IN_PROGRESS
>  };
>
>  define_commit_slab(contains_cache, enum contains_result);
>
> -int commit_contains(struct ref_filter *filter, struct commit *commit,
> -		    struct commit_list *list, struct contains_cache *cache);
> +/*
> + * Return whether "commit" is a descendant of any commit in "list". An empty
> + * list matches.
> + *
> + * "cache" records answers for one fixed "list". Clear it before changing the
> + * list.
> + */
> +int commit_contains(struct commit *commit, struct commit_list *list,
> +		    struct contains_cache *cache);
>
>  /*
>   * Determine if every commit in 'from' can reach at least one commit
> diff --git a/ref-filter.c b/ref-filter.c
> index 1da4c0e60d..7788147959 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,
>  			return NULL;
>  		/* We perform the filtering for the '--contains' option... */
>  		if (filter->with_commit &&
> -		    !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))
> +		    !commit_contains(commit, filter->with_commit,
> +				     &filter->internal.contains_cache))
>  			return NULL;
>  		/* ...or for the `--no-contains' option */
>  		if (filter->no_commit &&
> -		    commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))
> +		    commit_contains(commit, filter->no_commit,
> +				    &filter->internal.no_contains_cache))
>  			return NULL;
>  	}
>
> diff --git a/ref-filter.h b/ref-filter.h
> index 120221b47f..9e14afca9c 100644
> --- a/ref-filter.h
> +++ b/ref-filter.h
> @@ -73,10 +73,9 @@ struct ref_filter {
>  	struct commit_list *reachable_from;
>  	struct commit_list *unreachable_from;
>
> -	unsigned int with_commit_tag_algo : 1,
> -		match_as_path : 1,
> -		ignore_case : 1,
> -		detached : 1;
> +	unsigned int match_as_path : 1,
> +		     ignore_case : 1,
> +		     detached : 1;
>  	unsigned int kind,
>  		lines;
>  	int abbrev,

Nit: With the changes above. I do wish it was split into two commits.
1. Fix cyclic recursions in the algo.
2. Use the algo for all filter types.

> diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
> index 5d86a96c17..82235f713e 100644
> --- a/t/helper/test-reach.c
> +++ b/t/helper/test-reach.c
> @@ -6,7 +6,6 @@
>  #include "gettext.h"
>  #include "hex.h"
>  #include "object-name.h"
> -#include "ref-filter.h"
>  #include "setup.h"
>  #include "string-list.h"
>  #include "tag.h"
> @@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)
>
>  		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
>  	} else if (!strcmp(av[1], "commit_contains")) {
> -		struct ref_filter filter = REF_FILTER_INIT;
>  		struct contains_cache cache;
>  		init_contains_cache(&cache);
>
> -		if (ac > 2 && !strcmp(av[2], "--tag"))
> -			filter.with_commit_tag_algo = 1;
> -		else
> -			filter.with_commit_tag_algo = 0;
> -
> -		printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
> +		printf("%s(_,A,X,_):%d\n", av[1],
> +		       commit_contains(A, X, &cache));
>  		clear_contains_cache(&cache);
>  	} else if (!strcmp(av[1], "get_reachable_subset")) {
>  		const int reachable_flag = 1;

Makes sense.

> diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
> index 5b23ce5db9..ac68fdbacd 100755
> --- a/t/perf/p1500-graph-walks.sh
> +++ b/t/perf/p1500-graph-walks.sh
> @@ -5,6 +5,8 @@ test_description='Commit walk performance tests'
>
>  test_perf_large_repo
>
> +contains_ref_limit=8192
> +
>  test_expect_success 'setup' '
>  	git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs &&
>  	sort -r allrefs | head -n 50 >refs &&
> @@ -32,10 +34,25 @@ test_expect_success 'setup' '
>  		echo "X:$line" >>test-tool-tags || return 1
>  	done &&
>
> +	git rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&
> +	contains_ref_count=$(wc -l <contains-commits) &&
> +	test "$contains_ref_count" -gt 0 &&
> +	contains_base=$(tail -n 1 contains-commits) &&
> +	export contains_base &&
> +	awk "{
> +		printf \"update refs/contains-perf/%04d %s\\n\", NR, \$1
> +	}" contains-commits |
> +		git update-ref --stdin &&
> +	git pack-refs --include "refs/contains-perf/*" &&
> +
>  	commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&
>  	git update-ref refs/heads/disjoint-base $commit &&
>
> -	git commit-graph write --reachable
> +	git commit-graph write --reachable &&
> +
> +	git for-each-ref --contains="$contains_base" \
> +		refs/contains-perf/ >actual &&
> +	test_line_count = $contains_ref_count actual

Shouldn't this be a separate test and not a part of the setup?

>  '
>
>  test_perf 'ahead-behind counts: git for-each-ref' '
> @@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '
>  	xargs git tag --merged=HEAD <tags
>  '
>
> +test_perf 'contains: git for-each-ref --contains' '
> +	git for-each-ref --contains="$contains_base" \
> +		refs/contains-perf/ >/dev/null
> +'
> +

Ah! we also have this, so perhaps moving the `test_line_count` here and
dropping it above would be better.

>  test_perf 'is-base check: test-tool reach (refs)' '
>  	test-tool reach get_branch_base_for_tip <test-tool-refs
>  '
> diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh
> index e06feb06e9..169cc70c23 100755
> --- a/t/t6301-for-each-ref-errors.sh
> +++ b/t/t6301-for-each-ref-errors.sh
> @@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '
>  	test_must_be_empty brief-err
>  '
>
> +test_expect_success 'missing ancestors are reported by contains filters' '
> +	test_when_finished "git update-ref -d refs/heads/missing-parent" &&
> +	{
> +		echo "tree $(git rev-parse HEAD^{tree})" &&
> +		echo "parent $MISSING" &&
> +		git cat-file commit HEAD |
> +			sed -n -e "/^author /p" -e "/^committer /p" &&
> +		echo &&
> +		echo "missing parent"
> +	} > commit &&
> +	broken=$(git hash-object -t commit -w commit) &&
> +	git update-ref refs/heads/missing-parent "$broken" &&
> +	test_must_fail git for-each-ref --contains=HEAD \
> +		refs/heads/missing-parent >out 2>err &&
> +	test_must_be_empty out &&
> +	test_grep "unable to parse commit $MISSING" err
> +'
> +
>  test_expect_success 'ahead-behind requires an argument' '
>  	test_must_fail git for-each-ref \
>  		--format="%(ahead-behind)" 2>err &&
> diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
> index 7f060d97bf..423505d1fb 100755
> --- a/t/t6302-for-each-ref-filter.sh
> +++ b/t/t6302-for-each-ref-filter.sh
> @@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '
>  	test_cmp expect actual
>  '
>
> +test_expect_success 'contains handles cyclic replacement histories' '
> +	one=$(git rev-parse one) &&
> +	three=$(git rev-parse three) &&
> +	test_when_finished "
> +		git replace -d $one
> +		git replace -d $three
> +		git tag -d cycle-a cycle-b
> +	" &&
> +	git tag cycle-a "$one" &&
> +	git tag cycle-b "$three" &&
> +	git replace --graft "$one" "$three" two &&
> +	git replace --graft "$three" "$one" &&
> +	cat >expect <<-\EOF &&
> +	refs/tags/cycle-a
> +	refs/tags/cycle-b
> +	EOF
> +	git for-each-ref --format="%(refname)" --contains=two \
> +		"refs/tags/cycle-*" >actual &&
> +	test_cmp expect actual
> +'
> +
>  test_expect_success '%(color) must fail' '
>  	test_must_fail git for-each-ref --format="%(color)%(refname)"
>  '
> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index b5b314e570..1ecc2571c2 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '
>  	X:commit-9-3
>  	EOF
>  	echo "commit_contains(_,A,X,_):1" >expect &&
> -	test_all_modes commit_contains &&
> -	test_all_modes commit_contains --tag
> +	test_all_modes commit_contains
>  '
>
>  test_expect_success 'commit_contains:miss' '
> @@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '
>  	X:commit-9-3
>  	EOF
>  	echo "commit_contains(_,A,X,_):0" >expect &&
> -	test_all_modes commit_contains &&
> -	test_all_modes commit_contains --tag
> +	test_all_modes commit_contains
>  '
>
>  test_expect_success 'rev-list: basic topo-order' '
>
> ---
> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
> change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1
>
> Best regards,
> --
> Tamir Duberstein <tamird@gmail.com>

Overall the patch looks great. The perf improvements are also very
welcome. Some small nits from me.

Thanks

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]

Re: [PATCH] ref-filter: reuse --contains traversal results

[Tamir Duberstein]

On Mon, Jun 8, 2026 at 2:18 PM Karthik Nayak <karthik.188@gmail.com> wrote:
>
> Tamir Duberstein <tamird@gmail.com> writes:
>
> > git branch and git for-each-ref call repo_is_descendant_of() for each
> > candidate selected by --contains or --no-contains. Each call starts a
> > new graph walk, so refs with shared history repeatedly traverse the same
> > commits.
> >
> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced
> > the tag traversal that caches positive and negative answers across
> > candidates. ee2bd06b0f (ref-filter: implement '--contains' option,
> > 2015-07-07) preserved the branch and tag implementations when ref-filter
> > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for
> > the '--contains' option, 2015-10-18) noted that they should be unified.
> >
>
> Nicely explained. We should've merged this long ago, so this is a
> worthwhile change.
>
> > Use the memoized traversal for every ref-filter contains check and
> > remove the implementation selector. The cache records answers for one
> > fixed target list, so document that callers must clear it before
> > changing the list.
> >
> > The memoized depth-first walk assumes acyclic ancestry, but replacement
> > refs can create cycles. Track commits while they are on the walk. If a
> > cycle is found, discard partial cache entries and use
> > repo_is_descendant_of() for that candidate.
> >
> > The branch and for-each-ref path passed repo_is_descendant_of() through
> > a Boolean interface. In configurations where it returned -1 for missing
> > ancestry, ref-filter treated the error as "contains". The memoized path
> > instead fails when ancestry cannot be parsed, as git tag already did.
> > During review of the 2018 reachability series, making parse failures
> > fatal was explicitly deferred because that series was intended to
> > preserve behavior. Unifying the implementations now makes all callers
> > fail consistently instead of preserving that accidental Boolean
> > interpretation.
> >
> > The added p1500 case uses up to 8,192 packed refs along one first-parent
> > history. It improves from 0.68 to 0.03 seconds.
> >
> > On a checkout with 62,174 remote-tracking refs, I ran:
> >
> >     hyperfine --warmup 0 --runs 3 \
> >         --command-name parent \
> >         '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
> >         --command-name this-commit \
> >         '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'
> >
> > The results were:
> >
> >              parent       this commit
> >   elapsed    104.365 s     467.7 ms
> >   user        93.702 s     220.2 ms
> >   system       0.723 s     182.7 ms
> >
> > The wall-time standard deviations were 11.356 seconds and 133.8
> > milliseconds, respectively, for a 223x speedup. Both commands produced
> > output with SHA-256
> > 2466f6e2b72aa16b1a2126eddb81c8a1b2764ee251204ac034c191a925aa896f.
> >
> > Both revisions were rebuilt with the default -O2 flags using Apple clang
> > 21.0.0 on macOS 26.5. The machine was a MacBook Pro (Mac16,6) with a
> > 16-core Apple M4 Max (12 performance and four efficiency cores) and 128
> > GB RAM.
> >
> > Link: https://lore.kernel.org/git/1445163904-24611-1-git-send-email-Karthik.188@gmail.com/
> > Link: https://lore.kernel.org/git/20180723204112.233274-1-jonathantanmy@google.com/
> > Link: https://lore.kernel.org/git/24424e55-7fa8-d05b-bc39-e14b4d5abcb6@gmail.com/
> > Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> > ---
> >  builtin/tag.c                  |  1 -
> >  commit-reach.c                 | 45 +++++++++++++++++++++++++++++++-----------
> >  commit-reach.h                 | 15 ++++++++++----
> >  ref-filter.c                   |  6 ++++--
> >  ref-filter.h                   |  7 +++----
> >  t/helper/test-reach.c          | 10 ++--------
> >  t/perf/p1500-graph-walks.sh    | 24 +++++++++++++++++++++-
> >  t/t6301-for-each-ref-errors.sh | 18 +++++++++++++++++
> >  t/t6302-for-each-ref-filter.sh | 21 ++++++++++++++++++++
> >  t/t6600-test-reach.sh          |  6 ++----
> >  10 files changed, 117 insertions(+), 36 deletions(-)
> >
> > diff --git a/builtin/tag.c b/builtin/tag.c
> > index d51c2e3349..9f34d948d4 100644
> > --- a/builtin/tag.c
> > +++ b/builtin/tag.c
> > @@ -71,7 +71,6 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting,
> >
> >       if (verify_ref_format(format))
> >               die(_("unable to parse format string"));
> > -     filter->with_commit_tag_algo = 1;
>
> We were selectively using the algo for `git tag`, like mentioned I guess
> we'll entirely remove `with_commit_tag_algo` below somewhere
>
> >       filter_and_format_refs(filter, FILTER_REFS_TAGS, sorting, format);
> >
> >       free(to_free);
> > diff --git a/commit-reach.c b/commit-reach.c
> > index 9b3ea46d6f..6e599a3670 100644
> > --- a/commit-reach.c
> > +++ b/commit-reach.c
> > @@ -6,7 +6,6 @@
> >  #include "decorate.h"
> >  #include "hex.h"
> >  #include "prio-queue.h"
> > -#include "ref-filter.h"
> >  #include "revision.h"
> >  #include "tag.h"
> >  #include "commit-reach.h"
> > @@ -708,7 +707,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
> >
> >  /*
> >   * Test whether the candidate is contained in the list.
> > - * Do not recurse to find out, though, but return -1 if inconclusive.
> > + * Do not recurse to find out, though, but return CONTAINS_UNKNOWN if
> > + * inconclusive.
>
> Okay so the code does return CONTAINS_UNKNOWN which is an enum beginning
> at 0, so this makes sense.
>
> >   */
> >  static enum contains_result contains_test(struct commit *candidate,
> >                                         const struct commit_list *want,
> > @@ -743,9 +743,9 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta
> >       contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
> >  }
> >
> > -static enum contains_result contains_tag_algo(struct commit *candidate,
> > -                                           const struct commit_list *want,
> > -                                           struct contains_cache *cache)
> > +static enum contains_result contains_algo(struct commit *candidate,
> > +                                       struct commit_list *want,
> > +                                       struct contains_cache *cache)
> >  {
> >       struct contains_stack contains_stack = { 0, 0, NULL };
> >       enum contains_result result;
> > @@ -765,6 +765,7 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> >       if (result != CONTAINS_UNKNOWN)
> >               return result;
> >
> > +     *contains_cache_at(cache, candidate) = CONTAINS_IN_PROGRESS;
> >       push_to_contains_stack(candidate, &contains_stack);
> >       while (contains_stack.nr) {
> >               struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
> > @@ -776,8 +777,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> >                       contains_stack.nr--;
> >               }
> >               /*
> > -              * If we just popped the stack, parents->item has been marked,
> > -              * therefore contains_test will return a meaningful yes/no.
> > +              * A parent may have just been popped and marked, or may still
> > +              * be active when replacement refs create a cycle.
> >                */
> >               else switch (contains_test(parents->item, want, cache, cutoff)) {
> >               case CONTAINS_YES:
> > @@ -787,21 +788,41 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
> >               case CONTAINS_NO:
> >                       entry->parents = parents->next;
> >                       break;
> > +             case CONTAINS_IN_PROGRESS:
> > +                     /*
> > +                      * Partial negative answers are not safe across a cycle.
> > +                      * Discard them and use the cycle-safe reachability walk.
> > +                      */
> > +                     goto cycle;
> >
>
> If I understand this correctly, we now use CONTAINS_IN_PROGRESS to
> showcase a commit for which we still don't have a result. Since any
> commit with UNKNOWN will start a recursive search through its parents.
>
> So with this if we encounter a CONTAINS_IN_PROGRESS while recursion,
> this would indicate that we hit a cyclic graph and so go to the fallback
> of using repo_is_descendant_of(). So this avoids an infinite recursion
> in such instances. Makes sense.
>
> >               case CONTAINS_UNKNOWN:
> > +                     *contains_cache_at(cache, parents->item) =
> > +                             CONTAINS_IN_PROGRESS;
> >                       push_to_contains_stack(parents->item, &contains_stack);
> >                       break;
> >               }
> >       }
> >       free(contains_stack.contains_stack);
> >       return contains_test(candidate, want, cache, cutoff);
> > +
> > +cycle:
> > +     free(contains_stack.contains_stack);
> > +     clear_contains_cache(cache);
> > +     init_contains_cache(cache);
> > +
> > +     result = repo_is_descendant_of(the_repository, candidate, want);
> > +     if (result < 0)
> > +             exit(128);
> > +     *contains_cache_at(cache, candidate) =
> > +             result ? CONTAINS_YES : CONTAINS_NO;
> > +     return result ? CONTAINS_YES : CONTAINS_NO;
> >  }
> >
> > -int commit_contains(struct ref_filter *filter, struct commit *commit,
> > -                 struct commit_list *list, struct contains_cache *cache)
> > +int commit_contains(struct commit *commit, struct commit_list *list,
> > +                 struct contains_cache *cache)
> >  {
> > -     if (filter->with_commit_tag_algo)
> > -             return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
> > -     return repo_is_descendant_of(the_repository, commit, list);
> > +     if (!list)
> > +             return 1;
> > +     return contains_algo(commit, list, cache) == CONTAINS_YES;
> >  }
> >
> >  int can_all_from_reach_with_flag(struct object_array *from,
> > diff --git a/commit-reach.h b/commit-reach.h
> > index 3f3a563d8a..144dc56275 100644
> > --- a/commit-reach.h
> > +++ b/commit-reach.h
> > @@ -5,7 +5,6 @@
> >  #include "commit-slab.h"
> >
> >  struct commit_list;
> > -struct ref_filter;
> >  struct object_id;
> >  struct object_array;
> >
> > @@ -73,13 +72,21 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
> >  enum contains_result {
> >       CONTAINS_UNKNOWN = 0,
> >       CONTAINS_NO,
> > -     CONTAINS_YES
> > +     CONTAINS_YES,
> > +     CONTAINS_IN_PROGRESS
> >  };
> >
> >  define_commit_slab(contains_cache, enum contains_result);
> >
> > -int commit_contains(struct ref_filter *filter, struct commit *commit,
> > -                 struct commit_list *list, struct contains_cache *cache);
> > +/*
> > + * Return whether "commit" is a descendant of any commit in "list". An empty
> > + * list matches.
> > + *
> > + * "cache" records answers for one fixed "list". Clear it before changing the
> > + * list.
> > + */
> > +int commit_contains(struct commit *commit, struct commit_list *list,
> > +                 struct contains_cache *cache);
> >
> >  /*
> >   * Determine if every commit in 'from' can reach at least one commit
> > diff --git a/ref-filter.c b/ref-filter.c
> > index 1da4c0e60d..7788147959 100644
> > --- a/ref-filter.c
> > +++ b/ref-filter.c
> > @@ -2991,11 +2991,13 @@ static struct ref_array_item *apply_ref_filter(const struct reference *ref,
> >                       return NULL;
> >               /* We perform the filtering for the '--contains' option... */
> >               if (filter->with_commit &&
> > -                 !commit_contains(filter, commit, filter->with_commit, &filter->internal.contains_cache))
> > +                 !commit_contains(commit, filter->with_commit,
> > +                                  &filter->internal.contains_cache))
> >                       return NULL;
> >               /* ...or for the `--no-contains' option */
> >               if (filter->no_commit &&
> > -                 commit_contains(filter, commit, filter->no_commit, &filter->internal.no_contains_cache))
> > +                 commit_contains(commit, filter->no_commit,
> > +                                 &filter->internal.no_contains_cache))
> >                       return NULL;
> >       }
> >
> > diff --git a/ref-filter.h b/ref-filter.h
> > index 120221b47f..9e14afca9c 100644
> > --- a/ref-filter.h
> > +++ b/ref-filter.h
> > @@ -73,10 +73,9 @@ struct ref_filter {
> >       struct commit_list *reachable_from;
> >       struct commit_list *unreachable_from;
> >
> > -     unsigned int with_commit_tag_algo : 1,
> > -             match_as_path : 1,
> > -             ignore_case : 1,
> > -             detached : 1;
> > +     unsigned int match_as_path : 1,
> > +                  ignore_case : 1,
> > +                  detached : 1;
> >       unsigned int kind,
> >               lines;
> >       int abbrev,
>
> Nit: With the changes above. I do wish it was split into two commits.
> 1. Fix cyclic recursions in the algo.
> 2. Use the algo for all filter types.

Makes sense. I split v2 accordingly. The first patch now fixes the
existing git tag --contains traversal and tests that path directly.
The second patch then uses the traversal for the other ref-filter
callers.

>
> > diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
> > index 5d86a96c17..82235f713e 100644
> > --- a/t/helper/test-reach.c
> > +++ b/t/helper/test-reach.c
> > @@ -6,7 +6,6 @@
> >  #include "gettext.h"
> >  #include "hex.h"
> >  #include "object-name.h"
> > -#include "ref-filter.h"
> >  #include "setup.h"
> >  #include "string-list.h"
> >  #include "tag.h"
> > @@ -138,16 +137,11 @@ int cmd__reach(int ac, const char **av)
> >
> >               printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
> >       } else if (!strcmp(av[1], "commit_contains")) {
> > -             struct ref_filter filter = REF_FILTER_INIT;
> >               struct contains_cache cache;
> >               init_contains_cache(&cache);
> >
> > -             if (ac > 2 && !strcmp(av[2], "--tag"))
> > -                     filter.with_commit_tag_algo = 1;
> > -             else
> > -                     filter.with_commit_tag_algo = 0;
> > -
> > -             printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
> > +             printf("%s(_,A,X,_):%d\n", av[1],
> > +                    commit_contains(A, X, &cache));
> >               clear_contains_cache(&cache);
> >       } else if (!strcmp(av[1], "get_reachable_subset")) {
> >               const int reachable_flag = 1;
>
> Makes sense.
>
> > diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
> > index 5b23ce5db9..ac68fdbacd 100755
> > --- a/t/perf/p1500-graph-walks.sh
> > +++ b/t/perf/p1500-graph-walks.sh
> > @@ -5,6 +5,8 @@ test_description='Commit walk performance tests'
> >
> >  test_perf_large_repo
> >
> > +contains_ref_limit=8192
> > +
> >  test_expect_success 'setup' '
> >       git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs &&
> >       sort -r allrefs | head -n 50 >refs &&
> > @@ -32,10 +34,25 @@ test_expect_success 'setup' '
> >               echo "X:$line" >>test-tool-tags || return 1
> >       done &&
> >
> > +     git rev-list --first-parent --max-count=$contains_ref_limit HEAD >contains-commits &&
> > +     contains_ref_count=$(wc -l <contains-commits) &&
> > +     test "$contains_ref_count" -gt 0 &&
> > +     contains_base=$(tail -n 1 contains-commits) &&
> > +     export contains_base &&
> > +     awk "{
> > +             printf \"update refs/contains-perf/%04d %s\\n\", NR, \$1
> > +     }" contains-commits |
> > +             git update-ref --stdin &&
> > +     git pack-refs --include "refs/contains-perf/*" &&
> > +
> >       commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&
> >       git update-ref refs/heads/disjoint-base $commit &&
> >
> > -     git commit-graph write --reachable
> > +     git commit-graph write --reachable &&
> > +
> > +     git for-each-ref --contains="$contains_base" \
> > +             refs/contains-perf/ >actual &&
> > +     test_line_count = $contains_ref_count actual
>
> Shouldn't this be a separate test and not a part of the setup?
>
> >  '
> >
> >  test_perf 'ahead-behind counts: git for-each-ref' '
> > @@ -62,6 +79,11 @@ test_perf 'contains: git tag --merged' '
> >       xargs git tag --merged=HEAD <tags
> >  '
> >
> > +test_perf 'contains: git for-each-ref --contains' '
> > +     git for-each-ref --contains="$contains_base" \
> > +             refs/contains-perf/ >/dev/null
> > +'
> > +
>
> Ah! we also have this, so perhaps moving the `test_line_count` here and
> dropping it above would be better.

Makes sense! Done in v2.

>
> >  test_perf 'is-base check: test-tool reach (refs)' '
> >       test-tool reach get_branch_base_for_tip <test-tool-refs
> >  '
> > diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh
> > index e06feb06e9..169cc70c23 100755
> > --- a/t/t6301-for-each-ref-errors.sh
> > +++ b/t/t6301-for-each-ref-errors.sh
> > @@ -52,6 +52,24 @@ test_expect_success 'Missing objects are reported correctly' '
> >       test_must_be_empty brief-err
> >  '
> >
> > +test_expect_success 'missing ancestors are reported by contains filters' '
> > +     test_when_finished "git update-ref -d refs/heads/missing-parent" &&
> > +     {
> > +             echo "tree $(git rev-parse HEAD^{tree})" &&
> > +             echo "parent $MISSING" &&
> > +             git cat-file commit HEAD |
> > +                     sed -n -e "/^author /p" -e "/^committer /p" &&
> > +             echo &&
> > +             echo "missing parent"
> > +     } > commit &&
> > +     broken=$(git hash-object -t commit -w commit) &&
> > +     git update-ref refs/heads/missing-parent "$broken" &&
> > +     test_must_fail git for-each-ref --contains=HEAD \
> > +             refs/heads/missing-parent >out 2>err &&
> > +     test_must_be_empty out &&
> > +     test_grep "unable to parse commit $MISSING" err
> > +'
> > +
> >  test_expect_success 'ahead-behind requires an argument' '
> >       test_must_fail git for-each-ref \
> >               --format="%(ahead-behind)" 2>err &&
> > diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
> > index 7f060d97bf..423505d1fb 100755
> > --- a/t/t6302-for-each-ref-filter.sh
> > +++ b/t/t6302-for-each-ref-filter.sh
> > @@ -177,6 +177,27 @@ test_expect_success 'filtering with --contains and --no-contains' '
> >       test_cmp expect actual
> >  '
> >
> > +test_expect_success 'contains handles cyclic replacement histories' '
> > +     one=$(git rev-parse one) &&
> > +     three=$(git rev-parse three) &&
> > +     test_when_finished "
> > +             git replace -d $one
> > +             git replace -d $three
> > +             git tag -d cycle-a cycle-b
> > +     " &&
> > +     git tag cycle-a "$one" &&
> > +     git tag cycle-b "$three" &&
> > +     git replace --graft "$one" "$three" two &&
> > +     git replace --graft "$three" "$one" &&
> > +     cat >expect <<-\EOF &&
> > +     refs/tags/cycle-a
> > +     refs/tags/cycle-b
> > +     EOF
> > +     git for-each-ref --format="%(refname)" --contains=two \
> > +             "refs/tags/cycle-*" >actual &&
> > +     test_cmp expect actual
> > +'
> > +
> >  test_expect_success '%(color) must fail' '
> >       test_must_fail git for-each-ref --format="%(color)%(refname)"
> >  '
> > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> > index b5b314e570..1ecc2571c2 100755
> > --- a/t/t6600-test-reach.sh
> > +++ b/t/t6600-test-reach.sh
> > @@ -286,8 +286,7 @@ test_expect_success 'commit_contains:hit' '
> >       X:commit-9-3
> >       EOF
> >       echo "commit_contains(_,A,X,_):1" >expect &&
> > -     test_all_modes commit_contains &&
> > -     test_all_modes commit_contains --tag
> > +     test_all_modes commit_contains
> >  '
> >
> >  test_expect_success 'commit_contains:miss' '
> > @@ -303,8 +302,7 @@ test_expect_success 'commit_contains:miss' '
> >       X:commit-9-3
> >       EOF
> >       echo "commit_contains(_,A,X,_):0" >expect &&
> > -     test_all_modes commit_contains &&
> > -     test_all_modes commit_contains --tag
> > +     test_all_modes commit_contains
> >  '
> >
> >  test_expect_success 'rev-list: basic topo-order' '
> >
> > ---
> > base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
> > change-id: 20260607-ref-filter-memoized-contains-7cb6b3bccad1
> >
> > Best regards,
> > --
> > Tamir Duberstein <tamird@gmail.com>
>
> Overall the patch looks great. The perf improvements are also very
> welcome. Some small nits from me.

Thanks a lot for the review!

Re: [PATCH] ref-filter: reuse --contains traversal results

[Jeff King]

On Sun, Jun 07, 2026 at 08:33:29PM -0700, Tamir Duberstein wrote:

> git branch and git for-each-ref call repo_is_descendant_of() for each
> candidate selected by --contains or --no-contains. Each call starts a
> new graph walk, so refs with shared history repeatedly traverse the same
> commits.
> 
> ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced
> the tag traversal that caches positive and negative answers across
> candidates. ee2bd06b0f (ref-filter: implement '--contains' option,
> 2015-07-07) preserved the branch and tag implementations when ref-filter
> learned --contains. 008ed7df930 (tag.c: use the correct algorithm for
> the '--contains' option, 2015-10-18) noted that they should be unified.
> 
> Use the memoized traversal for every ref-filter contains check and
> remove the implementation selector. The cache records answers for one
> fixed target list, so document that callers must clear it before
> changing the list.

The subject line obfuscated the intent here (at least for me). I think a
more clear subject would just be: "ref-filter: always use
contains_tag_algo" or something.

But more importantly, I think the analysis above is missing a key point
about why we didn't make the tag algo the default in the first place: it
is depth first, and thus slower when the merge base can be found quickly
by the breadth-first traversal. For tags, you tend to have to look at
all of history anyway (because you have at least one old tag that
requires walking back that far), but that is often not true for
branches.

We are able to get the best of both worlds if we can cut off the
depth-first traversal early using generation numbers.

So I think a better rule here is to tweak the selection in
commit_contains() to select the depth-first algorithm when we have
generation numbers enabled. There's a patch in an old thread, which was
revived a week or two ago by Kristofer (cc'd):

  https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/

> The memoized depth-first walk assumes acyclic ancestry, but replacement
> refs can create cycles. Track commits while they are on the walk. If a
> cycle is found, discard partial cache entries and use
> repo_is_descendant_of() for that candidate.

I can believe that the depth-first code doesn't handle cycles well. But
if that's the case, then it's already a problem for "git tag
--contains". And we should fix it as a separate patch from enabling that
algorithm in more cases.

I'm not quite sure how ancestry should be defined in a cycle. How does
the algorithm behave now when it sees a cycle? If it loops infinitely,
we definitely would want to fix that. If not, then to some degree I
don't care too much what answer is provided, since the input is somewhat
nonsense in the first place. And if it is expensive to track, it might
not be worth inflicting that penalty on the sane cases. But it looks
like your solution is just setting an extra flag value in the slab,
which should be pretty cheap.

> The branch and for-each-ref path passed repo_is_descendant_of() through
> a Boolean interface. In configurations where it returned -1 for missing
> ancestry, ref-filter treated the error as "contains". The memoized path
> instead fails when ancestry cannot be parsed, as git tag already did.
> During review of the 2018 reachability series, making parse failures
> fatal was explicitly deferred because that series was intended to
> preserve behavior. Unifying the implementations now makes all callers
> fail consistently instead of preserving that accidental Boolean
> interpretation.

I think that's a good outcome.

> The added p1500 case uses up to 8,192 packed refs along one first-parent
> history. It improves from 0.68 to 0.03 seconds.
> 
> On a checkout with 62,174 remote-tracking refs, I ran:
> 
>     hyperfine --warmup 0 --runs 3 \
>         --command-name parent \
>         '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
>         --command-name this-commit \
>         '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'
> 
> The results were:
> 
>              parent       this commit
>   elapsed    104.365 s     467.7 ms
>   user        93.702 s     220.2 ms
>   system       0.723 s     182.7 ms

I didn't time it, but the probable regression case is something like
this: a very deep history with a small number of branches diverging only
a few commits away. Without a commit-graph file (or one without
generation numbers), that probably makes "git branch --contains" slower.

-Peff

Re: [PATCH] ref-filter: reuse --contains traversal results

[Tamir Duberstein]

On Mon, Jun 8, 2026 at 3:34 PM Jeff King <peff@peff.net> wrote:
>
> On Sun, Jun 07, 2026 at 08:33:29PM -0700, Tamir Duberstein wrote:
>
> > git branch and git for-each-ref call repo_is_descendant_of() for each
> > candidate selected by --contains or --no-contains. Each call starts a
> > new graph walk, so refs with shared history repeatedly traverse the same
> > commits.
> >
> > ffc4b8012d (tag: speed up --contains calculation, 2011-06-11) introduced
> > the tag traversal that caches positive and negative answers across
> > candidates. ee2bd06b0f (ref-filter: implement '--contains' option,
> > 2015-07-07) preserved the branch and tag implementations when ref-filter
> > learned --contains. 008ed7df930 (tag.c: use the correct algorithm for
> > the '--contains' option, 2015-10-18) noted that they should be unified.
> >
> > Use the memoized traversal for every ref-filter contains check and
> > remove the implementation selector. The cache records answers for one
> > fixed target list, so document that callers must clear it before
> > changing the list.
>
> The subject line obfuscated the intent here (at least for me). I think a
> more clear subject would just be: "ref-filter: always use
> contains_tag_algo" or something.

Ack, changed to "ref-filter: memoize --contains with generations" in v2 draft.

>
> But more importantly, I think the analysis above is missing a key point
> about why we didn't make the tag algo the default in the first place: it
> is depth first, and thus slower when the merge base can be found quickly
> by the breadth-first traversal. For tags, you tend to have to look at
> all of history anyway (because you have at least one old tag that
> requires walking back that far), but that is often not true for
> branches.
>
> We are able to get the best of both worlds if we can cut off the
> depth-first traversal early using generation numbers.
>
> So I think a better rule here is to tweak the selection in
> commit_contains() to select the depth-first algorithm when we have
> generation numbers enabled. There's a patch in an old thread, which was
> revived a week or two ago by Kristofer (cc'd):
>
>   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/

Very good catch, thank you. I reproduced the regression with a
100,000-commit history and generation numbers disabled. The parent
took 13.0 ms, the unconditional depth-first version took 238.4 ms, and
the generation-aware version took 9.1 ms.

I didn't find a patch in that thread, so I will reroll using the
memoized walk for tags or when generation numbers are enabled, while
retaining the breadth-first walk otherwise. If someone else would
prefer to send that patch, that is fine by me as well.

>
> > The memoized depth-first walk assumes acyclic ancestry, but replacement
> > refs can create cycles. Track commits while they are on the walk. If a
> > cycle is found, discard partial cache entries and use
> > repo_is_descendant_of() for that candidate.
>
> I can believe that the depth-first code doesn't handle cycles well. But
> if that's the case, then it's already a problem for "git tag
> --contains". And we should fix it as a separate patch from enabling that
> algorithm in more cases.

Agreed, and Karthik flagged the same. The cycle handling is now a
separate first patch.

>
> I'm not quite sure how ancestry should be defined in a cycle. How does
> the algorithm behave now when it sees a cycle? If it loops infinitely,
> we definitely would want to fix that. If not, then to some degree I
> don't care too much what answer is provided, since the input is somewhat
> nonsense in the first place. And if it is expensive to track, it might
> not be worth inflicting that penalty on the sane cases. But it looks
> like your solution is just setting an extra flag value in the slab,
> which should be pretty cheap.
>
> > The branch and for-each-ref path passed repo_is_descendant_of() through
> > a Boolean interface. In configurations where it returned -1 for missing
> > ancestry, ref-filter treated the error as "contains". The memoized path
> > instead fails when ancestry cannot be parsed, as git tag already did.
> > During review of the 2018 reachability series, making parse failures
> > fatal was explicitly deferred because that series was intended to
> > preserve behavior. Unifying the implementations now makes all callers
> > fail consistently instead of preserving that accidental Boolean
> > interpretation.
>
> I think that's a good outcome.
>
> > The added p1500 case uses up to 8,192 packed refs along one first-parent
> > history. It improves from 0.68 to 0.03 seconds.
> >
> > On a checkout with 62,174 remote-tracking refs, I ran:
> >
> >     hyperfine --warmup 0 --runs 3 \
> >         --command-name parent \
> >         '"$parent" branch -r --contains c78ae85f3ce7e >/dev/null' \
> >         --command-name this-commit \
> >         '"$this" branch -r --contains c78ae85f3ce7e >/dev/null'
> >
> > The results were:
> >
> >              parent       this commit
> >   elapsed    104.365 s     467.7 ms
> >   user        93.702 s     220.2 ms
> >   system       0.723 s     182.7 ms
>
> I didn't time it, but the probable regression case is something like
> this: a very deep history with a small number of branches diverging only
> a few commits away. Without a commit-graph file (or one without
> generation numbers), that probably makes "git branch --contains" slower.
>
> -Peff

Re: [PATCH] ref-filter: reuse --contains traversal results

[Jeff King]

On Mon, Jun 08, 2026 at 07:35:57PM -0400, Tamir Duberstein wrote:

> > So I think a better rule here is to tweak the selection in
> > commit_contains() to select the depth-first algorithm when we have
> > generation numbers enabled. There's a patch in an old thread, which was
> > revived a week or two ago by Kristofer (cc'd):
> >
> >   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/
> 
> Very good catch, thank you. I reproduced the regression with a
> 100,000-commit history and generation numbers disabled. The parent
> took 13.0 ms, the unconditional depth-first version took 238.4 ms, and
> the generation-aware version took 9.1 ms.
> 
> I didn't find a patch in that thread, so I will reroll using the
> memoized walk for tags or when generation numbers are enabled, while
> retaining the breadth-first walk otherwise. If someone else would
> prefer to send that patch, that is fine by me as well.

It's just this:

diff --git a/commit-reach.c b/commit-reach.c
index 9b3ea46d6f..cdea0030b8 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -799,7 +799,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 int commit_contains(struct ref_filter *filter, struct commit *commit,
 		    struct commit_list *list, struct contains_cache *cache)
 {
-	if (filter->with_commit_tag_algo)
+	if (filter->with_commit_tag_algo ||
+	    generation_numbers_enabled(the_repository))
 		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
 	return repo_is_descendant_of(the_repository, commit, list);
 }

from:

  https://lore.kernel.org/git/20230324191009.GA536967@coredump.intra.peff.net/

But I won't be surprised if you recreated the identical patch yourself. ;)

-Peff

Re: [PATCH] ref-filter: reuse --contains traversal results

[Tamir Duberstein]

On Mon, Jun 8, 2026 at 4:52 PM Jeff King <peff@peff.net> wrote:
>
> On Mon, Jun 08, 2026 at 07:35:57PM -0400, Tamir Duberstein wrote:
>
> > > So I think a better rule here is to tweak the selection in
> > > commit_contains() to select the depth-first algorithm when we have
> > > generation numbers enabled. There's a patch in an old thread, which was
> > > revived a week or two ago by Kristofer (cc'd):
> > >
> > >   https://lore.kernel.org/git/20260527070510.3510836-1-krka@spotify.com/
> >
> > Very good catch, thank you. I reproduced the regression with a
> > 100,000-commit history and generation numbers disabled. The parent
> > took 13.0 ms, the unconditional depth-first version took 238.4 ms, and
> > the generation-aware version took 9.1 ms.
> >
> > I didn't find a patch in that thread, so I will reroll using the
> > memoized walk for tags or when generation numbers are enabled, while
> > retaining the breadth-first walk otherwise. If someone else would
> > prefer to send that patch, that is fine by me as well.
>
> It's just this:
>
> diff --git a/commit-reach.c b/commit-reach.c
> index 9b3ea46d6f..cdea0030b8 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -799,7 +799,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
>  int commit_contains(struct ref_filter *filter, struct commit *commit,
>                     struct commit_list *list, struct contains_cache *cache)
>  {
> -       if (filter->with_commit_tag_algo)
> +       if (filter->with_commit_tag_algo ||
> +           generation_numbers_enabled(the_repository))
>                 return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
>         return repo_is_descendant_of(the_repository, commit, list);
>  }
>
> from:
>
>   https://lore.kernel.org/git/20230324191009.GA536967@coredump.intra.peff.net/
>
> But I won't be surprised if you recreated the identical patch yourself. ;)

Yep, that's what happened!

>
> -Peff

Thanks again for all the reviews, v2 of all the patches coming shortly.