[Monotone-devel] Re: Deterministic *-merge

[Oren Ben-Kiki]

On Fri, 2007-01-12 at 10:35 -0600, Timothy Brownawell wrote:
> Because the value of a merge node is chosen from *(node).
> 
> The multi-*-merge writup at
> http://article.gmane.org/gmane.comp.version-control.revctrl/93
> says that *(A) is the minimal set of marked ancestors of A.
> 
> Adding labels to the individual nodes produces
>       a1
>      / \
>    b1*  b2*
>   /  \ /  \
> c1*   b3   c2*
>   \  / \  /
>    #1   #2
>     \  /
>      c3

The article states:
  Algorithm: Given two nodes to merge, A and B, we consider four cases:
   a) value(A) = value(B): return the shared value
   b) *(A) > B: return value(B)
   c) *(B) > A: return value(A)
   d) else: conflict; escalate to user
  Where "*(A) > B" means "all elements of the set *(A) are non-strict
  ancestors of the revision B".  The right way to read this is as "try
  (a) first, and then if that fails try (b), (c), (d) simultaneously".

The post said:
  This is already obviously true for non-merge nodes.  We want it to be
  true for merge nodes too.  The easy way is to simply use it as the
  definition of merge(A, B).  If every node in *(A) union *(B) has the
  same value, then cool -- we can just make merge(A, B) that value.  If
  there are different values, then we have only one option -- we must
  define merge(A, B) to be #, because # is the only thing that is
  similar to multiple different values.

I'm still missing it. Just to see I get the algorithms right (sorry for
being dense):

  Old way:
    value(b1) = value(b2)
    By (a), merge into b3

  New way:
    *(b1) union *(b2) = (b1, b2)
    exist v (= 'b') such that forall n in above, value(n) = v
    Merge into b3

  Old way:
    value(c1) != value(b3)
    *(c1) = c1
    *(b3) = (b1, b2)
    Not *(b3) > c
    Not *(c1) > b3
    Conflict.

  New way:
    *(c1) = c1
    *(b3) = (b1, b2)
    *(c1) union *(b3) = (c1, b1, b2)
    not exist v such that forall n in above value(n) = v
    Merge into '#'

So far, so good. But:
  *(#1) = (c1, b2)
  *(#2) = (c2, b1)
  *(#1) union *(#2) = (c1, b2, c2, b1)
  not exist v such that forall n in above value(n) = v
  Merge into '#' - how does this yield 'c'?

Trying a less formal way of thinking about it:

Looking at the graph above, if you (informally) think in terms of
values, then in both '#1' and '#2' we can see in the history the user
preferred the value 'c' over the value 'b'. If we (somehow) worked in
term of values rather than nodes, both '#1' and '#2' would become 'c'.
Some people would argue that an ideal merge should give this result :-)

However we are thinking in term of ancestor nodes instead. In this case,
we have no indication that c1 overrides b2 (or c2 overrided b1), so we
are forced to merge the node into '#'. That's probably acceptable, given
the advantages of the approach.

Now we merge the two nodes, we know that c1 overrides b1 and c2
overrides b2. So it makes sense that the result is 'c' (even though this
would be surprising to the uninitiated newbie). However, I don't see how
the algorithm produces this result.

It is tempting to try to improve the algorithm to be more
value-oriented. If we culled the minimal marked ancestor set such that
there were no duplicate values... Or possibly culled the union of the
two merged nodes... If we culled *(b3) to be just (b1), or culled *(c1)
union *(b3) to be (c1, b1), then we could merge c1 and b3 to 'c'.
Previous attempts in this direction weren't very successful, but perhaps
the addition of '#' into the mix makes it possible again?