[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 12:57:29 -0600 |
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
- [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, 2007/01/12
- [Monotone-devel] Re: 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
- 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
Re: [Monotone-devel] Deterministic *-merge, Florian Weimer, 2007/01/12