Three into Two: Three way merge with a two way result

Introduction

Since the introduction of our new Merge product (4.0 in February this year) we have seen a number of customers and potential users ask about user interfaces and in particular options for reusing existing interfaces based around two way change such as accept/reject systems.

We have also seen some customers who have been trying to apply merge to the branch merge problem as typically found in a software version control system. This blog post is written for these users, software developers familiar with systems such as subversion, git or mercurial who are looking at how DeltaXML Merge will work in a similar setting.

Software version control systems are often based around ‘diff3’, a line-based three way system that takes three inputs (two branches and their common ancestor). In some cases the merge results are often presented as a side-by-side representation, left side being my branch or the current branch. The right hand side is often the other branch, their branch or the remote branch. However, merge systems in other cases have extra content display panels, perhaps to show the ancestor content or the in-progress result.

Our three-to-two processing system is orientated towards this branch merge use-case. We will ‘rotate’ the result perspective slightly to show changes in the context of two branches. So if content exists in the other branch and not mine it has been added and vice versa. In some cases (such as a three way conflict) we will lose change information.

Merge direction and Symmetry

In the paragraph above we talked about ‘rotating’ results.  This is best illustrated with a diagram and a small example.

In this diagram above M is the common ancestor.  Concurrent merge allows us to do an n-way merge.  This is illustrated by the red arrow.  We can take P, Q, R and S inputs can combine them together in a symmetrical manner – none of them is treated any differently to the others.

For our example let’s consider a simple sentence of text that exists in M and which is edited in P1 and Q1:

M: The quick brown fox jumps over the lazy dog

P1: The very quick brown fox jumps over the lazy dog

Q1: The extremely quick brown fox jumps over the lazy dog

From the perspective of M, what’s happened is that there are two additional words here and our result will look like this:

The very extremely quick brown fox jumps over the lazy dog.

We see two additions and I’ve used different green styles to show that these were from different inputs.  In an editor we may have tool tips to identify who did the adding,  In accept/reject systems these words may have different authors.

Now let’s consider this from a different perspective.  I am on branch Q.  I’ve added the word extremely in the Q1 edit and I want to merge in what’s been happening on the P branch.  I can do this with a three way merge operation that is depicted by the blue arrow in the diagram above.

From my perspective on Q the P1 version does not have the word extremely in the text.  How can this be represented in a two way form?  Most accept/reject style interfaces work in terms of addition and deletion (either of which you can accept or reject).  If extremely doesn’t exist in the other (P) branch then it should be a delete rather than an add after the merge.  Similarly, the word very didn’t exist in my Q branch and so it has been added:

The very extremely quick brown fox jumps over the lazy dog.

When using accept/reject interfaces I can accept both changes and I get a result equivalent to one of the branches.  Likewise, if I reject both I get the other branch.

The yellow arrow in the diagram illustrates the merge in the other direction – merging Q onto P.  What was an add is now a delete and vice-versa.  With our APIs you can have both of these scenarios by swapping the order of the versions in the merge() methods or the order of addVersion() method calls.

This is a simple example of the distinction between the symmetrical three way merge and how it differs from the branch merge case where we can use a two-way representation of the result.

Use cases

As users of software version control systems we did find the merge process frustrating on occasion.  We are presented with conflicts, but in order to understand the conflicts it would help if we could understand some of the other changes that are being merged.  The diff3 algorithm automatically processes or accepts the non-conflicting changes and leaves just the conflicts for the user to deal with.  Our underlying n-way representation and the rule processing system we have developed allows us to do better and we’ve worked on three use cases which we believe will be useful/relevant.

Case 1: Conflicting Changes

This use case is modelled on software version control and diff3. Simple non-conflicting changes, such as element adds and deletes and text modification are automatically processed and the user only has to deal with the conflicts.

Case 2: All Changes

This differs from case 1 above by removing the automatic processing of non-conflicting changes.  We will show all of the changes including the simple ones.

Case 3: Their Changes

This use case is based on the assumption that the user doing a merge on the current branch remembers and understands what has happened on that branch but is interested in any conflicts and also any changes on the other, remote or ‘their’ branch.

A worked example of these use cases is included in the merge documentation.  Please take a look at: Three To Two Merge Use Cases

Nested Change

One thing not seen in a line-based software version control merge is the concept of nested change. Suppose that in a document one user changes a word in a paragraph while another user deletes the entire paragraph. Visually this would look like this (this is how our n-way merge and oXygen plugin represents this case):

Track change and accept/reject systems cannot represent this particular case. Indeed our two-way deltaV2 representation cannot either. It’s a consequence of both hierarchical change and three or more inputs.

If our goal is to produce a two-way result for this case we need to make some compromises and lose some granularity. In this case the change has happened at the paragraph deletion point. We have two paragraphs that differ by one word suddenly. From the perspective of the branch we can use either of these two paragraphs when representing the change, but as the example below demonstrates the user does not see the change to  word suddenly.

Nested change after two way processing and accept/reject conversion

The Two-Way Argument

We’ve been asked more than once: Why not simply do a two-way comparison between branches?

There are two answers to this question:

1. Firstly using the ancestor information provides better alignment of the information. It’s a common frame of reference to the changes that have been made in both branches and which provides a better overall alignment.
2. This leads onto the second answer which is that without an ancestor it is not possible to identify conflict.  With a two way comparison we only know that one branch has made a change and that it is different to the change in the other branch. For example, if we have a word that appears in P1 and not in Q1 we do not know if P1 has added it or if Q1 has deleted it.   We have no way of knowing that two changes overlap in the case of nested change.

Both of these arguments apply equally to diff3 used in software version control by the way!

Summary

We can generate a good two way representation of a three-way merge. But it’s not a perfect solution, information is lost in some cases.  However, it presents the results in terms of the very familiar two-way metaphor.  We’ve demonstrated interfaces for nested change, but these require a new type of interface to manage change and conflicts;  the two-way results should provide easier adoption through the use of familiar interfaces for this common branch merge process.