Misleading docs on duplicate required component constructors

[benfrankel]

The required components documentation describes the algorithm for resolving multiple constructors for the same component in a required components tree as follows:

In general, this shouldn’t happen often, but when it does the algorithm is simple and predictable:

1. Use all of the constructors (including default constructors) directly defined in the spawned component’s require list
2. In the order the requires are defined in #[require()], recursively visit the require list of each of the components in the list (this is a Depth First Search). When a constructor is found, it will only be used if one has not already been found.

However, this is not what actually happens. For example, consider this case:

#[derive(Component)]
#[require(B)]
struct A;

#[derive(Component, Default)]
#[require(C, D(|| D(1)))]
struct B;

#[derive(Component, Default)]
#[require(D(|| D(2)))]
struct C;

#[derive(Component)]
struct D(u8);

Now suppose we spawn A. Following the steps described in the docs to determine which constructor will be used for D:

1. The "spawned component" is A, which does not have a constructor for D, so go to step 2.
2. A DFS will visit the components in the order A B C D(2) D(1). So when D(2) is visited, it will be used because D hasn't been found yet; and when D(1) is visited, it will not be used because D has been found already.

This suggests that D(2) will be used as the constructor. But that's incorrect: D(1) is actually used.

[alice-i-cecile]

@cart, do we prefer the implemented behavior or the documented behavior? I think the implemented behavior is better: more locally defined is more likely to be relevant.

[cart]

The implemented behavior is what we want. The documented behavior was intended to capture the implemented behavior:

recursively visit the require list of each of the components in the list (this is a Depth First Search)

This was intended to define the "visiting" behavior as depth-first. Not to run a new naive Depth First Search algorithm, ignoring the previous aspects of the algorithm being defined. The recursion is depth first, but we insert the constructors of the direct requires for a given component before recursing.

I'd support a rephrase that makes it clearer.

[benfrankel]

IIRC it does traverse depth-first, but if a requirement with a higher precedence (lower depth) is found, it overwrites

From @Jondolf on Discord. The updated docs doesn't mention this, so it's still wrong. For example:

A: B, D
B: C
C: E(1)
D: E(2)

Here E(2) will be chosen because it's higher up in the tree, even though the DFS finds E(1) before E(2).

Assuming the algorithm is indeed "DFS in require(...) order but prefer lower-depth constructors", then the fact that it's a DFS is effectively an implementation detail. Every node of the tree will be visited eventually, and in the end the search will select the leftmost matching node of the highest layer with a match, which could equally (or even, more naturally) be implemented as a BFS.

In summary, the updated docs are still inaccurate and describing the algorithm as a DFS is a red herring.