↓ Skip to main content

Building a tiny text editor in Go, part 2: the simplest undo

·844 words·4 mins
Table of Contents

Undo sounds mysterious until we choose a deliberately unsophisticated answer: before every edit, copy the document. To undo, replace the current document with the most recent copy. It isn’t efficient, but it is easy to understand. That makes it a good first step.

A history is two stacks
#

A snapshot is a saved copy of the editor at one moment. Ours contains the text plus the cursor row and column. We keep snapshots in two stacks: simple collections where the most recently added item is the first one removed, like a stack of plates.

Before an insert, delete, split, or join, we put a complete independent copy onto the undo stack and clear the redo stack. Clearing redo matters: after undoing and then typing, we have chosen a different path, so the edits we had undone are no longer available to redo.

Undo performs three steps:

  1. Copy the current state to the redo stack.
  2. Remove the newest state from the undo stack.
  3. Restore its text and cursor.

Redo is the mirror image. We cap history at 200 entries so the experiment has a predictable upper bound.

Why a complete independent copy – often called a deep copy? A quick copy of our list of lines can leave the old and new versions sharing the same text in memory. A later edit could then silently change a supposedly saved snapshot. cloneLines copies the list and every line so each snapshot stands alone.

Record history where text changes
#

The code that interprets keys should not decide how history works. Every buffer operation that changes text records its own checkpoint – a saved point we can return to – immediately before the change. Moving the cursor and edits that do nothing record no history. This gives the buffer a useful promise: whenever it changes text, it preserves the state that came before.

One keystroke currently equals one undo step. A mature editor groups a run of typing and often treats pasted text as one edit. That is a useful refinement, but it is not needed to understand the basic idea.

Putting history into pseudocode
#

The editor now has two history collections in addition to its text buffer. A snapshot stores both text and cursor position, because undo should return us to where the edit began:

state:
    buffer.lines
    cursor.row, cursor.column
    undoStack = []
    redoStack = []

function snapshot():
    return {
        lines: deepCopy(buffer.lines),
        row: cursor.row,
        column: cursor.column
    }

Every edit that changes text starts by recording the state it is about to replace. A new edit also discards the redo path. In the pseudocode, push means “add to the top” and pop means “remove from the top” of a stack:

function checkpointBeforeEdit():
    push snapshot() onto undoStack

    if undoStack has more than 200 entries:
        discard its oldest entry

    clear redoStack

function insertCharacter(character):
    checkpointBeforeEdit()
    insert character into buffer at cursor
    move cursor right

function deleteBackward():
    if cursor is at beginning of document:
        return                         // no edit, so no checkpoint

    checkpointBeforeEdit()
    remove character before cursor,
        or join this line to the previous line

Undo and redo are the same transfer in opposite directions. Notice that these operations copy the current state before replacing it; otherwise moving one way through history would destroy the path back:

function undo():
    if undoStack is empty:
        show "nothing to undo"
        return

    push snapshot() onto redoStack
    previous = pop undoStack
    buffer.lines = deepCopy(previous.lines)
    cursor = (previous.row, previous.column)

function redo():
    if redoStack is empty:
        show "nothing to redo"
        return

    push snapshot() onto undoStack
    next = pop redoStack
    buffer.lines = deepCopy(next.lines)
    cursor = (next.row, next.column)

The code that handles keys adds two cases: Ctrl-Z calls undo, and Ctrl-Y calls redo. Drawing still receives the same array of lines; its status bar also shows the new shortcuts.

Drawbacks
#

As you’ll have noticed, this is a simple, understandable way to implement undo. But it comes at a cost: memory usage can climb quickly.

Suppose the document contains n characters. Copying a snapshot takes time and memory in proportion to those n characters: a document twice as large takes roughly twice as much work to copy. Keeping h snapshots multiplies that cost by the amount of history. In the usual shorthand, this is O(n) for one snapshot and O(hn) for the retained history. Typing 200 characters into a 10 MB ASCII file can retain roughly 8 GB of rune data: each rune occupies four bytes in memory. Go can copy quickly, but it cannot make that multiplication vanish.

This is why this simple implementation is valuable: it gives us something specific to improve. We want history states to describe edits without copying the whole file. In part 3 we will replace the array of lines with a piece table. It keeps the opened file unchanged, stores newly typed text by adding it to the end of a second collection, and represents the current document as a relatively small list of references into those two collections.

We now have a simple text editor with undo in about 520 lines of Go, excluding tests.

The code for this part is here.

Related