Nothing relevant. nothing relevant 1
Contents
1. We will denote operations to be stored in the operation history as follows e INSERT position text e DELETE position text Because the operation must store sufficient information to be reversible we cannot simply store the number of characters for the DELETE operation So we store the text which was actually deleted and can easily derive the number of characters which were deleted Consider an example Suppose that starting with an empty state this sequence of operations is performed by Mike Atul and Mike respectively e INSERT 1 abcde e DELETE 3 2 e INSERT 2 xyz The resulting state after all three operations is performed would be axyzbe The history after performing these three operations might be as follows where each row is an entry in a list column one contains operations column two contains the user tag and column three contains a timestamp tag INSERT abode Mike 10532 DELETEG cd INSERT xyz Atur 05 37 Mike 5527 Finally we define the Conflict Transpose and Inverse functions for the INSERT and DELETE primitives We begin with a simple utility function which determines whether two regions of character positions overlap Overlap pos leni posz lenz INSERT if it alters the text which was inserted An op eration will conflict with a DELETE if it alters the two characters bordering the DELETE The reason for us ing the borde2. any problems It is also possible to undo D if it does not conflict with C or B otherwise doPtr could not have been undone D B Figure 5 Remove an operation and its Undo from the temporary copy of the history list 10 5 4 Conflict List Generation The Conflict List Generation algorithm computes a list of all operations which must be undone prior to undoing a given operation This capability can be very useful in creating the user interface for undo Based on the comprehensive undo algorithm conflict list generation algorithm FindConflict works by shifting the input operation A to the end of a copy of the history list Figure 6 However when a conflicting operation C prevents a shift C is undone Should C conflict with any later operations those too are recursively undone The undo operations are not actually performed on the document only simulated and each conflict is added to a list And operations which have already been undone are ignored for the purpose of conflicts If each item in the resulting list is actually undone most recent operation being undo first the input opera tion will have no conflicts in the history and can be un done 5 5 Performance of Algorithms The Comprehensive Undo and Conflict List Generation algorithms have worst case run times of O n where n is the number of operations between the operation to be undone and the end of the history list For the undo a worst case example
3. as GROVE Elli90 ShrEdit CSMIL89 91 and DistEdit Knis90 but most lack undo capabilities Those which provide undo gener ally provide only a global undo in which the last change made by anyone to a document is undone rather than allowing users to individually reverse their own changes Undo is important in collaborative applications be cause it provides freedom to interact and experiment in a shared workspace A shared document is often used as a group blackboard during possibly distributed meetings If the current state of the document contains important information people may have inhibitions about making changes because the work is not solely theirs Knowing that any previous state can be easily recovered may free group members to demonstrate ideas in the document This freedom also applies to asynchronous sharing where group members work on a shared document at different times tentative changes can be made to the section of a document and undone at a later time if needed Performing undo in collaborative applications provides technical challenges three areas choosing the operation in choosing the action to be undone determining where the undo should occur and resolving conflicts between different users First choosing the action to undo in a single user system is usually easy simply choose the most recent action and use it to revert to the prior state of the document However in a group environment there are many para
4. if no such conflict exists The importance of the notion of a conflict is that an operation cannot be undone if it con flicts with a later operation unless the later operation is undone first 4 3 2 Transpose If no conflict exists between two operations we require that it be possible to transpose them That is by making some adjustments to the operations it is possible to per form them in a different order and still obtain the same result The Transpose A B function given two non conflicting operations A and B will return two new op erations B and A which satisfy the following two prop erties Transpose Property 1 Performing So Ao B will give the same result as executing S o B o A irrespective of the initial valid state S Transpose Property 2 B is the operation that would have been done to the document instead of B if op eration A had not been done before B Property 1 allows us to move operations around in the history list and still be guaranteed that the resulting state will be the same Property 2 shows that A can meaning fully be undone leaving only the effects of B As we will see operation A will usually be identical to A and B to B except that the position data may be different Our notion of transpose is similar to the one described in Eli89 However we require transpose function to be defined only when the operations do not conflict 4 3 3 Some useful properties As stated ear
5. then DELETE posz str str2 DELETE p else DELET E posa stra DELETE pos st Finally the znverse functions are Inverse INSERT pos str Inverse DELET E pos str DELETE pos str INSERT pos str 5 Undo Algorithms This section presents three algorithms a simple undo al gorithm to demonstrate the basic concepts a comprehen sive undo which handles multiple undo operations and an posz lenz lakyprithin to derive all conflicting operations which pre AND posz lt pos l pytay jundo Now we show the Conflict function which given two operations determines whether the second operation con flicts with the first An operation will conflict with an All three algorithms assume that an operation has al ready been chosen to be undone Methods of selecting which operation to undo are described in Section 6 on Undo Interfacing In our description of the algorithms we assume that only one centralized history list is maintained for all users We will discuss issues related to replication of edi tor state and history list in Section 7 1 We also assume that all operations will be done as requested by the users There are no failures and no un intended effects If necessary editor should provide some sort of locking scheme so that two users do not perform conflicting operations in parallel 5 1 Data Definitions The following data types are used by the algorithms Operation A primitive o
6. would be undoing A for the sequence and where A conflicts with every B In this case B must be transposed until it is before B and the same for every B A similar situation exists for the Conflict List algorithm 6 Undo Interfacing Before undo algorithms given above can be used a means must be provided for a user to select the operation he wishes to undo There are many user interfaces possible using our undo framework and algorithms Following are some sample interface methods 6 1 Individual History Undo The Emacs style history undo described in Section 2 3 can with minor modifications be made to work in our framework allowing each user to undo his most recent operations one by one The first time a user does an undo the system searches backward from the end of the history list until an opera tion tagged with that user s identity is located a pointer to that history record is stored for later use by the user The comprehensive undo algorithm is then applied to the 11 procedure FindConflicts Undoltem HistoryItem var HistTemp HistoryRec Conflicts HistoryRec A copy begin Make a copy of the history list from the Undoltem forward HistTemp CopyTatlofList Undoltem Conflicts NIL RecFindConflicts Hist Temp Return all conflicting operations with Undoltem at the end o return Conflicts end procedure RecFindConflicts doPtr HistoryRec Recursively undo doPtr opera
7. Nothing relevant nothing relevant Undoing Actions in Collaborative Work Atul Prakash Michael J Knister Software Systems Research Laboratory Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor MI 48109 2122 Phone 313 763 1585 Email aprakash eecs umich edu mknister eecs umich edu ABSTRACT Due to lack of full awareness of other users intentions the possibility of inadvertent mistakes is higher in collabora tive work and yet most current collaborative systems fail to provide adequate facilities for undoing actions This limitation occurs because undo facilities of single user sys tems do not readily apply to collaborative systems In this paper we propose a general framework for undoing actions in collaborative software systems The framework takes into account the possibility of conflicts between dif ferent users actions that may prevent a normal undo The framework also allows selection of actions to undo based on who performed them where they occurred or any other appropriate criteria 1 Introduction The ability to reverse or undo the effects of previous actions has become a common feature in modern applica tion software This ability is particularly valuable in col laborative applications but it is technically much more difficult to implement than in a single user system Numerous collaborative editors and other group appli cations have been constructed such
8. ate and the possibility of conflicts does not arise in single user applications since operations are never skipped 3 Our Approach Our approach is similar to history undo but it allows operations to be undone selectively and deals explicitly with location shifting and conflicts We use data structures similar to those used in history undo in particular upon an undo the inverse of an op eration is appended at the end of the history list In our experience use of history is simple and intuitive for most users However in a collaborative application since the last operation done by a user may not be globally last other users may have done operations subsequently we need to allow undoing of a particular user s last operation from the history list For example consider the following history list where A s refer to operations done by user A and B s refer to operations done by other users Ay By A B B3 Now suppose user A wishes to undo his her last ac tion As Normal history undo mechanisms in single user systems do not support it because they would require undoing B and Bs as well In the US amp R model it is possible to undo the last three operations and then redo B and B3 but as pointed out in the previous section that can be disconcerting to other users of the system Note that user A may not be aware that operations B and B3 have been carried out on the document by other users and the other users m
9. ay not aware of activities of user A In the above example the operation to be undone Ag is selected based on the identity of the user More gener ally the operation selected for undoing from the history list could be selected based on any other attribute for instance region type time task or anything else Thus we term our scheme as selective undo since the opera tion to be undone is not necessarily the last one but is selected using some attribute attached to the operation We would like to undo A2 but without undoing and then redoing By and B3 To selectively undo an operation we cannot simply ex ecute the inverse of the operation because later operations could have shifted the location where the undo must be performed For example suppose the following two text operations have been applied to the starting state abcd INSERT 4 x followed by INSERT 1 yy resulting in the state yyabcxd The first operation inserted x at position 4 and the second operation inserted yy at position 1 Assume that these operations were done by different users Now the user who did the first operation wishes to undo the operation However we cannot simply perform the first operation s inverse DELET E A4 1 be cause the second operation has moved the x to location 6 Our scheme takes this possibility of location shifting into account so that in this example the first operation will be undone by exec
10. can now be undone To implement repeated undo operations it may be use ful to define a new primitive for regional undo otherwise a repeated undo will fail The issue is there because after the first undo the region could change What is needed is a region identifying primitive that can be transposed with any operation even if an overlap in region exists 6 4 Multi operation actions Situations may arise in which the application may wish to treat a group of primitive operations as a single high level operation For instance consider the following sce narios e One user level action e g IndentParagraph could result in numerous primitive operations a bunch of INSERTs Users would expect to be able to undo the high level operation in entirety using one undo operation rather than having to undo the primitive operations one by one e Inverse of a primitive operation may not be a prim itive operation but a collection of primitive opera tions Again that collection has to be treated as a single high level operation in case it needs to un done e Undoing many steps at once can also be useful for returning to a known previous state For example a user may wish to revert chapter 15 of a paper back to the way it was at 5PM last Tuesday i e undo all operations for the region covering chapter 15 with timestamps after 5PM last Tuesday assuming suf ficient history with appropriate tags is kept Multiple operation undo is s
11. d to un doing one users changes Any arbitrary filtering criteria can be used to select the next operation to undo while searching back through the history as long as the neces sary information is stored in the history list For example history undo could use a filter to repeat edly undo actions for a set of users for a time range for a region of the document for a particular task or for any combination of these parameters The Individual History Undo is simply history undo with a filter which selects only operations of one user 6 3 Regional Undo Another useful criterion for selecting undo operations is a region in the document For example a user may want to undo his most recent changes to the abstract of a paper but not any other changes Using a region as a selection criterion is slightly more difficult than using user id or timestamps because op erations performed historically on a region refer to the location where the region used to be rather than where it is now To locate an operation which affect a region R we start by defining a new operation S which we know will conflict with any operation performed in R For instance S might be an operation which deletes all of R certainly any op eration affecting R would conflict with this We place S at the end of the history list and use transpose to shift it backward If it cannot be transposed due to a conflict that conflicting operation must be within the region and
12. del In addition we are investigating the uses of the his tory list in other contexts particularly to keep track of evolution of a document at a fine level of granularity References CSMIL89 91 Cognitive Science and Machine Intelli gence Laboratory ShrEdit A Multi user Shared Text Editor User Manual The University of Michi gan 1989 and 1991 Elli89 C A Ellis and S J Gibbs Concurrency Con trol in Groupware Systems Proceedings of the ACM SIGMOD 89 Conference on the Management of Data Seattle Washington May 1989 Elli90 C A Ellis S J Gibbs and G L Rein De sign and Use of a Group Editor in Engineering for Human Computer Interaction G Cockton Ed North Holland Amsterdam 1990 pp 13 25 Elli91 C A Ellis S J Gibbs and G L Rein Group ware Some Issues and Experiences Communica tions of the ACM January 1991 pp 38 58 FSF85 R Stallman GNU Emacs Manual 1985 Knis90 M Knister and A Prakash DistEdit A Distributed Toolkit for Supporting Multiple Group Editors Proceedings of the Third Conference on Computer Supported Cooperative Work Los Ange les California October 1990 pp 343 355 Teit78 W Teitelman Interlisp Reference Manual Xe rox Palo Alto Research Center 1978 Vitt84 J S Vitter US amp R A New Framework for Re doing IEEE Software October 1984 pp 39 52 14
13. e False ABCD p Example of Comprehensive Undo begin _Assume that operations B and C conflict and other than while Conflict HistPtr operation Mist Ptr nert operatian here are no conflicts If the operation C is undone if HistPtr next undoneBy lt gt nal then the history list will be a follows where C is the operation RemoveDoUndoPair HistPtr nert that results from shifting C past D else return False endif endwhile AB D g return True es end Now suppose operation B is to be undone The algorithm will first copy HistoryList will be copied into Temp Histo ryList so that the original list is not affected by shifting Figure 4 Check if there is a genuine conflict between an operations Then TrulyConflict will be called to check operation and the following operation for conflict between B and C TrulyConflict will de tect a conflict between B and C but will notice that C has a pointer to its undo operation C It will therefore call Remove DoUndoPair to remove the C and C pair The resulting temporary history list will be as follows procedure RemoveDoUndoPair doPtr HistoryRec where D C Transpose C D This subroutine given a pointer to an operation which is later undone physically shifts it forward in the HistTemp ABD list until it meets its undo then removes both operations Assume doPtr undoneBy points to the undo Pera ty Conflict continues to chec
14. e operations and state of a text document must defined Second the storage in a history list must be considered Third the Conflict Transpose and Inverse functions must be defined for the operations chosen The state of a text document can be modeled as a single string of text in which line breaks are represented by new line characters Now we must define the operations which can be used to alter the state We choose the primitives INSERT and DELETE INSERT is given two parameters the location of the character before which the insert will occur and the text to be inserted DELETE shall also have two parameters the starting position from which to delete and the number of characters to be deleted Lo cations are defined as the absolute position in the text with the leftmost position being one The two primitive operations are sufficient to make any change to a docu ment Additional primitives such as REPLACE could be added but are not necessary Other representations of position such as line and column number could also be used but the absolute positions we have chosen seem simpler Note that the model does not dictate the actual data structure which is used to store the document state The current state could be represented as a linked list of lines as a single array of characters or any other way The ap plication is responsible for correctly applying operations so that its internal data structure represents the correct state
15. e undo algorithm which is not blocked by prior undo operations Furthermore we demonstrate that the algorithm will work for undoing undo operations To perform a comprehensive undo we must know when one operation is the undo inverse of another We can detect this condition by whenever an undo is performed placing a pointer into the history list that links an op eration to its undo Thus upon undoing B from the sequence A B C the history list would appear as follows note that the oval line beneath the sequence indicates a do undo pointer A BC PB The Comprehensive Undo algorithm Figure 3 is same as the simple undo algorithm except that it uses a more type HistoryRec record operation Operation neat HistoryRec undoneBy HistoryRec This fie end procedure Undo Undoltem HistoryItem var HistTemp HistoryRec A copy HistPir HistoryRec Pointer ShiftOp Operation Newltem HistoryRec begin Make a copy of the history list from the Undoltem forward HistTemp CopyTatlofList Undoltem ShiftOp HistTemp operation HistPtr HistTemp nect Shift Undoltem forward removing all paired do undo operatii while HistPtr nert lt gt nil do if TrulyConflict HistPtr then return Sorry Conflicts with HistPtr next else Transpose returns two operations store the 2nd in Sh _ ShiftOp Transpose ShiftOp History i endif endwhile Newltem Perform Inverse ShiftOp Undoltem undon
16. eBy Newltem return Undo successful end Figure 3 Comprehensive undo sophisticated conflict checking algorithm TrulyConflict Figure 4 The undo algorithm works by making a copy of the end of the history list from the operation to undo onward The operation to undo is shifted until it reaches the end of the list Before each shift TrulyConflict is called to check if there is a conflict between the operation and the next operation If a conflict is found with an operation which has been later undone i e there is re ally no conflict that operation and its undo are removed from the history list by RemoveDoUndoPair Figure 5 The RemoveDoUndoPair subroutine given an opera tion X which is later undone by X shifts X until it is adjacent to X and then removes both operations This is valid because X o X is an identity operator Property 1 X will not conflict with another operation Y in the history between it and X unless Y itself has been undone otherwise X could not have been undone In the case of such an intervening Y RemoveDoUndoPair is called recursively to first eliminate Y from the history list function TrulyConflict HistPtr HistoryRec boolean This function determines whether the operation in HistPtr conflicts with the following operation ignoring any Upematidn which have been undone and stripping them from tha dpat the history list at some point is as follows list Like Conflict returns Tru
17. ent other users are likely to see their work un done for at least a short while with no apparent reason Furthermore if the implementation is not careful after the redo other users context cursor position window buffer may change unexpectedly from the original con text Also neither model addresses the problem of con flicts that redoing some operations may not semantically make sense if an earlier operation is skipped 2 3 History undo In the history undo scheme one can undo any number to some limit of past actions in a row The GNU Emacs ed itor FSF85 supports history undo Once a user stops un doing his work by doing something other than an undo e g inserting a character the undone actions become like any other actions they can be subsequently undone if desired Consider the sequence of operations ABCDE Now suppose E is undone Then in the history undo the history list will be as follows where Ff is the operation that reverses the effects of E ABCDEE T Notice that a pointer is used to keep track of the next operation to be undone On another undo the history list will be as follows ABCDEED T If one now breaks out of the undo mode by doing some operation other than an undo say F the history list will e ABCDEEDF T At this point doing two more undo operations will re sult in ABCDEEDFFD T History undo has the nice property that it is possible to go back to any previous st
18. eturns two operations store the 2nd in Sh _ ShiftOp Transpose ShiftOp History i endif endwhile Perform Inverse ShiftOp return Undo successful end Figure 2 Single step undo in collaborative applications BAC where B A Transpose A B Now if Conflicts A C is true the undo will fail Otherwise another shift will occur resulting in B C A where C A Transpose A C To see that this is correct consider what would happen if we perform A on the altered list giving B C A A Since B o C o A is equivalent to Ao BoC by Transpose Property 1 and B oC o A 0A B oC by Property 1 we find AoBoCoA BoC oA o AW B oC Thus performing A at the end of the original history gives the same result as if operation A had never been performed by Transpose Property 2 the undo has suc ceeded While the simple algorithm is correct it is unable to deal with the results of prior undo operations For exam ple suppose the history contains Ao BoC where A and B conflict but neither conflicts with C A user wanting to undo both A and B first does a simple undo of B re sulting in the history A B C B Then the user attempts to undo A Simple undo determines that A conflicts with B and is unable to shift A to the end of the history However since B is undone we should be able to undo A 5 3 Comprehensive Undo We now give a comprehensiv
19. her operations it might be practical to store the history at an undo server if some delay can be tolerated If the history information is replicated a decision must be made whether the semantics of an undo will be broad cast to the group or just the results of the undo opera tion If the undo itself is not broadcast for an operation other users will not be able to ignore the undone oper ation in executing further undo operations Thus it is probably preferable to broadcast undo semantics Replicated histories may or may not be kept identi cally for all users at all times for example the ordering of operations might vary between different users history lists If the histories are not identical the same undo op erations may work differently at each location but must 13 guarantee the same result Thus concurrency control is sues arise for replicating history which are very similar to and dependent upon concurrency techniques used for the actual document state 7 2 Length of History List In both single user and collaborative applications the length of the history list would dictate how far back op erations can be undone However in single user systems it is easy to provide a guarantee that the user will be able to undo at least his last operation with a bounded num ber of operations on history list the history list needs to only keep one operation the last one In collaborative applications on the other hand pr
20. imilar to the notion of transactions in databases Either they should all be un done collectively or conflicts should be reported and un done first For instance suppose that a paragraph is in dented and then modified so that conflicts arise it would not be desirable to allow a partial undo its effect would be hard to understand for the user Multi operation undo can be implemented in our framework with the following extensions 1 The history list needs to be extended to keep suffi cient information around so that the set of operations that constitute a high level operation can be deter mined 2 When undoing a high level operation all the primi tive operations that constitute the high level opera tion need to be shifted to the end and then undone collectively using Property 6 If conflicts arise dur ing shifting undo should not be permitted without undoing the conflicts first The collection of opera tions that are used to undo need to be treated as a high level operation 3 Do undo pointers need to go between corresponding operations which could be high level Transaction processing may lead to inefficiencies in a group environment because it hinders tight interactions between users Elli91 Elli89 However for a multi operation undo it is highly desirable to ensure atomic ity perhaps through use of locks so that an undo has a predictable effect We are still exploring whether there are important se ma
21. k for conflict between B Any intervening conflicts have been undone and the following operation and returns false to Com x prehensive Undo because there is no conflict between B and D After completion of the shifting operation while begin loop in Comprehensive Undo the temporary history list while doPtr nert lt gt doPtr undoneBy do will be as follows if Conflicts doPtr operation doPtr nezt operation then if there is a conflict it must have been undone so can be removed RemoveDoUndoPair doPtr nert where D B Transpose B D else Now that operation B has been shifted to the end of the Transpose the two operations logically and parah vA successfully undone using the operation B f it ca doPir next operation doPtr operation D This op ration is carried out and appended to the original Transpose doPtr operation doPtr negt ope fron with th iate d d int dded ListSwap doPtr doPtr nert istory list wi e appropriate do undo pointers added endif giving the result endwhile The operation is now adjacent to its undo remove them both from Hist Beni st y g Pp ListDelete HistTemp doPtr nezt ListDelete HistTemp doPtr end Note that in this configuration it is not possible to redo C by undoing C because assuming Property 5 C would conflict with B an operation that has not been undone However it is possible to undo B and then undo C with out
22. lier an Inverse Operation function must also be supplied by the application Inverse returns a new operation which can nullify the effects of its argu ment Specifically when the inverse of an operation is performed immediately after that operation the result ing state is the same as if neither operation had ever been executed Some properties that we will assume in our dis cussion are as follows Property 1 Ao A Property 2 A A Property 3 A B gt A B Property 4 If A and B have a conflict then B and A also have a conflict Property 5 If Ao B can be transposed then Bo A can also be transposed Property 6 Ao B BoAd The only crucial properties that we really need to hold in our algorithms are Properties 1 and 6 However we will assume that other properties also hold while discussing the examples Property 1 says that an operation A and its inverse A be J the null or identity operation which does not affect state i e Sof S The operator denotes that the left hand side and right hand side are equivalent in their effect on the document s state ex cluding the history list Property 6 states that to undo two actions undo them one by one Not all of the above properties are independent For instance Property 2 can be derived from Property 1 4 4 Document Model Applied to Text Editing We will now apply the document model to a specific type of document a plain text document with no formatting First th
23. llel streams of activity from different users and the undo needs to be more selective about choosing what to undo Also a return to a previous global state could have undesirable effects because it would undo actions of all users instead of just one Second once the correct operation is chosen to be undone the location at which the undo of an action should be performed may be differ ent from the location at which the action was originally performed due to the effects of other users activity on the document Finally if two or more users interleave their work in the same portion of a document it may not make sense to undo one user s changes without undoing the other users changes In this case there are conflicts between the changes the users made The rest of the paper is organized into the following sections e A review of previous work on undo e A discussion of how our approach extends undo ca pabilities particularly for group environments e The requirements an application must meet to use our undo framework and an example for text editing e The undo algorithms e Several interface possibilities for using the undo al gorithms e Other issues relevant to group undo including repli cation and the amount of undo state to store e Conclusions and future work 2 Related Work There are several basic methods for providing undo abil ities in single user systems We discuss them here In our discussion we as
24. note state prior to application of an operation A o placed between operations represents that the operation is being applied For example SoMoN denotes the state resulting from application of opera tion M followed by operation N on a document in state S Sometimes we will also use A o B to denote the com pound operation that first applies A and then applies B Two sequences of operations are equivalent if they pro duce the same state Equivalence is represented by For example SoMoN SoPoQ indicates that the two sequences produce the same state even though the operations in each sequence are not iden tical The parameters of an operation should fall into one of two classes operational data and positional data The operational data combined with the primitive should in dicate what the operation will accomplish The positional data indicates where in the document the operation is to be performed For a text editing primitive INSERT the operational data would be the text to be inserted and the positional information would contain a position where the insert will occur Generally an operation could be performed in a different location by changing only its positional data 4 2 Operation History To provide the raw ingredients for undo the application must maintain a history of the operations which have been performed on a document We assume that this history will be stored as a a simple list kept in the same orde
25. ntic or efficiency issues that may sometimes make it more appropriate to consider a high level operation as a new primitive operation rather than a collection of ex isting primitives 7 Other Issues 7 1 Replication Issues In a distributed environment it is highly desirable to replicate the document maintaining a copy at each users site to keep response time short If the data were kept only at a central site each time someone merely navi gated through the document they would have to wait for a round trip network delay before getting feedback Also central data storage provides a single point of failure When a program replicates data it must provide a means of concurrency control which ensures that all copies of the document are the same or nearly so within some bounds This generally involves broadcasting oper ations to all users in combination with some form of lock ing or re sequencing EIli91 discusses various approaches to concurrency control which vary in their response time flexibility and consistency guarantees Replication raises several questions with respect to undo e Should the history list be replicated e What messages should be broadcast for replication e Can replicated histories differ between users Deciding whether to replicate history is a trade off between performance storage requirements and fault tolerance Because undo is probably less commonly used and less critical compared to most ot
26. oviding such a guar antee is difficult with a bounded number of operations on the history list Say user X does an operation Then user Y does a sequence of operations Now in order to guarantee that X is able to undo his operation the X s operation as well as all the Y s operations have to be kept on the history list Either the history list has to be al lowed to grow as needed or the users have to be prepared to occasionally not be able to undo their last operation if other users have been active and they haven t been active for a while 8 Conclusions We have presented a framework for group undo which is simple and generally applicable to a variety of documents The techniques proposed in this paper are presently be ing implemented in DistEdit toolkit Knis90 Hope fully the framework and prototype will lead to behav ioral science work exploring the right interfaces for car rying out undo operations in collaborative applications We are also exploring whether our shifting and conflict checking strategy could be applied to carry out an opera tion retroactively to have the same effect as an undo do new operations redo sequence but without necessarily doing an undo redo cycle as in the linear and US amp R mod els For situations where shifting is difficult to carry out say due to too much dependence of Transpose and In verse functions on prior state we are investigating the integration of undo redo schemes with our mo
27. peration including the opera tional data and positional data History List A list of operations including tag infor mation such as user and time Figure 1 shows the structure of the history list in more detail History Listis a list of records in which each record contains an operation and the information used to locate operations such as the user who performed the operation the time at which it was executed and any other infor mation which will be used to select operations to undo The algorithms are not concerned with the details of op eration records such as the location and other internal data the Inverse Conflict and Transpose operations are used to manipulate operations The Perform routine performs an operation altering the document state and appends the operation to the end of the history list 5 2 Simple Undo To demonstrate the principals of our undo technique we first present an algorithm for the simple undo in which only one previous operation can be undone Since the op eration to be undone is not necessarily the one at the end of the history list the operation to be undone is passed to the algorithm The algorithm is given in Figure 2 The basic idea is to use the transpose function to shift the operation all the way to the end of the history list If it cannot be shifted to the end due to a conflict along the way it cannot be undone If the operation can be shifted to the end we can simply execute the inver
28. perations For instance suppose that there is a sequence of operations ABCDE Operations and D can be undone in sequence then a new operation F done and then D redone giving the following history list list of operations done so far ABCFDE T A pointer is used to keep track of next action to be undone in this example the undone operation E would be the next operation which could be redone Note that undo operations are not explicitly stored in the history list So if one wants to back to the original sequence without the F it is not possible One could undo F but then D and E must be done manually The Undo Skip Redo US amp R model Vitt84 sup ports redo like the linear undo model but also allows a more user friendly skipping of some operations during the redo Instead of a linear list US amp R model keeps a tree data structure for maintaining history so that it becomes possible to restore state to any point in the history un like the linear undo model In the above example F would be stored on a different branch of the tree from the sequence D E so that F could be undone and then D and E could be redone if the user so desired A limitation of both the linear undo model and the US amp R model is that in order to undo one operation O several steps back in the history all subsequent opera tions must first be undone and then redone skipping O during the redo This is potentially disruptive in a group environm
29. r as the operations were performed Our undo al gorithms need to read this list copy portions of it and alter the copy Only operations stored in the history can be undone Each item in the history list must contain e The operation which was performed e Any additional data required to immediately reverse an operation stored as part of that operation e The user who performed the operation and other criteria for selecting what to undo In order to selectively undo a particular user s opera tion we must tag each operation in the history with the identity of the user who performed it Other tags could be stored as well such as the time of the operation or the reason for the operation Any such tag could be used to select operations to undo Note that if the history is complete contains every op eration ever performed on the document then the cur rent state of the document could be reconstructed by per forming every operation in the list in sequence 4 3 Conflict Re ordering and Reversibility of Operations Our model requires that the application supply func tions which can detect conflicts between operations re order operations and create inverse operations In a syn chronous group environment these functions would usu ally be needed anyway to ensure predictable results when parallel streams of activities are going on For instance if two users are working simultaneously in a document con flict checking ma
30. r characters for DELETE is can be seen in the following example Suppose we begin with state abe and perform DELETE 2 1 followed by INSERT 2 x resulting in state axc If we later wish to undo the DELETE it is not clear whether the b should be placed before or after the x flict This definition may be conservative in the case of multiple deletes but it is safe Therefore this is a con Conflict INSERT pos str1 INSERT pose str2 pos lt poss lt pos str Conflict INSERT pos str DELETE poss strz Overlap posy str1 pose Conflict DELETE pos str1 INSERT poss str2 pos pos Conflict DELETE pos str1 DELETE pos strz Overlaps pos 1 2 pose Now we define transpose Note that the transpose func tion must be well defined only when there are no conflicts between the two operations Transpose INSERT pos str INSERT poss stra if posy gt pos then INSERT pose stri stro INSERT po else INSERT posz str2 INSERT pos str Transpose INSERT pos str DELET E posa str2 if posy gt pos then DELETE posz str str2 INSERT pi else DELET E posa stro INSERT pos sti Transpose DELET E pos str1 INSERT posa str2 if posy gt pos then INSERT pose stri stro DELETE pe else INSERT posz str2 DELET E pos sti Transpose DELETE pos str DELET E poss str2 if posy gt pos
31. rful editing operations should always map to a sequence of primitive operations For exam ple assume that INSERT location string is one of the primitive operations The user level action indent para graph might result in numerous INSERT operations In our scheme undoing of these more powerful operations will be implemented as a sequence of undo operations of the primitive commands see the Section 6 4 on multiple operation undo for more details All applications maintain a current state of the docu ment that is being edited This state can be represented in different data structures and our framework places no restrictions on the representation There should exist a null state representing an empty document Primitive operations or just operations are the only means by which the state of a document can be altered An operation applied to a state results in a new state Any given state is simply the result of a sequence of zero or more operations applied in sequence to a null state Operations can also have parameters which specify ex actly what the operation is to accomplish and where it is to be performed For instance a DELETE operation would have parameters to indicate what is to be deleted Operations will be denoted using upper case letters and sequences of operations using sequences of upper case letters The operations are assumed to be performed in left to right order left associative We will use the letter S to de
32. se of the shifted operation to undo it By shifting the opera tion we have effectively determined where the undo must be performed Note that the the history list is not being altered in the algorithm the shifting is simulated An example will help demonstrate the algorithm As sume we want to undo A given the history list ABC Suppose A conflicts with B Then the Con flicts A B will be true and the undo will fail as it should If A does not conflict with B the result after one loop cycle will be type Operation record prim Primitive locationData Application dependent type operationData Application dependent type end HistoryRec record operation Operation user User time Timestamp nett HistoryRec any other desired tags go here end var HistoryList HistoryItem Stored history for the document function Perform op Operation HistoryRec Performs operation on the document returns the new element added to the history list Figure 1 Data types used in the undo algorithms procedure Simple Undo Undoltem Historyltem Undo the Undoltem which is a pointer into the HistoryList var ShiftOp Operation HistPir HistoryRec Pointer into the history list begin ShiftOp Undoltem operation HistPtr Undoltem nest while HistPtr nezt lt gt nil do if Conflicts ShiftOp HistPtr next operation then return Sorry Undo conflicts with HistPtr next else Transpose r
33. sume that the operations that can be performed on a document are reversible i e for ev ery operation A we can determine an inverse operation A that will undo the effect of A For instance in an edi tor an INSERT operation can be undone by a DELETE operation Note that in general the inverse operation of A may depend on state of the document prior to A For instance if a DELETE operation is done on a text document that deletes three characters at position 10 then in order to determine its inverse we must know the three characters that were deleted The inverse operation then will be an INSERT operation that inserts those three characters back at position 10 2 1 Single step undo Single step undo is common in most Macintosh and Win dows applications as well as editors such as vi It allows undo of the last operation For instance given a sequence of operations ABCDE Single step undo allows undoing of operation E but not a subsequent undo of operation D Usually redo of last undo is also allowed often implemented as an undo of the last undo so that in the above example can be redone 2 2 Linear undo model and US amp R model The Interlisp system Teit78 one of the early systems to provide undo used the linear undo model The linear undo model allows undoing of a sequence of operations and keeps a pointer which tracks the last operation un done Operations can then be redone after possibly doing some new o
34. tion and undo all conflicts storing the conflicts and not actually performing operations begin while doPtr nert lt gt nil do if TrulyConflict doPtr then RecFindConflicts doPtr nert else Transpose operations logically and physically doPtr nezt operation doPtr operation Transpose doPtr operation doPtr nert operation ListSwap doPtr doPtr next endif endwhile Moved it to end of history Add to conflict list amp delete ListAppend Conflicts doPtr ListDelete HistTemp doPtr end Figure 6 Conflict List Generation Algorithm operation Should the user immediately do another undo the history search continues backward from the stored pointer Thus the user can proceed back through his most recent changes When an operation other than an other undo if performed the stored pointer is deleted making the undo operations appear as normal operations which can be undone If the undo algorithm fails due to a conflict the Conflict List Generation algorithm can be used to locate all the conflicting operations which must belong to other users At this point the interface can inform the user of the problem and show whose work must be undone He might then be given a choice canceling or proceeding to undo the operations of those other users In the latter case each further undo would operate on an item in the conflict list 6 2 History Undo with Selection Filters The history undo process need not be restricte
35. uting DELETE 6 1 We also take into account the possibility of conflicts In the above example B may have modified the same region of the document as Az so that it no longer makes sense semantically to undo A without first undoing Bo We do not allow an operation to be undone until any prior conflicting operations have been undone 4 Application Requirements Our undo framework assumes an application model in which all changes to a document are performed using a set of primitive operations As operations are performed they are archived in a history list to provide the basis for undo The operations must be reversible and capable of being re ordered when no conflicts between the operations exist This section describes in detail the model and require ments which our undo framework imposes upon applica tions It also demonstrates how the model can be applied to simple text documents 4 1 Document Model In our document model we assume that applications modify a document using only a well defined set of prim itive operations which are reversible For the purpose of undo we treat the document much like an object for which the primitive operations are the methods Unlike an object however we do not require that operations be defined to retrieve information from the document state only to alter it At the user interface level primitive as well as more powerful operations may be provided for modifying a doc ument More powe
36. y involve making sure that their changes do not overlap Mechanisms for reordering of parallel independent operations are also needed because the or der in which two operations will be done may be unpre dictable The editor must be prepared to accept the two operations in either order with the same resulting effect The functions which the application must provide are e Conflict Operation Operation gt Boolean e Transpose Operation Operation gt Operation Operation e Inverse Operation Operation The following sections provide descriptions and prop erties for these functions 4 3 1 Conflict A conflict between two adjacent operations A and B im plies that the second operation B affects what the oper ation A has done to the state it destroys the integrity of that first operation A conflict indicates that the two operations could not have been performed in parallel with a predictable result A conflict also arises if B depends on A and is not meaningful without having performed A Suppose for example that a graphics document is be ing edited Operation A creates a circle in the document and operation B resizes that circle In this case there is a conflict between A and B If operation A had not been done operation B would make little sense The Conflict A B function supplied by the applica tion must return True if there exists a conflict when the two operations are performed in sequence and False
Download Pdf Manuals
Related Search