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