User:Huffchen/Undo

Undo is an interaction technique which is implemented in many computer programs. It erases the last change done to the document reverting it to an older state. In some more advanced programs such as graphic processing, undo will negate the last command done to the file being edited. With the possibility of undo users can explore and work with the programs without be afraid of making mistakes because they can easily be undone.

So the expectations for undo are to be easy to understand, to have a predictable functionality and to include all undoable commands. Usually undo is always available until the user undoes all executed operations back. But there are some actions which are not stored in the undo list and so there’s no possibility to undo these. For example saving file is not undoable, but is queued in the list to show, that this command was executed. Another action, which is not undoable and not stored, too, is scrolling or selection.

The opposite of undo is redo. The redo command reverses the undo or advances the buffer to a more current state.

The usual common parts of the undo functionality are the commands, which were executed of the user, the history buffer(s), which store the completed actions, the undo/redo manager for controlling the history buffer and the user interface for interacting with the user.

In most Windows applications, the Undo command is activated by pressing the Ctrl+Z or Alt+Backspace keybindings. In all Macintosh applications, the Undo command is activated by pressing Command-Z. The common command for Redo on Microsoft Windows systems is Ctrl+Y or Ctrl+Shift+Z. The common command for Redo on Apple Macintosh systems is Command-Shift-Z.

History

The ability to undo an operation on a computer was independently invented multiple times, as a response to how people used computers.

The File Retrieval and Editing System, developed starting in 1968 at Brown University, is reported to be the first computer-based system to have had an "undo" feature.

Warren Teitelman developed a Programmer's Assistantas part of BBN-LISP with an Undo function, by 1971.

The Xerox PARC Bravo text editor had an Undo command in 1974. Behavioral Issues in the Use of Interactive Systems, a 1976 research report by Lance A. Miller and John C. Thomas of IBM, noted that "It would be quite useful to permit users to 'take back' at least the immediately preceding command (by issuing some special 'undo' command)." The programmers at the Xerox PARC research center assigned the keyboard shortcut Ctrl-Z to the undo command, which became a crucial feature of text editors and word processors in the personal computer era. In 1980, Larry Tesler of Xerox PARC began working at Apple Computer. There, he and Bill Atkinson advocated for the presence of the undo command as a standard fixture on the Apple Lisa. Atkinson was able to convince the individual developers of the Lisa's application software to include a single level of undo and redo, but was unsuccessful in lobbying for multiple levels.

Multi-level undo commands were introduced in the 1980s, allowing the users to take back a series of actions, not just the most recent one. AtariWriter, a word-processing application introduced in 1982, featured undo. NewWord, another word-processing program released by NewStar in 1984, had an unerase command. IBM's VisiWord also had an undelete command.

Undo and redo models

Undo models can be categorizes as linear or non-linear undo models. The non-linear undo model can be sub classified in script model, us&r model, triadic model and selective undo as an augmentation of the models.

For models there are some properties, which describe their behaviors.

• 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 executes 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 is a history list in which all executed commands are stored. When a new command is called, it is added to the list. Thereof only the last executed command can be undone and after that removed from the history list. Undo can repeated as long as the history list is 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. He has 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 steps.

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 an 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 because it can be difficult when other users change the application state meanwhile. So undo for groupware is more complex than for single user. 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 encapsulate 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. For example one strategy is 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. Another possibility is 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.“ The most used strategy is partial checkpoint. With this the changed application state is saved and with undo the part of the state is set back to the forward value. Another strategy is the inverse function that needs no saved state information. „For example, money can be reversed by moving the object back by relative amount.“ For selective undo there are not enough informations for saving the state.

See also

• Reversible computing
• Rollback (data management)
• Undeletion
• Version control (native file format)

External links

• The Age of Undoing - Article about the linguistic history of Undo at The New York Times Magazine.
• Cascading undo control - a paper focused on what is cascading undo and how it might be presented to users