A while ago I spent some time carefully figuring out how Emacs undo works. I decided to post this here; perhaps you might find it interesting.
First, you should have a basic idea of how Emacs undo works. When you edit a file, changes are placed on a undo list. When you undo, the state of the buffer is reverted according to the undo list; however the undo itself is placed on the undo list, so you redo by undoing again. The advantage of this approach is that you will never lose any state your buffer was in, and all states are available via a linear undo (unlike undo-tree which requires navigating a non-linear tree).
Unforunately, after many undos and undos of undos and undos of undos of undos, it's quite easy to get your undo history into an interesting mess, but once you understand exactly how it works, it's not so bad (keep reading).
First, I will describe the rules governing undo. Next, I will walk through an example of a complex undo change. Finally, I will present the state of the undo list for completeness.
If you read the manual, linked above, you will know that there are
two undo commands, undo
and undo-only. undo-only will only undo,
skipping undoing undos (redoing).
The rules:
undo moves back one state along the undo chain.undo-only moves back one state along the temporal axis.undo-only always move backward along the temporal axis.undo moves in the opposite direction along the temporal axis as
the change it is undoing.
I encourage you to follow along with the example. Open up *scratch*
and bind undo-only to an easy to press key; you don't want to use
M-x for this.
First, insert some text
A B C
Insert! o--o--o--o
Each node represents a buffer state. Each buffer state will be
labeled with a letter. For convenience, type a RET to
move to state A. The RET is an easy way to make Emacs
set a break in the undo chain; otherwise Emacs will group contiguous
inserts into one "state". Also, this state A is actually two states,
the "inserted a" and "inserted RET" states. In this example, each
undo will actually be two undos, one to undo the RET and
one to undo the letter.
After following the above, your buffer should look like this:
a
b
c
Next, undo twice:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/
o
You are now back at state A. Note how the undo chain is presented here. The undos have been added to the end of the undo chain, however, the chain is now going backward temporally. We type some more:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
Still simple. We keep going:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
/
/ F G H
Insert! o--o--o--o Undo!
/
/ I J
Insert! o--o--o
It's getting complex now; we'll start calling undo-only now:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
/
/ F G H
Insert! o--o--o--o Undo!
/
/ I J
Insert! o--o--o undo-only
/
F G /
o--o--o
Our first undo-only goes back one state to state I. So far so good.
Our second undo-only goes back one state to state G. So far so good.
Our third undo-only goes back three states to state F. However, we
only went back only one state "temporally": we skipped all intervening
undo/redo pairs.
We keep going.
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
/
/ F G H
Insert! o--o--o--o Undo!
/
/ I J
Insert! o--o--o undo-only
/
D F G /
o--o--o--o
/
A/
o
Now we're all the way back to state A. With undo, we would have had
to traverse every single state (count them, there's a lot), but with
undo-only, it only took five.
Now for the final stretch. We insert a few more fresh states:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
/
/ F G H
Insert! o--o--o--o Undo!
/
/ I J
Insert! o--o--o undo-only
/
D F G /
o--o--o--o
/
A/ K L
Insert! o--o--o
And we undo a whole bunch:
A B C
Insert! o--o--o--o Undo!
/
/
o
/
/ D E
Insert! o--o--o Undo!
/
/ F G H
Insert! o--o--o--o Undo!
/
/ I J
Insert! o--o--o undo-only
/
D F G /
o--o--o--o
/
A/ K L
Insert! o--o--o Undo!
/
/
o
/
/ D F G I J
(continue) o--o--o--o--o--o
Okay, what happened here? We undid the new states we added, and those
undo actions get added going backward temporally. After that though,
we started undoing undos. These undo changes get added with the
reverse temporality as the original changes, so these undo changes are
going forward temporally. If you did undo-only at this point, you
would undo these changes.
(But wait, aren't these changes undo changes? undo-only doesn't undo
undos, right? Well, these changes are actually undos of undos, so
they're actually redos, not undos, hence why they move forward
temporally.)
That's it for the example. Keep in mind however that this "undo
chain" is just a concept to help understand how undo works. What
Emacs actually stores is buffer-undo-list. You can check it out
with describe-variable.
If you have been following along with the example, the state of
buffer-undo-list should be like below. I have annotated it with
points from the undo chain diagrams.
'(
nil
(12 . 13)
nil
(11 . 12) ;Redo insert j
nil
(10 . 11)
nil
(9 . 10) ;Redo insert i
nil
(8 . 9)
nil
(7 . 8) ;Redo insert g
nil
(6 . 7)
nil
(5 . 6) ;Redo insert f
nil
(4 . 5) ;Redo insert newline
nil
(3 . 4) ;Redo insert d
nil
("k" . 3)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("\n" . 4)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("l" . 5)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("\n" . 6)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
(6 . 7)
nil
(5 . 6) ;Insert l
nil
(4 . 5)
nil
(3 . 4) ;Insert k
nil
("d" . 3)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 4)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("f" . 5)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 6)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("g" . 7)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 8)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("i" . 9)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 10)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("j" . 11) ;Undo-only insert j
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 12)
(#<marker
(moves after insertion)
at 12 in tmp-undo> . 1)
(#<marker at 12 in tmp-undo> . -1)
(#<marker at 12 in tmp-undo> . -1)
nil
(12 . 13)
nil
(11 . 12) ;Insert j
nil
(10 . 11)
nil
(9 . 10) ;Insert i
nil
("h" . 9)
(#<marker at 12 in tmp-undo> . -1)
nil
("\n" . 10)
(#<marker at 12 in tmp-undo> . -1)
nil
(10 . 11)
nil
(9 . 10) ;Insert h
nil
(8 . 9)
nil
(7 . 8) ;Insert g
nil
(6 . 7)
nil
(5 . 6) ;Insert f
nil
("e" . 5)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("\n" . 6)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
(6 . 7)
nil
(5 . 6) ;Insert e
nil
(4 . 5)
nil
(3 . 4) ;Insert d
nil
("b" . 3) ;Undo insert b
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("\n" . 4)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("c" . 5) ;Undo insert c
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
("\n" . 6)
(#<marker at 12 in tmp-undo> . -1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
(#<marker
(moves after insertion)
at 13 in tmp-undo> . 1)
nil
(6 . 7)
nil
(5 . 6) ;Insert c
nil
(4 . 5)
nil
(3 . 4) ;Insert b
nil
(2 . 3) ;Insert newline
nil
(1 . 2) ;Insert a
(t . 0) ;Buffer before modification time
)
Finally finally, undo records for undos (redos) are stored in
undo-equiv-table. Again, feel free to check it out.