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. 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) 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) 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) not exist v such that forall n in above value(n) = v Merge into '#' - how does this yield 'c'? Trying a less formal way of thinking about it: Looking at the graph above, if you (informally) think in terms of values, then in both '#1' and '#2' we can see in the history the user preferred the value 'c' over the value 'b'. If we (somehow) worked in term of values rather than nodes, both '#1' and '#2' would become 'c'. Some people would argue that an ideal merge should give this result :-) However we are thinking in term of ancestor nodes instead. In this case, we have no indication that c1 overrides b2 (or c2 overrided b1), so we are forced to merge the node into '#'. That's probably acceptable, given the advantages of the approach. Now we merge the two nodes, we know that c1 overrides b1 and c2 overrides b2. So it makes sense that the result is 'c' (even though this would be surprising to the uninitiated newbie). However, I don't see how the algorithm produces this result. It is tempting to try to improve the algorithm to be more value-oriented. If we culled the minimal marked ancestor set such that there were no duplicate values... Or possibly culled the union of the two merged nodes... If we culled *(b3) to be just (b1), or culled *(c1) union *(b3) to be (c1, b1), then we could merge c1 and b3 to 'c'. Previous attempts in this direction weren't very successful, but perhaps the addition of '#' into the mix makes it possible again? _______________________________________________ Monotone-devel mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel