Depsgraph: New dependency graph integration commit
[blender.git] / source / blender / depsgraph / intern / depsgraph_query.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) 2013 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  *
26  * Implementation of Querying and Filtering API's
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 extern "C" {
32 #include "BLI_utildefines.h"
33 #include "BLI_ghash.h"
34
35 #include "BKE_main.h"
36
37 #include "DEG_depsgraph_query.h"
38 } /* extern "C" */
39
40 #include "depsgraph_queue.h"
41 #include "depsnode.h"
42 #include "depsnode_operation.h"
43 #include "depsgraph_intern.h"
44
45 /* ************************* */
46 /* Low-Level Graph Traversal */
47
48 #if 0
49 /* Prepare for graph traversal, by tagging nodes, etc. */
50 static void DEG_graph_traverse_begin(Depsgraph * /*graph*/)
51 {
52         /* go over all nodes, initialising the valence counts */
53         // XXX: this will end up being O(|V|), which is bad when we're just updating a few nodes...
54 }
55
56 /* Perform a traversal of graph from given starting node (in execution order) */
57 // TODO: additional flags for controlling the process?
58 void DEG_graph_traverse_from_node(Depsgraph *graph, OperationDepsNode *start_node,
59                                   DEG_FilterPredicate filter, void *filter_data,
60                                   DEG_NodeOperation op, void *operation_data)
61 {
62         DepsgraphQueue *q;
63
64         /* sanity checks */
65         if (ELEM(NULL, graph, start_node, op))
66                 return;
67
68         /* add node as starting node to be evaluated, with value of 0 */
69         q = DEG_queue_new();
70
71         start_node->num_links_pending = 0;
72         DEG_queue_push(q, start_node, 0.0f);
73
74         /* while we still have nodes in the queue, grab and work on next one */
75         do {
76                 /* grab item at front of queue */
77                 // XXX: in practice, we may need to wait until one becomes available...
78                 OperationDepsNode *node = (OperationDepsNode *)DEG_queue_pop(q);
79
80                 /* perform operation on node */
81                 op(graph, node, operation_data);
82
83                 /* schedule up operations which depend on this */
84                 DEPSNODE_RELATIONS_ITER_BEGIN(node->outlinks, rel)
85                 {
86                         /* ensure that relationship is not tagged for ignoring (i.e. cyclic, etc.) */
87                         // TODO: cyclic refs should probably all get clustered towards the end, so that we can just stop on the first one
88                         if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
89                                 OperationDepsNode *child_node = (OperationDepsNode *)rel->to;
90
91                                 /* only visit node if the filtering function agrees */
92                                 if ((filter == NULL) || filter(graph, child_node, filter_data)) {
93                                         /* schedule up node... */
94                                         child_node->num_links_pending--;
95                                         DEG_queue_push(q, child_node, (float)child_node->num_links_pending);
96                                 }
97                         }
98                 }
99                 DEPSNODE_RELATIONS_ITER_END;
100         } while (DEG_queue_is_empty(q) == false);
101
102         /* cleanup */
103         DEG_queue_free(q);
104 }
105 #endif
106
107 /* ************************************************************** */
108 /* Filtering API - Basically, making a copy of the existing graph */
109
110 /* Create filtering context */
111 // TODO: allow passing in a number of criteria?
112 DepsgraphCopyContext *DEG_filter_init()
113 {
114         DepsgraphCopyContext *dcc = (DepsgraphCopyContext *)MEM_callocN(sizeof(DepsgraphCopyContext), "DepsgraphCopyContext");
115
116         /* init hashes for easy lookups */
117         dcc->nodes_hash = BLI_ghash_ptr_new("Depsgraph Filter NodeHash");
118         dcc->rels_hash = BLI_ghash_ptr_new("Depsgraph Filter Relationship Hash"); // XXX?
119
120         /* store filtering criteria? */
121         // xxx...
122
123         return dcc;
124 }
125
126 /* Cleanup filtering context */
127 void DEG_filter_cleanup(DepsgraphCopyContext *dcc)
128 {
129         /* sanity check */
130         if (dcc == NULL)
131                 return;
132
133         /* free hashes - contents are weren't copied, so are ok... */
134         BLI_ghash_free(dcc->nodes_hash, NULL, NULL);
135         BLI_ghash_free(dcc->rels_hash, NULL, NULL);
136
137         /* clear filtering criteria */
138         // ...
139
140         /* free dcc itself */
141         MEM_freeN(dcc);
142 }
143
144 /* -------------------------------------------------- */
145
146 /* Create a copy of provided node */
147 // FIXME: the handling of sub-nodes and links will need to be subject to filtering options...
148 // XXX: perhaps this really shouldn't be exposed, as it will just be a sub-step of the evaluation process?
149 DepsNode *DEG_copy_node(DepsgraphCopyContext *dcc, const DepsNode *src)
150 {
151         /* sanity check */
152         if (src == NULL)
153                 return NULL;
154
155         DepsNodeFactory *factory = DEG_get_node_factory(src->type);
156         BLI_assert(factory != NULL);
157         DepsNode *dst = factory->copy_node(dcc, src);
158
159         /* add this node-pair to the hash... */
160         BLI_ghash_insert(dcc->nodes_hash, (DepsNode *)src, dst);
161
162 #if 0 /* XXX TODO */
163         /* now, fix up any links in standard "node header" (i.e. DepsNode struct, that all
164          * all others are derived from) that are now corrupt
165          */
166         {
167                 /* relationships to other nodes... */
168                 // FIXME: how to handle links? We may only have partial set of all nodes still?
169                 // XXX: the exact details of how to handle this are really part of the querying API...
170
171                 // XXX: BUT, for copying subgraphs, we'll need to define an API for doing this stuff anyways
172                 // (i.e. for resolving and patching over links that exist within subtree...)
173                 dst->inlinks.clear();
174                 dst->outlinks.clear();
175
176                 /* clear traversal data */
177                 dst->num_links_pending = 0;
178                 dst->lasttime = 0;
179         }
180
181         /* fix links */
182         // XXX...
183 #endif
184
185         /* return copied node */
186         return dst;
187 }
188
189 bool DEG_id_type_tagged(Main *bmain, short idtype)
190 {
191         return bmain->id_tag_update[((unsigned char *)&idtype)[0]] != 0;
192 }
193
194 short DEG_get_eval_flags_for_id(Depsgraph *graph, ID *id)
195 {
196         if (graph == NULL) {
197                 /* Happens when converting objects to mesh from a python script
198                  * after modifying scene graph.
199                  *
200                  * Currently harmless because it's only called for temporary
201                  * objects which are out of the DAG anyway.
202                  */
203                 return 0;
204         }
205
206         IDDepsNode *id_node = graph->find_id_node(id);
207         if (id_node == NULL) {
208                 /* TODO(sergey): Does it mean we need to check set scene? */
209                 return 0;
210         }
211
212         return id_node->eval_flags;
213 }