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 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.

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.