diff options
Diffstat (limited to 'ecs/src/component/storage.rs')
| -rw-r--r-- | ecs/src/component/storage.rs | 1118 |
1 files changed, 642 insertions, 476 deletions
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs index ffd682e..b27b552 100644 --- a/ecs/src/component/storage.rs +++ b/ecs/src/component/storage.rs @@ -1,621 +1,787 @@ -use std::any::type_name; -use std::borrow::Borrow; +use std::any::Any; +use std::array::IntoIter as ArrayIter; use std::cell::RefCell; -use std::collections::{HashMap, HashSet}; -use std::slice::Iter as SliceIter; -use std::vec::IntoIter as OwnedVecIter; - -use crate::archetype::Id as ArchetypeId; -use crate::component::{ - Component, - IsOptional as ComponentIsOptional, - Metadata as ComponentMetadata, +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::type_name::TypeName; -use crate::uid::Uid; -use crate::util::Sortable; -use crate::EntityComponent; +use crate::component::storage::graph::{ + ArchetypeAddEdgeDfsIter, + ArchetypeAddEdgeDfsIterResult, + ArchetypeEdges, + Graph, +}; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt}; -#[derive(Debug, Default)] -pub struct Storage +pub mod archetype; + +mod graph; + +#[derive(Debug)] +pub struct ArchetypeSearchTerms<'a> { - archetypes: Vec<Archetype>, - archetype_lookup: RefCell<HashMap<ArchetypeId, ArchetypeLookupEntry>>, - entity_archetype_lookup: HashMap<Uid, ArchetypeId>, + pub required_components: &'a [Uid], + pub excluded_components: &'a [Uid], } -impl Storage +impl ArchetypeSearchTerms<'_> { - pub fn find_entities<CompMetadataList>( - &self, - mut components_metadata: CompMetadataList, - ) -> ArchetypeRefIter<'_> - where - CompMetadataList: Sortable<Item = ComponentMetadata>, - CompMetadataList: AsRef<[ComponentMetadata]>, + fn excluded_contains(&self, comp_id: Uid) -> bool { - components_metadata.sort_by_key_b(|component_metadata| component_metadata.id); + let comp_id_kind = comp_id.kind(); - let archetype_id = ArchetypeId::from_components_metadata(&components_metadata); + debug_assert!( + comp_id_kind == UidKind::Component + || (comp_id_kind == UidKind::Pair + && comp_id.target_component() != Uid::wildcard()) + ); - // This looks stupid but the borrow checker complains otherwise - if self.archetype_lookup.borrow().contains_key(&archetype_id) { - return self.iter_archetypes_by_lookup(archetype_id); - } + let is_found = self.excluded_components.binary_search(&comp_id).is_ok(); - let comp_ids_set = create_non_opt_component_id_set(components_metadata.as_ref()); + if !is_found && comp_id_kind == UidKind::Pair { + return self.excluded_components.iter().any(|excluded_comp_id| { + excluded_comp_id.kind() == UidKind::Pair + && excluded_comp_id.has_same_relation_as(comp_id) + && excluded_comp_id.target_component() == Uid::wildcard() + }); + } - let matching_archetype_indices = self - .archetypes - .iter() - .enumerate() - .filter_map(|(index, archetype)| { - if archetype.component_ids_is_superset(&comp_ids_set) { - return Some(index); - } + is_found + } - None - }) - .collect(); - - self.archetype_lookup.borrow_mut().insert( - archetype_id, - ArchetypeLookupEntry { - component_ids: comp_ids_set, - archetype_indices: matching_archetype_indices, - }, - ); + fn contains_conflicting(&self) -> bool + { + self.excluded_components.iter().any(|excluded_comp_id| { + self.required_components + .binary_search(excluded_comp_id) + .is_ok() + }) + } - self.iter_archetypes_by_lookup(archetype_id) + fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool + { + self.required_components + .iter() + .all(|comp_id| archetype.contains_matching_component(*comp_id)) } +} - pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype> +#[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>( + &self, + search_terms: ArchetypeSearchTerms<'search_terms>, + ) -> ArchetypeRefIter<'_, 'search_terms> { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; + let archetype_id = ArchetypeId::new(search_terms.required_components); + + 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 archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; + 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.required_components.iter().filter( + |required_comp_id| { + required_comp_id.kind() != UidKind::Pair + || required_comp_id.target_component() != Uid::wildcard() + }, + )), + component_ids: search_terms + .required_components + .iter() + .copied() + .filter(|required_comp_id| { + required_comp_id.kind() != UidKind::Pair + || required_comp_id.target_component() != 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, + }; + }; - self.archetypes.get(archetype_index) + ArchetypeRefIter { + storage: self, + pre_iter: Either::A([archetype_id].into_iter()), + dfs_iter: add_edge_recursive_iter, + search_terms, + } } - #[cfg_attr(feature = "debug", tracing::instrument(skip_all))] - pub fn push_entity( - &mut self, - entity_uid: Uid, - mut components: Vec<Box<dyn Component>>, - ) -> Result<(ArchetypeId, Uid), Error> + pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype> { - if self.entity_archetype_lookup.contains_key(&entity_uid) { - return Err(Error::EntityAlreadyExists(entity_uid)); + Some(self.graph.get_node_by_id(id)?.archetype()) + } + + pub fn create_entity(&mut self, uid: Uid) -> Result<(), Error> + { + debug_assert_eq!(uid.kind(), UidKind::Entity); + + if self.entity_archetype_lookup.contains_key(&uid) { + return Err(Error::EntityAlreadyExists(uid)); } - components.sort_by_key(|component| component.self_id()); + let empty_archetype_id = ArchetypeId::new_empty(); - #[cfg(feature = "debug")] - tracing::debug!( - "Pushing entity with components: ({})", - components - .iter() - .map(|component| component.type_name()) - .collect::<Vec<_>>() - .join(", ") - ); + let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]); - let archetype_id = ArchetypeId::from_components_metadata( - &components - .iter() - .map(|component| ComponentMetadata::get(&**component)) - .collect::<Vec<_>>(), - ); + archetype_node + .archetype_mut() + .push_entity(ArchetypeEntity::new(uid, [])); - let comp_ids_set = create_non_opt_component_id_set( - components - .iter() - .map(|component| ComponentMetadata::get(&**component)), - ); + self.entity_archetype_lookup.insert(uid, empty_archetype_id); - let archetype_index = - self.get_or_create_archetype(archetype_id, &comp_ids_set, &components); + Ok(()) + } - self.populate_matching_archetype_lookup_entries(&comp_ids_set, archetype_index); + 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 = self - .archetypes - .get_mut(archetype_index) - .expect("Archetype is gone"); + let archetype_node = self + .graph + .get_node_by_id_mut(*archetype_id) + .expect("Archetype should exist"); - archetype.push_entity(entity_uid, components); + let entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); - archetype - .entity_lookup - .insert(entity_uid, archetype.entities.len() - 1); + self.entity_archetype_lookup.remove(&entity_uid); - self.entity_archetype_lookup - .insert(entity_uid, archetype_id); + Ok(entity) + } - Ok((archetype_id, entity_uid)) + 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_components_to_entity( + pub fn add_entity_component( &mut self, entity_uid: Uid, - components: Vec<Box<dyn Component>>, - ) -> Option<()> + (component_id, component_name, component): (Uid, &'static str, Box<dyn Any>), + ) -> Result<(), Error> { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; + 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 archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; + 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); + } - let archetype = self.archetypes.get_mut(archetype_index)?; + add_edge_id + } else { + let archetype_node = self + .graph + .get_node_by_id(archetype_id) + .expect("Archetype should exist"); - let contains_component_already = components - .iter() - .any(|component| archetype.component_ids.contains_key(&component.self_id())); - - if contains_component_already { - let component_cnt = components.len(); - - // TODO: return error - panic!( - "Entity with UID {:?} already contains one or more component(s) ({})", - entity_uid, - components - .iter() - .flat_map(|component| [component.type_name(), ", "]) - .enumerate() - .take_while(|(index, _)| { *index < (component_cnt * 2) - 1 }) - .map(|(_, component)| component) - .collect::<String>() - ); - } + let (add_edge_id, add_edge_comp_ids) = + archetype_node.make_add_edge(component_id); - let entity = archetype.take_entity(entity_uid)?; + if !self.graph.contains_archetype(add_edge_id) { + self.graph.create_node(add_edge_id, &add_edge_comp_ids); + } - self.entity_archetype_lookup.remove(&entity_uid); + 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_id, component_name), + add_edge_archetype, + ); - self.push_entity( - entity_uid, - entity - .components - .into_iter() - .map(|component| component.component.into_inner()) - .chain(components) - .collect(), - ) - .expect("Not supposed to return Err since the entity is removed"); + add_edge_archetype.push_entity(entity); - Some(()) + self.entity_archetype_lookup + .insert(entity_uid, add_edge_archetype_id); + + Ok(()) } - pub fn remove_components_from_entity( + pub fn remove_entity_component( &mut self, entity_uid: Uid, - component_ids: impl IntoIterator<Item = Uid>, - ) -> Option<()> + component_id: Uid, + ) -> Result<(), Error> { - let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?; + 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 archetype_index = - self.find_archetype_index_with_entity(*archetype_id, entity_uid)?; + 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); + } - let archetype = self.archetypes.get_mut(archetype_index)?; + remove_edge_id + }); - let entity = archetype.take_entity(entity_uid)?; + let archetype_node = self + .graph + .get_node_by_id_mut(archetype_id) + .expect("Archetype should exist"); - let component_ids_set = component_ids.into_iter().collect::<HashSet<_>>(); + let mut entity = archetype_node + .archetype_mut() + .remove_entity(entity_uid) + .expect("Entity should exist in archetype"); - self.entity_archetype_lookup.remove(&entity_uid); + entity.remove_component(component_id, archetype_node.archetype()); - self.push_entity( - entity_uid, - entity - .components - .into_iter() - .map(|component| component.component.into_inner()) - .filter(|component| !component_ids_set.contains(&component.self_id())) - .collect(), - ) - .expect("Not supposed to return Err since the entity is removed"); + self.graph + .get_node_by_id_mut(remove_edge_id) + .expect("Remove edge archetype should exist") + .archetype_mut() + .push_entity(entity); - Some(()) + self.entity_archetype_lookup + .insert(entity_uid, remove_edge_id); + + Ok(()) } - fn populate_matching_archetype_lookup_entries( - &mut self, - comp_ids_set: &HashSet<Uid>, - archetype_index: usize, - ) + pub fn create_imaginary_archetypes(&mut self) { - let mut archetype_lookup = self.archetype_lookup.borrow_mut(); - - for (_, lookup_entry) in archetype_lookup.iter_mut() { - if &lookup_entry.component_ids == comp_ids_set { + for imaginary_archetype in self.imaginary_archetypes.get_mut().drain(..) { + if self.graph.contains_archetype(imaginary_archetype.id) { continue; } - // There shouldn't be duplicate archetype indices in the lookup entry - if lookup_entry.archetype_indices.contains(&archetype_index) { - continue; - } - - if lookup_entry.component_ids.is_subset(comp_ids_set) { - lookup_entry.archetype_indices.push(archetype_index); - } + self.graph + .create_node(imaginary_archetype.id, &imaginary_archetype.component_ids); } } - fn get_or_create_archetype( - &mut self, - archetype_id: ArchetypeId, - comp_ids_set: &HashSet<Uid>, - components: &[Box<dyn Component>], - ) -> usize + fn find_all_archetype_with_comps( + &self, + search_terms: &ArchetypeSearchTerms<'_>, + ) -> Vec<ArchetypeId> { - let mut archetype_lookup = self.archetype_lookup.borrow_mut(); + 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; + }; - let lookup_entry = archetype_lookup.entry(archetype_id).or_insert_with(|| { - ArchetypeLookupEntry { - component_ids: comp_ids_set.clone(), - archetype_indices: Vec::with_capacity(1), + 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.required_components.len() { + continue; + } + + if !search_terms.archetype_contains_all_required(node.archetype()) { + continue; } - }); - if lookup_entry.archetype_indices.is_empty() { - self.archetypes.push(Archetype::new( - components.iter().map(|component| component.self_id()), - )); + found.push(node.archetype().id()); - lookup_entry - .archetype_indices - .push(self.archetypes.len() - 1); + search_iter.pop(); } - // SAFETY: Above, we push a archetype index if archetype_indices is empty so this - // cannot fail - unsafe { *lookup_entry.archetype_indices.first().unwrap_unchecked() } + found } +} - fn find_archetype_index_with_entity( +#[cfg(feature = "vizoxide")] +impl Storage +{ + pub fn create_vizoxide_archetype_graph( &self, - archetype_id: ArchetypeId, - entity_uid: Uid, - ) -> Option<usize> + graph_name: impl AsRef<str>, + params: VizoxideArchetypeGraphParams, + ) -> Result<vizoxide::Graph, vizoxide::GraphvizError> { - let archetype_lookup = self.archetype_lookup.borrow_mut(); + 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); + } - let archetype_lookup_entry = archetype_lookup.get(&archetype_id)?; + 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()?; + } - // TODO: Also have a hashmap for precise archetype ID -> archetype index lookup. - // This way is slow - archetype_lookup_entry - .archetype_indices - .iter() - .find(|archetype_index| { - let Some(archetype) = self.archetypes.get(**archetype_index) else { - return false; - }; + 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()?; + } + } + } - archetype.has_entity(entity_uid) - }) - .copied() + drop(viz_node_lookup); + + Ok(viz_graph) } - fn iter_archetypes_by_lookup(&self, archetype_id: ArchetypeId) - -> ArchetypeRefIter<'_> + 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> { - let archetype_lookup = self.archetype_lookup.borrow(); - - // The archetype indices have to be cloned to prevent a panic when query - // iterations are nested. The panic happens because the archetype_lookup RefCell - // is borrowed and it tries to mutably borrow it - let archetype_indices = archetype_lookup - .get(&archetype_id) - .unwrap() - .archetype_indices - .clone(); - - ArchetypeRefIter { - indices: archetype_indices.into_iter(), - archetypes: &self.archetypes, + 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() + } } } } -/// Component storage error -#[derive(Debug, Clone, thiserror::Error)] -pub enum Error +#[cfg(feature = "vizoxide")] +pub struct VizoxideArchetypeGraphParams { - #[error("Entity already exists")] - EntityAlreadyExists(Uid), + 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>, } -impl TypeName for Storage +#[cfg(feature = "vizoxide")] +#[derive(Debug, Clone)] +pub struct ArchetypeMetadata { - fn type_name(&self) -> &'static str - { - type_name::<Self>() - } + pub is_imaginary: bool, } -#[derive(Debug)] -struct ArchetypeLookupEntry +#[cfg(feature = "vizoxide")] +#[derive(Debug, Clone, Copy)] +pub enum VizoxideArchetypeGraphEdgeKind { - component_ids: HashSet<Uid>, - archetype_indices: Vec<usize>, + Add, + Remove, } #[derive(Debug)] -pub struct Archetype +pub struct ArchetypeRefIter<'storage, 'search_terms> { - component_ids: HashMap<Uid, usize>, - entity_lookup: HashMap<Uid, usize>, - entities: Vec<ArchetypeEntity>, + storage: &'storage Storage, + pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>, + dfs_iter: ArchetypeAddEdgeDfsIter<'storage>, + search_terms: ArchetypeSearchTerms<'search_terms>, } -impl Archetype +impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_> { - fn new(component_ids: impl IntoIterator<Item = Uid>) -> Self - { - Self { - component_ids: component_ids - .into_iter() - .enumerate() - .map(|(index, component_id)| (component_id, index)) - .collect(), - entity_lookup: HashMap::new(), - entities: Vec::new(), - } - } + type Item = &'component_storage Archetype; - pub fn component_ids_is_superset(&self, other_component_ids: &HashSet<Uid>) -> bool + fn next(&mut self) -> Option<Self::Item> { - if other_component_ids.len() <= self.component_ids.len() { - other_component_ids - .iter() - .all(|v| self.component_ids.contains_key(v)) - } else { - false + 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"), + ); } - } - - pub fn get_entity(&self, entity_uid: Uid) -> Option<&ArchetypeEntity> - { - let entity_index = *self.entity_lookup.get(&entity_uid)?; - - self.entities.get(entity_index) - } - - pub fn entities(&self) -> EntityIter<'_> - { - EntityIter { iter: self.entities.iter() } - } - - pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> - { - self.component_ids.get(&component_id).copied() - } - - fn push_entity( - &mut self, - entity_uid: Uid, - components: impl IntoIterator<Item = Box<dyn Component>>, - ) - { - self.entities.push(ArchetypeEntity { - uid: entity_uid, - components: components.into_iter().map(Into::into).collect(), - }); - } - - pub fn take_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity> - { - let entity_index = self.entity_lookup.remove(&entity_uid)?; - - let entity = self.entities.remove(entity_index); - for index in self.entity_lookup.values_mut() { - if *index > entity_index { - *index -= 1; + let archetype_id = 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; + } + + break add_edge_archetype_id; + } + 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::<Vec<_>>(); + + add_edge_archetype_comps.insert_at_partition_point_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); + + self.dfs_iter.push(( + BorrowedOrOwned::Owned(Archetype::new( + add_edge_archetype_id, + add_edge_archetype_comps.clone(), + )), + found.into_iter(), + )); + } + _ => { + unreachable!(); + } } - } + }; - Some(entity) - } - - fn has_entity(&self, entity_uid: Uid) -> bool - { - self.entity_lookup.contains_key(&entity_uid) + Some( + self.storage + .get_archetype_by_id(archetype_id) + .expect("Archetype should exist"), + ) } } -#[derive(Debug)] -pub struct ArchetypeEntity +impl ArchetypeRefIter<'_, '_> { - uid: Uid, - components: Vec<EntityComponent>, -} - -impl ArchetypeEntity -{ - pub fn uid(&self) -> Uid + fn find_edges_of_imaginary_archetype( + &self, + imaginary_archetype_comps: &[Uid], + ) -> Vec<(Uid, ArchetypeEdges)> { - self.uid - } + self.storage + .find_all_archetype_with_comps(&ArchetypeSearchTerms { + required_components: imaginary_archetype_comps, + excluded_components: &[], + }) + .into_iter() + .filter_map(|found_id| { + let found_archetype = self.storage.get_archetype_by_id(found_id).unwrap(); - pub fn components(&self) -> &[EntityComponent] - { - &self.components - } + if found_archetype.component_cnt() < imaginary_archetype_comps.len() + 1 { + return None; + } - pub fn get_component(&self, index: usize) -> Option<&EntityComponent> - { - self.components.get(index) - } -} + 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"); -#[derive(Debug)] -pub struct ArchetypeRefIter<'component_storage> -{ - indices: OwnedVecIter<usize>, - archetypes: &'component_storage [Archetype], -} + let mut add_edge_comp_ids = imaginary_archetype_comps.to_vec(); -impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage> -{ - type Item = &'component_storage Archetype; + add_edge_comp_ids + .insert_at_partition_point_by_key(unique_comp_id, |id| *id); - fn next(&mut self) -> Option<Self::Item> - { - let archetype_index = self.indices.next()?; + let add_edge = ArchetypeId::new(&add_edge_comp_ids); - Some( - self.archetypes - .get(archetype_index) - .expect("Archetype index in archetype lookup entry was not found"), - ) + Some(( + unique_comp_id, + ArchetypeEdges { add: Some(add_edge), remove: None }, + )) + }) + .collect::<Vec<_>>() } } -#[derive(Debug)] -pub struct EntityIter<'archetype> +#[derive(Debug, thiserror::Error)] +pub enum Error { - iter: SliceIter<'archetype, ArchetypeEntity>, -} + #[error("Entity with ID {0:?} already exists")] + EntityAlreadyExists(Uid), -impl<'archetype> Iterator for EntityIter<'archetype> -{ - type Item = &'archetype ArchetypeEntity; + #[error("Entity with ID {0:?} does not exist")] + EntityDoesNotExist(Uid), - fn next(&mut self) -> Option<Self::Item> + #[error("Entity with ID {entity:?} already has component with ID {component:?}")] + ComponentAlreadyInEntity { - self.iter.next() - } + entity: Uid, component: Uid + }, + + #[error("Entity with ID {entity:?} does not have component with ID {component:?}")] + ComponentNotFoundInEntity + { + entity: Uid, component: Uid + }, } -fn create_non_opt_component_id_set<Item>( - component_metadata_iter: impl IntoIterator<Item = Item>, -) -> HashSet<Uid> -where - Item: Borrow<ComponentMetadata>, +#[derive(Debug)] +struct ImaginaryArchetype { - component_metadata_iter - .into_iter() - .filter_map(|item| { - let component_metadata = item.borrow(); - - if component_metadata.is_optional == ComponentIsOptional::Yes { - return None; - } - - Some(component_metadata.id) - }) - .collect::<HashSet<_>>() + id: ArchetypeId, + component_ids: Vec<Uid>, } #[cfg(test)] mod tests { - - use ecs_macros::Component; - - use super::Storage; - use crate::archetype::Id as ArchetypeId; - use crate::component::{ - Component, - IsOptional as ComponentIsOptional, - Metadata as ComponentMetadata, - }; + use crate::component::storage::archetype::Id as ArchetypeId; + use crate::component::storage::Storage; use crate::uid::{Kind as UidKind, Uid}; - #[derive(Debug, Component)] - struct HealthPotion - { - _hp_restoration: u32, - } - - #[derive(Debug, Component)] - struct Hookshot - { - _range: u32, - } - - #[derive(Debug, Component)] - struct DekuNut - { - _throwing_damage: u32, - } - - #[derive(Debug, Component)] - struct Bow - { - _damage: u32, - } - - #[derive(Debug, Component)] - struct IronBoots; - #[test] - fn push_entity_works() + fn create_entity_works() { - let mut component_storage = Storage::default(); - - component_storage - .push_entity( - Uid::new_unique(UidKind::Entity), - vec![ - Box::new(HealthPotion { _hp_restoration: 12 }), - Box::new(Hookshot { _range: 50 }), - ], - ) - .expect("Expected Ok"); - - assert_eq!(component_storage.archetypes.len(), 1); - - let archetype = component_storage - .archetypes - .first() - .expect("Expected a archetype in archetypes Vec"); - - assert_eq!(archetype.component_ids.len(), 2); + let mut new_storage = Storage::default(); - // One entity - assert_eq!(archetype.entities.len(), 1); + let uid = Uid::new_unique(UidKind::Entity); - let entity_components = archetype - .entities - .first() - .expect("Expected a entity in archetype"); + new_storage.create_entity(uid).expect("Expected Ok"); - assert_eq!(entity_components.components.len(), 2); + 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!(component_storage.archetype_lookup.borrow().len(), 1); + assert_eq!(archetype_node.archetype().component_cnt(), 0); + assert_eq!(archetype_node.archetype().entity_cnt(), 1); - let mut components_metadata = [ - ComponentMetadata { - id: HealthPotion::id(), - is_optional: ComponentIsOptional::No, - }, - ComponentMetadata { - id: Hookshot::id(), - is_optional: ComponentIsOptional::No, - }, - ]; - - components_metadata.sort_by_key(|comp_metadata| comp_metadata.id); - - let archetype_lookup = component_storage.archetype_lookup.borrow(); - - let lookup_entry = archetype_lookup - .get(&ArchetypeId::from_components_metadata(&components_metadata)) - .expect("Expected entry in archetype lookup map"); - - let first_archetype_index = lookup_entry - .archetype_indices - .first() - .expect("Expected archetype lookup to contain a archetype reference"); - - assert_eq!(*first_archetype_index, 0); + assert_eq!( + new_storage.entity_archetype_lookup.get(&uid).copied(), + Some(ArchetypeId::new_empty()) + ); } } |