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

On Mon, May 21, 2018 at 2:50 PM, Jeff King [off-list ref] wrote:

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

quoted

quoted

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?

The hash sounds reasonable as the definite tie breaker.

git merge-base is documented as "Find as good common ancestors
as possible for a merge", so in case we do not require the tie
breaking to be cheap, we could go by "smallest diff output"
of the two diffs against the potential merge commit.

Though I don't think this is really optimal for performance reasons.