A better undo system?

The current undo system of kakoune uses a very common model, and works fine. But this model also has a well-known disadvantage. Consider the following operations:

do operation A
do operation B

then the state with A performed is lost forever: one can not reach this state through undoing and/or redoing. If viewing operation history as a tree, things become clearer:

   initial state
    /            \
  A              B*

In the model kakoune uses, only the “current” branch of the tree (the one of B in the above example) is preserved. Hence any other branches (e.g. the one with A) will be lost.
This can often be annoying, the evidence can be found from other editors. VIM uses the same model as kakoune by default, and there’s the plugin undotree, which support navigating the complete undo tree as illustrated above. Emacs by default uses a weird model (generally considered worse than that of VIM and kakoune, but actually more “powerful” in terms of what can be navigated), and again there’s a plugin.

While this might indicate that a plugin or built in support for full undo-tree would be desirable, too, I think the undo-tree approach is not perfect as well. In particular, it introduces at least two more operations (prev-branch and next-branch) and potentially an extra UI interface to visualize the tree. And the decision point to apply prev-branch and next-branch can only be obtained from users’ memory. Actually, I believe why full tree support is rarely found as default of editors.

But in fact the same expressiveness can be achieved with only undo and redo as well, since different branches in the undo tree are actually ordered. Recall the example at first:

do A
do B

In my opinion, the best behavior would be:

do A  --> state: A applied
undo  --> state: initial
do B  --> state: B applied

undo  --> state: nothing applied
undo  --> state: A applied
undo  --> state: nothing applied

You can see, in the second undo at the bottom, another undo is undone. But if we simply let undo undoes other undo's as well, we will end up being unable to undo more than once:

do A --> A applied
do B --> A then B applied
undo --> A applied
undo --> last undo undone, A applied again
undo --> same as the first undo, dead loop

Therefore, a decision on when undo should be undone is crucial (BTW, rely on poorly chosen key to do this is why the Emacs model seem so weird, in my opinion). In fact, this can be completely automatic and intuitive, too. When we really need to undo undo is clear: when a new branch in the undo tree is created, i.e. when something other than undo and redo is applied at a state with several undo's applied. Using the first example again:

do A --> A applied
undo --> nothing applied, now one undo is applied
do B --> B is neither undo or redo, hence a new branch is created, the last undo should be undone
undo --> nothing applied, now the next command to undo is the first "undo"
undo --> undo the first "undo", A applied

Here’s a way to implement this:

  • when performing undo, besides the present behavior, push the undo into a separate stack recording top-level undo'es.
  • when a command except undo and redo is applied, append the undo stack to the command history first.
  • when performing redo, also pop one undo from the undo-stack.

Maybe this can be implemented as a plugin, using %val{history}, which seem to store all branches. Not diving deep yet.

I am not sure if something similar has been posted somewhere before, and I would also like to hear your ideas on this proposed model ; )

1 Like

UPD: kakoune has support for full tree-based undoing, only lacking a visual interface compared to other editors’ plugins, via <a-u>. My miss, luckily the latter half of the above arguments still hold.