Subject: 3-way merge considered harmful (was Re: merge weirdness...)
Newsgroups: gmane.comp.version-control.monotone.devel
Date: 2005-05-01 07:29:48 GMT (3 years, 2 weeks, 2 days, 15 hours and 27 minutes ago)
On Wed, Apr 27, 2005 at 03:54:14AM -0700, Nathaniel Smith wrote: > For merging, monotone does _not_ use the closest common ancestor. The > reason is that doing so could silently corrupt your code. > > The simplest example is the famous "criss-cross merge": The last few days I've been thinking more about this and some other pathological 3-way merge cases we've known about for a while, re-considering and re-digesting in the light of the recent #revctrl-inspired explosion of understanding of merge algorithms. The rename bug Richard just found is something of a final straw. I no longer believe 3-way merge is a viable technique for modern VCSes. To expand: I'll assume everyone knows about the criss-cross merge case, which forces us to choose more distant ancestors in some cases, or else risk silently corrupting code. There are some limited workarounds to this (per-file ancestor selection, for instance), but they merely reduce the frequency of the problem, rather than eliminate it. Here's another pathological case for 3-way merge: A | B / \ C D Suppose that a file was added on the A->B edge, and then removed again in B->C, while it was left alone on the B->D edge. We want to merge C and D. Let's assume that for some reason we decide to use A as a common ancestor. What will happen? Our file does not exist in either A or C, so when comparing A and C 3-way merge will think that nothing has happened. Our file _does_ exist in D, though, so when comparing A and D, 3-way merge will decide that a file has been added. Therefore, says 3-way merge, this file should exist in the new merged node. But, this is obviously wrong; the file was deleted between B and C, and this delete should have caused a delete of D's copy as well. This was the version originally discovered some time ago, and codified in monotone's t_merge_add_del.at test. There is a corresponding version for content changes -- suppose that a file was modified in B, and then this change was reverted in C, but left alone in D. The same problem occurs; the bad code mysteriously reappears in the merge of C and D. When we discovered this a while ago, we sort of scratched our heads, tossed around some ideas about "per-hunk ancestor selection" and such, and shrugged and ignored it for a while. Richard just discovered a related problem that is harder to ignore. Take the same graph as above, and suppose that instead of being deleted in C, our file was _renamed_ in C. Now, when we go to merge, the A->C changeset says file "foo" was added, the A->D changeset says file "bar" was added, and there is no way to tell that these files are really the same file, so they are both added. Now we have a single logical file that exists twice in the same tree. (This has now actually happened in the monotone tree, which means that we have another ancestry rebuild in our future.) Notice the problem doesn't actually get much better in a system where files are assigned unique persistent ids, rather than having them calculated on the fly as monotone does (or if monotone used a better way to calculate them on the fly); it would make this case marginally better, in that 3-way merge would signal a conflict instead of doing the incorrect thing, but this is not that much of an improvement. (And is exactly the sort of weird id-only conflict that monotone _doesn't_ store peristent file ids so it can _avoid_.) (This problem seems specific to the semantics of "rename"; there doesn't seem to an analogue for file content, because file content cannot be moved, only created or destroyed. If anyone wanted to attempt supporting content movement despite its horrible edge cases and inherent potential for misbehavior, though, then this is yet another problem they would need some solution to.) So, clearly, picking A as an ancestor in the above graph is terrible. This leaves us in a bad situation, though. The possibility of criss-cross merge means that we are sometimes (or often) forced to choose ancestors that are far away, or else risk corrupting user data; the above cases mean that we are sometimes (or often?) forced to choose ancestors that are _close_, or else risk corrupting user data. I am fairly confident that one can construct more complicated graph topologies embedding the above example, in which one is _forced_ by criss-cross rules to choose A as an ancestor. (Certainly it is possible for monotone's current criss-cross avoidance algorithm; I believe it is possible in general, but it's harder to check as-yet-undiscovered criss-cross avoidance algorithms in general. Per-file ancestors don't seem to help; criss-cross and mysterious unreversion both can happen at the hunk level, and thus can both be going on in the very same file at the very same time.) Conclusion 1: While the thought of rewriting change_set.cc again fills me with something almost, but not quite, entirely unlike joy, I don't see any way to fix Richard's bug without some major surgery, and we need to not generate nonsense changesets. At which point, I guess, we might as well implement: Conclusion 2: 3-way merge is an inappropriate choice of merge algorithm for a modern VCS. Fortunately, it seems like codeville-merge is a viable replacement here (it can be applied to both content merges and tree rearrangement merges), and with some recent improvements that Bram and some other people (including me) have been playing with, it may (I'm not sure yet) be strictly more powerful than 3-way merge. -- Nathaniel -- "...these, like all words, have single, decontextualized meanings: everyone knows what each of these words means, everyone knows what constitutes an instance of each of their referents. Language is fixed. Meaning is certain. Santa Claus comes down the chimney at midnight on December 24." -- The Language War, Robin Lakoff