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

In defense of JSDoc

JSDoc is untrendy and corporate. The documentation that people write in the format can be weak and formulaic. The implementations leave much to be desired, relative to other language-level tooling like babel. For people allergic to documentation authoring, JSDoc feels even more like a chore.

JSDoc is an API documentation standard that is written as code comments that start with /** and are structured by standardized tags like @param or @throws. It's a descendent of JavaDoc, and the cousin of Python docstrings and Ruby's RDoc.

Here's what it looks like:

/**
 * Add one to a number
 * @param {number} input
 * @returns {number} that number plus one
 */

Most JavaScript projects have given up on embedded API documentation. Even the node.js project manages documentation as a series of Markdown files.

I think JavaScript needs JSDoc, and that it is the future of API documentation.

Checklists are writing tools

In elementary school, writing assignments had clear requirements: an introduction, the thesis, and a conclusion. Some teachers had specific paragraph counts with expectations around the content of every paragraph.

Freeform API documentation is the opposite of a checklist, and that is a problem.

JavaScript is a wonderfully flexible and expressive language, but it is not ineffable. Every JavaScript function takes input and returns a value. These two things should be documented, even if the returned value is undefined or there are no required arguments.

Input and output are two fundamental requirements of API documentation, and they are forgotten often. What does domain.run return?

Examples are not API documentation

var addOne = require('add-one');
addOne(1);

Examples are essentially video game speedruns: you watch someone winning the game, and watch the perfect way. It's impressive how much they achieve in so little time, and how they never run into a tough spot or lose points.

But if you're actually playing the game, a map is more useful.

Super Mario Map

The problem with examples is that they inherently avoid pitfalls and typically simplify their task to make the code approachable. But in day-to-day programming, the promise of documentation is to show the whole picture: every possibility, every outcome, every failure.

Failure especially. JSDoc has a wonderful @throws tag that you lets you document corners in the software: under what conditions is what kind of error propagated? Almost no software does this well, despite errors being a large part of their API surface, and having many different forms.

/**
 * @throws Will throw an error if the argument is null.
 */
function bar(x) {}

Markdown is a semantic dead end

You can try to standardize the format of Markdown documentation. I tried to do this with Mapbox.js's DOCUMENTATION.md document that described how to write API.md.

This barely works, and is going nowhere. Markdown is well-suited for narrative text, but within the realm of documentation there simply isn't a real difference between ## and ### that enables any sort of uniformity or real structure. Markdown isn't structured data, much in the way that Wikitext isn't structured data.

JSDoc is structured, and its connection to code is powerful. Tools like Tern.js are able to parse JSDoc comments and provide inline documentation as you type. ESLint has a valid-jsdoc rule that can require the existence of documentation. Documentation generators like my nascent documentationjs project and many others can transform JSDoc comments into Markdown, HTML, and many other formats.

Modular documentation for modular APIs

I started taking JSDoc very seriously in the context of the Turf.js project. Turf is a geospatial analysis system that follows the tiny module philosophy: when you require('turf') really you're including over 50 tiny modules that all do one thing well.

While this is a great approach on a code level, how should it work for documentation? Surely we don't require people to read 50 different README.md files to use a single library.

The solution we decided on was JSDoc: each module is documented with JSDoc, and all of the docs are aggregated into a single API website. But since JSDoc can easily be pushed into other forms, every module also gets a README.md with content autogenerated by doxme.

This is something that wouldn't be possible with API.md or any other semi-standard convention: we're able to document a modular library with modular documentation, so that every part is documented in its own repo, and the user-facing library is documented completely on one page.

The future of JSDoc

I'm working on tools for a second generation of Mapbox's documentation: making it possible to document Mapbox GL JS the same way we do Turf, and making conventions that can be applied across projects. A big part of this is the documentationjs project that aims to build better tooling than the default JSDoc documentation generator, but supporting the same syntax. We're currently in the golden age of JavaScript tooling: browserify and webpack solve the problems of dependencies, babel conquers transpilation, Flow enforces type constraints, and eslint finds errors and style problems. We need tools for documentation that are just as robust and friendly, and that's what documentationjs aims to be.

JavaScript needs to shrug off its reputation of sub-par documentation culture. JSDoc is one strong bet to get there, starting with robust API docs that narrative documentation and tutorials can be built around.

Big 1.0.0

Today the big presentation system that I started in 2011 gets its first version: 1.0.0. The tires have been kicked, and for the crazy presentations that it's made for, big is feature complete.

Lots of people have used big in their presentations: it can be trusted to work. Draft now supports Big presentations, Biggie makes them easy to build with Markdown, the big cookbook documents tips and tricks.

Sergio contributed slide transition timing for lightning talks, Andy added per-slide body classes, Kathleen helped with documentation, Mikeal fixed bugs, Brian added fancy page titles, Calvin added the ability to swipe slides on mobile, and Braulio fixed accented characters.

Big 1.0.0 includes two high-priority changes that I had been putting off for a while: compatibility with older versions of IE & speakers notes. Speakers notes let you write inline notes and display them in the developer console of your browser.