Vim Tip of the Day: Time Travel

[In tribute to Bram Moolenaar, 1961 – 3 August 2023, creator of Vim. The undo tree was one of the major “improvements” that Bram made over Vim’s predecessor, Vi. This was also the one big topic missing from this series, and I felt that now was the right time to add it.]

You know how, sometimes, you wish you could just go back and do it all over again? There was that critical juncture when you made the wrong choice, either because you didn’t know enough, or because you were mistaken, or because, in a moment of weakness, you hesitated, even while knowing the right path? Or those times when you wish you’d thought of doing something before it was too late, and the opportunity was lost forever? The bitterest tears shed, they say, are for words left unsaid and deeds left undone.

In the real world, we can only live with regret in such cases, carrying these hard lessons with us in our hearts as we strive to avoid making the same mistakes again. Luckily, Vim is much kinder than the real world in this respect. In Vim, we don’t have to live with the consequences of our mistakes. Indeed, we can make all the mistakes we like, learn from all of them, and even compose for ourselves a synthesized version of reality that includes the best of all possibilities. Sometimes, it is even expedient to make a mistake just to take advantage of these “many worlds.” Today, we’ll learn about Vim’s incredible undo tree.

It starts out simply enough. You add a sentence to your text, then undo it and add a different sentence, only to realize you’d actually like to have both sentences. In a conventional text editor or word processor, the original sentence is gone forever, since undoing its addition eliminated it from the timeline accessible to you with the undo operation. That is, traditional editors model changes as a linear sequence, like 1→2→3→4→5. If you undo at this point, you get 1→2→3→4. Now, adding a new change gives you 1→2→3→4→5′, where 5′ is a different change than 5. Undoing now takes you back to 4, not to 5, which has been lost.

In Vim, in the same situation, undo (u) brings you back to 4 and redo (C-r) takes you to 5′ again, so it would seem that there is nothing different here (for now, we are setting aside the fact that only in Vim can you treat the addition of a sentence neatly as a single change — in a conventional editor, it could entail a single undo or several, depending on arbitrary factors like when you paused during typing). But in fact, Vim represents the undo history like this:

    1→2→3→4→5
           →5'

That is, no edit ever destroys or mutates data (even if you’re using something like c that appears to mutate the buffer); rather, a node representing the new buffer state is grafted onto the node representing the a priori buffer state, implicitly giving rise to a tree of buffer states. With the history represented this way, no change is ever lost.

We are now in a position to see that u and C-r are for structural translation across time — that is, translation in relation to the sequence of changes along branches of this tree. Structurally, 4 comes before 5′ because 5′ reflects the change that was made to the buffer when it was initially in state 4.

But there’s also chronological translation:

g- / g+ — chronological undo / redo

If you do g- when at 5′, it will take you to 5 and not 4, because chronologically (i.e. in terms of actual wall clock time), 5 came after 4, and 5′ came after 5. Importantly, the act of undoing or redoing is not considered a change in the buffer, so these temporal translations don’t reflect in the undo tree as fresh changes. This was a point of confusion for me when I first learned about the undo tree. After all, if you g- at some point, then wouldn’t your state right before that be returned to upon g- again? No, because neither of these were fresh changes but only temporal translation over existing changes¹.

Vim provides many commands to interact with the undo tree (see :help undo), but personally, I find some form of visualization indispensable to full use of the undo tree, making most of these commands superfluous. There are many plugins for this, including Gundo in Vim, which allow you to navigate through time using the same motions you use in navigating through space — that is, h, j, k, and l. Other Vimlikes such as Emacs Evil also have similar visualization plugins.

Let’s try an exercise. Imagine you’re writing a poem and you start with these lines:

When great trees fall,
rocks on distant hills shudder,

… and then add a couple of lines:

When great trees fall,
rocks on distant hills shudder,
and even elephants
lumber after safety.

At this point, you’ve decided you want something else here, so hit u to undo. Now, add two different lines:

When great trees fall,
rocks on distant hills shudder,
lions hunker down
in tall grasses,

But looking at it now, you decide that the poem is best with all of these lines in it. Use the undo tree commands we’ve learned to paste the most recently added lines into the original, to get:

When great trees fall,
rocks on distant hills shudder,
lions hunker down
in tall grasses,
and even elephants
lumber after safety.²

This tip was added to the series on the occasion of Bram Moolenaar’s untimely passing at the age of 62, after three decades of dedicating himself to the labor of love that is Vim. Farewell, Bram. Many have said in recent days that he :wq this world — a quip he would probably enjoy. But I like to think he’s merely yyg-p and is continuing his journey somewhere among the dense and sprawling branches of the great tree of life.

¹To be precise, u, C-r, g+ and g- are not changes but navigations of the tree of prior buffer states. u and C-r simply ascend and descend with respect to some terminal change (so not every change is encountered), while g+ traverses the tree using a preorder traversal, and g- traverses using a converse postorder traversal (so that these reach every change).

²From When Great Trees Fall, by Maya Angelou.