diff options
Diffstat (limited to 'ecs/src/query.rs')
| -rw-r--r-- | ecs/src/query.rs | 622 |
1 files changed, 464 insertions, 158 deletions
diff --git a/ecs/src/query.rs b/ecs/src/query.rs index f3318bd..ccb7add 100644 --- a/ecs/src/query.rs +++ b/ecs/src/query.rs @@ -1,115 +1,91 @@ -use std::iter::{Filter, Flatten, Map}; +use std::any::type_name; use std::marker::PhantomData; -use crate::component::storage::{ - Archetype, - ArchetypeEntity, - ArchetypeRefIter, - EntityIter, - Storage as ComponentStorage, -}; +use seq_macro::seq; + use crate::component::{ Component, - Metadata as ComponentMetadata, - Sequence as ComponentSequence, -}; -use crate::lock::{ReadGuard, WriteGuard}; -use crate::query::options::Options; -use crate::system::{ - NoInitParamFlag as NoInitSystemParamFlag, - Param as SystemParam, - System, + Handle as ComponentHandle, + HandleMut as ComponentHandleMut, }; -use crate::uid::Uid; -use crate::{EntityComponent, World}; +use crate::entity::Handle as EntityHandle; +use crate::query::flexible::{Iter as FlexibleQueryIter, Query as FlexibleQuery}; +use crate::system::{Param as SystemParam, System}; +use crate::uid::{Kind as UidKind, Uid, With as WithUid}; +use crate::util::array_vec::ArrayVec; +use crate::util::Array; +use crate::World; -pub mod options; +pub mod flexible; +pub mod term; #[derive(Debug)] -pub struct Query<'world, Comps, OptionsT = ()> +pub struct Query<'world, FieldTerms, FieldlessTerms = ()> where - Comps: ComponentSequence, + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, { world: &'world World, - component_storage: ReadGuard<'world, ComponentStorage>, - _pd: PhantomData<(Comps, OptionsT)>, + // A term tuple type can have a maximum of 17 elements + inner: FlexibleQuery<'world, 17>, + _pd: PhantomData<(FieldTerms, FieldlessTerms)>, } -impl<'world, Comps, OptionsT> Query<'world, Comps, OptionsT> +impl<'world, FieldTerms, FieldlessTerms> Query<'world, FieldTerms, FieldlessTerms> where - Comps: ComponentSequence, - OptionsT: Options, + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, { - /// Iterates over the entities matching this query. + /// Iterates over the entities matching this query, the iterator item being the entity + /// components. #[must_use] - pub fn iter_mut( - &'world self, - ) -> ComponentIterMut<'world, Comps, QueryEntityIter<'world>> + pub fn iter<'query>( + &'query self, + ) -> Iter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>> { - #[cfg(feature = "debug")] - tracing::debug!("Searching for {}", std::any::type_name::<Comps>()); + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); - #[allow(clippy::map_flatten)] - ComponentIterMut { + Iter { world: self.world, - entities: self - .component_storage - .find_entities(Comps::metadata()) - .map(Archetype::entities as ComponentIterMapFn) - .flatten() - .filter(|entity| OptionsT::entity_filter(entity.components())), + iter: self.inner.iter(), comps_pd: PhantomData, } } - /// Iterates over the entities matching this query. + /// Iterates over the entities matching this query, the iterator item being the entity + /// [`Uid`] and the matching entity components. #[must_use] - pub fn iter(&'world self) -> ComponentIter<'world, Comps, QueryEntityIter<'world>> + pub fn iter_with_euids<'query>( + &'query self, + ) -> ComponentAndEuidIter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>> { - #[cfg(feature = "debug")] - tracing::debug!("Searching for {}", std::any::type_name::<Comps>()); + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); - #[allow(clippy::map_flatten)] - ComponentIter { + ComponentAndEuidIter { world: self.world, - entities: self - .component_storage - .find_entities(Comps::metadata()) - .map(Archetype::entities as ComponentIterMapFn) - .flatten() - .filter(|entity| OptionsT::entity_filter(entity.components())), + iter: self.inner.iter(), comps_pd: PhantomData, } } - /// Iterates over the entities matching this query and has the provided extra - /// component. + /// 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_extra_comps( - &'world self, - extra_components: impl IntoIterator<Item = ComponentMetadata>, - ) -> ComponentIter<'world, Comps, QueryEntityIter<'world>> + pub fn iter_with<'query, OutIter>( + &'query self, + func: impl FnOnce(FlexibleQueryIter<'query>) -> OutIter, + ) -> Iter<'query, 'world, FieldTerms, OutIter> + where + OutIter: Iterator<Item = EntityHandle<'query>>, { - #[cfg(feature = "debug")] - tracing::debug!( - "Searching for {} + extra components", - std::any::type_name::<Comps>() - ); - - #[allow(clippy::map_flatten)] - ComponentIter { + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); + + Iter { world: self.world, - entities: self - .component_storage - .find_entities( - Comps::metadata() - .into_iter() - .chain(extra_components) - .collect::<Vec<_>>(), - ) - .map(Archetype::entities as ComponentIterMapFn) - .flatten() - .filter(|entity| OptionsT::entity_filter(entity.components())), + iter: func(self.inner.iter()), comps_pd: PhantomData, } } @@ -118,51 +94,45 @@ where #[must_use] pub fn get_entity_uid(&self, entity_index: usize) -> Option<Uid> { - Some( - self.component_storage - .find_entities(Comps::metadata()) - .flat_map(|archetype| archetype.entities()) - .filter(|entity| OptionsT::entity_filter(entity.components())) - .nth(entity_index)? - .uid(), - ) + Some(self.inner.iter().nth(entity_index)?.uid()) } pub(crate) fn new(world: &'world World) -> Self { + let mut terms_builder = Terms::builder(); + + FieldTerms::apply_terms_to_builder(&mut terms_builder); + FieldlessTerms::apply_terms_to_builder(&mut terms_builder); + Self { world, - component_storage: world - .data - .component_storage - .read_nonblock() - .expect("Failed to acquire read-only component storage lock"), + inner: world.flexible_query(terms_builder.build()), _pd: PhantomData, } } } -impl<'world, Comps, OptionsT> IntoIterator for &'world Query<'world, Comps, OptionsT> +impl<'query, 'world, FieldTerms, FieldlessTerms> IntoIterator + for &'query Query<'world, FieldTerms, FieldlessTerms> where - Comps: ComponentSequence, - OptionsT: Options, + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, { - type IntoIter = ComponentIterMut<'world, Comps, QueryEntityIter<'world>>; - type Item = Comps::MutRefs<'world>; + type IntoIter = Iter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>>; + type Item = FieldTerms::Fields<'query>; fn into_iter(self) -> Self::IntoIter { - self.iter_mut() + self.iter() } } -unsafe impl<'world, Comps, OptionsT> SystemParam<'world> - for Query<'world, Comps, OptionsT> +impl<'world, FieldTerms, FieldlessTerms> SystemParam<'world> + for Query<'world, FieldTerms, FieldlessTerms> where - Comps: ComponentSequence, - OptionsT: Options, + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, { - type Flags = NoInitSystemParamFlag; type Input = (); fn initialize<SystemImpl>( @@ -181,93 +151,429 @@ where } } -type ComponentIterMapFn = for<'a> fn(&'a Archetype) -> EntityIter<'a>; +#[derive(Debug)] +pub struct Terms<const MAX_TERM_CNT: usize> +{ + required_components: ArrayVec<Uid, MAX_TERM_CNT>, + excluded_components: ArrayVec<Uid, MAX_TERM_CNT>, +} -type ComponentIterFilterFn = for<'a, 'b> fn(&'a &'b ArchetypeEntity) -> bool; +impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT> +{ + pub fn builder() -> TermsBuilder<MAX_TERM_CNT> + { + TermsBuilder::default() + } +} -type QueryEntityIter<'world> = Filter< - Flatten<Map<ArchetypeRefIter<'world>, ComponentIterMapFn>>, - ComponentIterFilterFn, ->; +#[derive(Debug, Default)] +#[must_use] +pub struct TermsBuilder<const MAX_TERM_CNT: usize> +{ + required_components: ArrayVec<Uid, MAX_TERM_CNT>, + excluded_components: ArrayVec<Uid, MAX_TERM_CNT>, +} -pub struct ComponentIterMut<'world, Comps, EntityIter> -where - EntityIter: Iterator<Item = &'world ArchetypeEntity>, +#[allow(clippy::return_self_not_must_use)] +pub trait TermsBuilderInterface { - world: &'world World, - entities: EntityIter, - comps_pd: PhantomData<Comps>, + fn with<WithUidT: WithUid>(self) -> Self; + + fn without<WithUidT: WithUid>(self) -> Self; + + fn with_required(self, ids: impl Array<Uid>) -> Self; + + fn without_ids(self, ids: impl Array<Uid>) -> Self; } -impl<'world, Comps, EntityIter> Iterator for ComponentIterMut<'world, Comps, EntityIter> -where - Comps: ComponentSequence + 'world, - EntityIter: Iterator<Item = &'world ArchetypeEntity>, +macro_rules! impl_terms_builder { + ($($impl_content: tt)*) => { + impl<const MAX_TERM_CNT: usize> + TermsBuilderInterface for TermsBuilder<MAX_TERM_CNT> + { + $($impl_content)* + } + + impl<const MAX_TERM_CNT: usize> + TermsBuilderInterface for &mut TermsBuilder<MAX_TERM_CNT> + { + $($impl_content)* + } + }; +} + +impl_terms_builder! { + #[allow(unused_mut)] + fn with<WithUidT: WithUid>(mut self) -> Self + { + let insert_index = self.required_components + .partition_point(|id| *id <= WithUidT::uid()); + + self.required_components + .insert(insert_index, WithUidT::uid()); + + self + } + + #[allow(unused_mut)] + fn without<WithUidT: WithUid>(mut self) -> Self + { + let insert_index = self.excluded_components + .partition_point(|id| *id <= WithUidT::uid()); + + self.excluded_components + .insert(insert_index, WithUidT::uid()); + + self + } + + #[allow(unused_mut)] + fn with_required(mut self, mut ids: impl Array<Uid>) -> Self + { + if !ids.as_ref().is_sorted() { + ids.as_mut().sort(); + } + + if self.required_components.is_empty() { + self.required_components.extend(ids); + return self; + } + + let mut id_iter = ids.into_iter(); + + while let Some(id) = id_iter.next() { + let insert_index = self.required_components + .partition_point(|other_id| *other_id <= id); + + if insert_index == self.required_components.len() { + self.required_components.extend([id].into_iter().chain(id_iter)); + + return self; + } + + self.required_components + .insert(insert_index, id); + + } + + self + } + + #[allow(unused_mut)] + fn without_ids(mut self, mut ids: impl Array<Uid>) -> Self + { + if !ids.as_ref().is_sorted() { + ids.as_mut().sort(); + } + + if self.excluded_components.is_empty() { + self.excluded_components.extend(ids); + return self; + } + + let mut id_iter = ids.into_iter(); + + while let Some(id) = id_iter.next() { + let insert_index = self.excluded_components + .partition_point(|other_id| *other_id <= id); + + if insert_index == self.excluded_components.len() { + self.excluded_components.extend([id].into_iter().chain(id_iter)); + + return self; + } + + self.excluded_components + .insert(insert_index, id); + + } + + self + } +} + +impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT> { - type Item = Comps::MutRefs<'world>; + #[must_use] + pub fn build(self) -> Terms<MAX_TERM_CNT> + { + debug_assert!(self.required_components.is_sorted()); + debug_assert!(self.excluded_components.is_sorted()); - fn next(&mut self) -> Option<Self::Item> + Terms { + required_components: self.required_components, + excluded_components: self.excluded_components, + } + } +} + +pub trait TermWithoutField +{ + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); +} + +pub trait TermWithField +{ + type Field<'a>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world>; +} + +impl<ComponentT: Component> TermWithField for &ComponentT +{ + type Field<'a> = ComponentHandle<'a, ComponentT>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) { - Some(Comps::from_components_mut( - self.entities.next()?.components().iter(), - self.world, - lock_component_rw, - )) + terms_builder.with::<ComponentT>(); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + _world: &'world World, + ) -> Self::Field<'world> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let Some(component) = entity_handle + .get_matching_components(ComponentT::id()) + .next() + else { + panic!( + concat!( + "Component {} was not found in entity {}. There ", + "is most likely a bug in the entity querying" + ), + type_name::<ComponentT>(), + entity_handle.uid() + ); + }; + + Self::Field::from_entity_component_ref(component).unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }) } } -fn lock_component_rw( - entity_component: &EntityComponent, -) -> WriteGuard<'_, Box<dyn Component>> +impl<ComponentT: Component> TermWithField for &mut ComponentT { - entity_component - .component - .write_nonblock() - .unwrap_or_else(|_| { + type Field<'a> = ComponentHandleMut<'a, ComponentT>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with::<ComponentT>(); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + _world: &'world World, + ) -> Self::Field<'world> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let Some(component) = entity_handle + .get_matching_components(ComponentT::id()) + .next() + else { + panic!( + concat!( + "Component {} was not found in entity {}. There ", + "is most likely a bug in the entity querying" + ), + type_name::<ComponentT>(), + entity_handle.uid() + ); + }; + + Self::Field::from_entity_component_ref(component).unwrap_or_else(|err| { panic!( - "Failed to acquire read-write lock to component {}", - entity_component.name + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() ); }) + } +} + +pub trait TermWithoutFieldTuple +{ + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); +} + +pub trait TermWithFieldTuple +{ + type Fields<'component>; + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); + + fn get_fields<'component>( + entity_handle: &EntityHandle<'component>, + world: &'component World, + ) -> Self::Fields<'component>; +} + +pub struct Iter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, +{ + world: &'world World, + iter: EntityHandleIter, + comps_pd: PhantomData<FieldTerms>, } -pub struct ComponentIter<'world, Comps, EntityIter> +impl<'query, 'world, FieldTerms, EntityHandleIter> + Iter<'query, 'world, FieldTerms, EntityHandleIter> where - EntityIter: Iterator<Item = &'world ArchetypeEntity>, + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, + 'world: 'query, +{ + /// Creates a new iterator from the given entity handle iterator. + /// + /// # Important + /// All of the yielded entities of the entity handle iterator should match the + /// terms `Terms`. The [`Self::next`] function will panic if it encounters a + /// entity that does not match the terms `Terms`. + pub fn new(world: &'world World, iter: EntityHandleIter) -> Self + { + Self { world, iter, comps_pd: PhantomData } + } +} + +impl<'query, 'world, FieldTerms, EntityHandleIter> Iterator + for Iter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, + 'world: 'query, +{ + type Item = FieldTerms::Fields<'query>; + + fn next(&mut self) -> Option<Self::Item> + { + let entity_handle = self.iter.next()?; + + Some(FieldTerms::get_fields(&entity_handle, self.world)) + } +} + +pub struct ComponentAndEuidIter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, { world: &'world World, - entities: EntityIter, - comps_pd: PhantomData<Comps>, + iter: EntityHandleIter, + comps_pd: PhantomData<FieldTerms>, } -impl<'world, Comps, EntityIter> Iterator for ComponentIter<'world, Comps, EntityIter> +impl<'query, 'world, FieldTerms, EntityHandleIter> Iterator + for ComponentAndEuidIter<'query, 'world, FieldTerms, EntityHandleIter> where - Comps: ComponentSequence + 'world, - EntityIter: Iterator<Item = &'world ArchetypeEntity>, + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, + 'world: 'query, { - type Item = Comps::Refs<'world>; + type Item = (Uid, FieldTerms::Fields<'query>); fn next(&mut self) -> Option<Self::Item> { - Some(Comps::from_components( - self.entities.next()?.components().iter(), - self.world, - lock_component_ro, + let entity_handle = self.iter.next()?; + + Some(( + entity_handle.uid(), + FieldTerms::get_fields(&entity_handle, self.world), )) } } -fn lock_component_ro( - entity_component: &EntityComponent, -) -> ReadGuard<'_, Box<dyn Component>> +macro_rules! impl_term_sequence { + ($c: tt) => { + seq!(I in 0..=$c { + impl<#(Term~I: TermWithoutField,)*> TermWithoutFieldTuple for (#(Term~I,)*) + { + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT> + ) + { + #( + Term~I::apply_to_terms_builder(terms_builder); + )* + } + } + + impl<#(Term~I: TermWithField,)*> TermWithFieldTuple for (#(Term~I,)*) + { + type Fields<'component> = (#(Term~I::Field<'component>,)*); + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT> + ) + { + #( + Term~I::apply_to_terms_builder(terms_builder); + )* + } + + fn get_fields<'component>( + entity_handle: &EntityHandle<'component>, + world: &'component World, + ) -> Self::Fields<'component> + { + (#(Term~I::get_field(entity_handle, world),)*) + } + } + }); + }; +} + +seq!(C in 0..=16 { + impl_term_sequence!(C); +}); + +impl TermWithoutFieldTuple for () +{ + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } +} + +impl TermWithFieldTuple for () { - entity_component - .component - .read_nonblock() - .unwrap_or_else(|_| { - panic!( - "Failed to acquire read-write lock to component {}", - entity_component.name - ); - }) + type Fields<'component> = (); + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } + + fn get_fields<'component>( + _entity_handle: &EntityHandle<'_>, + _world: &'component World, + ) -> Self::Fields<'component> + { + } } |