68
3.4 Persistent addressing
In Section 3.3 we simply assumed, when we needed to, that we can construct a total or-
dering on the points that define the zones of effect of an operation, which will be sensible
for each operation, even when combined with other operations that cause changes in the
order of the sequence. This section describes the basic idea behind this ordering, and ex-
plores some of the implications of its existence. As with the other descriptions in this chap-
ter, the goal is insight; the precise definitions are part of Chapter 4’s formal model.
3.4.1 The basic principle
The fundamental idea of the global address space is to imagine that there is an address
for every point that could exist in anyversion of the sequence. This means that each opera-
tion that could affect a sequence can only create new addresses, and not re-order or delete
old ones. When a set of operations is interpreted to create a particular state of a sequence,
many of the global addresses contain a null substring, and do not correspond to any content
in that state of the sequence. These addresses designate the places where text was deleted,
or the source of active move operations: they can be thought of almost as the ghosts of sub-
sequences that used to exist in a
particular place, but do so no
more.
Figure 3.2 shows two changes,
each applied to the same base
sequence, and then shows the set
of addressable points when those
changes are included in a docu-
ment. The lower sequence repre-
sents the underlying address
ABCDEABCF
ABCDEF
C2
ABCDEABCF
ABCDEF
M3
F F F F iii ig g g gu u u ur r r re e e e 3333....2222:::: Some move and copy changes and their re-
sults
3.4 Persistent addressing
In Section 3.3 we simply assumed, when we needed to, that we can construct a total or-
dering on the points that define the zones of effect of an operation, which will be sensible
for each operation, even when combined with other operations that cause changes in the
order of the sequence. This section describes the basic idea behind this ordering, and ex-
plores some of the implications of its existence. As with the other descriptions in this chap-
ter, the goal is insight; the precise definitions are part of Chapter 4’s formal model.
3.4.1 The basic principle
The fundamental idea of the global address space is to imagine that there is an address
for every point that could exist in anyversion of the sequence. This means that each opera-
tion that could affect a sequence can only create new addresses, and not re-order or delete
old ones. When a set of operations is interpreted to create a particular state of a sequence,
many of the global addresses contain a null substring, and do not correspond to any content
in that state of the sequence. These addresses designate the places where text was deleted,
or the source of active move operations: they can be thought of almost as the ghosts of sub-
sequences that used to exist in a
particular place, but do so no
more.
Figure 3.2 shows two changes,
each applied to the same base
sequence, and then shows the set
of addressable points when those
changes are included in a docu-
ment. The lower sequence repre-
sents the underlying address
ABCDEABCF
ABCDEF
C2
ABCDEABCF
ABCDEF
M3
F F F F iii ig g g gu u u ur r r re e e e 3333....2222:::: Some move and copy changes and their re-
sults
