diff options
| -rw-r--r-- | engine-ecs/src/component/storage.rs | 240 | ||||
| -rw-r--r-- | engine-ecs/src/component/storage/archetype.rs | 32 | ||||
| -rw-r--r-- | engine-ecs/src/pair.rs | 164 | ||||
| -rw-r--r-- | engine-ecs/src/query.rs | 334 | ||||
| -rw-r--r-- | engine-ecs/src/query/flexible.rs | 87 | ||||
| -rw-r--r-- | engine-ecs/src/query/term.rs | 182 | ||||
| -rw-r--r-- | engine-ecs/src/tuple.rs | 66 | ||||
| -rw-r--r-- | engine-ecs/src/util.rs | 28 | ||||
| -rw-r--r-- | engine-ecs/src/util/array_vec.rs | 26 |
9 files changed, 805 insertions, 354 deletions
diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs index a4944c7..4a1c035 100644 --- a/engine-ecs/src/component/storage.rs +++ b/engine-ecs/src/component/storage.rs @@ -17,7 +17,8 @@ use crate::component::storage::graph::{ ArchetypeEdges, Graph, }; -use crate::uid::Uid; +use crate::uid::{PairParams, Uid}; +use crate::util::array_vec::ArrayVec; use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; pub mod archetype; @@ -25,13 +26,56 @@ pub mod archetype; mod graph; #[derive(Debug)] -pub struct ArchetypeSearchTerms<'a> +pub struct SearchTerms<const TERM_CAP: usize> { - pub present: &'a [Uid], - pub absent: &'a [Uid], + pub(crate) present: ArrayVec<Uid, TERM_CAP>, + pub(crate) absent: ArrayVec<Uid, TERM_CAP>, + pub(crate) traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>, } -impl ArchetypeSearchTerms<'_> +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct TermMetadata +{ + pub level: u32, + pub index: u32, +} + +#[derive(Debug, Clone)] +pub struct Traversal<const TERM_CAP: usize> +{ + pub kind: TraversalKind, + pub relation: Uid, + pub terms: fn(&Self) -> SearchTerms<TERM_CAP>, + pub term_metadata: TermMetadata, +} + +impl<const TERM_CAP: usize> Traversal<TERM_CAP> +{ + fn relationship(&self) -> Uid + { + Uid::new_pair(&PairParams { + relation: self.relation, + target: Uid::wildcard(), + }) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +#[non_exhaustive] +pub enum TraversalKind +{ + Up, +} + +#[derive(Debug)] +pub struct TraversalResult +{ + pub relation: Uid, + pub term_metadata: TermMetadata, + pub found_ent: Uid, +} + +impl<const TERM_CAP: usize> SearchTerms<TERM_CAP> { fn excluded_contains(&self, comp_id: Uid) -> bool { @@ -55,11 +99,9 @@ impl ArchetypeSearchTerms<'_> fn contains_conflicting(&self) -> bool { - self.absent.iter().any(|excluded_comp_id| { - self.present - .binary_search(excluded_comp_id) - .is_ok() - }) + self.absent + .iter() + .any(|excluded_comp_id| self.present.binary_search(excluded_comp_id).is_ok()) } fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool @@ -80,12 +122,12 @@ pub struct Storage impl Storage { - pub fn search_archetypes<'search_terms>( + pub fn search_archetypes<'search_terms, const TERM_CAP: usize>( &self, - search_terms: ArchetypeSearchTerms<'search_terms>, - ) -> ArchetypeRefIter<'_, 'search_terms> + search_terms: &'search_terms SearchTerms<TERM_CAP>, + ) -> ArchetypeRefIter<'_, 'search_terms, TERM_CAP> { - let archetype_id = ArchetypeId::new(search_terms.present); + let archetype_id = ArchetypeId::new(search_terms.present.iter()); if search_terms.contains_conflicting() { return ArchetypeRefIter { @@ -370,9 +412,9 @@ impl Storage } } - fn find_all_archetype_with_comps( + fn find_all_archetype_with_comps<const TERM_CAP: usize>( &self, - search_terms: &ArchetypeSearchTerms<'_>, + search_terms: &SearchTerms<TERM_CAP>, ) -> Vec<ArchetypeId> { let Some(mut search_iter) = @@ -594,29 +636,52 @@ pub enum VizoxideArchetypeGraphEdgeKind } #[derive(Debug)] -pub struct ArchetypeRefIter<'storage, 'search_terms> +pub struct ArchetypeRefIter<'storage, 'search_terms, const TERM_CAP: usize> { storage: &'storage Storage, pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>, dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, - search_terms: ArchetypeSearchTerms<'search_terms>, + search_terms: &'search_terms SearchTerms<TERM_CAP>, } -impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> +impl<'component_storage, const TERM_CAP: usize> Iterator + for ArchetypeRefIter<'component_storage, '_, TERM_CAP> { - type Item = &'component_storage Archetype; + type Item = ( + &'component_storage Archetype, + ArrayVec<TraversalResult, TERM_CAP>, + ); fn next(&mut self) -> Option<Self::Item> { - if let Some(pre_iter_archetype_id) = self.pre_iter.next() { - return Some( - self.storage - .get_archetype_by_id(pre_iter_archetype_id) - .expect("Archetype should exist"), - ); + if let Some((pre_iter_archetype, pre_iter_traversal_results)) = + self.pre_iter.find_map(|archetype_id| { + let archetype = self + .storage + .get_archetype_by_id(archetype_id) + .expect("Archetype should exist"); + + let mut traversal_results = + ArrayVec::<TraversalResult, TERM_CAP>::default(); + + if do_traversals( + self.storage, + archetype, + &self.search_terms.traverse, + &mut traversal_results, + ) + .is_none() + { + return None; + }; + + Some((archetype, traversal_results)) + }) + { + return Some((pre_iter_archetype, pre_iter_traversal_results)); } - let archetype_id = loop { + let (archetype, traversal_results) = loop { match self.dfs_iter.streaming_find(|res| { matches!( res, @@ -633,7 +698,27 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> continue; } - break add_edge_archetype_id; + let add_edge_archetype = self + .storage + .get_archetype_by_id(add_edge_archetype_id) + .expect("Archetype should exist"); + + let mut traversal_results = + ArrayVec::<TraversalResult, TERM_CAP>::default(); + + if do_traversals( + self.storage, + add_edge_archetype, + &self.search_terms.traverse, + &mut traversal_results, + ) + .is_none() + { + self.dfs_iter.pop(); + continue; + }; + + break (add_edge_archetype, traversal_results); } ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { archetype, @@ -644,8 +729,9 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> continue; } - let mut add_edge_archetype_comps = - archetype.component_ids_sorted().collect::<Vec<_>>(); + let mut add_edge_archetype_comps = archetype + .component_ids_sorted() + .collect::<ArrayVec<_, 32>>(); add_edge_archetype_comps .insert_at_part_pt_by_key(add_edge_component_id, |comp_id| { @@ -659,13 +745,14 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> }, ); - let found = - self.find_edges_of_imaginary_archetype(&add_edge_archetype_comps); + let found = self.find_edges_of_imaginary_archetype( + add_edge_archetype_comps.clone(), + ); self.dfs_iter.push(( BorrowedOrOwned::Owned(Archetype::new( add_edge_archetype_id, - add_edge_archetype_comps.clone(), + add_edge_archetype_comps, )), found.into_iter(), )); @@ -676,25 +763,22 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> } }; - Some( - self.storage - .get_archetype_by_id(archetype_id) - .expect("Archetype should exist"), - ) + Some((archetype, traversal_results)) } } -impl ArchetypeRefIter<'_, '_> +impl<const TERM_CAP: usize> ArchetypeRefIter<'_, '_, TERM_CAP> { fn find_edges_of_imaginary_archetype( &self, - imaginary_archetype_comps: &[Uid], + imaginary_archetype_comps: ArrayVec<Uid, 32>, ) -> Vec<(Uid, ArchetypeEdges)> { self.storage - .find_all_archetype_with_comps(&ArchetypeSearchTerms { - present: imaginary_archetype_comps, - absent: &[], + .find_all_archetype_with_comps(&SearchTerms { + present: imaginary_archetype_comps.clone(), + absent: ArrayVec::default(), + traverse: ArrayVec::default(), }) .into_iter() .filter_map(|found_id| { @@ -757,7 +841,75 @@ pub struct EntityAlreadyExistsError; struct ImaginaryArchetype { id: ArchetypeId, - component_ids: Vec<Uid>, + component_ids: ArrayVec<Uid, 32>, +} + +fn do_traversals<const TERM_CAP: usize>( + storage: &Storage, + archetype: &Archetype, + traversals: &[Traversal<TERM_CAP>], + results: &mut ArrayVec<TraversalResult, TERM_CAP>, +) -> Option<()> +{ + // TODO: Optimize traversals. Caching is needed especially + + for traversal in traversals { + if traversal.kind == TraversalKind::Up { + archetype + .get_matching_component_ids(traversal.relationship()) + .find_map(|relationship| { + traverse_dfs( + storage, + relationship.target(), + traversal, + &(traversal.terms)(traversal), + results, + ) + })?; + } else { + unimplemented!(); + } + } + + Some(()) +} + +fn traverse_dfs<const TERM_CAP: usize>( + storage: &Storage, + ent_id: Uid, + traversal: &Traversal<TERM_CAP>, + terms: &SearchTerms<TERM_CAP>, + results: &mut ArrayVec<TraversalResult, TERM_CAP>, +) -> Option<()> +{ + let ent_archetype = storage.get_entity_archetype(ent_id)?; + + if terms + .absent + .iter() + .all(|absent_comp_id| !ent_archetype.contains_matching_component(*absent_comp_id)) + && terms.archetype_contains_all_required(ent_archetype) + && do_traversals(storage, ent_archetype, &terms.traverse, results).is_some() + { + results.push(TraversalResult { + relation: traversal.relation, + term_metadata: traversal.term_metadata, + found_ent: ent_id, + }); + + return Some(()); + } + + for relationship in ent_archetype.get_matching_component_ids(traversal.relationship()) + { + if traverse_dfs(storage, relationship.target(), traversal, terms, results) + .is_some() + { + return Some(()); + } + } + + None } #[cfg(test)] diff --git a/engine-ecs/src/component/storage/archetype.rs b/engine-ecs/src/component/storage/archetype.rs index c5cce10..236bf97 100644 --- a/engine-ecs/src/component/storage/archetype.rs +++ b/engine-ecs/src/component/storage/archetype.rs @@ -107,11 +107,6 @@ impl Archetype EntityIter { iter: self.entities.iter() } } - pub fn entity_cnt(&self) -> usize - { - self.entities.len() - } - pub fn component_cnt(&self) -> usize { self.component_index_lookup.len() @@ -182,6 +177,33 @@ impl Archetype self.contains_component_with_exact_id(component_id) } + pub fn get_matching_component_ids( + &self, + component_id: Uid, + ) -> impl Iterator<Item = Uid> + use<'_> + { + if component_id.is_pair() && component_id.target() == Uid::wildcard() { + return Either::A( + self.component_ids + .iter() + .filter(move |other_comp_id| { + other_comp_id.is_pair() + && other_comp_id.has_same_relation_as(component_id) + }) + .copied(), + ); + } + + Either::B( + (if self.contains_component_with_exact_id(component_id) { + Some(component_id) + } else { + None + }) + .into_iter(), + ) + } + pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool { debug_assert!( diff --git a/engine-ecs/src/pair.rs b/engine-ecs/src/pair.rs index 1168f67..00c6a72 100644 --- a/engine-ecs/src/pair.rs +++ b/engine-ecs/src/pair.rs @@ -14,11 +14,12 @@ use crate::entity::{ MatchingComponentIter as EntityMatchingComponentIter, }; use crate::query::{ + SearchResult, Term as QueryTerm, + TermMetadata as QueryTermMetadata, TermsBuilder as QueryTermsBuilder, TermsBuilderInterface, }; -use crate::tuple::Tuple; use crate::uid::{PairParams as UidPairParams, Uid, With as WithUid}; use crate::util::impl_multiple; use crate::{Component, EntityComponentRef, World}; @@ -192,121 +193,128 @@ where } } -impl<'world, Relation, Target> QueryTerm<'world> for Pair<Relation, &Target> +impl<'query, Relation, Target> QueryTerm<'query> for Pair<Relation, &Target> where Relation: Component, Target: Component, { - type AddField<Fields: Tuple> = - Fields::WithElementAtEnd<ComponentHandle<'world, Target>>; + type Fields = (ComponentHandle<'query, Target>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + _term_metadata: QueryTermMetadata, ) { terms_builder.present([Pair::<Relation, Target>::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: QueryTermMetadata, + ) -> Self::Fields { - let target_component = entity_handle + let target_component = search_result + .entity_handle .get_matching_components(Pair::<Relation, Target>::uid()) .next() .expect("Not possible"); - let target_component = match ComponentHandle::<Target>::from_entity_component_ref(&target_component) { - Ok(target_component) => target_component, - Err(err) => { - panic!( - "Creating handle to target component {} failed: {err}", - type_name::<Target>() - ); - } - }; + let target_component = + match ComponentHandle::<Target>::from_entity_component_ref(&target_component) + { + Ok(target_component) => target_component, + Err(err) => { + panic!( + "Creating handle to target component {} failed: {err}", + type_name::<Target>() + ); + } + }; - fields.with_elem(target_component) + (target_component,) } } -impl<'world, Relation, Target> QueryTerm<'world> for Pair<Relation, &mut Target> +impl<'query, Relation, Target> QueryTerm<'query> for Pair<Relation, &mut Target> where Relation: Component, Target: Component, { - type AddField<Fields: Tuple> = - Fields::WithElementAtEnd<ComponentHandleMut<'world, Target>>; + type Fields = (ComponentHandleMut<'query, Target>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + _term_metadata: QueryTermMetadata, ) { terms_builder.present([Pair::<Relation, Target>::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: QueryTermMetadata, + ) -> Self::Fields { - let target_component = entity_handle + let target_component = search_result + .entity_handle .get_matching_components(Pair::<Relation, Target>::uid()) .next() .expect("Not possible"); - let target_component = match ComponentHandleMut::<Target>::from_entity_component_ref(&target_component, world) { - Ok(target_component) => target_component, - Err(err) => { - panic!( - "Creating mut handle to target component {} failed: {err}", - type_name::<Target>() - ); - } - }; + let target_component = + match ComponentHandleMut::<Target>::from_entity_component_ref( + &target_component, + world, + ) { + Ok(target_component) => target_component, + Err(err) => { + panic!( + "Creating mut handle to target component {} failed: {err}", + type_name::<Target>() + ); + } + }; - fields.with_elem(target_component) + (target_component,) } } // TODO: implement QueryTerm for Pair<&Relation, Target> (or equivalent) // TODO: implement QueryTerm for Pair<&mut Relation, Target> (or equivalent) -impl<'world, Relation> QueryTerm<'world> for Pair<Relation, Wildcard> +impl<'query, Relation> QueryTerm<'query> for Pair<Relation, Wildcard> where Relation: Component, { - type AddField<Fields: Tuple> = - Fields::WithElementAtEnd<WithWildcard<'world, Relation, Wildcard>>; + type Fields = (WithWildcard<'query, Relation, Wildcard>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + _term_metadata: QueryTermMetadata, ) { terms_builder.present([Self::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: QueryTermMetadata, + ) -> Self::Fields { - let first_matching_comp = entity_handle + let first_matching_comp = search_result + .entity_handle .get_matching_components(Self::uid()) .next() .expect("Not possible"); - fields.with_elem( - WithWildcard { - world, - component_ref: first_matching_comp, - _pd: PhantomData, - } - ) + (WithWildcard { + world, + component_ref: first_matching_comp, + _pd: PhantomData, + },) } } @@ -337,45 +345,43 @@ where } } -impl<'world, Relation> QueryTerm<'world> for &[Pair<Relation, Wildcard>] +impl<'query, Relation> QueryTerm<'query> for &[Pair<Relation, Wildcard>] where Relation: Component, { - type AddField<Fields: Tuple> = - Fields::WithElementAtEnd<MultipleWithWildcard<'world, Relation, Wildcard>>; + type Fields = (MultipleWithWildcard<'query, Relation, Wildcard>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( _terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + _term_metadata: QueryTermMetadata, ) { } - 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: QueryTermMetadata, + ) -> Self::Fields { - fields.with_elem( - MultipleWithWildcard { - entity_handle: entity_handle.clone(), - world, - _pd: PhantomData, - } - ) + (MultipleWithWildcard { + entity_handle: search_result.entity_handle.clone(), + world, + _pd: PhantomData, + },) } } /// Reference to a pair with a wildcard relation/target. #[derive(Debug)] -pub struct WithWildcard<'world, Relation, Target> +pub struct WithWildcard<'query, Relation, Target> { - world: &'world World, - component_ref: EntityComponentRef<'world>, + world: &'query World, + component_ref: EntityComponentRef<'query>, _pd: PhantomData<(Relation, Target)>, } -impl<'world, Relation, Target> WithWildcard<'world, Relation, Target> +impl<'query, Relation, Target> WithWildcard<'query, Relation, Target> { /// Returns a new `WithWildcard`. /// @@ -388,7 +394,7 @@ impl<'world, Relation, Target> WithWildcard<'world, Relation, Target> /// component's ID /// - Both `Relation::uid()` and `Target::uid()` are wildcards /// - Neither `Relation::uid()` or `Target::uid()` are wildcards - pub fn new(world: &'world World, component_ref: EntityComponentRef<'world>) -> Self + pub fn new(world: &'query World, component_ref: EntityComponentRef<'query>) -> Self where Relation: ComponentOrWildcard, Target: ComponentOrWildcard, @@ -480,13 +486,13 @@ impl<'world, Relation, Target> WithWildcard<'world, Relation, Target> } } -impl<'world, Relation> WithWildcard<'world, Relation, Wildcard> +impl<'query, Relation> WithWildcard<'query, Relation, Wildcard> where Relation: Component, { /// Attempts to retrieve the target as a entity, returning `None` if not found. #[must_use] - pub fn get_target_ent(&self) -> Option<EntityHandle<'world>> + pub fn get_target_ent(&self) -> Option<EntityHandle<'query>> { let archetype = self .world @@ -562,7 +568,7 @@ pub struct MultipleWithWildcard<'a, Relation, Target> _pd: PhantomData<(Relation, Target)>, } -impl<'world, Relation, Target> MultipleWithWildcard<'world, Relation, Target> +impl<'query, Relation, Target> MultipleWithWildcard<'query, Relation, Target> { /// Returns a new `MultipleWithWildcard`. /// @@ -570,7 +576,7 @@ impl<'world, Relation, Target> MultipleWithWildcard<'world, Relation, Target> /// This function will panic if: /// - Both `Relation::uid()` and `Target::uid()` are wildcards /// - Neither `Relation::uid()` or `Target::uid()` are wildcards - pub fn new(world: &'world World, entity_handle: EntityHandle<'world>) -> Self + pub fn new(world: &'query World, entity_handle: EntityHandle<'query>) -> Self where Relation: ComponentOrWildcard, Target: ComponentOrWildcard, diff --git a/engine-ecs/src/query.rs b/engine-ecs/src/query.rs index 8549411..10260f2 100644 --- a/engine-ecs/src/query.rs +++ b/engine-ecs/src/query.rs @@ -1,8 +1,8 @@ use std::any::type_name; use std::marker::PhantomData; -use seq_macro::seq; use paste::paste; +use seq_macro::seq; use util_macros::sub; use crate::component::{ @@ -11,13 +11,27 @@ use crate::component::{ HandleMut as ComponentHandleMut, }; use crate::entity::Handle as EntityHandle; +use crate::pair::Wildcard; use crate::query::flexible::{Iter as FlexibleQueryIter, Query as FlexibleQuery}; use crate::system::{Metadata as SystemMetadata, Param as SystemParam}; -use crate::tuple::Tuple; +use crate::tuple::{Concat, Tuple}; use crate::uid::Uid; use crate::util::array_vec::ArrayVec; use crate::util::Array; -use crate::World; +use crate::{pair, World}; + +mod reexports +{ + pub use crate::component::storage::{ + SearchTerms as Terms, + TermMetadata, + Traversal, + TraversalKind, + TraversalResult, + }; +} + +pub use reexports::*; pub mod flexible; pub mod term; @@ -27,23 +41,20 @@ pub const MAX_TERM_CNT: usize = 17; #[derive(Debug)] pub struct Query<'world, TermsT> -where - TermsT: TermTuple<'world>, { inner: FlexibleQuery<'world, MAX_TERM_CNT>, _pd: PhantomData<TermsT>, } impl<'world, TermsT> Query<'world, TermsT> -where - TermsT: TermTuple<'world>, { /// Iterates over the entities matching this query, the iterator item being the entity /// components. #[must_use] - pub fn iter<'this>( - &'this self, - ) -> Iter<'this, 'world, TermsT, FlexibleQueryIter<'this, 'world>> + pub fn iter<'this>(&'this self) -> Iter<'this, TermsT> + where + TermsT: TermTuple<'this>, + 'world: 'this, { tracing::trace!("Searching for {}", std::any::type_name::<TermsT>()); @@ -57,44 +68,25 @@ where /// Iterates over the entities matching this query, the iterator item being the entity /// [`Uid`] and the matching entity components. #[must_use] - pub fn iter_with_euids<'this>( - &'this self, - ) -> ComponentAndEuidIter<'this, 'world, TermsT, FlexibleQueryIter<'this, 'world>> - { - tracing::trace!("Searching for {}", std::any::type_name::<TermsT>()); - - ComponentAndEuidIter { - world: self.inner.world(), - iter: self.inner.iter(), - comps_pd: PhantomData, - } - } - - /// Iterates over the entities matching this query using the iterator returned by - /// `func`. - /// - /// This function exists so that a custom [`EntityHandle`] iterator can be given to - /// [`Iter`] without giving the user access to a reference to the [`World`]. - #[must_use] - pub fn iter_with<'this, OutIter>( - &'this self, - func: impl FnOnce(FlexibleQueryIter<'this, 'world>) -> OutIter, - ) -> Iter<'this, 'world, TermsT, OutIter> + pub fn iter_with_euids<'this>(&'this self) -> ComponentAndEuidIter<'this, TermsT> where - OutIter: Iterator<Item = EntityHandle<'world>>, + TermsT: TermTuple<'this>, + 'world: 'this, { tracing::trace!("Searching for {}", std::any::type_name::<TermsT>()); - Iter { + ComponentAndEuidIter { world: self.inner.world(), - inner: func(self.inner.iter()), + inner: self.inner.iter(), comps_pd: PhantomData, } } /// Returns the UID of the entity at the given query iteration index. #[must_use] - pub fn get_entity_uid(&self, entity_index: usize) -> Option<Uid> + pub fn get_entity_uid<'this>(&'this self, entity_index: usize) -> Option<Uid> + where + TermsT: TermTuple<'this>, { Some(self.inner.iter().nth(entity_index)?.uid()) } @@ -124,10 +116,12 @@ where } pub(crate) fn new(world: &'world World) -> Self + where + TermsT: TermTuple<'world>, { let mut terms_builder = Terms::builder(); - TermsT::apply_terms_to_builder(&mut terms_builder); + TermsT::apply_terms_to_builder(&mut terms_builder, 0); Self { inner: world.flexible_query(terms_builder.build()), @@ -136,12 +130,12 @@ where } } -impl<'query, 'world, TermsT> IntoIterator - for &'query Query<'world, TermsT> +impl<'query, 'world, TermsT> IntoIterator for &'query Query<'world, TermsT> where - TermsT: TermTuple<'world>, + TermsT: TermTuple<'query>, + 'world: 'query, { - type IntoIter = Iter<'query, 'world, TermsT, FlexibleQueryIter<'query, 'world>>; + type IntoIter = Iter<'query, TermsT>; type Item = TermsT::Fields; fn into_iter(self) -> Self::IntoIter @@ -150,8 +144,7 @@ where } } -impl<'world, TermsT> SystemParam<'world> - for Query<'world, TermsT> +impl<'world, TermsT> SystemParam<'world> for Query<'world, TermsT> where TermsT: TermTuple<'world>, { @@ -163,13 +156,6 @@ where } } -#[derive(Debug)] -pub struct Terms<const MAX_TERM_CNT: usize> -{ - present: ArrayVec<Uid, MAX_TERM_CNT>, - absent: ArrayVec<Uid, MAX_TERM_CNT>, -} - impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT> { pub fn builder() -> TermsBuilder<MAX_TERM_CNT> @@ -180,30 +166,33 @@ impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT> #[derive(Debug, Default)] #[must_use] -pub struct TermsBuilder<const MAX_TERM_CNT: usize> +pub struct TermsBuilder<const TERM_CAP: usize> { - present: ArrayVec<Uid, MAX_TERM_CNT>, - absent: ArrayVec<Uid, MAX_TERM_CNT>, + present: ArrayVec<Uid, TERM_CAP>, + absent: ArrayVec<Uid, TERM_CAP>, + traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>, } #[allow(clippy::return_self_not_must_use)] -pub trait TermsBuilderInterface +pub trait TermsBuilderInterface<const TERM_CAP: usize> { fn present(self, ids: impl Array<Uid>) -> Self; fn absent(self, ids: impl Array<Uid>) -> Self; + + fn traverse(self, traversals: impl Array<Traversal<TERM_CAP>> + Clone) -> Self; } macro_rules! impl_terms_builder { ($($impl_content: tt)*) => { - impl<const MAX_TERM_CNT: usize> - TermsBuilderInterface for TermsBuilder<MAX_TERM_CNT> + impl<const TERM_CAP: usize> + TermsBuilderInterface<TERM_CAP> for TermsBuilder<TERM_CAP> { $($impl_content)* } - impl<const MAX_TERM_CNT: usize> - TermsBuilderInterface for &mut TermsBuilder<MAX_TERM_CNT> + impl<const TERM_CAP: usize> + TermsBuilderInterface<TERM_CAP> for &mut TermsBuilder<TERM_CAP> { $($impl_content)* } @@ -274,6 +263,17 @@ impl_terms_builder! { self } + + #[allow(unused_mut)] + fn traverse(mut self, traversals: impl Array<Traversal<TERM_CAP>> + Clone) -> Self + { + self.traverse.extend(traversals.clone()); + + self.present( + traversals + .map(|traversal| pair!({ traversal.relation }, Wildcard).id()) + ) + } } impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT> @@ -287,45 +287,49 @@ impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT> Terms { present: self.present, absent: self.absent, + traverse: self.traverse, } } } -pub trait Term<'world> +pub trait Term<'query> { - type AddField<Fields: Tuple>; + type Fields: Tuple; 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; } -impl<'world, ComponentT: Component> Term<'world> for &ComponentT +impl<'query, ComponentT: Component> Term<'query> for &ComponentT { - type AddField<Fields: Tuple> = Fields::WithElementAtEnd<ComponentHandle<'world, ComponentT>>; + type Fields = (ComponentHandle<'query, ComponentT>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + _term_metadata: TermMetadata, ) { terms_builder.present([ComponentT::id()]); } - 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 { assert!(!ComponentT::id().is_pair()); - let Some(component) = entity_handle + let Some(component) = search_result + .entity_handle .get_matching_components(ComponentT::id()) .next() else { @@ -335,44 +339,47 @@ impl<'world, ComponentT: Component> Term<'world> for &ComponentT "is most likely a bug in the entity querying" ), type_name::<ComponentT>(), - entity_handle.uid() + search_result.entity_handle.uid() ); }; - let component = match ComponentHandle::<ComponentT>::from_entity_component_ref(&component) { - Ok(component) => component, - Err(err) => { - panic!( - "Creating handle to component {} failed: {err}", - type_name::<ComponentT>() - ); - } - }; + let component = + match ComponentHandle::<ComponentT>::from_entity_component_ref(&component) { + Ok(component) => component, + Err(err) => { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + } + }; - fields.with_elem(component) + (component,) } } -impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT +impl<'query, ComponentT: Component> Term<'query> for &mut ComponentT { - type AddField<Fields: Tuple> = Fields::WithElementAtEnd<ComponentHandleMut<'world, ComponentT>>; + type Fields = (ComponentHandleMut<'query, ComponentT>,); fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + _term_metadata: TermMetadata, ) { terms_builder.present([ComponentT::id()]); } - 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 { assert!(!ComponentT::id().is_pair()); - let Some(component) = entity_handle + let Some(component) = search_result + .entity_handle .get_matching_components(ComponentT::id()) .next() else { @@ -382,11 +389,13 @@ impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT "is most likely a bug in the entity querying" ), type_name::<ComponentT>(), - entity_handle.uid() + search_result.entity_handle.uid() ); }; - let component = match ComponentHandleMut::<ComponentT>::from_entity_component_ref(&component, world) { + let component = match ComponentHandleMut::<ComponentT>::from_entity_component_ref( + &component, world, + ) { Ok(component) => component, Err(err) => { panic!( @@ -396,57 +405,67 @@ impl<'world, ComponentT: Component> Term<'world> for &mut ComponentT } }; - fields.with_elem(component) + (component,) } } -impl<'world, TermT, FieldAcc> TermFieldSource<'world, FieldAcc> for TermT -where - TermT: Term<'world>, - TermT::AddField<FieldAcc>: Tuple, - FieldAcc: Tuple +impl<'query, TermT, FieldAcc> TermFieldSource<'query, FieldAcc> for TermT +where + TermT: Term<'query, Fields: Concat<FieldAcc>>, + FieldAcc: Tuple, { - type NewFieldAcc = TermT::AddField<FieldAcc>; + type NewFieldAcc = <TermT::Fields as Concat<FieldAcc>>::Output; fn collect_field( - entity_handle: &EntityHandle<'world>, - world: &'world World, + world: &'query World, + search_result: &SearchResult<'query, '_>, + term_metadata: TermMetadata, fields: FieldAcc, ) -> Self::NewFieldAcc { - Self::add_field(entity_handle, world, fields) + <TermT::Fields as Concat<FieldAcc>>::concat( + Self::fields(world, search_result, term_metadata), + fields, + ) } } -pub trait TermTuple<'world> +pub trait TermTuple<'query> { - type Fields; + type Fields: Tuple; fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + term_level: u32, ); fn get_fields( - entity_handle: &EntityHandle<'world>, - world: &'world World, + world: &'query World, + search_result: &SearchResult<'query, '_>, + term_level: u32, ) -> Self::Fields; } -pub struct Iter<'query, 'world, TermsT, EntityHandleIter> +#[derive(Debug)] +#[non_exhaustive] +pub struct SearchResult<'query, 'temp> +{ + pub entity_handle: EntityHandle<'query>, + pub traversal_results: &'temp [TraversalResult], +} + +pub struct Iter<'query, TermsT> where - TermsT: TermTuple<'world>, - EntityHandleIter: Iterator<Item = EntityHandle<'world>>, + TermsT: TermTuple<'query>, { - world: &'world World, - inner: EntityHandleIter, - comps_pd: PhantomData<(TermsT, &'query ())>, + world: &'query World, + inner: FlexibleQueryIter<'query, MAX_TERM_CNT>, + comps_pd: PhantomData<TermsT>, } -impl<'query, 'world, TermsT, EntityHandleIter> Iterator - for Iter<'query, 'world, TermsT, EntityHandleIter> +impl<'query, TermsT> Iterator for Iter<'query, TermsT> where - TermsT: TermTuple<'world>, - EntityHandleIter: Iterator<Item = EntityHandle<'world>>, + TermsT: TermTuple<'query>, { type Item = TermsT::Fields; @@ -454,46 +473,58 @@ where { let entity_handle = self.inner.next()?; - Some(TermsT::get_fields(&entity_handle, self.world)) + Some(TermsT::get_fields( + self.world, + &SearchResult { + entity_handle, + traversal_results: self.inner.traversal_results().unwrap(), + }, + 0, + )) } } -pub struct ComponentAndEuidIter<'query, 'world, TermsT, EntityHandleIter> +pub struct ComponentAndEuidIter<'query, TermsT> where - TermsT: TermTuple<'world>, - EntityHandleIter: Iterator<Item = EntityHandle<'world>>, + TermsT: TermTuple<'query>, { - world: &'world World, - iter: EntityHandleIter, - comps_pd: PhantomData<(TermsT, &'query ())>, + world: &'query World, + inner: FlexibleQueryIter<'query, MAX_TERM_CNT>, + comps_pd: PhantomData<TermsT>, } -impl<'query, 'world, TermsT, EntityHandleIter> Iterator - for ComponentAndEuidIter<'query, 'world, TermsT, EntityHandleIter> +impl<'query, TermsT> Iterator for ComponentAndEuidIter<'query, TermsT> where - TermsT: TermTuple<'world>, - EntityHandleIter: Iterator<Item = EntityHandle<'world>>, + TermsT: TermTuple<'query>, { type Item = (Uid, TermsT::Fields); fn next(&mut self) -> Option<Self::Item> { - let entity_handle = self.iter.next()?; + let entity_handle = self.inner.next()?; Some(( entity_handle.uid(), - TermsT::get_fields(&entity_handle, self.world), + TermsT::get_fields( + self.world, + &SearchResult { + entity_handle, + traversal_results: self.inner.traversal_results().unwrap(), + }, + 0, + ), )) } } -pub trait TermFieldSource<'world, FieldAcc> +pub trait TermFieldSource<'query, FieldAcc> { type NewFieldAcc; fn collect_field( - entity_handle: &EntityHandle<'world>, - world: &'world World, + world: &'query World, + search_result: &SearchResult<'query, '_>, + term_metadata: TermMetadata, fields: FieldAcc, ) -> Self::NewFieldAcc; } @@ -513,11 +544,11 @@ macro_rules! term_field_source_new_field_acc { macro_rules! gen_term_tuple_impls { ($c: tt) => { seq!(I in 0..$c { - impl<'world, #(Term~I,)*> TermTuple<'world> for (#(Term~I,)*) + impl<'query, #(Term~I,)*> TermTuple<'query> for (#(Term~I,)*) where #( - Term~I: Term<'world> + TermFieldSource< - 'world, + Term~I: Term<'query> + TermFieldSource< + 'query, sub!(I - 1, term_field_source_new_field_acc), NewFieldAcc: Tuple >, @@ -527,24 +558,40 @@ macro_rules! gen_term_tuple_impls { #[allow(unused)] fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( - terms_builder: &mut TermsBuilder<MAX_TERM_CNT> + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + term_level: u32, ) { #( - Term~I::apply_to_terms_builder(terms_builder); + Term~I::apply_to_terms_builder( + terms_builder, + TermMetadata { + level: term_level, + index: I + }, + ); )* } #[allow(unused)] fn get_fields( - entity_handle: &EntityHandle<'world>, - world: &'world World, + world: &'query World, + search_result: &SearchResult<'query, '_>, + term_level: u32, ) -> Self::Fields { let fields = (); #( - let fields = Term~I::collect_field(entity_handle, world, fields); + let fields = Term~I::collect_field( + world, + search_result, + TermMetadata { + level: term_level, + index: I + }, + fields + ); )* fields @@ -557,4 +604,3 @@ macro_rules! gen_term_tuple_impls { seq!(C in 0..17 { gen_term_tuple_impls!(C); }); - 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 {} } diff --git a/engine-ecs/src/tuple.rs b/engine-ecs/src/tuple.rs index 15e1719..a2073b1 100644 --- a/engine-ecs/src/tuple.rs +++ b/engine-ecs/src/tuple.rs @@ -1,4 +1,5 @@ -use std::{any::TypeId, convert::Infallible}; +use std::any::TypeId; +use std::convert::Infallible; use paste::paste; use seq_macro::seq; @@ -55,6 +56,32 @@ pub trait ReduceElement<Accumulator, Operation> type Return; } +pub trait ElementConcat<Acc> +{ + type Output; + + fn add_to(self, acc: Acc) -> Self::Output; +} + +impl<Elem, Acc> ElementConcat<Acc> for Elem +where + Acc: Tuple, +{ + type Output = Acc::WithElementAtEnd<Elem>; + + fn add_to(self, acc: Acc) -> Self::Output + { + acc.with_elem(self) + } +} + +pub trait Concat<Left> +{ + type Output; + + fn concat(self, left: Left) -> Self::Output; +} + macro_rules! tuple_reduce_elem_tuple { (overflow) => { () @@ -67,6 +94,18 @@ macro_rules! tuple_reduce_elem_tuple { }; } +macro_rules! tuple_concat_elem_ouput { + (overflow) => { + Left + }; + + ($index: tt) => { + paste! { + [<Elem $index>]::Output + } + }; +} + macro_rules! elem_type_by_index { (overflow) => { () @@ -148,6 +187,31 @@ macro_rules! impl_tuple_traits { } } + paste! { + impl<Left, #(Elem~I,)*> Concat<Left> for (#(Elem~I,)*) + where + Left: Tuple, + #( + Elem~I: ElementConcat< + sub!(I - 1, tuple_concat_elem_ouput), + >, + )* + { + type Output = sub!($cnt - 1, tuple_concat_elem_ouput); + + fn concat(self, left: Left) -> Self::Output + { + let out = left; + + #( + let out = self.I.add_to(out); + )* + + out + } + } + } + impl<#(Elem~I: 'static,)*> WithAllElemLtStatic for (#(Elem~I,)*) { fn get_mut<Element: 'static>(&mut self, index: usize) -> Option<&mut Element> diff --git a/engine-ecs/src/util.rs b/engine-ecs/src/util.rs index f56a5c4..c52608a 100644 --- a/engine-ecs/src/util.rs +++ b/engine-ecs/src/util.rs @@ -34,6 +34,23 @@ impl<Item> VecExt<Item> for Vec<Item> } } +impl<Item, const CAPACITY: usize> VecExt<Item> for ArrayVec<Item, CAPACITY> +{ + fn insert_at_part_pt_by_key<Key>( + &mut self, + item: Item, + mut func: impl FnMut(&Item) -> &Key, + ) where + Key: Ord, + { + let key = func(&item); + + let insert_index = self.partition_point(|other_item| func(other_item) <= key); + + self.insert(insert_index, item); + } +} + pub trait StreamingIterator { type Item<'a> @@ -190,9 +207,16 @@ pub trait Array<Item>: + Sortable<Item = Item> + sealed::Sealed { + fn map<T>(self, func: impl FnMut(Item) -> T) -> impl Array<T>; } -impl<Item, const CNT: usize> Array<Item> for [Item; CNT] {} +impl<Item, const CNT: usize> Array<Item> for [Item; CNT] +{ + fn map<T>(self, func: impl FnMut(Item) -> T) -> impl Array<T> + { + self.map(func) + } +} impl<Item, const CNT: usize> sealed::Sealed for [Item; CNT] {} @@ -414,6 +438,8 @@ macro_rules! const_assert { pub(crate) use const_assert; +use crate::util::array_vec::ArrayVec; + mod sealed { pub trait Sealed {} diff --git a/engine-ecs/src/util/array_vec.rs b/engine-ecs/src/util/array_vec.rs index 5d0aac9..5863507 100644 --- a/engine-ecs/src/util/array_vec.rs +++ b/engine-ecs/src/util/array_vec.rs @@ -57,9 +57,23 @@ impl<Item, const CAPACITY: usize> ArrayVec<Item, CAPACITY> } } +impl<Item, const CAPACITY: usize> FromIterator<Item> for ArrayVec<Item, CAPACITY> +{ + fn from_iter<IterT: IntoIterator<Item = Item>>(iter: IterT) -> Self + { + let mut new = Self::default(); + + for item in iter { + new.push(item); + } + + new + } +} + impl<Item, const CAPACITY: usize> Extend<Item> for ArrayVec<Item, CAPACITY> { - fn extend<IntoIter: IntoIterator<Item = Item>>(&mut self, iter: IntoIter) + fn extend<Iter: IntoIterator<Item = Item>>(&mut self, iter: Iter) { for item in iter { self.push(item); @@ -116,6 +130,16 @@ impl<Item, const CAPACITY: usize> Default for ArrayVec<Item, CAPACITY> } } +impl<Item, const CAPACITY: usize> Clone for ArrayVec<Item, CAPACITY> +where + Item: Clone, +{ + fn clone(&self) -> Self + { + Self::from_iter(self.iter().cloned()) + } +} + impl<Item, const CAPACITY: usize> Drop for ArrayVec<Item, CAPACITY> { fn drop(&mut self) |