60
gence when sequence states have diverged due to parallel work. The ability to arbitrarily ex-
clude a change is required to enable easy undoing of operations during collaboration (where
temporal ordering cannot be respected), and to allow repair of incorrect merge results, when
the automatically converged state does not give the desired result. When adding changes to
a given document state, no structural constraints on the operations can be assumed, since
they may have been created with respect to very different states of the underlying sequence.
Let us first consider a simple example using only the operations of insertion and deletion.
This corresponds to the simplest model of change-oriented editing, as implemented in the
internal file format of SCCS, Kruskal’s edi-
tor (Kruskal 1984), Epos (Munch 1993),
the C preprocessor and other systems.
Figure 3.1 shows a diagram of a num-
ber of insertion and deletion operations on
a string which contains one large inser-
tion, of the string “The dog worried at the
bone.” This insertion has the Id I1. One
version would simply be this string, and
its specification would be “use only the set of changes {I1}."However, several other changes
were added, probably in separate editing sessions. Two of these delete text; D1deletes the
“w” of “worried” up through the “t” of “at”, and D2deletes from the same start all the way
though the “e” at the end of “bone”. Insertion I2adds the string “ate “ immediately fol-
lowing the space after “dog”, and I3adds the string “big “ right before the “b” of “bone”. A
number of possible versions of the string can be obtained by selecting different sets of
changes. For instance, the set {I1,I2,D1}represents ‘The dog ate the bone.”, while the set
{I1,D2}represents “The dog ate.”.
The dog worried at the bone.
I1
ate
I2
big
I3
D2
D1
F F F F iii ig g g gu u u ur r r re e e e 3333....1111:::: a set of insertions and deletions
gence when sequence states have diverged due to parallel work. The ability to arbitrarily ex-
clude a change is required to enable easy undoing of operations during collaboration (where
temporal ordering cannot be respected), and to allow repair of incorrect merge results, when
the automatically converged state does not give the desired result. When adding changes to
a given document state, no structural constraints on the operations can be assumed, since
they may have been created with respect to very different states of the underlying sequence.
Let us first consider a simple example using only the operations of insertion and deletion.
This corresponds to the simplest model of change-oriented editing, as implemented in the
internal file format of SCCS, Kruskal’s edi-
tor (Kruskal 1984), Epos (Munch 1993),
the C preprocessor and other systems.
Figure 3.1 shows a diagram of a num-
ber of insertion and deletion operations on
a string which contains one large inser-
tion, of the string “The dog worried at the
bone.” This insertion has the Id I1. One
version would simply be this string, and
its specification would be “use only the set of changes {I1}."However, several other changes
were added, probably in separate editing sessions. Two of these delete text; D1deletes the
“w” of “worried” up through the “t” of “at”, and D2deletes from the same start all the way
though the “e” at the end of “bone”. Insertion I2adds the string “ate “ immediately fol-
lowing the space after “dog”, and I3adds the string “big “ right before the “b” of “bone”. A
number of possible versions of the string can be obtained by selecting different sets of
changes. For instance, the set {I1,I2,D1}represents ‘The dog ate the bone.”, while the set
{I1,D2}represents “The dog ate.”.
The dog worried at the bone.
I1
ate
I2
big
I3
D2
D1
F F F F iii ig g g gu u u ur r r re e e e 3333....1111:::: a set of insertions and deletions