use super::{ComponentAlreadyBorrowed, Fetch, Query, QueryParams};
use std::any::{Any, TypeId};
use std::collections::{hash_map::DefaultHasher, HashMap};
use std::hash::{Hash, Hasher};
use std::sync::RwLock;
type EntityId = u32;
trait ComponentVec {
fn to_any(&self) -> &dyn Any;
fn to_any_mut(&mut self) -> &mut dyn Any;
fn len(&mut self) -> usize;
fn swap_remove(&mut self, index: EntityId);
fn migrate(&mut self, entity_index: EntityId, other_archetype: &mut dyn ComponentVec);
fn new_same_type(&self) -> Box<dyn ComponentVec + Send + Sync>;
}
impl<T: 'static + Send + Sync> ComponentVec for RwLock<Vec<T>> {
fn to_any(&self) -> &dyn Any {
self
}
fn to_any_mut(&mut self) -> &mut dyn Any {
self
}
fn len(&mut self) -> usize {
self.get_mut().unwrap().len()
}
fn swap_remove(&mut self, index: EntityId) {
self.get_mut().unwrap().swap_remove(index as usize);
}
fn migrate(&mut self, entity_index: EntityId, other_component_vec: &mut dyn ComponentVec) {
let data: T = self.get_mut().unwrap().swap_remove(entity_index as usize);
component_vec_to_mut(other_component_vec).push(data);
}
fn new_same_type(&self) -> Box<dyn ComponentVec + Send + Sync> {
Box::new(RwLock::new(Vec::<T>::new()))
}
}
fn component_vec_to_mut<T: 'static>(c: &mut dyn ComponentVec) -> &mut Vec<T> {
c.to_any_mut()
.downcast_mut::<RwLock<Vec<T>>>()
.unwrap()
.get_mut()
.unwrap()
}
pub(crate) struct ComponentStore {
pub(crate) type_id: TypeId,
data: Box<dyn ComponentVec + Send + Sync>,
}
impl ComponentStore {
pub fn new<T: 'static + Send + Sync>() -> Self {
Self {
type_id: TypeId::of::<T>(),
data: Box::new(RwLock::new(Vec::<T>::new())),
}
}
pub fn new_same_type(&self) -> Self {
Self {
type_id: self.type_id,
data: self.data.new_same_type(),
}
}
pub fn len(&mut self) -> usize {
self.data.len()
}
}
#[doc(hidden)]
pub struct Archetype {
pub(crate) entities: Vec<EntityId>,
pub(crate) components: Vec<ComponentStore>,
}
impl Archetype {
pub fn new() -> Self {
Self {
entities: Vec::new(),
components: Vec::new(),
}
}
pub(crate) fn get<T: 'static>(&self, index: usize) -> &RwLock<Vec<T>> {
self.components[index]
.data
.to_any()
.downcast_ref::<RwLock<Vec<T>>>()
.unwrap()
}
fn remove_entity(&mut self, index: EntityId) -> EntityId {
for c in self.components.iter_mut() {
c.data.swap_remove(index)
}
let moved = *self.entities.last().unwrap();
self.entities.swap_remove(index as usize);
moved
}
fn mutable_component_store<T: 'static>(&mut self, component_index: usize) -> &mut Vec<T> {
component_vec_to_mut(&mut *self.components[component_index].data)
}
fn replace_component<T: 'static>(&mut self, component_index: usize, index: EntityId, t: T) {
self.mutable_component_store(component_index)[index as usize] = t;
}
fn push<T: 'static>(&mut self, component_index: usize, t: T) {
self.mutable_component_store(component_index).push(t)
}
fn get_component_mut<T: 'static>(
&mut self,
index: EntityId,
) -> Result<&mut T, EntityMissingComponent> {
let type_id = TypeId::of::<T>();
let mut component_index = None;
for (i, c) in self.components.iter().enumerate() {
if c.type_id == type_id {
component_index = Some(i);
break;
}
}
if let Some(component_index) = component_index {
Ok(&mut self.mutable_component_store(component_index)[index as usize])
} else {
Err(EntityMissingComponent::new::<T>(index))
}
}
fn migrate_component(
&mut self,
component_index: usize,
entity_index: EntityId,
other_archetype: &mut Archetype,
other_index: usize,
) {
self.components[component_index].data.migrate(
entity_index,
&mut *other_archetype.components[other_index].data,
);
}
fn len(&mut self) -> usize {
self.components[0].len()
}
}
#[derive(Debug, Clone, Copy)]
#[doc(hidden)]
pub struct EntityLocation {
archetype_index: EntityId,
index_in_archetype: EntityId,
}
#[derive(Clone, Copy)]
struct EntityInfo {
generation: EntityId,
location: EntityLocation,
}
#[derive(Debug, Clone, Copy, Hash, Eq, Ord, PartialEq, PartialOrd)]
pub struct Entity {
index: EntityId,
generation: EntityId,
}
pub struct World {
pub(crate) archetypes: Vec<Archetype>,
bundle_id_to_archetype: HashMap<u64, usize>,
entities: Vec<EntityInfo>,
free_entities: Vec<EntityId>,
}
#[derive(Debug)]
pub struct NoSuchEntity;
impl std::fmt::Display for NoSuchEntity {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"The entity no longer exists so the operation cannot be performed"
)
}
}
impl std::error::Error for NoSuchEntity {}
#[derive(Debug)]
pub struct EntityMissingComponent(EntityId, &'static str);
impl EntityMissingComponent {
pub fn new<T>(entity_id: EntityId) -> Self {
Self(entity_id, std::any::type_name::<T>())
}
}
impl std::fmt::Display for EntityMissingComponent {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"Entity {:?} does not have a [{}] component",
self.0, self.1
)
}
}
impl std::error::Error for EntityMissingComponent {}
pub enum ComponentError {
EntityMissingComponent(EntityMissingComponent),
NoSuchEntity(NoSuchEntity),
}
impl World {
pub fn new() -> Self {
Self {
archetypes: Vec::new(),
bundle_id_to_archetype: HashMap::new(),
entities: Vec::new(),
free_entities: Vec::new(),
}
}
pub fn spawn(&mut self, b: impl ComponentBundle) -> Entity {
let (index, generation) = if let Some(index) = self.free_entities.pop() {
let (generation, _) = self.entities[index as usize].generation.overflowing_add(1);
(index, generation)
} else {
self.entities.push(EntityInfo {
location: EntityLocation {
archetype_index: 0,
index_in_archetype: 0,
},
generation: 0,
});
debug_assert!(self.entities.len() <= EntityId::MAX as usize);
((self.entities.len() - 1) as EntityId, 0)
};
let location = b.spawn_in_world(self, index);
self.entities[index as usize] = EntityInfo {
location,
generation: generation,
};
Entity { index, generation }
}
pub fn despawn(&mut self, entity: Entity) -> Result<(), NoSuchEntity> {
let entity_info = self.entities[entity.index as usize];
if entity_info.generation == entity.generation {
self.entities[entity.index as usize].generation += 1;
let moved_entity = self.archetypes[entity_info.location.archetype_index as usize]
.remove_entity(entity_info.location.index_in_archetype);
self.free_entities.push(entity.index);
self.entities[moved_entity as usize].location = entity_info.location;
Ok(())
} else {
Err(NoSuchEntity)
}
}
pub fn get_component_mut<T: 'static>(
&mut self,
entity: Entity,
) -> Result<&mut T, ComponentError> {
let entity_info = self.entities[entity.index as usize];
if entity_info.generation == entity.generation {
let archetype = &mut self.archetypes[entity_info.location.archetype_index as usize];
archetype
.get_component_mut(entity_info.location.index_in_archetype)
.map_err(|e| ComponentError::EntityMissingComponent(e))
} else {
Err(ComponentError::NoSuchEntity(NoSuchEntity))
}
}
pub fn remove_component<T: 'static>(&mut self, entity: Entity) -> Result<T, ComponentError> {
let entity_info = self.entities[entity.index as usize];
if entity_info.generation == entity.generation {
let current_archetype = &self.archetypes[entity_info.location.archetype_index as usize];
let type_id = TypeId::of::<T>();
let mut type_ids: Vec<TypeId> = current_archetype
.components
.iter()
.map(|c| c.type_id)
.collect();
let binary_search_index = type_ids.binary_search(&type_id);
if let Ok(remove_index) = binary_search_index {
type_ids.remove(remove_index);
let bundle_id = calculate_bundle_id(&type_ids);
let new_archetype_index = if let Some(new_archetype_index) =
self.bundle_id_to_archetype.get(&bundle_id)
{
*new_archetype_index
} else {
let mut archetype = Archetype::new();
for c in current_archetype.components.iter() {
if c.type_id != type_id {
archetype.components.push(c.new_same_type());
}
}
let new_archetype_index = self.archetypes.len();
self.bundle_id_to_archetype
.insert(bundle_id, new_archetype_index);
self.archetypes.push(archetype);
new_archetype_index
};
let (old_archetype, new_archetype) = index_twice(
&mut self.archetypes,
entity_info.location.archetype_index as usize,
new_archetype_index,
);
if let Some(last) = old_archetype.entities.last() {
self.entities[*last as usize].location = entity_info.location;
}
self.entities[entity.index as usize].location = EntityLocation {
archetype_index: new_archetype_index as EntityId,
index_in_archetype: (new_archetype.len()) as EntityId,
};
for i in 0..remove_index {
old_archetype.migrate_component(
i,
entity_info.location.index_in_archetype,
new_archetype,
i,
);
}
let components_in_archetype = old_archetype.components.len();
for i in (remove_index + 1)..components_in_archetype {
old_archetype.migrate_component(
i,
entity_info.location.index_in_archetype,
new_archetype,
i - 1,
);
}
old_archetype
.entities
.swap_remove(entity_info.location.index_in_archetype as usize);
new_archetype.entities.push(entity.index);
Ok(
component_vec_to_mut::<T>(&mut *old_archetype.components[remove_index].data)
.swap_remove(entity_info.location.index_in_archetype as usize),
)
} else {
Err(ComponentError::EntityMissingComponent(
EntityMissingComponent::new::<T>(entity.index),
))
}
} else {
Err(ComponentError::NoSuchEntity(NoSuchEntity))
}
}
pub fn add_component<T: 'static + Send + Sync>(
&mut self,
entity: Entity,
t: T,
) -> Result<(), NoSuchEntity> {
let entity_info = self.entities[entity.index as usize];
if entity_info.generation == entity.generation {
let type_id = TypeId::of::<T>();
let current_archetype = &self.archetypes[entity_info.location.archetype_index as usize];
let mut type_ids: Vec<TypeId> = current_archetype
.components
.iter()
.map(|c| c.type_id)
.collect();
let binary_search_index = type_ids.binary_search(&type_id);
if let Ok(insert_index) = binary_search_index {
let current_archetype =
&mut self.archetypes[entity_info.location.archetype_index as usize];
current_archetype.replace_component(
insert_index,
entity_info.location.index_in_archetype,
t,
);
} else {
let insert_index = binary_search_index.unwrap_or_else(|i| i);
type_ids.insert(insert_index, type_id);
let bundle_id = calculate_bundle_id(&type_ids);
let new_archetype_index = if let Some(new_archetype_index) =
self.bundle_id_to_archetype.get(&bundle_id)
{
*new_archetype_index
} else {
let mut archetype = Archetype::new();
for c in current_archetype.components.iter() {
archetype.components.push(c.new_same_type());
}
let new_archetype_index = self.archetypes.len();
archetype
.components
.insert(insert_index, ComponentStore::new::<T>());
self.bundle_id_to_archetype
.insert(bundle_id, new_archetype_index);
self.archetypes.push(archetype);
new_archetype_index
};
let (old_archetype, new_archetype) = index_twice(
&mut self.archetypes,
entity_info.location.archetype_index as usize,
new_archetype_index,
);
if let Some(last) = old_archetype.entities.last() {
self.entities[*last as usize].location = entity_info.location;
}
self.entities[entity.index as usize].location = EntityLocation {
archetype_index: new_archetype_index as EntityId,
index_in_archetype: (new_archetype.len()) as EntityId,
};
for i in 0..insert_index {
old_archetype.migrate_component(
i,
entity_info.location.index_in_archetype,
new_archetype,
i,
);
}
new_archetype.push(insert_index, t);
let components_in_archetype = old_archetype.components.len();
for i in insert_index..components_in_archetype {
old_archetype.migrate_component(
i,
entity_info.location.index_in_archetype,
new_archetype,
i + 1,
);
}
old_archetype
.entities
.swap_remove(entity_info.location.index_in_archetype as usize);
new_archetype.entities.push(entity.index);
}
Ok(())
} else {
Err(NoSuchEntity)
}
}
pub fn query<'world_borrow, T: QueryParams>(
&'world_borrow self,
) -> Result<Query<T>, ComponentAlreadyBorrowed> {
Ok(Query {
borrow: <<T as QueryParams>::Fetch as Fetch>::get(self, 0)?,
phantom: std::marker::PhantomData,
})
}
}
pub trait ComponentBundle {
#[doc(hidden)]
fn new_archetype() -> Archetype;
#[doc(hidden)]
fn spawn_in_world(self, world: &mut World, entity_index: EntityId) -> EntityLocation;
}
fn calculate_bundle_id(types: &[TypeId]) -> u64 {
let mut s = DefaultHasher::new();
types.hash(&mut s);
s.finish()
}
macro_rules! component_bundle_impl {
($count: expr, $(($name: ident, $index: tt)),*) => {
impl< $($name: 'static + Send + Sync),*> ComponentBundle for ($($name,)*) {
fn new_archetype() -> Archetype {
let mut components = vec![$(ComponentStore::new::<$name>()), *];
components.sort_unstable_by(|a, b| a.type_id.cmp(&b.type_id));
Archetype { components, entities: Vec::new() }
}
fn spawn_in_world(self, world: &mut World, entity_index: EntityId) -> EntityLocation {
let mut types = [$(($index, TypeId::of::<$name>())), *];
types.sort_unstable_by(|a, b| a.1.cmp(&b.1));
debug_assert!(
types.windows(2).all(|x| x[0].1 != x[1].1),
"`ComponentBundle`s cannot have duplicate types"
);
let mut order = [0; $count];
for i in 0..order.len() {
order[types[i].0] = i;
}
let types = [$(types[$index].1), *];
let bundle_id = calculate_bundle_id(&types);
let archetype_index = if let Some(archetype) = world.bundle_id_to_archetype.get(&bundle_id) {
*archetype
} else {
let archetype = Self::new_archetype();
let index = world.archetypes.len();
world.bundle_id_to_archetype.insert(bundle_id, index);
world.archetypes.push(archetype);
index
};
world.archetypes[archetype_index].entities.push(entity_index);
$(world.archetypes[archetype_index].push(order[$index], self.$index);)*
EntityLocation {
archetype_index: archetype_index as EntityId,
index_in_archetype: (world.archetypes[archetype_index].len() - 1) as EntityId
}
}
}
}
}
component_bundle_impl! {1, (A, 0)}
component_bundle_impl! {2, (A, 0), (B, 1)}
component_bundle_impl! {3, (A, 0), (B, 1), (C, 2)}
component_bundle_impl! {4, (A, 0), (B, 1), (C, 2), (D, 3)}
component_bundle_impl! {5, (A, 0), (B, 1), (C, 2), (D, 3), (E, 4)}
component_bundle_impl! {6, (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5)}
component_bundle_impl! {7, (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6)}
component_bundle_impl! {8, (A, 0), (B, 1), (C, 2), (D, 3), (E, 4), (F, 5), (G, 6), (H, 7)}
fn index_twice<T>(slice: &mut [T], first: usize, second: usize) -> (&mut T, &mut T) {
if first < second {
let (a, b) = slice.split_at_mut(second);
(&mut a[first], &mut b[0])
} else {
let (a, b) = slice.split_at_mut(first);
(&mut b[0], &mut a[second])
}
}