Tardis

Undo/redo (aka history aka time travel) is a fun problem.

After building a few design tools, which make heavy use of edit histories, I decided to build my own solution. I call it Tardis.

It borrows its name from Doctor Who - a character that can travel through time and can take any form. That’s the whole pitch, really: undo/redo for anything (that is serializable).

there are two ways to time travel

The naive approach is to just

1. copy your entire state on every mutation
2. push it onto a stack
3. pop off the stack on undo

This is easy to implement, but enormously wasteful.

It’s better to diff state changes, and serialize the mutation itself. This is more efficient, but harder to implement, because you have to know how to revert every change.

Tardis tries to make reversions easier to reason about.

json paths

Tardis imagines every object as a set of addressable content. Every field in your state model can be singularly identified by a path from the root of your state object.

Given the following object:

myObj = {
  items: [
    { id: "a", label: "hello" },
    { id: "b", label: "world" },
  ],
};

To retrieve the value “world”, you could theoretically identify it with a series of path identifiers:

["myObj", "items", 1, "label"];

WHen you specify all state changes with these addresses, and are as granular as possible, Tardis can easily derive the inverse of any mutation.

api

To begin, you instantiate a new state model with the Tardis constructor:

tardis = new Tardis({
  items: [{ label: "hello" }],
});

To perform a mutation, you give Tardis three things: the operation (insert, update, or delete), the path to the exact spot you want to change, and the data for the change itself.

tardis.do("insert", ["items", 1], { label: "world" });

This gives you a very easy-to-travel history:

tardis.undo();
tardis.redo();

how unwinding works

Like database migrations, every operation produces a record with two halves: an up and a down.

• up does/redoes the change
• down undoes the change

The beautiful thing is that undo and redo are expressed in the exact same vocabulary. They’re just commands pointing in opposite directions.

The inverse of an insert is a delete at the same path. The inverse of a delete is an insert carrying the data that was removed. And an update is its own inverse - it just carries the original value so it can be swapped back.

// inserting produces:
up: {
  type: "insert", path, data;
}
down: {
  type: "delete", path;
}

So undo isn’t some separate, bespoke unwinding routine. It’s the same machinery running the down command instead of the up command. Once you see it that way, the whole thing collapses into something really small - the actual library is about 330 lines with zero runtime dependencies.

The efficiency win comes from the fact that mutations happen in place. Tardis walks the path down to the parent of your target and mutates the leaf directly. The only thing it ever clones is the single value being changed, so it can hand it back to you on undo.

prior art

While building this, I kept wondering whether anyone had thought of it before, or whether I was off in the weeds on my own. It turns out I’d basically reinvented JSON Patch - an actual proposal (RFC 6902) that the IETF published back in 2014. A JSON Patch is a list of operations, each with an op and a path, so my tardis.do("insert", ["items", 1], data) is almost exactly their { "op": "add", "path": "/items/1", "value": ... }. My insert / delete / update even line up one-to-one with their add / remove / replace.

Finding this out felt pretty cool. Landing on the same shape a couple of spec authors arrived at a decade earlier is a pretty good sign you’re not completely off track.

The one thing JSON Patch doesn’t do is reverse itself. A patch only describes the forward change. That reversibility is the part I actually needed, hence this library.

try it yourself

It’s up on Github, but I haven’t published it to NPM.

Feel free to fork it. Cheers.