Make undo / redo a tree instead of a stack (vim-like) [$5]

[muja]

All text editors I know have undo and redo stacks. However, having a tree like vim does would be extremely useful for some cases where a stack just isn't enough. Thoughts / opinions?

--- There is a **[$5 open bounty](https://www.bountysource.com/issues/10575656-make-undo-redo-a-tree-instead-of-a-stack-vim-like?utm_campaign=plugin&utm_content=tracker%2F282001&utm_medium=issues&utm_source=github)** on this issue. Add to the bounty at [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F282001&utm_medium=issues&utm_source=github).

[muja]

To give an example I often encounter this situation:

I have two ways of solving a problem in my code: I write out the first solution. I test it and now I write the second solution and compare them. I want to decide which solution I go with, I switch back and forth, do some tweaks on Solution 1 and 2 to see which one is more flexible / readable / etc.
With a stack, I would have an extremely hard time while with a tree, this would be an easy task.

This feature obviously wouldn't change the normal undo/redo behavior which still acts like a stack. You'd just have an extra command to select between the branches. This should also not break API compatibility.

[quarnster]

What's the benefit of having the editor track a full undo-tree vs just managing two git branches via a plugin?

[muja]

Sorry but I don't quite understand your question. This has nothing to do with git. I'm talking about the cmd-z / ctrl-z and cmd-shift-z / ctrl-y / ctrl-shift-z commands in the text editor and that it would be extremely useful to have a tree over a stack. I have provided a common use case.

Sure you could have two git branches and switch back and forth (if that's your question), but that's way more tedious and I personally don't think an editor's design should depend on what we can already do with other tools, its features should give you a convenient alternative over using those tools. Obviously, nothing can replace git, but you get the gist - otherwise, ultimately, we could argue that the whole editor is redundant since we already have cat and tail and head and could use those instead of Lime.

[erbridge]

I think @quarnster was suggesting someone write a plugin that does the same thing but uses a git repo under the hood. Rather than building it into the editor itself.

I can see the value in this as a feature, but it's pretty low priority.

[quarnster]

My point is that from the use case presented, it doesn't seem to me like you care about every single branch in a potential undo-forest. Wouldn't a K.I.S.S. solution like saving your file into "solution1.cpp" and "solution2.cpp", and linking that "active" file to the originally named file, either manually or via a plugin solve the use case much more trivially?

[muja]

Another example / use case:

I added and changed a lot of code, and now it doesn't compile / work, damn! How did it look before again before I broke it? Let's take a quick look....
CMD-Z, CMD-Z, CMD-Z, CMD-Z......, Z (no CMD) -> the whole progress is gone because I typed Z. Good grief, now I have to rewrite everything!

There are so many more cases that I can't think of right now. If memory is an issue, limit the amount of branches to like... 10? Or the size of an inactive branch can never "deceed" 10% of the current branch or something, to limit memory explosion.

[quarnster]

IMO the CMD-Z*100 then a mistaken "z" destroying the whole stack is much more a convincing use case for implementing this :)

If we limit it, it should be user configurable. In a sense, "regular" stack undo-redo is just the tree undo-redo limited to a single branch.

[muja]

Awesome! :D It's also worth mentioning that I often copy some text, delete it to insert somewhere else later, make 100+ edits, and in the meantime fill the clipboard with other things. So I have to Undo*100 to find the deleted text again.

It'd be nice to be configurable, for sure. What do you think about the memory limitations? I think it would be great to have some "intelligence" behind it. Certain possibilities that come to mind:

1. Keep last X branches (configurable, default to 10?)
2. Keep branches whose edit-count weighs ≥X% of the active branch's. (configurable, default to 10)
   Example:
   Open Editor, 10 * Edit, 5 * Undo, 50 * Edit
   Branch b1 (inactive) has 10 edits in total, 5 since separated from b2.
   Branch b2 (active) has 55 edits.
   Relative to their fusion point, b1 has 5 edits, b2 has 50, which is 10%, so b1 remains in the tree.
   If user makes another edit to active branch, b1 will be removed. 1 Undo + 1 Edit will have no effect on b1.

Opinions?

[quarnster]

Well, this needs to be implemented in steps but I can see it as something like:

• Extend undo-redo into a tree, but keeping it work like current undo-redo
• Add in ability to switch tree branch (preferably a visual tree and ability to select any change in the tree, perhaps using the same backend bits as are needed for the "sidebar-tree"?)
• Define a user configurable memory budget allowance for the undo-redo tree. Once the budget is overrun, trim the tree.
  • How much memory is saved by merging several undo-steps into a single one?
  • How much memory is saved by cutting the <= X% branches?
  • Should it be possible to save/restore parts of the tree to disc?
  • Worst case, just cut off the oldest changes