Simple undo in JavaScript with Immutable.js

chairs

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

diagram

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');
}

May 18, 2015 @tmcw

Tom MacWright