Just wanted to make some notes on “Resolving the Great Undo-Redo Quandary”. It was high on HackerNews, but I missed the window to post.
Here’s my attempt to visualize what the author described. This is what the undo/redo stacks would look like in the standard case (and, I believe what emacs does).
| iter | undo | redo | display | action |
|------|--------------------|-------|---------|---------|
| 1 | A | | A | Add 'A' |
| 2 | AB | | AB | Add 'B' |
| 3 | ABC | | ABC | Add 'C' |
| 4 | AB | C | AB | Undo |
| 5 | A | CB | A | Undo |
| 6 | ABC(-C)(-B)D | | AD | Add 'D' |
| 8 | ABC(-C)(-B) | D | A | Undo |
| 9 | ABC(-C) | D(-B) | AB | Undo |
| 10 | ABC(-C)(-B)D(-D)BE | | ABE | Add 'E' |
Then, there is this optimization.
Third, although it isn’t strictly necessary, we can add a slight shortcut because of redundancies. In the A-B-C example above, B) is redundant with A), because one is just the other in reverse. When the butterfly is squashed and we create B, we mark its beginning and end as “instant”; whenever we later traverse onto either end of B), we proceed to the opposite end in one fell swoop to save the user some traversal time. All edit states are recoverable from A & C alone. Again, it’s strictly optional, but less cumbersome.
After confirming with the author (thanks, Troy!) I now understand the behavior described would be like this:
| iter | undo | redo | display | action |
|------|------------------------|------------|---------|---------|
| 1 | A | | A | Add 'A' |
| 2 | AB | | AB | Add 'B' |
| 3 | ABC | | ABC | Add 'C' |
| 4 | AB | C | AB | Undo |
| 5 | A | CB | A | Undo |
| 6 | ABC(-C)(-B)D | | AD | Add 'D' |
| 8 | ABC(-C)(-B) | D | A | Undo |
| 9 | ABC | D(-B)(-C) | ABC | Undo |
| 10 | AB | D(-B)(-C)C | AB | Undo |
| 11 | ABC(-C)(-B)D(-D)BC(-C) | | ABE | Add 'E' |
Note the “fast forward” in step 9, where we rewind through both (-B)(-C).