Design and implement a full-fledged undo-redo system

[alice-i-cecile]

[10:34 PM]Alice 🌹: I think that there's a lot of interesting and important complexity to tackle with undoing, and I really like the contextual / nested undo-redo + a trait based approach
[10:34 PM]Alice 🌹: But for now, a relatively simple trait will do
[10:36 PM]Alice 🌹: I'd also like to lean away from a snapshot-based approach if possible, and avoid a distinct storage (sorry @nth but I've worked with this and I found it very frustrating)
[10:36 PM]Alice 🌹: There's definitely a chance that we can't make that sort of design work, but I'm happy to cross that bridge when we get there

This is a followup to #2, which is a simple design to get us started.

Cross-posted from Discord.

[MiniaczQ]

related bevyengine/bevy#15350

[rewin123]

Since we now have milestones corresponding to the roadmap, I took the liberty of assigning a milestone to this PR. Feel free to change the assigned milestone, as "I have no power here"

[Atlas16A]

Useful Material for those tackling this problem: https://developer.blender.org/docs/features/core/undo/

[rewin123]

I have collected all the Undo/redo requirements discussed in this md file. I propose to edit it until we come to some design, which basically everyone will agree with https://hackmd.io/@bevy/r1RXR5DC0

[viridia]

So the first half of the document looks pretty good. I would possibly add some detail about the relationship between "undo" and "redo":

• Adding a new undo action pushes onto the undo stack and clears the redo stack.
• Undoing an action pops an undo action off the undo stack and pushes a redo action on the redo stack.
• Redoing an action pops an action off the redo stack and pushes an action on the undo stack.

Also the undo stack has a max size.

(I tend to think of these things as a "stack" rather than a "timeline", but that's just terminology).

I think the second half of the doc is more complex than it needs to be.

First, most apps have a single undo stack, with a special case for text input fields which have their own dedicated stack.

For apps that have multiple "documents", there is an undo stack for each document. These aren't nested, nor do they overlap in anyway - undoing in one doc has no effect on other docs. When the user selects the undo menu, which undo stack gets invoked is determined by the currently selected document, and only one document can be selected at a time, so it's always unambiguous.

VSCode is one of the few apps that has a more complex undo structure: the undo stack for the folder pane is separate from the undo stack for the individual document views. However, you can fit this into the previous model if you consider the directory hierarchy to be a separate "document": otherwise the rules are the same. That is, if you select a file in the tree view, and choose the undo action, then the undo stack that gets used is the tree view undo stack. The only special case is if a doc gets deleted, in which case the corresponding document window is closed - but this would be the same if we deleted the file from the console, so it's not a special case.

This, BTW, gets into the whole nature of "selection" which dates back to the original Mac Human Interface Guidelines, the rule that selections can't cross contextual boundaries: you can select multiple characters in a document, or you can select multiple documents, but you can't select both characters and documents at the same time. Otherwise it would be too confusing.

So in other words, except for the special case of text input, none of these undo contexts are "nested", and they don't interact with each other. I think this is an important point, because building a system with independent parallel undo stacks is a much simpler problem than building multiple contexts which interact with each other.

I also don't think it's important for editor settings to be undoable, unless they are really complex. The vast majority of apps don't support undoing of settings, because settings are pretty simple, and it's easy to change your mind. Like, if you are setting the audio volume, you really don't need a way to undo that - just set it again.

[rewin123]

Yes. The second part of the document is over-complicated. I like the idea of purely separate undo/redo lines for each document. Without using DAG, since I've been thinking about it for a week now, I can't think of a really good use for it. (Although it was discussed and seemed like a good idea at the time of the discussion). I will then rewrite the section and cut out DAG since I don't like it now either.

[rewin123]

The editor settings can and will get complicated over time, and adding undo/redo for them is easy. So I don't see any obstacle to implementing undo/redo in the editor settings window.

[rewin123]

I think we can highlight in the document that one and only one undo/redo time line can be active. And each time line is bound to a specific scene/document or widget or window.

[viridia]

Also, I want to talk about "timeline collapsing", which I call "edit coalescing" or "aggregate mutations".

An example is typing in a text editor. When you undo, you don't want to undo one keystroke at a time, but in larger gulps.

For an app like a text editor, the individual key insertions are delineated by "breakpoints". Any non-typing action, such as moving the cursor, selecting text, cut and paste, and so on, is a breakpoint. Depending on the editor, inserting a line break can also be a breakpoint. All the keys inserted between breakpoints are combined into a single undo action. In other words, the mutations are coalesced.

There are several approaches for implementing this. One is to have explicit "start action" and "end action" operations, and record all of the individual edits that happen between them. However, this isn't necessary for most edit actions, which consist of a single mutation. For example, cut & paste are atomic and transactional - you can't undo part of a paste, it's all or nothing.

A different approach is to allow certain undo stack entries to be "amended" after they have been pushed onto the stack. For example, when typing, each keystroke appends to the undo record on the top of the stack - but only if the top of the stack has a "insert keystroke" undo record. If it's a different kind of undo record, such as "make bold", then typing a key creates a brand new undo action instead of amending the old one. However, in order for this to work, we need a mechanism for downcasting the undo records so that we can tell whether the types match.

Once an undo record is no longer on top of the undo stack, it can not be amended any more.

Now, all this being said, my editor doesn't support amending because it doesn't need it. It doesn't have any fine-grained edit actions like typing, so all undo actions are atomic.

[Niashi24]

We might also consider having our Undo/Redo trait require serialization/deserialization with something like typetag.

The main benefit is that we can deserialize the undo(/redo) stack upon opening the project which would allow users to easier get back into their workflow. Additionally, if the editor crashes at any point the user won't lose their workflow.

We could either serialize the stack every time it changes, which would cover both cases (on user exit or on editor crash), or just on when the user exits the editor and use a panic hook for crashes.

[alice-i-cecile]

FYI, we've implemented this trait serde over in LWIM. It's not fun, but it is feasible.