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