Command: undo and redo

"Add undo" is one of the most common new requirements in a coding round. It appears in a text editor, a drawing tool and a shopping cart. The interviewer wants to see you add it without a rewrite.

A weak answer saves a full copy of a big document before every change. Or it spreads "how to reverse this" across many if branches. A strong answer turns each action into a small object that knows how to do itself and how to undo itself. Then undo is a loop over a list. This shape is the Command pattern. It also gives you redo and a history.

At SDE-1 you should build undo for one kind of action. At SDE-2 you should add redo, a history limit and grouped steps, and keep the position in the text exact. Interviewers often ask: "What happens to redo when the user types something new?"

A waiter writes your order on a piece of paper. Before that, the order was only said aloud. Now it is a thing. The waiter can hand it to the kitchen, repeat it for the next table, or cancel it. A command is the same: a request written down as an object, so that you can store it, run it later and reverse it.

A command has two methods. do makes the change. undo puts everything back exactly as it was before do. You write undo next to do, so the command knows what to put back.

This lesson uses a small text editor. Its document holds the text and a cursor, the position where the next typed letter goes. Position 3 in helo is between hel and o. We keep both fields open to keep the code short. A real editor would give the document its own methods, as the lesson on encapsulation taught.

class Document:
    def __init__(self):
        self.text = ""
        self.cursor = 0

The commands share one interface, an abstract class (the lesson on interfaces). The editor works only with this interface, so a new action is a new class.

from abc import ABC, abstractmethod

class Command(ABC):
    @abstractmethod
    def do(self, doc):
        """Make the change. Raise ValueError, before changing anything,
        if it cannot be done. Return True if something changed."""

    @abstractmethod
    def undo(self, doc):
        """Put the document back exactly as it was before do."""

Why a command is worth it

Because a request is now an object, one idea gives you several things:

• Undo and redo. Call undo on the last command, or call do again.
• History. Keep the commands you have run, as a list of what happened.
• Delay. Keep the command and run it later.
• A macro. A group of commands that you can run together.

Two ways to undo

The first way is to store just enough to reverse the change: the typed text and the cursor for typing, the removed text for deleting. The second way is to copy the whole state before the change and put the copy back. The copy is simple to write. But its memory grows with the size of the state.

Assumption: the document has 100,000 characters, and the history keeps 100 steps. Copying the whole text each time stores 100 x 100,000 = 10,000,000 characters. Storing what is needed to reverse a typed word of 10 characters stores 100 x 10 = 1,000 characters. Each step also keeps two cursor numbers. Copying is fine when the state is small, such as a board of 9 cells.

Reading the code

The commands use a few small Python features:

• text[:at] is the text before position at. text[at:] is the text from at to the end. text[a:b] is from a up to, but not including, b.
• So text[:at] + new + text[at:] puts new at position at.
• max(a, b) gives the larger of two numbers.
• a <= x <= b means that x is between a and b.
• d.get(k, v) gives the value of key k, or v if the key is missing.
• del d[k] removes the key k from a dictionary.
• reversed(xs) goes through a list from the end. xs.clear() empties a list.
• x if c else y is x when c is true, otherwise y.
• a, b = c, d sets both names at once.

The commands

Typing inserts text at the cursor and moves the cursor to the end of the new text. The cursor can move between an undo and a redo, because move is not a command. So each command stores its own positions: the cursor before and the cursor after. It never reads the cursor again.

class InsertText(Command):
    def __init__(self, new_text):
        self._new_text = new_text
        self._before = None
        self._after = None

    def do(self, doc):
        if not self._new_text:
            return False
        if self._before is None:
            self._before = doc.cursor
        at = self._before
        doc.text = doc.text[:at] + self._new_text + doc.text[at:]
        self._after = at + len(self._new_text)
        doc.cursor = self._after
        return True

The first do reads the cursor. A later do (a redo) uses the stored value. Now the other half of the class:

    def undo(self, doc):
        doc.text = doc.text[:self._before] + doc.text[self._after:]
        doc.cursor = self._before

Deleting removes characters before the cursor. To undo it, store the removed text and both cursors. A delete at the start of the text removes nothing, so it returns False. A bad count raises an error before anything changes (the lesson on bad input and errors).

class DeleteBack(Command):
    def __init__(self, count):
        self._count = count
        self._before = None
        self._after = None
        self._removed = ""

    def do(self, doc):
        if self._count < 1:
            raise ValueError("count must be at least 1")
        before = doc.cursor if self._before is None else self._before
        after = max(0, before - self._count)
        if after == before:
            return False
        self._before, self._after = before, after
        self._removed = doc.text[after:before]
        doc.text = doc.text[:after] + doc.text[before:]
        doc.cursor = after
        return True

The undo puts the removed text back where it was, and the cursor back where it was:

    def undo(self, doc):
        at = self._after
        doc.text = doc.text[:at] + self._removed + doc.text[at:]
        doc.cursor = self._before

Two stacks

A stack is a pile where the last item added is the first one taken. A Python list does this with append and pop. The editor keeps two stacks. The undo stack holds the commands that were done. The redo stack holds the commands that were undone.

• Run a new command: call do. If it changed something, push it on the undo stack and clear the redo stack.
• Undo: pop the last command from the undo stack, call its undo, and push it on the redo stack.
• Redo: pop from the redo stack, call do again, and push it on the undo stack.

Why clear the redo stack on a new command? The undone commands were made for a document that has changed. Most editors work this way. Some keep a tree of the undone branches, which is more work than a round needs.

A command that changed nothing is not recorded. If it were, one undo press would seem to do nothing, and the redo stack would be cleared for no reason.

A history limit. Memory is finite, so keep only the last N commands. A deque(maxlen=N) (lesson "Ordered data") does it: when it is full, a new command pushes the oldest one out.

from collections import deque

class Editor:
    def __init__(self, history_limit=100):
        self.doc = Document()
        self._undo = deque(maxlen=history_limit)
        self._redo = []

    def execute(self, command):
        if command.do(self.doc):
            self._undo.append(command)
            self._redo.clear()

If do raises an error, the next line never runs, so nothing is recorded. Moving the cursor is not a command, because it changes no text.

    def move(self, position):
        if not 0 <= position <= len(self.doc.text):
            raise ValueError("cursor outside the text")
        self.doc.cursor = position

    def show(self):
        return (self.doc.text, self.doc.cursor)

The two methods for undo and redo:

    def undo(self):
        if not self._undo:
            return False
        command = self._undo.pop()
        command.undo(self.doc)
        self._redo.append(command)
        return True

    def redo(self):
        if not self._redo:
            return False
        command = self._redo.pop()
        command.do(self.doc)
        self._undo.append(command)
        return True

Group several commands as one step

"Replace a word" is a delete followed by an insert. The user expects one undo to bring the old word back. A group is a command that holds a list of commands. Its do runs them in order. Its undo undoes them in the reverse order. If one command fails halfway, the group undoes the ones that already ran, and raises the error again. This is the "undo on failure" way of the lesson on bad input and errors.

class Group(Command):
    def __init__(self, commands):
        self._commands = commands
        self._done = []

    def do(self, doc):
        self._done = []
        try:
            for command in self._commands:
                if command.do(doc):
                    self._done.append(command)
        except ValueError:
            self.undo(doc)
            raise
        return len(self._done) > 0

    def undo(self, doc):
        for command in reversed(self._done):
            command.undo(doc)
        self._done = []

A group that you keep and run again is also a macro.

Command, Strategy and State

Strategy and State (the lesson on Strategy, Observer and State) also use small classes. They answer different questions.

The same idea in other places

A store that can cancel changes. A transaction is a group of changes that all happen or are all undone. A small store can support it with an undo log. Before each change, it writes down the key and its old value. To cancel, it goes through the log from the end to the start and puts the old values back. This is the undo stack again, with a value in place of a command. MISSING is a marker that says "this key did not exist".

MISSING = object()

class TinyStore:
    def __init__(self):
        self._data = {}
        self._log = None

    def begin(self):
        self._log = []

    def set(self, key, value):
        if self._log is not None:
            self._log.append((key, self._data.get(key, MISSING)))
        self._data[key] = value

    def get(self, key):
        return self._data.get(key)

The two ways to end a transaction check first that one is open:

    def commit(self):
        if self._log is None:
            raise ValueError("no transaction is open")
        self._log = None

    def rollback(self):
        if self._log is None:
            raise ValueError("no transaction is open")
        for key, old in reversed(self._log):
            if old is MISSING:
                del self._data[key]
            else:
                self._data[key] = old
        self._log = None

A task you save and run later. A command is an object, so you can keep it in a list and call do when the time comes. A reminder such as "close the counter at 9 pm" waits in a list until then.

Run with Python 3.11. The classes are the ones above. The method show returns the pair (text, cursor).

e = Editor()
e.execute(InsertText("helo"))
e.move(3)
e.execute(InsertText("l"))
e.undo()
e.redo()
e.execute(DeleteBack(1))

Here are the text and the cursor after each step. The stacks are listed with the top first.

The undo and redo stacks of the editor at two moments. After step 4, the undo stack holds type helo and the redo stack holds type l, which just moved there from the undo stack. After step 6, the undo stack holds delete l on top, then type l, then type helo, and the redo stack is empty because a new command clears it.

The predict box. At step 4 the text is helo and the cursor is 3, not 4 or 0. The command for l stored the cursor before (3), so undo removed the l at position 3 and put the cursor back there. The undo stack holds one command, the typing of helo. The redo stack holds the typing of l.

Step 5 runs the same command again: hello, cursor 4. Step 6 deletes the one character before the cursor 4, which is the second l. The text is helo and the cursor is 3. The redo stack is empty, because a new command clears it. A further undo gives hello with cursor 4, because the delete stored the removed l and both cursors.

A new edit after an undo.

e.undo()
e.execute(InsertText("!"))
print(e.show(), e.redo())

It prints ('hell!o', 5) False. The undo gave hello with cursor 4. Typing ! put it at position 4, so the text is hell!o and the cursor is 5. redo() returns False, because the new command cleared the redo stack.

The cursor moves between undo and redo. This is the case that the stored positions protect.

e = Editor()
e.execute(InsertText("abc"))
e.execute(InsertText("X"))
e.undo()
e.move(0)
e.redo()
print(e.show())

It prints ('abcX', 4). The X went back after abc, although the cursor was at 0 when we pressed redo. If the command read the cursor again, it would insert X at position 0 and print ('Xabc', 1). A delete works the same way: undo puts the removed text back at the stored position.

The history limit. Make an editor with Editor(history_limit=3), type a, b, c and d one at a time, and press undo four times:

e = Editor(history_limit=3)
for letter in "abcd":
    e.execute(InsertText(letter))
print(e.show(), [e.undo() for _ in range(4)], e.show())

It prints ('abcd', 4) [True, True, True, False] ('a', 1). The first command left the history when the fourth was added, so the editor cannot go back before a. (range(4) counts 0, 1, 2, 3, and _ is a name for a value we do not use.)

A group, and a group that fails. Type hello (cursor 5). Run Group([DeleteBack(5), InsertText("world")]). The text is world. One undo gives hello, and one redo gives world again. Now run Group([InsertText("x"), DeleteBack(0)]). The insert runs, and then the delete raises count must be at least 1. The group undoes the insert. The text and cursor are as before, and nothing was recorded.

The undo log. In the store, set a to 1, call begin(), then set a to 2, b to 9 and a to 3. get("a") gives 3 and get("b") gives 9. After rollback(), get("a") gives 1 and get("b") gives None. The log held (a, 1), (b, MISSING) and (a, 2).

Command solves undo, redo and history. Every new action is a new small class, so the editor does not change. It costs a class for each action, memory for the history, and an undo that you must write by hand and get exactly right. I would change to a copy of the whole state when the state is small, or when reversing is hard to write. I would use a plain method when the product does not need undo.

"To undo, I must save a copy of the whole document before each step." That is one way, and it is simple. But with 100 steps of a 100,000-character document it stores 10,000,000 characters. Storing only what reverses the step stores 1,000.

"After an undo, a new edit keeps the redo list." It does not. The redo stack is cleared, because the undone commands were made for a document that has changed. In the example, redo() returned False after the !.

"Command and Strategy are the same, because both are small classes with one method." A Strategy is one way of doing a job, chosen once. A Command is one request, kept in a list with what is needed to reverse it. If you never store, reverse or repeat the request, you do not need a Command.

1. What two methods does a command have? What happens to the redo stack when a new command runs, and why?
2. A document has 20,000 characters, and the history keeps 50 steps. How many characters does the "copy the whole text" way store? How many does the "store what is needed to reverse" way store, if each step is a typed word of at most 10 characters?
3. A teammate writes InsertText.undo as doc.text = doc.text[:-len(self._new_text)] and sets the cursor to the end of the text. A user types helo, moves to 3, types l and presses undo. What do they see, and what do you change?