Hacker News Reader

Comment by lolive | Hacker News Reader

Not sure it is off-topic or not, but I wonder what resources it would contain to help design a software with undo/redo feature.

View on HN

A Merkle-tree data structure + an append only log with checkpoints + a command processor would provide a basic foundation.

Your data can be represented in a Merkle-tree. You provide operations add-node, delete-node, move-node etc., on the Merkle-tree and build a command processor that takes as input a checkpointed Merkle-tree snapshot (could be empty when you start) and a log of operations (essentially an sequence of operations). The command processor then applies the series of tree operations in the log to build the final state of the tree. The special checkpoint operation saves a snapshot of the Merkle-tree.

This basic set of operations should allow you to do unlimited undo/redo/transaction playback capabilities.

Also see: Command Pattern, https://en.wikipedia.org/wiki/Command_pattern

Simple. For every operation performed by the user, you push a function to the end of a list that undoes that operation. When the user presses undo, you pop the function from the end of the list and call it.

check out emacs' undo-tree for a cool implementation

https://www.dr-qubit.org/undo-tree/undo-tree.txt

Emacs’s undo system is quite frankly amazing. Not only can you recover any state through an arbitrary number of undo and redo operations, but you can also localize the undo/redo operations to a selected region of the buffer.

It’s the number one feature I miss when I’m using another editor.

Am I missing something or would it just need to be a doubly linked list? It really depends on your program state being… stateful (so you can navigate forwards and back consistently)

If you store the total application state for each step then it's simple, but consumes lots of memory.

If you want to store something more like a diff, there are choices. For example, you could have code to undo each operation, but you can also implement undo by going back to some checkpoint and then recomputing all operations between the checkpoint and now. Latter consumes more CPU, but comparable memory and a lot less code surface for bugs.

If you use persistent data structures, you can store the total state, and you'll get deduplication of the common parts, which brings down the memory usage to a more reasonable amount. This is what git does essentially, which gets you O(1) checkout to arbitrary steps in the future/past. This also means you don't need to design/pick a diffing algorithm, which you would be locked into (since changing the diffing algorithm would mean you couldn't consume old diffs).

Git does store deltas when packing objects because storing all distinct objects as-is would be too inefficient for large repos. This isn't the same text diffs as shown to the user but there is still a diffing algorithm that all future git versions need to support (well, at least the patch counterpart).

Reply on news.ycombinator.com