# Rainbow team

This is an informal doc for Bevy's Rainbow team, which is focused on paving the path towards relations support in bevy ecs.

## Terminology

- **Entity**: the identifier for an object in the ECS
- **Generational index**: id composed of an index (usually 32 bits) and a generation (32 bits). Entities use a generational index. The generation is a basically a counter of how many times a given index has been recycled in the world. A world will never have two alive entities that share the same index.
- **Relation**: a 'special' component that represents the combination of a Component and an Entity ( [Eats, Entity1]) or a Component and a Component ([Eats, Fruits]).
- **Component entity**: a Component which is stored in the ECS as an Entity. (the id of the Component is an Entity with 64 bits)
- **Wildcard**: a special id in a relation that represents 'Any'. For example [Eats, \*] would represent "eats anything".
- **Observers**: a callback that is triggered when an ECS event happens (Component is Added/Removed, etc.)

## General plan (not in order)

**1. Represent relations using an Entity identifier**

The plan is to represent relations similarly to [what flecs did](https://ajmmertens.medium.com/doing-a-lot-with-a-little-ecs-identifiers-25a72bd2647):
- components are represented as 64 bits Entities
- a relation (Component+Entity or Component+Component) can fit into 64 bits by using a simple trick:
- the first 32 bits are the index of the Component Entity (we discard the generational index, which shouldn't be a problem because a Component doesn't get removed, so we don't need to keep track of its generation)
- the last 32 bits are the index of the Component Entity, or of the Entity. (we discard the generational index, which again is not a problem because the world will never have 2 live entities that have the same index)

This means that `[Likes, Dogs]` and `[Likes, Cats]` are 2 relations that can be added to the same entity, because they have different ids.

- [x] **2. Add a ComponentIndex**

The component-index is essentially a map from a `ComponentId` to:
- all the archetypes that contain this component
- for the archetypes that contain this component, the column number of that component in the Table of that Archetype

This would let us efficiently find all the archetypes that contain the "relation/component" `[Likes, Dogs]`.
This is necessary so that we can:
- efficiently do archetype cleanup. If the entity `Entity1` is despawned, we want all relations of the type `[*, Entity1]` to also be despawned. This means that we need to identify all the archetypes that contain this component, which is what the ComponentIndex is for.
- efficiently update the query state. The query state is a cache that lets us iterate quickly through the matching archetypes of the query. Currently we just iterate through all archetypes and check if they match the query. But with the component index, we could instead iterate only through the archetypes that contain the components of the query!

- [x] **3. Merge observers**

Observers [PR](https://github.com/bevyengine/bevy/pull/10839) is a work to create callbacks that are triggered whenever an `Event` happens. Users can register their own events, and some ECS-level events are provided (OnAdd, OnUpdate, OnRemove).

These will be useful to update the ECS-internals whenever an ECS change happens

**4. Make queries Entities so that they can be accessed by observers**

We said earlier that we need to optimize the query cache because the number of archetypes will be much higher. One way to do this (also done by Flecs) is to make Queries Entities, and the QueryState (the internal cache of the query) a Component. Why? So that observers can update the query state every time a component gets added/updated/removed. Then we won't need to iterate through every archetype to update the query states, instead we will just have the observer callbacks to 'targeted' updates for us!

**5. Archetype cleanup**

If an entity used in a pair is deleted (for example with the relation `[Eats, Entity1]`, if `Entity1` or `Eats` is deleted), then we need to delete all the relations that used this entity.
The main reason is that the `Entity1` in `[Eats, Entity1]` only uses the **index** part of the Entity. Since the entity `Entity1` was despawned, we could have another entity `Entity2` that re-uses the same index but with a different generation! This means that all existing relations of the shape `[*, Entity1]` would also represent `[*, Entity2]`, since `Entity1` and `Entity2` have the same index!

This is obviously incorrect, so we need to clear all relations that contained `Entity1`.

What do we need to do?
- Update the query caches so that they can skip the deleted archetypes
- Update the archetype index to actually delete the archetype
- Update the archetype graph
- Update the component index

**6. Update queries to be able to work with relations**

This is the payoff, we want to be able to write queries of the form:
`world.query<(Entity, Targets<Eats>)>()`

TODO:
- the API needs to be defined

**7. Extras**

- Store data in component-entities?
- Uncached query
- etc.

## Potential API

### Adding relations

#[derive(Component)]
struct Likes;

world.entity_mut(source_entity_a)
    .insert_relation::<Likes>(target_entity_b)
    .remove_relation::<Likes>(target_entity_b)
    .insert_relation::<Likes>(target_component_c)
    .remove_relation::<Likes>(target_component_c)
    .insert_relation::<Likes, Component>() // 2 types provided if the relation is between 2 components?
    .insert_relation(likes_component, target_component); // less-typed API

command.entity(source_entity_a)
	.insert_relation::<Relationship>(target_entity_b)
	.remove_relation::<Relationship>(target_entity_b)
	.insert_relation::<Relationship>(target_entity_b)
	.remove_relation::<Relationship>(target_entity_b);

To be discussed:
- should components that appear in relations have an explicit `#[derive(Relation)]` ?
- do we want an API like `insert_relation::<Likes, Dogs>()` for when the relation is a `[Component, Component]` pair?
- should we also have less-typed apis like `command.entity(source_entity).insert_relation(component_entity, target_entity)` ?

### Has relation / Targets

#[derive(Component)]
struct Eats;

let alice_mut = world.entity_mut(alice);

alice_mut
    .insert_relation::<Eats, Fruits>()
    .insert_relation::<Eats>(apple)
	.insert_relation::<Eats>(banana);

alice_mut.has_relation<Eats>(apple); // does alice have the [Eats, apple] relation?
alice_mut.has_relation<Eats, Fruits>(); // does alice have the [Eats, Fruits] relation?
alice_mut.has_relation<Eats, Wildcard>(); // does alice have any [Eats, *] relation?

for target in alice_mut.targets<Eats>() { // targets X in the relations [Eats, X] that alice has
	// target == apple
	// target == banana
}

### Queries

// OPTION 1
let query = world.query<(Entity, Targets<Eats>)>();/
for entity, targets in query.iter(&world) {
	// entity == alice
	for target in targets {
		// target == apple
		// target == banana
	}
}
let query = world.query<Entity, With<Targets<Eats>>>();
for entity in query.iter(&world) {
	// entity == alice
}

To be discussed:
- for an entity E, how do we find all the entities E' where E' have the [C, E] relation? or the [*, E] relation?

## Immediate next steps (in order)

graph TD
    A[A: Update Table/Archetype to remove SparseSets]
    B[B: Add a ComponentIndex]
    C[C: Update queries to use ComponentIndex]
    D[D: Merge observers]
    E[E: Update observers to use ComponentIndex]
    F[F: Queries as entities]
    G[G: Archetype cleanup]
    H[H: Introduce relations]
    B --> C
    B & D --> E
    D & C--> F
    A & F --> G
    G --> H

**A: Update Table/Archetype to remove SparseSets**
- Table and Archetype both have a SparseSet of `ComponentId`, which is intractable as the number of components will explode.
- We need to rework their storage

**B: Add a ComponentIndex**
- We need a way to map from ComponentId to the list of Archetypes that contain this component
- Used for
- efficiently preparing Query states. (iter only through archetypes which contain a Component present in the query)
- efficiently preparing observer states
- used in archetype cleanup

**C: Update queries to use ComponentIndex for query state creation**
- We can use the ComponentIndex to more efficiently prepare query caches, by not iterating through all archetypes, but only through the archetypes that might contain the components in the Query.
- Possible impl:
- For each WorldData in the query, get the set of archetypes that contain this component

**D: Merge observers**
- Observers will play the key part of being to keep ECS internals up-to-date on ECS events (component inserted/removed and entity deleted)
- PR: https://github.com/bevyengine/bevy/pull/10839

**E: Update observers to use ComponentIndex**
- Observer creation can be made more efficient using ComponentIndex (@James)

**F: Queries as entities**
- We want to update the query states efficiently.
- Instead of iterating though all archetypes (which is unfeasible because the number of archetypes will explode), we model queries as entities and use observers to update the query state (which is a component on the query-as-entity) whenever a component gets removed/added, etc.

**G: Archetype cleanup**
- When an entity gets deleted, we might have to delete an archetype
- Cleanup the archetype index
- Cleanup the archetype graph
- Cleanup the query states: store the matches tables/archetypes using a indexed linked list, which enables addition/removal and iteration
- Cleanup the component index

## Blockers

### Extracting all entities to the Render world

Issue: https://github.com/bevyengine/bevy/issues/12144

**Problem:** it's problematic for internal book-keeping if we move more things (Queries, Systems, Components) to becoming entities. In the Render world we currently require all entities to be dropped at the end of the frame, because we want the entity ids to match between the main world and the render world. But if we despawn all entities, we also despawn observers, queries, etc. (once they are implemented as entities) so the ECS of the render world will break down.

**Solutions:**

1. [@pcwalton](https://discord.com/channels/691052431525675048/1237010014355456115/1237089327335346246): we don't need to extract much apart from Views and maybe lights. It would be possible to move views/lights to table resources. Then the render world doesn't need to extract any entity from the main world, so the render world doesn't need to despawn entities by the end of every frame.
2. [@joy](https://discord.com/channels/691052431525675048/1237010014355456115/1237090465564594206): it might be possible to move everything in the RenderSet apart from `Render` and `Cleanup` to the main world. (i.e. do the prep work in the main world, and the actual rendering that requires GPU in the render world)
-> looks like this is not viable

3. Retained entities in the render world. This is some work by @robswain where it wouldn't be required to despawn entities in the render world.

4. Remove the need for entity ids to match between the main world and render world; then we wouldn't need to despawn entities in the render world

5. Don't store observers as entities (and don't model queries/systems as entities)

### Archetype cleanup

**Problem:** when an entity E is despawned, we need to make sure that all archetypes that included that entity as a target (i.e. that included a component of shape (Component, E)) are destroyed. Otherwise, a future entity re-using the id E (but with a different generation) would be interpreted as the past entity. (because with relations, we use only the index of the entity, not the generation)
Basically we need to delete all archetypes in the shape (E), (*, E), (E, *).

When the archetype gets deleted, we must cleanup:
- the Archetypes index
- the Archetype graph
- the QueryState in all the cached queries
- the ComponentIndex

**Solutions**

1. For archetype cleanup, the data structure used by flecs is roughly

struct ArchetypeGraph {
    nodes: Vec<*mut Archetype>,
    edges: Vec<*mut ArchetypeEdge>,
    index: HashMap<ArchetypeDef, Archetype>,
}

/// All entities that have the same specific set of components.
pub struct Archetype {
    edges: ArchetypeEdges,
    /* ... */
}

/// All known edges connecting an archetype to others.
pub(crate) struct ArchetypeEdges {
    // outgoing edges are tracked using a map 
    outgoing_insert: IndexSet<*mut ArchetypeEdge>,
    outgoing_remove: IndexSet<*mut ArchetypeEdge>,
    // index outgoing edges by component (for graph traversal when processing structural changes)
    outgoing_insert_index: IndexMap<Identifier, *mut ArchetypeEdge>,
    outgoing_remove_index: IndexMap<Identifier, *mut ArchetypeEdge>,
    // incoming edges are tracked using a linked list.
    incoming_insert: Option<*mut ArchetypeEdge>,
    incoming_remove: Option<*mut ArchetypeEdge>,
}

/// The details of a previous move from one archetype to another.
pub(crate) struct ArchetypeEdge {
    src: *mut Archetype,
    dst: *mut Archetype,
    /// Whether a component was added or removed.
    removed: bool,
    /// The component that is added or removed by this edge.
    component_id: Identifier,
    prev_incoming: Option<*mut ArchetypeEdge>,
    next_incoming: Option<*mut ArchetypeEdge>,
}

* Have a better data structure than a vector to hold the list of all Archetypes.

Currently we store all archetypes of the world in a vector, not efficient for deletion.

2. For updating the Query States

* One option is to have Queries as Entities, and we can use observers to update the Query's state whenever an archetype gets deleted

* Another option is to use `Arc<RwLock<dyn System>>` instead of `Box<dyn System>` to store system. Then on archetype deletion we could directly access the Query State in every system that might be impacted by the archetype deletion.
(I didn't understand if a pre-requisite for this is still that we use observers to re-act on archetype deletions)

### Query state cache

**Problem:** As the number of archetypes explodes, the current way of updating each Query's cache (by iterating through every new archetype since the query was accessed) will become too inefficient.

**Solutions:**

1. Again, represent each Query as an entity (with the query state as a component inside that entity), and use observers to update the Query's state whenever an archetype relevant to that query gets updated. **This is also what flecs does (use observers to update the query state)**

2. Have a better data structure than a vector to hold the list of all Archetypes.

### Access bitsets

**Problem:** We use various bitsets in `QueryState` and `SystemMeta` to track the list of `ComponentIds` and `ArchetypeComponentIds` that are accessed by the Query or System.
These might not scale if the number of archetypes in the World greatly increases.

**Solutions:**

1. For each ComponentId, we could assign a bitset id incremented from 0, so that the bitset sizes don't explode in memory
2. Replace the bitsets with sorted SmallVecs

3. Consider (R, *) as one access (where we only include R in the bitset). This would limit the ability to parallelize between (R, E1) and (R, E2).

4. @joy Maybe use generation indices (e.g. SlotMap)

### SparseSet components

**Problem:**

**Solutions:**

## References

RFC for relations: https://github.com/bevyengine/rfcs/pull/79

Sander Mertens posts:
* [re-using entity identifies for relations](https://ajmmertens.medium.com/doing-a-lot-with-a-little-ecs-identifiers-25a72bd2647)
* [guide to entity relations](https://ajmmertens.medium.com/building-games-in-ecs-with-entity-relationships-657275ba2c6c)
* [roadmap to entity relations](https://ajmmertens.medium.com/a-roadmap-to-entity-relationships-5b1d11ebb4eb)