Repository: Ralith/hecs
Pull request #199 (2021-11-02 09:32:12)

command buffer helper
As regards the [127](https://github.com/Ralith/hecs/issues/127#issue-782330578) this is a simple and efficient solution to the issue.

It's faster than the naive Vec<EntityBuilder> approach.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 55e498b..a3da19e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@
 - `EntityRef::has` to efficiently check for the presence of a component without borrowing it
 - `EntityBulider::new_cloneable` constructs an `EntityBuilder` that builds a `ReusableBuiltEntity`,
   which can be spawned repeatedly by reference.
+- `Satisfies` query combinator, which yields a `bool` without borrowing any components
 
 ### Changed
 - Added a niche to `Entity`, making `Option<Entity>` the same size as a bare `Entity`. As a
diff --git a/Cargo.toml b/Cargo.toml
index 0939329..4c82820 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -32,6 +32,7 @@ hecs-macros = { path = "macros", version = "0.7.0", optional = true }
 hashbrown = { version = "0.11.0", default-features = false, features = ["ahash", "inline-more"] }
 lazy_static = { version = "1.4.0", optional = true, features = ["spin_no_std"] }
 serde = { version = "1.0.117", default-features = false, optional = true }
+spin = { version = "0.9.2", default-features = false, features = ["mutex", "spin_mutex"] }
 
 [dev-dependencies]
 bencher = "0.1.5"
diff --git a/benches/bench.rs b/benches/bench.rs
index 35831de..b6539a2 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -207,6 +207,16 @@ fn build_cloneable(b: &mut Bencher) {
     });
 }
 
+fn spawn_buffered(b: &mut Bencher) {
+    let mut world = World::new();
+    let mut buffer = CommandBuffer::new();
+    let ent = world.reserve_entity();
+    b.iter(|| {
+        buffer.spawn_at(ent, (Position(0.0), Velocity(0.0)));
+        buffer.run_on(&mut world);
+    });
+}
+
 benchmark_group!(
     benches,
     spawn_tuple,
@@ -222,5 +232,6 @@ benchmark_group!(
     iterate_mut_cached_100_by_50,
     build,
     build_cloneable,
+    spawn_buffered,
 );
 benchmark_main!(benches);
diff --git a/src/command_buffer.rs b/src/command_buffer.rs
new file mode 100644
index 0000000..6aa2188
--- /dev/null
+++ b/src/command_buffer.rs
@@ -0,0 +1,242 @@
+// Copyright 2019 Google LLC
+//
+// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
+// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
+// http://opensource.org/licenses/MIT>, at your option. This file may not be
+// copied, modified, or distributed except according to those terms.
+
+use core::any::TypeId;
+use core::ptr::{self, NonNull};
+
+use crate::alloc::alloc::{alloc, dealloc, Layout};
+use crate::alloc::vec::Vec;
+use crate::archetype::TypeInfo;
+use crate::Entity;
+use crate::World;
+use crate::{align, DynamicBundle};
+
+/// Allows spawn operations to be buffered for future application to a ['World']
+///
+/// ```
+/// # use hecs::*;
+/// let mut world = World::new();
+/// let reserved_ent = world.reserve_entity();
+/// let mut entity_buffer = CommandBuffer::new();
+/// entity_buffer.spawn_at(reserved_ent,(true,0.10));
+/// entity_buffer.run_on(&mut world); // buffer can now be reused
+/// assert!(world.contains(reserved_ent));
+/// ```
+pub struct CommandBuffer {
+    entities: Vec<EntityIndex>,
+    storage: NonNull<u8>,
+    layout: Layout,
+    cursor: usize,
+    info: Vec<ComponentInfo>,
+    ids: Vec<TypeId>,
+}
+
+impl CommandBuffer {
+    /// Create an empty buffer
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    unsafe fn grow(
+        min_size: usize,
+        cursor: usize,
+        align: usize,
+        storage: NonNull<u8>,
+    ) -> (NonNull<u8>, Layout) {
+        let layout = Layout::from_size_align(min_size.next_power_of_two().max(64), align).unwrap();
+        let new_storage = NonNull::new_unchecked(alloc(layout));
+        ptr::copy_nonoverlapping(storage.as_ptr(), new_storage.as_ptr(), cursor);
+        (new_storage, layout)
+    }
+
+    unsafe fn add_inner(&mut self, ptr: *mut u8, ty: TypeInfo) {
+        let offset = align(self.cursor, ty.layout().align());
+        let end = offset + ty.layout().size();
+
+        if end > self.layout.size() || ty.layout().align() > self.layout.align() {
+            let new_align = self.layout.align().max(ty.layout().align());
+            let (new_storage, new_layout) = Self::grow(end, self.cursor, new_align, self.storage);
+            if self.layout.size() != 0 {
+                dealloc(self.storage.as_ptr(), self.layout);
+            }
+            self.storage = new_storage;
+            self.layout = new_layout;
+        }
+
+        let addr = self.storage.as_ptr().add(offset);
+        ptr::copy_nonoverlapping(ptr, addr, ty.layout().size());
+        self.info.push(ComponentInfo {
+            ty_info: ty,
+            offset,
+        });
+        self.cursor = end;
+    }
+
+    /// Record an entity spawn operation
+    pub fn spawn_at(&mut self, ent: Entity, bundle: impl DynamicBundle) {
+        let len = bundle.type_info().len();
+        unsafe {
+            bundle.put(|ptr, ty| self.add_inner(ptr, ty));
+        }
+        let begin = self.entities.last().map_or(0, |x| x.end);
+        let end = begin + len;
+        self.entities.push(EntityIndex {
+            entity: ent,
+            begin,
+            end,
+        });
+    }
+
+    /// Spawn every entity recorded with their components
+    ///
+    /// # Example
+    /// ```
+    /// # use hecs::*;
+    /// let mut world = World::new();
+    /// let a = world.reserve_entity();
+    /// let mut recorder = CommandBuffer::new();
+    /// recorder.spawn_at(a, (false,0.0));
+    /// recorder.run_on(&mut world);
+    /// assert!(world.contains(a));
+    /// ```
+    pub fn run_on(&mut self, world: &mut World) {
+        let mut mark = self.entities.len() - 1;
+
+        for index in self.entities.iter() {
+            self.info[index.begin..index.end].sort_unstable_by_key(|z| z.ty_info);
+        }
+
+        for _ in 0..self.entities.len() {
+            let (ent, comps) = self.build(mark);
+            world.spawn_at(ent, comps);
+            if mark != 0 {
+                mark -= 1;
+            }
+        }
+        self.clear();
+    }
+
+    fn build(&mut self, mark: usize) -> (Entity, ReadyBuffer<'_>) {
+        self.ids.clear();
+        self.ids.extend(
+            self.info[self.entities[mark].begin..self.entities[mark].end]
+                .iter()
+                .map(|x| x.ty_info.id()),
+        );
+        let entity = self.entities[mark].entity;
+        (entity, ReadyBuffer { buffer: self, mark })
+    }
+
+    /// Drop previously `recorded` entities and their components
+    ///
+    /// Recorder is cleared implicitly when entities are spawned, so usually this doesn't need to
+    /// be called
+    pub fn clear(&mut self) {
+        self.ids.clear();
+        self.entities.clear();
+        self.cursor = 0;
+        unsafe {
+            for info in self.info.drain(..) {
+                info.ty_info.drop(self.storage.as_ptr().add(info.offset));
+            }
+        }
+    }
+}
+
+unsafe impl Send for CommandBuffer {}
+unsafe impl Sync for CommandBuffer {}
+
+impl Drop for CommandBuffer {
+    fn drop(&mut self) {
+        self.clear();
+        if self.layout.size() != 0 {
+            unsafe {
+                dealloc(self.storage.as_ptr(), self.layout);
+            }
+        }
+    }
+}
+
+impl Default for CommandBuffer {
+    /// Create an empty buffer
+    fn default() -> Self {
+        Self {
+            entities: Vec::new(),
+            storage: NonNull::dangling(),
+            layout: Layout::from_size_align(0, 8).unwrap(),
+            cursor: 0,
+            info: Vec::new(),
+            ids: Vec::new(),
+        }
+    }
+}
+
+/// The output of an '[CommandBuffer]` suitable for passing to
+/// [`World::spawn_into`](crate::World::spawn_into)
+struct ReadyBuffer<'a> {
+    buffer: &'a mut CommandBuffer,
+    mark: usize,
+}
+unsafe impl DynamicBundle for ReadyBuffer<'_> {
+    fn with_ids<T>(&self, f: impl FnOnce(&[TypeId]) -> T) -> T {
+        f(&self.buffer.ids)
+    }
+
+    fn type_info(&self) -> Vec<TypeInfo> {
+        self.buffer.info[self.buffer.entities[self.mark].begin..self.buffer.entities[self.mark].end]
+            .iter()
+            .map(|x| x.ty_info)
+            .collect()
+    }
+
+    unsafe fn put(self, mut f: impl FnMut(*mut u8, TypeInfo)) {
+        for info in self
+            .buffer
+            .info
+            .drain(self.buffer.entities[self.mark].begin..self.buffer.entities[self.mark].end)
+        {
+            let ptr = self.buffer.storage.as_ptr().add(info.offset);
+            f(ptr, info.ty_info);
+        }
+    }
+}
+
+/// Data required to store components and their offset  
+struct ComponentInfo {
+    ty_info: TypeInfo,
+    // Position in 'storage'
+    offset: usize,
+}
+
+/// Data of buffered 'entity' and its relative position in component data
+struct EntityIndex {
+    entity: Entity,
+    // Range of associated indices in `CommandBuffer`'s `info` member
+    begin: usize,
+    end: usize,
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn populate_archetypes() {
+        let mut world = World::new();
+        let mut buffer = CommandBuffer::new();
+        let ent = world.reserve_entity();
+        let enta = world.reserve_entity();
+        let entb = world.reserve_entity();
+        let entc = world.reserve_entity();
+        buffer.spawn_at(ent, (true, "a"));
+        buffer.spawn_at(entc, (true, "a"));
+        buffer.spawn_at(enta, (1, 1.0));
+        buffer.spawn_at(entb, (1.0, "a"));
+        buffer.run_on(&mut world);
+        assert_eq!(world.archetypes().len(), 4);
+    }
+}
diff --git a/src/entities.rs b/src/entities.rs
index 50a8473..092a273 100644
--- a/src/entities.rs
+++ b/src/entities.rs
@@ -4,7 +4,7 @@ use core::convert::TryFrom;
 use core::iter::ExactSizeIterator;
 use core::num::{NonZeroU32, NonZeroU64};
 use core::ops::Range;
-use core::sync::atomic::{AtomicI64, Ordering};
+use core::sync::atomic::{AtomicIsize, Ordering};
 use core::{fmt, mem};
 #[cfg(feature = "std")]
 use std::error::Error;
@@ -171,7 +171,7 @@ pub(crate) struct Entities {
     //
     // Once `flush()` is done, `free_cursor` will equal `pending.len()`.
     pending: Vec<u32>,
-    free_cursor: AtomicI64,
+    free_cursor: AtomicIsize,
     len: u32,
 }
 
@@ -183,8 +183,10 @@ impl Entities {
         // Use one atomic subtract to grab a range of new IDs. The range might be
         // entirely nonnegative, meaning all IDs come from the freelist, or entirely
         // negative, meaning they are all new IDs to allocate, or a mix of both.
-        let range_end = self.free_cursor.fetch_sub(count as i64, Ordering::Relaxed);
-        let range_start = range_end - count as i64;
+        let range_end = self
+            .free_cursor
+            .fetch_sub(count as isize, Ordering::Relaxed);
+        let range_start = range_end - count as isize;
 
         let freelist_range = range_start.max(0) as usize..range_end.max(0) as usize;
 
@@ -201,7 +203,7 @@ impl Entities {
             // In this example, we truncate the end to 0, leaving us with `-3..0`.
             // Then we negate these values to indicate how far beyond the end of `meta.end()`
             // to go, yielding `meta.len()+0 .. meta.len()+3`.
-            let base = self.meta.len() as i64;
+            let base = self.meta.len() as isize;
 
             let new_id_end = u32::try_from(base - range_start).expect("too many entities");
 
@@ -238,7 +240,7 @@ impl Entities {
             // and farther beyond `meta.len()`.
             Entity {
                 generation: NonZeroU32::new(1).unwrap(),
-                id: u32::try_from(self.meta.len() as i64 - n).expect("too many entities"),
+                id: u32::try_from(self.meta.len() as isize - n).expect("too many entities"),
             }
         }
     }
@@ -259,7 +261,7 @@ impl Entities {
 
         self.len += 1;
         if let Some(id) = self.pending.pop() {
-            let new_free_cursor = self.pending.len() as i64;
+            let new_free_cursor = self.pending.len() as isize;
             self.free_cursor.store(new_free_cursor, Ordering::Relaxed); // Not racey due to &mut self
             Entity {
                 generation: self.meta[id as usize].generation,
@@ -326,14 +328,14 @@ impl Entities {
 
         let loc = if entity.id as usize >= self.meta.len() {
             self.pending.extend((self.meta.len() as u32)..entity.id);
-            let new_free_cursor = self.pending.len() as i64;
+            let new_free_cursor = self.pending.len() as isize;
             self.free_cursor.store(new_free_cursor, Ordering::Relaxed); // Not racey due to &mut self
             self.meta.resize(entity.id as usize + 1, EntityMeta::EMPTY);
             self.len += 1;
             None
         } else if let Some(index) = self.pending.iter().position(|item| *item == entity.id) {
             self.pending.swap_remove(index);
-            let new_free_cursor = self.pending.len() as i64;
+            let new_free_cursor = self.pending.len() as isize;
             self.free_cursor.store(new_free_cursor, Ordering::Relaxed); // Not racey due to &mut self
             self.len += 1;
             None
@@ -367,7 +369,7 @@ impl Entities {
 
         self.pending.push(entity.id);
 
-        let new_free_cursor = self.pending.len() as i64;
+        let new_free_cursor = self.pending.len() as isize;
         self.free_cursor.store(new_free_cursor, Ordering::Relaxed); // Not racey due to &mut self
         self.len -= 1;
 
@@ -379,7 +381,7 @@ impl Entities {
         self.verify_flushed();
 
         let freelist_size = self.free_cursor.load(Ordering::Relaxed);
-        let shortfall = additional as i64 - freelist_size;
+        let shortfall = additional as isize - freelist_size;
         if shortfall > 0 {
             self.meta.reserve(shortfall as usize);
         }
@@ -458,7 +460,7 @@ impl Entities {
 
     fn needs_flush(&mut self) -> bool {
         // Not racey due to &mut self
-        self.free_cursor.load(Ordering::Relaxed) != self.pending.len() as i64
+        self.free_cursor.load(Ordering::Relaxed) != self.pending.len() as isize
     }
 
     /// Allocates space for entities previously reserved with `reserve_entity` or
diff --git a/src/lib.rs b/src/lib.rs
index bd70b05..a89d8d8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -60,6 +60,7 @@ mod archetype;
 mod batch;
 mod borrow;
 mod bundle;
+mod command_buffer;
 mod entities;
 mod entity_builder;
 mod entity_ref;
@@ -69,15 +70,16 @@ mod query_one;
 pub mod serialize;
 mod world;
 
-pub use archetype::Archetype;
+pub use archetype::{Archetype, ColumnRef};
 pub use batch::{BatchIncomplete, BatchWriter, ColumnBatch, ColumnBatchBuilder, ColumnBatchType};
 pub use bundle::{Bundle, DynamicBundle, MissingComponent};
+pub use command_buffer::CommandBuffer;
 pub use entities::{Entity, NoSuchEntity};
 pub use entity_builder::{BuiltEntity, Cloneable, EntityBuilder, ReusableBuiltEntity};
 pub use entity_ref::{EntityRef, Ref, RefMut};
 pub use query::{
-    Access, BatchedIter, Or, PreparedQuery, PreparedQueryBorrow, PreparedQueryIter, Query,
-    QueryBorrow, QueryItem, QueryIter, QueryMut, With, Without,
+    Access, Batch, BatchedIter, Or, PreparedQuery, PreparedQueryBorrow, PreparedQueryIter, Query,
+    QueryBorrow, QueryItem, QueryIter, QueryMut, Satisfies, With, Without,
 };
 pub use query_one::QueryOne;
 pub use world::{
diff --git a/src/query.rs b/src/query.rs
index 4e18e93..f3bc4dc 100644
--- a/src/query.rs
+++ b/src/query.rs
@@ -490,6 +490,64 @@ unsafe impl<'a, T: Component, F: Fetch<'a>> Fetch<'a> for FetchWith<T, F> {
     }
 }
 
+/// A query that yields `true` iff an entity would satisfy the query `Q`
+///
+/// Does not borrow any components, making it faster and more concurrency-friendly than `Option<Q>`.
+///
+/// # Example
+/// ```
+/// # use hecs::*;
+/// let mut world = World::new();
+/// let a = world.spawn((123, true, "abc"));
+/// let b = world.spawn((456, false));
+/// let c = world.spawn((42, "def"));
+/// let entities = world.query::<Satisfies<&bool>>()
+///     .iter()
+///     .map(|(e, x)| (e, x))
+///     .collect::<Vec<_>>();
+/// assert_eq!(entities.len(), 3);
+/// assert!(entities.contains(&(a, true)));
+/// assert!(entities.contains(&(b, true)));
+/// assert!(entities.contains(&(c, false)));
+/// ```
+pub struct Satisfies<Q>(PhantomData<Q>);
+
+impl<Q: Query> Query for Satisfies<Q> {
+    type Fetch = FetchSatisfies<Q::Fetch>;
+}
+
+#[doc(hidden)]
+pub struct FetchSatisfies<F>(bool, PhantomData<F>);
+
+unsafe impl<'a, F: Fetch<'a>> Fetch<'a> for FetchSatisfies<F> {
+    type Item = bool;
+
+    type State = bool;
+
+    fn dangling() -> Self {
+        Self(false, PhantomData)
+    }
+
+    fn access(archetype: &Archetype) -> Option<Access> {
+        F::access(archetype).map(|_| Access::Iterate)
+    }
+
+    fn borrow(_archetype: &Archetype, _state: Self::State) {}
+    fn prepare(archetype: &Archetype) -> Option<Self::State> {
+        Some(F::prepare(archetype).is_some())
+    }
+    fn execute(_archetype: &'a Archetype, state: Self::State) -> Self {
+        Self(state, PhantomData)
+    }
+    fn release(_archetype: &Archetype, _state: Self::State) {}
+
+    fn for_each_borrow(_: impl FnMut(TypeId, bool)) {}
+
+    unsafe fn get(&self, _: usize) -> bool {
+        self.0
+    }
+}
+
 /// A borrow of a [`World`](crate::World) sufficient to execute the query `Q`
 ///
 /// Note that borrows are not released until this object is dropped.
diff --git a/src/world.rs b/src/world.rs
index 0fcad0d..b460d09 100644
--- a/src/world.rs
+++ b/src/world.rs
@@ -9,7 +9,8 @@ use crate::alloc::{vec, vec::Vec};
 use core::any::TypeId;
 use core::borrow::Borrow;
 use core::convert::TryFrom;
-use core::sync::atomic::{AtomicU64, Ordering};
+use spin::Mutex;
+
 use core::{fmt, mem, ptr};
 
 #[cfg(feature = "std")]
@@ -54,15 +55,20 @@ pub struct World {
 impl World {
     /// Create an empty world
     pub fn new() -> Self {
-        static ID: AtomicU64 = AtomicU64::new(1);
-
+        // AtomicU64 is unsupported on 32-bit MIPS and PPC architectures
+        // For compatibility, use Mutex<u64>
+        static ID: Mutex<u64> = Mutex::new(1);
+        let id = {
+            let mut id = ID.lock();
+            let next = id.checked_add(1).unwrap();
+            *id = next;
+            next
+        };
         Self {
             entities: Entities::default(),
             archetypes: ArchetypeSet::new(),
             bundle_to_archetype: HashMap::default(),
-            id: ID
-                .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |id| id.checked_add(1))
-                .unwrap(),
+            id,
         }
     }
 


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index 0c61fa3..b2a31c2 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -272,6 +272,29 @@ fn dynamic_components() {
     );
 }
 
+#[test]
+fn spawn_buffered_entity() {
+    let mut world = World::new();
+    let mut buffer = CommandBuffer::new();
+    let ent = world.reserve_entity();
+    let ent1 = world.reserve_entity();
+    let ent2 = world.reserve_entity();
+    let ent3 = world.reserve_entity();
+
+    buffer.spawn_at(ent, (1, true));
+    buffer.spawn_at(ent1, (13, 7.11, "hecs"));
+    buffer.spawn_at(ent2, (17 as i8, false, 'o'));
+    buffer.spawn_at(ent3, (2 as u8, "qwe", 101.103, false));
+
+    buffer.run_on(&mut world);
+
+    assert_eq!(*world.get::<bool>(ent).unwrap(), true);
+    assert_eq!(*world.get::<&str>(ent1).unwrap(), "hecs");
+    assert_eq!(*world.get::<i32>(ent1).unwrap(), 13);
+    assert_eq!(*world.get::<bool>(ent2).unwrap(), false);
+    assert_eq!(*world.get::<u8>(ent3).unwrap(), 2);
+}
+
 #[test]
 #[should_panic(expected = "already borrowed")]
 fn illegal_borrow() {