A criss-cross merge is an ancestry graph in which minimal common ancestors are not unique. The simplest example with scalars is something like:

   a
  / \
 b1  c1
 |\ /|
 | X |
 |/ \|
 b2  c2

The story one can tell here is that Bob and Claire made some change independently, then each merged the changes together. They conflicted, and Bob (of course) decided his change was better, while Claire (typically) picked her version. Now, we need to merge again. This should be a conflict.

Note that this can happen equally well with a textual merger -- they have each edited the same place in the file, and when resolving the conflict they each choose to make the resulting text identical to their original version (i.e., they don't munge the two edits together somehow, they just pick one to win).

This is one of the key examples that has driven development of merge algorithms; there is currently no textual merge algorithm that fully handles this case.

Three way merge

ThreeWayMerge has obvious problems here -- there are two "least" (or more properly, "minimal") common ancestors it could use.

Furthermore, using either of them as a base for the merge will give an incorrectly clean merge -- if b1 as used as a base, it will appear that b2 is unchanged while c2 has changed, therefore c2 will win. If c1 is used as a base, the opposite occurs.

One possible solution is to use 'a' as the common ancestor for the merge; this is the approach taken by Monotone, when it uses the LCA+DOM rather than LCA as a merge base. However, this approach has its own problems.

Scalar codeville merge

Traditional CodevilleMerge on scalar values gives an AmbiguousCleanMerge here -- the last-changed revision for b2 is b1, which is an ancestor of c2, and thus c2 should win cleanly; similarly, the last-changed revision for c2 is c1, which is an ancestor of b2, and thus b2 should win cleanly.

This somewhat anomalous case is normally presented to the user as a conflict (what else can one do?), which is the right result. But there is a more subtle problem:

   a
  / \
 b1  c1
 |\ /|
 | X |
 |/ \|
 b2  c2
  \ / \
   b3  c3

Suppose someone else commits another version under c2, in which they didn't touch this scalar at all -- they are blissfully ignorant of Bob and Claire's shenanigans. Now, this should merge cleanly -- someone has resolved the b2/c2 conflict, someone else has made no changes at all, all should be fine. But it's not; it's another ambiguous clean merge, because the last-changed revisions for b3 and c3 are still b1 and c1, respectively. In fact, this can continue arbitrarily long:

   a
  / \
 b1  c1
 |\ /|
 | X |
 |/ \|
 b2  c2
  \ / \
   b3  c3
    \ / \
     b4  c4

This is yet another conflict. These conflicts continue so long as new versions are committed that do not have the ambiguous-clean resolution as an ancestor.

(Of course, if at any point someone resolves one of these repeated conflicts in favor of c, then things get even more complicated.

*-merge

*-merge handles this case well. The graph, annotated with *s, is:

   a*
  / \
 b1* c1*
 |\ /|
 | X |
 |/ \|
 b2* c2*

Note that the two conflicting merges at the end cause b2 and c2 to be marked. This the key to *-merge's success in this case. *(b2) = b2, and *(c2) = c2, neither of c2 and b2 are an ancestor of the other, so a conflict is reported.

Nor does *-merge suffer from the indefinite procession of repeated conflicts:

   a*
  / \
 b1* c1*
 |\ /|
 | X |
 |/ \|
 b2* c2*
  \ / \
   b3* c3

Because b2 and c2 conflicted, b3 is marked; c3, however, is not changed from its parent, so it is not marked. Therefore b3 wins this merge cleanly.

*-merge does perform sub-optimally in a similar case:

    a*
   / \
  b1* c1*
  |\ /|
  | X |
  |/ \|
  b2* c2*
 / \ /
d*  b3*

Here it reports a conflict, rather than merging cleanly to d. However, this is because this is a StaircaseMerge, and has nothing to do with the criss-cross merge at all.

Simple weave merge

SimpleWeaveMerge handles the simple form of criss-cross correctly. However, it runs into problems on a slightly different example, that only arise in the textual merging case:

    xy
   /  \
 xby  xcy
  | \/ |
  | /\ |
  |/  \|
xbcy  xcby

(each letter represents a line in a file)

Here Bob and Claire have managed to overcome their differences somewhat -- they each actually include the other's new lines when they merge -- but they both insist that their own line must come _first_.

SimpleWeaveMerge will silently clean merge this to either xcby or xbcy -- which it picks is somewhat random, and depends on the details of the Resolution and global ordering it uses.


CategoryMergeExample

last edited 2005-09-04 05:23:24 by RossCohen