I’ve needed this before - a couple of times. Third time I figured I needed something small, nimble - yet complete. And - at the same time - wondering about how to do it in a very simple manner. I think it worked out great, so let’s dig in.

Undo histories and managers

Most UIs will have some form of undo functionality. Now, there are generally two forms of it: undo stacks and version histories. A “version history” is what Photoshop history gives you - the ability to “paint through” to a previous state of the system. You can add five paint strokes, and then reveal a stroke you have made 4 steps back.

But most apps won’t need that. What you will need is an undo stack, which can be specced out as follows:

• An undoable action gets performed and gets pushed onto the stack.
• If undo is requested, the stack is popped and the rollback action gets applied for the popped action.
• If an action was undone, you can redo that action. If you have undone 2 actions, you can redo 2 actions.
• If you push an undoable action onto the stack in presence of actions that can be redone, they get discarded - there is no branching, remember?

If you are curious how “the big guys” used to do it - check out the NSUndoManager documentation

So, as I usually like to do, I want to understand the API that would be optimal. For this use case - drawing - I had the following workflow:

• When you draw a stroke the input points get added to currentStroke
• When you release the pen the currentStroke gets appended to strokes and reset for the next stroke.

I wanted something like this:

let addStroke = () => strokes.push(currentPaintStroke);
let removeStroke = () => strokes.pop();
undoThing.push(addStroke, removeStroke);

// then, on user action
undoThing.undo(); // calls removeStroke()
undoThing.redo(); // calls strokes.push(...) again

The perils of stack pointers

Simplest thing in the world. Now, if you look at most recommended (and some existing!) implementations of an undo stack, you will find they usually make use of a stack with a pointer. Like here and here - you would have a stack, usually represented as a JS array, and some kind of pointer or an index that you would use to index into it.

And while it is workable and standard, it just didn’t jive with me well. See, using an index into an array usually makes JS code susceptible to two things, which bite me every single time:

• Indexing into a nonexistent index - hello undefined checks
• Mistakes in offsets when calling Array.slice and Array.splice. Oh, and confusing slice and splice, of course.

The fact that Ruby and JS have different semantics for slice - one uses the index bounds, the other uses two offsets - doesn’t help things. And what happens if an API uses offsets into a vector? Exactly: confusion whether those offsets are inclusive or exclusive. Oh, and the offsets change after you mutate the array, which makes it even more painful.

Could we not index?

So what came to mind was this: we effectively have two stacks, not one. We have an undoStack (things that can be rolled back) and a redoStack - things that can be rolled forward. All the things we do with our undo-redo actions actually do not change the pointer - they move things from one stack to another. And rules change between these two stacks! We erase the redoable actions when we add a new undoable action, remember? So while an undoable stack will rarely get “nullified”, the redoable stack likely will be nullified frequently.

Once this became clear, the implementation practically wrote itself:

function createUndoStack() {
  let past = [];
  let future = [];

  return {
    push(doFn, undoFn) {
      doFn();
      past.push({doFn, undoFn});
      // Adding a new action wipes the redoable steps
      future.length = 0;
    },
    undo() {
     let action = past.pop();
     if (action) {
       action.undoFn();
       future.unshift(action);
     }
    },
    redo() {
      let action = future.unshift();
      if (action) {
        action.doFn();
        past.push(action);
      }
    }
  };
}

So instead of trying to save resources by having just one array (and miserably failing with off-by-one index errors), we can embrace dynamically sized arrays and just forget indices altogether. Neat!

Let’s add a couple more methods to display our UI:

  get canUndo() {
    return past.length > 0;
  },
  get canRedo() {
    return future.length > 0;
  }

The pass-by-reference problem

There is a catch with our implementation though. JS is pass-by-reference for pretty much all of its types. This means, that when we create a closure over a value - currentStroke in this case - the closure will keep addressing whatever is stored in currentStroke right now. And these doFn and undoFn are very particular in a specific behavioral trait: they must be idempotent. No matter how many times you call them, they should lead to the same result.

If we just do this:

let doFn = () => strokes.push(currentStroke)

each time we call doFn - whatever is currentStroke in the calling scope will end up getting pushed onto the strokes stack. That’s not what we want - we want the doFn to use a cloned copy of the currentStroke, and we want it to do so always. Same for the undoFnx - although in this case there is no need for it to know what’s stored in strokes nor what the currentStroke used to be, as we are not going to resume drawing that currentStroke. Modern JS has a thing for this called structuredClone(), which is perfect for the occasion:

  push(doFn, undoFn, ...withArgumentsToClone) {
    const clonedArgs = structuredClone(withArgumentsToClone);
    const action = {
      doWithData() {
        doFn(...clonedArgs);
      },
      undoWithData() {
        undoFn(...clonedArgs);
      },
    };
    action.doWithData();
  
    // Adding a new action wipes the redoable steps
    past.push(action);
    future.length = 0;
  }

and we’ll amend our functions accordingly. Instead of closuring over currentStroke we’ll make it an argument:

let appendStroke = strokes.push.bind(strokes);
undoStack.push(appendStroke, () => strokes.pop(), currentStroke);

with the push() of our undoStack taking care of making a deep clone for us. Nice!

The complete definition then becomes:

function createUndoStack() {
  const past = [];
  const future = [];
  return {
    push(doFn, undoFn, ...withArgumentsToClone) {
      const clonedArgs = structuredClone(withArgumentsToClone);
      const action = {
        doWithData() {
          doFn(...clonedArgs);
        },
        undoWithData() {
          undoFn(...clonedArgs);
        },
      };
      action.doWithData();

      // Adding a new action wipes the redoable steps
      past.push(action);
      future.length = 0;
    },
    undo() {
      let action = past.pop();
      if (action) {
        action.undoWithData();
        future.unshift(action);
      }
    },
    redo() {
      let action = future.shift();
      if (action) {
        action.doWithData();
        past.push(action);
      }
    },
    get undoAvailable() {
      return past.length > 0;
    },
    get redoAvailable() {
      return future.length > 0;
    },
    clear() {
      past.length = 0;
      future.length = 0;
      return true;
    }
  }
}

export {createUndoStack};

Robust, small, and no indexing errors. My jam.