Ghost nodes: layout- and rendering-ignored entities in hierarchies

[viridia]

This is a follow-up to an issue I filed and then closed a long time ago: #9731 The reason I closed the issue was that I was able to find a workaround; however, I'm re-opening the issue in modified form because the workaround is making my code much more complex than it needs to be.

First, let me describe what I mean by "auxiliary" and "fragment" nodes. I'm not sure what's the best word to describe the concept, but the basic idea is that a fragment node is an entity that has a special marker component, or perhaps a special type of visibility, that causes the node to be ignored by the ui layout and rendering code, but allows its children to be displayed in its place. The term "fragment" comes from React - a <Fragment/> is a special type of JSX element that contains multiple children, but which can be passed around like a single element reference.

Fragment nodes behave like regular entities in all other ways: they can be children of other nodes, they can listen for events, they have have components and children of their own and so on. The only difference is that they are not displayed, but their children are displayed in their place.

This has an effect on flexboxes and grids: let's say we have a flexbox node with three children, one of which is a fragment with N children. The flexbox layout algorithm should treat each child of the fragment as if it were a direct child of the flexbox, meaning that in this example the flexbox will have 2+N layout items. If the fragment has a child which is also a fragment, the children of that fragment is also treated as direct children of the flexbox.

This also affects scenes: if a fragment node is a child of a SpatialBundle, and has in turn a child which is a MeshBundle, the mesh bundle is rendered as if it were a direct child of the SpatialBundle; there's no warning about the lack of a transform component on the fragment.

What problem does this solve or what need does it fill?

For a reactive framework, the benefits of fragments are huge: I'd estimate that the amount of code for bevy_reactor and Quill could be reduced by 30-50%.

The reason is that these frameworks need to insert special "housekeeping" nodes into the entity tree. An if-condition node needs to keep track of the current state of the condition, as well as state information needed to tear down the children when the condition changes. A for-loop node needs to keep around information about the array elements so that it can do a 'diff' when the array changes. Template call nodes need to keep a copy of the template parameters.

Why can't these simply be stored as components? Because there might not be any entity available to store them - a conditional branch might render an empty tree, a for-loop might render zero items. Or it might render 100 items. There's no obvious, unambiguous way to annotate the children of these conditional operators on the child nodes.

For similar reasons, these aux nodes can't be stored as siblings or on the parent node without creating additional ambiguity or complexity. The only way that really makes sense is to have a special node which dynamically generates its children, and then to somehow mark that node as not being part of the layout.

The way I am doing this currently is to maintain an entirely separate tree in parallel which stores these housekeeping nodes. However, this introduces a lot of complexity, because these trees have to cross-link to each other, when you despawn part of one tree you also have to despawn the corresponding part of the other tree. (This is part of the reason why Quill UIs cannot be StateScoped - you can't just call despawn_recursive and expect it not to crash.)

What solution would you like?

One possible approach is to add a new type of Visibility, such as Visibility::Fragment. Another is to have a special marker component. The hard part is modifying the layout / rendering code to recursively traverse into the fragment node.

The original proposal was to add a new type of Display, but that only fixes the issue for bevy_ui nodes and doesn't address the issue for other kinds of scenes.

Finally, I want to mention that this may have an impact on BSN. We don't have much details on the reactive strategy for BSN, other than @cart 's comment about favoring a fine-grained approach. However, I have a hard time imagining how BSN is going to be able to implement any kind of dynamic/incremental updates without a way to store template housekeeping information in the entity tree.

[viridia]

Here's an illustration of how this could be used. The blue-tinted node would be hidden, but its children would be displayed as if they were direct children of the flexbox.

[viridia]

A few more comments on this:

CSS has a similar concept, called display: content: https://caniuse.com/css-display-contents .

Another reason why I can't simply use components to store the template state (beyond the ones I already mentioned) is the case of nested control constructs, such as a nested "if". Since you can't store two components of the same type on an entity, each "if" needs to be stored on a separate entity. This is very easy to do if the entities are nested in the same way that the if-statements are. But the if-statements shouldn't show up in the visible scene.

Also, the motivation for this ticket comes out of this discussion on the next-gen scene ui design. Specifically, the part where @cart says: "I'm very in favor of not maintaining a fully separate hierarchy."

Also, it's important that the solution chosen be agnostic to the rendering technology: that is, the same marker component should work regardless of whether we are talking about ui code or 3d scenes. The reason is because the templating language is meant to work with both, and we shouldn't have to use a different kind of "if" statement or "for" loop in different contexts. In this sense, it's no different from Visibility or Transform, which is universal.

[UkoeHB]

Thinking about this a bit more, it could be implemented with a marker component CollapseChildren that causes an entity's children to be treated 'as if' they were inserted to the entity's position in its parent's Children list for purposes of hierarchy traversal (UI layout, visibility, transform). If the entity has no children, or all children are 'collapse', then the entity will be skipped over entirely.

This would solve another issue in UI where it's useful to attach observers as children of nodes so they will be auto-despawned when nodes are despawned.

[viridia]

There's been some discussion about naming. I chose the word "fragment" because there's an analogous concept in React, but I'm open to suggestions.

Another word that might apply here is "flatten" or "flat".

Also, @nicoburns Suggested the idea of an iterator or library function which would do the recursive traversal needed to produce the flat list of visible entities - that is, it would traverse into any fragments and produce a flat sequence of entities. This could then be used by the layout code.

Another open question is whether to use a marker component or a new visibility variant. There are pros and cons:

• The advantage of a visibility variant is that we don't have to query a new component in the layout and extractor code.
• The disadvantage is that visibility calculations which traverse upwards - for things like visibility inheritance - now have to be smart enough to skip over fragments.

[UkoeHB]

We should assume users don't know anything about React and pick a name that makes sense within Bevy. To me, who does not know React, Fragment doesn't tell me anything about what the component actually does to an entity. I would be fine with FlattenChildren since that lines up with rust iterator flattening.

Another open question is whether to use a marker component or a new visibility variant.

Visibility is about what gets rendered, not how trees of entities are traversed. We should keep the concepts separate.

[Diddykonga]

Not sure if it makes sense or not, but would be nice if this were more modular and had specific naming that represented what it does.
NoUILayout + NoUIRender

[villor]

It seems like this would benefit from some kind of generic solution for shadow hierarchies in bevy_hierarchy.

We want to iterate children as if some entities in the hierarchy does not exist, let's call those shadow entities. The children of those shadow entities are considered children of the shadow entity's first non-shadow ancestor, unless the child is also a shadow entity, in which case the traversal continues...

So, we have a shadow hierarchy. A hierarchy where some entities are treated as shadow entities.

Hierarchy traversal

Today we have iter_descendants, which traverses the whole parent-child hierarchy breadth-first.

Not sure how viable this is, but maybe we can add extensions to traverse the hierarchy with a QueryFilter applied?

Something like:

• iter_descendants_shadowed::<F: QueryFilter>: Works just like iter_descendants, but filters out entities that match the QueryFilter (those are considered shadow entities).
• iter_ancestors_shadowed::<F: QueryFilter>: Works just like iter_ancestors, but filters out entities that match the QueryFilter (those are considered shadow entities).
• iter_children_shadowed::<F: QueryFilter>: Works like iter_descendants_shadowed but stops traversing further down when a non-shadow entity is found, treating the first non-shadow as a child.

For the purpose of UI fragments, it could be explicit by using a filter like Without<Fragment>. Or it could be implicit by using something like With<Node>.

Potential optimization: Retained shadow hierarchies

One downside of the extensions above are that they might do some unnecessary tree traversal on every frame. Compare this to how layout code works today, iterating Children directly, no traversal necessary.

One way to solve this could be to allow defining shadow hierarchies upfront in bevy_hierarchy, which would store them just like Parent and Children, and update them automatically.

We could add a new pair of components:

#[derive(Component)]
struct ShadowParent<F: QueryFilter>(pub(crate) Entity);

#[derive(Component)]
struct ShadowChildren<F: QueryFilter>(pub(crate) SmallVec<[Entity; 8]>);

To make use of these, the shadow hierarchy would need to be initialized upfront:

app.init_shadow_hierarchy::<Without<LayoutFragment>>();

This would set up the systems/hooks/observers necessary to keep them up-to-date.

Those components could then be used in place of Parent or Children in a system, for example for UI layout:

fn ui_layout_system(
    /* ... */
    children_query: Query<(Entity, Ref<ShadowChildren<Without<LayoutFragment>>), With<Node>>,
    just_children_query: Query<&ShadowChildren<Without<LayoutFragment>>,
    /* ... */
) {
    /* ... */
}

[viridia]

I kind of like the name "shadow hierarchies".

[villor]

Decided that the QueryFilter approach was a little bit too much, and tried implementing traversal for "shadow hierarchies" using a marker for the shadow entities.
Draft at #15238

[viridia]

A few more comments:

1. I'd be OK with renaming this issue "Shadow Nodes" if no one objects.
2. I still prefer using Visibility for this, and here's my reasoning: we want most of the Bevy code to be unaware of shadow nodes - to treat them (and their children) exactly like any other entity with children. This includes observers, queries and so on. The only code that we want to actually be aware of shadow nodes is layout, rendering extraction, and picking - which are, coincidentally, the only parts of Bevy that pay attention to the Visibility. component. And although I haven't actually looked at the code in detail, I strongly suspect that the code that implements shadow nodes would be located close to the code that handles visibility. So a shadow node is simply a node with the component Visibility::Shadow.
3. Note that the "shadow node" behavior is not the same as "shadow DOM" in HTML, so let's not get confused.

I recognize, of course, that I'm making several assumptions here:

• I'm assuming that the only parts of Bevy that would care about shadow nodes are layout, rendering extraction, and picking. It's hard to know a definitive answer to this without knowing all of Bevy's code, which obviously I don't.
• I'm assuming that overloading Visibility in this way wouldn't create other problems. As you know, there's both a Visibility and InheritedVisibility which is calculated from the former. I'm assuming that the InheritedVisibility enum would not need to change, however the way it's calculated would be. If a child of a shadow node had Inherited visibility, the code would have to skip over the shadow node parent to get the true visibility. (The shadow node itself would always have InheritedVisibility::Hidden so nothing complex there.) This calculation would have to happen regardless of how we implement shadow nodes, but I think using Visibility::Shadow is actually more efficient because it avoids the need to query for an extra ShadowParent component during the visibility calculation. But I could be wrong about this...

Here's some things I don't know yet:

• First, I have no sense of whether or not people think this is a good idea. I'd really like to build a consensus around this before diving into an implementation.
• Second, I have a rough idea of what parts of Bevy would be impacted by this, but I don't know for sure if my ideas are accurate. Similarly, I'd like to get a sense of how hard this would be to implement.
• I'd very much like to know if other people have use cases other than the ones I have come up with. That is, if the only library that uses this is my own library (bevy_quill), then I would vote against doing it. However, I think it has broader applicability than just my own use case.

Part of what I'm trying to do here is define a path for reactivity in BSN. Whether sickle_ui or any other framework will take advantage of this I can't estimate, but I can see advantages to doing so. I haven't gotten a lot of feedback from cart, but some comments made by both him and Sander have propelled me in this direction. I think that in order to satisfy their stated preference of to having reactivity in a "single hierarchy" (as opposed to the dual-hierarchy approach used by Quill now) we need some way to have these extra nodes inserted in the hierarchy.

A typical example of how shadow nodes might be used is a templating language that supports a reactive "if" statement - that is, a conditional branch which automatically re-executes when the test condition changes. When the template is run, it creates an entity tree for the template content, including a shadow node representing the "if" statement itself, and child nodes representing the content of the current branch (true branch or false branch). If the branch is empty (returns void) then the shadow node might not have any children. The shadow node also has an "If" or "Cond" Component which contains, among other things, the formula for computing the test expression and the sub-templates for the two branches. An ECS system queries for the If component, evaluates the expression, and if it's changed it despawns all of the children of the shadow node (representing the old branch, no longer taken), and then executes the template for the new branch, which then populates the children of the shadow node.

Note that this can be done even without reactivity: you can write a system that simply re-executes the conditional expression every frame. All that reactivity adds here is a performance optimization, where you only run the test expression if the variables used within the test expression change.

The templating language will, of course, generate all of this machinery automatically, so the user only needs to write a normal-looking "if" statement within the template.

[villor]

I posted some thoughts in #15238

I started leaning more towards “Ghost Nodes” to not confuse them with actual rendered shadows. Not confusing them with shadow DOM is another good point.

I like the idea of using Visibility for this. Had not considered how my proposed approach would handle picking. I’ll do some research on how/where Visibility is used today and what it would mean to add a Shadow/Ghost variant.

[villor]

About the consensus before implementation. I personally like to get my hands dirty as early as possible since that is the natural way for me to truly understand the problem at hand and its implications.

And maybe a more concrete draft can help bring consensus as well!

[viridia]

@villor Another reason for doing an early implementation is to convince people that the idea is possible; sometimes it's easier to get consensus if people think it's a done deal.

I'm fine with the name "Ghost nodes".

[viridia]

I cobbled together a prototype of what bevy_reactor would look like with ghost nodes. You can browse the code here: https://github.com/viridia/bevy_reactor/blob/main/crates/bevy_reactor_views/src/view.rs#L12 - it doesn't actually work without the ghost nodes (it spews lots of warnings about the lack of InheritedVisibility and such), but it does compile and run.

In this new scheme, the View trait only has one method that you have to implement, build():

pub trait View {
    /// Initialize the view, creating any entities needed.
    ///
    /// Arguments:
    /// * `owner`: The entity that owns this view.
    /// * `world`: The Bevy world.
    /// * `scope`: The parent tracking scope which owns any reactions created by this view.
    /// * `out`: A mutable reference to a vector where the output entities will be stored.
    fn build(
        &mut self,
        owner: Entity,
        world: &mut World,
        scope: &mut TrackingScope,
        out: &mut Vec<Entity>,
    );
}

(There's one other method in View, to_root(), but the default implementation is provided.)

All of the other methods of View are gone:

• There's no raze() method any more, because views can be despawned using Bevy's standard despawn_recursive().
• There's no nodes() method any more, because output nodes can never change unless the view is destroyed - instead, the build method returns the output nodes in a Vec.
• Similar, there's no longer any attach_children() or children_changed() methods, for the same reason.

In the previous design, we had to deal with the fact that the children of a template node could be changed as a result of a control-flow construct such as if/for, which required fixing up the ancestor's children list. With ghost nodes, however, the ghost node is responsible for changing its own children, the logic of which is purely internal to the ghost node - no other nodes need be affected or aware of the change. So there's no need for complex logic to patch up the hierarchy when this happens.

Check out the source to Cond which is now much easier to follow: https://github.com/viridia/bevy_reactor/blob/main/crates/bevy_reactor_views/src/cond.rs - the Cond view spawns a node with a CondReaction, which handles destroying and re-creating the children when the test condition changes.

However, this experiment does raise one important detail that needs to be handled: the case where the root of the hierarchy is a ghost node. This case happens in my prototype because the "view root" - that is, the root element which is responsible for executing all the templates that are attached to the root - is a ghost node. In this case, the ideal behavior is that the children of the ghost node should behave as if they had no parent. This is probably what would happen anyway, but we need to make sure our test cases include this.