From: James Cook <falsifian@falsifian.org>
Subject: Re: [patch] simplify ancestry checks
To: gameoftrees@openbsd.org
Date: Wed, 24 May 2023 22:28:24 +0000

On Wed, May 24, 2023 at 05:58:20PM +0200, Stefan Sperling wrote:
> On Sun, May 21, 2023 at 03:09:33AM +0000, James Cook wrote:
> > As far as I can tell, the below patch doesn't change any behaviour
> > except maybe to save a bit of time.
> >
> > I added a comment to got_commit_graph_find_youngest_ancestor mostly to
> > make it easier to verify that yca_id can't be NULL when the new line
> > 11313 is reached.
> >
> > The calls to check_same_branch that I replaced were equivalent to just
> > checking whether one commit was the youngest common ancestor of both. It
> > is complicated a bit by whether non-linear ancestors were considered,
> > i.e. the first_parent_traversal argument to
> > got_commit_graph_find_youngest_common_ancestor, but I believe it all
> > works out:
> >
> > - The check in cmd_rebase only considers linear history, before and
> >   after this change.
> >
> > - The check in cmd_merge considers full history, both before and after
> >   this change. (The reason it considered full history before this change
> >   is that one of the first things check_same_branch did was to compare
> >   commit_id to yca_id, and yca_id was based on full history.)
> >
> > I was working on making "got merge" fast-forward when possible as
> > discussed in the other thread when I noticed this apparently unneeded
> > complexity. If this change is correct, I think it makes sense to do it
> > first as a separate change, because it's already tricky enough to reason
> > about on its own.
> 
> Indeed. After reading over this diff for a while with plenty of context lines
> added, I have to agree with this simplification. Thanks for pointing it out.

Thanks for taking a look!

> Just one question about terminology, not a technical question:
> 
> > +/*
> > + * Sets *yca_id to the last commit that can be reached from both commit_id and
> > + * commit_id2. Returns got_error(GOT_ERR_ANCESTRY) if there are none.
> 
> The above wording is a bit misleading.
> 
> The term "last commit" is not defined in Got's or Git's vocabulary.
> It is unclear which commit this refers to. I would suggest to use the phrase
> "youngest common ancestor commit" (even though it is already in the name of
> the function). This phrase seems self-explanatory to me.
> Do you agree or do you have another suggestion?

Sure, or just "youngest common ancestor". I wasn't being careful about
terminology.

(The first time I read "youngest" in the got code, I was afraid things
were being compared by timestamp. But I don't think that's a serious
problem with the word.)

> And should it not say "if there is none" rather than "if there are none"?
> I cannot think of a case where multiple YCA commits would exist. Unless
> perhaps if merge-commits were excluded from the set of possible YCAs which
> would leave their parent commits as a set of YCAs... ?
> Maybe I am missing something?

I meant "if there are no commits that can be reached from both commit_id
and commit_id2".

How about...

/*
 * Sets *yca_id to the youngest common ancestor of commit_id and
 * commit_id2. Returns got_error(GOT_ERR_ANCESTRY) if they have no
 * common ancestors.
 *
 * If first_parent_traversal is nonzero, only linear history is considered.
 */

> > + *
> > + * If first_parent_traversal is nonzero, only linear history is considered.
> > + */
> >  const struct got_error *
> >  got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
> >      struct got_object_id *commit_id, struct got_object_id *commit_id2,
> >
> >
> 

-- 
James