How to come undone
March 4, 2010
Dominik Haumann of Kate is writing about the design of Kate’s text buffer. He also linked to an explanation of Kate’s undo/redo system. An interesting coincidence that this shows up on Planet KDE just now, because I’ve spent the last two days rewriting the undo stack of Kolf.
I’m using this opportunity to share my thoughts and experiences with undo/redo frameworks in general, just in case that this information might be useful to someone.
When everything goes right, an undo/redo framework remains mostly invisible. At the heart of each such framework is an undo stack. When you make some input in your program, information about this change is pushed onto the stack. One can then go back to previous versions by traversing this stack. Because the stack is linear, there are only two primitive actions which the user needs to invoke:
- Undo: Go back to the previous version.
- Redo: Go forth to the next version.
The words “previous” and “next” imply that the program keeps track of the current position in the stack. There is another bit of information which is saved in the stack: Besides the current index (where index means a position in the stack, I’ll expand on this in a minute), there is also a clean index, which refers to that state which has been saved on the disk. A good undo/redo framework should automagically enable or disable the “Save” button and add the “[Modified]” flag to the window title when the current index changes.
Select a state, or execute a command?
Until now, I’ve tried to keep the terms as abstract as possible, but what objects are actually stored in the undo stack? There are two basic models, each with its distinct advantages, disadvantages and application areas.
Let’s start with the right one, which I will call the state-based undo stack. In this model, the stack stores a list of states of the document. The current index refers to the state which is currently presented to the user. The “undo” action decrements the current index, and loads the new state into the view. Similarly, “redo” will increment the current index.
The state-based stack is very easy to grasp, but does not scale. Consider a text document of e. g. 300 KB which you type into your text editor from scratch. If the state is only the plain text string, we end up with a hilariously big undo stack which eats 44 GB of your memory. Not quite what we want, eh? Of course, we could constrain the size of the undo stack, but there is a much better solution.
The left stack in the picture is the command-based undo stack (at least in my terminology). It does not store complete states, but commands. One command contains the information which is necessary to convert two adjacent states into each other. In the above example, we would not store 300000 complete documents, but only 300000 character insertion commands. If a character insertion command consists of the cursor position (with line and column number) and the character inserted, a single command is 12 KB big. The whole undo stack would then be 3.5 MB in memory. Much better, isn’t it?
For these reasons, the standard QUndoStack provided by Qt 4 is a command-based undo stack. The state-based undo stack has other advantages: For example, it has a much better performance when selecting an arbitrary state. Let N be the absolute difference between current index and the target index which you want to select. This selection is an O(N) process, because N commands need to be executed. The complexity is O(1) for the state-based undo stack.
The other primitive actions
In the context of the undo stack, I have already identified the primitive actions Undo and Redo, but when the program is launched, the undo stack contains only one state (or no commands). Undo and Redo do not change the size of the stack, so there must be more primitive operations. It turns out there is one further primitive operation on an undo stack: Push adds a new state (or command) just after the current state. If there are states after the current state, these states are deleted before adding the new state. This is necessary to retain the linear shape of the stack. If we would not cut off, there would be two following states after the old current state.
When a new state is pushed onto the stack, the commands following the current index are removed. Imagine correcting a wrong word in a text editor: You press Ctrl+Z to undo this insertion, then type the correct word. The correct word will be pushed on the undo stack, and the incorrect word is removed. After having typed the correct word, there is no way for you to return to the incorrect word.
What I’m doing in Kolf
I already told you that Qt provides a command-based undo stack. And by now, you should have figured out that I won’t be writing about all this if the QUndoStack would suit my needs. In Kolf, I have chosen to use state-based undo stacks for two reasons:
- The states are rather small. The memory footprint is nearly identical for both types of undo stacks.
- The QUndoStack is, due to its design, missing some functionality which I need.
I have to admit that my usecase is rather exotic: I want to split the undo stacks to improve the modularization of my code. In Kolf’s editor, there are several objects which allow editing. Each hole has an editable par score and quite a number of objects on the green. All objects have separate undo stacks, which are (per hole) combined into one undo group. The undo group itself is an undo stack, again; its states are composed of the states of all contained substacks. The grouping can therefore be continued recursively.
Small disclaimer: The relevant code has not yet been committed because it has some severe regressions. (I previously used a command-based stack, which proved not to scale.)