diff options
Diffstat (limited to 'engine-ecs/src/component/storage.rs')
| -rw-r--r-- | engine-ecs/src/component/storage.rs | 1003 |
1 files changed, 1003 insertions, 0 deletions
diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs new file mode 100644 index 0000000..5746bea --- /dev/null +++ b/engine-ecs/src/component/storage.rs @@ -0,0 +1,1003 @@ +use std::any::Any; +use std::array::IntoIter as ArrayIter; +use std::cell::RefCell; +use std::fmt::Debug; +use std::vec::IntoIter as VecIntoIter; + +use hashbrown::HashMap; + +use crate::component::storage::archetype::{ + Archetype, + Entity as ArchetypeEntity, + EntityComponent as ArchetypeEntityComponent, + Id as ArchetypeId, +}; +use crate::component::storage::graph::{ + ArchetypeAddEdgeDfsIter, + ArchetypeAddEdgeDfsIterResult, + ArchetypeEdges, + Graph, +}; +use crate::uid::{PairParams, Uid}; +use crate::util::array_vec::ArrayVec; +use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; + +pub mod archetype; + +mod graph; + +#[derive(Debug)] +pub struct SearchTerms<const TERM_CAP: usize> +{ + pub(crate) present: ArrayVec<Uid, TERM_CAP>, + pub(crate) absent: ArrayVec<Uid, TERM_CAP>, + pub(crate) traverse: ArrayVec<Traversal<TERM_CAP>, TERM_CAP>, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct TermMetadata +{ + pub level: u32, + pub index: u32, +} + +#[derive(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> Debug for Traversal<TERM_CAP> +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + formatter + .debug_struct("Traversal") + .field("kind", &self.kind) + .field("relation", &self.relation) + .field("terms", &(self.terms)(self)) + .field("term_metadata", &self.term_metadata) + .finish() + } +} + +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, + SelfOrUp, +} + +#[derive(Debug)] +pub struct TraversalResult +{ + pub relation: Uid, + pub term_metadata: TermMetadata, + pub found: FoundByTraversal, +} + +#[derive(Debug)] +#[non_exhaustive] +pub enum FoundByTraversal +{ + SelfEntity, + OtherEntity(Uid), +} + +impl<const TERM_CAP: usize> SearchTerms<TERM_CAP> +{ + fn excluded_contains(&self, comp_id: Uid) -> bool + { + debug_assert!( + !comp_id.is_pair() + || (comp_id.is_pair() && comp_id.target() != Uid::wildcard()) + ); + + let is_found = self.absent.binary_search(&comp_id).is_ok(); + + if !is_found && comp_id.is_pair() { + return self.absent.iter().any(|excluded_comp_id| { + excluded_comp_id.is_pair() + && excluded_comp_id.has_same_relation_as(comp_id) + && excluded_comp_id.target() == Uid::wildcard() + }); + } + + is_found + } + + fn contains_conflicting(&self) -> bool + { + 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 + { + self.present + .iter() + .all(|comp_id| archetype.contains_matching_component(*comp_id)) + } +} + +#[derive(Debug, Default)] +pub struct Storage +{ + graph: Graph, + entity_archetype_lookup: HashMap<Uid, ArchetypeId>, + imaginary_archetypes: RefCell<Vec<ImaginaryArchetype>>, +} + +impl Storage +{ + pub fn search_archetypes<'search_terms, const TERM_CAP: usize>( + &self, + search_terms: &'search_terms SearchTerms<TERM_CAP>, + ) -> ArchetypeRefIter<'_, 'search_terms, TERM_CAP> + { + let archetype_id = ArchetypeId::new(search_terms.present.iter()); + + if search_terms.contains_conflicting() { + return ArchetypeRefIter { + storage: self, + pre_iter: Either::B(Vec::new().into_iter()), + dfs_iter: ArchetypeAddEdgeDfsIter::new(&self.graph, &[]), + search_terms, + }; + } + + let Some(add_edge_recursive_iter) = + self.graph.dfs_archetype_add_edges(archetype_id) + else { + self.imaginary_archetypes + .borrow_mut() + .push(ImaginaryArchetype { + id: ArchetypeId::new(search_terms.present.iter().filter( + |required_comp_id| { + !required_comp_id.is_pair() + || required_comp_id.target() != Uid::wildcard() + }, + )), + component_ids: search_terms + .present + .iter() + .copied() + .filter(|required_comp_id| { + !required_comp_id.is_pair() + || required_comp_id.target() != Uid::wildcard() + }) + .collect(), + }); + + let found_archetypes = self.find_all_archetype_with_comps(&search_terms); + + return ArchetypeRefIter { + storage: self, + pre_iter: Either::B(found_archetypes.clone().into_iter()), + dfs_iter: ArchetypeAddEdgeDfsIter::new(&self.graph, &found_archetypes), + search_terms, + }; + }; + + ArchetypeRefIter { + storage: self, + pre_iter: Either::A([archetype_id].into_iter()), + dfs_iter: add_edge_recursive_iter, + search_terms, + } + } + + pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype> + { + Some(self.graph.get_node_by_id(id)?.archetype()) + } + + pub fn create_entity(&mut self, uid: Uid) -> Result<(), EntityAlreadyExistsError> + { + debug_assert!(!uid.is_pair()); + + if self.entity_archetype_lookup.contains_key(&uid) { + return Err(EntityAlreadyExistsError); + } + + let empty_archetype_id = ArchetypeId::new_empty(); + + let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]); + + archetype_node + .archetype_mut() + .push_entity(ArchetypeEntity::new(uid, [])); + + self.entity_archetype_lookup.insert(uid, empty_archetype_id); + + Ok(()) + } + + pub fn remove_entity(&mut self, entity_uid: Uid) -> Result<ArchetypeEntity, Error> + { + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; + + let archetype_node = self + .graph + .get_node_by_id_mut(*archetype_id) + .expect("Archetype should exist"); + + let entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); + + self.entity_archetype_lookup.remove(&entity_uid); + + Ok(entity) + } + + pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype> + { + let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; + + self.get_archetype_by_id(*archetype_id) + } + + pub fn add_entity_component( + &mut self, + entity_uid: Uid, + (component_id, component_name, component): (Uid, &'static str, Box<dyn Any>), + ) -> Result<(), Error> + { + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; + + let archetype_id = *archetype_id; + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + if archetype_node + .archetype() + .contains_component_with_exact_id(component_id) + { + return Err(Error::ComponentAlreadyInEntity { + entity: entity_uid, + component: component_id, + }); + } + + let add_edge_archetype_id = if let Some(add_edge_id) = archetype_node + .get_or_insert_edges(component_id, ArchetypeEdges::default) + .add + { + if !self.graph.contains_archetype(add_edge_id) { + let (_, add_edge_comp_ids) = self + .graph + .get_node_by_id(archetype_id) + .expect("Archetype should exist") + .make_add_edge(component_id); + + self.graph.create_node(add_edge_id, &add_edge_comp_ids); + } + + add_edge_id + } else { + let archetype_node = self + .graph + .get_node_by_id(archetype_id) + .expect("Archetype should exist"); + + let (add_edge_id, add_edge_comp_ids) = + archetype_node.make_add_edge(component_id); + + if !self.graph.contains_archetype(add_edge_id) { + self.graph.create_node(add_edge_id, &add_edge_comp_ids); + } + + add_edge_id + }; + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + let mut entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); + + let add_edge_archetype = self + .graph + .get_node_by_id_mut(add_edge_archetype_id) + .expect("Add edge archetype should exist") + .archetype_mut(); + + entity.insert_component( + component_id, + ArchetypeEntityComponent::new(component, component_name), + add_edge_archetype, + ); + + add_edge_archetype.push_entity(entity); + + self.entity_archetype_lookup + .insert(entity_uid, add_edge_archetype_id); + + Ok(()) + } + + pub fn remove_entity_component( + &mut self, + entity_uid: Uid, + component_id: Uid, + ) -> Result<(), Error> + { + let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else { + return Err(Error::EntityDoesNotExist(entity_uid)); + }; + + let archetype_id = *archetype_id; + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + if !archetype_node + .archetype() + .contains_component_with_exact_id(component_id) + { + return Err(Error::ComponentNotFoundInEntity { + entity: entity_uid, + component: component_id, + }); + } + + let remove_edge_id = archetype_node + .get_or_insert_edges(component_id, ArchetypeEdges::default) + .remove + .unwrap_or_else(|| { + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + let (remove_edge_id, remove_edge_comp_ids) = + archetype_node.make_remove_edge(component_id); + + if !self.graph.contains_archetype(remove_edge_id) { + self.graph + .create_node(remove_edge_id, &remove_edge_comp_ids); + } + + remove_edge_id + }); + + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); + + let mut entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); + + let removed_component = + entity.remove_component(component_id, archetype_node.archetype()); + + self.graph + .get_node_by_id_mut(remove_edge_id) + .expect("Remove edge archetype should exist") + .archetype_mut() + .push_entity(entity); + + self.entity_archetype_lookup + .insert(entity_uid, remove_edge_id); + + tracing::debug!( + entity_id = %entity_uid, + component_id = %component_id, + component_name = removed_component.name(), + "Removed component from entity" + ); + + Ok(()) + } + + pub fn create_imaginary_archetypes(&mut self) + { + for imaginary_archetype in self.imaginary_archetypes.get_mut().drain(..) { + if self.graph.contains_archetype(imaginary_archetype.id) { + continue; + } + + self.graph + .create_node(imaginary_archetype.id, &imaginary_archetype.component_ids); + } + } + + fn find_all_archetype_with_comps<const TERM_CAP: usize>( + &self, + search_terms: &SearchTerms<TERM_CAP>, + ) -> Vec<ArchetypeId> + { + let Some(mut search_iter) = + self.graph.dfs_archetype_add_edges(ArchetypeId::new_empty()) + else { + // If the root archetype doesn't exist, no other archetype can exist either + // + // TODO: The above comment is not true. Cases where imaginary archetypes have + // been created should be handled as well + return Vec::new(); + }; + + let mut found = Vec::<ArchetypeId>::new(); + + while let Some(node_id) = search_iter.streaming_next() { + let ArchetypeAddEdgeDfsIterResult::AddEdge { + add_edge_archetype_id: node_id, + add_edge_component_id, + } = node_id + else { + continue; + }; + + if search_terms.excluded_contains(add_edge_component_id) { + search_iter.pop(); + continue; + } + + let node = self + .graph + .get_node_by_id(node_id) + .expect("Graph node found through DFS doesn't exist"); + + if node.archetype().component_cnt() < search_terms.present.len() { + continue; + } + + if !search_terms.archetype_contains_all_required(node.archetype()) { + continue; + } + + found.push(node.archetype().id()); + + search_iter.pop(); + } + + found + } +} + +#[cfg(feature = "vizoxide")] +impl Storage +{ + pub fn create_vizoxide_archetype_graph( + &self, + graph_name: impl AsRef<str>, + params: VizoxideArchetypeGraphParams, + ) -> Result<vizoxide::Graph, vizoxide::GraphvizError> + { + let viz_graph = vizoxide::Graph::builder(graph_name.as_ref()) + .strict(true) + .directed(true) + .build()?; + + let mut viz_node_lookup = HashMap::new(); + + for node in self.graph.iter_nodes() { + let id = node.archetype().id(); + + if !viz_node_lookup.contains_key(&id) { + let node = self.graph.get_node_by_id(id).unwrap(); + + let viz_node = (params.create_node_cb)( + node.archetype(), + ArchetypeMetadata { is_imaginary: false }, + viz_graph.create_node(&(params.create_node_name)( + node.archetype(), + ArchetypeMetadata { is_imaginary: false }, + )), + ) + .build()?; + + viz_node_lookup.insert(id, viz_node); + } + + for (edge_comp_id, edges) in node.iter_edges() { + if let Some(add_edge) = edges.add { + if !viz_node_lookup.contains_key(&add_edge) { + let viz_node = self.create_vizoxide_archetype_graph_edge_node( + &viz_graph, + node, + add_edge, + *edge_comp_id, + ¶ms, + )?; + + viz_node_lookup.insert(add_edge, viz_node); + } + + (params.create_edge_cb)( + node.archetype(), + *edge_comp_id, + VizoxideArchetypeGraphEdgeKind::Add, + viz_graph.create_edge( + viz_node_lookup.get(&id).unwrap(), + viz_node_lookup.get(&add_edge).unwrap(), + Some(&format!("Add {}", edge_comp_id.id())), + ), + ) + .build()?; + } + + if let Some(remove_edge) = edges.remove { + if !viz_node_lookup.contains_key(&remove_edge) { + let viz_node = self.create_vizoxide_archetype_graph_edge_node( + &viz_graph, + node, + remove_edge, + *edge_comp_id, + ¶ms, + )?; + + viz_node_lookup.insert(remove_edge, viz_node); + } + + (params.create_edge_cb)( + node.archetype(), + *edge_comp_id, + VizoxideArchetypeGraphEdgeKind::Remove, + viz_graph.create_edge( + viz_node_lookup.get(&id).unwrap(), + viz_node_lookup.get(&remove_edge).unwrap(), + Some(&format!("Remove {}", edge_comp_id.id())), + ), + ) + .build()?; + } + } + } + + drop(viz_node_lookup); + + Ok(viz_graph) + } + + fn create_vizoxide_archetype_graph_edge_node<'vizoxide_graph>( + &self, + viz_graph: &'vizoxide_graph vizoxide::Graph, + node: &graph::ArchetypeNode, + edge_id: ArchetypeId, + edge_comp_id: Uid, + params: &VizoxideArchetypeGraphParams, + ) -> Result<vizoxide::Node<'vizoxide_graph>, vizoxide::GraphvizError> + { + match self.graph.get_node_by_id(edge_id) { + Some(edge_node) => (params.create_node_cb)( + edge_node.archetype(), + ArchetypeMetadata { is_imaginary: false }, + viz_graph.create_node(&(params.create_node_name)( + edge_node.archetype(), + ArchetypeMetadata { is_imaginary: false }, + )), + ) + .build(), + None => { + let mut comp_ids = + node.archetype().component_ids_sorted().collect::<Vec<_>>(); + + let insert_index = comp_ids.partition_point(|cid| *cid <= edge_comp_id); + + comp_ids.insert(insert_index, edge_comp_id); + + let imaginary_edge_archetype = Archetype::new(edge_id, comp_ids); + + (params.create_node_cb)( + &imaginary_edge_archetype, + ArchetypeMetadata { is_imaginary: true }, + viz_graph.create_node(&(params.create_node_name)( + &imaginary_edge_archetype, + ArchetypeMetadata { is_imaginary: true }, + )), + ) + .build() + } + } + } +} + +#[cfg(feature = "vizoxide")] +pub struct VizoxideArchetypeGraphParams +{ + pub create_node_name: fn(&Archetype, ArchetypeMetadata) -> std::borrow::Cow<'_, str>, + pub create_node_cb: for<'storage, 'graph> fn( + &'storage Archetype, + ArchetypeMetadata, + vizoxide::NodeBuilder<'graph>, + ) -> vizoxide::NodeBuilder<'graph>, + pub create_edge_cb: for<'storage, 'graph> fn( + &'storage Archetype, + Uid, + VizoxideArchetypeGraphEdgeKind, + vizoxide::EdgeBuilder<'graph>, + ) -> vizoxide::EdgeBuilder<'graph>, +} + +#[cfg(feature = "vizoxide")] +#[derive(Debug, Clone)] +pub struct ArchetypeMetadata +{ + pub is_imaginary: bool, +} + +#[cfg(feature = "vizoxide")] +#[derive(Debug, Clone, Copy)] +pub enum VizoxideArchetypeGraphEdgeKind +{ + Add, + Remove, +} + +#[derive(Debug)] +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: &'search_terms SearchTerms<TERM_CAP>, +} + +impl<'component_storage, const TERM_CAP: usize> Iterator + for ArchetypeRefIter<'component_storage, '_, TERM_CAP> +{ + type Item = ( + &'component_storage Archetype, + ArrayVec<TraversalResult, TERM_CAP>, + ); + + fn next(&mut self) -> Option<Self::Item> + { + 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, traversal_results) = loop { + match self.dfs_iter.streaming_find(|res| { + matches!( + res, + ArchetypeAddEdgeDfsIterResult::AddEdge { .. } + | ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { .. } + ) + })? { + ArchetypeAddEdgeDfsIterResult::AddEdge { + add_edge_archetype_id, + add_edge_component_id, + } => { + if self.search_terms.excluded_contains(add_edge_component_id) { + self.dfs_iter.pop(); + continue; + } + + 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, + add_edge_archetype_id, + add_edge_component_id, + } => { + if self.search_terms.excluded_contains(add_edge_component_id) { + continue; + } + + 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| { + comp_id + }); + + self.storage.imaginary_archetypes.borrow_mut().push( + ImaginaryArchetype { + id: add_edge_archetype_id, + component_ids: add_edge_archetype_comps.clone(), + }, + ); + + 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, + )), + found.into_iter(), + )); + } + _ => { + unreachable!(); + } + } + }; + + Some((archetype, traversal_results)) + } +} + +impl<const TERM_CAP: usize> ArchetypeRefIter<'_, '_, TERM_CAP> +{ + fn find_edges_of_imaginary_archetype( + &self, + imaginary_archetype_comps: ArrayVec<Uid, 32>, + ) -> Vec<(Uid, ArchetypeEdges)> + { + self.storage + .find_all_archetype_with_comps(&SearchTerms { + present: imaginary_archetype_comps.clone(), + absent: ArrayVec::default(), + traverse: ArrayVec::default(), + }) + .into_iter() + .filter_map(|found_id| { + let found_archetype = self.storage.get_archetype_by_id(found_id).unwrap(); + + if found_archetype.component_cnt() < imaginary_archetype_comps.len() + 1 { + return None; + } + + let unique_comp_id = found_archetype + .component_ids_sorted() + .find(|found_archetype_comp_id| { + !imaginary_archetype_comps.iter().any( + |imaginary_archetype_comp_id| { + *imaginary_archetype_comp_id == *found_archetype_comp_id + }, + ) + }) + .expect("Oh noooo"); + + let mut add_edge_comp_ids = imaginary_archetype_comps.to_vec(); + + add_edge_comp_ids.insert_at_part_pt_by_key(unique_comp_id, |id| id); + + let add_edge = ArchetypeId::new(&add_edge_comp_ids); + + Some(( + unique_comp_id, + ArchetypeEdges { add: Some(add_edge), remove: None }, + )) + }) + .collect::<Vec<_>>() + } +} + +#[derive(Debug, thiserror::Error)] +pub enum Error +{ + #[error("Entity {0} does not exist")] + EntityDoesNotExist(Uid), + + #[error("Entity {entity} already has component {component}")] + ComponentAlreadyInEntity + { + entity: Uid, component: Uid + }, + + #[error("Entity {entity} does not have component {component}")] + ComponentNotFoundInEntity + { + entity: Uid, component: Uid + }, +} + +#[derive(Debug, thiserror::Error)] +#[error("Entity already exists")] +pub struct EntityAlreadyExistsError; + +#[derive(Debug)] +struct ImaginaryArchetype +{ + id: ArchetypeId, + 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 { + let traversal_terms = (traversal.terms)(traversal); + + match traversal.kind { + TraversalKind::Up => { + archetype + .get_matching_component_ids(traversal.relationship()) + .find_map(|relationship| { + traverse_dfs( + storage, + relationship.target(), + traversal, + &traversal_terms, + results, + ) + })?; + } + TraversalKind::SelfOrUp => { + if traversal_terms.absent.iter().all(|absent_comp_id| { + !archetype.contains_matching_component(*absent_comp_id) + }) && traversal_terms.archetype_contains_all_required(archetype) + && do_traversals( + storage, + archetype, + &traversal_terms.traverse, + results, + ) + .is_some() + { + results.push(TraversalResult { + relation: traversal.relation, + term_metadata: traversal.term_metadata, + found: FoundByTraversal::SelfEntity, + }); + + return Some(()); + } + + archetype + .get_matching_component_ids(traversal.relationship()) + .find_map(|relationship| { + traverse_dfs( + storage, + relationship.target(), + traversal, + &traversal_terms, + results, + ) + })?; + } + } + } + + 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: FoundByTraversal::OtherEntity(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)] +mod tests +{ + use crate::component::storage::archetype::Id as ArchetypeId; + use crate::component::storage::Storage; + use crate::uid::Uid; + + #[test] + fn create_entity_works() + { + let mut new_storage = Storage::default(); + + let uid = Uid::new_unique(); + + new_storage.create_entity(uid).expect("Expected Ok"); + + let archetype_node = new_storage + .graph + .get_node_by_id(ArchetypeId::new_empty()) + .expect("Archetype for entities with no component doesn't exist"); + + assert_eq!(archetype_node.archetype().component_cnt(), 0); + assert_eq!(archetype_node.archetype().entity_cnt(), 1); + + assert_eq!( + new_storage.entity_archetype_lookup.get(&uid).copied(), + Some(ArchetypeId::new_empty()) + ); + } +} |