1use std::collections::{HashMap, HashSet};
2use std::error::Error;
3use std::fmt::{Display, Formatter};
4
5use bevy_ecs::change_detection::{DetectChanges, Tick};
6use bevy_ecs::entity::Entity;
7use bevy_ecs::prelude::{Or, Ref, Resource, With, World};
8use nalgebra::Matrix4;
9
10use crate::components::{Children, GlobalTransform, Parent};
11use crate::transform::Transform;
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub enum HierarchyError {
16 MissingEntity(Entity),
17 Cycle { child: Entity, parent: Entity },
18}
19
20impl Display for HierarchyError {
21 fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
22 match self {
23 Self::MissingEntity(entity) => write!(formatter, "entity {entity:?} does not exist"),
24 Self::Cycle { child, parent } => write!(
25 formatter,
26 "parenting {child:?} beneath {parent:?} would create a hierarchy cycle"
27 ),
28 }
29 }
30}
31
32impl Error for HierarchyError {}
33
34#[derive(Resource, Clone, Debug, Default)]
35pub struct HierarchyDiagnostics {
36 pub cycles: Vec<Entity>,
37 pub missing_parents: Vec<Entity>,
38}
39
40#[doc(hidden)]
44#[derive(Resource, Clone)]
45pub struct PropagationFingerprint {
46 last_run: Tick,
47 counts: [usize; 3],
48}
49
50pub fn set_parent(
52 world: &mut World,
53 child: Entity,
54 parent: Entity,
55) -> Result<(), HierarchyError> {
56 if world.get_entity(child).is_err() {
57 return Err(HierarchyError::MissingEntity(child));
58 }
59 if world.get_entity(parent).is_err() {
60 return Err(HierarchyError::MissingEntity(parent));
61 }
62
63 let mut ancestor = Some(parent);
64 let mut visited = HashSet::new();
65 while let Some(entity) = ancestor {
66 if entity == child || !visited.insert(entity) {
67 return Err(HierarchyError::Cycle { child, parent });
68 }
69 ancestor = world.get::<Parent>(entity).map(|parent| parent.0);
70 }
71
72 clear_parent(world, child)?;
73 world.entity_mut(child).insert(Parent(parent));
74 let mut parent_entity = world.entity_mut(parent);
75 if let Some(mut children) = parent_entity.get_mut::<Children>() {
76 if !children.0.contains(&child) {
77 children.0.push(child);
78 }
79 } else {
80 parent_entity.insert(Children(vec![child]));
81 }
82 Ok(())
83}
84
85pub fn clear_parent(
87 world: &mut World,
88 child: Entity,
89) -> Result<(), HierarchyError> {
90 if world.get_entity(child).is_err() {
91 return Err(HierarchyError::MissingEntity(child));
92 }
93 let old_parent = world.get::<Parent>(child).map(|parent| parent.0);
94 world.entity_mut(child).remove::<Parent>();
95 if let Some(parent) = old_parent {
96 if let Ok(mut parent_entity) = world.get_entity_mut(parent) {
97 if let Some(mut children) = parent_entity.get_mut::<Children>() {
98 children.0.retain(|entity| *entity != child);
99 }
100 }
101 }
102 Ok(())
103}
104
105pub fn propagate_transforms(world: &mut World) {
126 let this_run = world.increment_change_tick();
127 let mut counts = [0; 3];
128 let mut moved = Vec::new();
129 let mut reparented = false;
130 let last_run = world
131 .get_resource::<PropagationFingerprint>()
132 .map(|fingerprint| fingerprint.last_run);
133 let mut query = world.query_filtered::<(
134 Entity,
135 Option<Ref<Transform>>,
136 Option<Ref<Parent>>,
137 Option<&Children>,
138 ), Or<(With<Transform>, With<Parent>, With<Children>)>>(
139 );
140 for (entity, transform, parent, children) in query.iter(world) {
141 counts[0] += usize::from(transform.is_some());
142 counts[1] += usize::from(parent.is_some());
143 counts[2] += usize::from(children.is_some());
144 if let Some(last_run) = last_run {
145 if transform.is_some_and(|value| {
146 value.last_changed().is_newer_than(last_run, this_run)
147 }) {
148 moved.push(entity);
149 }
150 reparented |= parent.is_some_and(|value| {
151 value.last_changed().is_newer_than(last_run, this_run)
152 });
153 }
154 }
155 let same_shape = last_run.is_some()
156 && world
157 .get_resource::<PropagationFingerprint>()
158 .is_some_and(|fingerprint| fingerprint.counts == counts)
159 && !reparented;
160 let clean_hierarchy = world
161 .get_resource::<HierarchyDiagnostics>()
162 .is_some_and(|diagnostics| {
163 diagnostics.cycles.is_empty()
164 && diagnostics.missing_parents.is_empty()
165 });
166 world.insert_resource(PropagationFingerprint {
167 last_run: this_run,
168 counts,
169 });
170 if same_shape && world.contains_resource::<HierarchyDiagnostics>() {
171 if moved.is_empty() {
172 return;
173 }
174 if clean_hierarchy {
175 update_moved(world, &moved);
176 return;
177 }
178 }
179
180 if !world.contains_resource::<HierarchyDiagnostics>() {
181 world.insert_resource(HierarchyDiagnostics::default());
182 }
183 {
184 let mut diagnostics = world.resource_mut::<HierarchyDiagnostics>();
185 diagnostics.cycles.clear();
186 diagnostics.missing_parents.clear();
187 }
188
189 let mut existing = HashSet::new();
190 let mut locals = HashMap::new();
191 let mut parents = HashMap::new();
192 let mut query =
193 world.query::<(Entity, Option<&Transform>, Option<&Parent>)>();
194 for (entity, transform, parent) in query.iter(world) {
195 existing.insert(entity);
196 if let Some(transform) = transform {
197 locals.insert(entity, matrix_from_array(transform.to_matrix()));
198 }
199 if let Some(parent) = parent {
200 parents.insert(entity, parent.0);
201 }
202 }
203
204 let mut resolved = HashMap::new();
205 let mut visiting = HashSet::new();
206 let mut cycles = Vec::new();
207 let mut missing_parents = Vec::new();
208 let mut worklist = existing.iter().copied().collect::<Vec<_>>();
209 worklist.sort_unstable();
210 for entity in worklist.iter().copied() {
211 resolve_global(
212 entity,
213 &existing,
214 &locals,
215 &parents,
216 &mut resolved,
217 &mut visiting,
218 &mut cycles,
219 &mut missing_parents,
220 );
221 }
222
223 let mut transformed = locals.keys().copied().collect::<Vec<_>>();
224 transformed.sort_unstable();
225 for entity in transformed {
226 let matrix = resolved[&entity];
227 let global = GlobalTransform {
228 matrix: matrix.into(),
229 };
230 if world.get::<GlobalTransform>(entity) != Some(&global) {
231 world.entity_mut(entity).insert(global);
232 }
233 }
234 cycles.sort_unstable();
235 missing_parents.sort_unstable();
236 let mut diagnostics = world.resource_mut::<HierarchyDiagnostics>();
237 diagnostics.cycles = cycles;
238 diagnostics.missing_parents = missing_parents;
239}
240
241fn update_moved(world: &mut World, moved: &[Entity]) {
244 let moved: HashSet<Entity> = moved.iter().copied().collect();
245 let mut affected = Vec::new();
246 let mut query = world.query_filtered::<Entity, With<Transform>>();
247 for entity in query.iter(world) {
248 let mut depth = 0_usize;
249 let mut hit = moved.contains(&entity);
250 let mut current = entity;
251 while let Some(parent) = world.get::<Parent>(current) {
253 current = parent.0;
254 depth += 1;
255 hit |= moved.contains(¤t);
256 }
257 if hit {
258 affected.push((depth, entity));
259 }
260 }
261 affected.sort_unstable();
262 for (_, entity) in affected {
263 let local = matrix_from_array(
264 world.get::<Transform>(entity).unwrap().to_matrix(),
265 );
266 let global = match world.get::<Parent>(entity) {
267 Some(parent) => world_of(world, parent.0) * local,
268 None => local,
269 };
270 let global = GlobalTransform {
271 matrix: global.into(),
272 };
273 if world.get::<GlobalTransform>(entity) != Some(&global) {
274 world.entity_mut(entity).insert(global);
275 }
276 }
277}
278
279fn world_of(world: &World, entity: Entity) -> Matrix4<f32> {
282 if world.get::<Transform>(entity).is_some() {
283 return world
284 .get::<GlobalTransform>(entity)
285 .map_or_else(Matrix4::identity, |global| {
286 matrix_from_array(global.matrix)
287 });
288 }
289 match world.get::<Parent>(entity) {
290 Some(parent) => world_of(world, parent.0) * Matrix4::identity(),
291 None => Matrix4::identity(),
292 }
293}
294
295#[allow(clippy::too_many_arguments)]
296fn resolve_global(
297 entity: Entity,
298 existing: &HashSet<Entity>,
299 locals: &HashMap<Entity, Matrix4<f32>>,
300 parents: &HashMap<Entity, Entity>,
301 resolved: &mut HashMap<Entity, Matrix4<f32>>,
302 visiting: &mut HashSet<Entity>,
303 cycles: &mut Vec<Entity>,
304 missing_parents: &mut Vec<Entity>,
305) -> Matrix4<f32> {
306 if let Some(matrix) = resolved.get(&entity) {
307 return *matrix;
308 }
309 let local = locals
310 .get(&entity)
311 .copied()
312 .unwrap_or_else(Matrix4::identity);
313 if !visiting.insert(entity) {
314 cycles.push(entity);
315 return local;
316 }
317
318 let global = if let Some(parent) = parents.get(&entity).copied() {
319 if existing.contains(&parent) {
320 resolve_global(
321 parent,
322 existing,
323 locals,
324 parents,
325 resolved,
326 visiting,
327 cycles,
328 missing_parents,
329 ) * local
330 } else {
331 missing_parents.push(entity);
332 local
333 }
334 } else {
335 local
336 };
337 visiting.remove(&entity);
338 resolved.insert(entity, global);
339 global
340}
341
342fn matrix_from_array(matrix: [[f32; 4]; 4]) -> Matrix4<f32> {
343 Matrix4::from_column_slice(&[
344 matrix[0][0],
345 matrix[0][1],
346 matrix[0][2],
347 matrix[0][3],
348 matrix[1][0],
349 matrix[1][1],
350 matrix[1][2],
351 matrix[1][3],
352 matrix[2][0],
353 matrix[2][1],
354 matrix[2][2],
355 matrix[2][3],
356 matrix[3][0],
357 matrix[3][1],
358 matrix[3][2],
359 matrix[3][3],
360 ])
361}
362
363#[cfg(test)]
364mod tests {
365 use super::*;
366
367 fn world_with_diagnostics() -> World {
368 let mut world = World::new();
369 world.insert_resource(HierarchyDiagnostics::default());
370 world
371 }
372
373 #[test]
374 fn moving_part_of_a_hierarchy_matches_a_full_rebuild_bit_for_bit() {
375 let mut world = world_with_diagnostics();
376 let mut entities = Vec::new();
377 let at = |i: usize| [i as f32 * 0.37, (i % 5) as f32, -(i as f32)];
378 for i in 0..60 {
379 let entity = if i % 7 == 3 {
380 world.spawn_empty().id()
382 } else {
383 let mut transform = Transform::new(at(i));
384 transform.rotation = [0.1 * i as f32, 0.3, -0.2];
385 transform.scale = [1.0 + 0.01 * i as f32; 3];
386 world.spawn(transform).id()
387 };
388 if i % 4 != 0 {
389 set_parent(&mut world, entity, entities[i * 2 / 3]).unwrap();
390 }
391 entities.push(entity);
392 }
393 propagate_transforms(&mut world);
394 let globals = |world: &mut World| {
395 entities
396 .iter()
397 .map(|entity| world.get::<GlobalTransform>(*entity).copied())
398 .collect::<Vec<_>>()
399 };
400 for tick in 0..4 {
401 for (n, &entity) in entities.iter().enumerate() {
402 if n % (3 + tick) == 1 {
403 if let Some(mut transform) =
404 world.get_mut::<Transform>(entity)
405 {
406 transform.position[1] += 0.25 * tick as f32 + 0.1;
407 transform.rotation[1] -= 0.05;
408 }
409 }
410 }
411 propagate_transforms(&mut world);
412 let incremental = globals(&mut world);
413 world.remove_resource::<PropagationFingerprint>();
415 propagate_transforms(&mut world);
416 assert_eq!(incremental, globals(&mut world), "tick {tick}");
417 let bits = |list: Vec<Option<GlobalTransform>>| {
418 list.iter()
419 .flatten()
420 .flat_map(|global| global.matrix.concat())
421 .map(f32::to_bits)
422 .collect::<Vec<_>>()
423 };
424 assert_eq!(bits(incremental), bits(globals(&mut world)));
425 }
426 }
427
428 #[test]
429 fn propagation_composes_parent_and_child_transforms() {
430 let mut world = world_with_diagnostics();
431 let parent = world.spawn(Transform::new([2.0, 3.0, 4.0])).id();
432 let child = world.spawn(Transform::new([5.0, 7.0, 11.0])).id();
433 set_parent(&mut world, child, parent).unwrap();
434 propagate_transforms(&mut world);
435 assert_eq!(
436 world.get::<GlobalTransform>(child).unwrap().matrix[3],
437 [7.0, 10.0, 15.0, 1.0]
438 );
439 }
440
441 #[test]
442 fn propagation_initializes_diagnostics_in_a_fresh_world() {
443 let mut world = World::new();
444 let entity = world.spawn(Transform::new([1.0, 2.0, 3.0])).id();
445
446 propagate_transforms(&mut world);
447
448 assert!(world.contains_resource::<HierarchyDiagnostics>());
449 let diagnostics = world.resource::<HierarchyDiagnostics>();
450 assert!(diagnostics.cycles.is_empty());
451 assert!(diagnostics.missing_parents.is_empty());
452 assert_eq!(
453 world.get::<GlobalTransform>(entity).unwrap().matrix[3],
454 [1.0, 2.0, 3.0, 1.0]
455 );
456 }
457
458 #[test]
459 fn propagation_uses_transformless_intermediate_entities_as_identity() {
460 let mut world = World::new();
461 let grandparent = world.spawn(Transform::new([2.0, 3.0, 4.0])).id();
462 let middle = world.spawn(Parent(grandparent)).id();
463 let child = world
464 .spawn((Transform::new([5.0, 7.0, 11.0]), Parent(middle)))
465 .id();
466
467 propagate_transforms(&mut world);
468
469 assert_eq!(
470 world.get::<GlobalTransform>(child).unwrap().matrix[3],
471 [7.0, 10.0, 15.0, 1.0]
472 );
473 assert!(world.get::<GlobalTransform>(middle).is_none());
474 assert!(world
475 .resource::<HierarchyDiagnostics>()
476 .missing_parents
477 .is_empty());
478 }
479
480 #[test]
481 fn clearing_the_final_parent_resets_an_unchanged_child_global() {
482 let mut world = World::new();
483 let parent = world.spawn(Transform::new([2.0, 3.0, 4.0])).id();
484 let child = world.spawn(Transform::new([5.0, 7.0, 11.0])).id();
485 set_parent(&mut world, child, parent).unwrap();
486 propagate_transforms(&mut world);
487 assert_eq!(
488 world.get::<GlobalTransform>(child).unwrap().matrix[3],
489 [7.0, 10.0, 15.0, 1.0]
490 );
491
492 clear_parent(&mut world, child).unwrap();
493 propagate_transforms(&mut world);
494
495 assert_eq!(
496 world.get::<GlobalTransform>(child).unwrap().matrix[3],
497 [5.0, 7.0, 11.0, 1.0]
498 );
499 }
500
501 #[test]
502 fn reparenting_and_clearing_maintain_both_sides() {
503 let mut world = World::new();
504 let first = world.spawn_empty().id();
505 let second = world.spawn_empty().id();
506 let child = world.spawn_empty().id();
507 set_parent(&mut world, child, first).unwrap();
508 set_parent(&mut world, child, second).unwrap();
509 assert_eq!(world.get::<Parent>(child), Some(&Parent(second)));
510 assert!(world.get::<Children>(first).unwrap().0.is_empty());
511 assert_eq!(world.get::<Children>(second).unwrap().0, vec![child]);
512 clear_parent(&mut world, child).unwrap();
513 assert!(world.get::<Parent>(child).is_none());
514 assert!(world.get::<Children>(second).unwrap().0.is_empty());
515 }
516
517 #[test]
518 fn cycle_rejection_does_not_mutate_existing_hierarchy() {
519 let mut world = World::new();
520 let root = world.spawn_empty().id();
521 let child = world.spawn_empty().id();
522 set_parent(&mut world, child, root).unwrap();
523 assert_eq!(
524 set_parent(&mut world, root, child),
525 Err(HierarchyError::Cycle {
526 child: root,
527 parent: child
528 })
529 );
530 assert!(world.get::<Parent>(root).is_none());
531 assert_eq!(world.get::<Parent>(child), Some(&Parent(root)));
532 assert_eq!(world.get::<Children>(root).unwrap().0, vec![child]);
533 }
534
535 #[test]
536 fn deep_self_and_preexisting_cycles_are_rejected() {
537 let mut world = world_with_diagnostics();
538 let root = world.spawn(Transform::new([1.0, 0.0, 0.0])).id();
539 let middle = world.spawn(Transform::new([0.0, 2.0, 0.0])).id();
540 let leaf = world.spawn(Transform::new([0.0, 0.0, 3.0])).id();
541 set_parent(&mut world, middle, root).unwrap();
542 set_parent(&mut world, leaf, middle).unwrap();
543 for (child, parent) in [(root, leaf), (root, middle), (leaf, leaf)] {
544 assert_eq!(
545 set_parent(&mut world, child, parent),
546 Err(HierarchyError::Cycle { child, parent })
547 );
548 }
549 propagate_transforms(&mut world);
550 assert_eq!(
551 world.get::<GlobalTransform>(leaf).unwrap().matrix[3],
552 [1.0, 2.0, 3.0, 1.0]
553 );
554
555 let first = world.spawn_empty().id();
557 let second = world.spawn_empty().id();
558 world.entity_mut(first).insert(Parent(second));
559 world.entity_mut(second).insert(Parent(first));
560 let outsider = world.spawn_empty().id();
561 assert_eq!(
562 set_parent(&mut world, outsider, first),
563 Err(HierarchyError::Cycle {
564 child: outsider,
565 parent: first
566 })
567 );
568 assert!(world.get::<Parent>(outsider).is_none());
569 }
570
571 #[test]
572 fn missing_child_and_parent_are_reported() {
573 let mut world = World::new();
574 let child = world.spawn_empty().id();
575 let parent = world.spawn_empty().id();
576 world.despawn(child);
577 assert_eq!(
578 set_parent(&mut world, child, parent),
579 Err(HierarchyError::MissingEntity(child))
580 );
581 let child = world.spawn_empty().id();
582 world.despawn(parent);
583 assert_eq!(
584 set_parent(&mut world, child, parent),
585 Err(HierarchyError::MissingEntity(parent))
586 );
587 assert_eq!(
588 clear_parent(&mut world, parent),
589 Err(HierarchyError::MissingEntity(parent))
590 );
591 }
592
593 #[test]
594 fn propagation_diagnoses_a_missing_parent() {
595 let mut world = world_with_diagnostics();
596 let missing = world.spawn_empty().id();
597 world.despawn(missing);
598 let child = world
599 .spawn((Transform::new([1.0, 2.0, 3.0]), Parent(missing)))
600 .id();
601 propagate_transforms(&mut world);
602 let diagnostics = world.resource::<HierarchyDiagnostics>();
603 assert_eq!(diagnostics.missing_parents, vec![child]);
604 assert!(diagnostics.cycles.is_empty());
605 assert_eq!(
606 world.get::<GlobalTransform>(child).unwrap().matrix[3],
607 [1.0, 2.0, 3.0, 1.0]
608 );
609 }
610
611 #[test]
612 fn propagation_diagnoses_a_transformless_dangling_parent() {
613 let mut world = World::new();
614 let missing = world.spawn_empty().id();
615 world.despawn(missing);
616 let child = world.spawn(Parent(missing)).id();
617
618 propagate_transforms(&mut world);
619
620 let diagnostics = world.resource::<HierarchyDiagnostics>();
621 assert_eq!(diagnostics.missing_parents, vec![child]);
622 assert!(diagnostics.cycles.is_empty());
623 assert!(world.get::<GlobalTransform>(child).is_none());
624 }
625
626 #[test]
627 fn propagation_diagnoses_a_malformed_cycle() {
628 let mut world = world_with_diagnostics();
629 let first = world.spawn(Transform::default()).id();
630 let second = world.spawn(Transform::default()).id();
631 world.entity_mut(first).insert(Parent(second));
632 world.entity_mut(second).insert(Parent(first));
633 propagate_transforms(&mut world);
634 let diagnostics = world.resource::<HierarchyDiagnostics>();
635 assert_eq!(diagnostics.cycles, vec![std::cmp::min(first, second)]);
636 assert!(diagnostics.missing_parents.is_empty());
637 }
638
639 #[test]
640 fn propagation_diagnoses_a_transformless_cycle_deterministically() {
641 let mut world = World::new();
642 let first = world.spawn_empty().id();
643 let second = world.spawn_empty().id();
644 world.entity_mut(first).insert(Parent(second));
645 world.entity_mut(second).insert(Parent(first));
646
647 propagate_transforms(&mut world);
648
649 let diagnostics = world.resource::<HierarchyDiagnostics>();
650 assert_eq!(diagnostics.cycles, vec![std::cmp::min(first, second)]);
651 assert!(diagnostics.missing_parents.is_empty());
652 assert!(world.get::<GlobalTransform>(first).is_none());
653 assert!(world.get::<GlobalTransform>(second).is_none());
654 }
655
656 #[test]
657 fn propagation_skips_unchanged_worlds_but_sees_later_edits() {
658 let mut world = World::new();
659 let parent = world.spawn(Transform::new([2.0, 0.0, 0.0])).id();
660 let child = world.spawn(Transform::new([1.0, 0.0, 0.0])).id();
661 set_parent(&mut world, child, parent).unwrap();
662 propagate_transforms(&mut world);
663
664 world.get_mut::<GlobalTransform>(child).unwrap().matrix[3][0] = 99.0;
666 propagate_transforms(&mut world);
667 assert_eq!(
668 world.get::<GlobalTransform>(child).unwrap().matrix[3][0],
669 99.0
670 );
671
672 world.get_mut::<Transform>(parent).unwrap().position[0] = 5.0;
673 propagate_transforms(&mut world);
674 assert_eq!(
675 world.get::<GlobalTransform>(child).unwrap().matrix[3][0],
676 6.0
677 );
678
679 world.despawn(parent);
681 propagate_transforms(&mut world);
682 assert_eq!(
683 world.get::<GlobalTransform>(child).unwrap().matrix[3][0],
684 1.0
685 );
686 assert_eq!(
687 world.resource::<HierarchyDiagnostics>().missing_parents,
688 vec![child]
689 );
690 }
691
692 #[test]
693 fn hierarchy_error_has_the_public_error_traits() {
694 fn assert_traits<
695 T: Error + Clone + Copy + Eq + Send + Sync + 'static,
696 >() {
697 }
698 assert_traits::<HierarchyError>();
699 let entity = World::new().spawn_empty().id();
700 assert_eq!(
701 HierarchyError::MissingEntity(entity).to_string(),
702 format!("entity {entity:?} does not exist")
703 );
704 }
705}