Minority Opinions

Not everyone can be mainstream, after all.

Unfolding the Undo Tree

with one comment

In the beginning, there was the text editor.  At some point, someone noticed how easy it was to destroy an hour’s worth of typing with a single keystroke, and invented the “undo” command.  A simple keystroke could pretend that your latest edit never happened; hit it again, and that edit gets restored.

Fast forward to a time when memory is less scarce, and many more people are using computers even faster.  It’s now a bit too common to make two or more changes before realizing that something needs to be undone, so undo learns how to revert multiple edits.  However, that requires a second command, redo, to restore them.  Nobody complains, because the extra power is worth it.

Yet there’s still a problem; if an edit gets undone, and another edit made, there’s no way for a simple undo/redo stack to restore the first edit.  Therefore, we now have the undo tree.  I first noticed it in Vim 7, but it’s entirely possible that another program had it first.  Unfortunately, the interface sucks.

To fully understand the tree, consider the hypothetical undo sequence at the right, where each circled letter stands for a state of the document, and each arrow an undoable edit.  The letters correspond to the order in which the edits occurred; A is first, and M is last.  Note in particular that K happened after J, meaning that the user had somehow backtracked from state J to state H, then later went back to J.  Let’s say that M has been undone, so L is the current state.

How would you like to navigate this tree?  The common undo and redo commands navigate up and down, but only along the right-most branches; they can’t get to states C, F, G, H, or K.  Vim solved this by adding :earlier and :later commands to navigate between states by timestamp, but that’s a little confusing.  For example, going :earlier from L will get you to K, then from K to J.  From D, :undo will take you to B, but :earlier will take you to C.  If you go :earlier to E, it’s not at all clear whether :redo will take to to F (where you came from) or I (the most recent next state).

The good news is that :earlier and :later get you to every node on the tree, sooner or later; the bad news is that the transitions between branches can feel abrupt and jarring.  The main issue is that the tree is best expressed in terms of states, but we as humans tend to think in terms of edits.  The D to C transition is uncomfortable because the edit being undone is B→D, but the B→C edit gets restored at the same time.  Yes, state C was created after B, but we most recently saw B, so that’s where we expect to end up.  The :undo command gets us there, but is less powerful.

Perhaps there’s a way to combine the best of both commands, into something that can be integrated into a mainstream product.  (Yes, I like Vim, and yes, I think every programmer should be using it, or at least be able to use it, but no, I don’t consider it mainstream.  I would never subject my sisters to it, for example, even though they’re quite proficient at word processors.)  The key is to go back to where the user came from.

We can reconstruct the user’s path through the tree by looking at timestamps alone, but the task would be much easier with the addition of a few more arrows: C→B, G→F, H→E, J→H, and K→J.  These arrows represent undo paths that led to new branches on the tree.  Note, however, that M→L doesn’t get created; that would only happen once a new change N gets added, assuming that it’s an edit from L instead of from M.

Once we have those new transitions, we need a command pair that traverses over transitions in timestamp order.  Not the timestamp of the nodes — :earlier and :later do that — but of the transitions themselves.  Backtracking from L will take you to J, then K, then H, then J again.  Backtracking from D will go to B, then C, then B again.  States get visited more than once, but each real edit is represented coherently.  The only time multiple edits get lumped together is when you’ve backtracked to start a new branch.

Now I’m tempted to convince Vim to do that somehow, so I can evaluate whether it really would work as a full undo/redo replacement.  It might be possible as a plugin, perhaps based on Gundo; if not, I could be convinced to edit the Vim source.


Written by eswald

18 Apr 2011 at 5:24 pm

Posted in Technology

One Response

Subscribe to comments with RSS.

  1. I’m under the vague impression that Emacs’s approach to this is to treat redos like any other command. I think that linearizes the whole tree but it can be confusing. In fact, I’m confused just trying to describe it.

    Daniel Reeves

    26 Apr 2011 at 10:56 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s