I've made some python list and dict with undo and redo so I can play back and forth the operations applied to them. Its on Github.
When making this, I found a few webpages about undo but there doesn't seem to a clear answer for how to get fast undo and/or low memory usage (or what the trade-off between the two can be). Or even some nice basic building block to start from to ensure a coherent state at all times.
Well there's this description which is pretty comprehensive but its making an entire copy of an object whenever the object changes, which just looks very inefficient for something like list.append. The author does say that in their implementation, they use partial copies but it doesn't address the issue of array-like structures in general.
There's this Stackoverflow question which suggests some patterns.
Command pattern: record the function and parameters to undo an action before taking the action. Then run the recorded function with the recorded parameters to undo.
It doesn't need to be functions and parameters in general, just all the information needed to undo packed in an object (a command). Multiple undos have to be rolled back one-by-one.
Memento pattern: save a state regeneration "seed" whenever a change is made. To undo, just pick the state you want to be in and regenerate it from the seed.
This seems more adapted for simple things like random number generation and not lists of lists.
I ended up using the command pattern.
Undo and redo are exactly the kind of operations databases deal with but I didn't find anything that I could use for list and dict. Stuff on databases are very strongly focused on relational databases which are tables with rows and columns. While lists could be thought of as a single row or column, having a table for each list doesn't look like the right representation of the data, especially if you have lists of lists of lists.
I'm assume parameters passed are immutable, which is very much not true. For example list.extend would give a different result on a redo if the list passed as parameter is changed after extend is called.
Although in general, mixing objects tracked and untracked by the undo system could give you this problem anyway.
We have so many programs with pretty advanced looking undo features. Is there an easy way to extract a description of how each of them implement undo?
Does this mean whenever they add something new, they have to make it "tracked" by the existing undo feature? Or is everything else immutable?
Rolling back one command at a time is a bit slow and snapshots take up memory (and are slow to make). What if we only redo operations and a snapshot from one operation ago, 2 operations ago, 4, 8, 16, and so on? (Or a different base for the exponent, like 1.5.)
This would save on memory and only things from far back would take long to get to.