Undo History as Structural Patches: 88 Bytes Instead of 87 Kilobytes

The Studio in Stem Shovel is a multitrack recorder and editor that runs in the browser. Everything the user has built, the tracks, the clips on them, the buses, the markers, the automation lanes, lives in one plain JSON document called the arrangement. Every edit replaces the arrangement with a new one, and undo was, for the Studio's first eighteen days, a hundred-deep stack of whole copies of that document. That design was correct and we would choose it again. This post is about the afternoon we replaced the copies with patches without changing what undo does, how we proved the replacement behaves the same, and the small hash that keeps the autosave from writing the same song twice.

Why Snapshots Were Right the First Time

The engine has a method called #commit(). It is called once before any edit, and it pushed a deep copy of the arrangement onto the undo stack:

#commit() {
	this.#past.push(structuredClone($state.snapshot(this.arrangement)));
	if (this.#past.length > UNDO_DEPTH) this.#past.shift();
	this.#future = [];
	// ...
}

Today there are 69 call sites. Trim, split, ripple delete, a tempo change, a lane edit, a fader move (folded to one step per gesture by a helper that waits 400 ms for the hand to pause): every one of them is one #commit() and then whatever mutation it likes. None of them knows how to undo itself. Undo pops the previous arrangement and hands it to the engine, which treats it like a freshly opened song.

The alternative most people reach for is the command pattern, where each edit is an object with a do and an undo. The plan note from the Studio's first week says why we did not: "immutable snapshots are simpler than a command log at this size and are what revisions are anyway." With what is now 69 edit paths, a command log is 69 inverses, each of which can be subtly wrong, and a wrong inverse does not crash. It quietly corrupts the history so the fourth undo lands somewhere nobody was. A snapshot cannot be wrong. It is the state. Named revisions and autosaves are whole arrangements too, so the undo stack and the save path shared one idea.

The cost was memory, and we deferred it on purpose. A realistic arrangement with eight tracks, five hundred clips, automation points and a bus serializes to about 87 kB. A hundred of those is nearly nine megabytes serialized, more as decoded objects, and more again once every lane holds real points. On a laptop that is nothing. On a phone with a dozen decoded stems already in memory, where a tab that runs out of memory dies with no event at all, it is a cost we did not want to carry into long sessions. It sat on the plan as "operation-based undo" until the rest of the scale work was done.

Keep the Structure, Diff by Identity

Operation-based undo never shipped. What shipped keeps the snapshot semantics exactly and changes only the storage: one whole snapshot on each side of the stack, and every older state kept as a patch from the state after it.

The patch format lives in src/lib/utils/structuralPatch.ts. A patch is itself plain JSON, null when nothing changed, and otherwise one of three shapes:

type ObjectPatch = { t: "o"; k?: { [key: string]: Patch }; d?: string[] };
type ListPatch = {
	t: "a";
	r?: string[];          // removed ids
	o?: string[];          // the survivors' new order, when it changed
	i?: [number, Json][];  // inserted elements, as [index, element]
	c?: { [id: string]: Patch };  // a surviving id's own patch
};
export type Patch = null | { t: "s"; v: Json } | ObjectPatch | ListPatch;

s sets a value whole. o patches an object key by key, with k carrying each changed key's own patch and d listing the keys that went away. a patches an array of objects that each carry a unique string id, which in the arrangement means tracks, clips, markers, buses and sends.

The decision that makes it work is what counts as an id-keyed array:

export function patchBetween(from: Json, to: Json): Patch {
	if (from === to) return null;
	if (Array.isArray(from) && Array.isArray(to)) {
		if (keyedById(from) && keyedById(to)) return listPatch(from, to);
		return sameList(from, to) ? null : { t: "s", v: to };
	}
	if (isObject(from) && isObject(to)) return objectPatch(from, to);
	return { t: "s", v: to };
}

An array whose elements all have unique string ids is diffed by id. Any other array (an automation lane's points, a clip's gain envelope, the tempo changes) is replaced whole when it differs anywhere. We considered diffing those by index and decided against it. A lane edit usually moves or inserts one point, and an index diff of "insert one point in the middle" is a cascade of shifted values that costs more to store than the lane. A clip list is the opposite case: hundreds of clips, each with an identity that survives any reorder, and a move touches exactly one of them. Diff by the identity the data already has, and replace whole where there is none.

The array diff is about thirty lines. It lists the ids that vanished, notes whether the survivors changed order (and if so spells out the new order), records each new element with the index it occupies in the result, and recurses into each survivor whose contents changed:

to.forEach((e, index) => {
	const old = fromById.get(e.id);
	if (!old) {
		i.push([index, e]);
		return;
	}
	const p = patchBetween(old, e);
	if (p === null) return;
	put(c, e.id, p);
	changed = true;
});

Apply runs the same steps in order: filter the removed, reorder if asked, splice the inserts at their indexes, then patch the survivors. The result shares every unchanged subtree with its input, which is why nothing is allowed to mutate what applyPatch returns.

Moving one clip of five hundred by one second produces exactly this, 88 bytes:

{"t":"o","k":{"clips":{"t":"a","c":{"c250":{"t":"o","k":{"start":{"t":"s","v":501}}}}}}}

The arrangement it describes a change to is 87,142 bytes. Removing a clip is 46 bytes. Adding one is 250, because the new clip rides along whole. The test that guards this asserts each of the three stays under five percent of the document; in practice they are a tenth of a percent, a twentieth, and three tenths.

One Whole Snapshot per Side

The stack in src/lib/audio/undoStack.ts has two sides, past and future, and each side is the same small class:

class Side<T extends Json> {
	#head: T | undefined;
	#older: Patch[] = [];

	push(state: T) {
		if (this.#head !== undefined) this.#older.push(patchBetween(state, this.#head));
		this.#head = state;
	}

	pop(): T | undefined {
		const head = this.#head;
		if (head === undefined) return undefined;
		const patch = this.#older.pop();
		this.#head = patch === undefined ? undefined : (applyPatch(head, patch) as T);
		return head;
	}
}

Read push carefully, because the direction of the patch is the whole trick. When a newer state arrives, the previous head is turned into the patch that takes the new head back to it: patchBetween(state, this.#head), from the newer to the older. The newest state on each side always stays whole, because it is the one the next undo returns. Stepping back costs one patch application, which makes the next-older state whole, plus one deep copy of what is handed out, since the stack's documents share subtrees with each other and the engine will mutate what it receives. There is never a replay of the chain from some ancient base, which is the failure mode of a naive patch history: undo number ninety should not cost ninety applications.

The cost moved to push, which now walks two documents to compute a patch instead of cloning one. That walk costs about as much as the clone it replaced, and it happens on commit, hidden under the edit itself.

The engine side of the change is almost nothing. Two arrays became one #history, and the three methods now read:

#commit() {
	this.#history.push($state.snapshot(this.arrangement) as StudioArrangement);
	// ...
}
undo() {
	const prev = this.#history.undo($state.snapshot(this.arrangement) as StudioArrangement);
	if (prev) this.#restoreArrangement(prev);
}

The stack takes ownership of what is pushed in, so the engine passes a fresh snapshot and never touches it again. Trimming to depth is a splice of the oldest patches, safe for the same reason: dropping the oldest patch only drops the ability to reach the oldest state, and the head stays whole. All 69 edit paths are untouched.

Proving It Does the Same Thing

An optimization that changes storage but claims to preserve behavior deserves a test against the thing it replaced, and the old behavior fit in a dozen lines, so we kept it as the oracle. The stack's test file carries a Reference class that is the engine's previous code: whole clones on both sides, a shift beyond the depth, a cleared redo on push. A seeded generator (so a failing seed replays byte for byte) drives both implementations through 200 steps, 55 percent of which are a random edit, 25 percent an undo and 20 percent a redo. The edits insert, remove and move clips, add and delete a gain envelope, change the tempo, and add or remove a markers array entirely, so the diff sees new keys, deleted keys, nested arrays with and without ids, and reorders. After every step the test asserts the two documents are equal and that canUndo, canRedo and the stack length agree. Five seeds run at depth 100, three at depth 5, and two at depth 1, where the trim fires on nearly every push.

The patch module has its own characterization. A roundTrip helper computes the patch, asserts it survives JSON.stringify and JSON.parse unchanged, applies it, checks the result equals the target, and checks the source was not mutated. A realistic arrangement goes through fifteen kinds of edit, each applied alone against the base in both directions and then accumulated, with the whole chain round-tripped at the end. One case covers the only place the id rule degrades: two elements sharing an id fall back to a whole replacement rather than a wrong patch.

None of this is clever. It is the discipline the loudness meter taught us: code that transforms data is only worth trusting next to a fixture that pins what it should produce. Here the fixture was the old implementation.

The Companion: Knowing When Nothing Changed

The autosave has a related problem in miniature. It waits 1,500 ms after the last edit, then sends the arrangement to the server, which appends an unnamed revision and keeps the ten most recent. Two things make that wasteful: a save can fire after a gesture that changed nothing, and a revision that holds the same arrangement as the one before it is a row nobody will ever restore to.

Both ends skip the redundant work, differently. The browser keeps the serialized string of the last arrangement it sent and compares the new one to it with === before any network call. The server cannot compare strings, because the arrangement it stored was rebuilt by schema validation on the way in and may hold its keys in a different order. So the server hashes canonical JSON, with every object's keys sorted, stores the hash on the revision row, and answers unchanged to an autosave whose hash matches the newest revision's, writing nothing.

The hash is deliberately not crypto.subtle. The Web Crypto digest is asynchronous, and it is absent on insecure origins, which means any page served over plain HTTP. A collision here costs exactly one redundant row, so cryptographic strength buys nothing. Two 32-bit FNV-1a lanes with different seeds give 16 hex characters:

function lane(text: string, seed: number): number {
	let h = seed >>> 0;
	for (let i = 0; i < text.length; i++) {
		h ^= text.charCodeAt(i);
		h = Math.imul(h, 0x01000193) >>> 0;
	}
	return h;
}

The same function runs in the browser and on the server, synchronously, with no dependency, and its tests pin the three properties that matter: equal values hash equal, key order does not matter but array order does, and a member set to undefined hashes like a missing one, because that is how JSON.stringify treats it.

What Carries Over to Any Editor

The undo stack knows nothing about music. It takes any JSON value, and the patch module only asks that arrays of things with identity carry a string id. The lessons travel the same way.

Start with whole snapshots. For a document that is one JSON value, snapshot undo is correct by construction, every edit path stays ignorant of undo, and it is what your save path wants anyway. The command pattern earns its place when edits must be transmitted or merged, which is a collaboration problem rather than an undo problem.

When the copies get expensive, change the storage and keep the semantics. Hold the newest state whole on each side so a step costs one patch, and diff by the identity the data already has: objects by key, keyed arrays by id, everything else whole. Index diffs on unkeyed arrays mostly store more than they save.

And keep the simple version as the oracle. The old dozen lines of undo became the reference in the new test, and a seeded random walk compared them step by step. That is a few hours of work, and it is the difference between an optimization and a hope. The patch stack went into the Studio in the same commit as the test that proves it matches, and a session with hundreds of clips now holds one copy of the song per side plus its edits, instead of a hundred copies of the song.