summaryrefslogtreecommitdiff
path: root/ecs/src/component/storage.rs
diff options
context:
space:
mode:
authorHampusM <hampus@hampusmat.com>2026-05-21 17:55:20 +0200
committerHampusM <hampus@hampusmat.com>2026-05-21 17:55:20 +0200
commit8022e8998290b067b8aa0cb9cba8ba410826bdab (patch)
tree7171e79ce530e03079046ee8fd12167160c45480 /ecs/src/component/storage.rs
parent412cee02c252f91bcf0b70a3f5cc5fca6d2b4c62 (diff)
chore: rename ecs* crates to engine-ecs*
Diffstat (limited to 'ecs/src/component/storage.rs')
-rw-r--r--ecs/src/component/storage.rs795
1 files changed, 0 insertions, 795 deletions
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs
deleted file mode 100644
index dc38b6a..0000000
--- a/ecs/src/component/storage.rs
+++ /dev/null
@@ -1,795 +0,0 @@
-use std::any::Any;
-use std::array::IntoIter as ArrayIter;
-use std::cell::RefCell;
-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::{Kind as UidKind, Uid};
-use crate::util::{BorrowedOrOwned, Either, StreamingIterator, VecExt};
-
-pub mod archetype;
-
-mod graph;
-
-#[derive(Debug)]
-pub struct ArchetypeSearchTerms<'a>
-{
- pub required_components: &'a [Uid],
- pub excluded_components: &'a [Uid],
-}
-
-impl ArchetypeSearchTerms<'_>
-{
- fn excluded_contains(&self, comp_id: Uid) -> bool
- {
- let comp_id_kind = comp_id.kind();
-
- debug_assert!(
- comp_id_kind == UidKind::Component
- || (comp_id_kind == UidKind::Pair
- && comp_id.target_component() != Uid::wildcard())
- );
-
- let is_found = self.excluded_components.binary_search(&comp_id).is_ok();
-
- 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()
- });
- }
-
- is_found
- }
-
- fn contains_conflicting(&self) -> bool
- {
- self.excluded_components.iter().any(|excluded_comp_id| {
- self.required_components
- .binary_search(excluded_comp_id)
- .is_ok()
- })
- }
-
- fn archetype_contains_all_required(&self, archetype: &Archetype) -> bool
- {
- self.required_components
- .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>(
- &self,
- search_terms: ArchetypeSearchTerms<'search_terms>,
- ) -> ArchetypeRefIter<'_, 'search_terms>
- {
- 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 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,
- };
- };
-
- 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_eq!(uid.kind(), UidKind::Entity);
-
- 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(
- &self,
- search_terms: &ArchetypeSearchTerms<'_>,
- ) -> 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.required_components.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,
- &params,
- )?;
-
- 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,
- &params,
- )?;
-
- 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>
-{
- storage: &'storage Storage,
- pre_iter: Either<ArrayIter<ArchetypeId, 1>, VecIntoIter<ArchetypeId>>,
- dfs_iter: ArchetypeAddEdgeDfsIter<'storage>,
- search_terms: ArchetypeSearchTerms<'search_terms>,
-}
-
-impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage, '_>
-{
- type Item = &'component_storage Archetype;
-
- 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"),
- );
- }
-
- 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_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);
-
- self.dfs_iter.push((
- BorrowedOrOwned::Owned(Archetype::new(
- add_edge_archetype_id,
- add_edge_archetype_comps.clone(),
- )),
- found.into_iter(),
- ));
- }
- _ => {
- unreachable!();
- }
- }
- };
-
- Some(
- self.storage
- .get_archetype_by_id(archetype_id)
- .expect("Archetype should exist"),
- )
- }
-}
-
-impl ArchetypeRefIter<'_, '_>
-{
- fn find_edges_of_imaginary_archetype(
- &self,
- imaginary_archetype_comps: &[Uid],
- ) -> Vec<(Uid, ArchetypeEdges)>
- {
- 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();
-
- 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 with ID {0:?} does not exist")]
- EntityDoesNotExist(Uid),
-
- #[error("Entity with ID {entity:?} already has component with ID {component:?}")]
- ComponentAlreadyInEntity
- {
- entity: Uid, component: Uid
- },
-
- #[error("Entity with ID {entity:?} does not have component with ID {component:?}")]
- ComponentNotFoundInEntity
- {
- entity: Uid, component: Uid
- },
-}
-
-#[derive(Debug, thiserror::Error)]
-#[error("Entity with already exists")]
-pub struct EntityAlreadyExistsError;
-
-#[derive(Debug)]
-struct ImaginaryArchetype
-{
- id: ArchetypeId,
- component_ids: Vec<Uid>,
-}
-
-#[cfg(test)]
-mod tests
-{
- use crate::component::storage::Storage;
- use crate::component::storage::archetype::Id as ArchetypeId;
- use crate::uid::{Kind as UidKind, Uid};
-
- #[test]
- fn create_entity_works()
- {
- let mut new_storage = Storage::default();
-
- let uid = Uid::new_unique(UidKind::Entity);
-
- 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())
- );
- }
-}