77
tential solution to these problems as well. Most single-user text editors do not need a merge
operation for normal operation.
The definition of what operations are available is one important component of analyzing
merge facilities. For a differencing algorithm, the precise set of operations significantly af-
fects the time complexity of finding an optimal set of changes. The choice of primitive op-
erations does not affect the performance of a computational process, but rather what choice
of merge operations users get while editing, as well as what variations of merge application
designers can accommodate.
We shall not use the sequential model of changes. Sequential dependencies between
changes mean that changes following an operation must be updated if that operation is un-
done, or if a new operation is added out of sequence. The changes required to update Ellis
and Gibbs’ algorithm to handle collaborative undo (out of sequence updates) are actually
rather complex (Prakash and Knister 1992). We will use a formalism that removes such de-
pendencies at the level of the model. While this creates a less-obvious representation at first
glance, the problems of out-of-sequence representation go away in the new model. The key
to removing sequential dependencies is to change the representation of individual changes
so that they refer only to other changes, rather than to transitional states of the sequence.
This can also be thought of as a replacement of the total sequential temporal ordering of
operations by a causal, partial ordering of operations. This representation makes it easier to
model merge operations as well. The changes in the two versions need not be ordered with
respect to each other, nor will offsets have to be corrected to reflect the new ordering. This
technique not only simplifies the definition of merge behavior and consistency conditions,
but also allows for flexible implementation of merge algorithms.
With such a change representation, versions are just sets of changes that define unique
states of a sequence. Dependencies in the set are reflected in the structure of the changes
themselves, and are detectable by the structural properties of the addresses they use. This
tential solution to these problems as well. Most single-user text editors do not need a merge
operation for normal operation.
The definition of what operations are available is one important component of analyzing
merge facilities. For a differencing algorithm, the precise set of operations significantly af-
fects the time complexity of finding an optimal set of changes. The choice of primitive op-
erations does not affect the performance of a computational process, but rather what choice
of merge operations users get while editing, as well as what variations of merge application
designers can accommodate.
We shall not use the sequential model of changes. Sequential dependencies between
changes mean that changes following an operation must be updated if that operation is un-
done, or if a new operation is added out of sequence. The changes required to update Ellis
and Gibbs’ algorithm to handle collaborative undo (out of sequence updates) are actually
rather complex (Prakash and Knister 1992). We will use a formalism that removes such de-
pendencies at the level of the model. While this creates a less-obvious representation at first
glance, the problems of out-of-sequence representation go away in the new model. The key
to removing sequential dependencies is to change the representation of individual changes
so that they refer only to other changes, rather than to transitional states of the sequence.
This can also be thought of as a replacement of the total sequential temporal ordering of
operations by a causal, partial ordering of operations. This representation makes it easier to
model merge operations as well. The changes in the two versions need not be ordered with
respect to each other, nor will offsets have to be corrected to reflect the new ordering. This
technique not only simplifies the definition of merge behavior and consistency conditions,
but also allows for flexible implementation of merge algorithms.
With such a change representation, versions are just sets of changes that define unique
states of a sequence. Dependencies in the set are reflected in the structure of the changes
themselves, and are detectable by the structural properties of the addresses they use. This
