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.

The basics

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.

Undostack designs: command-based and state-based

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.

Push and Trim commands illustrated

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.)

Advertisements

3 Responses to “How to come undone”

  1. Petr Viktorin Says:

    A bit of an off-topic rant, if you care to read it:
    “A good undo/redo framework should automagically enable or disable the “Save” button”
    Is disabling the Save button whenever the application thinks nothing has changed considered good practice?
    It drives me nuts sometimes, especially when it’s the framework doing this as a default (or making it a simple signal connection) and the app is not communicating with the framework enough.
    Or, more often, when I know the file’s been modified on disk and I want to overwrite with what I have currently open.
    KDE apps, luckily, don’t seem to do this automagic disabling – at least the ones I use. And I’m grateful. Please, don’t disable the Save button, in Kolf or any other editor you might write. Unless you find better reasons than a random lurker’s comment, that is 🙂

  2. Christoph Bartoschek Says:

    I would like to have a non-linear undo stack for most applications like kate. Basically the undo stack should be a tree such that it is always possible to get back into any state that existed. I hate it when parts of the undo history are discarded.

  3. Karellen Says:

    Undo/redo is basically the same as a version control system, but with a new “commit” at every user action. Some version control systems store patches between versions (e.g. CVS, darcs) while others store complete changesets (e.g. git). Undo/redo is just like going back and forth through your version history, with new edits starting from partway through the stack being like starting and switching to a new branch from an old point in history – possibly discarding (or just disconnecting, in git’s terminology) the original HEAD.

    Looking at how various VCSs solve their respective problems (e.g. how git uses packs to stop disk/mem usage spiralling out of control) would be useful for implementing a undo/redo system.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s