diff options
Diffstat (limited to 'engine-ecs/src')
29 files changed, 7593 insertions, 0 deletions
diff --git a/engine-ecs/src/actions.rs b/engine-ecs/src/actions.rs new file mode 100644 index 0000000..3d8afe6 --- /dev/null +++ b/engine-ecs/src/actions.rs @@ -0,0 +1,174 @@ +use crate::component::{Parts as ComponentParts, Sequence as ComponentSequence}; +use crate::event::component::Removed; +use crate::pair::Pair; +use crate::system::{Metadata as SystemMetadata, Param as SystemParam}; +use crate::uid::{Kind as UidKind, Uid, WithUidTuple}; +use crate::{ActionQueue, World}; + +/// Used to to queue up actions for a [`World`] to perform. +#[derive(Debug)] +pub struct Actions<'world> +{ + action_queue: &'world ActionQueue, + world: Option<&'world World>, +} + +impl Actions<'_> +{ + /// Queues up a entity to spawn at the end of the current tick, returning the [`Uid`] + /// that the entity will have. + pub fn spawn<Comps: ComponentSequence>(&mut self, components: Comps) -> Uid + { + let new_entity_uid = Uid::new_unique(UidKind::Entity); + + self.action_queue.push(Action::Spawn( + new_entity_uid, + components.into_parts_array().into(), + )); + + new_entity_uid + } + + /// Queues up despawning a entity at the end of the current tick. + pub fn despawn(&mut self, entity_uid: Uid) + { + debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + let Some(world) = self.world else { + self.action_queue.push(Action::Despawn(entity_uid)); + return; + }; + + let Some(ent) = world.get_entity(entity_uid) else { + tracing::warn!("Cannot entity that doesn't exist"); + return; + }; + + // TODO: Submit all events with a single function call to reduce overhead + for comp_id in ent.component_ids() { + if comp_id.kind() == UidKind::Pair { + continue; + } + + world.event_submitter().submit_event( + &Pair::builder() + .relation::<Removed>() + .target_id(comp_id) + .build(), + entity_uid, + ); + } + + self.action_queue.push(Action::Despawn(entity_uid)); + } + + /// Queues up adding component(s) to a entity at the end of the current tick. + pub fn add_components<Comps>(&mut self, entity_uid: Uid, components: Comps) + where + Comps: ComponentSequence, + { + debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + if Comps::COUNT == 0 { + return; + } + + self.action_queue.push(Action::AddComponents( + entity_uid, + components.into_parts_array().into(), + )); + } + + /// Queues up removing component(s) from a entity at the end of the current tick. + #[tracing::instrument(skip(self, component_ids))] + pub fn remove_components( + &mut self, + entity_uid: Uid, + component_ids: impl IntoIterator<Item = Uid>, + ) + { + debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + let mut component_ids = component_ids.into_iter().peekable(); + + if component_ids.peek().is_none() { + return; + } + + let Some(world) = self.world else { + self.action_queue.push(Action::RemoveComponents( + entity_uid, + component_ids.collect(), + )); + return; + }; + + let Some(ent) = world.get_entity(entity_uid) else { + tracing::warn!("Cannot remove components from entity that doesn't exist"); + return; + }; + + let component_ids = component_ids + .filter(|comp_id| ent.has_component(*comp_id)) + .collect::<Vec<_>>(); + + if component_ids.is_empty() { + return; + } + + // TODO: Submit all events with a single function call to reduce overhead + for comp_id in &component_ids { + if comp_id.kind() == UidKind::Pair { + continue; + } + + world.event_submitter().submit_event( + &Pair::builder() + .relation::<Removed>() + .target_id(*comp_id) + .build(), + entity_uid, + ); + } + + self.action_queue + .push(Action::RemoveComponents(entity_uid, component_ids)); + } + + /// Queues up removing component(s) from a entity at the end of the current tick. + pub fn remove_comps<Ids: WithUidTuple>(&mut self, entity_uid: Uid) + { + self.remove_components(entity_uid, Ids::uids()); + } + + /// Stops the [`World`]. The world will finish the current tick and that tick will be + /// the last. + pub fn stop(&mut self) + { + self.action_queue.push(Action::Stop); + } +} + +impl<'world> SystemParam<'world> for Actions<'world> +{ + type Input = (); + + fn new(world: &'world World, _system_metadata: &SystemMetadata) -> Self + { + Self { + action_queue: &world.data.action_queue, + world: Some(world), + } + } +} + +/// A action for a [`System`] to perform. +#[derive(Debug)] +pub(crate) enum Action +{ + Spawn(Uid, Vec<ComponentParts>), + Despawn(Uid), + AddComponents(Uid, Vec<ComponentParts>), + RemoveComponents(Uid, Vec<Uid>), + Stop, +} diff --git a/engine-ecs/src/component.rs b/engine-ecs/src/component.rs new file mode 100644 index 0000000..17b279b --- /dev/null +++ b/engine-ecs/src/component.rs @@ -0,0 +1,324 @@ +use std::any::{type_name, Any}; +use std::fmt::Debug; +use std::ops::{Deref, DerefMut}; + +use seq_macro::seq; + +use crate::event::component::Changed; +use crate::event::Submitter as EventSubmitter; +use crate::lock::{ + Error as LockError, + MappedReadGuard, + MappedWriteGuard, + ReadGuard, + WriteGuard, +}; +use crate::pair::Pair; +use crate::system::Input as SystemInput; +use crate::uid::Uid; +use crate::util::Array; +use crate::{EntityComponentRef, World}; + +pub mod local; + +pub(crate) mod storage; + +pub trait Component: SystemInput + Any +{ + /// Returns the ID of this component. + fn id() -> Uid + where + Self: Sized; + + /// Returns the name of this component. + fn name(&self) -> &'static str; +} + +impl dyn Component +{ + pub fn downcast_mut<Real: 'static>(&mut self) -> Option<&mut Real> + { + (self as &mut dyn Any).downcast_mut() + } + + pub fn downcast_ref<Real: 'static>(&self) -> Option<&Real> + { + (self as &dyn Any).downcast_ref() + } + + pub fn is<Other: 'static>(&self) -> bool + { + (self as &dyn Any).is::<Other>() + } +} + +impl Debug for dyn Component +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + formatter.debug_struct("Component").finish_non_exhaustive() + } +} + +/// A sequence of components. +pub trait Sequence +{ + /// The number of components in this component sequence. + const COUNT: usize; + + type PartsArray: Array<Parts>; + + fn into_parts_array(self) -> Self::PartsArray; +} + +#[derive(Debug)] +pub struct Handle<'a, DataT: 'static> +{ + inner: MappedReadGuard<'a, DataT>, +} + +impl<'comp, DataT: 'static> Handle<'comp, DataT> +{ + /// Creates a new handle instance from a [`EntityComponentRef`]. + /// + /// # Errors + /// Will return `Err` if acquiring the component's lock fails. + pub fn from_entity_component_ref( + entity_component_ref: &EntityComponentRef<'comp>, + ) -> Result<Self, HandleError> + { + Self::new( + entity_component_ref + .component() + .read_nonblock() + .map_err(AcquireLockError)?, + ) + } + + fn new(inner: ReadGuard<'comp, Box<dyn Any>>) -> Result<Self, HandleError> + { + Ok(Self { + inner: ReadGuard::try_map(inner, |component| { + component.downcast_ref::<DataT>() + }) + .map_err(|_| HandleError::IncorrectType)?, + }) + } +} + +impl<DataT: 'static> Deref for Handle<'_, DataT> +{ + type Target = DataT; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +#[derive(Debug)] +pub struct HandleMut<'a, DataT: 'static> +{ + entity_component_ref: EntityComponentRef<'a>, + inner: MappedWriteGuard<'a, DataT>, + event_submitter: EventSubmitter<'a>, +} + +impl<'comp, DataT: 'static> HandleMut<'comp, DataT> +{ + /// Creates a new handle instance from a [`EntityComponentRef`]. + /// + /// # Errors + /// Will return `Err` if acquiring the component's lock fails. + pub fn from_entity_component_ref( + entity_component_ref: &EntityComponentRef<'comp>, + world: &'comp World, + ) -> Result<Self, HandleError> + { + let inner = entity_component_ref + .component() + .write_nonblock() + .map_err(AcquireLockError)?; + + Ok(Self { + entity_component_ref: entity_component_ref.clone(), + inner: WriteGuard::try_map(inner, |component| { + component.downcast_mut::<DataT>() + }) + .map_err(|_| HandleError::IncorrectType)?, + event_submitter: world.event_submitter(), + }) + } + + pub fn set_changed(&self) + { + self.event_submitter.submit_event( + &Pair::builder() + .relation::<Changed>() + .target_id(self.entity_component_ref.id()) + .build(), + self.entity_component_ref.entity_id(), + ); + } +} + +impl<DataT: 'static> Deref for HandleMut<'_, DataT> +{ + type Target = DataT; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +impl<DataT: 'static> DerefMut for HandleMut<'_, DataT> +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + &mut self.inner + } +} + +#[derive(Debug, thiserror::Error)] +pub enum HandleError +{ + #[error(transparent)] + AcquireLockFailed(#[from] AcquireLockError), + + #[error("Incorrect component type")] + IncorrectType, +} + +#[derive(Debug, thiserror::Error)] +#[error("Failed to acquire component lock")] +pub struct AcquireLockError(#[source] LockError); + +macro_rules! inner { + ($c: tt) => { + seq!(I in 0..=$c { + impl<#(IntoCompParts~I: IntoParts,)*> Sequence for (#(IntoCompParts~I,)*) + { + const COUNT: usize = $c + 1; + + type PartsArray = [Parts; $c + 1]; + + fn into_parts_array(self) -> Self::PartsArray + { + [#({ + self.I.into_parts() + },)*] + } + } + }); + }; +} + +seq!(C in 0..=16 { + inner!(C); +}); + +impl Sequence for () +{ + type PartsArray = [Parts; 0]; + + const COUNT: usize = 0; + + fn into_parts_array(self) -> Self::PartsArray + { + [] + } +} + +pub trait IntoParts +{ + fn into_parts(self) -> Parts; +} + +impl<ComponentT> IntoParts for ComponentT +where + ComponentT: Component, +{ + fn into_parts(self) -> Parts + { + Parts::builder() + .name(type_name::<Self>()) + .build(Self::id(), self) + } +} + +/// The parts of a component. +#[derive(Debug)] +#[non_exhaustive] +pub struct Parts +{ + id: Uid, + name: &'static str, + data: Box<dyn Any>, +} + +impl Parts +{ + #[must_use] + pub fn id(&self) -> Uid + { + self.id + } + + #[must_use] + pub fn name(&self) -> &'static str + { + self.name + } + + #[must_use] + pub fn builder() -> PartsBuilder + { + PartsBuilder::default() + } + + pub(crate) fn into_data(self) -> Box<dyn Any> + { + self.data + } +} + +#[derive(Debug)] +pub struct PartsBuilder +{ + name: &'static str, +} + +impl PartsBuilder +{ + #[must_use] + pub fn name(mut self, name: &'static str) -> Self + { + self.name = name; + self + } + + #[must_use] + pub fn build<Data: 'static>(self, id: Uid, data: Data) -> Parts + { + Parts { + id, + name: self.name, + data: Box::new(data), + } + } + + #[must_use] + pub fn build_with_any_data(self, id: Uid, data: Box<dyn Any>) -> Parts + { + Parts { id, name: self.name, data } + } +} + +impl Default for PartsBuilder +{ + fn default() -> Self + { + Self { name: "(unspecified)" } + } +} diff --git a/engine-ecs/src/component/local.rs b/engine-ecs/src/component/local.rs new file mode 100644 index 0000000..29afcee --- /dev/null +++ b/engine-ecs/src/component/local.rs @@ -0,0 +1,101 @@ +use std::any::type_name; +use std::ops::{Deref, DerefMut}; + +use crate::component::{ + HandleMut as ComponentHandleMut, + IntoParts as _, + Parts as ComponentParts, +}; +use crate::pair::Pair; +use crate::system::initializable::Param as InitializableParam; +use crate::system::{Metadata as SystemMetadata, Param as SystemParam}; +use crate::{Component, World}; + +/// Holds a component which is local to a single system. +#[derive(Debug)] +pub struct Local<'world, LocalComponent: Component> +{ + local_component: ComponentHandleMut<'world, LocalComponent>, +} + +impl<'world, LocalComponent> SystemParam<'world> for Local<'world, LocalComponent> +where + LocalComponent: Component, +{ + type Input = LocalComponent; + + fn new(world: &'world World, system_metadata: &SystemMetadata) -> Self + { + let Some(system_ent) = world.get_entity(system_metadata.ent_id) else { + panic!( + "System entity with ID {} does not exist", + system_metadata.ent_id + ); + }; + + let Some(local_component) = system_ent.get_with_id_mut::<LocalComponent>( + Pair::builder() + .relation::<IsLocalComponent>() + .target::<LocalComponent>() + .build() + .id(), + ) else { + panic!( + "Local component {} of system with ID {} is uninitialized", + type_name::<LocalComponent>(), + system_metadata.ent_id + ); + }; + + Self { local_component } + } +} + +impl<'world, LocalComponent, SystemT> InitializableParam<'world, SystemT> + for Local<'world, LocalComponent> +where + LocalComponent: Component, + SystemT: SystemWithLocalComponents, + Self: SystemParam<'world, Input = LocalComponent>, +{ + fn initialize(system: &mut SystemT, input: Self::Input) + { + system.add_local_component( + Pair::builder() + .relation::<IsLocalComponent>() + .target_as_data(input) + .build() + .into_parts(), + ); + } +} + +impl<LocalComponent> Deref for Local<'_, LocalComponent> +where + LocalComponent: Component, +{ + type Target = LocalComponent; + + fn deref(&self) -> &Self::Target + { + &self.local_component + } +} + +impl<LocalComponent> DerefMut for Local<'_, LocalComponent> +where + LocalComponent: Component, +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + &mut self.local_component + } +} + +pub trait SystemWithLocalComponents +{ + fn add_local_component(&mut self, component_parts: ComponentParts); +} + +#[derive(Component)] +struct IsLocalComponent; diff --git a/engine-ecs/src/component/storage.rs b/engine-ecs/src/component/storage.rs new file mode 100644 index 0000000..dc38b6a --- /dev/null +++ b/engine-ecs/src/component/storage.rs @@ -0,0 +1,795 @@ +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, + ¶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> +{ + 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()) + ); + } +} diff --git a/engine-ecs/src/component/storage/archetype.rs b/engine-ecs/src/component/storage/archetype.rs new file mode 100644 index 0000000..a7fe7ed --- /dev/null +++ b/engine-ecs/src/component/storage/archetype.rs @@ -0,0 +1,385 @@ +use std::any::Any; +use std::array::IntoIter as ArrayIntoIter; +use std::hash::{DefaultHasher, Hash, Hasher}; +use std::iter::{Enumerate, Filter, Map, RepeatN, Zip}; +use std::option::IntoIter as OptionIntoIter; +use std::slice::Iter as SliceIter; + +use hashbrown::HashMap; + +use crate::lock::Lock; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::{Either, HashMapExt}; + +#[derive(Debug)] +pub struct Archetype +{ + id: Id, + entities: Vec<Entity>, + entity_index_lookup: HashMap<Uid, usize>, + component_index_lookup: HashMap<Uid, usize>, + component_ids: Vec<Uid>, +} + +impl Archetype +{ + pub fn new(id: Id, component_ids: impl AsRef<[Uid]>) -> Self + { + Self { + id, + entities: Vec::new(), + entity_index_lookup: HashMap::new(), + component_index_lookup: component_ids + .as_ref() + .iter() + .enumerate() + .map(|(index, id)| (*id, index)) + .collect(), + component_ids: component_ids.as_ref().to_vec(), + } + } + + pub fn id(&self) -> Id + { + self.id + } + + pub fn is_superset(&self, other: &Self) -> bool + { + self.component_index_lookup + .keys_is_superset(&other.component_index_lookup) + } + + pub fn is_subset(&self, other: &Self) -> bool + { + self.component_index_lookup + .keys_is_subset(&other.component_index_lookup) + } + + pub fn get_entity_by_id(&self, entity_uid: Uid) -> Option<&Entity> + { + let index = *self.entity_index_lookup.get(&entity_uid)?; + + Some(self.entities.get(index).unwrap_or_else(|| { + panic!( + "In invalid state! Index of entity with ID {entity_uid:?} is out of bounds" + ); + })) + } + + pub fn push_entity(&mut self, entity: Entity) + { + self.entity_index_lookup + .insert(entity.uid, self.entities.len()); + + self.entities.push(entity); + } + + pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<Entity> + { + //debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + let entity_index = self.entity_index_lookup.remove(&entity_uid)?; + + if self.entities.len() == 1 { + return Some(self.entities.remove(entity_index)); + } + + let last_entity_uid = self + .entities + .last() + .expect(concat!( + "Invalid state. No entities in archetype but entry was ", + "removed successfully from entity index lookup" + )) + .uid; + + // By using swap_remove, no memory reallocation occurs and only one index in the + // entity lookup needs to be updated + let removed_entity = self.entities.swap_remove(entity_index); + + self.entity_index_lookup + .insert(last_entity_uid, entity_index); + + Some(removed_entity) + } + + pub fn entities(&self) -> EntityIter<'_> + { + EntityIter { iter: self.entities.iter() } + } + + pub fn entity_cnt(&self) -> usize + { + self.entities.len() + } + + pub fn component_cnt(&self) -> usize + { + self.component_index_lookup.len() + } + + pub fn get_matching_component_indices( + &self, + component_id: Uid, + ) -> MatchingComponentIter<'_> + { + assert!( + component_id.kind() == UidKind::Component + || component_id.kind() == UidKind::Pair + ); + + if component_id.kind() == UidKind::Pair + && component_id.target_component() == Uid::wildcard() + { + return MatchingComponentIter { + inner: Either::A( + self.component_ids + .iter() + .enumerate() + .zip(std::iter::repeat_n(component_id, self.component_ids.len())) + .filter( + (|((_, other_comp_id), component_id)| { + other_comp_id.kind() == UidKind::Pair + && other_comp_id.has_same_relation_as(*component_id) + }) + as MatchingComponentIterFilterFn, + ) + .map(|((index, other_comp_id), _)| (*other_comp_id, index)), + ), + }; + } + + MatchingComponentIter { + inner: Either::B( + [component_id] + .into_iter() + .zip(self.get_index_for_component(component_id)), + ), + } + } + + pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize> + { + assert!( + component_id.kind() == UidKind::Component + || (component_id.kind() == UidKind::Pair + && component_id.target_component() != Uid::wildcard()) + ); + + self.component_index_lookup.get(&component_id).copied() + } + + pub fn component_ids_unsorted(&self) -> impl Iterator<Item = Uid> + '_ + { + self.component_index_lookup.keys().copied() + } + + pub fn component_ids_sorted(&self) -> impl Iterator<Item = Uid> + '_ + { + self.component_ids.iter().copied() + } + + pub fn contains_matching_component(&self, component_id: Uid) -> bool + { + let component_id_kind = component_id.kind(); + + debug_assert!( + component_id_kind == UidKind::Component || component_id_kind == UidKind::Pair + ); + + if component_id.kind() == UidKind::Pair + && component_id.target_component() == Uid::wildcard() + { + return self.component_ids.iter().any(|other_comp_id| { + other_comp_id.kind() == UidKind::Pair + && other_comp_id.has_same_relation_as(component_id) + }); + } + + self.contains_component_with_exact_id(component_id) + } + + pub fn contains_component_with_exact_id(&self, component_id: Uid) -> bool + { + let component_id_kind = component_id.kind(); + + debug_assert!( + component_id_kind == UidKind::Component + || (component_id_kind == UidKind::Pair + && component_id.target_component() != Uid::wildcard()) + ); + + self.component_index_lookup.contains_key(&component_id) + } +} + +type MatchingComponentIterFilterFn = fn(&((usize, &Uid), Uid)) -> bool; + +type MatchingComponentIterMapFn = fn(((usize, &Uid), Uid)) -> (Uid, usize); + +type InnerMatchingComponentIterA<'archetype> = Map< + Filter< + Zip<Enumerate<SliceIter<'archetype, Uid>>, RepeatN<Uid>>, + MatchingComponentIterFilterFn, + >, + MatchingComponentIterMapFn, +>; + +type InnerMatchingComponentIterB = Zip<ArrayIntoIter<Uid, 1>, OptionIntoIter<usize>>; + +#[derive(Debug)] +pub struct MatchingComponentIter<'archetype> +{ + inner: Either<InnerMatchingComponentIterA<'archetype>, InnerMatchingComponentIterB>, +} + +impl Iterator for MatchingComponentIter<'_> +{ + type Item = (Uid, usize); + + fn next(&mut self) -> Option<Self::Item> + { + self.inner.next() + } +} + +#[derive(Debug)] +pub struct EntityIter<'archetype> +{ + iter: SliceIter<'archetype, Entity>, +} + +impl<'archetype> Iterator for EntityIter<'archetype> +{ + type Item = &'archetype Entity; + + fn next(&mut self) -> Option<Self::Item> + { + self.iter.next() + } +} + +#[derive(Debug)] +pub struct Entity +{ + uid: Uid, + components: Vec<EntityComponent>, +} + +impl Entity +{ + pub fn new(uid: Uid, components: impl IntoIterator<Item = EntityComponent>) -> Self + { + Self { + uid, + components: components.into_iter().collect(), + } + } + + pub fn uid(&self) -> Uid + { + self.uid + } + + pub fn components(&self) -> &[EntityComponent] + { + &self.components + } + + pub fn remove_component( + &mut self, + component_id: Uid, + archetype: &Archetype, + ) -> EntityComponent + { + let index = archetype + .get_index_for_component(component_id) + .expect("Archetype should contain component"); + + self.components.remove(index) + } + + pub fn insert_component( + &mut self, + component_id: Uid, + component: EntityComponent, + archetype: &Archetype, + ) + { + let index = archetype + .get_index_for_component(component_id) + .expect("Archetype should contain component"); + + self.components.insert(index, component); + } +} + +#[derive(Debug)] +pub struct EntityComponent +{ + component: Lock<Box<dyn Any>>, + name: &'static str, +} + +impl EntityComponent +{ + pub fn new(component: Box<dyn Any>, component_name: &'static str) -> Self + { + Self { + component: Lock::new(component, component_name), + name: component_name, + } + } + + pub fn component(&self) -> &Lock<Box<dyn Any>> + { + &self.component + } + + pub fn name(&self) -> &str + { + self.name + } +} + +/// Archetype ID. +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] +pub struct Id +{ + hash: u64, +} + +impl Id +{ + pub fn new_empty() -> Self + { + Self { hash: 0 } + } + + pub fn new<'a>(component_ids: impl IntoIterator<Item = &'a Uid>) -> Self + { + let mut hasher = DefaultHasher::new(); + + let mut prev_component_id: Option<Uid> = None; + + let mut component_id_iter = component_ids.into_iter().peekable(); + + if component_id_iter.peek().is_none() { + return Self::new_empty(); + } + + for comp_id in component_id_iter { + assert!( + prev_component_id.is_none_or(|prev_comp_id| *comp_id >= prev_comp_id), + "Cannot create archetype ID from a unsorted component metadata list" + ); + + prev_component_id = Some(*comp_id); + + comp_id.hash(&mut hasher); + } + + Self { hash: hasher.finish() } + } +} diff --git a/engine-ecs/src/component/storage/graph.rs b/engine-ecs/src/component/storage/graph.rs new file mode 100644 index 0000000..76200f9 --- /dev/null +++ b/engine-ecs/src/component/storage/graph.rs @@ -0,0 +1,432 @@ +use std::vec::IntoIter as VecIntoIter; + +use hashbrown::{HashMap, HashSet}; + +use crate::component::storage::archetype::{Archetype, Id as ArchetypeId}; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::{BorrowedOrOwned, StreamingIterator}; + +#[derive(Debug, Default)] +pub struct Graph +{ + nodes: Vec<ArchetypeNode>, + archetype_index_lookup: HashMap<ArchetypeId, usize>, +} + +impl Graph +{ + pub fn create_node(&mut self, id: ArchetypeId, component_ids: &impl AsRef<[Uid]>) + { + debug_assert!(!self.contains_archetype(id)); + + let _ = self.get_or_create_node(id, component_ids); + } + + pub fn get_or_create_node( + &mut self, + id: ArchetypeId, + component_ids: &impl AsRef<[Uid]>, + ) -> &mut ArchetypeNode + { + let exists_before = self.archetype_index_lookup.contains_key(&id); + + let index = *self.archetype_index_lookup.entry(id).or_insert_with(|| { + self.nodes.push(ArchetypeNode { + archetype: Archetype::new(id, component_ids.as_ref()), + edges: HashMap::new(), + }); + + self.nodes.len() - 1 + }); + + if !exists_before { + self.create_missing_edges(id); + } + + self.nodes + .get_mut(index) + .expect("Archetype index from lookup is out of bounds") + } + + pub fn contains_archetype(&self, id: ArchetypeId) -> bool + { + self.archetype_index_lookup.contains_key(&id) + } + + pub fn get_node_by_id(&self, id: ArchetypeId) -> Option<&ArchetypeNode> + { + let index = self.archetype_index_lookup.get(&id)?; + + Some(self.nodes.get(*index).unwrap_or_else(|| { + panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") + })) + } + + pub fn get_node_by_id_mut(&mut self, id: ArchetypeId) -> Option<&mut ArchetypeNode> + { + let index = self.archetype_index_lookup.get(&id)?; + + Some(self.nodes.get_mut(*index).unwrap_or_else(|| { + panic!("In invalid state! Index of archetype with ID {id:?} is out of bounds") + })) + } + + #[cfg(feature = "vizoxide")] + pub fn iter_nodes(&self) -> impl Iterator<Item = &ArchetypeNode> + { + self.nodes.iter() + } + + pub fn dfs_archetype_add_edges( + &self, + archetype_id: ArchetypeId, + ) -> Option<ArchetypeAddEdgeDfsIter<'_>> + { + let node = self.get_node_by_id(archetype_id)?; + + Some(ArchetypeAddEdgeDfsIter { + graph: self, + stack: vec![( + BorrowedOrOwned::Borrowned(node.archetype()), + node.edges + .iter() + .map(|(comp_id, edges)| (*comp_id, edges.clone())) + .collect::<Vec<_>>() + .into_iter(), + )], + visited: HashSet::new(), + }) + } + + fn create_missing_edges(&mut self, archetype_id: ArchetypeId) + { + let archetype_node_index = *self + .archetype_index_lookup + .get(&archetype_id) + .expect("Archetype should exist"); + + let (nodes_before, nodes_rest) = self.nodes.split_at_mut(archetype_node_index); + + let ([archetype_node], nodes_after) = nodes_rest.split_at_mut(1) else { + unreachable!(); + }; + + for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut()) + { + if archetype_node.archetype().component_cnt() + > other_archetype_node.archetype().component_cnt() + && other_archetype_node + .archetype() + .is_subset(archetype_node.archetype()) + { + Self::create_missing_subset_node_edges( + archetype_node, + other_archetype_node, + ); + + continue; + } + + if other_archetype_node + .archetype() + .is_superset(archetype_node.archetype()) + { + Self::create_missing_superset_node_edges( + archetype_node, + other_archetype_node, + ); + } + } + } + + fn create_missing_subset_node_edges( + target_node: &mut ArchetypeNode, + subset_node: &mut ArchetypeNode, + ) + { + let uniq_comp_id = target_node + .archetype() + .component_ids_sorted() + .find(|id| { + !subset_node + .archetype() + .contains_component_with_exact_id(*id) + }) + .unwrap(); + + subset_node + .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default) + .add = Some(subset_node.make_add_edge(uniq_comp_id).0); + + if target_node.archetype().component_cnt() + == subset_node.archetype().component_cnt() + 1 + { + target_node + .get_or_insert_edges(uniq_comp_id, ArchetypeEdges::default) + .remove = Some(subset_node.archetype().id()); + } + } + + fn create_missing_superset_node_edges( + target_node: &mut ArchetypeNode, + superset_node: &mut ArchetypeNode, + ) + { + if superset_node.archetype().component_cnt() + > target_node.archetype().component_cnt() + 1 + { + let first_unique_comp_id = superset_node + .archetype() + .component_ids_sorted() + .find(|other_archetype_comp_id| { + !target_node + .archetype() + .contains_component_with_exact_id(*other_archetype_comp_id) + }) + .or_else(|| { + if target_node.archetype().component_cnt() != 0 { + return None; + } + + superset_node.archetype().component_ids_sorted().next() + }) + .expect("Not possible"); + + target_node + .get_or_insert_edges(first_unique_comp_id, ArchetypeEdges::default) + .add = Some(target_node.make_add_edge(first_unique_comp_id).0); + + return; + } + + if superset_node.archetype().component_cnt() + != target_node.archetype().component_cnt() + 1 + { + return; + } + + let extra_comp_id = superset_node + .archetype() + .component_ids_unsorted() + .find(|comp_id| { + !target_node + .archetype() + .contains_component_with_exact_id(*comp_id) + }) + .expect("Archetype should contain one extra component ID"); + + superset_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .remove = Some(target_node.archetype().id()); + + target_node + .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default) + .add = Some(superset_node.archetype().id()); + } +} + +#[derive(Debug)] +pub struct ArchetypeNode +{ + archetype: Archetype, + edges: HashMap<Uid, ArchetypeEdges>, +} + +impl ArchetypeNode +{ + pub fn archetype(&self) -> &Archetype + { + &self.archetype + } + + pub fn archetype_mut(&mut self) -> &mut Archetype + { + &mut self.archetype + } + + pub fn get_or_insert_edges( + &mut self, + component_id: Uid, + insert_fn: impl FnOnce() -> ArchetypeEdges, + ) -> &mut ArchetypeEdges + { + debug_assert!(matches!( + component_id.kind(), + UidKind::Component | UidKind::Pair + )); + + self.edges.entry(component_id).or_insert_with(insert_fn) + } + + #[cfg(feature = "vizoxide")] + pub fn iter_edges(&self) -> impl Iterator<Item = (&Uid, &ArchetypeEdges)> + { + self.edges.iter() + } + + pub fn make_add_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) + { + let mut edge_comp_ids = self + .archetype() + .component_ids_unsorted() + .chain([component_id]) + .collect::<Vec<_>>(); + + edge_comp_ids.sort(); + + let add_edge_id = ArchetypeId::new(&edge_comp_ids); + + (add_edge_id, edge_comp_ids) + } + + pub fn make_remove_edge(&self, component_id: Uid) -> (ArchetypeId, Vec<Uid>) + { + let mut edge_comp_ids = self + .archetype() + .component_ids_unsorted() + .filter(|id| *id != component_id) + .collect::<Vec<_>>(); + + edge_comp_ids.sort(); + + let remove_edge_id = ArchetypeId::new(&edge_comp_ids); + + (remove_edge_id, edge_comp_ids) + } +} + +#[derive(Debug, Default, Clone)] +pub struct ArchetypeEdges +{ + pub add: Option<ArchetypeId>, + pub remove: Option<ArchetypeId>, +} + +type ArchetypeAddEdgeDfsIterStackElem<'graph> = ( + BorrowedOrOwned<'graph, Archetype>, + VecIntoIter<(Uid, ArchetypeEdges)>, +); + +#[derive(Debug)] +pub struct ArchetypeAddEdgeDfsIter<'graph> +{ + graph: &'graph Graph, + stack: Vec<ArchetypeAddEdgeDfsIterStackElem<'graph>>, + visited: HashSet<ArchetypeId>, +} + +impl<'graph> ArchetypeAddEdgeDfsIter<'graph> +{ + pub fn new(graph: &'graph Graph, start_nodes: &[ArchetypeId]) -> Self + { + Self { + graph, + stack: start_nodes + .iter() + .map(|start_node_id| { + let start_node = graph + .get_node_by_id(*start_node_id) + .expect("Start node does not exist"); + + ( + BorrowedOrOwned::Borrowned(start_node.archetype()), + start_node + .edges + .iter() + .map(|(comp_id, edges)| (*comp_id, edges.clone())) + .collect::<Vec<_>>() + .into_iter(), + ) + }) + .collect(), + visited: start_nodes.iter().copied().collect::<HashSet<_>>(), + } + } + + pub fn push( + &mut self, + item: ( + BorrowedOrOwned<'graph, Archetype>, + VecIntoIter<(Uid, ArchetypeEdges)>, + ), + ) + { + self.stack.push(item); + } + + pub fn pop(&mut self) + { + self.stack.pop(); + } +} + +impl<'graph> StreamingIterator for ArchetypeAddEdgeDfsIter<'graph> +{ + type Item<'a> + = ArchetypeAddEdgeDfsIterResult<'graph, 'a> + where + Self: 'a; + + fn streaming_next(&mut self) -> Option<Self::Item<'_>> + { + let (_, edges_iter) = self.stack.last_mut()?; + + let Some((component_id, edges)) = edges_iter.next() else { + self.stack.pop(); + + return Some(ArchetypeAddEdgeDfsIterResult::NoEdgesLeftForArchetype); + }; + + let Some(add_edge) = edges.add else { + return Some(ArchetypeAddEdgeDfsIterResult::NoAddEdge); + }; + + if self.visited.contains(&add_edge) { + return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeAlreadyVisited); + } + + self.visited.insert(add_edge); + + let Some(add_edge_archetype) = self.graph.get_node_by_id(add_edge) else { + return Some(ArchetypeAddEdgeDfsIterResult::AddEdgeArchetypeNotFound { + archetype: &self.stack.last().unwrap().0, + add_edge_archetype_id: add_edge, + add_edge_component_id: component_id, + }); + }; + + self.stack.push(( + BorrowedOrOwned::Borrowned(add_edge_archetype.archetype()), + add_edge_archetype + .edges + .iter() + .map(|(comp_id, edges)| (*comp_id, edges.clone())) + .collect::<Vec<_>>() + .into_iter(), + )); + + Some(ArchetypeAddEdgeDfsIterResult::AddEdge { + add_edge_archetype_id: add_edge, + add_edge_component_id: component_id, + }) + } +} + +#[derive(Debug)] +pub enum ArchetypeAddEdgeDfsIterResult<'graph, 'iter> +{ + AddEdge + { + add_edge_archetype_id: ArchetypeId, + add_edge_component_id: Uid, + }, + NoEdgesLeftForArchetype, + NoAddEdge, + AddEdgeAlreadyVisited, + AddEdgeArchetypeNotFound + { + archetype: &'iter BorrowedOrOwned<'graph, Archetype>, + add_edge_archetype_id: ArchetypeId, + add_edge_component_id: Uid, + }, +} diff --git a/engine-ecs/src/entity.rs b/engine-ecs/src/entity.rs new file mode 100644 index 0000000..ad9f179 --- /dev/null +++ b/engine-ecs/src/entity.rs @@ -0,0 +1,295 @@ +use std::any::type_name; +use std::ops::Deref; +use std::sync::LazyLock; + +use crate::component::storage::archetype::{ + Archetype, + Entity as ArchetypeEntity, + MatchingComponentIter as ArchetypeMatchingComponentIter, +}; +use crate::component::{ + Component, + Handle as ComponentHandle, + HandleMut as ComponentHandleMut, +}; +use crate::pair::{ + ComponentOrWildcard, + MultipleWithWildcard as PairMultipleWithWildcard, + Pair, + WithWildcard as PairWithWildcard, +}; +use crate::uid::{Kind as UidKind, Uid}; +use crate::{EntityComponentRef, World}; + +pub mod obtainer; + +/// A handle to a entity. +#[derive(Debug, Clone)] +pub struct Handle<'a> +{ + archetype: &'a Archetype, + entity: &'a ArchetypeEntity, + world: &'a World, +} + +impl<'a> Handle<'a> +{ + /// Returns the [`Uid`] of this entity. + #[inline] + #[must_use] + pub fn uid(&self) -> Uid + { + self.entity.uid() + } + + /// Returns a reference to the specified component in this entity. `None` is + /// returned if the component isn't found in the entity. + /// + /// # Panics + /// Will panic if: + /// - The component's ID is not a component ID + /// - The component is mutably borrowed elsewhere + #[must_use] + pub fn get<ComponentT: Component>(&self) -> Option<ComponentHandle<'a, ComponentT>> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let component = self.get_matching_components(ComponentT::id()).next()?; + + Some( + ComponentHandle::from_entity_component_ref(&component).unwrap_or_else( + |err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }, + ), + ) + } + + /// Returns a mutable reference to the specified component in this entity. `None` is + /// returned if the component isn't found in the entity. + /// + /// # Panics + /// Will panic if: + /// - The component's ID is not a component ID + /// - The component is borrowed elsewhere + #[must_use] + pub fn get_mut<ComponentT: Component>( + &self, + ) -> Option<ComponentHandleMut<'a, ComponentT>> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let component = self.get_matching_components(ComponentT::id()).next()?; + + Some( + ComponentHandleMut::from_entity_component_ref(&component, self.world) + .unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }), + ) + } + + /// Returns a reference to the component with the ID `id` in this entity. + /// `None` is returned if the component isn't found. + /// + /// # Panics + /// Will panic if: + /// - The ID is not a component/pair ID + /// - The component is borrowed mutably elsewhere + /// - The component type is incorrect + #[must_use] + pub fn get_with_id<ComponentDataT: 'static>( + &self, + id: Uid, + ) -> Option<ComponentHandle<'a, ComponentDataT>> + { + assert!( + matches!(id.kind(), UidKind::Component | UidKind::Pair), + "ID {id:?} is not a component/pair ID" + ); + + let component = self.get_matching_components(id).next()?; + + Some( + ComponentHandle::from_entity_component_ref(&component).unwrap_or_else( + |err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentDataT>() + ); + }, + ), + ) + } + + /// Returns a mutable reference to the component with the ID `id` in this entity. + /// `None` is returned if the component isn't found. + /// + /// # Panics + /// Will panic if: + /// - The ID is not a component/pair ID + /// - The component is borrowed elsewhere + /// - The component type is incorrect + #[must_use] + pub fn get_with_id_mut<ComponentDataT: 'static>( + &self, + id: Uid, + ) -> Option<ComponentHandleMut<'a, ComponentDataT>> + { + assert!( + matches!(id.kind(), UidKind::Component | UidKind::Pair), + "ID {id:?} is not a component/pair ID" + ); + + let component = self.get_matching_components(id).next()?; + + Some( + ComponentHandleMut::from_entity_component_ref(&component, self.world) + .unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentDataT>() + ); + }), + ) + } + + #[must_use] + pub fn get_first_wildcard_pair_match<Relation, Target>( + &self, + ) -> Option<PairWithWildcard<'a, Relation, Target>> + where + Relation: ComponentOrWildcard, + Target: ComponentOrWildcard, + { + let mut matching_comps = self.get_matching_components( + Pair::builder() + .relation_id(Relation::uid()) + .target_id(Target::uid()) + .build() + .id(), + ); + + Some(PairWithWildcard::new(self.world, matching_comps.next()?)) + } + + #[must_use] + pub fn get_wildcard_pair_matches<Relation, Target>( + &self, + ) -> PairMultipleWithWildcard<'a, Relation, Target> + where + Relation: ComponentOrWildcard, + Target: ComponentOrWildcard, + { + PairMultipleWithWildcard::new(self.world, self.clone()) + } + + #[inline] + #[must_use] + pub fn get_matching_components(&self, component_uid: Uid) + -> MatchingComponentIter<'a> + { + MatchingComponentIter { + inner: self.archetype.get_matching_component_indices(component_uid), + entity: self.entity, + } + } + + /// Returns whether or not this entity contains a component with the specified `Uid`. + #[must_use] + pub fn has_component(&self, component_uid: Uid) -> bool + { + self.archetype + .contains_component_with_exact_id(component_uid) + } + + /// Returns the `Uids`s of the components this entity has. + pub fn component_ids(&self) -> impl Iterator<Item = Uid> + '_ + { + self.archetype.component_ids_sorted() + } + + pub(crate) fn new( + archetype: &'a Archetype, + entity: &'a ArchetypeEntity, + world: &'a World, + ) -> Self + { + Self { archetype, entity, world } + } +} + +#[derive(Debug)] +pub struct MatchingComponentIter<'a> +{ + inner: ArchetypeMatchingComponentIter<'a>, + entity: &'a ArchetypeEntity, +} + +impl<'a> Iterator for MatchingComponentIter<'a> +{ + type Item = EntityComponentRef<'a>; + + fn next(&mut self) -> Option<Self::Item> + { + let (matching_component_id, index) = self.inner.next()?; + + Some(EntityComponentRef::new( + matching_component_id, + self.entity.components().get(index).unwrap(), + self.entity.uid(), + )) + } +} + +/// The data type of a declaration of a entity. +#[derive(Debug)] +pub struct Declaration +{ + uid: LazyLock<Uid>, + create_func: fn(&mut World), +} + +impl Declaration +{ + pub(crate) fn create(&self, world: &mut World) + { + (self.create_func)(world); + } + + #[doc(hidden)] + pub const fn new(create_func: fn(&mut World)) -> Self + { + Self { + uid: LazyLock::new(|| Uid::new_unique(UidKind::Entity)), + create_func, + } + } +} + +impl Deref for Declaration +{ + type Target = Uid; + + fn deref(&self) -> &Self::Target + { + &self.uid + } +} + +#[allow(clippy::module_name_repetitions)] +#[macro_export] +macro_rules! declare_entity { + ($visibility: vis $ident: ident, $components: expr) => { + $visibility static $ident: $crate::entity::Declaration = + $crate::entity::Declaration::new(|world| { + world.create_entity_with_uid(*$ident, $components); + }); + } +} diff --git a/engine-ecs/src/entity/obtainer.rs b/engine-ecs/src/entity/obtainer.rs new file mode 100644 index 0000000..6c2ea96 --- /dev/null +++ b/engine-ecs/src/entity/obtainer.rs @@ -0,0 +1,29 @@ +use crate::entity::Handle as EntityHandle; +use crate::system::{Metadata as SystemMetadata, Param as SystemParam}; +use crate::uid::Uid; +use crate::World; + +#[derive(Debug)] +pub struct Obtainer<'world> +{ + world: &'world World, +} + +impl<'world> SystemParam<'world> for Obtainer<'world> +{ + type Input = (); + + fn new(world: &'world World, _system_metadata: &SystemMetadata) -> Self + { + Self { world } + } +} + +impl Obtainer<'_> +{ + #[must_use] + pub fn get_entity(&self, entity_id: Uid) -> Option<EntityHandle<'_>> + { + self.world.get_entity(entity_id) + } +} diff --git a/engine-ecs/src/error.rs b/engine-ecs/src/error.rs new file mode 100644 index 0000000..185b706 --- /dev/null +++ b/engine-ecs/src/error.rs @@ -0,0 +1,270 @@ +use std::fmt::{Debug, Display, Write as _}; + +use backtrace::Backtrace; + +#[macro_export] +macro_rules! error { + ($lit: literal) => { + $crate::error::Error::from($lit) + }; + + ($lit: literal, $($tt: tt)*) => { + $crate::error::Error::from(std::format!($lit, $($tt)*)) + }; + + ($err: expr) => { + $crate::error::Error::from($err) + }; +} + +pub struct Error +{ + inner: Box<dyn std::error::Error + Send + Sync>, + backtrace: Backtrace, +} + +impl Error +{ + pub fn resolve_backtrace(&mut self) + { + self.backtrace.resolve(); + } + + fn is_backtrace_resolved(&self) -> bool + { + let Some(first_frame) = self.backtrace.frames().first() else { + return false; + }; + + !first_frame.symbols().is_empty() + } +} + +impl Debug for Error +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + let error = &*self.inner; + + write!(formatter, "{error}")?; + + if let Some(cause) = error.source() { + write!(formatter, "\n\nCaused by:")?; + let multiple = cause.source().is_some(); + for (n, error) in anyhow::Chain::new(cause).enumerate() { + writeln!(formatter)?; + + let mut indented = Indented { + inner: formatter, + number: if multiple { Some(n) } else { None }, + started: false, + }; + write!(indented, "{error}")?; + } + } + + if std::env::var_os("ENGINE_ECS_BACKTRACE") + .is_none_or(|backtrace_enabled| backtrace_enabled != "1") + { + write!( + formatter, + concat!( + "\n\nnote: run with `ENGINE_ECS_BACKTRACE=1` environment variable ", + "to display a engine backtrace" + ) + )?; + + return Ok(()); + } + + let mut cloned_backtrace; + + let backtrace = if self.is_backtrace_resolved() { + &self.backtrace + } else { + cloned_backtrace = self.backtrace.clone(); + cloned_backtrace.resolve(); + &cloned_backtrace + }; + + write!( + formatter, + "\n\nStack backtrace:\n{:?}", + std::fmt::from_fn(|backtrace_formatter| fmt_backtrace( + backtrace, + backtrace_formatter + )) + )?; + + Ok(()) + } +} + +impl Display for Error +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + let error = &*self.inner; + + write!(formatter, "{error}")?; + + if formatter.alternate() { + let chain = anyhow::Chain::new(error); + for cause in chain.skip(1) { + write!(formatter, ": {}", cause)?; + } + } + + Ok(()) + } +} + +impl<Err: Send + Sync + 'static> From<Err> for Error +where + Box<dyn std::error::Error + Send + Sync>: From<Err>, +{ + fn from(err: Err) -> Self + { + Self { + inner: err.into(), + backtrace: Backtrace::new_unresolved(), + } + } +} + +pub type ErrorHandler = fn(Error, Metadata); + +/// Error metadata. +#[derive(Debug)] +pub struct Metadata +{ + pub source_name: &'static str, + pub source_kind: SourceKind, +} + +/// Error source kind. +#[derive(Debug)] +#[non_exhaustive] +pub enum SourceKind +{ + System, + Observer, +} + +impl Display for SourceKind +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + match self { + SourceKind::System => formatter.write_str("system"), + SourceKind::Observer => formatter.write_str("observer"), + } + } +} + +pub fn err_handler_panic(mut err: Error, err_metadata: Metadata) +{ + err.resolve_backtrace(); + + panic!( + "Error occurred in {} '{}': {err:?}", + err_metadata.source_kind, err_metadata.source_name + ); +} + +pub fn err_handler_log_error(err: Error, err_metadata: Metadata) +{ + tracing::error!( + "Error occurred in {} '{}': {err:#}", + err_metadata.source_kind, + err_metadata.source_name + ); +} + +fn fmt_backtrace( + backtrace: &Backtrace, + fmt: &mut std::fmt::Formatter<'_>, +) -> std::fmt::Result +{ + let style = if fmt.alternate() { + backtrace::PrintFmt::Full + } else { + backtrace::PrintFmt::Short + }; + + // When printing paths we try to strip the cwd if it exists, otherwise + // we just print the path as-is. Note that we also only do this for the + // short format, because if it's full we presumably want to print + // everything. + let cwd = std::env::current_dir(); + let mut print_path = + move |fmt: &mut std::fmt::Formatter<'_>, + path: backtrace::BytesOrWideString<'_>| { + let path = path.into_path_buf(); + if style != backtrace::PrintFmt::Full { + if let Ok(cwd) = &cwd { + if let Ok(suffix) = path.strip_prefix(cwd) { + return std::fmt::Display::fmt(&suffix.display(), fmt); + } + } + } + std::fmt::Display::fmt(&path.display(), fmt) + }; + + let mut f = backtrace::BacktraceFmt::new(fmt, style, &mut print_path); + + f.add_context()?; + + for frame in backtrace.frames() { + if frame.symbols().iter().all(|symbol| { + symbol.name().is_some_and(|symbol_name| { + let symbol_name = symbol_name.to_string(); + + symbol_name + .contains("<ecs::error::Error as core::convert::From<Err>>::from") + }) + }) { + continue; + } + + f.frame().backtrace_frame(frame)?; + } + f.finish()?; + Ok(()) +} + +struct Indented<'a, D> +{ + inner: &'a mut D, + number: Option<usize>, + started: bool, +} + +impl<T> std::fmt::Write for Indented<'_, T> +where + T: std::fmt::Write, +{ + fn write_str(&mut self, s: &str) -> std::fmt::Result + { + for (i, line) in s.split('\n').enumerate() { + if !self.started { + self.started = true; + match self.number { + Some(number) => write!(self.inner, "{: >5}: ", number)?, + None => self.inner.write_str(" ")?, + } + } else if i > 0 { + self.inner.write_char('\n')?; + if self.number.is_some() { + self.inner.write_str(" ")?; + } else { + self.inner.write_str(" ")?; + } + } + + self.inner.write_str(line)?; + } + + Ok(()) + } +} diff --git a/engine-ecs/src/event.rs b/engine-ecs/src/event.rs new file mode 100644 index 0000000..15455b6 --- /dev/null +++ b/engine-ecs/src/event.rs @@ -0,0 +1,105 @@ +use crate::lock::Lock; +use crate::pair::Pair; +use crate::uid::{Kind as UidKind, Uid}; +use crate::util::VecExt; + +pub mod component; + +#[derive(Debug, Clone)] +#[non_exhaustive] +pub struct Emitted<'a> +{ + pub event: Uid, + pub match_ids: &'a [Uid], +} + +#[derive(Debug)] +pub struct Submitter<'world> +{ + new_events: &'world Lock<NewEvents>, +} + +impl<'world> Submitter<'world> +{ + /// Submits a event to be handled later. + /// + /// # Panics + /// Will panic if unable to acquire a read-write lock to the event store. + pub fn submit_event(&self, event: &Pair<Uid, Uid>, match_id: Uid) + { + let mut new_events_lock = self + .new_events + .write_nonblock() + .expect("Failed to acquire read-write lock to new events"); + + new_events_lock.push_event_match(event, match_id); + } + + pub(crate) fn new(new_events: &'world Lock<NewEvents>) -> Self + { + Self { new_events } + } +} + +#[derive(Debug, Default)] +pub(crate) struct NewEvents +{ + events: Vec<(Uid, Matches)>, +} + +impl NewEvents +{ + pub fn push_event_match(&mut self, event: &Pair<Uid, Uid>, match_id: Uid) + { + let event_id = event.id(); + + assert_eq!(event_id.kind(), UidKind::Pair); + + if let Ok(event_index) = self + .events + .binary_search_by_key(&event_id, |(other_event_id, _)| *other_event_id) + { + let Some((_, matches)) = self.events.get_mut(event_index) else { + unreachable!(); + }; + + matches.sorted_push(match_id); + + return; + } + + self.events.insert_at_part_pt_by_key( + (event_id, Matches { match_ids: Vec::from([match_id]) }), + |(other_event_id, _)| other_event_id, + ); + } + + pub fn take(&mut self) -> Vec<(Uid, Matches)> + { + std::mem::take(&mut self.events) + } + + pub fn is_empty(&self) -> bool + { + self.events.is_empty() + } +} + +#[derive(Debug)] +pub(crate) struct Matches +{ + pub match_ids: Vec<Uid>, +} + +impl Matches +{ + fn sorted_push(&mut self, match_id: Uid) + { + if self.match_ids.binary_search(&match_id).is_ok() { + return; + } + + self.match_ids + .insert_at_part_pt_by_key(match_id, |other_match_id| other_match_id); + } +} diff --git a/engine-ecs/src/event/component.rs b/engine-ecs/src/event/component.rs new file mode 100644 index 0000000..70ea3e5 --- /dev/null +++ b/engine-ecs/src/event/component.rs @@ -0,0 +1,103 @@ +//! Component events. + +use std::convert::Infallible; + +use crate::Component; +use crate::component::{Handle as ComponentHandle, HandleMut as ComponentHandleMut}; +use crate::entity::Handle as EntityHandle; +use crate::pair::Pair; +use crate::system::observer::{EventMatch, Observed}; + +/// Implemented by the relations of component event pairs +pub trait EventRelation: Component {} + +/// Pair relation for events emitted when: +/// a) A entity with the target component is spawned. +/// b) The target component is added to a entity. +#[derive(Debug, Component)] +pub struct Added(Infallible); + +impl EventRelation for Added {} + +/// Pair relation for events emitted **before**: +/// a) The target component is removed from a entity. +/// b) A entity with the target component is despawned. +#[derive(Debug, Component)] +pub struct Removed(Infallible); + +impl EventRelation for Removed {} + +#[derive(Debug, Component)] +pub struct Changed(Infallible); + +impl EventRelation for Changed {} + +/// [`EventMatch`] extension trait for component event matches. +pub trait EventMatchExt<Target>: sealed::Sealed +{ + #[must_use] + fn get_entity(&self) -> EntityHandle<'_>; + + #[must_use] + fn get_ent_target_comp(&self) -> ComponentHandle<'_, Target> + where + Target: Component; + + #[must_use] + fn get_ent_target_comp_mut(&self) -> ComponentHandleMut<'_, Target> + where + Target: Component; +} + +impl<ComponentEventRelation: EventRelation, Target> EventMatchExt<Target> + for EventMatch<'_, Pair<ComponentEventRelation, Target>> +where + Pair<ComponentEventRelation, Target>: Observed, +{ + fn get_entity(&self) -> EntityHandle<'_> + { + let Some(ent) = self.try_get_entity() else { + unreachable!(); + }; + + ent + } + + fn get_ent_target_comp(&self) -> ComponentHandle<'_, Target> + where + Target: Component, + { + let ent = self.get_entity(); + + let Some(comp) = ent.get::<Target>() else { + unreachable!(); + }; + + comp + } + + fn get_ent_target_comp_mut(&self) -> ComponentHandleMut<'_, Target> + where + Target: Component, + { + let ent = self.get_entity(); + + let Some(comp) = ent.get_mut::<Target>() else { + unreachable!(); + }; + + comp + } +} + +impl<ComponentEventRelation: EventRelation, Target> sealed::Sealed + for EventMatch<'_, Pair<ComponentEventRelation, Target>> +where + Pair<ComponentEventRelation, Target>: Observed, +{ +} + +mod sealed +{ + pub trait Sealed {} +} diff --git a/engine-ecs/src/extension.rs b/engine-ecs/src/extension.rs new file mode 100644 index 0000000..9c6614b --- /dev/null +++ b/engine-ecs/src/extension.rs @@ -0,0 +1,72 @@ +use crate::component::Sequence as ComponentSequence; +use crate::entity::Declaration as EntityDeclaration; +use crate::sole::Sole; +use crate::system::observer::Observer; +use crate::system::System; +use crate::uid::Uid; +use crate::{SoleAlreadyExistsError, World}; + +/// A collection of systems, entities & soles that can be added to a [`World`]. +pub trait Extension +{ + fn collect(self, collector: Collector<'_>); +} + +/// Passed to a [`Extension`] to collects it's systems, entities & soles. +pub struct Collector<'world> +{ + world: &'world mut World, +} + +impl<'world> Collector<'world> +{ + /// Returns a new `Collector` for the given [`World`]. + pub fn new(world: &'world mut World) -> Self + { + Self { world } + } + + /// Adds a system to the [`World`]. + pub fn add_system<'this, SystemImpl>( + &'this mut self, + phase_euid: Uid, + system: impl System<'this, SystemImpl>, + ) + { + self.world.register_system(phase_euid, system); + } + + /// Adds a observer system to the [`World`]. + pub fn add_observer<'this, SystemImpl>( + &'this mut self, + observer: impl Observer<'this, SystemImpl>, + ) + { + self.world.register_observer(observer); + } + + /// Adds a entity to the [`World`]. + pub fn add_entity<Comps>(&mut self, components: Comps) + where + Comps: ComponentSequence, + { + self.world.create_entity(components); + } + + /// Adds a declared entity to the [`World`]. + pub fn add_declared_entity(&mut self, entity_decl: &EntityDeclaration) + { + self.world.create_declared_entity(entity_decl); + } + + /// Adds a globally shared singleton value to the [`World`]. + /// + /// # Errors + /// Returns `Err` if this [`Sole`] has already been added. + pub fn add_sole<SoleT>(&mut self, sole: SoleT) -> Result<(), SoleAlreadyExistsError> + where + SoleT: Sole, + { + self.world.add_sole(sole) + } +} diff --git a/engine-ecs/src/lib.rs b/engine-ecs/src/lib.rs new file mode 100644 index 0000000..6450587 --- /dev/null +++ b/engine-ecs/src/lib.rs @@ -0,0 +1,773 @@ +#![deny(clippy::all, clippy::pedantic)] + +use std::any::{Any, TypeId, type_name}; +use std::fmt::Debug; +use std::hint::cold_path; +use std::mem::ManuallyDrop; +use std::rc::Rc; +use std::sync::Arc; +use std::sync::atomic::{AtomicBool, Ordering}; + +use hashbrown::HashMap; + +use crate::actions::Action; +use crate::component::storage::archetype::EntityComponent as ArchetypeEntityComponent; +use crate::component::storage::{EntityAlreadyExistsError, Storage as ComponentStorage}; +use crate::component::{ + Component, + IntoParts as IntoComponentParts, + Parts as ComponentParts, + Sequence as ComponentSequence, +}; +use crate::entity::{Declaration as EntityDeclaration, Handle as EntityHandle}; +use crate::error::{ + ErrorHandler, + Metadata as ErrorMetadata, + SourceKind as ErrorSourceKind, + err_handler_panic, +}; +use crate::event::component::Added; +use crate::event::{Emitted as EmittedEvent, NewEvents, Submitter as EventSubmitter}; +use crate::extension::{Collector as ExtensionCollector, Extension}; +use crate::lock::Lock; +use crate::pair::{ChildOf, Pair, Wildcard}; +use crate::phase::{ + HasSystem as PhaseHasSystem, + POST_UPDATE as POST_UPDATE_PHASE, + PRE_UPDATE as PRE_UPDATE_PHASE, + Phase, + START as START_PHASE, + UPDATE as UPDATE_PHASE, +}; +use crate::query::flexible::Query as FlexibleQuery; +use crate::query::{ + MAX_TERM_CNT as QUERY_MAX_TERM_CNT, + TermWithFieldTuple as QueryTermWithFieldTuple, + TermWithoutFieldTuple as QueryTermWithoutFieldTuple, + Terms as QueryTerms, + TermsBuilderInterface, +}; +use crate::sole::{Single, Sole}; +use crate::stats::Stats; +use crate::system::observer::{Observer, WrapperComponent as ObserverWrapperComponent}; +use crate::system::{Callbacks, Metadata as SystemMetadata, System, SystemComponent}; +use crate::uid::{Kind as UidKind, Uid}; + +pub mod actions; +pub mod component; +pub mod entity; +pub mod error; +pub mod event; +pub mod extension; +pub mod pair; +pub mod phase; +pub mod query; +pub mod sole; +pub mod stats; +pub mod system; +pub mod tuple; +pub mod uid; +pub mod util; + +mod lock; + +pub use engine_ecs_macros::{Component, Sole}; + +pub use crate::query::Query; + +#[derive(Debug)] +pub struct World +{ + data: WorldData, + stop: AtomicBool, + is_first_tick: AtomicBool, + error_handler: ErrorHandler, +} + +impl World +{ + #[must_use] + pub fn new() -> Self + { + let mut world = Self { + data: WorldData::default(), + stop: AtomicBool::new(false), + is_first_tick: AtomicBool::new(false), + error_handler: err_handler_panic, + }; + + crate::phase::spawn_entities(&mut world); + + world.add_sole(Stats::default()).ok(); + + world + } + + pub fn set_err_handler(&mut self, err_handler: ErrorHandler) + { + self.error_handler = err_handler; + } + + /// Creates a entity with the given components. A new unique [`Uid`] will be generated + /// for this entity. + pub fn create_entity<Comps>(&mut self, components: Comps) -> Uid + where + Comps: ComponentSequence, + { + let entity_uid = Uid::new_unique(UidKind::Entity); + + self.create_entity_with_uid(entity_uid, components); + + entity_uid + } + + /// Creates a entity with the given components. The entity will have the specified + /// [`Uid`]. + #[tracing::instrument(skip_all)] + pub fn create_entity_with_uid<Comps>(&mut self, entity_uid: Uid, components: Comps) + where + Comps: ComponentSequence, + { + self.create_ent(entity_uid, components.into_parts_array()); + } + + pub fn add_component(&mut self, entity_id: Uid, component_parts: ComponentParts) + { + Self::add_entity_components( + entity_id, + [component_parts], + &mut self.data.component_storage, + &EventSubmitter::new(&self.data.new_events), + ); + } + + pub fn create_declared_entity(&mut self, entity_decl: &EntityDeclaration) + { + entity_decl.create(self); + } + + /// Adds a globally shared singleton value. + /// + /// # Errors + /// Returns `Err` if this [`Sole`] has already been added. + pub fn add_sole<SoleT>(&mut self, sole: SoleT) -> Result<(), SoleAlreadyExistsError> + where + SoleT: Sole, + { + self.data.sole_storage.insert(sole) + } + + pub fn register_observer<'this, SystemImpl, ObserverT>( + &'this mut self, + observer: ObserverT, + ) where + ObserverT: Observer<'this, SystemImpl>, + { + let (wrapper_comp, mut system_callbacks) = observer.finish_observer(); + + let ent_id = Uid::new_unique(UidKind::Entity); + + self.create_ent( + ent_id, + [wrapper_comp.into_parts()].into_iter().chain( + ObserverT::observed_events() + .into_iter() + .map(IntoComponentParts::into_parts), + ), + ); + + system_callbacks.on_created(self, SystemMetadata { ent_id }); + } + + pub fn register_system<'this, SystemImpl>( + &'this mut self, + phase_euid: Uid, + system: impl System<'this, SystemImpl>, + ) + { + let (type_erased_system, mut system_callbacks) = system.finish(); + + let system_ent_id = + self.create_entity((SystemComponent { system: type_erased_system },)); + + system_callbacks.on_created(self, SystemMetadata { ent_id: system_ent_id }); + + self.create_entity_with_uid( + phase_euid, + (Pair::builder() + .relation::<PhaseHasSystem>() + .target_id(system_ent_id) + .build(),), + ); + } + + /// Adds a extensions. + pub fn add_extension(&mut self, extension: impl Extension) + { + let extension_collector = ExtensionCollector::new(self); + + extension.collect(extension_collector); + } + + pub fn query<FieldTerms, FieldlessTerms>( + &self, + ) -> Query<'_, FieldTerms, FieldlessTerms> + where + FieldTerms: QueryTermWithFieldTuple, + FieldlessTerms: QueryTermWithoutFieldTuple, + { + Query::new(self) + } + + pub fn flexible_query<const MAX_TERM_CNT: usize>( + &self, + terms: QueryTerms<MAX_TERM_CNT>, + ) -> FlexibleQuery<'_, MAX_TERM_CNT> + { + FlexibleQuery::new(self, terms) + } + + pub fn get_entity(&self, entity_id: Uid) -> Option<EntityHandle<'_>> + { + let archetype = self + .data + .component_storage + .get_entity_archetype(entity_id)?; + + let Some(entity) = archetype.get_entity_by_id(entity_id) else { + unreachable!("Should exist since archetype was found by entity id"); + }; + + Some(EntityHandle::new(archetype, entity, self)) + } + + pub fn get_sole<SoleT: Sole>(&self) -> Option<Single<'_, SoleT>> + { + Some(Single::new(self.data.sole_storage.get::<SoleT>()?)) + } + + pub fn event_submitter(&self) -> EventSubmitter<'_> + { + EventSubmitter::new(&self.data.new_events) + } + + /// Performs a single tick. + /// # Panics + /// Will panic if mutable internal lock cannot be acquired. + pub fn step(&mut self) -> StepResult + { + if self.stop.load(Ordering::Relaxed) { + return StepResult::Stop; + } + + if self + .is_first_tick + .compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed) + .is_ok() + { + let Some(start_phase_entity) = self.get_entity(*START_PHASE) else { + unreachable!(); + }; + + self.run_phase_systems(&start_phase_entity); + } + + self.perform_phases(); + + self.emit_new_events(); + + self.data.component_storage.create_imaginary_archetypes(); + + self.perform_queued_actions(); + + if self.stop.load(Ordering::Relaxed) { + return StepResult::Stop; + } + + let Some(mut stats) = self.get_sole::<Stats>() else { + unreachable!(); // Reason: is added in World::new + }; + + stats.current_tick += 1; + + StepResult::Continue + } + + /// Starts a loop which calls [`Self::step`] until the world is stopped. + pub fn start_loop(&mut self) + { + while let StepResult::Continue = self.step() {} + } + + #[cfg(feature = "vizoxide")] + pub fn create_vizoxide_archetype_graph( + &self, + name: impl AsRef<str>, + ) -> Result<vizoxide::Graph, vizoxide::GraphvizError> + { + use std::borrow::Cow; + + use crate::component::storage::{ + VizoxideArchetypeGraphEdgeKind, + VizoxideArchetypeGraphParams, + }; + + self.data.component_storage.create_vizoxide_archetype_graph( + name, + VizoxideArchetypeGraphParams { + create_node_name: |archetype, _| { + Cow::Owned(format!( + "[{}]", + archetype + .component_ids_sorted() + .into_iter() + .map(|comp_id| comp_id.to_string()) + .collect::<Vec<_>>() + .join(", ") + )) + }, + create_node_cb: |_archetype, archetype_metadata, node_builder| { + if archetype_metadata.is_imaginary { + return node_builder.attribute("shape", "ellipse"); + } + + node_builder.attribute("shape", "box") + }, + create_edge_cb: |_, _, edge_kind, edge_builder| { + edge_builder.attribute( + "color", + match edge_kind { + VizoxideArchetypeGraphEdgeKind::Add => "green", + VizoxideArchetypeGraphEdgeKind::Remove => "red", + }, + ) + }, + }, + ) + } + + #[tracing::instrument(skip_all)] + fn create_ent( + &mut self, + entity_uid: Uid, + components: impl IntoIterator<Item = ComponentParts>, + ) + { + debug_assert_eq!(entity_uid.kind(), UidKind::Entity); + + if let Err(EntityAlreadyExistsError) = + self.data.component_storage.create_entity(entity_uid) + { + // This is fine + } + + Self::add_entity_components( + entity_uid, + components, + &mut self.data.component_storage, + &EventSubmitter::new(&self.data.new_events), + ); + } + + fn run_phase_systems(&self, phase_entity: &EntityHandle<'_>) + { + // The phase's systems are retrieved this way so that the order they are + // run is the same order as they were registered, even if they have local + // components. + for system_entity in phase_entity + .get_wildcard_pair_matches::<PhaseHasSystem, Wildcard>() + .into_iter() + .filter_map(|phase_has_system| phase_has_system.get_target_ent()) + { + let Some(system) = system_entity.get::<SystemComponent>() else { + cold_path(); + continue; + }; + + // SAFETY: The world lives long enough + if let Err(err) = unsafe { + system + .system + .run(self, SystemMetadata { ent_id: system_entity.uid() }) + } { + cold_path(); + + (self.error_handler)( + err, + ErrorMetadata { + source_name: system.system.name(), + source_kind: ErrorSourceKind::System, + }, + ) + } + } + } + + fn perform_child_phases(&self, parent_phase_euid: Uid) + { + let phase_query = self.flexible_query( + QueryTerms::<2>::builder() + .with_required([ + Phase::id(), + Pair::builder() + .relation::<ChildOf>() + .target_id(parent_phase_euid) + .build() + .id(), + ]) + .build(), + ); + + for child_phase_entity in &phase_query { + self.run_phase_systems(&child_phase_entity); + self.perform_child_phases(child_phase_entity.uid()); + } + } + + fn perform_single_phase(&self, phase_entity_id: Uid) + { + let Some(phase_entity) = self.get_entity(phase_entity_id) else { + unreachable!(); + }; + + self.run_phase_systems(&phase_entity); + self.perform_child_phases(phase_entity_id); + } + + fn perform_phases(&self) + { + self.perform_single_phase(*PRE_UPDATE_PHASE); + self.perform_single_phase(*UPDATE_PHASE); + self.perform_single_phase(*POST_UPDATE_PHASE); + } + + fn emit_new_events(&self) + { + loop { + let new_events = { + let mut new_events_lock = self + .data + .new_events + .write_nonblock() + .expect("Failed to acquire read-write lock to new events"); + + if new_events_lock.is_empty() { + break; + } + + new_events_lock.take() + }; + + for (event_id, event_matches) in new_events { + self.emit_event_observers( + event_id, + &EmittedEvent { + event: event_id, + match_ids: &event_matches.match_ids, + }, + ); + } + } + } + + #[tracing::instrument(skip_all)] + fn perform_queued_actions(&mut self) + { + let mut action_queue_lock = self + .data + .action_queue + .queue + .write_nonblock() + .unwrap_or_else(|err| { + panic!("Failed to take read-write action queue lock: {err}",); + }); + + for action in action_queue_lock.drain(..) { + match action { + Action::Spawn(new_entity_uid, components) => { + if let Err(err) = + self.data.component_storage.create_entity(new_entity_uid) + { + tracing::warn!("Failed to create entity: {err}"); + continue; + } + + Self::add_entity_components( + new_entity_uid, + components, + &mut self.data.component_storage, + &EventSubmitter::new(&self.data.new_events), + ); + } + Action::Despawn(entity_uid) => { + if let Err(err) = + self.data.component_storage.remove_entity(entity_uid) + { + tracing::error!("Failed to despawn entity: {err}"); + } + } + Action::AddComponents(entity_uid, components) => { + Self::add_entity_components( + entity_uid, + components, + &mut self.data.component_storage, + &EventSubmitter::new(&self.data.new_events), + ); + } + Action::RemoveComponents(entity_uid, component_ids) => { + Self::remove_entity_components( + entity_uid, + component_ids, + &mut self.data.component_storage, + ); + } + Action::Stop => { + self.stop.store(true, Ordering::Relaxed); + } + } + } + } + + fn add_entity_components( + entity_uid: Uid, + components: impl IntoIterator<Item = ComponentParts>, + component_storage: &mut ComponentStorage, + event_submitter: &EventSubmitter<'_>, + ) + { + let component_iter = components.into_iter(); + + for component_parts in component_iter { + let comp_id = component_parts.id(); + + let comp_name = component_parts.name(); + + if let Err(err) = component_storage.add_entity_component( + entity_uid, + (comp_id, comp_name, component_parts.into_data()), + ) { + tracing::error!("Failed to add component {comp_name} to entity: {err}"); + continue; + } + + if comp_id.kind() == UidKind::Pair { + continue; + } + + event_submitter.submit_event( + &Pair::builder() + .relation::<Added>() + .target_id(comp_id) + .build(), + entity_uid, + ); + } + } + + fn remove_entity_components( + entity_uid: Uid, + component_ids: impl IntoIterator<Item = Uid>, + component_storage: &mut ComponentStorage, + ) + { + let component_id_iter = component_ids.into_iter(); + + for component_id in component_id_iter { + if let Err(err) = + component_storage.remove_entity_component(entity_uid, component_id) + { + tracing::error!("Failed to remove component to entity: {err}"); + } + } + } + + fn emit_event_observers(&self, event_id: Uid, emitted_event: &EmittedEvent<'_>) + { + assert_eq!(event_id.kind(), UidKind::Pair); + + let query = Query::<(&ObserverWrapperComponent,)>::from_flexible_query( + self.flexible_query( + QueryTerms::<QUERY_MAX_TERM_CNT>::builder() + .with_required([ObserverWrapperComponent::id(), event_id]) + .build(), + ), + ); + + for (observer_ent_id, (observer,)) in query.iter_with_euids() { + if let Err(err) = unsafe { + observer.run( + self, + SystemMetadata { ent_id: observer_ent_id }, + emitted_event.clone(), + ) + } { + cold_path(); + + (self.error_handler)( + err, + ErrorMetadata { + source_name: observer.name(), + source_kind: ErrorSourceKind::Observer, + }, + ) + } + } + } +} + +impl Default for World +{ + fn default() -> Self + { + Self::new() + } +} + +/// The result of calling [`World::step`]. +pub enum StepResult +{ + /// Another step can be made. + Continue, + + /// The world have been stopped so no step can be made again. + Stop, +} + +#[derive(Debug, Default)] +struct WorldData +{ + component_storage: ComponentStorage, + sole_storage: SoleStorage, + action_queue: Rc<ActionQueue>, + new_events: Lock<NewEvents>, +} + +#[derive(Debug, Clone)] +pub struct EntityComponentRef<'a> +{ + component_id: Uid, + component: &'a ArchetypeEntityComponent, + entity_id: Uid, +} + +impl<'a> EntityComponentRef<'a> +{ + fn component(&self) -> &'a Lock<Box<dyn Any>> + { + self.component.component() + } + + #[must_use] + pub fn id(&self) -> Uid + { + self.component_id + } + + #[must_use] + pub fn entity_id(&self) -> Uid + { + self.entity_id + } + + fn new(component_id: Uid, comp: &'a ArchetypeEntityComponent, entity_id: Uid) + -> Self + { + Self { + component_id, + component: comp, + entity_id, + } + } +} + +#[derive(Debug, Default)] +struct ActionQueue +{ + queue: Lock<Vec<Action>>, +} + +impl ActionQueue +{ + fn push(&self, action: Action) + { + self.queue + .write_nonblock() + .expect("Failed to aquire read-write lock to action queue") + .push(action); + } +} + +#[derive(Debug, thiserror::Error)] +#[error("Sole {0} already exists")] +pub struct SoleAlreadyExistsError(pub &'static str); + +#[derive(Debug)] +struct StoredSole +{ + sole: Arc<Lock<Box<dyn Sole>>>, + drop_last: bool, +} + +#[derive(Debug, Default)] +struct SoleStorage +{ + storage: HashMap<TypeId, ManuallyDrop<StoredSole>>, +} + +impl SoleStorage +{ + fn get<SoleT: Sole>(&self) -> Option<&Arc<Lock<Box<dyn Sole>>>> + { + self.storage + .get(&TypeId::of::<SoleT>()) + .map(|sole| &sole.sole) + } + + fn insert<SoleT: Sole>(&mut self, sole: SoleT) -> Result<(), SoleAlreadyExistsError> + { + let sole_type_id = TypeId::of::<SoleT>(); + + if self.storage.contains_key(&sole_type_id) { + return Err(SoleAlreadyExistsError(type_name::<SoleT>())); + } + + let drop_last = sole.drop_last(); + + // TODO: Reconsider this maybe? + #[allow(clippy::arc_with_non_send_sync)] + self.storage.insert( + sole_type_id, + ManuallyDrop::new(StoredSole { + sole: Arc::new(Lock::new(Box::new(sole), type_name::<SoleT>())), + drop_last, + }), + ); + + Ok(()) + } +} + +impl Drop for SoleStorage +{ + fn drop(&mut self) + { + let mut soles_to_drop_last = Vec::new(); + + for sole in self.storage.values_mut() { + if sole.drop_last { + soles_to_drop_last.push(sole); + continue; + } + + unsafe { + ManuallyDrop::drop(sole); + } + } + + for sole in &mut soles_to_drop_last { + unsafe { + ManuallyDrop::drop(sole); + } + } + } +} diff --git a/engine-ecs/src/lock.rs b/engine-ecs/src/lock.rs new file mode 100644 index 0000000..fe4e08b --- /dev/null +++ b/engine-ecs/src/lock.rs @@ -0,0 +1,259 @@ +use std::any::type_name; +use std::mem::forget; +use std::ops::{Deref, DerefMut}; + +use parking_lot::{ + MappedRwLockReadGuard, + MappedRwLockWriteGuard, + RwLock, + RwLockReadGuard, + RwLockWriteGuard, +}; + +#[derive(Debug)] +pub struct Lock<Value> +{ + inner: RwLock<Value>, + value_type_name: &'static str, +} + +impl<Value> Lock<Value> +{ + pub fn new(value: Value, value_type_name: &'static str) -> Self + { + Self { + inner: RwLock::new(value), + value_type_name, + } + } + + /// Tries to a acquire a handle to the resource with read access. + /// + /// # Errors + /// Returns `Err` if unavailable (A mutable handle is hold). + pub fn read_nonblock(&self) -> Result<ReadGuard<'_, Value>, Error> + { + let guard = self.inner.try_read().ok_or(Error::ReadUnavailable)?; + + tracing::trace!("Acquired lock to value of type {}", self.value_type_name); + + Ok(ReadGuard { + inner: guard, + value_type_name: self.value_type_name, + }) + } + + /// Tries to a acquire a handle to the resource with mutable access. + /// + /// # Errors + /// Returns `Err` if unavailable (A mutable or immutable handle is hold). + pub fn write_nonblock(&self) -> Result<WriteGuard<'_, Value>, Error> + { + let guard = self.inner.try_write().ok_or(Error::WriteUnavailable)?; + + tracing::trace!( + "Acquired mutable lock to value of type {}", + self.value_type_name + ); + + Ok(WriteGuard { + inner: guard, + value_type_name: self.value_type_name, + }) + } +} + +impl<Value: Default + 'static> Default for Lock<Value> +{ + fn default() -> Self + { + Self::new(Value::default(), type_name::<Value>()) + } +} + +#[derive(Debug, thiserror::Error)] +pub enum Error +{ + #[error("Lock is unavailable for reading")] + ReadUnavailable, + + #[error("Lock is unavailable for writing")] + WriteUnavailable, +} + +#[derive(Debug)] +pub struct ReadGuard<'guard, Value> +{ + inner: RwLockReadGuard<'guard, Value>, + value_type_name: &'static str, +} + +impl<'guard, Value> ReadGuard<'guard, Value> +{ + pub fn try_map<NewValue>( + this: Self, + func: impl FnOnce(&Value) -> Option<&NewValue>, + ) -> Result<MappedReadGuard<'guard, NewValue>, Self> + { + let value_type_name = this.value_type_name; + + // The 'inner' field cannot be moved out of ReadGuard in a normal way since + // ReadGuard implements Drop + let inner = unsafe { std::ptr::read(&raw const this.inner) }; + forget(this); + + match RwLockReadGuard::try_map(inner, func) { + Ok(mapped_guard) => { + Ok(MappedReadGuard { inner: mapped_guard, value_type_name }) + } + Err(unmapped_guard) => Err(Self { + inner: unmapped_guard, + value_type_name, + }), + } + } +} + +impl<Value> Deref for ReadGuard<'_, Value> +{ + type Target = Value; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +impl<Value> Drop for ReadGuard<'_, Value> +{ + fn drop(&mut self) + { + tracing::trace!("Dropped lock to value of type {}", self.value_type_name); + } +} + +#[derive(Debug)] +pub struct MappedReadGuard<'guard, Value> +{ + inner: MappedRwLockReadGuard<'guard, Value>, + value_type_name: &'static str, +} + +impl<Value> Deref for MappedReadGuard<'_, Value> +{ + type Target = Value; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +impl<Value> Drop for MappedReadGuard<'_, Value> +{ + fn drop(&mut self) + { + tracing::trace!( + "Dropped mapped lock to value of type {}", + self.value_type_name + ); + } +} + +#[derive(Debug)] +pub struct WriteGuard<'guard, Value> +{ + inner: RwLockWriteGuard<'guard, Value>, + value_type_name: &'static str, +} + +impl<'guard, Value> WriteGuard<'guard, Value> +{ + pub fn try_map<NewValue>( + this: Self, + func: impl FnOnce(&mut Value) -> Option<&mut NewValue>, + ) -> Result<MappedWriteGuard<'guard, NewValue>, Self> + { + let value_type_name = this.value_type_name; + + // The 'inner' field cannot be moved out of ReadGuard in a normal way since + // ReadGuard implements Drop + let inner = unsafe { std::ptr::read(&raw const this.inner) }; + forget(this); + + match RwLockWriteGuard::try_map(inner, func) { + Ok(mapped_guard) => { + Ok(MappedWriteGuard { inner: mapped_guard, value_type_name }) + } + Err(unmapped_guard) => Err(Self { + inner: unmapped_guard, + value_type_name, + }), + } + } +} + +impl<Value> Deref for WriteGuard<'_, Value> +{ + type Target = Value; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +impl<Value> DerefMut for WriteGuard<'_, Value> +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + &mut self.inner + } +} + +impl<Value> Drop for WriteGuard<'_, Value> +{ + fn drop(&mut self) + { + tracing::trace!( + "Dropped mutable lock to value of type {}", + self.value_type_name + ); + } +} + +#[derive(Debug)] +pub struct MappedWriteGuard<'guard, Value> +{ + inner: MappedRwLockWriteGuard<'guard, Value>, + value_type_name: &'static str, +} + +impl<Value> Deref for MappedWriteGuard<'_, Value> +{ + type Target = Value; + + fn deref(&self) -> &Self::Target + { + &self.inner + } +} + +impl<Value> DerefMut for MappedWriteGuard<'_, Value> +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + &mut self.inner + } +} + +impl<Value> Drop for MappedWriteGuard<'_, Value> +{ + fn drop(&mut self) + { + tracing::trace!( + "Dropped mapped mutable lock to value of type {}", + self.value_type_name + ); + } +} diff --git a/engine-ecs/src/pair.rs b/engine-ecs/src/pair.rs new file mode 100644 index 0000000..0d353e3 --- /dev/null +++ b/engine-ecs/src/pair.rs @@ -0,0 +1,687 @@ +use std::any::type_name; +use std::convert::Infallible; +use std::marker::PhantomData; + +use crate::component::{ + Handle as ComponentHandle, + HandleError as ComponentHandleError, + HandleMut as ComponentHandleMut, + IntoParts as IntoComponentParts, + Parts as ComponentParts, +}; +use crate::entity::{ + Handle as EntityHandle, + MatchingComponentIter as EntityMatchingComponentIter, +}; +use crate::query::{ + TermWithField as QueryTermWithField, + TermsBuilder as QueryTermsBuilder, + TermsBuilderInterface, +}; +use crate::uid::{Kind as UidKind, PairParams as UidPairParams, Uid, With as WithUid}; +use crate::util::impl_multiple; +use crate::{Component, EntityComponentRef, World}; + +/// Pair builder. +#[derive(Debug)] +pub struct Builder<Relation, Target> +{ + relation: Relation, + target: Target, +} + +impl<Relation, Target> Builder<Relation, Target> +{ + pub fn relation<NewRelation: Component>(self) -> Builder<Uid, Target> + { + Builder { + relation: NewRelation::id(), + target: self.target, + } + } + + pub fn relation_id(self, id: Uid) -> Builder<Uid, Target> + { + Builder { relation: id, target: self.target } + } + + pub fn target<NewTarget: Component>(self) -> Builder<Relation, Uid> + { + Builder { + relation: self.relation, + target: NewTarget::id(), + } + } + + pub fn target_id(self, id: Uid) -> Builder<Relation, Uid> + { + Builder { relation: self.relation, target: id } + } +} + +impl_multiple!( + Builder, + (impl<Target> _<><Uid, Target>, impl<Target> _<><(), Target>) + cb=(type_params=(ty_param_1, ty_param_2)) => { + pub fn target_as_data<NewTarget: Component>( + self, + data: NewTarget, + ) -> Builder<$ty_param_1, NewTarget> + { + Builder { + relation: self.relation, + target: data, + } + } + } +); + +impl_multiple!( + Builder, + (impl<Relation> _<><Relation, Uid>, impl<Relation> _<><Relation, ()>) + cb=(type_params=(ty_param_1, ty_param_2)) => { + pub fn relation_as_data<NewRelation: Component>( + self, + data: NewRelation, + ) -> Builder<NewRelation, $ty_param_2> + { + Builder { + relation: data, + target: self.target, + } + } + } +); + +impl_multiple!( + Builder, + ( + impl _<><Uid, Uid>, + impl<Relation: Component> _<><Relation, Uid>, + impl<Target: Component> _<><Uid, Target>, + impl<Relation: Component, Target: Component> _<><Relation, Target> + ) + cb=(type_params=(ty_param_1, ty_param_2)) => { + #[must_use] + pub fn build(self) -> Pair<$ty_param_1, $ty_param_2> + { + Pair { + relation: self.relation, + target: self.target + } + } + } +); + +impl Default for Builder<(), ()> +{ + fn default() -> Self + { + Self { relation: (), target: () } + } +} + +#[derive(Debug)] +pub struct Pair<Relation, Target> +{ + relation: Relation, + target: Target, +} + +impl Pair<(), ()> +{ + #[must_use] + pub fn builder() -> Builder<(), ()> + { + Builder { relation: (), target: () } + } +} + +impl Pair<Uid, Uid> +{ + #[must_use] + pub fn id(&self) -> Uid + { + Uid::new_pair(&UidPairParams { + relation: self.relation, + target: self.target, + }) + } +} + +impl IntoComponentParts for Pair<Uid, Uid> +{ + fn into_parts(self) -> ComponentParts + { + ComponentParts::builder().name("Pair").build(self.id(), ()) + } +} + +impl<Target> IntoComponentParts for Pair<Uid, Target> +where + Target: Component, +{ + fn into_parts(self) -> ComponentParts + { + let id = Uid::new_pair(&UidPairParams { + relation: self.relation, + target: Target::id(), + }); + + ComponentParts::builder() + .name("Pair") + .build(id, self.target) + } +} + +impl<Relation> IntoComponentParts for Pair<Relation, Uid> +where + Relation: Component, +{ + fn into_parts(self) -> ComponentParts + { + let id = Uid::new_pair(&UidPairParams { + relation: Relation::id(), + target: self.target, + }); + + ComponentParts::builder() + .name("Pair") + .build(id, self.relation) + } +} + +impl<Relation, Target> QueryTermWithField for Pair<Relation, &Target> +where + Relation: Component, + Target: Component, +{ + type Field<'a> = ComponentHandle<'a, Target>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with_required([Pair::<Relation, Target>::uid()]); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + _world: &'world World, + ) -> Self::Field<'world> + { + let target_component = entity_handle + .get_matching_components(Pair::<Relation, Target>::uid()) + .next() + .expect("Not possible"); + + Self::Field::from_entity_component_ref(&target_component).unwrap_or_else(|err| { + panic!( + "Creating handle to target component {} failed: {err}", + type_name::<Target>() + ); + }) + } +} + +impl<Relation, Target> QueryTermWithField for Pair<Relation, &mut Target> +where + Relation: Component, + Target: Component, +{ + type Field<'a> = ComponentHandleMut<'a, Target>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with_required([Pair::<Relation, Target>::uid()]); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world> + { + let target_component = entity_handle + .get_matching_components(Pair::<Relation, Target>::uid()) + .next() + .expect("Not possible"); + + Self::Field::from_entity_component_ref(&target_component, world).unwrap_or_else( + |err| { + panic!( + "Creating handle to target component {} failed: {err}", + type_name::<Target>() + ); + }, + ) + } +} + +// TODO: implement QueryTermWithField for Pair<&Relation, Target> (or equivalent) +// TODO: implement QueryTermWithField for Pair<&mut Relation, Target> (or equivalent) + +impl<Relation> QueryTermWithField for Pair<Relation, Wildcard> +where + Relation: Component, +{ + type Field<'a> = WithWildcard<'a, Relation, Wildcard>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with_required([Self::uid()]); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world> + { + let first_matching_comp = entity_handle + .get_matching_components(Self::uid()) + .next() + .expect("Not possible"); + + WithWildcard { + world, + component_ref: first_matching_comp, + _pd: PhantomData, + } + } +} + +impl<Relation, Target> WithUid for Pair<Relation, Target> +where + Relation: Component, + Target: Component, +{ + fn uid() -> Uid + { + Uid::new_pair(&UidPairParams { + relation: Relation::id(), + target: Target::id(), + }) + } +} + +impl<Relation> WithUid for Pair<Relation, Wildcard> +where + Relation: Component, +{ + fn uid() -> Uid + { + Uid::new_pair(&UidPairParams { + relation: Relation::id(), + target: Wildcard::uid(), + }) + } +} + +impl<Relation> QueryTermWithField for &'_ [Pair<Relation, Wildcard>] +where + Relation: Component, +{ + type Field<'a> = MultipleWithWildcard<'a, Relation, Wildcard>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut QueryTermsBuilder<MAX_TERM_CNT>, + ) + { + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world> + { + MultipleWithWildcard { + entity_handle: entity_handle.clone(), + world, + _pd: PhantomData, + } + } +} + +/// Reference to a pair with a wildcard relation/target. +#[derive(Debug)] +pub struct WithWildcard<'world, Relation, Target> +{ + world: &'world World, + component_ref: EntityComponentRef<'world>, + _pd: PhantomData<(Relation, Target)>, +} + +impl<'world, Relation, Target> WithWildcard<'world, Relation, Target> +{ + /// Returns a new `WithWildcard`. + /// + /// # Panics + /// This function will panic if: + /// - The given component's ID is not a pair ID. + /// - `Relation::uid()` is not wildcard and does not equal to the relation of the + /// given component's ID + /// - `Target::uid()` is not wildcard and does not equal to the target of the given + /// component's ID + /// - Both `Relation::uid()` and `Target::uid()` are wildcards + /// - Neither `Relation::uid()` or `Target::uid()` are wildcards + pub fn new(world: &'world World, component_ref: EntityComponentRef<'world>) -> Self + where + Relation: ComponentOrWildcard, + Target: ComponentOrWildcard, + { + let component_id = component_ref.id(); + + assert!(component_id.kind() == UidKind::Pair); + + assert!( + Relation::uid() == Wildcard::uid() + || component_id.relation_component() == Relation::uid() + ); + + assert!( + Target::uid() == Wildcard::uid() + || component_id.target_component() == Target::uid() + ); + + assert!(Relation::uid() == Wildcard::uid() || Target::uid() == Wildcard::uid()); + + assert!( + !(Relation::uid() == Wildcard::uid() && Target::uid() == Wildcard::uid()) + ); + + WithWildcard { + world, + component_ref, + _pd: PhantomData, + } + } + + /// Returns the [`Uid`] of the pair. + #[must_use] + pub fn id(&self) -> Uid + { + self.component_ref.id() + } + + /// Attempts to get the component data of this pair, returning `None` if the `Data` + /// type is incorrect. + /// + /// # Panics + /// Will panic if the component data is mutably borrowed elsewhere. + #[must_use] + pub fn get_data<Data>(&self) -> Option<ComponentHandle<'_, Data>> + where + Data: 'static, + { + ComponentHandle::<Data>::from_entity_component_ref(&self.component_ref) + .map_or_else( + |err| match err { + ComponentHandleError::IncorrectType => None, + err @ ComponentHandleError::AcquireLockFailed(_) => { + panic!( + "Creating handle to pair data as component {} failed: {err}", + type_name::<Data>() + ); + } + }, + Some, + ) + } + + /// Attempts to get the component data of this pair, returning `None` if the `Data` + /// type is incorrect. + /// + /// # Panics + /// Will panic if the component data is borrowed elsewhere. + #[must_use] + pub fn get_data_mut<Data>(&self) -> Option<ComponentHandleMut<'_, Data>> + where + Data: 'static, + { + ComponentHandleMut::<Data>::from_entity_component_ref( + &self.component_ref, + self.world, + ) + .map_or_else( + |err| match err { + ComponentHandleError::IncorrectType => None, + err @ ComponentHandleError::AcquireLockFailed(_) => { + panic!( + "Creating handle to pair data as component {} failed: {err}", + type_name::<Data>() + ); + } + }, + Some, + ) + } +} + +impl<'world, Relation> WithWildcard<'world, Relation, Wildcard> +where + Relation: Component, +{ + /// Attempts to retrieve the target as a entity, returning `None` if not found. + #[must_use] + pub fn get_target_ent(&self) -> Option<EntityHandle<'world>> + { + let archetype = self + .world + .data + .component_storage + .get_entity_archetype(self.component_ref.id().target_entity())?; + + let Some(archetype_entity) = + archetype.get_entity_by_id(self.component_ref.id().target_entity()) + else { + unreachable!(); + }; + + Some(EntityHandle::new(archetype, archetype_entity, self.world)) + } + + /// Attempts to get the component data of this pair, returning `None` if the + /// `Relation` type is incorrect. + /// + /// # Panics + /// Will panic if the component data is mutably borrowed elsewhere. + #[must_use] + pub fn get_data_as_relation(&self) -> Option<ComponentHandle<'_, Relation>> + { + ComponentHandle::<Relation>::from_entity_component_ref(&self.component_ref) + .map_or_else( + |err| match err { + ComponentHandleError::IncorrectType => None, + err @ ComponentHandleError::AcquireLockFailed(_) => { + panic!( + "Creating handle to pair data as component {} failed: {err}", + type_name::<Relation>() + ); + } + }, + Some, + ) + } + + /// Attempts to get the component data of this pair, returning `None` if the + /// `Relation` type is incorrect. + /// + /// # Panics + /// Will panic if the component data is borrowed elsewhere. + #[must_use] + pub fn get_data_as_relation_mut(&self) -> Option<ComponentHandleMut<'_, Relation>> + { + ComponentHandleMut::<Relation>::from_entity_component_ref( + &self.component_ref, + self.world, + ) + .map_or_else( + |err| match err { + ComponentHandleError::IncorrectType => None, + err @ ComponentHandleError::AcquireLockFailed(_) => { + panic!( + "Creating handle to pair data as component {} failed: {err}", + type_name::<Relation>() + ); + } + }, + Some, + ) + } +} + +/// Used to access matching pairs in a entity containing zero or more matching pairs. +#[derive(Debug)] +pub struct MultipleWithWildcard<'a, Relation, Target> +{ + entity_handle: EntityHandle<'a>, + world: &'a World, + _pd: PhantomData<(Relation, Target)>, +} + +impl<'world, Relation, Target> MultipleWithWildcard<'world, Relation, Target> +{ + /// Returns a new `MultipleWithWildcard`. + /// + /// # Panics + /// This function will panic if: + /// - Both `Relation::uid()` and `Target::uid()` are wildcards + /// - Neither `Relation::uid()` or `Target::uid()` are wildcards + pub fn new(world: &'world World, entity_handle: EntityHandle<'world>) -> Self + where + Relation: ComponentOrWildcard, + Target: ComponentOrWildcard, + { + assert!(Relation::uid() == Wildcard::uid() || Target::uid() == Wildcard::uid()); + + assert!( + !(Relation::uid() == Wildcard::uid() && Target::uid() == Wildcard::uid()) + ); + + MultipleWithWildcard { + entity_handle, + world, + _pd: PhantomData, + } + } +} + +impl<'a, Relation: Component> MultipleWithWildcard<'a, Relation, Wildcard> +{ + #[must_use] + pub fn get_with_target_id( + &self, + target_id: Uid, + ) -> Option<WithWildcard<'a, Relation, Wildcard>> + { + Some(WithWildcard { + world: self.world, + component_ref: self + .entity_handle + .get_matching_components( + Pair::builder() + .relation::<Relation>() + .target_id(target_id) + .build() + .id(), + ) + .next()?, + _pd: PhantomData, + }) + } +} + +impl<'a, Relation: Component> IntoIterator + for MultipleWithWildcard<'a, Relation, Wildcard> +{ + type IntoIter = WithWildcardIter<'a, Relation, Wildcard>; + type Item = <Self::IntoIter as Iterator>::Item; + + fn into_iter(self) -> Self::IntoIter + { + WithWildcardIter { + inner: self + .entity_handle + .get_matching_components(Pair::<Relation, Wildcard>::uid()), + world: self.world, + _pd: PhantomData, + } + } +} + +/// Iterator of matching pairs in a entity. +pub struct WithWildcardIter<'a, Relation, Target> +{ + inner: EntityMatchingComponentIter<'a>, + world: &'a World, + _pd: PhantomData<(Relation, Target)>, +} + +impl<'a, Relation, Target> Iterator for WithWildcardIter<'a, Relation, Target> +{ + type Item = WithWildcard<'a, Relation, Target>; + + fn next(&mut self) -> Option<Self::Item> + { + let matching_comp = self.inner.next()?; + + Some(WithWildcard { + world: self.world, + component_ref: matching_comp, + _pd: PhantomData, + }) + } +} + +/// Relation denoting a dependency to another entity +#[derive(Debug, Default, Clone, Copy, Component)] +pub struct DependsOn; + +/// Relation denoting being the child of another entity. +#[derive(Debug, Default, Clone, Copy, Component)] +pub struct ChildOf; + +#[derive(Debug)] +pub struct Wildcard(Infallible); + +impl Wildcard +{ + #[must_use] + pub fn uid() -> Uid + { + Uid::wildcard() + } +} + +pub trait ComponentOrWildcard: sealed::Sealed +{ + fn uid() -> Uid; +} + +impl<ComponentT: Component> ComponentOrWildcard for ComponentT +{ + fn uid() -> Uid + { + ComponentT::id() + } +} + +impl<ComponentT: Component> sealed::Sealed for ComponentT {} + +impl ComponentOrWildcard for Wildcard +{ + fn uid() -> Uid + { + Wildcard::uid() + } +} + +impl sealed::Sealed for Wildcard {} + +mod sealed +{ + pub trait Sealed {} +} diff --git a/engine-ecs/src/phase.rs b/engine-ecs/src/phase.rs new file mode 100644 index 0000000..976de1b --- /dev/null +++ b/engine-ecs/src/phase.rs @@ -0,0 +1,20 @@ +use crate::{Component, World, declare_entity}; + +#[derive(Debug, Default, Clone, Copy, Component)] +pub struct Phase; + +declare_entity!(pub START, (Phase,)); +declare_entity!(pub PRE_UPDATE, (Phase,)); +declare_entity!(pub UPDATE, (Phase,)); +declare_entity!(pub POST_UPDATE, (Phase,)); + +pub(crate) fn spawn_entities(world: &mut World) +{ + world.create_declared_entity(&START); + world.create_declared_entity(&PRE_UPDATE); + world.create_declared_entity(&UPDATE); + world.create_declared_entity(&POST_UPDATE); +} + +#[derive(Debug, Component)] +pub(crate) struct HasSystem; diff --git a/engine-ecs/src/query.rs b/engine-ecs/src/query.rs new file mode 100644 index 0000000..5f13579 --- /dev/null +++ b/engine-ecs/src/query.rs @@ -0,0 +1,569 @@ +use std::any::type_name; +use std::marker::PhantomData; + +use seq_macro::seq; + +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::uid::{Kind as UidKind, Uid, With as WithUid}; +use crate::util::array_vec::ArrayVec; +use crate::util::Array; +use crate::World; + +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, FieldTerms, FieldlessTerms = ()> +where + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, +{ + inner: FlexibleQuery<'world, MAX_TERM_CNT>, + _pd: PhantomData<(FieldTerms, FieldlessTerms)>, +} + +impl<'world, FieldTerms, FieldlessTerms> Query<'world, FieldTerms, FieldlessTerms> +where + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, +{ + /// Iterates over the entities matching this query, the iterator item being the entity + /// components. + #[must_use] + pub fn iter<'query>( + &'query self, + ) -> Iter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>> + { + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); + + 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<'query>( + &'query self, + ) -> ComponentAndEuidIter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>> + { + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); + + ComponentAndEuidIter { + world: self.inner.world(), + iter: self.inner.iter(), + comps_pd: PhantomData, + } + } + + /// Iterates over the entities matching this query using the iterator returned by + /// `func`. + /// + /// This function exists so that a custom [`EntityHandle`] iterator can be given to + /// [`Iter`] without giving the user access to a reference to the [`World`]. + #[must_use] + pub fn iter_with<'query, OutIter>( + &'query self, + func: impl FnOnce(FlexibleQueryIter<'query>) -> OutIter, + ) -> Iter<'query, 'world, FieldTerms, OutIter> + where + OutIter: Iterator<Item = EntityHandle<'query>>, + { + tracing::trace!("Searching for {}", std::any::type_name::<FieldTerms>()); + + Iter { + world: self.inner.world(), + inner: func(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(&self, entity_index: usize) -> Option<Uid> + { + Some(self.inner.iter().nth(entity_index)?.uid()) + } + + /// Returns a new `Query` created from a [`FlexibleQuery`]. + /// + /// # Important notes + /// The terms in `FieldTerms` and `FieldlessTerms` 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(crate) fn new(world: &'world World) -> Self + { + let mut terms_builder = Terms::builder(); + + FieldTerms::apply_terms_to_builder(&mut terms_builder); + FieldlessTerms::apply_terms_to_builder(&mut terms_builder); + + Self { + inner: world.flexible_query(terms_builder.build()), + _pd: PhantomData, + } + } +} + +impl<'query, 'world, FieldTerms, FieldlessTerms> IntoIterator + for &'query Query<'world, FieldTerms, FieldlessTerms> +where + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, +{ + type IntoIter = Iter<'query, 'world, FieldTerms, FlexibleQueryIter<'query>>; + type Item = FieldTerms::Fields<'query>; + + fn into_iter(self) -> Self::IntoIter + { + self.iter() + } +} + +impl<'world, FieldTerms, FieldlessTerms> SystemParam<'world> + for Query<'world, FieldTerms, FieldlessTerms> +where + FieldTerms: TermWithFieldTuple, + FieldlessTerms: TermWithoutFieldTuple, +{ + type Input = (); + + fn new(world: &'world World, _system_metadata: &SystemMetadata) -> Self + { + Self::new(world) + } +} + +#[derive(Debug)] +pub struct Terms<const MAX_TERM_CNT: usize> +{ + required_components: ArrayVec<Uid, MAX_TERM_CNT>, + excluded_components: ArrayVec<Uid, MAX_TERM_CNT>, +} + +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 MAX_TERM_CNT: usize> +{ + required_components: ArrayVec<Uid, MAX_TERM_CNT>, + excluded_components: ArrayVec<Uid, MAX_TERM_CNT>, +} + +#[allow(clippy::return_self_not_must_use)] +pub trait TermsBuilderInterface +{ + fn with<WithUidT: WithUid>(self) -> Self; + + fn without<WithUidT: WithUid>(self) -> Self; + + fn with_required(self, ids: impl Array<Uid>) -> Self; + + fn without_ids(self, ids: impl Array<Uid>) -> Self; +} + +macro_rules! impl_terms_builder { + ($($impl_content: tt)*) => { + impl<const MAX_TERM_CNT: usize> + TermsBuilderInterface for TermsBuilder<MAX_TERM_CNT> + { + $($impl_content)* + } + + impl<const MAX_TERM_CNT: usize> + TermsBuilderInterface for &mut TermsBuilder<MAX_TERM_CNT> + { + $($impl_content)* + } + }; +} + +impl_terms_builder! { + #[allow(unused_mut)] + fn with<WithUidT: WithUid>(mut self) -> Self + { + let insert_index = self.required_components + .partition_point(|id| *id <= WithUidT::uid()); + + self.required_components + .insert(insert_index, WithUidT::uid()); + + self + } + + #[allow(unused_mut)] + fn without<WithUidT: WithUid>(mut self) -> Self + { + let insert_index = self.excluded_components + .partition_point(|id| *id <= WithUidT::uid()); + + self.excluded_components + .insert(insert_index, WithUidT::uid()); + + self + } + + #[allow(unused_mut)] + fn with_required(mut self, mut ids: impl Array<Uid>) -> Self + { + if !ids.as_ref().is_sorted() { + ids.as_mut().sort(); + } + + if self.required_components.is_empty() { + self.required_components.extend(ids); + return self; + } + + let mut id_iter = ids.into_iter(); + + while let Some(id) = id_iter.next() { + let insert_index = self.required_components + .partition_point(|other_id| *other_id <= id); + + if insert_index == self.required_components.len() { + self.required_components.extend([id].into_iter().chain(id_iter)); + + return self; + } + + self.required_components + .insert(insert_index, id); + + } + + self + } + + #[allow(unused_mut)] + fn without_ids(mut self, mut ids: impl Array<Uid>) -> Self + { + if !ids.as_ref().is_sorted() { + ids.as_mut().sort(); + } + + if self.excluded_components.is_empty() { + self.excluded_components.extend(ids); + return self; + } + + let mut id_iter = ids.into_iter(); + + while let Some(id) = id_iter.next() { + let insert_index = self.excluded_components + .partition_point(|other_id| *other_id <= id); + + if insert_index == self.excluded_components.len() { + self.excluded_components.extend([id].into_iter().chain(id_iter)); + + return self; + } + + self.excluded_components + .insert(insert_index, id); + + } + + self + } +} + +impl<const MAX_TERM_CNT: usize> TermsBuilder<MAX_TERM_CNT> +{ + #[must_use] + pub fn build(self) -> Terms<MAX_TERM_CNT> + { + debug_assert!(self.required_components.is_sorted()); + debug_assert!(self.excluded_components.is_sorted()); + + Terms { + required_components: self.required_components, + excluded_components: self.excluded_components, + } + } +} + +pub trait TermWithoutField +{ + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); +} + +pub trait TermWithField +{ + type Field<'a>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world>; +} + +impl<ComponentT: Component> TermWithField for &ComponentT +{ + type Field<'a> = ComponentHandle<'a, ComponentT>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with::<ComponentT>(); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + _world: &'world World, + ) -> Self::Field<'world> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let Some(component) = entity_handle + .get_matching_components(ComponentT::id()) + .next() + else { + panic!( + concat!( + "Component {} was not found in entity {}. There ", + "is most likely a bug in the entity querying" + ), + type_name::<ComponentT>(), + entity_handle.uid() + ); + }; + + Self::Field::from_entity_component_ref(&component).unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }) + } +} + +impl<ComponentT: Component> TermWithField for &mut ComponentT +{ + type Field<'a> = ComponentHandleMut<'a, ComponentT>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with::<ComponentT>(); + } + + fn get_field<'world>( + entity_handle: &EntityHandle<'world>, + world: &'world World, + ) -> Self::Field<'world> + { + assert_eq!(ComponentT::id().kind(), UidKind::Component); + + let Some(component) = entity_handle + .get_matching_components(ComponentT::id()) + .next() + else { + panic!( + concat!( + "Component {} was not found in entity {}. There ", + "is most likely a bug in the entity querying" + ), + type_name::<ComponentT>(), + entity_handle.uid() + ); + }; + + Self::Field::from_entity_component_ref(&component, world).unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }) + } +} + +pub trait TermWithoutFieldTuple +{ + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); +} + +pub trait TermWithFieldTuple +{ + type Fields<'component>; + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ); + + fn get_fields<'component>( + entity_handle: &EntityHandle<'component>, + world: &'component World, + ) -> Self::Fields<'component>; +} + +pub struct Iter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, +{ + world: &'world World, + inner: EntityHandleIter, + comps_pd: PhantomData<FieldTerms>, +} + +impl<'query, 'world, FieldTerms, EntityHandleIter> Iterator + for Iter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, + 'world: 'query, +{ + type Item = FieldTerms::Fields<'query>; + + fn next(&mut self) -> Option<Self::Item> + { + let entity_handle = self.inner.next()?; + + Some(FieldTerms::get_fields(&entity_handle, self.world)) + } +} + +pub struct ComponentAndEuidIter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, +{ + world: &'world World, + iter: EntityHandleIter, + comps_pd: PhantomData<FieldTerms>, +} + +impl<'query, 'world, FieldTerms, EntityHandleIter> Iterator + for ComponentAndEuidIter<'query, 'world, FieldTerms, EntityHandleIter> +where + FieldTerms: TermWithFieldTuple, + EntityHandleIter: Iterator<Item = EntityHandle<'query>>, + 'world: 'query, +{ + type Item = (Uid, FieldTerms::Fields<'query>); + + fn next(&mut self) -> Option<Self::Item> + { + let entity_handle = self.iter.next()?; + + Some(( + entity_handle.uid(), + FieldTerms::get_fields(&entity_handle, self.world), + )) + } +} + +macro_rules! impl_term_sequence { + ($c: tt) => { + seq!(I in 0..=$c { + impl<#(Term~I: TermWithoutField,)*> TermWithoutFieldTuple for (#(Term~I,)*) + { + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT> + ) + { + #( + Term~I::apply_to_terms_builder(terms_builder); + )* + } + } + + impl<#(Term~I: TermWithField,)*> TermWithFieldTuple for (#(Term~I,)*) + { + type Fields<'component> = (#(Term~I::Field<'component>,)*); + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT> + ) + { + #( + Term~I::apply_to_terms_builder(terms_builder); + )* + } + + fn get_fields<'component>( + entity_handle: &EntityHandle<'component>, + world: &'component World, + ) -> Self::Fields<'component> + { + (#(Term~I::get_field(entity_handle, world),)*) + } + } + }); + }; +} + +seq!(C in 0..=16 { + impl_term_sequence!(C); +}); + +impl TermWithoutFieldTuple for () +{ + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } +} + +impl TermWithFieldTuple for () +{ + type Fields<'component> = (); + + fn apply_terms_to_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } + + fn get_fields<'component>( + _entity_handle: &EntityHandle<'_>, + _world: &'component World, + ) -> Self::Fields<'component> + { + } +} diff --git a/engine-ecs/src/query/flexible.rs b/engine-ecs/src/query/flexible.rs new file mode 100644 index 0000000..936ab82 --- /dev/null +++ b/engine-ecs/src/query/flexible.rs @@ -0,0 +1,92 @@ +//! Low-level querying. +use std::iter::{repeat_n, FlatMap, RepeatN, Zip}; + +use crate::component::storage::archetype::{Archetype, EntityIter}; +use crate::component::storage::{ArchetypeRefIter, ArchetypeSearchTerms}; +use crate::entity::Handle as EntityHandle; +use crate::query::Terms; +use crate::World; + +/// Low-level entity query structure. +#[derive(Debug)] +pub struct Query<'world, const MAX_TERM_CNT: usize> +{ + world: &'world World, + terms: Terms<MAX_TERM_CNT>, +} + +impl<'world, const MAX_TERM_CNT: usize> Query<'world, MAX_TERM_CNT> +{ + /// Iterates over the entities matching this query. + #[must_use] + pub fn iter(&self) -> Iter<'_> + { + Iter { + iter: self + .world + .data + .component_storage + .search_archetypes(ArchetypeSearchTerms { + required_components: &self.terms.required_components, + excluded_components: &self.terms.excluded_components, + }) + .flat_map( + (|archetype| { + repeat_n(archetype, archetype.entity_cnt()) + .zip(archetype.entities()) + }) as ComponentIterMapFn, + ), + world: self.world, + } + } + + #[must_use] + pub fn world(&self) -> &'world World + { + self.world + } + + pub(crate) fn new(world: &'world World, terms: Terms<MAX_TERM_CNT>) -> Self + { + Self { world, terms } + } +} + +impl<'query, const MAX_TERM_CNT: usize> IntoIterator for &'query Query<'_, MAX_TERM_CNT> +{ + type IntoIter = Iter<'query>; + type Item = EntityHandle<'query>; + + fn into_iter(self) -> Self::IntoIter + { + self.iter() + } +} + +pub struct Iter<'query> +{ + iter: QueryEntityIter<'query>, + world: &'query World, +} + +impl<'query> Iterator for Iter<'query> +{ + type Item = EntityHandle<'query>; + + fn next(&mut self) -> Option<Self::Item> + { + let (archetype, entity) = self.iter.next()?; + + Some(EntityHandle::new(archetype, entity, self.world)) + } +} + +type ComponentIterMapFnOutput<'a> = Zip<RepeatN<&'a Archetype>, EntityIter<'a>>; + +type ComponentIterMapFn = for<'a> fn(&'a Archetype) -> ComponentIterMapFnOutput<'a>; + +type QueryEntityIter<'query> = FlatMap< + ArchetypeRefIter<'query, 'query>, + ComponentIterMapFnOutput<'query>, + ComponentIterMapFn, +>; diff --git a/engine-ecs/src/query/term.rs b/engine-ecs/src/query/term.rs new file mode 100644 index 0000000..0683918 --- /dev/null +++ b/engine-ecs/src/query/term.rs @@ -0,0 +1,116 @@ +use std::any::type_name; +use std::marker::PhantomData; + +use crate::component::{ + Component, + Handle as ComponentHandle, + HandleMut as ComponentHandleMut, +}; +use crate::query::{ + TermWithField, + TermWithoutField, + TermsBuilder, + TermsBuilderInterface, +}; +use crate::uid::With as WithUid; + +pub struct With<WithUidT> +where + WithUidT: WithUid, +{ + _pd: PhantomData<WithUidT>, +} + +impl<WithUidT> TermWithoutField for With<WithUidT> +where + WithUidT: WithUid, +{ + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.with::<WithUidT>(); + } +} + +pub struct Without<WithUidT> +where + WithUidT: WithUid, +{ + _pd: PhantomData<WithUidT>, +} + +impl<WithUidT> TermWithoutField for Without<WithUidT> +where + WithUidT: WithUid, +{ + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + terms_builder.without::<WithUidT>(); + } +} + +impl<ComponentT: Component> TermWithField for Option<&ComponentT> +{ + type Field<'a> = Option<ComponentHandle<'a, ComponentT>>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } + + fn get_field<'world>( + entity_handle: &crate::entity::Handle<'world>, + _world: &'world crate::World, + ) -> Self::Field<'world> + { + Some( + ComponentHandle::<'world, ComponentT>::from_entity_component_ref( + &entity_handle + .get_matching_components(ComponentT::id()) + .next()?, + ) + .unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }), + ) + } +} + +impl<ComponentT: Component> TermWithField for Option<&mut ComponentT> +{ + type Field<'a> = Option<ComponentHandleMut<'a, ComponentT>>; + + fn apply_to_terms_builder<const MAX_TERM_CNT: usize>( + _terms_builder: &mut TermsBuilder<MAX_TERM_CNT>, + ) + { + } + + fn get_field<'world>( + entity_handle: &crate::entity::Handle<'world>, + world: &'world crate::World, + ) -> Self::Field<'world> + { + Some( + ComponentHandleMut::<'world, ComponentT>::from_entity_component_ref( + &entity_handle + .get_matching_components(ComponentT::id()) + .next()?, + world, + ) + .unwrap_or_else(|err| { + panic!( + "Creating handle to component {} failed: {err}", + type_name::<ComponentT>() + ); + }), + ) + } +} diff --git a/engine-ecs/src/sole.rs b/engine-ecs/src/sole.rs new file mode 100644 index 0000000..82e5e0f --- /dev/null +++ b/engine-ecs/src/sole.rs @@ -0,0 +1,104 @@ +use std::any::{Any, type_name}; +use std::fmt::Debug; +use std::marker::PhantomData; +use std::ops::{Deref, DerefMut}; +use std::sync::Arc; + +use crate::World; +use crate::lock::{Lock, WriteGuard}; +use crate::system::{Metadata as SystemMetadata, Param as SystemParam}; + +/// A type which has a single instance and is shared globally. +pub trait Sole: Any +{ + fn drop_last(&self) -> bool; + + fn as_any_mut(&mut self) -> &mut dyn Any; + + fn as_any(&self) -> &dyn Any; +} + +impl dyn Sole +{ + pub fn downcast_mut<Real: 'static>(&mut self) -> Option<&mut Real> + { + self.as_any_mut().downcast_mut() + } + + pub fn downcast_ref<Real: 'static>(&self) -> Option<&Real> + { + self.as_any().downcast_ref() + } +} + +impl Debug for dyn Sole +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + formatter.debug_struct("Sole").finish_non_exhaustive() + } +} + +/// Holds a reference to a globally shared singleton value. +#[derive(Debug)] +pub struct Single<'world, SoleT: Sole> +{ + sole: WriteGuard<'world, Box<dyn Sole>>, + _ph: PhantomData<SoleT>, +} + +impl<'world, SoleT> Single<'world, SoleT> +where + SoleT: Sole, +{ + pub(crate) fn new(sole: &'world Arc<Lock<Box<dyn Sole>>>) -> Self + { + Self { + sole: sole.write_nonblock().unwrap_or_else(|_| { + panic!( + "Failed to aquire read-write lock to single component {}", + type_name::<SoleT>() + ) + }), + _ph: PhantomData, + } + } +} + +impl<'world, SoleT> SystemParam<'world> for Single<'world, SoleT> +where + SoleT: Sole, +{ + type Input = (); + + fn new(world: &'world World, _system_metadata: &SystemMetadata) -> Self + { + let sole = world.data.sole_storage.get::<SoleT>().unwrap_or_else(|| { + panic!("Sole {} was not found in world", type_name::<SoleT>()) + }); + + Self::new(sole) + } +} + +impl<SoleT> Deref for Single<'_, SoleT> +where + SoleT: Sole, +{ + type Target = SoleT; + + fn deref(&self) -> &Self::Target + { + self.sole.downcast_ref().unwrap() + } +} + +impl<SoleT> DerefMut for Single<'_, SoleT> +where + SoleT: Sole, +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + self.sole.downcast_mut().unwrap() + } +} diff --git a/engine-ecs/src/stats.rs b/engine-ecs/src/stats.rs new file mode 100644 index 0000000..2fe731b --- /dev/null +++ b/engine-ecs/src/stats.rs @@ -0,0 +1,8 @@ +use crate::Sole; + +#[derive(Debug, Default, Sole)] +#[non_exhaustive] +pub struct Stats +{ + pub current_tick: u64, +} diff --git a/engine-ecs/src/system.rs b/engine-ecs/src/system.rs new file mode 100644 index 0000000..38e480d --- /dev/null +++ b/engine-ecs/src/system.rs @@ -0,0 +1,157 @@ +use std::fmt::Debug; + +use seq_macro::seq; + +use crate::error::Error; +use crate::uid::Uid; +use crate::{Component, World}; + +pub mod initializable; +pub mod observer; +pub mod stateful; + +/// Metadata of a system. +#[derive(Debug)] +#[non_exhaustive] +pub struct Metadata +{ + pub ent_id: Uid, +} + +pub trait System<'world, Impl>: 'static +{ + type Callbacks: Callbacks; + + fn finish(self) -> (TypeErased, Self::Callbacks); +} + +macro_rules! impl_system { + ($c: tt) => { + seq!(I in 0..$c { + impl<'world, Func, Ret, #(TParam~I,)*> System<'world, fn(#(TParam~I,)*) -> Ret> + for Func + where + Func: Fn(#(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world, Input = ()>,)* + { + type Callbacks = NoCallbacks; + + fn finish(self) -> (TypeErased, Self::Callbacks) + { + #![allow(unused)] + + let type_erased = TypeErased { + run: Box::new(move |world, metadata| { + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let world = unsafe { &*std::ptr::from_ref(world) }; + + self(#({ + TParam~I::new(world, &metadata) + },)*).into_result() + }), + name: std::any::type_name::<Self>() + }; + + (type_erased, NoCallbacks) + } + } + }); + }; +} + +seq!(C in 0..16 { + impl_system!(C); +}); + +pub trait Into<'world, Impl> +{ + type System; + + fn into_system(self) -> Self::System; +} + +pub struct TypeErased +{ + run: Box<TypeErasedRunFn>, + name: &'static str, +} + +impl TypeErased +{ + /// Runs the system. + /// + /// # Safety + /// `world_data` must live at least as long as the [`World`] the system belongs to. + pub unsafe fn run(&self, world: &World, metadata: Metadata) -> Result<(), Error> + { + (self.run)(world, metadata) + } + + pub fn name(&self) -> &'static str + { + self.name + } +} + +impl Debug for TypeErased +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + formatter.debug_struct("TypeErased").finish_non_exhaustive() + } +} + +pub trait ReturnValue +{ + fn into_result(self) -> Result<(), Error>; +} + +impl ReturnValue for () +{ + fn into_result(self) -> Result<(), Error> + { + Ok(()) + } +} + +impl ReturnValue for Result<(), Error> +{ + fn into_result(self) -> Result<(), Error> + { + self + } +} + +/// A parameter to a [`System`]. +pub trait Param<'world> +{ + type Input; + + fn new(world: &'world World, system_metadata: &Metadata) -> Self; +} + +/// A type which can be used as input to a [`System`]. +pub trait Input: 'static {} + +pub trait Callbacks +{ + fn on_created(&mut self, world: &mut World, metadata: Metadata); +} + +pub struct NoCallbacks; + +impl Callbacks for NoCallbacks +{ + fn on_created(&mut self, _world: &mut World, _metadata: Metadata) {} +} + +#[derive(Debug, Component)] +pub(crate) struct SystemComponent +{ + pub(crate) system: TypeErased, +} + +/// Function in [`TypeErased`] used to run the system. +type TypeErasedRunFn = dyn Fn(&World, Metadata) -> Result<(), Error>; diff --git a/engine-ecs/src/system/initializable.rs b/engine-ecs/src/system/initializable.rs new file mode 100644 index 0000000..b6ec8e8 --- /dev/null +++ b/engine-ecs/src/system/initializable.rs @@ -0,0 +1,131 @@ +use std::marker::PhantomData; + +use seq_macro::seq; + +use crate::system::{Input, Param as SystemParam, System}; +use crate::tuple::{Reduce as TupleReduce, ReduceElement as TupleReduceElement, Tuple}; + +/// A initializable system. +pub trait Initializable<'world, Impl>: System<'world, Impl> +{ + type Inputs; + + #[must_use] + fn initialize(self, inputs: Self::Inputs) -> Self; +} + +pub trait Param<'world, SystemT>: SystemParam<'world> +{ + fn initialize(system: &mut SystemT, input: Self::Input); +} + +pub struct ParamTupleFilter<'world, SystemT> +{ + _pd: PhantomData<(&'world (), SystemT)>, +} + +impl<'world, SystemT, ParamT, Accumulator> + TupleReduceElement<Accumulator, ParamTupleFilter<'world, SystemT>> for ParamT +where + ParamT: SystemParam< + 'world, + Input: AppendInitializableParam<'world, Accumulator, ParamT, SystemT>, + >, + Accumulator: Tuple, +{ + type Return = <ParamT::Input as AppendInitializableParam< + 'world, + Accumulator, + ParamT, + SystemT, + >>::Return; +} + +pub trait AppendInitializableParam<'world, Accumulator, ParamT, SystemT> +{ + type Return; +} + +impl<'world, InputT, ParamT, Accumulator, SystemT> + AppendInitializableParam<'world, Accumulator, ParamT, SystemT> for InputT +where + InputT: Input, + Accumulator: Tuple, + ParamT: Param<'world, SystemT>, +{ + type Return = Accumulator::WithElementAtEnd<ParamT>; +} + +impl<ParamT, Accumulator, SystemT> + AppendInitializableParam<'_, Accumulator, ParamT, SystemT> for () +where + Accumulator: Tuple, +{ + type Return = Accumulator; +} + +pub trait ParamTuple<'world, SystemT> +{ + type Inputs; + + fn initialize_all(system: &mut SystemT, inputs: Self::Inputs); +} + +macro_rules! impl_initializable_param_tuple { + ($c: tt) => { + seq!(I in 0..$c { + impl<'world, SystemT, #(Param~I,)*> ParamTuple<'world, SystemT> + for (#(Param~I,)*) + where + #(Param~I: Param<'world, SystemT>,)* + { + type Inputs = (#(Param~I::Input,)*); + + fn initialize_all( + system: &mut SystemT, + inputs: Self::Inputs, + ) { + #( + <Param~I as Param<'world, SystemT>>::initialize( + system, + inputs.I + ); + )* + } + } + }); + }; +} + +seq!(C in 1..16 { + impl_initializable_param_tuple!(C); +}); + +impl<SystemT> ParamTuple<'_, SystemT> for () +{ + type Inputs = (); + + fn initialize_all(_system: &mut SystemT, _inputs: Self::Inputs) {} +} + +/// A tuple of system parameters that may or may not be initializable. +pub trait MaybeInitializableParamTuple<'world, SystemT> +{ + /// A tuple of the inputs of the initializable system parameters in this tuple. + type Inputs; + + fn init_initializable(system: &mut SystemT, inputs: Self::Inputs); +} + +impl<'world, SystemT, Params> MaybeInitializableParamTuple<'world, SystemT> for Params +where + Params: + TupleReduce<ParamTupleFilter<'world, SystemT>, Out: ParamTuple<'world, SystemT>>, +{ + type Inputs = <Params::Out as ParamTuple<'world, SystemT>>::Inputs; + + fn init_initializable(system: &mut SystemT, inputs: Self::Inputs) + { + Params::Out::initialize_all(system, inputs); + } +} diff --git a/engine-ecs/src/system/observer.rs b/engine-ecs/src/system/observer.rs new file mode 100644 index 0000000..1ad7496 --- /dev/null +++ b/engine-ecs/src/system/observer.rs @@ -0,0 +1,278 @@ +use std::any::type_name; +use std::fmt::Debug; +use std::marker::PhantomData; +use std::mem::transmute; +use std::slice::Iter as SliceIter; + +use seq_macro::seq; + +use crate::entity::Handle as EntityHandle; +use crate::error::Error; +use crate::event::Emitted as EmittedEvent; +use crate::pair::Pair; +use crate::system::{ + Metadata, + NoCallbacks, + Param, + ReturnValue as SystemReturnValue, + System, + TypeErased as TypeErasedSystem, +}; +use crate::uid::Uid; +use crate::util::Array; +use crate::{Component, World}; + +pub trait Observed +{ + type Events: Array<Pair<Uid, Uid>>; + + fn events() -> Self::Events; +} + +impl<Relation, Target> Observed for Pair<Relation, Target> +where + Relation: Component, + Target: Component, +{ + type Events = [Pair<Uid, Uid>; 1]; + + fn events() -> Self::Events + { + [Pair::builder() + .relation::<Relation>() + .target::<Target>() + .build()] + } +} + +/// Observer system. +pub trait Observer<'world, Impl>: System<'world, Impl> +{ + type ObservedEvents: Array<Pair<Uid, Uid>>; + + fn observed_events() -> Self::ObservedEvents; + + fn finish_observer(self) -> (WrapperComponent, Self::Callbacks); +} + +pub struct Observe<'world, ObservedT: Observed> +{ + _pd: PhantomData<ObservedT>, + world: &'world World, + emitted_event: EmittedEvent<'world>, +} + +impl<'world, ObservedT: Observed> Observe<'world, ObservedT> +{ + pub fn new(world: &'world World, emitted_event: EmittedEvent<'world>) -> Self + { + Self { + _pd: PhantomData, + world, + emitted_event, + } + } + + #[must_use] + pub fn event(&self) -> Uid + { + self.emitted_event.event + } +} + +impl<ObservedT: Observed> Observe<'_, ObservedT> +{ + #[must_use] + pub fn iter(&self) -> ObserveIter<'_, ObservedT> + { + ObserveIter { + world: self.world, + inner: self.emitted_event.match_ids.iter(), + _pd: PhantomData, + } + } +} + +impl<'a, ObservedT: Observed> IntoIterator for &'a Observe<'_, ObservedT> +{ + type IntoIter = ObserveIter<'a, ObservedT>; + type Item = <Self::IntoIter as Iterator>::Item; + + fn into_iter(self) -> Self::IntoIter + { + self.iter() + } +} + +pub struct ObserveIter<'observe, ObservedT: Observed> +{ + world: &'observe World, + inner: SliceIter<'observe, Uid>, + _pd: PhantomData<ObservedT>, +} + +impl<'observe, ObservedT: Observed> Iterator for ObserveIter<'observe, ObservedT> +{ + type Item = EventMatch<'observe, ObservedT>; + + fn next(&mut self) -> Option<Self::Item> + { + let match_id = *self.inner.next()?; + + Some(EventMatch { + world: self.world, + id: match_id, + _pd: PhantomData, + }) + } +} + +/// A event match. +#[derive(Debug)] +pub struct EventMatch<'world, ObservedT: Observed> +{ + world: &'world World, + id: Uid, + _pd: PhantomData<ObservedT>, +} + +impl<'world, ObservedT: Observed> EventMatch<'world, ObservedT> +{ + #[must_use] + pub fn entity_id(&self) -> Uid + { + self.id + } + + /// Attempts to get the entity with the id of this match. + #[must_use] + pub fn try_get_entity(&self) -> Option<EntityHandle<'world>> + { + self.world.get_entity(self.id) + } +} + +macro_rules! impl_observer { + ($c: tt) => { + seq!(I in 0..$c { + impl<'world, ObservedT, Func, Ret, #(TParam~I,)*> System< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Func + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: SystemReturnValue, + #(TParam~I: Param<'world, Input = ()>,)* + { + type Callbacks = NoCallbacks; + + fn finish(self) -> (TypeErasedSystem, NoCallbacks) + { + const { + panic!("Observers cannot be used as regular systems"); + } + } + } + + impl<'world, ObservedT, Func, Ret, #(TParam~I,)*> Observer< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Func + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: SystemReturnValue, + #(TParam~I: Param<'world, Input = ()>,)* + { + type ObservedEvents = ObservedT::Events; + + fn observed_events() -> Self::ObservedEvents + { + ObservedT::events() + } + + fn finish_observer(self) -> (WrapperComponent, NoCallbacks) + { + #[allow(unused)] + + let wrapper_comp = WrapperComponent::new( + move |world, metadata, emitted_event| { + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let world = unsafe { &*std::ptr::from_ref(world) }; + + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let emitted_event = unsafe { + transmute::<EmittedEvent<'_>, EmittedEvent<'_>>( + emitted_event + ) + }; + + self(Observe::new(world, emitted_event), #({ + TParam~I::new(world, &metadata) + },)*).into_result() + }, + type_name::<Func>() + ); + + (wrapper_comp, NoCallbacks) + } + } + }); + }; +} + +seq!(C in 0..16 { + impl_observer!(C); +}); + +#[derive(Component)] +pub struct WrapperComponent +{ + run: Box<RunFn>, + name: &'static str, +} + +impl WrapperComponent +{ + pub fn new( + run: impl Fn(&World, Metadata, EmittedEvent<'_>) -> Result<(), Error> + 'static, + name: &'static str, + ) -> Self + { + Self { run: Box::new(run), name } + } + + /// Runs the observer system. + /// + /// # Safety + /// `world` must live at least as long as the [`World`] the system belongs to. + pub unsafe fn run( + &self, + world: &World, + metadata: Metadata, + emitted_event: EmittedEvent<'_>, + ) -> Result<(), Error> + { + (self.run)(world, metadata, emitted_event) + } + + pub fn name(&self) -> &'static str + { + self.name + } +} + +impl Debug for WrapperComponent +{ + fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result + { + formatter + .debug_struct("WrapperComponent") + .finish_non_exhaustive() + } +} + +type RunFn = dyn Fn(&World, Metadata, EmittedEvent<'_>) -> Result<(), Error>; diff --git a/engine-ecs/src/system/stateful.rs b/engine-ecs/src/system/stateful.rs new file mode 100644 index 0000000..3e0076a --- /dev/null +++ b/engine-ecs/src/system/stateful.rs @@ -0,0 +1,269 @@ +use std::any::type_name; +use std::mem::transmute; + +use seq_macro::seq; + +use crate::World; +use crate::component::Parts as ComponentParts; +use crate::component::local::SystemWithLocalComponents; +use crate::event::Emitted as EmittedEvent; +use crate::system::initializable::{Initializable, MaybeInitializableParamTuple}; +use crate::system::observer::{ + Observe, + Observed, + Observer, + WrapperComponent as ObserverWrapperComponent, +}; +use crate::system::{ + Into as IntoSystem, + Metadata, + Param, + ReturnValue, + System, + TypeErased, +}; + +/// A stateful system. +pub struct Stateful<Func> +{ + func: Func, + local_components: Vec<ComponentParts>, +} + +macro_rules! impl_system { + ($c: tt) => { + seq!(I in 0..$c { + impl<'world, Func, Ret, #(TParam~I,)*> + System<'world, fn(#(TParam~I,)*) -> Ret> for Stateful<Func> + where + Func: Fn(#(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world, Input: 'static>,)* + { + type Callbacks = Callbacks; + + fn finish(self) -> (TypeErased, Self::Callbacks) + { + let Self { func, local_components } = self; + + let callbacks = Callbacks { local_components }; + + let type_erased = TypeErased { + run: Box::new(move |world, metadata| { + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let world = unsafe { &*std::ptr::from_ref(world) }; + + func(#({ + TParam~I::new(&world, &metadata) + },)*); + + Ok(()) + }), + name: type_name::<Func>() + }; + + + (type_erased, callbacks) + } + } + + impl<'world, Func, Ret, #(TParam~I,)*> + Initializable<'world, fn(#(TParam~I,)*) -> Ret> for Stateful<Func> + where + Func: Fn(#(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world, Input: 'static>,)* + (#(TParam~I,)*): MaybeInitializableParamTuple<'world, Self> + { + type Inputs = < + (#(TParam~I,)*) as MaybeInitializableParamTuple<'world, Self> + >::Inputs; + + fn initialize(mut self, inputs: Self::Inputs) -> Self + { + init_initializable_params::<_, (#(TParam~I,)*)>(&mut self, inputs); + + self + } + } + + impl<'world, Func, Ret, #(TParam~I,)*> + IntoSystem<'world, fn(#(TParam~I,)*) -> Ret> for Func + where + Func: Fn(#(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world>,)* + { + type System = Stateful<Func>; + + fn into_system(self) -> Self::System + { + Self::System { + func: self, + local_components: Vec::new(), // TODO: Use Vec::with_capacity + } + } + } + }); + }; +} + +seq!(C in 1..16 { + impl_system!(C); +}); + +impl<Func> SystemWithLocalComponents for Stateful<Func> +{ + fn add_local_component(&mut self, component_parts: ComponentParts) + { + self.local_components.push(component_parts); + } +} + +#[derive(Debug)] +pub struct Callbacks +{ + local_components: Vec<ComponentParts>, +} + +impl crate::system::Callbacks for Callbacks +{ + fn on_created(&mut self, world: &mut World, metadata: Metadata) + { + for local_comp_parts in self.local_components.drain(..) { + world.add_component(metadata.ent_id, local_comp_parts); + } + } +} + +fn init_initializable_params<'world, SystemT, Params>( + system: &mut SystemT, + inputs: Params::Inputs, +) where + Params: MaybeInitializableParamTuple<'world, SystemT>, +{ + Params::init_initializable(system, inputs); +} + +macro_rules! impl_observer { + ($c: tt) => { + seq!(I in 0..$c { + impl<'world, ObservedT, Func, Ret, #(TParam~I,)*> System< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Stateful<Func> + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world>,)* + { + type Callbacks = Callbacks; + + fn finish(self) -> (TypeErased, Callbacks) + { + unimplemented!(); + } + } + + impl<'world, ObservedT, Func, Ret, #(TParam~I,)*> Initializable< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Stateful<Func> + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world>,)* + (#(TParam~I,)*): MaybeInitializableParamTuple<'world, Self> + { + type Inputs = < + (#(TParam~I,)*) as MaybeInitializableParamTuple<'world, Self> + >::Inputs; + + fn initialize(mut self, inputs: Self::Inputs) -> Self + { + init_initializable_params::<_, (#(TParam~I,)*)>(&mut self, inputs); + + self + } + } + + impl<'world, ObservedT, Func, Ret, #(TParam~I,)*> Observer< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Stateful<Func> + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world>,)* + { + type ObservedEvents = ObservedT::Events; + + fn observed_events() -> Self::ObservedEvents + { + ObservedT::events() + } + + fn finish_observer(self) -> (ObserverWrapperComponent, Callbacks) + { + #![allow(unused)] + + let Self { func, local_components } = self; + + let callbacks = Callbacks { local_components }; + + let wrapper_comp = ObserverWrapperComponent::new( + move |world, metadata, emitted_event| { + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let world = unsafe { &*std::ptr::from_ref(world) }; + + // SAFETY: The caller of TypeErased::run ensures the lifetime + // is correct + let emitted_event = unsafe { + transmute::<EmittedEvent<'_>, EmittedEvent<'_>>( + emitted_event + ) + }; + + func(Observe::new(world, emitted_event), #({ + TParam~I::new(world, &metadata) + },)*).into_result() + }, + type_name::<Func>() + ); + + (wrapper_comp, callbacks) + } + } + + impl<'world, Func, Ret, ObservedT, #(TParam~I,)*> IntoSystem< + 'world, + fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + > for Func + where + ObservedT: Observed, + Func: Fn(Observe<'world, ObservedT>, #(TParam~I,)*) -> Ret + 'static, + Ret: ReturnValue, + #(TParam~I: Param<'world>,)* + { + type System = Stateful<Func>; + + fn into_system(self) -> Stateful<Func> + { + Stateful { + func: self, + local_components: Vec::new(), // TODO: Use Vec::with_capacity + } + } + } + }); + }; +} + +seq!(C in 0..16 { + impl_observer!(C); +}); diff --git a/engine-ecs/src/tuple.rs b/engine-ecs/src/tuple.rs new file mode 100644 index 0000000..def25a0 --- /dev/null +++ b/engine-ecs/src/tuple.rs @@ -0,0 +1,238 @@ +use std::any::TypeId; + +use paste::paste; +use seq_macro::seq; +use util_macros::sub; + +pub trait Tuple: sealed::Sealed +{ + /// `Self` with the given type added as the last element. + /// + /// `(String, i32, u8)::WithElementAtEnd<Path> = (String, i32, u8, Path)` + /// + /// # Important note + /// If `Self` has 16 elements, this will be `()`. The reason for this is that the + /// `Tuple` trait is only implemented for tuples with up to and including 16 elements. + type WithElementAtEnd<NewElem>: Tuple; + + /// `Self` without the last element. + /// + /// `(u16, AtomicU8)::WithoutLastElement = (u16,)` + type WithoutLastElement: Tuple; + + /// The last element of `Self`. + type LastElement; + + /// Self with all elements wrapped in [`Option`]. + type InOptions: Tuple; + + /// Pops the last element from this tuple, returning the new tuple and the popped + /// element. + fn pop_last(self) -> (Self::WithoutLastElement, Self::LastElement); + + /// Converts this tuple so that all elements are wrapped in [`Option`]. + fn into_in_options(self) -> Self::InOptions; +} + +/// A tuple with element types that all have the lifetime `'static`. +pub trait WithAllElemLtStatic: Tuple + sealed::Sealed +{ + /// Returns the element at the given index. + fn get_mut<Element: 'static>(&mut self, index: usize) -> Option<&mut Element>; +} + +/// Using the type system, reduces the elements of a tuple to a single one. Each element +/// determines itself how it is handled. +pub trait Reduce<Operation> +{ + type Out; +} + +pub trait ReduceElement<Accumulator, Operation> +{ + type Return; +} + +macro_rules! tuple_reduce_elem_tuple { + (overflow) => { + () + }; + + ($index: tt) => { + paste! { + [<Elem $index>]::Return + } + }; +} + +macro_rules! elem_type_by_index { + (overflow) => { + () + }; + + ($index: tt) => { + paste! { + [<Elem $index>] + } + }; +} + +macro_rules! elem_by_index { + (overflow) => { + () + }; + + ($index: tt, $self: ident) => { + $self.$index + }; +} + +macro_rules! all_except_last { + (start $($rest: tt)*) => { + all_except_last!(@[] $($rest)*) + }; + + (@[$($included_elem: ident,)*] $elem: ident $($rest: tt)+) => { + all_except_last!(@[$($included_elem,)* $elem,] $($rest)*) + }; + + (@[$($included_elem: expr,)*] ($elem: expr) $($rest: tt)+) => { + all_except_last!(@[$($included_elem,)* $elem,] $($rest)*) + }; + + (@[$($included_elem: ident,)*] $elem: ident) => { + ($($included_elem,)*) + }; + + (@[$($included_elem: expr,)*] $elem: expr) => { + ($($included_elem,)*) + }; + + (@[]) => { + () + }; +} + +macro_rules! impl_tuple_traits { + ($cnt: tt) => { + seq!(I in 0..$cnt { + impl<#(Elem~I,)*> Tuple for (#(Elem~I,)*) + { + type WithElementAtEnd<NewElem> = (#(Elem~I,)* NewElem,); + + type WithoutLastElement = all_except_last!(start #(Elem~I)*); + + type LastElement = sub!($cnt - 1, elem_type_by_index); + + type InOptions = (#(Option<Elem~I>,)*); + + fn pop_last(self) -> (Self::WithoutLastElement, Self::LastElement) + { + ( + all_except_last!(start #((self.I))*), + sub!($cnt - 1, elem_by_index, (self)) + ) + } + + fn into_in_options(self) -> Self::InOptions + { + #![allow(clippy::unused_unit)] + (#(Some(self.I),)*) + } + } + + impl<#(Elem~I: 'static,)*> WithAllElemLtStatic for (#(Elem~I,)*) + { + fn get_mut<Element: 'static>(&mut self, index: usize) -> Option<&mut Element> + { + match index { + #( + I => { + assert!(TypeId::of::<Element>() == TypeId::of::<Elem~I>()); + + // SAFETY: It is checked above that the type is correct + Some(unsafe { &mut *(&raw mut self.I).cast::<Element>() }) + } + )* + _ => None + } + } + } + + impl<#(Elem~I,)*> sealed::Sealed for (#(Elem~I,)*) + { + } + + paste! { + impl<Operation, #(Elem~I,)*> Reduce<Operation> for (#(Elem~I,)*) + where + #( + Elem~I: ReduceElement< + sub!(I - 1, tuple_reduce_elem_tuple), Operation + >, + )* + { + type Out = sub!($cnt - 1, tuple_reduce_elem_tuple); + } + } + }); + }; +} + +seq!(N in 0..16 { + impl_tuple_traits!(N); +}); + +seq!(I in 0..16 { + impl<#(Elem~I,)*> Tuple for (#(Elem~I,)*) + { + type WithElementAtEnd<NewElem> = (); + + type WithoutLastElement = all_except_last!(start #(Elem~I)*); + + type LastElement = Elem15; + + type InOptions = (#(Option<Elem~I>,)*); + + fn pop_last(self) -> (Self::WithoutLastElement, Self::LastElement) + { + ( + all_except_last!(start #((self.I))*), + self.15 + ) + } + + fn into_in_options(self) -> Self::InOptions + { + #![allow(clippy::unused_unit)] + (#(Some(self.I),)*) + } + } + + impl<#(Elem~I: 'static,)*> WithAllElemLtStatic for (#(Elem~I,)*) + { + fn get_mut<Element: 'static>(&mut self, index: usize) -> Option<&mut Element> + { + match index { + #( + I => { + assert!(TypeId::of::<Element>() == TypeId::of::<Elem~I>()); + + // SAFETY: It is checked above that the type is correct + Some(unsafe { &mut *(&raw mut self.I).cast::<Element>() }) + } + )* + _ => None + } + } + } + + impl<#(Elem~I,)*> sealed::Sealed for (#(Elem~I,)*) + { + } +}); + +mod sealed +{ + pub trait Sealed {} +} diff --git a/engine-ecs/src/uid.rs b/engine-ecs/src/uid.rs new file mode 100644 index 0000000..bb393a1 --- /dev/null +++ b/engine-ecs/src/uid.rs @@ -0,0 +1,261 @@ +use std::fmt::{Debug, Display, Formatter}; +use std::mem::transmute; +use std::sync::atomic::{AtomicU32, Ordering}; + +use seq_macro::seq; + +use crate::component::Component; +use crate::util::{gen_mask_64, Array, BitMask, NumberExt}; + +static NEXT: AtomicU32 = AtomicU32::new(Uid::FIRST_UNIQUE_ID); + +static WILDCARD_ID: u32 = 1; + +const ID_BITS: BitMask<u64> = BitMask::new(gen_mask_64!(32..=63)); +const RELATION_BITS: BitMask<u64> = BitMask::new(gen_mask_64!(6..=31)); +const KIND_BITS: BitMask<u64> = BitMask::new(gen_mask_64!(0..=1)); + +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] +#[repr(u8)] +pub enum Kind +{ + Pair = 3, + Entity = 2, + Component = 1, +} + +/// A unique identifier. +#[derive(Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)] +pub struct Uid +{ + inner: u64, +} + +impl Uid +{ + /// The id part of the first unique `Uid`. The ids `0..Uid::FIRST_UNIQUE_ID` are + /// reserved. + pub const FIRST_UNIQUE_ID: u32 = 5; + + /// Returns a new unique entity/component ID. + pub fn new_unique(kind: Kind) -> Self + { + let id = NEXT.fetch_add(1, Ordering::Relaxed); + + Self { + inner: ID_BITS.field_prep(u64::from(id)) | KIND_BITS.field_prep(kind as u64), + } + } + + #[must_use] + pub fn wildcard() -> Self + { + Self { + inner: ID_BITS.field_prep(u64::from(WILDCARD_ID)) + | KIND_BITS.field_prep(Kind::Component as u64), + } + } + + /// Returns a new pair UID. + /// + /// # Panics + /// Will panic if either the given relation or target is a pair UID. + #[must_use] + pub fn new_pair(params: &PairParams) -> Self + { + assert_ne!( + params.relation.kind(), + Kind::Pair, + "Pair relation cannot be a pair" + ); + + assert_ne!( + params.target.kind(), + Kind::Pair, + "Pair target cannot be a pair" + ); + + Self { + inner: ID_BITS.field_prep(u64::from(params.target.id())) + | RELATION_BITS.field_prep(u64::from(params.relation.id())) + | KIND_BITS.field_prep(Kind::Pair as u64), + } + } + + #[must_use] + pub fn id(&self) -> u32 + { + let Ok(id) = u32::try_from(self.inner.field_get(ID_BITS)) else { + unreachable!("Uid id does not fit in u32"); + }; + + id + } + + #[must_use] + pub fn kind(&self) -> Kind + { + let Ok(kind) = u8::try_from(self.inner.field_get(KIND_BITS)) else { + unreachable!("Uid kind does not fit in u8"); + }; + + // SAFETY: The kind bits cannot be invalid since they are set using the Kind enum + // in the new_unique function + unsafe { transmute::<u8, Kind>(kind) } + } + + /// If this `Uid` is a pair, returns the relation as a component `Uid`. + /// + /// # Panics + /// Will panic if this `Uid` is not a pair. + #[must_use] + pub fn relation_component(&self) -> Self + { + assert_eq!(self.kind(), Kind::Pair, "Uid is not a pair"); + + Self { + inner: ID_BITS.field_prep(u64::from(self.relation())) + | KIND_BITS.field_prep(Kind::Component as u64), + } + } + + #[must_use] + pub fn has_same_relation_as(&self, other: Self) -> bool + { + self.relation() == other.relation() + } + + /// If this `Uid` is a pair, returns the relation as a entity `Uid`. + /// + /// # Panics + /// Will panic if this `Uid` is not a pair. + #[must_use] + pub fn relation_entity(&self) -> Self + { + assert_eq!(self.kind(), Kind::Pair, "Uid is not a pair"); + + Self { + inner: ID_BITS.field_prep(u64::from(self.relation())) + | KIND_BITS.field_prep(Kind::Entity as u64), + } + } + + /// If this `Uid` is a pair, returns the target as a component `Uid`. + /// + /// # Panics + /// Will panic if this `Uid` is not a pair. + #[must_use] + pub fn target_component(&self) -> Self + { + assert_eq!(self.kind(), Kind::Pair, "Uid is not a pair"); + + Self { + inner: ID_BITS.field_prep(u64::from(self.id())) + | KIND_BITS.field_prep(Kind::Component as u64), + } + } + + /// If this `Uid` is a pair, returns the target as a entity `Uid`. + /// + /// # Panics + /// Will panic if this `Uid` is not a pair. + #[must_use] + pub fn target_entity(&self) -> Self + { + assert_eq!(self.kind(), Kind::Pair, "Uid is not a pair"); + + Self { + inner: ID_BITS.field_prep(u64::from(self.id())) + | KIND_BITS.field_prep(Kind::Entity as u64), + } + } + + fn relation(self) -> u32 + { + let Ok(relation) = u32::try_from(self.inner.field_get(RELATION_BITS)) else { + unreachable!("Uid relation does not fit in u32"); + }; + + relation + } +} + +impl Debug for Uid +{ + fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result + { + formatter + .debug_struct("Uid") + .field("id", &self.id()) + .field("kind", &self.kind()) + .finish_non_exhaustive() + } +} + +impl Display for Uid +{ + fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result + { + if self.kind() == Kind::Pair { + return write!( + formatter, + "({}, {})", + self.relation(), + self.target_component() + ); + } + + if *self == Uid::wildcard() { + return write!(formatter, "*"); + } + + write!(formatter, "{}", self.id()) + } +} + +#[derive(Debug, Clone)] +pub struct PairParams +{ + pub relation: Uid, + pub target: Uid, +} + +pub trait With +{ + fn uid() -> Uid; +} + +impl<ComponentT: Component> With for ComponentT +{ + fn uid() -> Uid + { + Self::id() + } +} + +pub trait WithUidTuple +{ + type UidsArray: Array<Uid>; + + fn uids() -> Self::UidsArray; +} + +macro_rules! impl_with_uid_tuple { + ($c: tt) => { + seq!(I in 0..=$c { + impl<#(WithUid~I: With,)*> WithUidTuple for (#(WithUid~I,)*) + { + type UidsArray = [Uid; $c + 1]; + + fn uids() -> Self::UidsArray + { + [#(WithUid~I::uid(),)*] + } + } + }); + }; +} + +seq!(C in 0..=16 { + impl_with_uid_tuple!(C); +}); diff --git a/engine-ecs/src/util.rs b/engine-ecs/src/util.rs new file mode 100644 index 0000000..27e9748 --- /dev/null +++ b/engine-ecs/src/util.rs @@ -0,0 +1,415 @@ +use std::hash::Hash; +use std::mem::transmute; +use std::ops::{BitAnd, Deref}; + +use hashbrown::HashMap; + +pub(crate) mod array_vec; + +pub trait VecExt<Item> +{ + fn insert_at_part_pt_by_key<Key>( + &mut self, + item: Item, + func: impl FnMut(&Item) -> &Key, + ) where + Key: Ord; +} + +impl<Item> VecExt<Item> for Vec<Item> +{ + fn insert_at_part_pt_by_key<Key>( + &mut self, + item: Item, + mut func: impl FnMut(&Item) -> &Key, + ) where + Key: Ord, + { + let key = func(&item); + + let insert_index = self.partition_point(|other_item| func(other_item) <= key); + + self.insert(insert_index, item); + } +} + +pub trait StreamingIterator +{ + type Item<'a> + where + Self: 'a; + + fn streaming_next(&mut self) -> Option<Self::Item<'_>>; + + fn streaming_map<NewItem, Func>(self, func: Func) -> StreamingMap<Self, Func> + where + Self: Sized, + Func: FnMut(Self::Item<'_>) -> NewItem, + { + StreamingMap { iter: self, func } + } + + fn streaming_find<'this, Predicate>( + &'this mut self, + mut predicate: Predicate, + ) -> Option<Self::Item<'this>> + where + Self: Sized, + Predicate: FnMut(&Self::Item<'this>) -> bool, + { + while let Some(item) = unsafe { + transmute::<Option<Self::Item<'_>>, Option<Self::Item<'_>>>( + self.streaming_next(), + ) + } { + if predicate(&item) { + return Some(item); + } + } + + None + } +} + +pub struct StreamingMap<Iter, Func> +{ + iter: Iter, + func: Func, +} + +impl<Iter, Func, Item> StreamingIterator for StreamingMap<Iter, Func> +where + Iter: StreamingIterator, + Func: FnMut(Iter::Item<'_>) -> Item, +{ + type Item<'a> + = Item + where + Iter: 'a, + Func: 'a; + + fn streaming_next(&mut self) -> Option<Self::Item<'_>> + { + Some((self.func)(self.iter.streaming_next()?)) + } +} + +#[derive(Debug)] +pub enum BorrowedOrOwned<'a, Value> +{ + Borrowned(&'a Value), + Owned(Value), +} + +impl<Value> Deref for BorrowedOrOwned<'_, Value> +{ + type Target = Value; + + fn deref(&self) -> &Self::Target + { + match self { + Self::Borrowned(value) => value, + Self::Owned(value) => value, + } + } +} + +#[derive(Debug, Clone)] +pub enum Either<A, B> +{ + A(A), + B(B), +} + +impl<A, B> Iterator for Either<A, B> +where + A: Iterator, + B: Iterator<Item = A::Item>, +{ + type Item = A::Item; + + fn next(&mut self) -> Option<Self::Item> + { + match self { + Self::A(a) => a.next(), + Self::B(b) => b.next(), + } + } +} + +pub trait HashMapExt<Key, Value> +{ + /// Returns true if the keys are a subset of another [`HashMap`]'s keys, i.e., `other` + /// contains at least all the keys in `self`. + fn keys_is_subset(&self, other: &Self) -> bool; + + /// Returns true if the keys are a superset of another [`HashMap`]'s keys, i.e., + /// `self` contains at least all the keys in `other`. + fn keys_is_superset(&self, other: &Self) -> bool; +} + +impl<Key, Value> HashMapExt<Key, Value> for HashMap<Key, Value> +where + Key: Eq + Hash, +{ + fn keys_is_subset(&self, other: &Self) -> bool + { + if self.len() <= other.len() { + self.keys().all(|key| other.contains_key(key)) + } else { + false + } + } + + fn keys_is_superset(&self, other: &Self) -> bool + { + other.keys_is_subset(self) + } +} + +pub trait Array<Item>: + AsRef<[Item]> + + AsMut<[Item]> + + IntoIterator<Item = Item> + + Into<Vec<Item>> + + Sortable<Item = Item> + + sealed::Sealed +{ +} + +impl<Item, const CNT: usize> Array<Item> for [Item; CNT] {} + +impl<Item, const CNT: usize> sealed::Sealed for [Item; CNT] {} + +pub trait Sortable +{ + type Item; + + fn sort_by_key_b<Key, Func>(&mut self, func: Func) + where + Func: FnMut(&Self::Item) -> Key, + Key: Ord; +} + +impl<Item> Sortable for [Item] +{ + type Item = Item; + + fn sort_by_key_b<Key, Func>(&mut self, func: Func) + where + Func: FnMut(&Self::Item) -> Key, + Key: Ord, + { + self.sort_by_key(func); + } +} + +impl<Item, const LENGTH: usize> Sortable for [Item; LENGTH] +{ + type Item = Item; + + fn sort_by_key_b<Key, Func>(&mut self, func: Func) + where + Func: FnMut(&Self::Item) -> Key, + Key: Ord, + { + self.sort_by_key(func); + } +} + +impl<Item> Sortable for Vec<Item> +{ + type Item = Item; + + fn sort_by_key_b<Key, Func>(&mut self, func: Func) + where + Func: FnMut(&Self::Item) -> Key, + Key: Ord, + { + self.sort_by_key(func); + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct BitMask<Value> +{ + mask: Value, +} + +impl BitMask<u64> +{ + #[must_use] + pub const fn new(mask: u64) -> Self + { + Self { mask } + } + + #[must_use] + pub const fn value(self) -> u64 + { + self.mask + } + + /// Prepares a bitfield value in the range of bits specified by this `BitMask`. + #[must_use] + pub const fn field_prep(self, field_value: u64) -> u64 + { + debug_assert!(field_value < 1 << self.mask.count_ones()); + + ((field_value) << self.mask.trailing_zeros()) & (self.mask) + } +} + +impl BitAnd<u64> for BitMask<u64> +{ + type Output = u64; + + fn bitand(self, rhs: u64) -> Self::Output + { + self.mask & rhs + } +} + +pub trait NumberExt: Sized +{ + /// Returns a range of bits (field) specified by the provided [`BitMask`]. + #[must_use] + fn field_get(self, field_mask: BitMask<Self>) -> Self; +} + +impl NumberExt for u64 +{ + fn field_get(self, field_mask: BitMask<Self>) -> Self + { + (field_mask & self) >> field_mask.value().trailing_zeros() + } +} + +macro_rules! gen_mask_64 { + ($low: literal..=$high: literal) => { + const { + if $high <= $low { + panic!("High bit index cannot be less than or equal to low bit index"); + } + + (((!0u64) - (1u64 << ($low)) + 1) + & (!0u64 >> (u64::BITS as u64 - 1 - ($high)))) + } + }; +} + +pub(crate) use gen_mask_64; + +macro_rules! impl_multiple { + ( + $type: ident, + ($( + impl$(<$($generic: tt$(: $bound: ident)?),*>)? + _<$($lt_param: lifetime),*><$($type_param: ty),*> + $(($($extra_cb_arg: expr),*))? + ),*) + cb=( + type_params=($($ty_param_matcher: ident),*) + $(, $($extra_matcher: ident),+)? + ) => { + $($item_tt: tt)* + } + ) => { + const _: () = { + $crate::util::impl_multiple!( + @(make_gen_item_macro) + _gen_multiple_impl_item, + ($($ty_param_matcher),*), + ($($($extra_matcher),+)?), + ($($item_tt)*) + ); + + $( + impl $(<$($generic$(: $bound)?,)*>)? $type<$($lt_param,)* $($type_param),*> + { + _gen_multiple_impl_item!( + type_params=($($type_param),*), + $($($extra_cb_arg),*)? + ); + } + )* + }; + }; + + ( + @(make_gen_item_macro) + $name: ident, + ($($ty_param_matcher: ident),*), + ($($extra_matcher: ident),*), + ($($transcriber: tt)*) + ) => { + $crate::util::impl_multiple!( + @(make_gen_item_macro) + ($), + $name, + ($($ty_param_matcher),*), + ($($extra_matcher),*), + ($($transcriber)*) + ); + }; + + ( + @(make_gen_item_macro) + ($dollar: tt), + $name: ident, + ($($ty_param_matcher: ident),*), + ($($extra_matcher: ident),*), + ($($transcriber: tt)*) + ) => { + $crate::util::impl_multiple!( + @(make_gen_item_macro) + $name, + ( + type_params=($($dollar$ty_param_matcher: ty),*), + $($dollar$extra_matcher: expr),* + ) => { + $($transcriber)* + } + ); + }; + + (@(make_gen_item_macro) $name: ident, $($rule: tt)*) => { + macro_rules! $name { + $($rule)* + } + }; +} + +pub(crate) use impl_multiple; + +mod sealed +{ + pub trait Sealed {} +} + +#[cfg(test)] +mod tests +{ + + use super::BitMask; + use crate::util::NumberExt; + + #[test] + fn field_get_works() + { + assert_eq!(0b11011u64.field_get(BitMask::new(0b11100)), 0b00110); + } + + #[test] + fn bitmask_field_prep_works() + { + assert_eq!(BitMask::new(0b11000).field_prep(3), 0b11000); + } + + #[test] + #[should_panic] + fn bitmask_field_prep_too_large_value_panics() + { + let _ = BitMask::new(0b001110).field_prep(9); + } +} diff --git a/engine-ecs/src/util/array_vec.rs b/engine-ecs/src/util/array_vec.rs new file mode 100644 index 0000000..5d0aac9 --- /dev/null +++ b/engine-ecs/src/util/array_vec.rs @@ -0,0 +1,131 @@ +use std::mem::MaybeUninit; +use std::ops::{Deref, DerefMut}; + +#[derive(Debug)] +pub struct ArrayVec<Item, const CAPACITY: usize> +{ + items: [MaybeUninit<Item>; CAPACITY], + len: usize, +} + +impl<Item, const CAPACITY: usize> ArrayVec<Item, CAPACITY> +{ + #[inline] + #[must_use] + pub fn len(&self) -> usize + { + self.len + } + + #[inline] + #[must_use] + pub fn is_empty(&self) -> bool + { + self.len == 0 + } + + pub fn push(&mut self, item: Item) + { + assert!(self.len < CAPACITY); + + self.items[self.len].write(item); + + self.len += 1; + } + + pub fn insert(&mut self, index: usize, item: Item) + { + assert!(index <= self.len); + assert!(self.len < CAPACITY); + + if index == self.len { + self.push(item); + return; + } + + unsafe { + std::ptr::copy( + &raw const self.items[index], + &raw mut self.items[index + 1], + self.len - index, + ); + } + + self.items[index].write(item); + + self.len += 1; + } +} + +impl<Item, const CAPACITY: usize> Extend<Item> for ArrayVec<Item, CAPACITY> +{ + fn extend<IntoIter: IntoIterator<Item = Item>>(&mut self, iter: IntoIter) + { + for item in iter { + self.push(item); + } + } +} + +impl<Item, const CAPACITY: usize> AsRef<[Item]> for ArrayVec<Item, CAPACITY> +{ + fn as_ref(&self) -> &[Item] + { + let ptr = &raw const self.items[..self.len]; + + unsafe { &*(ptr as *const [Item]) } + } +} + +impl<Item, const CAPACITY: usize> AsMut<[Item]> for ArrayVec<Item, CAPACITY> +{ + fn as_mut(&mut self) -> &mut [Item] + { + let ptr = &raw mut self.items[..self.len]; + + unsafe { &mut *(ptr as *mut [Item]) } + } +} + +impl<Item, const CAPACITY: usize> Deref for ArrayVec<Item, CAPACITY> +{ + type Target = [Item]; + + fn deref(&self) -> &Self::Target + { + self.as_ref() + } +} + +impl<Item, const CAPACITY: usize> DerefMut for ArrayVec<Item, CAPACITY> +{ + fn deref_mut(&mut self) -> &mut Self::Target + { + self.as_mut() + } +} + +impl<Item, const CAPACITY: usize> Default for ArrayVec<Item, CAPACITY> +{ + fn default() -> Self + { + Self { + items: [const { MaybeUninit::uninit() }; CAPACITY], + len: 0, + } + } +} + +impl<Item, const CAPACITY: usize> Drop for ArrayVec<Item, CAPACITY> +{ + fn drop(&mut self) + { + for item in &mut self.items[..self.len] { + // SAFETY: The items from index 0 to the length index will always be + // initialized and satisfy all the invariants of the Item type. + unsafe { + item.assume_init_drop(); + } + } + } +} |