DVCS and its most vexing merge

There's this very elegant way to shoot your leg off with a DVCS. Here's the recipe:

  1. I create a clone of the repository A and call it B. You create another clone of A and call it C.
  2. I add an if statement in B, fixing a bug. You fix the same bug in C in a very similar way.
  3. I pull your changes from C to B. There's a conflict around the bug since we both fixed it. I take my patch, throwing away your nearly identical patch.
  4. Meanwhile, your roommate pulled both B and C into his clone, D. And he had to resolve that conflict, too. And he took your patch, and threw mine away.
  5. Now, D and B are pushed back to A. DVCS quiz: what happens?

Answer: the system has accurately recorded the manual merges, so it has enough information to make this new merge automatically. It sees your patch, and it throws it away as it should according to my manual merge. It sees my patch, and it flushes it down the toilet since that's what your roommate said. Net result: both patches are gone, the bug is back in business. (Edit: it doesn't work that way – bk version 4 does a different thing, and other systems reportedly do still other things. Do you still want to read the rest of this?..)

Which of course doesn't matter, since it's immediately discovered by the massive Automated Test Suite. For example, if it's an OS kernel, each revision is automatically tested on all hardware configurations it should run on. And the whole process only takes 10 minutes, according to the Ten Minute Build XP Practice. No harm done, no reason to discuss it. I just thought it was a curious thing worth sharing.

Maybe it's a well-known thing, but I don't think it is, and if I'm right, it's definitely lovable. For example, here's what BitMover, maker of BitKeeper, the common ancestor of DVCSes, has to say about this:

"It's important to note that because BitKeeper has a star topology and its possible to share data with any repository, it's not necessarily recommended."

What this is trying to say is that the graph of pulls shouldn't be a generic graph and you're better off with a tree. That is, I shouldn't pull directly from you; we should both pull from and push to A. You and your roommate should also synchronize via A, or via A's "child" repository, but then you shouldn't push to A directly, only via that child, and so on. If we maintain this tree structure, the same conflict will never be resolved twice, and then we won't get screwed when the merges are merged.

I wonder if you could detect the situations when you "merge merges", that is, when the same conflict was resolved differently. You could then insist on human intervention and save those humans' bacon. I'm too lazy to think this out and too stupid to effortlessly see the answer, so I'll resort to a social heuristic like all of us uber-formal nerds do. The social heuristic is that Larry McVoy of BitMover has probably already thought about this, and found ways in which it could fail. So I'm not going to argue that BitKeeper merges are broken.

What I'm going to argue, at least for the next couple of paragraphs, is that it sucks when they tell you about their superstar topology and then explain that it's best to avoid actually using it. Not only that, but they fail to mention a fairly frightening and, trust me, not at all unlikely scenario which could actually persuade you to follow their advice.

Because when they tell me "we have this simple model of how things work – repositories with complete local history and changes flowing between them – but you should arbitrarily restrict yourself to a subset of this model, for reasons we aren't going to share with you, even though the general case works", when they tell me that, my reply is "I alias rm to rm -f". I understand how rm works, it's fairly simple, and I don't like to talk about it over and over again, "Are you sure?" – yes, I'm sure, thank you very much and good bye.

But the lovable part is, speaking of social heuristics, the lovable part is that BitMover said it right. Because if they mentioned that fairly frightening and not at all unlikely scenario, they'd scare people off rather than illustrate a point. On the other hand, when they say "It's good practice to think about how the data should flow", most people will nod and follow whatever advice they give them.

Just imagine a team of programmers engaging in the practice of thinking about how the data should flow, dammit, all on company time. Yeah, yeah, so BitKeeper earned a sarcastic comment on Proper Fixation. It's still a small price to pay for getting your message to the majority of your users.

You see, the majority of programmers are not just "irrational" as we all are, but their reliance on reasoning doesn't even exceed the mean of the population, which means they barely use reasoning at all, it's pure gut feeling.

For example, I was writing a bunch of macros in a proprietary debugger extension language. A guy who came to talk to me looked over my shoulder, and I explained, "Debugger macros. Very useful, a crappy language though." He said, "Yeah, looks like so."

HE COULDN'T POSSIBLY KNOW THAT. I knew he couldn't. How could he look at the code and realize that all variables were global? How could he know they were printed upon assignment, including loop counters ('cause it's a "macro", so it works just like assigning at the debugger console, which prints the variable)? He couldn't know any of that. So why did he agree with the "crappy" part? Oh, I knew why.

"You mean it has dollar signs?" Silence. "You mean it prefixes variable names with the dollar sign, don't you?" "Yeah, that." "Well, I like the dollar signs, helps you distinguish between your macro variables and the variables of the debugged C program. Anything else?" "Well, um, yeah, it looks kinda primitive." Low-end Ignorant Language Bigotry quiz: if "crappy" means "has dollar signs", what does "primitive" mean? Answer: no type declarations. I'm sure it was that, although I didn't go on and ask.

So that's "engineers" for you. If you want to write programs or tech docs for the average engineer, keep that picture in mind. Or don't. Aim for the minority, for people who don't work that way, under the assumption that they are the ones that actually matter the most. I don't know if this assumption is right, but at least it's lofty.


For the record, I had my share of both centralized and distributed version control systems, and today I like it distributed and I wouldn't ever want to go back, The Most Vexing Merge be damned. Why? I'll share my reasons with you through the story of My Last CVS To BitKeeper Exodus. I think I'll illustrate the engineers-and-reasoning-don't-mix point as a by-product, because that's how that story goes.

There recently was this argument about DVCS encouraging "code bombs", a.k.a "crawling into a cave". I haven't heard either of these terms, so I've been using a term of my own – "accumulating critical mass". The idea is to develop in your own corner, without integrating it with the main branch. You then show up with N KLOC of new stuff and kindly ask to merge it in.

Some people claimed this was particularly harmful for open source projects where there was no managerial authority to prevent this. Ha! Double ha. In an open source project, the key maintainers may say, "you see, we can't integrate it when it's done this way; we're sorry, but you should have talked to us." The changes will then be reimplemented or dropped on the floor.

Now, if you think that in a commercial environment a manager can easily decide to drop changes on the floor, together with the cost of implementing them and especially the cost of delaying the delivery of the features, if you think that, well, I wonder why you do. But perhaps a manager could insist on frequent integration? She could try, but she'd have to deal with real or imaginary cost of merges, increasing over time and getting in the way of deliveries. Of course there are perfect managers and perfect teams where it's all dealt with appropriately, you just have to find them.

So yeah, "code bombing" is a problem, especially in commercial projects. But the idea that DVCS encourages it? Hilarity! It's like saying that guns encourage murder. I prefer to think of guns as something that encourages fear of armed policemen, getting in the way of the natural instinct to club your neighbors to death. I mean, yeah, it's easier to code bomb with a DVCS, but with a centralized system, people use code bombing – or clubbing? – even more, because merging is harder, the cost of merges increases more quickly and the ability to force integration is thus lower. The criminals are poorly equipped, but so is the police.

And this is exactly what happened to the last team stuck with CVS that I helped migrate to BitKeeper. Everybody had their own version made up of file snapshots taken at different times and merged with the repository version to different extents. A centralized system doesn't record these local versions, so unless you immediately commit your merges, you are left with a version of a file which the system doesn't know. This means that the next merges are going to be really hard, because you've lost your GCA, the greatest common ancestor. So instead of a 3-way merge, you'll be doing a 2-way merge, which really sucks.

So I decided to not talk about the caves they were crawling into and the code bombs they were throwing at each other. Rather, I decided to show them how a 2-way merge couldn't do what a 3-way merge could. I still think it's the ultimate argument for DVCS, because DVCS is basically about accurate recording of all versions and not just the single time line of the main trunk. So the argument for it has to do with the benefits of such detailed recording.

So I gave this example where you start with a file having two lines:

And then I add a line, ccc, and you delete a line, aaa. If we have the GCA (a 3-way merge), then clearly the right result is deleting aaa and adding ccc, getting this:

But with a 2-way merge, we only have your file:

…and my file:

This can only be merged manually, because there's no way to automatically figure out that you deleted aaa and I added ccc; for all the tool knows, you could have done nothing and I've added two lines, so the right merge is:

…canceling your change. So it has to be manual merge. Manual merge means dozens of boring deltas you have to inspect in each file. That's what I call "costly".

Of course it doesn't matter in a right world, where people integrate frequently and always commit their merged files to the centralized repository. Except it wasn't so in the wrong world of the CVS developers I was "helping" to upgrade to new tools (for the last time in my life, people, for the last time in my life). And I thought we could avoid the discussion of the somewhat-technical-but-largely-social reasons of the constantly increasing cost of merges, and instead we could focus on the technical benefits of the 3-way merge and accurate GCA recording.

And of course I was wrong. The discussion immediately shifted to "we don't need merges" because everything is "modular" and there's a single owner to each file. Of course it wasn't, and there wasn't. Some things were used by everybody, like the awful build scripts and the DMA code. Some modules had two owners, or were in a transition state and had 1.5 owners, and so on. There were merges all over the place.

And if there weren't merges and merge-related problems, how come everybody worked on their own "pirate" version which was never recorded in the main trunk and was made from a colorful variety of files partially merged at different times? How come changes propagated with cp and emacs-diff and not cvs update? And why was the tech lead so passionate about moving to BitKeeper which doesn't let you partially update a repository so you have to merge everything? And why did everybody anxiously object that necessity if there were "no problems with merges"?

The final result: the tech lead simply forced the migration to bk. Everybody on the team hated me for my connection with the idea (I wasn't on their team but I used to be a likable satellite and now became a hateful satellite). Developers who I thought were their best eventually (and I mean eventually) told me it was actually a good thing. So it wasn't a bad closure. And still, I decided that I'm not going to "help" anybody "deploy" any kind of "tool" in this lifetime again, roughly speaking. Too much emotions for this programmer.

And this was supposed to show why I like DVCS, at least in the imperfect world where long-living branches occasionally happen, and the kind of reasoning I think is interesting in this context, and the kind of reasoning other people I came across found interesting. So there were are.

P.S. Why "most vexing"?

I thought I saw that "C++'s most vexing parse" from Scott Meyers' Effective STL has its own Wikipedia entry, but apparently it doesn't. It's basically a variation on the theme of C++'s declaration/definition ambiguity, and I liked the term, especially the "most" part where parses are unambiguously sorted along the vexing dimension. So I figured "X's most vexing Y" is a good template.

I'd like to use this opportunity to say that I skimmed though Effective C++, 3rd Edition, and… Where do I start? There's an advice to create date objects with "Date d(Day(31), Month::april(), Year(2000))" or something. That is, create special types for the constructor arguments. Well, it doesn't check that April comes without the 31th day, does it? The Date constructor could test for it though. Well, why not test for April 41st in the Date constructor, too, and, ya know, spare the users some keystrokes, if you see what I mean? The code is verbose. C++ compiler error messages are verbose. VERBOSITY EVERYWHERE! Help!

This raises the question to the author, whether he ever worked with a system where every piece of data comes covered with the toxic waste of overzealous static typing. But this borders on an ad hominem attack. And seriously, that sort of thing is to be avoided, at least until somebody proposes to have named constants for days or years and not just months.

So instead of the personal attack, I'll ask Software Development Consultants, all of them, to kindly change the phrasing "it's best to do so and so" to "I like so and so" or something. Because we have this huge crappy-dollar-sign crowd, and they copy style from each other like crazy, and their ultimate source of style is books by Software Development Consultants, and whenever they see a "best practice", their common sense is turned off and they add the technique to the bag of tricks. So Consultants have a great power in this world. It doesn't make the common sense shut-off feature their fault, but power they do have.

And with great power comes great responsibility, profanity deleted. I mean, you're obviously giving advice neither you nor others have tested for very long, out of generic principles, profanity deleted. Like "prefer algorithms such as for_each to loops", an advice issued before fully compliant implementations of STL were even widely available, profanity deleted. Quite a piece of advice, that, profanity deleted. Couldn't you at least phrase your advices in a little less self-assured way, fucking profanity deleted?

For example, Meyers has finally lowered the bridge and let the enemy of template metaprogramming occupy a notable share of pages in an Effective C++ edition. I still remember his promise to "never write about templates", in the preface to Modern C++ Design, I think. And now the promise is broken. Hordes of clueless weenies are rushing into the minefield of template metaprogramming as we speak, since it's now officially Mainstream C++. Can you imagine the consequences? I can't. It's too awful. I think I'll go to sleep now.


#1 Aristotle Pagaltzis on 07.11.08 at 7:48 pm

Eh? When I try to recreate this scenario in git, in the last step, no matter whether B or D has gone first, the second guy to try to push loses: s/he cannot push before pulling, and when s/he does, s/he gets a merge conflict that needs manual resolution. But then, git is known to refuse to merge some cases automatically where other DVCSs will try. Maybe this is one of them? (In which case that would resoundingly vindicate Linus’ insistence on this design, whence git got its “stupid content tracker” moniker.

#2 DGentry on 07.11.08 at 8:23 pm

Unfortunately in many software development organizations, once a project creates a branch most of the other developers stop paying any attention to it. So even if the changes are submitted to the branch in small, easily digestible chunks they will still be perceived as a Code Bomb by the rest of the team when the branch merges back to main. Thats human nature, not the technology of the version control system.

#3 Yossi Kreinin on 07.11.08 at 11:44 pm

To AP: in bk, you'd have to pull before pushing, too, but the conflict resolution would be automatic. Apparently the merge heuristics differ; I wonder what makes git refuse to merge.

In general, I think automerges are always unsafe, so the whole question of deciding when you go ahead and use them and when you demand human intervention is completely heuristical. And I'm not very good at heuristics, that is, in deciding which of two provably incorrect methods is going to do less harm and more good across the (informally specified) distribution of use cases.

To DGentry: Exactly, people don't like the overhead of merging and try to delay it, which creates long-living branches, which makes merging even costlier, etc. A vicious cycle, made even more vicious by the fact that people won't admit its existence.

#4 Entity on 07.12.08 at 12:50 am

I really really hate STL, god the pain…. Rather C than STL.

#5 Aristotle Pagaltzis on 07.12.08 at 2:30 am

Yes, well, Bram Cohen had a long argument going with Linus back when git was new, based on the fact that in the Codeville project, Bram and friends tried really hard to automerge as many things as possible. Linus was of the opinion that this is lunacy, and that beyond any but the most trivial conflicts you want a human to examine and decide. The git-merge manpage describes its strategies; the hint I get from it is that the design goal was to make the merge strategies less stupid, but not smarter, and that experiments with existing data informed the design process. Given how many other things git does in an unusual but unusually right way, even among DVCSs, I wouldn’t be surprised if this were yet another area in which it stands out from the pack.

#6 John Millikin on 07.12.08 at 5:50 am

I am unable to replicate your merge issues in Bazaar. When trying to push from D to A, I receive an error that the branches have diverged and I should merge before pushing. Executing `bzr merge` discovers the error and marks the conflict for manual resolution.

This is because when it comes time to push, the repository looks like this:

A: A[1]
B: A[1] -> B[1] -> B[2, B->C]
C: A[1] -> C[1]
D: A[1] -> D[1, B->D] -> D[2, C->D]

When you push from B to A, A is updated to:

A: A[1] -> B[1] -> B[2] (B->C)

And then trying to push from D to A obviously fails, because revisions exist in A that are not present in D.

BitKeeper's willingness to force the merge anyway and drop your revisions on the floor is just more indication that it is unsuitable for production. BitKeeper is only useful for people that do not mind silent data loss.

> This begs the question to the author, whether he ever worked with a system where

It raises the question. Begging the quesiton is a specific form of logical fallacy not present here.

#7 Yossi Kreinin on 07.12.08 at 6:08 am

To AP: I think working on a kernel raises the bar for merge safety. A large portion of bugs in kernelish code, interrupt handlers, context switching and stuff, a large portion of those bugs by which I got personally fucked came from automerges. As far as I recall, all those automerges happened in spots remote from each other and basically any merge algorithm would do them automatically and assume it was safe. However, while all kinds of automerges are a risk, you'd obviously want to at least restrict them to the safest subset once you realize you can't afford the cost of actually reviewing all conflicts.

#8 Yossi Kreinin on 07.12.08 at 6:24 am

To John: for starters, I can't reproduce the issue with bk, embarrassingly enough; what bk 4 apparently does is it takes the newer conflict resolution, so one of the patches is kept. Of course it still isn't "safe" in the sense that one manual resolution was dropped on the floor; it's just the right thing in my example assuming the semantics of the edits.

Regarding "unsuitable for production": just a little bit over the edge; I used bk a lot in production and it, um, worked. I mean, I never allowed myself to say that C++ was unsuitable for production, because the fact is that you can deliver with C++, and I did, and C++ is, really, an exceedingly hateful piece of excrement. "Unsuitable for production" is kinda under the belt for new systems and not very credible for old ones that have already been used in production.

Another thing is that all automerges are risky, and so are manual merges because you'll get tired of reviewing conflicts and err; the balance between manual and automatic merges is apparently a completely heuristical thing, because you can't prove anything about the relation of the semantics of a merged program to the semantics of the two original versions.

That said, I shouldn't have generalized my experience with bk (itself somewhat stale) to other distributed systems; I should have realized that merging is a can of warms, so quite likely everybody is doing it differently. That "merging merges" is a situation unique to DVCSs doesn't mean they use the same solution. Where's a brain when I need one?

And thanks for, um, begging the question… Fixed.

#9 Yossi Kreinin on 07.12.08 at 6:30 am

To Entity: while <algorithm> sucks better than your average vacuum cleaner, having <map>, <list> and <vector> comes handy. If I could add one thing to C, it would be a standard container library. The troubles with the STL containers are the trademark verbosity and debuggability problems, ranging from the awful type names to inability to make sense of them when they are partially overwritten. But it can still be better than C's nothing.

#10 John Millikin on 07.12.08 at 6:34 am

I do not mean "unusable", but "unsuitable". I consider the primary purpose of a VCS to be the storage and preservation of version data, and if a particular VCS will discard version data, I don't want it anywhere near my code. CVS, for example, is another system that I call unsuitable for production. Although it is obviously heavily used, much more than all DVCSes combined, it nevertheless is a poor choice in version control.

You could compare it to using a RAM disk for permanently storing vital data. I'm sure that somebody somewhere does so and has never had a problem with eg. power outages, but this fact still doesn't make it a good idea.

#11 Yossi Kreinin on 07.12.08 at 6:47 am

Well, bk won't throw away version data in the sense that it will preserve all revisions and you'll be able to go back to any point; that the new version it automatically generates isn't necessarily the right way to resolve the conflict it sees is another matter. So it's more like an opinionated hard disk than a RAM disk…

#12 Aristotle Pagaltzis on 07.12.08 at 9:33 am

Not only can’t you afford to review every single conflict, but I would argue that there is an even more important reason you aren’t going to review every conflict. Essentially this reason is because the danger of semantic conflict introduced by a disparate changes increases with distance. Let me try to explain.

If the changes are close by, then trivial resolutions are more likely to be correct (because those that are incorrect are more likely to touch the same parts of the code and thus result in non-trivial conflicts), and in those few cases where they aren’t, the problem will manifest itself relatively quickly and probably in an obvious way. But detecting semantic conflicts introduced by merges between changes in widely separated areas of the code is likely to require holding more of the program in your head than most programmers can – or in projects the size of the kernel, than any programmer can. So even if you did review those 3-way diffs manually, it would be a comparatively useless exercise: the effort would be far disproportionate with the gain in confidence.

In fact, I would argue that merging is a red herring: this sort of semantic clash between disparate but interdependent parts of the code is inevitable the moment they can evolve separately. How this concurrent development process is organised – DVCS; CVCS; tarballs and patches; everyone edits the same files on a network share – is of no consequence at all to that fact. Merging doesn’t cause semantic clashes, programming causes semantic clashes.

And so you might as well at least relieve the programmers from the drudge work.

#13 bfish.xaedalus.net » A tech blog recommendation on 03.25.10 at 2:16 pm

[...] an evil of distributed revision control systems (and a retraction, but still worth a [...]

Leave a Comment