This document has been written without the actual slides we made, so expect changes.
The undo structure should serve two purposes:
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.
Each undo step must store the following:
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.
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.
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.
An intelligent algorithm to prune the undo list should be used to prune pixel data from older undo steps, e.g.:
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.
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.
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.
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.
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).
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.
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.