Undo/redo system

[inact1v1ty]

I think it is the time for blackjack to have an undo/redo system. I really believe that an undo/redo system should be in the core architecture part of a program/engine.

The reason behind such belief is the I have an example of thinking about such system from the start vs adding it "somehow" later: Unity and Ventuz Designer. You probably know Unity - a robust and popular game engine. Ventuz is a software mainly for interactive installations and some related artsy stuff.

Both tools have user code in C# (so they are able to diff structs at runtime and etc). There are some differences - Ventuz is written completely in C#, without C++ core, and mainly uses graphs and not code (just like blackjack with Lua being behind the scenes most of the time except "code" nodes).

Unity has the undo/redo system integrated in the inner core of the language - it is closely coupled with the serialization system. Even when you create new editor windows you just need to tell it "I will do some undoable things in this func, track it as 'Undo My Super Cool Action'" - which is really nice. See example here.

Ventuz on the other hand seems to have neglected the importance of such a system. As a result the system doesn't track some actions and you never know whether it will for the next thing you do. So, you can't rely on it when you work - maybe you will do an important mistake exactly when it fails to help you. Most of the time when we worked with Ventuz we dropped to the pattern of "save the project at a state you like", "do some things without pressing Ctrl-S", "save the project only when you like its state again". I personally think this is a very important usability concern.

That said, I think that it is time to integrate undo/redo into blackjack, tying it to core stuff like parameters and node state (position, connections) while we can do it easily.

I am willing to volunteer and work on this task, but because it involves messing architecture I need your collaboration and advice @setzer22 to keep it in your vision. I plan to split it in several PRs as we will come up with the way to implement it. Sadly I have good experience only with Unity's system, but I think that it will be enough to create blackjack one with your vision.

[setzer22]

This is spot-on! I totally agree blackjack needs undo/redo, and I'm also a strong believer that something like this should be designed into the core of the application. Things designed after the fact never end up feeling as good. My excuse is that my bandwidth is limited, and I have mostly been focusing on the engine part of blackjack (the component that executes the graph and builds the meshes), so the UI has been lagging behind in UX features.

I agree it's time to think of an undo/redo system 👍 and I'd love to have extra hands on this :) I am not particularly attached to the architecture of blackjack_ui (which is where the undo/redo system would live), so I am open to any suggestions.

we dropped to the pattern of "save the project at a state you like", "do some things without pressing Ctrl-S", "save the project only when you like its state again". I personally think this is a very important usability concern.

This sounds all too familiar. I am currently doing this with blackjack when prototyping and I don't like it 😬 Lack of copy-paste for nodes is the other big UX issue right now.

Alright, so I'm in! Is there anything specific you need my input on right now?

[inact1v1ty]

I am glad to hear that you feel the same way about this feature! I think I will study the blackjack_ui codebase thoroughly and come up with a design draft to discuss 🙂

[setzer22]

Hi @inact1v1ty! Any news on that? No rush at all, just curious 😄

Please make sure pull from the latest changes from main. I just merged #62, which was a big PR and includes a major refactor simplifying lots of things in the blackjack_ui <-> blackjack_engine interaction.

[inact1v1ty]

Hi @setzer22! Just checked #62 and it is really awesome!

As of now, I'm (very?) slowly tackling #23 🙂 It's hard to get free time sometimes sadly, but I am very committed to continue contributing to this amazing software whenever I have an opportunity 🙂

After finishing #23 and getting your review I will finally get to the undo/redo one!

[setzer22]

Thanks @inact1v1ty! 😄 Glad to hear these PR notes reach people. Sometimes it's hard to measure if anyone reads them 😅. I'm currently working on a more traditional release workflow so I can do actual releases. Already managed to get an automated CI workflow for releases, so right now I'm doing a bit of general cleanup before actually publishing my first batch of binaries 😄

As of now, I'm (very?) slowly tackling #23 🙂
No rush! 😄 Take your time

After finishing #23 and getting your review I will finally get to the undo/redo one!

I've been thinking about potential ways to implement undo/redo as of late. My first (very informal!) usability test revealed most people will intuitively reach for Ctrl-Z (who would've thought! 😅), so it made me realize all the more that we need this.

I wanted to ask what you had in mind for undo/redo. I agree this should be part of the design from early on, and thankfully it's not too late. I don't mind if the feature takes a while, but I want to at least make sure I don't start shifting things in the wrong direction.

When I think of an undo system, what I have in mind is the traditional approach: A Command-like pattern, representing each possible action the UI may perform, with both a way to apply it and a way to undo it. By storing these commands in a stack-like data structure, you can undo (and also redo) them simply by running their "apply command" and "undo command" methods.

Still, there are some things that are not 100% clear to me, like what to do with parameter editing. Take for instance a user dragging a gizmo or a value slider in a node. You certainly don't want to store each of the tiny increments as an undoable action. Rather, you want to apply changes automatically, and then once the action ends (e.g. the user releases the mouse from the gizmo, the user stops dragging the slider...), store the full interaction as an undoable command. I can certainly think of ways to implement this, but I don't know if there's a more elegant way that simply tracking these ongoing actions as part of the application's state 🤔

Anyway, I'd like to hear your thoughts about this, if you have time 😄 I don't plan to immediately start any work, but being aware of the planned changes will make sure I don't introduce anything that makes it more difficult in the long run.

[inact1v1ty]

Release workflow seems to be a nice thing!

My first (very informal!) usability test revealed most people will intuitively reach for Ctrl-Z (who would've thought! 😅)

Yeah, Ctrl-Z thing has wired deeply into our brains 😅 . This a crucial UX feature for a desktop content creation now 🙂

I don't mind if the feature takes a while, but I want to at least make sure I don't start shifting things in the wrong direction.

I agree, this is a good concern!

Still, there are some things that are not 100% clear to me, like what to do with parameter editing.

Yeah, the traditional "carved in stone" Command pattern seems to have troubles with almost non-discrete, WYSIWYG nature of editors like blackjack.

I want to prepare a design document/RFC this week (probably during the weekend), but here are my thoughts in advance.

I think a system closely inspired by Unity behaviour can play good here, especially because whole blackjack UI is a giant immediate-mode GUI including the graph:

• We have document as a whole state accessible to us.
• We divide the document into serializable objects. For blackjack, it's nodes. They have serialized properties - for nodes these are inputs, node position, node connections (?).
• For each serializable object each frame we determine if user has touched it (plays well with egui interaction APIs).
• If user has touched an object, we diff previous serialized object state with the current one and have these diff saved as undo stack entry.
• But: if the changed object is the same as previous entry AND the properties (keys, not values) are the same as previous entry AND some kind of check that this is the same interaction (either timeout or that user has not released mouse button or some other condition that suits the best) then the new entry get squashed with previous entry.
• This way, we can rather easily go forward and back in the undo stack (as it's just applying diffs to a document) and it will play nice with continuous interactions.

There are implementation details and some corner cases to consider (for example, undoing node deletion), but this is the overall direction I think we can go.

Also, there are a lot of corner cases when modifying several nodes together, need to think about it too.

Looking forward to your thoughts on this @setzer22!

[setzer22]

I love it! I was toying with this idea right after writing my post thinking how well it would fit blackjack due to it being immediate mode 😄 We seem to be very much on the same page about that.

I think you're already making a very good analysis about potential drawbacks, but here's some additional things to be aware of:

• Some parts of the UI use shared ownership / interior mutability (currently NodeDefinitions and UiGizmoState). So we have to be careful about how they play out with the undo strategy. Essentially, my idea is that we should have a way to have those types opt-out from the diffing / serialization mechanism. The state held inside the NodeDefinitions is tied to the Lua source code, and hot reloads whenever that changes, so undo/redo shouldn't affect it at all. For the UiGizmoState, I'm thinking this shared ownership is accidental, and we might be able to refactor it as a regular owned struct by moving it further up the hierarchy and passing it down during method calls to the viewport and the graph 🤔.

• The graph library is split into a separate crate, so that might make some strategies (like a deriving macro to diff structs) a bit more cumbersome. Still, there's no reason we can't modify the graph library, we should just make sure to not introduce any blackjack-related stuff into it, since it's being used by more people.

for example, undoing node deletion

I was thinking, if we computed the diffs from the top of the object hierarchy (the RootViewport struct), things like node deletions would appear in the diff.

I'm not sure how crazy would it be to reach for some of the available general-purpose solutions like https://github.com/chinedufn/dipa or https://crates.io/crates/diff-struct 🤔

But: if the changed object is the same as previous entry AND the properties (keys, not values) are the same as previous entry AND some kind of check that this is the same interaction (either timeout or that user has not released mouse button or some other condition that suits the best) then the new entry get squashed with previous entry.

Another possibility I was considering was to add explicit calls to a "commit action" function throughout the code. The idea is to insert this call into every button click, every time the user releases the mouse when dragging a slider...

I've done similar things to implement change detection for egui in other projects and it was a very comfortable experience. As an added bonus, this state (the currently commited action(s) for the current frame) can live inside a thread local, so there's no need to pass it around everywhere. Setting the flag telling the UI that an undoable action has occurred would be as comfortable as calling println!. If you implement it as a trait for structs like egui::Response, it basically becomes:

if ui.button("foo").clicked().detect_changes() {
    // Freely mutate the app state here, the diff system will track the changes
}

[inact1v1ty]

We seem to be very much on the same page about that.

This is very nice! 🙂

Some parts of the UI use shared ownership / interior mutability

Yeah, these are among the things I will need to look into in the coming days.

If the NodeDefinition state is not a part of the saved document, we can just leave it there without putting it into the undo stack.

As for UiGizmoState, moving state higher in the hierarchy to have a single source of truth usually proves to be the right thing to do.

As for the graph state, that is another thing I need to dig deeper 🙂

I was thinking, if we computed the diffs from the top of the object hierarchy (the RootViewport struct), things like node deletions would appear in the diff.

Yeah, if we diff the whole state as one struct this would appear automatically. I have just considered that because of integrations with the graph and ui interactions and etc we will have to diff objects one-by-one, so there will some tricky things.

Like in pseudocode:

for node in nodes {
    undo.begin_change_check(node.state);

    <render a node>

    if node.has_changes(node.state) {
        let entry = node.state.diff(undo.prev_node_state)
        undo_stack.push(entry);
    }
}

(This will be trickier because you can move several nodes at once, etc, but this is the general idea.)

Another possibility I was considering was to add explicit calls to a "commit action" function throughout the code. The idea is to insert this call into every button click, every time the user releases the mouse when dragging a slider...

This is a good option to consider 🙂

it basically becomes:

Hmm, that is truly an option too! Need to research! 🙂

[setzer22]

Yeah, if we diff the whole state as one struct this would appear automatically. I have just considered that because of integrations with the graph and ui interactions and etc we will have to diff objects one-by-one, so there will some tricky things.

Ah, yes, I see what you mean. We'll need to figure something out, but I still think in this codebase we have a high level of control of the state that would allow performing a single top-down diff of the whole application (or, at least, the whole graph state).

Even if it's an "integration", the graph library was designed as part of blackjack, and was only split out into a separate crate so other users could benefit from it. In a logical sense, I still consider the library to be part of blackjack, so we can totally depend on its implementation details to compute the diffs. The fact that there are no private fields in the graph library is by design, because I didn't want to loose the ability to mess with the graph internals.

Another thing to take into account is that nodes don't store all their state in an object-oriented sense. Meaning, the node object doesn't have all the information it needs to render itself or perform its interaction. There are several things like the "Set active" flag, the gizmo configuration or the parameter configurations (e.g. the min / max values for a float field) which are not stored as part of the UI node, but in separate data structures. Typically the node will contain data to index those data structures, and these data structures made available during node rendering via the CustomGraphState object. This means diffing node objects individually without additional context won't be enough. Not that this means it's a bad idea, I'm just saying that the "diff" and "apply diff" operations would need to be written as custom logic.

Finally, the graph is very central to the application, but it's not everything there is 🤔. I'm not sure how we want undo to work in that regard, but should things like setting the mesh display options or resizing the panels be undoable?

[setzer22]

Another thing I just realized: As part of my last PR #62, I did a heavy refactor of the serialization system that may be relevant. Whereas before we serialized the UI state, we now have the logic to serialize graphs in blackjack_engine, with custom logic in the UI to generate a full description of the current graph as a .bjk file and apply it back. You can find this logic on blackjack_engine/src/graph/serialization.rsand the UI-specific bits in blackjack_ui/src/application/serialization.rs.

I intended this mechanism to be lossless, meaning that, currently, saving and restoring a .bjk file should be a no-op. And saving multiple .bjk files after each operation would behave as a very crappy version of undo / redo, just as you mentioned on your first post.

Maybe we could reuse this serialization mechanism to compute the diffs and store the previous state, instead of having an entirely separate mechanisim. Now I'm starting to think this is what you may have meant from the start when you said "an undo mechanism that is closely coupled with the serialization system"! Anyway, take a look at this serialized file: https://github.com/setzer22/blackjack/blob/main/all_nodes_test.bjk, we already have the ability to compute something like this as a Rust struct at runtime and apply it back, so basing the undo / redo system on top of this would be super convenient. The file even stores things like the node positions, so applying the diffs on top of this would mean the logic to handle multiple nodes moving is no longer a special case.

This would mean the performance equivalent of attempting to generate a save file each frame (minus the I/O and RON serialization cost, of course). However, I'm a strong believe in the computers are fast mantra and I'm thinking this is probably the kind of thing we wouldn't even notice. This serialization logic should already be quite fast to begin with, and if necessary there's probably plenty of room for optimization.

[setzer22]

This was on /r/rust today:

Not exactly related to the discussion above, but I'm thinking this undo/redo strategy would feel pretty intuitive!

There's even a crate for it: https://crates.io/undo_2