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

> Hello all,
>
> While working on the commit-graph feature, I made a test commit that sets
> core.commitGraph and gc.commitGraph to true by default AND runs 'git
> commit-graph write --reachable' after each 'git commit' command. This helped
> me find instances in the test suite where the commit-graph feature changes
> existing functionality. Most of these were in regards to grafts,
> replace-objects, and shallow-clones (as expected) or when trying to find a
> corrupt or hidden commit (the commit-graph hides this corrupt/missing data).
> However, there was one interesting case that I'd like to mention on-list.
>
> 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.

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

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

> In the Discussion section of the `git merge-base` docs [1], we have the
> following:
> 
>     When the history involves criss-cross merges, there can be more than one
> best common ancestor for two commits. For example, with this topology:
> 
>     ---1---o---A
>         \ /
>          X
>         / \
>     ---2---o---o---B
> 
>     both 1 and 2 are merge-bases of A and B. Neither one is better than the
> other (both are best merge bases). When the --all option is not given,    
> it is unspecified which best one is output.
> 
> This means our official documentation mentions that we do not have a
> concrete way to differentiate between these choices. This makes me think
> that this change in behavior is not a bug, but it _is_ a change in behavior.
> It's worth mentioning, but I don't think there is any value in making sure
> `git merge-base` returns the same output.
> 
> Does anyone disagree? Is this something we should solidify so we always have
> a "definitive" merge-base?

> Yes, I think this is clearly a case where all of the single merge-bases
> we could show are equally good. And I don't think we should promise to
> show a particular one, but I _do_ think it's friendly for us to have
> deterministic tie-breakers (we certainly don't now).
>
> -Peff

> [...]
> In the Discussion section of the `git merge-base` docs [1], we have the
> following:
> 
>     When the history involves criss-cross merges, there can be more than
> one best common ancestor for two commits. For example, with this topology:
> 
>     ---1---o---A
>         \ /
>          X
>         / \
>     ---2---o---o---B
> 
>     both 1 and 2 are merge-bases of A and B. Neither one is better than
> the other (both are best merge bases). When the --all option is not
> given,     it is unspecified which best one is output.
> 
> This means our official documentation mentions that we do not have a
> concrete way to differentiate between these choices. This makes me think
> that this change in behavior is not a bug, but it _is_ a change in
> behavior. It's worth mentioning, but I don't think there is any value in
> making sure `git merge-base` returns the same output.
> 
> Does anyone disagree? Is this something we should solidify so we always
> have a "definitive" merge-base?
> [...]

> On 05/21/2018 08:10 PM, Derrick Stolee wrote:
>> [...]
>> In the Discussion section of the `git merge-base` docs [1], we have the
>> following:
>>
>>      When the history involves criss-cross merges, there can be more than
>> one best common ancestor for two commits. For example, with this topology:
>>
>>      ---1---o---A
>>          \ /
>>           X
>>          / \
>>      ---2---o---o---B
>>
>>      both 1 and 2 are merge-bases of A and B. Neither one is better than
>> the other (both are best merge bases). When the --all option is not
>> given,     it is unspecified which best one is output.
>>
>> This means our official documentation mentions that we do not have a
>> concrete way to differentiate between these choices. This makes me think
>> that this change in behavior is not a bug, but it _is_ a change in
>> behavior. It's worth mentioning, but I don't think there is any value in
>> making sure `git merge-base` returns the same output.
>>
>> Does anyone disagree? Is this something we should solidify so we always
>> have a "definitive" merge-base?
>> [...]
> This may be beyond the scope of what you are working on, but there are
> significant advantages to selecting a "best" merge base from among the
> candidates. Long ago [1] I proposed that the "best" merge base is the
> merge base candidate that minimizes the number of non-merge commits that
> are in
>
>      git rev-list $candidate..$branch
>
> that are already in master:
>
>      git rev-list $master
>
> (assuming merging branch into master), which is equivalent to choosing
> the merge base that minimizes
>
>      git rev-list --count $candidate..$branch
>
> In fact, this criterion is symmetric if you exchange branch ↔ master,
> which is a nice property, and indeed generalizes pretty simply to
> computing the merge base of more than two commits.
>
> In that email I also included some data showing that the "best" merge
> base almost always results in either the same or a shorter diff than the
> more or less arbitrary algorithm that we currently use. Sometimes the
> difference in diff length is dramatic.
>
> To me it feels like the best *deterministic* merge base would be based
> on the above criterion, maybe with first-parent reachability, commit
> times, and SHA-1s used (in that order) to break ties.

> On 5/22/2018 1:39 AM, Michael Haggerty wrote:
>> On 05/21/2018 08:10 PM, Derrick Stolee wrote:
>>> [...]
>>> In the Discussion section of the `git merge-base` docs [1], we have the
>>> following:
>>>
>>>      When the history involves criss-cross merges, there can be more than
>>> one best common ancestor for two commits. For example, with this topology:
>>>
>>>      ---1---o---A
>>>          \ /
>>>           X
>>>          / \
>>>      ---2---o---o---B
>>>
>>>      both 1 and 2 are merge-bases of A and B. Neither one is better than
>>> the other (both are best merge bases). When the --all option is not
>>> given, it is unspecified which best one is output.
>>>
>>> This means our official documentation mentions that we do not have a
>>> concrete way to differentiate between these choices. This makes me think
>>> that this change in behavior is not a bug, but it _is_ a change in
>>> behavior. It's worth mentioning, but I don't think there is any value in
>>> making sure `git merge-base` returns the same output.
>>>
>>> Does anyone disagree? Is this something we should solidify so we always
>>> have a "definitive" merge-base?
>>> [...]
>> This may be beyond the scope of what you are working on, but there are
>> significant advantages to selecting a "best" merge base from among the
>> candidates. Long ago [1] I proposed that the "best" merge base is the
>> merge base candidate that minimizes the number of non-merge commits that
>> are in
>>
>>      git rev-list $candidate..$branch
>>
>> that are already in master:
>>
>>      git rev-list $master
>>
>> (assuming merging branch into master), which is equivalent to choosing
>> the merge base that minimizes
>>
>>      git rev-list --count $candidate..$branch

>>
>> In that email I also included some data showing that the "best" merge
>> base almost always results in either the same or a shorter diff than the
>> more or less arbitrary algorithm that we currently use. Sometimes the
>> difference in diff length is dramatic.
>>
>> To me it feels like the best *deterministic* merge base would be based
>> on the above criterion, maybe with first-parent reachability, commit
>> times, and SHA-1s used (in that order) to break ties.
>
> Thanks, everyone, for your perspective on this. I'm walking away with
> these conclusions:
>
> 1. While this is a change in behavior, it is not a regression. We do
> not need to act immediately to preserve old behavior in these
> ambiguous cases.
>
> 2. We should (eventually) define tie-breaking conditions. I like
> Michael's suggestion above.

> Derrick Stolee <stolee@gmail.com> writes:
>> On 5/22/2018 1:39 AM, Michael Haggerty wrote:
>>> On 05/21/2018 08:10 PM, Derrick Stolee wrote:
>>>> [...]
>>> This may be beyond the scope of what you are working on, but there are
>>> significant advantages to selecting a "best" merge base from among the
>>> candidates. Long ago [1] I proposed that the "best" merge base is the
>>> merge base candidate that minimizes the number of non-merge commits that
>>> are in
>>>
>>>      git rev-list $candidate..$branch
>>>
>>> that are already in master:
>>>
>>>      git rev-list $master
>>>
>>> (assuming merging branch into master), which is equivalent to choosing
>>> the merge base that minimizes
>>>
>>>      git rev-list --count $candidate..$branch
> 
> Is the above correct...
> 
>>> In fact, this criterion is symmetric if you exchange branch ↔ master,
>>> which is a nice property, and indeed generalizes pretty simply to
>>> computing the merge base of more than two commits.
> 
> ...as it doesn't seem to have the described symmetry.