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".