gloss_hecs/
world.rs

1// Copyright 2019 Google LLC
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8use crate::alloc::vec::Vec;
9// use core::any::StableTypeId;
10use crate::stabletypeid::StableTypeId;
11use core::{
12    borrow::Borrow,
13    convert::TryFrom,
14    hash::{BuildHasherDefault, Hasher},
15};
16use gloss_utils::abi_stable_aliases::std_types::map::REntry;
17use spin::Mutex;
18// use std::println;
19
20use core::{fmt, ptr};
21
22#[cfg(feature = "std")]
23use std::error::Error;
24
25use crate::{
26    alloc::boxed::Box,
27    archetype::{Archetype, StableTypeIdMap, TypeInfo},
28    entities::{Entities, EntityMeta, Location, ReserveEntitiesIterator},
29    query::assert_borrow,
30    Bundle, ColumnBatch, ComponentRef, DynamicBundle, Entity, EntityRef, Fetch, MissingComponent, NoSuchEntity, Query, QueryBorrow, QueryItem,
31    QueryMut, QueryOne, TakenEntity,
32};
33use gloss_utils::abi_stable_aliases::std_types::{RHashMap, RVec, Tuple2};
34#[cfg(target_arch = "wasm32")]
35use gloss_utils::abi_stable_aliases::FromSliceExt;
36#[cfg(not(target_arch = "wasm32"))]
37use gloss_utils::abi_stable_aliases::StableAbi;
38
39/// An unordered collection of entities, each having any number of distinctly
40/// typed components
41///
42/// Similar to `HashMap<Entity, Vec<Box<dyn Any>>>` where each `Vec` never
43/// contains two of the same type, but far more efficient to traverse.
44///
45/// The components of entities who have the same set of component types are
46/// stored in contiguous runs, allowing for extremely fast, cache-friendly
47/// iteration.
48///
49/// There is a maximum number of unique entity IDs, which means that there is a
50/// maximum number of live entities. When old entities are despawned, their IDs
51/// will be reused on a future entity, and old `Entity` values with that ID will
52/// be invalidated.
53///
54/// ### Collisions
55///
56/// If an entity is despawned and its `Entity` handle is preserved over the
57/// course of billions of following spawns and despawns, that handle may, in
58/// rare circumstances, collide with a newly-allocated `Entity` handle. Very
59/// long-lived applications should therefore limit the period over which they
60/// may retain handles of despawned entities.
61#[repr(C)]
62#[cfg_attr(not(target_arch = "wasm32"), derive(StableAbi))]
63pub struct World {
64    entities: Entities,
65    archetypes: ArchetypeSet,
66    /// Maps statically-typed bundle types to archetypes
67    bundle_to_archetype: StableTypeIdMap<u32>,
68    /// Maps source archetype and static bundle types to the archetype that an
69    /// entity is moved to after inserting the components from that bundle.
70    insert_edges: IndexStableTypeIdMap<InsertTarget>,
71    /// Maps source archetype and static bundle types to the archetype that an
72    /// entity is moved to after removing the components from that bundle.
73    remove_edges: IndexStableTypeIdMap<u32>,
74    id: u64,
75    removed_components: RHashMap<StableTypeId, RVec<Entity>>,
76}
77
78#[allow(clippy::missing_errors_doc)]
79impl World {
80    /// Create an empty world
81    pub fn new() -> Self {
82        // AtomicU64 is unsupported on 32-bit MIPS and PPC architectures
83        // For compatibility, use Mutex<u64>
84        static ID: Mutex<u64> = Mutex::new(1);
85        let id = {
86            let mut id = ID.lock();
87            let next = id.checked_add(1).unwrap();
88            *id = next;
89            next
90        };
91        Self {
92            entities: Entities::default(),
93            archetypes: ArchetypeSet::new(),
94            bundle_to_archetype: RHashMap::default(),
95            insert_edges: RHashMap::default(),
96            remove_edges: RHashMap::default(),
97            id,
98            removed_components: RHashMap::default(),
99        }
100    }
101
102    /// Create an entity with certain components
103    ///
104    /// Returns the ID of the newly created entity.
105    ///
106    /// Arguments can be tuples, structs annotated with
107    /// [`#[derive(Bundle)]`](macro@Bundle), or the result of calling
108    /// [`build`](crate::EntityBuilder::build) on an
109    /// [`EntityBuilder`](crate::EntityBuilder), which is useful if the set of
110    /// components isn't statically known. To spawn an entity with only one
111    /// component, use a one-element tuple like `(x,)`.
112    ///
113    /// Any type that satisfies `Send + Sync + 'static` can be used as a
114    /// component.
115    ///
116    /// # Example
117    /// ```
118    /// # use gloss_hecs::*;
119    /// let mut world = World::new();
120    /// let a = world.spawn((123, "abc"));
121    /// let b = world.spawn((456, true));
122    /// ```
123    pub fn spawn(&mut self, components: impl DynamicBundle) -> Entity {
124        // Ensure all entity allocations are accounted for so `self.entities` can
125        // realloc if necessary
126        self.flush();
127
128        let entity = self.entities.alloc();
129
130        self.spawn_inner(entity, components);
131
132        entity
133    }
134
135    /// Create an entity with certain components and a specific [`Entity`]
136    /// handle.
137    ///
138    /// See [`spawn`](Self::spawn).
139    ///
140    /// Despawns any existing entity with the same [`Entity::id`].
141    ///
142    /// Useful for easy handle-preserving deserialization. Be cautious
143    /// resurrecting old `Entity` handles in already-populated worlds as it
144    /// vastly increases the likelihood of collisions.
145    ///
146    /// # Example
147    /// ```
148    /// # use gloss_hecs::*;
149    /// let mut world = World::new();
150    /// let a = world.spawn((123, "abc"));
151    /// let b = world.spawn((456, true));
152    /// world.despawn(a);
153    /// assert!(!world.contains(a));
154    /// // all previous Entity values pointing to 'a' will be live again, instead pointing to the new entity.
155    /// world.spawn_at(a, (789, "ABC"));
156    /// assert!(world.contains(a));
157    /// ```
158    pub fn spawn_at(&mut self, handle: Entity, components: impl DynamicBundle) {
159        // Ensure all entity allocations are accounted for so `self.entities` can
160        // realloc if necessary
161        self.flush();
162
163        let loc = self.entities.alloc_at(handle);
164        if let Some(loc) = loc {
165            if let Some(moved) = unsafe { self.archetypes.archetypes[loc.archetype as usize].remove(loc.index, true) } {
166                self.entities.meta[moved as usize].location.index = loc.index;
167            }
168        }
169
170        self.spawn_inner(handle, components);
171    }
172
173    fn spawn_inner(&mut self, entity: Entity, components: impl DynamicBundle) {
174        let archetype_id = match components.key() {
175            Some(k) => {
176                let archetypes = &mut self.archetypes;
177                *self
178                    .bundle_to_archetype
179                    .entry(k)
180                    .or_insert_with(|| components.with_ids(|ids| archetypes.get(ids, || RVec::from(components.type_info()))))
181            }
182            None => components.with_ids(|ids| self.archetypes.get(ids, || RVec::from(components.type_info()))),
183        };
184
185        let archetype = &mut self.archetypes.archetypes[archetype_id as usize];
186        unsafe {
187            let index = archetype.allocate(entity.id);
188            components.put(|ptr, ty| {
189                archetype.put_dynamic(ptr, ty.id(), ty.layout().size(), index, true, false);
190            });
191            self.entities.meta[entity.id as usize].location = Location {
192                archetype: archetype_id,
193                index,
194            };
195        }
196    }
197
198    /// Efficiently spawn a large number of entities with the same
199    /// statically-typed components
200    ///
201    /// Faster than calling [`spawn`](Self::spawn) repeatedly with the same
202    /// components, but requires that component types are known at compile
203    /// time.
204    ///
205    /// # Example
206    /// ```
207    /// # use gloss_hecs::*;
208    /// let mut world = World::new();
209    /// let entities = world
210    ///     .spawn_batch((0..1_000).map(|i| (i, "abc")))
211    ///     .collect::<Vec<_>>();
212    /// for i in 0..1_000 {
213    ///     assert_eq!(*world.get::<&i32>(entities[i]).unwrap(), i as i32);
214    /// }
215    /// ```
216    pub fn spawn_batch<I>(&mut self, iter: I) -> SpawnBatchIter<'_, I::IntoIter>
217    where
218        I: IntoIterator,
219        I::Item: Bundle + 'static,
220    {
221        // Ensure all entity allocations are accounted for so `self.entities` can
222        // realloc if necessary
223        self.flush();
224
225        let iter = iter.into_iter();
226        let (lower, upper) = iter.size_hint();
227        let archetype_id = self.reserve_inner::<I::Item>(u32::try_from(upper.unwrap_or(lower)).expect("iterator too large"));
228
229        SpawnBatchIter {
230            inner: iter,
231            entities: &mut self.entities,
232            archetype_id,
233            archetype: &mut self.archetypes.archetypes[archetype_id as usize],
234        }
235    }
236
237    /// Super-efficiently spawn the contents of a [`ColumnBatch`]
238    ///
239    /// The fastest, but most specialized, way to spawn large numbers of
240    /// entities. Useful for high performance deserialization. Supports
241    /// dynamic component types.
242    pub fn spawn_column_batch(&mut self, batch: ColumnBatch) -> SpawnColumnBatchIter<'_> {
243        self.flush();
244
245        let archetype = batch.0;
246        let entity_count = archetype.len();
247        // Store component data
248        let (archetype_id, base) = self.archetypes.insert_batch(archetype);
249
250        let archetype = &mut self.archetypes.archetypes[archetype_id as usize];
251        let id_alloc = self.entities.alloc_many(entity_count, archetype_id, base);
252
253        // Fix up entity IDs
254        let mut id_alloc_clone = id_alloc.clone();
255        let mut index = base as usize;
256        while let Some(id) = id_alloc_clone.next(&self.entities) {
257            archetype.set_entity_id(index, id);
258            index += 1;
259        }
260
261        // Return iterator over new IDs
262        SpawnColumnBatchIter {
263            pending_end: id_alloc.pending_end,
264            id_alloc,
265            entities: &mut self.entities,
266        }
267    }
268
269    /// Hybrid of [`spawn_column_batch`](Self::spawn_column_batch) and
270    /// [`spawn_at`](Self::spawn_at)
271    #[allow(clippy::cast_possible_truncation)]
272    pub fn spawn_column_batch_at(&mut self, handles: &[Entity], batch: ColumnBatch) {
273        let archetype = batch.0;
274        assert_eq!(
275            handles.len(),
276            archetype.len() as usize,
277            "number of entity IDs {} must match number of entities {}",
278            handles.len(),
279            archetype.len()
280        );
281
282        // Drop components of entities that will be replaced
283        for &handle in handles {
284            let loc = self.entities.alloc_at(handle);
285            if let Some(loc) = loc {
286                if let Some(moved) = unsafe { self.archetypes.archetypes[loc.archetype as usize].remove(loc.index, true) } {
287                    self.entities.meta[moved as usize].location.index = loc.index;
288                }
289            }
290        }
291
292        // Store components
293        let (archetype_id, base) = self.archetypes.insert_batch(archetype);
294
295        // Fix up entity IDs
296        let archetype = &mut self.archetypes.archetypes[archetype_id as usize];
297        for (&handle, index) in handles.iter().zip(base as usize..) {
298            archetype.set_entity_id(index, handle.id());
299            self.entities.meta[handle.id() as usize].location = Location {
300                archetype: archetype_id,
301                index: index as u32,
302            };
303        }
304    }
305
306    /// Allocate many entities ID concurrently
307    ///
308    /// Unlike [`spawn`](Self::spawn), this can be called concurrently with
309    /// other operations on the [`World`] such as queries, but does not
310    /// immediately create the entities. Reserved entities are not visible
311    /// to queries or world iteration, but can be otherwise operated on
312    /// freely. Operations that add or remove components or entities, such as
313    /// `insert` or `despawn`, will cause all outstanding reserved entities
314    /// to become real entities before proceeding. This can also be done
315    /// explicitly by calling [`flush`](Self::flush).
316    ///
317    /// Useful for reserving an ID that will later have components attached to
318    /// it with `insert`.
319    pub fn reserve_entities(&self, count: u32) -> ReserveEntitiesIterator<'_> {
320        self.entities.reserve_entities(count)
321    }
322
323    /// Allocate an entity ID concurrently
324    ///
325    /// See [`reserve_entities`](Self::reserve_entities).
326    pub fn reserve_entity(&self) -> Entity {
327        self.entities.reserve_entity()
328    }
329
330    /// Destroy an entity and all its components
331    ///
332    /// See also [`take`](Self::take).
333    #[allow(clippy::unwrap_or_default)]
334    pub fn despawn(&mut self, entity: Entity) -> Result<(), NoSuchEntity> {
335        self.flush();
336        let loc = self.entities.free(entity)?;
337        let archetype = &mut self.archetypes.archetypes[loc.archetype as usize];
338        if let Some(moved) = unsafe { archetype.remove(loc.index, true) } {
339            self.entities.meta[moved as usize].location.index = loc.index;
340        }
341        for ty in archetype.types() {
342            let removed_entities = self.removed_components.entry(ty.id()).or_insert_with(RVec::new);
343            removed_entities.push(entity);
344        }
345        Ok(())
346    }
347
348    /// Ensure at least `additional` entities with exact components `T` can be
349    /// spawned without reallocating
350    pub fn reserve<T: Bundle + 'static>(&mut self, additional: u32) {
351        self.reserve_inner::<T>(additional);
352    }
353
354    fn reserve_inner<T: Bundle + 'static>(&mut self, additional: u32) -> u32 {
355        self.flush();
356        self.entities.reserve(additional);
357
358        let archetypes = &mut self.archetypes;
359        let archetype_id = *self
360            .bundle_to_archetype
361            .entry(StableTypeId::of::<T>())
362            .or_insert_with(|| T::with_static_ids(|ids| archetypes.get(ids, || T::with_static_type_info(|info| RVec::from(info.to_vec())))));
363
364        self.archetypes.archetypes[archetype_id as usize].reserve(additional);
365        archetype_id
366    }
367
368    /// Despawn all entities
369    ///
370    /// Preserves allocated storage for reuse but clears metadata so that
371    /// [`Entity`] values will repeat (in contrast to
372    /// [`despawn`][Self::despawn]).
373    #[allow(clippy::unwrap_or_default)]
374    pub fn clear(&mut self) {
375        for archetype in &self.archetypes.archetypes {
376            for ty in archetype.types() {
377                let archetype_entities: Vec<Entity> = archetype.ids().iter().map(|id| unsafe { self.find_entity_from_id(*id) }).collect();
378                let removed_entities = self.removed_components.entry(ty.id()).or_insert_with(RVec::new);
379                removed_entities.extend(archetype_entities);
380            }
381        }
382        for archetype in &mut self.archetypes.archetypes {
383            archetype.clear();
384        }
385        self.entities.clear();
386    }
387
388    /// Whether `entity` still exists
389    pub fn contains(&self, entity: Entity) -> bool {
390        self.entities.contains(entity)
391    }
392
393    /// Efficiently iterate over all entities that have certain components,
394    /// using dynamic borrow checking
395    ///
396    /// Prefer [`query_mut`](Self::query_mut) when concurrent access to the
397    /// [`World`] is not required.
398    ///
399    /// Calling `iter` on the returned value yields `(Entity, Q)` tuples, where
400    /// `Q` is some query type. A query type is any type for which an
401    /// implementation of [`Query`] exists, e.g. `&T`, `&mut T`, a tuple of
402    /// query types, or an `Option` wrapping a query type, where `T` is any
403    /// component type. Components queried with `&mut` must only appear once.
404    /// Entities which do not have a component type referenced outside of an
405    /// `Option` will be skipped.
406    ///
407    /// Entities are yielded in arbitrary order.
408    ///
409    /// The returned [`QueryBorrow`] can be further transformed with combinator
410    /// methods; see its documentation for details.
411    ///
412    /// Iterating a query will panic if it would violate an existing unique
413    /// reference or construct an invalid unique reference. This occurs when
414    /// two simultaneously-active queries could expose the same entity.
415    /// Simultaneous queries can access the same component type if and only if
416    /// the world contains no entities that have all components required by
417    /// both queries, assuming no other component borrows are outstanding.
418    ///
419    /// Iterating a query yields references with lifetimes bound to the
420    /// [`QueryBorrow`] returned here. To ensure those are invalidated, the
421    /// return value of this method must be dropped for its dynamic borrows
422    /// from the world to be released. Similarly, lifetime rules ensure that
423    /// references obtained from a query cannot outlive the [`QueryBorrow`].
424    ///
425    /// # Example
426    /// ```
427    /// # use gloss_hecs::*;
428    /// let mut world = World::new();
429    /// let a = world.spawn((123, true, "abc"));
430    /// let b = world.spawn((456, false));
431    /// let c = world.spawn((42, "def"));
432    /// let entities = world
433    ///     .query::<(&i32, &bool)>()
434    ///     .iter()
435    ///     .map(|(e, (&i, &b))| (e, i, b)) // Copy out of the world
436    ///     .collect::<Vec<_>>();
437    /// assert_eq!(entities.len(), 2);
438    /// assert!(entities.contains(&(a, 123, true)));
439    /// assert!(entities.contains(&(b, 456, false)));
440    /// ```
441    pub fn query<Q: Query>(&self) -> QueryBorrow<'_, Q> {
442        QueryBorrow::new(&self.entities.meta, &self.archetypes.archetypes)
443    }
444
445    /// Query a uniquely borrowed world
446    ///
447    /// Like [`query`](Self::query), but faster because dynamic borrow checks
448    /// can be skipped. Note that, unlike [`query`](Self::query), this
449    /// returns an `IntoIterator` which can be passed directly to a `for`
450    /// loop.
451    pub fn query_mut<Q: Query>(&mut self) -> QueryMut<'_, Q> {
452        QueryMut::new(&self.entities.meta, &mut self.archetypes.archetypes)
453    }
454
455    pub(crate) fn memo(&self) -> (u64, u32) {
456        (self.id, self.archetypes.generation())
457    }
458
459    pub(crate) fn entities_meta(&self) -> &[EntityMeta] {
460        &self.entities.meta
461    }
462
463    pub(crate) fn archetypes_inner(&self) -> &[Archetype] {
464        &self.archetypes.archetypes
465    }
466
467    /// Prepare a query against a single entity, using dynamic borrow checking
468    ///
469    /// Prefer [`query_one_mut`](Self::query_one_mut) when concurrent access to
470    /// the [`World`] is not required.
471    ///
472    /// Call [`get`](QueryOne::get) on the resulting [`QueryOne`] to actually
473    /// execute the query. The [`QueryOne`] value is responsible for
474    /// releasing the dynamically-checked borrow made by `get`, so it can't
475    /// be dropped while references returned by `get` are live.
476    ///
477    /// Handy for accessing multiple components simultaneously.
478    ///
479    /// # Example
480    /// ```
481    /// # use gloss_hecs::*;
482    /// let mut world = World::new();
483    /// let a = world.spawn((123, true, "abc"));
484    /// // The returned query must outlive the borrow made by `get`
485    /// let mut query = world.query_one::<(&mut i32, &bool)>(a).unwrap();
486    /// let (mut number, flag) = query.get().unwrap();
487    /// if *flag {
488    ///     *number *= 2;
489    /// }
490    /// assert_eq!(*number, 246);
491    /// ```
492    pub fn query_one<Q: Query>(&self, entity: Entity) -> Result<QueryOne<'_, Q>, NoSuchEntity> {
493        let loc = self.entities.get(entity)?;
494        Ok(unsafe { QueryOne::new(&self.archetypes.archetypes[loc.archetype as usize], loc.index) })
495    }
496
497    /// Query a single entity in a uniquely borrow world
498    ///
499    /// Like [`query_one`](Self::query_one), but faster because dynamic borrow
500    /// checks can be skipped. Note that, unlike
501    /// [`query_one`](Self::query_one), on success this returns the
502    /// query's results directly.
503    pub fn query_one_mut<Q: Query>(&mut self, entity: Entity) -> Result<QueryItem<'_, Q>, QueryOneError> {
504        assert_borrow::<Q>();
505
506        let loc = self.entities.get(entity)?;
507        let archetype = &self.archetypes.archetypes[loc.archetype as usize];
508        let state = Q::Fetch::prepare(archetype).ok_or(QueryOneError::Unsatisfied)?;
509        let fetch = Q::Fetch::execute(archetype, state);
510        unsafe { Ok(fetch.get(loc.index as usize)) }
511    }
512
513    /// Short-hand for [`entity`](Self::entity) followed by [`EntityRef::get`]
514    pub fn get<'a, T: ComponentRef<'a>>(&'a self, entity: Entity) -> Result<T::Ref, ComponentError> {
515        Ok(self.entity(entity)?.get::<T>().ok_or_else(MissingComponent::new::<T::Component>)?)
516    }
517
518    /// Short-hand for [`entity`](Self::entity) followed by
519    /// [`EntityRef::satisfies`]
520    pub fn satisfies<Q: Query>(&self, entity: Entity) -> Result<bool, NoSuchEntity> {
521        Ok(self.entity(entity)?.satisfies::<Q>())
522    }
523
524    /// Short-hand for [`entity`](Self::entity) followed by [`EntityRef::has`]
525    pub fn has<T: Component>(&self, entity: Entity) -> Result<bool, NoSuchEntity> {
526        Ok(self.entity(entity)?.has::<T>())
527    }
528
529    /// Access an entity regardless of its component types
530    ///
531    /// Does not immediately borrow any component.
532    pub fn entity(&self, entity: Entity) -> Result<EntityRef<'_>, NoSuchEntity> {
533        let loc = self.entities.get(entity)?;
534        unsafe { Ok(EntityRef::new(&self.archetypes.archetypes[loc.archetype as usize], entity, loc.index)) }
535    }
536
537    /// Given an id obtained from [`Entity::id`], reconstruct the still-live
538    /// [`Entity`].
539    ///
540    /// # Safety
541    ///
542    /// `id` must correspond to a currently live [`Entity`]. A despawned or
543    /// never-allocated `id` will produce undefined behavior.
544    pub unsafe fn find_entity_from_id(&self, id: u32) -> Entity {
545        self.entities.resolve_unknown_gen(id)
546    }
547
548    /// Iterate over all entities in the world
549    ///
550    /// Entities are yielded in arbitrary order. Prefer [`query`](Self::query)
551    /// for better performance when components will be accessed in
552    /// predictable patterns.
553    ///
554    /// # Example
555    /// ```
556    /// # use gloss_hecs::*;
557    /// let mut world = World::new();
558    /// let a = world.spawn(());
559    /// let b = world.spawn(());
560    /// let ids = world
561    ///     .iter()
562    ///     .map(|entity_ref| entity_ref.entity())
563    ///     .collect::<Vec<_>>();
564    /// assert_eq!(ids.len(), 2);
565    /// assert!(ids.contains(&a));
566    /// assert!(ids.contains(&b));
567    /// ```
568    pub fn iter(&self) -> Iter<'_> {
569        Iter::new(&self.archetypes.archetypes, &self.entities)
570    }
571
572    #[allow(missing_docs)]
573    pub fn removed<C: Component>(&self) -> &[Entity] {
574        self.removed_components
575            .get(&StableTypeId::of::<C>())
576            .map_or(&[], |entities| entities.as_slice())
577    }
578
579    /// Add `components` to `entity`
580    ///
581    /// Computational cost is proportional to the number of components `entity`
582    /// has. If an entity already has a component of a certain type, it is
583    /// dropped and replaced.
584    ///
585    /// When inserting a single component, see [`insert_one`](Self::insert_one)
586    /// for convenience.
587    ///
588    /// # Example
589    /// ```
590    /// # use gloss_hecs::*;
591    /// let mut world = World::new();
592    /// let e = world.spawn((123, "abc"));
593    /// world.insert(e, (456, true));
594    /// assert_eq!(*world.get::<&i32>(e).unwrap(), 456);
595    /// assert_eq!(*world.get::<&bool>(e).unwrap(), true);
596    /// ```
597    pub fn insert(&mut self, entity: Entity, components: impl DynamicBundle) -> Result<(), NoSuchEntity> {
598        self.flush();
599
600        let loc = self.entities.get(entity)?;
601        self.insert_inner(entity, components, loc.archetype, loc);
602        Ok(())
603    }
604
605    /// The implementation backing [`insert`](Self::insert) exposed so that it
606    /// can also be used by [`exchange`](Self::exchange).
607    ///
608    /// Note that `graph_origin` is always equal to `loc.archetype` during
609    /// insertion. Only for exchange, `graph_origin` identifies
610    /// the intermediate archetype which would be reached after removal and
611    /// before insertion even though the actual component data still resides
612    /// in `loc.archetype`.
613    fn insert_inner(&mut self, entity: Entity, components: impl DynamicBundle, graph_origin: u32, loc: Location) {
614        let target_storage;
615        let target = match components.key() {
616            None => {
617                target_storage = self.archetypes.get_insert_target(graph_origin, &components);
618                &target_storage
619            }
620            Some(key) => match self.insert_edges.entry(Tuple2(graph_origin, key)) {
621                REntry::Occupied(entry) => entry.into_mut(),
622                REntry::Vacant(entry) => {
623                    let target = self.archetypes.get_insert_target(graph_origin, &components);
624                    entry.insert(target)
625                }
626            },
627        };
628
629        let source_arch = &mut self.archetypes.archetypes[loc.archetype as usize];
630        unsafe {
631            // Drop the components we're overwriting
632            for &ty in &target.replaced {
633                let ptr = source_arch.get_dynamic(ty.id(), ty.layout().size(), loc.index).unwrap();
634                ty.drop(ptr.as_ptr());
635            }
636
637            if target.index == loc.archetype {
638                // Update components in the current archetype
639                let arch = &mut self.archetypes.archetypes[loc.archetype as usize];
640                components.put(|ptr, ty| {
641                    arch.put_dynamic(ptr, ty.id(), ty.layout().size(), loc.index, false, true);
642                });
643                return;
644            }
645
646            let (source_arch, target_arch) = index2(&mut self.archetypes.archetypes, loc.archetype as usize, target.index as usize);
647
648            // Allocate storage in the archetype and update the entity's location to address
649            // it
650            let target_index = target_arch.allocate(entity.id);
651            let meta = &mut self.entities.meta[entity.id as usize];
652            meta.location.archetype = target.index;
653            meta.location.index = target_index;
654
655            // Move the new components
656            components.put(|ptr, ty| {
657                let had_component = source_arch.has_dynamic(ty.id());
658                target_arch.put_dynamic(ptr, ty.id(), ty.layout().size(), target_index, !had_component, had_component);
659            });
660
661            // Move the components we're keeping
662            for &ty in &target.retained {
663                let src = source_arch.get_dynamic(ty.id(), ty.layout().size(), loc.index).unwrap();
664                //copy to the new archetype also the added and mutated flags
665                let state = source_arch.get_state_by_id(&ty.id()).unwrap();
666                let added = *source_arch.get_added(state).as_ptr();
667                let mutated = *source_arch.get_mutated(state).as_ptr();
668                target_arch.put_dynamic(src.as_ptr(), ty.id(), ty.layout().size(), target_index, added, mutated);
669            }
670
671            // Free storage in the old archetype
672            if let Some(moved) = source_arch.remove(loc.index, false) {
673                self.entities.meta[moved as usize].location.index = loc.index;
674            }
675        }
676    }
677
678    /// Add `component` to `entity`
679    ///
680    /// See [`insert`](Self::insert).
681    pub fn insert_one(&mut self, entity: Entity, component: impl Component) -> Result<(), NoSuchEntity> {
682        self.insert(entity, (component,))
683    }
684
685    /// Remove components from `entity`
686    ///
687    /// Computational cost is proportional to the number of components `entity`
688    /// has. The entity itself is not removed, even if no components remain;
689    /// use `despawn` for that. If any component in `T` is not present in
690    /// `entity`, no components are removed and an error is returned.
691    ///
692    /// When removing a single component, see [`remove_one`](Self::remove_one)
693    /// for convenience.
694    ///
695    /// # Example
696    /// ```
697    /// # use gloss_hecs::*;
698    /// let mut world = World::new();
699    /// let e = world.spawn((123, "abc", true));
700    /// assert_eq!(world.remove::<(i32, &str)>(e), Ok((123, "abc")));
701    /// assert!(world.get::<&i32>(e).is_err());
702    /// assert!(world.get::<&&str>(e).is_err());
703    /// assert_eq!(*world.get::<&bool>(e).unwrap(), true);
704    /// ```
705    #[allow(clippy::unwrap_or_default)]
706    pub fn remove<T: Bundle + 'static>(&mut self, entity: Entity) -> Result<T, ComponentError> {
707        self.flush();
708
709        // Gather current metadata
710        let loc = self.entities.get_mut(entity)?;
711        let old_index = loc.index;
712        let source_arch = &self.archetypes.archetypes[loc.archetype as usize];
713
714        // Move out of the source archetype, or bail out if a component is missing
715        let bundle = unsafe { T::get(|ty| source_arch.get_dynamic(ty.id(), ty.layout().size(), old_index))? };
716
717        // Find the target archetype ID
718        let target = Self::remove_target::<T>(&mut self.archetypes, &mut self.remove_edges, loc.archetype);
719
720        // Store components to the target archetype and update metadata
721        if loc.archetype != target {
722            // If we actually removed any components, the entity needs to be moved into a
723            // new archetype
724            let (source_arch, target_arch) = index2(&mut self.archetypes.archetypes, loc.archetype as usize, target as usize);
725            let target_index = unsafe { target_arch.allocate(entity.id) };
726            loc.archetype = target;
727            loc.index = target_index;
728            let removed_components = &mut self.removed_components;
729            if let Some(moved) = unsafe {
730                source_arch.move_to(old_index, |src, ty, size, is_added, is_mutated| {
731                    // Only move the components present in the target archetype, i.e. the
732                    // non-removed ones.
733                    if let Some(dst) = target_arch.get_dynamic(ty, size, target_index) {
734                        ptr::copy_nonoverlapping(src, dst.as_ptr(), size);
735                        let state = target_arch.get_state_by_id(&ty).unwrap();
736                        *target_arch.get_added(state).as_ptr().add(target_index as usize) = is_added;
737                        *target_arch.get_mutated(state).as_ptr().add(target_index as usize) = is_mutated;
738                    } else {
739                        let removed_entities = removed_components.entry(ty).or_insert_with(RVec::new);
740                        removed_entities.push(entity);
741                    }
742                })
743            } {
744                self.entities.meta[moved as usize].location.index = old_index;
745            }
746        }
747
748        Ok(bundle)
749    }
750
751    fn remove_target<T: Bundle + 'static>(archetypes: &mut ArchetypeSet, remove_edges: &mut IndexStableTypeIdMap<u32>, old_archetype: u32) -> u32 {
752        match remove_edges.entry(Tuple2(old_archetype, StableTypeId::of::<T>())) {
753            REntry::Occupied(entry) => *entry.into_mut(),
754            REntry::Vacant(entry) => {
755                let info = T::with_static_type_info(|removed| {
756                    archetypes.archetypes[old_archetype as usize]
757                        .types()
758                        .iter()
759                        .filter(|x| removed.binary_search(x).is_err())
760                        .copied()
761                        .collect::<Vec<_>>()
762                });
763                let elements = info.iter().map(super::archetype::TypeInfo::id).collect::<Box<_>>();
764                let r_info = RVec::from(info);
765                let index = archetypes.get(&*elements, move || r_info);
766                *entry.insert(index)
767            }
768        }
769    }
770
771    /// Remove the `T` component from `entity`
772    ///
773    /// See [`remove`](Self::remove).
774    pub fn remove_one<T: Component>(&mut self, entity: Entity) -> Result<T, ComponentError> {
775        self.remove::<(T,)>(entity).map(|(x,)| x)
776    }
777
778    /// Remove `S` components from `entity` and then add `components`
779    ///
780    /// This has the same effect as calling [`remove::<S>`](Self::remove) and
781    /// then [`insert::<T>`](Self::insert), but is more efficient as the
782    /// intermediate archetype after removal but before insertion is skipped.
783    pub fn exchange<S: Bundle + 'static, T: DynamicBundle>(&mut self, entity: Entity, components: T) -> Result<S, ComponentError> {
784        self.flush();
785
786        // Gather current metadata
787        let loc = self.entities.get(entity)?;
788
789        // Move out of the source archetype, or bail out if a component is missing
790        let source_arch = &self.archetypes.archetypes[loc.archetype as usize];
791
792        let bundle = unsafe { S::get(|ty| source_arch.get_dynamic(ty.id(), ty.layout().size(), loc.index))? };
793
794        // Find the intermediate archetype ID
795        let intermediate = Self::remove_target::<S>(&mut self.archetypes, &mut self.remove_edges, loc.archetype);
796
797        self.insert_inner(entity, components, intermediate, loc);
798
799        Ok(bundle)
800    }
801
802    /// Remove the `S` component from `entity` and then add `component`
803    ///
804    /// See [`exchange`](Self::exchange).
805    pub fn exchange_one<S: Component, T: Component>(&mut self, entity: Entity, component: T) -> Result<S, ComponentError> {
806        self.exchange::<(S,), (T,)>(entity, (component,)).map(|(x,)| x)
807    }
808
809    /// Borrow a single component of `entity` without safety checks
810    ///
811    /// `T` must be a shared or unique reference to a component type.
812    ///
813    /// Should only be used as a building block for safe abstractions.
814    ///
815    /// # Safety
816    ///
817    /// `entity` must have been previously obtained from this [`World`], and no
818    /// unique borrow of the same component of `entity` may be live
819    /// simultaneous to the returned reference.
820    pub unsafe fn get_unchecked<'a, T: ComponentRef<'a>>(&'a self, entity: Entity) -> Result<T, ComponentError> {
821        let loc = self.entities.get(entity)?;
822        let archetype = &self.archetypes.archetypes[loc.archetype as usize];
823        let state = archetype.get_state::<T::Component>().ok_or_else(MissingComponent::new::<T::Component>)?;
824        Ok(T::from_raw(archetype.get_base::<T::Component>(state).as_ptr().add(loc.index as usize)))
825    }
826
827    /// Convert all reserved entities into empty entities that can be iterated
828    /// and accessed
829    ///
830    /// Invoked implicitly by operations that add or remove components or
831    /// entities, i.e. all variations of `spawn`, `despawn`, `insert`, and
832    /// `remove`.
833    pub fn flush(&mut self) {
834        let arch = &mut self.archetypes.archetypes[0];
835        self.entities.flush(|id, location| location.index = unsafe { arch.allocate(id) });
836    }
837
838    /// Inspect the archetypes that entities are organized into
839    ///
840    /// Useful for dynamically scheduling concurrent queries by checking borrows
841    /// in advance, and for efficient serialization.
842    pub fn archetypes(&self) -> impl ExactSizeIterator<Item = &'_ Archetype> + '_ {
843        self.archetypes_inner().iter()
844    }
845
846    /// Despawn `entity`, yielding a [`DynamicBundle`] of its components
847    ///
848    /// Useful for moving entities between worlds.
849    pub fn take(&mut self, entity: Entity) -> Result<TakenEntity<'_>, NoSuchEntity> {
850        self.flush();
851        let loc = self.entities.get(entity)?;
852        let archetype = &mut self.archetypes.archetypes[loc.archetype as usize];
853        unsafe { Ok(TakenEntity::new(&mut self.entities, entity, archetype, loc.index)) }
854    }
855
856    /// Returns a distinct value after `archetypes` is changed
857    ///
858    /// Store the current value after deriving information from
859    /// [`archetypes`](Self::archetypes), then check whether the value
860    /// returned by this function differs before attempting an
861    /// operation that relies on its correctness. Useful for determining whether
862    /// e.g. a concurrent query execution plan is still correct.
863    ///
864    /// The generation may be, but is not necessarily, changed as a result of
865    /// adding or removing any entity or component.
866    ///
867    /// # Example
868    /// ```
869    /// # use gloss_hecs::*;
870    /// let mut world = World::new();
871    /// let initial_gen = world.archetypes_generation();
872    /// world.spawn((123, "abc"));
873    /// assert_ne!(initial_gen, world.archetypes_generation());
874    /// ```
875    pub fn archetypes_generation(&self) -> ArchetypesGeneration {
876        ArchetypesGeneration(self.archetypes.generation())
877    }
878
879    /// Clears each entity's tracker state. For example, each entity's component
880    /// "mutated" state will be reset to `false`.
881    pub fn clear_trackers(&mut self) {
882        for archetype in &mut self.archetypes.archetypes {
883            archetype.clear_trackers();
884        }
885
886        self.removed_components.clear();
887    }
888
889    /// Each entity's component "added" state will be reset to `true`.
890    pub fn set_trackers_added(&mut self) {
891        for archetype in &mut self.archetypes.archetypes {
892            archetype.set_trackers_added();
893        }
894
895        self.removed_components.clear();
896    }
897
898    /// Each entity's component "mutated" state will be reset to `true`.
899    pub fn set_trackers_changed(&mut self) {
900        for archetype in &mut self.archetypes.archetypes {
901            archetype.set_trackers_changed();
902        }
903
904        self.removed_components.clear();
905    }
906
907    /// Number of currently live entities
908    #[inline]
909    pub fn len(&self) -> u32 {
910        self.entities.len()
911    }
912
913    /// Whether no entities are live
914    #[inline]
915    pub fn is_empty(&self) -> bool {
916        self.len() == 0
917    }
918}
919
920unsafe impl Send for World {}
921unsafe impl Sync for World {}
922
923impl Default for World {
924    fn default() -> Self {
925        Self::new()
926    }
927}
928
929impl<'a> IntoIterator for &'a World {
930    type IntoIter = Iter<'a>;
931    type Item = EntityRef<'a>;
932    fn into_iter(self) -> Iter<'a> {
933        self.iter()
934    }
935}
936
937fn index2<T>(x: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
938    assert!(i != j);
939    assert!(i < x.len());
940    assert!(j < x.len());
941    let ptr = x.as_mut_ptr();
942    unsafe { (&mut *ptr.add(i), &mut *ptr.add(j)) }
943}
944
945/// Errors that arise when accessing components
946#[derive(Debug, Clone, Eq, PartialEq, Hash)]
947pub enum ComponentError {
948    /// The entity was already despawned
949    NoSuchEntity,
950    /// The entity did not have a requested component
951    MissingComponent(MissingComponent),
952}
953
954#[cfg(feature = "std")]
955impl Error for ComponentError {}
956
957impl fmt::Display for ComponentError {
958    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
959        use ComponentError::{MissingComponent, NoSuchEntity};
960        match *self {
961            NoSuchEntity => f.write_str("no such entity"),
962            MissingComponent(ref x) => x.fmt(f),
963        }
964    }
965}
966
967impl From<NoSuchEntity> for ComponentError {
968    fn from(NoSuchEntity: NoSuchEntity) -> Self {
969        ComponentError::NoSuchEntity
970    }
971}
972
973impl From<MissingComponent> for ComponentError {
974    fn from(x: MissingComponent) -> Self {
975        ComponentError::MissingComponent(x)
976    }
977}
978
979/// Errors that arise when querying a single entity
980#[derive(Debug, Clone, Eq, PartialEq, Hash)]
981pub enum QueryOneError {
982    /// The entity was already despawned
983    NoSuchEntity,
984    /// The entity exists but does not satisfy the query
985    Unsatisfied,
986}
987
988#[cfg(feature = "std")]
989impl Error for QueryOneError {}
990
991impl fmt::Display for QueryOneError {
992    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
993        use QueryOneError::{NoSuchEntity, Unsatisfied};
994        match *self {
995            NoSuchEntity => f.write_str("no such entity"),
996            Unsatisfied => f.write_str("unsatisfied"),
997        }
998    }
999}
1000
1001impl From<NoSuchEntity> for QueryOneError {
1002    fn from(NoSuchEntity: NoSuchEntity) -> Self {
1003        QueryOneError::NoSuchEntity
1004    }
1005}
1006
1007/// Types that can be components, implemented automatically for all `Send` +
1008/// `Sync`
1009/// + `'static` types
1010///
1011/// This is just a convenient shorthand for `Send + Sync + 'static`, and never
1012/// needs to be implemented manually.
1013pub trait Component: Send + Sync + 'static {}
1014impl<T: Send + Sync + 'static> Component for T {}
1015
1016/// Iterator over all of a world's entities
1017pub struct Iter<'a> {
1018    archetypes: core::slice::Iter<'a, Archetype>,
1019    entities: &'a Entities,
1020    current: Option<&'a Archetype>,
1021    index: u32,
1022}
1023
1024impl<'a> Iter<'a> {
1025    fn new(archetypes: &'a [Archetype], entities: &'a Entities) -> Self {
1026        Self {
1027            archetypes: archetypes.iter(),
1028            entities,
1029            current: None,
1030            index: 0,
1031        }
1032    }
1033}
1034
1035unsafe impl Send for Iter<'_> {}
1036unsafe impl Sync for Iter<'_> {}
1037
1038impl<'a> Iterator for Iter<'a> {
1039    type Item = EntityRef<'a>;
1040    fn next(&mut self) -> Option<Self::Item> {
1041        loop {
1042            match self.current {
1043                None => {
1044                    self.current = Some(self.archetypes.next()?);
1045                    self.index = 0;
1046                }
1047                Some(current) => {
1048                    if self.index == current.len() {
1049                        self.current = None;
1050                        continue;
1051                    }
1052                    let index = self.index;
1053                    self.index += 1;
1054                    let id = current.entity_id(index);
1055                    return Some(unsafe {
1056                        EntityRef::new(
1057                            current,
1058                            Entity {
1059                                id,
1060                                generation: self.entities.meta[id as usize].generation,
1061                            },
1062                            index,
1063                        )
1064                    });
1065                }
1066            }
1067        }
1068    }
1069
1070    fn size_hint(&self) -> (usize, Option<usize>) {
1071        (self.len(), Some(self.len()))
1072    }
1073}
1074
1075impl ExactSizeIterator for Iter<'_> {
1076    #[inline]
1077    fn len(&self) -> usize {
1078        self.entities.len() as usize
1079    }
1080}
1081
1082impl<A: DynamicBundle> Extend<A> for World {
1083    fn extend<T>(&mut self, iter: T)
1084    where
1085        T: IntoIterator<Item = A>,
1086    {
1087        for x in iter {
1088            self.spawn(x);
1089        }
1090    }
1091}
1092
1093impl<A: DynamicBundle> core::iter::FromIterator<A> for World {
1094    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
1095        let mut world = World::new();
1096        world.extend(iter);
1097        world
1098    }
1099}
1100
1101/// Determines freshness of information derived from [`World::archetypes`]
1102#[derive(Debug, Copy, Clone, Eq, PartialEq)]
1103pub struct ArchetypesGeneration(u32);
1104
1105/// Entity IDs created by [`World::spawn_batch`]
1106pub struct SpawnBatchIter<'a, I>
1107where
1108    I: Iterator,
1109    I::Item: Bundle,
1110{
1111    inner: I,
1112    entities: &'a mut Entities,
1113    archetype_id: u32,
1114    archetype: &'a mut Archetype,
1115}
1116
1117impl<I> Drop for SpawnBatchIter<'_, I>
1118where
1119    I: Iterator,
1120    I::Item: Bundle,
1121{
1122    fn drop(&mut self) {
1123        for _ in self {}
1124    }
1125}
1126
1127impl<I> Iterator for SpawnBatchIter<'_, I>
1128where
1129    I: Iterator,
1130    I::Item: Bundle,
1131{
1132    type Item = Entity;
1133
1134    fn next(&mut self) -> Option<Entity> {
1135        let components = self.inner.next()?;
1136        let entity = self.entities.alloc();
1137        let index = unsafe { self.archetype.allocate(entity.id) };
1138        unsafe {
1139            components.put(|ptr, ty| {
1140                self.archetype.put_dynamic(ptr, ty.id(), ty.layout().size(), index, true, false);
1141            });
1142        }
1143        self.entities.meta[entity.id as usize].location = Location {
1144            archetype: self.archetype_id,
1145            index,
1146        };
1147        Some(entity)
1148    }
1149
1150    fn size_hint(&self) -> (usize, Option<usize>) {
1151        self.inner.size_hint()
1152    }
1153}
1154
1155impl<I, T> ExactSizeIterator for SpawnBatchIter<'_, I>
1156where
1157    I: ExactSizeIterator<Item = T>,
1158    T: Bundle,
1159{
1160    fn len(&self) -> usize {
1161        self.inner.len()
1162    }
1163}
1164
1165/// Iterator over [`Entity`]s spawned by [`World::spawn_column_batch()`]
1166pub struct SpawnColumnBatchIter<'a> {
1167    pending_end: usize,
1168    id_alloc: crate::entities::AllocManyState,
1169    entities: &'a mut Entities,
1170}
1171
1172impl Iterator for SpawnColumnBatchIter<'_> {
1173    type Item = Entity;
1174
1175    fn next(&mut self) -> Option<Entity> {
1176        let id = self.id_alloc.next(self.entities)?;
1177        Some(unsafe { self.entities.resolve_unknown_gen(id) })
1178    }
1179
1180    fn size_hint(&self) -> (usize, Option<usize>) {
1181        (self.len(), Some(self.len()))
1182    }
1183}
1184
1185impl ExactSizeIterator for SpawnColumnBatchIter<'_> {
1186    fn len(&self) -> usize {
1187        self.id_alloc.len(self.entities)
1188    }
1189}
1190
1191impl Drop for SpawnColumnBatchIter<'_> {
1192    fn drop(&mut self) {
1193        // Consume used freelist entries
1194        self.entities.finish_alloc_many(self.pending_end);
1195    }
1196}
1197
1198#[repr(C)]
1199#[cfg_attr(not(target_arch = "wasm32"), derive(StableAbi))]
1200struct ArchetypeSet {
1201    /// Maps sorted component type sets to archetypes
1202    // index: RHashMap<RSlice<'a, StableTypeId>, u32>,
1203    index: RHashMap<RVec<StableTypeId>, u32>,
1204    // index: HashMap<Box<[StableTypeId]>, u32>,
1205    archetypes: RVec<Archetype>,
1206}
1207
1208#[allow(clippy::cast_possible_truncation)]
1209impl ArchetypeSet {
1210    fn new() -> Self {
1211        // `flush` assumes archetype 0 always exists, representing entities with no
1212        // components.
1213        let arch = Archetype::new(RVec::new());
1214        let mut archs = RVec::new();
1215        archs.push(arch);
1216        Self {
1217            // index: Some((Box::default(), 0)).into_iter().collect(),
1218            // index: Some((RSlice::default(), 0)).into_iter().collect(),
1219            index: Some((RVec::default(), 0)).into_iter().collect(),
1220            archetypes: archs,
1221        }
1222    }
1223
1224    /// Find the archetype ID that has exactly `components`
1225    // fn get<T: Borrow<[StableTypeId]> + for<'b> Into<RSlice<'b, StableTypeId>>>(
1226    fn get<T: Borrow<[StableTypeId]> + Into<Box<[StableTypeId]>>>(&mut self, components: T, info: impl FnOnce() -> RVec<TypeInfo>) -> u32 {
1227        // let borrow = components.borrow();
1228        // let comps_boxed: Box<[StableTypeId]> = components.into();
1229        // let r_comps = RSlice::from(&*comps_boxed);
1230        self.index
1231            // .get(&RSlice::from_slice(components.borrow()))
1232            .get(&RVec::from_slice(components.borrow()))
1233            .copied()
1234            // .unwrap_or_else(|| self.insert(RSlice::from(&*components.into()), info()))
1235            .unwrap_or_else(|| self.insert(components.into(), info()))
1236    }
1237
1238    // fn insert(&mut self, components: RSlice<'_, StableTypeId>, info:
1239    // RVec<TypeInfo>) -> u32 {
1240    #[allow(clippy::boxed_local)]
1241    #[allow(clippy::needless_pass_by_value)]
1242    fn insert(&mut self, components: Box<[StableTypeId]>, info: RVec<TypeInfo>) -> u32 {
1243        let x = self.archetypes.len() as u32;
1244        self.archetypes.push(Archetype::new(info));
1245        // let r_comps = RSlice::from(&*components);
1246        let r_comps = RVec::from(&*components);
1247        let old = self.index.insert(r_comps, x);
1248        debug_assert!(old.is_none(), "inserted duplicate archetype");
1249        x
1250    }
1251
1252    /// Returns archetype ID and starting location index
1253    fn insert_batch(&mut self, archetype: Archetype) -> (u32, u32) {
1254        let ids = archetype.types().iter().map(super::archetype::TypeInfo::id).collect::<Box<_>>();
1255
1256        // let r_ids: RSlice<StableTypeId> = RSlice::from(&*ids);
1257        let r_ids = RVec::from(&*ids);
1258
1259        match self.index.entry(r_ids) {
1260            REntry::Occupied(x) => {
1261                // Duplicate of existing archetype
1262                let existing = &mut self.archetypes[*x.get() as usize];
1263                let base = existing.len();
1264                unsafe {
1265                    existing.merge(archetype);
1266                }
1267                (*x.get(), base)
1268            }
1269            REntry::Vacant(x) => {
1270                // Brand new archetype
1271                let id = self.archetypes.len() as u32;
1272                self.archetypes.push(archetype);
1273                x.insert(id);
1274                (id, 0)
1275            }
1276        }
1277    }
1278
1279    fn generation(&self) -> u32 {
1280        self.archetypes.len() as u32
1281    }
1282
1283    fn get_insert_target(&mut self, src: u32, components: &impl DynamicBundle) -> InsertTarget {
1284        // Assemble Vec<TypeInfo> for the final entity
1285        let arch = &mut self.archetypes[src as usize];
1286        let mut info = arch.types().to_vec();
1287        let mut replaced = RVec::new(); // Elements in both archetype.types() and components.type_info()
1288        let mut retained = RVec::new(); // Elements in archetype.types() but not components.type_info()
1289
1290        // Because both `components.type_info()` and `arch.types()` are
1291        // ordered, we can identify elements in one but not the other efficiently with
1292        // parallel iteration.
1293        let mut src_ty = 0;
1294        for ty in components.type_info() {
1295            while src_ty < arch.types().len() && arch.types()[src_ty] <= ty {
1296                if arch.types()[src_ty] != ty {
1297                    retained.push(arch.types()[src_ty]);
1298                }
1299                src_ty += 1;
1300            }
1301            if arch.has_dynamic(ty.id()) {
1302                replaced.push(ty);
1303            } else {
1304                info.push(ty);
1305            }
1306        }
1307        info.sort_unstable();
1308        retained.extend_from_slice(&arch.types()[src_ty..]);
1309
1310        // Find the archetype it'll live in
1311        // let elements = info.iter().map(|x| x.id()).collect::<Box<_>>();
1312        let elements: Box<[StableTypeId]> = info.iter().map(super::archetype::TypeInfo::id).collect();
1313        // let r_elements: RSlice<StableTypeId> = RSlice::from(&*elements);
1314        let r_info = RVec::from(info);
1315        let index = self.get(elements, move || r_info);
1316        InsertTarget { replaced, retained, index }
1317    }
1318}
1319
1320/// Metadata cached for inserting components into entities from this archetype
1321#[repr(C)]
1322#[cfg_attr(not(target_arch = "wasm32"), derive(StableAbi))]
1323struct InsertTarget {
1324    /// Components from the current archetype that are replaced by the insert
1325    replaced: RVec<TypeInfo>,
1326    /// Components from the current archetype that are moved by the insert
1327    retained: RVec<TypeInfo>,
1328    /// ID of the target archetype
1329    index: u32,
1330}
1331
1332type IndexStableTypeIdMap<V> = RHashMap<Tuple2<u32, StableTypeId>, V, BuildHasherDefault<IndexStableTypeIdHasher>>;
1333
1334#[derive(Default)]
1335struct IndexStableTypeIdHasher(u64);
1336
1337impl Hasher for IndexStableTypeIdHasher {
1338    fn write_u32(&mut self, index: u32) {
1339        self.0 ^= u64::from(index);
1340    }
1341
1342    fn write_u64(&mut self, type_id: u64) {
1343        self.0 ^= type_id;
1344    }
1345
1346    fn write(&mut self, _bytes: &[u8]) {
1347        unreachable!()
1348    }
1349
1350    fn finish(&self) -> u64 {
1351        self.0
1352    }
1353}
1354
1355#[cfg(test)]
1356mod tests {
1357    use super::*;
1358
1359    #[test]
1360    fn reuse_empty() {
1361        let mut world = World::new();
1362        let a = world.spawn(());
1363        world.despawn(a).unwrap();
1364        let b = world.spawn(());
1365        assert_eq!(a.id, b.id);
1366        assert_ne!(a.generation, b.generation);
1367    }
1368
1369    #[test]
1370    fn clear_repeats_entity_id() {
1371        let mut world = World::new();
1372        let a = world.spawn(());
1373        world.clear();
1374        let b = world.spawn(());
1375        assert_eq!(a.id, b.id);
1376        assert_eq!(a.generation, b.generation);
1377    }
1378
1379    #[test]
1380    fn spawn_at() {
1381        let mut world = World::new();
1382        let a = world.spawn(());
1383        world.despawn(a).unwrap();
1384        let b = world.spawn(());
1385        assert!(world.contains(b));
1386        assert_eq!(a.id, b.id);
1387        assert_ne!(a.generation, b.generation);
1388        world.spawn_at(a, ());
1389        assert!(!world.contains(b));
1390        assert_eq!(b.id, a.id);
1391        assert_ne!(b.generation, a.generation);
1392    }
1393
1394    #[test]
1395    fn reuse_populated() {
1396        let mut world = World::new();
1397        let a = world.spawn((42,));
1398        assert_eq!(*world.get::<&i32>(a).unwrap(), 42);
1399        world.despawn(a).unwrap();
1400        let b = world.spawn((true,));
1401        assert_eq!(a.id, b.id);
1402        assert_ne!(a.generation, b.generation);
1403        assert!(world.get::<&i32>(b).is_err());
1404        assert!(*world.get::<&bool>(b).unwrap());
1405    }
1406
1407    #[test]
1408    fn remove_nothing() {
1409        let mut world = World::new();
1410        let a = world.spawn(("abc", 123));
1411        world.remove::<()>(a).unwrap();
1412    }
1413
1414    #[test]
1415    fn bad_insert() {
1416        let mut world = World::new();
1417        assert!(world.insert_one(Entity::DANGLING, ()).is_err());
1418    }
1419}
gloss_hecs/world.rs

gloss_hecs/
world.rs
