6 ms·

I was tasked with writing a undo/redo framework for an existing client app a few years back. It's basically an HMI system (a tool typically used in manufacturin

by joeax 9y ago

I was tasked with writing a undo/redo framework for an existing client app a few years back. It's basically an HMI system (a tool typically used in manufacturing to visually model an industrial system) that used SVG+HTML. I could have used a piece table concept (didn't know it was called that), storing a diff fragment of what was changed (using a library like diff-match-patch). Unfortunately, there was more than a text-representation that needed to be maintained so it didn't work initially. I wound up using a stack-based architecture that pushed operations stored as functions onto a main stack then its reverse operation onto an undo stack. Once I worked out the state management problems it worked out quite well. I've always wondered what other approaches others have done if tasked with a similar problem.

wila 9y ago
Having written an undo/redo stack for a graphical editing component. That's pretty much what I did. Maintain a redo stack that holds the operations and parameters. An undo then became going back to the original image plus a redo of everything on the stack minus the last operation. Rather simplistic, but it worked well for our purposes and was easy to implement.
- default-kramer 9y ago
  I do this all the time when I write a game which can easily be described as a sequence of discrete moves. Chess is a good example, and games with physics engines are the opposite. As you said, the Undo operation is just "start with the initial board and apply N-1 moves to get the current state." This plays nicely with immutability too.
  - terminalcommand 9y ago
    Starting with the initial board and applying n-1 moves should be significantly slower than using immutable data structures. I don't have much experience in algorithms but I think O(1) trumps O(N-1) :).
    - wila 9y ago
      The problem with graphics though is that some graphical operations are destructive so you can't just undo the operation. In order to undo without a redo list, you would have to keep a complete graphical representation of the image and each operation. With images the memory usage goes up very quickly in that case, copying large blocks of memory on each operation makes your image editing slow down too.
- beached_whale 9y ago
  I saw a video and Photoshop used to use the command pattern but moved to just saving complete images(mostly) and it was much simpler and fast
  - wila 9y ago
    Well I wasn't creating Photoshop :) this really was the easiest solution for our needs.
  - Sharlin 9y ago
    Lightroom, on the other hand, stores only the edit history by its very design (non-destructive editing). Though I guess that during editing it may cache intermediate results to speed things up.
jcelerier 9y ago
> I wound up using a stack-based architecture that pushed operations stored as functions onto a main stack then its reverse operation onto an undo stack. Once I worked out the state management problems it worked out quite well. that's quite common: it's called the Command pattern. https://en.wikipedia.org/wiki/Command_pattern https://en.wikipedia.org/wiki/Command_pattern Another common approach is Memento (basically, "save everything") A nice thing that can be added is a pair of serialization / deserialization functions for the state needed for your commands. This way you can save them regularly and restore them if a crash or something like this happens ; the user can then continue to work while keeping its undo / redo stack
- manmal 9y ago
  The command pattern only describes the encapsulation of an imperative, but not a complete undo/redo stack.
  - jcelerier 9y ago
    Technically, yes, but every book I read that talked about the Command pattern did so in the context of an undo-redo system
- flukus 9y ago
  > A nice thing that can be added is a pair of serialization / deserialization functions for the state needed for your commands. I wonder if this was the origin of modal text editors. Maybe they were designed for machine/programmer convenience more than machine convenience originally.
  - ZenPsycho 9y ago
    they were designed around the constraints of slow teletype machines and slow 300 baud modems. they make no sense as a UI until you take into account how long you used to need to wait for a computer to respond
    - 9y ago
laythea 9y ago
This task becomes more difficult once you need to undo calculations performed on the GPU. Not sure I will encounter a nice way to reverse those operations without numerical inaccuracies.
- duncan_bayne 9y ago
  Can you not store the result of those calculations, as a means of "reversing" them? As someone who's not directly programmed GPUs before, they look quite intimidating and opaque; certainly, that's the sense I get from HN threads and the like.
  - kobeya 9y ago
    I believe this is what graphics tools do, for other reasons as well. Each operation creates a new layer and what you see is the dynamically rendered composition. This lets you do things like adjust the strength / intensity of the effect as well, by changing the weight of the layers.
  - laythea 9y ago
    I wouldn't call GPU intimidating, more a royal pain in the butt! :) The approach of simply saving state doesn't work very well due to performance reasons. I.e. If user is "editing" some of 5-10 million+ vertices, via some sort of brush tool that runs modifications to vertices through a GPU shader, then saving the state becomes a big no-no due to the huge delay in copying the entire current state of the vertices back to the CPU. This results in a short (but unusably irritating) pause, before the user can use the editing brush. Well just copy the bits you are interested in you may say, but there is no way I have came across to save only regions of the vertex buffer that the user "touches". There may be some fan-dangled way to save the "operations" not data, and then run them through a "reverse" shader, but I have a feeling that is overly complex and subject to inaccuracies. Darn, GPU's are fast though.
kobeya 9y ago
At the cost of doubling the state size you can maintain an undo skip list to get log N performance for long undos. But that is useless for he common case of stepping back one at a time.
ridiculous_fish 9y ago
This is how NSUndoManager works in Cocoa, with the additional twist that recording the reverse operation is performed by actually invoking it on a proxy. Example: - (void)setTitle:(NSString *title) { [[NSUndoManager prepareWithInvocationTarget:self] setTitle:currentTitle_]; currentTitle_ = title; } This setTitle: method may be undone by calling setTitle: again with the old title. We actually send that to the undo manager, which records it. When the user invokes undo, the undo manager replays the message it was sent. setTitle again records how to undo the replayed operation, but this time it gets pushed onto the redo stack! What is nice about this approach is there is no need to manually reify commands (i.e. Command pattern). It's just a message send.
westoncb 9y ago
Anyone know if there is a best-practice immutable data structure variation here? The way I've thought about it is that if you store the entire sequence of operations which have occurred so far, and you have some function that can re-build the current state from that list, then you don't need any inverse operations. This means that undoing an operation is just removing the last operation performed from the operation list, and then rebuilding the state. This seems nice since you don't have to figure out inverse operations (which I've seen get tricky), but I imagine the performance penalty of having to store all operations and rebuild the entire state every time could be problematic in some cases. Then again, I imagine there are good standard optimizations for dealing with this kind of thing. One thing that occurs to me is that operations which 'cancel' each other could be sought out and eliminated before rebuilding the state. I'd be glad for any more information on the subject! Edit: more specifically I'm wondering if those optimizations do in fact exist, and if so what they are.
- throwanem 9y ago
  Seems like a fair fit for something like a Merkle tree. Do it properly and you could even save and load undo history with the file, treating external changes seen on load as new history states - which might be a nice feature to have.
- rawnlq 9y ago
  Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure or something more specific for this case? It's known how to only incur an O(1) cost in time and space for making a data structure persistent. So then you just need to keep a reference to all past versions of the data structure you might ever want to undo back to. EDIT: actually reading the wiki more carefully, I think they were talking about making a BST persistent specifically rather than any data structure. In that case looking at implementations such as rrb-vectors might be more interesting: https://github.com/clojure/core.rrb-vector https://github.com/clojure/core.rrb-vector
  - westoncb 9y ago
    That wikipedia article looks interesting. I guess the only thing more specific I'm wondering about is persistent data structures for undo/redo systems. But just knowing the name 'persistent data structure' is useful.
rdtsc 9y ago
I interned at a CAD/CAE company and our "cool" feature there was a history tree. I don't know maybe all of them do it today, but I remember being thoroughly impressed then, having only seen word and simple editor undo/redo before. Since we had all the visualization bits written, we reused them and displayed it as a tree and you'd try different approaches as branches by clicking between them to compare. I guess it was basically as a seeing the history graph of a git repo, but this was about 5 years before git was created.
ndh2 9y ago
I read that Blender initially didn't have undo. Saving to a file was quite fast because they used binary data. So what they did was save the scene to memory, then save again, and compute a diff for the undo queue.

by joeax 9y ago

wila 9y ago

Having written an undo/redo stack for a graphical editing component. That's pretty much what I did. Maintain a redo stack that holds the operations and parameters. An undo then became going back to the original image plus a redo of everything on the stack minus the last operation. Rather simplistic, but it worked well for our purposes and was easy to implement.

default-kramer 9y ago
I do this all the time when I write a game which can easily be described as a sequence of discrete moves. Chess is a good example, and games with physics engines are the opposite. As you said, the Undo operation is just "start with the initial board and apply N-1 moves to get the current state." This plays nicely with immutability too.
- terminalcommand 9y ago
  Starting with the initial board and applying n-1 moves should be significantly slower than using immutable data structures. I don't have much experience in algorithms but I think O(1) trumps O(N-1) :).
  - wila 9y ago
    The problem with graphics though is that some graphical operations are destructive so you can't just undo the operation. In order to undo without a redo list, you would have to keep a complete graphical representation of the image and each operation. With images the memory usage goes up very quickly in that case, copying large blocks of memory on each operation makes your image editing slow down too.
beached_whale 9y ago
I saw a video and Photoshop used to use the command pattern but moved to just saving complete images(mostly) and it was much simpler and fast
- wila 9y ago
  Well I wasn't creating Photoshop :) this really was the easiest solution for our needs.
- Sharlin 9y ago
  Lightroom, on the other hand, stores only the edit history by its very design (non-destructive editing). Though I guess that during editing it may cache intermediate results to speed things up.

jcelerier 9y ago

> I wound up using a stack-based architecture that pushed operations stored as functions onto a main stack then its reverse operation onto an undo stack. Once I worked out the state management problems it worked out quite well. that's quite common: it's called the Command pattern. https://en.wikipedia.org/wiki/Command_pattern https://en.wikipedia.org/wiki/Command_pattern Another common approach is Memento (basically, "save everything") A nice thing that can be added is a pair of serialization / deserialization functions for the state needed for your commands. This way you can save them regularly and restore them if a crash or something like this happens ; the user can then continue to work while keeping its undo / redo stack

manmal 9y ago
The command pattern only describes the encapsulation of an imperative, but not a complete undo/redo stack.
- jcelerier 9y ago
  Technically, yes, but every book I read that talked about the Command pattern did so in the context of an undo-redo system
flukus 9y ago
> A nice thing that can be added is a pair of serialization / deserialization functions for the state needed for your commands. I wonder if this was the origin of modal text editors. Maybe they were designed for machine/programmer convenience more than machine convenience originally.
- ZenPsycho 9y ago
  they were designed around the constraints of slow teletype machines and slow 300 baud modems. they make no sense as a UI until you take into account how long you used to need to wait for a computer to respond
  - 9y ago

laythea 9y ago

This task becomes more difficult once you need to undo calculations performed on the GPU. Not sure I will encounter a nice way to reverse those operations without numerical inaccuracies.

duncan_bayne 9y ago
Can you not store the result of those calculations, as a means of "reversing" them? As someone who's not directly programmed GPUs before, they look quite intimidating and opaque; certainly, that's the sense I get from HN threads and the like.
- kobeya 9y ago
  I believe this is what graphics tools do, for other reasons as well. Each operation creates a new layer and what you see is the dynamically rendered composition. This lets you do things like adjust the strength / intensity of the effect as well, by changing the weight of the layers.
- laythea 9y ago
  I wouldn't call GPU intimidating, more a royal pain in the butt! :) The approach of simply saving state doesn't work very well due to performance reasons. I.e. If user is "editing" some of 5-10 million+ vertices, via some sort of brush tool that runs modifications to vertices through a GPU shader, then saving the state becomes a big no-no due to the huge delay in copying the entire current state of the vertices back to the CPU. This results in a short (but unusably irritating) pause, before the user can use the editing brush. Well just copy the bits you are interested in you may say, but there is no way I have came across to save only regions of the vertex buffer that the user "touches". There may be some fan-dangled way to save the "operations" not data, and then run them through a "reverse" shader, but I have a feeling that is overly complex and subject to inaccuracies. Darn, GPU's are fast though.

kobeya 9y ago

At the cost of doubling the state size you can maintain an undo skip list to get log N performance for long undos. But that is useless for he common case of stepping back one at a time.

ridiculous_fish 9y ago

This is how NSUndoManager works in Cocoa, with the additional twist that recording the reverse operation is performed by actually invoking it on a proxy. Example: - (void)setTitle:(NSString *title) { [[NSUndoManager prepareWithInvocationTarget:self] setTitle:currentTitle_]; currentTitle_ = title; } This setTitle: method may be undone by calling setTitle: again with the old title. We actually send that to the undo manager, which records it. When the user invokes undo, the undo manager replays the message it was sent. setTitle again records how to undo the replayed operation, but this time it gets pushed onto the redo stack! What is nice about this approach is there is no need to manually reify commands (i.e. Command pattern). It's just a message send.

westoncb 9y ago

Anyone know if there is a best-practice immutable data structure variation here? The way I've thought about it is that if you store the entire sequence of operations which have occurred so far, and you have some function that can re-build the current state from that list, then you don't need any inverse operations. This means that undoing an operation is just removing the last operation performed from the operation list, and then rebuilding the state. This seems nice since you don't have to figure out inverse operations (which I've seen get tricky), but I imagine the performance penalty of having to store all operations and rebuild the entire state every time could be problematic in some cases. Then again, I imagine there are good standard optimizations for dealing with this kind of thing. One thing that occurs to me is that operations which 'cancel' each other could be sought out and eliminated before rebuilding the state. I'd be glad for any more information on the subject! Edit: more specifically I'm wondering if those optimizations do in fact exist, and if so what they are.

throwanem 9y ago
Seems like a fair fit for something like a Merkle tree. Do it properly and you could even save and load undo history with the file, treating external changes seen on load as new history states - which might be a nice feature to have.
rawnlq 9y ago
Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure or something more specific for this case? It's known how to only incur an O(1) cost in time and space for making a data structure persistent. So then you just need to keep a reference to all past versions of the data structure you might ever want to undo back to. EDIT: actually reading the wiki more carefully, I think they were talking about making a BST persistent specifically rather than any data structure. In that case looking at implementations such as rrb-vectors might be more interesting: https://github.com/clojure/core.rrb-vector https://github.com/clojure/core.rrb-vector
- westoncb 9y ago
  That wikipedia article looks interesting. I guess the only thing more specific I'm wondering about is persistent data structures for undo/redo systems. But just knowing the name 'persistent data structure' is useful.

rdtsc 9y ago

I interned at a CAD/CAE company and our "cool" feature there was a history tree. I don't know maybe all of them do it today, but I remember being thoroughly impressed then, having only seen word and simple editor undo/redo before. Since we had all the visualization bits written, we reused them and displayed it as a tree and you'd try different approaches as branches by clicking between them to compare. I guess it was basically as a seeing the history graph of a git repo, but this was about 5 years before git was created.

ndh2 9y ago

I read that Blender initially didn't have undo. Saving to a file was quite fast because they used binary data. So what they did was save the scene to memory, then save again, and compute a diff for the undo queue.