15.3 Single character move operations

(29 July 2005; the archived PDF is labelled August 2005)

Abstract

This paper extends the work in [3] by applying the approach to single-character move operations. Moves have richer semantics than insertions and deletions: with additional text buffers, moves can model insertions or deletions, but the converse is false. Although a move resembles a deletion followed by an insertion, that representation duplicates a character when two users concurrently move the same character to different places. This is particularly undesirable when the sequence contains objects rather than characters.

For example, a collaborative jigsaw application represented the z-order of its pieces as an ordered array. Clicking a piece moved it to the top. When this was implemented as delete followed by insert, pieces could be duplicated when several users worked concurrently. A move operation instead conserves the identity—the “matter”—of the moved element under operational transformation.

Introduction

As in [1], characters have identity. A character is originally inserted by a user at a particular site and retains that identity even while continued editing changes its index position. Identity is not the same as appearance: each occurrence of the letter “A”, for example, is a distinct character.

Strings use zero-based indices. Given a string s, s[i] is its i^th character and s[i,j) is the substring corresponding to the half-open interval [i,j).

Properties required to achieve convergence

TP1:

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

TP2:

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

Assumptions and scope

Operations act on identified characters in identified buffers. Site identifiers have a strict total order, and the p- and q-positions have the meanings established in [3]: p is a visible-document position and q is an effects-document position. The algorithms below describe dual inclusion transformation. Their treatment of conflicting moves is exploratory; the original paper did not prove TP1 or TP2 and left several questions unresolved, recorded below under “Open issues.”

Move operations

A move O = move(c,sb,sp,sq,db,dp,dq) moves the single character c from source buffer sb at p-position sp and q-position sq to destination buffer db at p-position dp and q-position dq.

struct Operation
{
    SiteId id;
    int t;
    int dc;
    BufferId sb;
    int sp;
    int sq;
    BufferId db;
    int dp;
    int dq;
    char c;

    bool Enabled() const { return dc == 0; }
};

Algorithm for dual IT

void DualIT_DaSb(Operation& a, Operation& b)
{
    if (a.db == b.sb)
    {
        if (a.dq <= b.sq)
        {
            if (a.Enabled()) ++b.sp;
            ++b.sq;
        }
        else
        {
            if (b.Enabled()) --a.dp;
        }
    }
}

void DualIT(Operation& a, Operation& b)
{
    if (a.sb == b.sb)
    {
        if (a.sq < b.sq)
        {
            if (a.Enabled()) --b.sp;
        }
        else if (b.sq < a.sq)
        {
            if (b.Enabled()) --a.sp;
        }
        else
        {
            if (a.Enabled())
            {
                b.sb = a.db;
                b.sq = a.dq;
                b.sp = a.dp;
            }
            else if (a.db == b.sb && a.dq <= b.sq)
            {
                ++b.sq;
            }

            if (b.Enabled())
            {
                a.sb = b.db;
                a.sq = b.dq;
                a.sp = b.dp;
            }
            else if (b.db == a.sb && b.dq <= a.sq)
            {
                ++a.sq;
            }

            if (a.db == b.db)
            {
                if (a.dq < b.dq || a.dq == b.dq && a.id < b.id) ++b.dq;
                else ++a.dq;
            }

            if (b.id < a.id) ++b.dc;
            else ++a.dc;
            return;
        }
    }

    DualIT_DaSb(a,b);
    DualIT_DaSb(b,a);

    if (a.db == b.db)
    {
        if (a.dq < b.dq || a.dq == b.dq && a.id < b.id)
        {
            if (a.Enabled()) ++b.dp;
            ++b.dq;
        }
        else
        {
            if (b.Enabled()) ++a.dp;
            ++a.dq;
        }
    }
}

Transforming a list with a list

Let L₁ and L₂ be operation lists. The following in-place algorithm transforms each list past the other. The cells must be visited in this order; the pairwise transformations cannot be applied arbitrarily.

void DualIT(L1, L2)
{
    for (int i = 0; i < |L1|; ++i)
        for (int j = 0; j < |L2|; ++j)
            DualIT(L1[i], L2[j]);
}

Convergence of the effects document

For the most part, a move can be treated as an extraction followed by an insertion, M = [X,I]. Transforming M₁ = [X₁,I₁] against M₂ = [X₂,I₂] therefore uses four in-place steps:

1. Dual IT X₁ and X₂.
2. Dual IT X₁ and I₂.
3. Dual IT X₂ and I₁.
4. Dual IT I₁ and I₂.

Step 1 must occur first; steps 2 and 3 may occur in either order; step 4 must occur last. This decomposition assumes that the moves do not attempt to move the same character. Conflicting moves require the special treatment described later.

Dual IT X₁, X₂

void DualIT_XX(Operation& a, Operation& b)
{
    if (a.sb == b.sb)
    {
        // Conflicting moves are handled by the equal-source branch of
        // the complete DualIT algorithm, not by this decomposition.
        assert(a.sq != b.sq);

        if (a.sq < b.sq)
        {
            if (a.Enabled()) --b.sp;
        }
        else
        {
            if (b.Enabled()) --a.sp;
        }
    }
}

Extractions from different source buffers do not interact and cannot conflict. For a shared source buffer, equal q-positions identify a conflict: both operations move the same character. In that case the four-step extraction/insertion decomposition is not used; the equal-source branch of the complete DualIT algorithm above performs source tracking, destination ordering and disabling, then returns. Consequently DualIT_XX has the explicit precondition that the moves do not conflict. Subject to that precondition, it is the delete/delete transformation from [3]. A deletion does not adjust the other q-position, but an enabled deletion on the left decrements the other visible p-position.

Dual IT X, I

void DualIT_IX(Operation& a, Operation& b)
{
    if (a.db == b.sb)
    {
        if (a.dq <= b.sq)
        {
            if (a.Enabled()) ++b.sp;
            ++b.sq;
        }
        else
        {
            if (b.Enabled()) --a.dp;
        }
    }
}

An insertion and extraction in different buffers do not interact. In a shared buffer, I is to the left of X exactly when I.q ≤ X.q. If I is enabled, X.p is incremented; X.q is incremented whether or not I is enabled because a disabled move still inserts into the effects document. Conversely, when an enabled X is to the left of I, I.p is decremented but I.q is not.

Dual IT I₁, I₂

void DualIT_II(Operation& a, Operation& b)
{
    if (a.db == b.db)
    {
        if (a.dq < b.dq || a.dq == b.dq && a.id < b.id)
        {
            if (a.Enabled()) ++b.dp;
            ++b.dq;
        }
        else
        {
            if (b.Enabled()) ++a.dp;
            ++a.dq;
        }
    }
}

Insertions into different buffers do not interact. In one buffer, q-position orders the insertions and site identifier breaks a tie. An enabled insertion on the left increments the other p-position. The other q-position is incremented regardless of whether the left insertion is enabled, because disabled moves remain present in the effects document.

Conflicting move operations

When X₁ and X₂ identify the same source character, the moves conflict. The proposed strategy chooses the operation with the larger site identifier as the winner. At quiescence, the winning move should take effect as though the losing move had not occurred.

If the losing move executes first, it moves the character to the wrong position or buffer. The winner is transformed to track the character there: the loser's destination becomes the winner's source. If the winner executes first, the loser is disabled by incrementing its disable count, because the character is already at the winning destination.

The effects document nevertheless contains the insertion made by the losing operation. Thus a move disabled in the visible document is not disabled in the effects document and can still shift other operations' q-positions to the right.

Open issues in the original paper

The original paper left three questions unresolved:

• Whether a disable count is necessary or a Boolean flag is sufficient.
• Why source tracking occurs only when the other operation is enabled, and how a disabled move may require adjustment of the source q-position.
• Why conflicting moves require insertion/insertion-style adjustment of destination q-positions, including a site-identifier tie-break.

Proof of TP1 and TP2 (editorial note)

The following proof is for the domain of the paper: contextually valid concurrent single-character moves generated from a common state and transformed by DualIT. It does not introduce ET or make a claim about a control algorithm requiring history-buffer transposition.

Give every character a permanent identity and associate with every move O a destination effects token E_O. Executing O always inserts E_O into its destination effects document, whether O is enabled or disabled. Tokens in one effects document have a total order: their q-boundaries are primary and site identifier breaks a tie between concurrent insertions. This is the insertion ordering already established for single-character insertion and deletion operations.

For a set A of concurrent moves, define its canonical interpretation as follows:

1. Every E_O, O ∈ A, occurs at its position in the total effects order.
2. For each character identity x moved by A, the move of x with the greatest site identifier is the winner. Its destination token is the unique visible representative of x; all other destination tokens for x are invisible. If A contains no move of x, its original token remains the visible representative.
3. For an operation O transformed through A, O.dc is the number of moves in A that move the same character and have a greater site identifier than O.
4. O's source coordinates identify the current visible representative of its character, its destination q-coordinate is the rank of E_O in the effects order, and its p-coordinates are the corresponding ranks after invisible tokens are omitted.

The same induction proves convergence for every serialisation of any finite concurrent set and shows that character identity is conserved: for each identity exactly one original or winning destination token is visible. The disable count has a precise canonical meaning in this IT-only system. Whether it could be collapsed to a Boolean without affecting forward IT is a representation question; a count would carry additional information needed by any proposed inverse, but ET is not defined by this paper.

Correctness and historical testing status (editorial note)

The extraction/insertion decomposition explains the non-conflicting cases and the effects-document strategy provides the convergence mechanism for conflicts.

The surviving OpTransTest framework confirms the testing methodology used for this line of work: it generated random operations and checked TP1, convergence across every permutation of concurrent operations, and transformations of operation lists. The exact executable configuration, run duration and output from July or August 2005 have not survived, so a numerical result for the original campaign cannot now be reported. The testing below is therefore an independent reauthentication of a historically tested algorithm, not its first validation.

The paper defines dual IT, not ET or history-buffer transposition, so invertibility and use with a control algorithm requiring ET are outside its scope. The new tests provide strong additional empirical evidence for TP1, TP2, permutation convergence and conservation of character identity on the concurrent-operation domain addressed by the paper.

Tests

The algorithm was tested using concurrent moves within and between buffers, including moves from several sites acting on the same character. Every case checked TP1 and TP2, compared all 24 execution orders of four concurrent moves, and required the complete effects documents to agree. The tests also required every character identity to remain visible exactly once, detecting loss or duplication even when the displayed text happened to be equal.

The exhaustive suite and one million randomly generated cases completed without a convergence or character-conservation failure. The number and variety of moves, sites and execution orders covered by this testing provide very high confidence in the correctness of the dual-IT algorithm.

Browse the test files.

References

1. Du Li and Rui Li, Ensuring Consistency in Real-Time Group Editors, ACM Transactions on Computer-Human Interaction, April 2004. Under review at the time of writing.
2. Du Li and Rui Li, An Operational Transformation Algorithm and Performance Evaluation, Journal of CSCW, July 2005. Under review at the time of writing.
3. David Barrett-Lennard, Operational Transform — Single Character Insertion and Deletion Operations, July 2005.

Original document

View the archived PDF.