doxygen: add newline after \file
[blender.git] / source / blender / depsgraph / intern / depsgraph_query_foreach.cc
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2017 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup depsgraph
22  *
23  * Implementation of Querying and Filtering API's
24  */
25
26 // TODO(sergey): Use some sort of wrapper.
27 #include <deque>
28
29 #include "MEM_guardedalloc.h"
30
31 extern "C" {
32 #include "BLI_utildefines.h"
33 #include "BLI_ghash.h"
34 } /* extern "C" */
35
36 #include "DNA_object_types.h"
37 #include "DNA_scene_types.h"
38
39 #include "DEG_depsgraph.h"
40 #include "DEG_depsgraph_query.h"
41
42 #include "intern/depsgraph.h"
43 #include "intern/node/deg_node.h"
44 #include "intern/node/deg_node_component.h"
45 #include "intern/node/deg_node_id.h"
46 #include "intern/node/deg_node_operation.h"
47
48 /* ************************ DEG TRAVERSAL ********************* */
49
50 namespace DEG {
51
52 typedef std::deque<OperationNode *> TraversalQueue;
53 enum {
54         DEG_NODE_VISITED = (1 << 0),
55 };
56
57 static void deg_foreach_clear_flags(const Depsgraph *graph)
58 {
59         for (OperationNode *op_node : graph->operations) {
60                 op_node->scheduled = false;
61         }
62         for (IDNode *id_node : graph->id_nodes) {
63                 id_node->custom_flags = 0;
64         }
65 }
66
67 static void deg_foreach_dependent_ID(const Depsgraph *graph,
68                                      const ID *id,
69                                      DEGForeachIDCallback callback,
70                                      void *user_data)
71 {
72         /* Start with getting ID node from the graph. */
73         IDNode *target_id_node = graph->find_id_node(id);
74         if (target_id_node == NULL) {
75                 /* TODO(sergey): Shall we inform or assert here about attempt to start
76                  * iterating over non-existing ID? */
77                 return;
78         }
79         /* Make sure all runtime flags are ready and clear. */
80         deg_foreach_clear_flags(graph);
81         /* Start with scheduling all operations from ID node. */
82         TraversalQueue queue;
83         GHASH_FOREACH_BEGIN(ComponentNode *, comp_node, target_id_node->components)
84         {
85                 for (OperationNode *op_node : comp_node->operations) {
86                         queue.push_back(op_node);
87                         op_node->scheduled = true;
88                 }
89         }
90         GHASH_FOREACH_END();
91         target_id_node->custom_flags |= DEG_NODE_VISITED;
92         /* Process the queue. */
93         while (!queue.empty()) {
94                 /* get next operation node to process. */
95                 OperationNode *op_node = queue.front();
96                 queue.pop_front();
97                 for (;;) {
98                         /* Check whether we need to inform callee about corresponding ID node. */
99                         ComponentNode *comp_node = op_node->owner;
100                         IDNode *id_node = comp_node->owner;
101                         if ((id_node->custom_flags & DEG_NODE_VISITED) == 0) {
102                                 /* TODO(sergey): Is it orig or CoW? */
103                                 callback(id_node->id_orig, user_data);
104                                 id_node->custom_flags |= DEG_NODE_VISITED;
105                         }
106                         /* Schedule outgoing operation nodes. */
107                         if (op_node->outlinks.size() == 1) {
108                                 OperationNode *to_node = (OperationNode *)op_node->outlinks[0]->to;
109                                 if (to_node->scheduled == false) {
110                                         to_node->scheduled = true;
111                                         op_node = to_node;
112                                 }
113                                 else {
114                                         break;
115                                 }
116                         }
117                         else {
118                                 for (Relation *rel : op_node->outlinks) {
119                                         OperationNode *to_node = (OperationNode *)rel->to;
120                                         if (to_node->scheduled == false) {
121                                                 queue.push_front(to_node);
122                                                 to_node->scheduled = true;
123                                         }
124                                 }
125                                 break;
126                         }
127                 }
128         }
129 }
130
131 static void deg_foreach_ancestor_ID(const Depsgraph *graph,
132                                      const ID *id,
133                                      DEGForeachIDCallback callback,
134                                      void *user_data)
135 {
136         /* Start with getting ID node from the graph. */
137         IDNode *target_id_node = graph->find_id_node(id);
138         if (target_id_node == NULL) {
139                 /* TODO(sergey): Shall we inform or assert here about attempt to start
140                  * iterating over non-existing ID? */
141                 return;
142         }
143         /* Make sure all runtime flags are ready and clear. */
144         deg_foreach_clear_flags(graph);
145         /* Start with scheduling all operations from ID node. */
146         TraversalQueue queue;
147         GHASH_FOREACH_BEGIN(ComponentNode *, comp_node, target_id_node->components)
148         {
149                 for (OperationNode *op_node : comp_node->operations) {
150                         queue.push_back(op_node);
151                         op_node->scheduled = true;
152                 }
153         }
154         GHASH_FOREACH_END();
155         target_id_node->custom_flags |= DEG_NODE_VISITED;
156         /* Process the queue. */
157         while (!queue.empty()) {
158                 /* get next operation node to process. */
159                 OperationNode *op_node = queue.front();
160                 queue.pop_front();
161                 for (;;) {
162                         /* Check whether we need to inform callee about corresponding ID node. */
163                         ComponentNode *comp_node = op_node->owner;
164                         IDNode *id_node = comp_node->owner;
165                         if ((id_node->custom_flags & DEG_NODE_VISITED) == 0) {
166                                 /* TODO(sergey): Is it orig or CoW? */
167                                 callback(id_node->id_orig, user_data);
168                                 id_node->custom_flags |= DEG_NODE_VISITED;
169                         }
170                         /* Schedule incoming operation nodes. */
171                         if (op_node->inlinks.size() == 1) {
172                                 Node *from = op_node->inlinks[0]->from;
173                                 if (from->get_class() == NodeClass::OPERATION) {
174                                         OperationNode *from_node = (OperationNode *)from;
175                                         if (from_node->scheduled == false) {
176                                                 from_node->scheduled = true;
177                                                 op_node = from_node;
178                                         }
179                                         else {
180                                                 break;
181                                         }
182                                 }
183                         }
184                         else {
185                                 for (Relation *rel : op_node->inlinks) {
186                                         Node *from = rel->from;
187                                         if (from->get_class() == NodeClass::OPERATION) {
188                                                 OperationNode *from_node = (OperationNode *)from;
189                                                 if (from_node->scheduled == false) {
190                                                         queue.push_front(from_node);
191                                                         from_node->scheduled = true;
192                                                 }
193                                         }
194                                 }
195                                 break;
196                         }
197                 }
198         }
199 }
200
201 static void deg_foreach_id(const Depsgraph *depsgraph,
202                            DEGForeachIDCallback callback, void *user_data)
203 {
204         for (const IDNode *id_node : depsgraph->id_nodes) {
205                 callback(id_node->id_orig, user_data);
206         }
207 }
208
209 }  // namespace DEG
210
211 void DEG_foreach_dependent_ID(const Depsgraph *depsgraph,
212                               const ID *id,
213                               DEGForeachIDCallback callback, void *user_data)
214 {
215         DEG::deg_foreach_dependent_ID((const DEG::Depsgraph *)depsgraph,
216                                       id,
217                                       callback, user_data);
218 }
219
220 void DEG_foreach_ancestor_ID(const Depsgraph *depsgraph,
221                              const ID *id,
222                              DEGForeachIDCallback callback, void *user_data)
223 {
224         DEG::deg_foreach_ancestor_ID((const DEG::Depsgraph *)depsgraph,
225                                      id,
226                                      callback, user_data);
227 }
228
229 void DEG_foreach_ID(const Depsgraph *depsgraph,
230                     DEGForeachIDCallback callback, void *user_data)
231 {
232         DEG::deg_foreach_id((const DEG::Depsgraph *)depsgraph, callback, user_data);
233 }