5 ms·

Serialization-Based Undo

76 points by prideout 5y ago

catern 5y ago
This is cool, but I don't understand the justification for why a more traditional "just store a sequence of events" undo system wasn't possible. As the author says in the post on the scripting system, the game scripts access virtual interfaces. Those could just record the methods called before forwarding them on - doesn't matter that the scripts make arbitrary method calls. It seems to me that there's nothing inherent to "the level script is arbitrary code rather than a list of commands as data" that makes that style of undo impossible.
- qsort 5y ago
  Well, yes, it does matter, because there's no guarantee that you can safely compute and execute the inverse operation. Same reason debuggers don't have a "step back" button. Strictly from a computation theory point of view, you could obviously store a list of executed opcodes and undo by replaying up to the (N-1)th operation, but I think they want to avoid the overhead.
  - johnday 5y ago
    "Forward replay" was actually the mechanism that Tabletop Simulator originally used for its undo system. After around 30 minutes of playing games in the simulator, pressing "Undo" would hang the client and likely disconnect most people connected to the server. It's not a great way to implement undo.
- royjacobs 5y ago
  It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. This then grows more complex if items have parent-child relationships and you also need to start storing all the information required to completely reinstate all the children, possibly also in the same order they were originally created in. You know, tricky.
  - jcelerier 5y ago
    > It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. yep, as soon as you have an object graph serialization is the only way to stay sane. Anecdotally that's what I do in https://ossia.io https://ossia.io with Qt's QDataStream and serializing / deserializing hundreds of steps is pretty much instant. A nice benefit of it is to be able to provide a "restore on crash" feature: the undo/redo stacks get saved to disk and can be used to go back to the exact state the user left if a crash happens
- nyanpasu64 5y ago
  I came up with a "almost too clever" way to reduce the tedium of writing command objects. Most command APIs expect you to write a separate redo and undo method, and possibly even a separate "apply" method. Instead I created a `BaseEditCommand` interface where each command object subclass precomputes the new state of the altered portions of the document. When the command is applied, the undo system calls `apply_swap(self: &mut dyn BaseEditCommand, &mut Document)` which swaps the Document's old state with the BaseEditCommand's new state. To undo the change, you merely call `apply_swap` a second time, which swaps the old state from the edit command back into the document (saving the document's new state in the edit command). To redo the change, you merely call `apply_swap` a third time. It has the same tradeoffs as the usual command/action pattern (richer information about what was changed, but you have to implement a new type for each operation, and might end up copying a lot of memory anyway). However it's a lot easier to implement each command (less boilerplate, somewhat lower risk of implementing undo/redo incorrectly and altering state). As a bonus, apply/undo/redo perform zero memory allocations, because they only swap data, not copy or destroy it. One arguable downside is that you can't transplant the same command from one point in the history to another (but most undo commands in traditional applications, as opposed to VCS systems or nonlinear editors, aren't built to do that either). And I'm not sure my "can_merge" system (which merely drops commands rather than bundling or intelligently combining their contents) was a good idea, since all mergable commands must alter the same state. API: https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/edit_common.h#L29 https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/...
hoseja 5y ago
>but since I’m not a fan of C++ streams, it doesn’t use them internally Nobody does, it's one of the worst mistakes of C++.
- formerly_proven 5y ago
  Unfortunately many C++ tutorials mention or use iostreams which makes it look like it's a good idea to use iostreams.
steeleduncan 5y ago
It is interesting to compare this to Jonathan Blow's talk on the rewind system in Braid [1]. This stores complete game states using a compression library to keep memory under control, whereas Braid stored a combination of keyframes, and diffs from those keyframes, to avoid using a compression library. [1] https://www.youtube.com/watch?v=8dinUbg2h70 https://www.youtube.com/watch?v=8dinUbg2h70
rocqua 5y ago
Essentially the idea here is not to muck about with diffs or event / command based sourcing. Just store each internal state you might want to recover, in full. Except use compression to store the states you want to recover. In this article, the compression is done based on the 'initial state'. I imagine there is flexibility on maybe 'checkpointing' some states once the difference becomes to big. Maybe do the compression not with a prefix of the 'initial' state but with a prefix of the entire undo history. All this requires is halfway efficient serialization / deserialization implementation, and access to Zstandard (I guess other compression algorithms also work). I think the key trick here is that, if you can serialize to bytes, you can just use compression methods as a replacement for storing diffs or other complicated methods for de-duplicating data. This could be a really powerful method to really easily keep a state history without high performance cost. From the developer p.o.v. its like you have each previous state at your fingertips. Whilst in reality the compression ensures it is stored efficiently.
- devit 5y ago
  This only works if the commands update only a few bytes. This would not work, for instance, in an image editor with an "adjust brightness/contrast" command since that changes the whole image. It's also inefficient since you need to examine the whole state to generate the diffs, so in general it's not a great solution.
  - saurik 5y ago
    What isn't the alternative you are comparing against, though? Keeping a command history from the start of time and re-executing all of it to undo one step? You can't just "undo" a brightness/contrast change as that operation isn't perfectly "reversible" (if this isn't obvious, drag the contrast so low that the entire image turns grey and now try to "undo" that given only what you did and a fully-grey buffer). If you keep checkpoints so you can replay smaller segments, that's effectively the same thing as what this is suggesting (with respect to what has to be implemented and the overall scale of storage required), but with a checkpoint for every step (which is a constant divisor).
Strilanc 5y ago
This is the design I also usually use for undo/redo. Actually for small interactive editors I like to go further and make it so that anytime you do anything the program serializes its state and loads it back in. This is sometimes too costly but has unexpected reliability benefits. It makes sure your serialization code is well exercised, it ensures most of your program states are linkable/nameable, and also it's sort of like every time you do anything you're restarting the program. There's much less implicit state that can cause problems. And as a fallback if you do get the program into a bad state you can just hit undo and you're back into a good state.

76 points by prideout 5y ago

This is cool, but I don't understand the justification for why a more traditional "just store a sequence of events" undo system wasn't possible. As the author says in the post on the scripting system, the game scripts access virtual interfaces. Those could just record the methods called before forwarding them on - doesn't matter that the scripts make arbitrary method calls. It seems to me that there's nothing inherent to "the level script is arbitrary code rather than a list of commands as data" that makes that style of undo impossible.

qsort 5y ago
Well, yes, it does matter, because there's no guarantee that you can safely compute and execute the inverse operation. Same reason debuggers don't have a "step back" button. Strictly from a computation theory point of view, you could obviously store a list of executed opcodes and undo by replaying up to the (N-1)th operation, but I think they want to avoid the overhead.
- johnday 5y ago
  "Forward replay" was actually the mechanism that Tabletop Simulator originally used for its undo system. After around 30 minutes of playing games in the simulator, pressing "Undo" would hang the client and likely disconnect most people connected to the server. It's not a great way to implement undo.
royjacobs 5y ago
It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. This then grows more complex if items have parent-child relationships and you also need to start storing all the information required to completely reinstate all the children, possibly also in the same order they were originally created in. You know, tricky.
- jcelerier 5y ago
  > It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. yep, as soon as you have an object graph serialization is the only way to stay sane. Anecdotally that's what I do in https://ossia.io https://ossia.io with Qt's QDataStream and serializing / deserializing hundreds of steps is pretty much instant. A nice benefit of it is to be able to provide a "restore on crash" feature: the undo/redo stacks get saved to disk and can be used to go back to the exact state the user left if a crash happens
nyanpasu64 5y ago
I came up with a "almost too clever" way to reduce the tedium of writing command objects. Most command APIs expect you to write a separate redo and undo method, and possibly even a separate "apply" method. Instead I created a `BaseEditCommand` interface where each command object subclass precomputes the new state of the altered portions of the document. When the command is applied, the undo system calls `apply_swap(self: &mut dyn BaseEditCommand, &mut Document)` which swaps the Document's old state with the BaseEditCommand's new state. To undo the change, you merely call `apply_swap` a second time, which swaps the old state from the edit command back into the document (saving the document's new state in the edit command). To redo the change, you merely call `apply_swap` a third time. It has the same tradeoffs as the usual command/action pattern (richer information about what was changed, but you have to implement a new type for each operation, and might end up copying a lot of memory anyway). However it's a lot easier to implement each command (less boilerplate, somewhat lower risk of implementing undo/redo incorrectly and altering state). As a bonus, apply/undo/redo perform zero memory allocations, because they only swap data, not copy or destroy it. One arguable downside is that you can't transplant the same command from one point in the history to another (but most undo commands in traditional applications, as opposed to VCS systems or nonlinear editors, aren't built to do that either). And I'm not sure my "can_merge" system (which merely drops commands rather than bundling or intelligently combining their contents) was a good idea, since all mergable commands must alter the same state. API: https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/edit_common.h#L29 https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/...

hoseja 5y ago

>but since I’m not a fan of C++ streams, it doesn’t use them internally Nobody does, it's one of the worst mistakes of C++.

formerly_proven 5y ago
Unfortunately many C++ tutorials mention or use iostreams which makes it look like it's a good idea to use iostreams.

steeleduncan 5y ago

It is interesting to compare this to Jonathan Blow's talk on the rewind system in Braid [1]. This stores complete game states using a compression library to keep memory under control, whereas Braid stored a combination of keyframes, and diffs from those keyframes, to avoid using a compression library. [1] https://www.youtube.com/watch?v=8dinUbg2h70 https://www.youtube.com/watch?v=8dinUbg2h70

rocqua 5y ago

Essentially the idea here is not to muck about with diffs or event / command based sourcing. Just store each internal state you might want to recover, in full. Except use compression to store the states you want to recover. In this article, the compression is done based on the 'initial state'. I imagine there is flexibility on maybe 'checkpointing' some states once the difference becomes to big. Maybe do the compression not with a prefix of the 'initial' state but with a prefix of the entire undo history. All this requires is halfway efficient serialization / deserialization implementation, and access to Zstandard (I guess other compression algorithms also work). I think the key trick here is that, if you can serialize to bytes, you can just use compression methods as a replacement for storing diffs or other complicated methods for de-duplicating data. This could be a really powerful method to really easily keep a state history without high performance cost. From the developer p.o.v. its like you have each previous state at your fingertips. Whilst in reality the compression ensures it is stored efficiently.

devit 5y ago
This only works if the commands update only a few bytes. This would not work, for instance, in an image editor with an "adjust brightness/contrast" command since that changes the whole image. It's also inefficient since you need to examine the whole state to generate the diffs, so in general it's not a great solution.
- saurik 5y ago
  What isn't the alternative you are comparing against, though? Keeping a command history from the start of time and re-executing all of it to undo one step? You can't just "undo" a brightness/contrast change as that operation isn't perfectly "reversible" (if this isn't obvious, drag the contrast so low that the entire image turns grey and now try to "undo" that given only what you did and a fully-grey buffer). If you keep checkpoints so you can replay smaller segments, that's effectively the same thing as what this is suggesting (with respect to what has to be implemented and the overall scale of storage required), but with a checkpoint for every step (which is a constant divisor).

Strilanc 5y ago

This is the design I also usually use for undo/redo. Actually for small interactive editors I like to go further and make it so that anytime you do anything the program serializes its state and loads it back in. This is sometimes too costly but has unexpected reliability benefits. It makes sure your serialization code is well exercised, it ensures most of your program states are linkable/nameable, and also it's sort of like every time you do anything you're restarting the program. There's much less implicit state that can cause problems. And as a fallback if you do get the program into a bad state you can just hit undo and you're back into a good state.