60
gencewhensequencestateshavedivergedduetoparallelwork.Theabilitytoarbitrarilyex-
cludeachangeisrequiredtoenableeasyundoingofoperationsduringcollaboration(where
temporalorderingcannotberespected),andtoallowrepairofincorrectmergeresults,when
theautomaticallyconvergedstatedoesnotgivethedesiredresult.Whenaddingchangesto
agivendocumentstate,nostructuralconstraintsontheoperationscanbeassumed,since
theymayhavebeencreatedwithrespecttoverydifferentstatesoftheunderlyingsequence.
Letusfirstconsiderasimpleexampleusingonlytheoperationsofinsertionanddeletion.
Thiscorrespondstothesimplestmodelofchange-orientedediting,asimplementedinthe
internalfileformatofSCCS,Kruskal’sedi-
tor(Kruskal1984),Epos(Munch1993),
theCpreprocessorandothersystems.
Figure3.1showsadiagramofanum-
berofinsertionanddeletionoperationson
astringwhichcontainsonelargeinser-
tion,ofthestring“Thedogworriedatthe
bone.”ThisinsertionhastheId I1.One
versionwouldsimplybethisstring,and
itsspecificationwouldbe“useonlythesetofchanges {I1}."However,severalotherchanges
wereadded,probablyinseparateeditingsessions.Twoofthesedeletetext;D1deletesthe
“w”of“worried”upthroughthe“t”of“at”,and D2deletesfromthesamestartalltheway
thoughthe“e”attheendof“bone”.Insertion I2addsthestring“ate“immediatelyfol-
lowingthespaceafter“dog”,and I3addsthestring“big“rightbeforethe“b”of“bone”.A
numberofpossibleversionsofthestringcanbeobtainedbyselectingdifferentsetsof
changes.Forinstance,theset{I1,I2,D1}represents‘Thedogatethebone.”,whiletheset
{I1,D2}represents“Thedogate.”.
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
61
Thissimplemodelofinsertionsanddeletionsistrivial,butstillhasagreatdealofpower
inexpandingthenumberofmergeandundopossibilitiesforsequenceediting.Itisalsosus-
ceptibleofverysimpleimplementation,simplybytreatingthetreeofinsertionsanddele-
tionsasadatastructure,thatcanbetraversedtoextractanydesiredversionondemand.
Comparingdifferentstatesisalsoeasy,sinceallchangesarerelatedtotheircontextofef-
fect,andastateisspecifiedintermsofitsconstituentchanges.Thesametraversalthatcan
generateaparticularstateofadocumentcanalsogenerateadetailedcomparisonoftwo
statesthatindicatestheexactoperationstakenduringtheeditingprocess.
3.3 Operationalconflicts
Inthissectionweshallexamineallpossibleoperation/operationconflictsandwhatkinds
ofresolutionarepossible.Wewillfirstexamineconflictresolutionintermsoflocalstruc-
turalconfigurations;manyrelativelyunproblematicquestionscanberesolvedpurelyin
theseterms.Then,wewillreconsidertheactualoperations,becausetherearealsomore
complexconflictswhichdependessentiallyontheoperationitself.Localconflictsituations
dependonlyontherelationsofspecificregionsofeffectforanoperation.Globalconflicts
willbeconsideredinSection,butareinstanceswhereanoperationalconflictexistseven
thoughthelocalconflictisofatypethatwouldnormallyhaveasensibleresolution.
Table3.2presentsagridarrangementofthefourtypesofPalimpsestoperation,with
notesastowhichlocalconflicttypestheycanrepresent.
Previous Page Next Page