Home > Articles

  • Print
  • + Share This
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 andarrow.jpg 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, thearrow.jpg 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. Thearrow.jpg 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.

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.

Figure 9.15

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.

Figure 9.16

Figure 9.16 MVC with Undoable Operations

book.jpg 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.

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) {
         ...
    }
     ...
}

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.

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.arrow.jpg 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.

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 referbook.jpg 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 thebook.jpg 100 COMMAND pattern, it is usually sensible to keep only incremental updates inside the mementos.

Figure 9.17

Figure 9.17 Idea of the Memento Pattern

9.5.2 The Command Processor Pattern

We have now finished examining the core of undo/redo: Any operation onarrow.jpg 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.book.jpg 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 availablearrow.jpg 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().arrow.jpg 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.

arrow.jpg 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 commanddouble_arrow.jpg 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 undoablearrow.jpg 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 forarrow.jpg 9.3.4 state changes. In the current example, the base class CommandProcessor Action already implements this mechanism in a template method and callsarrow.jpg 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 standarddouble_arrow.jpg 9.5.4 extensions.

Many frameworks and libraries provide variants of this scheme, andarrow.jpg 3.2.1 one then simply has to create new types of commands for the application-specificbook.jpg 235 models. For instance, the Eclipse Modeling Framework defines a Command interface and a BasicCommandStack command processor; thebook.jpg 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.

arrow.jpg 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 thearrow.jpg 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.

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 Eclipsebook.jpg 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 andbook.jpg 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 trulyarrow.jpg 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 andarrow.jpg 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 transactionsbook.jpg 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()

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;
     ...
}

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 somearrow.jpg 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 forarrow.jpg 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. Thearrow.jpg 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 specialarrow.jpg 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,arrow.jpg 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 ensurearrow.jpg 1.5.6 that the model they work with is not corrupted—that they are exception-safearrow.jpg 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.

  • + Share This
  • 🔖 Save To Your Account