feat(engine-ecs): add traversal query termHEADmaster

2 files changed, 190 insertions, 79 deletions

diff --git a/engine-ecs/src/query/flexible.rs b/engine-ecs/src/query/flexible.rs
index fd1e30e..0198fb4 100644
--- a/engine-ecs/src/query/flexible.rs
+++ b/engine-ecs/src/query/flexible.rs
@@ -1,41 +1,34 @@
 //! Low-level querying.
-use std::iter::{repeat_n, FlatMap, RepeatN, Zip};
-
 use crate::component::storage::archetype::{Archetype, EntityIter};
-use crate::component::storage::{ArchetypeRefIter, ArchetypeSearchTerms};
+use crate::component::storage::{ArchetypeRefIter, TraversalResult};
 use crate::entity::Handle as EntityHandle;
 use crate::query::Terms;
+use crate::util::array_vec::ArrayVec;
 use crate::World;
 
 /// Low-level entity query structure.
 #[derive(Debug)]
-pub struct Query<'world, const MAX_TERM_CNT: usize>
+pub struct Query<'world, const TERM_CAP: usize>
 {
     world: &'world World,
-    terms: Terms<MAX_TERM_CNT>,
+    terms: Terms<TERM_CAP>,
 }
 
-impl<'world, const MAX_TERM_CNT: usize> Query<'world, MAX_TERM_CNT>
+impl<'world, const TERM_CAP: usize> Query<'world, TERM_CAP>
 {
     /// Iterates over the entities matching this query.
     #[must_use]
-    pub fn iter(&self) -> Iter<'_, 'world>
+    pub fn iter<'this>(&'this self) -> Iter<'this, TERM_CAP>
+    where
+        'world: 'this,
     {
         Iter {
-            iter: self
+            archetype_iter: self
                 .world
                 .data
                 .component_storage
-                .search_archetypes(ArchetypeSearchTerms {
-                    present: &self.terms.present,
-                    absent: &self.terms.absent
-                })
-                .flat_map(
-                    (|archetype| {
-                        repeat_n(archetype, archetype.entity_cnt())
-                            .zip(archetype.entities())
-                    }) as ComponentIterMapFn,
-                ),
+                .search_archetypes(&self.terms),
+            current: None,
             world: self.world,
         }
     }
@@ -46,16 +39,19 @@ impl<'world, const MAX_TERM_CNT: usize> Query<'world, MAX_TERM_CNT>
         self.world
     }
 
-    pub(crate) fn new(world: &'world World, terms: Terms<MAX_TERM_CNT>) -> Self
+    pub(crate) fn new(world: &'world World, terms: Terms<TERM_CAP>) -> Self
     {
         Self { world, terms }
     }
 }
 
-impl<'query, 'world, const MAX_TERM_CNT: usize> IntoIterator for &'query Query<'world, MAX_TERM_CNT>
+impl<'query, 'world, const TERM_CAP: usize> IntoIterator
+    for &'query Query<'world, TERM_CAP>
+where
+    'world: 'query,
 {
-    type IntoIter = Iter<'query, 'world>;
-    type Item = EntityHandle<'world>;
+    type IntoIter = Iter<'query, TERM_CAP>;
+    type Item = EntityHandle<'query>;
 
     fn into_iter(self) -> Self::IntoIter
     {
@@ -63,30 +59,43 @@ impl<'query, 'world, const MAX_TERM_CNT: usize> IntoIterator for &'query Query<'
     }
 }
 
-pub struct Iter<'query, 'world>
+pub struct Iter<'query, const TERM_CAP: usize>
 {
-    iter: QueryEntityIter<'query, 'world>,
-    world: &'world World,
+    archetype_iter: ArchetypeRefIter<'query, 'query, TERM_CAP>,
+    current: Option<(
+        &'query Archetype,
+        ArrayVec<TraversalResult, TERM_CAP>,
+        EntityIter<'query>,
+    )>,
+    world: &'query World,
 }
 
-impl<'query, 'world> Iterator for Iter<'query, 'world>
+impl<'query, const TERM_CAP: usize> Iter<'query, TERM_CAP>
 {
-    type Item = EntityHandle<'world>;
-
-    fn next(&mut self) -> Option<Self::Item>
+    pub fn traversal_results(&self) -> Option<&[TraversalResult]>
     {
-        let (archetype, entity) = self.iter.next()?;
-
-        Some(EntityHandle::new(archetype, entity, self.world))
+        self.current
+            .as_ref()
+            .map(|(_, traversal_results, _)| traversal_results.as_ref())
     }
 }
 
-type ComponentIterMapFnOutput<'a> = Zip<RepeatN<&'a Archetype>, EntityIter<'a>>;
+impl<'query, const TERM_CAP: usize> Iterator for Iter<'query, TERM_CAP>
+{
+    type Item = EntityHandle<'query>;
 
-type ComponentIterMapFn = for<'a> fn(&'a Archetype) -> ComponentIterMapFnOutput<'a>;
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        if let Some((archetype, _, entity_iter)) = self.current.as_mut() {
+            if let Some(entity) = entity_iter.next() {
+                return Some(EntityHandle::new(archetype, entity, self.world));
+            }
+        }
+
+        let (archetype, traversal_results) = self.archetype_iter.next()?;
 
-type QueryEntityIter<'query, 'world> = FlatMap<
-    ArchetypeRefIter<'world, 'query>,
-    ComponentIterMapFnOutput<'world>,
-    ComponentIterMapFn,
->;
+        self.current = Some((archetype, traversal_results, archetype.entities()));
+
+        self.next()
+    }
+}
diff --git a/engine-ecs/src/query/term.rs b/engine-ecs/src/query/term.rs
index 04bca1d..1bcb3dd 100644
--- a/engine-ecs/src/query/term.rs
+++ b/engine-ecs/src/query/term.rs
@@ -1,20 +1,23 @@
 use std::any::type_name;
 use std::marker::PhantomData;
 
-use crate::World;
 use crate::component::{
     Component,
     Handle as ComponentHandle,
     HandleMut as ComponentHandleMut,
 };
-use crate::entity::Handle as EntityHandle;
 use crate::query::{
+    SearchResult,
     Term,
+    TermMetadata,
+    TermTuple,
     TermsBuilder,
     TermsBuilderInterface,
+    Traversal,
+    TraversalKind,
 };
-use crate::tuple::Tuple;
 use crate::uid::With as WithUid;
+use crate::World;
 
 pub struct With<WithUidT>
 where
@@ -23,26 +26,27 @@ where
     _pd: PhantomData<WithUidT>,
 }
 
-impl<'world, WithUidT> Term<'world> for With<WithUidT>
+impl<'query, WithUidT> Term<'query> for With<WithUidT>
 where
     WithUidT: WithUid,
 {
-    type AddField<Fields: Tuple> = Fields;
+    type Fields = ();
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.present([WithUidT::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        _entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        _search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
-        fields
+        ()
     }
 }
 
@@ -53,48 +57,50 @@ where
     _pd: PhantomData<WithUidT>,
 }
 
-impl<'world, WithUidT> Term<'world> for Without<WithUidT>
+impl<'query, WithUidT> Term<'query> for Without<WithUidT>
 where
     WithUidT: WithUid,
 {
-    type AddField<Fields: Tuple> = Fields;
+    type Fields = ();
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
         terms_builder.absent([WithUidT::uid()]);
     }
 
-    fn add_field<Fields: Tuple>(
-        _entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        _search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
-        fields
+        ()
     }
 }
 
-impl<'world, ComponentT: Component> Term<'world> for Option<&ComponentT>
+impl<'query, ComponentT: Component> Term<'query> for Option<&ComponentT>
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<Option<ComponentHandle<'world, ComponentT>>>;
+    type Fields = (Option<ComponentHandle<'query, ComponentT>>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        _world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        _world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         let component = (|| {
-            let comp_ref = &entity_handle
+            let comp_ref = &search_result
+                .entity_handle
                 .get_matching_components(ComponentT::id())
                 .next()?;
 
@@ -109,33 +115,36 @@ impl<'world, ComponentT: Component> Term<'world> for Option<&ComponentT>
             }
         })();
 
-        fields.with_elem(component)
+        (component,)
     }
 }
 
-impl<'world, ComponentT: Component> Term<'world> for Option<&mut ComponentT>
+impl<'query, ComponentT: Component> Term<'query> for Option<&mut ComponentT>
 {
-    type AddField<Fields: Tuple> =
-        Fields::WithElementAtEnd<Option<ComponentHandleMut<'world, ComponentT>>>;
+    type Fields = (Option<ComponentHandleMut<'query, ComponentT>>,);
 
     fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
         _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        _term_metadata: TermMetadata,
     )
     {
     }
 
-    fn add_field<Fields: Tuple>(
-        entity_handle: &EntityHandle<'world>,
-        world: &'world World,
-        fields: Fields,
-    ) -> Self::AddField<Fields>
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
     {
         let component = (|| {
-            let comp_ref = &entity_handle
+            let comp_ref = &search_result
+                .entity_handle
                 .get_matching_components(ComponentT::id())
                 .next()?;
 
-            match ComponentHandleMut::<ComponentT>::from_entity_component_ref(comp_ref, world) {
+            match ComponentHandleMut::<ComponentT>::from_entity_component_ref(
+                comp_ref, world,
+            ) {
                 Ok(component) => Some(component),
                 Err(err) => {
                     panic!(
@@ -146,6 +155,99 @@ impl<'world, ComponentT: Component> Term<'world> for Option<&mut ComponentT>
             }
         })();
 
-        fields.with_elem(component)
+        (component,)
+    }
+}
+
+pub struct Traverse<TermsT, Kind, Relation>
+{
+    _pd: PhantomData<(TermsT, Kind, Relation)>,
+}
+
+impl<'query, TermsT, Kind, Relation> Term<'query> for Traverse<TermsT, Kind, Relation>
+where
+    TermsT: TermTuple<'query>,
+    Kind: TraversalKindType,
+    Relation: Component,
+{
+    type Fields = TermsT::Fields;
+
+    fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
+        terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        term_metadata: TermMetadata,
+    )
+    {
+        terms_builder.traverse([Traversal {
+            kind: Kind::traversal_kind(),
+            relation: Relation::id(),
+            terms: |traversal| {
+                let mut terms_builder = TermsBuilder::default();
+
+                TermsT::apply_terms_to_builder(
+                    &mut terms_builder,
+                    traversal
+                        .term_metadata
+                        .level
+                        .checked_add(1)
+                        .expect("Too large term level. Would overflow"),
+                );
+
+                terms_builder.build()
+            },
+            term_metadata,
+        }]);
     }
+
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+    ) -> Self::Fields
+    {
+        let Some(traversal_result) = search_result
+            .traversal_results
+            .iter()
+            .find(|traversal_result| traversal_result.term_metadata == term_metadata)
+        else {
+            unreachable!();
+        };
+
+        let Some(found_ent) = world.get_entity(traversal_result.found_ent) else {
+            unreachable!();
+        };
+
+        TermsT::get_fields(
+            world,
+            &SearchResult {
+                entity_handle: found_ent,
+                traversal_results: search_result.traversal_results,
+            },
+            term_metadata
+                .level
+                .checked_add(1)
+                .expect("Too large term level. Would overflow"),
+        )
+    }
+}
+
+pub trait TraversalKindType: sealed::Sealed
+{
+    fn traversal_kind() -> TraversalKind;
+}
+
+pub struct TraverseUp;
+
+impl TraversalKindType for TraverseUp
+{
+    fn traversal_kind() -> TraversalKind
+    {
+        TraversalKind::Up
+    }
+}
+
+impl sealed::Sealed for TraverseUp {}
+
+mod sealed
+{
+    pub trait Sealed {}
 }