Empirical research (we asked tigert ;) indicates that people like a big undo stack (tigert uses 24 levels of undo!). The only limit for users usually is the available memory, and, as such is a tough decision the user should not need to be concerned with as much. Reducing the memory an undo-step requires would allow us to use a much higher undo setting (even unlimited).

The following proposal contains a few "must have"-proposals, but most of the stuff is quite demanding, i.e. an innovation.

2. Contents of an undo step

Each undo step must store the following:

an equivalent to the PDB call required to execute that change, including the context that was in effect during the call. more than one PDB call might be necessary (e.g. layer_new, drawable_fill and add_layer), unless each atomic step (i.e. action in the ui) can be represented using a single PDB call.
A "thumbnail" (e.g. 32x32 pixel in xv's P7 format) of the changed area, so the user can quickly navigate to older undo steps.
A user-editable comment (esp. when we have unlimited undo)
A flag that tells wether the undo step is to be executed normally or reversed (see the next part).
A flag (which could be optimized away) that tells wether the action modifies existing pixel data or creates new data.

For performance reasons, some undo steps (recent ones) should store a diff of the actual pixel data, so that undo/redo can be done fast, at the expense of memory.

3. A tree-like undo

Especially with an unlimited undo stack, the ability to make branches (so that alternative branches created while exploring possible effects don't get lost) and the ability to annotate certain steps make for some pretty rcs-like features.

Managing this, however, is too complex for the user, and should be left to some rcs/cvs-type-plug-in where concious checkpoints can be made.

A way to simplify this tree-structure into a simple linear list (which can be managed quite nicely using the current undo/redo methodology) would be to reverse the branch instead of discarding it, and putting the new change on top of the undo stack.

As an example, consider an image with 5 operations on the undo stack (1 is the newest, 5 is the oldest):

Undo and Redo just travel up and down in this stack (as usual). Now the user changes the image while at position 4 (i.e. when the image had been changed two times since the beginning). Instead of discarding positions 1-3 (as in gimp-1.x) and instead of creating a branch, the newer changes get reversed and the undo slot resulting from the change is put on top.

Doing this preserves the users expectation that he can undo back through all changes. Reversing the stack (rather than just preserving its contents as-is) also preserves the undo order the user expects.

4. Ways to achieve unlimited undo depth

Preserving branches increases the pressure on the undo system since a lot more undo states have to be saved. Ways to reduce the memory used by an undo step therefore are necessary to allow a high number of undo levels.

If we disregard the changed pixel data, the memory need for an undo-step is low, say, 1k for the undo structure + the pdb call, and another 1-2k for a thumbnail (interpolation would make it possible to store a small image while displaying it larger, which would be sufficient to quickly identify the image state).

This is small enough to warrant a practically unlimited number of undo steps (1000, 10000, really unlimited), that could even be saved in the xcf file.

4.1. Purging/Pruning of undo data

An intelligent algorithm to prune the undo list should be used to prune pixel data from older undo steps, e.g.:

exponential backoff: the older the undo step is, the higher should the probability of pruning the pixel data be. For example, after some tunable number of undo-levels (say 5 or 20), only every 10th or 20th undo step has pixel data attached.
when saving a file, a much more aggressive pruning algorithm could be used.
fast operations should be pruned first (e.g. a stroke is quicker than a gradient fill), even very early, on the assumption that half a second delay to draw a few strokes is acceptable. Only the last two undo states must be really fast, since they are often used to make a quick "compare before/after" check. The user should be warned if a large number of operations (or a slow one, like a plug-in) needs to be replayed.
annotated undo states (only sensible when the undo stack is being saved) should keep their pixel data.

4.2. Persistency

Optionally, the undo stack should be saved in the xcf file. Before doing that, one should prune the pixel data from almost all undo steps. There should be a way to purge the undo stack fully or in part.

4.3. Possible XCF file format extensions

The XCF format could be extended to allow on-demand-loading (e.g. using an ar file with a header and different compartments for each sub-object), very much like a persistent swap-file. Then the undo information need not be loaded at all, unless used.

This would be highly useful for other stuff, like brush hoses or patterns, since an xcf file could be quickly loaded (only the header needs to be parsed), with the actual image data to be loaded on-demand.

The problem with this approach is that the xcf file must stay on disk while it is being used (no problem for brushes, but maybe a problem for users). And on save the undo data would need to be copied to the new file, so other solutions (using an extra file for undo pixel data, using a persistent but installation-specific swap file etc..) might be more feasible.

5. Problems

5.1. Determinism

All operations must be deterministic. Plug-ins that render something based on random values must accept some seed value as argument. There might even be a gimp-specific random-number generator that plug-ins must use.

5.2. Purging of pixel differences

Purging pixel differences of some undo step requires tweaking a possibly large number of surrounding undo steps. It's not clear to me wether this can be done efficiently.

5.3. Reversability of undo steps

Undo steps without attached pixel data are unreversible by nature. The only way to reverse them is to go back to some known image state and replay all the actions.

This makes it neccessary that there is always "a first" undo step with full pixel information. An image can only be created by two methods: File->New and loading an existing image (Paste as New is basically the same). File->New is just a combination of image_new, layer_new, drawable_fill and layer_add. Since drawable_fill does not modify existent data it can be optimized (it defines a starting point for the undo step differences).

Loading an image cannot be optimized that way, so we would have to store the whole image in this case. The same is true for every action where external data is used, e.g. pasting from another image (or pasting in general).

5.4. Unreplayable actions

There are some reasons why an action cannot be replayed, for example when the plug-in/tools/pdb-function necessary to replay a step is no longer available, or has changed internally. All plug-ins therefore require a protocol version that is bumped on internal changes. This is the same problem (and the same solution) that effect layers face.

6. Summary

I'm tired now, so I probably forgot a lot. If you find the logical array that kills this whole proposal or you just find a typoe - just write me, Marc Lehmann marc@gimp.org and tell me.

Gimp-Plug-Ins @ SourceForge

proposal for the gimp 2.0 undo system

About this document

proposal for the gimp 2.0 undo system

Table of Contents