Allow cycles in required components

[cBournhonesque]

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

This PR: #20110 removed the ability to have cycles in required components (A requires B and B requires A).
This was a very useful feature that helps guarantee archetype invariants: for example if we always want A or B to be present on the entity together, we need A to require B and B to require A.

What solution would you like?

We use A -> [B(1), C(2)] as a notation for A requires B with constructor 1 and C with constructor 2.

The existing required components rules are:

• components in the bundle take priority over required components (i.e. if we insert (A, B(2)) and A -> [B(1)], only (A, B(2)) is inserted). Priority 1: inserted components
• if a component is directly required , that takes priority. Priority 2: direct components
• otherwise find it by DFS, starting from the first component in the list of required components. (and we do one DFS per component in the bundle, starting from the component in the bundle) Priority 3: DFS components

Additional rule:

• if we during the DFS we reach a component that was already in our DFS stack (cycle in required components), then instead of returning an error we stop the DFS at that point and backtrack

If we use A -> [B] as a notation for A requires B:

• A -> [A] is allowed but does nothing
• A -> [B] and B -> [A] to be allowed
• A -> [B, C(1)] and B -> [C(2), A, D(2)] and C -> [D(1)]:
  • if we insert A:
    • B and C(1) should be inserted since they are in the list of direct requires
    • D(1) should be inserted since we do a DFS starting from B
  • if we insert B:
    • C(2), A, D(2) should be inserted since they are in the list of direct requires
• A -> [B(1)], B -> [C(1), D(2)], C -> [D(1), B(2)], D -> [A(1), C(2)]
  • if we insert A: A, B(1), C(1), D(1) (via DFS)
  • if we insert B: B, C(1), D(1), A(1)
  • if we insert (C(3), B(3)): C(3), B(3), D(1), A(1) (via DFS)

[cBournhonesque]

Actually maybe I'm misunderstanding the existing rules, are they clearly laid out anywhere?
@SkiFire13 @cart
I see rules described in this PR: #14791 and in this docstring https://github.com/bevyengine/bevy/blob/v0.17.0-rc.2/crates/bevy_ecs/src/component/mod.rs#L284 but they only describe what happens with a one-component bundle, not a multi-component bundle.

https://github.com/bevyengine/bevy/blob/v0.17.0-rc.2/crates/bevy_ecs/src/component/required.rs#L1324
suggests that in a bundle (A, B) we first handle A's required components (direct + DFS), then B's required components (direct + DFS)
So B's direct requires have lower priority than A's DFS requires.

I thought all direct requires had higher priority over all DFS requires, so if A -> P -> Z(2) and B -> Z(1) and we insert (A, B) we would get (A, B, P (via direct require), Z(1) (via direct require)).

If it's the former (which is certainly easier to implement and understand), I can add it to the docs to make it clear.

[SkiFire13]

I see rules described in this PR: #14791 and in this docstring https://github.com/bevyengine/bevy/blob/v0.17.0-rc.2/crates/bevy_ecs/src/component/mod.rs#L284 but they only describe what happens with a one-component bundle, not a multi-component bundle.

For multi-components bundles the current behaviour is to treat it as if there was a "ghost" component that required all the component of the bundle.

So B's direct requires have lower priority than A's DFS requires.

This is correct and it's coherent with how we handle the required components of a C that directly requires A and B.

if we during the DFS we reach a component that was already in our DFS stack (cycle in required components), then instead of returning an error we stop the DFS at that point and backtrack

My issue with this "rule" is that this is not how it's currently done. There's no DFS scan or stack, instead the transitive closure of required components for a given component is computed from its direct required components and the transitive closure of their required components.

Even when doing DFS for every component it's a tricky problem because you have a circular dependency: you need to initialize the directly required components of your component, which in turn might need to initialize your type. The way this previously worked was a very hacky way that basically ended up computing the required components of each directly required component twice.

Another issue I see is with the order of initialization of required components. Currently it's unspecified, but IMO it would not be unreasonable to initialize the required components before the components that require them. Unfortunately this also breaks if there's a cycle between required components.

[cBournhonesque]

For multi-components bundles the current behaviour is to treat it as if there was a "ghost" component that required all the component of the bundle.

I'm not a fan of this as it's not consistent with what happens with a single component (if we assume that we also have a "ghost" component that requires the single component).
Or we can consider that the 'ghost' component approach is only used for multi-component bundles.

My issue with this "rule" is that this is not how it's currently done. There's no DFS scan or stack, instead the transitive closure of required components for a given component is computed from its direct required components and the transitive closure of their required components.

That's similar to a stack, but using the function stack, no? I remember that the implementation was pretty complex, I would have to look at it again.

Even when doing DFS for every component it's a tricky problem because you have a circular dependency: you need to initialize the directly required components of your component, which in turn might need to initialize your type. The way this previously worked was a very hacky way that basically ended up computing the required components of each directly required component twice.

I'm not sure I fully understand.
Are you talking about the A -> [B] and B -> [A(1)] case?
If we insert A(0), B is directly required by A, but we wouldn't consider A(1) since A(0) has higher priority (present in the bundle)

Another issue I see is with the order of initialization of required components. Currently it's unspecified, but IMO it would not be unreasonable to initialize the required components before the components that require them. Unfortunately this also breaks if there's a cycle between required components.

You're saying that if we have A -> [B(1)] and B -> [A(1)] and we insert A(0), then:

• in my opinion we would just initiate B(1) and then A(0) (if the required components are initialized first)
• you're saying that it's unspecified because to initialize B(1) we would want to initialize A(0) first?

[SkiFire13]

I'm not a fan of this as it's not consistent with what happens with a single component (if we assume that we also have a "ghost" component that requires the single component).

I don't see how this is not consistent, can you elaborate?

That's similar to a stack, but using the function stack, no?

You can implement it as such, but the definition is "local", it does not need to specify details concerning the whole stack to describe the final result.

I'm not sure I fully understand.
Are you talking about the A -> [B] and B -> [A(1)] case?
If we insert A(0), B is directly required by A, but we wouldn't consider A(1) since A(0) has higher priority (present in the bundle)

I'm talking about what happens when you do world.register_component::<A>(). When you do that it wants to register B because it depends on it. When registering B you have the issue: while for the purpose of knowing all the required components of A you don't care about recursing into A, for registering B you do care about all the required components that B requires, which includes the required components that A requires!

For an example, imagine you have A requiring B and C, while B requires A. You register A and that recurses into B. B depends on A but since it's on the stack you ignore it. You then go back to A and process C. But what about the required components of B? When you registered B you didn't recurse into A, so B does not include C in its required components.

So you can't just reason about registering a component anymore: you need to reason about registering a whole strongly connected component (in the graph sense of component) of components at all once.

Moreover you can create new strongly connected components when registering runtime required components, so you need to reason about what happens in that case too.

You're saying that if we have A -> [B(1)] and B -> [A(1)] and we insert A(0), then:

• in my opinion we would just initiate B(1) and then A(0) (if the required components are initialized first)
• you're saying that it's unspecified because to initialize B(1) we would want to initialize A(0) first?

Yeah. It's not really an issue in this case, but you will no longer be able to say "the hooks for all required components run before/after the hooks for the requiring component" because this case would break it. It's not a dealbreaker and you can probably specify some other useful order that allows cyclic requirements, but it's something to take into consideration before making a decision.

[cBournhonesque]

I don't see how this is not consistent, can you elaborate?

Let's say we have A -> [B, Z(1)] and B -> [Z(2)], if you insert A you get [A, B, Z(1)] since Z(1) is a direct require.
But if we consider that we have a ghost component G that requires A, we would apply a DFS, so we get [A, B, Z(2)]

you will no longer be able to say "the hooks for all required components run before/after the hooks for the requiring component"

I think that's fine, the rule could also be declared as 'hooks are run from deepest in the DFS from shallowest' (or basically hooks follow the inverse order of priority as required components), which will still be the case with cyclic required components.

As for the registration issue that sounds like a real problem, but tbh i didn't really understand the nuances of registration. I don't get the subtlety of why "for registering B you do care about all the required components that B requires" even though for the use case of inserting required components its ok to cut the DFS short early.
Is it that 'registering a component' also involves 'computing the list of its required components', so for B we should track that it indirectly requires C (via A)?

Anyways I will try to come up with an implementation so that we have something concrete to discuss!

[SkiFire13]

Let's say we have A -> [B, Z(1)] and B -> [Z(2)], if you insert A you get [A, B, Z(1)] since Z(1) is a direct require.
But if we consider that we have a ghost component G that requires A, we would apply a DFS, so we get [A, B, Z(2)]

No, in both cases Z(1) would be picked. The logic for picking the required components constructors works by doing a DFS, but the components visited by the DFS are not the ones picked for the constructors, instead their direct requirements are.

So in the example of A, the DFS starts by visiting A and picking its direct required components [B, Z(1)], then it visits B but doesn't pick Z(2) because it was already picked and finally Z is visited but it doesn't have requirements. A is of course included anyway because it's the component being inserted, so you end up with [A, B, Z(1)]

If you see it with using ghost component that requires A then first the ghost component is visited, and its direct required component A is picked, then A is visited and its direct required components are picked [B, Z(1)] then as before B is visited but doesn't pick Z(2) because it was already picked and finally Z is visited but it doesn't have requirements. You still end up with [A, B, Z(1)].

To convince yourself that this is the correct behaviour compared to what you described (i.e. a plain DFS), imagine we replaced the ghost component with a real component C -> A: if your behaviour was the real one then C would end up with different required component constructors than A, which is inconsistent.

I think that's fine, the rule could also be declared as 'hooks are run from deepest in the DFS from shallowest' (or basically hooks follow the inverse order of priority as required components), which will still be the case with cyclic required components.

As for the registration issue that sounds like a real problem, but tbh i didn't really understand the nuances of registration. I don't get the subtlety of why "for registering B you do care about all the required components that B requires" even though for the use case of inserting required components its ok to cut the DFS short early.
Is it that 'registering a component' also involves 'computing the list of its required components', so for B we should track that it indirectly requires C (via A)?

It's simple: registering B populates its ComponentInfo, which contains the list of all components that B requires. As for the second question, yes, in the ComponentInfo of B we need to track that it indirectly requires C (via A).

Edit: you might be tempted to skip the ComponentInfo and ask B's Component implementation for its required components, but note that B might be already registered andz some runtime required components might have been added, in that case they need to end up in the required components of A too.