use crate::alloc::vec::Vec;
use core::any::TypeId;
use core::{fmt, mem, ptr};
#[cfg(feature = "std")]
use std::error::Error;
use hashbrown::{HashMap, HashSet};
use crate::archetype::Archetype;
use crate::{Bundle, DynamicBundle, EntityRef, MissingComponent, Query, QueryBorrow, Ref, RefMut};
#[derive(Default)]
pub struct World {
entities: Entities,
index: HashMap<Vec<TypeId>, u32>,
archetypes: Vec<Archetype>,
}
impl World {
pub fn new() -> Self {
Self::default()
}
pub fn spawn(&mut self, components: impl DynamicBundle) -> Entity {
let entity = self.entities.alloc();
let archetype = components.with_ids(|ids| {
self.index.get(ids).copied().unwrap_or_else(|| {
let x = self.archetypes.len() as u32;
self.archetypes.push(Archetype::new(components.type_info()));
self.index.insert(ids.to_vec(), x);
x
})
});
self.entities.meta[entity.id as usize].location.archetype = archetype;
let archetype = &mut self.archetypes[archetype as usize];
unsafe {
let index = archetype.allocate(entity.id);
self.entities.meta[entity.id as usize].location.index = index;
components.put(|ptr, ty, size| {
archetype.put_dynamic(ptr, ty, size, index);
true
});
}
entity
}
pub fn despawn(&mut self, entity: Entity) -> Result<(), NoSuchEntity> {
let loc = self.entities.free(entity)?;
if let Some(moved) = unsafe { self.archetypes[loc.archetype as usize].remove(loc.index) } {
self.entities.meta[moved as usize].location.index = loc.index;
}
Ok(())
}
pub fn clear(&mut self) {
for x in &mut self.archetypes {
x.clear();
}
self.entities.clear();
}
pub fn contains(&self, entity: Entity) -> bool {
self.entities.meta[entity.id as usize].generation == entity.generation
}
pub fn query<Q: Query>(&self) -> QueryBorrow<'_, Q> {
QueryBorrow::new(&self.entities.meta, &self.archetypes)
}
pub fn get<T: Component>(&self, entity: Entity) -> Result<Ref<'_, T>, ComponentError> {
let meta = &self.entities.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(ComponentError::NoSuchEntity);
}
Ok(unsafe {
Ref::new(
&self.archetypes[meta.location.archetype as usize],
meta.location.index,
)?
})
}
pub fn get_mut<T: Component>(&self, entity: Entity) -> Result<RefMut<'_, T>, ComponentError> {
let meta = &self.entities.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(ComponentError::NoSuchEntity);
}
Ok(unsafe {
RefMut::new(
&self.archetypes[meta.location.archetype as usize],
meta.location.index,
)?
})
}
pub fn entity(&self, entity: Entity) -> Result<EntityRef<'_>, NoSuchEntity> {
let meta = &self.entities.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(NoSuchEntity);
}
Ok(unsafe {
EntityRef::new(
&self.archetypes[meta.location.archetype as usize],
meta.location.index,
)
})
}
pub fn iter(&self) -> Iter<'_> {
Iter::new(&self.archetypes, &self.entities.meta)
}
pub fn insert(
&mut self,
entity: Entity,
components: impl DynamicBundle,
) -> Result<(), NoSuchEntity> {
use hashbrown::hash_map::Entry;
let loc = self.entities.get_mut(entity)?;
unsafe {
let arch = &mut self.archetypes[loc.archetype as usize];
let mut info = arch.types().to_vec();
for ty in components.type_info() {
if let Some(ptr) = arch.get_dynamic(ty.id(), ty.layout().size(), loc.index) {
ty.drop(ptr.as_ptr());
} else {
info.push(ty);
}
}
info.sort();
let elements = info.iter().map(|x| x.id()).collect::<Vec<_>>();
let target = match self.index.entry(elements) {
Entry::Occupied(x) => *x.get(),
Entry::Vacant(x) => {
let index = self.archetypes.len() as u32;
self.archetypes.push(Archetype::new(info));
x.insert(index);
index
}
};
if target == loc.archetype {
let arch = &mut self.archetypes[loc.archetype as usize];
components.put(|ptr, ty, size| {
arch.put_dynamic(ptr, ty, size, loc.index);
true
});
return Ok(());
}
let (source_arch, target_arch) = index2(
&mut self.archetypes,
loc.archetype as usize,
target as usize,
);
let target_index = target_arch.allocate(entity.id);
loc.archetype = target;
let old_index = mem::replace(&mut loc.index, target_index);
if let Some(moved) = source_arch.move_to(old_index, |ptr, ty, size| {
target_arch.put_dynamic(ptr, ty, size, target_index);
}) {
self.entities.meta[moved as usize].location.index = old_index;
}
components.put(|ptr, ty, size| {
target_arch.put_dynamic(ptr, ty, size, target_index);
true
});
}
Ok(())
}
pub fn insert_one(
&mut self,
entity: Entity,
component: impl Component,
) -> Result<(), NoSuchEntity> {
self.insert(entity, (component,))
}
pub fn remove<T: Bundle>(&mut self, entity: Entity) -> Result<T, ComponentError> {
use hashbrown::hash_map::Entry;
let loc = self.entities.get_mut(entity)?;
unsafe {
let removed = T::with_static_ids(|ids| ids.iter().copied().collect::<HashSet<_>>());
let info = self.archetypes[loc.archetype as usize]
.types()
.iter()
.cloned()
.filter(|x| !removed.contains(&x.id()))
.collect::<Vec<_>>();
let elements = info.iter().map(|x| x.id()).collect::<Vec<_>>();
let target = match self.index.entry(elements) {
Entry::Occupied(x) => *x.get(),
Entry::Vacant(x) => {
self.archetypes.push(Archetype::new(info));
let index = (self.archetypes.len() - 1) as u32;
x.insert(index);
index
}
};
let old_index = loc.index;
let source_arch = &self.archetypes[loc.archetype as usize];
let bundle = T::get(|ty, size| source_arch.get_dynamic(ty, size, old_index))?;
let (source_arch, target_arch) = index2(
&mut self.archetypes,
loc.archetype as usize,
target as usize,
);
let target_index = target_arch.allocate(entity.id);
loc.archetype = target;
loc.index = target_index;
if let Some(moved) = source_arch.move_to(old_index, |src, ty, size| {
if let Some(dst) = target_arch.get_dynamic(ty, size, target_index) {
ptr::copy_nonoverlapping(src, dst.as_ptr(), size);
}
}) {
self.entities.meta[moved as usize].location.index = old_index;
}
Ok(bundle)
}
}
pub fn remove_one<T: Component>(&mut self, entity: Entity) -> Result<T, ComponentError> {
self.remove::<(T,)>(entity).map(|(x,)| x)
}
}
unsafe impl Send for World {}
unsafe impl Sync for World {}
impl<'a> IntoIterator for &'a World {
type IntoIter = Iter<'a>;
type Item = (Entity, EntityRef<'a>);
fn into_iter(self) -> Iter<'a> {
self.iter()
}
}
fn index2<T>(x: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
assert!(i != j);
assert!(i < x.len());
assert!(j < x.len());
let ptr = x.as_mut_ptr();
unsafe { (&mut *ptr.add(i), &mut *ptr.add(j)) }
}
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
pub enum ComponentError {
NoSuchEntity,
MissingComponent(MissingComponent),
}
#[cfg(feature = "std")]
impl Error for ComponentError {}
impl fmt::Display for ComponentError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
use ComponentError::*;
match *self {
NoSuchEntity => f.write_str("no such entity"),
MissingComponent(ref x) => x.fmt(f),
}
}
}
impl From<NoSuchEntity> for ComponentError {
fn from(NoSuchEntity: NoSuchEntity) -> Self {
ComponentError::NoSuchEntity
}
}
impl From<MissingComponent> for ComponentError {
fn from(x: MissingComponent) -> Self {
ComponentError::MissingComponent(x)
}
}
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct NoSuchEntity;
impl fmt::Display for NoSuchEntity {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.pad("no such entity")
}
}
#[cfg(feature = "std")]
impl Error for NoSuchEntity {}
pub trait Component: Send + Sync + 'static {}
impl<T: Send + Sync + 'static> Component for T {}
#[derive(Clone, Copy, Hash, Eq, Ord, PartialEq, PartialOrd)]
pub struct Entity {
pub(crate) generation: u32,
pub(crate) id: u32,
}
impl Entity {
pub fn to_bits(self) -> u64 {
u64::from(self.generation) << 32 | u64::from(self.id)
}
pub fn from_bits(bits: u64) -> Self {
Self {
generation: (bits >> 32) as u32,
id: bits as u32,
}
}
}
impl fmt::Debug for Entity {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}v{}", self.id, self.generation)
}
}
pub struct Iter<'a> {
archetypes: core::slice::Iter<'a, Archetype>,
entities: &'a [EntityMeta],
current: Option<&'a Archetype>,
index: u32,
}
impl<'a> Iter<'a> {
fn new(archetypes: &'a [Archetype], entities: &'a [EntityMeta]) -> Self {
Self {
archetypes: archetypes.iter(),
entities,
current: None,
index: 0,
}
}
}
unsafe impl Send for Iter<'_> {}
unsafe impl Sync for Iter<'_> {}
impl<'a> Iterator for Iter<'a> {
type Item = (Entity, EntityRef<'a>);
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.current {
None => {
self.current = Some(self.archetypes.next()?);
self.index = 0;
}
Some(current) => {
if self.index == current.len() as u32 {
self.current = None;
continue;
}
let index = self.index;
self.index += 1;
let id = current.entity_id(index);
return Some((
Entity {
id,
generation: self.entities[id as usize].generation,
},
unsafe { EntityRef::new(current, index) },
));
}
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.entities.len()))
}
}
impl<A: DynamicBundle> Extend<A> for World {
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = A>,
{
for x in iter {
self.spawn(x);
}
}
}
impl<A: DynamicBundle> core::iter::FromIterator<A> for World {
fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
let mut world = World::new();
world.extend(iter);
world
}
}
#[derive(Default)]
struct Entities {
meta: Vec<EntityMeta>,
free: Vec<u32>,
}
impl Entities {
fn alloc(&mut self) -> Entity {
match self.free.pop() {
Some(i) => Entity {
generation: self.meta[i as usize].generation,
id: i,
},
None => {
let i = self.meta.len() as u32;
self.meta.push(EntityMeta {
generation: 0,
location: Location {
archetype: 0,
index: 0,
},
});
Entity {
generation: 0,
id: i,
}
}
}
}
fn free(&mut self, entity: Entity) -> Result<Location, NoSuchEntity> {
let meta = &mut self.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(NoSuchEntity);
}
meta.generation += 1;
self.free.push(entity.id);
Ok(meta.location)
}
fn clear(&mut self) {
self.meta.clear();
self.free.clear();
}
fn get_mut(&mut self, entity: Entity) -> Result<&mut Location, NoSuchEntity> {
let meta = &mut self.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(NoSuchEntity);
}
Ok(&mut meta.location)
}
}
#[derive(Copy, Clone)]
pub(crate) struct EntityMeta {
pub(crate) generation: u32,
location: Location,
}
#[derive(Copy, Clone)]
struct Location {
archetype: u32,
index: u32,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn id_reuse() {
let mut world = World::new();
let a = world.spawn(());
world.despawn(a).unwrap();
let b = world.spawn(());
assert_eq!(a.id, b.id);
assert_ne!(a.generation, b.generation);
}
#[test]
fn entity_bits_roundtrip() {
let e = Entity {
generation: 0xDEADBEEF,
id: 0xBAADF00D,
};
assert_eq!(Entity::from_bits(e.to_bits()), e);
}
}