Repository: Ralith/hecs
Pull request #30 (2020-01-12 22:03:20)

Support reserving entity IDs concurrently

Ratysz: This appears to fail on the third assertion.
```rust
#[test]
fn minimal_repro() {
    type MyQuery<'a> = (&'a usize, &'a f32);
    let mut world = hecs::World::new();
    world.spawn((0usize, 0f32));
    world.spawn((0usize, 0f32));
    let entities = world
        .query::<MyQuery>()
        .iter()
        .map(|(entity, _)| entity)
        .collect::<Vec<_>>();
    assert_eq!(entities.len(), 2);
    assert!(world.despawn(entities[0]).is_ok());
    let entities = world
        .query::<MyQuery>()
        .iter()
        .map(|(entity, _)| entity)
        .collect::<Vec<_>>();
    assert_eq!(entities.len(), 1);
}
```
Ralith: Fixed and expanded tests to cover that case, thanks!

Patch:
diff --git a/src/borrow.rs b/src/borrow.rs
index 043ee72..f1a95c0 100644
--- a/src/borrow.rs
+++ b/src/borrow.rs
@@ -147,13 +147,24 @@ impl<'a, T: Component> DerefMut for RefMut<'a, T> {
 /// Handle to an entity with any component types
 #[derive(Copy, Clone)]
 pub struct EntityRef<'a> {
-    archetype: &'a Archetype,
+    archetype: Option<&'a Archetype>,
     index: u32,
 }
 
 impl<'a> EntityRef<'a> {
+    /// Construct a `Ref` for an entity with no components
+    pub(crate) fn empty() -> Self {
+        Self {
+            archetype: None,
+            index: 0,
+        }
+    }
+
     pub(crate) unsafe fn new(archetype: &'a Archetype, index: u32) -> Self {
-        Self { archetype, index }
+        Self {
+            archetype: Some(archetype),
+            index,
+        }
     }
 
     /// Borrow the component of type `T`, if it exists
@@ -161,14 +172,14 @@ impl<'a> EntityRef<'a> {
     /// Panics if the component is already uniquely borrowed from another entity with the same
     /// components.
     pub fn get<T: Component>(&self) -> Option<Ref<'a, T>> {
-        Some(unsafe { Ref::new(self.archetype, self.index).ok()? })
+        Some(unsafe { Ref::new(self.archetype?, self.index).ok()? })
     }
 
     /// Uniquely borrow the component of type `T`, if it exists
     ///
     /// Panics if the component is already borrowed from another entity with the same components.
     pub fn get_mut<T: Component>(&self) -> Option<RefMut<'a, T>> {
-        Some(unsafe { RefMut::new(self.archetype, self.index).ok()? })
+        Some(unsafe { RefMut::new(self.archetype?, self.index).ok()? })
     }
 }
 
diff --git a/src/bundle.rs b/src/bundle.rs
index e546f7f..dbce023 100644
--- a/src/bundle.rs
+++ b/src/bundle.rs
@@ -22,8 +22,10 @@ use crate::Component;
 
 /// A dynamically typed collection of components
 pub trait DynamicBundle {
+    /// Invoke a callback on the fields' type IDs, sorted by descending alignment then id
     #[doc(hidden)]
     fn with_ids<T>(&self, f: impl FnOnce(&[TypeId]) -> T) -> T;
+    /// Obtain the fields' TypeInfos, sorted by descending alignment then id
     #[doc(hidden)]
     fn type_info(&self) -> Vec<TypeInfo>;
     /// Allow a callback to move all components out of the bundle
diff --git a/src/entities.rs b/src/entities.rs
index 3984b72..e35d56e 100644
--- a/src/entities.rs
+++ b/src/entities.rs
@@ -1,5 +1,8 @@
+use alloc::boxed::Box;
 use alloc::vec::Vec;
-use core::fmt;
+use core::convert::TryFrom;
+use core::sync::atomic::{AtomicU32, Ordering};
+use core::{fmt, mem};
 #[cfg(feature = "std")]
 use std::error::Error;
 
@@ -51,64 +54,246 @@ impl fmt::Debug for Entity {
 
 #[derive(Default)]
 pub(crate) struct Entities {
-    pub meta: Vec<EntityMeta>,
-    free: Vec<u32>,
+    pub meta: Box<[EntityMeta]>,
+    // Reserved entities outside the range of `meta`, having implicit generation 0, archetype 0, and
+    // undefined index. Calling `flush` converts these to real entities, which can have a fully
+    // defined location.
+    pending: AtomicU32,
+    // Unused entity IDs below `meta.len()`
+    free: Box<[u32]>,
+    free_cursor: AtomicU32,
+    // Reserved IDs within `meta.len()` with implicit archetype 0 and undefined index. Should be
+    // consumed and used to initialize locations to produce real entities after calling `flush`.
+    reserved: Box<[AtomicU32]>,
+    reserved_cursor: AtomicU32,
 }
 
 impl Entities {
+    /// Reserve an entity ID concurrently
+    ///
+    /// Storage for entity generation and location is lazily allocated by calling `flush`. Locations
+    /// can be determined by the return value of `flush` and by iterating through the `reserved`
+    /// accessors, and should all be written immediately after flushing.
+    pub fn reserve(&self) -> Entity {
+        loop {
+            let index = self.free_cursor.load(Ordering::Relaxed);
+            match index.checked_sub(1) {
+                // The freelist is empty, so increment `pending` to arrange for a new entity with a
+                // predictable ID to be allocated on the next `flush` call
+                None => {
+                    let n = self.pending.fetch_add(1, Ordering::Relaxed);
+                    return Entity {
+                        generation: 0,
+                        id: u32::try_from(self.meta.len())
+                            .ok()
+                            .and_then(|x| x.checked_add(n))
+                            .expect("too many entities"),
+                    };
+                }
+                // The freelist has entities in it, so move the last entry to the reserved list, to
+                // be consumed by the caller as part of a higher-level flush.
+                Some(next) => {
+                    // We don't care about memory ordering here so long as we get our slot.
+                    if self
+                        .free_cursor
+                        .compare_exchange_weak(index, next, Ordering::Relaxed, Ordering::Relaxed)
+                        .is_err()
+                    {
+                        // Another thread already consumed this slot, start over.
+                        continue;
+                    }
+                    let id = self.free[next as usize];
+                    let reservation = self.reserved_cursor.fetch_add(1, Ordering::Relaxed);
+                    self.reserved[reservation as usize].store(id, Ordering::Relaxed);
+                    return Entity {
+                        generation: self.meta[id as usize].generation,
+                        id,
+                    };
+                }
+            }
+        }
+    }
+
+    /// Allocate an entity ID directly
+    ///
+    /// Location should be written immediately.
     pub fn alloc(&mut self) -> Entity {
-        match self.free.pop() {
-            Some(i) => Entity {
-                generation: self.meta[i as usize].generation,
-                id: i,
-            },
+        debug_assert_eq!(
+            self.pending.load(Ordering::Relaxed),
+            0,
+            "allocator must be flushed before potentially growing"
+        );
+        let index = self.free_cursor.load(Ordering::Relaxed);
+        match index.checked_sub(1) {
             None => {
-                let i = self.meta.len() as u32;
-                self.meta.push(EntityMeta {
-                    generation: 0,
-                    location: Location {
-                        archetype: 0,
-                        index: 0,
-                    },
-                });
+                self.grow(0);
+                let cursor = self.free_cursor.fetch_sub(1, Ordering::Relaxed);
+                let id = self.free[(cursor - 1) as usize];
                 Entity {
-                    generation: 0,
-                    id: i,
+                    generation: self.meta[id as usize].generation,
+                    id,
+                }
+            }
+            Some(next) => {
+                // Not racey due to &mut self
+                self.free_cursor.store(next, Ordering::Relaxed);
+                let id = self.free[next as usize];
+                Entity {
+                    generation: self.meta[id as usize].generation,
+                    id,
                 }
             }
         }
     }
 
+    /// Destroy an entity, allowing it to be reused
+    ///
+    /// Must not be called on reserved entities prior to `flush`.
     pub 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)
+        let loc = mem::replace(
+            &mut meta.location,
+            Location {
+                archetype: 0,
+                // Guard against bugs in reservation handling
+                index: u32::max_value(),
+            },
+        );
+        let index = self.free_cursor.fetch_add(1, Ordering::Relaxed); // Not racey due to &mut self
+        self.free[index as usize] = entity.id;
+        debug_assert!(
+            loc.index != u32::max_value(),
+            "free called on reserved entity without flush"
+        );
+        Ok(loc)
+    }
+
+    pub fn contains(&self, entity: Entity) -> bool {
+        if entity.id >= self.meta.len() as u32 {
+            return true;
+        }
+        self.meta[entity.id as usize].generation == entity.generation
     }
 
     pub fn clear(&mut self) {
-        self.meta.clear();
-        self.free.clear();
+        // Not racey due to &mut self
+        self.free_cursor
+            .store(self.meta.len() as u32, Ordering::Relaxed);
+        for (i, x) in self.free.iter_mut().enumerate() {
+            *x = i as u32;
+        }
+        self.pending.store(0, Ordering::Relaxed);
+        self.reserved_cursor.store(0, Ordering::Relaxed);
     }
 
+    /// Access the location storage of an entity
+    ///
+    /// Must not be called on pending entities.
     pub 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);
+        if meta.generation == entity.generation {
+            Ok(&mut meta.location)
+        } else {
+            Err(NoSuchEntity)
         }
-        Ok(&mut meta.location)
     }
 
+    /// Returns `Ok(Location { archetype: 0, index: undefined })` for pending entities
     pub fn get(&self, entity: Entity) -> Result<Location, NoSuchEntity> {
+        if self.meta.len() <= entity.id as usize {
+            return Ok(Location {
+                archetype: 0,
+                index: u32::max_value(),
+            });
+        }
         let meta = &self.meta[entity.id as usize];
         if meta.generation != entity.generation {
             return Err(NoSuchEntity);
         }
+        if meta.location.archetype == 0 {
+            return Ok(Location {
+                archetype: 0,
+                index: u32::max_value(),
+            });
+        }
         Ok(meta.location)
     }
+
+    /// Allocate space for and enumerate pending entities
+    pub fn flush(&mut self) -> impl Iterator<Item = u32> {
+        let pending = self.pending.swap(0, Ordering::Relaxed); // Not racey due to &mut self
+
+        if pending != 0 {
+            let first = self.meta.len() as u32;
+            self.grow(pending);
+            first..(first + pending)
+        } else {
+            0..0
+        }
+    }
+
+    // The following three methods allow iteration over `reserved` simultaneous to location
+    // writes. This is a lazy hack, but we only use it in `World::flush` so the complexity and unsafety
+    // involved in producing an `impl Iterator<Item=(u32, &mut Location)>` isn't a clear win.
+    pub fn reserved_len(&self) -> u32 {
+        self.reserved_cursor.load(Ordering::Relaxed)
+    }
+
+    pub fn reserved(&self, i: u32) -> u32 {
+        debug_assert!(i < self.reserved_len());
+        self.reserved[i as usize].load(Ordering::Relaxed)
+    }
+
+    pub fn clear_reserved(&mut self) {
+        self.reserved_cursor.store(0, Ordering::Relaxed);
+    }
+
+    /// Expand storage and mark all but the first `pending` of the new slots as free
+    fn grow(&mut self, pending: u32) {
+        let new_len = (self.meta.len() * 2)
+            .max(self.meta.len() + pending as usize)
+            .max(1024);
+        let mut new_meta = Vec::with_capacity(new_len);
+        new_meta.extend_from_slice(&self.meta);
+        new_meta.resize(
+            new_len,
+            EntityMeta {
+                generation: 0,
+                location: Location {
+                    archetype: 0,
+                    index: u32::max_value(), // dummy value, to be filled in
+                },
+            },
+        );
+
+        let free_cursor = self.free_cursor.load(Ordering::Relaxed); // Not racey due to &mut self
+        let mut new_free = Vec::with_capacity(new_len);
+        new_free.extend_from_slice(&self.free[0..free_cursor as usize]);
+        // Add freshly allocated trailing free slots
+        new_free.extend(((self.meta.len() as u32 + pending)..new_len as u32).rev());
+        debug_assert!(new_free.len() <= new_len);
+        self.free_cursor
+            .store(new_free.len() as u32, Ordering::Relaxed); // Not racey due to &mut self
+
+        // Zero-fill
+        new_free.resize(new_len, 0);
+
+        self.meta = new_meta.into();
+        self.free = new_free.into();
+        let mut new_reserved = Vec::with_capacity(new_len);
+        // Not racey due to &mut self
+        let reserved_cursor = self.reserved_cursor.load(Ordering::Relaxed);
+        for x in &self.reserved[..reserved_cursor as usize] {
+            new_reserved.push(AtomicU32::new(x.load(Ordering::Relaxed)));
+        }
+        new_reserved.resize_with(new_len, || AtomicU32::new(0));
+        for _ in 0..new_len {}
+        self.reserved = new_reserved.into();
+    }
 }
 
 #[derive(Copy, Clone)]
diff --git a/src/world.rs b/src/world.rs
index 447971c..8d8748b 100644
--- a/src/world.rs
+++ b/src/world.rs
@@ -22,7 +22,7 @@ use std::error::Error;
 use hashbrown::{HashMap, HashSet};
 
 use crate::archetype::Archetype;
-use crate::entities::{Entities, EntityMeta};
+use crate::entities::{Entities, Location};
 use crate::{
     Bundle, DynamicBundle, Entity, EntityRef, MissingComponent, NoSuchEntity, Query, QueryBorrow,
     Ref, RefMut,
@@ -35,7 +35,6 @@ use crate::{
 ///
 /// The components of entities who have the same set of component types are stored in contiguous
 /// runs, allowing for extremely fast, cache-friendly iteration.
-#[derive(Default)]
 pub struct World {
     entities: Entities,
     index: HashMap<Vec<TypeId>, u32>,
@@ -45,7 +44,14 @@ pub struct World {
 impl World {
     /// Create an empty world
     pub fn new() -> Self {
-        Self::default()
+        // `flush` assumes archetype 0 always exists, representing entities with no components.
+        let mut archetypes = Vec::new();
+        archetypes.push(Archetype::new(Vec::new()));
+        Self {
+            entities: Entities::default(),
+            index: HashMap::default(),
+            archetypes,
+        }
     }
 
     /// Create an entity with certain components
@@ -66,8 +72,12 @@ impl World {
     /// let b = world.spawn((456, true));
     /// ```
     pub fn spawn(&mut self, components: impl DynamicBundle) -> Entity {
+        // Ensure all entity allocations are accounted for so `self.entities` can realloc if
+        // necessary
+        self.flush();
+
         let entity = self.entities.alloc();
-        let archetype = components.with_ids(|ids| {
+        let archetype_id = 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()));
@@ -75,21 +85,39 @@ impl World {
                 x
             })
         });
-        self.entities.meta[entity.id as usize].location.archetype = archetype;
-        let archetype = &mut self.archetypes[archetype as usize];
+
+        let archetype = &mut self.archetypes[archetype_id 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
             });
+            self.entities.meta[entity.id as usize].location = Location {
+                archetype: archetype_id,
+                index,
+            };
         }
         entity
     }
 
+    /// Allocate an entity ID concurrently
+    ///
+    /// Unlike `spawn`, this can be called simultaneously to other operations on the `World` such as
+    /// queries, but does not immediately create an entity. Reserved entities are not visible to
+    /// queries or world iteration, but can be otherwise operated on freely. Operations that
+    /// uniquely borrow the world, such as `insert` or `despawn`, will cause all outstanding
+    /// reserved entities to become real entities before proceeding. This can also be done
+    /// explicitly by calling `flush`.
+    ///
+    /// Useful for reserving an ID that will later have components attached to it with `insert`.
+    pub fn reserve(&self) -> Entity {
+        self.entities.reserve()
+    }
+
     /// Destroy an entity and all its components
     pub fn despawn(&mut self, entity: Entity) -> Result<(), NoSuchEntity> {
+        self.flush();
         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;
@@ -109,7 +137,7 @@ impl World {
 
     /// Whether `entity` still exists
     pub fn contains(&self, entity: Entity) -> bool {
-        self.entities.meta[entity.id as usize].generation == entity.generation
+        self.entities.contains(entity)
     }
 
     /// Efficiently iterate over all entities that have certain components
@@ -160,6 +188,9 @@ impl World {
     /// components.
     pub fn get<T: Component>(&self, entity: Entity) -> Result<Ref<'_, T>, ComponentError> {
         let loc = self.entities.get(entity)?;
+        if loc.archetype == 0 {
+            return Err(MissingComponent::new::<T>().into());
+        }
         Ok(unsafe { Ref::new(&self.archetypes[loc.archetype as usize], loc.index)? })
     }
 
@@ -168,6 +199,9 @@ impl World {
     /// Panics if the component is already borrowed from another entity with the same components.
     pub fn get_mut<T: Component>(&self, entity: Entity) -> Result<RefMut<'_, T>, ComponentError> {
         let loc = self.entities.get(entity)?;
+        if loc.archetype == 0 {
+            return Err(MissingComponent::new::<T>().into());
+        }
         Ok(unsafe { RefMut::new(&self.archetypes[loc.archetype as usize], loc.index)? })
     }
 
@@ -175,8 +209,10 @@ impl World {
     ///
     /// Does not immediately borrow any component.
     pub fn entity(&self, entity: Entity) -> Result<EntityRef<'_>, NoSuchEntity> {
-        let loc = self.entities.get(entity)?;
-        Ok(unsafe { EntityRef::new(&self.archetypes[loc.archetype as usize], loc.index) })
+        Ok(match self.entities.get(entity)? {
+            Location { archetype: 0, .. } => EntityRef::empty(),
+            loc => unsafe { EntityRef::new(&self.archetypes[loc.archetype as usize], loc.index) },
+        })
     }
 
     /// Iterate over all entities in the world
@@ -190,10 +226,13 @@ impl World {
     /// let mut world = World::new();
     /// let a = world.spawn(());
     /// let b = world.spawn(());
-    /// assert_eq!(world.iter().map(|(id, _)| id).collect::<Vec<_>>(), &[a, b]);
+    /// let ids = world.iter().map(|(id, _)| id).collect::<Vec<_>>();
+    /// assert_eq!(ids.len(), 2);
+    /// assert!(ids.contains(&a));
+    /// assert!(ids.contains(&b));
     /// ```
     pub fn iter(&self) -> Iter<'_> {
-        Iter::new(&self.archetypes, &self.entities.meta)
+        Iter::new(&self.archetypes, &self.entities)
     }
 
     /// Add `components` to `entity`
@@ -219,8 +258,10 @@ impl World {
     ) -> Result<(), NoSuchEntity> {
         use hashbrown::hash_map::Entry;
 
+        self.flush();
         let loc = self.entities.get_mut(entity)?;
         unsafe {
+            // Assemble Vec<TypeInfo> for the final entity
             let arch = &mut self.archetypes[loc.archetype as usize];
             let mut info = arch.types().to_vec();
             for ty in components.type_info() {
@@ -232,6 +273,7 @@ impl World {
             }
             info.sort();
 
+            // Find the archetype it'll live in
             let elements = info.iter().map(|x| x.id()).collect::<Vec<_>>();
             let target = match self.index.entry(elements) {
                 Entry::Occupied(x) => *x.get(),
@@ -242,7 +284,9 @@ impl World {
                     index
                 }
             };
+
             if target == loc.archetype {
+                // Update components in the current archetype
                 let arch = &mut self.archetypes[loc.archetype as usize];
                 components.put(|ptr, ty, size| {
                     arch.put_dynamic(ptr, ty, size, loc.index);
@@ -251,6 +295,7 @@ impl World {
                 return Ok(());
             }
 
+            // Move into a new archetype
             let (source_arch, target_arch) = index2(
                 &mut self.archetypes,
                 loc.archetype as usize,
@@ -305,6 +350,7 @@ impl World {
     pub fn remove<T: Bundle>(&mut self, entity: Entity) -> Result<T, ComponentError> {
         use hashbrown::hash_map::Entry;
 
+        self.flush();
         let loc = self.entities.get_mut(entity)?;
         unsafe {
             let removed = T::with_static_ids(|ids| ids.iter().copied().collect::<HashSet<_>>());
@@ -364,6 +410,9 @@ impl World {
     /// same component of `entity` may be live simultaneous to the returned reference.
     pub unsafe fn get_unchecked<T: Component>(&self, entity: Entity) -> Result<&T, ComponentError> {
         let loc = self.entities.get(entity)?;
+        if loc.archetype == 0 {
+            return Err(MissingComponent::new::<T>().into());
+        }
         Ok(&*self.archetypes[loc.archetype as usize]
             .get::<T>()
             .ok_or_else(MissingComponent::new::<T>)?
@@ -384,17 +433,41 @@ impl World {
         entity: Entity,
     ) -> Result<&mut T, ComponentError> {
         let loc = self.entities.get(entity)?;
+        if loc.archetype == 0 {
+            return Err(MissingComponent::new::<T>().into());
+        }
         Ok(&mut *self.archetypes[loc.archetype as usize]
             .get::<T>()
             .ok_or_else(MissingComponent::new::<T>)?
             .as_ptr()
             .add(loc.index as usize))
     }
+
+    /// Convert all reserved entities into empty entities that can be iterated and accessed
+    ///
+    /// Invoked implicitly by `spawn`, `despawn`, `insert`, and `remove`.
+    pub fn flush(&mut self) {
+        let arch = &mut self.archetypes[0];
+        for id in self.entities.flush() {
+            self.entities.meta[id as usize].location.index = unsafe { arch.allocate(id) };
+        }
+        for i in 0..self.entities.reserved_len() {
+            let id = self.entities.reserved(i);
+            self.entities.meta[id as usize].location.index = unsafe { arch.allocate(id) };
+        }
+        self.entities.clear_reserved();
+    }
 }
 
 unsafe impl Send for World {}
 unsafe impl Sync for World {}
 
+impl Default for World {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
 impl<'a> IntoIterator for &'a World {
     type IntoIter = Iter<'a>;
     type Item = (Entity, EntityRef<'a>);
@@ -455,13 +528,13 @@ impl<T: Send + Sync + 'static> Component for T {}
 /// Iterator over all of a world's entities
 pub struct Iter<'a> {
     archetypes: core::slice::Iter<'a, Archetype>,
-    entities: &'a [EntityMeta],
+    entities: &'a Entities,
     current: Option<&'a Archetype>,
     index: u32,
 }
 
 impl<'a> Iter<'a> {
-    fn new(archetypes: &'a [Archetype], entities: &'a [EntityMeta]) -> Self {
+    fn new(archetypes: &'a [Archetype], entities: &'a Entities) -> Self {
         Self {
             archetypes: archetypes.iter(),
             entities,
@@ -494,7 +567,7 @@ impl<'a> Iterator for Iter<'a> {
                     return Some((
                         Entity {
                             id,
-                            generation: self.entities[id as usize].generation,
+                            generation: self.entities.meta[id as usize].generation,
                         },
                         unsafe { EntityRef::new(current, index) },
                     ));
@@ -504,7 +577,7 @@ impl<'a> Iterator for Iter<'a> {
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        (0, Some(self.entities.len()))
+        (0, Some(self.entities.meta.len()))
     }
 }
 
@@ -532,7 +605,7 @@ mod tests {
     use super::*;
 
     #[test]
-    fn id_reuse() {
+    fn reuse_empty() {
         let mut world = World::new();
         let a = world.spawn(());
         world.despawn(a).unwrap();
@@ -540,4 +613,17 @@ mod tests {
         assert_eq!(a.id, b.id);
         assert_ne!(a.generation, b.generation);
     }
+
+    #[test]
+    fn reuse_populated() {
+        let mut world = World::new();
+        let a = world.spawn((42,));
+        assert_eq!(*world.get::<i32>(a).unwrap(), 42);
+        world.despawn(a).unwrap();
+        let b = world.spawn((true,));
+        assert_eq!(a.id, b.id);
+        assert_ne!(a.generation, b.generation);
+        assert!(world.get::<i32>(b).is_err());
+        assert!(*world.get::<bool>(b).unwrap());
+    }
 }


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index 6348443..4b19bef 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -276,3 +276,24 @@ fn remove_missing() {
     let e = world.spawn(("abc", 123));
     assert!(world.remove_one::<bool>(e).is_err());
 }
+
+#[test]
+fn reserve() {
+    let mut world = World::new();
+    let a = world.reserve();
+    let b = world.reserve();
+
+    assert_eq!(world.query::<()>().iter().count(), 0);
+
+    world.flush();
+
+    let entities = world
+        .query::<()>()
+        .iter()
+        .map(|(e, _)| e)
+        .collect::<Vec<_>>();
+
+    assert_eq!(entities.len(), 2);
+    assert!(entities.contains(&a));
+    assert!(entities.contains(&b));
+}