Blender V5.3
depsgraph_query_foreach.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2017 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <deque>
12#include <queue>
13
14#include "DEG_depsgraph.hh"
16
17#include "intern/depsgraph.hh"
24
25namespace blender {
26
27/* ************************ DEG TRAVERSAL ********************* */
28
29namespace deg {
30namespace {
31
32using TraversalQueue = std::deque<OperationNode *>;
33
34/* Returns true to continue iterating or false to stop. The `void *` is the `user_data` passed into
35 * the iterator. For example `ForeachNamedComponentData`. See deg_foreach_dependent_component.
36 */
37using DEGForeachOperation = bool (*)(OperationNode *, void *);
38
39bool deg_foreach_needs_visit(const OperationNode *op_node, const int flags)
40{
42 if (op_node->opcode == OperationCode::RIGIDBODY_SIM) {
43 return false;
44 }
45 }
46 return true;
47}
48
49void deg_foreach_dependent_operation(const Depsgraph * /*graph*/,
50 const IDNode *target_id_node,
51 eDepsObjectComponentType source_component_type,
52 int flags,
53 DEGForeachOperation callback,
54 void *user_data)
55{
56 if (target_id_node == nullptr) {
57 /* TODO(sergey): Shall we inform or assert here about attempt to start
58 * iterating over non-existing ID? */
59 return;
60 }
61 /* Start with scheduling all operations from ID node. */
62 TraversalQueue queue;
63 Set<OperationNode *> scheduled;
64 for (ComponentNode *comp_node : target_id_node->components.values()) {
65 if (comp_node->type == NodeType::VISIBILITY) {
66 /* Visibility component is only used internally. It is not to be reporting dependencies to
67 * the outer world. */
68 continue;
69 }
70
71 if (source_component_type != DEG_OB_COMP_ANY &&
72 nodeTypeToObjectComponent(comp_node->type) != source_component_type)
73 {
74 continue;
75 }
76 for (OperationNode *op_node : comp_node->operations) {
77 if (!deg_foreach_needs_visit(op_node, flags)) {
78 continue;
79 }
80 queue.push_back(op_node);
81 scheduled.add(op_node);
82 }
83 }
84 /* Process the queue. */
85 while (!queue.empty()) {
86 /* get next operation node to process. */
87 OperationNode *op_node = queue.front();
88 queue.pop_front();
89 for (;;) {
90 callback(op_node, user_data);
91 /* Schedule outgoing operation nodes. */
92 if (op_node->outlinks.size() == 1) {
93 OperationNode *to_node = static_cast<OperationNode *>(op_node->outlinks[0]->to);
94 if (!scheduled.contains(to_node) && deg_foreach_needs_visit(to_node, flags)) {
95 scheduled.add_new(to_node);
96 op_node = to_node;
97 }
98 else {
99 break;
100 }
101 }
102 else {
103 for (Relation *rel : op_node->outlinks) {
104 OperationNode *to_node = static_cast<OperationNode *>(rel->to);
105 if (!scheduled.contains(to_node) && deg_foreach_needs_visit(to_node, flags)) {
106 queue.push_front(to_node);
107 scheduled.add_new(to_node);
108 }
109 }
110 break;
111 }
112 }
113 }
114}
115
116/* Starting at the given component, iterate all outgoing links and call `callback` on them. Each
117 * OperationNode is only visited once. */
118void deg_foreach_dependent_operation(const ComponentNode &start_component,
119 DEGForeachOperation callback,
120 void *user_data)
121{
122 TraversalQueue queue;
123 Set<OperationNode *> was_queued;
124 /* Since the OperationNodes hold the connections it is the level we need to
125 * traverse on. */
126 for (OperationNode *op_node : start_component.operations) {
127 queue.push_back(op_node);
128 was_queued.add(op_node);
129 }
130
131 /* Traverse the graph. */
132 while (!queue.empty()) {
133 OperationNode *op_node = queue.front();
134 queue.pop_front();
135 if (!callback(op_node, user_data)) {
136 /* Don't visit outgoing links when the callback returns false. */
137 continue;
138 }
139 for (const Relation *rel : op_node->outlinks) {
140 OperationNode *to_node = static_cast<OperationNode *>(rel->to);
141 if (!was_queued.contains(to_node)) {
142 queue.push_back(to_node);
143 was_queued.add_new(to_node);
144 }
145 }
146 }
147}
148
149struct ForeachIDComponentData {
151 IDNode *target_id_node;
152 Set<ComponentNode *> visited;
153};
154
155struct ForeachNamedComponentData {
157};
158
159bool deg_foreach_dependent_component_callback(OperationNode *op_node, void *user_data_v)
160{
161 ForeachIDComponentData *user_data = reinterpret_cast<ForeachIDComponentData *>(user_data_v);
162 ComponentNode *comp_node = op_node->owner;
163 IDNode *id_node = comp_node->owner;
164 if (id_node != user_data->target_id_node && !user_data->visited.contains(comp_node)) {
165 user_data->callback(id_node->id_orig, nodeTypeToObjectComponent(comp_node->type));
166 user_data->visited.add_new(comp_node);
167 }
168 return true;
169}
170
171bool deg_foreach_named_dependent_component_callback(OperationNode *op_node, void *user_data_v)
172{
173 ForeachNamedComponentData *user_data = reinterpret_cast<ForeachNamedComponentData *>(
174 user_data_v);
175 ComponentNode *comp_node = op_node->owner;
176 if (comp_node->type == NodeType::VISIBILITY) {
177 /* Visibility component is only used internally, it should not be handed to the callback. See
178 * the assert in `nodeTypeToObjectComponent`.*/
179 return true;
180 }
181 IDNode *id_node = comp_node->owner;
182 return user_data->callback(
183 id_node->id_orig, nodeTypeToObjectComponent(comp_node->type), comp_node->name);
184}
185
186void deg_foreach_dependent_ID_component(const Depsgraph *graph,
187 const ID *id,
188 eDepsObjectComponentType source_component_type,
189 int flags,
191{
192 ForeachIDComponentData data;
193 data.callback = callback;
194 data.target_id_node = graph->find_id_node(id);
195 deg_foreach_dependent_operation(graph,
196 data.target_id_node,
197 source_component_type,
198 flags,
199 deg_foreach_dependent_component_callback,
200 &data);
201}
202
203void deg_foreach_dependent_component(const Depsgraph *graph,
204 const ID *start_id,
205 const eDepsObjectComponentType start_component_type,
206 const StringRef component_name,
208{
209 ForeachNamedComponentData data;
210 data.callback = callback;
211 IDNode *id_node = graph->find_id_node(start_id);
212 if (!id_node) {
213 return;
214 }
215
216 const ComponentNode *start_component = id_node->find_component(
217 nodeTypeFromObjectComponent(start_component_type), component_name);
218
219 if (!start_component) {
220 return;
221 }
222
223 deg_foreach_dependent_operation(
224 *start_component, deg_foreach_named_dependent_component_callback, &data);
225}
226
227struct ForeachIDData {
228 DEGForeachIDCallback callback;
229 IDNode *target_id_node;
230 Set<IDNode *> visited;
231};
232
233bool deg_foreach_dependent_ID_callback(OperationNode *op_node, void *user_data_v)
234{
235 ForeachIDData *user_data = reinterpret_cast<ForeachIDData *>(user_data_v);
236 ComponentNode *comp_node = op_node->owner;
237 IDNode *id_node = comp_node->owner;
238 if (id_node != user_data->target_id_node && !user_data->visited.contains(id_node)) {
239 user_data->callback(id_node->id_orig);
240 user_data->visited.add_new(id_node);
241 }
242 return true;
243}
244
245void deg_foreach_dependent_ID(const Depsgraph *graph, const ID *id, DEGForeachIDCallback callback)
246{
247 ForeachIDData data;
248 data.callback = callback;
249 data.target_id_node = graph->find_id_node(id);
250 deg_foreach_dependent_operation(
251 graph, data.target_id_node, DEG_OB_COMP_ANY, 0, deg_foreach_dependent_ID_callback, &data);
252}
253
254void deg_foreach_ancestor_ID(const Depsgraph *graph, const ID *id, DEGForeachIDCallback callback)
255{
256 /* Start with getting ID node from the graph. */
257 IDNode *target_id_node = graph->find_id_node(id);
258 if (target_id_node == nullptr) {
259 /* TODO(sergey): Shall we inform or assert here about attempt to start
260 * iterating over non-existing ID? */
261 return;
262 }
263 /* Start with scheduling all operations from ID node. */
264 TraversalQueue queue;
265 Set<OperationNode *> scheduled;
266 for (ComponentNode *comp_node : target_id_node->components.values()) {
267 for (OperationNode *op_node : comp_node->operations) {
268 queue.push_back(op_node);
269 scheduled.add(op_node);
270 }
271 }
272 Set<IDNode *> visited;
273 visited.add_new(target_id_node);
274 /* Process the queue. */
275 while (!queue.empty()) {
276 /* get next operation node to process. */
277 OperationNode *op_node = queue.front();
278 queue.pop_front();
279 for (;;) {
280 /* Check whether we need to inform callee about corresponding ID node. */
281 ComponentNode *comp_node = op_node->owner;
282 IDNode *id_node = comp_node->owner;
283 if (!visited.contains(id_node)) {
284 /* TODO(sergey): Is it orig or evaluated? */
285 callback(id_node->id_orig);
286 visited.add_new(id_node);
287 }
288 /* Schedule incoming operation nodes. */
289 if (op_node->inlinks.size() == 1) {
290 Node *from = op_node->inlinks[0]->from;
291 if (from->get_class() == NodeClass::OPERATION) {
292 OperationNode *from_node = static_cast<OperationNode *>(from);
293 if (scheduled.add(from_node)) {
294 op_node = from_node;
295 }
296 else {
297 break;
298 }
299 }
300 }
301 else {
302 for (Relation *rel : op_node->inlinks) {
303 Node *from = rel->from;
304 if (from->get_class() == NodeClass::OPERATION) {
305 OperationNode *from_node = static_cast<OperationNode *>(from);
306 if (scheduled.add(from_node)) {
307 queue.push_front(from_node);
308 }
309 }
310 }
311 break;
312 }
313 }
314 }
315}
316
317void deg_foreach_id(const Depsgraph *depsgraph, DEGForeachIDCallback callback)
318{
319 for (const IDNode *id_node : depsgraph->id_nodes) {
320 callback(id_node->id_orig);
321 }
322}
323
324/* Find the component node with the given type in the given ID node. Returns nullptr if no such
325 * component is found. */
326const ComponentNode *find_component_node(const IDNode &id_node, const NodeType component_node_type)
327{
328 for (const ComponentNode *component_node : id_node.components.values()) {
329 if (component_node->type == component_node_type) {
330 return component_node;
331 }
332 }
333
334 return nullptr;
335}
336
337/* The main implementation of DEG_scene_component_depends_on_time. It performs a backward breadth
338 * first search starting from the component node that matches the given component type until it
339 * finds the time source node of the graph if it exists. */
340bool deg_scene_component_depends_on_time(const Depsgraph &depsgraph,
341 const Scene &scene,
342 const eDepsSceneComponentType component_type)
343{
344 const TimeSourceNode *time_source_node = depsgraph.find_time_source();
345 if (!time_source_node) {
346 return false;
347 }
348
349 IDNode *scene_id_node = depsgraph.find_id_node(reinterpret_cast<const ID *>(&scene));
350 if (!scene_id_node) {
352 return false;
353 }
354
355 const NodeType component_node_type = nodeTypeFromSceneComponent(component_type);
356 const ComponentNode *component_node = find_component_node(*scene_id_node, component_node_type);
357 if (!component_node) {
359 return false;
360 }
361
362 std::queue<const Node *> queue;
363 Set<const Node *> nodes_already_scheduled;
364 queue.push(component_node);
365 nodes_already_scheduled.add_new(component_node);
366
367 for (const OperationNode *operation_node : component_node->operations) {
368 queue.push(operation_node);
369 nodes_already_scheduled.add_new(operation_node);
370 }
371
372 while (!queue.empty()) {
373 const Node *current_node = queue.front();
374 queue.pop();
375
376 for (const Relation *relation : current_node->inlinks) {
377 const Node *from_node = relation->from;
378 if (from_node == time_source_node) {
379 return true;
380 }
381
382 if (!nodes_already_scheduled.contains(from_node)) {
383 queue.push(from_node);
384 nodes_already_scheduled.add_new(from_node);
385 }
386 }
387 }
388
389 return false;
390}
391
392} // namespace
393} // namespace deg
394
395void DEG_foreach_dependent_ID(const Depsgraph *depsgraph,
396 const ID *id,
397 DEGForeachIDCallback callback)
398{
399 deg::deg_foreach_dependent_ID(reinterpret_cast<const deg::Depsgraph *>(depsgraph), id, callback);
400}
401
402void DEG_foreach_dependent_ID_component(const Depsgraph *depsgraph,
403 const ID *id,
404 eDepsObjectComponentType source_component_type,
405 int flags,
407{
408 deg::deg_foreach_dependent_ID_component(reinterpret_cast<const deg::Depsgraph *>(depsgraph),
409 id,
410 source_component_type,
411 flags,
412 callback);
413}
414
415void DEG_foreach_ancestor_ID(const Depsgraph *depsgraph,
416 const ID *id,
417 DEGForeachIDCallback callback)
418{
419 deg::deg_foreach_ancestor_ID(reinterpret_cast<const deg::Depsgraph *>(depsgraph), id, callback);
420}
421
422void DEG_foreach_dependent_component(const Depsgraph *depsgraph,
423 const ID *start_id,
424 const eDepsObjectComponentType start_component_type,
425 const StringRef start_component_name,
427{
428 const deg::Depsgraph *deg = reinterpret_cast<const deg::Depsgraph *>(depsgraph);
429 deg::deg_foreach_dependent_component(
430 deg, start_id, start_component_type, start_component_name, callback);
431}
432
433void DEG_foreach_ID(const Depsgraph *depsgraph, DEGForeachIDCallback callback)
434{
435 deg::deg_foreach_id(reinterpret_cast<const deg::Depsgraph *>(depsgraph), callback);
436}
437
438bool DEG_scene_component_depends_on_time(const Depsgraph &depsgraph,
439 const Scene &scene,
440 const eDepsSceneComponentType component_type)
441{
442
443 return deg::deg_scene_component_depends_on_time(
444 reinterpret_cast<const deg::Depsgraph &>(depsgraph), scene, component_type);
445}
446
447} // namespace blender
#define BLI_assert_unreachable()
eDepsObjectComponentType nodeTypeToObjectComponent(NodeType type)
Definition deg_node.cc:204
NodeType nodeTypeFromSceneComponent(eDepsSceneComponentType component)
Definition deg_node.cc:114
NodeType nodeTypeFromObjectComponent(eDepsObjectComponentType component_type)
Definition deg_node.cc:179
BMesh Iterators.
FunctionRef< bool(ID *id, eDepsObjectComponentType component, StringRef component_name)> DEGForeachNamedIDComponentCallback
void DEG_foreach_dependent_ID(const Depsgraph *depsgraph, const ID *id, DEGForeachIDCallback callback)
void DEG_foreach_ID(const Depsgraph *depsgraph, DEGForeachIDCallback callback)
BMesh const char void * data
void DEG_foreach_ancestor_ID(const Depsgraph *depsgraph, const ID *id, DEGForeachIDCallback callback)
void DEG_foreach_dependent_ID_component(const Depsgraph *depsgraph, const ID *id, eDepsObjectComponentType source_component_type, int flags, DEGForeachIDComponentCallback callback)
FunctionRef< void(ID *id, eDepsObjectComponentType component)> DEGForeachIDComponentCallback
@ DEG_FOREACH_COMPONENT_IGNORE_TRANSFORM_SOLVERS
void DEG_foreach_dependent_component(const Depsgraph *depsgraph, const ID *start_id, eDepsObjectComponentType start_component_type, StringRef start_component_name, DEGForeachNamedIDComponentCallback callback)
FunctionRef< void(ID *id)> DEGForeachIDCallback
bool DEG_scene_component_depends_on_time(const Depsgraph &depsgraph, const Scene &scene, const eDepsSceneComponentType component_type)
Relations inlinks
Definition deg_node.hh:188