19.2 Operations

OpId

Each site has a unique SiteId. Site identifiers have a stable total order that is the same at every site; the algorithms use that order only to resolve ties between concurrent edits. An OpId identifies the operation with zero-based sequence number t generated at site id. Thus OpId{id,t} identifies the operation written op(id,t) in Section 16.1, Vector Time.

struct OpId
{
    SiteId id;
    int t;
};

For a vector time v, the component v(id) counts the initial sequence of operations generated at site id that belongs to the extent of v: OpId{id,t} is in that extent exactly when t < v(id).

CreateInterval

A CreateInterval represents insertion of the non-empty string str at position iq. The containing Operation::documents entry supplies idoc, the effects document into which the string is inserted. Creation positions are expressed in the common post-creation coordinate system produced after applying all creation intervals in the operation. The prevI and nextI pointers are the backward and forward links used to represent creation intervals as a doubly linked list in increasing iq order.

struct CreateInterval
{
    OpId opid;
    std::string str;
    int iq;
    mutable CreateInterval* prevI;
    mutable CreateInterval* nextI;
};

DeleteInterval

A DeleteInterval represents deletion of the non-empty string str from effects document xdoc at position xq. Deletion marks those characters as deleted; it does not remove them from the effects document. The prevX and nextX pointers link deletion intervals in non-decreasing xq order.

struct DeleteInterval
{
    OpId opid;
    DocId xdoc;
    int xq;
    std::string str;
    mutable DeleteInterval* prevX;
    mutable DeleteInterval* nextX;
};

Deletion intervals alias when concurrent operations delete the same characters, so several intervals refer to the same effects-document span. The site identifier in opid orders intervals within an alias group.

MoveInterval

A MoveInterval represents movement of the non-empty string str from (xdoc,xq) to (idoc,iq). The destination is its insertion interval and the source is its extraction interval. The e value orders moves whose extraction intervals alias; the move with e=0 is enabled.

struct MoveInterval
{
    OpId opid;
    int e;
    DocId idoc;
    int iq;
    DocId xdoc;
    int xq;
    std::string str;
    mutable MoveInterval* prevI;
    mutable MoveInterval* nextI;
    mutable MoveInterval* prevX;
    mutable MoveInterval* nextX;
};

A move interval is allocated once. Its prevI,nextI links place it in the insertion list for idoc, ordered by iq. Its prevX,nextX links simultaneously place the same object in the extraction list for xdoc, ordered by xq and then e. Neither list contains a copy or separate projection.

An update through either list changes the object observed through the other. Moving an object in one list does not disturb its links in the other. Given an interval pointer, insertion or removal next to it changes a fixed number of pointers and is (O(1)).

DocIntervals

A DocIntervals contains the four list heads associated with one effects document:

struct DocIntervals
{
    CreateInterval* c;
    DeleteInterval* d;
    MoveInterval* i;
    MoveInterval* x;
};

The notation O=[C D I X] gives the coordinate order of these four interval families, not merely their names. Creations establish the coordinates used by deletions. Move insertions then establish every possible destination before move extractions transfer presence and deletion state from source to destination. Each family is identified both by its effect and by the stage of the effects document in which its positions are meaningful.

The four lists are homogeneous. Adjacent intervals of the same family are therefore more likely to coalesce, intervals need no run-time type tag, algorithms need no type dispatch, and serialization can process one interval type at a time.

Operation

An Operation has an operation identifier and maps each affected document identifier to its four interval lists. A move between documents is the same MoveInterval object in the destination document's i list and the source document's x list.

struct Operation
{
    OpId opid;
    std::map<DocId, DocIntervals> documents;
};

Every interval retains its string. A creation inserts that string, while deletion and move application use it to verify extraction content.

The enclosing Operation::opid identifies the logical history operation. An interval's opid identifies the original edit from which that interval came. Splitting copies the interval identifier, and transformation does not change it. Merge preserves O1.opid, clears O2.documents while retaining O2.opid, and leaves the identifiers of all retained intervals unchanged. Consequently a composite can contain intervals with several identifiers even though it has one enclosing identifier. Callers that place a composite in a causally indexed history must decide which logical history operation the enclosing identifier represents.

Ownership and copying

An operation owns every interval reachable from its creation, deletion and move-insertion heads. Move objects are destroyed by walking insertion lists only; walking extraction lists as well would delete them twice. Clearing an operation deletes its owned objects, clears the document map and resets its operation identifier.

A deep copy first copies creation and deletion lists. It then walks every move insertion list, allocating each move exactly once and recording a map from old move pointers to new move pointers. In a second pass it walks the original extraction lists and builds the copied extraction lists using that pointer map. This preserves the sharing between the insertion and extraction lists.