More merge base discussion [was: monotone's LCA+DOM algo for selecting a merge base]

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Denys Duchier wrote:
| Aaron asked about monotone's LCA+DOM algo for selecting a merge base.
  I know
| essentially squat about monotone, but his question made think about
why their
| selection algorithm might be correct.  In this email, I'd like to
write up what
| I have thought of so far and offer it up for criticism and corrections.

Thank you, Denys.  I'd originally hoped we could start with
least-common-dominator (LCD) as our merge base selection algorithm, so I
was putting off thinking about LCA+DOM.

I now believe that that least-common-dominator is not suitable, so I'll
be taking a stab at LCA+DOM.

I believe that LCD is unsuitable because of this scenario:

~ A
~ |\
~ B C
~ |\|
~ D E

If we attempt to select a merge base for D and E, LCD will use A.  But
it's obvious that B is the best choice.  (Selecting a worse base will
produce more spurious conflicts.)

Because E descends from C, B doesn't dominate it, even though it
dominates D.

Since B is a dominator (though not a common one), LCA+DOM would pick it.

Say we have a criss-cross:

A
|\
B C
|X|
D E

Now LCA+DOM will select A, which is proper.  There will be more merge
conflicts, but they won't be spurious, because they reflect
disagreements between the A-B-D line and the A-C-E line.

So here are the things I'm looking at:
1. Does "is a dominator" reliably test for criss-cross?  Does it depend
on LCA?

I do not have much graph theory knowledge, so help here would be
appreciated.

2. Is LCA appropriate?
Certainly the last time we looked at it, we believed that it was not.
The problem is that the least common ancestor may be very old:

~  A
~  |\
~  B C
~  | |
~  E |
~  | |
~  F |
~  |\ \
~  G H \
~  |  X |
~  | / \|
~  I    J

Err, you my pefer this version:
http://aaronbentley.com/pastegraph.cgi?n=130

Of course, in this scenario, C is not a dominator, so maybe we're okay.
~ If we're certain that shortcuts like this one can never cause old bases
to be selected, LCA+DOM may still be a good idea.

| The gist of the problem is that, whenever you merge, you may need to
resolve a
| conflict by choosing one of a pair of conflicting hunks.  However, it
is clear
| that choosing is NOT making a change.

Actually, I tend to think of merging as a machine-assisted edit, so I do
think of these as changes.  But let's ignore that.

| When I pick a merge base, I should not
| pick a revision such that in one history it appears unchanged because
I always
| choose the same hunk when resolving while in the other it appears new
because I
| chose another hunk.

Right.  Both the THIS hunk and the OTHER hunk should differ from BASE,
to give the person doing the merge the "opportunity" to resolve the
conflict.

| Instead, it might be better to pick a base that dominates the origins
of both
| hunks.

I am not sure I follow this part.  The first part of my email shows why
it is fine to use a base that does not dominate both versions of the text.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFD9+Lb0F+nu1YWqI0RAq6XAJ9lYFWK8di1/cYbrsOLz5nd1MC+5QCfSPEt
d9cTnRkqNKwyJ7t5s9G/bC0=
=ZUVz
-----END PGP SIGNATURE-----