19.5 Applying operations

Constructing an original operation

Let S be the effects-document set on which an original operation is generated, and let id be its OpId. Every interval initially generated for that operation has opid=id. An atomic original edit is represented as follows:

• A create contains a non-empty new string and its insertion position.
• A delete contains a non-empty interval of present characters selected from S, including its document, position and matching string.
• A move contains a non-empty interval of present characters selected from S, a destination, and e=0.

The stored coordinates must then satisfy the coordinate systems defined above. In particular, creation positions are post-creation; deletion positions are post-creation; and both positions of a move are in the common state after creations and all move insertions. For a same-document atomic move whose destination is at or before its source, inserting the destination shifts the stored xq to the right by the length of the move. A destination after the source already has its post-insertion value. A move between documents needs no source adjustment for its destination insertion.

A compound original operation may be constructed by generating atomic edits serially against the state produced by their predecessors and information-preserving merging them in that order. All such atomic pieces use the same enclosing and interval OpId. This is the construction used by the tests; direct construction is equivalent if it produces the same interval families and satisfies all conditions below.

Applicability

An operation is applicable to an effects-document set S when all representation invariants hold and the following conditions hold at each stage of [C D I X] application:

• Every document named by the operation exists in S.
• Every insertion position is a valid boundary in its document at the stage at which it is used.
• Every deletion or move-extraction interval lies within its document and its stored string equals the effects characters in that span.
• The characters of each extraction span are present. For an alias group this condition is checked once for the common span, before applying its enabled member.
• Every move object occurs exactly once in its destination's insertion list and exactly once in its source's extraction list.

These are caller preconditions. Applying an operation outside this domain is undefined; assertions in the reference code diagnose some violations but are not the definition of applicability.

Application algorithm

Applying an operation has four phases, in this order:

1. Apply creations. Insert characters that are present and not deleted.
2. Apply deletions. Set the deletion flag, if it is not already set.
3. Apply move insertions. Insert destination characters with deletion clear. They are present exactly when the move has e=0.
4. Apply move extractions. For each move with e=0, clear presence at the source and transfer its deletion flags to the destination.

Applying an operation O=[C D I X] follows that order: creations, deletions, move insertions, then move extractions. The C, D and I stages are independent between documents, so the implementation completes them document by document. The X stage is a separate global pass: every possible move destination in every document must exist before any source transfers its deletion state.

Creation intervals insert present, undeleted characters. A deletion interval must identify present characters containing its recorded string; setting their deletion flags is idempotent. A move insertion is present exactly when e=0.

During the extraction pass the source is checked once at the head of each alias group. At most that head can be enabled because aliases have increasing e. An enabled move clears source presence and transfers each set deletion flag to the corresponding destination character.

void Operation::Apply(EffectsDocumentSet& ds) const
{
    for (const auto& [doc, di] : documents)
    {
        const CreateInterval* c = di.c;
        while (c)
        {
            ds[doc].Insert(c->iq, c->str, true);
            c = c->nextI;
        }

        const DeleteInterval* d = di.d;
        while (d)
        {
            assert(d->xdoc == doc);
            assert(ds[doc].IsPresent(d->xq, d->str));
            for (int j = 0; j < d->size(); ++j)
                ds[doc].SetDeleted(d->xq + j, true);
            d = d->nextX;
        }

        const MoveInterval* i = di.i;
        while (i)
        {
            assert(i->idoc == doc);
            ds[doc].Insert(i->iq, i->str, i->e == 0);
            i = i->nextI;
        }
    }

    // Every move insertion in every document now exists.
    for (const auto& [doc, di] : documents)
    {
        const MoveInterval* previous = nullptr;
        const MoveInterval* x = di.x;
        while (x)
        {
            assert(x->xdoc == doc);
            if (!previous || x->xq != previous->xq)
                assert(ds[doc].IsPresent(x->xq, x->str));

            if (x->e == 0)
            {
                ds[doc].Remove(x->xq, x->size());
                for (int j = 0; j < x->size(); ++j)
                {
                    int xq = x->xq + j;
                    int iq = x->iq + j;
                    if (ds[doc].IsDeleted(xq))
                    {
                        ds[doc].SetDeleted(xq, false);
                        ds[x->idoc].SetDeleted(iq, true);
                    }
                }
            }

            previous = x;
            x = x->nextX;
        }
    }
}

The displayed code removes tracing and conditional compilation around diagnostic variables, but its algorithm and execution order are identical to the tested reference implementation.