Design a text editor with undo and redo¶
TL;DR¶
- You build a
Document(buffer + caret + history under one lock) and anEditorfacade where every mutation becomes exactly oneCommandobject that knows how to apply itself and how to take itself back. - Three decisions carry the interview: the caret is part of the command (undo restores the selection, not just the characters), consecutive keystrokes coalesce into one undo entry while they stay adjacent and inside a time window, and a new command clears the redo stack.
- Patterns that earn their place: Command, Composite (macros — which is why there is no
PasteCommand), Strategy (the buffer), Flyweight (styles), Observer (views). Memento is discussed and deliberately not used.
Problem statement¶
"Design the core of a text editor. It holds one or more open documents; the user types, deletes, moves the caret, selects ranges, and cuts, copies and pastes. Undo and redo must work the way people expect: a burst of typing is one undo, the caret goes back where it was, and redo disappears the moment you type something new. Find-and-replace should be undoable in one step. Say what data structure is under the text, and keep the history from growing without bound."
Requirements¶
Functional
- Multiple open documents (tabs), each with its own buffer, caret and history.
- Insert and delete at the caret; caret movement; selection with an anchor.
- Copy, cut and paste through a clipboard.
- Undo and redo with a bounded history; a new command invalidates redo.
- Consecutive keystrokes coalesce into one undo entry; a pause or a caret move ends the run.
- Find (including overlapping matches) and replace-all as a single undoable step.
- Formatting runs over ranges that shift when text is inserted before them.
- Save and load through a storage interface; word count; a modified/saved indicator.
Non-functional and constraints
- Undo restores the caret and the selection exactly, not only the text.
- The buffer and the history can never disagree — an edit and its history entry are one atomic step.
- The undo stack is capped; the oldest entries are dropped, never the newest.
- In-memory, single process, standard library only. Time is injected, so the coalescing window is testable without sleeping.
Out of scope: rendering, syntax highlighting, real-time collaboration (that is Design Google Docs), regular-expression search, and encodings beyond Python str.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
| Command or Memento for undo? | Command. A Memento snapshots the whole document per edit, which is O(document) memory per keystroke; a command stores only the delta and the two caret states. |
| Is a burst of typing one undo or twenty? | One, while the inserts stay adjacent, contain no newline, arrive within the coalescing window and stay under a length cap. Every one of those four conditions is a real editor behaviour. |
| Does undo restore the selection? | Yes. Each command carries before and after cursors; undo applies before. This is the detail that separates a toy from a design. |
| What happens to redo after a new edit? | It is cleared. The branch you undid is gone — no undo tree, and say that you know the alternative exists. |
| Gap buffer, piece table or a plain string? | A gap buffer by default, behind a TextBuffer protocol, with a plain-string implementation kept as the honest baseline. |
| Is the history per document or per editor? | Per document. Undo in one tab must not touch another. |
| Where does paste live? | Paste is not a command class — it is a macro of delete-selection plus insert. |
Core entities and relationships¶
- Editor — the facade a keyboard talks to. It owns the tab registry, the clipboard, the style registry and storage, and it turns each keystroke into exactly one
Command. - Document — one tab: a
TextBuffer, aCursor, style runs, listeners and its ownCommandHistory. It implements the narrowEditTargetprotocol that commands are allowed to call. - TextBuffer (protocol) —
GapBuffer(default) andSimpleBuffer(a plain string). The commands never know which one they are editing. - Cursor and Selection — frozen value objects.
Cursor(position, anchor); a selection exists when the anchor differs from the position. - Command (abstract) —
InsertCommand,DeleteCommand,ReplaceCommand,MacroCommand. Each stores its delta plusbeforeandaftercursors. - CommandHistory — the undo deque and the redo list, plus the coalescing window and the cap. It shares the document's lock.
- Clipboard — one per process, injected; StyleRegistry — the Flyweight factory; Style / StyleRun — shared intrinsic state and per-range extrinsic state.
- FileStorage (protocol) —
InMemoryStoragehere; DocumentListener —StatusBar, an observer of revisions.
Multiplicities: editor 1 → * documents, document 1 → 1 buffer, document 1 → 1 history, history 1 → * commands, macro 1 → * commands.
Class diagram¶
Structure: a tab and everything hanging off it.
classDiagram
class Editor {
+storage: FileStorage
+clipboard: Clipboard
+styles: StyleRegistry
-_lock: Lock
+new_tab(name, text) Document
+type_text(text) Command
+backspace() Command
+move_to(position, extend) Cursor
+cut() str
+paste() Command
+replace_all(needle, replacement) Command
+save(name) str
}
class Document {
+name: str
+history: CommandHistory
-_lock: RLock
-_revision: int
+apply_insert(position, text)
+apply_delete(position, length) str
+set_cursor(cursor)
+run(command) Command
+undo() Command
+status() DocumentStatus
}
class Cursor {
+position: int
+anchor: int
+selection() Selection
+moved_to(position, extend) Cursor
}
class Selection {
+start: int
+end: int
+length: int
}
class TextBuffer {
<<interface>>
+text() str
+slice(start, end) str
+insert(position, text)
+delete(position, length) str
}
class GapBuffer {
-_gap_start: int
-_gap_end: int
+gap_size() int
}
class SimpleBuffer
class Style {
+bold: bool
+italic: bool
+colour: str
}
class StyleRun {
+start: int
+end: int
}
class StyleRegistry {
+get(bold, italic, underline, colour) Style
}
class Clipboard {
+copy(text)
+paste() str
}
class FileStorage {
<<interface>>
+save(name, content)
+load(name) str
}
class DocumentListener {
<<interface>>
+on_document_changed(name, revision)
}
class StatusBar
Editor "1" *-- "many" Document
Editor --> "1" Clipboard
Editor --> "1" StyleRegistry
Editor --> "1" FileStorage
Document --> "1" TextBuffer
Document --> "1" Cursor
Document "1" o-- "many" StyleRun
Document --> "many" DocumentListener
Cursor ..> Selection : derives
TextBuffer <|.. GapBuffer
TextBuffer <|.. SimpleBuffer
StyleRun --> "1" Style
StyleRegistry ..> Style : interns
DocumentListener <|.. StatusBarBehaviour: the command layer, which depends on nothing but a three-method protocol.
classDiagram
class Command {
<<abstract>>
+before: Cursor
+after: Cursor
+execute(target: EditTarget)*
+undo(target: EditTarget)*
+describe() str
+coalesce_with(previous) Command
}
class InsertCommand {
+position: int
+text: str
}
class DeleteCommand {
+position: int
+length: int
+removed: str
}
class ReplaceCommand {
+position: int
+old_length: int
+new_text: str
}
class MacroCommand {
+label: str
+commands: List~Command~
}
class CommandHistory {
+capacity: int
+coalesce_window: float
+dropped: int
-_undo: Deque~Command~
-_redo: List~Command~
-_lock: RLock
+record(command)
+undo(target) Command
+redo(target) Command
+break_coalescing()
+depth() int
+top() Command
}
class EditTarget {
<<interface>>
+apply_insert(position, text)
+apply_delete(position, length) str
+set_cursor(cursor)
}
class Document
class Cursor
Command <|-- InsertCommand
Command <|-- DeleteCommand
Command <|-- ReplaceCommand
Command <|-- MacroCommand
MacroCommand "1" o-- "many" Command
Command ..> EditTarget : acts on
Command --> "2" Cursor : before and after
CommandHistory "1" o-- "many" Command
EditTarget <|.. Document
Document --> "1" CommandHistoryDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| Command | InsertCommand, DeleteCommand, ReplaceCommand |
Undo becomes a method on the object that did the work, not a giant if on an operation code. Adding "indent block" is one class, and it gets undo for free. |
| Composite | MacroCommand |
Paste, type-over-a-selection and replace-all are all "several edits, one undo step". Because a macro is a command, it nests and needs no special case in the history. |
| Strategy | TextBuffer with GapBuffer / SimpleBuffer |
The data structure under the text is the question the interviewer wants discussed. Behind a four-method protocol you can answer it without rewriting anything else. |
| Flyweight | Style + StyleRegistry |
A million bold characters share one Style object; the per-range cost is a StyleRun of three fields. The registry interns by value so identity comparison works. |
| Observer | DocumentListener → StatusBar |
Views redraw when the revision changes and the document knows nothing about views. Notification happens outside the lock so a slow view never blocks typing. |
| Facade | Editor |
Keystrokes should not construct command objects. The editor turns intent ("backspace") into the right command with the right caret states. |
| Singleton (offered) | Clipboard.instance() |
The clipboard genuinely is machine-wide, but the constructor stays public: tests build their own, and two editors in one process can share one by injection. |
| Dependency Injection | Clock, FileStorage, buffer_factory |
FakeClock makes the coalescing window a deterministic assertion instead of a sleep(1.1). |
Deliberately not used: Memento. It is the pattern people reach for first, and it is the wrong trade here — a snapshot per keystroke costs O(document) memory and O(document) time, where a command costs O(edit). Memento earns its place when an operation is not invertible (a filter over a whole buffer, a re-flow); the right answer in a real editor is a hybrid, a command log with periodic snapshots. Say that, and you have said something the other candidates have not. Also not used: an undo tree. Redo is a stack and a new edit discards the branch, which is what every mainstream editor does.
Key flows¶
One keystroke: build the command, execute and record atomically, maybe merge.
sequenceDiagram
autonumber
actor U as Typist
participant E as Editor
participant D as Document
participant C as InsertCommand
participant B as GapBuffer
participant H as CommandHistory
U->>E: type_text(a)
E->>D: cursor()
D-->>E: Cursor(position, anchor)
E->>C: build with before and after cursors
E->>D: run(command)
D->>D: take the document RLock
D->>C: execute(document)
C->>B: insert(position, a)
C->>D: set_cursor(after)
D->>H: record(command)
alt adjacent, no newline, inside the window
H->>H: merge into the top entry
else new run
H->>H: push, clear redo, drop the oldest past the cap
end
D-->>U: revision bumped, listeners notified outside the lockUndo and redo: the two stacks, and the caret coming back with the text.
sequenceDiagram
autonumber
actor U as Typist
participant E as Editor
participant D as Document
participant H as CommandHistory
participant C as MacroCommand
U->>E: undo()
E->>D: undo()
D->>H: undo(document)
alt undo stack empty
H-->>U: NothingToUndoError
else
H->>C: pop the top entry, then undo(document)
C->>D: reverse each child edit, last to first
C->>D: set_cursor(before)
H->>H: push onto redo, stop coalescing
H-->>E: the command, for the status bar
end
U->>E: type_text(x)
E->>H: record(new command)
H->>H: clear redo - that future is goneDocument status. The saved marker stores the command object on top of the undo stack, which is why undoing back to where you saved shows SAVED again. Storing a depth instead is the trap: save, undo once, then type something new, and the stack is back to the same depth holding entirely different work — a counter reports SAVED over unsaved changes, and the user closes the tab.
stateDiagram-v2
[*] --> NEW : new_tab
NEW --> MODIFIED : first edit
NEW --> SAVED : save an empty document
MODIFIED --> SAVED : save, marking the top command
SAVED --> MODIFIED : any edit
MODIFIED --> SAVED : undo back to the marked command
SAVED --> [*] : close_tabImplementation¶
Start with the value objects, because the caret being a value is what makes undo restore a selection.
code/lld/text_editor/models.py — statuses
class DocumentStatus(StrEnum):
NEW = "new" # never saved and never edited
MODIFIED = "modified" # the buffer differs from what storage holds
SAVED = "saved" # in sync with storage (undoing back here restores it)
class Direction(StrEnum):
LEFT = "left"
RIGHT = "right"
LINE_START = "line_start"
LINE_END = "line_end"
code/lld/text_editor/models.py — the caret
@dataclass(frozen=True, slots=True)
class Selection:
"""A normalised half-open range. ``start <= end`` always holds."""
start: int
end: int
def __post_init__(self) -> None:
if self.start < 0 or self.end < self.start:
raise OutOfBoundsError(f"invalid selection ({self.start}, {self.end})")
@property
def length(self) -> int:
return self.end - self.start
def is_empty(self) -> bool:
return self.length == 0
@dataclass(frozen=True, slots=True)
class Cursor:
"""Caret position plus the anchor a shift-selection was started from."""
position: int
anchor: int | None = None
def selection(self) -> Selection | None:
if self.anchor is None or self.anchor == self.position:
return None
return Selection(min(self.anchor, self.position), max(self.anchor, self.position))
def collapsed(self) -> Cursor:
return Cursor(self.position)
def moved_to(self, position: int, extend: bool = False) -> Cursor:
anchor = (self.anchor if self.anchor is not None else self.position) if extend else None
return Cursor(position, anchor)
The buffer is a Strategy behind four methods. Write the plain-string version first and say what it costs, then write the gap buffer and say when the cost matters.
code/lld/text_editor/buffers.py — the honest baseline
class SimpleBuffer:
"""A plain string. Every insert copies the whole document: O(n) per keystroke.
Correct, and fine up to a few hundred kilobytes. Name it as the baseline you
would ship first, then say what you would replace it with and when.
"""
def __init__(self, text: str = "") -> None:
self._text = text
def __len__(self) -> int:
return len(self._text)
def text(self) -> str:
return self._text
def slice(self, start: int, end: int) -> str:
return self._text[max(0, start) : max(0, end)]
def insert(self, position: int, text: str) -> None:
self._check(position)
self._text = self._text[:position] + text + self._text[position:]
def delete(self, position: int, length: int) -> str:
self._check(position + length)
removed = self._text[position : position + length]
self._text = self._text[:position] + self._text[position + length :]
return removed
def _check(self, position: int) -> None:
if not 0 <= position <= len(self._text):
raise OutOfBoundsError(f"position {position} outside 0..{len(self._text)}")
code/lld/text_editor/buffers.py — the gap buffer
class GapBuffer:
"""A list of characters with a movable hole where the caret is.
Typing at the caret writes into the hole: O(1) amortised, no copying. Moving
the caret k characters copies k characters, which is exactly the workload a
text editor has -- edits cluster where the caret already is. A piece table
is the other classic answer: it never moves text and makes undo nearly free,
at the cost of a rope-like index for random access. Say both, pick one, and
give the reason: gap buffer for a single caret, piece table for collaborative
editing where several carets touch the document at once.
"""
MIN_GAP = 16
def __init__(self, text: str = "", gap_size: int = MIN_GAP) -> None:
self._chars: list[str] = list(text) + [""] * max(gap_size, 1)
self._gap_start = len(text)
self._gap_end = len(self._chars)
def __len__(self) -> int:
return len(self._chars) - (self._gap_end - self._gap_start)
def text(self) -> str:
return "".join(self._chars[: self._gap_start]) + "".join(self._chars[self._gap_end :])
def slice(self, start: int, end: int) -> str:
start, end = max(0, start), min(len(self), end)
return "".join(self._chars[self._raw(i)] for i in range(start, end))
def insert(self, position: int, text: str) -> None:
self._check(position)
self._move_gap(position)
if self._gap_end - self._gap_start < len(text):
self._grow(len(text))
for char in text:
self._chars[self._gap_start] = char
self._gap_start += 1
def delete(self, position: int, length: int) -> str:
self._check(position + length)
removed = self.slice(position, position + length)
self._move_gap(position)
self._gap_end += length # swallow the following characters into the gap
return removed
def gap_size(self) -> int:
return self._gap_end - self._gap_start
def _raw(self, index: int) -> int:
return index if index < self._gap_start else index + (self._gap_end - self._gap_start)
def _check(self, position: int) -> None:
if not 0 <= position <= len(self):
raise OutOfBoundsError(f"position {position} outside 0..{len(self)}")
def _move_gap(self, position: int) -> None:
if position < self._gap_start:
count = self._gap_start - position
self._chars[self._gap_end - count : self._gap_end] = self._chars[position : self._gap_start]
self._gap_start -= count
self._gap_end -= count
elif position > self._gap_start:
count = position - self._gap_start
self._chars[self._gap_start : self._gap_start + count] = self._chars[
self._gap_end : self._gap_end + count
]
self._gap_start += count
self._gap_end += count
def _grow(self, needed: int) -> None:
extra = max(needed, len(self._chars) // 2, self.MIN_GAP)
self._chars[self._gap_end : self._gap_end] = [""] * extra
self._gap_end += extra
Commands act on a three-method protocol, not on Document. That is what keeps tabs, styles, storage and listeners out of the undo layer entirely.
code/lld/text_editor/commands.py — what a command may touch
class EditTarget(Protocol):
"""The three operations a command needs. ``Document`` implements it.
Commands depend on this narrow protocol rather than on ``Document``, so the
command layer has no idea about tabs, listeners, styles or storage.
"""
def apply_insert(self, position: int, text: str) -> None: ...
def apply_delete(self, position: int, length: int) -> str: ...
def set_cursor(self, cursor: Cursor) -> None: ...
Here is the heart of it. Note coalesce_with: the command decides whether two edits are structurally mergeable, and the history decides whether they are close enough in time. Splitting the decision that way keeps the time policy in one place.
code/lld/text_editor/commands.py — the commands
class Command(ABC):
"""Every edit is an object that knows how to apply itself and how to take itself back.
``before`` and ``after`` are the caret states around the edit. Storing both
is what makes undo restore the *selection* and not just the characters --
the difference between an editor that feels right and one that does not.
"""
before: Cursor
after: Cursor
@abstractmethod
def execute(self, target: EditTarget) -> None: ...
@abstractmethod
def undo(self, target: EditTarget) -> None: ...
@abstractmethod
def describe(self) -> str: ...
def coalesce_with(self, previous: Command) -> Command | None:
"""Return a merged command, or None when the two must stay separate."""
return None
@dataclass(slots=True)
class InsertCommand(Command):
position: int
text: str
before: Cursor
after: Cursor
def execute(self, target: EditTarget) -> None:
target.apply_insert(self.position, self.text)
target.set_cursor(self.after)
def undo(self, target: EditTarget) -> None:
target.apply_delete(self.position, len(self.text))
target.set_cursor(self.before)
def describe(self) -> str:
return f"insert {self.text!r} at {self.position}"
def coalesce_with(self, previous: Command) -> Command | None:
"""Merge only *typing*: adjacent, same direction, no newline, bounded length."""
if not isinstance(previous, InsertCommand):
return None
if previous.position + len(previous.text) != self.position:
return None
if "\n" in previous.text or "\n" in self.text:
return None
if len(previous.text) + len(self.text) > MAX_COALESCED_RUN:
return None
return InsertCommand(previous.position, previous.text + self.text, previous.before, self.after)
@dataclass(slots=True)
class DeleteCommand(Command):
position: int
length: int
before: Cursor
after: Cursor
removed: str = ""
def execute(self, target: EditTarget) -> None:
self.removed = target.apply_delete(self.position, self.length)
target.set_cursor(self.after)
def undo(self, target: EditTarget) -> None:
target.apply_insert(self.position, self.removed)
target.set_cursor(self.before)
def describe(self) -> str:
return f"delete {self.length} at {self.position}"
def coalesce_with(self, previous: Command) -> Command | None:
"""Held-down backspace is one undo step, not thirty."""
if not isinstance(previous, DeleteCommand) or self.length != 1 or previous.length > MAX_COALESCED_RUN:
return None
if self.position + self.length != previous.position:
return None
merged = DeleteCommand(
self.position, self.length + previous.length, previous.before, self.after, self.removed + previous.removed
)
return merged
@dataclass(slots=True)
class ReplaceCommand(Command):
position: int
old_length: int
new_text: str
before: Cursor
after: Cursor
removed: str = ""
def execute(self, target: EditTarget) -> None:
self.removed = target.apply_delete(self.position, self.old_length)
target.apply_insert(self.position, self.new_text)
target.set_cursor(self.after)
def undo(self, target: EditTarget) -> None:
target.apply_delete(self.position, len(self.new_text))
target.apply_insert(self.position, self.removed)
target.set_cursor(self.before)
def describe(self) -> str:
return f"replace {self.old_length} at {self.position} with {self.new_text!r}"
@dataclass(slots=True)
class MacroCommand(Command):
"""Composite: many edits, one undo step.
Paste, type-over-a-selection and replace-all are all macros. That is why
there is no PasteCommand class -- paste is delete plus insert, and inventing
a third class for it would be duplication dressed up as design.
"""
label: str
before: Cursor
after: Cursor
commands: list[Command] = field(default_factory=list)
def execute(self, target: EditTarget) -> None:
for command in self.commands:
command.execute(target)
target.set_cursor(self.after)
def undo(self, target: EditTarget) -> None:
for command in reversed(self.commands):
command.undo(target)
target.set_cursor(self.before)
def describe(self) -> str:
return f"{self.label} ({len(self.commands)} edits)"
The history is three rules and a cap. Notice the shared lock in the constructor — it is passed in by the document.
code/lld/text_editor/commands.py — the two stacks
class CommandHistory:
"""Two stacks, a coalescing window and a cap.
Three rules an interviewer checks for:
1. a new command clears the redo stack -- the future you undid is gone;
2. consecutive keystrokes merge into one entry while they stay adjacent and
arrive inside ``coalesce_window`` seconds of each other;
3. the undo stack is bounded, and the *oldest* entry is dropped, because the
recent past is what a user actually undoes.
"""
def __init__(
self,
capacity: int = 100,
coalesce_window: float = 1.0,
clock: Clock | None = None,
lock: threading.RLock | None = None,
) -> None:
self.capacity = capacity
self.coalesce_window = coalesce_window
self._clock = clock or SystemClock()
# Shared with the document on purpose: the buffer and the stacks must
# move together, so they are guarded by one reentrant lock.
self._lock = lock or threading.RLock()
self._undo: deque[Command] = deque()
self._redo: list[Command] = []
self._last_at: float | None = None
self._can_coalesce = True
self.dropped = 0
def record(self, command: Command) -> None:
with self._lock:
self._redo.clear() # rule 1
now = self._clock.now()
gap = None if self._last_at is None else now - self._last_at
merged = None
if self._can_coalesce and self._undo and gap is not None and gap <= self.coalesce_window:
merged = command.coalesce_with(self._undo[-1]) # rule 2
if merged is not None:
self._undo[-1] = merged
else:
self._undo.append(command)
while len(self._undo) > self.capacity: # rule 3
self._undo.popleft()
self.dropped += 1
self._last_at = now
self._can_coalesce = True
def undo(self, target: EditTarget) -> Command:
with self._lock:
if not self._undo:
raise NothingToUndoError("nothing to undo")
command = self._undo.pop()
command.undo(target)
self._redo.append(command)
self._can_coalesce = False # typing after an undo starts a fresh entry
return command
def redo(self, target: EditTarget) -> Command:
with self._lock:
if not self._redo:
raise NothingToUndoError("nothing to redo")
command = self._redo.pop()
command.execute(target)
self._undo.append(command)
self._can_coalesce = False
return command
def break_coalescing(self) -> None:
"""Called on a cursor move or a save: the next keystroke starts a new entry."""
with self._lock:
self._can_coalesce = False
def depth(self) -> int:
"""Total edits ever applied and still applied."""
with self._lock:
return len(self._undo) + self.dropped
def top(self) -> Command | None:
"""The command an undo would take back -- the document's save marker.
Identity, not a count: after saving, undoing once and typing something
new, the stack is the same *depth* but a different *history*, and a
counter would wrongly report the document as saved.
"""
with self._lock:
return self._undo[-1] if self._undo else None
def can_undo(self) -> bool:
with self._lock:
return bool(self._undo)
def can_redo(self) -> bool:
with self._lock:
return bool(self._redo)
def labels(self) -> list[str]:
with self._lock:
return [command.describe() for command in self._undo]
The document is the EditTarget, the owner of the lock, and the thing that knows its own saved state.
code/lld/text_editor/services.py — the document
class Document:
"""One tab: a buffer, a caret, a style list and its own undo history.
``_lock`` is an ``RLock`` shared with the ``CommandHistory``. That sharing is
the point: applying an edit and pushing it onto the undo stack must be one
atomic step, or a second thread can undo a command whose text is not in the
buffer yet. One reentrant lock also means there is only one lock order, so
the design cannot deadlock against itself.
"""
def __init__(
self,
name: str,
buffer: TextBuffer | None = None,
clock: Clock | None = None,
history_capacity: int = 100,
coalesce_window: float = 1.0,
) -> None:
self.name = name
self._lock = threading.RLock()
self._buffer: TextBuffer = buffer if buffer is not None else GapBuffer()
self._cursor = Cursor(len(self._buffer))
self.history = CommandHistory(history_capacity, coalesce_window, clock or SystemClock(), self._lock)
self._styles: list[StyleRun] = []
self._revision = 0
self._ever_saved = False
self._saved_top: Command | None = None
self._listeners: list[DocumentListener] = []
# --- EditTarget: the only three methods a Command may call -------------------
def apply_insert(self, position: int, text: str) -> None:
with self._lock:
self._buffer.insert(position, text)
self._shift_styles(position, len(text))
self._revision += 1
def apply_delete(self, position: int, length: int) -> str:
with self._lock:
removed = self._buffer.delete(position, length)
self._shift_styles(position, -length)
self._revision += 1
return removed
def set_cursor(self, cursor: Cursor) -> None:
with self._lock:
if not 0 <= cursor.position <= len(self._buffer):
raise OutOfBoundsError(f"cursor {cursor.position} outside 0..{len(self._buffer)}")
self._cursor = cursor
# --- edits ------------------------------------------------------------------
def run(self, command: Command) -> Command:
"""Execute and record atomically, then notify listeners outside the lock."""
with self._lock:
command.execute(self)
self.history.record(command)
self._notify()
return command
def undo(self) -> Command:
with self._lock:
command = self.history.undo(self)
self._notify()
return command
def redo(self) -> Command:
with self._lock:
command = self.history.redo(self)
self._notify()
return command
# --- reads ------------------------------------------------------------------
def text(self) -> str:
with self._lock:
return self._buffer.text()
def slice(self, start: int, end: int) -> str:
with self._lock:
return self._buffer.slice(start, end)
def length(self) -> int:
with self._lock:
return len(self._buffer)
def cursor(self) -> Cursor:
with self._lock:
return self._cursor
def selection(self) -> Selection | None:
with self._lock:
return self._cursor.selection()
def revision(self) -> int:
with self._lock:
return self._revision
def word_count(self) -> int:
return len(self.text().split())
@property
def status(self) -> DocumentStatus:
"""Undoing back to the command you saved at shows SAVED again.
The marker is the *command object* on top of the undo stack, not its
depth. Save, undo once, then type: the stack is back to the same depth
holding different work, and a depth comparison would call that saved.
"""
with self._lock:
if not self._ever_saved:
return DocumentStatus.NEW if self._revision == 0 else DocumentStatus.MODIFIED
return DocumentStatus.SAVED if self._saved_top is self.history.top() else DocumentStatus.MODIFIED
def mark_saved(self) -> None:
with self._lock:
self._ever_saved = True
self._saved_top = self.history.top()
self.history.break_coalescing() # so the marker cannot be coalesced away
# --- styles and observers ----------------------------------------------------
def apply_style(self, start: int, end: int, style: Style) -> None:
with self._lock:
self._styles.append(StyleRun(start, end, style))
def styles_at(self, position: int) -> list[Style]:
with self._lock:
return [run.style for run in self._styles if run.start <= position < run.end]
def style_runs(self) -> list[StyleRun]:
with self._lock:
return list(self._styles)
def subscribe(self, listener: DocumentListener) -> None:
with self._lock:
self._listeners.append(listener)
def _shift_styles(self, position: int, delta: int) -> None:
shifted: list[StyleRun] = []
for run in self._styles:
start = run.start + delta if run.start >= position else run.start
end = run.end + delta if run.end > position else run.end
if end > start:
shifted.append(StyleRun(max(0, start), max(0, end), run.style))
self._styles = shifted
def _notify(self) -> None:
with self._lock:
listeners, name, revision = list(self._listeners), self.name, self._revision
for listener in listeners: # outside the lock: a slow view never blocks typing
listener.on_document_changed(name, revision)
The editor turns intent into commands. Every method here is short, and that is the sign the command layer is carrying its weight.
code/lld/text_editor/services.py — the editor facade
class Editor:
"""The facade a keyboard talks to. Every mutation becomes exactly one Command."""
def __init__(
self,
storage: FileStorage | None = None,
clipboard: Clipboard | None = None,
clock: Clock | None = None,
history_capacity: int = 100,
coalesce_window: float = 1.0,
buffer_factory: Callable[[str], TextBuffer] | None = None,
) -> None:
self.storage: FileStorage = storage or InMemoryStorage()
self.clipboard = clipboard or Clipboard()
self.styles = StyleRegistry()
self._clock = clock or SystemClock()
self._history_capacity = history_capacity
self._coalesce_window = coalesce_window
self._buffer_factory: Callable[[str], TextBuffer] = buffer_factory or GapBuffer
self._lock = threading.Lock() # guards the tab registry only
self._tabs: dict[str, Document] = {}
self._active: str | None = None
# --- tabs --------------------------------------------------------------------
def new_tab(self, name: str, text: str = "") -> Document:
with self._lock:
if name in self._tabs:
raise DocumentExistsError(f"tab {name!r} is already open")
document = Document(
name, self._buffer_factory(text), self._clock, self._history_capacity, self._coalesce_window
)
self._tabs[name] = document
self._active = name
return document
def open_tab(self, name: str) -> Document:
"""Load from storage into a new tab; the loaded text is not an undoable edit."""
document = self.new_tab(name, self.storage.load(name))
document.mark_saved()
return document
def close_tab(self, name: str) -> None:
with self._lock:
if name not in self._tabs:
raise DocumentNotFoundError(f"no open tab named {name!r}")
del self._tabs[name]
self._active = next(iter(self._tabs), None)
def switch_to(self, name: str) -> Document:
with self._lock:
if name not in self._tabs:
raise DocumentNotFoundError(f"no open tab named {name!r}")
self._active = name
return self._tabs[name]
def tabs(self) -> list[str]:
with self._lock:
return sorted(self._tabs)
@property
def active(self) -> Document:
with self._lock:
if self._active is None:
raise DocumentNotFoundError("no open tabs")
return self._tabs[self._active]
# --- editing -----------------------------------------------------------------
def type_text(self, text: str) -> Command:
"""Typing over a selection is a macro: delete the range, then insert."""
document = self.active
before = document.cursor()
selection = before.selection()
if selection is None:
command: Command = InsertCommand(before.position, text, before, Cursor(before.position + len(text)))
else:
after = Cursor(selection.start + len(text))
command = MacroCommand(
"type over selection",
before,
after,
[
DeleteCommand(selection.start, selection.length, before, Cursor(selection.start)),
InsertCommand(selection.start, text, Cursor(selection.start), after),
],
)
return document.run(command)
def backspace(self) -> Command:
document = self.active
before = document.cursor()
selection = before.selection()
if selection is not None:
return document.run(
DeleteCommand(selection.start, selection.length, before, Cursor(selection.start))
)
if before.position == 0:
raise OutOfBoundsError("nothing to delete before position 0")
return document.run(DeleteCommand(before.position - 1, 1, before, Cursor(before.position - 1)))
def delete_forward(self) -> Command:
document = self.active
before = document.cursor()
if before.position >= document.length():
raise OutOfBoundsError("nothing to delete after the end")
return document.run(DeleteCommand(before.position, 1, before, before.collapsed()))
def move_to(self, position: int, extend: bool = False) -> Cursor:
"""A caret move ends the current typing run, so undo stops at word boundaries."""
document = self.active
cursor = document.cursor().moved_to(position, extend)
document.set_cursor(cursor)
document.history.break_coalescing()
return cursor
def select(self, start: int, end: int) -> Selection:
document = self.active
document.set_cursor(Cursor(end, start))
document.history.break_coalescing()
return Selection(min(start, end), max(start, end))
def select_all(self) -> Selection:
return self.select(0, self.active.length())
# --- clipboard ---------------------------------------------------------------
def copy(self) -> str:
document = self.active
selection = document.selection()
text = "" if selection is None else document.slice(selection.start, selection.end)
self.clipboard.copy(text)
return text
def cut(self) -> str:
text = self.copy()
if text:
self.backspace()
return text
def paste(self) -> Command:
return self.type_text(self.clipboard.paste())
# --- history -----------------------------------------------------------------
def undo(self) -> Command:
return self.active.undo()
def redo(self) -> Command:
return self.active.redo()
# --- search, storage, stats ---------------------------------------------------
def find(self, needle: str) -> list[int]:
if not needle:
raise OutOfBoundsError("cannot search for an empty string")
text, hits, start = self.active.text(), [], 0
while (index := text.find(needle, start)) != -1:
hits.append(index)
start = index + 1 # overlapping matches count
return hits
def replace_all(self, needle: str, replacement: str) -> Command | None:
"""One macro, one undo step -- and applied right to left so offsets stay valid."""
hits: list[int] = []
for index in self.find(needle):
# find() reports overlapping matches, which is right for a search box
# and wrong here: replacing both halves of "aaaa" would corrupt each
# other. Keep the leftmost of every overlapping group.
if not hits or index >= hits[-1] + len(needle):
hits.append(index)
if not hits:
return None
document = self.active
before = document.cursor()
after = Cursor(hits[0] + len(replacement))
# Each inner edit carries a caret anchored at its own site. Handing them
# all the document-wide `before` breaks undo: mid-macro the text is
# shorter than it started, so restoring a caret past the end raises and
# leaves the document half-undone. Only the macro sets the real carets.
edits: list[Command] = [
ReplaceCommand(
index, len(needle), replacement, Cursor(index), Cursor(index + len(replacement))
)
for index in reversed(hits)
]
return document.run(MacroCommand(f"replace {needle!r}", before, after, edits))
def save(self, name: str | None = None) -> str:
document = self.active
target = name or document.name
self.storage.save(target, document.text())
document.mark_saved()
return target
def word_count(self) -> int:
return self.active.word_count()
The clipboard and the style registry are small, but the registry is where the Flyweight actually lives:
code/lld/text_editor/support.py — the flyweight factory
class StyleRegistry:
"""Flyweight factory: one shared ``Style`` object per distinct combination.
A million bold characters cost one Style plus one run, not a million objects.
"""
def __init__(self) -> None:
self._lock = threading.Lock()
self._styles: dict[tuple[bool, bool, bool, str], Style] = {}
def get(
self, bold: bool = False, italic: bool = False, underline: bool = False, colour: str = "default"
) -> Style:
key = (bold, italic, underline, colour)
with self._lock:
style = self._styles.get(key)
if style is None:
style = Style(*key)
self._styles[key] = style
return style
def __len__(self) -> int:
with self._lock:
return len(self._styles)
Running python -m lld.text_editor.demo walks coalescing, undo, redo invalidation, macros, flyweights and the history cap:
new tab: notes.txt status=new
typed 'hello' -> 'hello' as 1 undo entry
after a 3 s pause: ["insert 'hello' at 0", "insert ' world' at 5"]
undo -> 'hello' (redo available: True)
redo -> 'hello world'
cut 'hello' -> ' world', cursor at 0
paste at the end -> ' worldhello'
replace-all -> ' worLdheLLo' as one entry: replace 'l' (3 edits)
one undo took all three edits back -> ' worldhello'
a new command dropped the redo stack: can_redo=False
two style runs share one flyweight: True, registry holds 1
saved: status=saved, words=1, status bar: notes.txt (rev 23, 13 redraws)
cap 5: 13 edits recorded -> 5 kept, 8 dropped
undo past the cap: nothing to undo; the oldest edits are unreachable -> ' worldhello!abc'
Concurrency and edge cases¶
Which lock protects what. Two, and the interesting one is that there are not three:
Document._lockis anRLockthat guards the buffer, the caret, the style runs, the revision counter and the command history — because it is the same lock object, passed intoCommandHistory. If the history had its own lock you would have two acquisition orders (runtakes document then history;undotakes history then document) and a textbook deadlock. Sharing one reentrant lock means there is one order, so there is no cycle to close.Editor._lockguards the tab registry only. Opening a tab never blocks typing in another.
The race it prevents: run must execute the command and push it in one critical section. Split them and a second thread can call undo, pop a command whose text is not in the buffer yet, and delete characters that belong to someone else's edit.
Listener notification happens outside the lock, so a slow view cannot block a typist. The consequence is stated, not hidden: a listener may observe revision n+1 after the document has already reached n+2.
Coalescing has four guards and each has a reason: adjacency (otherwise a click-and-type merges with an edit somewhere else), no newline (Enter is a natural undo boundary), a length cap of 40 characters (so one undo cannot swallow a paragraph) and a time window from the injected clock. A caret move, a save, an undo or a redo all call break_coalescing, so the next keystroke starts a fresh entry.
Redo invalidation happens in record, before anything else, and it is unconditional — including when the new command coalesces.
History memory. The cap is on entries, but the cost is bytes: DeleteCommand holds the text it removed, so one "select all, delete" on a large document pins that document in the undo stack. A hundred 1 KB entries is 100 KB and irrelevant; one 10 MB deletion is not. In production you cap on retained bytes as well as on count, and you say so.
Buffer choice, honestly. Sequential memory reads run at roughly 1 MB per 3 µs, so re-copying a 10 MB document on every keystroke costs about 30 µs — invisible. SimpleBuffer is genuinely fine for ordinary files. The gap buffer matters when the document is much larger, when the allocator churn per keystroke starts to matter, or when you want insert to be O(1) regardless of size. A piece table is the other real answer: it never moves text, makes undo nearly free because every edit is an append, and is the natural base for collaborative editing where several carets touch the document at once.
Edge cases handled: backspace at position 0 and delete past the end raise OutOfBoundsError; an empty search string is rejected; overlapping matches are all found (find("aa") in "aaa" returns [0, 1]) but replace-all keeps only the leftmost of each overlapping group, because replacing both halves of "aaaa" would corrupt each other; replace-all applies right to left so earlier offsets stay valid, and each of its inner edits carries a caret at its own site so a shrinking replacement cannot leave the caret past the end mid-undo; style runs shift when text is inserted before them and disappear when their range is deleted; paste with an empty clipboard raises; each tab has its own history.
Common mistake
Storing only the text in each command and rebuilding the caret from the edit position. It works for typing and then breaks the first time someone undoes a paste over a selection — the selection does not come back, and the next keystroke lands in the wrong place. Store before and after cursors on every command from the start; it costs two integers and it is the difference between an editor that feels right and one that does not.
Extensibility and follow-ups¶
- A new operation (indent, uppercase, sort lines) is one
Commandsubclass withexecuteandundo. It joins the same stacks and needs no change anywhere else. If it is naturally several edits, build aMacroCommandinstead and get one undo step for free. - Autosave: a listener that watches
on_document_changedand callseditor.save()when the revision has moved and the injected clock says enough time has passed. No new mechanism, because saving already marks the top command. - Macros ("record what I do and replay it"): the commands are already objects, so recording is appending them to a list and replaying is
MacroCommand(recorded).execute(other_document). This is the pay-off you should name when asked why Command over Memento. - Syntax highlighting: another observer that re-lexes the changed range and emits
StyleRuns through the same Flyweight registry. - Bounded history by bytes: give
Commandaretained_bytes()and haveCommandHistorydrop from the front until both the count and the byte budget fit. - Collaborative editing is the hand-off. Once two people edit at once, "undo my last command" stops meaning "reverse the last edit", positions must be transformed against concurrent edits, and you need operational transformation or a CRDT — see Design Google Docs. A piece table becomes the better buffer at that point.
Interview tip
Say "Command, not Memento" in the first two minutes, and give the reason in memory terms. Then, before you are asked, name coalescing and redo invalidation as the two behaviours that make undo feel correct. Interviewers grade this problem on whether you have used an editor thoughtfully, not on whether you can push and pop.
Tests¶
tests/test_text_editor.py has 23 cases. The three worth walking through are coalescing, redo invalidation with caret restoration, and concurrency.
The coalescing test asserts all three boundaries in one pass — the window, the caret move, and the resulting undo granularity:
code/lld/text_editor/tests/test_text_editor.py — coalescing
def test_consecutive_typing_coalesces_but_a_pause_or_a_move_does_not(editor: Editor, clock: FakeClock) -> None:
type_all(editor, clock, "hello") # five keystrokes, 0.1 s apart
document = editor.active
assert document.text() == "hello" and len(document.history.labels()) == 1
clock.advance(3) # longer than the coalescing window
editor.type_text("!")
assert len(document.history.labels()) == 2
editor.move_to(0) # a caret move always ends the run
editor.type_text("A")
assert len(document.history.labels()) == 3
assert document.text() == "Ahello!"
editor.undo()
assert document.text() == "hello!" # one keystroke, one undo
editor.undo()
assert document.text() == "hello" # the pause split the run here
editor.undo()
assert document.text() == "" # all five coalesced keystrokes at once
The redo test is the one that catches shallow implementations: after undoing a type-over-a-selection, the selection must be back, and a new command must destroy the redo stack.
code/lld/text_editor/tests/test_text_editor.py — redo invalidation
def test_a_new_command_invalidates_the_redo_stack_and_undo_restores_the_selection(
editor: Editor, clock: FakeClock
) -> None:
document = editor.active
type_all(editor, clock, "hello")
clock.advance(3)
editor.select(1, 4) # anchor 1, caret 4 -> "ell" selected
editor.type_text("EY") # typing over a selection is one macro
assert document.text() == "hEYo" and isinstance(document.history.labels(), list)
editor.undo()
assert document.text() == "hello"
assert document.cursor() == Cursor(4, 1) # the selection came back, not just the text
assert document.history.can_redo() is True
editor.type_text("?") # a new command after an undo
assert document.history.can_redo() is False
with pytest.raises(NothingToUndoError):
editor.redo()
The concurrency test runs eight threads typing 50 characters each into one document and asserts the two invariants the shared lock exists for: 400 characters with none lost, and a full undo returning the document to empty.
code/lld/text_editor/tests/test_text_editor.py — concurrency
def test_concurrent_typing_loses_no_character(clock: FakeClock) -> None:
editor = Editor(clock=clock, history_capacity=1000, coalesce_window=1.0)
document = editor.new_tab("shared.txt")
def hammer(worker: int) -> None:
for _ in range(50):
editor.type_text(chr(ord("a") + worker))
with ThreadPoolExecutor(max_workers=8) as pool:
list(pool.map(hammer, range(8)))
text = document.text()
assert len(text) == 400 # buffer and history move under one lock: no lost update
for worker in range(8):
assert text.count(chr(ord("a") + worker)) == 50
labels = document.history.labels()
assert 0 < len(labels) <= 400 # adjacent keystrokes coalesced, however they interleaved
assert all(len(label) <= len("insert '' at 400") + 40 for label in labels) # runs stay bounded
while document.history.can_undo():
editor.undo()
assert document.text() == "" # every command undid exactly what it did
The rest cover: six invalid operations through parametrize; the NEW → MODIFIED → SAVED walk including undoing back to the saved point, and a different edit at the same stack depth correctly reporting MODIFIED; the history cap dropping the oldest three of six edits; cut and paste as separate undo steps; replace-all as one macro with overlapping find, undoing cleanly when the replacement is shorter than the needle, and skipping overlapping matches; independent per-tab histories; style flyweights shared and shifted by an insert before them; the status bar counting revisions; both buffer strategies passing the identical assertions via parametrize; a gap buffer growing past its initial gap with the caret jumping around; and a bare Document used without an Editor. Run them with uv run pytest code/lld/text_editor -q.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0–5 | Clarify | Command or Memento? Is a burst of typing one undo? Does undo restore the selection? What happens to redo? Out of scope: rendering, collaboration, regex. |
| 5–10 | Entities | Nouns: Editor, Document, Cursor, Selection, Command, CommandHistory, Clipboard, Style. Say "Command, not Memento" here with the memory reason. |
| 10–17 | Class diagram | Document and its buffer on one side, the command tree and the two stacks on the other, joined by the EditTarget protocol. |
| 17–34 | Code | Cursor → Command.execute/undo → InsertCommand.coalesce_with → CommandHistory.record (clear redo, merge, cap) → Document.run under the lock → Editor.type_text with the selection macro. |
| 34–40 | Buffers and concurrency | Gap buffer versus piece table with the copy-cost arithmetic; the one shared RLock and the deadlock it avoids; the byte-budget problem in the history. |
| 40–45 | Extensions | A new command class, macros as recorded commands, autosave as an observer, and collaboration as the hand-off. |
Related¶
- Command — the pattern the whole undo stack is built on
- Memento — the alternative, and why it loses on memory here
- Composite —
MacroCommandand one-step replace-all - Flyweight — shared
Styleobjects behind the registry - Observer — views redrawing on a revision change
- Design Google Docs — what changes when two people type at once