50 Composite operations on a text field

Atomic operation

An atomic operation is associated with particular (s,t) - i.e. an opid. Although it can represent arbitrary changes to objects in the Universal Tree (UT), in practise the changes tend to be rather minor.

// Identifies atomic operation op(s,t)
struct Opid
{
    SiteId s;
    int t;
};

Composite operation

A composite operation or delta is associated with a set of atomic operations bounded by a pair of causally valid vector times v1,v2. The delta corresponds to the operations in X(v2)\X(v1), which we denote as [v1,v2).

All the changes made on a working set relative to the state associated with the base vector time are recorded in a delta for certain [v1,v2). We assume v1 = {} - i.e. we assume that the vector time is reset to empty at the base vector time associated with a certain state recorded in a repository.

Composite operations on a text field

Definition: Let a composite operation on a text field be represented by the triple (I,D,B) where:

• I is a linear list of non-overlapping insertion intervals, expressed in post-insertion q-coordinates

  // Insertion of n characters at position q with temporal index u by operation op(s,t)
  struct InsertionInterval
  {
      Opid opid;
      int q, n, u;
  };

• D is a linear list of non-overlapping deletion intervals, expressed in post-insertion q-coordinates

  // Deletion of n characters at position q by operation op(s,t)
  struct DeletionInterval
  {
      Opid opid;
      int q,n;
  };

• B is the string of characters corrresponding to I\D

Conceptually the deletes are applied after the inserts (indeed D can delete some or all of the characters inserted by I). Both I and D are recorded in post-insertion q-coords.

Mapping from q to p coordinates

The recorded deletions serve the purpose of recording the mapping between p and q coordinates (in previous implementations that was recorded explicitly in the PtoQ map).

Let |S| denote the cardinality of set S. If we interpret the deletion intervals D as a subset of the integers - i.e. the set of q-positions which are tombstones, then we can define the function which maps q to p as follows:

D.getp(q) = q - |[0,q) ⋂ D|

In algorithms where we process q-positions of intervals from left to right, Monotone increasing extents on interval set provides an efficient basis for calculating the cardinality of [0,q) ⋂ D.

Taking an RFactor

Let

(I',D',B') = Rf(I,D,B,v)

be the RFactor of (I,D,B) with respect to vector time v.

Let's write this as:

I' = Rf_i(I,v)
D' = Rf_d(D,v)
B' = Rf_b(I,D,B,v)

The q-coordinates of both insertions and deletions are unchanged in an RFactor - because both are expressed in post-insertion coords.

I' = Rf_i(I,v) simply involves picking intervals in I outside X(v). No adjustments to the q-positions are required. Similarly for D' = Rf_d(D,v).

field_RFactor(B,I\D,v) assumes B is a buffer of characters corresponding to I\D. So it can be assumed B.size() == (I/D).extent(). This function calculates B' which corresponds to I'\D where I' = insertion_RFactor(I,v).

Taking an LFactor

insertion_Lfactor(I,v) involves picking the intervals inside X(v) and applying a negative shift according to the total extent of the intervals outside X(v) to the left of that interval.