1 files changed, 603 insertions, 0 deletions
diff --git a/engine-ecs/src/query.rs b/engine-ecs/src/query.rs
new file mode 100644
index 0000000..c323092
--- /dev/null
+++ b/engine-ecs/src/query.rs
@@ -0,0 +1,603 @@
+use std::any::type_name;
+use std::marker::PhantomData;
+
+use paste::paste;
+use seq_macro::seq;
+use util_macros::sub;
+
+use crate::component::{
+    Component,
+    Handle as ComponentHandle,
+    HandleMut as ComponentHandleMut,
+};
+use crate::entity::Handle as EntityHandle;
+use crate::query::flexible::{Iter as FlexibleQueryIter, Query as FlexibleQuery};
+use crate::system::{Metadata as SystemMetadata, Param as SystemParam};
+use crate::tuple::{Concat, Tuple};
+use crate::uid::Uid;
+use crate::util::array_vec::ArrayVec;
+use crate::util::Array;
+use crate::World;
+
+mod reexports
+{
+    pub use crate::component::storage::{
+        FoundByTraversal,
+        SearchTerms as Terms,
+        TermMetadata,
+        Traversal,
+        TraversalKind,
+        TraversalResult,
+    };
+}
+
+pub use reexports::*;
+
+pub mod flexible;
+pub mod term;
+
+// A term tuple type can have a maximum of 17 elements
+pub const MAX_TERM_CNT: usize = 17;
+
+#[derive(Debug)]
+pub struct Query<'world, TermsT>
+{
+    inner: FlexibleQuery<'world, MAX_TERM_CNT>,
+    _pd: PhantomData<TermsT>,
+}
+
+impl<'world, TermsT> Query<'world, TermsT>
+{
+    /// Iterates over the entities matching this query, the iterator item being the entity
+    /// components.
+    #[must_use]
+    pub fn iter<'this>(&'this self) -> Iter<'this, TermsT>
+    where
+        TermsT: TermTuple<'this>,
+        'world: 'this,
+    {
+        tracing::trace!("Searching for {}", std::any::type_name::<TermsT>());
+
+        Iter {
+            world: self.inner.world(),
+            inner: self.inner.iter(),
+            comps_pd: PhantomData,
+        }
+    }
+
+    /// 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, TermsT>
+    where
+        TermsT: TermTuple<'this>,
+        'world: 'this,
+    {
+        tracing::trace!("Searching for {}", std::any::type_name::<TermsT>());
+
+        ComponentAndEuidIter {
+            world: self.inner.world(),
+            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<'this>(&'this self, entity_index: usize) -> Option<Uid>
+    where
+        TermsT: TermTuple<'this>,
+    {
+        Some(self.inner.iter().nth(entity_index)?.uid())
+    }
+
+    /// Returns a new `Query` created from a [`FlexibleQuery`].
+    ///
+    /// # Important notes
+    /// The terms in `TermsT` must be compatible with the terms
+    /// in the given [`FlexibleQuery`], otherwise any method call or iterating might
+    /// panic.
+    #[must_use]
+    pub fn from_flexible_query(
+        flexible_query: FlexibleQuery<'world, MAX_TERM_CNT>,
+    ) -> Self
+    {
+        // TODO: Check compatability of terms
+
+        Self {
+            inner: flexible_query,
+            _pd: PhantomData,
+        }
+    }
+
+    pub fn into_flexible_query(self) -> FlexibleQuery<'world, MAX_TERM_CNT>
+    {
+        self.inner
+    }
+
+    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, 0);
+
+        Self {
+            inner: world.flexible_query(terms_builder.build()),
+            _pd: PhantomData,
+        }
+    }
+}
+
+impl<'query, 'world, TermsT> IntoIterator for &'query Query<'world, TermsT>
+where
+    TermsT: TermTuple<'query>,
+    'world: 'query,
+{
+    type IntoIter = Iter<'query, TermsT>;
+    type Item = TermsT::Fields;
+
+    fn into_iter(self) -> Self::IntoIter
+    {
+        self.iter()
+    }
+}
+
+impl<'world, TermsT> SystemParam<'world> for Query<'world, TermsT>
+where
+    TermsT: TermTuple<'world>,
+{
+    type Input = ();
+
+    fn new(world: &'world World, _system_metadata: &SystemMetadata) -> Self
+    {
+        Self::new(world)
+    }
+}
+
+impl<const MAX_TERM_CNT: usize> Terms<MAX_TERM_CNT>
+{
+    pub fn builder() -> TermsBuilder<MAX_TERM_CNT>
+    {
+        TermsBuilder::default()
+    }
+}
+
+#[derive(Debug, Default)]
+#[must_use]
+pub struct TermsBuilder<const TERM_CAP: usize>
+{
+    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<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 TERM_CAP: usize>
+            TermsBuilderInterface<TERM_CAP> for TermsBuilder<TERM_CAP>
+        {
+            $($impl_content)*
+        }
+
+        impl<const TERM_CAP: usize>
+            TermsBuilderInterface<TERM_CAP> for &mut TermsBuilder<TERM_CAP>
+        {
+            $($impl_content)*
+        }
+    };
+}
+
+impl_terms_builder! {
+    #[allow(unused_mut)]
+    fn present(mut self, mut ids: impl Array<Uid>) -> Self
+    {
+        if !ids.as_ref().is_sorted() {
+            ids.as_mut().sort();
+        }
+
+        if self.present.is_empty() {
+            self.present.extend(ids);
+            return self;
+        }
+
+        let mut id_iter = ids.into_iter();
+
+        while let Some(id) = id_iter.next() {
+            let insert_index = self.present
+                .partition_point(|other_id| *other_id <= id);
+
+            if insert_index == self.present.len() {
+                self.present.extend([id].into_iter().chain(id_iter));
+
+                return self;
+            }
+
+            self.present
+                .insert(insert_index, id);
+
+        }
+
+        self
+    }
+
+    #[allow(unused_mut)]
+    fn absent(mut self, mut ids: impl Array<Uid>) -> Self
+    {
+        if !ids.as_ref().is_sorted() {
+            ids.as_mut().sort();
+        }
+
+        if self.absent.is_empty() {
+            self.absent.extend(ids);
+            return self;
+        }
+
+        let mut id_iter = ids.into_iter();
+
+        while let Some(id) = id_iter.next() {
+            let insert_index = self.absent
+                .partition_point(|other_id| *other_id <= id);
+
+            if insert_index == self.absent.len() {
+                self.absent.extend([id].into_iter().chain(id_iter));
+
+                return self;
+            }
+
+            self.absent
+                .insert(insert_index, id);
+
+        }
+
+        self
+    }
+
+    #[allow(unused_mut)]
+    fn traverse(mut self, traversals: impl Array<Traversal<TERM_CAP>> + Clone) -> Self
+    {
+        self.traverse.extend(traversals.clone());
+
+        self
+    }
+}
+
+impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT>
+{
+    #[must_use]
+    pub fn build(self) -> Terms<MAX_TERM_CNT>
+    {
+        debug_assert!(self.present.is_sorted());
+        debug_assert!(self.absent.is_sorted());
+
+        Terms {
+            present: self.present,
+            absent: self.absent,
+            traverse: self.traverse,
+        }
+    }
+}
+
+pub trait Term<'query>
+{
+    type Fields: Tuple;
+
+    fn apply_to_terms_builder<const MAX_TERM_CNT: usize>(
+        terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+        term_metadata: TermMetadata,
+    );
+
+    fn fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+    ) -> Self::Fields;
+}
+
+impl<'query, ComponentT: Component> Term<'query> for &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 fields(
+        _world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
+    {
+        assert!(!ComponentT::id().is_pair());
+
+        let Some(component) = search_result
+            .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>(),
+                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>()
+                    );
+                }
+            };
+
+        (component,)
+    }
+}
+
+impl<'query, ComponentT: Component> Term<'query> for &mut 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 fields(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        _term_metadata: TermMetadata,
+    ) -> Self::Fields
+    {
+        assert!(!ComponentT::id().is_pair());
+
+        let Some(component) = search_result
+            .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>(),
+                search_result.entity_handle.uid()
+            );
+        };
+
+        let component = match ComponentHandleMut::<ComponentT>::from_entity_component_ref(
+            &component, world,
+        ) {
+            Ok(component) => component,
+            Err(err) => {
+                panic!(
+                    "Creating mut handle to component {} failed: {err}",
+                    type_name::<ComponentT>()
+                );
+            }
+        };
+
+        (component,)
+    }
+}
+
+impl<'query, TermT, FieldAcc> TermFieldSource<'query, FieldAcc> for TermT
+where
+    TermT: Term<'query, Fields: Concat<FieldAcc>>,
+    FieldAcc: Tuple,
+{
+    type NewFieldAcc = <TermT::Fields as Concat<FieldAcc>>::Output;
+
+    fn collect_field(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+        fields: FieldAcc,
+    ) -> Self::NewFieldAcc
+    {
+        <TermT::Fields as Concat<FieldAcc>>::concat(
+            Self::fields(world, search_result, term_metadata),
+            fields,
+        )
+    }
+}
+
+pub trait TermTuple<'query>
+{
+    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(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_level: u32,
+    ) -> Self::Fields;
+}
+
+#[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<'query>,
+{
+    world: &'query World,
+    inner: FlexibleQueryIter<'query, MAX_TERM_CNT>,
+    comps_pd: PhantomData<TermsT>,
+}
+
+impl<'query, TermsT> Iterator for Iter<'query, TermsT>
+where
+    TermsT: TermTuple<'query>,
+{
+    type Item = TermsT::Fields;
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        let entity_handle = self.inner.next()?;
+
+        Some(TermsT::get_fields(
+            self.world,
+            &SearchResult {
+                entity_handle,
+                traversal_results: self.inner.traversal_results().unwrap(),
+            },
+            0,
+        ))
+    }
+}
+
+pub struct ComponentAndEuidIter<'query, TermsT>
+where
+    TermsT: TermTuple<'query>,
+{
+    world: &'query World,
+    inner: FlexibleQueryIter<'query, MAX_TERM_CNT>,
+    comps_pd: PhantomData<TermsT>,
+}
+
+impl<'query, TermsT> Iterator for ComponentAndEuidIter<'query, TermsT>
+where
+    TermsT: TermTuple<'query>,
+{
+    type Item = (Uid, TermsT::Fields);
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        let entity_handle = self.inner.next()?;
+
+        Some((
+            entity_handle.uid(),
+            TermsT::get_fields(
+                self.world,
+                &SearchResult {
+                    entity_handle,
+                    traversal_results: self.inner.traversal_results().unwrap(),
+                },
+                0,
+            ),
+        ))
+    }
+}
+
+pub trait TermFieldSource<'query, FieldAcc>
+{
+    type NewFieldAcc;
+
+    fn collect_field(
+        world: &'query World,
+        search_result: &SearchResult<'query, '_>,
+        term_metadata: TermMetadata,
+        fields: FieldAcc,
+    ) -> Self::NewFieldAcc;
+}
+
+macro_rules! term_field_source_new_field_acc {
+    (overflow) => {
+        ()
+    };
+
+    ($index: tt) => {
+        paste! {
+            [<Term $index>]::NewFieldAcc
+        }
+    };
+}
+
+macro_rules! gen_term_tuple_impls {
+    ($c: tt) => {
+        seq!(I in 0..$c {
+            impl<'query, #(Term~I,)*> TermTuple<'query> for (#(Term~I,)*)
+            where
+                #(
+                    Term~I: Term<'query> + TermFieldSource<
+                        'query,
+                        sub!(I - 1, term_field_source_new_field_acc),
+                        NewFieldAcc: Tuple
+                    >,
+                )*
+            {
+                type Fields = sub!($c - 1, term_field_source_new_field_acc);
+
+                #[allow(unused)]
+                fn apply_terms_to_builder<const MAX_TERM_CNT: usize>(
+                    terms_builder: &mut TermsBuilder<MAX_TERM_CNT>,
+                    term_level: u32,
+                )
+                {
+                    #(
+                        Term~I::apply_to_terms_builder(
+                            terms_builder,
+                            TermMetadata {
+                                level: term_level,
+                                index: I
+                            },
+                        );
+                    )*
+                }
+
+                #[allow(unused)]
+                fn get_fields(
+                    world: &'query World,
+                    search_result: &SearchResult<'query, '_>,
+                    term_level: u32,
+                ) -> Self::Fields
+                {
+                    let fields = ();
+
+                    #(
+                        let fields = Term~I::collect_field(
+                            world,
+                            search_result,
+                            TermMetadata {
+                                level: term_level,
+                                index: I
+                            },
+                            fields
+                        );
+                    )*
+
+                    fields
+                }
+            }
+        });
+    };
+}
+
+seq!(C in 0..17 {
+    gen_term_tuple_impls!(C);
+});