Undo

Undo and redo models

Undo models can be categorized as linear or non-linear. The non-linear undo model can be sub-classified in script model, US&R model, triadic model, and selective undo.

Some common properties of models are:

• stable execution property: A state is represented as an ordered list of commands. This means that a command "is always undone in the state that was reached after the original execution."
• weakened stable execution: This means that if undo is executed all commands which depend on the undone command are undone dependent on the command.
• stable result property: This property has the similar meaning like the stable execution property except for the list. The ordered list of commands includes that they were executed instead of only the commands.
• commutative: That means that the reached state after undo and redo two different commands is the same when they are executed in the converse order.
• minimalistic undo property: It describes that "undo operation of command C undoes only command C and all commands younger than C which are dependent on C."

Linear undo

Linear undo is implemented with a stack (last in first out (LIFO) data structure) that stores a history of all executed commands. When a new command is executed it is added to the top of stack. Therefore, only the last executed command can be undone and removed from the history. Undo can be repeated as long as the history is not empty.

Restricted linear model

The restricted linear model is an augmentation of the linear undo model. It satisfies the above described stable execution property for linear undo, because this model does not keep the property if a command is done while the history list includes other commands. The restricted linear model clears the history list before a new command is added. But other restrictions are available, too. For example, the size of the history list can be restricted or when a defined size is reached, the first executed command is deleted from the list.

Non-linear undo

The main difference between linear undo and non-linear undo is the possibility of the user to undo the executed commands in an arbitrary order. They have the chance to undo not the most recently command but rather choose a command from the list. For non linear model there are subclasses which implement this model.

Script model

The script model handles user actions as editing a script of commands. The history list of the executed commands are interpreted "as a script, the effect of an undo is defined to be the same as if the undone action had never occurred in the first place." As the result of undo the state has to be the way as if the undone command was never executed. A disadvantage of this model is that the user has to know the connection between undone command and the current state to avoid side effects. One of this can be for example duplication. Other problems are that if "subsequent commands are redone in a different state that they were originally executed in direct manipulation interfaces, this reinterpretation of the original user action is not always obvious or well defined".

US&R model

The special feature of this model is that it has the option of skipping a command. This means that redoing a command can be skipped. The command which is skipped is marked as skipped but not deleted. When new commands are executed, the history list is retained, so the order of the executed commands can be reproducible with that. The order can be described through a history tree which is a directed graph, "because it is possible to continue redoing commands from another branch creating a link in the graph". Even though the set of commands is simple and easy to understand, the complex structure with skipping and linking branches is hard to comprehend and to remember, when the user wants to undo more than one step.

Triadic model

This non-linear undo model has besides undo and redo the possibility to rotate. It has the same data structure as the above-mentioned models with a history list and a separated redo list which includes the redo operations. The rotate operation sets the last command of the redo list in front of it. On one hand this means that the next command to be redone can be selected by placing it in front. On the other hand, rotation can be used "to select the place in the redo list where the next undo operation will put the command". The list of redo is therefore unordered. "To undo an isolated command, the user has to undo a number of steps, rotate the redo list, and then redo a number of steps". For redo the list has to be rotated until the wanted command is above.

Selective undo

Jakubec et al. say that selective undo is a feature which a model can offer but for selective undo there is no clear definition. The authors selected functions which a model should have when it supports selective undo. It should be possible to "undo any executed action in the history buffer. Actions independent of the action being undone should be left untouched". Just like that redo has to be possible to any undone command. The third function for selective undo is that "no command can be automatically discarded from history buffer without direct user’s request." For selective undo applies that undo and redo is executable outside of any context. There are three main issues. The first is that undone commands can be outside of the originally context. Through this there can be dead references which have to be handled. The second issue that modified commands can be undone and so it has to be solved which state after undo will be presented. The third issue is discarding command problems. Selective undo has no pointer in the lists, so this means that no command should be discarded of the stack.

Direct selective undo

Direct selective undo is an extension of restricted linear undo with a history tree. The operation creates a copy of the selected command, executes this and add it to the history list. There two non-linear operations selective undo and selective redo are defined, so it is more symmetric.

Multiuser application

When multiple users can edit the same document simultaneously, a multi-user undo is needed. Global multi-user undo reverts the latest action made to the document, regardless of who performed the edit. Local multi-user undo only reverts actions done by the local user, which requires a non-linear undo implementation.

Where undo can be used to backtrack through multiple edits, the redo command goes forward through the action history. Making a new edit usually clears the redo list. If a branching redo model is used, the new edit branches the action history.

The number of previous actions that can be undone varies by program, version, and hardware or software capabilities. For example, the default undo/redo stack size in Adobe Photoshop is 20 but can be changed by the user. As another example, earlier versions of Microsoft Paint only allowed up to three edits to be undone; the version introduced in Windows 7 increased this limit to 50.

Simplistic, single-edit undo features sometimes do away with "redo" by treating the undo command itself as an action that can be undone. This is known as the flip undo model, because the user can flip between two program states using the undo command. This was the standard model prior to the widespread adoption of multiple-level undo in the early 1990s.

Undo implementation

Undo can be implemented through different patterns. The most common patterns are command pattern and memento pattern.

Command pattern

The command pattern is a software design pattern which encapsulates information from the operation into command objects. This means that every action is stored in an object. The abstract command class implements an abstract execute operation, so every command object has an execute operation. For undo there also have to be unexecuted operation, which undoes the effect of the executed command, which are stored in a history list. Undo and redo are implemented so that the list is run through forwards and backwards when the execute or unexecute command is called.

For single undo only the executed command is stored. In contrast to the multi level undo where not only the history list with the commands is saved but also the number of undo levels can be determined of the maximum length of the list.

Memento pattern

With memento pattern the internal state of an object is stored. The object in which the state is saved, is called memento and is organized through the memento originator. This returns a memento, initialized with information of the current state, when undo is executed, so that the state can be checked. The memento is only visible for the originator.

In memento pattern the undo mechanism is called caretaker. It is responsible for the safekeeping of the mementos but never change the contents of these. For undo the caretaker requests a memento of the originator and then applying the undo.

The most part of undo mechanism can implemented without dependency to specific applications or command classes. This includes "the management of history list, the history scroller, menu entries for undo and redo and update of the menu entries depending on the name of the next available command."

Every command class has a do method which is called when a command is executed. The undo-method implements the reverse operation of the do-method. To implement the reverse, there are several different strategies.

• full checkpoint: That means that the complete state is saved after a command is executed. This is the easiest implementation, but is not highly efficient and therefore not often used.
• complete rerun: Therefore, the initial state is saved and every state in the history list can be reached through "starting with the initial state and redoing all commands from the beginning of the history."
• partial checkpoint: This is the most used strategy. The changed application state is saved and with undo the part of the state is set back to the forward value.
• inverse function: Inverse function needs no saved state information. "For example, moving can be reversed by moving the object back by relative amount." For selective undo there is not enough information for saving the state.