[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Monotone-devel] Re: Deterministic *-merge
From: |
Timothy Brownawell |
Subject: |
[Monotone-devel] Re: Deterministic *-merge |
Date: |
Fri, 12 Jan 2007 10:35:28 -0600 |
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
- [Monotone-devel] Deterministic *-merge, Nathaniel J. Smith, 2007/01/12
- Re: [Monotone-devel] Deterministic *-merge, Oren Ben-Kiki, 2007/01/12
- [Monotone-devel] Re: Deterministic *-merge,
Timothy Brownawell <=
- [Monotone-devel] Re: Deterministic *-merge, Oren Ben-Kiki, 2007/01/12
- [Monotone-devel] Re: Deterministic *-merge, Timothy Brownawell, 2007/01/12
- [Monotone-devel] Re: Deterministic *-merge, Oren Ben-Kiki, 2007/01/12
- Re: [Monotone-devel] Re: Deterministic *-merge, Nathaniel J. Smith, 2007/01/12
- Re: [Monotone-devel] Re: Deterministic *-merge, Oren Ben-Kiki, 2007/01/13
- [Monotone-devel] Re: Deterministic *-merge, Lapo Luchini, 2007/01/23
Re: [Monotone-devel] Deterministic *-merge, Justin Patrin, 2007/01/12