21 Inheritance case study: “undo”in an interactive system udesixmple weneed thatth desigers of amost any interactive system:how to provide a way to undo commands. The discussion will show how inheritance and dynamic binding yield a simple, regular and general solution to an apparently intricate and many-faceted problem;and it will teach us a few general lessons about the issues and principles of object-oriented design. 21.1 PERSEVERARE DIABOLICUM To err is human,it is said,but to foul things up for good takes a computer (aided,one should add,by humans).The faster and more powerful our interactive systems become, the easier it becomes to make them perform actions that we do not really want.This is why we all wish for a way to erase the recent past;not the "big red button"of computer jokes, but a Big Green Button that we can push to pretend that we did not do something that we did but wish we did not. Undoing for fun and profit In an interactive system,the equivalent of the Big Green Button is an Undo operation, which the system's designer has provided for the benefit of any user who,at some stage in a session,wants to cancel the effect of the last executed command. The primary aim of an undo mechanism is to allow users to recover from potentially damaging input mistakes.It is all too easy to type the wrong character or click on"OK" instead of"Cancel".But a good undo facility goes further.It frees users from having to concentrate nervously on every key they type and button they click.Beyond this,it encourages a "What if...?"style of interaction in which users try out various sorts of input,knowing that they can back up easily if the result is not what they expect. Every good interactive system should provide such a mechanism.When present,it tends to be one of the most frequently used operations.(For that reason,the makers ofthe computer on my desk have wisely provided an Undo key on the keyboard,although it is neither green nor particularly big.It is only effective,of course,for those regrettably few software applications whose authors took notice of it.)
21 Inheritance case study: “undo” in an interactive system For our second design example we examine a need that confronts the designers of almost any interactive system: how to provide a way to undo commands. The discussion will show how inheritance and dynamic binding yield a simple, regular and general solution to an apparently intricate and many-faceted problem; and it will teach us a few general lessons about the issues and principles of object-oriented design. 21.1 PERSEVERARE DIABOLICUM To err is human, it is said, but to foul things up for good takes a computer (aided, one should add, by humans). The faster and more powerful our interactive systems become, the easier it becomes to make them perform actions that we do not really want. This is why we all wish for a way to erase the recent past; not the “big red button” of computer jokes, but a Big Green Button that we can push to pretend that we did not do something that we did but wish we did not. Undoing for fun and profit In an interactive system, the equivalent of the Big Green Button is an Undo operation, which the system’s designer has provided for the benefit of any user who, at some stage in a session, wants to cancel the effect of the last executed command. The primary aim of an undo mechanism is to allow users to recover from potentially damaging input mistakes. It is all too easy to type the wrong character or click on “OK” instead of “Cancel”. But a good undo facility goes further. It frees users from having to concentrate nervously on every key they type and button they click. Beyond this, it encourages a “What if… ?” style of interaction in which users try out various sorts of input, knowing that they can back up easily if the result is not what they expect. Every good interactive system should provide such a mechanism. When present, it tends to be one of the most frequently used operations. (For that reason, the makers of the computer on my desk have wisely provided an Undo key on the keyboard, although it is neither green nor particularly big. It is only effective, of course, for those regrettably few software applications whose authors took notice of it.)
696 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.I Multi-level undo and redo Offering an undo mechanism is better than not offering one,but it is not enough.Most systems that provide Undo limit themselves to one level:you can only cancel the effect of the last command.If you never make two mistakes in a row,this is enough.But if you ever go off in the wrong direction,and wish you could go back several steps,you are in trouble. (Anyone having used Microsoft Word,the Unix Vi editor or FrameMaker,in the releases available at the time this book was published,will know exactly what I mean. There is really no excuse for the restriction to one level of undoing.Once you have set up the undoing machinery,going from one-level to multi-level undo is a simple matter, as we will see in this chapter.And,please (this is a potential customer speaking)do not, like so many application authors,limit the number of commands that can be undone to a ridiculously small value;if you must limit it at all,let the user choose his own limit (through a "preferences"setting that will apply to all future sessions)and set default to at least 20.The overhead is small if you apply the techniques below,and is well justified. With multi-level undo,you will also need a Redo operation for users who get carried away and undo too much.With one-level undo no special Redo is required;the universally applied convention is that an Undo immediately following an Undo cancels it,so that Redo and Undo are the same operation.But this cannot work if you can go back more than one step.So we will have to treat Redo as a separate operation. Practical issues Although undo-redo can be retrofitted with reasonable effort into a well-written O-O system,it is best,if you plan to support this facility,to make it part of the design from the start-if only because the solution encourages a certain form ofsoftware architecture(the use of command classes)which,although beneficial in other respects,does not necessarily come to mind if you do not need undoing. To make the undo-redo mechanism practical you will have to deal with a few practical concerns. First you must include the facility in the user interface.For a start,we may just assume that the set of operations available to users is enriched with two new requests: Undo (obtained for example by typing control-U,although following the Macintosh convention control-Z seems to have become the standard on PC tools)and Redo (for example control-R).Undo cancels the effect of the last command not yet undone;Redo re-executes the last undone command not yet redone.You will have to define some convention for dealing with attempts to undo more than what has been done (or more than what is remembered),or to redo more than what has been undone:ignore the request,or bring up a warning message. This is only a first shot at user interface support for undo-redo.At the end of this chapter we will see that a nicer,more visual interface is possible
696 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.1 Multi-level undo and redo Offering an undo mechanism is better than not offering one, but it is not enough. Most systems that provide Undo limit themselves to one level: you can only cancel the effect of the last command. If you never make two mistakes in a row, this is enough. But if you ever go off in the wrong direction, and wish you could go back several steps, you are in trouble. (Anyone having used Microsoft Word, the Unix Vi editor or FrameMaker, in the releases available at the time this book was published, will know exactly what I mean.) There is really no excuse for the restriction to one level of undoing. Once you have set up the undoing machinery, going from one-level to multi-level undo is a simple matter, as we will see in this chapter. And, please (this is a potential customer speaking) do not, like so many application authors, limit the number of commands that can be undone to a ridiculously small value; if you must limit it at all, let the user choose his own limit (through a “preferences” setting that will apply to all future sessions) and set default to at least 20. The overhead is small if you apply the techniques below, and is well justified. With multi-level undo, you will also need a Redo operation for users who get carried away and undo too much. With one-level undo no special Redo is required; the universally applied convention is that an Undo immediately following an Undo cancels it, so that Redo and Undo are the same operation. But this cannot work if you can go back more than one step. So we will have to treat Redo as a separate operation. Practical issues Although undo-redo can be retrofitted with reasonable effort into a well-written O-O system, it is best, if you plan to support this facility, to make it part of the design from the start — if only because the solution encourages a certain form of software architecture (the use of command classes) which, although beneficial in other respects, does not necessarily come to mind if you do not need undoing. To make the undo-redo mechanism practical you will have to deal with a few practical concerns. First you must include the facility in the user interface. For a start, we may just assume that the set of operations available to users is enriched with two new requests: Undo (obtained for example by typing control-U, although following the Macintosh convention control-Z seems to have become the standard on PC tools) and Redo (for example control-R). Undo cancels the effect of the last command not yet undone; Redo re-executes the last undone command not yet redone. You will have to define some convention for dealing with attempts to undo more than what has been done (or more than what is remembered), or to redo more than what has been undone: ignore the request, or bring up a warning message. This is only a first shot at user interface support for undo-redo. At the end of this chapter we will see that a nicer, more visual interface is possible
$21.1 PERSEVERARE DIABOLICUM 697 Second,not all commands are undoable.In some cases this is an impossibility of fact,as in the command "fire the missiles"(notwithstanding the televised comment of a then-in-office US president,who thought one could command a U-turn)or,less ominously,"print the page".In other cases,a command is theoretically undoable but the overhead is not worth the trouble;text editors typically do not let you undo the effect of a Save command,which writes the current document state into a file.The implementation of undoing will need to take into account such non-undoable commands,making this status clear in the user interface.Be sure to restrict non-undoable commands to cases for which this property is easily justifiable in user terms. As a counter-example,a document processing tool which I frequently use tells its user, once in a while,that in the current state of the document the command just requested is not undoable,with no other visible justification than the whim of the program.At least it says so in advance-in most cases. Interestingly,this warning is ina sense a lie:you can undo the effect if you want,although not through Undo but through "Revert to last saved version of the document".This observation yields a user interface rule:if there remains any case for which you feel justified to make a command non-undoable,do not follow the document processing system's example by just displaying a warning of the form"This command will not be undoable"and giving the choice between Continue anyway and Cancel.Give users three possibilities:save document,then execute command;execute without saving; cancel. Finally,it may be tempting to offer,besides Undo and Redo,the more general "Undo,Skip and Redo"scheme,allowing users,after one or more Undo operations,to skip some of the commands before triggering Redo.The user interface shown at the end of this chapter could support this extension,but it raises a conceptual problem:after you skip some commands,the next one may not make sense any more.As a trivial example assume a text editor session,with a text containing just one line,and a user who executes the two commands (1)Add a line at the end (2)Remove the second line Exercise E21.4. Our user undoes both,then wants to skip(1)and redo(2).Unfortunately at this stage page 716. (2)is meaningless:there is no second line.This is less a problem in the user interface (you could somehow indicate to the user that the command is impossible)than in the implementation:the command Remove the second line was applicable to the object structure obtained as a result of(1),but applying it to the object structure that exists prior to (1)may be impossible (that is to say,cause a crash or other unpleasant results). Solutions are certainly possible,but they may not be worth the trouble. Requirements on the solution The undo-redo mechanism that we set out to provide should satisfy the following properties. UI.The mechanism should be applicable to a wide class of interactive applications, regardless of the application domain
§21.1 PERSEVERARE DIABOLICUM 697 Second, not all commands are undoable. In some cases this is an impossibility of fact, as in the command “fire the missiles” (notwithstanding the televised comment of a then-in-office US president, who thought one could command a U-turn) or, less ominously, “print the page”. In other cases, a command is theoretically undoable but the overhead is not worth the trouble; text editors typically do not let you undo the effect of a Save command, which writes the current document state into a file. The implementation of undoing will need to take into account such non-undoable commands, making this status clear in the user interface. Be sure to restrict non-undoable commands to cases for which this property is easily justifiable in user terms. As a counter-example, a document processing tool which I frequently use tells its user, once in a while, that in the current state of the document the command just requested is not undoable, with no other visible justification than the whim of the program. At least it says so in advance — in most cases. Interestingly, this warning is in a sense a lie: you can undo the effect if you want, although not through Undo but through “Revert to last saved version of the document”. This observation yields a user interface rule: if there remains any case for which you feel justified to make a command non-undoable, do not follow the document processing system’s example by just displaying a warning of the form “This command will not be undoable” and giving the choice between Continue anyway and Cancel. Give users three possibilities: save document, then execute command; execute without saving; cancel. Finally, it may be tempting to offer, besides Undo and Redo, the more general “Undo, Skip and Redo” scheme, allowing users, after one or more Undo operations, to skip some of the commands before triggering Redo. The user interface shown at the end of this chapter could support this extension, but it raises a conceptual problem: after you skip some commands, the next one may not make sense any more. As a trivial example assume a text editor session, with a text containing just one line, and a user who executes the two commands (1) Add a line at the end. (2) Remove the second line. Our user undoes both, then wants to skip (1) and redo (2). Unfortunately at this stage (2) is meaningless: there is no second line. This is less a problem in the user interface (you could somehow indicate to the user that the command is impossible) than in the implementation: the command Remove the second line was applicable to the object structure obtained as a result of (1), but applying it to the object structure that exists prior to (1) may be impossible (that is to say, cause a crash or other unpleasant results). Solutions are certainly possible, but they may not be worth the trouble. Requirements on the solution The undo-redo mechanism that we set out to provide should satisfy the following properties. U1 • The mechanism should be applicable to a wide class of interactive applications, regardless of the application domain. Exercise E21.4, page 716
698 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.I U2.The mechanism should not require redesign for each new command. U3.It should make reasonable use of storage. U4.It should be applicable to both one-level and arbitrary-level Undo. The first requirement follows from the observation that there is nothing application- specific about undoing and redoing.To facilitate the discussion,we will use as example a kind of tool familiar to everyone:a text editor (such as Notepad or Vi),which enables its users to enter texts and to perform such commands as INSERT LINE,DELETE LINE, GLOBAL REPLACEMENT (of a word by another)and so on.But this is only an example and none of the concepts discussed below is specific to text editors. The second requirement excludes treating Undo and Redo as just any other command in the interactive system.Were Undo a command,it would need a structure of the form if"Last command was INSERT LINE"then "Undo the effect of INSERT LINE" elseif "Last command was DELETE LINE"then “Undo the effect of DELETE LINE” etc. We know how bad such structures,the opposite of what the Single Choice principle See"Single directs us to use,are for extendibility.They have to be changed every time you add a Choice”,page61. command;furthermore,the code in each branch will mirror the code for the corresponding command (the first branch,for example,has to know a lot about what INSERT LINE does),pointing to a flawed design. The third requirement directs us to be sparing in our use of storage.Supporting undo- redo will clearly force us to store some information for every Undo;for example when we execute a DELETE LINE,we will not be able to undo it later unless we put aside somewhere,before executing the command,a copy of the line being deleted and a record of its position in the text.But we should store only what is logically necessary. The immediate effect of this third requirement is to exclude an obvious solution: On STORABLE see saving the whole system state-the entire object structure-before every command “Deep storage:.afirst execution;then Undo would just restore the saved image.This would work but is terribly view ofpersistence" wasteful of space.Too bad,since the solution would be trivial to write:just use the page 250. STORABLE facilities for storing and retrieving an entire object structure in a single blow. But we must look for something a little more sophisticated. The final requirement,supporting an arbitrary depth of undoing,has already been discussed.It will tum out to be easier to consider a one-level mechanism first,and then to generalize it to multi-level. These requirements complete the presentation of the problem.It may be a good idea, as usual,to spend a little time looking for a solution on your own before proceeding with the rest of this chapter
698 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.1 U2 • The mechanism should not require redesign for each new command. U3 • It should make reasonable use of storage. U4 • It should be applicable to both one-level and arbitrary-level Undo. The first requirement follows from the observation that there is nothing applicationspecific about undoing and redoing. To facilitate the discussion, we will use as example a kind of tool familiar to everyone: a text editor (such as Notepad or Vi), which enables its users to enter texts and to perform such commands as INSERT_LINE, DELETE_LINE, GLOBAL_REPLACEMENT (of a word by another) and so on. But this is only an example and none of the concepts discussed below is specific to text editors. The second requirement excludes treating Undo and Redo as just any other command in the interactive system. Were Undo a command, it would need a structure of the form if “Last command was INSERT_LINE” then “Undo the effect of INSERT_LINE” elseif “Last command was DELETE_LINE” then “Undo the effect of DELETE_LINE” etc. We know how bad such structures, the opposite of what the Single Choice principle directs us to use, are for extendibility. They have to be changed every time you add a command; furthermore, the code in each branch will mirror the code for the corresponding command (the first branch, for example, has to know a lot about what INSERT_LINE does), pointing to a flawed design. The third requirement directs us to be sparing in our use of storage. Supporting undoredo will clearly force us to store some information for every Undo; for example when we execute a DELETE_LINE, we will not be able to undo it later unless we put aside somewhere, before executing the command, a copy of the line being deleted and a record of its position in the text. But we should store only what is logically necessary. The immediate effect of this third requirement is to exclude an obvious solution: saving the whole system state — the entire object structure — before every command execution; then Undo would just restore the saved image. This would work but is terribly wasteful of space. Too bad, since the solution would be trivial to write: just use the STORABLE facilities for storing and retrieving an entire object structure in a single blow. But we must look for something a little more sophisticated. The final requirement, supporting an arbitrary depth of undoing, has already been discussed. It will turn out to be easier to consider a one-level mechanism first, and then to generalize it to multi-level. These requirements complete the presentation of the problem. It may be a good idea, as usual, to spend a little time looking for a solution on your own before proceeding with the rest of this chapter. See “Single Choice”, page 61. On STORABLE see “Deep storage: a first view of persistence”, page 250
$21.2 FINDING THE ABSTRACTIONS 699 21.2 FINDING THE ABSTRACTIONS The key step in an object-oriented solution is the search for the right abstraction.Here the fundamental notion is staring us in the eyes. Command as a class The problem is characterized by a fundamental data abstraction:COMMAND, representing any editor operation other than Undo and Redo.Execution is only one of the features that may be applied to a command:the command might be stored,tested-or undone.So we need a class of the provisional form deferred class COMMAND feature execute is deferred end undo is deferred end end COMMAND describes the abstract notion of command and so must remain deferred. Actual command types are represented by effective descendants of this class,such as class LINE DELETION inherit COMMAND feature deleted line index:INTEGER deleted line:STRING set deleted line index (n:INTEGER)is -Set to n the number of next line to be deleted. do deleted line index:=n end execute is --Delete line. do "Delete line number deleted line index" "Record text of deleted line in deleted line" end undo is --Restore last deleted line. do "Put back deleted line at position deleted line index" end end And similarly for each command class
§21.2 FINDING THE ABSTRACTIONS 699 21.2 FINDING THE ABSTRACTIONS The key step in an object-oriented solution is the search for the right abstraction. Here the fundamental notion is staring us in the eyes. Command as a class The problem is characterized by a fundamental data abstraction: COMMAND, representing any editor operation other than Undo and Redo. Execution is only one of the features that may be applied to a command: the command might be stored, tested — or undone. So we need a class of the provisional form deferred class COMMAND feature execute is deferred end undo is deferred end end COMMAND describes the abstract notion of command and so must remain deferred. Actual command types are represented by effective descendants of this class, such as class LINE_DELETION inherit COMMAND feature deleted_line_index: INTEGER deleted_line: STRING set_deleted_line_index (n: INTEGER) is -- Set to n the number of next line to be deleted. do deleted_line_index := n end execute is -- Delete line. do “Delete line number deleted_line_index” “Record text of deleted line in deleted_line” end undo is -- Restore last deleted line. do “Put back deleted_line at position deleted_line_index” end end And similarly for each command class