From: Tamir Duberstein Date: Fri, 12 Jun 2026 02:40:18 GMT Subject: Re: [PATCH v2 1/2] commit-reach: handle cycles in contains walk Message-ID: In-Reply-To: <20260611072942.GG2191159@coredump.intra.peff.net> On Thu, Jun 11, 2026 at 12:29 AM Jeff King wrote: > > On Mon, Jun 08, 2026 at 07:36:34PM -0700, Tamir Duberstein wrote: > > > @@ -744,7 +745,7 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta > > } > > > > static enum contains_result contains_tag_algo(struct commit *candidate, > > - const struct commit_list *want, > > + struct commit_list *want, > > struct contains_cache *cache) > > OK, we must lose the const here because repo_is_descendant_of() does not > have it. We could add const to that function, though that cascades down > to a few other helpers (see below). I'm not sure if that is making the > world a better place, or if it is just const pedantry. I left the signature change local rather than propagating const through the other reachability helpers. > > diff --git a/commit-reach.c b/commit-reach.c > index 5df471a313..8cede01f01 100644 > --- a/commit-reach.c > +++ b/commit-reach.c > @@ -563,7 +563,7 @@ int repo_get_merge_bases(struct repository *r, > */ > int repo_is_descendant_of(struct repository *r, > struct commit *commit, > - struct commit_list *with_commit) > + const struct commit_list *with_commit) > { > if (!with_commit) > return 1; > @@ -955,11 +955,12 @@ int can_all_from_reach_with_flag(struct object_array *from, > return result; > } > > -int can_all_from_reach(struct commit_list *from, struct commit_list *to, > +int can_all_from_reach(const struct commit_list *from, > + const struct commit_list *to, > int cutoff_by_min_date) > { > struct object_array from_objs = OBJECT_ARRAY_INIT; > - struct commit_list *from_iter = from, *to_iter = to; > + const struct commit_list *from_iter = from, *to_iter = to; > int result; > timestamp_t min_commit_date = cutoff_by_min_date ? from->item->date : 0; > timestamp_t min_generation = GENERATION_NUMBER_INFINITY; > diff --git a/commit-reach.h b/commit-reach.h > index 3f3a563d8a..76e82f827e 100644 > --- a/commit-reach.h > +++ b/commit-reach.h > @@ -37,7 +37,7 @@ int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result) > > int repo_is_descendant_of(struct repository *r, > struct commit *commit, > - struct commit_list *with_commit); > + const struct commit_list *with_commit); > int repo_in_merge_bases(struct repository *r, > struct commit *commit, > struct commit *reference); > @@ -93,7 +93,8 @@ int can_all_from_reach_with_flag(struct object_array *from, > unsigned int assign_flag, > timestamp_t min_commit_date, > timestamp_t min_generation); > -int can_all_from_reach(struct commit_list *from, struct commit_list *to, > +int can_all_from_reach(const struct commit_list *from, > + const struct commit_list *to, > int commit_date_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); > > We are feeding the whole initial "want" list, so we should get a correct > answer regardless of how far we got into the cycle, which would run into > problems (e.g., if the cycle existed only on some branch of the > history). But going back to the initial list will always be correct. > Good. > > Two small points, though. > > One, the call to init_contains_cache() is redundant here; the clear > function is documented as making things ready for use (it's a little > hard to grep for, due to macros, but the docs are in commit-slab.h). > It's probably not hurting anything. > > Two, the call to exit(128) is unusual for our code base (I'd guess it > was cribbed off of the top-level exits in builtin/pull.c). We'd usually > die() instead. Even if repo_is_descendant_of() produced its own error > message, it may be useful to mention that we were falling back to it due > to a cycle. I removed the redundant initialization and replaced exit(128) with die(), adding context that the failure occurred after detecting a cycle. > > But even better is if we can return the error up the stack. We do not > return errors from contains_tag_algo() currently, but it has only one > caller. And that caller may also directly return the result of > repo_is_descendant_of(). So could we just pass that along? > > Perhaps not. Looking at the callers of commit_contains(), they treat the > result as a pure boolean. So probably calling die() is reasonable, and > we already do so via parse_commit_or_die() elsewhere in the algorithm. > That does leave a potential lurking bug for the non-tag-algo code path. I traced the callers. Returning an error from commit_contains() would only move the fatal check into apply_ref_filter(): its NULL return already means “filtered out”, filter_and_format_refs() returns void, and the branch caller ignores filter_refs()'s return value. Propagating the error to the command would require changing that whole chain, and none of the commands can recover from an unreadable commit. The series therefore makes both cases fail explicitly. Patch 1 calls die() if the cycle fallback cannot read the ancestry. Patch 3 calls die() when the ordinary non-memoized walk returns -1. > > > + *contains_cache_at(cache, candidate) = > > + result ? CONTAINS_YES : CONTAINS_NO; > > + return result ? CONTAINS_YES : CONTAINS_NO; > > So we actually cache our discovered value. Cute, and it might save us > from hitting the cycle again, though not always. E.g., two candidates A > and B share a parent P, and the cycle starts at P but does not include A > or B. We discover the cycle and cache the value for A, but discover it > again for B. > > We do lose all of the existing non-cycle cached values when we call > clear_contains_cache(). But we have to at least clear out all of the > IN_PROGRESS commits. It is hard to care too much about optimizing the > outcome for this case which we expect to happen approximately never. > So I think doing the simplest correct thing is OK. > > > +test_expect_success 'tag --contains handles 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 > > + " && > > We usually &&-chain the commands inside test_when_finished. If they > fail, the test harness will note this and complain (if the test was not > otherwise failing). It's usually not a big deal either way, though > sometimes it can catch silly mistakes (e.g., if you wrote $second > instead of $third and the "replace -d" is quietly doing nothing at all). Fixed in v3. > > I'm a little surprised that the chainlint checker doesn't catch this, > but I guess it doesn't know to recurse into the snippet handed to > test_when_finished. It probably is not really worth the trouble to teach > it to do so. > > Otherwise the test looks good to me. > > -Peff