How Is Undo Actually Implemented? The Underlying Logic from Text Editors to Photoshop

Undo exists in almost every piece of software. Users press Ctrl+Z every day, yet few ever stop to think about what's actually happening underneath. This Computerphile video takes apart this "taken-for-granted" feature and finds it touches on multiple layers of computer science — from user experience expectations to data structure choices to memory management. What looks like a simple keystroke turns out to be far more complex than you'd imagine.

The Era Before Undo

The video's presenter recalls a time when software simply had no undo functionality at all. The word processor on the old computer in the background — even though the keyboard had a physical Undo key — did nothing when pressed, and there was no undo option anywhere in the menus. It's hard for today's users to appreciate just how painful that experience was.

Even Photoshop didn't gain true undo functionality until relatively late in its life. Early versions only had the History panel on the side — there was no feature called "Undo" at all. In other words, undo isn't something software is born with; it's something developers have to deliberately design and implement.

What Do Users Actually Expect Undo to Do?

The really interesting question is: when a user presses undo, what do they actually expect to happen? The answer isn't as obvious as it seems.

Take a text editor. If you type a long string like "the cat sat on the mat" and press undo — should it only undo the last character? If it only undoes one character, how is that different from Backspace? Undo would be pointless. So users' real expectation is typically to undo "the last word" or "the previous editing action."

The key insight here is that computers don't "think" for themselves about where to undo to. Programmers must explicitly tell the program to place "milestones" or "checkpoints" throughout the editing process. Only then, when the user presses undo, does the program know which saved state to revert to. What seems simple immediately demands dedicated logic in the code.

Word's "Hidden Edits"

The video runs an interesting comparison experiment using Microsoft Word. After typing some text and pressing undo, Word doesn't wipe everything at once — it steps back incrementally. It first undoes the autocorrection made by spell check, then undoes the step where a plain apostrophe was replaced with a "smart quote."

These are "hidden edits" the user never actively made, but which the software performed in the background. Word records every point in a document where the "nature of editing changes": switching from typing to deleting, switching from manual input to spell check intervention, switching from typing to pasting a block of content — every such transition becomes an undoable node.

Bitmap Editors: Easy to Decide, Hard to Store

Switch to a bitmap drawing application, and the situation flips. The video demonstrates drawing a house with doors and windows on an iPad — each stroke, once the stylus lifts from the screen, constitutes a complete action. Pressing undo removes a window; pressing redo brings it back. From an interaction standpoint, this is more intuitive than a text editor.

But the trouble is in storage. A text editor only needs to record "which characters were inserted at which position" — to undo, just remove those characters; to redo, put them back. You could even simply log each keystroke and replay it. But once a bitmap is modified, the original pixels are gone — you can't "un-draw" content that's been painted over (unless you use a special drawing mode like XOR, which produces strange results).

The only solution is to back up the original image — or at least the small region being overwritten — somewhere else before drawing. This introduces a memory problem: every backup consumes space. Deciding "what to undo" becomes easier, but the actual work the program must do increases significantly.

The OS Can't Do Much Here

A common question is: is undo implemented by the programmer, or does the operating system handle it?

The answer is that most of it falls on the developer. The OS only passes key events to the program — "A key down, A key up, B key down" — it has no idea whether you're building a word processor or a drawing application, and it doesn't know which operations should be grouped together.

That said, some frameworks do provide undo support. The video mentions that macOS's AppKit and iOS's UIKit both have built-in multi-level undo capabilities, primarily helping you group and replay operations. But even so, you still need to tell the framework which operations belong in a group and how to replay them. If you're writing a graphics editor, your program still has to handle backing up the image data itself.

Using a Stack for Multi-Level Undo

When it comes to implementing multi-level undo, what's the most natural data structure? The video's answer is a stack.

A stack's Last-In-First-Out (LIFO) property fits undo perfectly: every edit gets wrapped into an object and pushed onto the stack. In a text editor that might be "added 'the cat', recorded insert position"; in a graphics editor it's "the original pixels of the overwritten region." When the user presses undo, pop the most recent operation from the top of the stack and execute it in reverse.

To support redo, you need two stacks: an undo stack and a redo stack. When you undo, pop from the undo stack and push onto the redo stack; when you redo, move it back in reverse. For an image editor, though, redo isn't just shuffling objects around — it also means actually writing the stored pixel block back into place.

Where to Draw the Undo Boundary

The presenter shares a personal perspective on implementation: how you define undo nodes determines the user experience. Word and the demo text editor both segment based on "operation type changes" (e.g., switching from typing to deleting). But if he were implementing it himself, he'd prefer a timer — resetting it on each keystroke, and setting a node if there's a pause of more than a second. Because when users are typing quickly and continuously, they usually don't want to undo one character at a time; but once they pause to think before continuing, that often signals the start of a new logical segment.

This shows that the same undo feature can be implemented in multiple ways, each corresponding to a different user experience and a different level of programming complexity — which may be exactly why many applications don't bother to be too fine-grained about it.

---

A stack is one of the most fundamental data structures in computer science. Its core property is Last-In-First-Out (LIFO): the last element pushed in is the first one popped out, like a stack of plates where you can only take from the top. Its counterpart is the queue, which follows First-In-First-Out. Undo history maps naturally to stack semantics — the operation a user most wants to undo is the most recent one, not the earliest.

Under the Command Pattern design paradigm, each user action is encapsulated as a "command object" containing both an execute and an undo method. When the user presses Ctrl+Z, the program retrieves the command object from the top of the stack and calls its undo method — the whole process is decoupled from the specific type of operation. This is also why framework-level tools like AppKit can provide generic undo support: as long as developers encapsulate command objects according to the spec, the framework can uniformly manage pushing and popping from the stack without needing to understand what each operation actually means.

---

Memory Is the Real Enemy

For bitmap editors, memory is an inescapable hard constraint. The video emphasizes that software like Photoshop works with uncompressed images — not a few hundred KB of JPEG, but raw bitmaps that might be hundreds of megabytes, or even several gigabytes in pre-press publishing workflows.

Every layer of undo history consumes corresponding memory. If you naively implement this with an unconstrained two-stack approach, the history will quickly exhaust RAM or disk space. Real implementations therefore need a structure with a capacity ceiling that knows exactly how much data it's holding — one that can, when memory gets tight, discard trivial operations from three hours ago (like a single dot placed on the canvas) while retaining more recent operations likely to be undone, rather than clinging to gigabytes of history that will never be used.

One optimization approach: graphics operations don't necessarily need to store the entire bitmap — you can crop and store only the modified region, then restore it in place on redo. But no matter how you optimize, all this information must be collected into objects and pushed onto the stack, so storage overhead always exists.

The "Almost Free" Undo in Text Editors

The video closes with a teaser: text editors can actually make undo "almost free" through a clever data structure. The "Gap Buffer" discussed in a previous Computerphile video requires extra objects to track edits, but there's another structure called the Piece Table — used by Microsoft Word and Visual Studio — that makes undo implementable at near-zero cost. That will be covered in a follow-up video.

This deep dive into undo illustrates a broader truth: the features users take most for granted are often the ones involving the most engineering trade-offs behind the scenes. From understanding user expectations, to choosing the right data structure, to carefully managing memory — one small Ctrl+Z manages to connect multiple layers of computer science.

---

The Piece Table is a data structure designed specifically for text editing, first systematically described by Charles Crowley in a 1998 paper. Its core idea is to never directly modify the original text buffer, but instead maintain a "piece descriptor table" where each entry points to a segment (start position + length) in either the original buffer or a new-additions buffer. When text is inserted or deleted, only the table entries need to be added, removed, or split — the original data is always preserved.

This property makes undo nearly "free" — before each edit, the state of the piece table itself serves as a lightweight snapshot, storing metadata (pointers and lengths) rather than copying the full text. By comparison, a Gap Buffer must physically move large numbers of bytes every time the cursor moves. The Piece Table's trade-off is lower random access efficiency — you must traverse table entries to locate a specific character position — but this has limited impact on text processing workflows that are primarily sequential, which is why it's widely adopted by mainstream editors like Word and VS Code.