Python list and dict with undo

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.

A broadly applicable way

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.

Patterns

There's this Stackoverflow question which suggests some patterns.

I ended up using the command pattern.

Databases

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.

Known problems

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.

Studying existing programs

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?

A half-baked idea for efficiency

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.

Blog index