Re: [PATCH v2 1/2] commit-reach: handle cycles in contains walk

>
> 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.

>
> 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.

>
> 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.

>
> > +     *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).

>
> 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