bevy_ecs/schedule/
schedule.rs

1use std::{
2    collections::BTreeSet,
3    fmt::{Debug, Write},
4};
5
6#[cfg(feature = "trace")]
7use bevy_utils::tracing::info_span;
8use bevy_utils::{default, tracing::info};
9use bevy_utils::{
10    tracing::{error, warn},
11    HashMap, HashSet,
12};
13use fixedbitset::FixedBitSet;
14use petgraph::{algo::TarjanScc, prelude::*};
15use thiserror::Error;
16
17use crate::{
18    self as bevy_ecs,
19    component::{ComponentId, Components, Tick},
20    prelude::Component,
21    schedule::*,
22    system::{BoxedSystem, IntoSystem, Resource, System},
23    world::World,
24};
25
26pub use stepping::Stepping;
27
28/// Resource that stores [`Schedule`]s mapped to [`ScheduleLabel`]s excluding the current running [`Schedule`].
29#[derive(Default, Resource)]
30pub struct Schedules {
31    inner: HashMap<InternedScheduleLabel, Schedule>,
32    /// List of [`ComponentId`]s to ignore when reporting system order ambiguity conflicts
33    pub ignored_scheduling_ambiguities: BTreeSet<ComponentId>,
34}
35
36impl Schedules {
37    /// Constructs an empty `Schedules` with zero initial capacity.
38    pub fn new() -> Self {
39        Self {
40            inner: HashMap::new(),
41            ignored_scheduling_ambiguities: BTreeSet::new(),
42        }
43    }
44
45    /// Inserts a labeled schedule into the map.
46    ///
47    /// If the map already had an entry for `label`, `schedule` is inserted,
48    /// and the old schedule is returned. Otherwise, `None` is returned.
49    pub fn insert(&mut self, schedule: Schedule) -> Option<Schedule> {
50        self.inner.insert(schedule.label, schedule)
51    }
52
53    /// Removes the schedule corresponding to the `label` from the map, returning it if it existed.
54    pub fn remove(&mut self, label: impl ScheduleLabel) -> Option<Schedule> {
55        self.inner.remove(&label.intern())
56    }
57
58    /// Removes the (schedule, label) pair corresponding to the `label` from the map, returning it if it existed.
59    pub fn remove_entry(
60        &mut self,
61        label: impl ScheduleLabel,
62    ) -> Option<(InternedScheduleLabel, Schedule)> {
63        self.inner.remove_entry(&label.intern())
64    }
65
66    /// Does a schedule with the provided label already exist?
67    pub fn contains(&self, label: impl ScheduleLabel) -> bool {
68        self.inner.contains_key(&label.intern())
69    }
70
71    /// Returns a reference to the schedule associated with `label`, if it exists.
72    pub fn get(&self, label: impl ScheduleLabel) -> Option<&Schedule> {
73        self.inner.get(&label.intern())
74    }
75
76    /// Returns a mutable reference to the schedule associated with `label`, if it exists.
77    pub fn get_mut(&mut self, label: impl ScheduleLabel) -> Option<&mut Schedule> {
78        self.inner.get_mut(&label.intern())
79    }
80
81    /// Returns a mutable reference to the schedules associated with `label`, creating one if it doesn't already exist.
82    pub fn entry(&mut self, label: impl ScheduleLabel) -> &mut Schedule {
83        self.inner
84            .entry(label.intern())
85            .or_insert_with(|| Schedule::new(label))
86    }
87
88    /// Returns an iterator over all schedules. Iteration order is undefined.
89    pub fn iter(&self) -> impl Iterator<Item = (&dyn ScheduleLabel, &Schedule)> {
90        self.inner
91            .iter()
92            .map(|(label, schedule)| (&**label, schedule))
93    }
94    /// Returns an iterator over mutable references to all schedules. Iteration order is undefined.
95    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&dyn ScheduleLabel, &mut Schedule)> {
96        self.inner
97            .iter_mut()
98            .map(|(label, schedule)| (&**label, schedule))
99    }
100
101    /// Iterates the change ticks of all systems in all stored schedules and clamps any older than
102    /// [`MAX_CHANGE_AGE`](crate::change_detection::MAX_CHANGE_AGE).
103    /// This prevents overflow and thus prevents false positives.
104    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
105        #[cfg(feature = "trace")]
106        let _all_span = info_span!("check stored schedule ticks").entered();
107        // label used when trace feature is enabled
108        #[allow(unused_variables)]
109        for (label, schedule) in &mut self.inner {
110            #[cfg(feature = "trace")]
111            let name = format!("{label:?}");
112            #[cfg(feature = "trace")]
113            let _one_span = info_span!("check schedule ticks", name = &name).entered();
114            schedule.check_change_ticks(change_tick);
115        }
116    }
117
118    /// Applies the provided [`ScheduleBuildSettings`] to all schedules.
119    pub fn configure_schedules(&mut self, schedule_build_settings: ScheduleBuildSettings) {
120        for (_, schedule) in &mut self.inner {
121            schedule.set_build_settings(schedule_build_settings.clone());
122        }
123    }
124
125    /// Ignore system order ambiguities caused by conflicts on [`Component`]s of type `T`.
126    pub fn allow_ambiguous_component<T: Component>(&mut self, world: &mut World) {
127        self.ignored_scheduling_ambiguities
128            .insert(world.init_component::<T>());
129    }
130
131    /// Ignore system order ambiguities caused by conflicts on [`Resource`]s of type `T`.
132    pub fn allow_ambiguous_resource<T: Resource>(&mut self, world: &mut World) {
133        self.ignored_scheduling_ambiguities
134            .insert(world.components.init_resource::<T>());
135    }
136
137    /// Iterate through the [`ComponentId`]'s that will be ignored.
138    pub fn iter_ignored_ambiguities(&self) -> impl Iterator<Item = &ComponentId> + '_ {
139        self.ignored_scheduling_ambiguities.iter()
140    }
141
142    /// Prints the names of the components and resources with [`info`]
143    ///
144    /// May panic or retrieve incorrect names if [`Components`] is not from the same
145    /// world
146    pub fn print_ignored_ambiguities(&self, components: &Components) {
147        let mut message =
148            "System order ambiguities caused by conflicts on the following types are ignored:\n"
149                .to_string();
150        for id in self.iter_ignored_ambiguities() {
151            writeln!(message, "{}", components.get_name(*id).unwrap()).unwrap();
152        }
153
154        info!("{}", message);
155    }
156
157    /// Adds one or more systems to the [`Schedule`] matching the provided [`ScheduleLabel`].
158    pub fn add_systems<M>(
159        &mut self,
160        schedule: impl ScheduleLabel,
161        systems: impl IntoSystemConfigs<M>,
162    ) -> &mut Self {
163        self.entry(schedule).add_systems(systems);
164
165        self
166    }
167
168    /// Configures a collection of system sets in the provided schedule, adding any sets that do not exist.
169    #[track_caller]
170    pub fn configure_sets(
171        &mut self,
172        schedule: impl ScheduleLabel,
173        sets: impl IntoSystemSetConfigs,
174    ) -> &mut Self {
175        self.entry(schedule).configure_sets(sets);
176
177        self
178    }
179
180    /// Suppress warnings and errors that would result from systems in these sets having ambiguities
181    /// (conflicting access but indeterminate order) with systems in `set`.
182    ///
183    /// When possible, do this directly in the `.add_systems(Update, a.ambiguous_with(b))` call.
184    /// However, sometimes two independent plugins `A` and `B` are reported as ambiguous, which you
185    /// can only suppress as the consumer of both.
186    #[track_caller]
187    pub fn ignore_ambiguity<M1, M2, S1, S2>(
188        &mut self,
189        schedule: impl ScheduleLabel,
190        a: S1,
191        b: S2,
192    ) -> &mut Self
193    where
194        S1: IntoSystemSet<M1>,
195        S2: IntoSystemSet<M2>,
196    {
197        self.entry(schedule).ignore_ambiguity(a, b);
198
199        self
200    }
201}
202
203fn make_executor(kind: ExecutorKind) -> Box<dyn SystemExecutor> {
204    match kind {
205        ExecutorKind::Simple => Box::new(SimpleExecutor::new()),
206        ExecutorKind::SingleThreaded => Box::new(SingleThreadedExecutor::new()),
207        ExecutorKind::MultiThreaded => Box::new(MultiThreadedExecutor::new()),
208    }
209}
210
211/// Chain systems into dependencies
212#[derive(PartialEq)]
213pub enum Chain {
214    /// Run nodes in order. If there are deferred parameters in preceding systems a
215    /// [`apply_deferred`] will be added on the edge.
216    Yes,
217    /// Run nodes in order. This will not add [`apply_deferred`] between nodes.
218    YesIgnoreDeferred,
219    /// Nodes are allowed to run in any order.
220    No,
221}
222
223/// A collection of systems, and the metadata and executor needed to run them
224/// in a certain order under certain conditions.
225///
226/// # Example
227/// Here is an example of a `Schedule` running a "Hello world" system:
228/// ```
229/// # use bevy_ecs::prelude::*;
230/// fn hello_world() { println!("Hello world!") }
231///
232/// fn main() {
233///     let mut world = World::new();
234///     let mut schedule = Schedule::default();
235///     schedule.add_systems(hello_world);
236///
237///     schedule.run(&mut world);
238/// }
239/// ```
240///
241/// A schedule can also run several systems in an ordered way:
242/// ```
243/// # use bevy_ecs::prelude::*;
244/// fn system_one() { println!("System 1 works!") }
245/// fn system_two() { println!("System 2 works!") }
246/// fn system_three() { println!("System 3 works!") }
247///    
248/// fn main() {
249///     let mut world = World::new();
250///     let mut schedule = Schedule::default();
251///     schedule.add_systems((
252///         system_two,
253///         system_one.before(system_two),
254///         system_three.after(system_two),
255///     ));
256///
257///     schedule.run(&mut world);
258/// }
259/// ```
260pub struct Schedule {
261    label: InternedScheduleLabel,
262    graph: ScheduleGraph,
263    executable: SystemSchedule,
264    executor: Box<dyn SystemExecutor>,
265    executor_initialized: bool,
266}
267
268#[derive(ScheduleLabel, Hash, PartialEq, Eq, Debug, Clone)]
269struct DefaultSchedule;
270
271impl Default for Schedule {
272    /// Creates a schedule with a default label. Only use in situations where
273    /// you don't care about the [`ScheduleLabel`]. Inserting a default schedule
274    /// into the world risks overwriting another schedule. For most situations
275    /// you should use [`Schedule::new`].
276    fn default() -> Self {
277        Self::new(DefaultSchedule)
278    }
279}
280
281impl Schedule {
282    /// Constructs an empty `Schedule`.
283    pub fn new(label: impl ScheduleLabel) -> Self {
284        Self {
285            label: label.intern(),
286            graph: ScheduleGraph::new(),
287            executable: SystemSchedule::new(),
288            executor: make_executor(ExecutorKind::default()),
289            executor_initialized: false,
290        }
291    }
292
293    /// Get the `InternedScheduleLabel` for this `Schedule`.
294    pub fn label(&self) -> InternedScheduleLabel {
295        self.label
296    }
297
298    /// Add a collection of systems to the schedule.
299    pub fn add_systems<M>(&mut self, systems: impl IntoSystemConfigs<M>) -> &mut Self {
300        self.graph.process_configs(systems.into_configs(), false);
301        self
302    }
303
304    /// Suppress warnings and errors that would result from systems in these sets having ambiguities
305    /// (conflicting access but indeterminate order) with systems in `set`.
306    #[track_caller]
307    pub fn ignore_ambiguity<M1, M2, S1, S2>(&mut self, a: S1, b: S2) -> &mut Self
308    where
309        S1: IntoSystemSet<M1>,
310        S2: IntoSystemSet<M2>,
311    {
312        let a = a.into_system_set();
313        let b = b.into_system_set();
314
315        let Some(&a_id) = self.graph.system_set_ids.get(&a.intern()) else {
316            panic!(
317                "Could not mark system as ambiguous, `{:?}` was not found in the schedule.
318                Did you try to call `ambiguous_with` before adding the system to the world?",
319                a
320            );
321        };
322        let Some(&b_id) = self.graph.system_set_ids.get(&b.intern()) else {
323            panic!(
324                "Could not mark system as ambiguous, `{:?}` was not found in the schedule.
325                Did you try to call `ambiguous_with` before adding the system to the world?",
326                b
327            );
328        };
329
330        self.graph.ambiguous_with.add_edge(a_id, b_id, ());
331
332        self
333    }
334
335    /// Configures a collection of system sets in this schedule, adding them if they does not exist.
336    #[track_caller]
337    pub fn configure_sets(&mut self, sets: impl IntoSystemSetConfigs) -> &mut Self {
338        self.graph.configure_sets(sets);
339        self
340    }
341
342    /// Changes miscellaneous build settings.
343    pub fn set_build_settings(&mut self, settings: ScheduleBuildSettings) -> &mut Self {
344        self.graph.settings = settings;
345        self
346    }
347
348    /// Returns the schedule's current `ScheduleBuildSettings`.
349    pub fn get_build_settings(&self) -> ScheduleBuildSettings {
350        self.graph.settings.clone()
351    }
352
353    /// Returns the schedule's current execution strategy.
354    pub fn get_executor_kind(&self) -> ExecutorKind {
355        self.executor.kind()
356    }
357
358    /// Sets the schedule's execution strategy.
359    pub fn set_executor_kind(&mut self, executor: ExecutorKind) -> &mut Self {
360        if executor != self.executor.kind() {
361            self.executor = make_executor(executor);
362            self.executor_initialized = false;
363        }
364        self
365    }
366
367    /// Set whether the schedule applies deferred system buffers on final time or not. This is a catch-all
368    /// in case a system uses commands but was not explicitly ordered before an instance of
369    /// [`apply_deferred`]. By default this
370    /// setting is true, but may be disabled if needed.
371    pub fn set_apply_final_deferred(&mut self, apply_final_deferred: bool) -> &mut Self {
372        self.executor.set_apply_final_deferred(apply_final_deferred);
373        self
374    }
375
376    /// Runs all systems in this schedule on the `world`, using its current execution strategy.
377    pub fn run(&mut self, world: &mut World) {
378        #[cfg(feature = "trace")]
379        let _span = info_span!("schedule", name = ?self.label).entered();
380
381        world.check_change_ticks();
382        self.initialize(world)
383            .unwrap_or_else(|e| panic!("Error when initializing schedule {:?}: {e}", self.label));
384
385        #[cfg(not(feature = "bevy_debug_stepping"))]
386        self.executor.run(&mut self.executable, world, None);
387
388        #[cfg(feature = "bevy_debug_stepping")]
389        {
390            let skip_systems = match world.get_resource_mut::<Stepping>() {
391                None => None,
392                Some(mut stepping) => stepping.skipped_systems(self),
393            };
394
395            self.executor
396                .run(&mut self.executable, world, skip_systems.as_ref());
397        }
398    }
399
400    /// Initializes any newly-added systems and conditions, rebuilds the executable schedule,
401    /// and re-initializes the executor.
402    ///
403    /// Moves all systems and run conditions out of the [`ScheduleGraph`].
404    pub fn initialize(&mut self, world: &mut World) -> Result<(), ScheduleBuildError> {
405        if self.graph.changed {
406            self.graph.initialize(world);
407            let ignored_ambiguities = world
408                .get_resource_or_insert_with::<Schedules>(Schedules::default)
409                .ignored_scheduling_ambiguities
410                .clone();
411            self.graph.update_schedule(
412                &mut self.executable,
413                world.components(),
414                &ignored_ambiguities,
415                self.label,
416            )?;
417            self.graph.changed = false;
418            self.executor_initialized = false;
419        }
420
421        if !self.executor_initialized {
422            self.executor.init(&self.executable);
423            self.executor_initialized = true;
424        }
425
426        Ok(())
427    }
428
429    /// Returns the [`ScheduleGraph`].
430    pub fn graph(&self) -> &ScheduleGraph {
431        &self.graph
432    }
433
434    /// Returns a mutable reference to the [`ScheduleGraph`].
435    pub fn graph_mut(&mut self) -> &mut ScheduleGraph {
436        &mut self.graph
437    }
438
439    /// Returns the [`SystemSchedule`].
440    pub(crate) fn executable(&self) -> &SystemSchedule {
441        &self.executable
442    }
443
444    /// Iterates the change ticks of all systems in the schedule and clamps any older than
445    /// [`MAX_CHANGE_AGE`](crate::change_detection::MAX_CHANGE_AGE).
446    /// This prevents overflow and thus prevents false positives.
447    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
448        for system in &mut self.executable.systems {
449            if !is_apply_deferred(system) {
450                system.check_change_tick(change_tick);
451            }
452        }
453
454        for conditions in &mut self.executable.system_conditions {
455            for system in conditions {
456                system.check_change_tick(change_tick);
457            }
458        }
459
460        for conditions in &mut self.executable.set_conditions {
461            for system in conditions {
462                system.check_change_tick(change_tick);
463            }
464        }
465    }
466
467    /// Directly applies any accumulated [`Deferred`](crate::system::Deferred) system parameters (like [`Commands`](crate::prelude::Commands)) to the `world`.
468    ///
469    /// Like always, deferred system parameters are applied in the "topological sort order" of the schedule graph.
470    /// As a result, buffers from one system are only guaranteed to be applied before those of other systems
471    /// if there is an explicit system ordering between the two systems.
472    ///
473    /// This is used in rendering to extract data from the main world, storing the data in system buffers,
474    /// before applying their buffers in a different world.
475    pub fn apply_deferred(&mut self, world: &mut World) {
476        for system in &mut self.executable.systems {
477            system.apply_deferred(world);
478        }
479    }
480
481    /// Returns an iterator over all systems in this schedule.
482    ///
483    /// Note: this method will return [`ScheduleNotInitialized`] if the
484    /// schedule has never been initialized or run.
485    pub fn systems(
486        &self,
487    ) -> Result<impl Iterator<Item = (NodeId, &BoxedSystem)> + Sized, ScheduleNotInitialized> {
488        if !self.executor_initialized {
489            return Err(ScheduleNotInitialized);
490        }
491
492        let iter = self
493            .executable
494            .system_ids
495            .iter()
496            .zip(&self.executable.systems)
497            .map(|(node_id, system)| (*node_id, system));
498
499        Ok(iter)
500    }
501
502    /// Returns the number of systems in this schedule.
503    pub fn systems_len(&self) -> usize {
504        if !self.executor_initialized {
505            self.graph.systems.len()
506        } else {
507            self.executable.systems.len()
508        }
509    }
510}
511
512/// A directed acyclic graph structure.
513#[derive(Default)]
514pub struct Dag {
515    /// A directed graph.
516    graph: DiGraphMap<NodeId, ()>,
517    /// A cached topological ordering of the graph.
518    topsort: Vec<NodeId>,
519}
520
521impl Dag {
522    fn new() -> Self {
523        Self {
524            graph: DiGraphMap::new(),
525            topsort: Vec::new(),
526        }
527    }
528
529    /// The directed graph of the stored systems, connected by their ordering dependencies.
530    pub fn graph(&self) -> &DiGraphMap<NodeId, ()> {
531        &self.graph
532    }
533
534    /// A cached topological ordering of the graph.
535    ///
536    /// The order is determined by the ordering dependencies between systems.
537    pub fn cached_topsort(&self) -> &[NodeId] {
538        &self.topsort
539    }
540}
541
542/// A [`SystemSet`] with metadata, stored in a [`ScheduleGraph`].
543struct SystemSetNode {
544    inner: InternedSystemSet,
545}
546
547impl SystemSetNode {
548    pub fn new(set: InternedSystemSet) -> Self {
549        Self { inner: set }
550    }
551
552    pub fn name(&self) -> String {
553        format!("{:?}", &self.inner)
554    }
555
556    pub fn is_system_type(&self) -> bool {
557        self.inner.system_type().is_some()
558    }
559
560    pub fn is_anonymous(&self) -> bool {
561        self.inner.is_anonymous()
562    }
563}
564
565/// A [`BoxedSystem`] with metadata, stored in a [`ScheduleGraph`].
566struct SystemNode {
567    inner: Option<BoxedSystem>,
568}
569
570impl SystemNode {
571    pub fn new(system: BoxedSystem) -> Self {
572        Self {
573            inner: Some(system),
574        }
575    }
576
577    pub fn get(&self) -> Option<&BoxedSystem> {
578        self.inner.as_ref()
579    }
580
581    pub fn get_mut(&mut self) -> Option<&mut BoxedSystem> {
582        self.inner.as_mut()
583    }
584}
585
586/// Metadata for a [`Schedule`].
587///
588/// The order isn't optimized; calling `ScheduleGraph::build_schedule` will return a
589/// `SystemSchedule` where the order is optimized for execution.
590#[derive(Default)]
591pub struct ScheduleGraph {
592    /// List of systems in the schedule
593    systems: Vec<SystemNode>,
594    /// List of conditions for each system, in the same order as `systems`
595    system_conditions: Vec<Vec<BoxedCondition>>,
596    /// List of system sets in the schedule
597    system_sets: Vec<SystemSetNode>,
598    /// List of conditions for each system set, in the same order as `system_sets`
599    system_set_conditions: Vec<Vec<BoxedCondition>>,
600    /// Map from system set to node id
601    system_set_ids: HashMap<InternedSystemSet, NodeId>,
602    /// Systems that have not been initialized yet; for system sets, we store the index of the first uninitialized condition
603    /// (all the conditions after that index still need to be initialized)
604    uninit: Vec<(NodeId, usize)>,
605    /// Directed acyclic graph of the hierarchy (which systems/sets are children of which sets)
606    hierarchy: Dag,
607    /// Directed acyclic graph of the dependency (which systems/sets have to run before which other systems/sets)
608    dependency: Dag,
609    ambiguous_with: UnGraphMap<NodeId, ()>,
610    ambiguous_with_all: HashSet<NodeId>,
611    conflicting_systems: Vec<(NodeId, NodeId, Vec<ComponentId>)>,
612    anonymous_sets: usize,
613    changed: bool,
614    settings: ScheduleBuildSettings,
615    /// Dependency edges that will **not** automatically insert an instance of `apply_deferred` on the edge.
616    no_sync_edges: BTreeSet<(NodeId, NodeId)>,
617    auto_sync_node_ids: HashMap<u32, NodeId>,
618}
619
620impl ScheduleGraph {
621    /// Creates an empty [`ScheduleGraph`] with default settings.
622    pub fn new() -> Self {
623        Self {
624            systems: Vec::new(),
625            system_conditions: Vec::new(),
626            system_sets: Vec::new(),
627            system_set_conditions: Vec::new(),
628            system_set_ids: HashMap::new(),
629            uninit: Vec::new(),
630            hierarchy: Dag::new(),
631            dependency: Dag::new(),
632            ambiguous_with: UnGraphMap::new(),
633            ambiguous_with_all: HashSet::new(),
634            conflicting_systems: Vec::new(),
635            anonymous_sets: 0,
636            changed: false,
637            settings: default(),
638            no_sync_edges: BTreeSet::new(),
639            auto_sync_node_ids: HashMap::new(),
640        }
641    }
642
643    /// Returns the system at the given [`NodeId`], if it exists.
644    pub fn get_system_at(&self, id: NodeId) -> Option<&dyn System<In = (), Out = ()>> {
645        if !id.is_system() {
646            return None;
647        }
648        self.systems
649            .get(id.index())
650            .and_then(|system| system.inner.as_deref())
651    }
652
653    /// Returns the system at the given [`NodeId`].
654    ///
655    /// Panics if it doesn't exist.
656    #[track_caller]
657    pub fn system_at(&self, id: NodeId) -> &dyn System<In = (), Out = ()> {
658        self.get_system_at(id)
659            .ok_or_else(|| format!("system with id {id:?} does not exist in this Schedule"))
660            .unwrap()
661    }
662
663    /// Returns the set at the given [`NodeId`], if it exists.
664    pub fn get_set_at(&self, id: NodeId) -> Option<&dyn SystemSet> {
665        if !id.is_set() {
666            return None;
667        }
668        self.system_sets.get(id.index()).map(|set| &*set.inner)
669    }
670
671    /// Returns the set at the given [`NodeId`].
672    ///
673    /// Panics if it doesn't exist.
674    #[track_caller]
675    pub fn set_at(&self, id: NodeId) -> &dyn SystemSet {
676        self.get_set_at(id)
677            .ok_or_else(|| format!("set with id {id:?} does not exist in this Schedule"))
678            .unwrap()
679    }
680
681    /// Returns an iterator over all systems in this schedule, along with the conditions for each system.
682    pub fn systems(
683        &self,
684    ) -> impl Iterator<Item = (NodeId, &dyn System<In = (), Out = ()>, &[BoxedCondition])> {
685        self.systems
686            .iter()
687            .zip(self.system_conditions.iter())
688            .enumerate()
689            .filter_map(|(i, (system_node, condition))| {
690                let system = system_node.inner.as_deref()?;
691                Some((NodeId::System(i), system, condition.as_slice()))
692            })
693    }
694
695    /// Returns an iterator over all system sets in this schedule, along with the conditions for each
696    /// system set.
697    pub fn system_sets(&self) -> impl Iterator<Item = (NodeId, &dyn SystemSet, &[BoxedCondition])> {
698        self.system_set_ids.iter().map(|(_, &node_id)| {
699            let set_node = &self.system_sets[node_id.index()];
700            let set = &*set_node.inner;
701            let conditions = self.system_set_conditions[node_id.index()].as_slice();
702            (node_id, set, conditions)
703        })
704    }
705
706    /// Returns the [`Dag`] of the hierarchy.
707    ///
708    /// The hierarchy is a directed acyclic graph of the systems and sets,
709    /// where an edge denotes that a system or set is the child of another set.
710    pub fn hierarchy(&self) -> &Dag {
711        &self.hierarchy
712    }
713
714    /// Returns the [`Dag`] of the dependencies in the schedule.
715    ///
716    /// Nodes in this graph are systems and sets, and edges denote that
717    /// a system or set has to run before another system or set.
718    pub fn dependency(&self) -> &Dag {
719        &self.dependency
720    }
721
722    /// Returns the list of systems that conflict with each other, i.e. have ambiguities in their access.
723    ///
724    /// If the `Vec<ComponentId>` is empty, the systems conflict on [`World`] access.
725    /// Must be called after [`ScheduleGraph::build_schedule`] to be non-empty.
726    pub fn conflicting_systems(&self) -> &[(NodeId, NodeId, Vec<ComponentId>)] {
727        &self.conflicting_systems
728    }
729
730    fn process_config<T: ProcessNodeConfig>(
731        &mut self,
732        config: NodeConfig<T>,
733        collect_nodes: bool,
734    ) -> ProcessConfigsResult {
735        ProcessConfigsResult {
736            densely_chained: true,
737            nodes: collect_nodes
738                .then_some(T::process_config(self, config))
739                .into_iter()
740                .collect(),
741        }
742    }
743
744    fn apply_collective_conditions<T: ProcessNodeConfig>(
745        &mut self,
746        configs: &mut [NodeConfigs<T>],
747        collective_conditions: Vec<BoxedCondition>,
748    ) {
749        if !collective_conditions.is_empty() {
750            if let [config] = configs {
751                for condition in collective_conditions {
752                    config.run_if_dyn(condition);
753                }
754            } else {
755                let set = self.create_anonymous_set();
756                for config in configs.iter_mut() {
757                    config.in_set_inner(set.intern());
758                }
759                let mut set_config = SystemSetConfig::new(set.intern());
760                set_config.conditions.extend(collective_conditions);
761                self.configure_set_inner(set_config).unwrap();
762            }
763        }
764    }
765
766    /// Adds the config nodes to the graph.
767    ///
768    /// `collect_nodes` controls whether the `NodeId`s of the processed config nodes are stored in the returned [`ProcessConfigsResult`].
769    /// `process_config` is the function which processes each individual config node and returns a corresponding `NodeId`.
770    ///
771    /// The fields on the returned [`ProcessConfigsResult`] are:
772    /// - `nodes`: a vector of all node ids contained in the nested `NodeConfigs`
773    /// - `densely_chained`: a boolean that is true if all nested nodes are linearly chained (with successive `after` orderings) in the order they are defined
774    #[track_caller]
775    fn process_configs<T: ProcessNodeConfig>(
776        &mut self,
777        configs: NodeConfigs<T>,
778        collect_nodes: bool,
779    ) -> ProcessConfigsResult {
780        match configs {
781            NodeConfigs::NodeConfig(config) => self.process_config(config, collect_nodes),
782            NodeConfigs::Configs {
783                mut configs,
784                collective_conditions,
785                chained,
786            } => {
787                self.apply_collective_conditions(&mut configs, collective_conditions);
788
789                let ignore_deferred = matches!(chained, Chain::YesIgnoreDeferred);
790                let chained = matches!(chained, Chain::Yes | Chain::YesIgnoreDeferred);
791
792                // Densely chained if
793                // * chained and all configs in the chain are densely chained, or
794                // * unchained with a single densely chained config
795                let mut densely_chained = chained || configs.len() == 1;
796                let mut configs = configs.into_iter();
797                let mut nodes = Vec::new();
798
799                let Some(first) = configs.next() else {
800                    return ProcessConfigsResult {
801                        nodes: Vec::new(),
802                        densely_chained,
803                    };
804                };
805                let mut previous_result = self.process_configs(first, collect_nodes || chained);
806                densely_chained &= previous_result.densely_chained;
807
808                for current in configs {
809                    let current_result = self.process_configs(current, collect_nodes || chained);
810                    densely_chained &= current_result.densely_chained;
811
812                    if chained {
813                        // if the current result is densely chained, we only need to chain the first node
814                        let current_nodes = if current_result.densely_chained {
815                            &current_result.nodes[..1]
816                        } else {
817                            &current_result.nodes
818                        };
819                        // if the previous result was densely chained, we only need to chain the last node
820                        let previous_nodes = if previous_result.densely_chained {
821                            &previous_result.nodes[previous_result.nodes.len() - 1..]
822                        } else {
823                            &previous_result.nodes
824                        };
825
826                        for previous_node in previous_nodes {
827                            for current_node in current_nodes {
828                                self.dependency
829                                    .graph
830                                    .add_edge(*previous_node, *current_node, ());
831
832                                if ignore_deferred {
833                                    self.no_sync_edges.insert((*previous_node, *current_node));
834                                }
835                            }
836                        }
837                    }
838                    if collect_nodes {
839                        nodes.append(&mut previous_result.nodes);
840                    }
841
842                    previous_result = current_result;
843                }
844                if collect_nodes {
845                    nodes.append(&mut previous_result.nodes);
846                }
847
848                ProcessConfigsResult {
849                    nodes,
850                    densely_chained,
851                }
852            }
853        }
854    }
855
856    /// Add a [`SystemConfig`] to the graph, including its dependencies and conditions.
857    fn add_system_inner(&mut self, config: SystemConfig) -> Result<NodeId, ScheduleBuildError> {
858        let id = NodeId::System(self.systems.len());
859
860        // graph updates are immediate
861        self.update_graphs(id, config.graph_info)?;
862
863        // system init has to be deferred (need `&mut World`)
864        self.uninit.push((id, 0));
865        self.systems.push(SystemNode::new(config.node));
866        self.system_conditions.push(config.conditions);
867
868        Ok(id)
869    }
870
871    #[track_caller]
872    fn configure_sets(&mut self, sets: impl IntoSystemSetConfigs) {
873        self.process_configs(sets.into_configs(), false);
874    }
875
876    /// Add a single `SystemSetConfig` to the graph, including its dependencies and conditions.
877    fn configure_set_inner(&mut self, set: SystemSetConfig) -> Result<NodeId, ScheduleBuildError> {
878        let SystemSetConfig {
879            node: set,
880            graph_info,
881            mut conditions,
882        } = set;
883
884        let id = match self.system_set_ids.get(&set) {
885            Some(&id) => id,
886            None => self.add_set(set),
887        };
888
889        // graph updates are immediate
890        self.update_graphs(id, graph_info)?;
891
892        // system init has to be deferred (need `&mut World`)
893        let system_set_conditions = &mut self.system_set_conditions[id.index()];
894        self.uninit.push((id, system_set_conditions.len()));
895        system_set_conditions.append(&mut conditions);
896
897        Ok(id)
898    }
899
900    fn add_set(&mut self, set: InternedSystemSet) -> NodeId {
901        let id = NodeId::Set(self.system_sets.len());
902        self.system_sets.push(SystemSetNode::new(set));
903        self.system_set_conditions.push(Vec::new());
904        self.system_set_ids.insert(set, id);
905        id
906    }
907
908    /// Checks that a system set isn't included in itself.
909    /// If not present, add the set to the graph.
910    fn check_hierarchy_set(
911        &mut self,
912        id: &NodeId,
913        set: InternedSystemSet,
914    ) -> Result<(), ScheduleBuildError> {
915        match self.system_set_ids.get(&set) {
916            Some(set_id) => {
917                if id == set_id {
918                    return Err(ScheduleBuildError::HierarchyLoop(self.get_node_name(id)));
919                }
920            }
921            None => {
922                self.add_set(set);
923            }
924        }
925
926        Ok(())
927    }
928
929    fn create_anonymous_set(&mut self) -> AnonymousSet {
930        let id = self.anonymous_sets;
931        self.anonymous_sets += 1;
932        AnonymousSet::new(id)
933    }
934
935    /// Check that no set is included in itself.
936    /// Add all the sets from the [`GraphInfo`]'s hierarchy to the graph.
937    fn check_hierarchy_sets(
938        &mut self,
939        id: &NodeId,
940        graph_info: &GraphInfo,
941    ) -> Result<(), ScheduleBuildError> {
942        for &set in &graph_info.hierarchy {
943            self.check_hierarchy_set(id, set)?;
944        }
945
946        Ok(())
947    }
948
949    /// Checks that no system set is dependent on itself.
950    /// Add all the sets from the [`GraphInfo`]'s dependencies to the graph.
951    fn check_edges(
952        &mut self,
953        id: &NodeId,
954        graph_info: &GraphInfo,
955    ) -> Result<(), ScheduleBuildError> {
956        for Dependency { kind: _, set } in &graph_info.dependencies {
957            match self.system_set_ids.get(set) {
958                Some(set_id) => {
959                    if id == set_id {
960                        return Err(ScheduleBuildError::DependencyLoop(self.get_node_name(id)));
961                    }
962                }
963                None => {
964                    self.add_set(*set);
965                }
966            }
967        }
968
969        if let Ambiguity::IgnoreWithSet(ambiguous_with) = &graph_info.ambiguous_with {
970            for set in ambiguous_with {
971                if !self.system_set_ids.contains_key(set) {
972                    self.add_set(*set);
973                }
974            }
975        }
976
977        Ok(())
978    }
979
980    /// Update the internal graphs (hierarchy, dependency, ambiguity) by adding a single [`GraphInfo`]
981    fn update_graphs(
982        &mut self,
983        id: NodeId,
984        graph_info: GraphInfo,
985    ) -> Result<(), ScheduleBuildError> {
986        self.check_hierarchy_sets(&id, &graph_info)?;
987        self.check_edges(&id, &graph_info)?;
988        self.changed = true;
989
990        let GraphInfo {
991            hierarchy: sets,
992            dependencies,
993            ambiguous_with,
994            ..
995        } = graph_info;
996
997        self.hierarchy.graph.add_node(id);
998        self.dependency.graph.add_node(id);
999
1000        for set in sets.into_iter().map(|set| self.system_set_ids[&set]) {
1001            self.hierarchy.graph.add_edge(set, id, ());
1002
1003            // ensure set also appears in dependency graph
1004            self.dependency.graph.add_node(set);
1005        }
1006
1007        for (kind, set) in dependencies
1008            .into_iter()
1009            .map(|Dependency { kind, set }| (kind, self.system_set_ids[&set]))
1010        {
1011            let (lhs, rhs) = match kind {
1012                DependencyKind::Before => (id, set),
1013                DependencyKind::BeforeNoSync => {
1014                    self.no_sync_edges.insert((id, set));
1015                    (id, set)
1016                }
1017                DependencyKind::After => (set, id),
1018                DependencyKind::AfterNoSync => {
1019                    self.no_sync_edges.insert((set, id));
1020                    (set, id)
1021                }
1022            };
1023            self.dependency.graph.add_edge(lhs, rhs, ());
1024
1025            // ensure set also appears in hierarchy graph
1026            self.hierarchy.graph.add_node(set);
1027        }
1028
1029        match ambiguous_with {
1030            Ambiguity::Check => (),
1031            Ambiguity::IgnoreWithSet(ambiguous_with) => {
1032                for set in ambiguous_with
1033                    .into_iter()
1034                    .map(|set| self.system_set_ids[&set])
1035                {
1036                    self.ambiguous_with.add_edge(id, set, ());
1037                }
1038            }
1039            Ambiguity::IgnoreAll => {
1040                self.ambiguous_with_all.insert(id);
1041            }
1042        }
1043
1044        Ok(())
1045    }
1046
1047    /// Initializes any newly-added systems and conditions by calling [`System::initialize`]
1048    pub fn initialize(&mut self, world: &mut World) {
1049        for (id, i) in self.uninit.drain(..) {
1050            match id {
1051                NodeId::System(index) => {
1052                    self.systems[index].get_mut().unwrap().initialize(world);
1053                    for condition in &mut self.system_conditions[index] {
1054                        condition.initialize(world);
1055                    }
1056                }
1057                NodeId::Set(index) => {
1058                    for condition in self.system_set_conditions[index].iter_mut().skip(i) {
1059                        condition.initialize(world);
1060                    }
1061                }
1062            }
1063        }
1064    }
1065
1066    /// Build a [`SystemSchedule`] optimized for scheduler access from the [`ScheduleGraph`].
1067    ///
1068    /// This method also
1069    /// - checks for dependency or hierarchy cycles
1070    /// - checks for system access conflicts and reports ambiguities
1071    pub fn build_schedule(
1072        &mut self,
1073        components: &Components,
1074        schedule_label: InternedScheduleLabel,
1075        ignored_ambiguities: &BTreeSet<ComponentId>,
1076    ) -> Result<SystemSchedule, ScheduleBuildError> {
1077        // check hierarchy for cycles
1078        self.hierarchy.topsort =
1079            self.topsort_graph(&self.hierarchy.graph, ReportCycles::Hierarchy)?;
1080
1081        let hier_results = check_graph(&self.hierarchy.graph, &self.hierarchy.topsort);
1082        self.optionally_check_hierarchy_conflicts(&hier_results.transitive_edges, schedule_label)?;
1083
1084        // remove redundant edges
1085        self.hierarchy.graph = hier_results.transitive_reduction;
1086
1087        // check dependencies for cycles
1088        self.dependency.topsort =
1089            self.topsort_graph(&self.dependency.graph, ReportCycles::Dependency)?;
1090
1091        // check for systems or system sets depending on sets they belong to
1092        let dep_results = check_graph(&self.dependency.graph, &self.dependency.topsort);
1093        self.check_for_cross_dependencies(&dep_results, &hier_results.connected)?;
1094
1095        // map all system sets to their systems
1096        // go in reverse topological order (bottom-up) for efficiency
1097        let (set_systems, set_system_bitsets) =
1098            self.map_sets_to_systems(&self.hierarchy.topsort, &self.hierarchy.graph);
1099        self.check_order_but_intersect(&dep_results.connected, &set_system_bitsets)?;
1100
1101        // check that there are no edges to system-type sets that have multiple instances
1102        self.check_system_type_set_ambiguity(&set_systems)?;
1103
1104        let mut dependency_flattened = self.get_dependency_flattened(&set_systems);
1105
1106        // modify graph with auto sync points
1107        if self.settings.auto_insert_apply_deferred {
1108            dependency_flattened = self.auto_insert_apply_deferred(&mut dependency_flattened)?;
1109        }
1110
1111        // topsort
1112        let mut dependency_flattened_dag = Dag {
1113            topsort: self.topsort_graph(&dependency_flattened, ReportCycles::Dependency)?,
1114            graph: dependency_flattened,
1115        };
1116
1117        let flat_results = check_graph(
1118            &dependency_flattened_dag.graph,
1119            &dependency_flattened_dag.topsort,
1120        );
1121
1122        // remove redundant edges
1123        dependency_flattened_dag.graph = flat_results.transitive_reduction;
1124
1125        // flatten: combine `in_set` with `ambiguous_with` information
1126        let ambiguous_with_flattened = self.get_ambiguous_with_flattened(&set_systems);
1127
1128        // check for conflicts
1129        let conflicting_systems = self.get_conflicting_systems(
1130            &flat_results.disconnected,
1131            &ambiguous_with_flattened,
1132            ignored_ambiguities,
1133        );
1134        self.optionally_check_conflicts(&conflicting_systems, components, schedule_label)?;
1135        self.conflicting_systems = conflicting_systems;
1136
1137        // build the schedule
1138        Ok(self.build_schedule_inner(dependency_flattened_dag, hier_results.reachable))
1139    }
1140
1141    // modify the graph to have sync nodes for any dependants after a system with deferred system params
1142    fn auto_insert_apply_deferred(
1143        &mut self,
1144        dependency_flattened: &mut GraphMap<NodeId, (), Directed>,
1145    ) -> Result<GraphMap<NodeId, (), Directed>, ScheduleBuildError> {
1146        let mut sync_point_graph = dependency_flattened.clone();
1147        let topo = self.topsort_graph(dependency_flattened, ReportCycles::Dependency)?;
1148
1149        // calculate the number of sync points each sync point is from the beginning of the graph
1150        // use the same sync point if the distance is the same
1151        let mut distances: HashMap<usize, Option<u32>> = HashMap::with_capacity(topo.len());
1152        for node in &topo {
1153            let add_sync_after = self.systems[node.index()].get().unwrap().has_deferred();
1154
1155            for target in dependency_flattened.neighbors_directed(*node, Outgoing) {
1156                let add_sync_on_edge = add_sync_after
1157                    && !is_apply_deferred(self.systems[target.index()].get().unwrap())
1158                    && !self.no_sync_edges.contains(&(*node, target));
1159
1160                let weight = if add_sync_on_edge { 1 } else { 0 };
1161
1162                let distance = distances
1163                    .get(&target.index())
1164                    .unwrap_or(&None)
1165                    .or(Some(0))
1166                    .map(|distance| {
1167                        distance.max(
1168                            distances.get(&node.index()).unwrap_or(&None).unwrap_or(0) + weight,
1169                        )
1170                    });
1171
1172                distances.insert(target.index(), distance);
1173
1174                if add_sync_on_edge {
1175                    let sync_point = self.get_sync_point(distances[&target.index()].unwrap());
1176                    sync_point_graph.add_edge(*node, sync_point, ());
1177                    sync_point_graph.add_edge(sync_point, target, ());
1178
1179                    // edge is now redundant
1180                    sync_point_graph.remove_edge(*node, target);
1181                }
1182            }
1183        }
1184
1185        Ok(sync_point_graph)
1186    }
1187
1188    /// add an [`apply_deferred`] system with no config
1189    fn add_auto_sync(&mut self) -> NodeId {
1190        let id = NodeId::System(self.systems.len());
1191
1192        self.systems
1193            .push(SystemNode::new(Box::new(IntoSystem::into_system(
1194                apply_deferred,
1195            ))));
1196        self.system_conditions.push(Vec::new());
1197
1198        // ignore ambiguities with auto sync points
1199        // They aren't under user control, so no one should know or care.
1200        self.ambiguous_with_all.insert(id);
1201
1202        id
1203    }
1204
1205    /// Returns the `NodeId` of the cached auto sync point. Will create
1206    /// a new one if needed.
1207    fn get_sync_point(&mut self, distance: u32) -> NodeId {
1208        self.auto_sync_node_ids
1209            .get(&distance)
1210            .copied()
1211            .or_else(|| {
1212                let node_id = self.add_auto_sync();
1213                self.auto_sync_node_ids.insert(distance, node_id);
1214                Some(node_id)
1215            })
1216            .unwrap()
1217    }
1218
1219    /// Return a map from system set `NodeId` to a list of system `NodeId`s that are included in the set.
1220    /// Also return a map from system set `NodeId` to a `FixedBitSet` of system `NodeId`s that are included in the set,
1221    /// where the bitset order is the same as `self.systems`
1222    fn map_sets_to_systems(
1223        &self,
1224        hierarchy_topsort: &[NodeId],
1225        hierarchy_graph: &GraphMap<NodeId, (), Directed>,
1226    ) -> (HashMap<NodeId, Vec<NodeId>>, HashMap<NodeId, FixedBitSet>) {
1227        let mut set_systems: HashMap<NodeId, Vec<NodeId>> =
1228            HashMap::with_capacity(self.system_sets.len());
1229        let mut set_system_bitsets = HashMap::with_capacity(self.system_sets.len());
1230        for &id in hierarchy_topsort.iter().rev() {
1231            if id.is_system() {
1232                continue;
1233            }
1234
1235            let mut systems = Vec::new();
1236            let mut system_bitset = FixedBitSet::with_capacity(self.systems.len());
1237
1238            for child in hierarchy_graph.neighbors_directed(id, Outgoing) {
1239                match child {
1240                    NodeId::System(_) => {
1241                        systems.push(child);
1242                        system_bitset.insert(child.index());
1243                    }
1244                    NodeId::Set(_) => {
1245                        let child_systems = set_systems.get(&child).unwrap();
1246                        let child_system_bitset = set_system_bitsets.get(&child).unwrap();
1247                        systems.extend_from_slice(child_systems);
1248                        system_bitset.union_with(child_system_bitset);
1249                    }
1250                }
1251            }
1252
1253            set_systems.insert(id, systems);
1254            set_system_bitsets.insert(id, system_bitset);
1255        }
1256        (set_systems, set_system_bitsets)
1257    }
1258
1259    fn get_dependency_flattened(
1260        &mut self,
1261        set_systems: &HashMap<NodeId, Vec<NodeId>>,
1262    ) -> GraphMap<NodeId, (), Directed> {
1263        // flatten: combine `in_set` with `before` and `after` information
1264        // have to do it like this to preserve transitivity
1265        let mut dependency_flattened = self.dependency.graph.clone();
1266        let mut temp = Vec::new();
1267        for (&set, systems) in set_systems {
1268            if systems.is_empty() {
1269                // collapse dependencies for empty sets
1270                for a in dependency_flattened.neighbors_directed(set, Incoming) {
1271                    for b in dependency_flattened.neighbors_directed(set, Outgoing) {
1272                        if self.no_sync_edges.contains(&(a, set))
1273                            && self.no_sync_edges.contains(&(set, b))
1274                        {
1275                            self.no_sync_edges.insert((a, b));
1276                        }
1277
1278                        temp.push((a, b));
1279                    }
1280                }
1281            } else {
1282                for a in dependency_flattened.neighbors_directed(set, Incoming) {
1283                    for &sys in systems {
1284                        if self.no_sync_edges.contains(&(a, set)) {
1285                            self.no_sync_edges.insert((a, sys));
1286                        }
1287                        temp.push((a, sys));
1288                    }
1289                }
1290
1291                for b in dependency_flattened.neighbors_directed(set, Outgoing) {
1292                    for &sys in systems {
1293                        if self.no_sync_edges.contains(&(set, b)) {
1294                            self.no_sync_edges.insert((sys, b));
1295                        }
1296                        temp.push((sys, b));
1297                    }
1298                }
1299            }
1300
1301            dependency_flattened.remove_node(set);
1302            for (a, b) in temp.drain(..) {
1303                dependency_flattened.add_edge(a, b, ());
1304            }
1305        }
1306
1307        dependency_flattened
1308    }
1309
1310    fn get_ambiguous_with_flattened(
1311        &self,
1312        set_systems: &HashMap<NodeId, Vec<NodeId>>,
1313    ) -> GraphMap<NodeId, (), Undirected> {
1314        let mut ambiguous_with_flattened = UnGraphMap::new();
1315        for (lhs, rhs, _) in self.ambiguous_with.all_edges() {
1316            match (lhs, rhs) {
1317                (NodeId::System(_), NodeId::System(_)) => {
1318                    ambiguous_with_flattened.add_edge(lhs, rhs, ());
1319                }
1320                (NodeId::Set(_), NodeId::System(_)) => {
1321                    for &lhs_ in set_systems.get(&lhs).unwrap_or(&Vec::new()) {
1322                        ambiguous_with_flattened.add_edge(lhs_, rhs, ());
1323                    }
1324                }
1325                (NodeId::System(_), NodeId::Set(_)) => {
1326                    for &rhs_ in set_systems.get(&rhs).unwrap_or(&Vec::new()) {
1327                        ambiguous_with_flattened.add_edge(lhs, rhs_, ());
1328                    }
1329                }
1330                (NodeId::Set(_), NodeId::Set(_)) => {
1331                    for &lhs_ in set_systems.get(&lhs).unwrap_or(&Vec::new()) {
1332                        for &rhs_ in set_systems.get(&rhs).unwrap_or(&vec![]) {
1333                            ambiguous_with_flattened.add_edge(lhs_, rhs_, ());
1334                        }
1335                    }
1336                }
1337            }
1338        }
1339
1340        ambiguous_with_flattened
1341    }
1342
1343    fn get_conflicting_systems(
1344        &self,
1345        flat_results_disconnected: &Vec<(NodeId, NodeId)>,
1346        ambiguous_with_flattened: &GraphMap<NodeId, (), Undirected>,
1347        ignored_ambiguities: &BTreeSet<ComponentId>,
1348    ) -> Vec<(NodeId, NodeId, Vec<ComponentId>)> {
1349        let mut conflicting_systems = Vec::new();
1350        for &(a, b) in flat_results_disconnected {
1351            if ambiguous_with_flattened.contains_edge(a, b)
1352                || self.ambiguous_with_all.contains(&a)
1353                || self.ambiguous_with_all.contains(&b)
1354            {
1355                continue;
1356            }
1357
1358            let system_a = self.systems[a.index()].get().unwrap();
1359            let system_b = self.systems[b.index()].get().unwrap();
1360            if system_a.is_exclusive() || system_b.is_exclusive() {
1361                conflicting_systems.push((a, b, Vec::new()));
1362            } else {
1363                let access_a = system_a.component_access();
1364                let access_b = system_b.component_access();
1365                if !access_a.is_compatible(access_b) {
1366                    let conflicts: Vec<_> = access_a
1367                        .get_conflicts(access_b)
1368                        .into_iter()
1369                        .filter(|id| !ignored_ambiguities.contains(id))
1370                        .collect();
1371
1372                    if !conflicts.is_empty() {
1373                        conflicting_systems.push((a, b, conflicts));
1374                    }
1375                }
1376            }
1377        }
1378
1379        conflicting_systems
1380    }
1381
1382    fn build_schedule_inner(
1383        &self,
1384        dependency_flattened_dag: Dag,
1385        hier_results_reachable: FixedBitSet,
1386    ) -> SystemSchedule {
1387        let dg_system_ids = dependency_flattened_dag.topsort.clone();
1388        let dg_system_idx_map = dg_system_ids
1389            .iter()
1390            .cloned()
1391            .enumerate()
1392            .map(|(i, id)| (id, i))
1393            .collect::<HashMap<_, _>>();
1394
1395        let hg_systems = self
1396            .hierarchy
1397            .topsort
1398            .iter()
1399            .cloned()
1400            .enumerate()
1401            .filter(|&(_i, id)| id.is_system())
1402            .collect::<Vec<_>>();
1403
1404        let (hg_set_with_conditions_idxs, hg_set_ids): (Vec<_>, Vec<_>) = self
1405            .hierarchy
1406            .topsort
1407            .iter()
1408            .cloned()
1409            .enumerate()
1410            .filter(|&(_i, id)| {
1411                // ignore system sets that have no conditions
1412                // ignore system type sets (already covered, they don't have conditions)
1413                id.is_set() && !self.system_set_conditions[id.index()].is_empty()
1414            })
1415            .unzip();
1416
1417        let sys_count = self.systems.len();
1418        let set_with_conditions_count = hg_set_ids.len();
1419        let hg_node_count = self.hierarchy.graph.node_count();
1420
1421        // get the number of dependencies and the immediate dependents of each system
1422        // (needed by multi_threaded executor to run systems in the correct order)
1423        let mut system_dependencies = Vec::with_capacity(sys_count);
1424        let mut system_dependents = Vec::with_capacity(sys_count);
1425        for &sys_id in &dg_system_ids {
1426            let num_dependencies = dependency_flattened_dag
1427                .graph
1428                .neighbors_directed(sys_id, Incoming)
1429                .count();
1430
1431            let dependents = dependency_flattened_dag
1432                .graph
1433                .neighbors_directed(sys_id, Outgoing)
1434                .map(|dep_id| dg_system_idx_map[&dep_id])
1435                .collect::<Vec<_>>();
1436
1437            system_dependencies.push(num_dependencies);
1438            system_dependents.push(dependents);
1439        }
1440
1441        // get the rows and columns of the hierarchy graph's reachability matrix
1442        // (needed to we can evaluate conditions in the correct order)
1443        let mut systems_in_sets_with_conditions =
1444            vec![FixedBitSet::with_capacity(sys_count); set_with_conditions_count];
1445        for (i, &row) in hg_set_with_conditions_idxs.iter().enumerate() {
1446            let bitset = &mut systems_in_sets_with_conditions[i];
1447            for &(col, sys_id) in &hg_systems {
1448                let idx = dg_system_idx_map[&sys_id];
1449                let is_descendant = hier_results_reachable[index(row, col, hg_node_count)];
1450                bitset.set(idx, is_descendant);
1451            }
1452        }
1453
1454        let mut sets_with_conditions_of_systems =
1455            vec![FixedBitSet::with_capacity(set_with_conditions_count); sys_count];
1456        for &(col, sys_id) in &hg_systems {
1457            let i = dg_system_idx_map[&sys_id];
1458            let bitset = &mut sets_with_conditions_of_systems[i];
1459            for (idx, &row) in hg_set_with_conditions_idxs
1460                .iter()
1461                .enumerate()
1462                .take_while(|&(_idx, &row)| row < col)
1463            {
1464                let is_ancestor = hier_results_reachable[index(row, col, hg_node_count)];
1465                bitset.set(idx, is_ancestor);
1466            }
1467        }
1468
1469        SystemSchedule {
1470            systems: Vec::with_capacity(sys_count),
1471            system_conditions: Vec::with_capacity(sys_count),
1472            set_conditions: Vec::with_capacity(set_with_conditions_count),
1473            system_ids: dg_system_ids,
1474            set_ids: hg_set_ids,
1475            system_dependencies,
1476            system_dependents,
1477            sets_with_conditions_of_systems,
1478            systems_in_sets_with_conditions,
1479        }
1480    }
1481
1482    /// Updates the `SystemSchedule` from the `ScheduleGraph`.
1483    fn update_schedule(
1484        &mut self,
1485        schedule: &mut SystemSchedule,
1486        components: &Components,
1487        ignored_ambiguities: &BTreeSet<ComponentId>,
1488        schedule_label: InternedScheduleLabel,
1489    ) -> Result<(), ScheduleBuildError> {
1490        if !self.uninit.is_empty() {
1491            return Err(ScheduleBuildError::Uninitialized);
1492        }
1493
1494        // move systems out of old schedule
1495        for ((id, system), conditions) in schedule
1496            .system_ids
1497            .drain(..)
1498            .zip(schedule.systems.drain(..))
1499            .zip(schedule.system_conditions.drain(..))
1500        {
1501            self.systems[id.index()].inner = Some(system);
1502            self.system_conditions[id.index()] = conditions;
1503        }
1504
1505        for (id, conditions) in schedule
1506            .set_ids
1507            .drain(..)
1508            .zip(schedule.set_conditions.drain(..))
1509        {
1510            self.system_set_conditions[id.index()] = conditions;
1511        }
1512
1513        *schedule = self.build_schedule(components, schedule_label, ignored_ambiguities)?;
1514
1515        // move systems into new schedule
1516        for &id in &schedule.system_ids {
1517            let system = self.systems[id.index()].inner.take().unwrap();
1518            let conditions = std::mem::take(&mut self.system_conditions[id.index()]);
1519            schedule.systems.push(system);
1520            schedule.system_conditions.push(conditions);
1521        }
1522
1523        for &id in &schedule.set_ids {
1524            let conditions = std::mem::take(&mut self.system_set_conditions[id.index()]);
1525            schedule.set_conditions.push(conditions);
1526        }
1527
1528        Ok(())
1529    }
1530}
1531
1532/// Values returned by [`ScheduleGraph::process_configs`]
1533struct ProcessConfigsResult {
1534    /// All nodes contained inside this `process_configs` call's [`NodeConfigs`] hierarchy,
1535    /// if `ancestor_chained` is true
1536    nodes: Vec<NodeId>,
1537    /// True if and only if all nodes are "densely chained", meaning that all nested nodes
1538    /// are linearly chained (as if `after` system ordering had been applied between each node)
1539    /// in the order they are defined
1540    densely_chained: bool,
1541}
1542
1543/// Trait used by [`ScheduleGraph::process_configs`] to process a single [`NodeConfig`].
1544trait ProcessNodeConfig: Sized {
1545    /// Process a single [`NodeConfig`].
1546    fn process_config(schedule_graph: &mut ScheduleGraph, config: NodeConfig<Self>) -> NodeId;
1547}
1548
1549impl ProcessNodeConfig for BoxedSystem {
1550    fn process_config(schedule_graph: &mut ScheduleGraph, config: NodeConfig<Self>) -> NodeId {
1551        schedule_graph.add_system_inner(config).unwrap()
1552    }
1553}
1554
1555impl ProcessNodeConfig for InternedSystemSet {
1556    fn process_config(schedule_graph: &mut ScheduleGraph, config: NodeConfig<Self>) -> NodeId {
1557        schedule_graph.configure_set_inner(config).unwrap()
1558    }
1559}
1560
1561/// Used to select the appropriate reporting function.
1562enum ReportCycles {
1563    Hierarchy,
1564    Dependency,
1565}
1566
1567// methods for reporting errors
1568impl ScheduleGraph {
1569    fn get_node_name(&self, id: &NodeId) -> String {
1570        self.get_node_name_inner(id, self.settings.report_sets)
1571    }
1572
1573    #[inline]
1574    fn get_node_name_inner(&self, id: &NodeId, report_sets: bool) -> String {
1575        let mut name = match id {
1576            NodeId::System(_) => {
1577                let name = self.systems[id.index()].get().unwrap().name().to_string();
1578                if report_sets {
1579                    let sets = self.names_of_sets_containing_node(id);
1580                    if sets.is_empty() {
1581                        name
1582                    } else if sets.len() == 1 {
1583                        format!("{name} (in set {})", sets[0])
1584                    } else {
1585                        format!("{name} (in sets {})", sets.join(", "))
1586                    }
1587                } else {
1588                    name
1589                }
1590            }
1591            NodeId::Set(_) => {
1592                let set = &self.system_sets[id.index()];
1593                if set.is_anonymous() {
1594                    self.anonymous_set_name(id)
1595                } else {
1596                    set.name()
1597                }
1598            }
1599        };
1600        if self.settings.use_shortnames {
1601            name = bevy_utils::get_short_name(&name);
1602        }
1603        name
1604    }
1605
1606    fn anonymous_set_name(&self, id: &NodeId) -> String {
1607        format!(
1608            "({})",
1609            self.hierarchy
1610                .graph
1611                .edges_directed(*id, Outgoing)
1612                // never get the sets of the members or this will infinite recurse when the report_sets setting is on.
1613                .map(|(_, member_id, _)| self.get_node_name_inner(&member_id, false))
1614                .reduce(|a, b| format!("{a}, {b}"))
1615                .unwrap_or_default()
1616        )
1617    }
1618
1619    fn get_node_kind(&self, id: &NodeId) -> &'static str {
1620        match id {
1621            NodeId::System(_) => "system",
1622            NodeId::Set(_) => "system set",
1623        }
1624    }
1625
1626    /// If [`ScheduleBuildSettings::hierarchy_detection`] is [`LogLevel::Ignore`] this check
1627    /// is skipped.
1628    fn optionally_check_hierarchy_conflicts(
1629        &self,
1630        transitive_edges: &[(NodeId, NodeId)],
1631        schedule_label: InternedScheduleLabel,
1632    ) -> Result<(), ScheduleBuildError> {
1633        if self.settings.hierarchy_detection == LogLevel::Ignore || transitive_edges.is_empty() {
1634            return Ok(());
1635        }
1636
1637        let message = self.get_hierarchy_conflicts_error_message(transitive_edges);
1638        match self.settings.hierarchy_detection {
1639            LogLevel::Ignore => unreachable!(),
1640            LogLevel::Warn => {
1641                error!(
1642                    "Schedule {schedule_label:?} has redundant edges:\n {}",
1643                    message
1644                );
1645                Ok(())
1646            }
1647            LogLevel::Error => Err(ScheduleBuildError::HierarchyRedundancy(message)),
1648        }
1649    }
1650
1651    fn get_hierarchy_conflicts_error_message(
1652        &self,
1653        transitive_edges: &[(NodeId, NodeId)],
1654    ) -> String {
1655        let mut message = String::from("hierarchy contains redundant edge(s)");
1656        for (parent, child) in transitive_edges {
1657            writeln!(
1658                message,
1659                " -- {} `{}` cannot be child of set `{}`, longer path exists",
1660                self.get_node_kind(child),
1661                self.get_node_name(child),
1662                self.get_node_name(parent),
1663            )
1664            .unwrap();
1665        }
1666
1667        message
1668    }
1669
1670    /// Tries to topologically sort `graph`.
1671    ///
1672    /// If the graph is acyclic, returns [`Ok`] with the list of [`NodeId`] in a valid
1673    /// topological order. If the graph contains cycles, returns [`Err`] with the list of
1674    /// strongly-connected components that contain cycles (also in a valid topological order).
1675    ///
1676    /// # Errors
1677    ///
1678    /// If the graph contain cycles, then an error is returned.
1679    fn topsort_graph(
1680        &self,
1681        graph: &DiGraphMap<NodeId, ()>,
1682        report: ReportCycles,
1683    ) -> Result<Vec<NodeId>, ScheduleBuildError> {
1684        // Tarjan's SCC algorithm returns elements in *reverse* topological order.
1685        let mut tarjan_scc = TarjanScc::new();
1686        let mut top_sorted_nodes = Vec::with_capacity(graph.node_count());
1687        let mut sccs_with_cycles = Vec::new();
1688
1689        tarjan_scc.run(graph, |scc| {
1690            // A strongly-connected component is a group of nodes who can all reach each other
1691            // through one or more paths. If an SCC contains more than one node, there must be
1692            // at least one cycle within them.
1693            if scc.len() > 1 {
1694                sccs_with_cycles.push(scc.to_vec());
1695            }
1696            top_sorted_nodes.extend_from_slice(scc);
1697        });
1698
1699        if sccs_with_cycles.is_empty() {
1700            // reverse to get topological order
1701            top_sorted_nodes.reverse();
1702            Ok(top_sorted_nodes)
1703        } else {
1704            let mut cycles = Vec::new();
1705            for scc in &sccs_with_cycles {
1706                cycles.append(&mut simple_cycles_in_component(graph, scc));
1707            }
1708
1709            let error = match report {
1710                ReportCycles::Hierarchy => ScheduleBuildError::HierarchyCycle(
1711                    self.get_hierarchy_cycles_error_message(&cycles),
1712                ),
1713                ReportCycles::Dependency => ScheduleBuildError::DependencyCycle(
1714                    self.get_dependency_cycles_error_message(&cycles),
1715                ),
1716            };
1717
1718            Err(error)
1719        }
1720    }
1721
1722    /// Logs details of cycles in the hierarchy graph.
1723    fn get_hierarchy_cycles_error_message(&self, cycles: &[Vec<NodeId>]) -> String {
1724        let mut message = format!("schedule has {} in_set cycle(s):\n", cycles.len());
1725        for (i, cycle) in cycles.iter().enumerate() {
1726            let mut names = cycle.iter().map(|id| self.get_node_name(id));
1727            let first_name = names.next().unwrap();
1728            writeln!(
1729                message,
1730                "cycle {}: set `{first_name}` contains itself",
1731                i + 1,
1732            )
1733            .unwrap();
1734            writeln!(message, "set `{first_name}`").unwrap();
1735            for name in names.chain(std::iter::once(first_name)) {
1736                writeln!(message, " ... which contains set `{name}`").unwrap();
1737            }
1738            writeln!(message).unwrap();
1739        }
1740
1741        message
1742    }
1743
1744    /// Logs details of cycles in the dependency graph.
1745    fn get_dependency_cycles_error_message(&self, cycles: &[Vec<NodeId>]) -> String {
1746        let mut message = format!("schedule has {} before/after cycle(s):\n", cycles.len());
1747        for (i, cycle) in cycles.iter().enumerate() {
1748            let mut names = cycle
1749                .iter()
1750                .map(|id| (self.get_node_kind(id), self.get_node_name(id)));
1751            let (first_kind, first_name) = names.next().unwrap();
1752            writeln!(
1753                message,
1754                "cycle {}: {first_kind} `{first_name}` must run before itself",
1755                i + 1,
1756            )
1757            .unwrap();
1758            writeln!(message, "{first_kind} `{first_name}`").unwrap();
1759            for (kind, name) in names.chain(std::iter::once((first_kind, first_name))) {
1760                writeln!(message, " ... which must run before {kind} `{name}`").unwrap();
1761            }
1762            writeln!(message).unwrap();
1763        }
1764
1765        message
1766    }
1767
1768    fn check_for_cross_dependencies(
1769        &self,
1770        dep_results: &CheckGraphResults<NodeId>,
1771        hier_results_connected: &HashSet<(NodeId, NodeId)>,
1772    ) -> Result<(), ScheduleBuildError> {
1773        for &(a, b) in &dep_results.connected {
1774            if hier_results_connected.contains(&(a, b)) || hier_results_connected.contains(&(b, a))
1775            {
1776                let name_a = self.get_node_name(&a);
1777                let name_b = self.get_node_name(&b);
1778                return Err(ScheduleBuildError::CrossDependency(name_a, name_b));
1779            }
1780        }
1781
1782        Ok(())
1783    }
1784
1785    fn check_order_but_intersect(
1786        &self,
1787        dep_results_connected: &HashSet<(NodeId, NodeId)>,
1788        set_system_bitsets: &HashMap<NodeId, FixedBitSet>,
1789    ) -> Result<(), ScheduleBuildError> {
1790        // check that there is no ordering between system sets that intersect
1791        for (a, b) in dep_results_connected {
1792            if !(a.is_set() && b.is_set()) {
1793                continue;
1794            }
1795
1796            let a_systems = set_system_bitsets.get(a).unwrap();
1797            let b_systems = set_system_bitsets.get(b).unwrap();
1798
1799            if !a_systems.is_disjoint(b_systems) {
1800                return Err(ScheduleBuildError::SetsHaveOrderButIntersect(
1801                    self.get_node_name(a),
1802                    self.get_node_name(b),
1803                ));
1804            }
1805        }
1806
1807        Ok(())
1808    }
1809
1810    fn check_system_type_set_ambiguity(
1811        &self,
1812        set_systems: &HashMap<NodeId, Vec<NodeId>>,
1813    ) -> Result<(), ScheduleBuildError> {
1814        for (&id, systems) in set_systems {
1815            let set = &self.system_sets[id.index()];
1816            if set.is_system_type() {
1817                let instances = systems.len();
1818                let ambiguous_with = self.ambiguous_with.edges(id);
1819                let before = self.dependency.graph.edges_directed(id, Incoming);
1820                let after = self.dependency.graph.edges_directed(id, Outgoing);
1821                let relations = before.count() + after.count() + ambiguous_with.count();
1822                if instances > 1 && relations > 0 {
1823                    return Err(ScheduleBuildError::SystemTypeSetAmbiguity(
1824                        self.get_node_name(&id),
1825                    ));
1826                }
1827            }
1828        }
1829        Ok(())
1830    }
1831
1832    /// if [`ScheduleBuildSettings::ambiguity_detection`] is [`LogLevel::Ignore`], this check is skipped
1833    fn optionally_check_conflicts(
1834        &self,
1835        conflicts: &[(NodeId, NodeId, Vec<ComponentId>)],
1836        components: &Components,
1837        schedule_label: InternedScheduleLabel,
1838    ) -> Result<(), ScheduleBuildError> {
1839        if self.settings.ambiguity_detection == LogLevel::Ignore || conflicts.is_empty() {
1840            return Ok(());
1841        }
1842
1843        let message = self.get_conflicts_error_message(conflicts, components);
1844        match self.settings.ambiguity_detection {
1845            LogLevel::Ignore => Ok(()),
1846            LogLevel::Warn => {
1847                warn!("Schedule {schedule_label:?} has ambiguities.\n{}", message);
1848                Ok(())
1849            }
1850            LogLevel::Error => Err(ScheduleBuildError::Ambiguity(message)),
1851        }
1852    }
1853
1854    fn get_conflicts_error_message(
1855        &self,
1856        ambiguities: &[(NodeId, NodeId, Vec<ComponentId>)],
1857        components: &Components,
1858    ) -> String {
1859        let n_ambiguities = ambiguities.len();
1860
1861        let mut message = format!(
1862                "{n_ambiguities} pairs of systems with conflicting data access have indeterminate execution order. \
1863                Consider adding `before`, `after`, or `ambiguous_with` relationships between these:\n",
1864            );
1865
1866        for (name_a, name_b, conflicts) in self.conflicts_to_string(ambiguities, components) {
1867            writeln!(message, " -- {name_a} and {name_b}").unwrap();
1868
1869            if !conflicts.is_empty() {
1870                writeln!(message, "    conflict on: {conflicts:?}").unwrap();
1871            } else {
1872                // one or both systems must be exclusive
1873                let world = std::any::type_name::<World>();
1874                writeln!(message, "    conflict on: {world}").unwrap();
1875            }
1876        }
1877
1878        message
1879    }
1880
1881    /// convert conflicts to human readable format
1882    pub fn conflicts_to_string<'a>(
1883        &'a self,
1884        ambiguities: &'a [(NodeId, NodeId, Vec<ComponentId>)],
1885        components: &'a Components,
1886    ) -> impl Iterator<Item = (String, String, Vec<&str>)> + 'a {
1887        ambiguities
1888            .iter()
1889            .map(move |(system_a, system_b, conflicts)| {
1890                let name_a = self.get_node_name(system_a);
1891                let name_b = self.get_node_name(system_b);
1892
1893                debug_assert!(system_a.is_system(), "{name_a} is not a system.");
1894                debug_assert!(system_b.is_system(), "{name_b} is not a system.");
1895
1896                let conflict_names: Vec<_> = conflicts
1897                    .iter()
1898                    .map(|id| components.get_name(*id).unwrap())
1899                    .collect();
1900
1901                (name_a, name_b, conflict_names)
1902            })
1903    }
1904
1905    fn traverse_sets_containing_node(&self, id: NodeId, f: &mut impl FnMut(NodeId) -> bool) {
1906        for (set_id, _, _) in self.hierarchy.graph.edges_directed(id, Incoming) {
1907            if f(set_id) {
1908                self.traverse_sets_containing_node(set_id, f);
1909            }
1910        }
1911    }
1912
1913    fn names_of_sets_containing_node(&self, id: &NodeId) -> Vec<String> {
1914        let mut sets = HashSet::new();
1915        self.traverse_sets_containing_node(*id, &mut |set_id| {
1916            !self.system_sets[set_id.index()].is_system_type() && sets.insert(set_id)
1917        });
1918        let mut sets: Vec<_> = sets
1919            .into_iter()
1920            .map(|set_id| self.get_node_name(&set_id))
1921            .collect();
1922        sets.sort();
1923        sets
1924    }
1925}
1926
1927/// Category of errors encountered during schedule construction.
1928#[derive(Error, Debug)]
1929#[non_exhaustive]
1930pub enum ScheduleBuildError {
1931    /// A system set contains itself.
1932    #[error("System set `{0}` contains itself.")]
1933    HierarchyLoop(String),
1934    /// The hierarchy of system sets contains a cycle.
1935    #[error("System set hierarchy contains cycle(s).\n{0}")]
1936    HierarchyCycle(String),
1937    /// The hierarchy of system sets contains redundant edges.
1938    ///
1939    /// This error is disabled by default, but can be opted-in using [`ScheduleBuildSettings`].
1940    #[error("System set hierarchy contains redundant edges.\n{0}")]
1941    HierarchyRedundancy(String),
1942    /// A system (set) has been told to run before itself.
1943    #[error("System set `{0}` depends on itself.")]
1944    DependencyLoop(String),
1945    /// The dependency graph contains a cycle.
1946    #[error("System dependencies contain cycle(s).\n{0}")]
1947    DependencyCycle(String),
1948    /// Tried to order a system (set) relative to a system set it belongs to.
1949    #[error("`{0}` and `{1}` have both `in_set` and `before`-`after` relationships (these might be transitive). This combination is unsolvable as a system cannot run before or after a set it belongs to.")]
1950    CrossDependency(String, String),
1951    /// Tried to order system sets that share systems.
1952    #[error("`{0}` and `{1}` have a `before`-`after` relationship (which may be transitive) but share systems.")]
1953    SetsHaveOrderButIntersect(String, String),
1954    /// Tried to order a system (set) relative to all instances of some system function.
1955    #[error("Tried to order against `{0}` in a schedule that has more than one `{0}` instance. `{0}` is a `SystemTypeSet` and cannot be used for ordering if ambiguous. Use a different set without this restriction.")]
1956    SystemTypeSetAmbiguity(String),
1957    /// Systems with conflicting access have indeterminate run order.
1958    ///
1959    /// This error is disabled by default, but can be opted-in using [`ScheduleBuildSettings`].
1960    #[error("Systems with conflicting access have indeterminate run order.\n{0}")]
1961    Ambiguity(String),
1962    /// Tried to run a schedule before all of its systems have been initialized.
1963    #[error("Systems in schedule have not been initialized.")]
1964    Uninitialized,
1965}
1966
1967/// Specifies how schedule construction should respond to detecting a certain kind of issue.
1968#[derive(Debug, Clone, PartialEq)]
1969pub enum LogLevel {
1970    /// Occurrences are completely ignored.
1971    Ignore,
1972    /// Occurrences are logged only.
1973    Warn,
1974    /// Occurrences are logged and result in errors.
1975    Error,
1976}
1977
1978/// Specifies miscellaneous settings for schedule construction.
1979#[derive(Clone, Debug)]
1980pub struct ScheduleBuildSettings {
1981    /// Determines whether the presence of ambiguities (systems with conflicting access but indeterminate order)
1982    /// is only logged or also results in an [`Ambiguity`](ScheduleBuildError::Ambiguity) error.
1983    ///
1984    /// Defaults to [`LogLevel::Ignore`].
1985    pub ambiguity_detection: LogLevel,
1986    /// Determines whether the presence of redundant edges in the hierarchy of system sets is only
1987    /// logged or also results in a [`HierarchyRedundancy`](ScheduleBuildError::HierarchyRedundancy)
1988    /// error.
1989    ///
1990    /// Defaults to [`LogLevel::Warn`].
1991    pub hierarchy_detection: LogLevel,
1992    /// Auto insert [`apply_deferred`] systems into the schedule,
1993    /// when there are [`Deferred`](crate::prelude::Deferred)
1994    /// in one system and there are ordering dependencies on that system. [`Commands`](crate::system::Commands) is one
1995    /// such deferred buffer.
1996    ///
1997    /// You may want to disable this if you only want to sync deferred params at the end of the schedule,
1998    /// or want to manually insert all your sync points.
1999    ///
2000    /// Defaults to `true`
2001    pub auto_insert_apply_deferred: bool,
2002    /// If set to true, node names will be shortened instead of the fully qualified type path.
2003    ///
2004    /// Defaults to `true`.
2005    pub use_shortnames: bool,
2006    /// If set to true, report all system sets the conflicting systems are part of.
2007    ///
2008    /// Defaults to `true`.
2009    pub report_sets: bool,
2010}
2011
2012impl Default for ScheduleBuildSettings {
2013    fn default() -> Self {
2014        Self::new()
2015    }
2016}
2017
2018impl ScheduleBuildSettings {
2019    /// Default build settings.
2020    /// See the field-level documentation for the default value of each field.
2021    pub const fn new() -> Self {
2022        Self {
2023            ambiguity_detection: LogLevel::Ignore,
2024            hierarchy_detection: LogLevel::Warn,
2025            auto_insert_apply_deferred: true,
2026            use_shortnames: true,
2027            report_sets: true,
2028        }
2029    }
2030}
2031
2032/// Error to denote that [`Schedule::initialize`] or [`Schedule::run`] has not yet been called for
2033/// this schedule.
2034#[derive(Error, Debug)]
2035#[error("executable schedule has not been built")]
2036pub struct ScheduleNotInitialized;
2037
2038#[cfg(test)]
2039mod tests {
2040    use bevy_ecs_macros::ScheduleLabel;
2041
2042    use crate::{
2043        self as bevy_ecs,
2044        prelude::{Res, Resource},
2045        schedule::{
2046            tests::ResMut, IntoSystemConfigs, IntoSystemSetConfigs, Schedule,
2047            ScheduleBuildSettings, SystemSet,
2048        },
2049        system::Commands,
2050        world::World,
2051    };
2052
2053    use super::Schedules;
2054
2055    #[derive(Resource)]
2056    struct Resource1;
2057
2058    #[derive(Resource)]
2059    struct Resource2;
2060
2061    // regression test for https://github.com/bevyengine/bevy/issues/9114
2062    #[test]
2063    fn ambiguous_with_not_breaking_run_conditions() {
2064        #[derive(SystemSet, Debug, Clone, PartialEq, Eq, Hash)]
2065        struct Set;
2066
2067        let mut world = World::new();
2068        let mut schedule = Schedule::default();
2069
2070        schedule.configure_sets(Set.run_if(|| false));
2071        schedule.add_systems(
2072            (|| panic!("This system must not run"))
2073                .ambiguous_with(|| ())
2074                .in_set(Set),
2075        );
2076        schedule.run(&mut world);
2077    }
2078
2079    #[test]
2080    fn inserts_a_sync_point() {
2081        let mut schedule = Schedule::default();
2082        let mut world = World::default();
2083        schedule.add_systems(
2084            (
2085                |mut commands: Commands| commands.insert_resource(Resource1),
2086                |_: Res<Resource1>| {},
2087            )
2088                .chain(),
2089        );
2090        schedule.run(&mut world);
2091
2092        // inserted a sync point
2093        assert_eq!(schedule.executable.systems.len(), 3);
2094    }
2095
2096    #[test]
2097    fn merges_sync_points_into_one() {
2098        let mut schedule = Schedule::default();
2099        let mut world = World::default();
2100        // insert two parallel command systems, it should only create one sync point
2101        schedule.add_systems(
2102            (
2103                (
2104                    |mut commands: Commands| commands.insert_resource(Resource1),
2105                    |mut commands: Commands| commands.insert_resource(Resource2),
2106                ),
2107                |_: Res<Resource1>, _: Res<Resource2>| {},
2108            )
2109                .chain(),
2110        );
2111        schedule.run(&mut world);
2112
2113        // inserted sync points
2114        assert_eq!(schedule.executable.systems.len(), 4);
2115
2116        // merges sync points on rebuild
2117        schedule.add_systems(((
2118            (
2119                |mut commands: Commands| commands.insert_resource(Resource1),
2120                |mut commands: Commands| commands.insert_resource(Resource2),
2121            ),
2122            |_: Res<Resource1>, _: Res<Resource2>| {},
2123        )
2124            .chain(),));
2125        schedule.run(&mut world);
2126
2127        assert_eq!(schedule.executable.systems.len(), 7);
2128    }
2129
2130    #[test]
2131    fn adds_multiple_consecutive_syncs() {
2132        let mut schedule = Schedule::default();
2133        let mut world = World::default();
2134        // insert two consecutive command systems, it should create two sync points
2135        schedule.add_systems(
2136            (
2137                |mut commands: Commands| commands.insert_resource(Resource1),
2138                |mut commands: Commands| commands.insert_resource(Resource2),
2139                |_: Res<Resource1>, _: Res<Resource2>| {},
2140            )
2141                .chain(),
2142        );
2143        schedule.run(&mut world);
2144
2145        assert_eq!(schedule.executable.systems.len(), 5);
2146    }
2147
2148    #[test]
2149    fn disable_auto_sync_points() {
2150        let mut schedule = Schedule::default();
2151        schedule.set_build_settings(ScheduleBuildSettings {
2152            auto_insert_apply_deferred: false,
2153            ..Default::default()
2154        });
2155        let mut world = World::default();
2156        schedule.add_systems(
2157            (
2158                |mut commands: Commands| commands.insert_resource(Resource1),
2159                |res: Option<Res<Resource1>>| assert!(res.is_none()),
2160            )
2161                .chain(),
2162        );
2163        schedule.run(&mut world);
2164
2165        assert_eq!(schedule.executable.systems.len(), 2);
2166    }
2167
2168    mod no_sync_edges {
2169        use super::*;
2170
2171        fn insert_resource(mut commands: Commands) {
2172            commands.insert_resource(Resource1);
2173        }
2174
2175        fn resource_does_not_exist(res: Option<Res<Resource1>>) {
2176            assert!(res.is_none());
2177        }
2178
2179        #[derive(SystemSet, Hash, PartialEq, Eq, Debug, Clone)]
2180        enum Sets {
2181            A,
2182            B,
2183        }
2184
2185        fn check_no_sync_edges(add_systems: impl FnOnce(&mut Schedule)) {
2186            let mut schedule = Schedule::default();
2187            let mut world = World::default();
2188            add_systems(&mut schedule);
2189
2190            schedule.run(&mut world);
2191
2192            assert_eq!(schedule.executable.systems.len(), 2);
2193        }
2194
2195        #[test]
2196        fn system_to_system_after() {
2197            check_no_sync_edges(|schedule| {
2198                schedule.add_systems((
2199                    insert_resource,
2200                    resource_does_not_exist.after_ignore_deferred(insert_resource),
2201                ));
2202            });
2203        }
2204
2205        #[test]
2206        fn system_to_system_before() {
2207            check_no_sync_edges(|schedule| {
2208                schedule.add_systems((
2209                    insert_resource.before_ignore_deferred(resource_does_not_exist),
2210                    resource_does_not_exist,
2211                ));
2212            });
2213        }
2214
2215        #[test]
2216        fn set_to_system_after() {
2217            check_no_sync_edges(|schedule| {
2218                schedule
2219                    .add_systems((insert_resource, resource_does_not_exist.in_set(Sets::A)))
2220                    .configure_sets(Sets::A.after_ignore_deferred(insert_resource));
2221            });
2222        }
2223
2224        #[test]
2225        fn set_to_system_before() {
2226            check_no_sync_edges(|schedule| {
2227                schedule
2228                    .add_systems((insert_resource.in_set(Sets::A), resource_does_not_exist))
2229                    .configure_sets(Sets::A.before_ignore_deferred(resource_does_not_exist));
2230            });
2231        }
2232
2233        #[test]
2234        fn set_to_set_after() {
2235            check_no_sync_edges(|schedule| {
2236                schedule
2237                    .add_systems((
2238                        insert_resource.in_set(Sets::A),
2239                        resource_does_not_exist.in_set(Sets::B),
2240                    ))
2241                    .configure_sets(Sets::B.after_ignore_deferred(Sets::A));
2242            });
2243        }
2244
2245        #[test]
2246        fn set_to_set_before() {
2247            check_no_sync_edges(|schedule| {
2248                schedule
2249                    .add_systems((
2250                        insert_resource.in_set(Sets::A),
2251                        resource_does_not_exist.in_set(Sets::B),
2252                    ))
2253                    .configure_sets(Sets::A.before_ignore_deferred(Sets::B));
2254            });
2255        }
2256    }
2257
2258    mod no_sync_chain {
2259        use super::*;
2260
2261        #[derive(Resource)]
2262        struct Ra;
2263
2264        #[derive(Resource)]
2265        struct Rb;
2266
2267        #[derive(Resource)]
2268        struct Rc;
2269
2270        fn run_schedule(expected_num_systems: usize, add_systems: impl FnOnce(&mut Schedule)) {
2271            let mut schedule = Schedule::default();
2272            let mut world = World::default();
2273            add_systems(&mut schedule);
2274
2275            schedule.run(&mut world);
2276
2277            assert_eq!(schedule.executable.systems.len(), expected_num_systems);
2278        }
2279
2280        #[test]
2281        fn only_chain_outside() {
2282            run_schedule(5, |schedule: &mut Schedule| {
2283                schedule.add_systems(
2284                    (
2285                        (
2286                            |mut commands: Commands| commands.insert_resource(Ra),
2287                            |mut commands: Commands| commands.insert_resource(Rb),
2288                        ),
2289                        (
2290                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2291                                assert!(res_a.is_some());
2292                                assert!(res_b.is_some());
2293                            },
2294                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2295                                assert!(res_a.is_some());
2296                                assert!(res_b.is_some());
2297                            },
2298                        ),
2299                    )
2300                        .chain(),
2301                );
2302            });
2303
2304            run_schedule(4, |schedule: &mut Schedule| {
2305                schedule.add_systems(
2306                    (
2307                        (
2308                            |mut commands: Commands| commands.insert_resource(Ra),
2309                            |mut commands: Commands| commands.insert_resource(Rb),
2310                        ),
2311                        (
2312                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2313                                assert!(res_a.is_none());
2314                                assert!(res_b.is_none());
2315                            },
2316                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2317                                assert!(res_a.is_none());
2318                                assert!(res_b.is_none());
2319                            },
2320                        ),
2321                    )
2322                        .chain_ignore_deferred(),
2323                );
2324            });
2325        }
2326
2327        #[test]
2328        fn chain_first() {
2329            run_schedule(6, |schedule: &mut Schedule| {
2330                schedule.add_systems(
2331                    (
2332                        (
2333                            |mut commands: Commands| commands.insert_resource(Ra),
2334                            |mut commands: Commands, res_a: Option<Res<Ra>>| {
2335                                commands.insert_resource(Rb);
2336                                assert!(res_a.is_some());
2337                            },
2338                        )
2339                            .chain(),
2340                        (
2341                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2342                                assert!(res_a.is_some());
2343                                assert!(res_b.is_some());
2344                            },
2345                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2346                                assert!(res_a.is_some());
2347                                assert!(res_b.is_some());
2348                            },
2349                        ),
2350                    )
2351                        .chain(),
2352                );
2353            });
2354
2355            run_schedule(5, |schedule: &mut Schedule| {
2356                schedule.add_systems(
2357                    (
2358                        (
2359                            |mut commands: Commands| commands.insert_resource(Ra),
2360                            |mut commands: Commands, res_a: Option<Res<Ra>>| {
2361                                commands.insert_resource(Rb);
2362                                assert!(res_a.is_some());
2363                            },
2364                        )
2365                            .chain(),
2366                        (
2367                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2368                                assert!(res_a.is_some());
2369                                assert!(res_b.is_none());
2370                            },
2371                            |res_a: Option<Res<Ra>>, res_b: Option<Res<Rb>>| {
2372                                assert!(res_a.is_some());
2373                                assert!(res_b.is_none());
2374                            },
2375                        ),
2376                    )
2377                        .chain_ignore_deferred(),
2378                );
2379            });
2380        }
2381
2382        #[test]
2383        fn chain_second() {
2384            run_schedule(6, |schedule: &mut Schedule| {
2385                schedule.add_systems(
2386                    (
2387                        (
2388                            |mut commands: Commands| commands.insert_resource(Ra),
2389                            |mut commands: Commands| commands.insert_resource(Rb),
2390                        ),
2391                        (
2392                            |mut commands: Commands,
2393                             res_a: Option<Res<Ra>>,
2394                             res_b: Option<Res<Rb>>| {
2395                                commands.insert_resource(Rc);
2396                                assert!(res_a.is_some());
2397                                assert!(res_b.is_some());
2398                            },
2399                            |res_a: Option<Res<Ra>>,
2400                             res_b: Option<Res<Rb>>,
2401                             res_c: Option<Res<Rc>>| {
2402                                assert!(res_a.is_some());
2403                                assert!(res_b.is_some());
2404                                assert!(res_c.is_some());
2405                            },
2406                        )
2407                            .chain(),
2408                    )
2409                        .chain(),
2410                );
2411            });
2412
2413            run_schedule(5, |schedule: &mut Schedule| {
2414                schedule.add_systems(
2415                    (
2416                        (
2417                            |mut commands: Commands| commands.insert_resource(Ra),
2418                            |mut commands: Commands| commands.insert_resource(Rb),
2419                        ),
2420                        (
2421                            |mut commands: Commands,
2422                             res_a: Option<Res<Ra>>,
2423                             res_b: Option<Res<Rb>>| {
2424                                commands.insert_resource(Rc);
2425                                assert!(res_a.is_none());
2426                                assert!(res_b.is_none());
2427                            },
2428                            |res_a: Option<Res<Ra>>,
2429                             res_b: Option<Res<Rb>>,
2430                             res_c: Option<Res<Rc>>| {
2431                                assert!(res_a.is_some());
2432                                assert!(res_b.is_some());
2433                                assert!(res_c.is_some());
2434                            },
2435                        )
2436                            .chain(),
2437                    )
2438                        .chain_ignore_deferred(),
2439                );
2440            });
2441        }
2442
2443        #[test]
2444        fn chain_all() {
2445            run_schedule(7, |schedule: &mut Schedule| {
2446                schedule.add_systems(
2447                    (
2448                        (
2449                            |mut commands: Commands| commands.insert_resource(Ra),
2450                            |mut commands: Commands, res_a: Option<Res<Ra>>| {
2451                                commands.insert_resource(Rb);
2452                                assert!(res_a.is_some());
2453                            },
2454                        )
2455                            .chain(),
2456                        (
2457                            |mut commands: Commands,
2458                             res_a: Option<Res<Ra>>,
2459                             res_b: Option<Res<Rb>>| {
2460                                commands.insert_resource(Rc);
2461                                assert!(res_a.is_some());
2462                                assert!(res_b.is_some());
2463                            },
2464                            |res_a: Option<Res<Ra>>,
2465                             res_b: Option<Res<Rb>>,
2466                             res_c: Option<Res<Rc>>| {
2467                                assert!(res_a.is_some());
2468                                assert!(res_b.is_some());
2469                                assert!(res_c.is_some());
2470                            },
2471                        )
2472                            .chain(),
2473                    )
2474                        .chain(),
2475                );
2476            });
2477
2478            run_schedule(6, |schedule: &mut Schedule| {
2479                schedule.add_systems(
2480                    (
2481                        (
2482                            |mut commands: Commands| commands.insert_resource(Ra),
2483                            |mut commands: Commands, res_a: Option<Res<Ra>>| {
2484                                commands.insert_resource(Rb);
2485                                assert!(res_a.is_some());
2486                            },
2487                        )
2488                            .chain(),
2489                        (
2490                            |mut commands: Commands,
2491                             res_a: Option<Res<Ra>>,
2492                             res_b: Option<Res<Rb>>| {
2493                                commands.insert_resource(Rc);
2494                                assert!(res_a.is_some());
2495                                assert!(res_b.is_none());
2496                            },
2497                            |res_a: Option<Res<Ra>>,
2498                             res_b: Option<Res<Rb>>,
2499                             res_c: Option<Res<Rc>>| {
2500                                assert!(res_a.is_some());
2501                                assert!(res_b.is_some());
2502                                assert!(res_c.is_some());
2503                            },
2504                        )
2505                            .chain(),
2506                    )
2507                        .chain_ignore_deferred(),
2508                );
2509            });
2510        }
2511    }
2512
2513    #[derive(ScheduleLabel, Hash, Debug, Clone, PartialEq, Eq)]
2514    struct TestSchedule;
2515
2516    #[derive(Resource)]
2517    struct CheckSystemRan(usize);
2518
2519    #[test]
2520    fn add_systems_to_existing_schedule() {
2521        let mut schedules = Schedules::default();
2522        let schedule = Schedule::new(TestSchedule);
2523
2524        schedules.insert(schedule);
2525        schedules.add_systems(TestSchedule, |mut ran: ResMut<CheckSystemRan>| ran.0 += 1);
2526
2527        let mut world = World::new();
2528
2529        world.insert_resource(CheckSystemRan(0));
2530        world.insert_resource(schedules);
2531        world.run_schedule(TestSchedule);
2532
2533        let value = world
2534            .get_resource::<CheckSystemRan>()
2535            .expect("CheckSystemRan Resource Should Exist");
2536        assert_eq!(value.0, 1);
2537    }
2538
2539    #[test]
2540    fn add_systems_to_non_existing_schedule() {
2541        let mut schedules = Schedules::default();
2542
2543        schedules.add_systems(TestSchedule, |mut ran: ResMut<CheckSystemRan>| ran.0 += 1);
2544
2545        let mut world = World::new();
2546
2547        world.insert_resource(CheckSystemRan(0));
2548        world.insert_resource(schedules);
2549        world.run_schedule(TestSchedule);
2550
2551        let value = world
2552            .get_resource::<CheckSystemRan>()
2553            .expect("CheckSystemRan Resource Should Exist");
2554        assert_eq!(value.0, 1);
2555    }
2556
2557    #[derive(SystemSet, Debug, Hash, Clone, PartialEq, Eq)]
2558    enum TestSet {
2559        First,
2560        Second,
2561    }
2562
2563    #[test]
2564    fn configure_set_on_existing_schedule() {
2565        let mut schedules = Schedules::default();
2566        let schedule = Schedule::new(TestSchedule);
2567
2568        schedules.insert(schedule);
2569
2570        schedules.configure_sets(TestSchedule, (TestSet::First, TestSet::Second).chain());
2571        schedules.add_systems(
2572            TestSchedule,
2573            (|mut ran: ResMut<CheckSystemRan>| {
2574                assert_eq!(ran.0, 0);
2575                ran.0 += 1;
2576            })
2577            .in_set(TestSet::First),
2578        );
2579
2580        schedules.add_systems(
2581            TestSchedule,
2582            (|mut ran: ResMut<CheckSystemRan>| {
2583                assert_eq!(ran.0, 1);
2584                ran.0 += 1;
2585            })
2586            .in_set(TestSet::Second),
2587        );
2588
2589        let mut world = World::new();
2590
2591        world.insert_resource(CheckSystemRan(0));
2592        world.insert_resource(schedules);
2593        world.run_schedule(TestSchedule);
2594
2595        let value = world
2596            .get_resource::<CheckSystemRan>()
2597            .expect("CheckSystemRan Resource Should Exist");
2598        assert_eq!(value.0, 2);
2599    }
2600
2601    #[test]
2602    fn configure_set_on_new_schedule() {
2603        let mut schedules = Schedules::default();
2604
2605        schedules.configure_sets(TestSchedule, (TestSet::First, TestSet::Second).chain());
2606        schedules.add_systems(
2607            TestSchedule,
2608            (|mut ran: ResMut<CheckSystemRan>| {
2609                assert_eq!(ran.0, 0);
2610                ran.0 += 1;
2611            })
2612            .in_set(TestSet::First),
2613        );
2614
2615        schedules.add_systems(
2616            TestSchedule,
2617            (|mut ran: ResMut<CheckSystemRan>| {
2618                assert_eq!(ran.0, 1);
2619                ran.0 += 1;
2620            })
2621            .in_set(TestSet::Second),
2622        );
2623
2624        let mut world = World::new();
2625
2626        world.insert_resource(CheckSystemRan(0));
2627        world.insert_resource(schedules);
2628        world.run_schedule(TestSchedule);
2629
2630        let value = world
2631            .get_resource::<CheckSystemRan>()
2632            .expect("CheckSystemRan Resource Should Exist");
2633        assert_eq!(value.0, 2);
2634    }
2635}