Undo and Redo in Python: the Memento and Command Patterns Compared

Undo looks easy until the edits stop happening at the end of the text. This lesson breaks a naive undo, then builds two correct ones and measures the difference between them.

A naive undo that assumes edits are appended

This editor remembers how long each edit was, and undoes it by cutting that many characters off the end.

# undo_naive.py: undo remembers how many characters each edit added, and chops them off the end
class Editor:
    def __init__(self):
        self.text = ""
        self.added = []                       # length of each edit, for undo

    def insert(self, pos, chunk):
        self.text = self.text[:pos] + chunk + self.text[pos:]
        self.added.append(len(chunk))

    def undo(self):
        n = self.added.pop()
        self.text = self.text[:-n]            # assumes the last edit was at the end

ed = Editor()
ed.insert(0, "Hello world")
ed.insert(5, ",")                             # a comma in the middle
print("after edits:", repr(ed.text))
ed.undo()
print("after undo: ", repr(ed.text))

$ python undo_naive.py
after edits: 'Hello, world'
after undo:  'Hello, worl'

Undoing the comma should give back 'Hello world'. Instead the comma is still there and the final d is gone. The undo assumed the last edit was at the end; this one was in the middle. The history recorded how much changed, not where or what, so there’s no way to fix it from that information.

Memento: snapshot the state, restore it whole

The editor creates a snapshot of itself before each edit. A separate history keeps the snapshots, and only the editor reads them back.

# memento.py: the editor hands out snapshots of itself; the history keeps them without reading them
class Memento:
    """An opaque snapshot. Only the Editor reads what's inside."""
    def __init__(self, text, cursor):
        self._text, self._cursor = text, cursor

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

    def insert(self, chunk):
        self.text = self.text[:self.cursor] + chunk + self.text[self.cursor:]
        self.cursor += len(chunk)

    def delete(self, n):                      # delete n characters before the cursor
        self.text = self.text[:self.cursor - n] + self.text[self.cursor:]
        self.cursor -= n

    def save(self):
        return Memento(self.text, self.cursor)

    def restore(self, memento):
        self.text, self.cursor = memento._text, memento._cursor

class History:
    def __init__(self, editor):
        self.editor, self.stack = editor, []
    def checkpoint(self):
        self.stack.append(self.editor.save())
    def undo(self):
        self.editor.restore(self.stack.pop())

ed = Editor()
history = History(ed)
history.checkpoint(); ed.insert("Hello world")
ed.cursor = 5
history.checkpoint(); ed.insert(",")
history.checkpoint(); ed.cursor = len(ed.text); ed.delete(5)
print("after edits:", repr(ed.text))
for _ in range(3):
    history.undo()
    print("undo ->     ", repr(ed.text))

$ python memento.py
after edits: 'Hello, '
undo ->      'Hello, world'
undo ->      'Hello world'
undo ->      ''

Every undo is exact, including the delete, because restoring a snapshot doesn’t need to know what the edit was. The roles are deliberate. The Editor creates and reads mementos; History only stacks them, so it never depends on the editor’s internals. Adding a field to the editor, such as the cursor here, changes save and restore and nothing else.

Command: store the edit, not the state

The other approach records each edit as an object that can reverse itself. The Command pattern is already covered on this site; here it carries undo and redo.

# command_undo.py: each edit is a Command that keeps just enough to reverse itself
class Insert:
    def __init__(self, pos, chunk):
        self.pos, self.chunk = pos, chunk
    def execute(self, doc):
        doc.text = doc.text[:self.pos] + self.chunk + doc.text[self.pos:]
    def undo(self, doc):
        doc.text = doc.text[:self.pos] + doc.text[self.pos + len(self.chunk):]

class Delete:
    def __init__(self, pos, n):
        self.pos, self.n, self.removed = pos, n, ""
    def execute(self, doc):
        self.removed = doc.text[self.pos:self.pos + self.n]   # remembered for undo
        doc.text = doc.text[:self.pos] + doc.text[self.pos + self.n:]
    def undo(self, doc):
        doc.text = doc.text[:self.pos] + self.removed + doc.text[self.pos:]

class Document:
    def __init__(self):
        self.text, self.done, self.undone = "", [], []
    def run(self, command):
        command.execute(self)
        self.done.append(command)
        self.undone.clear()                   # a new edit discards the redo stack
    def undo(self):
        command = self.done.pop()
        command.undo(self)
        self.undone.append(command)
    def redo(self):
        command = self.undone.pop()
        command.execute(self)
        self.done.append(command)

doc = Document()
doc.run(Insert(0, "Hello world"))
doc.run(Insert(5, ","))
doc.run(Delete(6, 6))
print("after edits:", repr(doc.text))
doc.undo(); print("undo ->     ", repr(doc.text))
doc.undo(); print("undo ->     ", repr(doc.text))
doc.redo(); print("redo ->     ", repr(doc.text))

$ python command_undo.py
after edits: 'Hello,'
undo ->      'Hello, world'
undo ->      'Hello world'
redo ->      'Hello, world'

Delete saves the six characters it removed during execute, so its undo can put them back. Redo replays a command from the second stack. A new run clears that stack, because the undone edits no longer fit the document.

What each one costs

The same 1,000 one-character edits, recorded both ways, on a 10,000-character document.

# undo_memory.py: 1,000 one-character edits to a 10,000-character document, two ways
import sys

class Insert:                                 # the same command class as above
    def __init__(self, pos, chunk):
        self.pos, self.chunk = pos, chunk

def footprint(objects):
    """Total getsizeof of every distinct object, so shared ones count once."""
    seen = {id(o): o for o in objects}
    return sum(sys.getsizeof(o) for o in seen.values())

document = "x" * 10_000
snapshots, commands = [], []
for i in range(1_000):
    snapshots.append(document)                # Memento: a full copy before every edit
    pos = i * 7 % len(document)
    commands.append(Insert(pos, "y"))         # Command: only what the edit changed
    document = document[:pos] + "y" + document[pos:]

snapshot_bytes = footprint(snapshots)
parts = [p for c in commands for p in (c, c.__dict__, c.pos, c.chunk)]
command_bytes = footprint(parts)
print(f"snapshots: {len(snapshots):,} copies, {snapshot_bytes:,} bytes")
print(f"commands:  {len(commands):,} objects, {command_bytes:,} bytes")
print(f"ratio:     about {snapshot_bytes // command_bytes}x")

$ python undo_memory.py
snapshots: 1,000 copies, 10,540,500 bytes
commands:  1,000 objects, 164,042 bytes
ratio:     about 64x

Snapshots copy the whole document every time, so they cost about 10.5 MB here. The 1,000 Insert objects, counting each one’s instance, its attribute dict and its pos integer, take about 164 KB, roughly 64 times less. footprint counts each distinct object once: the 'y' is a single shared string, and Python reuses small integers, so those aren’t counted 1,000 times. That’s the trade: Memento is simpler and works for any change; Command needs a correct undo for every kind of edit, and in return its memory grows with the size of the edits, not the size of the document.

Practice

# p18_1.py: redo for the Memento history: undo saves the current state on a redo stack
class Memento:
    def __init__(self, text):
        self._text = text

class Editor:
    def __init__(self):
        self.text = ""
    def save(self):
        return Memento(self.text)
    def restore(self, memento):
        self.text = memento._text

class History:
    def __init__(self, editor):
        self.editor, self.undo_stack, self.redo_stack = editor, [], []
    def checkpoint(self):
        self.undo_stack.append(self.editor.save())
        self.redo_stack.clear()
    def undo(self):
        self.redo_stack.append(self.editor.save())
        self.editor.restore(self.undo_stack.pop())
    def redo(self):
        self.undo_stack.append(self.editor.save())
        self.editor.restore(self.redo_stack.pop())

ed = Editor()
history = History(ed)
for word in ["one", " two", " three"]:
    history.checkpoint()
    ed.text += word
history.undo(); history.undo()
print("after 2 undos:", repr(ed.text))
history.redo()
print("after redo:   ", repr(ed.text))

$ python p18_1.py
after 2 undos: 'one'
after redo:    'one two'

# p18_2.py: cap the history at 3 snapshots with a deque, so memory stops growing
from collections import deque

class Editor:
    def __init__(self):
        self.text = ""

history = deque(maxlen=3)                     # the oldest snapshot falls off the left
ed = Editor()
for word in ["a", "b", "c", "d", "e"]:
    history.append(ed.text)
    ed.text += word
print("kept snapshots:", list(history))
undos = 0
while history:
    ed.text = history.pop()
    undos += 1
print(f"undid {undos} times, text is now {ed.text!r}")

$ python p18_2.py
kept snapshots: ['ab', 'abc', 'abcd']
undid 3 times, text is now 'ab'

# p18_3.py: a Macro command groups several commands so one undo reverses all of them
class Insert:
    def __init__(self, pos, chunk):
        self.pos, self.chunk = pos, chunk
    def execute(self, doc):
        doc.text = doc.text[:self.pos] + self.chunk + doc.text[self.pos:]
    def undo(self, doc):
        doc.text = doc.text[:self.pos] + doc.text[self.pos + len(self.chunk):]

class Macro:
    def __init__(self, *commands):
        self.commands = commands
    def execute(self, doc):
        for c in self.commands:
            c.execute(doc)
    def undo(self, doc):
        for c in reversed(self.commands):     # undo in the opposite order
            c.undo(doc)

class Document:
    def __init__(self):
        self.text, self.done = "", []
    def run(self, command):
        command.execute(self)
        self.done.append(command)
    def undo(self):
        self.done.pop().undo(self)

doc = Document()
doc.run(Insert(0, "price"))
doc.run(Macro(Insert(0, "<b>"), Insert(8, "</b>")))   # "bold" is two inserts
print("after bold:", doc.text)
doc.undo()
print("one undo:  ", doc.text)

$ python p18_3.py
after bold: <b>price</b>
one undo:   price