UNDO part II general implementation techniques

Introduction

Last time I discussed the semantics of the standard UNDO mechanism found on most GUI based applications. Today I will describe the basic implementation methodologies and next time we shall look at actually engineering the undo mechanism into one's application. As the basic mechanisms of implementing UNDO are few, relatively simple as well as quite easy to understand, today's installment will be quite short.

Snapshots

The most obvious method for implementing UNDO is to simply maintain prior copies of the document. This may require a lot of memory and/or disc space. If, however, a limited number of UNDO steps are retained or the document itself is relatively small, this may be acceptable. One might also consider using this approach when document size is not expected to become very large. This could also be appropriate in a prototype or research implementation. Additionally in a complex system, different parts of the UNDO mechanism may be implemented in different ways and may be appropriate for some elements.

If a hypothetical user of a text editor which simply stored its contents as 8 bit char strings and we assume a typing rate of 40 words per minute with an average word length of 6 letters (counting spaces) - that would be 260 chars per minute. They might be able to type over 100k in a day including letters that they had deleted but had been stored on the UNDO stack. If the document is duplicated at each keystroke we are looking at 100k^2 /2. This would take 5 Gig to store. But an hour of typing would only require 121 Megs of temp files which would be okay for a demo or UX experiment. Limiting the depth to 30 or fewer steps would cut the temporary requirements still farther. For applications that use more data per action, you may also want to do some back- of- the-envelope disk speed calculations and or even tests. 

Action Log Replay

The other very simple approach is to merely log all of the user's actions. Then when the UNDO operation is invoked, the system will merely clear the document and replay the log (less one operation). Obviously the unused operation will have to be held in reserve to implement REDO. It should also be obvious how multiple UNDO and REDO operations can be implemented using this approach. Less obviously, if UNDO is not supposed to affect the clipboard, then one will have to make a copy of the clipboard before re-playing the action log. While this approach also has scalability issues, it will not use excessive amounts of memory and in some instances it may be sufficiently performant.

Snapshot Action Log Replay Hybrid

One could easily hybridize these two methods. For example one could maintain one or more additional copies of the document and editor state along with the user action log. To undo an action the system would start with the most recent of the archived states and only re-execute a small number of user actions. If we only need to support a limited number of UNDOs it might be fine to merely retain a single state. Alternatively we may maintain a set of states. One could imagine a very large number of strategies for deciding how many and which states to retain. But not having used this approach. I cannot report on its relevant merit nor even the merit of this hybrid approach at all. As always, remember not to prematurely optimize your code. You should design your code so that you can easily modify it if there are performance issues and not go down the rabbit hole of optimizing it in places where it is unnecessary. Complex state action log hybrids would seem to fall into this zone. Most modern computers are fast and have a lot of memory so we don’t need to overthink this.

Some untested and potentially excessive ideas include:

1.   Saving a state after some set number of actions.

2.   Using an exponential decay strategy in which fewer older states are stored under the assumption that deep UNDOs are unlikely and that variable latency will not disrupt the user experience.

3.   Use a worker thread to do things like advance save states in the background and limit memory usage.

4.   If we have limited UNDO, keep a single continually updated state that number of actions behind the current document state and maintain an action log that can generate intervening states.

Users may sometimes need to invoke many UNDOs in a row and hold the UNDO key down to use auto repeat. It may be problematic if the time it takes to do an UNDO or REDO is wildly inconsistent.

Generic Differencing

In some domains it might be feasible to use a generic algorithm to compute the difference between two states such that this diff can be used to transition between them. This would only make sense if the diff were generally relatively small and the associated algorithms were relatively performant and simple to implement.

Inverse Actions Stacks

The above approaches are generally quick to implement and may often be possible to wrap around an existing code base. We might even be able to wrap them around applications at the operating system level and not even need to have access to the source code.

However, it will be far more efficient to generate some kind of UNDO object with every action and then store that in a stack. This object could be a function that you run to undo the prior action, or it could be a class with an UNDO function; or it might be an object that must be processed by some other function. It doesn't really matter. This is a lower level orthogonal design decision.

If you are supporting REDO, then running the UNDO action will need to generate a REDO object. This REDO action could be generated by the document editing class when you apply the UNDO to it using the same mechanism that was used to generate the UNDO object in the first place. For instance, a delete action could generate an insert object that would be stored on the UNDO stack. When the user hits INDO the insert object would be popped off the UNDO stack and applied to the document, this would in turn generate a delete object that would be pushed into the REDO stack. A REDO action would simply apply the process in reverse: popping the delete action of the REDO stack, applying it to the document and storing the resulting insert action back in the UNDO stack.

Hence we would not need to write code to generate an insert REDO but could use the delete UNDO generator. Such symmetries might not always exist. It is important to think through exactly what needs to be stored in each object. Also remember that to undo a delete operation your program will need to retain a copy of the object that was deleted and likewise for redoing an insert operation.

Undoing Linklist Edits

In the single track audio editor I have been developing, I store much of the document as a doubly linked list. Among other things, nodes, in the linklist, contain pointers to ranges of audio on the disk. 

Many editing operations consist of merely removing some nodes in a sequence, inserting new sequences into the link list or replacing one sequence with another. As with any linked list one can accomplish this by simply switching a few pointers (two in the case of a deletion and 4 in the case of an insertion of replacement). In the case of a deletion or replacement one must also dispose of the nodes that have been effectively taken out of the linklist. But instead of deleting them we can instead attach them to an UNDO object. When we invoke the UNDO operation we can use the links from the ends of the segment we are reinserting to find the nodes that they need to reattach to.

If we are undoing a replacement operation we can then generate a REDO object to track the re-replaced segment of the link list. When we undo a delete operation or redo and insert we will not have any leftovers but we can instead set the pointers in the UNDO/REDO object to point to the nodes around the edit and set a flag in the object and run a slightly different set of pointer manipulations.

Conclusion 

In many cases none of these simple approaches may address all of the issues required for one's application. However, in the next installment, I will describe ways to combine these different methods and how to implement UNDO in complex system architectures.