Merge branch 'master' into blender2.8
[blender.git] / source / blender / depsgraph / intern / depsgraph_query_foreach.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2017 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Sergey Sharybin
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/depsgraph_query_foreach.cc
28  *  \ingroup depsgraph
29  *
30  * Implementation of Querying and Filtering API's
31  */
32
33 // TODO(sergey): Use some sort of wrapper.
34 #include <deque>
35
36 #include "MEM_guardedalloc.h"
37
38 extern "C" {
39 #include "BLI_utildefines.h"
40 #include "BLI_ghash.h"
41 } /* extern "C" */
42
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45
46 #include "DEG_depsgraph.h"
47 #include "DEG_depsgraph_query.h"
48
49 #include "intern/depsgraph_intern.h"
50
51 #include "intern/nodes/deg_node.h"
52 #include "intern/nodes/deg_node_component.h"
53 #include "intern/nodes/deg_node_id.h"
54 #include "intern/nodes/deg_node_operation.h"
55
56 #include "util/deg_util_foreach.h"
57
58 /* ************************ DEG TRAVERSAL ********************* */
59
60 namespace DEG {
61
62 typedef std::deque<OperationDepsNode *> TraversalQueue;
63
64 static void deg_foreach_clear_flags(const Depsgraph *graph)
65 {
66         foreach (OperationDepsNode *op_node, graph->operations) {
67                 op_node->scheduled = false;
68         }
69         foreach (IDDepsNode *id_node, graph->id_nodes) {
70                 id_node->done = false;
71         }
72 }
73
74 static void deg_foreach_dependent_ID(const Depsgraph *graph,
75                                      const ID *id,
76                                      DEGForeachIDCallback callback,
77                                      void *user_data)
78 {
79         /* Start with getting ID node from the graph. */
80         IDDepsNode *id_node = graph->find_id_node(id);
81         if (id_node == NULL) {
82                 /* TODO(sergey): Shall we inform or assert here about attempt to start
83                  * iterating over non-existing ID?
84                  */
85                 return;
86         }
87         /* Make sure all runtime flags are ready and clear. */
88         deg_foreach_clear_flags(graph);
89         /* Start with scheduling all operations from ID node. */
90         TraversalQueue queue;
91         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
92         {
93                 foreach (OperationDepsNode *op_node, comp_node->operations) {
94                         queue.push_back(op_node);
95                         op_node->scheduled = true;
96                 }
97         }
98         GHASH_FOREACH_END();
99         id_node->done = true;
100         /* Process the queue. */
101         while (!queue.empty()) {
102                 /* get next operation node to process. */
103                 OperationDepsNode *op_node = queue.front();
104                 queue.pop_front();
105                 for (;;) {
106                         /* Check whether we need to inform callee about corresponding ID node. */
107                         ComponentDepsNode *comp_node = op_node->owner;
108                         IDDepsNode *id_node = comp_node->owner;
109                         if (!id_node->done) {
110                                 /* TODO(sergey): Is it orig or CoW? */
111                                 callback(id_node->id_orig, user_data);
112                                 id_node->done = true;
113                         }
114                         /* Schedule outgoing operation nodes. */
115                         if (op_node->outlinks.size() == 1) {
116                                 OperationDepsNode *to_node = (OperationDepsNode *)op_node->outlinks[0]->to;
117                                 if (to_node->scheduled == false) {
118                                         to_node->scheduled = true;
119                                         op_node = to_node;
120                                 }
121                                 else {
122                                         break;
123                                 }
124                         }
125                         else {
126                                 foreach (DepsRelation *rel, op_node->outlinks) {
127                                         OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
128                                         if (to_node->scheduled == false) {
129                                                 queue.push_front(to_node);
130                                                 to_node->scheduled = true;
131                                         }
132                                 }
133                                 break;
134                         }
135                 }
136         }
137 }
138
139 }  // namespace DEG
140
141 void DEG_foreach_dependent_ID(const Depsgraph *depsgraph,
142                               const ID *id,
143                               DEGForeachIDCallback callback, void *user_data)
144 {
145         DEG::deg_foreach_dependent_ID((const DEG::Depsgraph *)depsgraph,
146                                       id,
147                                       callback, user_data);
148 }