66
that option is not necessarily practical, and in any case, for most off-line editing situations
the variation in merge effects is unlikely to be functional. For example, consider two col-
laborators merging changes separately prepared over a week of disconnected operation: the
precise time an edit was created is almost sure to be irrelevant.
A second method is simply to order the changes in some purely arbitrary way. Lexico-
graphically ordering the changes based on some well-known representation provides a sim-
ple, easily distributed way to determine the ordering of two changes.
While both of the foregoing are possible, and have their potential advantages, we will be
choosing a different ordering, based on the structure of the sequence in question. We will
order changes with respect to each other based on their position within the sequence itself.
The key is to consider the interaction of move operations that overlap. In the case that two
move source regions intersect, but neither is completely contained in the other, any order-
ing is as good as any other. However, if one source region is completely contained in the
other, then the inner region should have priority. This is important, because the containing
region would convert move of the contained region into a NOP by claiming all of its content.
The best solution is one where “smaller” operations take priority and can be freely combined
with larger ones.
3.3.4 Global conflicts
The global conflicts are those that involve cyclic relationships between the regions of ef-
fect of a set of changes, so that a conflict exists only when the entire set of changes is con-
sidered, but the removal of even one of the constituent changes would eliminate the con-
flict, by breaking the cycle. It is simplest to consider the degenerate case, a single change
(either a copy or a delete) whose destination region is insideits source region. (See Figure).
In the case of a copy, we get an infinite document if we attempt to honor the general policy
of having the source region reflect all updates within it. In the case of a move, we end up
that option is not necessarily practical, and in any case, for most off-line editing situations
the variation in merge effects is unlikely to be functional. For example, consider two col-
laborators merging changes separately prepared over a week of disconnected operation: the
precise time an edit was created is almost sure to be irrelevant.
A second method is simply to order the changes in some purely arbitrary way. Lexico-
graphically ordering the changes based on some well-known representation provides a sim-
ple, easily distributed way to determine the ordering of two changes.
While both of the foregoing are possible, and have their potential advantages, we will be
choosing a different ordering, based on the structure of the sequence in question. We will
order changes with respect to each other based on their position within the sequence itself.
The key is to consider the interaction of move operations that overlap. In the case that two
move source regions intersect, but neither is completely contained in the other, any order-
ing is as good as any other. However, if one source region is completely contained in the
other, then the inner region should have priority. This is important, because the containing
region would convert move of the contained region into a NOP by claiming all of its content.
The best solution is one where “smaller” operations take priority and can be freely combined
with larger ones.
3.3.4 Global conflicts
The global conflicts are those that involve cyclic relationships between the regions of ef-
fect of a set of changes, so that a conflict exists only when the entire set of changes is con-
sidered, but the removal of even one of the constituent changes would eliminate the con-
flict, by breaking the cycle. It is simplest to consider the degenerate case, a single change
(either a copy or a delete) whose destination region is insideits source region. (See Figure).
In the case of a copy, we get an infinite document if we attempt to honor the general policy
of having the source region reflect all updates within it. In the case of a move, we end up
