Optimal Merge Base selection

[John Arbash Meinel]

I've been thinking about how to select the merge base, and I think I'm
realizing that it really doesn't matter all that much. Because if I
cherrypick a change from someone else, that change will be in the text,
and when I use diff3 or merge3.Merge3() if someone else did the
cherrypick, then it will show up in both, and diff3 won't change
anything. So with something like this layout:

Me:    A - B - C - D - E - F
#      |             /   /
Other: + - G - - - -    /
#      |     \        /
You:   + - H - I - - /

In this case, G is probably not as good of a merge base as A, but
breadth-first-search would use G (to merge I into F).

So I was thinking, what about using depth-first search along the
revision-history of each branch, compared to the complete tree of the
other branch.

So the history for "Me" is A-F, the history for "You" is A,H,I, which
means that A is our common ancestor.

Another situation is something like this:

Me:    A - B - C - D - E - F
#      |             /   /
Other: + - G - - - -   /
#          |         /
You:       + - H - I

In this case, G probably is the optimal merge, but it is in the
revision-history of "You".

This change would mean trees with no real common ancestry, which only
merged from a common group would not find their commonality. I mean
something like this:

Me:    A - B - C - D - E - F
#            /           /
Other: G - H           /
#            \       /
You:   J - K - L - M

In this case, it would not find H as a merge base, since it is not along
the main line of development for either tree.
Though how 'H' got merged in, considering it doesn't share history, is
left as an exercise for the user. Say somehow Me and You both merged a
library (Other) into our main program. And then You update the library,
and I want to merge your changes. In arch this could be done with a "baz
replay M", which would even ignore any changes in M that did not effect
shared code. I don't really know what "baz merge" would do. And now that
it is after 1am, I can't think what it should do.

John
=:->