Introduction
This article introduces a reusable library that can equip any action in your application with the undo/redo feature. You may use complex data structures and complex algorithms with no care about how they will be rolled back on user demand or after an error.
Background
If you've ever developed a graphic editor or designer for complex data, you've encountered the daunting task of implementing an undo/redo feature supported throughout the application. Implementing the mirror methods Do and Undo for each operation is a boring and very bug-prone process when you are building something more exquisite than a calculator. After my experiments then, I researched a way to make undo/redo support transparent for business logic. To achieve it, we will use the magic of generics.
This project has been published on CodePlex so that everybody can contribute to it and gain from it.
Using the Code
There are two points of good news. First, the public properties of your data classes will not have to be changed. We will just declare the private fields in another way than usual. Second, the business logic of processing your data objects will not be changed either. All we have to do is embrace this code with start and end points like a transaction. So, the code will look like the following:
UndoRedoManager.Start("My Command");
myData1.Name = "Name1";
myData2.Weight = 33;
myData3.MyList.Add(myData2);
UndoRedoManager.Commit();
All of the changes made in the code block above can be rolled back with one line:
UndoRedoManager.Undo();
The next line allows enforcing of the changes again:
UndoRedoManager.Redo();
Let me draw your attention to the fact that no matter how many objects were involved in an operation and what data types were used, all changes can be undone/redone as a single transaction. Both value and reference data types work well. UndoRedoFramework also supports lists and dictionaries. Now let's consider how to declare a data class and make it work. Here is the trick: private data fields should be wrapped in the special generic type UndoRedo<>:
class MyData
{
private readonly UndoRedo<string> name = new UndoRedo<string />("");
public string string Name
{
get { return name.Value; }
set { name.Value = value; }
}
}
Below is a classic declaration of a property with a backing field, so you can compare it with the previous example.
class MyData
{
private string name = "";
public string string Name
{
get { return name; }
set { name = value; }
}
}
There are three vital differences in these code snippets:
- I use the
UndoRedo<> generic type for backing a field. The field does not store values itself, but refers the container that stores the value for us.
- Whenever we need access to the backing field, we use
name.Value in place of name. As you can see, name.Value is used without any type conversion. That is because Value will always have the type we nested into the UndoRedo<...> brackets.
- The private field is made
readonly. This is because the field holds the container that is responsible for accumulating the history of changes. It must live as long as the parent instance. We do not have to change the container itself but, of course, we can change the Value.
This works well both for value and reference types.
Implementation
If you are not interested in implementation details, you may go to the next section with no hesitation. In this article, I will highlight only a couple of core implementation points. I hope you will cast a glimpse into the source code for further details. It is quite small and simple. There are two core classes in the framework: UndoRedoManager and UndoRedo<>. UndoRedoManager is a facade class that contains static methods for manipulations with commands. Below is a partial list of methods:
public static class UndoRedoManager
{
public static IDisposable Start(string commandCaption) { ... }
public static void Commit() { ... }
public static void Cancel() { ... }
public static void Undo() { ... }
public static void Redo() { ... }
public static bool CanUndo { get { ... } }
public static bool CanRedo { get { ... } }
public static void FlushHistory() { ... }
}
Beyond UndoRedoManager, there is the following internal logical structure of objects:
\UndoRedoManager \History \Command \Change \OldValue,NewValue
In other words, UndoRedoManager stores the history of commands. Every Command has its own changes list. Every Change stores old and new values. The Change object is created by UndoRedo<> when the user attempts to make any modifications. As you may remember, we used the UndoRedo<> type to declare backing fields in the samples above. This class is responsible for creating a Change object and filling it with old and new values. Below is a key part of this class:
public class UndoRedo<TValue> : IUndoRedoMember
{
TValue tValue;
public TValue Value
{
get { return tValue; }
set
{
if (!UndoRedoManager.CurrentCommand.ContainsKey(this))
{
Change<TValue> change = new Change<TValue>();
change.OldState = tValue;
UndoRedoManager.CurrentCommand[this] = change;
}
tValue = value;
}
}
}
The code above is the key point of the whole framework. It shows how changes are intercepted inside the user property that we declared in the previous chapter. Thanks to generics, the Value property eliminates any type conversion. The Change object is created inside the current command at only the first attempt of setting a property. So, we have the least amount of overhead possible. When the user commits the command, every Change object will be filled with a new value. The framework will automatically invoke the OnCommit method for each changed property:
public class UndoRedo<TValue> : IUndoRedoMember
{
void IUndoRedoMember.OnCommit(object change)
{
((Change<TValue>)change).NewState = tValue;
}
}
The old and new values gathered above are used by the framework to perform undo/redo operations. As you will see later in the Performance section, all of these routines give a very small overhead. In a real-world application, it can be less than 1%.
Collections
As I mentioned before, changes in lists and dictionaries can be undone/redone, as can those in simple properties. For these purposes, the library provides the classes UndoRedoList<> and UndoRedoDictionary<>, which have exactly the same interfaces as the standard List<> and Dictionary<> classes. However, despite this similarity, the internal implementation of these classes is upgraded with the undo/redo ability. Let's consider how a data object can declare a list:
class MyData
{
private readonly UndoRedoList<MyData> myList= new UndoRedoList<MyData>();
public UndoRedoList<MyData> MyList
{
get { return myList; }
}
}
The major caveat here is that the list is transactionable, but the reference to the list is not. In other words, we are free to Add, Remove and Sort items and all of these changes will be correctly undone. However, in the code above, we may not change the list's reference to another one because it is readonly.
Actually, my practice shows that this is not a problem because in most cases, a typical list stored in a field lives as long as the parent data object. If you are used to another design and want to change the reference to the list, you should use a little bit more sophisticated code. Combine the two generics UndoRedo<> and UndoRedoList<>, as in the following example:
private readonly UndoRedo<UndoRedoList<MyData>> myList ...
Dictionary can be used in the same way as List. So, I won't produce a tautology.
Fail-proof Code
Sometimes code may fail during execution. An I/O error or internal exception may lead to data inconsistency even when the exception was caught carefully. UndoRedoFramework can help here and bring all data into the consistent state it was in at the start point. If the code passes with no error, all changes will be committed. Otherwise, it will be automatically rolled back. See below:
try
{
UndoRedoManager.Start("My Command");
UndoRedoManager.Commit();
}
catch (Exception)
{
UndoRedoManager.Cancel();
}
Moreover, it is possible to use a more slick approach with the same result:
using (UndoRedoManager.Start("My Command"))
{
UndoRedoManager.Commit();
}
As you can see, the latest sample does not have a rollback routine. That is because it will be done automatically (!) if Commit is not reached, e.g. in the case of an exception. It gains ultimate reliability even if you do not need the undo/redo feature itself. The application will recover after any failure and retain a consistent state.
UI and Data Synchronization
A complex UI is often implemented using the Model-View-Controller pattern. A simple Windows application has only Data and Presentation tiers. However, in both cases the developer must write some sort of synchronization code between UI and Data. The demo project has a main form that contains three UI controls:
EditCityControl CitiesChartControl UndoRedoControl, which displays two lists of commands that can be undone/redone for cities data
These controls show different views of the same cities data. The real-world application -- i.e. a designer or any editor -- has dozens of such components and controls to display. However, there is the problem of synchronization: If one of the controls changes the data, ALL of the controls have to reload their data. This is because changing one entity may cause a business rule that changes some other entities.
So, what do we need? First, the synchronization code must get to know about changes made in a component or somewhere in the business logic. Second, it has to force controls on the form to reload and show new data.
This problem can be solved in several ways, good and bad. I want a decoupled code. Ideally, the form should not know much about components. Similarly, the components should not know about each other. Business rules should be as least aware as possible. Honestly, I am too lazy to write synchronization code every time I add another new component to the form. So, cast a glance at the demo project attached to the article and you will see a very lean form:
public partial class DemoForm : Form
{
public DemoForm()
{
InitializeComponent();
CitiesList cities = CitiesList.Load();
chartControl.SetData(cities);
editCityControl.SetData(cities);
}
}
The form simply loads initial data into the custom controls. In this way, the form does not do any synchronization. Event handlers of controls have no code synchronization either, e.g. EditCityControl has a handler of the "Remove City" button:
private void removeCity_Click(object sender, EventArgs e)
{
if (CurrentCity != null)
{
UndoRedoManager.Start("Remove " + CurrentCity.Name);
cities.Remove(CurrentCity);
UndoRedoManager.Commit();
}
}
This notwithstanding, all of the controls on the form are refreshed immediately after the action. This is because UndoRedoFramework provides an ad hoc event, notifying when a command is done/undone/redone. It allows us to put all UI-refreshing code at a single place in the control:
public EditCityControl()
{
UndoRedoManager.CommandDone += delegate { ReloadData(); };
}
Thus, solely subscribing to the CommandDone event, the control solves a bunch of problems. It always stays up-to-date when data has been changed in some other component. Moreover, the control will be immediately updated with the correct data when the user chooses to undo/redo operations.
Performance
Performance and memory optimizations are always competing with each other... and probably with the developer's girlfriend for his spare time. In this article, I will consider the first two factors only. Fortunately, editors and designers with user interaction have no rigid performance requirements for most operations, in contrast to real-time systems. Anyway, I will bring a short performance analysis in some points below:
- Reading the data does not cause any overhead. Thanks to generics, we have gotten rid of type conversions and boxing/unboxing. Values are returned immediately, without searching in history logs.
- Any attempt to change a property incurs one search in an internal hash table. Additionally, the first attempt to change a property during operation copies its value into the history.
- Any attempt to change a list incurs one search in an internal hash table. Additionally, the first attempt to change the list forces the Framework to create a copy of the list and put it into its history.
- Any attempt to change the dictionary incurs one search in an internal hash table and creates two small objects. The Framework never creates an entire copy of the dictionary. In place of that, it stores changes in a log.
- The
Undo and Redo methods simply restore changed values. They do not touch unchanged ones. Restoring a list is a O(1) operation. Therefore Undo may work even faster than the primary algorithm itself.
In other words, you may do the following without considerable overhead:
- Read and change any properties
- Read and change lists with average size
- Read and moderately change dictionaries with large size
However, if you change several huge lists often, there is some risk of slowdown. In this case, I would recommend revision of the data design with splitting long lists.
Below, I bring up a profiling sample from my real-world application. In this example, the user resized a graphical object inside a designer. This middle-sized operation did 5500 readings, 70 changes of properties and 4 changes of dictionaries. All of the extra stuff required for undo/redo took less than 0.7 milliseconds (1/7000 of second). Here are the details of how UndoRedoFramework brought influence on performance:
|
Hit count |
Total milliseconds |
Total % |
| Whole resizing logic and redrawing routines |
|
159.328 |
100% |
| UndoRedo routines |
|
0.677 |
0.425% |
| Starting a command |
1 |
0.008 |
0.005% |
| Getting a property value |
5461 |
0.114 |
0.071% |
| Setting a property value |
71 |
0.026 |
0.017% |
| Changing a dictionary |
4 |
0.065 |
0.041% |
| Finishing a command |
1 |
0.463 |
0.291% |
Memory
UndoRedoFramework needs memory for storing changes only. Memory consumption does not depend on overall data volume, but on how much data was changed. So, your history of changes will take kilobytes even if the overall data takes megabytes. The length of the history is not limited by default, but it can be constrained with the static property UndoRedoManager.MaxHistorySize. This property sets how many of the last operations are stored. The oldest operation will be thrown away from the history when the maximum size is exceeded.
Additionally, let me give some advanced details about references and garbage collection: In a field that stores a reference to an object, it can be substituted by another reference. In .NET, the substituted object is put into the garbage if no more references are. So, this object can be thrown away at any time by the garbage collector. This does not fit our plans because we want to roll back to the old state, including the reference and its object. Luckily, our history holds the old reference. So, the object will not be purged even if the original data model forsook it.
The bottom line is that the old objects are protected from GC until the corresponding operation is removed from the history. It guarantees data consistency, but you should take it into account when you think about consumed memory.
Generics vs. Proxies
There is an alternative method of undo/redo implementation using proxies. Proxies exploit the calling context feature of .NET to seamlessly intercept properties invocations. It allows changes to be logged and rolled back. You can find some articles about that on this site. These are good articles written by really smart people. Here, I would like to summarize the difference between the generic and proxy approaches.
Proxy suggests an "external" way of intercepting changes. It catches a setter call before it reaches the property. Undoing is an external operation, too. To restore the value, proxy invokes a property setter on its own wish. However, there are many side effects: What if the property changes other properties? What if it fires a notification event? What if it checks a business rule against another property that may not be restored yet? The bottom line is that if you have "rich" properties, undo/redo will provoke unpredictable code execution.
Generics come from the "internal" side. This technique intercepts and restores changes beyond the property and its logic. The undo process is completely invisible. Business rules and event notifications will not be repeated. Hereby, application code has no chance to run and see data in inconsistent states during recovery.
I hope you have gotten the difference.
Further Development
I have some advanced features currently under research and prototyping:
- Implementing isolated "areas" where data changes are being accumulated independently. It will be useful in multi-document applications where the user can undo/redo each document separately.
- Enlisting files into transactions. Sometimes your data processing may save and refer some intermediate files, like asset files or banal temporary files. In such cases, the versions of these files should be consistent with the data in memory, which can be rolled back. The Framework will be able to synchronously undo file changes, along with undoing data objects in memory.
- Multi-threading support, with concern to the first two points.
This project has been published on CodePlex so that everybody can contribute to it and gain from it.
History
- July 10, 2007 - Initial version posted
- July 12, 2007 - "Generics vs. Proxies" section added
- July 31, 2007 - Performance sample added
