In my C code, I implement undo/redo using write protection (mprotect).
First you mark all of your app memory as read only, so that you can define a SIGBUS handler when attempts are made to write to it.
Then when you detect a write to a page in the app memory, you append a copy of that page's memory to a stack, and then mark the page as writeable so that the page can be updated.
Then undo is simply a matter of popping the stack and overwriting the app memory with the copy stored on the stack entry.
This means you don't have to explicitly write "actions" for everything you want to undo/redo. All in-memory actions are handled automatically.
Obviously this means that things like FS changes or network IO changes aren't captured, but sometimes that's fine, and I'm sure there's a way to extend this scheme to handle those things somehow
That's great until your manager says something like: please group undo actions such that typing a word+undo will remove the entire word, not just one character at a time. Or show "Redo" in the menu after the undo.
Anyway perhaps there's a place for your solution at the compiler/language level, at various granularities. I've played with the thought, but considered it impractical so far considering those always changing requirements. Also, memory use might go through the roof for some applications.
Besides memory use I'm not sure why his approach isn't easy for everything you suggested.
Want to group undo actions? It's pretty easy to define arbitrary grouping algorithms on the sequence of recent state snapshots, which yields...a smaller sequence of state snapshots :-) a nice composeable idea.
To show redo after an undo, store recent undo triggers in the state, and if there is undo in current state, show redo with a list of older mem states to jump to. This repr also makes it easy to wipe out redos when doing a redo-breaking operation like editing the doc.
Memory use can indeed become a problem. But if/when it does, there is probably some obvious trait of the sequence of recent states that makes it easy to compress. Like for example that it's 99% the same contents, after a small edit. Or that one edit type dominates. Or that folks don't often care if they can't Ctrl+Z through 8GB of typing.
I think most programmers would gain by not dismissing simple approaches out of hand as too simple.
If writing it off for memory, write out the math for the size of the state and the allotted memory. This is not the era of computers that our languages were invented in; the page size your CPU fetches from insanely fast SSDs can be 4kb. And it can do a lot of that in a blink. Trying to shift runtime work (that the computer does) back to compile/design time (that the dev does) can cripple a system's performance in the short run (for coding/delivery time) and long run (for performance after pointer chasing)...luckily most of the time it doesn't matter anyway :-)
I honestly can’t tell if that’s an elaborate joke response or if that’s really something that works. If it does:
* How do you make sure you capture all mapped memory within a process? Walking something like /proc/self/maps?
* Does this include the stack and if so, doesn’t this cause havok when you write back. And if it doesn’t include the stack, can’t run things out of sync easily?
* This is then a page sized undo/redo, so it isn’t atomic with regards to actions triggered. Wouldn’t partially undoing such changes easily cause an invalid state?
I can't speak to every use case but it's been working great for my game:
1. I don't heap allocate anything after init. All allocations are custom allocated from this memory. I use a linear allocator, but could use some other scheme.
2. I don't account for the stack at all, but it doesn't mess anything up. The only important memory is the app memory, and that persists across frames.
3. It is, but you're computing deltas across frames, so they are atomic wrt user input. It's true that if multiple changes are made to the same page in the same frame then undoing that page undoes all of the changes, but that is often desirable from the user's perspective.
Thanks for your response. Interesting. I can see that working with these restrictions. This basically also assumes the data within that memory area only has pointers to either somewhere else in that area or to static structures outside, correct? Also the write rate is probably quite low as I imagine constantly handling SIGBUS would quickly slow things down? Did you look into userfaultfd?
First you mark all of your app memory as read only, so that you can define a SIGBUS handler when attempts are made to write to it.
Then when you detect a write to a page in the app memory, you append a copy of that page's memory to a stack, and then mark the page as writeable so that the page can be updated.
Then undo is simply a matter of popping the stack and overwriting the app memory with the copy stored on the stack entry.
This means you don't have to explicitly write "actions" for everything you want to undo/redo. All in-memory actions are handled automatically.
Obviously this means that things like FS changes or network IO changes aren't captured, but sometimes that's fine, and I'm sure there's a way to extend this scheme to handle those things somehow