bevy_ecs/archetype.rs
1//! Types for defining [`Archetype`]s, collections of entities that have the same set of
2//! components.
3//!
4//! An archetype uniquely describes a group of entities that share the same components:
5//! a world only has one archetype for each unique combination of components, and all
6//! entities that have those components and only those components belong to that
7//! archetype.
8//!
9//! Archetypes are not to be confused with [`Table`]s. Each archetype stores its table
10//! components in one table, and each archetype uniquely points to one table, but multiple
11//! archetypes may store their table components in the same table. These archetypes
12//! differ only by the [`SparseSet`] components.
13//!
14//! Like tables, archetypes can be created but are never cleaned up. Empty archetypes are
15//! not removed, and persist until the world is dropped.
16//!
17//! Archetypes can be fetched from [`Archetypes`], which is accessible via [`World::archetypes`].
18//!
19//! [`Table`]: crate::storage::Table
20//! [`World::archetypes`]: crate::world::World::archetypes
21
22use crate::{
23 bundle::BundleId,
24 component::{ComponentId, Components, StorageType},
25 entity::{Entity, EntityLocation},
26 observer::Observers,
27 storage::{ImmutableSparseSet, SparseArray, SparseSet, SparseSetIndex, TableId, TableRow},
28};
29use std::{
30 hash::Hash,
31 ops::{Index, IndexMut, RangeFrom},
32};
33
34/// An opaque location within a [`Archetype`].
35///
36/// This can be used in conjunction with [`ArchetypeId`] to find the exact location
37/// of an [`Entity`] within a [`World`]. An entity's archetype and index can be
38/// retrieved via [`Entities::get`].
39///
40/// [`World`]: crate::world::World
41/// [`Entities::get`]: crate::entity::Entities
42#[derive(Debug, Copy, Clone, Eq, PartialEq)]
43// SAFETY: Must be repr(transparent) due to the safety requirements on EntityLocation
44#[repr(transparent)]
45pub struct ArchetypeRow(u32);
46
47impl ArchetypeRow {
48 /// Index indicating an invalid archetype row.
49 /// This is meant to be used as a placeholder.
50 pub const INVALID: ArchetypeRow = ArchetypeRow(u32::MAX);
51
52 /// Creates a `ArchetypeRow`.
53 #[inline]
54 pub const fn new(index: usize) -> Self {
55 Self(index as u32)
56 }
57
58 /// Gets the index of the row.
59 #[inline]
60 pub const fn index(self) -> usize {
61 self.0 as usize
62 }
63}
64
65/// An opaque unique ID for a single [`Archetype`] within a [`World`].
66///
67/// Archetype IDs are only valid for a given World, and are not globally unique.
68/// Attempting to use an archetype ID on a world that it wasn't sourced from will
69/// not return the archetype with the same components. The only exception to this is
70/// [`EMPTY`] which is guaranteed to be identical for all Worlds.
71///
72/// [`World`]: crate::world::World
73/// [`EMPTY`]: ArchetypeId::EMPTY
74#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, PartialOrd, Ord)]
75// SAFETY: Must be repr(transparent) due to the safety requirements on EntityLocation
76#[repr(transparent)]
77pub struct ArchetypeId(u32);
78
79impl ArchetypeId {
80 /// The ID for the [`Archetype`] without any components.
81 pub const EMPTY: ArchetypeId = ArchetypeId(0);
82 /// # Safety:
83 ///
84 /// This must always have an all-1s bit pattern to ensure soundness in fast entity id space allocation.
85 pub const INVALID: ArchetypeId = ArchetypeId(u32::MAX);
86
87 /// Create an `ArchetypeId` from a plain value.
88 ///
89 /// This is useful if you need to store the `ArchetypeId` as a plain value,
90 /// for example in a specialized data structure such as a bitset.
91 ///
92 /// While it doesn't break any safety invariants, you should ensure the
93 /// values comes from a pre-existing [`ArchetypeId::index`] in this world
94 /// to avoid panics and other unexpected behaviors.
95 #[inline]
96 pub const fn new(index: usize) -> Self {
97 ArchetypeId(index as u32)
98 }
99
100 /// The plain value of this `ArchetypeId`.
101 ///
102 /// In bevy, this is mostly used to store archetype ids in [`FixedBitSet`]s.
103 ///
104 /// [`FixedBitSet`]: fixedbitset::FixedBitSet
105 #[inline]
106 pub fn index(self) -> usize {
107 self.0 as usize
108 }
109}
110
111#[derive(Copy, Clone, Eq, PartialEq)]
112pub(crate) enum ComponentStatus {
113 Added,
114 Mutated,
115}
116
117pub(crate) struct AddBundle {
118 /// The target archetype after the bundle is added to the source archetype
119 pub archetype_id: ArchetypeId,
120 /// For each component iterated in the same order as the source [`Bundle`](crate::bundle::Bundle),
121 /// indicate if the component is newly added to the target archetype or if it already existed
122 pub bundle_status: Vec<ComponentStatus>,
123 pub added: Vec<ComponentId>,
124}
125
126/// This trait is used to report the status of [`Bundle`](crate::bundle::Bundle) components
127/// being added to a given entity, relative to that entity's original archetype.
128/// See [`crate::bundle::BundleInfo::write_components`] for more info.
129pub(crate) trait BundleComponentStatus {
130 /// Returns the Bundle's component status for the given "bundle index"
131 ///
132 /// # Safety
133 /// Callers must ensure that index is always a valid bundle index for the
134 /// Bundle associated with this [`BundleComponentStatus`]
135 unsafe fn get_status(&self, index: usize) -> ComponentStatus;
136}
137
138impl BundleComponentStatus for AddBundle {
139 #[inline]
140 unsafe fn get_status(&self, index: usize) -> ComponentStatus {
141 // SAFETY: caller has ensured index is a valid bundle index for this bundle
142 unsafe { *self.bundle_status.get_unchecked(index) }
143 }
144}
145
146pub(crate) struct SpawnBundleStatus;
147
148impl BundleComponentStatus for SpawnBundleStatus {
149 #[inline]
150 unsafe fn get_status(&self, _index: usize) -> ComponentStatus {
151 // Components added during a spawn call are always treated as added
152 ComponentStatus::Added
153 }
154}
155
156/// Archetypes and bundles form a graph. Adding or removing a bundle moves
157/// an [`Entity`] to a new [`Archetype`].
158///
159/// [`Edges`] caches the results of these moves. Each archetype caches
160/// the result of a structural alteration. This can be used to monitor the
161/// state of the archetype graph.
162///
163/// Note: This type only contains edges the [`World`] has already traversed.
164/// If any of functions return `None`, it doesn't mean there is guaranteed
165/// not to be a result of adding or removing that bundle, but rather that
166/// operation that has moved an entity along that edge has not been performed
167/// yet.
168///
169/// [`World`]: crate::world::World
170#[derive(Default)]
171pub struct Edges {
172 add_bundle: SparseArray<BundleId, AddBundle>,
173 remove_bundle: SparseArray<BundleId, Option<ArchetypeId>>,
174 take_bundle: SparseArray<BundleId, Option<ArchetypeId>>,
175}
176
177impl Edges {
178 /// Checks the cache for the target archetype when adding a bundle to the
179 /// source archetype. For more information, see [`EntityWorldMut::insert`].
180 ///
181 /// If this returns `None`, it means there has not been a transition from
182 /// the source archetype via the provided bundle.
183 ///
184 /// [`EntityWorldMut::insert`]: crate::world::EntityWorldMut::insert
185 #[inline]
186 pub fn get_add_bundle(&self, bundle_id: BundleId) -> Option<ArchetypeId> {
187 self.get_add_bundle_internal(bundle_id)
188 .map(|bundle| bundle.archetype_id)
189 }
190
191 /// Internal version of `get_add_bundle` that fetches the full `AddBundle`.
192 #[inline]
193 pub(crate) fn get_add_bundle_internal(&self, bundle_id: BundleId) -> Option<&AddBundle> {
194 self.add_bundle.get(bundle_id)
195 }
196
197 /// Caches the target archetype when adding a bundle to the source archetype.
198 /// For more information, see [`EntityWorldMut::insert`].
199 ///
200 /// [`EntityWorldMut::insert`]: crate::world::EntityWorldMut::insert
201 #[inline]
202 pub(crate) fn insert_add_bundle(
203 &mut self,
204 bundle_id: BundleId,
205 archetype_id: ArchetypeId,
206 bundle_status: Vec<ComponentStatus>,
207 added: Vec<ComponentId>,
208 ) {
209 self.add_bundle.insert(
210 bundle_id,
211 AddBundle {
212 archetype_id,
213 bundle_status,
214 added,
215 },
216 );
217 }
218
219 /// Checks the cache for the target archetype when removing a bundle to the
220 /// source archetype. For more information, see [`EntityWorldMut::remove`].
221 ///
222 /// If this returns `None`, it means there has not been a transition from
223 /// the source archetype via the provided bundle.
224 ///
225 /// If this returns `Some(None)`, it means that the bundle cannot be removed
226 /// from the source archetype.
227 ///
228 /// [`EntityWorldMut::remove`]: crate::world::EntityWorldMut::remove
229 #[inline]
230 pub fn get_remove_bundle(&self, bundle_id: BundleId) -> Option<Option<ArchetypeId>> {
231 self.remove_bundle.get(bundle_id).cloned()
232 }
233
234 /// Caches the target archetype when removing a bundle to the source archetype.
235 /// For more information, see [`EntityWorldMut::remove`].
236 ///
237 /// [`EntityWorldMut::remove`]: crate::world::EntityWorldMut::remove
238 #[inline]
239 pub(crate) fn insert_remove_bundle(
240 &mut self,
241 bundle_id: BundleId,
242 archetype_id: Option<ArchetypeId>,
243 ) {
244 self.remove_bundle.insert(bundle_id, archetype_id);
245 }
246
247 /// Checks the cache for the target archetype when removing a bundle to the
248 /// source archetype. For more information, see [`EntityWorldMut::remove`].
249 ///
250 /// If this returns `None`, it means there has not been a transition from
251 /// the source archetype via the provided bundle.
252 ///
253 /// [`EntityWorldMut::remove`]: crate::world::EntityWorldMut::remove
254 #[inline]
255 pub fn get_take_bundle(&self, bundle_id: BundleId) -> Option<Option<ArchetypeId>> {
256 self.take_bundle.get(bundle_id).cloned()
257 }
258
259 /// Caches the target archetype when removing a bundle to the source archetype.
260 /// For more information, see [`EntityWorldMut::take`].
261 ///
262 /// [`EntityWorldMut::take`]: crate::world::EntityWorldMut::take
263 #[inline]
264 pub(crate) fn insert_take_bundle(
265 &mut self,
266 bundle_id: BundleId,
267 archetype_id: Option<ArchetypeId>,
268 ) {
269 self.take_bundle.insert(bundle_id, archetype_id);
270 }
271}
272
273/// Metadata about an [`Entity`] in a [`Archetype`].
274pub struct ArchetypeEntity {
275 entity: Entity,
276 table_row: TableRow,
277}
278
279impl ArchetypeEntity {
280 /// The ID of the entity.
281 #[inline]
282 pub const fn id(&self) -> Entity {
283 self.entity
284 }
285
286 /// The row in the [`Table`] where the entity's components are stored.
287 ///
288 /// [`Table`]: crate::storage::Table
289 #[inline]
290 pub const fn table_row(&self) -> TableRow {
291 self.table_row
292 }
293}
294
295/// Internal metadata for an [`Entity`] getting removed from an [`Archetype`].
296pub(crate) struct ArchetypeSwapRemoveResult {
297 /// If the [`Entity`] was not the last in the [`Archetype`], it gets removed by swapping it out
298 /// with the last entity in the archetype. In that case, this field contains the swapped entity.
299 pub(crate) swapped_entity: Option<Entity>,
300 /// The [`TableRow`] where the removed entity's components are stored.
301 pub(crate) table_row: TableRow,
302}
303
304/// Internal metadata for a [`Component`] within a given [`Archetype`].
305///
306/// [`Component`]: crate::component::Component
307struct ArchetypeComponentInfo {
308 storage_type: StorageType,
309 archetype_component_id: ArchetypeComponentId,
310}
311
312bitflags::bitflags! {
313 /// Flags used to keep track of metadata about the component in this [`Archetype`]
314 ///
315 /// Used primarily to early-out when there are no [`ComponentHook`] registered for any contained components.
316 #[derive(Clone, Copy)]
317 pub(crate) struct ArchetypeFlags: u32 {
318 const ON_ADD_HOOK = (1 << 0);
319 const ON_INSERT_HOOK = (1 << 1);
320 const ON_REMOVE_HOOK = (1 << 2);
321 const ON_ADD_OBSERVER = (1 << 3);
322 const ON_INSERT_OBSERVER = (1 << 4);
323 const ON_REMOVE_OBSERVER = (1 << 5);
324 }
325}
326
327/// Metadata for a single archetype within a [`World`].
328///
329/// For more information, see the *[module level documentation]*.
330///
331/// [`World`]: crate::world::World
332/// [module level documentation]: crate::archetype
333pub struct Archetype {
334 id: ArchetypeId,
335 table_id: TableId,
336 edges: Edges,
337 entities: Vec<ArchetypeEntity>,
338 components: ImmutableSparseSet<ComponentId, ArchetypeComponentInfo>,
339 flags: ArchetypeFlags,
340}
341
342impl Archetype {
343 pub(crate) fn new(
344 components: &Components,
345 observers: &Observers,
346 id: ArchetypeId,
347 table_id: TableId,
348 table_components: impl Iterator<Item = (ComponentId, ArchetypeComponentId)>,
349 sparse_set_components: impl Iterator<Item = (ComponentId, ArchetypeComponentId)>,
350 ) -> Self {
351 let (min_table, _) = table_components.size_hint();
352 let (min_sparse, _) = sparse_set_components.size_hint();
353 let mut flags = ArchetypeFlags::empty();
354 let mut archetype_components = SparseSet::with_capacity(min_table + min_sparse);
355 for (component_id, archetype_component_id) in table_components {
356 // SAFETY: We are creating an archetype that includes this component so it must exist
357 let info = unsafe { components.get_info_unchecked(component_id) };
358 info.update_archetype_flags(&mut flags);
359 observers.update_archetype_flags(component_id, &mut flags);
360 archetype_components.insert(
361 component_id,
362 ArchetypeComponentInfo {
363 storage_type: StorageType::Table,
364 archetype_component_id,
365 },
366 );
367 }
368
369 for (component_id, archetype_component_id) in sparse_set_components {
370 // SAFETY: We are creating an archetype that includes this component so it must exist
371 let info = unsafe { components.get_info_unchecked(component_id) };
372 info.update_archetype_flags(&mut flags);
373 observers.update_archetype_flags(component_id, &mut flags);
374 archetype_components.insert(
375 component_id,
376 ArchetypeComponentInfo {
377 storage_type: StorageType::SparseSet,
378 archetype_component_id,
379 },
380 );
381 }
382 Self {
383 id,
384 table_id,
385 entities: Vec::new(),
386 components: archetype_components.into_immutable(),
387 edges: Default::default(),
388 flags,
389 }
390 }
391
392 /// Fetches the ID for the archetype.
393 #[inline]
394 pub fn id(&self) -> ArchetypeId {
395 self.id
396 }
397
398 /// Fetches the flags for the archetype.
399 #[inline]
400 pub(crate) fn flags(&self) -> ArchetypeFlags {
401 self.flags
402 }
403
404 /// Fetches the archetype's [`Table`] ID.
405 ///
406 /// [`Table`]: crate::storage::Table
407 #[inline]
408 pub fn table_id(&self) -> TableId {
409 self.table_id
410 }
411
412 /// Fetches the entities contained in this archetype.
413 #[inline]
414 pub fn entities(&self) -> &[ArchetypeEntity] {
415 &self.entities
416 }
417
418 /// Gets an iterator of all of the components stored in [`Table`]s.
419 ///
420 /// All of the IDs are unique.
421 ///
422 /// [`Table`]: crate::storage::Table
423 #[inline]
424 pub fn table_components(&self) -> impl Iterator<Item = ComponentId> + '_ {
425 self.components
426 .iter()
427 .filter(|(_, component)| component.storage_type == StorageType::Table)
428 .map(|(id, _)| *id)
429 }
430
431 /// Gets an iterator of all of the components stored in [`ComponentSparseSet`]s.
432 ///
433 /// All of the IDs are unique.
434 ///
435 /// [`ComponentSparseSet`]: crate::storage::ComponentSparseSet
436 #[inline]
437 pub fn sparse_set_components(&self) -> impl Iterator<Item = ComponentId> + '_ {
438 self.components
439 .iter()
440 .filter(|(_, component)| component.storage_type == StorageType::SparseSet)
441 .map(|(id, _)| *id)
442 }
443
444 /// Gets an iterator of all of the components in the archetype.
445 ///
446 /// All of the IDs are unique.
447 #[inline]
448 pub fn components(&self) -> impl Iterator<Item = ComponentId> + '_ {
449 self.components.indices()
450 }
451
452 /// Returns the total number of components in the archetype
453 #[inline]
454 pub fn component_count(&self) -> usize {
455 self.components.len()
456 }
457
458 /// Fetches a immutable reference to the archetype's [`Edges`], a cache of
459 /// archetypal relationships.
460 #[inline]
461 pub fn edges(&self) -> &Edges {
462 &self.edges
463 }
464
465 /// Fetches a mutable reference to the archetype's [`Edges`], a cache of
466 /// archetypal relationships.
467 #[inline]
468 pub(crate) fn edges_mut(&mut self) -> &mut Edges {
469 &mut self.edges
470 }
471
472 /// Fetches the row in the [`Table`] where the components for the entity at `index`
473 /// is stored.
474 ///
475 /// An entity's archetype row can be fetched from [`EntityLocation::archetype_row`], which
476 /// can be retrieved from [`Entities::get`].
477 ///
478 /// # Panics
479 /// This function will panic if `index >= self.len()`.
480 ///
481 /// [`Table`]: crate::storage::Table
482 /// [`EntityLocation::archetype_row`]: crate::entity::EntityLocation::archetype_row
483 /// [`Entities::get`]: crate::entity::Entities::get
484 #[inline]
485 pub fn entity_table_row(&self, row: ArchetypeRow) -> TableRow {
486 self.entities[row.index()].table_row
487 }
488
489 /// Updates if the components for the entity at `index` can be found
490 /// in the corresponding table.
491 ///
492 /// # Panics
493 /// This function will panic if `index >= self.len()`.
494 #[inline]
495 pub(crate) fn set_entity_table_row(&mut self, row: ArchetypeRow, table_row: TableRow) {
496 self.entities[row.index()].table_row = table_row;
497 }
498
499 /// Allocates an entity to the archetype.
500 ///
501 /// # Safety
502 /// valid component values must be immediately written to the relevant storages
503 /// `table_row` must be valid
504 #[inline]
505 pub(crate) unsafe fn allocate(
506 &mut self,
507 entity: Entity,
508 table_row: TableRow,
509 ) -> EntityLocation {
510 let archetype_row = ArchetypeRow::new(self.entities.len());
511 self.entities.push(ArchetypeEntity { entity, table_row });
512
513 EntityLocation {
514 archetype_id: self.id,
515 archetype_row,
516 table_id: self.table_id,
517 table_row,
518 }
519 }
520
521 #[inline]
522 pub(crate) fn reserve(&mut self, additional: usize) {
523 self.entities.reserve(additional);
524 }
525
526 /// Removes the entity at `index` by swapping it out. Returns the table row the entity is stored
527 /// in.
528 ///
529 /// # Panics
530 /// This function will panic if `index >= self.len()`
531 #[inline]
532 pub(crate) fn swap_remove(&mut self, row: ArchetypeRow) -> ArchetypeSwapRemoveResult {
533 let is_last = row.index() == self.entities.len() - 1;
534 let entity = self.entities.swap_remove(row.index());
535 ArchetypeSwapRemoveResult {
536 swapped_entity: if is_last {
537 None
538 } else {
539 Some(self.entities[row.index()].entity)
540 },
541 table_row: entity.table_row,
542 }
543 }
544
545 /// Gets the total number of entities that belong to the archetype.
546 #[inline]
547 pub fn len(&self) -> usize {
548 self.entities.len()
549 }
550
551 /// Checks if the archetype has any entities.
552 #[inline]
553 pub fn is_empty(&self) -> bool {
554 self.entities.is_empty()
555 }
556
557 /// Checks if the archetype contains a specific component. This runs in `O(1)` time.
558 #[inline]
559 pub fn contains(&self, component_id: ComponentId) -> bool {
560 self.components.contains(component_id)
561 }
562
563 /// Gets the type of storage where a component in the archetype can be found.
564 /// Returns `None` if the component is not part of the archetype.
565 /// This runs in `O(1)` time.
566 #[inline]
567 pub fn get_storage_type(&self, component_id: ComponentId) -> Option<StorageType> {
568 self.components
569 .get(component_id)
570 .map(|info| info.storage_type)
571 }
572
573 /// Fetches the corresponding [`ArchetypeComponentId`] for a component in the archetype.
574 /// Returns `None` if the component is not part of the archetype.
575 /// This runs in `O(1)` time.
576 #[inline]
577 pub fn get_archetype_component_id(
578 &self,
579 component_id: ComponentId,
580 ) -> Option<ArchetypeComponentId> {
581 self.components
582 .get(component_id)
583 .map(|info| info.archetype_component_id)
584 }
585
586 /// Clears all entities from the archetype.
587 pub(crate) fn clear_entities(&mut self) {
588 self.entities.clear();
589 }
590
591 /// Returns true if any of the components in this archetype have `on_add` hooks
592 #[inline]
593 pub fn has_add_hook(&self) -> bool {
594 self.flags().contains(ArchetypeFlags::ON_ADD_HOOK)
595 }
596
597 /// Returns true if any of the components in this archetype have `on_insert` hooks
598 #[inline]
599 pub fn has_insert_hook(&self) -> bool {
600 self.flags().contains(ArchetypeFlags::ON_INSERT_HOOK)
601 }
602
603 /// Returns true if any of the components in this archetype have `on_remove` hooks
604 #[inline]
605 pub fn has_remove_hook(&self) -> bool {
606 self.flags().contains(ArchetypeFlags::ON_REMOVE_HOOK)
607 }
608
609 /// Returns true if any of the components in this archetype have at least one [`OnAdd`] observer
610 ///
611 /// [`OnAdd`]: crate::world::OnAdd
612 #[inline]
613 pub fn has_add_observer(&self) -> bool {
614 self.flags().contains(ArchetypeFlags::ON_ADD_OBSERVER)
615 }
616
617 /// Returns true if any of the components in this archetype have at least one [`OnInsert`] observer
618 ///
619 /// [`OnInsert`]: crate::world::OnInsert
620 #[inline]
621 pub fn has_insert_observer(&self) -> bool {
622 self.flags().contains(ArchetypeFlags::ON_INSERT_OBSERVER)
623 }
624
625 /// Returns true if any of the components in this archetype have at least one [`OnRemove`] observer
626 ///
627 /// [`OnRemove`]: crate::world::OnRemove
628 #[inline]
629 pub fn has_remove_observer(&self) -> bool {
630 self.flags().contains(ArchetypeFlags::ON_REMOVE_OBSERVER)
631 }
632}
633
634/// The next [`ArchetypeId`] in an [`Archetypes`] collection.
635///
636/// This is used in archetype update methods to limit archetype updates to the
637/// ones added since the last time the method ran.
638#[derive(Debug, Copy, Clone, PartialEq)]
639pub struct ArchetypeGeneration(ArchetypeId);
640
641impl ArchetypeGeneration {
642 /// The first archetype.
643 #[inline]
644 pub const fn initial() -> Self {
645 ArchetypeGeneration(ArchetypeId::EMPTY)
646 }
647}
648
649#[derive(Hash, PartialEq, Eq)]
650struct ArchetypeComponents {
651 table_components: Box<[ComponentId]>,
652 sparse_set_components: Box<[ComponentId]>,
653}
654
655/// An opaque unique joint ID for a [`Component`] in an [`Archetype`] within a [`World`].
656///
657/// A component may be present within multiple archetypes, but each component within
658/// each archetype has its own unique `ArchetypeComponentId`. This is leveraged by the system
659/// schedulers to opportunistically run multiple systems in parallel that would otherwise
660/// conflict. For example, `Query<&mut A, With<B>>` and `Query<&mut A, Without<B>>` can run in
661/// parallel as the matched `ArchetypeComponentId` sets for both queries are disjoint, even
662/// though `&mut A` on both queries point to the same [`ComponentId`].
663///
664/// In SQL terms, these IDs are composite keys on a [many-to-many relationship] between archetypes
665/// and components. Each component type will have only one [`ComponentId`], but may have many
666/// [`ArchetypeComponentId`]s, one for every archetype the component is present in. Likewise, each
667/// archetype will have only one [`ArchetypeId`] but may have many [`ArchetypeComponentId`]s, one
668/// for each component that belongs to the archetype.
669///
670/// Every [`Resource`] is also assigned one of these IDs. As resources do not belong to any
671/// particular archetype, a resource's ID uniquely identifies it.
672///
673/// These IDs are only valid within a given World, and are not globally unique.
674/// Attempting to use an ID on a world that it wasn't sourced from will
675/// not point to the same archetype nor the same component.
676///
677/// [`Component`]: crate::component::Component
678/// [`World`]: crate::world::World
679/// [`Resource`]: crate::system::Resource
680/// [many-to-many relationship]: https://en.wikipedia.org/wiki/Many-to-many_(data_model)
681#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
682pub struct ArchetypeComponentId(usize);
683
684impl SparseSetIndex for ArchetypeComponentId {
685 #[inline]
686 fn sparse_set_index(&self) -> usize {
687 self.0
688 }
689
690 fn get_sparse_set_index(value: usize) -> Self {
691 Self(value)
692 }
693}
694
695/// The backing store of all [`Archetype`]s within a [`World`].
696///
697/// For more information, see the *[module level documentation]*.
698///
699/// [`World`]: crate::world::World
700/// [module level documentation]: crate::archetype
701pub struct Archetypes {
702 pub(crate) archetypes: Vec<Archetype>,
703 archetype_component_count: usize,
704 by_components: bevy_utils::HashMap<ArchetypeComponents, ArchetypeId>,
705}
706
707impl Archetypes {
708 pub(crate) fn new() -> Self {
709 let mut archetypes = Archetypes {
710 archetypes: Vec::new(),
711 by_components: Default::default(),
712 archetype_component_count: 0,
713 };
714 // SAFETY: Empty archetype has no components
715 unsafe {
716 archetypes.get_id_or_insert(
717 &Components::default(),
718 &Observers::default(),
719 TableId::empty(),
720 Vec::new(),
721 Vec::new(),
722 );
723 }
724 archetypes
725 }
726
727 /// Returns the "generation", a handle to the current highest archetype ID.
728 ///
729 /// This can be used with the `Index` [`Archetypes`] implementation to
730 /// iterate over newly introduced [`Archetype`]s since the last time this
731 /// function was called.
732 #[inline]
733 pub fn generation(&self) -> ArchetypeGeneration {
734 let id = ArchetypeId::new(self.archetypes.len());
735 ArchetypeGeneration(id)
736 }
737
738 /// Fetches the total number of [`Archetype`]s within the world.
739 #[inline]
740 #[allow(clippy::len_without_is_empty)] // the internal vec is never empty.
741 pub fn len(&self) -> usize {
742 self.archetypes.len()
743 }
744
745 /// Fetches an immutable reference to the archetype without any components.
746 ///
747 /// Shorthand for `archetypes.get(ArchetypeId::EMPTY).unwrap()`
748 #[inline]
749 pub fn empty(&self) -> &Archetype {
750 // SAFETY: empty archetype always exists
751 unsafe { self.archetypes.get_unchecked(ArchetypeId::EMPTY.index()) }
752 }
753
754 /// Fetches an mutable reference to the archetype without any components.
755 #[inline]
756 pub(crate) fn empty_mut(&mut self) -> &mut Archetype {
757 // SAFETY: empty archetype always exists
758 unsafe {
759 self.archetypes
760 .get_unchecked_mut(ArchetypeId::EMPTY.index())
761 }
762 }
763
764 /// Generate and store a new [`ArchetypeComponentId`].
765 ///
766 /// This simply increment the counter and return the new value.
767 ///
768 /// # Panics
769 ///
770 /// On archetype component id overflow.
771 pub(crate) fn new_archetype_component_id(&mut self) -> ArchetypeComponentId {
772 let id = ArchetypeComponentId(self.archetype_component_count);
773 self.archetype_component_count = self
774 .archetype_component_count
775 .checked_add(1)
776 .expect("archetype_component_count overflow");
777 id
778 }
779
780 /// Fetches an immutable reference to an [`Archetype`] using its
781 /// ID. Returns `None` if no corresponding archetype exists.
782 #[inline]
783 pub fn get(&self, id: ArchetypeId) -> Option<&Archetype> {
784 self.archetypes.get(id.index())
785 }
786
787 /// # Panics
788 ///
789 /// Panics if `a` and `b` are equal.
790 #[inline]
791 pub(crate) fn get_2_mut(
792 &mut self,
793 a: ArchetypeId,
794 b: ArchetypeId,
795 ) -> (&mut Archetype, &mut Archetype) {
796 if a.index() > b.index() {
797 let (b_slice, a_slice) = self.archetypes.split_at_mut(a.index());
798 (&mut a_slice[0], &mut b_slice[b.index()])
799 } else {
800 let (a_slice, b_slice) = self.archetypes.split_at_mut(b.index());
801 (&mut a_slice[a.index()], &mut b_slice[0])
802 }
803 }
804
805 /// Returns a read-only iterator over all archetypes.
806 #[inline]
807 pub fn iter(&self) -> impl Iterator<Item = &Archetype> {
808 self.archetypes.iter()
809 }
810
811 /// Gets the archetype id matching the given inputs or inserts a new one if it doesn't exist.
812 /// `table_components` and `sparse_set_components` must be sorted
813 ///
814 /// # Safety
815 /// [`TableId`] must exist in tables
816 /// `table_components` and `sparse_set_components` must exist in `components`
817 pub(crate) unsafe fn get_id_or_insert(
818 &mut self,
819 components: &Components,
820 observers: &Observers,
821 table_id: TableId,
822 table_components: Vec<ComponentId>,
823 sparse_set_components: Vec<ComponentId>,
824 ) -> ArchetypeId {
825 let archetype_identity = ArchetypeComponents {
826 sparse_set_components: sparse_set_components.clone().into_boxed_slice(),
827 table_components: table_components.clone().into_boxed_slice(),
828 };
829
830 let archetypes = &mut self.archetypes;
831 let archetype_component_count = &mut self.archetype_component_count;
832 *self
833 .by_components
834 .entry(archetype_identity)
835 .or_insert_with(move || {
836 let id = ArchetypeId::new(archetypes.len());
837 let table_start = *archetype_component_count;
838 *archetype_component_count += table_components.len();
839 let table_archetype_components =
840 (table_start..*archetype_component_count).map(ArchetypeComponentId);
841 let sparse_start = *archetype_component_count;
842 *archetype_component_count += sparse_set_components.len();
843 let sparse_set_archetype_components =
844 (sparse_start..*archetype_component_count).map(ArchetypeComponentId);
845 archetypes.push(Archetype::new(
846 components,
847 observers,
848 id,
849 table_id,
850 table_components.into_iter().zip(table_archetype_components),
851 sparse_set_components
852 .into_iter()
853 .zip(sparse_set_archetype_components),
854 ));
855 id
856 })
857 }
858
859 /// Returns the number of components that are stored in archetypes.
860 /// Note that if some component `T` is stored in more than one archetype, it will be counted once for each archetype it's present in.
861 #[inline]
862 pub fn archetype_components_len(&self) -> usize {
863 self.archetype_component_count
864 }
865
866 /// Clears all entities from all archetypes.
867 pub(crate) fn clear_entities(&mut self) {
868 for archetype in &mut self.archetypes {
869 archetype.clear_entities();
870 }
871 }
872
873 pub(crate) fn update_flags(
874 &mut self,
875 component_id: ComponentId,
876 flags: ArchetypeFlags,
877 set: bool,
878 ) {
879 // TODO: Refactor component index to speed this up.
880 for archetype in &mut self.archetypes {
881 if archetype.contains(component_id) {
882 archetype.flags.set(flags, set);
883 }
884 }
885 }
886}
887
888impl Index<RangeFrom<ArchetypeGeneration>> for Archetypes {
889 type Output = [Archetype];
890
891 #[inline]
892 fn index(&self, index: RangeFrom<ArchetypeGeneration>) -> &Self::Output {
893 &self.archetypes[index.start.0.index()..]
894 }
895}
896impl Index<ArchetypeId> for Archetypes {
897 type Output = Archetype;
898
899 #[inline]
900 fn index(&self, index: ArchetypeId) -> &Self::Output {
901 &self.archetypes[index.index()]
902 }
903}
904
905impl IndexMut<ArchetypeId> for Archetypes {
906 #[inline]
907 fn index_mut(&mut self, index: ArchetypeId) -> &mut Self::Output {
908 &mut self.archetypes[index.index()]
909 }
910}