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