Undo Manager

System Support for a Painless Undo

This document describes how to do Undo on a system-wide level, so that the application code has a minimum of effort to support (single level) Undo.

The Macintosh OS introduced Undo to the computing world, and now no self-respecting program would be without it. The idea is that users should be protected from destructive acts, but not prevented from doing their job. Research has shown that responding to incessant confirmations turns into a habitual gesture, which is equivalent to no protection at all. The only real protection is to do the operation as requested, but give the user the opportunity to reverse the action after seeing the result. Of course Undo should also be undo-able, which we call Redo.

There are essentially two kinds of operations that can be undone. The simplest is atomic actions, like deleting or pasting. Typing an extended block of text can also be seen as atomic, even though it involves a large number of sequential steps, because (like pasting) it is a single block of text being entered. The other kind of operation extends this idea of a sequence of connected or related steps to capture the entire sequence as a single Undo-able event. Examples might include changing the size and style -- and maybe even color -- of a single block of text, or setting multiple attributes of any single object. Another example could be moving an object in a visual field to some other place by means of several separate steps, perhaps one large drag, followed by incremental adjustments to get its position exactly right. In such a case, the user almost never is interested in reversing only the final one-pixel tweak, but rather reverting back to where it originally came from; Undo should reflect this perspective of a single atomic motion in multiple steps.

The application program doing the sequential steps seldom has the overall perspective of the user at hand. The best it can do is notice that this operation is in some sense "just like" the previous, and therefore part of the same Undo-able event. The program does not need to track this information. Because Undo should work essentially the same for everybody, a small number OS system calls can implement the desired behavior, with only the particulars supplied by the application program.

When a sequence of operations can be merged automatically into a single atomic event -- for example, accumulating a sequence of object position changes into a single move -- then it makes sense to record a single event in the Undo package. If the sequence is logically but not programmatically connected, it makes more sense to record each individual step separately in the package, and then play the package back backwards when effecting the Undo operation. Furthermore, it is often convenient to record reversible steps, so that Redo consists in nothing more than playing the same package back in the forward direction. This minimizes the overhead of separately recording a new package during the Undo operation.

The Mini Operating System (MOS) has an Undo Manager which supplies the necessary functions for both Undo and Redo. It also manages the Undo menu and dispatches the recorded events. In MOS, events are uniquely identified by a 4-character (32-bit integer) keyword. This same mechanism supports the menu system and inter-process communication and scripting. In the case of Undo, the event information is recorded in the Undo package. When Undo is selected from the menu, the package is opened and the events are played back (posted to the application program) in reverse order. The program has the option of starting a new Undo package to record the Redo event, or letting MOS do the work.

At the heart of the Undo Manager is the scripting package, which is also used for scripting and journalling, as well as drag/copy events (none of which concern us here). Because there is only one user interface per program, the system can maintain the Undo state as part of the program (or possibly thread) state.

The program determines the category of event it is about to process, and issues a system call to begin an undoable sequence in that category. The system responds with a boolean reply, "This is the first in its category" or "we already have one of these open." In the former case, the program can then load up whatever is needed to finish off the Undo event (recall, these are played back in reverse order), which might be as simple as storing into the package a copy of the current (unmodified) state of the object about to be changed. For atomic operations, the program can at the same time load into the package the new object state, tagged for "Redo". Otherwise, the system will issue an event using the category keyword if the Undo menu is selected for this package, and the program can immediately finalize the package with the last state of the object, or whatever needs to happen at the beginning of Undo or the end of Redo. If another category of event starts another Undo package, the previous package is simply discarded.

That's essentially all there is to it. Each undoable step issues the system call to begin an undoable sequence, and then, if the boolean result is true, proceeds to initialize its undo. After that (or otherwise), the actual operation takes place, and its own Undo event data is also recorded. The program needs to have handlers for each of the events it records, and also for the termination event in the case of a non-atomic Undo sequence.

For atomic events, the program tells the system to start an atomic Undo package (which always returns true), then records both the Undo and Redo data. For granular events the program asks the system to start a package for this category, and if true, sets up the termination; when it gets that category event, it sets up the initialization, then tells the system to proceed with playing the package back. Intermediate steps can be recorded or not, as appropriate.


We have the following (internal) Undo state variables:
UndoClass, UndoRefInfo -- two 32-bit values that uniquely define this Undo package
NeedUndoFinalize -- true if the current package needs a finalize step
...and the (open) package itself, containing Undo & Redo menu texts, plus the events
These functions access this information and perform the indicated operations:
void CantUndo();
Undo for some operations is not feasible. This notifies the system and discards any outstanding package.

void DoUndo(Window win);
This is the usual response to the user selecting Undo from the menu. The optional window reference win is passed to the program as the target of this operation. If a package is still recording, then its finalize event is sent (which normally adds a final event to the package) before processing the package.

boolean BeganUndoPkg(Char4 sgn, int info, String txt, boolean fize);
This begins or continues an Undo-able sequence of operations. The signature sgn is matched against UndoClass, and the additional identification info is matched against UndoRefInfo, to determine if this continues a previously started Undo sequence. If fize is false, then this is an atomic operation, which always fails to match any prior or subsequent call and returns true. It returns false if this is a continuation of a previous BeganUndoPkg call with the same UndoClass and UndoRefInfo. The txt is the new Undo menu text, not including the word "Undo".

void UndoAdd(Char4 ms, int info...);
Adds an event to the currently open Undo package.

void RedoMenu(String txt);
Adds a Redo menu text (not including the word "Redo") to the currently open package, if different from the Undo menu label given to BeganUndoPkg.

void RedoAdd(Char4 ms, int info...);
Adds a Redo event to the currently open package. When the package is processed, Undo and Redo events are swapped, so that the Undo events are sent to the program and converted to Redo events (in a copy of the package, in reverse order), and the Redo events become Undo events. Choosing Undo again repeats the process. Alternatively, the program can record its own Redo package, which is used instead.

Other functions expand the capabilities of UndoAdd and RedoAdd for other data types.

First draft, 2007 August 2
API added 2008 February 6