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:

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:

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