19.3 Coordinate systems

Why coordinates require care

An interval position is meaningful only relative to a state of its effects document. Insertions change the numeric positions of existing effects characters; deletions and move presence changes do not. The algorithms therefore establish explicit coordinate systems in which the required interval comparisons can be made directly.

Deletes must be in post-creation coordinates

Let the initial state contain one present, undeleted character:

Apply O1, which creates b at q=0:

Now apply O2, which deletes that b at q=0:

The deletion can refer to a character created by the same composite operation only if its position is expressed after the creations. Therefore deletion intervals use post-creation coordinates.

Move extractions must account for creations

Again let the initial effects document contain only present character a:

Create b at q=0:

Then move that b from q=0 to q=2:

The extraction can refer to the newly created character only in post-creation coordinates. Creation insertions must therefore be accounted for before move extraction positions are interpreted.

Move coordinates must also be post-move-insertion

A move creates a destination effects interval and changes which copy is present. Applying all move insertions first provides one coordinate system containing every possible destination. Both iq and xq of every move are expressed in that system, before any source presence is changed.

This is required when an enabled move transfers deletion flags: xq+j and iq+j must be simultaneously valid positions. It also allows move sources and destinations from different operations to be compared directly once the algorithms have transformed both insertion sets into the same context.

Post-insertion positions within one document

If a range is moved within one document to a position before its source, inserting the destination shifts the source to the right by the moved length. The recorded extraction position includes that shift:

before insertion:       [ source )
destination:       ^

after insertion:   [ destination ) [ source )
                                   ^ recorded xq

If the destination is after the source, its insertion position is chosen in the original effects document at or after the end of the source; the source position does not shift. Moves between different documents do not create this within-document adjustment.

The e coordinate

Several moves may extract the same characters. Each is treated as inserting one marker into a hypothetical effects document at position e. The coordinates are post-insertion, are strictly increasing within an alias group, and select a unique winner: e=0 is enabled.

    [-----)      [--------) e=0        [--)        [-----)
                 [--------) e=3                    [-----)
                 [--------) e=5                    [-----)
                 [--------) e=6
                 [--------) e=20

Thinking of e values as insertion positions determines how concurrent competing moves are transformed and how serial competing moves are merged. It reduces operations on two alias groups to linear insertion-list scans.

Summary

Information preservation and coordinate order

The order of creates and deletes is part of information-preserving merge. Because deletion positions are expressed in post-creation coordinates, a delete can identify a character created by the same merged operation. If deletes instead came first in pre-insertion coordinates, an insert followed by deletion of the inserted character would disappear from the net state difference. The final text would be unchanged, but the character identity and the two edits would be lost, so a later transformation could not determine how a concurrent edit related to them.

By contrast, Section 13.2, Log Compression Algorithm seeks better compression by representing a state difference in [X I] order, written [-X +I] there. Its deletions, called extractions there, are in pre-insertion coordinates and cannot refer to characters inserted by the same compressed operation. Insert-then-delete pairs can therefore be discarded, retaining only the overall state difference. This resembles squashing commits on a Git branch: the result reproduces the branch's final state, but loses the history needed to combine its individual edits with concurrent edits on another branch. Information-preserving merge accepts less compression so the edits remain composable by IT and ET.