Undo/Redo

Undo.md

Undo/Redo

Undo/Redo is one of those features of an application that you almost always need to have if you are building serious GUI tools for people to do work.

The best way to look at undo/redo is two stacks of operations the user has performed:

• The Undo stack is the "history" of what they've done
• The redo stack is the breadcrumbs back to the initial state before they started undoing

So, as the user does something in the application, we PUSH an action onto the undo stack.

If the user "undos" an action, we POP off the undo stack, do the operation, then we PUSH an action onto the redo stack.

If the user undos multiple times, then does not redo but instead performs a unique action, we consider the redo stack lost. A complicated undo/redo system that needs to preserve these lost operations will probably FORK off here. I believe photoshop does this but it's not necessary for the vast majority of tools as people expect modifications after undo to be lossy.

Stacks

So, we know at the core undo is just a stack we push to as the user does something, and pop from when we want to undo. But how do we represent the action a user has done, so we know how to undo it, or redo it later?

There are two ways to do this:

1. Using closures to call a undo() function or a redo() function for that operation, where all the information needed to undo or redo is in the memory of the closure.
2. Keep a light-weight action representation that has only the minimal amount of information needed to undo/redo.

The reason I mention #1 is that it comes up a lot in Javascript land because closures are so convenient. This might look like this:

function addRectangle(x,y,w,h) {
  var rect = new Rectangle(x,y,w,h);
  rectangles.push(rect);
  
  UndoRedo.push({
   perform: function() {
     rectangles.push(rect);
   },
   revert: function() {
     rectanges.remove(rect);
   }
  });
}

Then the UndoRedo manager calls those perform() and revert() functions which have access to the memory from that function call, so this works. But it uses unnecessary memory for the closure and isn't very elegant.

The second approach is better, and it has a well-known design pattern behind it called the Command Pattern. The basic idea is we store all the data needed to call a function later to achieve a given effect, and only that data.

To clarify, instead of keeping the rectangle in a closure in memory, we just track what we know about it so we can modify it later:

function addRectangle(x,y,w,h) {
  var rect = new Rectangle(x,y,w,h);
  rectangles.push(rect);
  
  UndoRedo.pushAction('addRectangle', [x,y,w,h]);
}

Then if we redo later, the UndoRedo system would then call the operation associated with addRectangle and pass in the data it knows about how to add that rectangle back.

Scripting

Undo/Redo is very simple if done through the Command Pattern. But adding it to your application can be tedious especially since Undo/Redo is often saved until the end.

It makes a lot more sense to think of the operations of your application as a simple script executing system. That means, when the user does something, we never do that operation directly. Instead, we run a script that both handles undo/redo for us, and does the operation.

So, we might create an addRectangle operation that we used above like this:

UndoRedo.registerScript('addRectangle', {
  perform: function(data) {
    rectangles.push(data.x,data.y,data.w,data.h);
  },
  revert: function(data) {
    // this is a bad example because we have no lookup data
    rectangles.remove(data.rectangle);
  }
});

function addRectangle(x,y,w,h) {  
  UndoRedo.exec('addRectangle', [x,y,w,h]);
}

Then, the UndoRedo system handles pushing to the undo stack whenever we do an exec, and also handling redos. This is a much easier way to build your application because it benefits from undo/redo on day one.

Thanks~

I wrote this a long time ago, wow! Since then I've used this successfully, but one alternative to this is to just keep a copy of state and re-set it on each interaction (might do this with a redux undo/redo lib, for example). One downside to that is keeping references the same. I didn't like this solution for my use case because the tree needed to keep references per API contract (think DOM) instead of re-creating elements on each state change.

Thanks for the info, it's the clearest and yet most concise explanation I found.

@mlynch How would you mix this approach, which seems best suited for "zero-second actions", with actions that have a physical duration, in which we debounce/throttle to capture the change?

For example, when the user drags an object around a canvas we get many different micro updates, but we don't want every single one of those updates to be pushed onto the stack as its own action. I can think of some ideas but I'm curious to hear from your expertise, for myself and future readers.