Re: [Monotone-devel] Re: [Revctrl] improvements to *-merge
On Friday 02 September 2005 21:48, Bram Cohen wrote: First of all though, there's a point I have to get out of the way. Just how does one pronounce 'precise-*-merge'? Star-merge is already taken as a term, and asterisk-merge just doesn't roll off the tongue in quite the same way. Precis(e)tar-r-merge? :-) This approach is entirely based on values, not graph node There's a subtlety involved: a1 / \ d1 b1 \ / \ b? c1 b? would have been a conflict, resolved in favor of b. So the rule is: In case of a conflict resolved for one of the values, you keep the winner's generational number. On the other hand, a1 / \ b1 a1 \ / a2? Here there would have been a clean merge to b1, overridden for a, so the rule is: In case a clean merge is overridden for the losing value, you increment the generation number. It sounds like a potential divergence between the programmer's intent and the algorithm's interpretation. It does seem to work however... Any rationale? Then there's implicit undo :-) The whole approach philosophically opposes implicit undo, since the undone generation number _must_ be higher than the original, causing conflicts. I really don't see how you could even approach trying to make implicit undo work... Have fun, Oren Ben-Kiki ___ Monotone-devel mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel
[Monotone-devel] Re: [Revctrl] improvements to *-merge
Okay, I've read over this and thought about it, and have figured out how to give it proper convergence. First of all though, there's a point I have to get out of the way. Just how does one pronounce 'precise-*-merge'? Star-merge is already taken as a term, and asterisk-merge just doesn't roll off the tongue in quite the same way. This approach is entirely based on values, not graph node relationships. Values are obviously the normal a, b, c, etc. but they also have implicit generation numbers, b1, b2, b3, etc. The usual generational number of any value is 1. If a b1 has ever appeared and been overwritten anywhere in the history, then if the value is set to b the implicit generational number is b2, unless b2 has already been done away with, in which case it's b3, unless it needs to be b4, etc. Here's the simplest example: a1 | b1 | a2 | b2 Nothing to merge in the above, just demonstrating how generation numbers work. Here's the case which keeps tripping up *-merge, which I'd like to calle the 'staircase' case, since Nathaniel asked for a name for it: a1 / \ d1 b1 \ / \ b1 c1 In this case b1 has already been done away with (specifically, by c1, but which one immediately followed on doesn't matter) so c1 wins. a1 / \ | b1 | | b1 a2 b1 has already been beaten, so a2 wins. Note that a1 was beaten, but a2 has not been, so a2 is still permitted to win. a1 / \ b1 c1 | \ / | | X | | / \ | b1 c1 b1 and c1 have both been beaten (or, viewed alternatively, each one has beaten the other) so both sides lose, which is presented to the user as a conflict. b1 b2 \ / ? In this case b2 wins, because by definition of when b2 appears b1 must already have been defeated. a1 / \ b1 b1 | \ / | a2 X a2 | / \ | |/ \| b2b2 Obviously b2 wins this one. a1 / \ b1 a1 \ / a2 Nothing to merge here, just wanted to point out that this must have been presented to the user as a clean resolve to b, and even though one of the ancestors is the same as the descendant it's still a different generation number. a1 / \ b1 | | | a2 c1 Neither a2 nor c1 has been beaten, so this is a conflict. I still haven't worked out a way of adding implicit undo to this approach. I suspect that there's an algorithm for recognizing situations like this one and resolving them automatically, in a conservative way which only affects conflict cases and only automatically resolves them when there's a clear right answer. I'm generally very happy with this algorithm. I think that with the addition of implicit undo it may really be the uber-merge algorithm for scalars, and even without implicit undo it's pretty darn close. -Bram ___ Monotone-devel mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel
[Monotone-devel] Re: [Revctrl] improvements to *-merge
On Tue, Aug 30, 2005 at 02:21:18AM -0700, Nathaniel Smith wrote: Corollary 1: If *(A) B, and any element R of *(B) is R A, then value(A) = value(B). [...] The nastiest case of this is where *(A) B, but some elements of *(B) are A -- so we silently make B win, but it's really not _quite_ clear that's a good idea, since A also beat B sometimes -- and we're ignoring those user's intentions. This is the nice thing about Corollary 1 (and why I didn't just collapse it into Corollary 2) -- it assures us that the only time this _weak_ form of ambiguous clean can happen is when A and B are already identical. It occurs to me belatedly that there are actually even more complexities here than I realized. In particular, we need Corollary 1 to show that in the (v) case: a b1 \ / b2 with b2 unmarked, then *(b2) = *(b1). It's in principle possible that *(b2) is merely a subset of *(b1), in case some element of *(a) masked out an element of *(b1). That would be bad, if we were dropping intentions on the floor... OTOH, if that happened, then that element of *(a) would also be an element of *(b2), so perhaps the proof of Corollary 1 is overcomplex, and we could have just used the theorem that said all elements of *(b2) have value b. I also noticed something interesting, in this regard. One of the biggest differences between the *-merges and the codeville-merges they came from is that in codeville merge, each node has associated with it one or more source revisions, analogous to *(A). The difference is that in codeville merge, you have to write these down for each node, or else do some content-sensitive annotation-like traversal of the graph; there isn't the same sense that *'s are things associated with particular _ancestor_ nodes, and *() just reads off the nearest one(s) from the graph topology. I'd been thinking of this as a *-merge advantage mainly because it's what makes the analysis of *-merge so tractable. On further reflection, I think it is actually a theoretical advantage as well. Inasmuch as we are modeling user intentions, there is something wrong the the idea that an intention could be expressed at one point in the graph, and then later on the value changes to something else -- but without any intervening intention being expressed! For example, the classic: a / \ b1* c1* |\ /| | X | |/ \| b2 c2 b2 is a child of c1, yet there is no record of any intention that overrode the c1 intention to explain how the value changed from c1 to b2. So now I think that the particular way *-merge uses graph topology is in some ways a design feature, not just a convenient fact. -- Nathaniel -- - Don't let your informants burn anything. - Don't grow old. - Be good grad students. -- advice of Murray B. Emeneau on the occasion of his 100th birthday ___ Monotone-devel mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel
