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 mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel