[Monotone-devel] Re: Deterministic *-merge

[Timothy Brownawell]

On Fri, 2007-01-12 at 08:02 -0800, Oren Ben-Kiki wrote:
> On Fri, 2007-01-12 at 03:00 -0800, Nathaniel J. Smith wrote:
> > ...
> >
> > Deterministic merging
> > =====================
> 
> Beautiful! There's just one point I didn't follow, though.
> 
> > But, magically, with deterministic *-merge, all orders work the same
> > -- it even turns out to be possible to merge two conflicts and get out
> > a non-conflict (!):
> > 
> >       a             a             a
> >      / \           / \           / \
> >     b*  b*        b*  b*        b*  b*
> >    / \ / \       / \ / \       / \ / \
> >   c*  b   c*    c*  b   c*    c*  b   c*
> >    \ /   /       \   \ /       \ / \ /
> >     #   /         \   #         #   #
> >      \ /           \ /           \ /
> >       c             c             c
> 
> You lost me here. In the '#' node, you lost the specific values 'b' and
> 'c' - all you have is 'some unknown value'. How does merging two
> 'unknown values' produce a specific value?

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
.

*(#1) is {c1, b2}. This has multiple values, and gives a conflict node.
*(#2) is {b1, c2}. This also has multiple values.
*(c3) is erase_ancestors(*(#1) union *(#2)), which is {c1, c2}.
Since all of *(c3) have value 'c', c3 is also given value 'c'.

> I like the idea of not using the generic '#' and instead listing the set
> of candidate values. 

The '#' effectively already has a set of candidate values, which are the
values of *(node). Including that detail in the value of # is merely an
optimization to avoid having to inspect the members of *(node).

> This can be done in text files by some
> not-so-pretty syntax tricks. Speaking of which, how did you envision
> representing '#' in actual text files?

He probably didn't; this algorithm is designed for scalar merging, not
text merging. Not that it couldn't be used as a starting point to build
a text merger... :)

If you did use this as a base for a text merging algorithm I'd think
you'd just provide the user with all the values of *(node), either
through normal in-line conflict markers or some fancy next-gen UI.

> If the result of a conflict was replacing a scalar with a set of
> conflicting values, we'd get a user action (creating a separate node)
> that would pick one or replace the set by a new one. It seems like this
> would be very useful when users need to resolve conflicts in practice...

Therefore most implementations will probably provide the user with the
values of *(node) when presenting a conflict. ;-)

> At first I thought that was how you obtained 'c' above, but it turns out
> not to be the case:
> 
>       a             a             a
>      / \           / \           / \
>     b*  b*        b*  b*        b*  b*
>    / \ / \       / \ / \       / \ / \
>   c*  b   c*    c*  b   c*    c*  b   c*
>    \ /   /       \   \ /       \ / \ /
>   {b,c} /         \ {b,c}     {b,c}{b,c}
>      \ /           \ /           \ /
>       c             c           {b,c}
> 
> So I'm still stumped on how you obtained 'c' in all three cases. I must have 
> missed some important point here...

It's from the "minimal" in the definition of *(node). When calculating
*(final-node), both 'b' elements are ancestors of another element and
therefore aren't part of the mark set.

-- 
Timothy

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