63 Single character insertion and deletion operations

(written 26 July 2005)

Abstract

This paper describes a new technique for operational transform of single character insertion and deletion operations on a text document that solves the ERV puzzles and TP2 convergence problems in a far simpler, more efficient and elegant fashion than the SDT [1] or SDTO [2] algorithms.

Like the SDT algorithm, the IT and ET is based on the effects relation which is a total ordering on all characters inserted into the text document. The paper provides an easy way to calculate the effects relation.

Introduction

For state S and operation O, S' = S+O denotes the state obtained after executing O on state S. Operation O may only be executed on state S. Therefore we define state_in(O) = S.

Let id(O) denote the site identifier of the site on which O was originally generated. It is assumed there is a total ordering on site identifiers.

Two operations O₁, O₂ are equivalent (written O₁ ~ O₂) if state_in(O₁) = state_in(O₂) = S and S+O₁ = S+O₂. Note that this doesn't imply that the operations are equal. For example, it is possible that id(O₁)≠id(O₂).

[O₁ ... O_n] denotes the list of operations O₁,...,O_n assumed to be contextually serialised - i.e. intended to be performed in the given order on some initial state S. S + [O₁...O_n] denotes the state (((S+O₁)+O₂)+...+O_n).

As in [1], by definition characters in text documents have identity. A character is originally inserted by a particular user at a particular site. The character keeps its unique identity even though its index position in the document changes as characters are inserted or deleted. Note that a character doesn't simply relate to its appearance (eg its ASCII code) - for example each appearance of the letter 'A' in a document represents a different character.

We take the convention that strings use zero based index positions. Given string s, let s[i] be the ith character and let s[i,j) denote the sub-string corresponding to the half open interval [i,j).

Definition of IT, ET

Let O₁ || O₂ and state_in(O₁) = state_in(O₂) = S. Then we define O₁' = IT(O₁,O₂) as being a transformed version of O₁ that maintains the original intention of O₁, whilst being executed in the document state following execution of O₂. i.e. state_in(O₁') = S+O₂. Therefore [O₂ IT(O₁,O₂] is contextually serialised.

ET is defined to be the inverse of IT. i.e. whenever O₁' = IT(O₁,O₂) is defined, we define ET(O₁', O₂) = O₁. Note that ET is only defined on contextually serialised concurrent operations

It has been shown in [3] that if IT satisfies conditions TP1, TP2 (defined below) then sites are able to execute operations in different orders yet achieve convergence at quiescence.

TP1

∀ O₁, O₂ where O₁ || O₂ and state_in(O₁) = state_in(O₂) = S, S + [O₁ IT(O₂, O₁)] = S + [ O₂ IT(O₁, O₂) ]

In the following diagram we require S12 = S21.

TP2

∀ O₁, O₂, O₃, IT( IT( O₃, O₁), IT(O₂, O₁)) = IT( IT( O₃, O₂), IT(O₁, O₂))

System 1 : Insert operations

In system 1 we limit ourselves to insert operations that apply to a single text document. Operation O = ins(p,c) inserts character c at position p.

Let each operation contain the following fields

The following diagram shows two cases of transforming operations Ox, Oy against each other. For each cell the initial state is in the bottom left corner and the final state is in the top right corner. There are two paths from the initial state to the final state - either along the bottom and right edges, or along the left and top edges.

From these two cells we get four cases for IT(O₁,O₂)

The criteria for these four cases are mutually exclusive and cover all possible cases. Therefore the above cells lead to the following well-defined algorithm for IT.

// Assumes O1 || O2
IT(Operation& O1, const Operation& O2)
{
    if (O2.p < O1.p || O2.p == O1.p && O2.id < O1.id) ++O1.p;
}

From the two cells we get four cases for ET(O₁,O₂)

These four criteria are mutually exclusive, but do not cover all cases. The missing cases are

• O₁.p = O₂.p ∧ O₂.id < O₁.id
• O₁.p = O₂.p + 1 ∧ O₁.id < O₂.id

It would seem that these cases can only occur when there is a causal dependence between O₁, O₂. Therefore we argue that this "incompleteness" is acceptable as long as we only ET concurrent operations. Therefore we have the following algorithm for ET

// Assumes O1 || O2
ET(Operation& O1, const Operation& O2)
{
    if (O2.p < O1.p) --O1.p;
}

We may return to this incompleteness issue in a future paper that addresses the support for selective undo - because that requires transpose of causally dependent operations.

Proof of convergence:

TP1: Let the initial document state be S. We want to show that

∀O₁,O₂, S + [O₁ IT(O₂, O₁)] = S + [ O₂ IT(O₁, O₂) ].

Let |S| = n and Si denote the ith character in S. Let O₁ = ins(p1,c1). O₂ = ins(p2,c2). O₁, O₂ both execute on state S. Let O₁' = IT(O₁,O₂) and O₂' = IT(O₂,O₁).

Let S1 = S + [O₁] = [S0 S1 ... Sp1-1 c1 Sp1+1 ... Sn-1 ] and S2 = S + [O₂] = [S0 S1 ... Sp2-1 c2 Sp2+1 ... Sn-1 ]

There are four cases to consider

Note that the relative order of characters is preserved under IT. This relates to the requirement of user intention preservation.

TP2: Need to show ∀ O₁, O₂, O₃, IT( IT( O₃, O₁), IT(O₂, O₁)) = IT( IT( O₃, O₂), IT(O₁, O₂))

Continuing the conventions in the proof of TP1, let O₃ = ins(p3,c3).

Suppose p1 < p2. Then there are seven cases to consider. The following table shows the shifts (i.e. Δp3) applied to p3 as O₃ ITs first past O₁ then O₂' = ins(p2',c2), or alternatively first past O₂ then O₁' = ins(p1',c1). Note that p2' = p2+1, and p1' = p1.

There is a consistency in the relationship between p1,p3 (irrespective of whether O₃ ITs past O₁ first or O₂ first): In the first five rows, when O₃ ITs first past O₂, p3 is not changed (Δp3 = 0). Also p1' = p1 so the relationship between p1,p3 is preserved. In the last two rows, when O₃ ITs past O₂, p3 is incremented. This still means p3 > p1 so again the relationship between p1,p3 is preserved.

There is a consistency in the relationship between p2,p3 (irrespective of whether O₃ ITs past O₁ first or O₂ first): In the first two rows, when O₃ first ITs past O₁, p3 is not changed (Δp3 = 0). In these cases p3 < p2 and also p3 < p2' = p2+1, so the relationship between p2, p3 is preserved. In the last five rows, when O₃ ITs past O₁, p3 is incremented. However O₂' also has its position p2 incremented, so the relationship between p2, p3 is preserved.

In all cases the total shift applied to p3 is the same, and therefore condition TP2 is proven. By symmetry we see that TP2 is also proven when p2 < p1.

Let p = p1 = p2, WLOG assume O₁.id < O₂.id. Therefore O₁' = ins(p1,c1) and O₂' = ins(p2+1,c2). There are five cases to consider. The following table shows the shifts (i.e. Δp3) applied to p3 as O₃ ITs past O₁ then O₂', or alternatively O₂ then O₁'. In all cases the total shift is the same, and therefore condition TP2 is proven.

Alternative proof of convergence

At quiescence all sites have executed all the insert operations. Therefore all sites agree on the set of characters that have been inserted. Therefore to show convergence, it is sufficient to show that all sites agree on a total ordering of the characters.

Consider that we break up the text document into groups of characters, where characters within a group were tied for insertion position during IT (and therefore site ids were used to break the ties). It is claimed that all the following are true

1. All sites agree on the assignment of characters to these groups
2. There is agreement by all sites on a total ordering of these groups.
3. Within a group, the characters are ordered according to the total ordering on the siteids

Cell 1 relates to the division of the characters into the groups, and cell 2 to the ordering of operations within a group.

It follows that all sites agree on a total ordering of the inserted characters.

System 2 : Insert and track operations

System 2 extends System 1 by allowing for "track" operations, in addition to insert operations. i.e. System 2 supports the following two operations:-

• ins(p, c) - insert character c at position p
• trk(p) - track character at position p

The "track" operation doesn't have any side effects. Its only purpose is to track the location of a character.

The solution is expressed with the following two additional cells

Cell 3 says that tracking operations have no effect on each other. Cell 4 says we need to increment the position of a tracked character when there is an insertion at the same position or to the left.

IT(Operation& O1,const Operation& O2)
{
    if (O2.ins)
    {
        if (O2.p < O1.p || O2.p == O1.p && (O1.trk || O1.id < O2.id)
        {
            ++O1.p;
        }
    }
}

ET(Operation& O1,const Operation& O2)
{
    if (O2.ins && O2.p < O1.p)
    {
        --O1.p;
    }
}

Note that ET assumes O₁ || O₂, so it never sees the case of t(O₁) = trk, t(O₂) = ins and O₁.p = O₂.p.

Proof of convergence: The tracking operations have no effect on the document state; therefore convergence is achieved because we continue to use cells 1,2.

System 3 : Insert and delete operations

System 3 extends System 1 by allowing for single character delete operations, in addition to single character insert operations. i.e. System 3 supports the following two operations:-

• ins(p, c) - insert character c at position p
• del(p) - delete character at position p

A correct solution to IT and ET is surprisingly difficult and there have been many attempts in the last 15 years by researchers that have failed to correctly provide both properties TP1 and TP2. Some researchers have avoided the problem by employing a control algorithm that doesn't require TP2 for convergence. However, [1] points out that it is necessary to address ERV puzzles to preserve user intention correctly, and only the solutions in [1] and [2] have addressed the ERV puzzles.

The solutions that appear in [1] (SDT) and [2] (SDTO) appear correct but are quite complex and this paper describes a far simpler solution. Importantly the proposed approach leads to a far more economical implementation, and doesn't require a change to the control algorithm as required by both [1] and [2].

Note firstly that (in System 1 or 2) we have a working solution that satisfies both TP1 and TP2 when we limit ourselves to insertion operations only. It seems that delete operations are the "fly in the ointment". This leads to the following central idea: to imagine that all delete operations on the document have been disabled! The result would be that the document contains all characters that have ever been inserted into the document. The useful thing here is that we get a total ordering on all characters. This forms the basis of correctly determining the effects relation between any two operations.

Definition: Let the Effects Document refer to the (hypothetical) document obtained at a given site assuming all delete operations have been disabled so that the document contains all characters that have ever been inserted by operations.

The Effects Document is only a theoretical tool - it is not actually stored. For each operation we keep track of both the position p in the normal document (in which deletes are allowed to take effect) as well as the position q in the Effects Document (in which all delete operations are ignored). The effects relation is then as simple as comparing q positions instead of p positions. The "false ties" according to [1] are precisely the cases where p positions are tied but q positions are not.

So by comparing q positions, we correctly determine when one operation is to the left of another, avoiding the problem of prematurely resorting to site ids to break the tie. This is used to update both the p and q positions as required. Note that because delete operations never occur on the Effects Document, a q position is never shifted to the left.

Let each operation contain the following fields

Let ins(p,q,c) represent the operation to insert character c at the given p-position and q-position. Let del(p,q) represent the operation to delete the character at the given p-position and q-position. Let ~del(p,q) represent a disabled deletion operation. Insertion operations cannot be disabled.

Analysis using cells

The following sections provide an analysis using our "cells".

Insert with insert

Cells 5,6 account for transforming insertion operations with insertion operations, and are analogous to cells 1,2 described previously. Note that only the q-position is tested, while both the p-position and q-position are shifted.

Delete with insert

In cell 7 we have a delete on the left of an insert, causing the insertion position to be shift to the left. Note that the p-position is adjusted, but not the q-position.

In cell 8 we have an insert on the left of a delete, causing the deletion position to be shifted to the right. Note that both the p-position and q-position are shifted.

Delete with delete

In cell 11 we have a delete on the left of an delete, causing the deletion on the right to shift to the left. Note that the p-value is adjusted, but not the q-value.

In cell 12 we have two delete operations that delete the same character. Both of the operations are disabled after transformation.

TODO: Need cells for delete against delete when one or both of the operations are already disabled.

Algorithm

The following tables provide the implementations of IT, ET (in C++) based on the type of operations O₁ and O₂.

Comments on use of enable flag

This algorithm makes use of an enable flag to avoid deleting a character twice. Note that the first operation in a linear history buffer to delete the character is enabled, and all subsequent delete operations are disabled. Therefore, sites may disagree about which operation actually deleted the character! This is reasonable because we are only interested in convergence of the final document state.

Alternative exposition

Definition 1: For operation O, let shiftp(O) and shiftq(O) be defined as follows

Definition 2: For operations O₁, O₂, let O₁ < O₂ (meaning O₁ is on the left of O₂) be defined as follows

O₁ < O₂ = (O₁.q < O₂.q) ∨ (O₁.q = O₂.q  O₁.ins  (O₂.del ∨ O₁.id < O₂.id))

Algorithm

IT(O1,O2)
{
    if (O2.enabled && !O1.ins && !O2.ins && O1.q == O2.q && O1.enabled)
    {
        O1.enabled = false;
    }
    else if (O2 < O1)
    {
        O1.q += shiftq(O2)
        O1.p += shiftp(O2)
    }
}

ET(O1,O2)
{
    if (O2.enabled && !O1.ins && !O2.ins && O1.q == O2.q && !O1.enabled)
    {
        O1.enabled = true;
    }
    else if (O2 < O1)
    {
        O1.q -= shiftq(O2)
        O1.p -= shiftp(O2)
    }
}

Proof of correctness

There is a useful mapping from system 3 to system 2, where delete operations are mapped to tracking operations, and the effects document is mapped to a document in which delete operations are never performed. This immediately gives us two useful results - that convergence of the effects document is achieved, and delete operations correctly track the location of the character within the effects document.

Lemma 1: ET( IT(O₁,O₂), O₂) = O₁

Proof: There are three cases to consider

1. If O₁,O₂ are both enabled delete operations at the same q-position then O₁ is disabled by IT, then re-enabled by ET.
2. Otherwise, suppose O₂ < O₁. Shifts are applied to O₁.p and O₁.q. Now shiftq(O₂) ≥ 0, therefore O₁.q can only be shifted further to the right. Therefore O₂ < O₁ must continue to hold after IT. Therefore under ET the shifts that were applied to O₁.p, O₁.q will be reversed.
3. Otherwise not O₂ < O₁. Then under IT O₁ is not modified. Similarly under ET O₁ is again not modified.

In all cases we have established the result.

Note also, that ET doesn't upset the order relation between operations either. Proof?

Lemma 2: Assuming operations on a single text document, the < relation on operations is anti-symmetric. i.e. O₁ < O₂ ⇒ ¬ (O₂ < O₁)

Proof: Suppose not i.e. O₁ < O₂ and O₂ < O₁. Now O₁.q < O₂.q contradicts O₂ < O₁. Similarly O₂.q < O₁.q contradicts O₁ < O₂. Therefore O₁.q = O₂.q. Hence O₁.ins ∧ (O₂.del ∨ O₁.id < O₂.id) and also O₂.ins ∧ (O₁.del ∨ O₂.id < O₁.id). So O₁.id < O₂.id and O₂.id < O₁.id. This contradicts a total ordering on the site identifiers.

Lemma 3: Assuming operations on a single text document and O₁,O₂ are not deleting then same character then < relation defines a total ordering.

Proof: Suppose not. i.e. ¬ (O₁ < O₂) and ¬ (O₁ < O₂). Now O₁.q < O₂.q contradicts ¬ (O₁ < O₂). Similarly O₂.q < O₁.q contradicts ¬ (O₁ < O₂). Therefore O₁.q = O₂.q. So ¬(O₁.ins ∧ (O₂.del ∨ O₁.id < O₂.id)) and also ¬(O₂.ins ∧ (O₁.del ∨ O₂.id < O₁.id)). Therefore O₁.del ∨ (O₂.ins ∧ O₂.id < O₂.id) and O₂.del ∨ (O₁.ins ∧ O₁.id < O₂.id). From the first condition, if O₁ is an insert then O₂ must be an insert. From the second condition if O₂ is an insert then O₁ must be an insert as well. Therefore we can't have an insert and a delete. If O₁, O₂ are both inserts then we obtain a contradiction because of the total ordering on site identifiers. If O₁, O₂ are both deletes then they must be deleting the same character because O₁.q = O₂.q which contradicts assumption.

Lemma 5: At quiescence, convergence of the effects document is achieved.

Proof : Only insert operations cause changes to the effects document. Furthermore, when an insert operation O₁ is transformed against a delete operation O₂, O₁.q is not adjusted. Therefore the presence of delete operations has no effect on the q-positions of the insert operations.

This shows that the solution can be mapped to the simpler system where the document state is related to the effects document, document positions are related to q-positions, and there are only insert operations.

So assuming the simpler system (with only insert operations) achieves convergence, we demonstrate convergence of the effects document as required.

Lemma 6: At quiescence, convergence of the document is achieved.

Proof: This follows from lemma 5 which shows that the effects document converges at all sites, and from lemma 4 which shows that delete operations track correctly in the effects document.

Lemma 7: Characters in the document appears in the same order as the effects document

Lemma 8: IT and ET preserves the intention of the user, according to CSM defined in [1].

Proof: TODO

Generation of operations

When generating an operation it is necessary to correctly initialise both the p-position and q-position stored in the operation. To support this it is necessary to be able to map from p-position to q- position. Therefore a document needs to maintain information about where characters have been deleted. An efficient implementation can store run-length encoded information. However, for the purposes of easily understanding the requirements, consider that an array B[] of booleans flags is stored, indexed by q-position. Let B[q] be false to indicate that the qth character has been deleted, otherwise B[q] = true.

To generate an operation to delete the pth character, we calculate the q-position as follows

int Getq(int p)
{
    int n = B.size();
    int pi = 0;
    for (int i=0 ; i < n ; ++i)
    {
        if (B[i])
        {
            if (pi == p)
            {
                return i;
            }
            ++pi;
        }
    }
    return n;
}

When operation O = del(p,q) is executed, B[] is updated as follows

void UpdateBForDelete(int p,int q)
{
    B[q] = false;
}

When operation O = ins(p,q,c) is executed, B[] is updated as follows

void UpdateBForInsert(int p,int q)
{
    B.insert(B.begin() + q, true);
}

Note that the q-positions (not the p-positions) stored within the operation are used to update B.

References

[1] Du Li and Rui Li. Ensuring consistency in real-time group editors. ACM Transactions on Computer-Human Interaction, April 2004. Under review.

[2] Du Li and Rui Li. An Operational Transformation Algorithm and Performance Evaluation. Journal of CSCW, July 2005. Under review.

SingleCharInsertOrDeleteOp.h

Deprecated source: /ceda-implementation/ceda-core-libs/deprecated/Operation/src/OpTransTest/src/Ops/SingleCharInsertOrDeleteOp.h

SingleCharInsertOrDeleteOp.cpp

Deprecated source: /ceda-implementation/ceda-core-libs/deprecated/Operation/src/OpTransTest/src/Ops/SingleCharInsertOrDeleteOp.cpp