Operational Transformation On Text

Can we merge without conflicts?

If you're used to using source code control programs such as git, you will probably be used to the idea of merge conflicts when merging updates to text documents.

git is line based and will give merge conlicts when the same lines are text are edited.

It can even produce merge conflicts when adjacent lines are edits. In the following example there are originally three lines with the text "1", "2" and "3". One user deletes the line with "2", another uses inserts a line with "x". By default git will give a merge conflict. Alternatively using a union merge a result is defined, but in that case the output doesn't perserve the intention of the user that deleted the line with "2", that line still appears in the output!

However it's actually possible to always merge edits on text, even on the same line of text and preserve the original intentions in terms of the insertions and deletions of characters.

Intentions of operations

The intentions of insert and delete operations on text can be defined in terms of the relative positions of the characters. One can ask whether it is possible to preserve these intentions as concurrent operations are merged.

A merge can always preserve these intentions

It is always possible to preserve these intentions when merging concurrent insert and delete operations. In that sense there are never conflicts when merging operations on text!

The merge result is the union of all the insertions minus the union of all the deletions.

This is unambiguous except for insertions at the same position. In that case the CEDA merge algorithms determine the insertion order from the total order on the site identifiers.

There can be cases where merging of operations doesn't preserve the intentions of the users at some higher semantic level. Such conflicts fall outside the scope of the CEDA implementation of OT. In general the merge of concurrent operations is always defined, even if there are real conflicts between users. Users are expected to edit the result of the merge (perhaps interactively) to resolve conflicts.

Example with two sites

As a simple example consider two sites which independently insert a single character into a string. Initially the string is "b" and one site inserts an "a" before and another site inserts a "c" after. Obviously after merging these operations the result should be "abc".

The following state transition diagram shows the four possible states of the string variable at the corners of a square. The operations represent transitions between these states. There are two paths from the initial state in the bottom left corner to the final state in the top right corner. Notice that the insertion position of "c" needs to be shifted to the right when it is applied in the context of having first inserted the "a".

Example with three sites

We now consider a third concurrent operation generated by a third site which deletes the "b" character. The final state should clearly be "ac".

In the earlier example the state transition diagram (i.e. lattice) was a square. The additional concurrent operation means the lattice now has a cube structure. The previous lattice corresponds to the front face of the cube.

There are 6 paths through the cube all starting in the front-left-bottom corner and ending on the back-right-top corner. The insertion/deletion positions of the operations are transformed as appropriate so that sites can apply the three operations in any order and they all end up with the same result in the replicated text document.

TP2 puzzle

There is a troubling ambiguity in the state where the deletion of a character has meant that the two insertions positions now coincide

This ambiguity occurs on the back face of the cube

This is related to the problem of meeting a mathematical condition in the literature called TP2. Unlike a number of other implementations of OT (which can give the result "ca" instead of "ac"), the CEDA implementation of OT resolves the ambiguity correctly and satisfies TP2.

Efficient linear time merging

A naive implementation of operational transformation using "history buffers" of operations is quadratic when merging many operations.

However it is possible to merge changes in linear time, in a manner that is similar to the merge of two sorted lists as used in mergesort.