Undo

If there’s one feature almost every non-trivial application should have which is overlooked, left as an exercise, or put aside as “too hard” by web frameworks, it’s undo.

I do not have much (any) love for Redux, but whenever I think about it, I wonder “why isn’t undo support built in out of the box”?

To its credit, the Redux folks do actually address Undo in their documentation. “It’s a breeze” the document says at the top, and it’s a mere 14 pages later that it concludes “This is it!”.

I’ve pretty much never seen a React/Redux application that implements undo. Since it’s such a breeze, I wonder why. My guesses:

  1. The words “service” and “back-end” do not appear in the document.
  2. It doesn’t look like a breeze to me. A 14 page document describing implementation of a core concept in a toy application sounds more like a tornado.
  3. Finally, every non-trivial Redux application I’ve ever seen is an incomprehensible mess. (Once multiple Reduxes get composed together, you’re left with multidimensional spaghetti code of the ‘come-from’ variety.) Adding undo into this mix as an afterthought strikes me as a Kafkaesque nightmare.

It’s since been pointed out to me that there are libraries, such as redux-undo, around that wrap the implementation described in the Redux documentation (or variants thereof) in libraries. The example application is a counter, I don’t know of nor have I seen any non-trivial examples.

“Come-from”? Come again?

Programmers by now fall into two groups. Folks who have either read or know by reputation the article Goto considered harmful — possibly the most famous rant in the history of computer science — or folks who have grown up in a world where the entire concept of goto has been hushed up as a dark family secret.

come-from means code that is triggered by a foreign entity, you don’t know when. You can think of it as an uncharitable description of the Observer Pattern. It’s the dual of goto. There are two common examples that are employed widely in user-interfaces — event-handling and pub-sub.

Event-handling is necessitated by the way human-computer interaction works — you’re talking to the analog world, it’s not going to be pretty. The user will do something, it’s generally unrelated to what, if anything, your code was doing. You need to deal with it.

Pub-sub can be self-inflicted (i.e. used when there’s no reason for it), but is often necessitated by the realities of asynchronous and unreliable communication between different entities. Again, that’s not going to be pretty. You make a request, you make other requests. Time passes. Things change. Suddenly you get a response…

Redux is a state management system, so it is natural that it implements the Observer Pattern, but it adds the additional garnish that the mapping between action names and what parts of your application’s state they modify can be — and often is — completely arbitrary.

implementing undo in b8r should be a breeze!?

If you stand back a bit, b8r‘s registry is a similar to redux except instead of your state being a quasi-immutable object which is swapped out by “actions” (with each action being a name linked to a function that creates a new object from the old object) with b8r your state is the registry (or some subset thereof) and your actions are paths.

In my opinion, b8r is wins here because you generally don’t need to implement your actions, when you do they still act on the registry in the expected way, and instead of having an arbitrary map of action names to underlying functions the path tells you exactly which bit of state you’re messing with.

For purposes of implementing Undo, however, Redux seems to have an advantage out of the gate in that it is (partially) cloning state every time something changes. So all you need to do is maintain a list of previous states, and you’re golden, right?

What should it require to implement Undo (in b8r)?

To my mind, it should be something like this:

import {UndoManager} from 'perfectUndoLib'
new UndoManager('path.to.foo', {
    path: 'foo-history',
    onUndo: ...
    unRedo: ...
    onUndoRedo: ...
    onHandleChange: ...
});
b8r.get('foo-history.undoQueue.length') // number of undoables
b8r.get('foo-history.redoQueue.length') // number of redoables
b8r.call('foo-history.undo') // undoes the last thing
b8r.call('foo-history.redo') // redoes the last thing
b8r.call('foo-history.reset') // clears queues (e.g. after saving a file)

The first parameter could allow a list of paths to include in the undo manager’s purview, while also allowing multiple independent undo chains using multiple undo managers (e.g. some advanced graphics applications separate out changes in viewport from changes in the underlying scene).

The path option would probably default to lastThing-history and so foo-path would be superfluous.

Ideally, the callback options would allow async functions to do things like perform a service call to keep the store consistent with the interface, curate the undo and redo queues (e.g. TextMate used to do single keystroke undo which was infuriating when going back through a large edit history, addressing this appears to have paralyzed development and sidelined what had been the darling text editor of the hipter screencast brogrammer crowd), handle errors, and so on.

Implementation Details

At this point in our story, I hadn’t written a single line of code.

I have, however, been thinking about this for several years, which is more important. I’ve implemented several different non-trivial applications (RiddleMeThis, two word-processors, and a non-destructive image editor) with undo support. I think it’s worthwhile when saying something like “I wrote this code in 2h, am I not a true 100x coder!?” to acknowledge, at least to oneself, that it crystallized thoughts collected over a longer period (in this case several years), or whatever.

E.g. I wrote the core of b8r in less than two weeks, but it was a rewrite from scratch of a library I had written over a period of several months while at Facebook which was itself a rewrite of a rewrite of code I had written at USPTO.

b8r — or rather its registry — already has a robust observe method that informs you when anything happens to a particular path (or its subpaths), so something like:

import b8r from '../source/b8r.js'

Of course we’re going to need to deep clone state because — unlike with Redux — we can’t just grab the current state object.

On the plus side, we can just keep a copy of the subtree that changed. Keeping a clone of the entire state in memory every time something changes can get hairy.

Aside: two of the three serious implementations of undo I’ve been responsible for have been (a) a long form word-processor that handled both annotations and multi-user-edit-history and (b) a non-destructive image-editor). And, in fact two things I’ve been thinking about putting together as side projects are a long-form book-publishing system (which aims to publish on web and ePub vs. print/pdf/etc.) and a photography-workflow application, neither of which are going to play nicely with naive “every undo step is the state of your app” approaches.

Here is the code actually committed to the repository in the course of writing this post. Or you can see it in the inline documentation system.

After a quick visit to StackOverflow and Google, it looks at first approximation like the most robust option is “the dumb thing”:

const deepClone = (thing) => JSON.parse(JSON.stringify(thing));

OK so now for the meat!

export class UndoManager {
  constructor (watchPaths, options={}) {
    watchPaths = [watchPaths].flat()
    const {
      historyPath,
      onUndo,
      onRedo,
      onUndoRedo,
      onHandleChange,
    } = {
      historyPath: '_' + watchPaths[0].split('.').pop() + '_history',
      ...options
    }

We expose the buffers and methods in the registry, which makes binding controls to undo and redo super simple. The observer is how we get notified state we care about changes.

    b8r.register(historyPath, {
      undoBuffer: [],
      redoBuffer: [],
      undo: this.undo,
      redo: this.redo,
      observer: this.handleChange.bind(this)
    });

    Object.assign(this, {
      watchPaths,
      historyPath,
      onUndo: onUndo || onUndoRedo,
      onRedo: onRedo || onUndoRedo,
      onHandleChange
    })

    this.reset()
    this.observe()
  }

  reset () {
    this.undoBuffer.splice(0)

    this.undoBuffer.push(this.watchPaths.reduce(
      (state, watchPath) => {
        state[watchPath] = deepClone(b8r.get(watchPath))
        return state;
      },
      {}
    ));

    b8r.touch(this.historyPath)
  }

b8r.observe informs you of state-changes after they happen. (Because, for perf reasons, changes to the registry are queued and handled asynchronously, so if one or more registry entries are changed rapidly, each relevant observer will only be fired once.) So if we wait to collect state until the first user action, we’re not going to be able to restore our original state.

  observe () {
    this.watchPaths.forEach(path => b8r.observe(path, `${this.historyPath}.observer`))
  }

  unobserve () {
    this.watchPaths.forEach(path => b8r.unobserve(path, `${this.historyPath}.observer`))
  }

  get undoBuffer () {
    return b8r.get(`${this.historyPath}.undoBuffer`)
  }

  get redoBuffer () {
    return b8r.get(`${this.historyPath}.redoBuffer`)
  }

restore doesn’t care where state is coming from, its job is just to restore it without triggering handleChange and notify anything bound to the the instance that its state has changed.

  async restore () {
    this.unobserve()
    // const state = b8r.last(this.undoBuffer)
    // b8r.forEachKey(state, (value, key) => b8r.set(key, value))
    this.undoBuffer.forEach(state => {
      b8r.forEachKey(state, (value, key) => b8r.replace(key, deepClone(value)))
    })
    this.observe()
    b8r.touch(this.historyPath)
  }

It turns out there’s a couple of subtle bugs in restore both of which become obvious if the UndoManager (now called HistoryManager) is handling changes on more than one path. So restore() now replays all changes in the undo queue.

I’ve commended out the bad lines of code — the loop below fixes both bugs. There are obvious optimizations here which I have not yet implemented.

When the state of the world changes owing to user action, we need to put the new state on the undoBuffer and clear the redoBuffer (which is now obsolete).

  async handleChange (pathChanged) {
    if (this.onHandleChange && ! await this.onHandleChange()) return
    this.undoBuffer.push({
      [pathChanged]: deepClone(b8r.get(pathChanged))
    })
    this.redoBuffer.splice(0)
    b8r.touch(this.historyPath);
  }

  undo = async () => {
    if (this.undoBuffer.length === 1) return
    if (this.onUndo && ! await this.onUndo()) return false
    this.redoBuffer.push(this.undoBuffer.pop())
    await this.restore()
    return true
  }

  redo = async () => {
    if (this.onUndo && ! await this.onRedo()) return false
    this.undoBuffer.push(this.redoBuffer.pop())
    await this.restore()
    return true
  }

  destroy() {
    this.unobserve()
    b8r.remove(this.historyPath)
  }
}

And undo/redo are now super simple to implement. E.g. this example is now in the documentation of undo.js:

<button 
  data-event="click:_simple-undo-example_history.undo"
  data-bind="enabled_if=_simple-undo-example_history.undoBuffer.length"
>undo</button>
<button 
  data-event="click:_simple-undo-example_history.redo"
  data-bind="enabled_if=_simple-undo-example_history.redoBuffer.length"
>redo</button><br>
<textarea data-bind="value=simple-undo-example.text"></textarea>
<script>
  const {UndoManager} = await import('../lib/undo.js');
  b8r.register('simple-undo-example', {
    text: 'hello undo'
  })
  const undoManager = new UndoManager('simple-undo-example')
  set('destroy', () => {
    b8r.remove('simple-undo-example');
    undoManager.destroy()
  })
</script>

And that’s it!

I’ve walked through the general-purpose implementation of undo in b8r and it looks to me like you can use this to implement undo in a typical b8r application in a single line of code (plus whatever extra lines it takes to put in and add the widgets to your view and bind them). I’d say that qualifies as a breeze — at least until you get to dealing with services.