People seem to think that implementing a solid undo system in a program is hard work, and yes for the most part that can be true, but it doesn’t have to be. In this blog post I explore the design of undo/redo and provide some guidelines that simplify such a task. I’ll touch on the fact that there is no right or wrong, that undo can be implemented in a variety of different ways and that the best practice strongly depends on the choice of data structures you designed for your application.
My current pet project from which I explore and take inspiration to write this blog is a growing 3d editor where documents are 3d scenes representing virtual worlds. The data I am architecting for is complex and granular, I expect the scenes to grow to the memory limit of what my machine can handle. This said, if I break a complex program into smaller bits, some of these may compare to a simpler program with a bounded data complexity. This opens opportunities to create reusable designs.
1. Undo is not a feature
People knows what undo is, so I gladly skip that part, but it may not be clear to everyone where undo fits in a software architecture. The first fact to discover is that undo is not a feature, it is a subsystem, a foundational service among others the program is built on top. If I’d draw a system diagram, I would put undo on the same level next to a thread scheduler and a math library.
When somebody thinks of undo as a feature, they log it on a list of things to do and they will triage priorities. When they start on a new project, it will be a while before anyone can use any of it; if nobody is using the program, nobody is going to complain if undo is not there. The lack in “functionality” will not affect any workflow, nor impact productivity. Undo is left on the oblivion of the backlog. At some point, testing begins, QA, early adopters, developers trying to make a demo, and all of a sudden undo is expected to be there and by that time it may be too late to avoid the struggle.
See, undo is like plumbing in a building… more like drain pipes and sewer lines actually. Nobody thinks of it and marvels. Not unless you are Ellis S. Chesbrough, drafting a plan to raise the city of Chicago by jack screws, to install drain pipes that weren’t a thing before.
You see, sewer pipes pass through the foundation of a building. Pipes are laid before pouring the concrete. In this analogy, the concrete slab is made of the data structures, the memory model of your application, and pipes (the undo) are an integral part of it. When memory model and undo are designed together, undo is easy on the developer. When undo is an afterthought, it become intrusive and laborious, and in the worse case scenario, a substantial portion of an application need redesigning, making undo one of the single most expensive tasks you’ll ever do.
There is no single technique that would fit everything. If your application relies on a simple data model, with predictable and bounded complexity, undo can be centralized and automated. When you application is data driven, working on extensive, granular, dynamic data sets, the data complexity mandates for granular undo handling and a mix of a variety of techniques that best suite each case.
Here we will explore a range of possibilities, from a completely automatic undo, which may fit simple data models, to a completely manual undo that can adapt to any data and retrofit an existing app. We will see how different methods can be expressed on top of a very simple set of definitions and rules where a high degree of design freedom is possible.
1.1 Basics of Undo
At its essence, undo is a history of changes in the data within a program. Nowadays it is expected that undo handles a complete history of transformations since some seeding event that produced the initial data, such as launching the program, or loading a document.
Undo must record the sequence of edit events the user executes, and unwind or rewind the changes in the data. An intuitive way to conceptualize this is with 2 opposing stacks: the undo stack is at the bottom, the redo stack is on top of it, flipped upside down. Each change to the data is “recorded” by pushing an undo entry to the top of the undo stack. When the user invokes undo, the topmost entry is popped form the undo stack, executed to restore the previous state in the data, then pushed to the redo stack. As the user keeps on undoing, further undo events pop, execute, and are pushed to the redo stack. The undo stack shrinks, the redo stack grows.
At this point one of a few things can happen. The user decides to redo some of the undone operations. The process is the same but backwards: the flow of undo entries reverses, undo entries pop from the redo stack, they execute, and are pushed back to the undo stack. The quantity of entries across the two stacks remains unchanged, what changes is the “now” point where the two opposing stacks joins. If the user makes some further changes in the data instead, anything left in the redo stack is wiped clean. This is how a traditional undo system works.
1.2 What count as “data”
I did already mention a few time “data”, “transformation to the data” Data is too generic so a clarification is in order. Let’s define:
- Principal data: fundamental, non-constant data in your program that cannot be derived or recomputed from some other data. For example any user defined value is principle data, a ray-tracing acceleration structure that is computed from points and topology in a mesh is not. A clock, a timer, threads and their stack, memory statistics, meta-data of various kind tend to fall out of this category.
- Directly-reachable data: principal data that undoable actions can read or modify directly. In particular this refers to data and data structures that can be accessed by pointer or by index and modified in place. Any immutable or managed data hidden behind some API, which can be retrieved or modified only through some mapping is not considered directly-reachable data. Example, resources accessed by hash or name, and returned by value through setters and getters.
Later these definitions will become clearer.
1.3 Undo, not a command engine
Some designs implement undo following the command pattern. According to this pattern, any action that modifies principle data (and requires undo) is implemented as subclass of a command class. Such an object may look like this:
class Command
{
Command();
virtual ~Command();
virtual bool doit();
virtual void undo();
virtual void redo();
};
It is one way of doing things, but it’s not what I chose. What is the problem with this? First and foremost it imposes a rigid structure and redundant code. Say you have ten ways to modify a single numerical value… Think of a 4×4 transformation matrix. There is a simple “set identity” and a much more complex matrix inversion, SVDs etc… The math for each of the commands is a completely different implementation, each of them requires undo. However, because the ten commands changes the same value, by reasoning as data and algorithms as two separate entities, one could have ten algorithms and only one implementation of undo/redo to swap the data between “before and after”. I can make flexible patters to create editing commands, and I can make flexible undo patterns. A joined pattern for both loses in both fronts.
A different example of what can go wrong with Commands: say you need undo for the creation of some new data. One may think the undo should be the deletion of such data, and redo should be about creating it once more. Such a command should store all the parameters that were used for the construction of the object (the new data) in order to create it again. Deletion may sounds simple enough, and making redo() call doit() seems a win in terms of code simplicity. Now imagine the creation of the object is not a pure function, say that the object creation function reads some context or global variables (global options or environment variables), say you are not even aware of such a thing, or that tomorrow somebody decides to add all of that. Now your redo has a problem: by attempting to create a new object, it cannot guarantee it is going to create an identical one. Sure it can be fixed by making sure the program doesn’t do these things, but sometimes these changes are not easy, or possible, or in code you can control.
From this perspective, undo should not undo an action performed by the user: “an action performed by the user” is an high level concept: Undo should work at a lower level. Whatever that action is, it is a transformation of some principal data. To get rid of the complexity and ambiguity of the “action”, think that undo must restore the previous data, before the edit, while a redo must restore the data after the edit… which makes most undo/redo implementation relatively simple values swap.
Note: while some people firmly believe that computing is made easier by encapsulating and abstracting the data, such as in commands pattern, I firmly believe that computing is made easier by recognizing that data and transformations to it are (should be) distinct.
2. The Undo System
Listing 1 provides a simple, basic definition of the undo system. Depending on your program, you may have a single-document architecture with a global undo (a singleton perhaps), or multiple separate undo tracks, one per document, or one per independent system (more examples later…). Because of this, I don’t attempt to fit the undo system implementation to a specific pattern. You can use a singleton, or instantiate it as part of a context… or anything else that fits your case.
// Undo system
// This is a low-tech implementation of an undo/redo system. It leaves a lot
// of freedom to the developer to do whatever they want in the implementation
// of any undo and redo entry. By keeping it simple, and dependencies free,
// it simplifies the task of adding support of undo to just about anything within
// a program.
class Undo
{
public:
// Undo::Entry is a base struct for a description of some data modification.
// Derived structs are specialized with the implementation to undo and redo
// such a modification. For example, some command implements a change of an
// numerical value stored in some part of the system. The Undo entry subclass
// may specialize to store the original value before the change, along with
// just enough information of where the change was made. The implementation
// will define how to swap such a value with that stored in the entry.
// Entry is very generic and does not make any assumption of what is it that
// is getting undone and redone.
struct Entry
{
Entry();
virtual ~Entry();
// A method to return a string describing the undo entry, this can be
// used to create a GUI listing the current undo/redo stacks and
// let the user to jump between descriptive entries.
virtual const char* getType() const;
virtual void undo();
virtual void redo();
};
// A Track is composed of two stacks, the bottom of which represents the very
// beginning of a sequence of transformations and the very end. The top of the
// stacks joins to the current point in time. Typically, the undone stack is
// empty and everything the user does is pushed to the done stack. As soon as
// the user undoes something, that entry is popped from the done stack and
// pushed to the undone stack. When something is redone, it is popped from the
// undone stack and pushed to the done stack...
struct Track
{
std::vector<Entry*> done; //< stack of entries that can be undone
std::vector<Entry*> undone; //< stack of entries that can be redone
};
Undo();
~Undo();
void clear();
// Undo entries must be allocated and destroyed by the Undo subsystem for a safe
// memory life cycle across modules boundaries. CreateEntry is used to allocate
// a new entry subclass, variadic arguments are passed to the constructor of
// the specific subclass of Entry, e.g.:
// MyUndoEntry* entry1 = Undo::createEntry<MyUndoEntry>();
// MyUndoEntry* entry2 = Undo::createEntry<MyUndoEntry>(arg1, arg2);
template<typename EntryT, typename ...Args>
static EntryT* createEntry(Args&&... params)
{
// There is no good way to implement a function that will call the new
// new operator on subclass that is defined elsewhere. To do that we allocate
// a generic memory block and use the placement new operator to construct
// the specific entry.
// To complete the picture see how memory is safely freed in the destroyEntry
// implementation.
void* block = allocateEntry(sizeof(EntryT), alignof(EntryT));
return new (block) EntryT(params...);
}
// DestroyEntry is mostly used internally to destroy any undo entry. Other than
// that, any entry allocated with createEntry and *not* passed to done(...) method
// must be explicitly destroyed with this method.
static void destroyEntry(Entry* cmd);
// Adds a new entry to the undo track. If any entry is in the redo stack,
// adding a new done entry will flush that content.
void done(Entry* cmd);
// The main undo and redo methods
void undo();
void redo();
bool hasUndo() const
{
return !m_track.undo.empty();
}
bool hasRedo() const
{
return !m_track.undone.empty();
}
private:
static void* allocateEntry(size_t size, size_t alignment);
Track m_track;
};
And here is the implementation to punt in a cpp file.
// Implementation of empty methods for the base undo entry struct
Undo::Entry::Entry() {}
Undo::Entry::~Entry() {}
void Undo::Entry::undo() {}
void Undo::Entry::redo() {}
const char* Undo::Entry::getType() const
{
return "base command";
}
void* Undo::allocateEntry(size_t size, size_t alignment)
{
// Use aligned memory allocator for compatibility. This allow us to support any
// struct alignment the developer may intentionally or inadvertently add to
// their subclasses of Entry.
// An alternative would be to implement a memory pool to let all of Entry memory
// to be store contiguously and reduce pressure of many granular memory
// allocations. Such an effort can be valuable but it is completely independent
// from the implementation of undo system itself, as such it is left out from this
// listing.
return _mm_malloc(size, alignment);
}
void Undo::destroyEntry(Undo::Entry* cmd)
{
if (!cmd) return;
// Mimic delete operator by calling the virtual destructor before freeing the memory
cmd->~Entry();
_mm_free(cmd);
}
Undo::Undo()
{
}
Undo::~Undo()
{
clear();
}
void Undo::clear()
{
for (Entry* cmd : m_track.done)
{
destroyEntry(cmd);
}
m_track.done.clear();
for (Entry* cmd : m_track.undone)
{
destroyEntry(cmd);
}
m_track.undone.clear();
}
void Undo::done(Entry* cmd)
{
m_track.done.push_back(cmd);
// Erase redo stack when a new entry is added to the undo stack
for (Entry* cmd : m_track.undone)
{
destroyEntry(cmd);
}
m_track.undone.clear();
}
bool Undo::undo()
{
if (m_track.done.empty())
return false;
Entry* cmd = m_track.done.back();
m_track.done.pop_back();
cmd->undo();
m_track.undone.push_back(cmd);
}
bool Undo::redo()
{
if (m_track.undone.empty())
return false;
Entry* cmd = m_track.undone.back();
m_track.undone.pop_back();
cmd->redo();
m_track.done.push_back(cmd);
return true;
}
I keep this code simple for readability. I didn’t add any error handling for memory allocations and the like. There are different ways and styles to do that, all of it is orthogonal to the undo system design. Do what fits your programming guideline. Moreover, if a memory allocation for a tiny Undo::Entry fails, all bets are off and the process is doomed anyway.
For Undo::Entry I have chosen inheritance for a couple of reasons:
- The undo entries can be considered plugins to the system. One can go out of their ways to avoid inheritance, but in this case it is arguably a good fit.
- Undo and redo actions need to be memory efficient but not performance critical in their infrastructure. Undo and redo actions are typically executed at the beat of the user UI clicks… If one is worried about optimizing the virtual method calls, they are wasting their time here. And if one is instantiating hundreds of thousands of undo entries per second, their undo actions and data structures are probably wrong to begin with.
Differently than commands, Undo::Entry is simpler: it doesn’t have to know anything about how some data was changed, only that it had changed from A to B. For some type of programs you only need a single implementation of Undo:Entry.
Something I don’t want to leave untouched is how memory allocation need to be done carefully. Undo is a service, likely referred to by many parts of the program, which may be implemented in several dll/dso. Memory allocation across dynamic linked libraries is dirty business. Everything that is allocated from one library must be freed by that library. Failing to do so can result is cryptic heap corruption. For this reason, the undo system provides methods to allocate and destroy entries and these methods are implemented in a module and should never be inline.
An alternative would be to implement a factory for Undo:Entry subclasses, a technique I feel is much more involved, adding lots of boilerplate code for each and every type of undo entry. I tend to avoid that construct, and if you are like me, interested in alternative, flexible patterns, this may be one for you.
Note about “modern” C++
Some folks my react to some of my choices, such as “why not use use unique_ptr and stuff”. Ultimately, the Undo class is a custom container and it is safe to use like it is. If you’d manage to decipher the gobbledygook of a std::map, you’d see that the memory management of the internals of the container are done “be hand” and guaranteed safe by the implementation of the container. The only “issue” left on the table (if we want to call it an issue…) is that if something fails (e.g. throws) between a call to Undo::createEntry() and Undo::done(), you may have a few bytes of a memory leak. Is this possible to happen? Well, it depends on your implementation, but yes. It is likely to happen in practice? No, it is not. If something fails at this level all bets to maintain a functioning undo track are off and the user session is doomed to corrupt memory… a bomb ticking at the clicking sound of Ctrl+Z. By keeping the code simple I increase the chances I get it right to begin with, instead of opening cracks to unforeseen, hard to debug problems in the attempt to cover everything. What I care the most in this article is the concept of Undo, and pedantry is a distraction.
2.1 Wiring the system up
Connecting the undo system entry points to the rest of the program should be simple, beside the fact that this undo system doesn’t do anything yet… Depending on how your program works, and which platform conventions you follow, write the code to map the execution of Undo::undo() and Undo::redo() to the appropriate menu and hotkeys. If you need to gray-out buttons for it, Undo::hasUndo() and Undo::hasRedo() have you covered.
I didn’t add any, but it may be convenient to add methods to enumerate undo/redo entry and query their names/types, to create a drop down in the GUI for example. The Undo::Entry::getType() method is supposed to provide a descriptive string of what each entry does. It is up to the subclasses implementation to provide as much detail as needed, form “Move”, to “Move object abc to [0.5, 0.0, 0.0]” and beyond. As usual, I’d consider YAGNI (You Ain’t Gonna Need It).
3. Undo Patterns
Now that I have some infrastructure to implement undo entries, I can explore different ways this can be achieved. What I presented thus far is very basic and provides for many different techniques. Mix and match of different techniques is possible and I don’t need to pick one. Simplicity and flexibility go far.
To ground all the implementations to follow I define 10 simple rules. Some rules are strict, some are more of a suggestion, but following them as a whole helps to give a cohesive design. Some of the rules are more to guide the design of the data structures in your program than they are about the implementation of undo entries.
- It is imperative that each undo entry must restore directly-reachable data to the exact same state as prior the change. Any principal data must be restored by the undo/redo implementation of an undo entry. Any other data may be updated by queueing/triggering the required recomputation. Undo entries are not supposed to validate the state of any directly reachable data or attempt to gracefully handle any state incongruence.
- Undoable actions don’t mix with plain actions over the same principal data dependencies. Doing so will be against rule #1. Undo is a viral feature, once undo is implemented for some edits of some data, everything that is allowed to modify such data must support undo as well.
- Pay attention to principal data allocation and deletion, instead of deleting, hold on to it by transferring ownership to the undo action. The undo of a “delete object” may not be a “create object”, and vice-versa. Memory persistency greatly simplifies the implementation of undo entries: undo to a value change may become as simple as storing the pointer to such a variable to overwrite its value.
- Transferring data ownership to the undo system should not be a forcing factor to adopt reference counting. It must be clear if the data is owned by the application or by the undo system. Most of the time, undo actions refers to data in use (case A) and occasionally they retain data not in use since the user deleted something (case B). Case A shouldn’t use reference counting to the data. According to rule #1 there is no reason for the data to have been deallocated prior an undo event execution to change it, hence there should be no reasons for undo to attempt reference counting data to guaranteed its lifetime. To adopt reference counting as defensive-programming (to make sure data is “still around” when some undo/redo entry executes) is a poor practice that may make undo/redo bugs much harder to isolate: the undo may attempt to change data held by the undo entry but not in use by the system anymore, thus hiding the spot of some critical failure, and preventing memory debugging tools such as valgrind to provide any clue. For case B, the transfer of ownership from the active data set to the undo system make it clear data is not shared, not in use in the application anymore.
- When designing a data structure, make strong demarcation between principal data and data that can be recomputed at any moment from it. Retaining data in the undo system adds to the app memory footprint. Design such that non principal data can be easily released and recreated. Release such data when transferring resources to it the undo system, make sure the redo action also releases non-principal data, and assure the undo action triggers/flags its recomputation.
- Avoid accessing data by pointer that your never want to retain in the undo system because it is simpler to recreate than it is practical to retain. Deleting and reallocating data may invalidate pointers and cause memory corruption. Consider you will need to design systems to access such data by indices instead, or consider making such data not directly reachable. For such cases, question if the data should be considered principal and directly reachable, and design accordingly, otherwise bite the bullet and retain that data.
- For indexed resources and data structure. It is important that any undo entry must preserve the ordering of the data in a container. For example, if an action consists in the deletion of the Nth element of a vector, undo must insert it back to the same index. This increases predictability even if the ordering within the container is not relied upon.
- Try to implement simple, reusable undo entries. For example, instead of many specific subclasses to undo translation, rotation, and scale of an object, consider to handle transformation as a whole.
- For long, consecutive chain of similar entries, consider undo actions that can be collapsed into one. This may be useful to implement compression of the undo stack.
- Be conscious of how much memory your undo entries will use; try to design compact data structures where every byte counts.
3.1 Serialized data
This method is conceptually simple and works well in a variety of cases, including any program where the quantity of principal data is limited and can be easily and efficiently serialized to a contiguous memory block. Starting simple, say all you have in your program is a single struct with plain old data, no pointers to other memory blocks or containers. Say that such data is relatively small to the extent that making many copies of it is not a concern. Then undo is very easy!
// A template struct to undo change to any copyable struct
template<typename T>
struct UndoStruct : Undo::Entry
{
UndoStruct(T* data)
:dataRef(data), data(*data)
{}
virtual ~UndoStruct()
{}
virtual void undo()
{
std::swap(data, *dataRef)
}
virtual void redo()
{
std::swap(data, *dataRef);
}
T* dataRef; //< keep a pointer to the data we need to change
T data; //< the data before the change
};
Undo undoSystem; //< Instantiation of the undo system
// Suppose this is the data we need to add undo support:
struct AppData appData;
[...]
{
// Usage: before making any change to the app data
UndoStruct<AppData>* entry = undoSystem.createEntry<AppData>(&appData);
// Edit values in the struct
[...]
undoSystem.done(entry);
}
[...]
// Later, to undo the change:
undoSystem.undo();
// Resync the app data if necessary
myAppDataResync();
If your app can comprehensively serialize all of its state, and such state is small. This undo pattern is all you need for a complete undo system. It becomes possible to hide the undo behind some beginEdit/endEdit calls in the system, and nobody will ever have to know undo is there… But, there is but! This only works if the data is small. Each new undo entry will carry a copy of the data and long undo queues will increase data usage in your program. Say the data at hand is 1MiB. One thousand undo entries will approach 1GiB.
There are several things you can consider to reduce the undo stack footprint. Undo compaction is one: because each undo caries the entire principal data in the application, it is possible to erase entries in the undo stack without breaking rule #1. What can be erased highly depends on what it is that is getting changed. Suppose it is a text editor that we are talking about. Undo entries may be inserted for each single keypress, but after a word typed in letters form the previous word may be collapsed to undo one word at a time. At some point entire sentences are undo at once… I don’t have code for this, but since the undo system have no idea what data is dealing with, some tagging of each undo entry is required to orchestrate what can be evicted and when.
3.2 Serialized delta
A refinement over the first approach is to compare the data before and after the change and extract only the bytes that changed. This could dramatically reduce the payload of an undo entry to just a few bytes, making seemingly “infinite” undo stacks possible. Here we begin to trade the simplicity of the concept with the complexity of the implementation and its efficiency.
I start simple, very simple… Here is a sample program that computes a binary delta of some struct. A very convenient way to do so is by xor. Do you remember that classic interview question: “How do you swap two variables without using a third one?” Doh! Who knew we could use that in practice!? Xor is convenient way to extract a bitwise difference between two operands. Let x = before ^ after; Undo is before = after ^ x; Redo is after = before ^ x;
// An utility to print a vector of values, just to support this example.
template<typename Line>
void printLine(const char* header, Line lineClosure)
{
printf(header);
lineClosure();
printf("\n");
}
// For each byte in inout, compute: inout = inout ^ src
// Assumes src and inout points to buffers of same size.
void xorDelta(const void* src, size_t size,
void* inout)
{
const uint8_t* data = (const uint8_t*)src;
uint8_t* target = (uint8_t*)inout;
// Naive loop to xor each byte. In a real implementation we would do this using
// 64 bits unsigned or wider vector registers to process as many bytes as we
// can with each instruction.
for (int i = 0; i < size; ++i)
target[i] ^= data[i];
}
int main(int argc, char** argv)
{
// Here is some arbitrary data as a starting point
struct Data
{
int a[16];
};
Data x;
for (int i = 0; i < 16; ++i) x.a[i] = i;
// Print the initial values
printLine("Data: ", [&]() { for (int i = 0; i < 16; ++i) printf(" %3d", x.a[i]); });
// Copy data before change
uint32_t* xor = (uint32_t*)malloc(sizeof(Data));
memcpy(xor, &x, sizeof(Data));
// Make a change to the data and print values again
x.a[5] = 50;
x.a[11] = 100;
printLine("Edit: ", [&]() { for (int i = 0; i < 16; ++i) printf(" %3d", x.a[i]); });
// Compute the xor delta and print, all values will be zeros but the one changed
xorDelta(&x, sizeof(Data), xor);
printLine("Xor: ", [&]() { for (int i = 0; i < 16; ++i) printf(" %3u", xor [i]); });
// Undo the change by re-applying the xor to the data.
xorDelta(xor, sizeof(Data), &x);
printLine("Undo: ", [&]() { for (int i = 0; i < 16; ++i) printf(" %3d", x.a[i]); });
// Redo the change by re-applying the xor to the data.
xorDelta(xor, sizeof(Data), &x);
printLine("Redo: ", [&]() { for (int i = 0; i < 16; ++i) printf(" %3d", x.a[i]); });
free(xor);
return 0;
}
// Output produced by this listing:
Data: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Edit: 0 1 2 3 4 50 6 7 8 9 10 100 12 13 14 15
Xor: 0 0 0 0 0 55 0 0 0 0 0 111 0 0 0 0
Undo: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Redo: 0 1 2 3 4 50 6 7 8 9 10 100 12 13 14 15
A few things I like about this delta approach: a) the implementation is completely agnostic about the data, pointers, float values with NaNs, and comparison will work just fine; what matters is that it is a contiguous memory block; b) what I store in the undo entry don’t need to be updated to go from undo to redo; if we were swapping values instead, we would need to swap the content of the undo entry too, making compression tricky; c) Entry::undo and Entry::redo implementation is the same; d) what results is a easily compressible block of memory that contains a lot of zeros that are easy to eliminate. Content like this can be compressed in many different ways. RLE (Run Length Encoding) is simple to implement and can be rather effective. Here is a slightly naïve implementation of RLE specialized to eliminate zeroes. By keeping it simple I can present it as part of this post.
// Naive implementation of an RLE encoding to skip zeroes in the data. The compressed stream is
// divided in windows of values, each beginning with a header providing the length of the
// window. A template argument (UINT_T) defines the value entries in the compressed stream.
// Any unsigned int of any width is suitable, pick the widest unsigned that fits the
// alignment of the data to compress. Windows can be of two types:
// - skip window represents zeroes in the xor data, the header is the number of zeroes.
// - data window containing a number of consecutive elements of raw data.
// The stream terminates when a window header has a value of zero.
template<typename UINT_T>
std::vector<UINT_T> xorDeltaRleCompress(const void* src, size_t size, void* inout)
{
static_assert(std::numeric_limits<UINT_T>::is_signed == false, "xorDeltaRleCompress only works with unsigned types");
static_assert(sizeof(UINT_T) <= sizeof(uint64_t), "maximum unit size is 8 bytes");
// Verify size is a multiple of sizeof(UINT_T)
assert((size & (sizeof(UINT_T) - 1)) == 0);
// Process the stream in sizeof(UINT_T) byte chunks
size /= sizeof(UINT_T);
const UINT_T* data = (const UINT_T*)src;
UINT_T* target = (UINT_T*)inout;
std::vector<UINT_T> resultStream;
// Add k_dataWindowOffset counter to encode a data window
constexpr UINT_T k_skipWindowLimit = std::numeric_limits<UINT_T>::max() >> 1;
uint64_t counterSkip = 0;
uint64_t counterData = 0;
uint64_t counterDataPosition = 0;
for (size_t i = 0; i < size; ++i)
{
UINT_T xor = target[i] ^ data[i];
if (xor == 0)
{
// Begin or continue a skip window
if (counterData)
{
// If we were in a data window, close it by storing the window lenght.
resultStream[counterDataPosition] = k_skipWindowLimit + counterData;
counterData = 0;
}
counterSkip++;
if (counterSkip == k_skipWindowLimit)
{
// Store skip window when we overflow the max count of 127
resultStream.push_back(counterSkip);
counterSkip = 0;
}
}
else
{
if (counterSkip)
{
// If we were in a skip window, close it by storing it to the stream.
resultStream.push_back(counterSkip);
counterSkip = 0;
}
if (counterData == 0)
{
// Start a new data window by reserving a spot for the window length
counterDataPosition = resultStream.size();
resultStream.push_back(0);
}
// Push one byte of data to the data window
counterData++;
resultStream.push_back(xor);
if (counterData == (k_skipWindowLimit + 1))
{
// Don't make the window data overflow.
resultStream[counterDataPosition] = k_skipWindowLimit + counterData;
counterData = 0;
}
}
}
// Finalize any open window.
if (counterData)
{
assert(counterSkip == 0); //< no way both windows should be open at once.
resultStream[counterDataPosition] = k_skipWindowLimit + counterData;
}
#ifndef NDEBUG
// Don't need to store any trailing skip window unless we want to validate the stream
// will decode to the exact length. Implementation should enforce correctness so
// let's do this only in debug.
else if (counterSkip)
{
resultStream.push_back(counterSkip);
}
#endif
// End the stream
resultStream.push_back(0);
return resultStream;
}
template<typename UINT_T>
void xorDeltaRleApply(const std::vector<UINT_T>& deltaStream, size_t size, void* inout)
{
static_assert(std::numeric_limits<UINT_T>::is_signed == false, "xorDeltaRleCompress only works with unsigned types");
static_assert(sizeof(UINT_T) <= sizeof(uint64_t), "maximum unit size is 8 bytes");
UINT_T* target = (UINT_T*)inout;
// Number to subtract from counter to decode data window length
constexpr UINT_T k_skipWindowLimit = std::numeric_limits<UINT_T>::max() >> 1;
// Decode the stream
const UINT_T* stream = deltaStream.data();
while (*stream)
{
uint64_t count = *(stream++);
bool skip = count <= k_skipWindowLimit;
if (skip)
{
// Skip window
target += count;
}
else
{
// Data window
count -= k_skipWindowLimit;
while (count --> 0)
{
*(target++) ^= *(stream++);
}
}
}
// Debug validation the stream decoded to the correct length
assert(size == sizeof(UINT_T) * (target - (UINT_T*)inout));
}
Data changes over a one variable at a time tends to be common, in which case the RLE stream will contain 2 blocks, one with how many zeroes to skip, one with data for some consecutive bytes. For versatility I have chosen a template over the xor data unit. The most generic possible specialization is for uint8_t, which is also the slowest and less compact. Each skip window can encode as many as 127 bytes, which means that the theoretical compression limit of a stream filled with zeros is 127:1. For a small struct this may be ideal, for larger data buffers, this may be limiting. At 1MiB, compression at its limit would produce a stream of at least 8KiB in size. By specializing the template for uint16_t the maximum compression would be 16,384:1, and the size of the compressed stream at the limit would be 64 bytes. For uint32_t, maximum compression of the same block would be 262,144:1 and the zeroed stream would encode in 4 bytes. Going wider means gaining efficiency in computation and may add some data footprint overhead in case the data change is spread every few bytes across the entire buffer, this may result in many windows and the for worse case scenario, compressed stream may end up 1/3 longer than the uncompressed buffer. How often can this happen? It depends on the data and the nature of the change. I could protect against that and store the uncompressed xor stream when it happens.
Here is an Undo::Entry implementation of the xor RLE compression technique, along with the modified example:
template<typename T, typename EncodingType = uint32_t>
struct UndoStruct : Undo::Entry
{
UndoStruct(T* data)
:dataRef(data)
{
stagingArea = (EncodingType*)_mm_malloc(sizeof(T), alignof(EncodingType));
if (stagingArea)
memcpy(stagingArea, data, sizeof(T));
}
virtual ~UndoStruct()
{
if (stagingArea)
{
_mm_free(stagingArea);
stagingArea = nullptr;
}
}
bool compress()
{
static_assert(alignof(T) >= sizeof(EncodingType), "Verify alignement");
if (!stagingArea)
return false;
xorStream = xorDeltaRleCompress<EncodingType>(dataRef, sizeof(T), stagingArea);
_mm_free(stagingArea);
stagingArea = nullptr;
return true;
}
virtual void undo()
{
assert(!xorStream.empty());
xorDeltaRleApply(xorStream, sizeof(T), dataRef);
}
virtual void redo()
{
assert(!xorStream.empty());
xorDeltaRleApply(xorStream, sizeof(T), dataRef);
}
T* dataRef; //< keep a pointer to the data we need to change
std::vector<EncodingType> xorStream;
// The data before the change, held temporarily is a staging memory block for the purpose
// of computing compression.
EncodingType* stagingArea = nullptr;
};
// Example
int main(int argc, char** argv)
{
Undo undoSystem;
constexpr int size = 16;
// Here is some arbitrary data as a starting point
struct Data
{
uint32_t a[size];
};
Data x;
for (int i = 0; i < size; ++i) x.a[i] = i;
// Print the initial values
printLine("Data: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// Copy data before change
UndoStruct<Data>* undo = undoSystem.createEntry<UndoStruct<Data>>(&x);
// Make a change to the data and print values again
x.a[5] = 50;
x.a[11] = 100;
printLine("Edit: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// Compute the xor delta and compress it using RLE
undo->compress();
undoSystem.done(undo);
// Undo the change
undoSystem.undo();
printLine("Undo: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// Redo the change
undoSystem.redo();
printLine("Redo: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
return 0;
}
// Output produced by this listing:
Data: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Edit: 0 1 2 3 4 50 6 7 8 9 10 100 12 13 14 15
Undo: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Redo: 0 1 2 3 4 50 6 7 8 9 10 100 12 13 14 15
Data compression is fun, but never completely trivial. A good alternative is to resort to a general purpose compression library, such as LZ4. Because the xor stream it is predominantly made of zeroes, it is ideal to compress even with the lowest compression setting, LZ4 is very fast and it does wonders. If you need more than my wacky xor RLE compression, this is an option.
To recap, the serialized delta so far described can be appropriate for any contiguous data block, serialization or not. Any struct that fits the criteria can be handled this way, even when it’s not the whole data set. This is the first step into the adoption of more granular undo events, where we step away from auto-magic and gain control and (hopefully) efficiency.
3.3 Targeted opaque data
What if instead of backing up a complete block of memory (with or without compression) I only target specific regions of it? If I know which member variable changed, I can implement an Undo::Entry that swaps just that precise value and nothing else. Picture this common scenario, I am in a 3d editor and I am typing 3d transformation values in a property panel. I move the object to coordinates [0, 10, 0], I focus the cursor to the “Translation” control and start typing: 0, tab, 10, tab, 0, enter. Then I proceed with Euler “Rotation”: 45, tab, 0, tab, 0, enter, and so on and so forth… Each time the cursor leaves a field after typing a value, that is likely considered a value change, at least this is the case in my program. The above sequence is 6 distinct undo events, each changing a single floating point value in some struct. I believe it is well worth to specialize for those changes.
An approach is to specialize an undo entry to store a pointer to some filed in a struct and the value of such a variable before a change. Just with this little information we can restore the change by swapping before and after.
// An Undo::Entry template struct to undo a single opaque value at some arbitrary memory
// location, typically a member variable of a struct. The struct retains a pointer to the
// variable to change along with its original value. Undo/redo will swap the value.
// For EncodingType favor integral types to floating point values, which makes simpler to
// compare any value including denormals and NaNs.
template<typename EncodingType = uint32_t>
struct UndoSingleOpaqueValue: Undo::Entry
{
template<typename Type>
UndoSingleOpaqueValue(Type* data)
:dataRef((EncodingType*)data), data(*dataRef)
{
// Make sure we have the correct size, while maintaining flexibility with types
static_assert(sizeof(Type) == sizeof(EncodingType), "check size");
}
virtual ~UndoSingleOpaqueValue()
{}
bool didChange() const
{
return *dataRef != data;
}
virtual void undo()
{
std::swap(*dataRef, data);
}
virtual void redo()
{
std::swap(*dataRef, data);
}
EncodingType* dataRef; //< keep a pointer to the data we need to change
EncodingType data; //< copy of the data before the change
};
// Example
int main(int argc, char** argv)
{
Undo undoSystem;
constexpr int size = 16;
// Here is some arbitrary data as a starting point
struct Data
{
uint32_t a[size];
};
Data x;
for (int i = 0; i < size; ++i) x.a[i] = i;
// Print the initial values
printLine("Data: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// Copy data before change
auto undo = undoSystem.createEntry<UndoSingleOpaqueValue<uint32_t>>(&(x.a[5]));
// Make a change to the data and print values again
x.a[5] = 53;
printLine("Edit: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// We can destroy the undo entry if data didn't change.
// Todo: should didChange be part of Undo::Entry virtual inteface?
if (undo->didChange())
undoSystem.done(undo);
else
undoSystem.destroyEntry(undo);
undoSystem.undo();
printLine("Undo: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
undoSystem.redo();
printLine("Redo: ", [&]() { for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
return 0;
}
// Output produced by this listing:
Data: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Edit: 0 1 2 3 4 53 6 7 8 9 10 11 12 13 14 15
Undo: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Redo: 0 1 2 3 4 53 6 7 8 9 10 11 12 13 14 15
Sometimes it is not enough to swap some values, especially if some non-principal data need updating with each change, or if something else in the program need to be notified that something changed. Say we have a geometry and after moving one of its points, its bounding box need to be updated. According to my definitions, points are principal data and the bounding box is not: the bonding box is derived from the points and never modified directly. We would need the undo entry to know how to trigger that computation. For this we need a variant of UndoSingleOpaqueValue that can capture a lambda:
// An Undo::Entry template struct to undo a single opaque value at some arbitrary memory
// location, typically a member variable of a struct. The struct retains a pointer to the
// variable to change along with its original value. Undo/redo will swap the value and
// execute some update lambda to trigger recomputation of synchronization of associated
// non principal data.
// It is important than any data captured by the update lambda is captured explicitly and
// by value so that it remains embedded in the struct instantiation.
// To create this Undo::Entry use MakeUndoSingleOpaqueValue, example:
// Data* dataPtr = [...];
// Context* context = [...];
// auto undo = MakeUndoSingleOpaqueValue(&(dataPtr->someField), [context, dataPtr]()
// {
// dataPtr->update(context); //< some arbitrary update
// });
//
template<typename EncodingType, typename UpdateClosure>
struct UndoSingleOpaqueValueClosure : Undo::Entry
{
UndoSingleOpaqueValueClosure(EncodingType* data, UpdateClosure& updateClosure)
:dataRef((EncodingType*)data), data(*dataRef), updateClosure(updateClosure)
{
}
virtual ~UndoSingleOpaqueValueClosure()
{}
bool didChange() const
{
return memcmp(dataRef, &data, sizeof(EncodingType)) != 0;
}
virtual void undo()
{
std::swap(*dataRef, data);
updateClosure();
}
virtual void redo()
{
std::swap(*dataRef, data);
updateClosure();
}
EncodingType* dataRef; //< keep a pointer to the data we need to change
EncodingType data; //< copy of the data before the change
UpdateClosure updateClosure;
};
template<typename Type, typename UpdateClosure>
UndoSingleOpaqueValueClosure<Type, UpdateClosure>* MakeUndoSingleOpaqueValue(Type* data, UpdateClosure& updateClosure)
{
return Undo::createEntry<UndoSingleOpaqueValueClosure<Type, UpdateClosure>>(data, updateClosure);
}
int main(int argc, char** argv)
{
Undo undoSystem;
constexpr int size = 16;
// Here is some arbitrary data as a starting point
struct Data
{
// Principal data the user can enter and change
int a[size];
// Non-principal data that is derived from principal data
int lowerBound;
int upperBound;
void updateRange()
{
lowerBound = upperBound = a[0];
for (int i = 1; i < size; ++i)
{
lowerBound = std::min(lowerBound, a[i]);
upperBound = std::max(upperBound, a[i]);
}
}
};
Data x;
for (int i = 0; i < size; ++i) x.a[i] = i;
x.updateRange();
// Print the initial values
printLine("Data: ", [&]() { printf("Bounds[%3d, %3d] ", x.lowerBound, x.upperBound); for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// Create undo entry before making changes to the data
// Capture explicitly and only by values to pointers of objects that are persistent
Data* xPtr = &x;
auto undo = MakeUndoSingleOpaqueValue(&(x.a[5]), [xPtr]()
{
xPtr->updateRange();
});
// Make a change to the data, update non-principal data and print values again
x.a[5] = 53;
x.updateRange();
printLine("Edit: ", [&]() { printf("Bounds[%3d, %3d] ", x.lowerBound, x.upperBound); for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
// We can destroy the undo entry if data didn't change.
// Todo: should didChange be part of Undo::Entry virtual inteface?
if (undo->didChange())
undoSystem.done(undo);
else
undoSystem.destroyEntry(undo);
undoSystem.undo();
printLine("Undo: ", [&]() { printf("Bounds[%3d, %3d] ", x.lowerBound, x.upperBound); for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
undoSystem.redo();
printLine("Redo: ", [&]() { printf("Bounds[%3d, %3d] ", x.lowerBound, x.upperBound); for (int i = 0; i < size; ++i) printf(" %3d", x.a[i]); });
return 0;
}
// Output produced by this listing. Notice the bounds getting updated:
Data: Renge[ 0, 15] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Edit: Renge[ 0, 53] 0 1 2 3 4 53 6 7 8 9 10 11 12 13 14 15
Undo: Renge[ 0, 15] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Redo: Renge[ 0, 53] 0 1 2 3 4 53 6 7 8 9 10 11 12 13 14 15
The implementation of the undo entry itself is very generic, but the lambda allows to trigger very specific update events, making this solution flexible.
A further extension to this pattern would be to allow multiple opaque values to be changed at once. It can be implemented in a variety of ways:
- by adding a container for pairs of pointer and value
- by allowing to specify a size of consecutive values following in memory the first
- by using a vector of UndoSingleOpaqueValue instances and a wrapper Undo::Entry to execute them.
3.4 Wrapper entries
Method #3 in previous section introduces the idea of wrappers, which allow modularization and composition. For example, can the lambda in UndoSingleOpaqueValueClosure be a feature added to any of the Undo entry patterns described so far? Let’s give it a go:
// An Undo::Entry template struct to undo wrap the execution of another arbitrary Undo::Entry
// and execute some update lambda to trigger recomputation of synchronization of associated
// non principal data.
// It is important than any data captured by the update lambda is captured explicitly and
// by value so that it remains embedded in UndoClosure instantiation.
// To create this Undo::Entry use MakeUndoClosure, example:
// Undo::Entry* undoEntry = Undo::createEntry(...);
// auto undo = MakeUndoClosure(undoEntry, [context, dataPtr]()
// {
// dataPtr->update(context); //< some arbitrary update
// });
//
template<typename UpdateClosure>
struct UndoClosure : Undo::Entry
{
UndoClosure(Undo::Entry* entry, UpdateClosure& updateClosure)
:entry(entry), updateClosure(updateClosure)
{
}
virtual ~UndoClosure()
{
Undo::destroyEntry(entry);
}
virtual void undo()
{
entry->undo();
updateClosure();
}
virtual void redo()
{
entry->redo();
updateClosure();
}
Undo::Entry* entry;
UpdateClosure updateClosure;
};
template<typename UpdateClosure>
UndoClosure<UpdateClosure>* MakeUndoClosure(Undo::Entry* entry, UpdateClosure& updateClosure)
{
return Undo::createEntry<UndoClosure<UpdateClosure>>(entry, updateClosure);
}
To make this pattern widely useful I may have to formalize some optional virtual methods in Undo::Entry interface, such as didChange() or compress() or anything else useful. I decided not to add these in the description earlier on, this to develop infrastructure when it makes sense to do so. The example at the section 3.3 could be modified by constructing the undo entry this way instead:
// Create undo entry before making changes to the data
Undo::Entry* entryToWrap = Undo::createEntry<UndoSingleOpqaueValue<uint32_t>>(&(x.a[5]));
// Wrap the undo entry with a lambda to update data bounds
// Capture explicitly and only by values to pointers of objects that are persistent
Data* xPtr = &x;
Undo::Entry* undo = MakeUndoClosure(entryToWrap, [xPtr]()
{
xPtr->updateRange();
});
I hope it is easy to see how I could create an undo entry container with a vector of entries that executes at once.
struct UndoVector : Undo::Entry
{
UndoVector(std::vector<Undo::Entry*>&& entries)
:entries(std::move(entries))
{
}
virtual ~UndoVector()
{
for (size_t i = 0; i < entries.size(); ++i)
Undo::destroyEntry(entries[i]);
entries.clear();
}
virtual void undo()
{
// Undo in reverse order
for (size_t i = entries.size(); i --> 0;)
entries[i]->undo();
}
virtual void redo()
{
// Redo in forward order
for (size_t i = 0; i < entries.size(); ++i)
entries[i]->redo();
}
std::vector<Undo::Entry*> entries;
};
// Example
// Create undo entry before making changes to the data
std::vector<Undo::Entry*> entries;
entries.push_back(Undo::createEntry<UndoSingleOpqaueValue<uint32_t>
>(&object.width);
entries.push_back(Undo::createEntry<UndoSingleOpqaueValue<uint32_t>>(&object.depth);
entries.push_back(Undo::createEntry<UndoSingleOpqaueValue<uint64_t>>(&object.particlesCount);
// Transfer ownership of undo entries to an UndoVector to combine them as a single undo event.
Undo::Entry* undo = Undo::createEntry<UndoVector>(entries);
// Make changes to the data
[...]
undoSystem.done(undo);
3.5 Custom entries
Some times it is not possible to fit an exiting pattern into a specific case. This prompts for the creation of a variety of specific undo entries. Because I didn’t adopt the formalism of a factory to handle the creation of undo entries, it is easy to code in a simple solution to a specific data edit. This is particularly true with managed data and non reachable data, where we don’t have the luxury of altering the data in its plain form. For the times where we need to query objects and state from opaque interfaces, getters and setters we have two options:
- embed the undo behind such interfaces. It may complicate the undo system, which may become a state machine with beginUndo/endUndo to group together a myriad of tiny undo events happening behind the API. This may also add a unwanted dependency between subsystems. You may not have such control over some APIs.
- Code the exact undo action you need right on the spot.
// Some function in the guts if the program to edit some content...
void Editor::toggleVisibility(Context* ctx, int objectHandle)
{
// Validation...
[...]
// Define a local entry to undo a specific set of calls only done in this function
struct UndoObjectVisibility : Undo::Entry
{
UndoObjectVisibility(Context* ctx, int objectHandle)
:ctx(ctx), objectHandle(objectHandle)
{
visibility = ctx->getObjectVisibility(objectHandle);
}
virtual ~UndoObjectVisibility()
{}
virtual void undo()
{
bool currentVisibility = ctx->getObjectVisibility(objectHandle);
ctx->setObjectVisibility(objectHandle, visibility);
visibility = currentVisibility;
}
virtual void redo()
{
bool currentVisibility = ctx->getObjectVisibility(objectHandle);
ctx->setObjectVisibility(objectHandle, visibility);
visibility = currentVisibility;
}
Context* ctx;
int objectHandle;
bool visibility;
};
Undo::Entry* undo = Undo::createEntry<UndoObjectVisibility>(ctx, objectHandle);
// Make the change
bool currentVisibility = ctx->getObjectVisibility(objectHandle);
ctx->setObjectVisibility(objectHandle, !currentVisibility);
m_undoSystem.done(undo);
}
Hopefully you can appreciate that data abstraction and encapsulation may look sleek at first, but it turns into a lot of complications when a program grows in complexity, and something like hiding everything behind setters and getters seems clean, it may turn into lots of code… If the API you are dealing with (and I say you, because I don’t have much of this in my program) has a consistent design, you may be able to pack the entire implementation of an entry like this behind a macro and make it look like this:
#define DELARE_UNDO_FOR_CONTEXT(type, method) \
struct Undo#method : Undo::Entry \
{ \
Undo#method(Context* ctx, int objectHandle) \
:ctx(ctx), objectHandle(objectHandle) \
{ \
visibility = ctx->get#method(objectHandle); \
} \
virtual ~Undo#method() \
{} \
\
virtual void undo() \
{ \
bool currentVisibility = ctx->get#method(objectHandle); \
ctx->set#method(objectHandle, visibility); \
visibility = currentVisibility; \
} \
\
virtual void redo() \
{ \
bool currentVisibility = ctx->get#method(objectHandle); \
ctx->set#method(objectHandle, visibility); \
visibility = currentVisibility; \
} \
\
Context* ctx; \
int objectHandle; \
type visibility; \
}
// Some function in the guts if the program to edit some content...
void Editor::toggleVisibility(Context* ctx, int objectHandle)
{
// Validation...
[...]
DELARE_UNDO_FOR_CONTEXT(bool, ObjectVisibility);
Undo::Entry* undo = Undo::createEntry<UndoObjectVisibility>(ctx, objectHandle);
// Make the change
[...]
m_undoSystem.done(undo);
}
void Editor::editSpeed(Context* ctx, int objectHandle, float speed)
{
// Validation...
[...]
DELARE_UNDO_FOR_CONTEXT(float, Speed);
Undo::Entry* undo = Undo::createEntry<UndoSpeed>(ctx, objectHandle);
// Make the change
[...]
m_undoSystem.done(undo);
}
On the plus side, macros are easy to refactor and update. They eliminate a lot of boilerplate code. On the flip side they are a mess to debug, but for some cases like these they may be the appropriate tool to get yourself out of an abstract API mess you may have no control over. Hopefully you don’t need a lot of these. If you do it’s a sign your program grew without accounting for undo and now you are retrofitting.
4. Conclusion, for now…
Implementing undo can be a lot of work, but done the right way it doesn’t have to be. Here we explored my design of an undo system, which I find versatile. I have not completed this exploration, this is only part 1 and the length of this text is stretching what wordpress editor is able to handle. Each and every keystroke is getting slower… I wonder if they have a poor implementation of undo…
In part 2 I will elaborate on editing data in containers, creation and deletion of complex data structures and transfer of data ownership. As usual, I hope you enjoy this series.
Art, Tech and other Nonsense 
Just have to chime in with a *Thank You!* This is such an excellent resource, finding anything about undo online – especially at this level and so related to what I do – is incredibly hard. And with your prior posts about manipulators, well, I’m hooked. Thank you so much for sharing!
LikeLike
You are welcome. Glad this is useful to you.
LikeLike
Thank you very much Max.
Cedric.
LikeLike
I join the choir to praise your work! I am currently working on a undo system and the things you present will help me a lot. I really like the whole xor delta thing, that is super clever. Thanks
LikeLike
Great to read a post that doesn’t pretend that some command pattern is enough.
LikeLike