From: Jeff King <peff@peff.net>
Date: Thu, 16 Jul 2026 09:05:25 GMT
Subject: Re: [PATCH v4 1/3] commit-reach: reject cycles in contains walk
Message-ID: <20260716090525.GA1196203@coredump.intra.peff.net>
In-Reply-To: <20260612-ref-filter-memoized-contains-v4-1-5ed39fd001dd@gmail.com>

On Fri, Jun 12, 2026 at 05:49:12PM -0400, Tamir Duberstein wrote:

> @@ -708,7 +708,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,

This hunk is a good cleanup, but unrelated to the patch at hand.

We used to return a bare -1, then that became CONTAINS_UNKNOWN in
a0262c51d0 (ref-filter: use contains_result enum consistently,
2017-03-09). And then that value changed to 0 in a91aca44bf (ref-filter:
use separate cache for contains_tag_algo, 2017-03-09) when we started
using a slab.

So the code is correct and the comment is wrong, and it is worth
updating. I was just surprised to find it here.

> @@ -765,6 +766,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 +778,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,7 +789,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
>  		case CONTAINS_NO:
>  			entry->parents = parents->next;
>  			break;
> +		case CONTAINS_IN_PROGRESS:
> +			die(_("commit ancestry contains a cycle"));
>  		case CONTAINS_UNKNOWN:
> +			*contains_cache_at(cache, parents->item) =
> +				CONTAINS_IN_PROGRESS;
>  			push_to_contains_stack(parents->item, &contains_stack);
>  			break;
>  		}

Nice, this looks cleanly done.

> +test_expect_success 'tag --contains rejects cyclic replacement histories' '
> +	first=$(git rev-parse HEAD~2) &&
> +	second=$(git rev-parse HEAD~) &&
> +	third=$(git rev-parse HEAD) &&
> +	test_when_finished "
> +		git replace -d $first &&
> +		git replace -d $third &&
> +		git tag -d cycle-a cycle-b
> +	" &&
> +	git tag cycle-a "$first" &&
> +	git tag cycle-b "$third" &&
> +	git replace --graft "$first" "$third" "$second" &&
> +	git replace --graft "$third" "$first" &&
> +	test_must_fail git tag --contains="$second" --list "cycle-*" \
> +		>/dev/null 2>err &&
> +	test_grep "fatal: commit ancestry contains a cycle" err
> +'

Likewise the test looks good.

-Peff