Feature name: `minimal-relations-api`

Summary

Relations allow users to create logical connection between entities. Each source entity can have multiple kinds of relations, each with their own data, and multiple relations of the same kind pointing to a different target entity. Queries are expanded to allow efficient filtering of entities by the relations they have or the targets of these relations.

This RFC covers the very first step of a minimal user facing API for relations that can replace the current Parent/Children hierarchy that is in use. It does not make decisions on implementation issues, nor does it make decisions between fragmenting and non-fragmenting relations. It should be future-proof in the sense that we estimate that there's a reasonable path forward from it without breaking backward compatibility too badly, but it is not meant to solve the full set of challenges around a relations API.

Motivation

Relations have been talked about for a long time in Bevy, and a lot of work has been done towards them, but the long term solution is gated behind a lot of implementation issues. At the same time, many people have tried to make incremental improvements to the current situation, which have been largely thwarted by them not aligning with the long term solution. Yet, the requirements set by the long term solution have not been written down, and there isn't a generally accepted consensus as to what they exactly are. This puts everybody that tries to work with relations against an impossible task of adhering to requirements that are unstated.

The primary motivation for this RFC is meant to break that deadlock by explicitly specifying the requirements for the relations API, so that any incremental improvement that fulfills those requirements can avoid having the design discussions mixed in with the implementation discussions in the same pull request. This means it can be very incremental from the current hierarchy implementation in Bevy, as long as it enables movement forward in this space.

A secondary motivation for this RFC is making the design constraints explicit on the long term relations implementation. For example, there are varying opinions on the expected level of consistency under different types of mutation operations, directly exposing components to users, interaction with reflection and so on. Without specifying these design constraints clearly, the same sort of issues will happen also for the long term plans where different expectations on the design get mixed up with the implementation and performance issues.

It is not a goal for this specification to solve all the use cases around relations or to specify advanced query APIs that do not exist today. The aim is to avoid spending time thinking about things which are better discussed as concrete implementation proposals or further specifications, but instead to just set the sandbox inside which these proposals live.

Guide-level explanation

Reference-level explanation

Drawbacks

Rationale and alternatives

Q1: Should relation changes be atomic?

When relations are changed (added, removed, replaced, etc.), should all the related changes be immediately visible or can there be a delay? Concretely for example if changing the Parent of an entity, should corresponding Children change immediately, or only after a flush, or after some scheduled systems have had a change to run? Alternatively, should there be any cases where an inconsistent view of relations is observable, or should every change immediately be made consistent so that there is no way to see the world in an inconsistent state?

In the past, Bevy has had Parent/Children implemented through systems that used change detection events, which meant that if you manually changed some things, not everything was immediately updated. Today, all changes to hierarchy must be done through commands and independent hierarchy APIs that atomically do modifications. Manually changing the components is not supported.

Suggestion: All relationship modifications are required to be atomic. The world should never be observable in an inconsistent state, except perhaps during the execution of hooks.

Should any components used in the implementation of relations be private and unmodifiable by users except through explicitly bypassing API safeguards?

Note: just a sample description so far, not decided upon.

Currently, components such as Parent and Children are public, even though their data fields are not. This allows the user to manually insert, replace or remove them.

In the actual relations implementation, components might not be the storage for relations at all, and even if it is, the logic and consistency of that implementation might not support the user manually changing these instead of going through an API. Keeping backward compatibility with the component based approach might be especially difficult if we continue to allow them to be public, or even bless more ways to manually manipulate them.

Hence, it is better to treat all concrete components used in relations as implementation details and hide them as much as possible. For backward compatibility, we should provide QueryData and Bundle for the existing components, but deprecate that usage in the long term.

Decision: Components on entities for relations should be treated as implementation details and not exposed to users.

Should children of an entity be treated ordered or unordered?

Fill in explanation and alternatives.

Decision: Fill in decision.

Prior art

Flecs, an advanced C++ ECS framework, has a similar feature, which they call "relationships". These are somewhat different, they use an elaborate query domain-specific language along with being more feature rich. You can read more about them in the docs or corresponding PR.

You can, of course, build similar data structures using the ECS itself. Here's a look at the complexities involved in doing so in EnTT.

Unresolved questions

Future possibilities

SCRATCHSPACE

Edit and add whatever below here, used just a workspace for keeping things around.

Current hierarchy API

despawn_with_children_recursive
ChildBuilder / WorldChildBuilder / ChildBuild
- spawn
- spawn_empty
- parent_entity
- enqueue_command
HierarchyEvent
- ChildAdded { child: Entity, parent: Entity }
- ChildRemoved { child: Entity, parent: Entity }
- ChildMoved { child: Entity, previous_parent: Entity, new_parent: Entity }
BuildChildren / BuildWorldChildren
- with_children
- with_child
- add_children
- insert_children
- remove_children
- add_child
- clear_children
- replace_children
- set_parent
- remove_parent
DespawnRecursiveExt
- despawn_recursive
- despawn_descendants
- try_despawn_recursive
- try_despawn_descendants
HierarchyQueryExt
- parent -> Option<Entity>
- children -> &[Entity]
- root_ancestor -> Entity
- iter_leaves -> Iterator<Item=Entity>
- iter_siblings -> Iterator<Item=Entity>
- iter_descendants -> Iterator<Item=Entity>
- iter_descendants_depth_first -> Iterator<Item=Entity>
- iter_ancestors -> Iterator<Item=Entity>
Parent
- get
- as_slice
- Deref<Target=Entity>
Children
- sort_by
- sort_by_cached_key
- sort_by_key
- sort_unstable_by
- sort_unstable_by_key
- swap
- Deref<Target=[Entity]>
VisitEntities / VisitEntitiesMut
Traversal

Notes:

Children/Parent have no constructors, and the entity is private, so the expectation is that they are read-only and the "blessed API" is used to make changes

Private vs Public Relationship Types

While the components of a relationship should be considered an implementation detail, and thus be private, the relationship itself is public. In other words, the Parent component should be private, but knowing that one entity is the parent of another is public.

A possible mechanism to support this distinction is to have public marker types (e.g, ChildOf), and private storage. for example:

pub struct ChildOf;

#[derive(Component)]
struct Relationship<T> {
    entity: Entity,
    _phantom: PhantomData<T>,
}

Note that in the above example, Relationship is an implementation detail, and could be replaced with any other storage mechanism (e.g., resources).

Actionable takeaway: relationships need a public name. A simple solution for that name is a ZST component.

#[derive(Component)]
pub struct Eats;

Open Question: Should relationship markers be allowed to include data (a non-ZST)?

Relationship Invariants

Certain types of relationships may have invariants that should be encoded into the relationship system where possible. Typical invariants include:

Acyclic (e.g., no entity is its own ancestor in a parent/child hierarchy)
Tree-Like (e.g., acyclic and all entities share a common ancestor)
One-to-One (e.g., if A points to B, then B points to A)

Feature name: minimal-relations-api