How are "undo" operations implemented?

[Maximilian]

There must be a better way than having a method that's the reverse operation of every other method How are they implemented in things like libreoffice etc?

 

[nickbits]

Reverse operations and data snapshots are the only 2 ways I can think of, with the former being much more efficient.

 

[Schmide]

Most undos I've implemented have been stack based. Basically you take a base state and reapply all the changes minus the ones you remove.

 

[Cogman]

Most undos I've implemented have been stack based. Basically you take a base state and reapply all the changes minus the ones you remove.

Yep, that is how I would go about it, Treat data as a blob of information with several transformations applied to it. Hard limit the number of transformations that can be made. Save off spillover, and reapply transformations every time a change is made.

You just need to make sure that none of your transformations change external state and then undo becomes a snap.

 

[BrightCandle]

The classical way this is done is with the Command pattern where there is a do and undo that based on the data the command carries can be undone.

Its also possible to do this by storing previous states of the program, typically this is done with immutable data structures that can efficiently share parts that don't change.

Either approach gets the job done, Command pattern is more for mutable state programs and versioned history approach is for immutable data structures.

 

[Maximilian]

So with storing states, the object that represents the current page of a word document would be copied and stored in some collection before every state changing action the user takes. Subsequent actions that cause change also cause each version of the object to be stored in the same collection.

Man that's beautiful.

 

[Markbnj]

So with storing states, the object that represents the current page of a word document would be copied and stored in some collection before every state changing action the user takes. Subsequent actions that cause change also cause each version of the object to be stored in the same collection.

Man that's beautiful.

Similar to the way a version control system works, but I think the command pattern is more common because it's a lot more efficient, especially for data that is not intended to be durable.

 

[BrightCandle]

Word is definitely using a mutable data structure. So I strongly suspect its undo functionality is based on commands. The simplest one being a character pressed on the keyboard.

The way that would work is likely as follows. A key is pressed and a new KeyCommand object is made where the data is the character and the location in the document is also stored. The KeyCommand object will be passed to the Commander which will run the do against the the document and store the object in the head of a list.

On the press of undo the Commander will pick up the head object and run the undo, then add the Command (in this case a KeyCommand but its the interface that the Commander cares about) to the redo list.

I think the best description of this pattern for this purpose is at the beginning of the Objects elements of reusable software design patterns by Gamma et al. The beginning chapter is the design of a word like editor and uses a variety of patterns and this is one of the things it covers.

 

[Cogman]

Similar to the way a version control system works, but I think the command pattern is more common because it's a lot more efficient, especially for data that is not intended to be durable.

Of course it depends on your structure, but IIRC, photoshop uses the Immutable data + transformers method. So as far as performance goes, it can be pretty snappy even with semi large amounts of data.

I mean, if you are working with < 10mb of data, then the immutable method would be pretty snappy on pretty much everything.

 

[Cogman]

So with storing states, the object that represents the current page of a word document would be copied and stored in some collection before every state changing action the user takes. Subsequent actions that cause change also cause each version of the object to be stored in the same collection.

Man that's beautiful.

I was thinking more along the lines of having a list of transformations, rather than saving the state at the end of each transformation, you pass a copy of the data to the transformers and then modify that copy as it goes through each transformer and present the end result to the user. If they want to undo any transformer, you simply rerun the transformation process with one less transformer, if they change something you add a new transformer. If you have too many transformers, you save state after the oldest transformer on your golden copy of the data.

This depends on your transformers being relatively quick (which they usually are). You would only save the state after each transformation if your transformer was particularly slow.