[ACCEPTED]-Design Pattern for Undo Engine-undo

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

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

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

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

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

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

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

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

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

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

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

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

-Adam

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

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

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

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

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

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

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

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

more info here

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

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

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

Codeplex project:

It's a simple framework to add Undo/Redo 7 functionality to your applications, based 6 on the classical Command design pattern. It 5 supports merging actions, nested transactions, delayed 4 execution (execution on top-level transaction 3 commit) and possible non-linear undo history 2 (where you can have a choice of multiple 1 actions to redo).

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

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

For reference, here's a simple implementation 2 of the Command pattern for Undo/Redo in 1 C#: Simple undo/redo system for C#.

A clever way to handle undo, which would 8 make your software also suitable for multi 7 user collaboration, is implementing an operational transformation of 6 the data structure.

This concept is not very 5 popular but well defined and useful. If 4 the definition looks too abstract to you, this project is 3 a successful example of how an operational 2 transformation for JSON objects is defined 1 and implemented in Javascript

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

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

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

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

You can try ready-made implementation of 10 Undo/Redo pattern in PostSharp. https://www.postsharp.net/model/undo-redo

It lets 9 you add undo/redo functionality to your 8 application without implementing the pattern 7 yourself. It uses Recordable pattern to 6 track the changes in your model and it works 5 with INotifyPropertyChanged pattern which 4 is also implemented in PostSharp.

You are 3 provided with UI controls and you can decide 2 what the name and granularity of each operation 1 will be.

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

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

You can make your initial idea performant.

Use 6 persistent data structures, and stick with keeping a list of references to old state around. (But that 5 only really works if operations all data 4 in your state class are immutable, and all 3 operations on it return a new version---but 2 the new version doesn't need to be a deep 1 copy, just replace the changed parts 'copy-on-write'.)

I've found the Command pattern to be very 8 useful here. Instead of implementing several 7 reverse commands, I'm using rollback with 6 delayed execution on a second instance of 5 my API.

This approach seems reasonable if 4 you want low implementation effort and easy 3 maintainability (and can afford the extra 2 memory for the 2nd instance).

See here for 1 an example: https://github.com/thilo20/Undo/