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
38
39mod clone_entities;
40mod entity_set;
41mod map_entities;
42#[cfg(feature = "bevy_reflect")]
43use bevy_reflect::Reflect;
44#[cfg(all(feature = "bevy_reflect", feature = "serialize"))]
45use bevy_reflect::{ReflectDeserialize, ReflectSerialize};
46
47pub use clone_entities::*;
48use derive_more::derive::Display;
49pub use entity_set::*;
50pub use map_entities::*;
51
52mod hash;
53pub use hash::*;
54
55pub mod hash_map;
56pub mod hash_set;
57
58pub use hash_map::EntityHashMap;
59pub use hash_set::EntityHashSet;
60
61pub mod index_map;
62pub mod index_set;
63
64pub use index_map::EntityIndexMap;
65pub use index_set::EntityIndexSet;
66
67pub mod unique_array;
68pub mod unique_slice;
69pub mod unique_vec;
70
71use nonmax::NonMaxU32;
72pub use unique_array::{UniqueEntityArray, UniqueEntityEquivalentArray};
73pub use unique_slice::{UniqueEntityEquivalentSlice, UniqueEntitySlice};
74pub use unique_vec::{UniqueEntityEquivalentVec, UniqueEntityVec};
75
76use crate::{
77    archetype::{ArchetypeId, ArchetypeRow},
78    change_detection::MaybeLocation,
79    component::{CheckChangeTicks, Tick},
80    storage::{SparseSetIndex, TableId, TableRow},
81};
82use alloc::vec::Vec;
83use bevy_platform::sync::atomic::Ordering;
84use core::{fmt, hash::Hash, mem, num::NonZero, panic::Location};
85use log::warn;
86
87#[cfg(feature = "serialize")]
88use serde::{Deserialize, Serialize};
89
90#[cfg(target_has_atomic = "64")]
91use bevy_platform::sync::atomic::AtomicI64 as AtomicIdCursor;
92#[cfg(target_has_atomic = "64")]
93type IdCursor = i64;
94
95/// Most modern platforms support 64-bit atomics, but some less-common platforms
96/// do not. This fallback allows compilation using a 32-bit cursor instead, with
97/// the caveat that some conversions may fail (and panic) at runtime.
98#[cfg(not(target_has_atomic = "64"))]
99use bevy_platform::sync::atomic::AtomicIsize as AtomicIdCursor;
100#[cfg(not(target_has_atomic = "64"))]
101type IdCursor = isize;
102
103/// This represents the row or "index" of an [`Entity`] within the [`Entities`] table.
104/// This is a lighter weight version of [`Entity`].
105///
106/// This is a unique identifier for an entity in the world.
107/// This differs from [`Entity`] in that [`Entity`] is unique for all entities total (unless the [`Entity::generation`] wraps),
108/// but this is only unique for entities that are active.
109///
110/// This can be used over [`Entity`] to improve performance in some cases,
111/// but improper use can cause this to identify a different entity than intended.
112/// Use with caution.
113#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Display)]
114#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
115#[cfg_attr(feature = "bevy_reflect", reflect(opaque))]
116#[cfg_attr(feature = "bevy_reflect", reflect(Hash, PartialEq, Debug, Clone))]
117#[repr(transparent)]
118pub struct EntityRow(NonMaxU32);
119
120impl EntityRow {
121    const PLACEHOLDER: Self = Self(NonMaxU32::MAX);
122
123    /// Constructs a new [`EntityRow`] from its index.
124    pub const fn new(index: NonMaxU32) -> Self {
125        Self(index)
126    }
127
128    /// Equivalent to [`new`](Self::new) except that it takes a `u32` instead of a `NonMaxU32`.
129    ///
130    /// Returns `None` if the index is `u32::MAX`.
131    pub const fn from_raw_u32(index: u32) -> Option<Self> {
132        match NonMaxU32::new(index) {
133            Some(index) => Some(Self(index)),
134            None => None,
135        }
136    }
137
138    /// Gets the index of the entity.
139    #[inline(always)]
140    pub const fn index(self) -> u32 {
141        self.0.get()
142    }
143
144    /// Gets some bits that represent this value.
145    /// The bits are opaque and should not be regarded as meaningful.
146    #[inline(always)]
147    const fn to_bits(self) -> u32 {
148        // SAFETY: NonMax is repr transparent.
149        unsafe { mem::transmute::<NonMaxU32, u32>(self.0) }
150    }
151
152    /// Reconstruct an [`EntityRow`] previously destructured with [`EntityRow::to_bits`].
153    ///
154    /// Only useful when applied to results from `to_bits` in the same instance of an application.
155    ///
156    /// # Panics
157    ///
158    /// This method will likely panic if given `u32` values that did not come from [`EntityRow::to_bits`].
159    #[inline]
160    const fn from_bits(bits: u32) -> Self {
161        Self::try_from_bits(bits).expect("Attempted to initialize invalid bits as an entity row")
162    }
163
164    /// Reconstruct an [`EntityRow`] previously destructured with [`EntityRow::to_bits`].
165    ///
166    /// Only useful when applied to results from `to_bits` in the same instance of an application.
167    ///
168    /// This method is the fallible counterpart to [`EntityRow::from_bits`].
169    #[inline(always)]
170    const fn try_from_bits(bits: u32) -> Option<Self> {
171        match NonZero::<u32>::new(bits) {
172            // SAFETY: NonMax and NonZero are repr transparent.
173            Some(underlying) => Some(Self(unsafe {
174                mem::transmute::<NonZero<u32>, NonMaxU32>(underlying)
175            })),
176            None => None,
177        }
178    }
179}
180
181impl SparseSetIndex for EntityRow {
182    #[inline]
183    fn sparse_set_index(&self) -> usize {
184        self.index() as usize
185    }
186
187    #[inline]
188    fn get_sparse_set_index(value: usize) -> Self {
189        Self::from_bits(value as u32)
190    }
191}
192
193/// This tracks different versions or generations of an [`EntityRow`].
194/// Importantly, this can wrap, meaning each generation is not necessarily unique per [`EntityRow`].
195///
196/// This should be treated as a opaque identifier, and its internal representation may be subject to change.
197///
198/// # Aliasing
199///
200/// Internally [`EntityGeneration`] wraps a `u32`, so it can't represent *every* possible generation.
201/// Eventually, generations can (and do) wrap or alias.
202/// This can cause [`Entity`] and [`EntityGeneration`] values to be equal while still referring to different conceptual entities.
203/// This can cause some surprising behavior:
204///
205/// ```
206/// # use bevy_ecs::entity::EntityGeneration;
207/// let (aliased, did_alias) = EntityGeneration::FIRST.after_versions(1u32 << 31).after_versions_and_could_alias(1u32 << 31);
208/// assert!(did_alias);
209/// assert!(EntityGeneration::FIRST == aliased);
210/// ```
211///
212/// This can cause some unintended side effects.
213/// See [`Entity`] docs for practical concerns and how to minimize any risks.
214#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Display)]
215#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
216#[cfg_attr(feature = "bevy_reflect", reflect(opaque))]
217#[cfg_attr(feature = "bevy_reflect", reflect(Hash, PartialEq, Debug, Clone))]
218#[repr(transparent)]
219pub struct EntityGeneration(u32);
220
221impl EntityGeneration {
222    /// Represents the first generation of an [`EntityRow`].
223    pub const FIRST: Self = Self(0);
224
225    /// Non-wrapping difference between two generations after which a signed interpretation becomes negative.
226    const DIFF_MAX: u32 = 1u32 << 31;
227
228    /// Gets some bits that represent this value.
229    /// The bits are opaque and should not be regarded as meaningful.
230    #[inline(always)]
231    pub const fn to_bits(self) -> u32 {
232        self.0
233    }
234
235    /// Reconstruct an [`EntityGeneration`] previously destructured with [`EntityGeneration::to_bits`].
236    ///
237    /// Only useful when applied to results from `to_bits` in the same instance of an application.
238    #[inline]
239    pub const fn from_bits(bits: u32) -> Self {
240        Self(bits)
241    }
242
243    /// Returns the [`EntityGeneration`] that would result from this many more `versions` of the corresponding [`EntityRow`] from passing.
244    #[inline]
245    pub const fn after_versions(self, versions: u32) -> Self {
246        Self(self.0.wrapping_add(versions))
247    }
248
249    /// Identical to [`after_versions`](Self::after_versions) but also returns a `bool` indicating if,
250    /// after these `versions`, one such version could conflict with a previous one.
251    ///
252    /// If this happens, this will no longer uniquely identify a version of an [`EntityRow`].
253    /// This is called entity aliasing.
254    #[inline]
255    pub const fn after_versions_and_could_alias(self, versions: u32) -> (Self, bool) {
256        let raw = self.0.overflowing_add(versions);
257        (Self(raw.0), raw.1)
258    }
259
260    /// Compares two generations.
261    ///
262    /// Generations that are later will be [`Greater`](core::cmp::Ordering::Greater) than earlier ones.
263    ///
264    /// ```
265    /// # use bevy_ecs::entity::EntityGeneration;
266    /// # use core::cmp::Ordering;
267    /// let later_generation = EntityGeneration::FIRST.after_versions(400);
268    /// assert_eq!(EntityGeneration::FIRST.cmp_approx(&later_generation), Ordering::Less);
269    ///
270    /// let (aliased, did_alias) = EntityGeneration::FIRST.after_versions(400).after_versions_and_could_alias(u32::MAX);
271    /// assert!(did_alias);
272    /// assert_eq!(EntityGeneration::FIRST.cmp_approx(&aliased), Ordering::Less);
273    /// ```
274    ///
275    /// Ordering will be incorrect and [non-transitive](https://en.wikipedia.org/wiki/Transitive_relation)
276    /// for distant generations:
277    ///
278    /// ```should_panic
279    /// # use bevy_ecs::entity::EntityGeneration;
280    /// # use core::cmp::Ordering;
281    /// let later_generation = EntityGeneration::FIRST.after_versions(3u32 << 31);
282    /// let much_later_generation = later_generation.after_versions(3u32 << 31);
283    ///
284    /// // while these orderings are correct and pass assertions...
285    /// assert_eq!(EntityGeneration::FIRST.cmp_approx(&later_generation), Ordering::Less);
286    /// assert_eq!(later_generation.cmp_approx(&much_later_generation), Ordering::Less);
287    ///
288    /// // ... this ordering is not and the assertion fails!
289    /// assert_eq!(EntityGeneration::FIRST.cmp_approx(&much_later_generation), Ordering::Less);
290    /// ```
291    ///
292    /// Because of this, `EntityGeneration` does not implement `Ord`/`PartialOrd`.
293    #[inline]
294    pub const fn cmp_approx(&self, other: &Self) -> core::cmp::Ordering {
295        use core::cmp::Ordering;
296        match self.0.wrapping_sub(other.0) {
297            0 => Ordering::Equal,
298            1..Self::DIFF_MAX => Ordering::Greater,
299            _ => Ordering::Less,
300        }
301    }
302}
303
304/// Lightweight identifier of an [entity](crate::entity).
305///
306/// The identifier is implemented using a [generational index]: a combination of an index ([`EntityRow`]) and a generation ([`EntityGeneration`]).
307/// This allows fast insertion after data removal in an array while minimizing loss of spatial locality.
308///
309/// These identifiers are only valid on the [`World`] it's sourced from. Attempting to use an `Entity` to
310/// fetch entity components or metadata from a different world will either fail or return unexpected results.
311///
312/// [generational index]: https://lucassardois.medium.com/generational-indices-guide-8e3c5f7fd594
313///
314/// # Aliasing
315///
316/// Once an entity is despawned, it ceases to exist.
317/// However, its [`Entity`] id is still present, and may still be contained in some data.
318/// This becomes problematic because it is possible for a later entity to be spawned at the exact same id!
319/// If this happens, which is rare but very possible, it will be logged.
320///
321/// Aliasing can happen without warning.
322/// Holding onto a [`Entity`] id corresponding to an entity well after that entity was despawned can cause un-intuitive behavior for both ordering, and comparing in general.
323/// To prevent these bugs, it is generally best practice to stop holding an [`Entity`] or [`EntityGeneration`] value as soon as you know it has been despawned.
324/// If you must do otherwise, do not assume the [`Entity`] corresponds to the same conceptual entity it originally did.
325/// See [`EntityGeneration`]'s docs for more information about aliasing and why it occurs.
326///
327/// # Stability warning
328/// For all intents and purposes, `Entity` should be treated as an opaque identifier. The internal bit
329/// representation is liable to change from release to release as are the behaviors or performance
330/// characteristics of any of its trait implementations (i.e. `Ord`, `Hash`, etc.). This means that changes in
331/// `Entity`'s representation, though made readable through various functions on the type, are not considered
332/// breaking changes under [SemVer].
333///
334/// In particular, directly serializing with `Serialize` and `Deserialize` make zero guarantee of long
335/// term wire format compatibility. Changes in behavior will cause serialized `Entity` values persisted
336/// to long term storage (i.e. disk, databases, etc.) will fail to deserialize upon being updated.
337///
338/// # Usage
339///
340/// This data type is returned by iterating a `Query` that has `Entity` as part of its query fetch type parameter ([learn more]).
341/// It can also be obtained by calling [`EntityCommands::id`] or [`EntityWorldMut::id`].
342///
343/// ```
344/// # use bevy_ecs::prelude::*;
345/// # #[derive(Component)]
346/// # struct SomeComponent;
347/// fn setup(mut commands: Commands) {
348///     // Calling `spawn` returns `EntityCommands`.
349///     let entity = commands.spawn(SomeComponent).id();
350/// }
351///
352/// fn exclusive_system(world: &mut World) {
353///     // Calling `spawn` returns `EntityWorldMut`.
354///     let entity = world.spawn(SomeComponent).id();
355/// }
356/// #
357/// # bevy_ecs::system::assert_is_system(setup);
358/// # bevy_ecs::system::assert_is_system(exclusive_system);
359/// ```
360///
361/// 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.
362///
363/// ```
364/// # use bevy_ecs::prelude::*;
365/// #
366/// # #[derive(Component)]
367/// # struct Expired;
368/// #
369/// fn dispose_expired_food(mut commands: Commands, query: Query<Entity, With<Expired>>) {
370///     for food_entity in &query {
371///         commands.entity(food_entity).despawn();
372///     }
373/// }
374/// #
375/// # bevy_ecs::system::assert_is_system(dispose_expired_food);
376/// ```
377///
378/// [learn more]: crate::system::Query#entity-id-access
379/// [`EntityCommands::id`]: crate::system::EntityCommands::id
380/// [`EntityWorldMut::id`]: crate::world::EntityWorldMut::id
381/// [`EntityCommands`]: crate::system::EntityCommands
382/// [`Query::get`]: crate::system::Query::get
383/// [`World`]: crate::world::World
384/// [SemVer]: https://semver.org/
385#[derive(Clone, Copy)]
386#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
387#[cfg_attr(feature = "bevy_reflect", reflect(opaque))]
388#[cfg_attr(feature = "bevy_reflect", reflect(Hash, PartialEq, Debug, Clone))]
389#[cfg_attr(
390    all(feature = "bevy_reflect", feature = "serialize"),
391    reflect(Serialize, Deserialize)
392)]
393// Alignment repr necessary to allow LLVM to better output
394// optimized codegen for `to_bits`, `PartialEq` and `Ord`.
395#[repr(C, align(8))]
396pub struct Entity {
397    // Do not reorder the fields here. The ordering is explicitly used by repr(C)
398    // to make this struct equivalent to a u64.
399    #[cfg(target_endian = "little")]
400    row: EntityRow,
401    generation: EntityGeneration,
402    #[cfg(target_endian = "big")]
403    row: EntityRow,
404}
405
406// By not short-circuiting in comparisons, we get better codegen.
407// See <https://github.com/rust-lang/rust/issues/117800>
408impl PartialEq for Entity {
409    #[inline]
410    fn eq(&self, other: &Entity) -> bool {
411        // By using `to_bits`, the codegen can be optimized out even
412        // further potentially. Relies on the correct alignment/field
413        // order of `Entity`.
414        self.to_bits() == other.to_bits()
415    }
416}
417
418impl Eq for Entity {}
419
420// The derive macro codegen output is not optimal and can't be optimized as well
421// by the compiler. This impl resolves the issue of non-optimal codegen by relying
422// on comparing against the bit representation of `Entity` instead of comparing
423// the fields. The result is then LLVM is able to optimize the codegen for Entity
424// far beyond what the derive macro can.
425// See <https://github.com/rust-lang/rust/issues/106107>
426impl PartialOrd for Entity {
427    #[inline]
428    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
429        // Make use of our `Ord` impl to ensure optimal codegen output
430        Some(self.cmp(other))
431    }
432}
433
434// The derive macro codegen output is not optimal and can't be optimized as well
435// by the compiler. This impl resolves the issue of non-optimal codegen by relying
436// on comparing against the bit representation of `Entity` instead of comparing
437// the fields. The result is then LLVM is able to optimize the codegen for Entity
438// far beyond what the derive macro can.
439// See <https://github.com/rust-lang/rust/issues/106107>
440impl Ord for Entity {
441    #[inline]
442    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
443        // This will result in better codegen for ordering comparisons, plus
444        // avoids pitfalls with regards to macro codegen relying on property
445        // position when we want to compare against the bit representation.
446        self.to_bits().cmp(&other.to_bits())
447    }
448}
449
450impl Hash for Entity {
451    #[inline]
452    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
453        self.to_bits().hash(state);
454    }
455}
456
457impl Entity {
458    /// Creates a new instance with the given index and generation.
459    #[inline(always)]
460    pub const fn from_row_and_generation(row: EntityRow, generation: EntityGeneration) -> Entity {
461        Self { row, generation }
462    }
463
464    /// An entity ID with a placeholder value. This may or may not correspond to an actual entity,
465    /// and should be overwritten by a new value before being used.
466    ///
467    /// ## Examples
468    ///
469    /// Initializing a collection (e.g. `array` or `Vec`) with a known size:
470    ///
471    /// ```no_run
472    /// # use bevy_ecs::prelude::*;
473    /// // Create a new array of size 10 filled with invalid entity ids.
474    /// let mut entities: [Entity; 10] = [Entity::PLACEHOLDER; 10];
475    ///
476    /// // ... replace the entities with valid ones.
477    /// ```
478    ///
479    /// Deriving [`Reflect`] for a component that has an `Entity` field:
480    ///
481    /// ```no_run
482    /// # use bevy_ecs::{prelude::*, component::*};
483    /// # use bevy_reflect::Reflect;
484    /// #[derive(Reflect, Component)]
485    /// #[reflect(Component)]
486    /// pub struct MyStruct {
487    ///     pub entity: Entity,
488    /// }
489    ///
490    /// impl FromWorld for MyStruct {
491    ///     fn from_world(_world: &mut World) -> Self {
492    ///         Self {
493    ///             entity: Entity::PLACEHOLDER,
494    ///         }
495    ///     }
496    /// }
497    /// ```
498    pub const PLACEHOLDER: Self = Self::from_row(EntityRow::PLACEHOLDER);
499
500    /// Creates a new entity ID with the specified `row` and a generation of 1.
501    ///
502    /// # Note
503    ///
504    /// Spawning a specific `entity` value is __rarely the right choice__. Most apps should favor
505    /// [`Commands::spawn`](crate::system::Commands::spawn). This method should generally
506    /// only be used for sharing entities across apps, and only when they have a scheme
507    /// worked out to share an index space (which doesn't happen by default).
508    ///
509    /// In general, one should not try to synchronize the ECS by attempting to ensure that
510    /// `Entity` lines up between instances, but instead insert a secondary identifier as
511    /// a component.
512    #[inline(always)]
513    pub const fn from_row(row: EntityRow) -> Entity {
514        Self::from_row_and_generation(row, EntityGeneration::FIRST)
515    }
516
517    /// This is equivalent to [`from_row`](Self::from_row) except that it takes a `u32` instead of an [`EntityRow`].
518    ///
519    /// Returns `None` if the row is `u32::MAX`.
520    #[inline(always)]
521    pub const fn from_raw_u32(row: u32) -> Option<Entity> {
522        match NonMaxU32::new(row) {
523            Some(row) => Some(Self::from_row(EntityRow::new(row))),
524            None => None,
525        }
526    }
527
528    /// Convert to a form convenient for passing outside of rust.
529    ///
530    /// Only useful for identifying entities within the same instance of an application. Do not use
531    /// for serialization between runs.
532    ///
533    /// No particular structure is guaranteed for the returned bits.
534    #[inline(always)]
535    pub const fn to_bits(self) -> u64 {
536        self.row.to_bits() as u64 | ((self.generation.to_bits() as u64) << 32)
537    }
538
539    /// Reconstruct an `Entity` previously destructured with [`Entity::to_bits`].
540    ///
541    /// Only useful when applied to results from `to_bits` in the same instance of an application.
542    ///
543    /// # Panics
544    ///
545    /// This method will likely panic if given `u64` values that did not come from [`Entity::to_bits`].
546    #[inline]
547    pub const fn from_bits(bits: u64) -> Self {
548        if let Some(id) = Self::try_from_bits(bits) {
549            id
550        } else {
551            panic!("Attempted to initialize invalid bits as an entity")
552        }
553    }
554
555    /// Reconstruct an `Entity` previously destructured with [`Entity::to_bits`].
556    ///
557    /// Only useful when applied to results from `to_bits` in the same instance of an application.
558    ///
559    /// This method is the fallible counterpart to [`Entity::from_bits`].
560    #[inline(always)]
561    pub const fn try_from_bits(bits: u64) -> Option<Self> {
562        let raw_row = bits as u32;
563        let raw_gen = (bits >> 32) as u32;
564
565        if let Some(row) = EntityRow::try_from_bits(raw_row) {
566            Some(Self {
567                row,
568                generation: EntityGeneration::from_bits(raw_gen),
569            })
570        } else {
571            None
572        }
573    }
574
575    /// Return a transiently unique identifier.
576    /// See also [`EntityRow`].
577    ///
578    /// No two simultaneously-live entities share the same row, but dead entities' indices may collide
579    /// with both live and dead entities. Useful for compactly representing entities within a
580    /// specific snapshot of the world, such as when serializing.
581    #[inline]
582    pub const fn row(self) -> EntityRow {
583        self.row
584    }
585
586    /// Equivalent to `self.row().index()`. See [`Self::row`] for details.
587    #[inline]
588    pub const fn index(self) -> u32 {
589        self.row.index()
590    }
591
592    /// Returns the generation of this Entity's row. The generation is incremented each time an
593    /// entity with a given row is despawned. This serves as a "count" of the number of times a
594    /// given row has been reused (row, generation) pairs uniquely identify a given Entity.
595    #[inline]
596    pub const fn generation(self) -> EntityGeneration {
597        self.generation
598    }
599}
600
601#[cfg(feature = "serialize")]
602impl Serialize for Entity {
603    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
604    where
605        S: serde::Serializer,
606    {
607        serializer.serialize_u64(self.to_bits())
608    }
609}
610
611#[cfg(feature = "serialize")]
612impl<'de> Deserialize<'de> for Entity {
613    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
614    where
615        D: serde::Deserializer<'de>,
616    {
617        use serde::de::Error;
618        let id: u64 = Deserialize::deserialize(deserializer)?;
619        Entity::try_from_bits(id)
620            .ok_or_else(|| D::Error::custom("Attempting to deserialize an invalid entity."))
621    }
622}
623
624/// Outputs the short entity identifier, including the index and generation.
625///
626/// This takes the format: `{index}v{generation}`.
627///
628/// For [`Entity::PLACEHOLDER`], this outputs `PLACEHOLDER`.
629///
630/// For a unique [`u64`] representation, use [`Entity::to_bits`].
631impl fmt::Debug for Entity {
632    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
633        fmt::Display::fmt(self, f)
634    }
635}
636
637/// Outputs the short entity identifier, including the index and generation.
638///
639/// This takes the format: `{index}v{generation}`.
640///
641/// For [`Entity::PLACEHOLDER`], this outputs `PLACEHOLDER`.
642impl fmt::Display for Entity {
643    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
644        if self == &Self::PLACEHOLDER {
645            write!(f, "PLACEHOLDER")
646        } else {
647            write!(f, "{}v{}", self.index(), self.generation())
648        }
649    }
650}
651
652impl SparseSetIndex for Entity {
653    #[inline]
654    fn sparse_set_index(&self) -> usize {
655        self.row().sparse_set_index()
656    }
657
658    #[inline]
659    fn get_sparse_set_index(value: usize) -> Self {
660        Entity::from_row(EntityRow::get_sparse_set_index(value))
661    }
662}
663
664/// An [`Iterator`] returning a sequence of [`Entity`] values from
665pub struct ReserveEntitiesIterator<'a> {
666    // Metas, so we can recover the current generation for anything in the freelist.
667    meta: &'a [EntityMeta],
668
669    // Reserved indices formerly in the freelist to hand out.
670    freelist_indices: core::slice::Iter<'a, EntityRow>,
671
672    // New Entity indices to hand out, outside the range of meta.len().
673    new_indices: core::ops::Range<u32>,
674}
675
676impl<'a> Iterator for ReserveEntitiesIterator<'a> {
677    type Item = Entity;
678
679    fn next(&mut self) -> Option<Self::Item> {
680        self.freelist_indices
681            .next()
682            .map(|&row| {
683                Entity::from_row_and_generation(row, self.meta[row.index() as usize].generation)
684            })
685            .or_else(|| {
686                self.new_indices.next().map(|index| {
687                    // SAFETY: This came from an exclusive range so the max can't be hit.
688                    let row = unsafe { EntityRow::new(NonMaxU32::new_unchecked(index)) };
689                    Entity::from_row(row)
690                })
691            })
692    }
693
694    fn size_hint(&self) -> (usize, Option<usize>) {
695        let len = self.freelist_indices.len() + self.new_indices.len();
696        (len, Some(len))
697    }
698}
699
700impl<'a> ExactSizeIterator for ReserveEntitiesIterator<'a> {}
701
702impl<'a> core::iter::FusedIterator for ReserveEntitiesIterator<'a> {}
703
704// SAFETY: Newly reserved entity values are unique.
705unsafe impl EntitySetIterator for ReserveEntitiesIterator<'_> {}
706
707/// A [`World`]'s internal metadata store on all of its entities.
708///
709/// Contains metadata on:
710///  - The generation of every entity.
711///  - The alive/dead status of a particular entity. (i.e. "has entity 3 been despawned?")
712///  - The location of the entity's components in memory (via [`EntityLocation`])
713///
714/// [`World`]: crate::world::World
715#[derive(Debug)]
716pub struct Entities {
717    meta: Vec<EntityMeta>,
718
719    /// The `pending` and `free_cursor` fields describe three sets of Entity IDs
720    /// that have been freed or are in the process of being allocated:
721    ///
722    /// - The `freelist` IDs, previously freed by `free()`. These IDs are available to any of
723    ///   [`alloc`], [`reserve_entity`] or [`reserve_entities`]. Allocation will always prefer
724    ///   these over brand new IDs.
725    ///
726    /// - The `reserved` list of IDs that were once in the freelist, but got reserved by
727    ///   [`reserve_entities`] or [`reserve_entity`]. They are now waiting for [`flush`] to make them
728    ///   fully allocated.
729    ///
730    /// - The count of new IDs that do not yet exist in `self.meta`, but which we have handed out
731    ///   and reserved. [`flush`] will allocate room for them in `self.meta`.
732    ///
733    /// The contents of `pending` look like this:
734    ///
735    /// ```txt
736    /// ----------------------------
737    /// |  freelist  |  reserved   |
738    /// ----------------------------
739    ///              ^             ^
740    ///          free_cursor   pending.len()
741    /// ```
742    ///
743    /// As IDs are allocated, `free_cursor` is atomically decremented, moving
744    /// items from the freelist into the reserved list by sliding over the boundary.
745    ///
746    /// Once the freelist runs out, `free_cursor` starts going negative.
747    /// The more negative it is, the more IDs have been reserved starting exactly at
748    /// the end of `meta.len()`.
749    ///
750    /// This formulation allows us to reserve any number of IDs first from the freelist
751    /// and then from the new IDs, using only a single atomic subtract.
752    ///
753    /// Once [`flush`] is done, `free_cursor` will equal `pending.len()`.
754    ///
755    /// [`alloc`]: Entities::alloc
756    /// [`reserve_entity`]: Entities::reserve_entity
757    /// [`reserve_entities`]: Entities::reserve_entities
758    /// [`flush`]: Entities::flush
759    pending: Vec<EntityRow>,
760    free_cursor: AtomicIdCursor,
761}
762
763impl Entities {
764    pub(crate) const fn new() -> Self {
765        Entities {
766            meta: Vec::new(),
767            pending: Vec::new(),
768            free_cursor: AtomicIdCursor::new(0),
769        }
770    }
771
772    /// Reserve entity IDs concurrently.
773    ///
774    /// Storage for entity generation and location is lazily allocated by calling [`flush`](Entities::flush).
775    #[expect(
776        clippy::allow_attributes,
777        reason = "`clippy::unnecessary_fallible_conversions` may not always lint."
778    )]
779    #[allow(
780        clippy::unnecessary_fallible_conversions,
781        reason = "`IdCursor::try_from` may fail on 32-bit platforms."
782    )]
783    pub fn reserve_entities(&self, count: u32) -> ReserveEntitiesIterator<'_> {
784        // Use one atomic subtract to grab a range of new IDs. The range might be
785        // entirely nonnegative, meaning all IDs come from the freelist, or entirely
786        // negative, meaning they are all new IDs to allocate, or a mix of both.
787        let range_end = self.free_cursor.fetch_sub(
788            IdCursor::try_from(count)
789                .expect("64-bit atomic operations are not supported on this platform."),
790            Ordering::Relaxed,
791        );
792        let range_start = range_end
793            - IdCursor::try_from(count)
794                .expect("64-bit atomic operations are not supported on this platform.");
795
796        let freelist_range = range_start.max(0) as usize..range_end.max(0) as usize;
797
798        let (new_id_start, new_id_end) = if range_start >= 0 {
799            // We satisfied all requests from the freelist.
800            (0, 0)
801        } else {
802            // We need to allocate some new Entity IDs outside of the range of self.meta.
803            //
804            // `range_start` covers some negative territory, e.g. `-3..6`.
805            // Since the nonnegative values `0..6` are handled by the freelist, that
806            // means we need to handle the negative range here.
807            //
808            // In this example, we truncate the end to 0, leaving us with `-3..0`.
809            // Then we negate these values to indicate how far beyond the end of `meta.end()`
810            // to go, yielding `meta.len()+0 .. meta.len()+3`.
811            let base = self.meta.len() as IdCursor;
812
813            let new_id_end = u32::try_from(base - range_start).expect("too many entities");
814
815            // `new_id_end` is in range, so no need to check `start`.
816            let new_id_start = (base - range_end.min(0)) as u32;
817
818            (new_id_start, new_id_end)
819        };
820
821        ReserveEntitiesIterator {
822            meta: &self.meta[..],
823            freelist_indices: self.pending[freelist_range].iter(),
824            new_indices: new_id_start..new_id_end,
825        }
826    }
827
828    /// Reserve one entity ID concurrently.
829    ///
830    /// Equivalent to `self.reserve_entities(1).next().unwrap()`, but more efficient.
831    pub fn reserve_entity(&self) -> Entity {
832        let n = self.free_cursor.fetch_sub(1, Ordering::Relaxed);
833        if n > 0 {
834            // Allocate from the freelist.
835            let row = self.pending[(n - 1) as usize];
836            Entity::from_row_and_generation(row, self.meta[row.index() as usize].generation)
837        } else {
838            // Grab a new ID, outside the range of `meta.len()`. `flush()` must
839            // eventually be called to make it valid.
840            //
841            // As `self.free_cursor` goes more and more negative, we return IDs farther
842            // and farther beyond `meta.len()`.
843            let raw = self.meta.len() as IdCursor - n;
844            if raw >= u32::MAX as IdCursor {
845                panic!("too many entities");
846            }
847            // SAFETY: We just checked the bounds
848            let row = unsafe { EntityRow::new(NonMaxU32::new_unchecked(raw as u32)) };
849            Entity::from_row(row)
850        }
851    }
852
853    /// Check that we do not have pending work requiring `flush()` to be called.
854    fn verify_flushed(&mut self) {
855        debug_assert!(
856            !self.needs_flush(),
857            "flush() needs to be called before this operation is legal"
858        );
859    }
860
861    /// Allocate an entity ID directly.
862    pub fn alloc(&mut self) -> Entity {
863        self.verify_flushed();
864        if let Some(row) = self.pending.pop() {
865            let new_free_cursor = self.pending.len() as IdCursor;
866            *self.free_cursor.get_mut() = new_free_cursor;
867            Entity::from_row_and_generation(row, self.meta[row.index() as usize].generation)
868        } else {
869            let index = u32::try_from(self.meta.len())
870                .ok()
871                .and_then(NonMaxU32::new)
872                .expect("too many entities");
873            self.meta.push(EntityMeta::EMPTY);
874            Entity::from_row(EntityRow::new(index))
875        }
876    }
877
878    /// Destroy an entity, allowing it to be reused.
879    ///
880    /// Returns the `Option<EntityLocation>` of the entity or `None` if the `entity` was not present.
881    ///
882    /// Must not be called while reserved entities are awaiting `flush()`.
883    pub fn free(&mut self, entity: Entity) -> Option<EntityIdLocation> {
884        self.verify_flushed();
885
886        let meta = &mut self.meta[entity.index() as usize];
887        if meta.generation != entity.generation {
888            return None;
889        }
890
891        let (new_generation, aliased) = meta.generation.after_versions_and_could_alias(1);
892        meta.generation = new_generation;
893        if aliased {
894            warn!(
895                "Entity({}) generation wrapped on Entities::free, aliasing may occur",
896                entity.row()
897            );
898        }
899
900        let loc = mem::replace(&mut meta.location, EntityMeta::EMPTY.location);
901
902        self.pending.push(entity.row());
903
904        let new_free_cursor = self.pending.len() as IdCursor;
905        *self.free_cursor.get_mut() = new_free_cursor;
906        Some(loc)
907    }
908
909    /// Ensure at least `n` allocations can succeed without reallocating.
910    #[expect(
911        clippy::allow_attributes,
912        reason = "`clippy::unnecessary_fallible_conversions` may not always lint."
913    )]
914    #[allow(
915        clippy::unnecessary_fallible_conversions,
916        reason = "`IdCursor::try_from` may fail on 32-bit platforms."
917    )]
918    pub fn reserve(&mut self, additional: u32) {
919        self.verify_flushed();
920
921        let freelist_size = *self.free_cursor.get_mut();
922        let shortfall = IdCursor::try_from(additional)
923            .expect("64-bit atomic operations are not supported on this platform.")
924            - freelist_size;
925        if shortfall > 0 {
926            self.meta.reserve(shortfall as usize);
927        }
928    }
929
930    /// Returns true if the [`Entities`] contains [`entity`](Entity).
931    // This will return false for entities which have been freed, even if
932    // not reallocated since the generation is incremented in `free`
933    pub fn contains(&self, entity: Entity) -> bool {
934        self.resolve_from_id(entity.row())
935            .is_some_and(|e| e.generation() == entity.generation())
936    }
937
938    /// Clears all [`Entity`] from the World.
939    pub fn clear(&mut self) {
940        self.meta.clear();
941        self.pending.clear();
942        *self.free_cursor.get_mut() = 0;
943    }
944
945    /// Returns the [`EntityLocation`] of an [`Entity`].
946    /// Note: for pending entities and entities not participating in the ECS (entities with a [`EntityIdLocation`] of `None`), returns `None`.
947    #[inline]
948    pub fn get(&self, entity: Entity) -> Option<EntityLocation> {
949        self.get_id_location(entity).flatten()
950    }
951
952    /// Returns the [`EntityIdLocation`] of an [`Entity`].
953    /// Note: for pending entities, returns `None`.
954    #[inline]
955    pub fn get_id_location(&self, entity: Entity) -> Option<EntityIdLocation> {
956        self.meta
957            .get(entity.index() as usize)
958            .filter(|meta| meta.generation == entity.generation)
959            .map(|meta| meta.location)
960    }
961
962    /// Updates the location of an [`Entity`].
963    /// This must be called when moving the components of the existing entity around in storage.
964    ///
965    /// # Safety
966    ///  - `index` must be a valid entity index.
967    ///  - `location` must be valid for the entity at `index` or immediately made valid afterwards
968    ///    before handing control to unknown code.
969    #[inline]
970    pub(crate) unsafe fn set(&mut self, index: u32, location: EntityIdLocation) {
971        // SAFETY: Caller guarantees that `index` a valid entity index
972        let meta = unsafe { self.meta.get_unchecked_mut(index as usize) };
973        meta.location = location;
974    }
975
976    /// Mark an [`Entity`] as spawned or despawned in the given tick.
977    ///
978    /// # Safety
979    ///  - `index` must be a valid entity index.
980    #[inline]
981    pub(crate) unsafe fn mark_spawn_despawn(&mut self, index: u32, by: MaybeLocation, tick: Tick) {
982        // SAFETY: Caller guarantees that `index` a valid entity index
983        let meta = unsafe { self.meta.get_unchecked_mut(index as usize) };
984        meta.spawned_or_despawned = SpawnedOrDespawned { by, tick };
985    }
986
987    /// Increments the `generation` of a freed [`Entity`]. The next entity ID allocated with this
988    /// `index` will count `generation` starting from the prior `generation` + the specified
989    /// value + 1.
990    ///
991    /// Does nothing if no entity with this `index` has been allocated yet.
992    pub(crate) fn reserve_generations(&mut self, index: u32, generations: u32) -> bool {
993        if (index as usize) >= self.meta.len() {
994            return false;
995        }
996
997        let meta = &mut self.meta[index as usize];
998        if meta.location.is_none() {
999            meta.generation = meta.generation.after_versions(generations);
1000            true
1001        } else {
1002            false
1003        }
1004    }
1005
1006    /// Get the [`Entity`] with a given id, if it exists in this [`Entities`] collection
1007    /// Returns `None` if this [`Entity`] is outside of the range of currently reserved Entities
1008    ///
1009    /// Note: This method may return [`Entities`](Entity) which are currently free
1010    /// Note that [`contains`](Entities::contains) will correctly return false for freed
1011    /// entities, since it checks the generation
1012    pub fn resolve_from_id(&self, row: EntityRow) -> Option<Entity> {
1013        let idu = row.index() as usize;
1014        if let Some(&EntityMeta { generation, .. }) = self.meta.get(idu) {
1015            Some(Entity::from_row_and_generation(row, generation))
1016        } else {
1017            // `id` is outside of the meta list - check whether it is reserved but not yet flushed.
1018            let free_cursor = self.free_cursor.load(Ordering::Relaxed);
1019            // If this entity was manually created, then free_cursor might be positive
1020            // Returning None handles that case correctly
1021            let num_pending = usize::try_from(-free_cursor).ok()?;
1022            (idu < self.meta.len() + num_pending).then_some(Entity::from_row(row))
1023        }
1024    }
1025
1026    fn needs_flush(&mut self) -> bool {
1027        *self.free_cursor.get_mut() != self.pending.len() as IdCursor
1028    }
1029
1030    /// Allocates space for entities previously reserved with [`reserve_entity`](Entities::reserve_entity) or
1031    /// [`reserve_entities`](Entities::reserve_entities), then initializes each one using the supplied function.
1032    ///
1033    /// See [`EntityLocation`] for details on its meaning and how to set it.
1034    ///
1035    /// # Safety
1036    /// Flush _must_ set the entity location to the correct [`ArchetypeId`] for the given [`Entity`]
1037    /// each time init is called. This _can_ be [`ArchetypeId::INVALID`], provided the [`Entity`]
1038    /// has not been assigned to an [`Archetype`][crate::archetype::Archetype].
1039    ///
1040    /// Note: freshly-allocated entities (ones which don't come from the pending list) are guaranteed
1041    /// to be initialized with the invalid archetype.
1042    pub unsafe fn flush(
1043        &mut self,
1044        mut init: impl FnMut(Entity, &mut EntityIdLocation),
1045        by: MaybeLocation,
1046        tick: Tick,
1047    ) {
1048        let free_cursor = self.free_cursor.get_mut();
1049        let current_free_cursor = *free_cursor;
1050
1051        let new_free_cursor = if current_free_cursor >= 0 {
1052            current_free_cursor as usize
1053        } else {
1054            let old_meta_len = self.meta.len();
1055            let new_meta_len = old_meta_len + -current_free_cursor as usize;
1056            self.meta.resize(new_meta_len, EntityMeta::EMPTY);
1057            for (index, meta) in self.meta.iter_mut().enumerate().skip(old_meta_len) {
1058                // SAFETY: the index is less than the meta length, which can not exceeded u32::MAX
1059                let row = EntityRow::new(unsafe { NonMaxU32::new_unchecked(index as u32) });
1060                init(
1061                    Entity::from_row_and_generation(row, meta.generation),
1062                    &mut meta.location,
1063                );
1064                meta.spawned_or_despawned = SpawnedOrDespawned { by, tick };
1065            }
1066
1067            *free_cursor = 0;
1068            0
1069        };
1070
1071        for row in self.pending.drain(new_free_cursor..) {
1072            let meta = &mut self.meta[row.index() as usize];
1073            init(
1074                Entity::from_row_and_generation(row, meta.generation),
1075                &mut meta.location,
1076            );
1077            meta.spawned_or_despawned = SpawnedOrDespawned { by, tick };
1078        }
1079    }
1080
1081    /// Flushes all reserved entities to an "invalid" state. Attempting to retrieve them will return `None`
1082    /// unless they are later populated with a valid archetype.
1083    pub fn flush_as_invalid(&mut self, by: MaybeLocation, tick: Tick) {
1084        // SAFETY: as per `flush` safety docs, the archetype id can be set to [`ArchetypeId::INVALID`] if
1085        // the [`Entity`] has not been assigned to an [`Archetype`][crate::archetype::Archetype], which is the case here
1086        unsafe {
1087            self.flush(
1088                |_entity, location| {
1089                    *location = None;
1090                },
1091                by,
1092                tick,
1093            );
1094        }
1095    }
1096
1097    /// The count of all entities in the [`World`] that have ever been allocated
1098    /// including the entities that are currently freed.
1099    ///
1100    /// This does not include entities that have been reserved but have never been
1101    /// allocated yet.
1102    ///
1103    /// [`World`]: crate::world::World
1104    #[inline]
1105    pub fn total_count(&self) -> usize {
1106        self.meta.len()
1107    }
1108
1109    /// The count of all entities in the [`World`] that are used,
1110    /// including both those allocated and those reserved, but not those freed.
1111    ///
1112    /// [`World`]: crate::world::World
1113    #[inline]
1114    pub fn used_count(&self) -> usize {
1115        (self.meta.len() as isize - self.free_cursor.load(Ordering::Relaxed) as isize) as usize
1116    }
1117
1118    /// The count of all entities in the [`World`] that have ever been allocated or reserved, including those that are freed.
1119    /// This is the value that [`Self::total_count()`] would return if [`Self::flush()`] were called right now.
1120    ///
1121    /// [`World`]: crate::world::World
1122    #[inline]
1123    pub fn total_prospective_count(&self) -> usize {
1124        self.meta.len() + (-self.free_cursor.load(Ordering::Relaxed)).min(0) as usize
1125    }
1126
1127    /// The count of currently allocated entities.
1128    #[inline]
1129    pub fn len(&self) -> u32 {
1130        // `pending`, by definition, can't be bigger than `meta`.
1131        (self.meta.len() - self.pending.len()) as u32
1132    }
1133
1134    /// Checks if any entity is currently active.
1135    #[inline]
1136    pub fn is_empty(&self) -> bool {
1137        self.len() == 0
1138    }
1139
1140    /// Try to get the source code location from which this entity has last been
1141    /// spawned, despawned or flushed.
1142    ///
1143    /// Returns `None` if its index has been reused by another entity
1144    /// or if this entity has never existed.
1145    pub fn entity_get_spawned_or_despawned_by(
1146        &self,
1147        entity: Entity,
1148    ) -> MaybeLocation<Option<&'static Location<'static>>> {
1149        MaybeLocation::new_with_flattened(|| {
1150            self.entity_get_spawned_or_despawned(entity)
1151                .map(|spawned_or_despawned| spawned_or_despawned.by)
1152        })
1153    }
1154
1155    /// Try to get the [`Tick`] at which this entity has last been
1156    /// spawned, despawned or flushed.
1157    ///
1158    /// Returns `None` if its index has been reused by another entity or if this entity
1159    /// has never been spawned.
1160    pub fn entity_get_spawn_or_despawn_tick(&self, entity: Entity) -> Option<Tick> {
1161        self.entity_get_spawned_or_despawned(entity)
1162            .map(|spawned_or_despawned| spawned_or_despawned.tick)
1163    }
1164
1165    /// Try to get the [`SpawnedOrDespawned`] related to the entity's last spawn,
1166    /// despawn or flush.
1167    ///
1168    /// Returns `None` if its index has been reused by another entity or if
1169    /// this entity has never been spawned.
1170    #[inline]
1171    fn entity_get_spawned_or_despawned(&self, entity: Entity) -> Option<SpawnedOrDespawned> {
1172        self.meta
1173            .get(entity.index() as usize)
1174            .filter(|meta|
1175            // Generation is incremented immediately upon despawn
1176            (meta.generation == entity.generation)
1177            || meta.location.is_none()
1178            && (meta.generation == entity.generation.after_versions(1)))
1179            .map(|meta| meta.spawned_or_despawned)
1180    }
1181
1182    /// Returns the source code location from which this entity has last been spawned
1183    /// or despawned and the Tick of when that happened.
1184    ///
1185    /// # Safety
1186    ///
1187    /// The entity index must belong to an entity that is currently alive or, if it
1188    /// despawned, was not overwritten by a new entity of the same index.
1189    #[inline]
1190    pub(crate) unsafe fn entity_get_spawned_or_despawned_unchecked(
1191        &self,
1192        entity: Entity,
1193    ) -> (MaybeLocation, Tick) {
1194        // SAFETY: caller ensures entity is allocated
1195        let meta = unsafe { self.meta.get_unchecked(entity.index() as usize) };
1196        (meta.spawned_or_despawned.by, meta.spawned_or_despawned.tick)
1197    }
1198
1199    #[inline]
1200    pub(crate) fn check_change_ticks(&mut self, check: CheckChangeTicks) {
1201        for meta in &mut self.meta {
1202            meta.spawned_or_despawned.tick.check_tick(check);
1203        }
1204    }
1205
1206    /// Constructs a message explaining why an entity does not exist, if known.
1207    pub(crate) fn entity_does_not_exist_error_details(
1208        &self,
1209        entity: Entity,
1210    ) -> EntityDoesNotExistDetails {
1211        EntityDoesNotExistDetails {
1212            location: self.entity_get_spawned_or_despawned_by(entity),
1213        }
1214    }
1215}
1216
1217/// An error that occurs when a specified [`Entity`] does not exist.
1218#[derive(thiserror::Error, Debug, Clone, Copy, PartialEq, Eq)]
1219#[error("The entity with ID {entity} {details}")]
1220pub struct EntityDoesNotExistError {
1221    /// The entity's ID.
1222    pub entity: Entity,
1223    /// Details on why the entity does not exist, if available.
1224    pub details: EntityDoesNotExistDetails,
1225}
1226
1227impl EntityDoesNotExistError {
1228    pub(crate) fn new(entity: Entity, entities: &Entities) -> Self {
1229        Self {
1230            entity,
1231            details: entities.entity_does_not_exist_error_details(entity),
1232        }
1233    }
1234}
1235
1236/// Helper struct that, when printed, will write the appropriate details
1237/// regarding an entity that did not exist.
1238#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
1239pub struct EntityDoesNotExistDetails {
1240    location: MaybeLocation<Option<&'static Location<'static>>>,
1241}
1242
1243impl fmt::Display for EntityDoesNotExistDetails {
1244    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1245        match self.location.into_option() {
1246            Some(Some(location)) => write!(f, "was despawned by {location}"),
1247            Some(None) => write!(
1248                f,
1249                "does not exist (index has been reused or was never spawned)"
1250            ),
1251            None => write!(
1252                f,
1253                "does not exist (enable `track_location` feature for more details)"
1254            ),
1255        }
1256    }
1257}
1258
1259#[derive(Copy, Clone, Debug)]
1260struct EntityMeta {
1261    /// The current [`EntityGeneration`] of the [`EntityRow`].
1262    generation: EntityGeneration,
1263    /// The current location of the [`EntityRow`].
1264    location: EntityIdLocation,
1265    /// Location and tick of the last spawn, despawn or flush of this entity.
1266    spawned_or_despawned: SpawnedOrDespawned,
1267}
1268
1269#[derive(Copy, Clone, Debug)]
1270struct SpawnedOrDespawned {
1271    by: MaybeLocation,
1272    tick: Tick,
1273}
1274
1275impl EntityMeta {
1276    /// meta for **pending entity**
1277    const EMPTY: EntityMeta = EntityMeta {
1278        generation: EntityGeneration::FIRST,
1279        location: None,
1280        spawned_or_despawned: SpawnedOrDespawned {
1281            by: MaybeLocation::caller(),
1282            tick: Tick::new(0),
1283        },
1284    };
1285}
1286
1287/// A location of an entity in an archetype.
1288#[derive(Copy, Clone, Debug, PartialEq)]
1289pub struct EntityLocation {
1290    /// The ID of the [`Archetype`] the [`Entity`] belongs to.
1291    ///
1292    /// [`Archetype`]: crate::archetype::Archetype
1293    pub archetype_id: ArchetypeId,
1294
1295    /// The index of the [`Entity`] within its [`Archetype`].
1296    ///
1297    /// [`Archetype`]: crate::archetype::Archetype
1298    pub archetype_row: ArchetypeRow,
1299
1300    /// The ID of the [`Table`] the [`Entity`] belongs to.
1301    ///
1302    /// [`Table`]: crate::storage::Table
1303    pub table_id: TableId,
1304
1305    /// The index of the [`Entity`] within its [`Table`].
1306    ///
1307    /// [`Table`]: crate::storage::Table
1308    pub table_row: TableRow,
1309}
1310
1311/// An [`Entity`] id may or may not correspond to a valid conceptual entity.
1312/// If it does, the conceptual entity may or may not have a location.
1313/// If it has no location, the [`EntityLocation`] will be `None`.
1314/// An location of `None` means the entity effectively does not exist; it has an id, but is not participating in the ECS.
1315/// This is different from a location in the empty archetype, which is participating (queryable, etc) but just happens to have no components.
1316///
1317/// Setting a location to `None` is often helpful when you want to destruct an entity or yank it from the ECS without allowing another system to reuse the id for something else.
1318/// It is also useful for reserving an id; commands will often allocate an `Entity` but not provide it a location until the command is applied.
1319pub type EntityIdLocation = Option<EntityLocation>;
1320
1321#[cfg(test)]
1322mod tests {
1323    use super::*;
1324    use alloc::format;
1325
1326    #[test]
1327    fn entity_niche_optimization() {
1328        assert_eq!(size_of::<Entity>(), size_of::<Option<Entity>>());
1329    }
1330
1331    #[test]
1332    fn entity_bits_roundtrip() {
1333        let r = EntityRow::from_raw_u32(0xDEADBEEF).unwrap();
1334        assert_eq!(EntityRow::from_bits(r.to_bits()), r);
1335
1336        let e = Entity::from_row_and_generation(
1337            EntityRow::from_raw_u32(0xDEADBEEF).unwrap(),
1338            EntityGeneration::from_bits(0x5AADF00D),
1339        );
1340        assert_eq!(Entity::from_bits(e.to_bits()), e);
1341    }
1342
1343    #[test]
1344    fn reserve_entity_len() {
1345        let mut e = Entities::new();
1346        e.reserve_entity();
1347        // SAFETY: entity_location is left invalid
1348        unsafe { e.flush(|_, _| {}, MaybeLocation::caller(), Tick::default()) };
1349        assert_eq!(e.len(), 1);
1350    }
1351
1352    #[test]
1353    fn get_reserved_and_invalid() {
1354        let mut entities = Entities::new();
1355        let e = entities.reserve_entity();
1356        assert!(entities.contains(e));
1357        assert!(entities.get(e).is_none());
1358
1359        // SAFETY: entity_location is left invalid
1360        unsafe {
1361            entities.flush(
1362                |_entity, _location| {
1363                    // do nothing ... leaving entity location invalid
1364                },
1365                MaybeLocation::caller(),
1366                Tick::default(),
1367            );
1368        };
1369
1370        assert!(entities.contains(e));
1371        assert!(entities.get(e).is_none());
1372    }
1373
1374    #[test]
1375    fn entity_const() {
1376        const C1: Entity = Entity::from_row(EntityRow::from_raw_u32(42).unwrap());
1377        assert_eq!(42, C1.index());
1378        assert_eq!(0, C1.generation().to_bits());
1379
1380        const C2: Entity = Entity::from_bits(0x0000_00ff_0000_00cc);
1381        assert_eq!(!0x0000_00cc, C2.index());
1382        assert_eq!(0x0000_00ff, C2.generation().to_bits());
1383
1384        const C3: u32 = Entity::from_row(EntityRow::from_raw_u32(33).unwrap()).index();
1385        assert_eq!(33, C3);
1386
1387        const C4: u32 = Entity::from_bits(0x00dd_00ff_1111_1111)
1388            .generation()
1389            .to_bits();
1390        assert_eq!(0x00dd_00ff, C4);
1391    }
1392
1393    #[test]
1394    fn reserve_generations() {
1395        let mut entities = Entities::new();
1396        let entity = entities.alloc();
1397        entities.free(entity);
1398
1399        assert!(entities.reserve_generations(entity.index(), 1));
1400    }
1401
1402    #[test]
1403    fn reserve_generations_and_alloc() {
1404        const GENERATIONS: u32 = 10;
1405
1406        let mut entities = Entities::new();
1407        let entity = entities.alloc();
1408        entities.free(entity);
1409
1410        assert!(entities.reserve_generations(entity.index(), GENERATIONS));
1411
1412        // The very next entity allocated should be a further generation on the same index
1413        let next_entity = entities.alloc();
1414        assert_eq!(next_entity.index(), entity.index());
1415        assert!(next_entity
1416            .generation()
1417            .cmp_approx(&entity.generation().after_versions(GENERATIONS))
1418            .is_gt());
1419    }
1420
1421    #[test]
1422    #[expect(
1423        clippy::nonminimal_bool,
1424        reason = "This intentionally tests all possible comparison operators as separate functions; thus, we don't want to rewrite these comparisons to use different operators."
1425    )]
1426    fn entity_comparison() {
1427        assert_eq!(
1428            Entity::from_row_and_generation(
1429                EntityRow::from_raw_u32(123).unwrap(),
1430                EntityGeneration::from_bits(456)
1431            ),
1432            Entity::from_row_and_generation(
1433                EntityRow::from_raw_u32(123).unwrap(),
1434                EntityGeneration::from_bits(456)
1435            )
1436        );
1437        assert_ne!(
1438            Entity::from_row_and_generation(
1439                EntityRow::from_raw_u32(123).unwrap(),
1440                EntityGeneration::from_bits(789)
1441            ),
1442            Entity::from_row_and_generation(
1443                EntityRow::from_raw_u32(123).unwrap(),
1444                EntityGeneration::from_bits(456)
1445            )
1446        );
1447        assert_ne!(
1448            Entity::from_row_and_generation(
1449                EntityRow::from_raw_u32(123).unwrap(),
1450                EntityGeneration::from_bits(456)
1451            ),
1452            Entity::from_row_and_generation(
1453                EntityRow::from_raw_u32(123).unwrap(),
1454                EntityGeneration::from_bits(789)
1455            )
1456        );
1457        assert_ne!(
1458            Entity::from_row_and_generation(
1459                EntityRow::from_raw_u32(123).unwrap(),
1460                EntityGeneration::from_bits(456)
1461            ),
1462            Entity::from_row_and_generation(
1463                EntityRow::from_raw_u32(456).unwrap(),
1464                EntityGeneration::from_bits(123)
1465            )
1466        );
1467
1468        // ordering is by generation then by index
1469
1470        assert!(
1471            Entity::from_row_and_generation(
1472                EntityRow::from_raw_u32(123).unwrap(),
1473                EntityGeneration::from_bits(456)
1474            ) >= Entity::from_row_and_generation(
1475                EntityRow::from_raw_u32(123).unwrap(),
1476                EntityGeneration::from_bits(456)
1477            )
1478        );
1479        assert!(
1480            Entity::from_row_and_generation(
1481                EntityRow::from_raw_u32(123).unwrap(),
1482                EntityGeneration::from_bits(456)
1483            ) <= Entity::from_row_and_generation(
1484                EntityRow::from_raw_u32(123).unwrap(),
1485                EntityGeneration::from_bits(456)
1486            )
1487        );
1488        assert!(
1489            !(Entity::from_row_and_generation(
1490                EntityRow::from_raw_u32(123).unwrap(),
1491                EntityGeneration::from_bits(456)
1492            ) < Entity::from_row_and_generation(
1493                EntityRow::from_raw_u32(123).unwrap(),
1494                EntityGeneration::from_bits(456)
1495            ))
1496        );
1497        assert!(
1498            !(Entity::from_row_and_generation(
1499                EntityRow::from_raw_u32(123).unwrap(),
1500                EntityGeneration::from_bits(456)
1501            ) > Entity::from_row_and_generation(
1502                EntityRow::from_raw_u32(123).unwrap(),
1503                EntityGeneration::from_bits(456)
1504            ))
1505        );
1506
1507        assert!(
1508            Entity::from_row_and_generation(
1509                EntityRow::from_raw_u32(9).unwrap(),
1510                EntityGeneration::from_bits(1)
1511            ) < Entity::from_row_and_generation(
1512                EntityRow::from_raw_u32(1).unwrap(),
1513                EntityGeneration::from_bits(9)
1514            )
1515        );
1516        assert!(
1517            Entity::from_row_and_generation(
1518                EntityRow::from_raw_u32(1).unwrap(),
1519                EntityGeneration::from_bits(9)
1520            ) > Entity::from_row_and_generation(
1521                EntityRow::from_raw_u32(9).unwrap(),
1522                EntityGeneration::from_bits(1)
1523            )
1524        );
1525
1526        assert!(
1527            Entity::from_row_and_generation(
1528                EntityRow::from_raw_u32(1).unwrap(),
1529                EntityGeneration::from_bits(1)
1530            ) > Entity::from_row_and_generation(
1531                EntityRow::from_raw_u32(2).unwrap(),
1532                EntityGeneration::from_bits(1)
1533            )
1534        );
1535        assert!(
1536            Entity::from_row_and_generation(
1537                EntityRow::from_raw_u32(1).unwrap(),
1538                EntityGeneration::from_bits(1)
1539            ) >= Entity::from_row_and_generation(
1540                EntityRow::from_raw_u32(2).unwrap(),
1541                EntityGeneration::from_bits(1)
1542            )
1543        );
1544        assert!(
1545            Entity::from_row_and_generation(
1546                EntityRow::from_raw_u32(2).unwrap(),
1547                EntityGeneration::from_bits(2)
1548            ) < Entity::from_row_and_generation(
1549                EntityRow::from_raw_u32(1).unwrap(),
1550                EntityGeneration::from_bits(2)
1551            )
1552        );
1553        assert!(
1554            Entity::from_row_and_generation(
1555                EntityRow::from_raw_u32(2).unwrap(),
1556                EntityGeneration::from_bits(2)
1557            ) <= Entity::from_row_and_generation(
1558                EntityRow::from_raw_u32(1).unwrap(),
1559                EntityGeneration::from_bits(2)
1560            )
1561        );
1562    }
1563
1564    // Feel free to change this test if needed, but it seemed like an important
1565    // part of the best-case performance changes in PR#9903.
1566    #[test]
1567    fn entity_hash_keeps_similar_ids_together() {
1568        use core::hash::BuildHasher;
1569        let hash = EntityHash;
1570
1571        let first_id = 0xC0FFEE << 8;
1572        let first_hash =
1573            hash.hash_one(Entity::from_row(EntityRow::from_raw_u32(first_id).unwrap()));
1574
1575        for i in 1..=255 {
1576            let id = first_id + i;
1577            let hash = hash.hash_one(Entity::from_row(EntityRow::from_raw_u32(id).unwrap()));
1578            assert_eq!(first_hash.wrapping_sub(hash) as u32, i);
1579        }
1580    }
1581
1582    #[test]
1583    fn entity_hash_id_bitflip_affects_high_7_bits() {
1584        use core::hash::BuildHasher;
1585
1586        let hash = EntityHash;
1587
1588        let first_id = 0xC0FFEE;
1589        let first_hash =
1590            hash.hash_one(Entity::from_row(EntityRow::from_raw_u32(first_id).unwrap())) >> 57;
1591
1592        for bit in 0..u32::BITS {
1593            let id = first_id ^ (1 << bit);
1594            let hash = hash.hash_one(Entity::from_row(EntityRow::from_raw_u32(id).unwrap())) >> 57;
1595            assert_ne!(hash, first_hash);
1596        }
1597    }
1598
1599    #[test]
1600    fn entity_generation_is_approximately_ordered() {
1601        use core::cmp::Ordering;
1602
1603        let old = EntityGeneration::FIRST;
1604        let middle = old.after_versions(1);
1605        let younger_before_ord_wrap = middle.after_versions(EntityGeneration::DIFF_MAX);
1606        let younger_after_ord_wrap = younger_before_ord_wrap.after_versions(1);
1607
1608        assert_eq!(middle.cmp_approx(&old), Ordering::Greater);
1609        assert_eq!(middle.cmp_approx(&middle), Ordering::Equal);
1610        assert_eq!(middle.cmp_approx(&younger_before_ord_wrap), Ordering::Less);
1611        assert_eq!(
1612            middle.cmp_approx(&younger_after_ord_wrap),
1613            Ordering::Greater
1614        );
1615    }
1616
1617    #[test]
1618    fn entity_debug() {
1619        let entity = Entity::from_row(EntityRow::from_raw_u32(42).unwrap());
1620        let string = format!("{entity:?}");
1621        assert_eq!(string, "42v0");
1622
1623        let entity = Entity::PLACEHOLDER;
1624        let string = format!("{entity:?}");
1625        assert_eq!(string, "PLACEHOLDER");
1626    }
1627
1628    #[test]
1629    fn entity_display() {
1630        let entity = Entity::from_row(EntityRow::from_raw_u32(42).unwrap());
1631        let string = format!("{entity}");
1632        assert_eq!(string, "42v0");
1633
1634        let entity = Entity::PLACEHOLDER;
1635        let string = format!("{entity}");
1636        assert_eq!(string, "PLACEHOLDER");
1637    }
1638}