Design Pattern for Undo Engine

Question

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.

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.

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

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.