Design Pattern for Undo Engine

Question

I'm writing a structural modeling tool for a civil enginering application. I have one huge model class representing the entire building, which include collections of nodes, line elements, loads, etc. which are also custom classes.

I have already coded an undo engine which saves a deep-copy of the model class after each modification to the model. Now I started thinking if I could have coded differently. Instead of saving the deep-copies, I could perhaps save a list of each modifier action with a corresponding reverse modifier. So that I could apply the reverse modifiers to the current model to undo, or the modifiers to redo.

I can imagine how you would carry out simple commands that change object properties, etc. But how about complex commands? Like inserting new node objects to the model and adding some line objects which keep references to the new nodes.

How would one go about implementing that?

Answer 1

Most examples I've seen use a variant of the Command-Pattern for this. Every user-action that's undoable gets its own command instance with all the information to execute the action and roll it back. You can then maintain a list of all the commands that have been executed and you can roll them back one by one.

Answer 2

Just been reading about the command pattern in my agile development book - maybe that's got potential?

You can have every command implement the command interface (which has an Execute() method). If you want undo, you can add an Undo method.

more info here

Answer 3

You might want to refer to the Paint.NET code for their undo - they've got a really nice undo system. It's probably a bit simpler than what you'll need, but it might give you some ideas and guidelines.

Answer 4

This might be a case where CSLA is applicable. It was designed to provide complex undo support to objects in Windows Forms applications.

Answer 5

I had to do this when writing a solver for a peg-jump puzzle game. I made each move a Command object that held enough information that it could be either done or undone. In my case this was as simple as storing the starting position and the direction of each move. I then stored all these objects in a stack so the program could easily undo as many moves as it needed while backtracking.

Answer 6

If you're talking GoF, the Memento pattern specifically addresses undo.

Answer 7

I once worked on an application in which all changes made by a command to the application's model (i.e. CDocument... we were using MFC) were persisted at the end of the command by updating fields in an internal database maintained within the model. So we did not have to write separate undo/redo code for each action. The undo stack simply remembered the primary keys, field names and old values every time a record was changed (at the end of each command).

Answer 8

I'm with Mendelt Siebenga on the fact that you should use the Command Pattern. The pattern you used was the Memento Pattern, which can and will become very wasteful over time.

Since you're working on a memory-intensive application, you should be able to specify either how much memory the undo engine is allowed to take up, how many levels of undo are saved or some storage to which they will be persisted. Should you not do this, you will soon face errors resulting from the machine being out of memory.

I would advise you check whether there's a framework that already created a model for undos in the programming language / framework of your choice. It is nice to invent new stuff, but it's better to take something already written, debugged and tested in real scenarios. It would help if you added what you're writing this in, so people can recommend frameworks they know.

Answer 9

Most examples I've read do it by using either the command or memento pattern. But you can do it without design patterns too with a simple deque-structure.

Answer 10

We reused the file load and save serialization code for “objects” for a convenient form to save and restore the entire state of an object. We push those serialized objects on the undo stack – along with some information about what operation was performed and hints on undo-ing that operation if there isn’t enough info gleaned from the serialized data. Undo and Redoing is often just replacing one object with another (in theory).

There have been many MANY bugs due to pointers (C++) to objects that were never fixed-up as you perform some odd undo redo sequences (those places not updated to safer undo aware “identifiers”). Bugs in this area often ...ummm... interesting.

Some operations can be special cases for speed/resource usage - like sizing things, moving things around.

Multi-selection provides some interesting complications as well. Luckly we already had a grouping concept in the code. Kristopher Johnson comment about sub-items is pretty close to what we do.

Answer 11

I've implemented complex undo systems sucessfully using the Memento pattern - very easy, and has the benefit of naturally providing a Redo framework too. A more subtle benefit is that aggregate actions can be contained within a single Undo too.

In a nutshell, you have two stacks of memento objects. One for Undo, the other for Redo. Every operation creates a new memento, which ideally will be some calls to change the state of your model, document (or whatever). This gets added to the undo stack. When you do an undo operation, in addition to executing the Undo action on the Memento object to change the model back again, you also pop the object off the Undo stack and push it right onto the Redo stack.

How the method to change the state of your document is implemented depends completely on your implementation. If you can simply make an API call (e.g. ChangeColour(r,g,b)), then precede it with a query to get and save the corresponding state. But the pattern will also support making deep copies, memory snapshots, temp file creation etc - it's all up to you as it is is simply a virtual method implementation.

To do aggregate actions (e.g. user Shift-Selects a load of objects to do an operation on, such as delete, rename, change attribute), your code creates a new Undo stack as a single memento, and passes that to the actual operation to add the individual operations to. So your action methods don't need to (a) have a global stack to worry about and (b) can be coded the same whether they are executed in isolation or as part of one aggregate operation.

Many undo systems are in-memory only, but you could persist the undo stack out if you wish, I guess.

Answer 12

As others have stated, the command pattern is a very powerful method of implementing Undo/Redo. But there is important advantage I would like to mention to the command pattern.

When implementing undo/redo using the command pattern, you can avoid large amounts of duplicated code by abstracting (to a degree) the operations performed on the data and utilize those operations in the undo/redo system. For example in a text editor cut and paste are complementary commands (aside from the management of the clipboard). In other words, the undo operation for a cut is paste and the undo operation for a paste is cut. This applies to much simpler operations as typing and deleting text.

The key here is that you can use your undo/redo system as the primary command system for your editor. Instead of writing the system such as "create undo object, modify the document" you can "create undo object, execute redo operation on undo object to modify the document".

Now, admittedly, many people are thinking to themselves "Well duh, isn't part of the point of the command pattern?" Yes, but I've seen too many command systems that have two sets of commands, one for immediate operations and another set for undo/redo. I'm not saying that there won't be commands that are specific to immediate operations and undo/redo, but reducing the duplication will make the code more maintainable.

Answer 13

Command pattern.

Answer 14

The first section of Design Patterns (GoF, 1994) has a use case for implementing the undo/redo as a design pattern.

Answer 15

I think both memento and command are not practical when you are dealing with a model of the size and scope that the OP implies. They would work, but it would be a lot of work to maintain and extend.

For this type of problem, I think you need to build in support to your data model to support differential checkpoints for every object involved in the model. I've done this once and it worked very slick. The biggest thing you have to do is avoid the direct use of pointers or references in the model.

Every reference to another object uses some identifier (like an integer). Whenever the object is needed, you lookup the current definition of the object from a table. The table contains a linked list for each object that contains all the previous versions, along with information regarding which checkpoint they were active for.

Implementing undo/redo is simple: Do your action and establish a new checkpoint; rollback all object versions to the previous checkpoint.

It takes some discipline in the code, but has many advantages: you don't need deep copies since you are doing differential storage of the model state; you can scope the amount of memory you want to use (very important for things like CAD models) by either number of redos or memory used; very scalable and low-maintenance for the functions that operate on the model since they don't need to do anything to implement undo/redo.

Answer 16

For reference, here's a simple implementation of the Command pattern for Undo/Redo in C#:

http://www.catnapgames.com/blog/206

Answer 17

http://blogs.msdn.com/kirillosenkov/archive/2009/06/29/new-codeplex-project-a-simple-undo-redo-framework.aspx

Answer 18

I don't know if this is going to be of any use to you, but when I had to do something similar on one of my projects, I ended up downloading UndoEngine from http://www.undomadeeasy.com - a wonderful engine and I really didn't care too much about what was under the bonnet - it just worked.

Answer 19

I'd go for www.undomadeeasy.com. Their UdoEngine allows you to make incremental undo and redo changes rather than storing the complete object each time. Much better control.