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