Build an in-memory record database — think a table of users, each keyed by an id — that supports undo and redo the way a data grid does: a burst of edits is one Ctrl+Z step, not one per cell. The user pastes ten rows, retypes a name, deletes a row; that is many small mutations, but a single undo should roll back the whole burst. Your database keeps two layers: a draft that buffers uncommitted mutations, and a stack of committed checkpoints that undo and redo navigate between. Mutations land in the draft; a commit() is the moment you declare "this is one undoable unit" and freeze the whole table as a checkpoint.
class UndoableDatabase {
constructor();
insert(record): id; // stage an insert in the draft; return the id
update(id, patch): void; // shallow-merge patch into the draft copy
delete(id): void; // stage a delete in the draft
get(id): record | undefined; // read the effective record (draft applied)
getAll(): record[]; // read every effective record
commit(): void; // snapshot the draft as ONE checkpoint
undo(): void; // restore the previous committed table
redo(): void; // restore the next committed table
canUndo(): boolean;
canRedo(): boolean;
}insert uses record.id if you supply one, otherwise it assigns an auto-incrementing id; either way it returns the id it used. get/getAll always read the effective state — the committed table with the current draft applied on top — so uncommitted edits are visible immediately.
// Insert + update + delete, ONE commit → a single undo reverts the whole batch.
const db = new UndoableDatabase();
const a = db.insert({ name: 'Ada' });
const b = db.insert({ name: 'Bob' });
db.update(a, { role: 'admin' });
db.delete(b); // all of this lives in the draft, no undo step yet
db.commit(); // the burst becomes ONE checkpoint
db.get(a); // → { id: a, name: 'Ada', role: 'admin' }
db.get(b); // → undefined
db.undo(); // one step reverts insert A, insert B, update, delete
db.getAll(); // → []
db.canUndo(); // → false (back at the empty start)// A commit AFTER an undo invalidates the redo stack.
const db = new UndoableDatabase();
const a = db.insert({ name: 'Ada' }); db.commit();
const b = db.insert({ name: 'Bob' }); db.commit();
db.undo(); // back to just { Ada }; B is redoable
db.canRedo(); // → true
db.insert({ name: 'Carol' });
db.commit(); // diverged: the B branch is discarded
db.canRedo(); // → false
db.get(b); // → undefined (B is gone for good)insert/update/delete calls before a commit collapse into a single undoable step. None of them push a checkpoint on their own — only commit does, and one undo reverts the entire batch.get/getAll always read the draft (the effective current table). undo/redo operate on committed checkpoints: each restores the whole table to the checkpoint it lands on and rebuilds the draft from it. An uncommitted draft is not itself an undo step — commit it first if you want it preserved.undo, committing new work abandons the forward branch you stepped off of. You cannot redo into history you have diverged from.get/getAll, or mutating one after a later commit, must not corrupt stored history.commit does not push a step, so undo never stops on a phantom checkpoint.update is a shallow merge. update(id, { role: 'admin' }) overwrites only the role field and keeps the rest of the record; updating an id that doesn't exist in the draft is a no-op.undo at the oldest checkpoint and redo at the newest are no-ops that leave the table unchanged rather than throwing.id, or persisting history across sessions — those are out of scope.You'll build a small in-memory record database where a whole burst of row edits is a single undoable step — exactly the way Ctrl+Z behaves in a data grid.
Open a spreadsheet and paste a block of rows, retype a name, delete a row, then press Ctrl+Z once. You don't lose just the last keystroke — the whole burst rolls back in one step. The grid decided that everything since your last natural boundary was one undoable unit. That boundary is a commit.
So there are two distinct layers. There's the live, in-progress edit — call it the draft — which insert, update, and delete change immediately but which is not yet undoable. And there's the committed checkpoint: a frozen snapshot of the whole table that the database saved at a boundary, which undo and redo step between. This is a database of records — many rows keyed by id, not a single value — so each checkpoint is a snapshot of the entire table. Your job is to make the split explicit: mutations write the draft, commit freezes it as one checkpoint, and undo/redo walk the list of checkpoints, restoring the whole table each time.
Picture two layers. The bottom layer is the current committed table — a frozen object keyed by id. The top layer is the draft: a working copy of that table that insert/update/delete mutate. Every get/getAll reads the draft (which started life as a copy of the committed table underneath it), so the user always sees their in-progress edits. A commit snapshots the draft down into a new checkpoint.
The committed checkpoints live in an array — the history — with a single integer index pointing at the snapshot you're currently on. undo decrements the index; redo increments it. The snapshots themselves never move or change; only the pointer slides.
That's the entire data model: a history array of table snapshots, an index into it, and a draft table layered on top (plus a small nextId counter for inserts). Every method is a small operation over those fields.
The instinct is to make each mutation the undoable unit — push a snapshot of the table onto history on every insert/update/delete. After all, that's "save the state so I can get back to it," right? And while we're at it, store the draft object directly so we don't pay for a copy.
class UndoableDatabase {
constructor() {
this.history = [{}];
this.index = 0;
this.nextId = 1;
}
insert(record) {
const id = record.id ?? this.nextId++;
const table = this.history[this.index]; // the live committed object
table[id] = { ...record, id }; // BUG 3: mutates the snapshot in place
this.history.push(table); // BUG 1: a checkpoint per mutation
this.index = this.history.length - 1; // BUG 2: never truncates the redo branch
return id;
}
update(id, patch) {
const table = this.history[this.index];
table[id] = { ...table[id], ...patch };
this.history.push(table);
this.index = this.history.length - 1;
}
delete(id) {
const table = this.history[this.index];
delete table[id];
this.history.push(table);
this.index = this.history.length - 1;
}
get(id) { return this.history[this.index][id]; }
getAll() { return Object.values(this.history[this.index]); }
commit() {} // nothing to do — every mutation already snapshots
undo() { if (this.index > 0) this.index--; }
redo() { if (this.index < this.history.length - 1) this.index++; }
canUndo() { return this.index > 0; }
canRedo() { return this.index < this.history.length - 1; }
}This is wrong in three distinct ways, and each one matters.
It undoes per mutation, not per batch. Insert Ada, insert Bob, update Ada, delete Bob — that's four checkpoints. One undo only reverts the delete; you'd have to press undo four times to get back to the empty table. The user pasted those rows as one action and expects one Ctrl+Z to erase the whole burst. We collapsed nothing; we exploded one logical edit into four undo steps. (That's why commit exists in the contract — and here it does nothing.)
It never truncates the redo branch. Every mutation pushes, even right after an undo. Step back two checkpoints, then insert a new row — push adds it to the end of the array, leaving the stale future checkpoints stranded in the middle of history. Now redo walks back into a future you'd diverged away from. Real grids throw that abandoned branch away the moment you make a new edit.
It shares one table object across every checkpoint. Look closely: this.history[this.index] is the same object each time, and table[id] = ... mutates it in place before pushing it again. So history ends up holding the same reference at every index. Every "snapshot" is actually the latest state. undo slides the pointer but history[0] and history[5] are the identical object — the table never changes. The undo does nothing visible.
const db = new UndoableDatabase();
db.insert({ name: 'Ada' });
db.insert({ name: 'Bob' });
db.undo();
db.getAll(); // → still [Ada, Bob] ← BUG 3: undo changed nothingThe fix to the first problem is the draft: let many mutations pile up in a working layer and only snapshot on commit. The fix to the second is to truncate history past the pointer before pushing. The fix to the third is to deep-clone on every snapshot so each checkpoint is an independent value.
class UndoableDatabase {
constructor() {
// The committed history: an array of whole-table snapshots. Each snapshot
// is a plain object keyed by record id. history[index] is the table we are
// currently sitting on.
this.history = [{}];
// Pointer into history. Always a valid index in 0..history.length-1.
this.index = 0;
// The uncommitted working layer: a deep copy of the current committed table
// that insert/update/delete mutate. It IS the effective state, so get and
// getAll read straight from it. commit() snapshots it; undo()/redo() rebuild
// it from the checkpoint they land on.
this.draft = clone(this.history[this.index]);
// Auto-increment id source for inserts that don't supply their own id.
this.nextId = 1;
}
insert(record) {
// Use the caller's id if they supplied one, otherwise mint a fresh one.
const id = record.id != null ? record.id : this.nextId;
// Keep nextId ahead of any explicit numeric id so a later auto-insert can't
// collide with one the caller already placed.
if (typeof id === 'number' && id >= this.nextId) this.nextId = id + 1;
// Stage the insert in the draft only — no checkpoint yet.
this.draft[id] = { ...record, id };
return id;
}
update(id, patch) {
const current = this.draft[id];
if (current === undefined) return; // nothing to merge into
// Shallow-merge the patch over the draft copy; id is pinned so a patch
// can't accidentally rewrite the key it lives under.
this.draft[id] = { ...current, ...patch, id };
}
delete(id) {
// Stage a delete in the draft. Still no checkpoint until commit.
delete this.draft[id];
}
get(id) {
const record = this.draft[id];
// Hand back a deep copy so a caller mutating the result can't reach into
// the draft (and from there into the next commit's snapshot).
return record === undefined ? undefined : clone(record);
}
getAll() {
// Deep-copy every row for the same isolation reason as get().
return Object.values(this.draft).map(clone);
}
commit() {
// No pending changes? Don't push a phantom checkpoint that undo would stop
// on for no visible effect.
if (tablesEqual(this.draft, this.history[this.index])) return;
// A commit after an undo diverges: drop everything past the pointer so we
// can't redo into a branch we've abandoned.
this.history = this.history.slice(0, this.index + 1);
this.history.push(clone(this.draft));
this.index = this.history.length - 1;
}
undo() {
if (this.canUndo()) this.index -= 1;
this._restore();
}
redo() {
if (this.canRedo()) this.index += 1;
this._restore();
}
canUndo() {
return this.index > 0;
}
canRedo() {
return this.index < this.history.length - 1;
}
// Rebuild the draft from the checkpoint the pointer now lands on, so the next
// insert/update/delete batch starts from the restored table.
_restore() {
this.draft = clone(this.history[this.index]);
}
}
// Deep copy so nested values (arrays, objects) are isolated between snapshots
// and between the store and the caller.
function clone(value) {
if (typeof structuredClone === 'function') return structuredClone(value);
return JSON.parse(JSON.stringify(value));
}
// Are two tables structurally identical? Used to detect a no-op commit.
function tablesEqual(a, b) {
const ak = Object.keys(a);
const bk = Object.keys(b);
if (ak.length !== bk.length) return false;
return ak.every((k) => deepEqual(a[k], b[k]));
}
// Structural deep equality for record values.
function deepEqual(a, b) {
if (Object.is(a, b)) return true;
if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null) {
return false;
}
const ak = Object.keys(a);
const bk = Object.keys(b);
if (ak.length !== bk.length) return false;
return ak.every((k) => deepEqual(a[k], b[k]));
}
module.exports = { UndoableDatabase };The shift from the naive version is concentrated in three places. Take each in turn.
Mutations write the draft, not history. This is the batching fix. The draft is a plain object keyed by id that starts as a copy of the current committed table; insert assigns a new key, update shallow-merges over an existing one, delete removes one. None of them push, none touch history, so canUndo() is unaffected. Ten mutations leave ten changes sitting in one draft object, indistinguishable from one big change. History is untouched until commit runs. Note update's shallow merge — { ...current, ...patch, id } keeps every field the patch didn't mention, and re-pins id last so a stray id in the patch can't move the record to a different key.
commit is where a checkpoint is born — and where divergence is handled. Two guards bracket the push. First, tablesEqual(this.draft, this.history[this.index]) short-circuits a no-op commit: if the draft matches the table we're already on, committing would add a phantom step that an undo would later stop on for no visible change, so we skip it. Second, this.history.slice(0, this.index + 1) truncates everything after the pointer before pushing. If you'd undone and then committed fresh work, the abandoned future is sliced off — that's the redo-invalidation fix. After the push, the pointer moves to the new last index.
undo/redo move the pointer and rebuild the draft. They change index (guarded by canUndo/canRedo so the boundaries are safe no-ops) and then call _restore, which resets this.draft to a fresh clone of the now-current checkpoint — so a subsequent mutation batch starts from the restored table, not from stale draft data.
Why everything is cloned. A snapshot must be a value, not a shared reference — that's the third naive bug fixed at the root. If commit stored this.draft directly, the next insert would mutate the very object sitting in history. If get/getAll returned the draft's records directly, a caller doing row.tags.push(x) would edit the draft (and, after a commit, the stored checkpoint) in place. clone — structuredClone where available, falling back to a JSON round-trip — gives each checkpoint and each returned record its own deep copy, so the layers stay isolated all the way down to nested arrays and objects.
Walkthrough 1 — insert + update + delete, one commit, one undo reverts the whole batch. Start from an empty database. Auto-ids: Ada gets 1, Bob gets 2.
new UndoableDatabase()
history = [ {} ] index = 0
draft = {} nextId = 1
insert({name:'Ada'}) id = 1; draft = { 1:{id:1,name:'Ada'} } nextId = 2
insert({name:'Bob'}) id = 2; draft = { 1:{...}, 2:{id:2,name:'Bob'} } nextId = 3
update(1, {role:'admin'})
draft[1] = {id:1, name:'Ada', role:'admin'}
delete(2) draft = { 1:{id:1,name:'Ada',role:'admin'} }
canUndo() -> false <- no checkpoint pushed yet
commit() draft != history[0], nothing past index 0 to slice.
history = [ {}, { 1:{...admin} } ] index = 1
canUndo() -> true
undo() index 1 > 0 -> index = 0
draft = clone(history[0]) = {}
getAll() -> [] get(1) -> undefined
canUndo() -> false
The four mutations produced exactly one checkpoint, so the single undo reverts both inserts, the update, and the delete together. That's the batching contract: the burst collapsed into one undoable unit.
Walkthrough 2 — undo, a divergent commit, and redo being unavailable. Start empty.
insert({name:'Ada'}); commit() // id 1
history = [ {}, { 1:Ada } ] index = 1
insert({name:'Bob'}); commit() // id 2
history = [ {}, { 1:Ada }, { 1:Ada, 2:Bob } ] index = 2
undo() index = 1; draft = clone({ 1:Ada }) = { 1:Ada }
get(2) -> undefined
canRedo() -> true <- redo would restore { 1:Ada, 2:Bob }
insert({name:'Carol'}) draft = { 1:Ada, 3:Carol } (id 3; nextId stays ahead)
commit() draft != history[1]. SLICE first:
history.slice(0, 1+1) = [ {}, { 1:Ada } ] <- {1,2} dropped
push clone(draft):
history = [ {}, { 1:Ada }, { 1:Ada, 3:Carol } ] index = 2
canRedo() -> false <- the Bob branch is gone
redo() index 2 is already the last -> no-op
get(2) -> undefined, get(1) -> { id:1, name:'Ada' }
The slice on the divergent commit is the whole story: stepping back and committing new work permanently discards the forward branch. You can never redo into a history you've edited away from — which is exactly how a grid behaves.
insert/update/delete push a checkpoint, a paste of four rows becomes four undo steps and one Ctrl+Z only removes the last row. Fix: mutations write the draft; only commit pushes a checkpoint. The batch boundary is the commit, not the individual write.canRedo() lies and redo() jumps into an abandoned branch. Fix: history = history.slice(0, index + 1) before pushing, so everything past the pointer is dropped.commit stores this.draft itself (not a deep copy), the next insert mutates the object already sitting in history — every checkpoint silently becomes the latest table, and undo changes nothing visible. The same trap hides in get/getAll: hand back the stored record and the caller's row.tags.push(x) rewrites history. Fix: clone the draft on commit, and clone again on every record handed out. A snapshot must be a value, not a live reference — deep, so nested arrays and objects are isolated too.canUndo is index > 0 (step back only if there's an earlier checkpoint), and canRedo is index < history.length - 1 (step forward only if there's a later one). Writing index >= 0 or index <= length lets the pointer walk off the array and history[index] becomes undefined, which _restore then clones into a broken draft. Fix: guard both moves with the exact boundary checks, and reuse canUndo/canRedo inside undo/redo so there's one source of truth.commit with no staged changes — or right after construction — must not add a checkpoint; otherwise undo stops on phantom steps that don't change what the user sees. Fix: compare the draft to the current checkpoint (a structural, deep compare — a re-inserted-but-identical record is still a no-op) and bail early when they're equal.nextId naively can hand out an id that a still-live record already uses — for example after an undo rewinds the table but you forgot to keep the counter ahead. Fix: only ever move nextId forward (if (id >= this.nextId) this.nextId = id + 1), and let it keep climbing across undos so a fresh insert never reuses a key that's currently occupied. (nextId deliberately isn't part of a snapshot — ids stay globally monotonic, which is what real auto-increment columns do.)undo at index 0 and redo at the last index must be safe no-ops, not crashes or pointer underflow/overflow. Fix: the canUndo()/canRedo() guards leave the index untouched at the ends, and _restore still rebuilds the draft from the (unchanged) current snapshot, so the table stays usable.N: after pushing, if history.length > N, drop the oldest snapshot (history.shift()) and decrement index. The classic "you can only undo 100 steps" behaviour — at the cost of being unable to undo past the window.O(table size) memory per step — brutal for a large table where one commit touched three rows. Instead store the batch of changes per checkpoint ([{ op:'insert', id, record }, { op:'update', id, before, after }, …]) and apply or invert them to move between states. Undo replays the inverse ops; redo replays them forward. Trades CPU on each undo for far less memory — the approach Immer's patches and most production editors use.rollback() that throws the current draft away and rebuilds it from history[index] — an explicit "cancel my uncommitted edits" the way a database ROLLBACK discards an open transaction. Pairs naturally with commit as COMMIT, giving the draft true transaction semantics: nothing is durable until you commit, and you can abandon a half-finished batch.{ history, index } to JSON (the snapshots are already plain objects) and reload it on startup so undo history survives a refresh. For large histories, persist only the diff log from the previous bullet plus periodic full snapshots, and replay on load — the same checkpoint-plus-patches strategy databases use for write-ahead logs.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Build an in-memory record database — think a table of users, each keyed by an id — that supports undo and redo the way a data grid does: a burst of edits is one Ctrl+Z step, not one per cell. The user pastes ten rows, retypes a name, deletes a row; that is many small mutations, but a single undo should roll back the whole burst. Your database keeps two layers: a draft that buffers uncommitted mutations, and a stack of committed checkpoints that undo and redo navigate between. Mutations land in the draft; a commit() is the moment you declare "this is one undoable unit" and freeze the whole table as a checkpoint.
class UndoableDatabase {
constructor();
insert(record): id; // stage an insert in the draft; return the id
update(id, patch): void; // shallow-merge patch into the draft copy
delete(id): void; // stage a delete in the draft
get(id): record | undefined; // read the effective record (draft applied)
getAll(): record[]; // read every effective record
commit(): void; // snapshot the draft as ONE checkpoint
undo(): void; // restore the previous committed table
redo(): void; // restore the next committed table
canUndo(): boolean;
canRedo(): boolean;
}insert uses record.id if you supply one, otherwise it assigns an auto-incrementing id; either way it returns the id it used. get/getAll always read the effective state — the committed table with the current draft applied on top — so uncommitted edits are visible immediately.
// Insert + update + delete, ONE commit → a single undo reverts the whole batch.
const db = new UndoableDatabase();
const a = db.insert({ name: 'Ada' });
const b = db.insert({ name: 'Bob' });
db.update(a, { role: 'admin' });
db.delete(b); // all of this lives in the draft, no undo step yet
db.commit(); // the burst becomes ONE checkpoint
db.get(a); // → { id: a, name: 'Ada', role: 'admin' }
db.get(b); // → undefined
db.undo(); // one step reverts insert A, insert B, update, delete
db.getAll(); // → []
db.canUndo(); // → false (back at the empty start)// A commit AFTER an undo invalidates the redo stack.
const db = new UndoableDatabase();
const a = db.insert({ name: 'Ada' }); db.commit();
const b = db.insert({ name: 'Bob' }); db.commit();
db.undo(); // back to just { Ada }; B is redoable
db.canRedo(); // → true
db.insert({ name: 'Carol' });
db.commit(); // diverged: the B branch is discarded
db.canRedo(); // → false
db.get(b); // → undefined (B is gone for good)insert/update/delete calls before a commit collapse into a single undoable step. None of them push a checkpoint on their own — only commit does, and one undo reverts the entire batch.get/getAll always read the draft (the effective current table). undo/redo operate on committed checkpoints: each restores the whole table to the checkpoint it lands on and rebuilds the draft from it. An uncommitted draft is not itself an undo step — commit it first if you want it preserved.undo, committing new work abandons the forward branch you stepped off of. You cannot redo into history you have diverged from.get/getAll, or mutating one after a later commit, must not corrupt stored history.commit does not push a step, so undo never stops on a phantom checkpoint.update is a shallow merge. update(id, { role: 'admin' }) overwrites only the role field and keeps the rest of the record; updating an id that doesn't exist in the draft is a no-op.undo at the oldest checkpoint and redo at the newest are no-ops that leave the table unchanged rather than throwing.id, or persisting history across sessions — those are out of scope.You'll build a small in-memory record database where a whole burst of row edits is a single undoable step — exactly the way Ctrl+Z behaves in a data grid.
Open a spreadsheet and paste a block of rows, retype a name, delete a row, then press Ctrl+Z once. You don't lose just the last keystroke — the whole burst rolls back in one step. The grid decided that everything since your last natural boundary was one undoable unit. That boundary is a commit.
So there are two distinct layers. There's the live, in-progress edit — call it the draft — which insert, update, and delete change immediately but which is not yet undoable. And there's the committed checkpoint: a frozen snapshot of the whole table that the database saved at a boundary, which undo and redo step between. This is a database of records — many rows keyed by id, not a single value — so each checkpoint is a snapshot of the entire table. Your job is to make the split explicit: mutations write the draft, commit freezes it as one checkpoint, and undo/redo walk the list of checkpoints, restoring the whole table each time.
Picture two layers. The bottom layer is the current committed table — a frozen object keyed by id. The top layer is the draft: a working copy of that table that insert/update/delete mutate. Every get/getAll reads the draft (which started life as a copy of the committed table underneath it), so the user always sees their in-progress edits. A commit snapshots the draft down into a new checkpoint.
The committed checkpoints live in an array — the history — with a single integer index pointing at the snapshot you're currently on. undo decrements the index; redo increments it. The snapshots themselves never move or change; only the pointer slides.
That's the entire data model: a history array of table snapshots, an index into it, and a draft table layered on top (plus a small nextId counter for inserts). Every method is a small operation over those fields.
The instinct is to make each mutation the undoable unit — push a snapshot of the table onto history on every insert/update/delete. After all, that's "save the state so I can get back to it," right? And while we're at it, store the draft object directly so we don't pay for a copy.
class UndoableDatabase {
constructor() {
this.history = [{}];
this.index = 0;
this.nextId = 1;
}
insert(record) {
const id = record.id ?? this.nextId++;
const table = this.history[this.index]; // the live committed object
table[id] = { ...record, id }; // BUG 3: mutates the snapshot in place
this.history.push(table); // BUG 1: a checkpoint per mutation
this.index = this.history.length - 1; // BUG 2: never truncates the redo branch
return id;
}
update(id, patch) {
const table = this.history[this.index];
table[id] = { ...table[id], ...patch };
this.history.push(table);
this.index = this.history.length - 1;
}
delete(id) {
const table = this.history[this.index];
delete table[id];
this.history.push(table);
this.index = this.history.length - 1;
}
get(id) { return this.history[this.index][id]; }
getAll() { return Object.values(this.history[this.index]); }
commit() {} // nothing to do — every mutation already snapshots
undo() { if (this.index > 0) this.index--; }
redo() { if (this.index < this.history.length - 1) this.index++; }
canUndo() { return this.index > 0; }
canRedo() { return this.index < this.history.length - 1; }
}This is wrong in three distinct ways, and each one matters.
It undoes per mutation, not per batch. Insert Ada, insert Bob, update Ada, delete Bob — that's four checkpoints. One undo only reverts the delete; you'd have to press undo four times to get back to the empty table. The user pasted those rows as one action and expects one Ctrl+Z to erase the whole burst. We collapsed nothing; we exploded one logical edit into four undo steps. (That's why commit exists in the contract — and here it does nothing.)
It never truncates the redo branch. Every mutation pushes, even right after an undo. Step back two checkpoints, then insert a new row — push adds it to the end of the array, leaving the stale future checkpoints stranded in the middle of history. Now redo walks back into a future you'd diverged away from. Real grids throw that abandoned branch away the moment you make a new edit.
It shares one table object across every checkpoint. Look closely: this.history[this.index] is the same object each time, and table[id] = ... mutates it in place before pushing it again. So history ends up holding the same reference at every index. Every "snapshot" is actually the latest state. undo slides the pointer but history[0] and history[5] are the identical object — the table never changes. The undo does nothing visible.
const db = new UndoableDatabase();
db.insert({ name: 'Ada' });
db.insert({ name: 'Bob' });
db.undo();
db.getAll(); // → still [Ada, Bob] ← BUG 3: undo changed nothingThe fix to the first problem is the draft: let many mutations pile up in a working layer and only snapshot on commit. The fix to the second is to truncate history past the pointer before pushing. The fix to the third is to deep-clone on every snapshot so each checkpoint is an independent value.
class UndoableDatabase {
constructor() {
// The committed history: an array of whole-table snapshots. Each snapshot
// is a plain object keyed by record id. history[index] is the table we are
// currently sitting on.
this.history = [{}];
// Pointer into history. Always a valid index in 0..history.length-1.
this.index = 0;
// The uncommitted working layer: a deep copy of the current committed table
// that insert/update/delete mutate. It IS the effective state, so get and
// getAll read straight from it. commit() snapshots it; undo()/redo() rebuild
// it from the checkpoint they land on.
this.draft = clone(this.history[this.index]);
// Auto-increment id source for inserts that don't supply their own id.
this.nextId = 1;
}
insert(record) {
// Use the caller's id if they supplied one, otherwise mint a fresh one.
const id = record.id != null ? record.id : this.nextId;
// Keep nextId ahead of any explicit numeric id so a later auto-insert can't
// collide with one the caller already placed.
if (typeof id === 'number' && id >= this.nextId) this.nextId = id + 1;
// Stage the insert in the draft only — no checkpoint yet.
this.draft[id] = { ...record, id };
return id;
}
update(id, patch) {
const current = this.draft[id];
if (current === undefined) return; // nothing to merge into
// Shallow-merge the patch over the draft copy; id is pinned so a patch
// can't accidentally rewrite the key it lives under.
this.draft[id] = { ...current, ...patch, id };
}
delete(id) {
// Stage a delete in the draft. Still no checkpoint until commit.
delete this.draft[id];
}
get(id) {
const record = this.draft[id];
// Hand back a deep copy so a caller mutating the result can't reach into
// the draft (and from there into the next commit's snapshot).
return record === undefined ? undefined : clone(record);
}
getAll() {
// Deep-copy every row for the same isolation reason as get().
return Object.values(this.draft).map(clone);
}
commit() {
// No pending changes? Don't push a phantom checkpoint that undo would stop
// on for no visible effect.
if (tablesEqual(this.draft, this.history[this.index])) return;
// A commit after an undo diverges: drop everything past the pointer so we
// can't redo into a branch we've abandoned.
this.history = this.history.slice(0, this.index + 1);
this.history.push(clone(this.draft));
this.index = this.history.length - 1;
}
undo() {
if (this.canUndo()) this.index -= 1;
this._restore();
}
redo() {
if (this.canRedo()) this.index += 1;
this._restore();
}
canUndo() {
return this.index > 0;
}
canRedo() {
return this.index < this.history.length - 1;
}
// Rebuild the draft from the checkpoint the pointer now lands on, so the next
// insert/update/delete batch starts from the restored table.
_restore() {
this.draft = clone(this.history[this.index]);
}
}
// Deep copy so nested values (arrays, objects) are isolated between snapshots
// and between the store and the caller.
function clone(value) {
if (typeof structuredClone === 'function') return structuredClone(value);
return JSON.parse(JSON.stringify(value));
}
// Are two tables structurally identical? Used to detect a no-op commit.
function tablesEqual(a, b) {
const ak = Object.keys(a);
const bk = Object.keys(b);
if (ak.length !== bk.length) return false;
return ak.every((k) => deepEqual(a[k], b[k]));
}
// Structural deep equality for record values.
function deepEqual(a, b) {
if (Object.is(a, b)) return true;
if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null) {
return false;
}
const ak = Object.keys(a);
const bk = Object.keys(b);
if (ak.length !== bk.length) return false;
return ak.every((k) => deepEqual(a[k], b[k]));
}
module.exports = { UndoableDatabase };The shift from the naive version is concentrated in three places. Take each in turn.
Mutations write the draft, not history. This is the batching fix. The draft is a plain object keyed by id that starts as a copy of the current committed table; insert assigns a new key, update shallow-merges over an existing one, delete removes one. None of them push, none touch history, so canUndo() is unaffected. Ten mutations leave ten changes sitting in one draft object, indistinguishable from one big change. History is untouched until commit runs. Note update's shallow merge — { ...current, ...patch, id } keeps every field the patch didn't mention, and re-pins id last so a stray id in the patch can't move the record to a different key.
commit is where a checkpoint is born — and where divergence is handled. Two guards bracket the push. First, tablesEqual(this.draft, this.history[this.index]) short-circuits a no-op commit: if the draft matches the table we're already on, committing would add a phantom step that an undo would later stop on for no visible change, so we skip it. Second, this.history.slice(0, this.index + 1) truncates everything after the pointer before pushing. If you'd undone and then committed fresh work, the abandoned future is sliced off — that's the redo-invalidation fix. After the push, the pointer moves to the new last index.
undo/redo move the pointer and rebuild the draft. They change index (guarded by canUndo/canRedo so the boundaries are safe no-ops) and then call _restore, which resets this.draft to a fresh clone of the now-current checkpoint — so a subsequent mutation batch starts from the restored table, not from stale draft data.
Why everything is cloned. A snapshot must be a value, not a shared reference — that's the third naive bug fixed at the root. If commit stored this.draft directly, the next insert would mutate the very object sitting in history. If get/getAll returned the draft's records directly, a caller doing row.tags.push(x) would edit the draft (and, after a commit, the stored checkpoint) in place. clone — structuredClone where available, falling back to a JSON round-trip — gives each checkpoint and each returned record its own deep copy, so the layers stay isolated all the way down to nested arrays and objects.
Walkthrough 1 — insert + update + delete, one commit, one undo reverts the whole batch. Start from an empty database. Auto-ids: Ada gets 1, Bob gets 2.
new UndoableDatabase()
history = [ {} ] index = 0
draft = {} nextId = 1
insert({name:'Ada'}) id = 1; draft = { 1:{id:1,name:'Ada'} } nextId = 2
insert({name:'Bob'}) id = 2; draft = { 1:{...}, 2:{id:2,name:'Bob'} } nextId = 3
update(1, {role:'admin'})
draft[1] = {id:1, name:'Ada', role:'admin'}
delete(2) draft = { 1:{id:1,name:'Ada',role:'admin'} }
canUndo() -> false <- no checkpoint pushed yet
commit() draft != history[0], nothing past index 0 to slice.
history = [ {}, { 1:{...admin} } ] index = 1
canUndo() -> true
undo() index 1 > 0 -> index = 0
draft = clone(history[0]) = {}
getAll() -> [] get(1) -> undefined
canUndo() -> false
The four mutations produced exactly one checkpoint, so the single undo reverts both inserts, the update, and the delete together. That's the batching contract: the burst collapsed into one undoable unit.
Walkthrough 2 — undo, a divergent commit, and redo being unavailable. Start empty.
insert({name:'Ada'}); commit() // id 1
history = [ {}, { 1:Ada } ] index = 1
insert({name:'Bob'}); commit() // id 2
history = [ {}, { 1:Ada }, { 1:Ada, 2:Bob } ] index = 2
undo() index = 1; draft = clone({ 1:Ada }) = { 1:Ada }
get(2) -> undefined
canRedo() -> true <- redo would restore { 1:Ada, 2:Bob }
insert({name:'Carol'}) draft = { 1:Ada, 3:Carol } (id 3; nextId stays ahead)
commit() draft != history[1]. SLICE first:
history.slice(0, 1+1) = [ {}, { 1:Ada } ] <- {1,2} dropped
push clone(draft):
history = [ {}, { 1:Ada }, { 1:Ada, 3:Carol } ] index = 2
canRedo() -> false <- the Bob branch is gone
redo() index 2 is already the last -> no-op
get(2) -> undefined, get(1) -> { id:1, name:'Ada' }
The slice on the divergent commit is the whole story: stepping back and committing new work permanently discards the forward branch. You can never redo into a history you've edited away from — which is exactly how a grid behaves.
insert/update/delete push a checkpoint, a paste of four rows becomes four undo steps and one Ctrl+Z only removes the last row. Fix: mutations write the draft; only commit pushes a checkpoint. The batch boundary is the commit, not the individual write.canRedo() lies and redo() jumps into an abandoned branch. Fix: history = history.slice(0, index + 1) before pushing, so everything past the pointer is dropped.commit stores this.draft itself (not a deep copy), the next insert mutates the object already sitting in history — every checkpoint silently becomes the latest table, and undo changes nothing visible. The same trap hides in get/getAll: hand back the stored record and the caller's row.tags.push(x) rewrites history. Fix: clone the draft on commit, and clone again on every record handed out. A snapshot must be a value, not a live reference — deep, so nested arrays and objects are isolated too.canUndo is index > 0 (step back only if there's an earlier checkpoint), and canRedo is index < history.length - 1 (step forward only if there's a later one). Writing index >= 0 or index <= length lets the pointer walk off the array and history[index] becomes undefined, which _restore then clones into a broken draft. Fix: guard both moves with the exact boundary checks, and reuse canUndo/canRedo inside undo/redo so there's one source of truth.commit with no staged changes — or right after construction — must not add a checkpoint; otherwise undo stops on phantom steps that don't change what the user sees. Fix: compare the draft to the current checkpoint (a structural, deep compare — a re-inserted-but-identical record is still a no-op) and bail early when they're equal.nextId naively can hand out an id that a still-live record already uses — for example after an undo rewinds the table but you forgot to keep the counter ahead. Fix: only ever move nextId forward (if (id >= this.nextId) this.nextId = id + 1), and let it keep climbing across undos so a fresh insert never reuses a key that's currently occupied. (nextId deliberately isn't part of a snapshot — ids stay globally monotonic, which is what real auto-increment columns do.)undo at index 0 and redo at the last index must be safe no-ops, not crashes or pointer underflow/overflow. Fix: the canUndo()/canRedo() guards leave the index untouched at the ends, and _restore still rebuilds the draft from the (unchanged) current snapshot, so the table stays usable.N: after pushing, if history.length > N, drop the oldest snapshot (history.shift()) and decrement index. The classic "you can only undo 100 steps" behaviour — at the cost of being unable to undo past the window.O(table size) memory per step — brutal for a large table where one commit touched three rows. Instead store the batch of changes per checkpoint ([{ op:'insert', id, record }, { op:'update', id, before, after }, …]) and apply or invert them to move between states. Undo replays the inverse ops; redo replays them forward. Trades CPU on each undo for far less memory — the approach Immer's patches and most production editors use.rollback() that throws the current draft away and rebuilds it from history[index] — an explicit "cancel my uncommitted edits" the way a database ROLLBACK discards an open transaction. Pairs naturally with commit as COMMIT, giving the draft true transaction semantics: nothing is durable until you commit, and you can abandon a half-finished batch.{ history, index } to JSON (the snapshots are already plain objects) and reload it on startup so undo history survives a refresh. For large histories, persist only the diff log from the previous bullet plus periodic full snapshots, and replay on load — the same checkpoint-plus-patches strategy databases use for write-ahead logs.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.