Hacker News Reader

Comment by joeax | Hacker News Reader

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.

View on HN

> 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

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

The command pattern only describes the encapsulation of an imperative, but not a complete undo/redo stack.

Technically, yes, but every book I read that talked about the Command pattern did so in the context of an undo-redo system

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

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

A modal editor is not necessarily less efficient in keystrokes than one using control keys; modal just means you don't have to hold your control keys down while completing the command.

Using keyboard commands is often faster than pointing with a mouse, if you take advantage of structures in the text; e.g. "select everything inside the parens." And if you're doing that all day, it becomes second nature to build macros on the fly.

Less efficient in keystrokes? who said anything about that?

If you use a keyboard-based editor, presumably one that takes fewer keystrokes is a better UI, other things being equal. (There's also learning curve to consider but everyone has their own tradeoff on that.)

Of course there are also mouse-based editors, which my second paragraph addresses.

Musescore (open-source music notation software) uses this pattern, for those interested... but not in a particularly DRY or stable way (so much duplicated logic!). I'm sure other open-source examples exist, but this should give you an idea:

https://github.com/musescore/MuseScore/blob/master/libmscore...

https://github.com/musescore/MuseScore/blob/c4af0c22bc90a6ba...

http://gameprogrammingpatterns.com/command.html

Here's how I do it (interestingly, on a Qt-based art software too :p )

https://github.com/OSSIA/score/blob/master/base/lib/core/com...

https://github.com/OSSIA/score/blob/master/base/plugins/scor...

Also once your commands are serialized you can send them over the network for distributed edition

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.

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.

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.

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

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.

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

Well I wasn't creating Photoshop :) this really was the easiest solution for our needs.

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.

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.

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.

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.

Do you mean 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

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.

You need a reference to each state, but because the components are themselves immutable you can share objects. For example a Document may contain many Blocks which contain many Lines. Changing a Line means replacing that object, its parent Block and its parent Document, but references to everything else can be copied over.

A list zipper? https://en.wikipedia.org/wiki/Zipper_(data_structure)

An advantage of storing operations instead of using immutable data structures is that with them you can implement region-based undo.

> and you have some function that can re-build the current state from that list...

You can be far mor efficient than that. The trick is to use immutable data structures to represent your state. When something changes, return a new state. Parts of the state that didn’t change are still referring to chunks from the previous state, so it’s actually sharing most of the memory from the previous state.

There are data structures in libraries in different languages that support this idea, for example system.collections.immutable in .NET. Anything you build in Erlang or Elixir will basically automatically do this. (As an aside, Erlang IOlists are a related concept to the piece tables the article talks about.)

Using this approach you don’t actually have to rebuild a previous or redo state, you just keep a list of states and move between them for undo and redo.

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.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com