Cecilio Salmeron
December, 2012
I have started to work on the score editor. One of the things I've done is to review all the documentation I had from the editor in 4.0 LenMus series and to re-think about the design. Just in case it could be of help for other people, I will summarize here my findings/thoughts about the issue of implementing undo/redo in an application.
There are two basic approaches for implementing undo/redo:
All possible operations to modify a document are enclosed in "commands" by using the well known "Command pattern". The basic idea is to create an object that represents a user action and encapsulates all the information needed to perform the operation. The Command object receives the additional responsibility of undoing the operation when requested. With this, it is very easy to implement undo/redo. If all user actions in a program are implemented as command objects, the program can keep a stack of the most recently executed commands. When the user wants to undo a command, the program simply pops the most recent command object and executes its undo() method. There are two main approaches for implementing the undo responsibility in commands:
The Command just saves the object state before performing the actions. When the command undo() method is invoked, it simply restores the state which was saved by the command. Instead of saving the whole state of the object, an alternative is to save just the changes to the state.
Instead of saving the state or the changes to the state, the Command just restores the state by carrying out the inverse operation, that is, by doing a logical reverse of the particular actions performed by the command. Regenerating the state this way is not always possible, as implementing the logical inverse of a command could be difficult or impossible, or be too expensive in computational time or resources. For instance, regenerate state is usually simple to do when the command just changes object properties, but for commands deleting objects or parts of the document the only feasible approach is to save a copy of the deleted objects.
So, depending on the situation - possibility of a logical inverse action and the feasibility of it, you need to choose between these two broad categories, and then implement them the way you want. Of course, it is possible to have a hybrid strategy: for some commands use the save strategy, and for others the regenerate strategy. It all will depends on the feasibility and cost of each approach.
A useful design pattern to be used by Command for saving/restoring the state of an object is the Memento pattern. It solves the problem of capturing and externalizing an object’s internal state so that the object can be returned to this state later, without violating document encapsulation.
The other broad alternative is to base undo/redo on checkpoints and rollback. In this approach the Command object is not responsible for undoing the operations. Instead, whenever a command is going to be executed, the command interpreter establishes a new checkpoint. Undo is then implemented by rolling back to a previous checkpoint.
The checkpoints are usually implemented by saving the complete state of the document. For this you can use any suitable mechanism: deep copies, memory snapshots, serialization to memory or to temporary files, etc.
Serialization is one of the simplest ways of implementing checkpoints and has the advantage of reusing existing infrastructure (i.e. part of the file load/save code). But poor time performance and huge memory consumption could be observed if the document is large. In some cases, these problems could be alleviated by saving only the differences between states (differential checkpoints) but this requires building additional support in your model for this.
The undo/redo based on checkpoints approach has important advantages: it is simple to implement, very scalable and requires no-maintenance when adding new actions to operate on the model, as they don't need to do anything for supporting undo/redo. In addition, the approach of serializing the state to disk instead of saving it to memory has the great advantage of facilitating the implementation of a mechanism to recover from system errors and program crashes, so ensuring that the user does not lose the work.
Independently of the undo/redo chosen approach, using Command objects to modify the Document has many advantages. Materializing commands as objects means they can be passed, staged, shared, loaded in a table, and otherwise instrumented or manipulated like any other object. It forces to organize actions and make them more consistent. It also tends to reveal opportunities to factor out repetitive code (i.e., you can separate similar commands into families, and re-factor repeated code into shared base classes). When you turn all user actions into a stream of Commands it is easy to implement scripting, and save the command stream to implement recordable macros. Also, it is easy to insert synthetic commands into the stream for special processing or to redirect the command stream to another computer to remote control another application over the Internet.
In theory, restoring a previous state is just replacing one object with another. But in practise there could be lots of unforeseen consequences that go unnoticed in the beginning stages of implementation. The big problem are pointers or references used in other parts of the application to point to specific parts or objects in the model. When the model is replaced by another copy, these pointers and references are no longer valid, and this causes many many bugs, sometimes difficult to debug, as they will manifest much later, when performing actions difficult to correlate with an undo/redo operation (by the way, this was one of the big problems in LenMus 4.x editor).
The biggest thing you have to do is avoid, outside the model, the use of pointers or references to model objects. A simple technique is to use instead safer undo aware “identifiers” (like unique integers). Whenever a model object is needed, you lookup the current 'good' pointer/reference for the object from a table in the model.
By transient actions I refer to those user actions that do not affect the document information, only to its presentation (i.e. Select objects or Scroll to a point). In many cases it is not necessary to provide undo/redo for transient actions, as the user can easily return to a prior state. Nevertheless, you should consider the convenience of providing undo/redo:
If the chosen approach for undo/redo is based on commands, you should consider the implications for aggregate actions (actions on several objects, e.g. user Shift-Selects a set of objects to do an operation on, such as delete, rename, change attribute) as well as for composite commands (commands created by aggregation, in sequence, of other commands). In these cases you should pay attention to two points:
And this is the summary of my findings/thoughts about the issue of implementing undo/redo in an application. Hope this could be of help for you,
Cecilio
LenMus