bevy_ecs/entity/
mod.rs

1//! Entity handling types.
2//!
3//! An **entity** exclusively owns zero or more [component] instances, all of different types, and can dynamically acquire or lose them over its lifetime.
4//!
5//! **empty entity**: Entity with zero components.
6//! **pending entity**: Entity reserved, but not flushed yet (see [`Entities::flush`] docs for reference).
7//! **reserved entity**: same as **pending entity**.
8//! **invalid entity**: **pending entity** flushed with invalid (see [`Entities::flush_as_invalid`] docs for reference).
9//!
10//! See [`Entity`] to learn more.
11//!
12//! [component]: crate::component::Component
13//!
14//! # Usage
15//!
16//! Operations involving entities and their components are performed either from a system by submitting commands,
17//! or from the outside (or from an exclusive system) by directly using [`World`] methods:
18//!
19//! |Operation|Command|Method|
20//! |:---:|:---:|:---:|
21//! |Spawn an entity with components|[`Commands::spawn`]|[`World::spawn`]|
22//! |Spawn an entity without components|[`Commands::spawn_empty`]|[`World::spawn_empty`]|
23//! |Despawn an entity|[`EntityCommands::despawn`]|[`World::despawn`]|
24//! |Insert a component, bundle, or tuple of components and bundles to an entity|[`EntityCommands::insert`]|[`EntityWorldMut::insert`]|
25//! |Remove a component, bundle, or tuple of components and bundles from an entity|[`EntityCommands::remove`]|[`EntityWorldMut::remove`]|
26//!
27//! [`World`]: crate::world::World
28//! [`Commands::spawn`]: crate::system::Commands::spawn
29//! [`Commands::spawn_empty`]: crate::system::Commands::spawn_empty
30//! [`EntityCommands::despawn`]: crate::system::EntityCommands::despawn
31//! [`EntityCommands::insert`]: crate::system::EntityCommands::insert
32//! [`EntityCommands::remove`]: crate::system::EntityCommands::remove
33//! [`World::spawn`]: crate::world::World::spawn
34//! [`World::spawn_empty`]: crate::world::World::spawn_empty
35//! [`World::despawn`]: crate::world::World::despawn
36//! [`EntityWorldMut::insert`]: crate::world::EntityWorldMut::insert
37//! [`EntityWorldMut::remove`]: crate::world::EntityWorldMut::remove
38mod map_entities;
39#[cfg(feature = "bevy_reflect")]
40use bevy_reflect::Reflect;
41#[cfg(all(feature = "bevy_reflect", feature = "serialize"))]
42use bevy_reflect::{ReflectDeserialize, ReflectSerialize};
43pub use map_entities::*;
44
45mod hash;
46pub use hash::*;
47
48use bevy_utils::tracing::warn;
49
50use crate::{
51    archetype::{ArchetypeId, ArchetypeRow},
52    identifier::{
53        error::IdentifierError,
54        kinds::IdKind,
55        masks::{IdentifierMask, HIGH_MASK},
56        Identifier,
57    },
58    storage::{SparseSetIndex, TableId, TableRow},
59};
60#[cfg(feature = "serialize")]
61use serde::{Deserialize, Serialize};
62use std::{fmt, hash::Hash, mem, num::NonZeroU32, sync::atomic::Ordering};
63
64#[cfg(target_has_atomic = "64")]
65use std::sync::atomic::AtomicI64 as AtomicIdCursor;
66#[cfg(target_has_atomic = "64")]
67type IdCursor = i64;
68
69/// Most modern platforms support 64-bit atomics, but some less-common platforms
70/// do not. This fallback allows compilation using a 32-bit cursor instead, with
71/// the caveat that some conversions may fail (and panic) at runtime.
72#[cfg(not(target_has_atomic = "64"))]
73use std::sync::atomic::AtomicIsize as AtomicIdCursor;
74#[cfg(not(target_has_atomic = "64"))]
75type IdCursor = isize;
76
77/// Lightweight identifier of an [entity](crate::entity).
78///
79/// The identifier is implemented using a [generational index]: a combination of an index and a generation.
80/// This allows fast insertion after data removal in an array while minimizing loss of spatial locality.
81///
82/// These identifiers are only valid on the [`World`] it's sourced from. Attempting to use an `Entity` to
83/// fetch entity components or metadata from a different world will either fail or return unexpected results.
84///
85/// [generational index]: https://lucassardois.medium.com/generational-indices-guide-8e3c5f7fd594
86///
87/// # Stability warning
88/// For all intents and purposes, `Entity` should be treated as an opaque identifier. The internal bit
89/// representation is liable to change from release to release as are the behaviors or performance
90/// characteristics of any of its trait implementations (i.e. `Ord`, `Hash`, etc.). This means that changes in
91/// `Entity`'s representation, though made readable through various functions on the type, are not considered
92/// breaking changes under [SemVer].
93///
94/// In particular, directly serializing with `Serialize` and `Deserialize` make zero guarantee of long
95/// term wire format compatibility. Changes in behavior will cause serialized `Entity` values persisted
96/// to long term storage (i.e. disk, databases, etc.) will fail to deserialize upon being updated.
97///
98/// # Usage
99///
100/// This data type is returned by iterating a `Query` that has `Entity` as part of its query fetch type parameter ([learn more]).
101/// It can also be obtained by calling [`EntityCommands::id`] or [`EntityWorldMut::id`].
102///
103/// ```
104/// # use bevy_ecs::prelude::*;
105/// # #[derive(Component)]
106/// # struct SomeComponent;
107/// fn setup(mut commands: Commands) {
108///     // Calling `spawn` returns `EntityCommands`.
109///     let entity = commands.spawn(SomeComponent).id();
110/// }
111///
112/// fn exclusive_system(world: &mut World) {
113///     // Calling `spawn` returns `EntityWorldMut`.
114///     let entity = world.spawn(SomeComponent).id();
115/// }
116/// #
117/// # bevy_ecs::system::assert_is_system(setup);
118/// # bevy_ecs::system::assert_is_system(exclusive_system);
119/// ```
120///
121/// It can be used to refer to a specific entity to apply [`EntityCommands`], or to call [`Query::get`] (or similar methods) to access its components.
122///
123/// ```
124/// # use bevy_ecs::prelude::*;
125/// #
126/// # #[derive(Component)]
127/// # struct Expired;
128/// #
129/// fn dispose_expired_food(mut commands: Commands, query: Query<Entity, With<Expired>>) {
130///     for food_entity in &query {
131///         commands.entity(food_entity).despawn();
132///     }
133/// }
134/// #
135/// # bevy_ecs::system::assert_is_system(dispose_expired_food);
136/// ```
137///
138/// [learn more]: crate::system::Query#entity-id-access
139/// [`EntityCommands::id`]: crate::system::EntityCommands::id
140/// [`EntityWorldMut::id`]: crate::world::EntityWorldMut::id
141/// [`EntityCommands`]: crate::system::EntityCommands
142/// [`Query::get`]: crate::system::Query::get
143/// [`World`]: crate::world::World
144/// [SemVer]: https://semver.org/
145#[derive(Clone, Copy, Debug)]
146#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
147#[cfg_attr(feature = "bevy_reflect", reflect_value(Hash, PartialEq))]
148#[cfg_attr(
149    all(feature = "bevy_reflect", feature = "serialize"),
150    reflect_value(Serialize, Deserialize)
151)]
152// Alignment repr necessary to allow LLVM to better output
153// optimised codegen for `to_bits`, `PartialEq` and `Ord`.
154#[repr(C, align(8))]
155pub struct Entity {
156    // Do not reorder the fields here. The ordering is explicitly used by repr(C)
157    // to make this struct equivalent to a u64.
158    #[cfg(target_endian = "little")]
159    index: u32,
160    generation: NonZeroU32,
161    #[cfg(target_endian = "big")]
162    index: u32,
163}
164
165// By not short-circuiting in comparisons, we get better codegen.
166// See <https://github.com/rust-lang/rust/issues/117800>
167impl PartialEq for Entity {
168    #[inline]
169    fn eq(&self, other: &Entity) -> bool {
170        // By using `to_bits`, the codegen can be optimised out even
171        // further potentially. Relies on the correct alignment/field
172        // order of `Entity`.
173        self.to_bits() == other.to_bits()
174    }
175}
176
177impl Eq for Entity {}
178
179// The derive macro codegen output is not optimal and can't be optimised as well
180// by the compiler. This impl resolves the issue of non-optimal codegen by relying
181// on comparing against the bit representation of `Entity` instead of comparing
182// the fields. The result is then LLVM is able to optimise the codegen for Entity
183// far beyond what the derive macro can.
184// See <https://github.com/rust-lang/rust/issues/106107>
185impl PartialOrd for Entity {
186    #[inline]
187    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
188        // Make use of our `Ord` impl to ensure optimal codegen output
189        Some(self.cmp(other))
190    }
191}
192
193// The derive macro codegen output is not optimal and can't be optimised as well
194// by the compiler. This impl resolves the issue of non-optimal codegen by relying
195// on comparing against the bit representation of `Entity` instead of comparing
196// the fields. The result is then LLVM is able to optimise the codegen for Entity
197// far beyond what the derive macro can.
198// See <https://github.com/rust-lang/rust/issues/106107>
199impl Ord for Entity {
200    #[inline]
201    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
202        // This will result in better codegen for ordering comparisons, plus
203        // avoids pitfalls with regards to macro codegen relying on property
204        // position when we want to compare against the bit representation.
205        self.to_bits().cmp(&other.to_bits())
206    }
207}
208
209impl Hash for Entity {
210    #[inline]
211    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
212        self.to_bits().hash(state);
213    }
214}
215
216pub(crate) enum AllocAtWithoutReplacement {
217    Exists(EntityLocation),
218    DidNotExist,
219    ExistsWithWrongGeneration,
220}
221
222impl Entity {
223    /// Construct an [`Entity`] from a raw `index` value and a non-zero `generation` value.
224    /// Ensure that the generation value is never greater than `0x7FFF_FFFF`.
225    #[inline(always)]
226    pub(crate) const fn from_raw_and_generation(index: u32, generation: NonZeroU32) -> Entity {
227        debug_assert!(generation.get() <= HIGH_MASK);
228
229        Self { index, generation }
230    }
231
232    /// An entity ID with a placeholder value. This may or may not correspond to an actual entity,
233    /// and should be overwritten by a new value before being used.
234    ///
235    /// ## Examples
236    ///
237    /// Initializing a collection (e.g. `array` or `Vec`) with a known size:
238    ///
239    /// ```no_run
240    /// # use bevy_ecs::prelude::*;
241    /// // Create a new array of size 10 filled with invalid entity ids.
242    /// let mut entities: [Entity; 10] = [Entity::PLACEHOLDER; 10];
243    ///
244    /// // ... replace the entities with valid ones.
245    /// ```
246    ///
247    /// Deriving [`Reflect`] for a component that has an `Entity` field:
248    ///
249    /// ```no_run
250    /// # use bevy_ecs::{prelude::*, component::*};
251    /// # use bevy_reflect::Reflect;
252    /// #[derive(Reflect, Component)]
253    /// #[reflect(Component)]
254    /// pub struct MyStruct {
255    ///     pub entity: Entity,
256    /// }
257    ///
258    /// impl FromWorld for MyStruct {
259    ///     fn from_world(_world: &mut World) -> Self {
260    ///         Self {
261    ///             entity: Entity::PLACEHOLDER,
262    ///         }
263    ///     }
264    /// }
265    /// ```
266    pub const PLACEHOLDER: Self = Self::from_raw(u32::MAX);
267
268    /// Creates a new entity ID with the specified `index` and a generation of 1.
269    ///
270    /// # Note
271    ///
272    /// Spawning a specific `entity` value is __rarely the right choice__. Most apps should favor
273    /// [`Commands::spawn`](crate::system::Commands::spawn). This method should generally
274    /// only be used for sharing entities across apps, and only when they have a scheme
275    /// worked out to share an index space (which doesn't happen by default).
276    ///
277    /// In general, one should not try to synchronize the ECS by attempting to ensure that
278    /// `Entity` lines up between instances, but instead insert a secondary identifier as
279    /// a component.
280    #[inline(always)]
281    pub const fn from_raw(index: u32) -> Entity {
282        Self::from_raw_and_generation(index, NonZeroU32::MIN)
283    }
284
285    /// Convert to a form convenient for passing outside of rust.
286    ///
287    /// Only useful for identifying entities within the same instance of an application. Do not use
288    /// for serialization between runs.
289    ///
290    /// No particular structure is guaranteed for the returned bits.
291    #[inline(always)]
292    pub const fn to_bits(self) -> u64 {
293        IdentifierMask::pack_into_u64(self.index, self.generation.get())
294    }
295
296    /// Reconstruct an `Entity` previously destructured with [`Entity::to_bits`].
297    ///
298    /// Only useful when applied to results from `to_bits` in the same instance of an application.
299    ///
300    /// # Panics
301    ///
302    /// This method will likely panic if given `u64` values that did not come from [`Entity::to_bits`].
303    #[inline]
304    pub const fn from_bits(bits: u64) -> Self {
305        // Construct an Identifier initially to extract the kind from.
306        let id = Self::try_from_bits(bits);
307
308        match id {
309            Ok(entity) => entity,
310            Err(_) => panic!("Attempted to initialise invalid bits as an entity"),
311        }
312    }
313
314    /// Reconstruct an `Entity` previously destructured with [`Entity::to_bits`].
315    ///
316    /// Only useful when applied to results from `to_bits` in the same instance of an application.
317    ///
318    /// This method is the fallible counterpart to [`Entity::from_bits`].
319    #[inline(always)]
320    pub const fn try_from_bits(bits: u64) -> Result<Self, IdentifierError> {
321        if let Ok(id) = Identifier::try_from_bits(bits) {
322            let kind = id.kind() as u8;
323
324            if kind == (IdKind::Entity as u8) {
325                return Ok(Self {
326                    index: id.low(),
327                    generation: id.high(),
328                });
329            }
330        }
331
332        Err(IdentifierError::InvalidEntityId(bits))
333    }
334
335    /// Return a transiently unique identifier.
336    ///
337    /// No two simultaneously-live entities share the same index, but dead entities' indices may collide
338    /// with both live and dead entities. Useful for compactly representing entities within a
339    /// specific snapshot of the world, such as when serializing.
340    #[inline]
341    pub const fn index(self) -> u32 {
342        self.index
343    }
344
345    /// Returns the generation of this Entity's index. The generation is incremented each time an
346    /// entity with a given index is despawned. This serves as a "count" of the number of times a
347    /// given index has been reused (index, generation) pairs uniquely identify a given Entity.
348    #[inline]
349    pub const fn generation(self) -> u32 {
350        // Mask so not to expose any flags
351        IdentifierMask::extract_value_from_high(self.generation.get())
352    }
353}
354
355impl TryFrom<Identifier> for Entity {
356    type Error = IdentifierError;
357
358    #[inline]
359    fn try_from(value: Identifier) -> Result<Self, Self::Error> {
360        Self::try_from_bits(value.to_bits())
361    }
362}
363
364impl From<Entity> for Identifier {
365    #[inline]
366    fn from(value: Entity) -> Self {
367        Identifier::from_bits(value.to_bits())
368    }
369}
370
371#[cfg(feature = "serialize")]
372impl Serialize for Entity {
373    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
374    where
375        S: serde::Serializer,
376    {
377        serializer.serialize_u64(self.to_bits())
378    }
379}
380
381#[cfg(feature = "serialize")]
382impl<'de> Deserialize<'de> for Entity {
383    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
384    where
385        D: serde::Deserializer<'de>,
386    {
387        use serde::de::Error;
388        let id: u64 = serde::de::Deserialize::deserialize(deserializer)?;
389        Entity::try_from_bits(id).map_err(D::Error::custom)
390    }
391}
392
393impl fmt::Display for Entity {
394    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
395        write!(f, "{}v{}", self.index(), self.generation())
396    }
397}
398
399impl SparseSetIndex for Entity {
400    #[inline]
401    fn sparse_set_index(&self) -> usize {
402        self.index() as usize
403    }
404
405    #[inline]
406    fn get_sparse_set_index(value: usize) -> Self {
407        Entity::from_raw(value as u32)
408    }
409}
410
411/// An [`Iterator`] returning a sequence of [`Entity`] values from
412pub struct ReserveEntitiesIterator<'a> {
413    // Metas, so we can recover the current generation for anything in the freelist.
414    meta: &'a [EntityMeta],
415
416    // Reserved indices formerly in the freelist to hand out.
417    index_iter: std::slice::Iter<'a, u32>,
418
419    // New Entity indices to hand out, outside the range of meta.len().
420    index_range: std::ops::Range<u32>,
421}
422
423impl<'a> Iterator for ReserveEntitiesIterator<'a> {
424    type Item = Entity;
425
426    fn next(&mut self) -> Option<Self::Item> {
427        self.index_iter
428            .next()
429            .map(|&index| {
430                Entity::from_raw_and_generation(index, self.meta[index as usize].generation)
431            })
432            .or_else(|| self.index_range.next().map(Entity::from_raw))
433    }
434
435    fn size_hint(&self) -> (usize, Option<usize>) {
436        let len = self.index_iter.len() + self.index_range.len();
437        (len, Some(len))
438    }
439}
440
441impl<'a> ExactSizeIterator for ReserveEntitiesIterator<'a> {}
442impl<'a> core::iter::FusedIterator for ReserveEntitiesIterator<'a> {}
443
444/// A [`World`]'s internal metadata store on all of its entities.
445///
446/// Contains metadata on:
447///  - The generation of every entity.
448///  - The alive/dead status of a particular entity. (i.e. "has entity 3 been despawned?")
449///  - The location of the entity's components in memory (via [`EntityLocation`])
450///
451/// [`World`]: crate::world::World
452#[derive(Debug)]
453pub struct Entities {
454    meta: Vec<EntityMeta>,
455
456    /// The `pending` and `free_cursor` fields describe three sets of Entity IDs
457    /// that have been freed or are in the process of being allocated:
458    ///
459    /// - The `freelist` IDs, previously freed by `free()`. These IDs are available to any of
460    ///   [`alloc`], [`reserve_entity`] or [`reserve_entities`]. Allocation will always prefer
461    ///   these over brand new IDs.
462    ///
463    /// - The `reserved` list of IDs that were once in the freelist, but got reserved by
464    ///   [`reserve_entities`] or [`reserve_entity`]. They are now waiting for [`flush`] to make them
465    ///   fully allocated.
466    ///
467    /// - The count of new IDs that do not yet exist in `self.meta`, but which we have handed out
468    ///   and reserved. [`flush`] will allocate room for them in `self.meta`.
469    ///
470    /// The contents of `pending` look like this:
471    ///
472    /// ```txt
473    /// ----------------------------
474    /// |  freelist  |  reserved   |
475    /// ----------------------------
476    ///              ^             ^
477    ///          free_cursor   pending.len()
478    /// ```
479    ///
480    /// As IDs are allocated, `free_cursor` is atomically decremented, moving
481    /// items from the freelist into the reserved list by sliding over the boundary.
482    ///
483    /// Once the freelist runs out, `free_cursor` starts going negative.
484    /// The more negative it is, the more IDs have been reserved starting exactly at
485    /// the end of `meta.len()`.
486    ///
487    /// This formulation allows us to reserve any number of IDs first from the freelist
488    /// and then from the new IDs, using only a single atomic subtract.
489    ///
490    /// Once [`flush`] is done, `free_cursor` will equal `pending.len()`.
491    ///
492    /// [`alloc`]: Entities::alloc
493    /// [`reserve_entity`]: Entities::reserve_entity
494    /// [`reserve_entities`]: Entities::reserve_entities
495    /// [`flush`]: Entities::flush
496    pending: Vec<u32>,
497    free_cursor: AtomicIdCursor,
498    /// Stores the number of free entities for [`len`](Entities::len)
499    len: u32,
500}
501
502impl Entities {
503    pub(crate) const fn new() -> Self {
504        Entities {
505            meta: Vec::new(),
506            pending: Vec::new(),
507            free_cursor: AtomicIdCursor::new(0),
508            len: 0,
509        }
510    }
511
512    /// Reserve entity IDs concurrently.
513    ///
514    /// Storage for entity generation and location is lazily allocated by calling [`flush`](Entities::flush).
515    #[allow(clippy::unnecessary_fallible_conversions)] // Because `IdCursor::try_from` may fail on 32-bit platforms.
516    pub fn reserve_entities(&self, count: u32) -> ReserveEntitiesIterator {
517        // Use one atomic subtract to grab a range of new IDs. The range might be
518        // entirely nonnegative, meaning all IDs come from the freelist, or entirely
519        // negative, meaning they are all new IDs to allocate, or a mix of both.
520        let range_end = self
521            .free_cursor
522            // Unwrap: these conversions can only fail on platforms that don't support 64-bit atomics
523            // and use AtomicIsize instead (see note on `IdCursor`).
524            .fetch_sub(IdCursor::try_from(count).unwrap(), Ordering::Relaxed);
525        let range_start = range_end - IdCursor::try_from(count).unwrap();
526
527        let freelist_range = range_start.max(0) as usize..range_end.max(0) as usize;
528
529        let (new_id_start, new_id_end) = if range_start >= 0 {
530            // We satisfied all requests from the freelist.
531            (0, 0)
532        } else {
533            // We need to allocate some new Entity IDs outside of the range of self.meta.
534            //
535            // `range_start` covers some negative territory, e.g. `-3..6`.
536            // Since the nonnegative values `0..6` are handled by the freelist, that
537            // means we need to handle the negative range here.
538            //
539            // In this example, we truncate the end to 0, leaving us with `-3..0`.
540            // Then we negate these values to indicate how far beyond the end of `meta.end()`
541            // to go, yielding `meta.len()+0 .. meta.len()+3`.
542            let base = self.meta.len() as IdCursor;
543
544            let new_id_end = u32::try_from(base - range_start).expect("too many entities");
545
546            // `new_id_end` is in range, so no need to check `start`.
547            let new_id_start = (base - range_end.min(0)) as u32;
548
549            (new_id_start, new_id_end)
550        };
551
552        ReserveEntitiesIterator {
553            meta: &self.meta[..],
554            index_iter: self.pending[freelist_range].iter(),
555            index_range: new_id_start..new_id_end,
556        }
557    }
558
559    /// Reserve one entity ID concurrently.
560    ///
561    /// Equivalent to `self.reserve_entities(1).next().unwrap()`, but more efficient.
562    pub fn reserve_entity(&self) -> Entity {
563        let n = self.free_cursor.fetch_sub(1, Ordering::Relaxed);
564        if n > 0 {
565            // Allocate from the freelist.
566            let index = self.pending[(n - 1) as usize];
567            Entity::from_raw_and_generation(index, self.meta[index as usize].generation)
568        } else {
569            // Grab a new ID, outside the range of `meta.len()`. `flush()` must
570            // eventually be called to make it valid.
571            //
572            // As `self.free_cursor` goes more and more negative, we return IDs farther
573            // and farther beyond `meta.len()`.
574            Entity::from_raw(
575                u32::try_from(self.meta.len() as IdCursor - n).expect("too many entities"),
576            )
577        }
578    }
579
580    /// Check that we do not have pending work requiring `flush()` to be called.
581    fn verify_flushed(&mut self) {
582        debug_assert!(
583            !self.needs_flush(),
584            "flush() needs to be called before this operation is legal"
585        );
586    }
587
588    /// Allocate an entity ID directly.
589    pub fn alloc(&mut self) -> Entity {
590        self.verify_flushed();
591        self.len += 1;
592        if let Some(index) = self.pending.pop() {
593            let new_free_cursor = self.pending.len() as IdCursor;
594            *self.free_cursor.get_mut() = new_free_cursor;
595            Entity::from_raw_and_generation(index, self.meta[index as usize].generation)
596        } else {
597            let index = u32::try_from(self.meta.len()).expect("too many entities");
598            self.meta.push(EntityMeta::EMPTY);
599            Entity::from_raw(index)
600        }
601    }
602
603    /// Allocate a specific entity ID, overwriting its generation.
604    ///
605    /// Returns the location of the entity currently using the given ID, if any. Location should be
606    /// written immediately.
607    pub fn alloc_at(&mut self, entity: Entity) -> Option<EntityLocation> {
608        self.verify_flushed();
609
610        let loc = if entity.index() as usize >= self.meta.len() {
611            self.pending
612                .extend((self.meta.len() as u32)..entity.index());
613            let new_free_cursor = self.pending.len() as IdCursor;
614            *self.free_cursor.get_mut() = new_free_cursor;
615            self.meta
616                .resize(entity.index() as usize + 1, EntityMeta::EMPTY);
617            self.len += 1;
618            None
619        } else if let Some(index) = self.pending.iter().position(|item| *item == entity.index()) {
620            self.pending.swap_remove(index);
621            let new_free_cursor = self.pending.len() as IdCursor;
622            *self.free_cursor.get_mut() = new_free_cursor;
623            self.len += 1;
624            None
625        } else {
626            Some(mem::replace(
627                &mut self.meta[entity.index() as usize].location,
628                EntityMeta::EMPTY.location,
629            ))
630        };
631
632        self.meta[entity.index() as usize].generation = entity.generation;
633
634        loc
635    }
636
637    /// Allocate a specific entity ID, overwriting its generation.
638    ///
639    /// Returns the location of the entity currently using the given ID, if any.
640    pub(crate) fn alloc_at_without_replacement(
641        &mut self,
642        entity: Entity,
643    ) -> AllocAtWithoutReplacement {
644        self.verify_flushed();
645
646        let result = if entity.index() as usize >= self.meta.len() {
647            self.pending
648                .extend((self.meta.len() as u32)..entity.index());
649            let new_free_cursor = self.pending.len() as IdCursor;
650            *self.free_cursor.get_mut() = new_free_cursor;
651            self.meta
652                .resize(entity.index() as usize + 1, EntityMeta::EMPTY);
653            self.len += 1;
654            AllocAtWithoutReplacement::DidNotExist
655        } else if let Some(index) = self.pending.iter().position(|item| *item == entity.index()) {
656            self.pending.swap_remove(index);
657            let new_free_cursor = self.pending.len() as IdCursor;
658            *self.free_cursor.get_mut() = new_free_cursor;
659            self.len += 1;
660            AllocAtWithoutReplacement::DidNotExist
661        } else {
662            let current_meta = &self.meta[entity.index() as usize];
663            if current_meta.location.archetype_id == ArchetypeId::INVALID {
664                AllocAtWithoutReplacement::DidNotExist
665            } else if current_meta.generation == entity.generation {
666                AllocAtWithoutReplacement::Exists(current_meta.location)
667            } else {
668                return AllocAtWithoutReplacement::ExistsWithWrongGeneration;
669            }
670        };
671
672        self.meta[entity.index() as usize].generation = entity.generation;
673        result
674    }
675
676    /// Destroy an entity, allowing it to be reused.
677    ///
678    /// Must not be called while reserved entities are awaiting `flush()`.
679    pub fn free(&mut self, entity: Entity) -> Option<EntityLocation> {
680        self.verify_flushed();
681
682        let meta = &mut self.meta[entity.index() as usize];
683        if meta.generation != entity.generation {
684            return None;
685        }
686
687        meta.generation = IdentifierMask::inc_masked_high_by(meta.generation, 1);
688
689        if meta.generation == NonZeroU32::MIN {
690            warn!(
691                "Entity({}) generation wrapped on Entities::free, aliasing may occur",
692                entity.index
693            );
694        }
695
696        let loc = mem::replace(&mut meta.location, EntityMeta::EMPTY.location);
697
698        self.pending.push(entity.index());
699
700        let new_free_cursor = self.pending.len() as IdCursor;
701        *self.free_cursor.get_mut() = new_free_cursor;
702        self.len -= 1;
703        Some(loc)
704    }
705
706    /// Ensure at least `n` allocations can succeed without reallocating.
707    #[allow(clippy::unnecessary_fallible_conversions)] // Because `IdCursor::try_from` may fail on 32-bit platforms.
708    pub fn reserve(&mut self, additional: u32) {
709        self.verify_flushed();
710
711        let freelist_size = *self.free_cursor.get_mut();
712        // Unwrap: these conversions can only fail on platforms that don't support 64-bit atomics
713        // and use AtomicIsize instead (see note on `IdCursor`).
714        let shortfall = IdCursor::try_from(additional).unwrap() - freelist_size;
715        if shortfall > 0 {
716            self.meta.reserve(shortfall as usize);
717        }
718    }
719
720    /// Returns true if the [`Entities`] contains [`entity`](Entity).
721    // This will return false for entities which have been freed, even if
722    // not reallocated since the generation is incremented in `free`
723    pub fn contains(&self, entity: Entity) -> bool {
724        self.resolve_from_id(entity.index())
725            .map_or(false, |e| e.generation() == entity.generation())
726    }
727
728    /// Clears all [`Entity`] from the World.
729    pub fn clear(&mut self) {
730        self.meta.clear();
731        self.pending.clear();
732        *self.free_cursor.get_mut() = 0;
733        self.len = 0;
734    }
735
736    /// Returns the location of an [`Entity`].
737    /// Note: for pending entities, returns `Some(EntityLocation::INVALID)`.
738    #[inline]
739    pub fn get(&self, entity: Entity) -> Option<EntityLocation> {
740        if let Some(meta) = self.meta.get(entity.index() as usize) {
741            if meta.generation != entity.generation
742                || meta.location.archetype_id == ArchetypeId::INVALID
743            {
744                return None;
745            }
746            Some(meta.location)
747        } else {
748            None
749        }
750    }
751
752    /// Updates the location of an [`Entity`]. This must be called when moving the components of
753    /// the entity around in storage.
754    ///
755    /// # Safety
756    ///  - `index` must be a valid entity index.
757    ///  - `location` must be valid for the entity at `index` or immediately made valid afterwards
758    ///    before handing control to unknown code.
759    #[inline]
760    pub(crate) unsafe fn set(&mut self, index: u32, location: EntityLocation) {
761        // SAFETY: Caller guarantees that `index` a valid entity index
762        let meta = unsafe { self.meta.get_unchecked_mut(index as usize) };
763        meta.location = location;
764    }
765
766    /// Increments the `generation` of a freed [`Entity`]. The next entity ID allocated with this
767    /// `index` will count `generation` starting from the prior `generation` + the specified
768    /// value + 1.
769    ///
770    /// Does nothing if no entity with this `index` has been allocated yet.
771    pub(crate) fn reserve_generations(&mut self, index: u32, generations: u32) -> bool {
772        if (index as usize) >= self.meta.len() {
773            return false;
774        }
775
776        let meta = &mut self.meta[index as usize];
777        if meta.location.archetype_id == ArchetypeId::INVALID {
778            meta.generation = IdentifierMask::inc_masked_high_by(meta.generation, generations);
779            true
780        } else {
781            false
782        }
783    }
784
785    /// Get the [`Entity`] with a given id, if it exists in this [`Entities`] collection
786    /// Returns `None` if this [`Entity`] is outside of the range of currently reserved Entities
787    ///
788    /// Note: This method may return [`Entities`](Entity) which are currently free
789    /// Note that [`contains`](Entities::contains) will correctly return false for freed
790    /// entities, since it checks the generation
791    pub fn resolve_from_id(&self, index: u32) -> Option<Entity> {
792        let idu = index as usize;
793        if let Some(&EntityMeta { generation, .. }) = self.meta.get(idu) {
794            Some(Entity::from_raw_and_generation(index, generation))
795        } else {
796            // `id` is outside of the meta list - check whether it is reserved but not yet flushed.
797            let free_cursor = self.free_cursor.load(Ordering::Relaxed);
798            // If this entity was manually created, then free_cursor might be positive
799            // Returning None handles that case correctly
800            let num_pending = usize::try_from(-free_cursor).ok()?;
801            (idu < self.meta.len() + num_pending).then_some(Entity::from_raw(index))
802        }
803    }
804
805    fn needs_flush(&mut self) -> bool {
806        *self.free_cursor.get_mut() != self.pending.len() as IdCursor
807    }
808
809    /// Allocates space for entities previously reserved with [`reserve_entity`](Entities::reserve_entity) or
810    /// [`reserve_entities`](Entities::reserve_entities), then initializes each one using the supplied function.
811    ///
812    /// # Safety
813    /// Flush _must_ set the entity location to the correct [`ArchetypeId`] for the given [`Entity`]
814    /// each time init is called. This _can_ be [`ArchetypeId::INVALID`], provided the [`Entity`]
815    /// has not been assigned to an [`Archetype`][crate::archetype::Archetype].
816    ///
817    /// Note: freshly-allocated entities (ones which don't come from the pending list) are guaranteed
818    /// to be initialized with the invalid archetype.
819    pub unsafe fn flush(&mut self, mut init: impl FnMut(Entity, &mut EntityLocation)) {
820        let free_cursor = self.free_cursor.get_mut();
821        let current_free_cursor = *free_cursor;
822
823        let new_free_cursor = if current_free_cursor >= 0 {
824            current_free_cursor as usize
825        } else {
826            let old_meta_len = self.meta.len();
827            let new_meta_len = old_meta_len + -current_free_cursor as usize;
828            self.meta.resize(new_meta_len, EntityMeta::EMPTY);
829            self.len += -current_free_cursor as u32;
830            for (index, meta) in self.meta.iter_mut().enumerate().skip(old_meta_len) {
831                init(
832                    Entity::from_raw_and_generation(index as u32, meta.generation),
833                    &mut meta.location,
834                );
835            }
836
837            *free_cursor = 0;
838            0
839        };
840
841        self.len += (self.pending.len() - new_free_cursor) as u32;
842        for index in self.pending.drain(new_free_cursor..) {
843            let meta = &mut self.meta[index as usize];
844            init(
845                Entity::from_raw_and_generation(index, meta.generation),
846                &mut meta.location,
847            );
848        }
849    }
850
851    /// Flushes all reserved entities to an "invalid" state. Attempting to retrieve them will return `None`
852    /// unless they are later populated with a valid archetype.
853    pub fn flush_as_invalid(&mut self) {
854        // SAFETY: as per `flush` safety docs, the archetype id can be set to [`ArchetypeId::INVALID`] if
855        // the [`Entity`] has not been assigned to an [`Archetype`][crate::archetype::Archetype], which is the case here
856        unsafe {
857            self.flush(|_entity, location| {
858                location.archetype_id = ArchetypeId::INVALID;
859            });
860        }
861    }
862
863    /// # Safety
864    ///
865    /// This function is safe if and only if the world this Entities is on has no entities.
866    pub unsafe fn flush_and_reserve_invalid_assuming_no_entities(&mut self, count: usize) {
867        let free_cursor = self.free_cursor.get_mut();
868        *free_cursor = 0;
869        self.meta.reserve(count);
870        // SAFETY: The EntityMeta struct only contains integers, and it is valid to have all bytes set to u8::MAX
871        unsafe {
872            self.meta.as_mut_ptr().write_bytes(u8::MAX, count);
873        }
874        // SAFETY: We have reserved `count` elements above and we have initialized values from index 0 to `count`.
875        unsafe {
876            self.meta.set_len(count);
877        }
878
879        self.len = count as u32;
880    }
881
882    /// The count of all entities in the [`World`] that have ever been allocated
883    /// including the entities that are currently freed.
884    ///
885    /// This does not include entities that have been reserved but have never been
886    /// allocated yet.
887    ///
888    /// [`World`]: crate::world::World
889    #[inline]
890    pub fn total_count(&self) -> usize {
891        self.meta.len()
892    }
893
894    /// The count of currently allocated entities.
895    #[inline]
896    pub fn len(&self) -> u32 {
897        self.len
898    }
899
900    /// Checks if any entity is currently active.
901    #[inline]
902    pub fn is_empty(&self) -> bool {
903        self.len == 0
904    }
905}
906
907// This type is repr(C) to ensure that the layout and values within it can be safe to fully fill
908// with u8::MAX, as required by [`Entities::flush_and_reserve_invalid_assuming_no_entities`].
909// Safety:
910// This type must not contain any pointers at any level, and be safe to fully fill with u8::MAX.
911/// Metadata for an [`Entity`].
912#[derive(Copy, Clone, Debug)]
913#[repr(C)]
914struct EntityMeta {
915    /// The current generation of the [`Entity`].
916    pub generation: NonZeroU32,
917    /// The current location of the [`Entity`]
918    pub location: EntityLocation,
919}
920
921impl EntityMeta {
922    /// meta for **pending entity**
923    const EMPTY: EntityMeta = EntityMeta {
924        generation: NonZeroU32::MIN,
925        location: EntityLocation::INVALID,
926    };
927}
928
929// This type is repr(C) to ensure that the layout and values within it can be safe to fully fill
930// with u8::MAX, as required by [`Entities::flush_and_reserve_invalid_assuming_no_entities`].
931// SAFETY:
932// This type must not contain any pointers at any level, and be safe to fully fill with u8::MAX.
933/// A location of an entity in an archetype.
934#[derive(Copy, Clone, Debug, PartialEq)]
935#[repr(C)]
936pub struct EntityLocation {
937    /// The ID of the [`Archetype`] the [`Entity`] belongs to.
938    ///
939    /// [`Archetype`]: crate::archetype::Archetype
940    pub archetype_id: ArchetypeId,
941
942    /// The index of the [`Entity`] within its [`Archetype`].
943    ///
944    /// [`Archetype`]: crate::archetype::Archetype
945    pub archetype_row: ArchetypeRow,
946
947    /// The ID of the [`Table`] the [`Entity`] belongs to.
948    ///
949    /// [`Table`]: crate::storage::Table
950    pub table_id: TableId,
951
952    /// The index of the [`Entity`] within its [`Table`].
953    ///
954    /// [`Table`]: crate::storage::Table
955    pub table_row: TableRow,
956}
957
958impl EntityLocation {
959    /// location for **pending entity** and **invalid entity**
960    const INVALID: EntityLocation = EntityLocation {
961        archetype_id: ArchetypeId::INVALID,
962        archetype_row: ArchetypeRow::INVALID,
963        table_id: TableId::INVALID,
964        table_row: TableRow::INVALID,
965    };
966}
967
968#[cfg(test)]
969mod tests {
970    use super::*;
971
972    #[test]
973    fn entity_niche_optimization() {
974        assert_eq!(
975            std::mem::size_of::<Entity>(),
976            std::mem::size_of::<Option<Entity>>()
977        );
978    }
979
980    #[test]
981    fn entity_bits_roundtrip() {
982        // Generation cannot be greater than 0x7FFF_FFFF else it will be an invalid Entity id
983        let e = Entity::from_raw_and_generation(0xDEADBEEF, NonZeroU32::new(0x5AADF00D).unwrap());
984        assert_eq!(Entity::from_bits(e.to_bits()), e);
985    }
986
987    #[test]
988    fn reserve_entity_len() {
989        let mut e = Entities::new();
990        e.reserve_entity();
991        // SAFETY: entity_location is left invalid
992        unsafe { e.flush(|_, _| {}) };
993        assert_eq!(e.len(), 1);
994    }
995
996    #[test]
997    fn get_reserved_and_invalid() {
998        let mut entities = Entities::new();
999        let e = entities.reserve_entity();
1000        assert!(entities.contains(e));
1001        assert!(entities.get(e).is_none());
1002
1003        // SAFETY: entity_location is left invalid
1004        unsafe {
1005            entities.flush(|_entity, _location| {
1006                // do nothing ... leaving entity location invalid
1007            });
1008        };
1009
1010        assert!(entities.contains(e));
1011        assert!(entities.get(e).is_none());
1012    }
1013
1014    #[test]
1015    fn entity_const() {
1016        const C1: Entity = Entity::from_raw(42);
1017        assert_eq!(42, C1.index());
1018        assert_eq!(1, C1.generation());
1019
1020        const C2: Entity = Entity::from_bits(0x0000_00ff_0000_00cc);
1021        assert_eq!(0x0000_00cc, C2.index());
1022        assert_eq!(0x0000_00ff, C2.generation());
1023
1024        const C3: u32 = Entity::from_raw(33).index();
1025        assert_eq!(33, C3);
1026
1027        const C4: u32 = Entity::from_bits(0x00dd_00ff_0000_0000).generation();
1028        assert_eq!(0x00dd_00ff, C4);
1029    }
1030
1031    #[test]
1032    fn reserve_generations() {
1033        let mut entities = Entities::new();
1034        let entity = entities.alloc();
1035        entities.free(entity);
1036
1037        assert!(entities.reserve_generations(entity.index(), 1));
1038    }
1039
1040    #[test]
1041    fn reserve_generations_and_alloc() {
1042        const GENERATIONS: u32 = 10;
1043
1044        let mut entities = Entities::new();
1045        let entity = entities.alloc();
1046        entities.free(entity);
1047
1048        assert!(entities.reserve_generations(entity.index(), GENERATIONS));
1049
1050        // The very next entity allocated should be a further generation on the same index
1051        let next_entity = entities.alloc();
1052        assert_eq!(next_entity.index(), entity.index());
1053        assert!(next_entity.generation() > entity.generation() + GENERATIONS);
1054    }
1055
1056    #[test]
1057    #[allow(clippy::nonminimal_bool)] // This is intentionally testing `lt` and `ge` as separate functions.
1058    fn entity_comparison() {
1059        assert_eq!(
1060            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap()),
1061            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1062        );
1063        assert_ne!(
1064            Entity::from_raw_and_generation(123, NonZeroU32::new(789).unwrap()),
1065            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1066        );
1067        assert_ne!(
1068            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap()),
1069            Entity::from_raw_and_generation(123, NonZeroU32::new(789).unwrap())
1070        );
1071        assert_ne!(
1072            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap()),
1073            Entity::from_raw_and_generation(456, NonZeroU32::new(123).unwrap())
1074        );
1075
1076        // ordering is by generation then by index
1077
1078        assert!(
1079            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1080                >= Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1081        );
1082        assert!(
1083            Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1084                <= Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1085        );
1086        assert!(
1087            !(Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1088                < Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap()))
1089        );
1090        assert!(
1091            !(Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap())
1092                > Entity::from_raw_and_generation(123, NonZeroU32::new(456).unwrap()))
1093        );
1094
1095        assert!(
1096            Entity::from_raw_and_generation(9, NonZeroU32::new(1).unwrap())
1097                < Entity::from_raw_and_generation(1, NonZeroU32::new(9).unwrap())
1098        );
1099        assert!(
1100            Entity::from_raw_and_generation(1, NonZeroU32::new(9).unwrap())
1101                > Entity::from_raw_and_generation(9, NonZeroU32::new(1).unwrap())
1102        );
1103
1104        assert!(
1105            Entity::from_raw_and_generation(1, NonZeroU32::new(1).unwrap())
1106                < Entity::from_raw_and_generation(2, NonZeroU32::new(1).unwrap())
1107        );
1108        assert!(
1109            Entity::from_raw_and_generation(1, NonZeroU32::new(1).unwrap())
1110                <= Entity::from_raw_and_generation(2, NonZeroU32::new(1).unwrap())
1111        );
1112        assert!(
1113            Entity::from_raw_and_generation(2, NonZeroU32::new(2).unwrap())
1114                > Entity::from_raw_and_generation(1, NonZeroU32::new(2).unwrap())
1115        );
1116        assert!(
1117            Entity::from_raw_and_generation(2, NonZeroU32::new(2).unwrap())
1118                >= Entity::from_raw_and_generation(1, NonZeroU32::new(2).unwrap())
1119        );
1120    }
1121
1122    // Feel free to change this test if needed, but it seemed like an important
1123    // part of the best-case performance changes in PR#9903.
1124    #[test]
1125    fn entity_hash_keeps_similar_ids_together() {
1126        use std::hash::BuildHasher;
1127        let hash = EntityHash;
1128
1129        let first_id = 0xC0FFEE << 8;
1130        let first_hash = hash.hash_one(Entity::from_raw(first_id));
1131
1132        for i in 1..=255 {
1133            let id = first_id + i;
1134            let hash = hash.hash_one(Entity::from_raw(id));
1135            assert_eq!(hash.wrapping_sub(first_hash) as u32, i);
1136        }
1137    }
1138
1139    #[test]
1140    fn entity_hash_id_bitflip_affects_high_7_bits() {
1141        use std::hash::BuildHasher;
1142
1143        let hash = EntityHash;
1144
1145        let first_id = 0xC0FFEE;
1146        let first_hash = hash.hash_one(Entity::from_raw(first_id)) >> 57;
1147
1148        for bit in 0..u32::BITS {
1149            let id = first_id ^ (1 << bit);
1150            let hash = hash.hash_one(Entity::from_raw(id)) >> 57;
1151            assert_ne!(hash, first_hash);
1152        }
1153    }
1154
1155    #[test]
1156    fn entity_display() {
1157        let entity = Entity::from_raw(42);
1158        let string = format!("{}", entity);
1159        assert!(string.contains("42"));
1160        assert!(string.contains("v1"));
1161    }
1162}