How Undo Works in Text and Graphics Editors: Key Concepts

Undo is a ubiquitous feature in modern software applications, yet its underlying complexity is often overlooked. While users expect a seamless experience, implementing undo requires careful consideration of various computer science principles, user expectations, and resource management.

The Evolution of Undo

Early software applications often lacked an undo feature, making mistakes frustrating and irreversible. The introduction of undo revolutionized user experience, providing a safety net for edits and encouraging experimentation. However, the concept of "undo" itself can be ambiguous.

User Expectations vs. Implementation Challenges

When a user presses undo, their expectation of what should be undone can vary significantly depending on the context.

Text Editors

In a simple text editor, if a user types "The cat sat on the mat. This is a long bit of text that I am typing in," and then presses undo, what should happen?

• Initial thought: Undo the last character typed. However, this is redundant with the backspace key.
• Second thought: Undo the last word. This is a more reasonable expectation, but still requires the software to define what constitutes a "word" and track it as a distinct action.
• Actual behavior (simple editor): Often, a simple text editor might undo the entire last "edit," which could be everything typed since the last pause or significant action.

Microsoft Word, a more sophisticated word processor, demonstrates further complexity. If text is typed and then a spelling correction occurs automatically, pressing undo once will undo the spelling correction. Pressing it again might undo the last typed word, or even a hidden edit like a "smart quote" conversion. This highlights that "undo" in a word processor tracks a sequence of discrete, often hidden, actions.

Graphics Software

In a bitmap graphics editor, the concept of undo is often more intuitive from a user's perspective. If a user draws a house with windows and then presses undo, they expect the last drawn element (e.g., a window) to disappear. This aligns with the idea of a "complete action" – the pen was put down, something was drawn, and the pen was lifted.

The Technical Hurdles of Implementing Undo

While user expectations for undo might seem straightforward, the technical implementation presents significant challenges, particularly concerning data storage and management.

Storing Changes for Undo

• Text Editors: For text, undo can be relatively simple. The system needs to track what characters were inserted or deleted at specific points. To undo an insertion, those characters are deleted. To redo, they are re-inserted. One approach is to store every key press, which can then be amalgamated or replayed.
• Bitmap Graphics Editors: This is where it gets complicated. When a user draws on a bitmap, the underlying image data is directly modified. There's no "undrawing" in the same way there's "undeleting" text. To enable undo, the software must:
  1. Before any drawing: Take a backup of the affected portion of the image (or the entire image) and store it.
  2. After drawing: If undo is requested, restore the backed-up image data.

This process consumes significant memory or disk space, especially with large image files. An uncompressed image can be hundreds of megabytes or even gigabytes, meaning each undo step requires storing a substantial amount of data.

Operating System Support and Data Structures

While operating systems might provide some basic support for grouping and replaying events (like key presses), they generally don't inherently understand the semantic meaning of an application's actions. The application itself is responsible for defining what constitutes an "undoable" action and how to store the necessary data.

Multi-Level Undo with Stacks

To implement multi-level undo (allowing users to undo multiple previous actions), a common data structure is a stack.

• How it works:
  1. Whenever an edit occurs, the details of that edit (e.g., "add 'the cat'" at a specific location, or "draw a window" with its associated image data) are encapsulated into an object.
  2. This object is then "pushed" onto an undo stack.
  3. When the user presses undo, the top object is "popped" off the undo stack, and the corresponding action is reversed.

Adding Redo Functionality

To support "redo" (undoing an undo), a second stack, the redo stack, is introduced.

• When an action is undone, its corresponding object is moved from the undo stack to the redo stack.
• When the user presses redo, the top object is popped from the redo stack, and the action is re-applied, moving the object back to the undo stack.

Challenges with Stacks in Graphics Editors

While stacks are effective for managing undo/redo sequences, they pose challenges for bitmap editors due to the sheer size of the data. Each object on the stack for a graphics editor might contain a large chunk of image data. This can quickly consume vast amounts of memory.

• Memory Management: Graphics applications often need a more sophisticated mechanism than a simple stack. This might involve a data structure that behaves like a stack but also intelligently manages memory, perhaps by discarding older, less likely to be undone, history items when memory runs low.
• Data Representation: Instead of storing entire bitmap chunks, some graphics applications might try to store the "action" itself (e.g., "draw a line from X,Y to A,B"). However, for complex brush strokes or filters, this can still be very data-intensive or difficult to reverse.

Defining an "Edit"

A crucial aspect of implementing undo is defining what constitutes a single "edit" from the user's perspective.

• Programmer's perspective: A programmer might define an edit as a single key press or a single mouse click.
• User's perspective: A user might consider a continuous typing session or a single drawing stroke as one logical edit.

Some applications might use a timer: if a user pauses typing for a certain duration (e.g., one second), the previous continuous typing session is considered a complete edit. This allows for a more intuitive undo experience, where a single undo action reverses a logical block of work rather than just the last character.

Future Considerations: Piece Tables

While gap buffers are a common way to store text in editors, other data structures like the piece table (used by applications like Microsoft Word and Visual Studio) can make undo almost "free." This more advanced data structure allows for efficient tracking of insertions and deletions, simplifying the implementation of undo functionality.