67
with a deletion, as the change, like the Ourobouros, swallows its own tail and disappears
(deleting, dutifully, the infinite region in question).
This problem cannot be solved by simply ruling out self-reference, since a copy or delete
cycle can have any number of links. Checking a large set of changes for such cycles is a
rather difficult task at merge time. Furthermore, the indexing required to make the relevant
relationships explicit is not useful for any other task than preventing this sort of conflict.
The geographical order principle allows an elegant solution to the problem. If every point
referred to by each change is linearly ordered, then the cycle problem can be solved without
attempting to perform global cycle detection on a large set of changes
6
. Conceptually, the
state described by a set of changes can be found by simply scanning all possible addresses in
the document from left to right (least to greatest), applying each change as soon as it is en-
countered. This gives priority to the change with the leftmost address. A literal scan of all
possible addresses would be very inefficient, since there can be a very large number of them,
but it is possible to implement this rule without such a literal scan. Any number of other
priority rules could be devised on similar structural principles: the advantage of this one is
that a left-right scan enumerating some number of elements of a sequence is in fact a com-
mon operation in editing scenarios: such a scan must take place whenever a display buffer
needs to be filled or refreshed. This rule also works well in a distributed environment be-
cause it does not require any information other than the changes themselves.
6
Although cycle-detection is a standard problem for which good algorithms are well known, the
graph we are required to check is not explicitly represented in a convenient way. Some form of index
would be required to efficiently determine what changes are “connected” by having the destination
point of one change in the source region of another change. Since this check would have to be per-
formed on every addition of a new change to a sequence, it could quickly become expensive even with
a fast incremental algorithm for determining these connections.
with a deletion, as the change, like the Ourobouros, swallows its own tail and disappears
(deleting, dutifully, the infinite region in question).
This problem cannot be solved by simply ruling out self-reference, since a copy or delete
cycle can have any number of links. Checking a large set of changes for such cycles is a
rather difficult task at merge time. Furthermore, the indexing required to make the relevant
relationships explicit is not useful for any other task than preventing this sort of conflict.
The geographical order principle allows an elegant solution to the problem. If every point
referred to by each change is linearly ordered, then the cycle problem can be solved without
attempting to perform global cycle detection on a large set of changes
6
. Conceptually, the
state described by a set of changes can be found by simply scanning all possible addresses in
the document from left to right (least to greatest), applying each change as soon as it is en-
countered. This gives priority to the change with the leftmost address. A literal scan of all
possible addresses would be very inefficient, since there can be a very large number of them,
but it is possible to implement this rule without such a literal scan. Any number of other
priority rules could be devised on similar structural principles: the advantage of this one is
that a left-right scan enumerating some number of elements of a sequence is in fact a com-
mon operation in editing scenarios: such a scan must take place whenever a display buffer
needs to be filled or refreshed. This rule also works well in a distributed environment be-
cause it does not require any information other than the changes themselves.
6
Although cycle-detection is a standard problem for which good algorithms are well known, the
graph we are required to check is not explicitly represented in a convenient way. Some form of index
would be required to efficiently determine what changes are “connected” by having the destination
point of one change in the source region of another change. Since this check would have to be per-
formed on every addition of a new change to a sequence, it could quickly become expensive even with
a fast incremental algorithm for determining these connections.
