bevy_render/render_phase/
mod.rs

1//! The modular rendering abstraction responsible for queuing, preparing, sorting and drawing
2//! entities as part of separate render phases.
3//!
4//! In Bevy each view (camera, or shadow-casting light, etc.) has one or multiple render phases
5//! (e.g. opaque, transparent, shadow, etc).
6//! They are used to queue entities for rendering.
7//! Multiple phases might be required due to different sorting/batching behaviors
8//! (e.g. opaque: front to back, transparent: back to front) or because one phase depends on
9//! the rendered texture of the previous phase (e.g. for screen-space reflections).
10//!
11//! To draw an entity, a corresponding [`PhaseItem`] has to be added to one or multiple of these
12//! render phases for each view that it is visible in.
13//! This must be done in the [`RenderSystems::Queue`].
14//! After that the render phase sorts them in the [`RenderSystems::PhaseSort`].
15//! Finally the items are rendered using a single [`TrackedRenderPass`], during
16//! the [`RenderSystems::Render`].
17//!
18//! Therefore each phase item is assigned a [`Draw`] function.
19//! These set up the state of the [`TrackedRenderPass`] (i.e. select the
20//! [`RenderPipeline`](crate::render_resource::RenderPipeline), configure the
21//! [`BindGroup`](crate::render_resource::BindGroup)s, etc.) and then issue a draw call,
22//! for the corresponding item.
23//!
24//! The [`Draw`] function trait can either be implemented directly or such a function can be
25//! created by composing multiple [`RenderCommand`]s.
26
27mod draw;
28mod draw_state;
29mod rangefinder;
30
31use bevy_app::{App, Plugin};
32use bevy_derive::{Deref, DerefMut};
33use bevy_ecs::component::Tick;
34use bevy_ecs::entity::EntityHash;
35use bevy_platform::collections::{hash_map::Entry, HashMap};
36use bevy_utils::default;
37pub use draw::*;
38pub use draw_state::*;
39use encase::{internal::WriteInto, ShaderSize};
40use fixedbitset::{Block, FixedBitSet};
41use indexmap::IndexMap;
42use nonmax::NonMaxU32;
43pub use rangefinder::*;
44use wgpu::Features;
45
46use crate::batching::gpu_preprocessing::{
47    GpuPreprocessingMode, GpuPreprocessingSupport, PhaseBatchedInstanceBuffers,
48    PhaseIndirectParametersBuffers,
49};
50use crate::renderer::RenderDevice;
51use crate::sync_world::{MainEntity, MainEntityHashMap};
52use crate::view::RetainedViewEntity;
53use crate::RenderDebugFlags;
54use crate::{
55    batching::{
56        self,
57        gpu_preprocessing::{self, BatchedInstanceBuffers},
58        no_gpu_preprocessing::{self, BatchedInstanceBuffer},
59        GetFullBatchData,
60    },
61    render_resource::{CachedRenderPipelineId, GpuArrayBufferIndex, PipelineCache},
62    Render, RenderApp, RenderSystems,
63};
64use bevy_ecs::intern::Interned;
65use bevy_ecs::{
66    define_label,
67    prelude::*,
68    system::{lifetimeless::SRes, SystemParamItem},
69};
70use bevy_render::renderer::RenderAdapterInfo;
71pub use bevy_render_macros::ShaderLabel;
72use core::{fmt::Debug, hash::Hash, iter, marker::PhantomData, ops::Range, slice::SliceIndex};
73use smallvec::SmallVec;
74use tracing::warn;
75
76define_label!(
77    #[diagnostic::on_unimplemented(
78        note = "consider annotating `{Self}` with `#[derive(ShaderLabel)]`"
79    )]
80    /// Labels used to uniquely identify types of material shaders
81    ShaderLabel,
82    SHADER_LABEL_INTERNER
83);
84
85/// A shorthand for `Interned<dyn RenderSubGraph>`.
86pub type InternedShaderLabel = Interned<dyn ShaderLabel>;
87
88pub use bevy_render_macros::DrawFunctionLabel;
89
90define_label!(
91    #[diagnostic::on_unimplemented(
92        note = "consider annotating `{Self}` with `#[derive(DrawFunctionLabel)]`"
93    )]
94    /// Labels used to uniquely identify types of material shaders
95    DrawFunctionLabel,
96    DRAW_FUNCTION_LABEL_INTERNER
97);
98
99pub type InternedDrawFunctionLabel = Interned<dyn DrawFunctionLabel>;
100
101/// Stores the rendering instructions for a single phase that uses bins in all
102/// views.
103///
104/// They're cleared out every frame, but storing them in a resource like this
105/// allows us to reuse allocations.
106#[derive(Resource, Deref, DerefMut)]
107pub struct ViewBinnedRenderPhases<BPI>(pub HashMap<RetainedViewEntity, BinnedRenderPhase<BPI>>)
108where
109    BPI: BinnedPhaseItem;
110
111/// A collection of all rendering instructions, that will be executed by the GPU, for a
112/// single render phase for a single view.
113///
114/// Each view (camera, or shadow-casting light, etc.) can have one or multiple render phases.
115/// They are used to queue entities for rendering.
116/// Multiple phases might be required due to different sorting/batching behaviors
117/// (e.g. opaque: front to back, transparent: back to front) or because one phase depends on
118/// the rendered texture of the previous phase (e.g. for screen-space reflections).
119/// All [`PhaseItem`]s are then rendered using a single [`TrackedRenderPass`].
120/// The render pass might be reused for multiple phases to reduce GPU overhead.
121///
122/// This flavor of render phase is used for phases in which the ordering is less
123/// critical: for example, `Opaque3d`. It's generally faster than the
124/// alternative [`SortedRenderPhase`].
125pub struct BinnedRenderPhase<BPI>
126where
127    BPI: BinnedPhaseItem,
128{
129    /// The multidrawable bins.
130    ///
131    /// Each batch set key maps to a *batch set*, which in this case is a set of
132    /// meshes that can be drawn together in one multidraw call. Each batch set
133    /// is subdivided into *bins*, each of which represents a particular mesh.
134    /// Each bin contains the entity IDs of instances of that mesh.
135    ///
136    /// So, for example, if there are two cubes and a sphere present in the
137    /// scene, we would generally have one batch set containing two bins,
138    /// assuming that the cubes and sphere meshes are allocated together and use
139    /// the same pipeline. The first bin, corresponding to the cubes, will have
140    /// two entities in it. The second bin, corresponding to the sphere, will
141    /// have one entity in it.
142    pub multidrawable_meshes: IndexMap<BPI::BatchSetKey, IndexMap<BPI::BinKey, RenderBin>>,
143
144    /// The bins corresponding to batchable items that aren't multidrawable.
145    ///
146    /// For multidrawable entities, use `multidrawable_meshes`; for
147    /// unbatchable entities, use `unbatchable_values`.
148    pub batchable_meshes: IndexMap<(BPI::BatchSetKey, BPI::BinKey), RenderBin>,
149
150    /// The unbatchable bins.
151    ///
152    /// Each entity here is rendered in a separate drawcall.
153    pub unbatchable_meshes: IndexMap<(BPI::BatchSetKey, BPI::BinKey), UnbatchableBinnedEntities>,
154
155    /// Items in the bin that aren't meshes at all.
156    ///
157    /// Bevy itself doesn't place anything in this list, but plugins or your app
158    /// can in order to execute custom drawing commands. Draw functions for each
159    /// entity are simply called in order at rendering time.
160    ///
161    /// See the `custom_phase_item` example for an example of how to use this.
162    pub non_mesh_items: IndexMap<(BPI::BatchSetKey, BPI::BinKey), NonMeshEntities>,
163
164    /// Information on each batch set.
165    ///
166    /// A *batch set* is a set of entities that will be batched together unless
167    /// we're on a platform that doesn't support storage buffers (e.g. WebGL 2)
168    /// and differing dynamic uniform indices force us to break batches. On
169    /// platforms that support storage buffers, a batch set always consists of
170    /// at most one batch.
171    ///
172    /// Multidrawable entities come first, then batchable entities, then
173    /// unbatchable entities.
174    pub(crate) batch_sets: BinnedRenderPhaseBatchSets<BPI::BinKey>,
175
176    /// The batch and bin key for each entity.
177    ///
178    /// We retain these so that, when the entity changes,
179    /// [`Self::sweep_old_entities`] can quickly find the bin it was located in
180    /// and remove it.
181    cached_entity_bin_keys: IndexMap<MainEntity, CachedBinnedEntity<BPI>, EntityHash>,
182
183    /// The set of indices in [`Self::cached_entity_bin_keys`] that are
184    /// confirmed to be up to date.
185    ///
186    /// Note that each bit in this bit set refers to an *index* in the
187    /// [`IndexMap`] (i.e. a bucket in the hash table). They aren't entity IDs.
188    valid_cached_entity_bin_keys: FixedBitSet,
189
190    /// The set of entities that changed bins this frame.
191    ///
192    /// An entity will only be present in this list if it was in one bin on the
193    /// previous frame and is in a new bin on this frame. Each list entry
194    /// specifies the bin the entity used to be in. We use this in order to
195    /// remove the entity from the old bin during
196    /// [`BinnedRenderPhase::sweep_old_entities`].
197    entities_that_changed_bins: Vec<EntityThatChangedBins<BPI>>,
198    /// The gpu preprocessing mode configured for the view this phase is associated
199    /// with.
200    gpu_preprocessing_mode: GpuPreprocessingMode,
201}
202
203/// All entities that share a mesh and a material and can be batched as part of
204/// a [`BinnedRenderPhase`].
205#[derive(Default)]
206pub struct RenderBin {
207    /// A list of the entities in each bin, along with their cached
208    /// [`InputUniformIndex`].
209    entities: IndexMap<MainEntity, InputUniformIndex, EntityHash>,
210}
211
212/// Information that we track about an entity that was in one bin on the
213/// previous frame and is in a different bin this frame.
214struct EntityThatChangedBins<BPI>
215where
216    BPI: BinnedPhaseItem,
217{
218    /// The entity.
219    main_entity: MainEntity,
220    /// The key that identifies the bin that this entity used to be in.
221    old_cached_binned_entity: CachedBinnedEntity<BPI>,
222}
223
224/// Information that we keep about an entity currently within a bin.
225pub struct CachedBinnedEntity<BPI>
226where
227    BPI: BinnedPhaseItem,
228{
229    /// Information that we use to identify a cached entity in a bin.
230    pub cached_bin_key: Option<CachedBinKey<BPI>>,
231    /// The last modified tick of the entity.
232    ///
233    /// We use this to detect when the entity needs to be invalidated.
234    pub change_tick: Tick,
235}
236
237/// Information that we use to identify a cached entity in a bin.
238pub struct CachedBinKey<BPI>
239where
240    BPI: BinnedPhaseItem,
241{
242    /// The key of the batch set containing the entity.
243    pub batch_set_key: BPI::BatchSetKey,
244    /// The key of the bin containing the entity.
245    pub bin_key: BPI::BinKey,
246    /// The type of render phase that we use to render the entity: multidraw,
247    /// plain batch, etc.
248    pub phase_type: BinnedRenderPhaseType,
249}
250
251impl<BPI> Clone for CachedBinnedEntity<BPI>
252where
253    BPI: BinnedPhaseItem,
254{
255    fn clone(&self) -> Self {
256        CachedBinnedEntity {
257            cached_bin_key: self.cached_bin_key.clone(),
258            change_tick: self.change_tick,
259        }
260    }
261}
262
263impl<BPI> Clone for CachedBinKey<BPI>
264where
265    BPI: BinnedPhaseItem,
266{
267    fn clone(&self) -> Self {
268        CachedBinKey {
269            batch_set_key: self.batch_set_key.clone(),
270            bin_key: self.bin_key.clone(),
271            phase_type: self.phase_type,
272        }
273    }
274}
275
276impl<BPI> PartialEq for CachedBinKey<BPI>
277where
278    BPI: BinnedPhaseItem,
279{
280    fn eq(&self, other: &Self) -> bool {
281        self.batch_set_key == other.batch_set_key
282            && self.bin_key == other.bin_key
283            && self.phase_type == other.phase_type
284    }
285}
286
287/// How we store and render the batch sets.
288///
289/// Each one of these corresponds to a [`GpuPreprocessingMode`].
290pub enum BinnedRenderPhaseBatchSets<BK> {
291    /// Batches are grouped into batch sets based on dynamic uniforms.
292    ///
293    /// This corresponds to [`GpuPreprocessingMode::None`].
294    DynamicUniforms(Vec<SmallVec<[BinnedRenderPhaseBatch; 1]>>),
295
296    /// Batches are never grouped into batch sets.
297    ///
298    /// This corresponds to [`GpuPreprocessingMode::PreprocessingOnly`].
299    Direct(Vec<BinnedRenderPhaseBatch>),
300
301    /// Batches are grouped together into batch sets based on their ability to
302    /// be multi-drawn together.
303    ///
304    /// This corresponds to [`GpuPreprocessingMode::Culling`].
305    MultidrawIndirect(Vec<BinnedRenderPhaseBatchSet<BK>>),
306}
307
308/// A group of entities that will be batched together into a single multi-draw
309/// call.
310pub struct BinnedRenderPhaseBatchSet<BK> {
311    /// The first batch in this batch set.
312    pub(crate) first_batch: BinnedRenderPhaseBatch,
313    /// The key of the bin that the first batch corresponds to.
314    pub(crate) bin_key: BK,
315    /// The number of batches.
316    pub(crate) batch_count: u32,
317    /// The index of the batch set in the GPU buffer.
318    pub(crate) index: u32,
319}
320
321impl<BK> BinnedRenderPhaseBatchSets<BK> {
322    fn clear(&mut self) {
323        match *self {
324            BinnedRenderPhaseBatchSets::DynamicUniforms(ref mut vec) => vec.clear(),
325            BinnedRenderPhaseBatchSets::Direct(ref mut vec) => vec.clear(),
326            BinnedRenderPhaseBatchSets::MultidrawIndirect(ref mut vec) => vec.clear(),
327        }
328    }
329}
330
331/// Information about a single batch of entities rendered using binned phase
332/// items.
333#[derive(Debug)]
334pub struct BinnedRenderPhaseBatch {
335    /// An entity that's *representative* of this batch.
336    ///
337    /// Bevy uses this to fetch the mesh. It can be any entity in the batch.
338    pub representative_entity: (Entity, MainEntity),
339    /// The range of instance indices in this batch.
340    pub instance_range: Range<u32>,
341
342    /// The dynamic offset of the batch.
343    ///
344    /// Note that dynamic offsets are only used on platforms that don't support
345    /// storage buffers.
346    pub extra_index: PhaseItemExtraIndex,
347}
348
349/// Information about the unbatchable entities in a bin.
350pub struct UnbatchableBinnedEntities {
351    /// The entities.
352    pub entities: MainEntityHashMap<Entity>,
353
354    /// The GPU array buffer indices of each unbatchable binned entity.
355    pub(crate) buffer_indices: UnbatchableBinnedEntityIndexSet,
356}
357
358/// Information about [`BinnedRenderPhaseType::NonMesh`] entities.
359pub struct NonMeshEntities {
360    /// The entities.
361    pub entities: MainEntityHashMap<Entity>,
362}
363
364/// Stores instance indices and dynamic offsets for unbatchable entities in a
365/// binned render phase.
366///
367/// This is conceptually `Vec<UnbatchableBinnedEntityDynamicOffset>`, but it
368/// avoids the overhead of storing dynamic offsets on platforms that support
369/// them. In other words, this allows a fast path that avoids allocation on
370/// platforms that aren't WebGL 2.
371#[derive(Default)]
372
373pub(crate) enum UnbatchableBinnedEntityIndexSet {
374    /// There are no unbatchable entities in this bin (yet).
375    #[default]
376    NoEntities,
377
378    /// The instances for all unbatchable entities in this bin are contiguous,
379    /// and there are no dynamic uniforms.
380    ///
381    /// This is the typical case on platforms other than WebGL 2. We special
382    /// case this to avoid allocation on those platforms.
383    Sparse {
384        /// The range of indices.
385        instance_range: Range<u32>,
386        /// The index of the first indirect instance parameters.
387        ///
388        /// The other indices immediately follow these.
389        first_indirect_parameters_index: Option<NonMaxU32>,
390    },
391
392    /// Dynamic uniforms are present for unbatchable entities in this bin.
393    ///
394    /// We fall back to this on WebGL 2.
395    Dense(Vec<UnbatchableBinnedEntityIndices>),
396}
397
398/// The instance index and dynamic offset (if present) for an unbatchable entity.
399///
400/// This is only useful on platforms that don't support storage buffers.
401#[derive(Clone)]
402pub(crate) struct UnbatchableBinnedEntityIndices {
403    /// The instance index.
404    pub(crate) instance_index: u32,
405    /// The [`PhaseItemExtraIndex`], if present.
406    pub(crate) extra_index: PhaseItemExtraIndex,
407}
408
409/// Identifies the list within [`BinnedRenderPhase`] that a phase item is to be
410/// placed in.
411#[derive(Clone, Copy, PartialEq, Debug)]
412pub enum BinnedRenderPhaseType {
413    /// The item is a mesh that's eligible for multi-draw indirect rendering and
414    /// can be batched with other meshes of the same type.
415    MultidrawableMesh,
416
417    /// The item is a mesh that can be batched with other meshes of the same type and
418    /// drawn in a single draw call.
419    BatchableMesh,
420
421    /// The item is a mesh that's eligible for indirect rendering, but can't be
422    /// batched with other meshes of the same type.
423    UnbatchableMesh,
424
425    /// The item isn't a mesh at all.
426    ///
427    /// Bevy will simply invoke the drawing commands for such items one after
428    /// another, with no further processing.
429    ///
430    /// The engine itself doesn't enqueue any items of this type, but it's
431    /// available for use in your application and/or plugins.
432    NonMesh,
433}
434
435impl<T> From<GpuArrayBufferIndex<T>> for UnbatchableBinnedEntityIndices
436where
437    T: Clone + ShaderSize + WriteInto,
438{
439    fn from(value: GpuArrayBufferIndex<T>) -> Self {
440        UnbatchableBinnedEntityIndices {
441            instance_index: value.index,
442            extra_index: PhaseItemExtraIndex::maybe_dynamic_offset(value.dynamic_offset),
443        }
444    }
445}
446
447impl<BPI> Default for ViewBinnedRenderPhases<BPI>
448where
449    BPI: BinnedPhaseItem,
450{
451    fn default() -> Self {
452        Self(default())
453    }
454}
455
456impl<BPI> ViewBinnedRenderPhases<BPI>
457where
458    BPI: BinnedPhaseItem,
459{
460    pub fn prepare_for_new_frame(
461        &mut self,
462        retained_view_entity: RetainedViewEntity,
463        gpu_preprocessing: GpuPreprocessingMode,
464    ) {
465        match self.entry(retained_view_entity) {
466            Entry::Occupied(mut entry) => entry.get_mut().prepare_for_new_frame(),
467            Entry::Vacant(entry) => {
468                entry.insert(BinnedRenderPhase::<BPI>::new(gpu_preprocessing));
469            }
470        }
471    }
472}
473
474/// The index of the uniform describing this object in the GPU buffer, when GPU
475/// preprocessing is enabled.
476///
477/// For example, for 3D meshes, this is the index of the `MeshInputUniform` in
478/// the buffer.
479///
480/// This field is ignored if GPU preprocessing isn't in use, such as (currently)
481/// in the case of 2D meshes. In that case, it can be safely set to
482/// [`core::default::Default::default`].
483#[derive(Clone, Copy, PartialEq, Default, Deref, DerefMut)]
484#[repr(transparent)]
485pub struct InputUniformIndex(pub u32);
486
487impl<BPI> BinnedRenderPhase<BPI>
488where
489    BPI: BinnedPhaseItem,
490{
491    /// Bins a new entity.
492    ///
493    /// The `phase_type` parameter specifies whether the entity is a
494    /// preprocessable mesh and whether it can be binned with meshes of the same
495    /// type.
496    pub fn add(
497        &mut self,
498        batch_set_key: BPI::BatchSetKey,
499        bin_key: BPI::BinKey,
500        (entity, main_entity): (Entity, MainEntity),
501        input_uniform_index: InputUniformIndex,
502        mut phase_type: BinnedRenderPhaseType,
503        change_tick: Tick,
504    ) {
505        // If the user has overridden indirect drawing for this view, we need to
506        // force the phase type to be batchable instead.
507        if self.gpu_preprocessing_mode == GpuPreprocessingMode::PreprocessingOnly
508            && phase_type == BinnedRenderPhaseType::MultidrawableMesh
509        {
510            phase_type = BinnedRenderPhaseType::BatchableMesh;
511        }
512
513        match phase_type {
514            BinnedRenderPhaseType::MultidrawableMesh => {
515                match self.multidrawable_meshes.entry(batch_set_key.clone()) {
516                    indexmap::map::Entry::Occupied(mut entry) => {
517                        entry
518                            .get_mut()
519                            .entry(bin_key.clone())
520                            .or_default()
521                            .insert(main_entity, input_uniform_index);
522                    }
523                    indexmap::map::Entry::Vacant(entry) => {
524                        let mut new_batch_set = IndexMap::default();
525                        new_batch_set.insert(
526                            bin_key.clone(),
527                            RenderBin::from_entity(main_entity, input_uniform_index),
528                        );
529                        entry.insert(new_batch_set);
530                    }
531                }
532            }
533
534            BinnedRenderPhaseType::BatchableMesh => {
535                match self
536                    .batchable_meshes
537                    .entry((batch_set_key.clone(), bin_key.clone()).clone())
538                {
539                    indexmap::map::Entry::Occupied(mut entry) => {
540                        entry.get_mut().insert(main_entity, input_uniform_index);
541                    }
542                    indexmap::map::Entry::Vacant(entry) => {
543                        entry.insert(RenderBin::from_entity(main_entity, input_uniform_index));
544                    }
545                }
546            }
547
548            BinnedRenderPhaseType::UnbatchableMesh => {
549                match self
550                    .unbatchable_meshes
551                    .entry((batch_set_key.clone(), bin_key.clone()))
552                {
553                    indexmap::map::Entry::Occupied(mut entry) => {
554                        entry.get_mut().entities.insert(main_entity, entity);
555                    }
556                    indexmap::map::Entry::Vacant(entry) => {
557                        let mut entities = MainEntityHashMap::default();
558                        entities.insert(main_entity, entity);
559                        entry.insert(UnbatchableBinnedEntities {
560                            entities,
561                            buffer_indices: default(),
562                        });
563                    }
564                }
565            }
566
567            BinnedRenderPhaseType::NonMesh => {
568                // We don't process these items further.
569                match self
570                    .non_mesh_items
571                    .entry((batch_set_key.clone(), bin_key.clone()).clone())
572                {
573                    indexmap::map::Entry::Occupied(mut entry) => {
574                        entry.get_mut().entities.insert(main_entity, entity);
575                    }
576                    indexmap::map::Entry::Vacant(entry) => {
577                        let mut entities = MainEntityHashMap::default();
578                        entities.insert(main_entity, entity);
579                        entry.insert(NonMeshEntities { entities });
580                    }
581                }
582            }
583        }
584
585        // Update the cache.
586        self.update_cache(
587            main_entity,
588            Some(CachedBinKey {
589                batch_set_key,
590                bin_key,
591                phase_type,
592            }),
593            change_tick,
594        );
595    }
596
597    /// Inserts an entity into the cache with the given change tick.
598    pub fn update_cache(
599        &mut self,
600        main_entity: MainEntity,
601        cached_bin_key: Option<CachedBinKey<BPI>>,
602        change_tick: Tick,
603    ) {
604        let new_cached_binned_entity = CachedBinnedEntity {
605            cached_bin_key,
606            change_tick,
607        };
608
609        let (index, old_cached_binned_entity) = self
610            .cached_entity_bin_keys
611            .insert_full(main_entity, new_cached_binned_entity.clone());
612
613        // If the entity changed bins, record its old bin so that we can remove
614        // the entity from it.
615        if let Some(old_cached_binned_entity) = old_cached_binned_entity
616            && old_cached_binned_entity.cached_bin_key != new_cached_binned_entity.cached_bin_key
617        {
618            self.entities_that_changed_bins.push(EntityThatChangedBins {
619                main_entity,
620                old_cached_binned_entity,
621            });
622        }
623
624        // Mark the entity as valid.
625        self.valid_cached_entity_bin_keys.grow_and_insert(index);
626    }
627
628    /// Encodes the GPU commands needed to render all entities in this phase.
629    pub fn render<'w>(
630        &self,
631        render_pass: &mut TrackedRenderPass<'w>,
632        world: &'w World,
633        view: Entity,
634    ) -> Result<(), DrawError> {
635        {
636            let draw_functions = world.resource::<DrawFunctions<BPI>>();
637            let mut draw_functions = draw_functions.write();
638            draw_functions.prepare(world);
639            // Make sure to drop the reader-writer lock here to avoid recursive
640            // locks.
641        }
642
643        self.render_batchable_meshes(render_pass, world, view)?;
644        self.render_unbatchable_meshes(render_pass, world, view)?;
645        self.render_non_meshes(render_pass, world, view)?;
646
647        Ok(())
648    }
649
650    /// Renders all batchable meshes queued in this phase.
651    fn render_batchable_meshes<'w>(
652        &self,
653        render_pass: &mut TrackedRenderPass<'w>,
654        world: &'w World,
655        view: Entity,
656    ) -> Result<(), DrawError> {
657        let draw_functions = world.resource::<DrawFunctions<BPI>>();
658        let mut draw_functions = draw_functions.write();
659
660        let render_device = world.resource::<RenderDevice>();
661        let render_adapter_info = world.resource::<RenderAdapterInfo>();
662        let multi_draw_indirect_count_supported = render_device
663            .features()
664            .contains(Features::MULTI_DRAW_INDIRECT_COUNT)
665            // TODO: https://github.com/gfx-rs/wgpu/issues/7974
666            && !matches!(render_adapter_info.backend, wgpu::Backend::Dx12);
667
668        match self.batch_sets {
669            BinnedRenderPhaseBatchSets::DynamicUniforms(ref batch_sets) => {
670                debug_assert_eq!(self.batchable_meshes.len(), batch_sets.len());
671
672                for ((batch_set_key, bin_key), batch_set) in
673                    self.batchable_meshes.keys().zip(batch_sets.iter())
674                {
675                    for batch in batch_set {
676                        let binned_phase_item = BPI::new(
677                            batch_set_key.clone(),
678                            bin_key.clone(),
679                            batch.representative_entity,
680                            batch.instance_range.clone(),
681                            batch.extra_index.clone(),
682                        );
683
684                        // Fetch the draw function.
685                        let Some(draw_function) =
686                            draw_functions.get_mut(binned_phase_item.draw_function())
687                        else {
688                            continue;
689                        };
690
691                        draw_function.draw(world, render_pass, view, &binned_phase_item)?;
692                    }
693                }
694            }
695
696            BinnedRenderPhaseBatchSets::Direct(ref batch_set) => {
697                for (batch, (batch_set_key, bin_key)) in
698                    batch_set.iter().zip(self.batchable_meshes.keys())
699                {
700                    let binned_phase_item = BPI::new(
701                        batch_set_key.clone(),
702                        bin_key.clone(),
703                        batch.representative_entity,
704                        batch.instance_range.clone(),
705                        batch.extra_index.clone(),
706                    );
707
708                    // Fetch the draw function.
709                    let Some(draw_function) =
710                        draw_functions.get_mut(binned_phase_item.draw_function())
711                    else {
712                        continue;
713                    };
714
715                    draw_function.draw(world, render_pass, view, &binned_phase_item)?;
716                }
717            }
718
719            BinnedRenderPhaseBatchSets::MultidrawIndirect(ref batch_sets) => {
720                for (batch_set_key, batch_set) in self
721                    .multidrawable_meshes
722                    .keys()
723                    .chain(
724                        self.batchable_meshes
725                            .keys()
726                            .map(|(batch_set_key, _)| batch_set_key),
727                    )
728                    .zip(batch_sets.iter())
729                {
730                    let batch = &batch_set.first_batch;
731
732                    let batch_set_index = if multi_draw_indirect_count_supported {
733                        NonMaxU32::new(batch_set.index)
734                    } else {
735                        None
736                    };
737
738                    let binned_phase_item = BPI::new(
739                        batch_set_key.clone(),
740                        batch_set.bin_key.clone(),
741                        batch.representative_entity,
742                        batch.instance_range.clone(),
743                        match batch.extra_index {
744                            PhaseItemExtraIndex::None => PhaseItemExtraIndex::None,
745                            PhaseItemExtraIndex::DynamicOffset(ref dynamic_offset) => {
746                                PhaseItemExtraIndex::DynamicOffset(*dynamic_offset)
747                            }
748                            PhaseItemExtraIndex::IndirectParametersIndex { ref range, .. } => {
749                                PhaseItemExtraIndex::IndirectParametersIndex {
750                                    range: range.start..(range.start + batch_set.batch_count),
751                                    batch_set_index,
752                                }
753                            }
754                        },
755                    );
756
757                    // Fetch the draw function.
758                    let Some(draw_function) =
759                        draw_functions.get_mut(binned_phase_item.draw_function())
760                    else {
761                        continue;
762                    };
763
764                    draw_function.draw(world, render_pass, view, &binned_phase_item)?;
765                }
766            }
767        }
768
769        Ok(())
770    }
771
772    /// Renders all unbatchable meshes queued in this phase.
773    fn render_unbatchable_meshes<'w>(
774        &self,
775        render_pass: &mut TrackedRenderPass<'w>,
776        world: &'w World,
777        view: Entity,
778    ) -> Result<(), DrawError> {
779        let draw_functions = world.resource::<DrawFunctions<BPI>>();
780        let mut draw_functions = draw_functions.write();
781
782        for (batch_set_key, bin_key) in self.unbatchable_meshes.keys() {
783            let unbatchable_entities =
784                &self.unbatchable_meshes[&(batch_set_key.clone(), bin_key.clone())];
785            for (entity_index, entity) in unbatchable_entities.entities.iter().enumerate() {
786                let unbatchable_dynamic_offset = match &unbatchable_entities.buffer_indices {
787                    UnbatchableBinnedEntityIndexSet::NoEntities => {
788                        // Shouldn't happen…
789                        continue;
790                    }
791                    UnbatchableBinnedEntityIndexSet::Sparse {
792                        instance_range,
793                        first_indirect_parameters_index,
794                    } => UnbatchableBinnedEntityIndices {
795                        instance_index: instance_range.start + entity_index as u32,
796                        extra_index: match first_indirect_parameters_index {
797                            None => PhaseItemExtraIndex::None,
798                            Some(first_indirect_parameters_index) => {
799                                let first_indirect_parameters_index_for_entity =
800                                    u32::from(*first_indirect_parameters_index)
801                                        + entity_index as u32;
802                                PhaseItemExtraIndex::IndirectParametersIndex {
803                                    range: first_indirect_parameters_index_for_entity
804                                        ..(first_indirect_parameters_index_for_entity + 1),
805                                    batch_set_index: None,
806                                }
807                            }
808                        },
809                    },
810                    UnbatchableBinnedEntityIndexSet::Dense(dynamic_offsets) => {
811                        dynamic_offsets[entity_index].clone()
812                    }
813                };
814
815                let binned_phase_item = BPI::new(
816                    batch_set_key.clone(),
817                    bin_key.clone(),
818                    (*entity.1, *entity.0),
819                    unbatchable_dynamic_offset.instance_index
820                        ..(unbatchable_dynamic_offset.instance_index + 1),
821                    unbatchable_dynamic_offset.extra_index,
822                );
823
824                // Fetch the draw function.
825                let Some(draw_function) = draw_functions.get_mut(binned_phase_item.draw_function())
826                else {
827                    continue;
828                };
829
830                draw_function.draw(world, render_pass, view, &binned_phase_item)?;
831            }
832        }
833        Ok(())
834    }
835
836    /// Renders all objects of type [`BinnedRenderPhaseType::NonMesh`].
837    ///
838    /// These will have been added by plugins or the application.
839    fn render_non_meshes<'w>(
840        &self,
841        render_pass: &mut TrackedRenderPass<'w>,
842        world: &'w World,
843        view: Entity,
844    ) -> Result<(), DrawError> {
845        let draw_functions = world.resource::<DrawFunctions<BPI>>();
846        let mut draw_functions = draw_functions.write();
847
848        for ((batch_set_key, bin_key), non_mesh_entities) in &self.non_mesh_items {
849            for (main_entity, entity) in non_mesh_entities.entities.iter() {
850                // Come up with a fake batch range and extra index. The draw
851                // function is expected to manage any sort of batching logic itself.
852                let binned_phase_item = BPI::new(
853                    batch_set_key.clone(),
854                    bin_key.clone(),
855                    (*entity, *main_entity),
856                    0..1,
857                    PhaseItemExtraIndex::None,
858                );
859
860                let Some(draw_function) = draw_functions.get_mut(binned_phase_item.draw_function())
861                else {
862                    continue;
863                };
864
865                draw_function.draw(world, render_pass, view, &binned_phase_item)?;
866            }
867        }
868
869        Ok(())
870    }
871
872    pub fn is_empty(&self) -> bool {
873        self.multidrawable_meshes.is_empty()
874            && self.batchable_meshes.is_empty()
875            && self.unbatchable_meshes.is_empty()
876            && self.non_mesh_items.is_empty()
877    }
878
879    pub fn prepare_for_new_frame(&mut self) {
880        self.batch_sets.clear();
881
882        self.valid_cached_entity_bin_keys.clear();
883        self.valid_cached_entity_bin_keys
884            .grow(self.cached_entity_bin_keys.len());
885        self.valid_cached_entity_bin_keys
886            .set_range(self.cached_entity_bin_keys.len().., true);
887
888        self.entities_that_changed_bins.clear();
889
890        for unbatchable_bin in self.unbatchable_meshes.values_mut() {
891            unbatchable_bin.buffer_indices.clear();
892        }
893    }
894
895    /// Checks to see whether the entity is in a bin and returns true if it's
896    /// both in a bin and up to date.
897    ///
898    /// If this function returns true, we also add the entry to the
899    /// `valid_cached_entity_bin_keys` list.
900    pub fn validate_cached_entity(
901        &mut self,
902        visible_entity: MainEntity,
903        current_change_tick: Tick,
904    ) -> bool {
905        if let indexmap::map::Entry::Occupied(entry) =
906            self.cached_entity_bin_keys.entry(visible_entity)
907            && entry.get().change_tick == current_change_tick
908        {
909            self.valid_cached_entity_bin_keys.insert(entry.index());
910            return true;
911        }
912
913        false
914    }
915
916    /// Removes all entities not marked as clean from the bins.
917    ///
918    /// During `queue_material_meshes`, we process all visible entities and mark
919    /// each as clean as we come to it. Then, in [`sweep_old_entities`], we call
920    /// this method, which removes entities that aren't marked as clean from the
921    /// bins.
922    pub fn sweep_old_entities(&mut self) {
923        // Search for entities not marked as valid. We have to do this in
924        // reverse order because `swap_remove_index` will potentially invalidate
925        // all indices after the one we remove.
926        for index in ReverseFixedBitSetZeroesIterator::new(&self.valid_cached_entity_bin_keys) {
927            let Some((entity, cached_binned_entity)) =
928                self.cached_entity_bin_keys.swap_remove_index(index)
929            else {
930                continue;
931            };
932
933            if let Some(ref cached_bin_key) = cached_binned_entity.cached_bin_key {
934                remove_entity_from_bin(
935                    entity,
936                    cached_bin_key,
937                    &mut self.multidrawable_meshes,
938                    &mut self.batchable_meshes,
939                    &mut self.unbatchable_meshes,
940                    &mut self.non_mesh_items,
941                );
942            }
943        }
944
945        // If an entity changed bins, we need to remove it from its old bin.
946        for entity_that_changed_bins in self.entities_that_changed_bins.drain(..) {
947            let Some(ref old_cached_bin_key) = entity_that_changed_bins
948                .old_cached_binned_entity
949                .cached_bin_key
950            else {
951                continue;
952            };
953            remove_entity_from_bin(
954                entity_that_changed_bins.main_entity,
955                old_cached_bin_key,
956                &mut self.multidrawable_meshes,
957                &mut self.batchable_meshes,
958                &mut self.unbatchable_meshes,
959                &mut self.non_mesh_items,
960            );
961        }
962    }
963}
964
965/// Removes an entity from a bin.
966///
967/// If this makes the bin empty, this function removes the bin as well.
968///
969/// This is a standalone function instead of a method on [`BinnedRenderPhase`]
970/// for borrow check reasons.
971fn remove_entity_from_bin<BPI>(
972    entity: MainEntity,
973    entity_bin_key: &CachedBinKey<BPI>,
974    multidrawable_meshes: &mut IndexMap<BPI::BatchSetKey, IndexMap<BPI::BinKey, RenderBin>>,
975    batchable_meshes: &mut IndexMap<(BPI::BatchSetKey, BPI::BinKey), RenderBin>,
976    unbatchable_meshes: &mut IndexMap<(BPI::BatchSetKey, BPI::BinKey), UnbatchableBinnedEntities>,
977    non_mesh_items: &mut IndexMap<(BPI::BatchSetKey, BPI::BinKey), NonMeshEntities>,
978) where
979    BPI: BinnedPhaseItem,
980{
981    match entity_bin_key.phase_type {
982        BinnedRenderPhaseType::MultidrawableMesh => {
983            if let indexmap::map::Entry::Occupied(mut batch_set_entry) =
984                multidrawable_meshes.entry(entity_bin_key.batch_set_key.clone())
985            {
986                if let indexmap::map::Entry::Occupied(mut bin_entry) = batch_set_entry
987                    .get_mut()
988                    .entry(entity_bin_key.bin_key.clone())
989                {
990                    bin_entry.get_mut().remove(entity);
991
992                    // If the bin is now empty, remove the bin.
993                    if bin_entry.get_mut().is_empty() {
994                        bin_entry.swap_remove();
995                    }
996                }
997
998                // If the batch set is now empty, remove it. This will perturb
999                // the order, but that's OK because we're going to sort the bin
1000                // afterwards.
1001                if batch_set_entry.get_mut().is_empty() {
1002                    batch_set_entry.swap_remove();
1003                }
1004            }
1005        }
1006
1007        BinnedRenderPhaseType::BatchableMesh => {
1008            if let indexmap::map::Entry::Occupied(mut bin_entry) = batchable_meshes.entry((
1009                entity_bin_key.batch_set_key.clone(),
1010                entity_bin_key.bin_key.clone(),
1011            )) {
1012                bin_entry.get_mut().remove(entity);
1013
1014                // If the bin is now empty, remove the bin.
1015                if bin_entry.get_mut().is_empty() {
1016                    bin_entry.swap_remove();
1017                }
1018            }
1019        }
1020
1021        BinnedRenderPhaseType::UnbatchableMesh => {
1022            if let indexmap::map::Entry::Occupied(mut bin_entry) = unbatchable_meshes.entry((
1023                entity_bin_key.batch_set_key.clone(),
1024                entity_bin_key.bin_key.clone(),
1025            )) {
1026                bin_entry.get_mut().entities.remove(&entity);
1027
1028                // If the bin is now empty, remove the bin.
1029                if bin_entry.get_mut().entities.is_empty() {
1030                    bin_entry.swap_remove();
1031                }
1032            }
1033        }
1034
1035        BinnedRenderPhaseType::NonMesh => {
1036            if let indexmap::map::Entry::Occupied(mut bin_entry) = non_mesh_items.entry((
1037                entity_bin_key.batch_set_key.clone(),
1038                entity_bin_key.bin_key.clone(),
1039            )) {
1040                bin_entry.get_mut().entities.remove(&entity);
1041
1042                // If the bin is now empty, remove the bin.
1043                if bin_entry.get_mut().entities.is_empty() {
1044                    bin_entry.swap_remove();
1045                }
1046            }
1047        }
1048    }
1049}
1050
1051impl<BPI> BinnedRenderPhase<BPI>
1052where
1053    BPI: BinnedPhaseItem,
1054{
1055    fn new(gpu_preprocessing: GpuPreprocessingMode) -> Self {
1056        Self {
1057            multidrawable_meshes: IndexMap::default(),
1058            batchable_meshes: IndexMap::default(),
1059            unbatchable_meshes: IndexMap::default(),
1060            non_mesh_items: IndexMap::default(),
1061            batch_sets: match gpu_preprocessing {
1062                GpuPreprocessingMode::Culling => {
1063                    BinnedRenderPhaseBatchSets::MultidrawIndirect(vec![])
1064                }
1065                GpuPreprocessingMode::PreprocessingOnly => {
1066                    BinnedRenderPhaseBatchSets::Direct(vec![])
1067                }
1068                GpuPreprocessingMode::None => BinnedRenderPhaseBatchSets::DynamicUniforms(vec![]),
1069            },
1070            cached_entity_bin_keys: IndexMap::default(),
1071            valid_cached_entity_bin_keys: FixedBitSet::new(),
1072            entities_that_changed_bins: vec![],
1073            gpu_preprocessing_mode: gpu_preprocessing,
1074        }
1075    }
1076}
1077
1078impl UnbatchableBinnedEntityIndexSet {
1079    /// Returns the [`UnbatchableBinnedEntityIndices`] for the given entity.
1080    fn indices_for_entity_index(
1081        &self,
1082        entity_index: u32,
1083    ) -> Option<UnbatchableBinnedEntityIndices> {
1084        match self {
1085            UnbatchableBinnedEntityIndexSet::NoEntities => None,
1086            UnbatchableBinnedEntityIndexSet::Sparse { instance_range, .. }
1087                if entity_index >= instance_range.len() as u32 =>
1088            {
1089                None
1090            }
1091            UnbatchableBinnedEntityIndexSet::Sparse {
1092                instance_range,
1093                first_indirect_parameters_index: None,
1094            } => Some(UnbatchableBinnedEntityIndices {
1095                instance_index: instance_range.start + entity_index,
1096                extra_index: PhaseItemExtraIndex::None,
1097            }),
1098            UnbatchableBinnedEntityIndexSet::Sparse {
1099                instance_range,
1100                first_indirect_parameters_index: Some(first_indirect_parameters_index),
1101            } => {
1102                let first_indirect_parameters_index_for_this_batch =
1103                    u32::from(*first_indirect_parameters_index) + entity_index;
1104                Some(UnbatchableBinnedEntityIndices {
1105                    instance_index: instance_range.start + entity_index,
1106                    extra_index: PhaseItemExtraIndex::IndirectParametersIndex {
1107                        range: first_indirect_parameters_index_for_this_batch
1108                            ..(first_indirect_parameters_index_for_this_batch + 1),
1109                        batch_set_index: None,
1110                    },
1111                })
1112            }
1113            UnbatchableBinnedEntityIndexSet::Dense(indices) => {
1114                indices.get(entity_index as usize).cloned()
1115            }
1116        }
1117    }
1118}
1119
1120/// A convenient abstraction for adding all the systems necessary for a binned
1121/// render phase to the render app.
1122///
1123/// This is the version used when the pipeline supports GPU preprocessing: e.g.
1124/// 3D PBR meshes.
1125pub struct BinnedRenderPhasePlugin<BPI, GFBD>
1126where
1127    BPI: BinnedPhaseItem,
1128    GFBD: GetFullBatchData,
1129{
1130    /// Debugging flags that can optionally be set when constructing the renderer.
1131    pub debug_flags: RenderDebugFlags,
1132    phantom: PhantomData<(BPI, GFBD)>,
1133}
1134
1135impl<BPI, GFBD> BinnedRenderPhasePlugin<BPI, GFBD>
1136where
1137    BPI: BinnedPhaseItem,
1138    GFBD: GetFullBatchData,
1139{
1140    pub fn new(debug_flags: RenderDebugFlags) -> Self {
1141        Self {
1142            debug_flags,
1143            phantom: PhantomData,
1144        }
1145    }
1146}
1147
1148impl<BPI, GFBD> Plugin for BinnedRenderPhasePlugin<BPI, GFBD>
1149where
1150    BPI: BinnedPhaseItem,
1151    GFBD: GetFullBatchData + Sync + Send + 'static,
1152{
1153    fn build(&self, app: &mut App) {
1154        let Some(render_app) = app.get_sub_app_mut(RenderApp) else {
1155            return;
1156        };
1157
1158        render_app
1159            .init_resource::<ViewBinnedRenderPhases<BPI>>()
1160            .init_resource::<PhaseBatchedInstanceBuffers<BPI, GFBD::BufferData>>()
1161            .insert_resource(PhaseIndirectParametersBuffers::<BPI>::new(
1162                self.debug_flags
1163                    .contains(RenderDebugFlags::ALLOW_COPIES_FROM_INDIRECT_PARAMETERS),
1164            ))
1165            .add_systems(
1166                Render,
1167                (
1168                    batching::sort_binned_render_phase::<BPI>.in_set(RenderSystems::PhaseSort),
1169                    (
1170                        no_gpu_preprocessing::batch_and_prepare_binned_render_phase::<BPI, GFBD>
1171                            .run_if(resource_exists::<BatchedInstanceBuffer<GFBD::BufferData>>),
1172                        gpu_preprocessing::batch_and_prepare_binned_render_phase::<BPI, GFBD>
1173                            .run_if(
1174                                resource_exists::<
1175                                    BatchedInstanceBuffers<GFBD::BufferData, GFBD::BufferInputData>,
1176                                >,
1177                            ),
1178                    )
1179                        .in_set(RenderSystems::PrepareResources),
1180                    sweep_old_entities::<BPI>.in_set(RenderSystems::QueueSweep),
1181                    gpu_preprocessing::collect_buffers_for_phase::<BPI, GFBD>
1182                        .run_if(
1183                            resource_exists::<
1184                                BatchedInstanceBuffers<GFBD::BufferData, GFBD::BufferInputData>,
1185                            >,
1186                        )
1187                        .in_set(RenderSystems::PrepareResourcesCollectPhaseBuffers),
1188                ),
1189            );
1190    }
1191}
1192
1193/// Stores the rendering instructions for a single phase that sorts items in all
1194/// views.
1195///
1196/// They're cleared out every frame, but storing them in a resource like this
1197/// allows us to reuse allocations.
1198#[derive(Resource, Deref, DerefMut)]
1199pub struct ViewSortedRenderPhases<SPI>(pub HashMap<RetainedViewEntity, SortedRenderPhase<SPI>>)
1200where
1201    SPI: SortedPhaseItem;
1202
1203impl<SPI> Default for ViewSortedRenderPhases<SPI>
1204where
1205    SPI: SortedPhaseItem,
1206{
1207    fn default() -> Self {
1208        Self(default())
1209    }
1210}
1211
1212impl<SPI> ViewSortedRenderPhases<SPI>
1213where
1214    SPI: SortedPhaseItem,
1215{
1216    pub fn insert_or_clear(&mut self, retained_view_entity: RetainedViewEntity) {
1217        match self.entry(retained_view_entity) {
1218            Entry::Occupied(mut entry) => entry.get_mut().clear(),
1219            Entry::Vacant(entry) => {
1220                entry.insert(default());
1221            }
1222        }
1223    }
1224}
1225
1226/// A convenient abstraction for adding all the systems necessary for a sorted
1227/// render phase to the render app.
1228///
1229/// This is the version used when the pipeline supports GPU preprocessing: e.g.
1230/// 3D PBR meshes.
1231pub struct SortedRenderPhasePlugin<SPI, GFBD>
1232where
1233    SPI: SortedPhaseItem,
1234    GFBD: GetFullBatchData,
1235{
1236    /// Debugging flags that can optionally be set when constructing the renderer.
1237    pub debug_flags: RenderDebugFlags,
1238    phantom: PhantomData<(SPI, GFBD)>,
1239}
1240
1241impl<SPI, GFBD> SortedRenderPhasePlugin<SPI, GFBD>
1242where
1243    SPI: SortedPhaseItem,
1244    GFBD: GetFullBatchData,
1245{
1246    pub fn new(debug_flags: RenderDebugFlags) -> Self {
1247        Self {
1248            debug_flags,
1249            phantom: PhantomData,
1250        }
1251    }
1252}
1253
1254impl<SPI, GFBD> Plugin for SortedRenderPhasePlugin<SPI, GFBD>
1255where
1256    SPI: SortedPhaseItem + CachedRenderPipelinePhaseItem,
1257    GFBD: GetFullBatchData + Sync + Send + 'static,
1258{
1259    fn build(&self, app: &mut App) {
1260        let Some(render_app) = app.get_sub_app_mut(RenderApp) else {
1261            return;
1262        };
1263
1264        render_app
1265            .init_resource::<ViewSortedRenderPhases<SPI>>()
1266            .init_resource::<PhaseBatchedInstanceBuffers<SPI, GFBD::BufferData>>()
1267            .insert_resource(PhaseIndirectParametersBuffers::<SPI>::new(
1268                self.debug_flags
1269                    .contains(RenderDebugFlags::ALLOW_COPIES_FROM_INDIRECT_PARAMETERS),
1270            ))
1271            .add_systems(
1272                Render,
1273                (
1274                    (
1275                        no_gpu_preprocessing::batch_and_prepare_sorted_render_phase::<SPI, GFBD>
1276                            .run_if(resource_exists::<BatchedInstanceBuffer<GFBD::BufferData>>),
1277                        gpu_preprocessing::batch_and_prepare_sorted_render_phase::<SPI, GFBD>
1278                            .run_if(
1279                                resource_exists::<
1280                                    BatchedInstanceBuffers<GFBD::BufferData, GFBD::BufferInputData>,
1281                                >,
1282                            ),
1283                    )
1284                        .in_set(RenderSystems::PrepareResources),
1285                    gpu_preprocessing::collect_buffers_for_phase::<SPI, GFBD>
1286                        .run_if(
1287                            resource_exists::<
1288                                BatchedInstanceBuffers<GFBD::BufferData, GFBD::BufferInputData>,
1289                            >,
1290                        )
1291                        .in_set(RenderSystems::PrepareResourcesCollectPhaseBuffers),
1292                ),
1293            );
1294    }
1295}
1296
1297impl UnbatchableBinnedEntityIndexSet {
1298    /// Adds a new entity to the list of unbatchable binned entities.
1299    pub fn add(&mut self, indices: UnbatchableBinnedEntityIndices) {
1300        match self {
1301            UnbatchableBinnedEntityIndexSet::NoEntities => {
1302                match indices.extra_index {
1303                    PhaseItemExtraIndex::DynamicOffset(_) => {
1304                        // This is the first entity we've seen, and we don't have
1305                        // compute shaders. Initialize an array.
1306                        *self = UnbatchableBinnedEntityIndexSet::Dense(vec![indices]);
1307                    }
1308                    PhaseItemExtraIndex::None => {
1309                        // This is the first entity we've seen, and we have compute
1310                        // shaders. Initialize the fast path.
1311                        *self = UnbatchableBinnedEntityIndexSet::Sparse {
1312                            instance_range: indices.instance_index..indices.instance_index + 1,
1313                            first_indirect_parameters_index: None,
1314                        }
1315                    }
1316                    PhaseItemExtraIndex::IndirectParametersIndex {
1317                        range: ref indirect_parameters_index,
1318                        ..
1319                    } => {
1320                        // This is the first entity we've seen, and we have compute
1321                        // shaders. Initialize the fast path.
1322                        *self = UnbatchableBinnedEntityIndexSet::Sparse {
1323                            instance_range: indices.instance_index..indices.instance_index + 1,
1324                            first_indirect_parameters_index: NonMaxU32::new(
1325                                indirect_parameters_index.start,
1326                            ),
1327                        }
1328                    }
1329                }
1330            }
1331
1332            UnbatchableBinnedEntityIndexSet::Sparse {
1333                instance_range,
1334                first_indirect_parameters_index,
1335            } if instance_range.end == indices.instance_index
1336                && ((first_indirect_parameters_index.is_none()
1337                    && indices.extra_index == PhaseItemExtraIndex::None)
1338                    || first_indirect_parameters_index.is_some_and(
1339                        |first_indirect_parameters_index| match indices.extra_index {
1340                            PhaseItemExtraIndex::IndirectParametersIndex {
1341                                range: ref this_range,
1342                                ..
1343                            } => {
1344                                u32::from(first_indirect_parameters_index) + instance_range.end
1345                                    - instance_range.start
1346                                    == this_range.start
1347                            }
1348                            PhaseItemExtraIndex::DynamicOffset(_) | PhaseItemExtraIndex::None => {
1349                                false
1350                            }
1351                        },
1352                    )) =>
1353            {
1354                // This is the normal case on non-WebGL 2.
1355                instance_range.end += 1;
1356            }
1357
1358            UnbatchableBinnedEntityIndexSet::Sparse { instance_range, .. } => {
1359                // We thought we were in non-WebGL 2 mode, but we got a dynamic
1360                // offset or non-contiguous index anyway. This shouldn't happen,
1361                // but let's go ahead and do the sensible thing anyhow: demote
1362                // the compressed `NoDynamicOffsets` field to the full
1363                // `DynamicOffsets` array.
1364                warn!(
1365                    "Unbatchable binned entity index set was demoted from sparse to dense. \
1366                    This is a bug in the renderer. Please report it.",
1367                );
1368                let new_dynamic_offsets = (0..instance_range.len() as u32)
1369                    .flat_map(|entity_index| self.indices_for_entity_index(entity_index))
1370                    .chain(iter::once(indices))
1371                    .collect();
1372                *self = UnbatchableBinnedEntityIndexSet::Dense(new_dynamic_offsets);
1373            }
1374
1375            UnbatchableBinnedEntityIndexSet::Dense(dense_indices) => {
1376                dense_indices.push(indices);
1377            }
1378        }
1379    }
1380
1381    /// Clears the unbatchable binned entity index set.
1382    fn clear(&mut self) {
1383        match self {
1384            UnbatchableBinnedEntityIndexSet::Dense(dense_indices) => dense_indices.clear(),
1385            UnbatchableBinnedEntityIndexSet::Sparse { .. } => {
1386                *self = UnbatchableBinnedEntityIndexSet::NoEntities;
1387            }
1388            _ => {}
1389        }
1390    }
1391}
1392
1393/// A collection of all items to be rendered that will be encoded to GPU
1394/// commands for a single render phase for a single view.
1395///
1396/// Each view (camera, or shadow-casting light, etc.) can have one or multiple render phases.
1397/// They are used to queue entities for rendering.
1398/// Multiple phases might be required due to different sorting/batching behaviors
1399/// (e.g. opaque: front to back, transparent: back to front) or because one phase depends on
1400/// the rendered texture of the previous phase (e.g. for screen-space reflections).
1401/// All [`PhaseItem`]s are then rendered using a single [`TrackedRenderPass`].
1402/// The render pass might be reused for multiple phases to reduce GPU overhead.
1403///
1404/// This flavor of render phase is used only for meshes that need to be sorted
1405/// back-to-front, such as transparent meshes. For items that don't need strict
1406/// sorting, [`BinnedRenderPhase`] is preferred, for performance.
1407pub struct SortedRenderPhase<I>
1408where
1409    I: SortedPhaseItem,
1410{
1411    /// The items within this [`SortedRenderPhase`].
1412    pub items: Vec<I>,
1413}
1414
1415impl<I> Default for SortedRenderPhase<I>
1416where
1417    I: SortedPhaseItem,
1418{
1419    fn default() -> Self {
1420        Self { items: Vec::new() }
1421    }
1422}
1423
1424impl<I> SortedRenderPhase<I>
1425where
1426    I: SortedPhaseItem,
1427{
1428    /// Adds a [`PhaseItem`] to this render phase.
1429    #[inline]
1430    pub fn add(&mut self, item: I) {
1431        self.items.push(item);
1432    }
1433
1434    /// Removes all [`PhaseItem`]s from this render phase.
1435    #[inline]
1436    pub fn clear(&mut self) {
1437        self.items.clear();
1438    }
1439
1440    /// Sorts all of its [`PhaseItem`]s.
1441    pub fn sort(&mut self) {
1442        I::sort(&mut self.items);
1443    }
1444
1445    /// An [`Iterator`] through the associated [`Entity`] for each [`PhaseItem`] in order.
1446    #[inline]
1447    pub fn iter_entities(&'_ self) -> impl Iterator<Item = Entity> + '_ {
1448        self.items.iter().map(PhaseItem::entity)
1449    }
1450
1451    /// Renders all of its [`PhaseItem`]s using their corresponding draw functions.
1452    pub fn render<'w>(
1453        &self,
1454        render_pass: &mut TrackedRenderPass<'w>,
1455        world: &'w World,
1456        view: Entity,
1457    ) -> Result<(), DrawError> {
1458        self.render_range(render_pass, world, view, ..)
1459    }
1460
1461    /// Renders all [`PhaseItem`]s in the provided `range` (based on their index in `self.items`) using their corresponding draw functions.
1462    pub fn render_range<'w>(
1463        &self,
1464        render_pass: &mut TrackedRenderPass<'w>,
1465        world: &'w World,
1466        view: Entity,
1467        range: impl SliceIndex<[I], Output = [I]>,
1468    ) -> Result<(), DrawError> {
1469        let items = self
1470            .items
1471            .get(range)
1472            .expect("`Range` provided to `render_range()` is out of bounds");
1473
1474        let draw_functions = world.resource::<DrawFunctions<I>>();
1475        let mut draw_functions = draw_functions.write();
1476        draw_functions.prepare(world);
1477
1478        let mut index = 0;
1479        while index < items.len() {
1480            let item = &items[index];
1481            let batch_range = item.batch_range();
1482            if batch_range.is_empty() {
1483                index += 1;
1484            } else {
1485                let draw_function = draw_functions.get_mut(item.draw_function()).unwrap();
1486                draw_function.draw(world, render_pass, view, item)?;
1487                index += batch_range.len();
1488            }
1489        }
1490        Ok(())
1491    }
1492}
1493
1494/// An item (entity of the render world) which will be drawn to a texture or the screen,
1495/// as part of a render phase.
1496///
1497/// The data required for rendering an entity is extracted from the main world in the
1498/// [`ExtractSchedule`](crate::ExtractSchedule).
1499/// Then it has to be queued up for rendering during the [`RenderSystems::Queue`],
1500/// by adding a corresponding phase item to a render phase.
1501/// Afterwards it will be possibly sorted and rendered automatically in the
1502/// [`RenderSystems::PhaseSort`] and [`RenderSystems::Render`], respectively.
1503///
1504/// `PhaseItem`s come in two flavors: [`BinnedPhaseItem`]s and
1505/// [`SortedPhaseItem`]s.
1506///
1507/// * Binned phase items have a `BinKey` which specifies what bin they're to be
1508///   placed in. All items in the same bin are eligible to be batched together.
1509///   The `BinKey`s are sorted, but the individual bin items aren't. Binned phase
1510///   items are good for opaque meshes, in which the order of rendering isn't
1511///   important. Generally, binned phase items are faster than sorted phase items.
1512///
1513/// * Sorted phase items, on the other hand, are placed into one large buffer
1514///   and then sorted all at once. This is needed for transparent meshes, which
1515///   have to be sorted back-to-front to render with the painter's algorithm.
1516///   These types of phase items are generally slower than binned phase items.
1517pub trait PhaseItem: Sized + Send + Sync + 'static {
1518    /// Whether or not this `PhaseItem` should be subjected to automatic batching. (Default: `true`)
1519    const AUTOMATIC_BATCHING: bool = true;
1520
1521    /// The corresponding entity that will be drawn.
1522    ///
1523    /// This is used to fetch the render data of the entity, required by the draw function,
1524    /// from the render world .
1525    fn entity(&self) -> Entity;
1526
1527    /// The main world entity represented by this `PhaseItem`.
1528    fn main_entity(&self) -> MainEntity;
1529
1530    /// Specifies the [`Draw`] function used to render the item.
1531    fn draw_function(&self) -> DrawFunctionId;
1532
1533    /// The range of instances that the batch covers. After doing a batched draw, batch range
1534    /// length phase items will be skipped. This design is to avoid having to restructure the
1535    /// render phase unnecessarily.
1536    fn batch_range(&self) -> &Range<u32>;
1537    fn batch_range_mut(&mut self) -> &mut Range<u32>;
1538
1539    /// Returns the [`PhaseItemExtraIndex`].
1540    ///
1541    /// If present, this is either a dynamic offset or an indirect parameters
1542    /// index.
1543    fn extra_index(&self) -> PhaseItemExtraIndex;
1544
1545    /// Returns a pair of mutable references to both the batch range and extra
1546    /// index.
1547    fn batch_range_and_extra_index_mut(&mut self) -> (&mut Range<u32>, &mut PhaseItemExtraIndex);
1548}
1549
1550/// The "extra index" associated with some [`PhaseItem`]s, alongside the
1551/// indirect instance index.
1552///
1553/// Sometimes phase items require another index in addition to the range of
1554/// instances they already have. These can be:
1555///
1556/// * The *dynamic offset*: a `wgpu` dynamic offset into the uniform buffer of
1557///   instance data. This is used on platforms that don't support storage
1558///   buffers, to work around uniform buffer size limitations.
1559///
1560/// * The *indirect parameters index*: an index into the buffer that specifies
1561///   the indirect parameters for this [`PhaseItem`]'s drawcall. This is used when
1562///   indirect mode is on (as used for GPU culling).
1563///
1564/// Note that our indirect draw functionality requires storage buffers, so it's
1565/// impossible to have both a dynamic offset and an indirect parameters index.
1566/// This convenient fact allows us to pack both indices into a single `u32`.
1567#[derive(Clone, PartialEq, Eq, Hash, Debug)]
1568pub enum PhaseItemExtraIndex {
1569    /// No extra index is present.
1570    None,
1571    /// A `wgpu` dynamic offset into the uniform buffer of instance data. This
1572    /// is used on platforms that don't support storage buffers, to work around
1573    /// uniform buffer size limitations.
1574    DynamicOffset(u32),
1575    /// An index into the buffer that specifies the indirect parameters for this
1576    /// [`PhaseItem`]'s drawcall. This is used when indirect mode is on (as used
1577    /// for GPU culling).
1578    IndirectParametersIndex {
1579        /// The range of indirect parameters within the indirect parameters array.
1580        ///
1581        /// If we're using `multi_draw_indirect_count`, this specifies the
1582        /// maximum range of indirect parameters within that array. If batches
1583        /// are ultimately culled out on the GPU, the actual number of draw
1584        /// commands might be lower than the length of this range.
1585        range: Range<u32>,
1586        /// If `multi_draw_indirect_count` is in use, and this phase item is
1587        /// part of a batch set, specifies the index of the batch set that this
1588        /// phase item is a part of.
1589        ///
1590        /// If `multi_draw_indirect_count` isn't in use, or this phase item
1591        /// isn't part of a batch set, this is `None`.
1592        batch_set_index: Option<NonMaxU32>,
1593    },
1594}
1595
1596impl PhaseItemExtraIndex {
1597    /// Returns either an indirect parameters index or
1598    /// [`PhaseItemExtraIndex::None`], as appropriate.
1599    pub fn maybe_indirect_parameters_index(
1600        indirect_parameters_index: Option<NonMaxU32>,
1601    ) -> PhaseItemExtraIndex {
1602        match indirect_parameters_index {
1603            Some(indirect_parameters_index) => PhaseItemExtraIndex::IndirectParametersIndex {
1604                range: u32::from(indirect_parameters_index)
1605                    ..(u32::from(indirect_parameters_index) + 1),
1606                batch_set_index: None,
1607            },
1608            None => PhaseItemExtraIndex::None,
1609        }
1610    }
1611
1612    /// Returns either a dynamic offset index or [`PhaseItemExtraIndex::None`],
1613    /// as appropriate.
1614    pub fn maybe_dynamic_offset(dynamic_offset: Option<NonMaxU32>) -> PhaseItemExtraIndex {
1615        match dynamic_offset {
1616            Some(dynamic_offset) => PhaseItemExtraIndex::DynamicOffset(dynamic_offset.into()),
1617            None => PhaseItemExtraIndex::None,
1618        }
1619    }
1620}
1621
1622/// Represents phase items that are placed into bins. The `BinKey` specifies
1623/// which bin they're to be placed in. Bin keys are sorted, and items within the
1624/// same bin are eligible to be batched together. The elements within the bins
1625/// aren't themselves sorted.
1626///
1627/// An example of a binned phase item is `Opaque3d`, for which the rendering
1628/// order isn't critical.
1629pub trait BinnedPhaseItem: PhaseItem {
1630    /// The key used for binning [`PhaseItem`]s into bins. Order the members of
1631    /// [`BinnedPhaseItem::BinKey`] by the order of binding for best
1632    /// performance. For example, pipeline id, draw function id, mesh asset id,
1633    /// lowest variable bind group id such as the material bind group id, and
1634    /// its dynamic offsets if any, next bind group and offsets, etc. This
1635    /// reduces the need for rebinding between bins and improves performance.
1636    type BinKey: Clone + Send + Sync + PartialEq + Eq + Ord + Hash;
1637
1638    /// The key used to combine batches into batch sets.
1639    ///
1640    /// A *batch set* is a set of meshes that can potentially be multi-drawn
1641    /// together.
1642    type BatchSetKey: PhaseItemBatchSetKey;
1643
1644    /// Creates a new binned phase item from the key and per-entity data.
1645    ///
1646    /// Unlike [`SortedPhaseItem`]s, this is generally called "just in time"
1647    /// before rendering. The resulting phase item isn't stored in any data
1648    /// structures, resulting in significant memory savings.
1649    fn new(
1650        batch_set_key: Self::BatchSetKey,
1651        bin_key: Self::BinKey,
1652        representative_entity: (Entity, MainEntity),
1653        batch_range: Range<u32>,
1654        extra_index: PhaseItemExtraIndex,
1655    ) -> Self;
1656}
1657
1658/// A key used to combine batches into batch sets.
1659///
1660/// A *batch set* is a set of meshes that can potentially be multi-drawn
1661/// together.
1662pub trait PhaseItemBatchSetKey: Clone + Send + Sync + PartialEq + Eq + Ord + Hash {
1663    /// Returns true if this batch set key describes indexed meshes or false if
1664    /// it describes non-indexed meshes.
1665    ///
1666    /// Bevy uses this in order to determine which kind of indirect draw
1667    /// parameters to use, if indirect drawing is enabled.
1668    fn indexed(&self) -> bool;
1669}
1670
1671/// Represents phase items that must be sorted. The `SortKey` specifies the
1672/// order that these items are drawn in. These are placed into a single array,
1673/// and the array as a whole is then sorted.
1674///
1675/// An example of a sorted phase item is `Transparent3d`, which must be sorted
1676/// back to front in order to correctly render with the painter's algorithm.
1677pub trait SortedPhaseItem: PhaseItem {
1678    /// The type used for ordering the items. The smallest values are drawn first.
1679    /// This order can be calculated using the [`ViewRangefinder3d`],
1680    /// based on the view-space `Z` value of the corresponding view matrix.
1681    type SortKey: Ord;
1682
1683    /// Determines the order in which the items are drawn.
1684    fn sort_key(&self) -> Self::SortKey;
1685
1686    /// Sorts a slice of phase items into render order. Generally if the same type
1687    /// is batched this should use a stable sort like [`slice::sort_by_key`].
1688    /// In almost all other cases, this should not be altered from the default,
1689    /// which uses an unstable sort, as this provides the best balance of CPU and GPU
1690    /// performance.
1691    ///
1692    /// Implementers can optionally not sort the list at all. This is generally advisable if and
1693    /// only if the renderer supports a depth prepass, which is by default not supported by
1694    /// the rest of Bevy's first party rendering crates. Even then, this may have a negative
1695    /// impact on GPU-side performance due to overdraw.
1696    ///
1697    /// It's advised to always profile for performance changes when changing this implementation.
1698    #[inline]
1699    fn sort(items: &mut [Self]) {
1700        items.sort_unstable_by_key(Self::sort_key);
1701    }
1702
1703    /// Whether this phase item targets indexed meshes (those with both vertex
1704    /// and index buffers as opposed to just vertex buffers).
1705    ///
1706    /// Bevy needs this information in order to properly group phase items
1707    /// together for multi-draw indirect, because the GPU layout of indirect
1708    /// commands differs between indexed and non-indexed meshes.
1709    ///
1710    /// If you're implementing a custom phase item that doesn't describe a mesh,
1711    /// you can safely return false here.
1712    fn indexed(&self) -> bool;
1713}
1714
1715/// A [`PhaseItem`] item, that automatically sets the appropriate render pipeline,
1716/// cached in the [`PipelineCache`].
1717///
1718/// You can use the [`SetItemPipeline`] render command to set the pipeline for this item.
1719pub trait CachedRenderPipelinePhaseItem: PhaseItem {
1720    /// The id of the render pipeline, cached in the [`PipelineCache`], that will be used to draw
1721    /// this phase item.
1722    fn cached_pipeline(&self) -> CachedRenderPipelineId;
1723}
1724
1725/// A [`RenderCommand`] that sets the pipeline for the [`CachedRenderPipelinePhaseItem`].
1726pub struct SetItemPipeline;
1727
1728impl<P: CachedRenderPipelinePhaseItem> RenderCommand<P> for SetItemPipeline {
1729    type Param = SRes<PipelineCache>;
1730    type ViewQuery = ();
1731    type ItemQuery = ();
1732    #[inline]
1733    fn render<'w>(
1734        item: &P,
1735        _view: (),
1736        _entity: Option<()>,
1737        pipeline_cache: SystemParamItem<'w, '_, Self::Param>,
1738        pass: &mut TrackedRenderPass<'w>,
1739    ) -> RenderCommandResult {
1740        if let Some(pipeline) = pipeline_cache
1741            .into_inner()
1742            .get_render_pipeline(item.cached_pipeline())
1743        {
1744            pass.set_render_pipeline(pipeline);
1745            RenderCommandResult::Success
1746        } else {
1747            RenderCommandResult::Skip
1748        }
1749    }
1750}
1751
1752/// This system sorts the [`PhaseItem`]s of all [`SortedRenderPhase`]s of this
1753/// type.
1754pub fn sort_phase_system<I>(mut render_phases: ResMut<ViewSortedRenderPhases<I>>)
1755where
1756    I: SortedPhaseItem,
1757{
1758    for phase in render_phases.values_mut() {
1759        phase.sort();
1760    }
1761}
1762
1763/// Removes entities that became invisible or changed phases from the bins.
1764///
1765/// This must run after queuing.
1766pub fn sweep_old_entities<BPI>(mut render_phases: ResMut<ViewBinnedRenderPhases<BPI>>)
1767where
1768    BPI: BinnedPhaseItem,
1769{
1770    for phase in render_phases.0.values_mut() {
1771        phase.sweep_old_entities();
1772    }
1773}
1774
1775impl BinnedRenderPhaseType {
1776    pub fn mesh(
1777        batchable: bool,
1778        gpu_preprocessing_support: &GpuPreprocessingSupport,
1779    ) -> BinnedRenderPhaseType {
1780        match (batchable, gpu_preprocessing_support.max_supported_mode) {
1781            (true, GpuPreprocessingMode::Culling) => BinnedRenderPhaseType::MultidrawableMesh,
1782            (true, _) => BinnedRenderPhaseType::BatchableMesh,
1783            (false, _) => BinnedRenderPhaseType::UnbatchableMesh,
1784        }
1785    }
1786}
1787
1788impl RenderBin {
1789    /// Creates a [`RenderBin`] containing a single entity.
1790    fn from_entity(entity: MainEntity, uniform_index: InputUniformIndex) -> RenderBin {
1791        let mut entities = IndexMap::default();
1792        entities.insert(entity, uniform_index);
1793        RenderBin { entities }
1794    }
1795
1796    /// Inserts an entity into the bin.
1797    fn insert(&mut self, entity: MainEntity, uniform_index: InputUniformIndex) {
1798        self.entities.insert(entity, uniform_index);
1799    }
1800
1801    /// Removes an entity from the bin.
1802    fn remove(&mut self, entity_to_remove: MainEntity) {
1803        self.entities.swap_remove(&entity_to_remove);
1804    }
1805
1806    /// Returns true if the bin contains no entities.
1807    fn is_empty(&self) -> bool {
1808        self.entities.is_empty()
1809    }
1810
1811    /// Returns the [`IndexMap`] containing all the entities in the bin, along
1812    /// with the cached [`InputUniformIndex`] of each.
1813    #[inline]
1814    pub fn entities(&self) -> &IndexMap<MainEntity, InputUniformIndex, EntityHash> {
1815        &self.entities
1816    }
1817}
1818
1819/// An iterator that efficiently finds the indices of all zero bits in a
1820/// [`FixedBitSet`] and returns them in reverse order.
1821///
1822/// [`FixedBitSet`] doesn't natively offer this functionality, so we have to
1823/// implement it ourselves.
1824#[derive(Debug)]
1825struct ReverseFixedBitSetZeroesIterator<'a> {
1826    /// The bit set.
1827    bitset: &'a FixedBitSet,
1828    /// The next bit index we're going to scan when [`Iterator::next`] is
1829    /// called.
1830    bit_index: isize,
1831}
1832
1833impl<'a> ReverseFixedBitSetZeroesIterator<'a> {
1834    fn new(bitset: &'a FixedBitSet) -> ReverseFixedBitSetZeroesIterator<'a> {
1835        ReverseFixedBitSetZeroesIterator {
1836            bitset,
1837            bit_index: (bitset.len() as isize) - 1,
1838        }
1839    }
1840}
1841
1842impl<'a> Iterator for ReverseFixedBitSetZeroesIterator<'a> {
1843    type Item = usize;
1844
1845    fn next(&mut self) -> Option<usize> {
1846        while self.bit_index >= 0 {
1847            // Unpack the bit index into block and bit.
1848            let block_index = self.bit_index / (Block::BITS as isize);
1849            let bit_pos = self.bit_index % (Block::BITS as isize);
1850
1851            // Grab the block. Mask off all bits above the one we're scanning
1852            // from by setting them all to 1.
1853            let mut block = self.bitset.as_slice()[block_index as usize];
1854            if bit_pos + 1 < (Block::BITS as isize) {
1855                block |= (!0) << (bit_pos + 1);
1856            }
1857
1858            // Search for the next unset bit. Note that the `leading_ones`
1859            // function counts from the MSB to the LSB, so we need to flip it to
1860            // get the bit number.
1861            let pos = (Block::BITS as isize) - (block.leading_ones() as isize) - 1;
1862
1863            // If we found an unset bit, return it.
1864            if pos != -1 {
1865                let result = block_index * (Block::BITS as isize) + pos;
1866                self.bit_index = result - 1;
1867                return Some(result as usize);
1868            }
1869
1870            // Otherwise, go to the previous block.
1871            self.bit_index = block_index * (Block::BITS as isize) - 1;
1872        }
1873
1874        None
1875    }
1876}
1877
1878#[cfg(test)]
1879mod test {
1880    use super::ReverseFixedBitSetZeroesIterator;
1881    use fixedbitset::FixedBitSet;
1882    use proptest::{collection::vec, prop_assert_eq, proptest};
1883
1884    proptest! {
1885        #[test]
1886        fn reverse_fixed_bit_set_zeroes_iterator(
1887            bits in vec(0usize..1024usize, 0usize..1024usize),
1888            size in 0usize..1024usize,
1889        ) {
1890            // Build a random bit set.
1891            let mut bitset = FixedBitSet::new();
1892            bitset.grow(size);
1893            for bit in bits {
1894                if bit < size {
1895                    bitset.set(bit, true);
1896                }
1897            }
1898
1899            // Iterate over the bit set backwards in a naive way, and check that
1900            // that iteration sequence corresponds to the optimized one.
1901            let mut iter = ReverseFixedBitSetZeroesIterator::new(&bitset);
1902            for bit_index in (0..size).rev() {
1903                if !bitset.contains(bit_index) {
1904                    prop_assert_eq!(iter.next(), Some(bit_index));
1905                }
1906            }
1907
1908            prop_assert_eq!(iter.next(), None);
1909        }
1910    }
1911}