[Monotone-devel] Re: [Revctrl] improvements to *-merge

[Bram Cohen]

Okay, I've read over this and thought about it, and have figured out how
to give it proper convergence.

First of all though, there's a point I have to get out of the way. Just
how does one pronounce 'precise-*-merge'? Star-merge is already taken as a
term, and asterisk-merge just doesn't roll off the tongue in quite the
same way.

This approach is entirely based on values, not graph node relationships.
Values are obviously the normal a, b, c, etc. but they also have implicit
generation numbers, b1, b2, b3, etc. The usual generational number of any
value is 1. If a b1 has ever appeared and been overwritten anywhere in the
history, then if the value is set to b the implicit generational number is
b2, unless b2 has already been done away with, in which case it's b3,
unless it needs to be b4, etc.

Here's the simplest example:

 a1
 |
 b1
 |
 a2
 |
 b2

Nothing to merge in the above, just demonstrating how generation numbers
work.

Here's the case which keeps tripping up *-merge, which I'd like to calle
the 'staircase' case, since Nathaniel asked for a name for it:

    a1
   / \
  d1  b1
   \ / \
    b1  c1

In this case b1 has already been done away with (specifically, by c1, but
which one immediately followed on doesn't matter) so c1 wins.

     a1
    / \
    |  b1
    |  |
   b1  a2

b1 has already been beaten, so a2 wins. Note that a1 was beaten, but a2
has not been, so a2 is still permitted to win.


          a1
         /  \
        b1   c1
        | \ / |
        |  X  |
        | / \ |
        b1   c1

b1 and c1 have both been beaten (or, viewed alternatively, each one has
beaten the other) so both sides lose, which is presented to the user as a
conflict.

  b1  b2
   \ /
    ?

In this case b2 wins, because by definition of when b2 appears b1 must
already have been defeated.


      a1
     /  \
    b1   b1
    | \ / |
   a2  X  a2
    | / \ |
    |/   \|
    b2    b2

Obviously b2 wins this one.


      a1
     /  \
    b1   a1
     \  /
      a2

Nothing to merge here, just wanted to point out that this must have been
presented to the user as a clean resolve to b, and even though one of the
ancestors is the same as the descendant it's still a different generation
number.


           a1
          /  \
         b1  |
         |   |
         a2  c1

Neither a2 nor c1 has been beaten, so this is a conflict. I still haven't
worked out a way of adding implicit undo to this approach. I suspect that
there's an algorithm for recognizing situations like this one and
resolving them automatically, in a conservative way which only affects
conflict cases and only automatically resolves them when there's a clear
right answer.


I'm generally very happy with this algorithm. I think that with the
addition of implicit undo it may really be the uber-merge algorithm for
scalars, and even without implicit undo it's pretty darn close.

-Bram