19.4 Character identity, moves and aliased extractions

Why extraction intervals may alias

Information-preserving closure under merge requires an operation to retain several deletes or moves that reference the same effects characters. Their extraction intervals therefore occupy the same document span. This is called aliasing.

Characters are aliased only at post-operation locations. The extraction of the enabled move itself does not alias another extraction that still describes the character at an earlier location; such an extraction must track to the character's new location.

Chained moves

Let Da, Db and Dc be three locations for the same contiguous range. Let O1 move it from Da to Db, and let O2 subsequently move it from Db to Dc. The merged operation moves directly from Da to Dc.

Two chained moves through A, B and C merging into moves with a common extraction at A

The merge still preserves two distinct move identities, but its internal representation is not a time-ordered sequence. The extraction of O2 is exclusion-transformed backward through O1, causing both moves to alias the original extraction location Da. Their e values record which destination is enabled.

Why aliasing cannot be avoided

Three concurrent moves showing why a transformed merged operation needs aliased extractions

Let O1, O2 and O3 concurrently move the same character to different locations, with increasing operation identifiers. Let O3'=IT(O3,O2). Merge the serial sequence [O2,O3'], then transform that composite against O1. The result must retain two disabled move extractions, and both must track to the destination selected by O1. One extraction interval cannot preserve both move identities. Therefore information-preserving merge requires aliased extraction intervals.

Working and effects characters

Definition:
A w-character is a character originally inserted by one operation. It retains this identity as it moves. At any time it occurs at no more than one location in the working documents. After its creation, precisely one effects character associated with it is present, whether or not it is deleted.
Definition:
An e-character is a character at a particular location in a particular effects document. Effects characters in different locations are distinct even when they represent the same w-character. Inserting other characters shifts an e-character without changing its identity.

Identity sets and mappings

Definition:
For a state S, E(S) is the set of all e-characters across all effects documents, and W(S) is the set of all w-characters present in S, including those marked as deleted.
Definition:
For an e-character e, wchar(e) is its associated w-character.
Definition:
For a w-character w, ecreate(w) is the unique e-character at which w was originally inserted by a create operation.
Definition:
For w in W(S), echar(S,w) is the unique e-character associated with the current position of w in state S.
Definition:
For e-characters e1 and e2, write e1 ~ e2 when wchar(e1)=wchar(e2). This is an equivalence relation over e-characters representing the same w-character.

Declarative extraction rule

Let operation O be applied to state S, and let w be involved in one or more moves or deletions recorded by O. Every extraction for w must refer to the same well-defined e-character: 

if w is in W(S):   x(S,w) = echar(S,w)
otherwise:        x(S,w) = ecreate(w)

Thus an operation may contain several extraction intervals for one w-character, but they alias one effects location. Transformation tracking preserves this rule when a concurrent enabled move changes that location. Merge applies it to remove chains of moves.

Ordering competing moves

Aliased move extractions are sorted by strictly increasing e. When concurrent groups are transformed, equal e positions are ordered by site identifier. When serial groups are merged or transposed, their causal order determines the equality case. This total order makes the first interval the unique possible winner and permits a linear merge-like algorithm.

Representation invariants

Partial aliasing is not a valid stored form. Transformations split intervals until overlapping spans are exactly equal or disjoint.

Aliased move extraction intervals ordered by e-coordinate
  1. Document identifiers and positions are non-negative; every interval is non-empty.
  2. Every list head has a null previous link and every adjacent pair has reciprocal links.
  3. In a document-map entry for doc, every deletion has xdoc=doc, every move insertion has idoc=doc, and every move extraction has xdoc=doc. The entry itself supplies the destination document of each creation.
  4. C and I are ordered and non-overlapping.
  5. D and X are ordered and their overlaps are exact aliases.
  6. Deletion aliases have equal strings and non-decreasing site identifiers.
  7. Move aliases have equal strings and strictly increasing e values.
  8. Every move object appears once through I links and once through X links.