Serialization-Based Undo | Hacker News Reader

Serialization-Based Undo

prideout.net

76 pointsprideout21 comments

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.

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.

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).

> Keeping a command history from the start of time and re-executing all of it to undo one step?

Someone needs to play around with NLE video editors. Because yes, that's what they basically do.

The video editing steps are all items on the "timeline". When you hit the "render" button, the computer goes into overdrive: spinning up a bunch of threads (maybe even GPU-kernels) and actually calculates everything.

What you see in the preview-screen doesn't always match the final render. The preview-screen is just a quickie-calculation, much like how 3d programs (ex: Blender) have a realtime renderer (see Eevee) vs the offline, more accurate renderer (see Cycles).

---------

From an NLE perspective: the GUI is basically a glorified editor of commands.

If photo editors have an internal representation of all operations in the history of the document and the ability to recompute them all up the a given point, and they DON'T expose this to the user except through the undo button, that's a pretty big failure of design.

I know some of them let you see the undo history and let you pop (and maybe reorder items) that aren’t at the top of the stack.

Micrografx Picture Publisher allowed that more than 20years ago, but it is the only image editor I know of that did this

Apple’s Aperture is another one.

The GEGL graph will be exposed to GIMP users any year now...

Reexecuting it all is the simplest strategy if you don't need to undo often or the performance is acceptable anyway.

But in general, every command would generate an "undo record" with information to undo it.

In case of the brightness/contrast change you can do that by undoing in the naive way and then storing the difference between the "naively undone" image and the origignal version, compressed, in the undo record.

In general the undo record will only be large if you lose a lot of information, and then there won't be as much information left to lose and thus the next undo records won't be able to be so large, so overall the total size of the compressed current image and undo record will amortize and be in the range of the size of the original image plus the command description.

For example, once you turn the image fully grey, then all per-pixel transformations will be either be reversible or the undo record will compress to the effect on one pixel since it's the same for all the image.

This doesn't hold however if you also have operations that create information (e.g. something that draws a pseudorandom image with you then adjust contrast on, resulting in a pseudorandom undo record that you can't compress with standard techniques): in that case I think reexecuting the command history is the only space-efficient solution that doesn't require coding for the specific application.

This "undo record" sounds like (essentially) the same thing as storing the (compressed) diff from the current state to the prior state which you were arguing against. If you have an operation that is changing a lot and isn't reversible, either you are reexecuting from the beginning of time (which particularly for image editing would be ridiculous: even a single operation on the image is often annoyingly slow, much less suddenly doing tons as you rapidly make changes and then undo back through them) or you are storing checkpoints at some frequency in the form of diffs on the full serialized state (which seems to be what you are returning to re-suggest anyway).

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

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.

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.

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.

> 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 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

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.

"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.

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/...

>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++.

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

Reply on news.ycombinator.com