Three-Way Merge

Summary

Three-way merge is a staple of revision control systems such as CVS and Bazaar. It takes three inputs: THIS, BASE, and OTHER. THIS is the current value in the user's tree. OTHER is the current value in the tree to be merged. BASE is a basis for comparison between THIS and OTHER, and is usually an ancestor of them.

The operation of three way merge can be paraphrased as "keep my changes, but apply the changes OTHER made to my copy".

Consider the values in each version in a scalar merge context.

Case	THIS	BASE	OTHER	RESULT
1.	A	A	A	A (Boring case)
2.	B	A	A	B (Take change from THIS)
3.	A	A	B	B (Take change from OTHER)
4.	A	B	A	A (AccidentalCleanMerge)
5.	A	B	C	Conflict

As long as any two versions have the same value, the algorithm produces a result. A conflict happens when all versions are have different values, because it is not clear whether OTHER or THIS (or some combination) should be taken. It is not universally accepted that case 4 should merge cleanly, so this case is sometimes an exception.

Conceptually, in a textual merge context Resolution is performed between BASE and the other 2 versions in turn (at merge time, ignoring changes in between). Discrete sections of the versions can then be compared according the above chart.

Gnu diff3 is a common implementation of three-way text merging.

The selection of an appropriate base is important in three-way merges, because three-way works best when the base is similar to THIS and OTHER. The less similar it is, the more chance that it will have a different value from either THIS or BASE, causing unnecessary conflicts. In addition, less similarity can result in Resolution errors, which can cause confusing conflicts and bad clean merges.

See ThreeWayTextMergeImplementation for implementation details.

Diff & Patch

Diff and patch can be used to perform something like a three-way merge. One simply performs a diff from BASE to OTHER, and then uses patch to apply it to THIS. This approach is more limited than diff3. In case 4, instead of reporting a clean merge, it necessarily produces a conflict. This approach is also prone to even worse Resolution errors than more intelligent implementations.