Re: commit-graph: change in "best" merge-base when ambiguous

[Jeff King <peff@peff.net>]

On Mon, May 21, 2018 at 11:33:11AM -0700, Elijah Newren wrote:

> > In t6024-recursive-merge.sh, we have the following commit structure:
> >
> >     # 1 - A - D - F
> >     #   \   X   /
> >     #     B   X
> >     #       X   \
> >     # 2 - C - E - G
> >
> > When merging F to G, there are two "best" merge-bases, A and C. With
> > core.commitGraph=false, 'git merge-base F G' returns A, while it returns C
> > when core.commitGraph=true. This is due to the new walk order when using
> > generation numbers, although I have not dug deep into the code to point out
> > exactly where the choice between A and C is made. Likely it's just whatever
> > order they are inserted into a list.
>
> Ooh, interesting.
> 
> Just a guess, but could it be related to relative ordering of
> committer timestamps?  Ordering of committer timestamps apparently
> affects order of merge-bases returned to merge-recursive, and although
> that shouldn't have mattered, a few bugs meant that it did and the
> order ended up determining what contents a successful merge would
> have.  See this recent post:
> 
> https://public-inbox.org/git/CABPp-BFc1OLYKzS5rauOehvEugPc0oGMJp-NMEAmVMW7QR=4Eg@mail.gmail.com/
> 
> The fact that the merge was successful for both orderings of merge
> bases was the real bug, though; it should have detected and reported a
> conflict both ways.

Traditionally we've inserted commits into the walk queue in commit-date
ordering, but with identical dates it may depend on the order in which
you reach the commits. Many of the tests are particularly bad for
showing this off because they do not use test_tick, and so you end up
with a bunch of commits with identical timestamps.

If we're just using generation numbers for queue ordering, we're even
more likely to hit these cases, since they're expected to increase along
parallel branches at roughly the same rate. It's probably a good idea to
have some tie-breakers to make things more deterministic (walk order
shouldn't matter, but it can be confusing if we sometimes use one order
and sometimes the other).

Even ordering by {generation, timestamp} isn't quite enough, since you
could still tie there. Perhaps {generation, timestamp, hash} would be a
sensible ordering?

As for this specific case, even with the current code asking for `git
merge-base G F` will return the other answer. This is clearly a case
with multiple merge bases, and I'd expect "merge-base --all" to return
both (and actually it shows "B" as well, which makes sense). In the
non-all case, there is no "best", so we're free to show any.

-Peff