Lesson 19 of 31
Design a Text Editor with Undo and Redo (Low-Level Design)
Undo and redo is the standard use of the command pattern: every change to the document is an object that knows how to apply itself and how to reverse itself, and the editor keeps a history of them. This article designs the core of a text editor: a buffer, a cursor, editing operations, an undo stack and a redo stack, and macros that record and replay user actions.
The classic form of the pattern is an interface with execute() and undo() and one class per command. The set of commands in an editor is closed, so this design uses a sealed interface of records instead, and a method apply returns the inverse command as data. That removes a undo() method on every class that must be kept in sync with its execute(). The method used here is described in the LLD interview framework.
Requirements
Functional
- Type text at the cursor, delete backwards and forwards, and move the cursor left, right, to the start of the line, and to the end of the line.
undoreverses the last edit, andredore-applies an undone edit. The cursor returns to where it was.- A new edit after an undo discards the redo history.
- Record a sequence of actions as a macro and replay it at any cursor position. One replay is one undo step.
- Text may contain any Unicode. An edit must never split a character.
Non-functional
- Each history entry stores only what changed, not a copy of the whole document.
- Undo and redo are exact inverses:
redo(undo(state)) == state. - A failing composite operation leaves the document unchanged.
Cursor movement is not an edit and is not undoable, which matches most editors.
Entities and class diagram
classDiagram
class Editor {
-text: StringBuilder
-cursor: int
-undo: Deque~Step~
-redo: Deque~Step~
-recorded: List~Action~
+perform(action)
+performMacro(actions)
+undo() boolean
+redo() boolean
}
class Action {
<<sealed interface>>
Type
Backspace
DeleteForward
Left
Right
Home
End
}
class Command {
<<sealed interface>>
Insert
Delete
Macro
}
class Step {
<<record>>
command: Command
inverse: Command
cursorBefore: int
cursorAfter: int
}
Editor *-- Step : history
Step *-- Command : forward and inverse
Editor ..> Action : resolves into Commands
Command o-- Command : Macro containsTwo sealed interfaces separate two ideas that are often confused. An Action is what the user did, relative to the cursor: "type this", "backspace twice". A Command is a resolved edit with absolute positions: "insert this at index 5". Macros must record actions, because "insert at index 5" replayed somewhere else is wrong, while "type this" replayed at another cursor is right. History must store commands, because undo needs the exact positions and text that were affected.
API
// Editor: one thread owns it.
Editor();
void perform(Action action);
void performMacro(List<Action> actions); // one undo step
boolean undo(); // false when there is nothing to undo
boolean redo(); // false when there is nothing to redo
void startRecording();
List<Action> stopRecording();
String text(); // an immutable copy of the buffer
int cursor();This block is a signature sketch, so the checker skips it. A Java String is a sequence of UTF-16 code units (char values), and positions in this design are indexes into that sequence. A character outside the Basic Multilingual Plane, such as an emoji, takes two char values called a surrogate pair. An index between the two halves is not a valid position: inserting there corrupts the text. The editor computes every position by stepping over whole code points (a code point is one Unicode character), and Command.apply rejects an index inside a pair with an exception. Combining marks and other multi-code-point characters (grapheme clusters) are out of scope and listed under extensions.
undo and redo return boolean because "nothing to undo" is a normal result of a user action, not a failure. Invalid positions throw an unchecked EditException: the editor computes positions itself, so a bad one means a bug in the caller of Command.apply, and there is nothing sensible for an intermediate caller to do except abort. The exception also drives the rollback of a failing macro.
Design decisions
Command as data that returns its inverse. apply(command, buffer) mutates the buffer and returns the command that undoes it. The inverse of Insert(at, text) is Delete(at, len). The inverse of Delete(at, len) is Insert(at, removed), where removed is read from the buffer during apply. The text is captured at apply time, which is why Delete does not store it beforehand. The inverse of a Macro is a macro of the inverses in reverse order. A switch over the sealed Command needs no default, so adding a command type makes the compiler list every place that must handle it.
Store deltas, not snapshots. The alternative is the memento pattern: copy the whole document before each edit. It is simpler and correct, but costs O(document size) per keystroke. Commands cost O(size of the change).
| Approach | History cost per edit | Complexity | Fits when |
|---|---|---|---|
| Snapshot (memento) | Whole document | Trivial | Small documents, or persistent data structures with structural sharing |
| Command with inverse | Size of the change | Each command needs a correct inverse | Large mutable documents |
A step records cursor positions. Reversing the text is not enough. After undo the cursor should be where it was before the edit, which is not necessarily where the edit happened. Each Step keeps cursorBefore and cursorAfter, so undo and redo restore them exactly.
Two stacks. undo pops a step, applies its inverse and pushes it to the redo stack. redo does the reverse. Any new edit clears the redo stack, because the redone future no longer follows from the present. Both stacks are ArrayDeque objects used through push and pop, which work at the head.
Composite commands are atomic. A Macro command applies its parts in order. If a part throws, the parts already applied are reversed and the exception is rethrown, so the document is either fully changed or unchanged. This is the composite pattern: a command that contains commands and is used like one.
Macros record actions, and replay is one undo step. While recording, each successful action is appended to a list. Replaying the list runs each action against the current cursor and then merges the resulting steps into one Step holding a Macro command. A replay that contains only cursor moves adds no step and leaves the redo history alone.
Immutable views of mutable state. The buffer is a StringBuilder that never leaves the editor. text() returns a String, which is an immutable copy, so a caller can keep it across later edits without seeing them change. The cost is O(n) per call. Records in the history (Insert, Delete, Macro) are immutable, and Macro copies its list with List.copyOf.
Character-aware movement. Left(n) and Backspace(n) count characters (code points), not char values. The example shows the index arithmetic that the editor relies on, with a text that mixes a one-unit character, an accented letter, and an emoji.
public class Main {
static boolean insidePair(CharSequence text, int pos) {
return pos > 0 && pos < text.length()
&& Character.isHighSurrogate(text.charAt(pos - 1))
&& Character.isLowSurrogate(text.charAt(pos));
}
/** Index reached by moving n characters left of pos. */
static int back(CharSequence text, int pos, int n) {
int p = pos;
for (int i = 0; i < n && p > 0; i++) {
p--;
if (insidePair(text, p)) {
p--;
}
}
return p;
}
/** Index reached by moving n characters right of pos. */
static int forward(CharSequence text, int pos, int n) {
int p = pos;
for (int i = 0; i < n && p < text.length(); i++) {
p += Character.isHighSurrogate(text.charAt(p)) && insidePair(text, p + 1) ? 2 : 1;
}
return p;
}
public static void main(String[] args) {
String text = "aĆ©šb"; // a, e with acute accent, an emoji (a surrogate pair), b
System.out.println("chars (UTF-16 units): " + text.length() + ", code points: " + text.codePointCount(0, text.length()));
int end = text.length();
for (int n = 0; n <= 4; n++) {
System.out.println(n + " characters left of the end -> index " + back(text, end, n));
}
System.out.println("3 characters right of the start -> index " + forward(text, 0, 3));
System.out.println("moving past the end stops at index " + forward(text, 0, 99));
System.out.println("index 3 is inside a pair: " + insidePair(text, 3) + ", index 2 is: " + insidePair(text, 2));
}
}chars (UTF-16 units): 5, code points: 4
0 characters left of the end -> index 5
1 characters left of the end -> index 4
2 characters left of the end -> index 2
3 characters left of the end -> index 1
4 characters left of the end -> index 0
3 characters right of the start -> index 4
moving past the end stops at index 5
index 3 is inside a pair: true, index 2 is: falseMoving over the accented letter is one unit and over the emoji two, and moving past either end stops. Because the cursor only ever lands on these computed indexes, it is always on a character boundary. Java provides Character.offsetByCodePoints for the same job. The loops above cost O(n) for a move of n characters, while Character.codePointCount over a prefix would cost O(position).
Full implementation
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Objects;
public class Main {
static abstract class EditException extends RuntimeException {
EditException(String message) {
super(message);
}
}
static final class OutOfBounds extends EditException {
OutOfBounds(long at, int length) {
super("position " + at + " is outside 0.." + length);
}
}
static final class NotCharBoundary extends EditException {
NotCharBoundary(int at) {
super("position " + at + " is inside a surrogate pair");
}
}
/** A resolved edit with absolute indexes. */
sealed interface Command {}
record Insert(int at, String text) implements Command {
Insert {
Objects.requireNonNull(text);
}
}
record Delete(int at, int len) implements Command {
Delete {
if (len < 0) {
throw new IllegalArgumentException("len must not be negative");
}
}
}
record Macro(List<Command> parts) implements Command {
Macro {
parts = List.copyOf(parts);
}
}
static void checkPosition(StringBuilder buf, long pos) {
if (pos < 0 || pos > buf.length()) {
throw new OutOfBounds(pos, buf.length());
}
int p = (int) pos;
if (p > 0 && p < buf.length()
&& Character.isHighSurrogate(buf.charAt(p - 1)) && Character.isLowSurrogate(buf.charAt(p))) {
throw new NotCharBoundary(p);
}
}
/** Applies the command and returns the command that reverses it. */
static Command apply(Command command, StringBuilder buf) {
return switch (command) {
case Insert(int at, String text) -> {
checkPosition(buf, at);
buf.insert(at, text);
yield new Delete(at, text.length());
}
case Delete(int at, int len) -> {
checkPosition(buf, at);
checkPosition(buf, (long) at + len);
String removed = buf.substring(at, at + len);
buf.delete(at, at + len);
yield new Insert(at, removed);
}
case Macro(List<Command> parts) -> {
var inverses = new ArrayList<Command>(parts.size());
try {
for (var part : parts) {
inverses.add(apply(part, buf));
}
} catch (EditException e) {
// All or nothing: undo what already succeeded.
for (var inverse : inverses.reversed()) {
apply(inverse, buf);
}
throw e;
}
yield new Macro(inverses.reversed());
}
};
}
/** What the user did, relative to the cursor. */
sealed interface Action {}
record Type(String text) implements Action {
Type {
Objects.requireNonNull(text);
}
}
record Backspace(int n) implements Action {}
record DeleteForward(int n) implements Action {}
record Left(int n) implements Action {}
record Right(int n) implements Action {}
record Home() implements Action {}
record End() implements Action {}
sealed interface Resolved {}
record Edit(Command command, int cursorAfter) implements Resolved {}
record Move(int pos) implements Resolved {}
record Step(Command command, Command inverse, int cursorBefore, int cursorAfter) {}
static boolean insidePair(CharSequence text, int pos) {
return pos > 0 && pos < text.length()
&& Character.isHighSurrogate(text.charAt(pos - 1))
&& Character.isLowSurrogate(text.charAt(pos));
}
static int back(CharSequence text, int pos, int n) {
int p = pos;
for (int i = 0; i < n && p > 0; i++) {
p--;
if (insidePair(text, p)) {
p--;
}
}
return p;
}
static int forward(CharSequence text, int pos, int n) {
int p = pos;
for (int i = 0; i < n && p < text.length(); i++) {
p += Character.isHighSurrogate(text.charAt(p)) && insidePair(text, p + 1) ? 2 : 1;
}
return p;
}
static final class Editor {
private final StringBuilder text = new StringBuilder();
private int cursor; // always a character boundary within text
private final Deque<Step> undo = new ArrayDeque<>();
private Deque<Step> redo = new ArrayDeque<>();
private final List<Action> recorded = new ArrayList<>();
private boolean recording;
String text() {
return text.toString();
}
int cursor() {
return cursor;
}
private Resolved resolve(Action action) {
int pos = cursor;
return switch (action) {
case Type(String s) when !s.isEmpty() -> new Edit(new Insert(pos, s), pos + s.length());
case Type t -> new Move(pos);
case Backspace(int n) -> {
int start = back(text, pos, n);
yield start < pos ? new Edit(new Delete(start, pos - start), start) : new Move(pos);
}
case DeleteForward(int n) -> {
int end = forward(text, pos, n);
yield end > pos ? new Edit(new Delete(pos, end - pos), pos) : new Move(pos);
}
case Left(int n) -> new Move(back(text, pos, n));
case Right(int n) -> new Move(forward(text, pos, n));
case Home h -> new Move(text.lastIndexOf("\n", pos - 1) + 1);
case End e -> {
int newline = text.indexOf("\n", pos);
yield new Move(newline < 0 ? text.length() : newline);
}
};
}
void perform(Action action) {
switch (resolve(action)) {
case Move(int pos) -> cursor = pos;
case Edit(Command command, int cursorAfter) -> {
var inverse = apply(command, text);
undo.push(new Step(command, inverse, cursor, cursorAfter));
redo.clear(); // a new edit abandons the undone future
cursor = cursorAfter;
}
}
if (recording) {
recorded.add(action);
}
}
/** Runs the actions as one undo step. On failure nothing changes. */
void performMacro(List<Action> actions) {
int base = undo.size();
int startCursor = cursor;
var savedRedo = redo;
redo = new ArrayDeque<>();
boolean wasRecording = recording;
recording = false; // do not record the replay itself
try {
actions.forEach(this::perform);
} catch (EditException e) {
while (undo.size() > base) {
apply(undo.pop().inverse(), text);
}
cursor = startCursor;
redo = savedRedo;
throw e;
} finally {
recording = wasRecording;
}
var steps = new ArrayList<Step>(); // newest first
while (undo.size() > base) {
steps.add(undo.pop());
}
if (steps.isEmpty()) {
redo = savedRedo; // only cursor moves: the history is untouched
return;
}
undo.push(new Step(
new Macro(steps.reversed().stream().map(Step::command).toList()),
new Macro(steps.stream().map(Step::inverse).toList()),
startCursor,
cursor));
}
boolean undo() {
var step = undo.poll();
if (step == null) {
return false;
}
apply(step.inverse(), text);
cursor = step.cursorBefore();
redo.push(step);
return true;
}
boolean redo() {
var step = redo.poll();
if (step == null) {
return false;
}
apply(step.command(), text);
cursor = step.cursorAfter();
undo.push(step);
return true;
}
void startRecording() {
recorded.clear();
recording = true;
}
List<Action> stopRecording() {
recording = false;
var result = List.copyOf(recorded);
recorded.clear();
return result;
}
}
/** Quotes the text and escapes newlines and non-ASCII chars, so the output does not depend on the terminal encoding. */
static String quote(String text) {
var sb = new StringBuilder("\"");
for (char c : text.toCharArray()) {
if (c == '\n') {
sb.append("\\n");
} else if (c < 32 || c > 126) {
sb.append("\\u%04x".formatted((int) c));
} else {
sb.append(c);
}
}
return sb.append('"').toString();
}
static void show(String label, Editor e) {
System.out.printf("%-22s %s cursor %d%n", label, quote(e.text()), e.cursor());
}
public static void main(String[] args) {
var e = new Editor();
e.perform(new Type("Hello"));
e.perform(new Type(" world"));
show("typed", e);
e.undo();
show("undo", e);
e.undo();
show("undo", e);
System.out.println("undo again: " + e.undo());
e.redo();
show("redo", e);
e.perform(new Type("!"));
System.out.println("redo after new edit: " + e.redo());
e.perform(new Type("š")); // an emoji: two chars
show("typed an emoji", e);
e.perform(new Backspace(1));
show("backspace 1", e);
e.undo();
show("undo backspace", e);
// Record a macro on a fresh document, then replay it on another line.
e = new Editor();
e.perform(new Type("one\ntwo"));
e.startRecording();
e.perform(new Home());
e.perform(new Type("- "));
var bullet = e.stopRecording();
show("recorded on line two", e);
System.out.println("macro: " + bullet);
e.perform(new Left(3)); // now inside line one
e.performMacro(bullet);
show("replayed on line one", e);
e.undo();
show("one undo", e);
e.redo();
show("redo", e);
}
}typed "Hello world" cursor 11
undo "Hello" cursor 5
undo "" cursor 0
undo again: false
redo "Hello" cursor 5
redo after new edit: false
typed an emoji "Hello!\ud83d\ude00" cursor 8
backspace 1 "Hello!" cursor 6
undo backspace "Hello!\ud83d\ude00" cursor 8
recorded on line two "one\n- two" cursor 6
macro: [Home[], Type[text=- ]]
replayed on line one "- one\n- two" cursor 2
one undo "one\n- two" cursor 3
redo "- one\n- two" cursor 2Follow the two history stacks through the output. Each undo restores both the text and the cursor from the step, and redo puts them back. The edit after the undo empties the redo stack, so the last redo returns false. Backspacing the emoji removes both char values with one step, and undo restores them, because the inverse Insert carries the removed text. The output prints the emoji as its two \u escapes, so the lines do not depend on the terminal encoding. The macro recorded on line two inserts the bullet at the start of whichever line the cursor is on, and undoing the replay removes it in one step even though it consisted of two actions.
Testing the commands
The riskiest logic is apply. Its central property is that applying a command and then its inverse restores the buffer. Testing the commands directly, without an editor, keeps these tests short. The project uses no test library, so each check is a plain assert statement. The checker runs programs with assertions enabled; outside the checker, start the JVM with -ea or the assertions are skipped.
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class Main {
static abstract class EditException extends RuntimeException {
EditException(String message) {
super(message);
}
}
static final class OutOfBounds extends EditException {
OutOfBounds(long at, int length) {
super("position " + at + " is outside 0.." + length);
}
}
static final class NotCharBoundary extends EditException {
NotCharBoundary(int at) {
super("position " + at + " is inside a surrogate pair");
}
}
sealed interface Command {}
record Insert(int at, String text) implements Command {
Insert {
Objects.requireNonNull(text);
}
}
record Delete(int at, int len) implements Command {}
record Macro(List<Command> parts) implements Command {
Macro {
parts = List.copyOf(parts);
}
}
static void checkPosition(StringBuilder buf, long pos) {
if (pos < 0 || pos > buf.length()) {
throw new OutOfBounds(pos, buf.length());
}
int p = (int) pos;
if (p > 0 && p < buf.length()
&& Character.isHighSurrogate(buf.charAt(p - 1)) && Character.isLowSurrogate(buf.charAt(p))) {
throw new NotCharBoundary(p);
}
}
static Command apply(Command command, StringBuilder buf) {
return switch (command) {
case Insert(int at, String text) -> {
checkPosition(buf, at);
buf.insert(at, text);
yield new Delete(at, text.length());
}
case Delete(int at, int len) -> {
checkPosition(buf, at);
checkPosition(buf, (long) at + len);
String removed = buf.substring(at, at + len);
buf.delete(at, at + len);
yield new Insert(at, removed);
}
case Macro(List<Command> parts) -> {
var inverses = new ArrayList<Command>(parts.size());
try {
for (var part : parts) {
inverses.add(apply(part, buf));
}
} catch (EditException e) {
for (var inverse : inverses.reversed()) {
apply(inverse, buf);
}
throw e;
}
yield new Macro(inverses.reversed());
}
};
}
static void inverseRestoresTheBuffer() {
var buf = new StringBuilder("hello");
for (Command cmd : List.of(new Insert(2, "XY"), new Delete(1, 3))) {
String before = buf.toString();
var inverse = apply(cmd, buf);
assert !buf.toString().equals(before);
apply(inverse, buf);
assert buf.toString().equals(before);
}
}
static void macroInverseUndoesAllPartsInReverse() {
var buf = new StringBuilder("ab");
var inverse = apply(new Macro(List.of(new Insert(1, "X"), new Insert(2, "Y"))), buf);
assert buf.toString().equals("aXYb");
apply(inverse, buf);
assert buf.toString().equals("ab");
}
static void failingMacroIsAtomic() {
var buf = new StringBuilder("ab");
try {
apply(new Macro(List.of(new Insert(1, "X"), new Insert(99, "Y"))), buf);
assert false : "expected an exception";
} catch (OutOfBounds expected) {
assert buf.toString().equals("ab");
}
}
static void splittingASurrogatePairIsAnException() {
var buf = new StringBuilder("š");
try {
apply(new Insert(1, "x"), buf);
assert false : "expected an exception";
} catch (NotCharBoundary expected) {
assert buf.toString().equals("š");
}
}
public static void main(String[] args) {
inverseRestoresTheBuffer();
System.out.println("inverse restores the buffer: ok");
macroInverseUndoesAllPartsInReverse();
System.out.println("macro inverse undoes all parts in reverse: ok");
failingMacroIsAtomic();
System.out.println("failing macro is atomic: ok");
splittingASurrogatePairIsAnException();
System.out.println("splitting a surrogate pair is an exception: ok");
}
}inverse restores the buffer: ok
macro inverse undoes all parts in reverse: ok
failing macro is atomic: ok
splitting a surrogate pair is an exception: okEach check prints a line only after its assertions pass. A failed assert throws an AssertionError and ends the program with an error instead.
Extensions
| Follow-up question | Answer |
|---|---|
| Group typed characters into one undo step | Coalesce: if the new command is an Insert that starts where the previous step's insert ended, extend the previous step instead of pushing a new one. Break the group on cursor moves or after a pause. |
| Limit memory used by history | Cap the undo ArrayDeque: when it exceeds a maximum depth, call removeLast to drop the oldest step. |
| Multiple cursors or selections | Actions resolve against a set of cursors, and the resolved edits form one Macro so they undo together. |
| Efficient large buffers | Replace StringBuilder with a rope or a gap buffer. Command and history stay unchanged because they only need insert, delete and positions. |
| Grapheme clusters (an emoji with a skin-tone modifier, a letter with combining marks) | Move by grapheme with java.text.BreakIterator.getCharacterInstance() instead of by code point. |
| Collaborative editing | Commands become operations that are transformed against concurrent operations. The invertible design is the starting point. |
| Save the macro to disk | Action is plain data. Write each record as a line of text, and the recording is a file. |
| Undo of cursor movement | Push moves as steps with a no-op command, or keep a separate cursor history. |
| Mark the document as modified | Track the undo stack size at the last save and compare it with the current size. |
| Observers such as a status bar | Publish a change event after each apply, undo and redo; see event bus and observers. |
Summary
- Undo and redo come from the command pattern: every edit is an object that can be applied and reversed. A closed set of commands is a sealed interface of records, and
applyreturns the inverse as data. - The inverse captures information that only exists at apply time, such as the text a delete removed. That is why
applycomputes it instead of the caller. - Keep two sealed interfaces:
Action(relative to the cursor, what macros record) andCommand(absolute positions, what history stores). - History is two stacks of
Steps. A step holds the command, its inverse and the cursor before and after. A new edit clears the redo stack. - Composite commands are atomic. A macro rolls back the parts that succeeded when a later part fails, and one macro replay is one undo step.
- Java strings are UTF-16. Move and edit by code point so that a surrogate pair is never split. Invalid positions throw an exception.
- Return an immutable
Stringfrom the editor and keep theStringBuilderprivate. - Snapshots are simpler and fine for small documents. Deltas keep the cost of each edit proportional to the change.