badmerge -- abstract version

See also the concrete example with real C code where darcs merge does the right thing and the others do the wrong thing. See also an attempted counter-example where darcs merge allegedly does the wrong thing, along with my argument that this is not actually a counter-example.

    a
   / \
  b1  c1
  |    
  b2

Now the task is to merge b2 and c1. As far as I know all revision control tools except for darcs, Codeville, SCCS, and perhaps BitKeeper treat this as a 3-merge of (a, b2, c1).

The git or svn 3-merge algorithm and the GNU diff3 algorithm apply the changed line from c1 to the wrong place in b2, resulting in an apparently clean but actually wrong result.

merged by SVN v1.2.0, GNU diff3 v3.8.1, or git v1.5.6.3

Whereas darcs applies the changed from from c1 to the right place in b2, resulting in a clean merge with the correct result.

merged by darcs v1

The difference between what svn does and what darcs does here is, contrary to popular belief, not that darcs makes a better or luckier guess as to where the line from c1 should go, but that darcs uses information that svn does not use -- namely the information contained in b1 -- to learn that the location has moved and precisely to where it has moved.

Any algorithm which merges c1 with b2 by examining (a, b2, c1) but without reference to the information in b1 is doomed to do worse than darcs does in this sort of case. (Where a silent but incorrect merge such as SVN currently does is worse than raising it to the user as a conflict, which is worse than merging it correctly.)

It is important to understand that darcs merge performs better in this example not because it is "luckier" or "more complicated" than 3-merge (indeed darcs merge is actually a much simpler algorithm than 3-merge is for this example) but because darcs merge takes advantage of more information -- information which is already present in other systems such as SVN but which is not used in the current SVN merge operation.

code listings

listing a, abstract

A
B
C
D
E

@@ -1,3 +1,6 @@
+G
+G
+G
 A
 B
 C

listing b1, abstract

G
G
G
A
B
C
D
E

@@ -1,3 +1,8 @@
+A
+B
+C
+D
+E
 G
 G
 G

listing b2, abstract

A
B
C
D
E
G
G
G
A
B
C
D
E

@@ -1,5 +1,5 @@
 A
 B
-C
+X
 D
 E

listing c1, abstract

A
B
X
D
E

listing 3-way merged, abstract

A
B
X
D
E
G
G
G
A
B
C
D
E

listing darcs merged, abstract

A
B
C
D
E
G
G
G
A
B
X
D
E

Thanks for Nathaniel J. Smith for help with this example.

Thanks for Ken Schalk for finding bugs in this web page.