Transaction Manager / Undo System

Contributors: Greg Kostello, Kin Blas, Akkana Peck
Last Change: Nov. 18, 1998

Overview

A standard feature of any editing system is the ability to undo a user action. This can be manifested by either a single level or multi-level undo system. In modern word processors, mulit-level undo is standard and our design will attempt to describe a system which supports multi-level undo support.

Requirements

A system that allows the developer to easily develop and record commands.
Ideally, these commands could be created from a series of subcommands. This would allow the creation of complex commands from simple commands.

A system which is not bound to the current content model.
We can safely assume that HTML will grow and that we would like an undo system that can also be used to modify XML documents. We cannot predict the kinds document types that may be supported by future versions of HTML/XML, but we can probably expect to see graphics, charting, presentations, etc..

A system which handle multiple documents.
Undo is a relevant to the currently active document, but undo events can happen in multiple disjoint documents. The system needs to be able to handle that.

The system must allow for efficient coalescing of events and aggregation of commands.

Implementation

An implementation that matches all those needs can be described as a transaction system.

A transaction system includes a transaction manager, a transaction stack, an editing manager that creates particular commands and the commands themselves.

Transactions (or commands) are objects which are relevant to a particular state of a document. The command describes the selection, the action that is to be applied to the document, any data required to apply that action and importantly the action, data and selection that describes how to undo the action.

After a GUI or semantic event enters the system and is routed to a particular document, the editing manager determines if the event should be processed as a transaction. All events which can modify the document must be processed as a transaction for the system to work correctly. Any action that by passes the transaction system and modifies the content model will require a reset of the undo stack. This is required because each command depends on the document being in a particular state. Events which do not modify the content model can be processed by the transaction system, but it is not a requirement.

The transaction manager is able to execute commands. Command stacks are keyed to individual documents. Commands are created by the editing manager in response to events. These commands are placed on the do command stack and then executed by the transaction manager. When an undo is requested, the transaction takes the command on the top of the do stack and the command is requested to execute an undo. Afterwards, the transaction manager places the command on the undo command stack. Undo requests can be repeated until the do stack is empty. When a redo is requested, the transaction manager pulls the command from the undo stack and has the command execute a redo. Any time a new command is created and added to the stack, the redo stack is pruned.

"Redo" is identical to "Do" by default, but you certainly want a mechanism to describe arbitrary actions in the "Redo" case for those times when it's not the same. As I recall, the way we did this in Xena was simply to have a list of Do, Undo, and Redo actions in each transaction, and the transaction manager was smart enough to execute the Do action if Redo was null and the caller requested a "redo."

I would also add that you need a way to efficiently query the undo system. Is there a transaction on the undo stack, or the redo stack? An example of use would be to know whether the "undo" and "redo" menu items should be enabled. You might further want the ability to associate a human-readable string with each transaction, so the undo menu could read "Undo typing" instead of just "Undo." This gives the user a little bit more feedback and predictability.

Aggregation allows a command to be played and then absorbed by the command at the top of the command stack. An example of aggregation can be replace all. A replace all command is first created, then a series of replace commands are executed against the document and each of these commands is aggregated into the the replace all command. Coelesing of events involves actually modifying a command that is already in place. An example of this would handling typing events. When a key press happens, the command stack is analyzed to see if a previous key press command is on top of the stack. If it is, and the key press event represents a character insertion, then the character is inserted directly into the document and the command on top of the stack is augmented with the character event data.

Risks

The two people (Steve and Greg) who have had the most experience implementing a transaction system, have the least amount of time to implement the system. This system is required to be in place before other team members can create transactions.

Dependencies

Service manager for requesting the transaction manager.

For individual commands, not for the transaction system :
DOM, the style system, parsing system

Issues/Black Holes

How do we efficiently store commands?