19.1 Effects Document

Logical meaning

An effects document is logically an ordered sequence of triples:

[(character, present, deleted), ...]

The position q of a triple is its zero-based position in this sequence, irrespective of the values of its flags. The flags have separate meanings:

• present says whether this occurrence is the current location of its character;
• deleted says whether the character has been deleted.

The working document is the projection obtained by retaining, in order, exactly those characters for which present && !deleted. Thus a present but deleted character and a non-present character are both absent from the working document, but for different reasons.

Insertions extend the sequence with new triples. A deletion sets deleted rather than removing a triple. A move inserts an occurrence at its destination and clears present at its source. Retaining the other occurrences and deleted characters gives transformations stable effects-document positions and enough information to combine concurrent edits. Convergence is required for the complete sequence of triples, not only for its working-document projection.

Concrete representation

EffectsDocument stores the three components in parallel arrays of equal length:

class EffectsDocument
{
    std::string buffer;
    std::vector<bool> present;
    std::vector<bool> deleted;
};

buffer[q], present[q] and deleted[q] together represent the triple at q. sizeq() is the common length. Inserting characters inserts matching entries into all three arrays and initially clears their deletion flags. Removing characters only clears their presence flags. SetDeleted changes deletion state, and CharExists(q) evaluates present[q] && !deleted[q].

EffectsDocumentSet

Logically, an EffectsDocumentSet is a mapping from DocId to EffectsDocument. Each DocId identifies one text document on which operations may act.

The implementation used by the tests represents this mapping as a vector indexed by DocId:

using DocId = int;

using EffectsDocumentSet = std::vector<EffectsDocument>;