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}