Simple undo in JavaScript with Immutable.js

The application that I’ve been working on for Mapbox - an editor for GL - is the third place I’ve needed to implement undo & redo. It may appear simple, but managing history is a very particular challenge. I learned this current technique from John Firebaugh. Modern JavaScript makes it simpler, but the core insight is entirely thanks to John.

The principles are:

• Data is immutable. It is never mutated in-place.
• Changes to data are encapsulated into operations that take a previous version and return a new one.
• History is represented as a list of states, with past on one end, the present on the other, and an index that can back up into ‘undo states’.
• Modifying data causes any future states to be thrown away.

Objects & Arrays are mutable

JavaScript arrays & objects are mutable data. If you create an object, reference it as a different variable, and modify it, both references point to a changed value.

var myself = { name: "Tom" };
var someoneElse = myself;
myself.name = "Thomas";
// both myself & someoneElse are now equal to { name: 'Thomas' }

Mutability applies to arrays too: common array operations like .sort(), .push(), and .pop() all change arrays in place.

var numbers = [3, 2, 1];
var sorted = numbers.sort();
// both numbers & sorted are equal to [1, 2, 3]
// because calling .sort() sorts the array in-place

Immutable.js

Luckily, the Immutable.js makes immutable data simple, by providing custom and efficient datastructures for unchanging data.

var myself = Immutable.Map({ name: "Tom" });

Instead of changing myself in-place like I would with vanilla JavaScript, Immutable provides methods that yield new modified objects.

var someoneElse = myself.set("name", "Thomas");

If you’ve dealt with this problem before, you might notice that there’s another way of approaching this problem, by cloning objects:

var myself = { name: "Tom" };
// clone myself, to ensure that changing someoneElse doesn't
// mutate it.
var someoneElse = JSON.parse(JSON.stringify(myself));
myself.name = "Thomas";

Immutable improves upon this hack with a guarantee and an optimization:

• Immutable’s methods like .set() can be more efficient than cloning because they let the new object reference data in the old object: only the changed properties differ. This way you can save memory and performance versus constantly deep-cloning everything.
• It’s nearly impossible to accidentally mutate an Immutable object, and remarkably easy to accidentally forget to clone a normal object. Immutable objects give a strong guarantee that nowhere does anyone mutate data in-place.

Operations are functions that create new versions

An operation takes a version of data and returns a new one.

// person is the data, and height is a property
// we want to change. this function creates a new
// version of person without modifying the old one
function changeHeight(person, height) {
  return person.set("height", height);
}

History is a list with an index

As simple as that: generally the start of the array is the first state, where there’s no ability to go backwards, and the tip of the array is the present.

var historyIndex = 0;
var history = [Immutable.Map({ name: "Tom" })];

Operations append new versions to the list of history

In order to increment historyIndex, push a new version on the stack, and run an operation, we write a helper function like this:

function operation(fn) {
  // eliminate the future
  history = history.slice(0, historyIndex + 1);

  // create a new version by applying an operation to the head
  var newVersion = fn(history[historyIndex]);
  history.push(newVersion);
  historyIndex++;
}

This way operations like changeHeight would be written like this:

function changeHeight(height) {
  operation(function (data) {
    return data.set("height", height);
  });
}

historyIndex decides whether we have undo & redo

Usually you’ll want to disable the undo button when there’s nothing to undo. This is pretty simple to test: If the historyIndex is 0, then we’re at the beginning of time and there’s nothing that could be undone.

var hasUndo = historyIndex !== 0;

The same goes for redo: if we’re at the end of the list, then there’s nothing to redo.

var hasRedo = historyIndex !== history.length - 1;

All together now

You can play with this example by drawing & removing dots, and moving through history with the undo & redo buttons. Toggle to the JavaScript panel to see how it works.

Annotations

Usually you won’t just need to build undo & redo, but also a system that records history in words: this is what we usually call “history annotations”. Along with an operation, you’ll add a little text snippet, like “Drew a circle” or “Changed a color”, and this augments an Undo/Redo interface to make the user aware of the current spot in history.

Luckily this is pretty simple to do: annotations are simply another list that we treat exactly the same as the history list.

function operation(fn, annotation) {
  // eliminate the future
  annotations = annotations.slice(0, historyIndex + 1);
  history = history.slice(0, historyIndex + 1);

  // create a new version by applying an operation to the head
  var newVersion = fn(history[historyIndex]);
  history.push(newVersion);
  annotations.push(annotation);
  historyIndex++;
}

// an operation that adds an annotation
function changeHeight(height) {
  operation(function (data) {
    return data.set("height", height);
  }, "Changed the height");
}