bevy_ecs/schedule/
auto_insert_apply_deferred.rs

1use alloc::{boxed::Box, collections::BTreeSet, vec::Vec};
2
3use bevy_platform::{collections::HashMap, hash::FixedHasher};
4use indexmap::IndexSet;
5
6use crate::{
7    schedule::{graph::Dag, 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        dependency_flattened: &mut Dag<SystemKey>,
77    ) -> Result<(), ScheduleBuildError> {
78        let mut sync_point_graph = dependency_flattened.graph().clone();
79        let (topo, flat_dependency) = dependency_flattened
80            .toposort_and_graph()
81            .map_err(ScheduleBuildError::FlatDependencySort)?;
82
83        fn set_has_conditions(graph: &ScheduleGraph, set: SystemSetKey) -> bool {
84            graph.system_sets.has_conditions(set)
85                || graph
86                    .hierarchy()
87                    .graph()
88                    .edges_directed(NodeId::Set(set), Direction::Incoming)
89                    .any(|(parent, _)| {
90                        parent
91                            .as_set()
92                            .is_some_and(|p| set_has_conditions(graph, p))
93                    })
94        }
95
96        fn system_has_conditions(graph: &ScheduleGraph, key: SystemKey) -> bool {
97            graph.systems.has_conditions(key)
98                || graph
99                    .hierarchy()
100                    .graph()
101                    .edges_directed(NodeId::System(key), Direction::Incoming)
102                    .any(|(parent, _)| {
103                        parent
104                            .as_set()
105                            .is_some_and(|p| set_has_conditions(graph, p))
106                    })
107        }
108
109        let mut system_has_conditions_cache = HashMap::<SystemKey, bool>::default();
110        let mut is_valid_explicit_sync_point = |key: SystemKey| {
111            is_apply_deferred(&graph.systems[key])
112                && !*system_has_conditions_cache
113                    .entry(key)
114                    .or_insert_with(|| system_has_conditions(graph, key))
115        };
116
117        // Calculate the distance for each node.
118        // The "distance" is the number of sync points between a node and the beginning of the graph.
119        // Also store if a preceding edge would have added a sync point but was ignored to add it at
120        // a later edge that is not ignored.
121        let mut distances_and_pending_sync: HashMap<SystemKey, (u32, bool)> =
122            HashMap::with_capacity_and_hasher(topo.len(), Default::default());
123
124        // Keep track of any explicit sync nodes for a specific distance.
125        let mut distance_to_explicit_sync_node: HashMap<u32, SystemKey> = HashMap::default();
126
127        // Determine the distance for every node and collect the explicit sync points.
128        for &key in topo {
129            let (node_distance, mut node_needs_sync) = distances_and_pending_sync
130                .get(&key)
131                .copied()
132                .unwrap_or_default();
133
134            if is_valid_explicit_sync_point(key) {
135                // The distance of this sync point does not change anymore as the iteration order
136                // makes sure that this node is no unvisited target of another node.
137                // Because of this, the sync point can be stored for this distance to be reused as
138                // automatically added sync points later.
139                distance_to_explicit_sync_node.insert(node_distance, key);
140
141                // This node just did a sync, so the only reason to do another sync is if one was
142                // explicitly scheduled afterwards.
143                node_needs_sync = false;
144            } else if !node_needs_sync {
145                // No previous node has postponed sync points to add so check if the system itself
146                // has deferred params that require a sync point to apply them.
147                node_needs_sync = graph.systems[key].has_deferred();
148            }
149
150            for target in flat_dependency.neighbors_directed(key, Direction::Outgoing) {
151                let (target_distance, target_pending_sync) =
152                    distances_and_pending_sync.entry(target).or_default();
153
154                let mut edge_needs_sync = node_needs_sync;
155                if node_needs_sync
156                    && !graph.systems[target].is_exclusive()
157                    && self
158                        .no_sync_edges
159                        .contains(&(NodeId::System(key), NodeId::System(target)))
160                {
161                    // The node has deferred params to apply, but this edge is ignoring sync points.
162                    // Mark the target as 'delaying' those commands to a future edge and the current
163                    // edge as not needing a sync point.
164                    *target_pending_sync = true;
165                    edge_needs_sync = false;
166                }
167
168                let mut weight = 0;
169                if edge_needs_sync || is_valid_explicit_sync_point(target) {
170                    // The target distance grows if a sync point is added between it and the node.
171                    // Also raise the distance if the target is a sync point itself so it then again
172                    // raises the distance of following nodes as that is what the distance is about.
173                    weight = 1;
174                }
175
176                // The target cannot have fewer sync points in front of it than the preceding node.
177                *target_distance = (node_distance + weight).max(*target_distance);
178            }
179        }
180
181        // Find any edges which have a different number of sync points between them and make sure
182        // there is a sync point between them.
183        for &key in topo {
184            let (node_distance, _) = distances_and_pending_sync
185                .get(&key)
186                .copied()
187                .unwrap_or_default();
188
189            for target in flat_dependency.neighbors_directed(key, Direction::Outgoing) {
190                let (target_distance, _) = distances_and_pending_sync
191                    .get(&target)
192                    .copied()
193                    .unwrap_or_default();
194
195                if node_distance == target_distance {
196                    // These nodes are the same distance, so they don't need an edge between them.
197                    continue;
198                }
199
200                if is_apply_deferred(&graph.systems[target]) {
201                    // We don't need to insert a sync point since ApplyDeferred is a sync point
202                    // already!
203                    continue;
204                }
205
206                let sync_point = distance_to_explicit_sync_node
207                    .get(&target_distance)
208                    .copied()
209                    .unwrap_or_else(|| self.get_sync_point(graph, target_distance));
210
211                sync_point_graph.add_edge(key, sync_point);
212                sync_point_graph.add_edge(sync_point, target);
213
214                // The edge without the sync point is now redundant.
215                sync_point_graph.remove_edge(key, target);
216            }
217        }
218
219        **dependency_flattened = sync_point_graph;
220        Ok(())
221    }
222
223    fn collapse_set(
224        &mut self,
225        set: SystemSetKey,
226        systems: &IndexSet<SystemKey, FixedHasher>,
227        dependency_flattening: &DiGraph<NodeId>,
228    ) -> impl Iterator<Item = (NodeId, NodeId)> {
229        if systems.is_empty() {
230            // collapse dependencies for empty sets
231            for a in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Incoming)
232            {
233                for b in
234                    dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Outgoing)
235                {
236                    if self.no_sync_edges.contains(&(a, NodeId::Set(set)))
237                        && self.no_sync_edges.contains(&(NodeId::Set(set), b))
238                    {
239                        self.no_sync_edges.insert((a, b));
240                    }
241                }
242            }
243        } else {
244            for a in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Incoming)
245            {
246                for &sys in systems {
247                    if self.no_sync_edges.contains(&(a, NodeId::Set(set))) {
248                        self.no_sync_edges.insert((a, NodeId::System(sys)));
249                    }
250                }
251            }
252
253            for b in dependency_flattening.neighbors_directed(NodeId::Set(set), Direction::Outgoing)
254            {
255                for &sys in systems {
256                    if self.no_sync_edges.contains(&(NodeId::Set(set), b)) {
257                        self.no_sync_edges.insert((NodeId::System(sys), b));
258                    }
259                }
260            }
261        }
262        core::iter::empty()
263    }
264}
bevy_ecs/schedule/auto_insert_apply_deferred.rs

bevy_ecs/schedule/
auto_insert_apply_deferred.rs
