# Objective

Support queries that soundly access multiple entities.  

This can be used to create queries that follow relations, as in #17647.

This can also be used to create queries that perform resource access.
This has been supported since #16843, although that approach may become
unsound if we do resources-as-components #19731, such as #21346.

Fixes #20315

## Solution

Allow a `QueryData` that wants to access other entities to store a
`QueryState<D, F>` in its `WorldQuery::State`, so that it can create a
nested `Query<D, F>` during the outer `fetch`.

### `NestedQuery` type

Introduce a `NestedQuery` type that implements `QueryData` by yielding a
`Query`. It is intended to be used inside other implementations of
`QueryData`, either for manual implementations or
`#[derive(QueryData)]`. It is not normally useful to query directly,
since it's equivalent to adding another `Query` parameter to a system.

In theory, we could directly `impl QueryData for Query`, but this would
be too easy to do accidentally. Having to explicitly import and write
`NestedQuery` will make it clear that it's something unusual, and also
allows us to remove the need for passing `'static` for the `'w` and `'s`
lifetimes.

### New `WorldQuery` methods

For it to be sound to create the `Query` during `fetch`, we need to
register the `FilteredAccess` of the nested query and check for
conflicts with other parameters. Create a
`WorldQuery::update_external_component_access` method for that purpose.
For `Query as SystemParam`, call this during `init_access` so the access
can be combined with the rest of the system access. For loose
`QueryState`s, call it during `QueryState::new`.

In order to keep the query cache up-to-date, create a
`WorldQuery::update_archetypes` method where it can call
`QueryState::update_archetypes_unsafe_world_cell`, and call it *from*
there.

### New `QueryData` subtraits

Some operations would not be sound with nested queries! In particular,
we want a `Parent<D>` query that reads data from the parent entity by
following the `ChildOf` relation. But many entities may share a parent,
so it's not sound to iterate a `Query<Parent<&mut C>>`.

It *is* sound to `get_mut`, though, so we want the query type to
*exist*, just not be iterable. And following the relation in the other
direction for a `Query<Children<&mut C>>` is sound to iterate, since
children are unique to a given parent.

So, introduce two new `QueryData` subtraits: 
* `IterQueryData` - For anything it's sound to iterate. This is used to
bound `iter_mut` and related methods.
* `SingleEntityQueryData` - For anything that only accesses data from
one entity. This is used to bound `EntityRef::get_components` (see
#20315). It's also used to bound `transmute` at the moment, although we
may be able to relax that later (see below, under Future Work).

Note that `SingleEntityQueryData: IterQueryData`, since single-entity
queries never alias data across entities, and `ReadOnlyQueryData:
IterQueryData`, since it's always sound to alias read-only data.

Here is a summary of the traits implemented by some representative
`QueryData`:

| Data | Iter | ReadOnly | SingleEntity |
| -- | -- | -- | -- |
| `&T` | ✓ | ✓ | ✓ |
| `&mut T` | ✓ | x | ✓ |
| `Parent<&T>` | ✓ | ✓ | x |
| `Parent<&mut T>` | x | x | x |
| `(&mut T, Parent<&U>)` | ✓ | x | x |
| `Children<&mut T>` | ✓ | x | x |

## Alternatives

We could avoid the need for the `IterQueryData` trait by making it a
requirement for *all* `QueryData`. That would reduce the number of
traits required, at the cost of making it impossible to support
`Query<Parent<&mut C>>`.

## Showcase

Here is an implementation of a `Related<R, D, F>` query using this PR: 

<details>

```rust
pub struct Related<R: Relationship, D: QueryData + 'static, F: QueryFilter + 'static = ()>(
    RelatedInner<R, D, F>,
);

type RelatedInner<R, D, F> = (
    &'static R,
    NestedQuery<D, (F, With<<R as Relationship>::RelationshipTarget>)>,
);

unsafe impl<R: Relationship, D: QueryData + 'static, F: QueryFilter + 'static> WorldQuery
    for Related<R, D, F>
{
    type Fetch<'w> = <RelatedInner<R, D, F> as WorldQuery>::Fetch<'w>;
    type State = <RelatedInner<R, D, F> as WorldQuery>::State;

    fn shrink_fetch<'wlong: 'wshort, 'wshort>(fetch: Self::Fetch<'wlong>) -> Self::Fetch<'wshort> {
        <RelatedInner<R, D, F> as WorldQuery>::shrink_fetch(fetch)
    }

    unsafe fn init_fetch<'w, 's>(
        world: UnsafeWorldCell<'w>,
        state: &'s Self::State,
        last_run: Tick,
        this_run: Tick,
    ) -> Self::Fetch<'w> {
        unsafe {
            <RelatedInner<R, D, F> as WorldQuery>::init_fetch(world, state, last_run, this_run)
        }
    }

    const IS_DENSE: bool = <RelatedInner<R, D, F> as WorldQuery>::IS_DENSE;

    unsafe fn set_archetype<'w, 's>(
        fetch: &mut Self::Fetch<'w>,
        state: &'s Self::State,
        archetype: &'w Archetype,
        table: &'w Table,
    ) {
        unsafe {
            <RelatedInner<R, D, F> as WorldQuery>::set_archetype(fetch, state, archetype, table)
        };
    }

    unsafe fn set_table<'w, 's>(
        fetch: &mut Self::Fetch<'w>,
        state: &'s Self::State,
        table: &'w Table,
    ) {
        unsafe { <RelatedInner<R, D, F> as WorldQuery>::set_table(fetch, state, table) };
    }

    fn update_component_access(state: &Self::State, access: &mut FilteredAccess) {
        <RelatedInner<R, D, F> as WorldQuery>::update_component_access(state, access);
    }

    fn init_nested_access(
        state: &Self::State,
        system_name: Option<&str>,
        component_access_set: &mut FilteredAccessSet,
        world: UnsafeWorldCell,
    ) {
        <RelatedInner<R, D, F> as WorldQuery>::init_nested_access(state, system_name, component_access_set, world);
    }

    fn init_state(world: &mut World) -> Self::State {
        <RelatedInner<R, D, F> as WorldQuery>::init_state(world)
    }

    fn get_state(components: &Components) -> Option<Self::State> {
        <RelatedInner<R, D, F> as WorldQuery>::get_state(components)
    }

    fn matches_component_set(
        state: &Self::State,
        set_contains_id: &impl Fn(ComponentId) -> bool,
    ) -> bool {
        <RelatedInner<R, D, F> as WorldQuery>::matches_component_set(state, set_contains_id)
    }

    fn update_archetypes(state: &mut Self::State, world: UnsafeWorldCell) {
        <RelatedInner<R, D, F> as WorldQuery>::update_archetypes(state, world);
    }
}

unsafe impl<R: Relationship, D: QueryData + 'static, F: QueryFilter + 'static> QueryData
    for Related<R, D, F>
{
    const IS_READ_ONLY: bool = D::IS_READ_ONLY;
    type ReadOnly = Related<R, D::ReadOnly, F>;
    type Item<'w, 's> = Option<D::Item<'w, 's>>;

    fn shrink<'wlong: 'wshort, 'wshort, 's>(
        item: Self::Item<'wlong, 's>,
    ) -> Self::Item<'wshort, 's> {
        item.map(D::shrink)
    }

    unsafe fn fetch<'w, 's>(
        state: &'s Self::State,
        fetch: &mut Self::Fetch<'w>,
        entity: Entity,
        table_row: TableRow,
    ) -> Self::Item<'w, 's> {
        let (relationship, query) =
            unsafe { <RelatedInner<R, D, F> as QueryData>::fetch(state, fetch, entity, table_row) };
        query.get_inner(relationship.get()).ok()
    }
}

unsafe impl<R: Relationship, D: ReadOnlyQueryData + 'static, F: QueryFilter + 'static> ReadOnlyQueryData for Related<R, D, F> { }

// Note that we require `D: ReadOnlyQueryData` for `Related: IterQueryData`
unsafe impl<R: Relationship, D: ReadOnlyQueryData + 'static, F: QueryFilter + 'static> IterQueryData for Related<R, D, F> { }
```

</details>

I'd like to leave that to a follow-up PR to allow bikeshedding the API,
and to take advantage of #21581 to remove the `Option`, but I think it
works!

## Future Work

There is more to do here, but this PR is already pretty big. Future work
includes:

* #17647
* Following #21346, update `AssetChanged` to use nested queries for
resource access, and stop tracking resource access separately in
`Access`
* Implement `get_state` for `NestedQuery`. This is difficult because
constructing a `QueryState` requires reading the `DefaultQueryFilters`
resource, but `get_state` can be called from `transmute` with no access.
* Relax the `SingleEntityQueryData` bound on transmutes and joins. This
will require checking that the nested query access is also a subset of
the original access. Although unless we also solve the problem of
implementing `get_state`, transmuting to a query with nested queries
won't work anyway.
* Support streaming iteration for `QueryIter` by offering a `fn
fetch_next(&self) -> D::Item<'_>` method and relaxing the
`IterQueryData` bound on `Query::into_iter` and `Query::iter_mut`. This
would work similar to `iter_many_mut` and `iter_many_inner`.
* Relax the `IterQueryData` bound on `Query::single_inner`,
`Query::single_mut`, and `Single<D, F>`. This seems like it should be
straightforward, because the method only returns a single item. But the
way it checks that there is only one item is by fetching the second one!