unlit_ecs/
scope.rs

1//! Entity scopes: which entity an entity lives in, and the tree that makes.
2//!
3//! An entity's scope is another entity, not a separate identifier space, so the
4//! relation between entities is a tree of handles. The tree that results is what
5//! a [`Scope`](crate::Scope) sees through: a scope of a scope sees that scope's
6//! whole subtree.
7//!
8//! The tree is the one copy of the relation. It is kept here rather than in a
9//! component because visibility is decided on every access, and a component
10//! would have to be borrowed to answer it: a caller holding a component of one
11//! entity must not make the visibility check of another entity depend on what is
12//! borrowed. Only the world writes the tree, so the recorded parent and the
13//! archetype's per-scope row counts have one writer rather than several.
14//!
15//! Two entities are special: the root owns the world, and the shared scope's
16//! subtree is visible to every scope.
17
18use crate::entity::Entity;
19use crate::error::EntityAccessError;
20use crate::hash::EntityHashMap;
21
22/// The parent and child links of every live entity.
23#[derive(Default)]
24pub(crate) struct ScopeTree {
25    parents: EntityHashMap<Entity>,
26    children: EntityHashMap<Vec<Entity>>,
27}
28
29impl ScopeTree {
30    /// Record that `entity` lives in `parent`, dropping its old link.
31    pub(crate) fn attach(&mut self, entity: Entity, parent: Entity) {
32        self.detach(entity);
33        self.parents.insert(entity, parent);
34        if parent != entity {
35            self.children.entry(parent).or_default().push(entity);
36        }
37    }
38
39    /// Drop `entity`'s link to its parent, keeping its children linked to it.
40    pub(crate) fn detach(&mut self, entity: Entity) {
41        let Some(parent) = self.parents.remove(&entity) else {
42            return;
43        };
44        let Some(siblings) = self.children.get_mut(&parent) else {
45            return;
46        };
47        if let Some(position) = siblings.iter().position(|&child| child == entity) {
48            siblings.swap_remove(position);
49        }
50        if siblings.is_empty() {
51            self.children.remove(&parent);
52        }
53    }
54
55    /// The parent of `entity`.
56    ///
57    /// Every live entity is attached to the tree in the same step that gives it
58    /// a row, so a handle missing from it names no live entity.
59    pub(crate) fn parent(&self, entity: Entity) -> Result<Entity, EntityAccessError> {
60        self.parents
61            .get(&entity)
62            .copied()
63            .ok_or(EntityAccessError::NotAlive { entity })
64    }
65
66    /// The direct children of `entity`.
67    pub(crate) fn children(&self, entity: Entity) -> &[Entity] {
68        self.children
69            .get(&entity)
70            .map_or(&[], |children| children.as_slice())
71    }
72
73    /// Whether `entity` is strictly below `ancestor` in the tree.
74    ///
75    /// A walk up the parent chain rather than an interval comparison: the tree
76    /// is as deep as a scene nests, which is a handful of levels, while an
77    /// interval index would have to be rebuilt over the whole world on every
78    /// spawn. The walk is bounded by the number of nodes so that a corrupted
79    /// index cannot loop forever.
80    #[must_use]
81    pub(crate) fn is_descendant(&self, ancestor: Entity, entity: Entity) -> bool {
82        let mut current = entity;
83        for _ in 0..=self.parents.len() {
84            let Some(&parent) = self.parents.get(&current) else {
85                return false;
86            };
87            if parent == current {
88                // The root's self-loop: the chain ends without reaching it.
89                return false;
90            }
91            if parent == ancestor {
92                return true;
93            }
94            current = parent;
95        }
96        false
97    }
98
99    /// The subtree rooted at `root`, deepest first.
100    ///
101    /// Post-order is what a cascade despawn needs: a child is removed before
102    /// the parent it lived in, so a child's callback still sees living
103    /// ancestors.
104    pub(crate) fn subtree_post_order(&self, root: Entity) -> Vec<Entity> {
105        let mut ordered = Vec::new();
106        let mut stack = vec![(root, false)];
107        while let Some((entity, expanded)) = stack.pop() {
108            if expanded {
109                ordered.push(entity);
110                continue;
111            }
112            stack.push((entity, true));
113            for &child in self.children(entity) {
114                stack.push((child, false));
115            }
116        }
117        ordered
118    }
119}
unlit_ecs/scope.rs

unlit_ecs/
scope.rs
