Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
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 without fear of making mistakes, because they can easily be undone.
The expectations for undo are easy to understand: to have a predictable functionality, and to include all "undoable" commands.[1] Usually undo is available until the user undoes all executed operations. But there are some actions which are not stored in the undo list, and thus they cannot be undone. For example, save file is not undoable, but is queued in the list to show that it was executed. Another action which is usually not stored, and thus not undoable, is scrolling or selection.[2]
The opposite of to undo is to redo. The redo command reverses the undo or advances the buffer to a more recent state.
The common components of undo functionality are the commands which were executed of the user, the history buffer(s) which stores the completed actions, the undo/redo manager for controlling the history buffer, and the user interface for interacting with the user.[3]
In most graphical applications for the majority of the mainstream operating systems (such as Microsoft Windows, Linux and BSDs), the keyboard shortcut for the undo command is Ctrl+Z or Alt+Backspace, and the shortcut for redo is Ctrl+Y or Ctrl+Shift+Z. In most macOS applications, the shortcut for the undo command is Command-Z, and the shortcut for redo is Command-Shift-Z. On all platforms, the undo/redo functions can also be accessed via the Edit menu.
History
[edit]The ability to undo an operation on a computer was independently invented multiple times, in response to how people used computers.[4]
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.[5][6]
Warren Teitelman developed a Programmer's Assistant as part of BBN-LISP with an Undo function, by 1971.[7]
Marvin Zelkowitz proposed in his PhD thesis (Reversible Execution as a Diagnostic Tool) in 1971 at Cornell University the concept of reversible execution, which is essentially an undo. In his PhD thesis (An Interactive Analysis System for Execution-Time Errors) at the University of Illinois at Urbana-Champaign in 1975, Alan M. Davis expanded on Zelkowitz's concept to show how multi-level undo (i.e., multi-level reversible execution) could be used for debugging software programs.
The Xerox PARC Bravo text editor had an Undo command in 1974.[8] A 1976 research report by Lance A. Miller and John C. Thomas of IBM, Behavioral Issues in the Use of Interactive Systems,[9] 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)."[10] 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.[11] In 1980, Larry Tesler of Xerox PARC began working at Apple Computer. There, he and Bill Atkinson advocated for the presence of an 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.[citation needed] When Apple introduced the Lisa's successor, the Macintosh, it stipulated that all standard applications should include an “Undo” as the first command in the “Edit” menu,[12] which has remained the standard on macOS and Windows to this day.
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.[11] EMACS and other timeshared screen editors had it before personal computer software. CygnusEd was the first Amiga text editor with an unlimited undo/redo feature. AtariWriter, a word-processing application introduced in 1982, featured undo. NewWord, another word-processing program released by NewStar in 1984, had an unerase command.[11] IBM's VisiWord also had an undelete command.
Undo and redo models
[edit]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.[1]
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."[3]
- 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."[3]
Linear undo
[edit]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.[1]
Restricted linear model
[edit]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.[1]
Non-linear undo
[edit]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.[3] For non linear model there are subclasses which implement this model.
Script model
[edit]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."[1] 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".[1]
US&R model
[edit]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".[1] 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.[1]
Triadic model
[edit]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".[1] 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".[1] For redo the list has to be rotated until the wanted command is above.
Selective undo
[edit]Jakubec et al. say that selective undo is a feature which a model can offer but for selective undo there is no clear definition.[3] 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".[3] 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."[3] 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.[3]
Direct selective undo
[edit]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.[1]
Multiuser application
[edit]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[when?] 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.[13] This was the standard model prior to the widespread adoption of multiple-level undo in the early 1990s.
Undo implementation
[edit]Undo can be implemented through different patterns. The most common patterns are command pattern and memento pattern.
Command pattern
[edit]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.[14]
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.[14]
Memento pattern
[edit]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.[14]
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."[1]
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."[1]
- 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."[1] For selective undo there is not enough information for saving the state.
See also
[edit]References
[edit]- ^ a b c d e f g h i j k l m n Berlage, Thomas (1994-09-01). "A selective undo mechanism for graphical user interfaces based on command objects". ACM Transactions on Computer-Human Interaction. 1 (3): 269–294. doi:10.1145/196699.196721. ISSN 1073-0516. S2CID 11848679.
- ^ Myers, Brad A.; Kosbie, David S. (1996-04-13). "Reusable hierarchical command objects". Proceedings of the SIGCHI conference on Human factors in computing systems common ground - CHI '96. ACM. pp. 260–267. doi:10.1145/238386.238526. ISBN 0897917774. S2CID 17033810.
- ^ a b c d e f g h Jakubec, Karel; Polák, Marek; Nečaský, Martin; Holubová, Irena (2014). "Undo/Redo Operations in Complex Environments". Procedia Computer Science. 32: 561–570. doi:10.1016/j.procs.2014.05.461. ISSN 1877-0509.
- ^ Moran, Chuktropolis Welling (2013-01-01). Interactive Time (Ph.D.). La Jolla: University of California, San Diego. ISBN 9781303194450. Archived from the original on 2021-04-28. Retrieved 2016-07-07.
- ^ Barnet, Belinda (2014-12-01). Memory Machines: The Evolution of Hypertext. Anthem Press. p. 108. ISBN 9781783083442.
But the most popular development for novice users in FRESS was not its capacity to accommodate multiple displays and users; it was the 'undo' feature – the feature of which van Dam is most proud (van Dam 2011). FRESS pioneered a single-level undo for both word processing and hypertext. Every edit to a file was saved in a shadow version of the data structure, which allowed for both an 'autosave' and an undo. Brown staff and students understood immediately the importance and usefulness of this feature (van Dam 1999).
- ^ Barnet, Belinda (2010-01-01). "Crafting the User-Centered Document Interface: The Hypertext Editing System (HES) and the File Retrieval and Editing System (FRESS)". Digital Humanities Quarterly. 4 (1). Archived from the original on 2021-05-01. Retrieved 2016-05-27.
- ^ Teitelman, Warren (1972-01-01). "Automated programmering: The programmer's assistant". Proceedings of the December 5-7, 1972, fall joint computer conference, Part II on - AFIPS '72 (Fall, part II). New York, NY, USA: ACM. pp. 917–921. doi:10.1145/1480083.1480119. S2CID 1276566.
- ^ "Bravo Manual in Alto Non-Programmers Guide, p. 52" (PDF). Archived (PDF) from the original on 2015-05-05. Retrieved 2014-03-29.
- ^ Miller, Lance A.; Thomas, John C. (1977-09-01). "Behavioral issues in the use of interactive systems". International Journal of Man-Machine Studies. 9 (5): 509–536. doi:10.1016/S0020-7373(77)80002-3. ISSN 0020-7373.
- ^ Miller, Lance A.; John C. Thomas Jr. (December 1976). "Behavioral Issues in the Use of Interactive Systems". Archived from the original (PDF) on May 27, 2012. Retrieved 2011-05-21.
- ^ a b c Ben Zimmer (2009-09-15). "The Age of Undoing". New York Times. Archived from the original on 2013-06-17. Retrieved 2013-06-02.
- ^ Apple Computer, Inc. (1984). "User Interface". Inside Macintosh, Volume I.
- ^ Roberta Mancini, Alan Dix and Stefano Levialdi. 2006. "Reflections on Undo"
- ^ a b c Erich Gamma; Richard Helm; Ralph Johnson; John Vlissides (1995). Design Patterns. Reading, Mass.: Addison-Wesley. ISBN 0201633612. OCLC 31171684.
External links
[edit]
- 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
Fundamentals
Definition and Functionality
Undo is a fundamental interaction technique in computer software that enables users to revert the effects of a previous action or command, thereby restoring the application or system to an earlier state in its history. This mechanism supports error correction by allowing reversal of unintended changes, such as deletions or modifications, without requiring manual reconstruction of prior conditions.[4] The primary functionality of undo involves maintaining a record of the system's evolution, either through a sequence of operations or discrete snapshots, to facilitate reversal upon user request. This history is typically managed via a stack data structure, where actions are pushed onto the stack sequentially, and undo pops the most recent entry to execute its inverse, subject to constraints like finite stack depth to manage memory usage or performance. For instance, exceeding the stack limit may discard older entries, preventing indefinite history retention. Undo implementations distinguish between state-based approaches, which store complete snapshots of the application state at key points for direct restoration, and operation-based (or command-based) approaches, which log individual commands along with their inverse functions to recompute prior states dynamically. State-based undo is straightforward for simple systems but can be resource-intensive for complex applications due to snapshot storage, while operation-based undo offers efficiency by avoiding full copies but requires careful command invertibility.[4] A practical example illustrates this in a text editor: when a user deletes a paragraph, an operation-based undo records the deletion command and its inverse (insertion of the original text at the exact position), enabling restoration of the deleted content upon invocation, thus seamlessly reversing the action. The inverse operation, redo, reinstates undone changes, typically using a parallel stack to track reversals. Key benefits of undo include facilitating error recovery to mitigate user mistakes, encouraging experimentation by lowering the cost of trial-and-error interactions, and building user confidence in direct manipulation interfaces, which promotes explorative learning without fear of irreversible consequences.[4][5]User Interface Conventions
In user interface design for software applications, the undo function is typically invoked through standardized keyboard shortcuts to facilitate quick error correction. On Windows and Linux systems, the primary shortcut is Ctrl+Z, while macOS uses Command+Z; for redo, these are Ctrl+Y or Command+Shift+Z, respectively. These conventions, established by major operating system developers, ensure cross-application consistency and reduce the learning curve for users switching between programs. Undo options are commonly integrated into menus and toolbars for accessibility beyond keyboard use. In the Edit menu of most desktop applications, such as Microsoft Word or Google Docs, "Undo" appears as the first or second item, often accompanied by a curved left-pointing arrow icon representing reversal. Toolbars in creative software like Adobe Illustrator feature prominent undo buttons with this icon, allowing one-click reversal of the last action. Visual feedback enhances user awareness of undo capabilities and states. Dynamic labels, such as "Undo Typing" in text editors like Notepad++ or "Undo Paste" in browsers, display the specific action being reversed, providing contextual clarity. When no actions are available for undo—such as at the start of a session—the menu item or button is grayed out or disabled, preventing erroneous attempts and signaling the undo stack's empty state. For applications supporting multi-level undo, interfaces often include panels or lists to preview and select from a history of actions. In Adobe Photoshop, the History panel lists recent states like "Crop" or "Brush Tool," enabling users to jump to any prior state without sequential reversals. This approach, common in professional tools, balances efficiency with precision by visualizing the undo depth, with a default limit of 50 steps that is configurable based on available memory.[6] Accessibility features extend undo functionality to diverse input methods, particularly in mobile and touch-based interfaces. On iOS devices, a "shake to undo" gesture detects device motion to trigger the function, with a confirmation dialog appearing to confirm the reversal, catering to users with motor impairments. Voice commands, such as "undo last action" via built-in assistants in Android or Windows apps, further support hands-free operation. Platform-specific variations influence how undo is presented and behaves. Desktop applications adhere closely to OS-level shortcuts and menus, whereas web browsers like Google Chrome treat browser history as an extended undo mechanism, allowing back-navigation via the left arrow button or Alt+Left Arrow to revert page changes. In contrast, mobile web views may rely more on swipe gestures for undo-like navigation, diverging from desktop norms to suit touch interactions.Historical Evolution
Early Developments
The concept of undo emerged in the late 1960s as a response to the need for error recovery in interactive computing environments. One of the earliest implementations appeared in the File Retrieval and Editing System (FRESS), developed at Brown University starting in 1968, which pioneered a single-level undo for word processing and hypertext editing. Another early example was in BBN-LISP, a Lisp dialect developed at Bolt, Beranek and Newman, where Warren Teitelman introduced an UNDO function in 1971 as part of a Programmer's Assistant. This feature allowed users to reverse previous commands, initially as a simple single-step reversal, marking a pioneering step in providing reversibility for programming tasks.[7] Motivations for such features stemmed from growing human-computer interaction research emphasizing the importance of error prevention and recovery. In the late 1970s, Ben Shneiderman's work highlighted the need for systems that offered immediate feedback and constructive guidance for correcting mistakes, rather than forcing users to restart tasks. His experiments demonstrated that prompt error detection and simple recovery mechanisms significantly improved user performance in interactive tasks, influencing the design of more forgiving interfaces.[8] Undo was introduced in commercial software through Xerox PARC's innovations in graphical user interfaces. The Alto computer system, developed in 1973, supported early graphical applications that incorporated basic undo capabilities for reversing actions in visual editing. This was notably adopted in the Bravo word processor, released in 1974, which included an Undo command to revert typing and formatting changes, representing one of the first instances in a WYSIWYG environment.[9] Early undo systems were constrained by hardware limitations, such as limited RAM, which restricted implementations to single-level reversals rather than multi-step stacks. These features were often designed as simple toggles—reversing the last action upon a second invocation—due to memory costs of storing multiple states, a common challenge in 1970s computing where systems like the Alto had only 96 KB of memory.[10] A key milestone came with the Apple Lisa in 1983, which introduced a dedicated undo mechanism integrated into its graphical user interface, allowing users to reverse the last change across applications and providing a foundational model that influenced the Macintosh system in 1984. This advancement built on prior work by emphasizing user experimentation without fear of irreversible errors. Later developments would evolve these concepts into more advanced models.[11]Integration into Modern Software
The integration of undo features into graphical user interfaces gained momentum in the early 1990s as operating systems standardized multi-level undo capabilities. Microsoft Windows 3.0, released in 1990, incorporated undo functionality in its core applications and shell, building on earlier single-action reversals to support more robust editing workflows that influenced subsequent software norms. Similarly, Apple System 7, launched in 1991, introduced a multiple-level undo/redo mechanism at the operating system level through patent-pending technology, enabling applications to provide deeper reversal histories and setting a precedent for consistent user expectations across the Macintosh ecosystem.[12] As computing shifted to the web and mobile platforms, undo adaptations extended to browser-based and touch interfaces. In the mobile domain, iOS 3.0 in 2009 pioneered gesture-based undo via the "Shake to Undo" feature, allowing users to reverse text edits by shaking the device, which integrated seamlessly with the multitouch paradigm and influenced Android's subsequent implementations.[13] Domain-specific software evolved undo to meet specialized needs, enhancing creative and development workflows. Adobe Photoshop introduced its History panel in version 5.0 (1998), enabling users to configure extensive or effectively unlimited undo states for non-destructive editing, a feature that persists in modern iterations and supports iterative design processes. Integrated development environments like Visual Studio, from the early 2000s, incorporated versioned undo tied to source control systems such as Visual SourceSafe, allowing developers to revert changes across file versions rather than isolated actions. Recent advancements up to 2025 emphasize context-aware and scalable undo in AI-driven and cloud environments. In AI-assisted editors, GitHub Copilot's 2023 integrations in Visual Studio Code enable contextual reversals of AI-generated code suggestions, where users can undo targeted insertions while preserving surrounding edits, improving reliability in collaborative coding. Cloud-based tools, such as Google Docs, leverage server-side storage for unlimited undo through version history, storing complete document states indefinitely to support long-term revisions without local constraints. These developments reflect ongoing standardization, with Apple's Human Interface Guidelines (updated for iOS 17 and visionOS in 2023–2024) recommending intuitive undo patterns like swipe gestures and confirmation dialogs, and Google's Material Design 3 revisions (2021 onward, with 2023 component updates) promoting snackbar-based undo actions for transient operations like deletions.[14][15]Undo and Redo Models
Linear Undo Models
Linear undo models represent the foundational approach to implementing undo functionality in software applications, treating user actions as a strict sequential history that can only be traversed backward or forward in chronological order. These models typically rely on two data structures: an undo stack to store completed actions in last-in, first-out (LIFO) order and a redo stack to manage previously undone actions for potential reapplication. When a new action is performed, it is pushed onto the undo stack after execution, and the redo stack is cleared to reflect the updated linear path. Performing an undo operation pops the most recent action from the undo stack, applies its inverse to revert the state, and pushes that action onto the redo stack; conversely, a redo pops from the redo stack and reapplies the action to the undo stack. This dual-stack mechanism ensures predictable navigation but enforces a single, unbranching timeline of changes.[16][17][4] To address memory constraints, particularly in early computing environments, linear undo models often incorporated a fixed-depth limit on the undo stack due to resource limitations. For example, some applications limited undo to a small number of recent actions to balance history retention with system performance. By overwriting the earliest actions, these models prevent unbounded growth in storage requirements while still providing practical error recovery for recent operations.[16][17] Central to the operation of linear undo models is the concept of command inversion, where each action is encapsulated as a self-contained unit that includes both its forward execution method and a corresponding inverse method to reverse its effects. For example, in a text editing context, a delete action would store the removed content along with its precise original position and attributes; the undo method then reapplies that content at the stored location to restore the prior state exactly. This pairing allows for reversible transformations without requiring the system to reconstruct states from scratch, ensuring atomicity and consistency in state transitions.[16][17][4] The strengths of linear undo models lie in their conceptual simplicity and minimal overhead, which facilitate straightforward integration into user interfaces and reduce the complexity of state management in single-threaded applications. These attributes have contributed to their widespread adoption in conventional software tools. However, their limitations become evident in scenarios requiring flexibility, as the model prohibits branching histories or the targeted reversal of non-consecutive actions, potentially forcing users to navigate through irrelevant steps to reach desired corrections.[16][17] A pseudocode illustration of the core linear undo mechanism highlights its operational flow:initialize undoStack as empty stack
initialize redoStack as empty stack
function performAction(action):
action.execute() // Apply the forward operation
undoStack.push(action)
redoStack.clear() // Discard alternative futures
function undo():
if not undoStack.isEmpty():
action = undoStack.pop()
action.invert() // Apply the inverse operation
redoStack.push(action)
function redo():
if not redoStack.isEmpty():
action = redoStack.pop()
action.execute() // Reapply the forward operation
undoStack.push(action)
initialize undoStack as empty stack
initialize redoStack as empty stack
function performAction(action):
action.execute() // Apply the forward operation
undoStack.push(action)
redoStack.clear() // Discard alternative futures
function undo():
if not undoStack.isEmpty():
action = undoStack.pop()
action.invert() // Apply the inverse operation
redoStack.push(action)
function redo():
if not redoStack.isEmpty():
action = redoStack.pop()
action.execute() // Reapply the forward operation
undoStack.push(action)
push operation on undoStack checks for capacity (e.g., if size exceeds a predefined limit, discard the bottom element before pushing). This design prioritizes recent actions while maintaining the LIFO principle for efficient access.[4][17]
Non-Linear Undo Models
Non-linear undo models extend beyond sequential reversal by enabling users to navigate and reverse action histories in flexible, non-chronological ways, often through branching structures or dependency-aware representations that accommodate complex workflows such as exploratory design or simulation.[4] These models contrast with linear stacks by modeling actions as interconnected elements, allowing undos that skip, branch, or selectively revert subsets without fully replaying the entire sequence.[18] The script model, introduced by Archer, Conway, and Schneider in 1984, represents user actions as executable scripts within a dependency graph, where each command is a node linked to prerequisites and effects. Undo is achieved by replaying inverse scripts that remove or reverse the targeted action's effects while preserving dependencies, enabling non-linear navigation such as skipping intermediate steps in a sequence. This approach is particularly suited to applications with parametric operations, like CAD software, where undoing a script segment restores object states without disrupting unrelated branches. For instance, in design tools, users can revert a specific geometric transformation while maintaining subsequent modifications to other elements.[4] The model divides the history into three streams—user history for all actions, active script for the current state, and pending script for redo candidates—facilitating partial execution and what-if explorations.[4] Building on similar principles, the US&R (Undo, Skip, & Redo) model, proposed by Vitter in 1984, separates undo and redo mechanisms through script-like structures that permit skipping commands during replay, creating branched histories in a directed graph.[18] This allows partial execution of sequences, where skipped actions are marked but not deleted, supporting non-linear recovery in environments with interdependent operations, such as complex simulations or parameterized queries. Introduced in the context of interactive systems, US&R enables users to explore alternative paths by branching from a skip point, then merging or discarding them, which was particularly innovative for research in handling reversible computations without linear commitment.[18] For example, in a simulation tool, a user could skip a faulty parameter adjustment during redo, branching to test variations while retaining the original history for fallback.[4] The triadic model, described in the literature as of 1988 (Yang, 1988), employs a three-way branching structure comprising past (undo stack), present (active state), and future (redo list) histories, with merge capabilities to integrate exploratory branches back into the main timeline. This supports non-linear undo by allowing users to rotate or select from the redo list for what-if scenarios, such as temporarily branching to evaluate alternative outcomes before committing or discarding changes. Unlike purely linear systems, it treats the redo buffer as a circular, navigable structure, enabling undos that revert to any prior state and redos that selectively advance along branches. Yang's framework was designed for general-purpose CAD systems, where designers could explore design variants—e.g., adjusting a component's position in a branch—without losing the primary history, thus fostering creative iteration.[19] Graph-based representations generalize these approaches by modeling actions as nodes in a directed graph, with edges denoting dependencies or causal relationships, allowing undo of entire subtrees or paths.[4] This structure supports non-sequential reversals, such as pruning a dependency subtree to undo a cluster of related actions (e.g., all modifications to a single object in a drawing), while preserving independent branches. Seminal work in this area, as discussed by Dix in 1996, highlights how such graphs resolve conflicts in selective undos by propagating inverses along dependency edges, making it applicable to object-oriented systems where state changes are interconnected.[4] For instance, in graphical editors, undoing a subtree might revert multiple linked edits without affecting unrelated graph components.[20] Despite their flexibility, non-linear undo models introduce significant limitations, including heightened computational complexity for maintaining and traversing dependency graphs, which can lead to performance overhead in real-time applications. In modern applications, these models have evolved to support larger histories, such as unlimited undo in cloud-based tools (as of 2025).[4] Storage requirements also escalate, as branching histories demand retaining multiple state versions or inverse operations, potentially consuming substantial memory compared to the simplicity of linear stacks—Yang noted that triadic structures, while powerful, require careful buffer management to avoid exponential growth in large histories. Additionally, user comprehension challenges arise from visualizing non-linear paths, increasing the risk of disorientation in intricate graphs.[4]Selective Undo Approaches
Selective undo approaches enable users to reverse specific, non-consecutive actions from an interaction history without necessarily undoing all subsequent operations, providing greater flexibility than linear models. These techniques are particularly valuable in complex editing environments where users may regret isolated decisions amid a sequence of productive changes. By allowing direct selection of individual actions or indirect grouping and filtering, selective undo addresses common user needs for precise recovery while maintaining the integrity of the overall workflow.[17] In direct selective undo, users explicitly choose any past action from a visualized history, such as a list or timeline, to reverse it while preserving later actions where possible. For instance, Adobe Illustrator's History panel displays a chronological list of states, enabling users to select and revert to a specific prior state, effectively undoing targeted changes without a full linear rollback. This approach relies on command objects that encapsulate each action's effects, allowing the system to re-execute or adjust dependent operations as needed.[21][17] Dependency resolution is crucial in selective undo to handle interdependencies between actions, such as when undoing an early operation affects the applicability of later ones. Systems automatically adjust subsequent actions—for example, in text editors, undoing an insertion may cause ripple effects that shift positions of deletions or modifications, requiring recomputation of offsets to avoid inconsistencies. Alternatively, user choices can be offered for conflicts, such as prompting whether to propagate the undo or isolate it. In painting applications like Aquamarine, the system skips undone operations in the script history and re-renders the canvas, ensuring visual consistency without manual intervention.[22][17] Indirect selective undo methods provide alternatives by grouping or categorizing actions for batch reversal, reducing the need for granular selection. Users can group related actions into macros, treating them as a single unit for undo; for example, a sequence of brush strokes in a drawing tool can be bundled and reverted collectively. Filtering by type offers another layer, allowing reversal of all actions of a certain category, such as undoing all formatting changes in a document while retaining content edits. In geographic information systems like ArcGIS Pro, users can filter the undo stack to target only editing operations, isolating them from other interface actions for selective reversal.[23][22] Research foundations for selective undo emerged in the early 1990s within human-computer interaction studies, building on command-based architectures to support non-linear recovery. A seminal contribution is Thomas Berlage's 1994 framework, which uses command objects to enable undoing isolated actions by assessing their applicability in the current state, thus resolving dependencies semantically rather than chronologically. This work influenced subsequent implementations, emphasizing generic mechanisms for consistent undo across graphical interfaces. Modern examples, such as timeline-based scrubbing in video editors like Final Cut Pro, extend these ideas by allowing users to navigate and revert to specific temporal points in the edit history.[17][24]Undo in Multi-User Environments
Challenges in Collaborative Editing
In collaborative editing environments, concurrency issues arise when multiple users perform simultaneous edits, leading to conflicts where one user's undo operation may inadvertently reverse or interfere with another's independent changes. For instance, in systems like Google Docs, a user attempting to undo their own recent insertion might transform or override concurrent modifications by peers, resulting in unexpected document states. This stems from the need to maintain per-user undo histories while synchronizing shared content, a challenge exacerbated by operational transformation (OT) algorithms that adjust operations for consistency but complicate selective reversals. Causality violations occur when an undo disrupts the intended sequence of interdependent actions across users, potentially breaking dependencies and causing lost work or inconsistencies. In shared histories, undoing an early operation (e.g., a foundational edit upon which later collaborative changes rely) can cascade into invalidating subsequent contributions, fostering scenarios akin to "undo wars" where users repeatedly reverse each other's efforts to restore coherence. Such violations are particularly pronounced in real-time systems, where the non-linear nature of multi-user interactions deviates from the linear causality assumed in single-user undo models. Scalability problems emerge in merging distributed undo stacks across networks, where latency in cloud-based applications amplifies synchronization delays and increases computational overhead for transforming large histories. As user counts grow, maintaining individual undo buffers while propagating changes globally leads to exponential complexity in operation reconciliation, straining resources in tools supporting dozens of concurrent editors. Early collaborative tools like EtherPad, released in 2008, highlighted these issues through OT-based implementations that struggled with "undo puzzles"—sequences of concurrent edits and reversals resulting in divergent states or lost contributions. Persistent challenges appear in wikis, where version control enables reversion but concurrent edits often trigger conflicts, requiring manual resolution to avoid fragmented histories despite advanced tracking. Psychological impacts include heightened user frustration from non-intuitive reversals, such as unexpected erasures of group work, which erodes trust in the system and hampers productivity in team settings.Resolution Strategies
In collaborative editing environments, operational transformation (OT) serves as a foundational strategy for handling undo operations by transforming concurrent edits to preserve document consistency across users. Originally developed for groupware systems, OT interprets an undo command as a concurrent inverse operation, which is then transformed relative to other pending operations to ensure it applies correctly without disrupting the shared state.[25] This approach was pivotal in tools like Google Docs, introduced in the late 2000s, where undos are executed by inverting and transforming the relevant operations to synchronize all participants seamlessly. By maintaining causal ordering through transformation functions, OT mitigates conflicts arising from simultaneous edits, allowing selective undos that target specific user actions or operations. Conflict-free replicated data types (CRDTs) offer an alternative resolution strategy, enabling commutative operations that inherently support undo mechanisms in distributed systems without requiring centralized coordination. CRDTs ensure that all replicas converge to the same state regardless of operation order, facilitating undos through reversible, monotonically increasing data structures that track additions and removals separately. This commutativity allows inverse operations for undos to propagate across peers without transformation overhead, making it suitable for peer-to-peer collaborative applications. For instance, design tools like Figma, launched in the 2010s, incorporate CRDT-inspired structures to handle real-time undos during multiplayer sessions, ensuring edits from multiple designers merge conflict-free.[26] Seminal work on CRDTs for text editing further extends this to selective undos, where users can revert specific insertions or deletions while preserving concurrent changes.[27] Version branching addresses undo challenges by maintaining per-user branches of the edit history that diverge during local undos and merge upon synchronization, preventing one user's reversal from overwriting others' contributions. In this model, each collaborator operates on a personal linear history, with undos creating branch points that are reconciled using merge algorithms to resolve divergences.[28] This strategy has been integrated into modern co-authoring features, such as version history in Microsoft Office, which allows users to restore prior document states to address changes from collaborative editing without disrupting ongoing work.[29] By treating undos as branch creations rather than universal reversals, the approach scales to multi-user scenarios, though it requires efficient merging to avoid history bloat.[30] Hybrid approaches combine elements of OT, CRDTs, and locking mechanisms, often employing server-side arbitration to manage undo permissions and resolve destructive conflicts in real-time. In these systems, a central server validates undo requests against the global state, applying transformations or commutativity checks while arbitrating access to prevent cascading reversals that could erase valid edits.[31] This arbitration ensures fairness, such as prioritizing the initiator's intent or queuing undos, and is particularly effective in heterogeneous environments where clients vary in latency. For example, hybrid models in collaborative graphics editors use server-mediated merges to handle undo conflicts that OT alone cannot resolve commutatively.[32]Implementation Methods
Command Pattern
The Command design pattern, a behavioral pattern introduced in the seminal work on object-oriented design, encapsulates a request as an object, thereby allowing parameterization of clients with queues, requests, and operations, and supporting undoable commands through methods like execute(), undo(), and redo().[33] This approach treats individual actions—such as editing text or drawing shapes—as command objects that can be stored, executed, and reversed, facilitating the maintenance of a history list for undo and redo functionality in applications.[33] In its structure, the pattern involves several key components: the Invoker, which initiates the command (often the user interface elements like menus or buttons); the Receiver, which is the target object that performs the actual operation on the application's state (e.g., a document or canvas); and ConcreteCommand classes that implement specific actions, such as a PasteCommand for inserting text or a DrawLineCommand for graphics.[33] The Client creates ConcreteCommands and sets their Receiver, while the Invoker maintains a history stack of executed commands.[33] Undo is realized by storing executed commands in a stack data structure, where invoking undo() on the top command reverses its effects, effectively restoring the prior state without full snapshots.[33] For instance, in a text insertion operation, the undo() method might swap the newly inserted characters with the previously stored selection or cursor position, ensuring precise inversion of changes.[33] Redo() similarly re-executes popped commands from a separate stack.[34] This pattern offers advantages such as decoupling the user interface from business logic, which promotes modularity and testability; it also enables advanced features like macro recording (chaining commands) and transaction logging for auditing.[33] It has been widely adopted in software frameworks, notably Qt's Undo Framework, which implements the pattern to provide robust undo/redo support in graphical applications since the early 2000s.[34] A representative example in pseudocode illustrates a simple DrawLineCommand for a graphics editor:interface Command {
void execute();
void undo();
void redo();
}
class DrawLineCommand implements Command {
private Canvas receiver;
private Point start, end;
private Color oldColor; // Stored for inversion
public DrawLineCommand(Canvas receiver, Point start, Point end) {
this.receiver = receiver;
this.start = start;
this.end = end;
}
public void execute() {
oldColor = receiver.getColorAt(start); // Capture pre-execute state
receiver.drawLine(start, end);
}
public void undo() {
receiver.eraseLine(start, end); // Or restore old state
receiver.setColorAt(start, oldColor);
}
public void redo() {
execute();
}
}
// Usage in Invoker (e.g., UI handler)
Stack<Command> undoStack = new Stack<>();
Command cmd = new DrawLineCommand(canvas, p1, p2);
cmd.execute();
undoStack.push(cmd);
interface Command {
void execute();
void undo();
void redo();
}
class DrawLineCommand implements Command {
private Canvas receiver;
private Point start, end;
private Color oldColor; // Stored for inversion
public DrawLineCommand(Canvas receiver, Point start, Point end) {
this.receiver = receiver;
this.start = start;
this.end = end;
}
public void execute() {
oldColor = receiver.getColorAt(start); // Capture pre-execute state
receiver.drawLine(start, end);
}
public void undo() {
receiver.eraseLine(start, end); // Or restore old state
receiver.setColorAt(start, oldColor);
}
public void redo() {
execute();
}
}
// Usage in Invoker (e.g., UI handler)
Stack<Command> undoStack = new Stack<>();
Command cmd = new DrawLineCommand(canvas, p1, p2);
cmd.execute();
undoStack.push(cmd);
Memento Pattern
The Memento pattern is a behavioral design pattern that enables the capture and externalization of an object's internal state, allowing restoration to a previous state without violating encapsulation.[35] Introduced in the seminal work Design Patterns: Elements of Reusable Object-Oriented Software by Gamma et al., it supports undo functionality by creating immutable snapshots of object states at key points, such as before user actions in applications like text editors or graphical tools.[35] This approach ensures that the object's implementation details remain hidden from components managing the history. In the pattern's structure, three primary participants interact: the Originator, which holds the state to be saved and restored; the Memento, an opaque object that stores the Originator's state; and the Caretaker, responsible for maintaining a collection of Mementos, such as a stack for undo history.[36] The Memento provides a narrow interface to the Caretaker—limited to operations like adding a snapshot or retrieving one for restoration—preventing access to sensitive internal data.[35] Conversely, the Originator accesses a wide interface on the Memento, enabling it to fully serialize its current state into the snapshot or deserialize and apply a prior one.[36] This separation preserves the Originator's encapsulation while allowing the Caretaker to manage state history externally. Undo operations leveraging Mementos follow a straightforward sequence: before executing a state-altering action, the Originator creates and passes a Memento to the Caretaker for storage.[35] On an undo request, the Caretaker supplies the most recent Memento back to the Originator, which then restores its state accordingly, effectively rolling back changes.[35] For instance, in text editors, this mechanism saves the document state—such as text content and formatting—enabling users to revert to previous versions without recomputing entire histories.[35] The pattern excels at managing complex, multifaceted states in a modular way, as the Originator delegates history tracking to the Caretaker without exposing internals, simplifying maintenance and enhancing reusability.[35] It also integrates seamlessly with other undo strategies, such as operation-based methods detailed in the Command pattern. However, drawbacks include substantial memory overhead from storing full state snapshots, particularly in resource-intensive applications with deep undo histories or large objects.[35] Optimizations mitigate these issues, such as using delta Mementos that capture only incremental changes between states rather than complete snapshots, significantly reducing storage needs for sequential operations. Compression techniques can further compact Memento data, especially for repetitive or sparse states. In practice, Java's Swing undo toolkit exemplifies these principles through theStateEdit class, which employs Mementos via the StateEditable interface to snapshot and revert component states, supporting robust undo/redo in graphical user interfaces.[37]