Reactivity design choices

[viridia]

This is a continuation of a conversation on the Discord: the intent is to help flesh out some of the missing / ambiguous pieces in the BSN design proposal by breaking down the "reactivity" question into multiple subproblems.

Background

Apologies if I get too pedagogical, since I don't know who will be reading this and I like to ensure that everything is explained.

The word "reactive programming" has a specific technical meaning, although it is often used rather ambiguously. It is not a synonym for "interactive", but rather a style of programming where the mere act of accessing data creates a subscription or dependence on that data. In this, it represents the classic "observer pattern" except without the need to explicitly subscribe and unsubscribe. The example I like to use is that of a spreadsheet cell: a formula that references cell A1 knows that it needs to be recalculated whenever the contents of A1 changes.

Reactive frameworks are often coupled with "incrementalization strategies", which are a way of patching/diffing a user interface so as to minimize the amount of change mutations to the UI in response to updates. This is not only important for performance, but also because UI nodes have a lot of "hidden state", such as cursor positions, input method states, focus, accessibility modes - things that can be lost if we simply replace the UI nodes wholesale.

The earliest form of incrementalization is simply "imperative mutations". That is, some code in response to, say, an event, directly modifies the UI tree. This is the strategy used by most older UI frameworks such as jQuery and Java AWT. It's also the strategy currently used for most bevy_ui code.

One problem (of many) with imperative mutations is that your UI has to be split into two separate subsystems: one to build the UI initially, and a separate system to handle updating the UI in response to events. This causes code related to a given feature to be spread out over the code base instead of being nicely grouped together. If the code involves displaying of data, it means that the data has to be fetched in both the initial build code and the update code, causing duplication.

Incrementalization and reactivity are separate features: you can have an incremental framework that is non-reactive, or a reactive framework that is non-incremental.

Terminology

To avoid confusion, let's introduce a few unambiguous terms.

Reactive UI frameworks generally maintain multiple hierarchies. Typically there are three layers, which are "templates", "template invocations", and the "DOM". Templates are generally static and unchanging at runtime, and can be defined either in code or as assets. Template invocations are the objects that result from actually calling a nested set of templates, and include both runtime parameters and local state. The DOM, or "display graph" is what actually gets drawn on the window.

We can compare various frameworks to see how these layers line up:

       Template                Template Invocation             Display
       ~~~~~~~~                ~~~~~~~~~~~~~~~~~~~             ~~~~~~~
React: Component Function ---> React.Element -------> VDOM --> HTML DOM
Solid: Component Function ---> JSX.Element ------------------> HTML DOM
Xylem: Component Function ---> View -------------------------> * (depends on backend)
Quill: Presenter ------------> View/PresenterState ----------> UiNode Bundle

Note that in the case of React, there's an extra layer, which will be discussed in the next section.

The action of running templates and building the display graph is called, variously, "rebuilding" or "updating" the UI. In the web world, the active of constructing the DOM is commonly called "rendering", however that term means something different in the Bevy world.

Item 1: Update Granularity

The goal of incrementalization is to minimize the scope and size of mutations to the display graph. There are two strategies for doing this:

• Use fine-grained updates, that is, updates on the level of individual attributes or elements. This is the approach used by Solid.js.
• Use coarse-grained updates and then do a 'diff' on the output. This is the approach used by React.

In the React approach, there's only one kind of "reaction" which is a re-run of a template function. Any other kind of reactive computation, such as effects, memos, and so on must happen as sub-tasks of template evaluation. A useEffect hook in React does nothing unless the containing component is re-run.

In the Solid approach, "reactions" are much more broadly defined, and can be arbitrary closures. Calling createEffect() in Solid creates a subtask which can be triggered in response to a reaction, regardless of what the enclosing scope is doing.

The advantage of the React approach is that it is far simpler to implement, particularly in the context of Bevy/ECS. It's fairly easy to mentally map the React approach to ECS thinking: template invocations are entities with components, and each "reaction" causes a recomputation of that entity.

The downside of the React approach is that "updates" are coarse-grained: they regenerate an entire template invocation rather than just the attributes that changed. To prevent unnecessary churn, the VDOM (Virtual DOM) is used to "diff" between the current and previous display output.

Although React's VDOM diffs the HTML DOM, that is not the only possible strategy. It's also possible to do diffing at a higher level, by comparing the internal states of template invocations, which is the strategy used by Quill. (The reason React maintains a separate VDOM is because DOM operations are slow, but if speed is not a problem then you can diff against the output nodes directly, without the extra layer.)

The advantage of the Solid.js approach is that it is far more performant. From the perspective of a Solid.js coder, the React VDOM is "pure overhead". Unlike React, where the template function re-executes and rebuilds the template invocation graph every update cycle, in Solid.js the template function is executed only once per invocation site.

However, implementing fine-grained reactivity is a lot more complicated, because now you need entities representing all of the individual bits and pieces that can be updated independently, like individual attributes. You also need a strategy for reacting to individual parameter changes, as well as come up with a solution for the reactive diamond problem.

Item 2: Diffing

A diff can only work if it has something to diff against. This means keeping around a copy of the previous state. What exactly that state consists of, and where it is stored, is a design choice.

Let's take a simple Text node as an example, like "The count is {count}". Each time we update, this string is going to be different; the UI framework needs to compare the newly generated string value with what's already in the Text node and decide whether or not to replace or mutate the TextSection elements within the node. This is a case where we don't need to keep around any additional state other than what's in the display graph itself.

A more complex case is an element with three children. Each child is an entity. When the element updates, we want to re-use the same entity ids for the children, instead of spawning brand-new entities and despawning the old ones. To make this work, the template invocation graph only needs to hold on to the entity id; the previous text can be accessed through direct inspection of the Text component on that entity.

Special consideration must be paid to conditional and mapping primitives ("if" and "for"). When the inputs change, the output of these constructs may change shape, which means that a naive diffing algorithm will give you nothing sensible. However, we can easily detect when the inputs change by keeping a copy of those inputs. Generally this copy will live as an attribute of the template invocation graph, although it could also be stored on the display graph as a hidden component.

For mapped arrays, we want to be able to detect insertions and deletions in the input so as to align the old display nodes with the new ones. In React, this is done by having a mandatory "key" property on array element nodes. Solid provides a number of different "For" constructs that offer a choice of how array comparisons are done.

Item 3: Tracking Scopes

Once incrementalization is dealt with, the next biggest chunk of the reactive framework is the design of tracking scopes. A tracking scope is simply a record of all of the reactive data sources that were accessed during a template execution. In a coarse-grained React-like architecture, each template invocation will have a tracking scope (generally stored as a Component). In a Solid-like architecture, not only will template invocations have tracking scopes, but individual "effects" will have their own tracking scopes as well, since they can run independently.

For something like ECS Component changes, the tracking scope can simply be a hash map storing entries of (EntityId, ComponentId) tuples. Any "read" of a component adds that component's id to the tracking scope for the current invocation. Similarly, resources can be tracked by having a hash set of resource ids.

In terms of design choices, Tracking scopes can live in the World as Components, or in a separate, dedicated World, or externally via some other data structure.

A "reaction" is triggered by detecting whether or not any of the items within the tracking scope have changed, and then queueing up a reaction / rebuild (which of course needs to be debounced). This can be done with a marker component, an AtomicBool or other ways of indicating an update flag.

Tracking scopes get more complicated once we start adding exotic reactive primitives. (Although in Solid tracking scopes are actually quite simple as they are just a Set<> of callbacks. However, this simplicity is only possible in a garbage-collected language.)

Another design point for tracking scopes is whether they are dynamic or static. Most frameworks use dynamic tracking scopes that are rebuilt each update cycle - that is, the tracking scope is a side-effect of template execution, and is rebuilt from scratch each time. However, some frameworks do static analysis of dependencies. How this works, I do not know, but I wanted to mention it for completeness.

Item 4: Shared Local State

Bevy ECS supports "global" objects such as entities and resources, as well as Local objects that are local to a single system. However, because UIs have deep hierarchies, there is often a need for a "semi-local" state, that is, some state that is private but visible to a cluster of individual widgets.

These objects are known by various names, "useState vars", "signals", "reducers", "atoms" and so on. These objects tend to be ubiquitous in reactive apps, but some sample use cases are: representing the open/closed state of a popup menu or dialog box; representing the current selected item in a list; or representing what type of drag operation is currently in progress.

The key requirements are:

• They are reactive, meaning that reading them creates an entity on the current tracking scope.
• They can be passed as parameters to child widgets or captured in closures.
• They are anonymous, meaning that they don't require pre-registration or a globally-visible name.

If we already have the ability to track changes to components, it's possible that these "atoms" or "signals" are nothing more than an entity with a simple component for holding the current value. Alternatively, these objects could be implemented in another way, using something other than entities / components as a base.

While it is possible to use global objects such as Resources to model local shared state, this approach breaks re-usability and modularity: you may want to have multiple instances of a popup or dialog, but you can only have a single resource of a given type. Similarly, you can also use regular (non-anonymous) Components to store state, but this entails additional boilerplate and makes the code more verbose. That being said, there are use cases for regular Components/Resources too: particularly when you want to share state between UI and non-UI code.

Item 5: Dynamic Construction

Up to this point we've discussed how changes are applied to the display graph. Now let's address the issue of where those changes come from.

In "classic" Bevy, the Commands object is used to insert components and children onto an entity. These methods are all one-shot, in the sense that they are intended to be executed once: the entity takes immediate ownership of the Bundle.

However, in template world, the ownership of the inserted components is more complex: the components are initially owned by the template invocation graph, and only later get inserted into the display graph. We can't transfer the components directly from the template function to the display graph without sacrificing incrementalization.

(This is a problem I'm still working on solving - I think it can be solved by recognizing that even though a template invocation may not immediately transfer the components to the display, it will eventually transfer them, and that transfer will only happen once - because you'd need to re-build the template invocation again to get updated versions.)

Item 6: Event Handling

First, there are generally two sorts of events: "system" events that are generated by the engine, and "user" or "custom" events that are generated by user code or widgets.

System events generally need to support "bubbling". More specifically, events which are targeted at a specific UI element (either because the event has some spatial coordinates such as a pointer location, or because the event is dispatched to the current focus element) are often handled, not by the target, but by some ancestor of the target. The event dispatching system does not know in advance which target to dispatch the event to, so an upward search is required.

In most frameworks this upward search happens on the display graph; however it's also possible to bubble on the graph of template invocations.

User events, OTOH, rarely use bubbling (although there are some exceptions). In most cases, the target for a user event is defined well in advance, often by passing in a specific entity id or a callback to the code that is emitting the event.

A use case for a bubbling a user event is popup menus: clicking on a menu item also causes the menu popup to close, but the individual menu items may not have a direct reference to the menu widget. So a 'Close' event can be sent up the display graph. This can also be used for things like keyboard navigation in menus.

One unintuitive aspect of event handlers is that while they live in a reactive component, they are not themselves reactive. You don't want a handler to run twice because some piece of dependent data changed. However, it is common for event handlers to trigger reactions, and in fact virtually all triggered reactions come from event handlers.

This means that event handlers need access to the same data that is accessed by the template during construction, but they need to access it in a different way - one that does not add to a tracking scope. Dependency injection is one possible solution, but you could also allow event handlers to have their own special "context" object ("ecx"?).

Item 7: Callbacks

Events are not the only way to communicate between widgets. Callbacks are often used to allow child widgets to notify their parents of important changes.

It's possible to do without callbacks and only use events, however this produces a lot of extra boilerplate: events need to be declared as Rust types and also generally need to be registered by the plugin. Callbacks can accomplish the same things much more succinctly.

Ideally, callbacks should be partially type-erased, so that a callback from widget A can be interchanged with a callback from widget B as long as the "In" parameter type is the same. Thus, you should be able to replace a Checkbox with a ToggleSwitch without having to modify the type of the callback.

It is sufficient that callbacks only support a single "In" parameter. Callbacks with output values are fairly rare, and aren't generally used for change notifications, but have a different set of use cases. As such they can be considered a separate category.

Item 8: Explicit vs Implement Parameter Memoization

Template invocations are often memoized, meaning that if a parent template updates but doesn't alter the properties passed to the child template, the child template will not rebuild, but will instead preserve the same output as before. If we didn't have this, then a rebuild of the root UI template would cause a rebuild of all its descendants, effectively rebuilding the entire UI. (Although it would still diff the output, it would be an expensive computation).

In React and Xylem, memoization is opt-in: you have to explicitly "wrap" the template with a "memo" to indicate that the template should be memoized. In Quill and some others, memoization is implicit, all templates are memoized automatically.

(Solid is different here: since the template is only executed once, memoization is irrelevant. However, individual template parameters are both individually memoized and individually reactive - they are in effect, signals. How to accomplish this in Rust, where there's no property getters/setters remains an "open research project".)

In order for memoization to work, memoized values need to support both PartialEq and Clone. This means that any template which is meant to be memoized must support these traits for all parameters.

Item 9: Integration with ECS

It's very common that UIs will want to display and manipulate data in the ECS. However, UIs are not like systems: because they often have deep hierarchies, the root UI element may not be aware of what resources and components a given leaf widget will want access to. Trying to have the root inject every dependency that is needed by any widget, anywhere, is a non-starter: it creates a painful coupling between different parts of the app that really ought to be separate and isolated.

Ideally we want each template to be able to specify, independently from any other template, what ECS items it needs. Two approaches to this are dependency injection and hooks.

The dependency injection approach treats every template as a one-shot system, so it can inject whatever resources and queries it needs. This is handy, but has some limitations:

• Often times you don't need a whole query, you really just want component X of entity Y. However, 'entity Y' is a runtime value, and cannot be encoded into a function signature.
• Because we want to add any injected resources or components to the tracking scope, we'll need to "wrap" the injected values. One approach would be to use a different name for injecting tracked items, e.g. UseRes instead of Res, but this is a potential footgun, since Res will still work but won't be reactive.
• Tracking scopes for queries is a hard problem because queries can be arbitrarily large; also, while queries do support change detection, that change detection is not persistent, there's no way (currently) to say "Give me a hash set of all the component ids produced by this query so that I can put it into the tracking scope".

The other approach is React-style hooks, so you can have say a cx.use_resource::<R>() method that returns a reference to a resource. This approach also has some limitations:

• Because hooks can return arbitrary parts of the ECS world, it means that the template calls must happen in an exclusive system (which is probably true anyway for other reasons).
• You can quickly run into issues with mutable borrows, since all of the objects returned by the hooks are coming from the ECS world.

Note that hooks and injections are partially substitutable: that is, any hook that takes no parameters can also be implemented as an injection.

Item 10: Ownership

All of these novel reactive objects such as callbacks and atoms need a lifetime: they exist until destroyed, they aren't going to destroy themselves, and we don't have a garbage collector.

In Solid, there's a notion of "owner" which is separate from (but often correlated with) the notion of a tracking scope. A template "owns" all of the objects it creates during execution. When that template invocation is despawned, all of the objects it owns are also despawned. Solid "effects" are also owners: creating an effect within an effect means that the inner effect is owned by the outer. There's a special "root" construct that can own things, but is not itself owned by anything - the root object (you can have more than one) is typically stored in some app data structure and is used for explicit cleanup under control of the app.

Owned objects don't just live in UI templates, they also frequently get stored in global data structures. A callback or signal might be created by a global setup system, in which case it's the responsibility of the creator to ensure that these items get cleaned up.

[UkoeHB]

This helped me better understand what 'reactive frameworks' really mean. I think the way you use the words 'reactive' and 're-render' is confusing, especially in an ECS. Maybe they make sense to you after a lifetime of UI, but for me (and probably other non-UI devs) it's easier to think more directly in terms of data and execution flow.

These frameworks are optimized data rebuilders that re-run every frame. Calling what they do a 're-render' distracts from what is really happening - data is created and modified. Data changes are picked up by rendering code in a separate step, and exactly what the rendering code does with the data or what to call what it does isn't that important. However, what is important is the distinction between general world data, contextual UI data (only accessible via the rebuilder interface, or maybe not accessible at all), and data we expect the rendering code to track (which is a subset of either general-world or contextual-UI data).

• Optimization 1: Rebuilds are 'in place', which means they reuse existing data structures.
• Optimization 2: Data storage is not mutated unless it will change (as much as possible). This is (presumed to be) a direct optimization and also helps the rendering code handle the data more efficiently.
• Optimization 3: Data values are not recomputed unless their dependencies have changed. The so-called 'reactivity' is more like dynamic conditional recomputations and closure invocations within the rebuild execution path.
• Ergonomics 1: The distinction between data-construction and data-updating is (mostly or entirely?) hidden from the user, so that the UI rebuilder looks like one big constructor even though reconstructions are optimized as described.

I'd like to see more clarity around the 'general-world, UI-contextual, render-visible' data model. What are the boundaries around these data sets? When you talk about event handling and callbacks, what data can be tied to event handlers/callbacks (readable vs mutable vs inaccessible data)? What is the relationship between the rebuilder and its data (UI-contextual?), and general app code?

[viridia]

@UkoeHB First, thanks for the feedback. Your comment about my use of the word "render" is a fair point - in the web world, "render" means "rebuild the DOM". I'll see if I can revise the doc to make the terms more clear, probably sometime tomorrow.

[afonsolage]

First of all, what an excellent write-up! As someone who has been following Bevy UI discussion for a while, this was one of the deepest write-ups until now.

Now some questions, if you don't mind:

1. On Item 8, there is the following quote:

If we didn't have this, then a rebuild of the root UI template would cause a rebuild of all its descendants, effectively rebuilding the entire UI. (Although it would still diff the output, it would be an expensive computation).

This is a typo and you mean "it wouldn't be an expensive computation" or in fact, it would be an expensive computation?

2. Still on Item 8 subject, you said on Quill the memoization is implicit, but is it viable/possible to be able to opt-out? AFAIK there are some use cases where the memoization can be more expensive than rebuilding the template, like for very simple templates like labels or images (knowing that after the template being rebuilt, there still another step which is the diffing).

3. On Item 9, when you talk about the limitations of using One-Shot systems as dependency injections, there is this problem:

Often times you don't need a whole query, you really just want component X of entity Y. However, 'entity Y' is a runtime value, and cannot be encoded into a function signature.

This problem could be solved with Entity Indexes?

[zicklag]

I was doing some thinking about reactivity in my own ECS and I think most of it is relevant to Bevy. This doesn't cover UI, event bubbling or anything like that, but only how you might minimally integrate reactivity into an ECS with a simple usage model.

Sorry if I over-explain, or cover stuff already addressed above, but I want this to be self-contained and as easy to read/explain as possible.

Leptos's Reactivity Model

I started by investigating leptos_reactive, which surprised me with how simple it was fundamentally. It's in the Solid.js / fine grained reactivity category.

Usage

Here's an overview of what the Leptos reactive usage looks like:

It let's you create signals, which are values that may be reacted to:

let count = create_rw_signal(0);
count.get(); // We can get the count
count.set(7); // And we can set the count

You can also create cached memos that will be re-calculated only when signals it depends on changes:

let tripple_count = create_memo(move |_| count.get() * 3);
tripple_count.get() // we can get the memo value

Finally you can create effects, which are closures that will be run one time when they are created, and will be re-run every time dependency signals change.

create_effect(move |_| {
    // Print count now, and every time it changes
    println!("Count = {}", count.get());
});

Implementation

Conceptually, the implementation is actually pretty simple, too. Basically there's a global static Runtime in the background with a graph that establishes the dependencies between the signals, memos, and effects. All of the signals, memos, and effects are stored in that global runtime, so every time you call a get(), set(), or create_effect() it accesses the runtime. This allows the runtime to do stuff like:

• add dependencies for any signal get()s were called while a create_effect() closure was running.
• re-run any effects that should be triggered whenever you call set() on a signal.

Note that, as far as I understand, any effects that need to be triggered because you called set() on a signal will be run immediately. Everything is synchronous.

Integration With an ECS

Imagine taking the idea behind Leptos's reactivity system, but we make a couple changes:

• we make create_effect() take a &mut World argument, so that effects are always given the chance to modify the world however they wish.
• we don't run effects immediately when you call set() on a signal, but we defer them until the command buffers are flushed.

Effects would then work very similar to commands that are automatically queued when corresponding signals change.

Additionally, when creating an effect, we could probably let you use the system syntax for the closure, instead of just supporting closures that take &mut World, so that you could easily access system parameters.

Additional Thoughts

I haven't tested this design yet, and there could be any number of things wrong with it, but some things I liked about the idea:

• It's very simple. It's easy to understand and doesn't introduce a ton of new concepts.
• It isn't specific in any way to UI and could be used to make any game elements reactive, possibly helping design interactive 3D elements.

Note that I haven't been able to keep up with all the Bevy UI stuff completely, so other proposals may already solve these problems better with more features or something, but hopefully this can be useful to the discussion!

[UkoeHB]

bevy_kot_ecs is doing something like this. There is no auto-detection of dependencies or 'memoized values', those are much deeper problems.

[gbj]

Just a small note as the maintainer of Leptos to say that if Bevy decides to go in this direction (doing something like forking leptos_reactive) I think that's cool and would be very happy to consult on any changes needed to adapt to Bevy. Note also the under-development new reactive system I have at https://github.com/gbj/tachys, building toward the next version of Leptos.

IMO the best review of different algorithms for reactivity (the diamond problem etc. described in the original post) is this article.

[jollygreenlaser]

Is there a world where Bevy and Leptos can both rely on the same underlying crate?

[gbj]

Is there a world where Bevy and Leptos can both rely on the same underlying crate?

Oh, totally. The proposal to have effects have access to &mut World would be one meaningful difference, but they can absolutely share (almost entirely?) the same codebase so it would make perfect sense.

[JMS55]

I experimented with tachys + bevy_ui a very small amount. Seems like a really nice fit. I'm currently pursuing bevy_dioxus at the moment, but I definitely want to experiment more with tachys when I have time.

[viridia]

@afonsolage No, I really did mean expensive. Without memoization, you re-create the entire view hierarchy, but it has little to no effect on the display graph because of diffing.

In terms of opting out, it's possible. Effectively you can wrap a ui component in a wrapper that evaluates it unconditionally. Another possibility is what Solid does, which allows you to override the comparison operator (this works better in a language that supports optional parameters).

Entity indices: not sure. Often the entity is passed in as a parameter from the parent, but not always.

@zicklag I would certainly like seeing the results of anyone experimenting with fine-grained reactivity.

The challenge here, I think, is partly political, in that there is a large segment of users who aren't going to like any solution that doesn't feel sufficiently "ECS native".

@gbj You may want to look at my own library, Quill, which is experimenting with Xylem-style Views in a Bevy context. Much of what I wrote here was the result of lessons learned building that prototype.

[PoignardAzur]

A thought I've had for a while: does ECS really bring something to GUI implementation?

The way I understand it, the big draw of ECS is systems: it's about handling lots of similar data at once in arbitrary order. Which is why eg archetypes in bevy are useful: you're grouping together entities with the same components, so that you can say "execute this code for all entities with component X and component Y" and have this code be executed on arrays of values with minimal indirection or branching. And the "arbitrary order" part makes them work really well with slotmaps: since you can just read from the beginning of the slotmap, you don't pay the double indirection penalty.

Basically, the ideal use case for an ECS is code of the type for (entity in entities) entity.position += entity.speed.

You don't have any of that in GUI programming. You almost never want to run code on every widget: usually you want to be sparse and only update changed widgets. Order often matters. And I'm not sure archetypes work well either: for the kind of things you might want to use components for (extra styling options, callbacks, animations), there are so many different combinations I'd expect you'd get tons of archetypes with only a handful of entities.

I think there are two things you really want from a Rust ECS library for GUI:

• Slotmaps.
• Efficient ways to add and remove components from an entity.

Everything else I'm not sure about.