118
supportawiderrangeofaccessandupdateoperations.Interactiveeditorsneedrandomac-
cesstosupportnavigationandtobeabletoretrievesmallerportionsofthesequencetofill
screenbuffers.Applicationsneedtoregisteruseractionsandremoteupdates,incrementally
addingchangestochangesetsrepresentingP-sequences.Finally,supportforsingle-or
multi-userundomeanssupportfortheincrementalremovalofachangefromachangeset.
GivenachangesetU,theuniverse,containingallchangesknownataninstanceofan
application,andchangesetsV
1 , …, V
n ˝ U,weareinterestedinsupportingthefollowing
capabilities:
1. Add(c,U):AddachangectoU.
2. LookupChange(ID,U):findallinformationaboutachangeinU.
3. FetchRange(a
1 , a
2 ,V
i ):Retrievethecontentsofarange(a
1 , a
2 )insomechangesetV
i .
4. AddChange(c, V
i ):UpdateachangesetV
i byaddingachangec.
5. DeleteChange(c, V
i ):UpdateachangesetV
i byremovingachangecfromit.
6. CreateChangeset(c
1 , …, c
k ):CreateanewchangesetV
i fromasetofchanges{c
1 , …,
c
k }.
AswithVTML,wewillassumethatchangesetsareexplicitlyrepresentedobjects:thiswill
allowustobuildincrementalindicesincludingonlytheoperationsinthoseversions,thus
speedingoverallperformance.Thisstrategyallowsustokeeptheruntimedependentonthe
numberofchangesinaversion,ratherthanthetotalnumberofchangesintheuniverse.
Thisispotentiallyausefulsavings,becauseoftheeffectsofuserundoactionsandthose
madetoresolvemergeconflicts.Thesearelikelytoleadtotheremovalofsomeoperations
fromallactiveversionsofinteresttotheuser(andtheseoperationsarealsocandidatesfor
garbagecollection).
TheP-sequencesdefinedbyparticularV
i representthecontentsofsignificantversions.
Theseversionsmaybepermanentrecordsofhistoricalstates,asinatraditionalversioning
system.Alternatively,theymayrepresenttheworkingstateofanapplicationwhichisman-
119
agingasharedartifactbyacceptingandintegratinguserrequestsandupdatesfromother
instances.Ineithercase,thesepersistentchangesetschangeincrementallyratherthanbe-
ingconstructedarbitrarily.Whilearbitraryversionconstructioniscommoninsmesoftware
engineeringapplications(Lie,Conradietal.1989;Munch1993),itisunlikelyinmost
authoringapplications.Whenfullydynamicversionconstructionisbeingused,theoptimiza-
tionofrepresentingexplicitversionsetsisinapplicable.Theoperationsetabovereflectsthe
useofexplicitlyrepresentedversions.ThePalimpsestaddressingmechanismisasignificant
inbothsortsofimplementation,sinceitprovidesawell-orderedsetofkeyswithwhichaux-
iliarystructurescanbebuilttospeedaccessandupdatefunctions.
Thecapabilitiesinitems1and2arerelativelysimple,andprovidetheabilitytolookup
informationaboutachangegivenitschangeID.Lookupofbasicinformationaboutachange
givenitsIDcanbehandledbystandardindexstructuresinlogarithmictimewithoutdiffi-
culty,orevenfasterifhashingmethodsareused.Therestofthelistedcapabilitiesdealwith
findingthecontentsofanarbitrarychangeset,andrepresentthedifficultpartofanimple-
mentation.
Onehighlysignificantissueistrackingtheareasofeffectforoperations.Therearefive
sortsofregionwithsignificancetothePalimpsestchangemodel,mostofwhichrequiresome
specialindexingsupport:
1. Insertionpointsrepresentthedestinationsofinsertoperations:placeswherecon-
stantdataisinserted.
2. Variableinsertionpointsaresimilartoregularinsertionpointssincetheycausethe
additionofnewdata,howeverthatdataisnotnecessarilyconstant.Foracopyop-
eration,theinserteddataalsoappearselsewhere.Foramoveoperation,thesource
dataisdeletedanditsselectionismorecomplex,duetointeractionsbetweenover-
lappingmovesources.However,thedifferenceinbehaviorattheinsertionpointis
determinedentirelybythebehaviorattheoperation’ssource.Forinstance,both
Previous Page Next Page