refactor(ecs): rewrite component storageHEADmaster

8 files changed, 871 insertions, 646 deletions

diff --git a/ecs/src/archetype.rs b/ecs/src/archetype.rs
deleted file mode 100644
index 846e231..0000000
--- a/ecs/src/archetype.rs
+++ /dev/null
@@ -1,56 +0,0 @@
-use std::hash::{DefaultHasher, Hash, Hasher};
-
-use crate::component::Metadata as ComponentMetadata;
-
-/// Archetype ID.
-#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
-pub struct Id
-{
-    hash: u64,
-}
-
-impl Id
-{
-    pub fn from_components_metadata(
-        components_metadata: &impl AsRef<[ComponentMetadata]>,
-    ) -> Self
-    {
-        if components_metadata.as_ref().len() == 0 {
-            return Self { hash: 0 };
-        }
-
-        debug_assert!(
-            components_metadata
-                .as_ref()
-                .is_sorted_by_key(|comp_metadata| comp_metadata.id),
-            "Cannot create archetype ID from a unsorted component metadata list"
-        );
-
-        let component_ids =
-            components_metadata
-                .as_ref()
-                .iter()
-                .filter_map(|component_metadata| {
-                    if component_metadata.is_optional {
-                        return None;
-                    }
-
-                    Some(component_metadata.id)
-                });
-
-        let mut hasher = DefaultHasher::new();
-
-        for component_id in component_ids {
-            component_id.hash(&mut hasher);
-        }
-
-        let hash = hasher.finish();
-
-        assert_ne!(
-            hash, 0,
-            "Archetype ID 0 is reserved for a archetype with zero components"
-        );
-
-        Self { hash }
-    }
-}
diff --git a/ecs/src/component/storage.rs b/ecs/src/component/storage.rs
index 0475bf1..0e1a03d 100644
--- a/ecs/src/component/storage.rs
+++ b/ecs/src/component/storage.rs
@@ -1,22 +1,31 @@
 use std::any::type_name;
-use std::borrow::Borrow;
-use std::cell::RefCell;
-use std::slice::Iter as SliceIter;
-use std::vec::IntoIter as OwnedVecIter;
+use std::iter::{Chain, Flatten};
 
 use hashbrown::{HashMap, HashSet};
 
-use crate::archetype::Id as ArchetypeId;
+use crate::component::storage::archetype::{
+    Archetype,
+    ArchetypeEntity,
+    Id as ArchetypeId,
+};
+use crate::component::storage::graph::{
+    ArchetypeAddEdgeRecursiveIter,
+    ArchetypeEdges,
+    Graph,
+};
 use crate::component::{Component, Metadata as ComponentMetadata};
 use crate::type_name::TypeName;
-use crate::uid::Uid;
+use crate::uid::{Kind as UidKind, Uid};
 use crate::EntityComponent;
 
+pub mod archetype;
+
+mod graph;
+
 #[derive(Debug, Default)]
 pub struct Storage
 {
-    archetypes: Vec<Archetype>,
-    archetype_lookup: RefCell<HashMap<ArchetypeId, ArchetypeLookupEntry>>,
+    graph: Graph,
     entity_archetype_lookup: HashMap<Uid, ArchetypeId>,
 }
 
@@ -24,481 +33,280 @@ impl Storage
 {
     pub fn iter_archetypes_with_comps(
         &self,
-        comp_metadata: impl AsRef<[ComponentMetadata]>,
+        component_metadata: impl AsRef<[ComponentMetadata]>,
     ) -> ArchetypeRefIter<'_>
     {
-        debug_assert!(comp_metadata
-            .as_ref()
-            .is_sorted_by_key(|metadata| metadata.id));
-
-        let archetype_id = ArchetypeId::from_components_metadata(&comp_metadata);
+        let archetype_id = ArchetypeId::from_components_metadata(&component_metadata);
 
-        if !self.archetype_lookup.borrow().contains_key(&archetype_id) {
-            self.archetype_lookup.borrow_mut().insert(
-                archetype_id,
-                self.create_populated_archetype_lookup_entry(comp_metadata.as_ref()),
-            );
+        ArchetypeRefIter {
+            storage: self,
+            iter: [archetype_id].into_iter().chain(
+                self.graph
+                    .recurse_archetype_add_edges(archetype_id)
+                    .into_iter()
+                    .flatten()
+                    .flatten(),
+            ),
+            visited: HashSet::new(),
         }
-
-        self.iter_archetypes_by_lookup(archetype_id)
     }
 
-    pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype>
+    pub fn get_archetype_by_id(&self, id: ArchetypeId) -> Option<&Archetype>
     {
-        let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?;
-
-        let archetype_index = self.get_archetype_index_by_id(*archetype_id)?;
-
-        self.archetypes.get(archetype_index)
+        Some(self.graph.get_node_by_id(id)?.archetype())
     }
 
-    pub fn remove_entity(&mut self, entity_uid: Uid)
+    pub fn create_entity(&mut self, uid: Uid) -> Result<(), Error>
     {
-        let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else {
-            return;
-        };
+        debug_assert_eq!(uid.kind(), UidKind::Entity);
 
-        let Some(archetype_index) = self.get_archetype_index_by_id(*archetype_id) else {
-            return;
-        };
-
-        let Some(archetype) = self.archetypes.get_mut(archetype_index) else {
-            return;
-        };
-
-        archetype.take_entity(entity_uid);
-
-        self.entity_archetype_lookup.remove(&entity_uid);
-    }
-
-    #[tracing::instrument(skip_all)]
-    pub fn push_entity(
-        &mut self,
-        entity_uid: Uid,
-        mut components: Vec<Box<dyn Component>>,
-    ) -> Result<(ArchetypeId, Uid), Error>
-    {
-        if self.entity_archetype_lookup.contains_key(&entity_uid) {
-            return Err(Error::EntityAlreadyExists(entity_uid));
+        if self.entity_archetype_lookup.contains_key(&uid) {
+            return Err(Error::EntityAlreadyExists(uid));
         }
 
-        components.sort_by_key(|component| component.self_id());
-        tracing::trace!(
-            "Pushing entity with components: ({})",
-            &components.iter().fold(
-                String::with_capacity(components.len() * 25),
-                |mut acc, component| {
-                    acc.extend([", ", component.type_name()]);
-                    acc
-                }
-            )[2..]
-        );
-
-        let archetype_id = ArchetypeId::from_components_metadata(
-            &components
-                .iter()
-                .map(|component| ComponentMetadata::get(&**component))
-                .collect::<Vec<_>>(),
-        );
-
-        let comp_ids_set = create_non_opt_component_id_set(
-            components
-                .iter()
-                .map(|component| ComponentMetadata::get(&**component)),
-        );
-
-        let archetype_index = self.get_or_create_archetype(archetype_id, &components);
+        let empty_archetype_id = ArchetypeId::from_components_metadata(&[]);
 
-        self.populate_matching_archetype_lookup_entries(&comp_ids_set, archetype_index);
+        let archetype_node = self.graph.get_or_create_node(empty_archetype_id, &[]);
 
-        let archetype = self
-            .archetypes
-            .get_mut(archetype_index)
-            .expect("Archetype is gone");
+        archetype_node
+            .archetype_mut()
+            .push_entity(ArchetypeEntity { uid, components: vec![] });
 
-        archetype.push_entity(entity_uid, components);
+        self.entity_archetype_lookup.insert(uid, empty_archetype_id);
 
-        self.entity_archetype_lookup
-            .insert(entity_uid, archetype_id);
-
-        Ok((archetype_id, entity_uid))
+        Ok(())
     }
 
-    pub fn add_components_to_entity(
+    pub fn remove_entity(
         &mut self,
         entity_uid: Uid,
-        components: Vec<Box<dyn Component>>,
-    ) -> Option<()>
+    ) -> Result<Vec<EntityComponent>, Error>
     {
-        let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?;
-
-        let archetype_index = self.get_archetype_index_by_id(*archetype_id)?;
-
-        let archetype = self.archetypes.get_mut(archetype_index)?;
+        let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else {
+            return Err(Error::EntityDoesNotExist(entity_uid));
+        };
 
-        let contains_component_already = components
-            .iter()
-            .any(|component| archetype.component_ids.contains_key(&component.self_id()));
-
-        if contains_component_already {
-            let component_cnt = components.len();
-
-            // TODO: return error
-            panic!(
-                "Entity with UID {:?} already contains one or more component(s) ({})",
-                entity_uid,
-                components
-                    .iter()
-                    .flat_map(|component| [component.type_name(), ", "])
-                    .enumerate()
-                    .take_while(|(index, _)| { *index < (component_cnt * 2) - 1 })
-                    .map(|(_, component)| component)
-                    .collect::<String>()
-            );
-        }
+        let archetype_node = self
+            .graph
+            .get_node_by_id_mut(*archetype_id)
+            .expect("Archetype should exist");
 
-        let entity = archetype.take_entity(entity_uid)?;
+        let entity = archetype_node
+            .archetype_mut()
+            .remove_entity(entity_uid)
+            .expect("Entity should exist in archetype");
 
         self.entity_archetype_lookup.remove(&entity_uid);
 
-        self.push_entity(
-            entity_uid,
-            entity
-                .components
-                .into_iter()
-                .map(|component| component.component.into_inner())
-                .chain(components)
-                .collect(),
-        )
-        .expect("Not supposed to return Err since the entity is removed");
-
-        Some(())
+        Ok(entity.components)
     }
 
-    pub fn remove_components_from_entity(
-        &mut self,
-        entity_uid: Uid,
-        component_ids: impl IntoIterator<Item = Uid>,
-    ) -> Option<()>
+    pub fn get_entity_archetype(&self, entity_uid: Uid) -> Option<&Archetype>
     {
         let archetype_id = self.entity_archetype_lookup.get(&entity_uid)?;
 
-        let archetype_index = self.get_archetype_index_by_id(*archetype_id)?;
-
-        let archetype = self.archetypes.get_mut(archetype_index)?;
-
-        let entity = archetype.take_entity(entity_uid)?;
-
-        let component_ids_set = component_ids.into_iter().collect::<HashSet<_>>();
-
-        self.entity_archetype_lookup.remove(&entity_uid);
-
-        self.push_entity(
-            entity_uid,
-            entity
-                .components
-                .into_iter()
-                .map(|component| component.component.into_inner())
-                .filter(|component| !component_ids_set.contains(&component.self_id()))
-                .collect(),
-        )
-        .expect("Not supposed to return Err since the entity is removed");
-
-        Some(())
-    }
-
-    fn populate_matching_archetype_lookup_entries(
-        &mut self,
-        comp_ids_set: &HashSet<Uid>,
-        archetype_index: usize,
-    )
-    {
-        let mut archetype_lookup = self.archetype_lookup.borrow_mut();
-
-        for (_, lookup_entry) in archetype_lookup.iter_mut() {
-            if &lookup_entry.component_ids == comp_ids_set {
-                continue;
-            }
-
-            // There shouldn't be duplicate archetype indices in the lookup entry
-            if lookup_entry.archetype_indices.contains(&archetype_index) {
-                continue;
-            }
-
-            if lookup_entry.component_ids.is_subset(comp_ids_set) {
-                lookup_entry.archetype_indices.push(archetype_index);
-            }
-        }
+        self.get_archetype_by_id(*archetype_id)
     }
 
-    fn get_or_create_archetype(
+    pub fn add_entity_component(
         &mut self,
-        archetype_id: ArchetypeId,
-        components: &[Box<dyn Component>],
-    ) -> usize
-    {
-        let mut archetype_lookup = self.archetype_lookup.borrow_mut();
-
-        if !archetype_lookup.contains_key(&archetype_id) {
-            self.archetypes.push(Archetype::new(
-                components.iter().map(|component| component.self_id()),
-            ));
-        }
-
-        let lookup_entry = archetype_lookup.entry(archetype_id).or_insert_with(|| {
-            self.create_populated_archetype_lookup_entry(
-                components
-                    .iter()
-                    .map(|component| ComponentMetadata::get(&**component)),
-            )
-        });
-
-        // SAFETY: Above, we push a archetype index if archetype_indices is empty so this
-        // cannot fail
-        unsafe { *lookup_entry.archetype_indices.first().unwrap_unchecked() }
-    }
-
-    fn get_archetype_index_by_id(&self, archetype_id: ArchetypeId) -> Option<usize>
+        entity_uid: Uid,
+        component: Box<dyn Component>,
+    ) -> Result<(), Error>
     {
-        let archetype_lookup = self.archetype_lookup.borrow();
-
-        let archetype_lookup_entry = archetype_lookup.get(&archetype_id)?;
-
-        let index = *archetype_lookup_entry
-            .archetype_indices
-            .first()
-            .expect("No archetype indices in archetype lookup entry");
-
         debug_assert!(
-            self.archetypes.get(index).is_some_and(|archetype| archetype
-                .component_ids_is(&archetype_lookup_entry.component_ids)),
-            "Archetype components is not exact match"
+            !component.self_is_optional(),
+            "Adding a optional component to a entity is not supported"
         );
 
-        Some(index)
-    }
-
-    fn iter_archetypes_by_lookup(&self, archetype_id: ArchetypeId)
-        -> ArchetypeRefIter<'_>
-    {
-        let archetype_lookup = self.archetype_lookup.borrow();
-
-        // The archetype indices have to be cloned to prevent a panic when query
-        // iterations are nested. The panic happens because the archetype_lookup RefCell
-        // is borrowed and it tries to mutably borrow it
-        let archetype_indices = archetype_lookup
-            .get(&archetype_id)
-            .unwrap()
-            .archetype_indices
-            .clone();
+        let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else {
+            return Err(Error::EntityDoesNotExist(entity_uid));
+        };
 
-        ArchetypeRefIter {
-            indices: archetype_indices.into_iter(),
-            archetypes: &self.archetypes,
+        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()
+            .has_component_with_id(component.self_id())
+        {
+            return Err(Error::EntityAlreadyHasComponent {
+                entity: entity_uid,
+                component: component.self_id(),
+            });
         }
-    }
-
-    fn create_populated_archetype_lookup_entry<CompMetadataIter>(
-        &self,
-        comp_metadata_iter: CompMetadataIter,
-    ) -> ArchetypeLookupEntry
-    where
-        CompMetadataIter: IntoIterator<Item: Borrow<ComponentMetadata>>,
-    {
-        let comp_ids_set = create_non_opt_component_id_set(comp_metadata_iter);
-
-        let mut exact_matching_archetype_index = None;
-
-        let matching_archetype_indices = self
-            .archetypes
-            .iter()
-            .enumerate()
-            .filter_map(|(index, archetype)| {
-                if archetype.component_ids_is(&comp_ids_set) {
-                    exact_matching_archetype_index = Some(index);
 
-                    return None;
+        let add_edge_archetype_id = archetype_node
+            .get_or_insert_edges(component.self_id(), ArchetypeEdges::default)
+            .add
+            .unwrap_or_else(|| {
+                let archetype_node = self
+                    .graph
+                    .get_node_by_id_mut(archetype_id)
+                    .expect("Archetype should exist");
+
+                let (add_edge_id, add_edge_comp_ids) =
+                    archetype_node.make_add_edge(component.self_id());
+
+                archetype_node
+                    .get_edges_mut(component.self_id())
+                    .expect("Edges for component in archetype should exist")
+                    .add = Some(add_edge_id);
+
+                if !self.graph.contains_archetype(add_edge_id) {
+                    self.graph.create_node(add_edge_id, &add_edge_comp_ids);
                 }
 
-                if archetype.component_ids_is_superset(&comp_ids_set) {
-                    return Some(index);
-                }
+                add_edge_id
+            });
 
-                None
-            })
-            .collect::<Vec<_>>();
+        {
+            let add_edge_archetype_node = self
+                .graph
+                .get_node_by_id_mut(add_edge_archetype_id)
+                .expect("Add edge archetype should exist");
 
-        ArchetypeLookupEntry {
-            component_ids: comp_ids_set,
-            archetype_indices: exact_matching_archetype_index
-                .into_iter()
-                .chain(matching_archetype_indices)
-                .collect(),
-        }
-    }
-}
+            let add_edge_archetype_edges = add_edge_archetype_node
+                .get_or_insert_edges(component.self_id(), ArchetypeEdges::default);
 
-/// Component storage error
-#[derive(Debug, Clone, thiserror::Error)]
-pub enum Error
-{
-    #[error("Entity already exists")]
-    EntityAlreadyExists(Uid),
-}
-
-impl TypeName for Storage
-{
-    fn type_name(&self) -> &'static str
-    {
-        type_name::<Self>()
-    }
-}
-
-#[derive(Debug)]
-struct ArchetypeLookupEntry
-{
-    component_ids: HashSet<Uid>,
-    archetype_indices: Vec<usize>,
-}
-
-#[derive(Debug)]
-pub struct Archetype
-{
-    component_ids: HashMap<Uid, usize>,
-    entity_lookup: HashMap<Uid, usize>,
-    entity_uid_lookup: Vec<Uid>,
-    entities: Vec<ArchetypeEntity>,
-}
-
-impl Archetype
-{
-    fn new(component_ids: impl IntoIterator<Item = Uid>) -> Self
-    {
-        Self {
-            component_ids: component_ids
-                .into_iter()
-                .enumerate()
-                .map(|(index, component_id)| (component_id, index))
-                .collect(),
-            entity_lookup: HashMap::new(),
-            entity_uid_lookup: Vec::new(),
-            entities: Vec::new(),
+            add_edge_archetype_edges.remove = Some(archetype_id);
         }
-    }
 
-    pub fn component_ids_is_superset(&self, other_component_ids: &HashSet<Uid>) -> bool
-    {
-        if other_component_ids.len() <= self.component_ids.len() {
-            other_component_ids
-                .iter()
-                .all(|v| self.component_ids.contains_key(v))
-        } else {
-            false
-        }
-    }
+        let archetype_node = self
+            .graph
+            .get_node_by_id_mut(archetype_id)
+            .expect("Archetype should exist");
 
-    pub fn component_ids_is(&self, other_component_ids: &HashSet<Uid>) -> bool
-    {
-        if other_component_ids.len() == self.component_ids.len() {
-            other_component_ids
-                .iter()
-                .all(|v| self.component_ids.contains_key(v))
-        } else {
-            false
-        }
-    }
+        let mut entity = archetype_node
+            .archetype_mut()
+            .remove_entity(entity_uid)
+            .expect("Entity should exist in archetype");
 
-    pub fn get_entity(&self, entity_uid: Uid) -> Option<&ArchetypeEntity>
-    {
-        let entity_index = *self.entity_lookup.get(&entity_uid)?;
+        let add_edge_archetype = self
+            .graph
+            .get_node_by_id_mut(add_edge_archetype_id)
+            .expect("Add edge archetype should exist")
+            .archetype_mut();
 
-        self.entities.get(entity_index)
-    }
+        let component_index = add_edge_archetype
+            .get_index_for_component(component.self_id())
+            .expect("Archetype should have index for component");
 
-    pub fn entities(&self) -> EntityIter<'_>
-    {
-        EntityIter { iter: self.entities.iter() }
-    }
+        entity.components.insert(component_index, component.into());
 
-    pub fn entity_cnt(&self) -> usize
-    {
-        self.entities.len()
-    }
+        add_edge_archetype.push_entity(entity);
 
-    pub fn get_index_for_component(&self, component_id: Uid) -> Option<usize>
-    {
-        self.component_ids.get(&component_id).copied()
+        self.entity_archetype_lookup
+            .insert(entity_uid, add_edge_archetype_id);
+
+        Ok(())
     }
 
-    fn push_entity(
+    pub fn remove_entity_component(
         &mut self,
         entity_uid: Uid,
-        components: impl IntoIterator<Item = Box<dyn Component>>,
-    )
+        component_id: Uid,
+    ) -> Result<(), Error>
     {
-        self.entities.push(ArchetypeEntity {
-            uid: entity_uid,
-            components: components.into_iter().map(Into::into).collect(),
-        });
+        let Some(archetype_id) = self.entity_archetype_lookup.get(&entity_uid) else {
+            return Err(Error::EntityDoesNotExist(entity_uid));
+        };
 
-        let index = self.entities.len() - 1;
+        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()
+            .has_component_with_id(component_id)
+        {
+            return Err(Error::EntityDoesNotHaveComponent {
+                entity: entity_uid,
+                component: component_id,
+            });
+        }
 
-        self.entity_lookup.insert(entity_uid, index);
+        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);
+
+                archetype_node
+                    .get_edges_mut(component_id)
+                    .expect("Edges for component in archetype should exist")
+                    .remove = Some(remove_edge_id);
+
+                if !self.graph.contains_archetype(remove_edge_id) {
+                    self.graph
+                        .create_node(remove_edge_id, &remove_edge_comp_ids);
+                }
 
-        self.entity_uid_lookup.push(entity_uid);
-    }
+                remove_edge_id
+            });
 
-    pub fn take_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity>
-    {
-        let entity_index = self.entity_lookup.remove(&entity_uid)?;
+        let archetype_node = self
+            .graph
+            .get_node_by_id_mut(archetype_id)
+            .expect("Archetype should exist");
 
-        let last_entity_uid = *self
-            .entity_uid_lookup
-            .get(self.entities.len() - 1)
-            .expect("Entity UID lookup contains too few entity UIDS");
+        let mut entity = archetype_node
+            .archetype_mut()
+            .remove_entity(entity_uid)
+            .expect("Entity should exist in archetype");
 
-        // 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);
+        let (comp_to_remove_index, _) = entity
+            .components
+            .iter()
+            .enumerate()
+            .find(|(_, comp)| comp.id == component_id)
+            .expect("Entity should contain component");
 
-        self.entity_lookup.insert(last_entity_uid, entity_index);
+        entity.components.remove(comp_to_remove_index);
 
-        self.entity_uid_lookup.swap_remove(entity_index);
+        self.graph
+            .get_node_by_id_mut(remove_edge_id)
+            .expect("Remove edge archetype should exist")
+            .archetype_mut()
+            .push_entity(entity);
 
-        Some(removed_entity)
-    }
-}
+        self.entity_archetype_lookup
+            .insert(entity_uid, remove_edge_id);
 
-#[derive(Debug)]
-pub struct ArchetypeEntity
-{
-    uid: Uid,
-    components: Vec<EntityComponent>,
+        Ok(())
+    }
 }
 
-impl ArchetypeEntity
+impl TypeName for Storage
 {
-    pub fn uid(&self) -> Uid
-    {
-        self.uid
-    }
-
-    pub fn components(&self) -> &[EntityComponent]
-    {
-        &self.components
-    }
-
-    pub fn get_component(&self, index: usize) -> Option<&EntityComponent>
+    fn type_name(&self) -> &'static str
     {
-        self.components.get(index)
+        type_name::<Self>()
     }
 }
 
 #[derive(Debug)]
-pub struct ArchetypeRefIter<'component_storage>
+pub struct ArchetypeRefIter<'storage>
 {
-    indices: OwnedVecIter<usize>,
-    archetypes: &'component_storage [Archetype],
+    storage: &'storage Storage,
+    iter: Chain<
+        std::array::IntoIter<ArchetypeId, 1>,
+        Flatten<Flatten<std::option::IntoIter<ArchetypeAddEdgeRecursiveIter<'storage>>>>,
+    >,
+    visited: HashSet<ArchetypeId>,
 }
 
 impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage>
@@ -507,150 +315,67 @@ impl<'component_storage> Iterator for ArchetypeRefIter<'component_storage>
 
     fn next(&mut self) -> Option<Self::Item>
     {
-        let archetype_index = self.indices.next()?;
+        let archetype_id = self
+            .iter
+            .find(|archetype_id| !self.visited.contains(archetype_id))?;
+
+        let archetype = self.storage.get_archetype_by_id(archetype_id)?;
 
-        Some(
-            self.archetypes
-                .get(archetype_index)
-                .expect("Archetype index in archetype lookup entry was not found"),
-        )
+        self.visited.insert(archetype_id);
+
+        Some(archetype)
     }
 }
 
-#[derive(Debug)]
-pub struct EntityIter<'archetype>
+#[derive(Debug, thiserror::Error)]
+pub enum Error
 {
-    iter: SliceIter<'archetype, ArchetypeEntity>,
-}
+    #[error("Entity with ID {0:?} already exists")]
+    EntityAlreadyExists(Uid),
 
-impl<'archetype> Iterator for EntityIter<'archetype>
-{
-    type Item = &'archetype ArchetypeEntity;
+    #[error("Entity with ID {0:?} does not exist")]
+    EntityDoesNotExist(Uid),
 
-    fn next(&mut self) -> Option<Self::Item>
+    #[error("Entity with ID {entity:?} already has component with ID {component:?}")]
+    EntityAlreadyHasComponent
     {
-        self.iter.next()
-    }
-}
+        entity: Uid, component: Uid
+    },
 
-fn create_non_opt_component_id_set<Item>(
-    component_metadata_iter: impl IntoIterator<Item = Item>,
-) -> HashSet<Uid>
-where
-    Item: Borrow<ComponentMetadata>,
-{
-    component_metadata_iter
-        .into_iter()
-        .filter_map(|item| {
-            let component_metadata = item.borrow();
-
-            if component_metadata.is_optional {
-                return None;
-            }
-
-            Some(component_metadata.id)
-        })
-        .collect::<HashSet<_>>()
+    #[error("Entity with ID {entity:?} does not have component with ID {component:?}")]
+    EntityDoesNotHaveComponent
+    {
+        entity: Uid, component: Uid
+    },
 }
 
 #[cfg(test)]
 mod tests
 {
-
-    use ecs_macros::Component;
-
-    use super::Storage;
-    use crate::archetype::Id as ArchetypeId;
-    use crate::component::{Component, Metadata as ComponentMetadata};
+    use crate::component::storage::archetype::Id as ArchetypeId;
+    use crate::component::storage::Storage;
     use crate::uid::{Kind as UidKind, Uid};
 
-    #[derive(Debug, Component)]
-    struct HealthPotion
-    {
-        _hp_restoration: u32,
-    }
-
-    #[derive(Debug, Component)]
-    struct Hookshot
-    {
-        _range: u32,
-    }
-
-    #[derive(Debug, Component)]
-    struct DekuNut
-    {
-        _throwing_damage: u32,
-    }
-
-    #[derive(Debug, Component)]
-    struct Bow
-    {
-        _damage: u32,
-    }
-
-    #[derive(Debug, Component)]
-    struct IronBoots;
-
     #[test]
-    fn push_entity_works()
+    fn create_entity_works()
     {
-        let mut component_storage = Storage::default();
-
-        component_storage
-            .push_entity(
-                Uid::new_unique(UidKind::Entity),
-                vec![
-                    Box::new(HealthPotion { _hp_restoration: 12 }),
-                    Box::new(Hookshot { _range: 50 }),
-                ],
-            )
-            .expect("Expected Ok");
-
-        assert_eq!(component_storage.archetypes.len(), 1);
-
-        let archetype = component_storage
-            .archetypes
-            .first()
-            .expect("Expected a archetype in archetypes Vec");
-
-        assert_eq!(archetype.component_ids.len(), 2);
-
-        // One entity
-        assert_eq!(archetype.entities.len(), 1);
+        let mut new_storage = Storage::default();
 
-        let entity_components = archetype
-            .entities
-            .first()
-            .expect("Expected a entity in archetype");
+        let uid = Uid::new_unique(UidKind::Entity);
 
-        assert_eq!(entity_components.components.len(), 2);
+        new_storage.create_entity(uid).expect("Expected Ok");
 
-        assert_eq!(component_storage.archetype_lookup.borrow().len(), 1);
+        let archetype_node = new_storage
+            .graph
+            .get_node_by_id(ArchetypeId::from_components_metadata(&[]))
+            .expect("Archetype for entities with no component doesn't exist");
 
-        let mut components_metadata = [
-            ComponentMetadata {
-                id: HealthPotion::id(),
-                is_optional: false,
-            },
-            ComponentMetadata {
-                id: Hookshot::id(),
-                is_optional: false,
-            },
-        ];
+        assert_eq!(archetype_node.archetype().component_cnt(), 0);
+        assert_eq!(archetype_node.archetype().entity_cnt(), 1);
 
-        components_metadata.sort_by_key(|comp_metadata| comp_metadata.id);
-
-        let archetype_lookup = component_storage.archetype_lookup.borrow();
-
-        let lookup_entry = archetype_lookup
-            .get(&ArchetypeId::from_components_metadata(&components_metadata))
-            .expect("Expected entry in archetype lookup map");
-
-        let first_archetype_index = lookup_entry
-            .archetype_indices
-            .first()
-            .expect("Expected archetype lookup to contain a archetype reference");
-
-        assert_eq!(*first_archetype_index, 0);
+        assert_eq!(
+            new_storage.entity_archetype_lookup.get(&uid).copied(),
+            Some(ArchetypeId::from_components_metadata(&[]))
+        );
     }
 }
diff --git a/ecs/src/component/storage/archetype.rs b/ecs/src/component/storage/archetype.rs
new file mode 100644
index 0000000..ee3d7f8
--- /dev/null
+++ b/ecs/src/component/storage/archetype.rs
@@ -0,0 +1,216 @@
+use std::borrow::Borrow;
+use std::hash::{DefaultHasher, Hash, Hasher};
+use std::slice::Iter as SliceIter;
+
+use hashbrown::HashMap;
+
+use crate::component::Metadata as ComponentMetadata;
+use crate::uid::{Kind as UidKind, Uid};
+use crate::util::HashMapExt;
+use crate::EntityComponent;
+
+#[derive(Debug)]
+pub struct Archetype
+{
+    id: Id,
+    entities: Vec<ArchetypeEntity>,
+    entity_index_lookup: HashMap<Uid, usize>,
+    component_index_lookup: HashMap<Uid, usize>,
+}
+
+impl Archetype
+{
+    pub fn new(id: Id, component_ids: impl IntoIterator<Item: Borrow<Uid>>) -> Self
+    {
+        Self {
+            id,
+            entities: Vec::new(),
+            entity_index_lookup: HashMap::new(),
+            component_index_lookup: component_ids
+                .into_iter()
+                .enumerate()
+                .map(|(index, id)| (*id.borrow(), index))
+                .collect(),
+        }
+    }
+
+    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 get_entity_by_id(&self, entity_uid: Uid) -> Option<&ArchetypeEntity>
+    {
+        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: ArchetypeEntity)
+    {
+        self.entity_index_lookup
+            .insert(entity.uid, self.entities.len());
+
+        self.entities.push(entity);
+    }
+
+    pub fn remove_entity(&mut self, entity_uid: Uid) -> Option<ArchetypeEntity>
+    {
+        //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_index_for_component(&self, component_id: Uid) -> Option<usize>
+    {
+        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 has_component_with_id(&self, component_id: Uid) -> bool
+    {
+        debug_assert_eq!(component_id.kind(), UidKind::Component);
+
+        self.component_index_lookup.contains_key(&component_id)
+    }
+}
+
+#[derive(Debug)]
+pub struct EntityIter<'archetype>
+{
+    iter: SliceIter<'archetype, ArchetypeEntity>,
+}
+
+impl<'archetype> Iterator for EntityIter<'archetype>
+{
+    type Item = &'archetype ArchetypeEntity;
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        self.iter.next()
+    }
+}
+
+#[derive(Debug)]
+pub struct ArchetypeEntity
+{
+    pub uid: Uid,
+    pub components: Vec<EntityComponent>,
+}
+
+/// Archetype ID.
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
+pub struct Id
+{
+    hash: u64,
+}
+
+impl Id
+{
+    pub fn new(component_ids: &impl AsRef<[Uid]>) -> Self
+    {
+        if component_ids.as_ref().len() == 0 {
+            return Self { hash: 0 };
+        }
+
+        debug_assert!(
+            component_ids.as_ref().is_sorted(),
+            "Cannot create archetype ID from unsorted component IDs"
+        );
+
+        let mut hasher = DefaultHasher::new();
+
+        for component_id in component_ids.as_ref() {
+            component_id.hash(&mut hasher);
+        }
+
+        Self { hash: hasher.finish() }
+    }
+
+    pub fn from_components_metadata(
+        components_metadata: &impl AsRef<[ComponentMetadata]>,
+    ) -> Self
+    {
+        if components_metadata.as_ref().len() == 0 {
+            return Self { hash: 0 };
+        }
+
+        debug_assert!(
+            components_metadata
+                .as_ref()
+                .is_sorted_by_key(|comp_metadata| comp_metadata.id),
+            "Cannot create archetype ID from a unsorted component metadata list"
+        );
+
+        let component_ids =
+            components_metadata
+                .as_ref()
+                .iter()
+                .filter_map(|component_metadata| {
+                    if component_metadata.is_optional {
+                        return None;
+                    }
+
+                    Some(component_metadata.id)
+                });
+
+        let mut hasher = DefaultHasher::new();
+
+        for component_id in component_ids {
+            component_id.hash(&mut hasher);
+        }
+
+        Self { hash: hasher.finish() }
+    }
+}
diff --git a/ecs/src/component/storage/graph.rs b/ecs/src/component/storage/graph.rs
new file mode 100644
index 0000000..fe97933
--- /dev/null
+++ b/ecs/src/component/storage/graph.rs
@@ -0,0 +1,269 @@
+use hashbrown::hash_map::Values as HashMapValueIter;
+use hashbrown::HashMap;
+
+use crate::component::storage::archetype::{Archetype, Id as ArchetypeId};
+use crate::uid::{Kind as UidKind, Uid};
+
+#[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 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
+        });
+
+        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")
+        }))
+    }
+
+    pub fn recurse_archetype_add_edges(
+        &self,
+        archetype_id: ArchetypeId,
+    ) -> Option<ArchetypeAddEdgeRecursiveIter>
+    {
+        Some(ArchetypeAddEdgeRecursiveIter {
+            graph: self,
+            stack: vec![self.get_node_by_id(archetype_id)?.edges.values()],
+        })
+    }
+
+    fn create_missing_edges(&mut self, archetype_id: ArchetypeId)
+    {
+        let archetype_node = self
+            .get_node_by_id(archetype_id)
+            .expect("Archetype should exist");
+
+        let mut comp_ids = archetype_node
+            .archetype()
+            .component_ids_unsorted()
+            .collect::<Vec<_>>();
+
+        comp_ids.sort();
+
+        for component_id_index in 0..archetype_node.archetype().component_cnt() {
+            let mut comp_ids_without_comp = comp_ids.clone();
+
+            let removed_comp_id = comp_ids_without_comp.remove(component_id_index);
+
+            let archetype_without_comp_id = ArchetypeId::new(&comp_ids_without_comp);
+
+            let Some(archetype_node_without_comp) =
+                self.get_node_by_id_mut(archetype_without_comp_id)
+            else {
+                continue;
+            };
+
+            archetype_node_without_comp
+                .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default)
+                .add = Some(archetype_id);
+
+            let archetype_node = self
+                .get_node_by_id_mut(archetype_id)
+                .expect("Archetype should exist");
+
+            archetype_node
+                .get_or_insert_edges(removed_comp_id, ArchetypeEdges::default)
+                .remove = Some(archetype_without_comp_id);
+        }
+
+        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!();
+        };
+
+        let expected_component_cnt = archetype_node.archetype().component_cnt() + 1;
+
+        for other_archetype_node in nodes_before.iter_mut().chain(nodes_after.iter_mut())
+        {
+            if other_archetype_node.archetype().component_cnt() != expected_component_cnt
+                || !other_archetype_node
+                    .archetype()
+                    .is_superset(&archetype_node.archetype())
+            {
+                continue;
+            }
+
+            let extra_comp_id = other_archetype_node
+                .archetype()
+                .component_ids_unsorted()
+                .find(|comp_id| {
+                    !archetype_node.archetype().has_component_with_id(*comp_id)
+                })
+                .expect("Archetype should contain one extra component ID");
+
+            other_archetype_node
+                .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default)
+                .remove = Some(archetype_id);
+
+            archetype_node
+                .get_or_insert_edges(extra_comp_id, ArchetypeEdges::default)
+                .add = Some(other_archetype_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_eq!(component_id.kind(), UidKind::Component);
+
+        self.edges.entry(component_id).or_insert_with(insert_fn)
+    }
+
+    pub fn get_edges_mut(&mut self, component_id: Uid) -> Option<&mut ArchetypeEdges>
+    {
+        debug_assert_eq!(component_id.kind(), UidKind::Component);
+
+        self.edges.get_mut(&component_id)
+    }
+
+    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)]
+pub struct ArchetypeEdges
+{
+    pub add: Option<ArchetypeId>,
+    pub remove: Option<ArchetypeId>,
+}
+
+#[derive(Debug)]
+pub struct ArchetypeAddEdgeRecursiveIter<'graph>
+{
+    graph: &'graph Graph,
+    stack: Vec<HashMapValueIter<'graph, Uid, ArchetypeEdges>>,
+}
+
+impl<'graph> Iterator for ArchetypeAddEdgeRecursiveIter<'graph>
+{
+    type Item = Option<ArchetypeId>;
+
+    fn next(&mut self) -> Option<Self::Item>
+    {
+        let iter = self.stack.last_mut()?;
+
+        let Some(edges) = iter.next() else {
+            self.stack.pop();
+
+            return Some(None);
+        };
+
+        let Some(add_edge) = edges.add else {
+            return Some(None);
+        };
+
+        let add_edge_archetype = self
+            .graph
+            .get_node_by_id(add_edge)
+            .expect("Add edge archetype not found");
+
+        self.stack.push(add_edge_archetype.edges.values());
+
+        Some(Some(add_edge))
+    }
+}
diff --git a/ecs/src/lib.rs b/ecs/src/lib.rs
index 72b5cf9..dc31daf 100644
--- a/ecs/src/lib.rs
+++ b/ecs/src/lib.rs
@@ -52,8 +52,6 @@ pub mod util;
 #[doc(hidden)]
 pub mod private;
 
-mod archetype;
-
 pub use ecs_macros::{Component, Sole};
 
 pub use crate::query::Query;
@@ -109,18 +107,20 @@ impl World
     {
         debug_assert_eq!(entity_uid.kind(), UidKind::Entity);
 
-        #[allow(unused_variables)]
-        if let Err(err) = self
-            .data
-            .component_storage
-            .write_nonblock()
-            .expect("Failed to acquire read-write component storage lock")
-            .push_entity(entity_uid, components.into_array().into())
         {
-            tracing::error!("Failed to create entity: {err}");
+            let mut component_storage_lock = self.lock_component_storage_rw();
 
-            return;
-        };
+            if let Err(err) = component_storage_lock.create_entity(entity_uid) {
+                tracing::warn!("Failed to create entity: {err}");
+                return;
+            };
+
+            Self::add_entity_components(
+                entity_uid,
+                components.into_array(),
+                &mut component_storage_lock,
+            );
+        }
 
         for added_event_id in Comps::added_event_ids() {
             self.emit_event_by_id(added_event_id);
@@ -316,19 +316,25 @@ impl World
         for action in active_action_queue.drain(..) {
             match action {
                 Action::Spawn(components, component_added_event_ids) => {
-                    let mut component_storage_lock = self.lock_component_storage_rw();
-
-                    #[allow(unused_variables)]
-                    if let Err(err) = component_storage_lock
-                        .push_entity(Uid::new_unique(UidKind::Entity), components)
                     {
-                        tracing::error!("Failed to create entity: {err}");
-
-                        continue;
+                        let mut component_storage_lock = self.lock_component_storage_rw();
+
+                        let new_entity_uid = Uid::new_unique(UidKind::Entity);
+
+                        if let Err(err) =
+                            component_storage_lock.create_entity(new_entity_uid)
+                        {
+                            tracing::warn!("Failed to create entity: {err}");
+                            continue;
+                        };
+
+                        Self::add_entity_components(
+                            new_entity_uid,
+                            components,
+                            &mut component_storage_lock,
+                        );
                     }
 
-                    drop(component_storage_lock);
-
                     if !has_swapped_active_queue {
                         self.swap_event_queue(&mut has_swapped_active_queue);
                     }
@@ -345,17 +351,23 @@ impl World
                     components,
                     component_added_event_ids,
                 ) => {
-                    let mut component_storage_lock = self.lock_component_storage_rw();
-
-                    component_storage_lock
-                        .add_components_to_entity(entity_uid, components);
+                    {
+                        let mut component_storage_lock = self.lock_component_storage_rw();
 
-                    drop(component_storage_lock);
+                        Self::add_entity_components(
+                            entity_uid,
+                            components,
+                            &mut component_storage_lock,
+                        );
+                    }
 
                     if !has_swapped_active_queue {
                         self.swap_event_queue(&mut has_swapped_active_queue);
                     }
 
+                    // TODO: Fix that events are emitted for components that haven't been
+                    // added because a error occurred (for example, the entity already has
+                    // the component)
                     for comp_added_event_id in component_added_event_ids.ids {
                         self.emit_event_by_id(comp_added_event_id);
                     }
@@ -365,21 +377,25 @@ impl World
                     components_metadata,
                     component_removed_event_ids,
                 ) => {
-                    let mut component_storage_lock = self.lock_component_storage_rw();
-
-                    component_storage_lock.remove_components_from_entity(
-                        entity_uid,
-                        components_metadata
-                            .iter()
-                            .map(|component_metadata| component_metadata.id),
-                    );
-
-                    drop(component_storage_lock);
+                    {
+                        let mut component_storage_lock = self.lock_component_storage_rw();
+
+                        Self::remove_entity_components(
+                            entity_uid,
+                            components_metadata
+                                .iter()
+                                .map(|comp_metadata| comp_metadata.id),
+                            &mut component_storage_lock,
+                        );
+                    }
 
                     if !has_swapped_active_queue {
                         self.swap_event_queue(&mut has_swapped_active_queue);
                     }
 
+                    // TODO: Fix that events are emitted for components that haven't been
+                    // removed because a error occurred (for example, the entity does not
+                    // have the component)
                     for comp_removed_event_id in component_removed_event_ids.ids {
                         self.emit_event_by_id(comp_removed_event_id);
                     }
@@ -391,23 +407,20 @@ impl World
         }
     }
 
+    #[tracing::instrument(skip_all)]
     fn despawn_entity(&self, entity_uid: Uid, has_swapped_active_queue: &mut bool)
     {
         let mut component_storage_lock = self.lock_component_storage_rw();
 
-        let Some(archetype) = component_storage_lock.get_entity_archetype(entity_uid)
-        else {
-            tracing::error!("No archetype for entity {entity_uid:?} was found");
-
-            return;
+        let components = match component_storage_lock.remove_entity(entity_uid) {
+            Ok(components) => components,
+            Err(err) => {
+                tracing::error!("Failed to despawn entity: {err}");
+                return;
+            }
         };
 
-        let entity = archetype
-            .get_entity(entity_uid)
-            .expect("Entity archetype was found but the entity is not in the archetype");
-
-        let component_removed_event_uids = entity
-            .components()
+        let component_removed_event_uids = components
             .iter()
             .map(|component| {
                 component
@@ -423,8 +436,6 @@ impl World
             })
             .collect::<Vec<_>>();
 
-        component_storage_lock.remove_entity(entity_uid);
-
         drop(component_storage_lock);
 
         if !*has_swapped_active_queue {
@@ -436,6 +447,36 @@ impl World
         }
     }
 
+    fn add_entity_components(
+        entity_uid: Uid,
+        components: impl IntoIterator<Item = Box<dyn Component>>,
+        component_storage: &mut ComponentStorage,
+    )
+    {
+        for component in components.into_iter() {
+            if let Err(err) =
+                component_storage.add_entity_component(entity_uid, component)
+            {
+                tracing::error!("Failed to add component to entity: {err}");
+            }
+        }
+    }
+
+    fn remove_entity_components(
+        entity_uid: Uid,
+        component_ids: impl IntoIterator<Item = Uid>,
+        component_storage: &mut ComponentStorage,
+    )
+    {
+        for component_id in component_ids.into_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_by_id(&self, event_id: Uid)
     {
         let query = self.flexible_query([
diff --git a/ecs/src/query/flexible.rs b/ecs/src/query/flexible.rs
index 5c23e68..129ee66 100644
--- a/ecs/src/query/flexible.rs
+++ b/ecs/src/query/flexible.rs
@@ -1,13 +1,8 @@
 //! Low-level querying.
 use std::iter::{repeat_n, Filter, Flatten, Map, RepeatN, Zip};
 
-use crate::component::storage::{
-    Archetype,
-    ArchetypeEntity,
-    ArchetypeRefIter,
-    EntityIter,
-    Storage as ComponentStorage,
-};
+use crate::component::storage::archetype::{Archetype, ArchetypeEntity, EntityIter};
+use crate::component::storage::{ArchetypeRefIter, Storage as ComponentStorage};
 use crate::component::{
     Metadata as ComponentMetadata,
     RefSequence as ComponentRefSequence,
@@ -48,7 +43,7 @@ where
                     }) as ComponentIterMapFn,
                 )
                 .flatten()
-                .filter(|(_, entity)| OptionsT::entity_filter(entity.components())),
+                .filter(|(_, entity)| OptionsT::entity_filter(&entity.components)),
         }
     }
 
@@ -117,13 +112,13 @@ impl<'query> EntityHandle<'query>
     #[inline]
     pub fn uid(&self) -> Uid
     {
-        self.entity.uid()
+        self.entity.uid
     }
 
     #[inline]
     pub fn components(&self) -> &'query [EntityComponent]
     {
-        self.entity.components()
+        &self.entity.components
     }
 
     #[inline]
diff --git a/ecs/src/relationship.rs b/ecs/src/relationship.rs
index 143b589..54dc0cd 100644
--- a/ecs/src/relationship.rs
+++ b/ecs/src/relationship.rs
@@ -174,14 +174,15 @@ where
         let archetype = self.component_storage_lock.get_entity_archetype(*target)?;
 
         let entity = archetype
-            .get_entity(*target)
+            .get_entity_by_id(*target)
             .expect("Target entity is gone from archetype");
 
         let component_index = archetype.get_index_for_component(ComponentT::id())?;
 
         let component = ComponentRefMut::new(
             entity
-                .get_component(component_index)?
+                .components
+                .get(component_index)?
                 .component
                 .write_nonblock()
                 .unwrap_or_else(|_| {
@@ -430,14 +431,15 @@ where
         let archetype = self.component_storage_lock.get_entity_archetype(*target)?;
 
         let entity = archetype
-            .get_entity(*target)
+            .get_entity_by_id(*target)
             .expect("Target entity is gone from archetype");
 
         let component_index = archetype.get_index_for_component(ComponentT::id())?;
 
         let component = ComponentRef::new(
             entity
-                .get_component(component_index)?
+                .components
+                .get(component_index)?
                 .component
                 .read_nonblock()
                 .unwrap_or_else(|_| {
diff --git a/ecs/src/util.rs b/ecs/src/util.rs
index 0273b18..71021cd 100644
--- a/ecs/src/util.rs
+++ b/ecs/src/util.rs
@@ -1,5 +1,38 @@
+use std::hash::Hash;
 use std::ops::BitAnd;
 
+use hashbrown::HashMap;
+
+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]>