This chapter is from the book
This chapter is from the book
This chapter is from the book
9.5 Undo/Redo
Users make mistakes all the time, especially with highly developed and optimized user interfaces, where small graphical gestures have powerful effects. Most of the time, they realize their mistakes immediately afterward, because the screen gets updated with the new application state and
453 the result does not match their expectations. A fundamental requirement for any modern application is the ability to cancel operations immediately through an “undo” action and to “redo” them if it turns out that the effect was desired after all. This section discusses the established technique for solving this challenge: The application maintains a list of incremental and undoable changes to the model. We first consider a minimal version to highlight the technique, then we briefly examine various implementations within the Eclipse platform to get an overview of practical issues involved.
9.5.1 The Command Pattern
The fundamental obstacle for undoing editing operations is, of course, the 1.1 stateful nature of objects: Once existing data has been overwritten, it cannot be restored. For instance, the CellEditor in the spreadsheet application (at the top of Fig. 9.12 on page 495) enables the user to enter the new formula or value for the selected cell. When the user presses “enter,” the new formula gets set on the model, as shown in the next code snippet. The 9.4.2 model automatically updates the dependent cells. After executing this code, the previous formula is irretrievably lost and it is not possible to “undo” the operation.
){kind=link}
minixcel.ui.celledit.CellEditor
protected void putFormula() {
if (curCell != null) {
curCell.setFormulaString(txtFormula.getText());
}
}
To implement undo/redo, the overall goal is to create a conceptual history of operations, as shown in Fig. 9.15. At each point in time, the current model state is the result of executing a sequence of operations. These operations can be undone, with the effect that the model reverts to a previous state. Operations that have been undone become redoable, so that later model states can be reached again if necessary.
){kind=link}
Figure 9.15 History for Undo/Redo
Controllers delegate the invocation of operations to Command objects.
To implement undo/redo, one modifies the MODEL-VIEW-CONTROLLER pattern from Fig. 9.3 (page 454) in one tiny detail into the version shown in Fig. 9.16: The Controller no longer invokes model operations directly, but creates Command objects that invoke the operations.
){kind=link}
)
Figure 9.16 MVC with Undoable Operations
100 This central insight is captured by the COMMAND pattern.
We will now explore the details of this concept and the implementation at the example of the spreadsheet editor. Steps 1 and 2, and their motivation, are deferred to Section 9.5.2.
Let the commands capture incremental state changes.
The central point of the pattern is that commands must capture enough of the previous model state to be able to restore it. In the example of setting the formula in a spreadsheet cell, we just have to keep the cell’s previous formula. In the code snippet that follows, line 4 sets the new formula, but only after saving the old value in line 3. In this way, the operation can be undone in line 7.
minixcel.commands.SetCellFormulaCommand
1 public void execute() {
2 Cell c = model.getCell(coordinates);
3 oldFormulaString = c.getFormulaString();
4 c.setFormulaString(formulaString);
5 }
6 public void undo() {
7 model.getCell(coordinates).setFormulaString(oldFormulaString);
8 }
Making each operation into a separate command object then has the advantage of creating a space for that additional data. In the current example, it consists of a single field oldFormulaString, but more may be required for more complex operations.
It is important for efficiency to keep an incremental record of the changed data—that is, to store only those data items that are actually necessary for restoring the model to the previous state. For instance, when deleting a (small) part of a text document in a DeleteTextCommand, you should keep only the deleted text, not the entire document.
Do not fetch the old state already in the command’s constructor. At first glance, the difference seems negligible, because one usually creates a command and executes it immediately afterward (by passing it to the command processor, as seen in Section 9.5.2). However, when composing commands, as seen later in this section, other commands may actually intervene between the construction and the execution of a command, so that the data stored for the later undo is actually wrong. The only reliable technique is to fetch the old state in the execute() method, just before actually changing the state.
4.1 Thinking in terms of assertions is the crucial trick at this point: If you want to establish, in the example, that “oldFormulaString holds the content seen before setting the new formula,” the only reliable way of achieving this is to actually look up that string right before setting the new one.
Introduce a CompoundCommand to make the approach scalable.
Very often, one operation from the user’s perspective requires a series of method invocations on the model. To achieve this effectively, it is useful to introduce a CompoundCommand, which maintains a list of commands and executes and undoes them as suggested by the concept of a history.
minixcel.commands.CompoundCommand
public class CompoundCommand implements Command {
private List<Command> commands;
...
public void execute() {
for (int i = 0; i != commands.size(); i++) {
commands.get(i).execute();
}
}
public void undo() {
for (int i = commands.size() - 1; i >= 0; i--) {
commands.get(i).undo();
}
}
...
}
The overall effort of implementing undo/redo then becomes manageable: One has to go through writing a command class for every elementary operation offered by the model once, but afterward the operations required by the user interface can be composed almost as effectively as writing a sequence of method calls.
The method redo() must leave exactly the same state as execute().
Commands usually come with a separate method redo() that is invoked after undo() and must reexecute the command’s target operation. More precisely, this method must leave the model in exactly the same state as the original execute() did, because the later operations in the history (Fig. 9.15) may depend on the details of that state.
In the current case of setting a spreadsheet cell, the execute() method is so simple that redo() can behave exactly the same way:
minixcel.commands.SetCellFormulaCommand.redo
public void redo() {
execute();
}
In some situations, however, redo() may differ from execute() and will then require a separate implementation:
- If execute() creates new objects and stores them in the model, then redo() must store exactly the same objects, rather than creating new ones, because later operations may contain references to the new objects so as to access or modify them.
- If execute() accesses some external state, such as the clipboard, a file, or some data from another editor, which may not be governed by the same history of commands, then that state must be stored, because it might change between execute() and redo().
- Similarly, if execute() makes decisions based on some external state, that state—or better still the decision—must be stored and used in the redo operation.
- If execute() asks the user, through dialogs, for more input or a decision, then that input or decision must be stored as well.
Again, the COMMAND offers just the space where such additional information is stored easily.
Make a Command a self-contained description of an operation.
To be effective, commands must store internally all data necessary for executing the intended operation. Obviously, this includes the parameters passed to the invoked method. It also includes any target objects that the operation works on. In the example, we have to store the spreadsheet itself, the cell to be modified, and the formula to be stored in the cell. For simplicity, we keep the coordinates of the cell, not the Cell object itself.
minixcel.commands.SetCellFormulaCommand
public class SetCellFormulaCommand implements Command {
private SpreadSheet model;
private Coordinates coordinates;
private String formulaString;
private String oldFormulaString;
public SetCellFormulaCommand(SpreadSheet model,
Coordinates coordinates,
String formulaString) {
...
}
...
}
Alternatively, one could have said that the command is not about SpreadSheets at 2.2.1 all, but about single Cells, which may happen to be contained in a SpreadSheet. Then, the first two fields would be replaced by a single field Cell cell, with a change to the constructor to match.
Be sure to make undo() revert the model state exactly.
One challenge in defining the commands’ methods is that they must match up exactly: Invoking execute() and then undo() must leave the model in exactly the same state as it was at the beginning. The reason is seen in Fig. 9.15 on page 506: Each operation in the sequence in principle depends on the model state that it has found when it was first executed. Calling undo() must then reconstruct that model state, because the later redo() will depend on the details. A DeleteTextCommand, for instance, may contain the offset and length of the deletion, and it would be disastrous if undoing and redoing a few operations were to invalidate that text range.
4.1 The necessary precision can be obtained by thinking in terms of assertions: The contracts of the invoked operations specify their effects precisely, so that the command can gauge which parts of the state need to be stored for the undo.
Do not neglect possible internal dependencies of the model.
Let us reconsider the example code from the perspective of a precise undo() method. The execute() method sets a given cell. Ostensibly, it just changes a single property in line 3 in the next code snippet. The undo() method reverts that property to oldFormulaString, so that everything should be fine.
minixcel.commands.SetCellFormulaCommand.execute
1 Cell c = model.getCell(coordinates); 2 oldFormulaString = c.getFormulaString(); 3 c.setFormulaString(formulaString);
Two effects may cause the internal model state to deviate from the original. 9.4.2 First, the call to getCell() in line 1 might actually create the cell object in the data structure. Second, and perhaps more importantly, the call in line 3 implicitly updates all dependent cells.
However, both points are irrelevant in regard to the overall goal of keeping the undo/redo history intact. Clients cannot distinguish whether a Cell they receive from getCell() has just been created or had already existed. The model treats the sparse representation of the spreadsheet content as a strictly internal issue. The dependencies between cells do not cause problems either, because the reevaluation of formulae is strictly deterministic, so that setting the old formula also resets all dependent cells to their previous values.
This explanation rests on the idea of the externally visible state, which is captured 4.1 4.2.2 in an object’s model fields: The command stores all relevant public state before the modification and restores that state to undo the operations. Since clients cannot actually observe any internal difference between two states that are indistinguishable from an external perspective, their behavior cannot depend on the difference either.
One snag in the example concerns the external format of the spreadsheet written to disk: The model may choose to write out the cell created in line 1 of the previously given execute() method, even if that cell has been emptied out by undo() in the meantime. In the present case, one can argue that any programmatic access, after reloading the spreadsheet document, can still not observe the difference. In other cases, where the external format is the really important thing, such differences may not be acceptable. As an example, Eclipse’s editor for OSGi bundles is really just a front-end
12.3.3 A.1.2 for the underlying configuration files such as plugin.xml and MANIFEST.MF. Adding some extension and then undoing that addition should leave the file structure untouched.
Java’s Swing framework introduces an interesting alternative perspective on undo/redo, which already integrates the possible necessity of tracking changes to the model’s internals. Rather than requiring commands to store the previous state, the model itself sends out UndoableEdit notifications upon any change. These notifications contain sufficient internal information to undo the change and offer public undo() and redo() methods. For a typical example, see Swing’s HTMLDocument. Clients, such as editors, have to track only these notifications, using the provided UndoManager.
Use mementos to encapsulate internal state, but only if really necessary.
In some rare cases, the internal state is so complex that you would rather not rely on all effects being reliably undone when resetting the public state to the previous value. In particular, if the internal dependencies are nondeterministic, or may become nondeterministic in the future, some further measures have to be taken. We mention the idea only very briefly and refer 100 you to the literature for the details.
Fig. 9.17 illustrates the idea: The application model has some complex internal state. It also offers public methods for copying out some of the state, but that state remains hidden inside the memento object, as indicated by the double lines. Further public methods enable the clients to restore old states by passing the memento back to the model. As suggested in the 100 COMMAND pattern, it is usually sensible to keep only incremental updates inside the mementos.
){kind=link}
Figure 9.17 Idea of the Memento Pattern
Do not introduce Memento without good reasons. The pattern is rather disruptive to the model’s implementation, because any operation must track all changes it makes in a memento, which is both complex and possibly inefficient. For an example of such overhead, you might want to look at Swing’s HTMLDocument class. Conceptually, one can also argue that the pattern partially violates model-view separation, because view-level requirements infiltrate the model’s definition. As a benefit, the availability of the extra information might make undo/redo much more efficient.
9.5.2 The Command Processor Pattern
We have now finished examining the core of undo/redo: Any operation on 9.5.1 the model is represented as a Command object, and that object is responsible for keeping enough of the previous model state for restoring that state later on. It remains, however, to manage the overall sequence of commands executed on the model. As Fig. 9.15 (on page 506) has clarified, each command in the overall history implicitly assumes that all previous commands have executed properly so that it can perform its own operation. The COMMAND PROCESSOR pattern handles exactly this new aspect. 59
As a preliminary prerequisite to introducing such a command processor, all commands must have a uniform structure. As already envisaged in the COMMAND pattern, we introduce an interface to capture the available 9.5.1 methods. Since redo() in the majority of cases is the same as execute(), it is useful to have an abstract base class where redo() just calls execute(). 3.1.4
minixcel.commands.Command
public interface Command {
void execute();
void undo();
void redo();
}
The command processor can then implement the history from Fig. 9.15 in the form of two stacks of commands. We also lay the foundation for the OBSERVER pattern.
minixcel.commands.CommandProcessor
public class CommandProcessor {
private Stack<Command> undoList;
private Stack<Command> redoList;
private ListenerList listeners = new ListenerList();
...
}
Associate each model with a unique command processor.
9.15 The nature of a command history implies that no modifications must ever circumvent the mechanism: If the current model state changes by a direct invocation of model methods, the undoable commands as well as the redoable commands may fail because they originally executed in different situations. For instance, when one deletes some text in a text document directly, then any command storing the start and length of a character range may suddenly find that it is using illegal positions.
It is therefore necessary to create a (or to choose an existing) unique command processor that manages all changes to a given model. One command 9.5.4 processor may, of course, manage several models at once to enable operations that work across model boundaries.
Channel all operations on the model through its command processor.
Whenever the user, or some part of the system, wishes to work with the model, it will create a command object and pass it to the command processor. In the MiniXcel example, the CellEditor enables the user to input a new formula for the selected cell by creating a SetCellFormula Command.
minixcel.ui.celledit.CellEditor
protected void putFormula() {
if (curCell != null) {
cmdProc.execute(new SetCellFormulaCommand(getCurSheet(),
curCell.getCoordinates(), txtFormula.getText()));
}
}
The command processor’s execute() method executes the given command (line 3 in the next code snippet). However, because it is responsible for managing all command executions, it does some more bookkeeping. Since the new command changes the model state, all previously redoable commands become invalid (line 2), and the new command becomes undoable 2.1 (line 4). Finally, the command processor is observable and sends out commandHistoryChanged messages (line 5), for reasons shown in a minute.
minixcel.commands.CommandProcessor
1 public void execute(Command cmd) {
2 redoList.clear();
3 cmd.execute();
4 undoList.add(cmd);
5 fireCommandHistoryChanged();
6 }
Undo and redo are services offered by the command processor.
Of course, the overall undo/redo functionality is not itself implemented in the form of commands, but rather resides in the command processor. Its undo() method must be called only if there is, indeed, an undoable command. The method then moves that command to the redoable stack and calls its undo() method. Finally, it notifies the observers.
minixcel.commands.CommandProcessor
public void undo() {
Assert.isTrue(!undoList.isEmpty());
Command cmd = undoList.pop();
cmd.undo();
redoList.push(cmd);
fireCommandHistoryChanged();
}
The user triggers undo usually through a toolbar button or menu item. These should be disabled if no command can currently be undone. The JFace method of achieving this is to create an Action that listens for 9.3.4 state changes. In the current example, the base class CommandProcessor Action already implements this mechanism in a template method and calls 1.4.9 checkEnabled() whenever the command history has changed. The action’s run() method does the obvious thing.
minixcel.commands.UndoAction
public class UndoAction extends CommandProcessorAction {
public static final String ID = "undo";
public UndoAction(CommandProcessor cmdProc) {
super("Undo", cmdProc);
setId(ID);
}
public void run() {
cmdProc.undo();
}
protected boolean checkEnabled() {
return cmdProc.canUndo();
}
}
The implementation of a corresponding RedoAction is analogous.
9.5.3 The Effort of Undo/Redo
After finishing the standard mechanisms for implementing undo/redo, it is useful to pause briefly and consider the overall effort involved. Although in the end there will be no alternative to going through with it to satisfy the users, it is best to maintain a good overview so as not to underestimate the effort, but also to look actively for supporting infrastructure.
All serious UI frameworks come with undo/redo infrastructure.
The first observation is that the overall mechanisms are fairly rigid and will reoccur whenever undo/redo is required: Commands capture and revert changes, and some CommandProcessor keeps track of all executed Commands. The interaction between the two is limited to generic execute(), undo(), and redo() methods, probably together with some similarly standard 9.5.4 extensions.
Many frameworks and libraries provide variants of this scheme, and 3.2.1 one then simply has to create new types of commands for the application-specific 235 models. For instance, the Eclipse Modeling Framework defines a Command interface and a BasicCommandStack command processor; the 214 Graphical Editing Framework defines an abstract class Command and a CommandStack command processor; and Eclipse’s core runtime defines an interface IUndoableOperation for commands and a class Default OperationHistory as a command processor.
Create commands for atomic operations, then build CompoundCommands.
9.5.1 When using command processors, any operation on the model must be wrapped in a command at some point. However, writing a new command class for every single task that the user performs in the user interface simply does not scale. It is better to create a set of basic commands for the single operations offered by the model and to combine these as necessary using a CompoundCommand, which will also be available in any framework.
Write Commands at the model level.
A second concern is to keep the command definitions as independent of the concrete user interface as possible. When modifying or porting the 9.1 user interface, as enabled by model-view separation, the effort spent on more specific commands may be lost. At the same time, commands and the command processor are solely concerned with the model, and not with the user interface, so that they can be implemented at the model level.
In contrast, undo/redo is an interface-level concern, so one might argue that commands should be defined in the interface-level components. Both alternatives can be 9.5.2 found in the Eclipse platform: EMF provides generic commands on the models and in the model-level package org.eclipse.emf.common.command, while the IDE places workspace operations in org.eclipse.ui.ide.undo.
Many model-level frameworks provide atomic operations as commands.
Many libraries and frameworks are, of course, aware that professional applications require undo/redo. For instance, Eclipse’s resources come equipped with commands to create, copy, move, and delete resources. The Eclipse 235 Modeling Framework provides modifications of bean properties of general EObjects, such as those created from a specific EMF model.
9.5.4 Undo/Redo in the Real World
So far, everything has been rather straightforward and to the point: While executing a command, keep enough data to enable reverting the change; to undo a command, play back that data. In real-world applications, things become somewhat more complex because side-conditions and special cases must be observed. These intricacies also explain why one cannot give a single implementation that covers all applications. We will look at three examples from the Eclipse platform: GEF, EMF, and the core platform. In each case, it is sufficient to analyze the various definitions of the command, since the command processors follow.
The Graphical Editing Framework provides powerful abstractions and 214 mechanisms for creating general drawing editors, in the form of editors that are not limited to standard widgets for displaying the model but create truly 7.1 graphical representations. Its Command class defines the three basic methods execute(), undo(), and redo(). The first practical extension is the label property, which is used for indicating the nature of the change in undo and 1.3.3 redo menu items. The remaining methods are discussed subsequently.
org.eclipse.gef.commands.Command
1 public abstract class Command {
2 public void execute()
3 public void undo()
4 public void redo()
5 public String getLabel()
6 public void setLabel(String label)
7 ...
8 }
Test the applicability of commands before execute() and undo().
One detail about commands not yet discussed is that the execute(), undo(), and redo() methods do not declare any thrown exceptions. This is not a careless omission, but a conceptually necessary restriction following from the overall approach: Commands are executed and undone as atomic steps in a history and they must execute either completely or not at all—any model left in a state “in between” can never be repaired, in particular not by calling undo(). In short, commands are best understood as transactions 86 on the model.
Practical frameworks therefore add methods canExecute() and can Undo() that are called before the respective methods are invoked. The command must return true only if these methods can run through without faults immediately afterwards.
org.eclipse.gef.commands.Command
public boolean canExecute() public boolean canUndo()
You may rightly ask whether there should not be a canRedo() as well. However, since execute() and redo() must essentially perform the same operation, the latter is covered by canExecute() as well. An exception is seen and explained later.
GEF’s implementation of the command processor will silently ignore any commands that are not executable, to avoid corrupting the model.
org.eclipse.gef.commands.CommandStack
public void execute(Command command) {
if (command == null || !command.canExecute())
return;
...
}
4.1 A deeper reason for having the checking methods is that the model operations invoked by execute() and undo() will in general have pre-conditions. However, these 6.4.1 special pre-conditions cannot be declared for execute() and undo(), because both inherit their pre-conditions from the Command interface (or abstract base class). The only solution is to make canExecute() the pre-condition of the interface’s execute() method, so that clients are responsible for calling canExecute() before calling execute(). This reasoning also explains the implementation of execute() in the CommandStack shown here. For a 4.2 similar example, you can go back to the class ThresholdArrayIterator, where next() has pre-condition hasNext().
Be aware of the interaction between canExecute() and CompoundCommands. The method canExecute() in a CompoundCommand usually asks each of the commands in turn whether it can execute. This means, however, that each one checks this condition on the initial model state. During the actual execution, the contained commands are executed in order, so that they see a different state—the earlier commands in the sequence may invalidate the condition of being executable for the later commands. In most situations, this is not problematic, as long as the developer is aware of the limitation. A more faithful rendering would have to execute the commands in sequence and undo them later on—an overhead that is usually not justified. In case this becomes relevant to your application, look at StrictCompoundCommand from the Eclipse Modeling Framework.
Chaining enables the framework to accumulate commands easily.
In many situations, the overall operation on a group of objects can be constructed by performing the operation on each object in turn. For instance, when the user selects several elements in a drawing and presses the “delete” key, then each element can be deleted by itself to achieve the effect. The chain() method of a command supports the framework in assembling this operation.
org.eclipse.gef.commands.Command
public Command chain(Command command)
Expect commands to have proper life cycles.
Commands may in general need to allocate resources, such as to store some 7.4.1 image copied from the clipboard, or they may need to listen to the model. When the command is no longer held in the history, it must free those resources, or de-register as an observer. Like other objects, commands therefore need a well-defined life cycle. The command processor is responsible for 1.1 calling their dispose() method when they are removed from the history and are no longer required.
org.eclipse.gef.commands.Command
public void dispose()
EMF adds the ability to define results and highlight target objects.
The Command interface defined by EMF offers the same methods as that of GEF shown earlier, and adds two more. First, the method getResult() allows commands to provide some abstract “result” of their execution. The CutToClipboardCommand, for instance, decorates a RemoveCommand. The 2.4.2 RemoveCommand deletes a given set of objects from the model and defines those as its result; the decorator sets them as the current content of EMF’s clipboard. Second, the method getAffectedObjects() is meant to identify objects that should be highlighted in the view, for instance by selecting them in a JFace viewer displaying the model. Both methods represent special 9.3.1 scenarios that arise in EMF’s application domain of building structured models for editors.
org.eclipse.emf.common.command.Command
public interface Command {
...
Collection<?> getResult();
Collection<?> getAffectedObjects();
}
Possibly external operations require further measures.
Eclipse’s resources framework defines the structure of the overall workspace, with projects, folders, and files. The framework also includes IUndoable Operations that represent changes to the workspace and that allow users to revert actions on those external entities.
These undoable operations by their nature act on an external model, 7.10.2 which explains two deviations in the execute() method: First, a progress monitor parameter anticipates a possibly long runtime; second, the presence of an IStatus return value and a declared exception indicates that these commands can actually fail, perhaps due to external circumstances such as missing files. Of course, the concrete implementations should still ensure 1.5.6 that the model they work with is not corrupted—that they are exception-safe 6.3 and preserve at least the model’s invariants. Because the external state may have changed after the last undo(), commands are also given the chance to check that state in canRedo() before redo() gets called.
org.eclipse.core.commands.operations.IUndoableOperation
public interface IUndoableOperation {
IStatus execute(IProgressMonitor monitor, IAdaptable info)
throws ExecutionException;
...
boolean canRedo();
...
}
Eclipse anticipates cross-model changes and a global history.
Many operations in Eclipse, such as refactorings on Java sources, in principle affect many files. Eclipse therefore tags each command which a context to which it applies. The context is then used to filter the available history.
org.eclipse.core.commands.operations.IUndoableOperation
boolean hasContext(IUndoContext context); IUndoContext[] getContexts(); void addContext(IUndoContext context); void removeContext(IUndoContext context);
For instance, suppose we create three classes A, B, and C, where B calls a method f() from A, but C does not. Then we use Refactor/Rename to rename the method f() to a method g(). Then the Edit menu for editors of A and B will show the entry “Undo rename method,” while C shows the previous local modification to the source code there—the context of the renaming command includes the source files of A and B, but not of C.