Skip to content

Status: approved

ecs-relations

Summary

@workspace/ecs-relations v0 adds three groups of flecs relationship features on top of koota, which has none of them: (A) relation traits, symmetric (a pair R(a, b) is mirrored as R(b, a)) and transitive (isReachable(a, R, b) plus an optional materialized closure relation), (B) traversal helpers, up (find the first entity along a relation that has a trait, walking depth-first in entity-id order) and cascade (iterate matching entities ordered by relation depth), and (C) hierarchies, a ChildOf relation, a Name trait, and path lookup. Koota relations are opaque: they carry no trait flags, and koota hooks cannot veto or see the final state of a removal. So relation traits are installed per world through world.onAdd / world.onRemove hooks, not declared on the relation (concept §4, §6). The driving demo is apps/demo-ck3 (concept §8: transitive VassalOf, symmetric MarriedTo / AlliedWith, up, ChildOf with names). No docs/products/demo-ck3.md exists yet, so the requirements follow the concept mapping and the W-008 scope only.

References

  • flecs:
  • ComponentTraits.md: § Symmetric trait (adding (R, Y) to X adds (R, X) to Y, and removal is mirrored), § Transitive trait (R(A, B) and R(B, C) give R(A, C)), § Reflexive trait (not ported), § Traversable trait (Acyclic, not ported).
  • Relationships.md: § The ChildOf relationship (children are deleted with the parent), § Namespacing (lookup by name, relative to a parent).
  • HierarchiesManual.md: § Get parent and children, § Recursive cleanup, § Depth-first traversal, § Breadth-first traversal (cascade), § Namespacing.
  • Queries.md: § Relationship Traversal (up is depth-first: the first instance of the relationship is followed to its root before the second; Self/Up flags; Cascade orders by hierarchy depth), § Transitive Relationships.
  • flecs tests reference/flecs/test/core/src/Pairs.c: Pairs_add_symmetric_relation, Pairs_remove_symmetric_relation, Pairs_delete_entity_w_symmetric_relation, Pairs_add_symmetric_exclusive_relation (a symmetric exclusive relation moved from B to C drops B(A) and gives C(A)).
  • flecs tests reference/flecs/test/core/src/Hierarchies.c: Hierarchies_rel_path_from_root, Hierarchies_rel_path_from_self (path from self is the empty string); reference/flecs/test/core/src/Lookup.c (path lookup).
  • bitECS / becsy / miniplex: no relation traits to port. bitECS Cascade is the prior art for depth-ordered iteration (concept §3).
  • koota (public API only; verified in reference/koota/packages/core/src):
  • relation({ exclusive, autoDestroy, store }), Rel(target), Rel('*'), entity.add(Rel(t)), entity.remove(Rel(t)), entity.remove(Rel('*')), entity.has(Rel(t)), entity.targetsFor(Rel), entity.targetFor(Rel), world.query(Rel(target)), world.query(Rel('*')), world.onAdd(Rel, (source, target) => …), world.onRemove(Rel, (source, target) => …), world.has(entity), createQuery, Not, trait, entity.id().
  • Prior art for the hierarchy: .github/skills/koota/references/relations.md (§ Hierarchies, § Finding ancestors, § Ordered Relations).
  • concept §4, §6, §8, package-rules.

Koota limits the package works within

The requirements below are written so that none of them needs $internal or a patch. Each limit is cited as KLn in the requirements.

  • KL1 Relations are opaque. relation() returns a callable that carries only internal context ($internal). There is no public way to attach a flag (symmetric, transitive, traversable) or to read its options (exclusive, autoDestroy, store). So the package cannot mark a relation, cannot tell whether it is exclusive, and cannot copy or check its pair data. Traits are installed per world by hooks (REL-001, REL-040) and callers must pass compatible relations (documented, REL-155).
  • KL2 Hook timing. world.onAdd(Rel, cb) runs after the pair is added, with (source, target), for specific targets only (adding Rel('*') is a no-op). world.onRemove(Rel, cb) runs before the pair is removed: inside the callback source.has(Rel(target)) is still true. It runs once per pair for remove(Rel(t)), remove(Rel('*')), remove(RelTrait), replacement of an exclusive pair, and the cleanup done when either end is destroyed or the world is reset (reference/koota/packages/core/src/trait/trait.ts: addRelationPair, removeRelationPair, cleanupRelationTarget, removeTrait; entity/entity.ts destroyEntity). Consequences: a naive removal mirror recurses without end (a.remove runs the hook, which removes b → a, which runs the hook for b → a, which calls a.remove(Rel(b)) while a → b still exists), so mirroring needs a re-entrancy guard (REL-010). A closure recomputed inside the hook must ignore the edge being removed (REL-043). The hook is also called when nothing is removed: removeRelationPair returns early only if the entity has no Rel pair at all, then calls the remove subscriptions for (entity, t) before checking that the entity has Rel(t). So if entity has some Rel pair but not Rel(t), entity.remove(Rel(t)) fires the hook for (entity, t) with entity.has(Rel(t)) === false, and nothing is removed. User hooks see that spurious call and the package cannot suppress it. The hooks of this package MUST ignore a removal when !source.has(rel(target)) (REL-015, REL-054).
  • KL3 Hooks cannot veto. An add cannot be rejected, so cycles in ChildOf or any other relation, and duplicate sibling names, cannot be prevented by the package. Helpers must terminate on cycles instead (REL-064, REL-085, REL-108, REL-124).
  • KL4 Hooks are per world and do not survive world.reset(). reset() destroys all entities (hooks fire during that) and then clears the trait instances and their subscriptions (world/world.ts reset, clearTraitInstance). A package cannot re-install itself without the internal resetSubscriptions, so callers re-install after a reset (REL-152).
  • KL5 Re-adding an existing pair is a silent no-op (no hook). A mirror add therefore ends by itself, and a pair never exists twice.
  • KL6 Reverse lookup and order. The only public reverse lookup is world.query(Rel(target)) (a snapshot of the sources). entity.targetsFor(Rel) is a snapshot in insertion order, except that a removal moves the last target into the freed slot (relation.ts removeRelationTarget). Neither order is a contract, so the package sorts by entity.id() wherever order is observable (REL-063, REL-082, REL-105, REL-128). entity.id() is reused after a destroy, so an order by id is creation order only until ids are recycled.
  • KL7 Not() takes traits only, not pairs. There is no query for "has no ChildOf". Roots are found with entity.targetFor(ChildOf) === undefined. There is no name index: path lookup scans the children of each parent, so it is linear in the number of children per segment, and linear in the number of named entities for the root segment (REL-135).
  • KL8 Entities have no public world accessor. entity.targetsFor, get, has, add work through koota's Number.prototype patch. All helpers therefore take world first, which also lets them validate that an entity is alive (world.has(entity)) and run queries (REL-028, REL-067, REL-109, REL-134).
  • KL9 autoDestroy and exclusive are koota's cleanup model. autoDestroy: 'orphan' (alias 'source') destroys the sources of a pair when its target is destroyed, recursively, through a LIFO queue. The order of destruction inside a subtree is not specified (flecs deletes children before parents). exclusive: true replaces the old target on add (hooks fire: remove, then add).
  • KL10 The wildcard is the string '*'. There is no Wildcard export. Rel('*') works in queries and remove, not in add (KL2).
  • KL11 Names and traversability do not exist. Traits and entities have no names (concept §4), and koota has no Acyclic / Traversable checks, so Name is an ordinary trait (REL-120) and traversal safety comes from visited sets.
  • KL12 ordered() (ordered children) is experimental and not used here.

Requirements

All requirements are [ecs] (model behaviour of the package) unless tagged [ux] (what a developer reading the docs or using the API sees). All are [test] (headless Vitest, fresh koota world per test) unless tagged [manual]. The groups below are sized so that Triage can create one feature item per group: F01 S, F02 S, F03 M, F04 S, F05 S, F06 S, F07 M, F08 S. Areas: A = relation traits (F01 to F03), B = traversal (F04, F05), C = hierarchies (F06, F07), plus F08 for package-wide rules. New IDs are numbered inside the group's range. The ranges do not follow creation order once edge cases are added.

Every group is buildable on its own: a group's requirements only use functions of its own group or of the groups it depends on. Dependencies: F03 depends on F02 (isReachable in REL-046), F07 depends on F06 (ChildOf, children), and F08 depends on F01 to F07 and is implemented last. Every error a function throws names that function (symmetric, transitive, up, parent, children, getPath, lookup) and leaves the world unchanged, and each requirement that throws says so in its own group. isReachable and cascade do not throw for dead entities or unused relations.

Terms: - A pair R(a, b) is a relation R with source a and target b. - Alive means world.has(entity). - The targets of e under R are e.targetsFor(R). - e reaches y under R if there is a path e → t1 → … → y of one or more R pairs. An entity reaches itself only through a cycle. - The sources* of a under R are the entities that reach a (the transitive reverse), found with world.query(R(x)) (KL6).

Area A: Relation traits

REL-F01 Symmetric (S)

  • REL-001 [ecs][test]: symmetric(world, rel) MUST return an unsubscribe function and install hooks on world for rel. After it, a.add(rel(b)) MUST leave both a.has(rel(b)) and b.has(rel(a)) true (flecs Pairs_add_symmetric_relation).
  • REL-002 [ecs][test]: a.remove(rel(b)) MUST leave both a.has(rel(b)) and b.has(rel(a)) false (flecs Pairs_remove_symmetric_relation). Other pairs of a and b MUST be unchanged.
  • REL-003 [ecs][test]: a.remove(rel('*')) MUST remove every rel pair of a and every mirrored pair rel(a) on the former targets. Entities that were never related to a MUST be unchanged.
  • REL-004 [ecs][test]: Destroying a MUST leave no entity with rel(a) and MUST NOT throw. The other side being destroyed first, or in the same cascade (autoDestroy), MUST NOT throw either (flecs Pairs_delete_entity_w_symmetric_relation; KL2, KL9).
  • REL-005 [ecs][test]: Pairs that exist when symmetric(world, rel) is called MUST be mirrored at install time, so the final state is symmetric for every existing pair.
  • REL-006 [ecs][test]: For an exclusive: true relation, a.add(rel(b)) then a.add(rel(c)) MUST leave a → c and c → a, MUST remove a → b and b → a. If c already had a target x, the mirrored add replaces it (exclusive), so x MUST lose rel(c) (flecs Pairs_add_symmetric_exclusive_relation).
  • REL-007 [ecs][test]: Self pair. a.add(rel(a)) MUST leave exactly one pair a → a and MUST NOT recurse without end. a.remove(rel(a)) MUST remove it.
  • REL-008 [ecs][test]: Adding a pair that already exists, in either direction, MUST be a no-op (KL5): no extra pair, no throw, and no second hook call for the existing pair.
  • REL-009 [ecs][test]: User hooks (world.onAdd(rel, cb), world.onRemove(rel, cb)) MUST fire exactly once per direction: once for (a, b) and once for (b, a) for one add, and likewise for one real remove (the pair exists). The order between the two calls is not specified. When a.remove(rel(b)) is called while a has some rel pair but not rel(b), koota calls user onRemove hooks for (a, b) once (KL2) and the package MUST NOT add a call for (b, a) or any other call.
  • REL-010 [ecs][test]: Removal mirroring MUST terminate for every removal route: remove(rel(b)), remove(rel('*')), remove(RelTrait), exclusive replacement (REL-006), destroy of either side, and world.reset() (KL2). A re-entrancy guard keyed by the unordered pair is part of the install (state lives in the install closure, per world). The guard MUST be cleared when a removal finishes, also when it was ignored (REL-015).
  • REL-011 [ecs][test]: Pair data is not mirrored. If rel has a store, the mirrored pair MUST get the store defaults, and a later set on one side MUST NOT change the other (OQ4).
  • REL-012 [ecs][test]: The unsubscribe function MUST remove the hooks. After it, adds and removes MUST NOT be mirrored, and existing pairs MUST stay as they are. Calling it twice MUST be harmless, and calling it after world.reset() or world.destroy() MUST NOT throw (moved from REL-153).
  • REL-013 [ecs][test]: Calling symmetric(world, rel) twice for the same rel MUST give the same observable state as one call (adds and removes are mirrored once, no throw, no recursion).
  • REL-014 [ecs][test]: symmetric(world, rel) for one relation MUST NOT affect another relation, and symmetric on world1 MUST NOT affect world2, even with the same rel object.
  • REL-015 [ecs][test]: The remove hook MUST ignore a call for (source, target) when !source.has(rel(target)) (KL2). Example: a → c and c → a exist, a has no pair with b, and a.remove(rel(b)) is called. Nothing changes: a → c, c → a stay, no pair of b is removed, and the guard of REL-010 holds no stale key, so a later real a.add(rel(b)) followed by a.remove(rel(b)) is mirrored as in REL-002.
  • REL-016 [ecs][test]: symmetric MUST throw, naming symmetric, if world is not initialized (world.isInitialized is false, e.g. after world.destroy()), and MUST install no hook: the world is unchanged.

REL-F02 Transitive reachability (S)

  • REL-020 [ecs][test]: isReachable(world, a, rel, b) MUST be true if a reaches b under rel, else false. For a → b → c: isReachable(a, c) is true, isReachable(c, a) is false. The result is computed from the pairs in the world at call time. No registration (transitive) is needed (OQ2).
  • REL-021 [ecs][test]: A direct pair counts: a → b gives isReachable(a, b) true.
  • REL-022 [ecs][test]: Not reflexive. isReachable(a, a) MUST be false unless a reaches itself through a cycle (flecs Reflexive is out of scope).
  • REL-023 [ecs][test]: Diamonds and several targets. With a → b, a → c, b → d, c → d: isReachable(a, d) is true. Each entity is visited at most once, so the cost is linear in the reachable subgraph.
  • REL-024 [ecs][test]: Cycle safety. With a → b → a (and a → a), isReachable MUST terminate and return the correct answer: isReachable(a, a) is true, and isReachable(a, x) for unrelated x is false.
  • REL-025 [ecs][test]: The answer MUST follow later changes: after b.remove(rel(c)), isReachable(a, c) is false. There is no cache.
  • REL-026 [ecs][test]: Works for exclusive and non-exclusive relations, and for relations with a store.
  • REL-027 [ecs][test]: Entities destroyed along a path break it: after destroying b in a → b → c, isReachable(a, c) is false.
  • REL-028 [ecs][test]: isReachable MUST return false, and MUST NOT throw, when a or b is not alive in world, including an entity of another world (a dead entity reaches and is reached by nothing; moved from REL-156).

REL-F03 Materialized closure (M)

The closure is an extra relation C chosen by the caller (OQ2). C(y) on x means x reaches y under rel. It makes "all x that reach y" a normal koota query: world.query(C(y)).

  • REL-040 [ecs][test]: transitive(world, rel, { closure }) MUST return an unsubscribe function and install hooks on world for rel. It MUST throw, naming transitive, if closure === rel or if world is not initialized, and MUST install no hook in that case. closure MUST be non-exclusive and have no store (KL1: not checked, documented in REL-053).
  • REL-041 [ecs][test]: Pairs that exist when transitive is called MUST be reflected in the closure at install time.
  • REL-042 [ecs][test]: Add. After a → b, b → c, c → d in any order of adds: the closure has a → {b, c, d}, b → {c, d}, c → {d} and nothing else. Adding the middle link last (a → b, c → d, then b → c) MUST give the same closure.
  • REL-043 [ecs][test]: Remove. After removing b → c from the chain in REL-042, the closure has a → {b}, b → {}, c → {d}. Removing a pair MUST be correct although koota runs the hook before the pair is gone (KL2): the recomputation ignores the edge being removed.
  • REL-044 [ecs][test]: Alternative paths keep closure pairs. With a → b, a → c, b → d, c → d: removing b → d MUST keep a → d (still reachable through c) and drop b → d.
  • REL-045 [ecs][test]: Destroying an entity in the middle of a chain MUST remove every closure pair whose only path went through it, and MUST leave closure pairs that have another path. It MUST NOT throw (KL2, KL9).
  • REL-046 [ecs][test]: Invariant. After each operation in REL-042 to REL-045, for every pair of alive entities (x, y): x.has(closure(y)) is true if and only if isReachable(world, x, rel, y). A randomized test over adds, removes, and destroys SHOULD check this.
  • REL-047 [ecs][test]: Cycle. With a → b → a, the closure has a → {a, b} and b → {a, b} (a path of length ≥ 1 from an entity to itself exists). Breaking the cycle with b.remove(rel(a)) leaves a → {b}.
  • REL-048 [ecs][test]: world.query(closure(y)) MUST return exactly the entities that reach y. world.query(closure(y), Trait) composes with other terms as in koota.
  • REL-049 [ecs][test]: Unsubscribe MUST remove the hooks. Later changes MUST NOT update the closure, and existing closure pairs MUST stay (stale). Calling it twice MUST be harmless, and calling it after world.reset() or world.destroy() MUST NOT throw (moved from REL-153). Calling transitive twice with the same rel and closure MUST leave the closure correct (as REL-013).
  • REL-050 [ecs][test]: closure pairs written by the package MUST NOT be mirrored or re-processed by symmetric or transitive hooks of rel. Hooks MUST only react to rel, never to closure.
  • REL-051 [ecs][test]: rel MAY have a store. set on pair data of rel MUST NOT change the closure.
  • REL-052 [ecs][test]: world.reset() MUST NOT throw while hooks are installed. After it, hooks are gone (KL4): a new rel pair does not update the closure, and calling transitive again works on the new empty state.
  • REL-053 [ux][manual]: The README MUST have a section for transitive (written with this feature) that states that: closure must be a dedicated, non-exclusive, store-less relation that only the package writes; a transitive call costs work proportional to the affected sources and their reach per change; the closure is not maintained after unsubscribe or world.reset(). Verify by reading it.
  • REL-054 [ecs][test]: The remove hook MUST ignore a call for (source, target) when !source.has(rel(target)) (KL2). Example: a → c exists with the closure a → {c}, a has no pair with b, and a.remove(rel(b)) is called. The closure is unchanged, nothing is recomputed for b, and the call does not throw.

Area B: Traversal

REL-F04 up (S)

  • REL-060 [ecs][test]: up(world, entity, rel, trait) MUST return the first entity found along rel that has trait, or undefined. "First" is by the depth-first walk of REL-063, not the smallest distance from entity. Example: ship ← cockpit ← pilot as ChildOf, Mass on ship: up(world, pilot, ChildOf, Mass) returns ship (flecs Up with ChildOf).
  • REL-061 [ecs][test]: By default entity itself is not considered (flecs Up without Self). With { self: true }, entity MUST be checked first, then its targets (flecs Self | Up).
  • REL-062 [ecs][test]: If no entity on the walk has trait, up MUST return undefined. For an entity with no targets, that is the result (or entity itself with { self: true } if it has trait).
  • REL-063 [ecs][test]: The walk is depth-first. At every entity, the targets under rel are visited in ascending entity.id() order, not in entity.targetsFor(rel) order (KL6). The first target is followed to its root before the next target is tried, and the first entity with trait wins (flecs Relationship Traversal). The result MUST be the same for equal world state, whatever the order of earlier adds and removes. Example: x → p1 → g1 and x → p2, with Mass on g1 and on p2, and p1.id() < p2.id(): result is g1, although p2 is nearer (distance 1, g1 is at 2). If p2.id() < p1.id(), the result is p2. Adding x → p2 before x → p1, or removing x → p2 and adding it again (which changes koota's target order), does not change either result.
  • REL-064 [ecs][test]: Cycles. If the walk reaches an entity a second time it MUST NOT follow it again. up MUST terminate, and return a match if one is reachable, else undefined (KL3).
  • REL-065 [ecs][test]: The result MUST follow later changes (reparenting, adding or removing trait). There is no cache. up MUST NOT change the world.
  • REL-066 [ecs][test]: up works for exclusive and non-exclusive relations and for any plain trait (tag, SoA, AoS). The caller reads the value with up(...)?.get(trait).
  • REL-067 [ecs][test]: up MUST throw, naming up, if entity is not alive in world, including an entity of another world. The world is unchanged (moved from REL-156).

REL-F05 cascade (S)

  • REL-080 [ecs][test]: cascade(world, query, rel) MUST return an array of the entities that match query (a createQuery(...) result or a QueryParameter[]), ordered by their depth under rel, lowest depth first. It MUST return each matching entity exactly once.
  • REL-081 [ecs][test]: Depth is 0 for an entity with no rel targets, else 1 + max(depth(t)) over its targets. So every entity comes after all of its rel targets that are in the result. With ChildOf: roots first, then their children, then grandchildren (flecs Breadth-first traversal, cascade).
  • REL-082 [ecs][test]: Entities of the same depth MUST be ordered by ascending entity.id() (KL6). The result MUST be deterministic for equal world state.
  • REL-083 [ecs][test]: Entities that do not match query are not returned, but they MUST still count for depth. With root ← mid ← leaf where mid does not match, leaf has depth 2.
  • REL-084 [ecs][test]: The result is a snapshot. Changing the world while iterating the array MUST NOT change the array.
  • REL-085 [ecs][test]: Cycles. Back edges on the current path are ignored when computing depth, so cascade MUST terminate and MUST return each matching entity once, including entities that are part of a cycle (KL3).
  • REL-086 [ecs][test]: Depth of an entity with several targets is the longest path (REL-081), so a → b → c and a → c give a depth 2.
  • REL-087 [ecs][test]: cascade returns [] for a query with no matches and does not throw for a relation that no entity uses.
  • REL-088 [ecs][test]: cascade MUST NOT change the world, and each call MUST reflect the current rel pairs (no cache).
  • REL-089 [ecs][test]: Query semantics are koota's: entities with IsExcluded MUST NOT be returned (as world.query). Their pairs still count for the depth of other entities.

Area C: Hierarchies

REL-F06 ChildOf (S)

  • REL-100 [ecs][test]: ChildOf MUST be a koota relation created with exclusive: true and autoDestroy: 'orphan' (KL1, KL9). An entity has at most one parent, and a parent's destruction destroys its children.
  • REL-101 [ecs][test]: parent(world, child) MUST return the entity p for which child.has(ChildOf(p)), or undefined for a root. children(world, p) MUST return every entity c with c.has(ChildOf(p)).
  • REL-102 [ecs][test]: Reparenting. child.add(ChildOf(p2)) while child is a child of p1 MUST make p2 the parent, remove child from children(world, p1), and add it to children(world, p2). The entity MUST keep all other traits (flecs: ChildOf is exclusive).
  • REL-103 [ecs][test]: Destroying a parent MUST destroy all descendants, at any depth, in the same call (flecs Recursive cleanup, koota autoDestroy). The order of destruction is not specified (KL9). The parent's own other relations MUST be cleaned as in koota.
  • REL-104 [ecs][test]: Destroying a child MUST leave the parent and its other children alive, and children(world, parent) MUST no longer contain it.
  • REL-105 [ecs][test]: children(world, p) MUST be ordered by ascending entity.id() (KL6). It returns [] for a leaf and for an unused entity, and a fresh array each call (a snapshot).
  • REL-106 [ecs][test]: Order by id is deterministic and independent of the order in which ChildOf was added or removed in between (the swap-and-pop order of koota does not show).
  • REL-107 [ecs][test]: Canary for koota behaviour the package relies on: world.query(ChildOf('*')) returns exactly the non-root entities, and world.query(ChildOf(p)) returns exactly the children of p.
  • REL-108 [ecs][test]: Cycles are not prevented (KL3). With a.add(ChildOf(b)) and b.add(ChildOf(a)) or a.add(ChildOf(a)), parent and children MUST still return normally. Destroying a member of the cycle MUST NOT recurse without end (koota's processedEntities set). The behaviour of getPath, up, and cascade on cycles is specified and tested in their own groups (REL-124, REL-064, REL-085).
  • REL-109 [ecs][test]: parent and children MUST throw, naming the function, for an entity that is not alive in world, including an entity of another world. The world is unchanged (moved from REL-156).
  • REL-110 [ux][manual]: The README MUST state that ChildOf is plain koota (queries with ChildOf(parent) work as documented), that cycles are the caller's responsibility, and that child order is by entity id (use koota ordered() if user order matters; out of scope). Verify by reading it.

REL-F07 Name, paths, and lookup (M)

  • REL-120 [ecs][test]: Name MUST be a koota SoA trait with one string field, value, default ''. A named entity is an entity with Name and a non-empty value. Entities are named, renamed, and read with plain koota calls (add(Name({ value })), set(Name, { value }), get(Name)). No other API is needed to name an entity.
  • REL-121 [ecs][test]: getPath(world, entity) MUST return the names from the root to entity joined by /. A named root Spaceship gives Spaceship. Its child Cockpit gives Spaceship/Cockpit (flecs Hierarchies_rel_path_from_root; separator: OQ5).
  • REL-122 [ecs][test]: An entity that is unnamed (no Name or an empty value) MUST appear in a path as #<entity.id()>. Such segments are not resolved by lookup (REL-129).
  • REL-123 [ecs][test]: getPath(world, entity, { from }) MUST return the path of entity relative to the ancestor from, without the segment of from (flecs Hierarchies_rel_path_from_self: path from self is ''). It MUST throw, naming getPath, if from is not entity or an ancestor of it.
  • REL-124 [ecs][test]: getPath MUST throw, naming getPath, if the parent chain of entity contains a cycle (REL-108).
  • REL-125 [ecs][test]: getPath MUST throw, naming getPath, if a name on the chain contains /, because the path would be ambiguous (OQ5).
  • REL-126 [ecs][test]: lookup(world, path) MUST resolve path segment by segment. The first segment is matched against the roots, and each next segment against the children of the previous match. It MUST return the entity, or undefined if any segment has no match. Matching is exact and case-sensitive. A root is an entity with a non-empty Name and no ChildOf target (KL7).
  • REL-127 [ecs][test]: lookup(world, path, { from }) MUST resolve path relative to the children of from (flecs ecs_lookup_from, "Parent::Child" relative to Parent). from MUST be alive, else lookup throws naming lookup.
  • REL-128 [ecs][test]: Sibling names are not unique (KL3, OQ6). If several siblings (or roots) share a name, lookup MUST return the one with the lowest entity.id().
  • REL-129 [ecs][test]: Unnamed entities MUST NOT match any segment, including a segment like #12 (no lookup by id in v0). An empty path, or a path with an empty segment (a//b, /a, a/) MUST return undefined.
  • REL-130 [ecs][test]: Renaming (entity.set(Name, { value })) MUST take effect immediately for lookup and getPath. There is no cache or index (KL7).
  • REL-131 [ecs][test]: Reparenting changes the path. After child.add(ChildOf(other)), getPath(child) starts with other's path, and lookup with the old path returns undefined.
  • REL-132 [ecs][test]: Round trip. For every entity whose chain has only named entities with names that are unique among their siblings: lookup(world, getPath(world, e)) === e.
  • REL-133 [ecs][test]: A named entity with a parent MUST NOT be found by a root-level segment. A named root MUST NOT be found as a child of any entity.
  • REL-134 [ecs][test]: getPath and lookup MUST throw, naming the function, for an entity argument (entity or from) that is not alive in world, including an entity of another world. The world is unchanged (moved from REL-156). Destroyed entities are never returned by lookup.
  • REL-135 [ux][manual]: The README MUST state that lookup scans names with no index (cost is linear in the number of siblings per segment and in the number of named entities for the first segment), that names are not unique unless the caller makes them so, that / cannot appear in names used with paths, and that #id segments are for display only. Verify by reading it.

REL-F08 Package rules (S)

Depends on F01 to F07 and is the last feature item: its tests use the install functions of F01 and F03 and the exports of all groups, and its README text links the sections written by REL-053, REL-110, and REL-135. Retired IDs: REL-153 moved into REL-012 and REL-049, REL-154 moved into the per-function requirements that throw (REL-016, REL-040, REL-067, REL-109, REL-123 to REL-127, REL-134), REL-156 moved into REL-028, REL-067, REL-109, and REL-134.

  • REL-150 [ecs][test]: There MUST be no module-level mutable state. Hooks, guards, and recompute state live in the closure of one symmetric or transitive call, which is one world. Installing symmetric and transitive in world1 MUST NOT change behaviour in world2, even with the same rel and closure objects (a relation definition is shared and holds no per-world state). It extends REL-014 to transitive and to both installs together.
  • REL-151 [ecs][test]: Importing the package MUST have no side effects: it creates no world, no entity, no hook. ChildOf and Name are definitions (constants) only.
  • REL-152 [ecs][test]: Canary for KL4: after world.reset(), hooks installed by symmetric and transitive are gone (a new pair is not mirrored). Calling the install functions again MUST work. The test documents koota's behaviour and fails if koota changes it, so the README can be updated.
  • REL-155 [ux][manual]: The README MUST have a "Preconditions" section that lists what the package cannot check (KL1) and links the sections written by REL-053 (transitive), REL-110 (ChildOf), and REL-135 (names): rel for symmetric does not mirror pair data (REL-011); closure for transitive is dedicated, non-exclusive, store-less; hooks are per world and lost on world.reset() (REL-152); koota onRemove hooks run before the removal and can fire for a pair the entity does not have (KL2), which user code that mixes its own hooks with these must expect. Verify by reading it.

API sketch

import type { Entity, Query, QueryParameter, Relation, TagTrait, Trait, World } from 'koota';

export type Unsubscribe = () => void;

// Area A: relation traits. Installed per world through hooks (KL1, KL2, KL4).
// Mirrors every pair of `rel` now and after. Throws (message names `symmetric`) if `world` is not initialized. (REL-001, REL-016)
export function symmetric(world: World, rel: Relation<Trait>): Unsubscribe;

export interface TransitiveOptions {
  // Dedicated, non-exclusive, store-less relation written only by the package. (REL-040)
  closure: Relation<Trait>;
}
// Keeps `closure(y)` on every x that reaches y under `rel`. Throws (names `transitive`) if closure === rel. (REL-040)
export function transitive(world: World, rel: Relation<Trait>, options: TransitiveOptions): Unsubscribe;

// Pure traversal, needs no registration. (REL-020)
export function isReachable(world: World, from: Entity, rel: Relation<Trait>, to: Entity): boolean;

// Area B: traversal.
export interface UpOptions {
  self?: boolean; // check `entity` first (default false) (REL-061)
}
export function up(
  world: World,
  entity: Entity,
  rel: Relation<Trait>,
  trait: Trait,
  options?: UpOptions,
): Entity | undefined;

// Entities matching `query`, ordered by depth under `rel`, then by entity id. (REL-080..REL-082)
export function cascade(world: World, query: Query<QueryParameter[]> | QueryParameter[], rel: Relation<Trait>): Entity[];

// Area C: hierarchies.
export const ChildOf: Relation<TagTrait>; // relation({ exclusive: true, autoDestroy: 'orphan' }) (REL-100)
export const Name: Trait<{ value: string }>; // trait({ value: '' }) (REL-120)

export function parent(world: World, entity: Entity): Entity | undefined;
export function children(world: World, parent: Entity): Entity[]; // ascending entity.id() (REL-105)

export interface PathOptions {
  from?: Entity; // an ancestor of `entity` (REL-123)
}
export function getPath(world: World, entity: Entity, options?: PathOptions): string;

export interface LookupOptions {
  from?: Entity; // resolve relative to the children of `from` (REL-127)
}
export function lookup(world: World, path: string, options?: LookupOptions): Entity | undefined;

Usage for the demo (docs only):

const MarriedTo = relation();
const VassalOf = relation({ exclusive: true });
const Reaches = relation(); // closure of VassalOf

symmetric(world, MarriedTo);
transitive(world, VassalOf, { closure: Reaches });

const emperor = world.spawn(Name({ value: 'Emperor' }));
const duke = world.spawn(VassalOf(emperor));
const count = world.spawn(VassalOf(duke));

isReachable(world, count, VassalOf, emperor); // true
world.query(Reaches(emperor)); // [duke, count]
up(world, count, VassalOf, Title); // first liege up the chain that has `Title` (`VassalOf` is exclusive, so this is the nearest)

Notes for implementation:

  • Shared helpers: one walk over entity.targetsFor(rel) sorted by entity.id() with a visited set (for up, isReachable, depth); sources* through world.query(rel(x)).
  • Mirroring: guard set of unordered pair keys in the symmetric closure. Skip the mirror if the other side is dead (world.has) (KL2, REL-004).
  • Closure: on every rel add or remove, recompute the closure for the affected sources, which are the source of the changed pair and its sources*. On remove, the traversal skips the edge in the callback (REL-043). Add and remove closure pairs by diffing against the current closure targets. Install runs the same recompute for every source found through world.query(rel('*')).
  • cascade: compute depth for every matching entity with memoization and the longest-path rule (REL-081, REL-086), then sort by [depth, entity.id()].
  • Roots for lookup: world.query(Name), filtered by entity.targetFor(ChildOf) === undefined and a non-empty name (KL7). Children by children(world, parent).

Differences from flecs

  • Per-world hooks instead of relation properties. flecs adds Symmetric / Transitive to the relation entity once for the world. koota relations are opaque (KL1), so the traits are installed per world with a call that returns an unsubscribe, and they are lost on world.reset() (KL4). The concept sketch (symmetric(rel), up(entity, rel, trait)) is extended with a leading world argument (KL8, OQ1).
  • Transitivity is not applied in queries. flecs makes (R, X) queries follow R. Here world.query(R(x)) stays one-hop. Reachability is isReachable, and a queryable materialized closure is opt-in (REL-040). Cost: closure maintenance work per change, which flecs avoids by traversing at query time.
  • Not reflexive, and no Acyclic / Traversable checks. koota cannot veto an add (KL3), so every helper guards against cycles instead of asserting. flecs refuses to traverse a relation that is not Traversable.
  • up and cascade are functions, not query terms. up returns the entity that holds the trait (flecs resolves it into the query's term source). cascade is an eager function that returns an array. It has no desc, no caching, and no group iterator. It orders by depth like flecs Cascade, and by entity id inside one depth (OQ3). up walks depth-first like flecs, but visits the targets of an entity in entity-id order, where flecs uses table order (REL-063).
  • ChildOf is plain koota. exclusive and autoDestroy: 'orphan' replace flecs's builtin cleanup. Children are destroyed, but in no specified order (flecs deletes children before parents) (KL9). flecs has Parent storage, OrderedChildren, and scoping (set_scope). None of those are ported.
  • Names are a trait. flecs entities carry a name in a builtin component and enforce unique names among siblings. Here Name is an ordinary trait, uniqueness is not enforced (KL3), and lookup is a scan (KL7). Path separator is / (flecs: . in C, :: in C++). Unnamed entities print as #<id> in paths but cannot be looked up by it (flecs resolves #id).
  • Symmetric pair data. flecs pairs carry no data in a symmetric relation. Here a relation with a store is allowed, its mirrored pair gets defaults, and the data is not kept in sync (REL-011).

Out of scope

  • Reflexive, Acyclic, Traversable, Final, Exclusive as package traits, and any query-level transitivity or traversal term ($this, $x, self|up in the query DSL).
  • cascade with desc (bottom-up), cached or grouped cascade queries, breadth-first / depth-first iterators other than the ordering in REL-081.
  • Cycle prevention and checked mutators (setParent that throws on a cycle), unique-name enforcement, and a name index.
  • OrderedChildren / koota ordered(), Parent storage, scoping, name lookup by #id, .. and relative path segments, case-insensitive lookup, and escaping of the separator.
  • Mirroring or merging pair data for symmetric. Per-relation configuration of what the mirror carries.
  • A reachable(world, a, rel) list function (the closure answers it), and incremental reachability for large graphs.
  • Re-installing hooks after world.reset() automatically (KL4).
  • React hooks over these helpers, serialization of Name and closures (ecs-serialize), prefab child copying (ecs-prefab), and devtools display of paths.
  • A demo-ck3 scenario group (as PREFAB-F06): add it when docs/products/demo-ck3.md and docs/specs/demo-ck3.md exist.
  • Upstream proposals: relation properties (symmetric, transitive, traversable) and a Not(pair) in koota, an onRemove hook that runs after the removal, hooks that survive world.reset(), and a public world accessor on an entity.

Open questions

Each has a recommended default. The requirements above already use the defaults. If the user decides otherwise, the named requirements change.

  1. API shape: world first. Default: symmetric(world, rel), transitive(world, rel, { closure }), isReachable(world, a, rel, b), up(world, entity, rel, trait), cascade(world, query, rel), because hooks are per world (KL4), entities have no world accessor (KL8), and the world lets every function reject dead entities (REL-028, REL-067, REL-109, REL-134). The concept sketch (symmetric(rel), up(entity, rel, trait)) would need a module-level registry or $internal, both against the package rules. Affects: all signatures.
  2. Who owns the closure relation, and is transitive needed for isReachable? Default: the caller passes closure (a dedicated relation), and isReachable is a pure traversal that needs no registration. Alternative: the package creates the closure relation per call and returns it (needs a package-held handle per rel, which is module state or a world trait), or isReachable throws unless transitive was installed (needs a per-world registry that goes stale after world.reset()). Affects: REL-020, REL-040, REL-053.
  3. cascade order. Default: depth-ordered like flecs Cascade (all of depth 0, then depth 1, and so on; ties by id). W-008 and concept §6 say "depth-first, depth-ordered", which can mean either breadth by level (flecs) or parent-before-child pre-order (each subtree before its next sibling). If the demo needs pre-order (subtree contiguous), REL-080 to REL-082 change, and the ordering key changes to the path of ids. Decide before implementing F05.
  4. Pair data of symmetric relations. Default: not mirrored, mirror gets defaults (REL-011). Alternative: copy data on add and sync on set (needs onChange hooks, which turn on change tracking for the relation), or reject relations with a store (not detectable, KL1).
  5. Path format. Default: / separator, no leading separator, a name containing / makes getPath throw (REL-125). Alternatives: . (as flecs C), ::, a configurable separator, or escaping. Affects: REL-121, REL-125, REL-129.
  6. Unique sibling names. Default: not enforced, lowest id wins (REL-128). Alternative: a checked spawnChild or setName helper that throws on a duplicate sibling name. koota cannot reject a plain entity.add(Name(...)) anyway (KL3).
  7. Cycles in ChildOf. Default: tolerated and not prevented, helpers terminate or throw (REL-108, REL-124). Alternative: a checked setParent(world, child, parent) that throws on a cycle.
  8. Closure on cycles includes self pairs (REL-047): a → a appears when a is on a cycle. Alternative: never write a self closure pair. Then the invariant in REL-046 would need x !== y.
  9. No demo-ck3 brief yet. The requirements follow the concept §8 mapping. Which of the three areas does the first ck3 backlog feature need first? Default order of work items: F01, F02, F03 (traits), F04, F05 (traversal), F06, F07 (hierarchy), then F08 last. F03 needs F02 and F07 needs F06. F08 depends on F01 to F07 and is the last item (REL-150 to REL-152 and REL-155 test or document all groups).