83
Definition 4.1:Each address is a tuple(p, i)wherepis a change path,iis a nonnegative
integer and:
1. A change path,pis a (possibly empty) sequence of change IDsI
1 …I
n ,.
2. The last change ID,I
n (if p is nonempty) denotes an insertion,
3. The indexiis in the interval0…Nwhere N is the length of the sequence inserted by
change I
n .This denotes a position in the sequence of items inserted by the insertion
with ID I
n .
4. No ID may occur more than once in the change pathp.
5. There is only one legal address with a null change path, and it must have an index of
0. This special address,((), 0),is referred to asnil.
6. Each ID in the change path,I
1 …I
n–1 ,must designate move or copy operations. (We
will discuss the effect of these on the ordering of addresses in Section 4.3.2).
The intention behind this addressing system is as follows:
• The first operation made in any document must be an insertion whose target is the spe-
cial address nil.
• An insertion defines an address for each inter-item gap in the sequence that it inserts,
including the positions before the first element (0), and after the last element (N).
• Addresses at the destination of one or more copy and move operations are identified by
the location where an initial insertion occurred. The other elements in the path repre-
sent successive move or copy changes that affected the original address.
• The set of addresses is finite, and does not contain any addresses that would represent
causal “loops”, for instance the results of a move applied to its own destination.
Thus, data is always identified by reference to the original insertion that created it, re-
gardless of what other changes may affect that data. The same contents may have more than
Definition 4.1:Each address is a tuple(p, i)wherepis a change path,iis a nonnegative
integer and:
1. A change path,pis a (possibly empty) sequence of change IDsI
1 …I
n ,.
2. The last change ID,I
n (if p is nonempty) denotes an insertion,
3. The indexiis in the interval0…Nwhere N is the length of the sequence inserted by
change I
n .This denotes a position in the sequence of items inserted by the insertion
with ID I
n .
4. No ID may occur more than once in the change pathp.
5. There is only one legal address with a null change path, and it must have an index of
0. This special address,((), 0),is referred to asnil.
6. Each ID in the change path,I
1 …I
n–1 ,must designate move or copy operations. (We
will discuss the effect of these on the ordering of addresses in Section 4.3.2).
The intention behind this addressing system is as follows:
• The first operation made in any document must be an insertion whose target is the spe-
cial address nil.
• An insertion defines an address for each inter-item gap in the sequence that it inserts,
including the positions before the first element (0), and after the last element (N).
• Addresses at the destination of one or more copy and move operations are identified by
the location where an initial insertion occurred. The other elements in the path repre-
sent successive move or copy changes that affected the original address.
• The set of addresses is finite, and does not contain any addresses that would represent
causal “loops”, for instance the results of a move applied to its own destination.
Thus, data is always identified by reference to the original insertion that created it, re-
gardless of what other changes may affect that data. The same contents may have more than
