bevy_ecs/schedule/
auto_insert_apply_deferred.rs

1use alloc::{borrow::ToOwned, boxed::Box, collections::BTreeSet, vec::Vec};
2
3use bevy_platform::{collections::HashMap, hash::FixedHasher};
4use indexmap::IndexSet;
5
6use crate::{
7    schedule::{FlattenedDependencies, SystemKey, SystemSetKey},
8    system::{IntoSystem, System},
9    world::World,
10};
11
12use super::{
13    is_apply_deferred, ApplyDeferred, DiGraph, Direction, NodeId, ScheduleBuildError,
14    ScheduleBuildPass, ScheduleGraph,
15};
16
17/// A [`ScheduleBuildPass`] that inserts [`ApplyDeferred`] systems into the schedule graph
18/// when there are [`Deferred`](crate::prelude::Deferred)
19/// in one system and there are ordering dependencies on that system. [`Commands`](crate::system::Commands) is one
20/// such deferred buffer.
21///
22/// This pass is typically automatically added to the schedule. You can disable this by setting
23/// [`ScheduleBuildSettings::auto_insert_apply_deferred`](crate::schedule::ScheduleBuildSettings::auto_insert_apply_deferred)
24/// to `false`. You may want to disable this if you only want to sync deferred params at the end of the schedule,
25/// or want to manually insert all your sync points.
26#[derive(Debug, Default)]
27pub struct AutoInsertApplyDeferredPass {
28    /// Dependency edges that will **not** automatically insert an instance of `ApplyDeferred` on the edge.
29    no_sync_edges: BTreeSet<(NodeId, NodeId)>,
30    auto_sync_node_ids: HashMap<u32, SystemKey>,
31}
32
33/// If added to a dependency edge, the edge will not be considered for auto sync point insertions.
34pub struct IgnoreDeferred;
35
36impl AutoInsertApplyDeferredPass {
37    /// Returns the `NodeId` of the cached auto sync point. Will create
38    /// a new one if needed.
39    fn get_sync_point(&mut self, graph: &mut ScheduleGraph, distance: u32) -> SystemKey {
40        self.auto_sync_node_ids
41            .get(&distance)
42            .copied()
43            .unwrap_or_else(|| {
44                let key = self.add_auto_sync(graph);
45                self.auto_sync_node_ids.insert(distance, key);
46                key
47            })
48    }
49    /// add an [`ApplyDeferred`] system with no config
50    fn add_auto_sync(&mut self, graph: &mut ScheduleGraph) -> SystemKey {
51        let key = graph
52            .systems
53            .insert(Box::new(IntoSystem::into_system(ApplyDeferred)), Vec::new());
54
55        // ignore ambiguities with auto sync points
56        // They aren't under user control, so no one should know or care.
57        graph.ambiguous_with_all.insert(NodeId::System(key));
58
59        key
60    }
61}
62
63impl ScheduleBuildPass for AutoInsertApplyDeferredPass {
64    type EdgeOptions = IgnoreDeferred;
65
66    fn add_dependency(&mut self, from: NodeId, to: NodeId, options: Option<&Self::EdgeOptions>) {
67        if options.is_some() {
68            self.no_sync_edges.insert((from, to));
69        }
70    }
71
72    fn build(
73        &mut self,
74        _world: &mut World,
75        graph: &mut ScheduleGraph,
76        mut dependency_flattened: FlattenedDependencies<'_>,
77    ) -> Result<(), ScheduleBuildError> {
78        let (topo, flat_dependency) = dependency_flattened
79            .toposort_and_graph()
80            .map_err(ScheduleBuildError::FlatDependencySort)?;
81        let topo = topo.to_owned();
82        let flat_dependency = flat_dependency.to_owned();
83
84        fn set_has_conditions(graph: &ScheduleGraph, set: SystemSetKey) -> bool {
85            graph.system_sets.has_conditions(set)
86                || graph
87                    .hierarchy()
88                    .graph()
89                    .edges_directed(NodeId::Set(set), Direction::Incoming)
90                    .any(|(parent, _)| {
91                        parent
92                            .as_set()
93                            .is_some_and(|p| set_has_conditions(graph, p))
94                    })
95        }
96
97        fn system_has_conditions(graph: &ScheduleGraph, key: SystemKey) -> bool {
98            graph.systems.has_conditions(key)
99                || graph
100                    .hierarchy()
101                    .graph()
102                    .edges_directed(NodeId::System(key), Direction::Incoming)
103                    .any(|(parent, _)| {
104                        parent
105                            .as_set()
106                            .is_some_and(|p| set_has_conditions(graph, p))
107                    })
108        }
109
110        let mut system_has_conditions_cache = HashMap::<SystemKey, bool>::default();
111        let mut is_valid_explicit_sync_point = |key: SystemKey| {
112            is_apply_deferred(&graph.systems[key])
113                && !*system_has_conditions_cache
114                    .entry(key)
115                    .or_insert_with(|| system_has_conditions(graph, key))
116        };
117
118        // Calculate the distance for each node.
119        // The "distance" is the number of sync points between a node and the beginning of the graph.
120        // Also store if a preceding edge would have added a sync point but was ignored to add it at
121        // a later edge that is not ignored.
122        let mut distances_and_pending_sync: HashMap<SystemKey, (u32, bool)> =
123            HashMap::with_capacity_and_hasher(topo.len(), Default::default());
124
125        // Keep track of any explicit sync nodes for a specific distance.
126        let mut distance_to_explicit_sync_node: HashMap<u32, SystemKey> = HashMap::default();
127
128        // Determine the distance for every node and collect the explicit sync points.
129        for &key in topo.iter() {
130            let (node_distance, mut node_needs_sync) = distances_and_pending_sync
131                .get(&key)
132                .copied()
133                .unwrap_or_default();
134
135            if is_valid_explicit_sync_point(key) {
136                // The distance of this sync point does not change anymore as the iteration order
137                // makes sure that this node is no unvisited target of another node.
138                // Because of this, the sync point can be stored for this distance to be reused as
139                // automatically added sync points later.
140                distance_to_explicit_sync_node.insert(node_distance, key);
141
142                // This node just did a sync, so the only reason to do another sync is if one was
143                // explicitly scheduled afterwards.
144                node_needs_sync = false;
145            } else if !node_needs_sync {
146                // No previous node has postponed sync points to add so check if the system itself
147                // has deferred params that require a sync point to apply them.
148                node_needs_sync = graph.systems[key].has_deferred();
149            }
150
151            for target in flat_dependency.neighbors_directed(key, Direction::Outgoing) {
152                let (target_distance, target_pending_sync) =
153                    distances_and_pending_sync.entry(target).or_default();
154
155                let mut edge_needs_sync = node_needs_sync;
156                if node_needs_sync
157                    && !graph.systems[target].is_exclusive()
158                    && self
159                        .no_sync_edges
160                        .contains(&(NodeId::System(key), NodeId::System(target)))
161                {
162                    // The node has deferred params to apply, but this edge is ignoring sync points.
163                    // Mark the target as 'delaying' those commands to a future edge and the current
164                    // edge as not needing a sync point.
165                    *target_pending_sync = true;
166                    edge_needs_sync = false;
167                }
168
169                let mut weight = 0;
170                if edge_needs_sync || is_valid_explicit_sync_point(target) {
171                    // The target distance grows if a sync point is added between it and the node.
172                    // Also raise the distance if the target is a sync point itself so it then again
173                    // raises the distance of following nodes as that is what the distance is about.
174                    weight = 1;
175                }
176
177                // The target cannot have fewer sync points in front of it than the preceding node.
178                *target_distance = (node_distance + weight).max(*target_distance);
179            }
180        }
181
182        // Find any edges which have a different number of sync points between them and make sure
183        // there is a sync point between them.
184        for &key in topo.iter() {
185            let (node_distance, _) = distances_and_pending_sync
186                .get(&key)
187                .copied()
188                .unwrap_or_default();
189
190            for target in flat_dependency.neighbors_directed(key, Direction::Outgoing) {
191                let (target_distance, _) = distances_and_pending_sync
192                    .get(&target)
193                    .copied()
194                    .unwrap_or_default();
195
196                if node_distance == target_distance {
197                    // These nodes are the same distance, so they don't need an edge between them.
198                    continue;
199                }
200
201                if is_apply_deferred(&graph.systems[target]) {
202                    // We don't need to insert a sync point since ApplyDeferred is a sync point
203                    // already!
204                    continue;
205                }
206
207                let sync_point = distance_to_explicit_sync_node
208                    .get(&target_distance)
209                    .copied()
210                    .unwrap_or_else(|| self.get_sync_point(graph, target_distance));
211
212                dependency_flattened.add_edge(key, sync_point);
213                dependency_flattened.add_edge(sync_point, target);
214
215                // The edge without the sync point is now redundant.
216                dependency_flattened.remove_edge(key, target);
217            }
218        }
219        Ok(())
220    }
221
222    fn collapse_set(
223        &mut self,
224        set: SystemSetKey,
225        systems: &IndexSet<SystemKey, FixedHasher>,
226        dependency_flattening: &DiGraph<NodeId>,
227    ) -> impl Iterator<Item = (NodeId, NodeId)> {
228        if systems.is_empty() {
229            // collapse dependencies for empty sets
230            for a in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Incoming)
231            {
232                for b in
233                    dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Outgoing)
234                {
235                    if self.no_sync_edges.contains(&(a, NodeId::Set(set)))
236                        && self.no_sync_edges.contains(&(NodeId::Set(set), b))
237                    {
238                        self.no_sync_edges.insert((a, b));
239                    }
240                }
241            }
242        } else {
243            for a in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Incoming)
244            {
245                for &sys in systems {
246                    if self.no_sync_edges.contains(&(a, NodeId::Set(set))) {
247                        self.no_sync_edges.insert((a, NodeId::System(sys)));
248                    }
249                }
250            }
251
252            for b in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Outgoing)
253            {
254                for &sys in systems {
255                    if self.no_sync_edges.contains(&(NodeId::Set(set), b)) {
256                        self.no_sync_edges.insert((NodeId::System(sys), b));
257                    }
258                }
259            }
260        }
261        core::iter::empty()
262    }
263}
bevy_ecs/schedule/auto_insert_apply_deferred.rs

bevy_ecs/schedule/
auto_insert_apply_deferred.rs
