Re: [PATCH v4 1/3] commit-reach: reject cycles in contains walk
- From
Jeff King <peff@peff.net>
- Date
- Jul 16, 2026, 09:05 UTC
- 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:
Show 10 quoted lines
> @@ -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.
Show 31 quoted lines
> @@ -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.
Show 17 quoted lines
> +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