In case you didn't know, Vim already had undo "trees". My mind was BLOWN when I discovered this: http://vimdoc.sourceforge.net/htmldoc/usr_32.html --
Never again accidentally lose work by accidentally breaking your redo change!
The online docs are still 7.2, so I had to dig into the source for a link to the new persistent undo/redo docs (search for "undo-persistence"):
I'm writing a new text editor and I spent an inordinate amount of time on the undo system. I never realized how many things the choice of undo implementation would affect.
But I did come to the conclusion that Emacs' default undo system is where it's at. Every modification should be undoable, including undos. Once you understand how it works, there's no longer a need for trees and the complexity that brings.
I can tell you a bit about how I implemented the same system in my editor.
It's quite simple if you think of every operation as a function that modifies the document. As you do something, a function that reverses those changes is pushed onto an undo stack. This incudes when you hit the "undo" button.
So if my document state looks like this:
start->A->B->C
where an arrow is a state change, my Undo stack will look like:
U0<-U1<-U2
Where function U2 will get me from C to B, U1 from B to A, and U0 from A to the original document.
If I hit undo, that's a modification, so the state history looks like:
start->A->B->C->B
And my undo stack gets the "un-undo" pushed on the top, and looks like:
U0<-U1<-U2<-U3
So U3, when executed, brings me from the second state B back to state C. I'll never lose anything because every state I've ever seen in the document is implicitly stored in the undo stack.
If you're wondering how pushing an un-undo function on top of the undo stack doesn't prevent you from going beyond one level of undo, it's a simple trick; there is an undo stack pointer that decrements every time you hit "undo" and resets on any non-undo action. This is why in emacs you used to have to "do something else" like type a character to break the undo chain and re-visit more recent states.
It's something in the line of every change is a transaction. A redo is a replay of a transaction. An undo is not exactly a rollback but a reverse of the change and also a new transaction. You can undo a transaction in the past by reaplying later transactions. Makes me think a bit about Operational Transforms but I couldn't synthesizes my precise thoughts on that.
I saw you have experience with Haskell, have you seen Yi? http://yi-editor.blogspot.com/ It has an Emacs and Vim frontend, but is far from being finished.
Yes, it is. That's an extremely old version I wrote as a "let's see if I can do this" project. You can see the newer one by browsing the subversion repository, which unfortunately is broken until I commit the fix tonight.
I'm working on integrating it with Google docs so that you can work on your documents using a vi/emacs-like editor, which is extensible just like emacs except using javascript rather than elisp.
I hadn't seen yi, but it looks very similar to what I want to do, which is combine the best of vi and emacs into a new editor. I'm particularly interested in decent web-based editors, however; the implementation language is secondary.
Thank you thank you thank you for linking to this. I also use both editors (daily), and Emacs' undo system is easily among its worst and most annoying features, while Vim's undo system is among its best. The documentation at the top of undo-tree.el spells out exactly why this is the case. This library makes it all better.
