bevy_ecs/schedule/
auto_insert_apply_deferred.rs

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

bevy_ecs/schedule/
auto_insert_apply_deferred.rs
