[Monotone-devel] Re: Deterministic *-merge

[Timothy Brownawell]

On Fri, 2007-01-12 at 10:36 -0800, Oren Ben-Kiki wrote:
> 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.

What you're missing is the "minimal" part of the definition of *(node).
You don't just union the mark sets of the parent nodes, you take that
union and then run erase_ancestors() on 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)

Should be
      erase_ancestors(*(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)

Should be
       erase_ancestors(*(c1) union *(b3)) = (c1, 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)

Should be
    erase_ancestors(*(#1) union *(#2)) = (c1, c2)

>   not exist v such that forall n in above value(n) = v

Should be
    exist v (= 'c') such that forall n in above, value(n) = v
, because of the erase_ancestors().

>   Merge into '#' - how does this yield 'c'?

    Merge into 'c'.

-- 
Timothy

Free (experimental) public monotone hosting: http://mtn-host.prjek.net