19.13 Relationship to a repository representation

The algorithm specified in this chapter represents operations relative to a particular input state. The original work also considered a repository that stores the merged effect of every operation since initially empty effects documents. That special initial state simplifies the declarative extraction rule.

Because no working character is present in the empty initial state:

x(S,w) = ecreate(w)

Every move can therefore refer directly to the unique creation interval that introduced its working characters. The historical paper proposed the following related representation:

struct Insert
{
    SiteId s; int t;
    Insert *prevI, *nextI;
};

struct Create : Insert
{
    String str;
    set<OpId> deleted;
    Move* firstX;
};

struct Move : Insert
{
    Create* srcCreate;
    Move *prevX, *nextX;
};

Only creation intervals store character strings. A move reaches the original string through srcCreate. Pure deletions are stored as operation identifiers on the creation, and deletion takes precedence over movement. All moves of one created interval form an e-ordered extraction list headed by that creation.

For a vector time v, the first move in that list whose timestamp is included by v gives the character's location; if none is included, the creation location does. This suggests a repository can derive positions as functions of vector time rather than storing ordinary q-positions.

History-buffer suffix

The proposed repository operation grows as a collaboration proceeds. Given a reconnecting site's vector time, it should be decomposable into [O1,O2], where O1 is exactly in that context and O2 is the suffix required to bring the site up to date. The same suffix can transform incoming operations, and can itself be progressively decomposed as received contexts increase.

This repository representation and suffix decomposition were design directions in the original paper, not implemented parts of Operation. They are retained here to distinguish them from the fully specified state-relative CDM algorithm rather than silently presenting them as completed functionality.