Merge branch 'master' into blender2.8
[blender.git] / source / blender / depsgraph / intern / depsgraph_debug.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) 2014 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Lukas Toenne
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/depsgraph_debug.cc
28  *  \ingroup depsgraph
29  *
30  * Implementation of tools for debugging the depsgraph
31  */
32
33 #include "BLI_utildefines.h"
34 #include "BLI_ghash.h"
35
36 extern "C" {
37 #include "DNA_scene_types.h"
38 }  /* extern "C" */
39
40 #include "DEG_depsgraph.h"
41 #include "DEG_depsgraph_debug.h"
42 #include "DEG_depsgraph_build.h"
43
44 #include "intern/depsgraph_intern.h"
45 #include "intern/nodes/deg_node_id.h"
46 #include "intern/nodes/deg_node_time.h"
47
48 #include "util/deg_util_foreach.h"
49
50 bool DEG_debug_compare(const struct Depsgraph *graph1,
51                        const struct Depsgraph *graph2)
52 {
53         BLI_assert(graph1 != NULL);
54         BLI_assert(graph2 != NULL);
55         const DEG::Depsgraph *deg_graph1 = reinterpret_cast<const DEG::Depsgraph *>(graph1);
56         const DEG::Depsgraph *deg_graph2 = reinterpret_cast<const DEG::Depsgraph *>(graph2);
57         if (deg_graph1->operations.size() != deg_graph2->operations.size()) {
58                 return false;
59         }
60         /* TODO(sergey): Currently we only do real stupid check,
61          * which is fast but which isn't 100% reliable.
62          *
63          * Would be cool to make it more robust, but it's good enough
64          * for now. Also, proper graph check is actually NP-complex
65          * problem..
66          */
67         return true;
68 }
69
70 bool DEG_debug_graph_relations_validate(Depsgraph *graph,
71                                         Main *bmain,
72                                         Scene *scene,
73                                         ViewLayer *view_layer)
74 {
75         Depsgraph *temp_depsgraph = DEG_graph_new();
76         bool valid = true;
77         DEG_graph_build_from_view_layer(temp_depsgraph, bmain, scene, view_layer);
78         if (!DEG_debug_compare(temp_depsgraph, graph)) {
79                 fprintf(stderr, "ERROR! Depsgraph wasn't tagged for update when it should have!\n");
80                 BLI_assert(!"This should not happen!");
81                 valid = false;
82         }
83         DEG_graph_free(temp_depsgraph);
84         return valid;
85 }
86
87 bool DEG_debug_consistency_check(Depsgraph *graph)
88 {
89         const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph);
90
91         /* Validate links exists in both directions. */
92         foreach (DEG::OperationDepsNode *node, deg_graph->operations) {
93                 foreach (DEG::DepsRelation *rel, node->outlinks) {
94                         int counter1 = 0;
95                         foreach (DEG::DepsRelation *tmp_rel, node->outlinks) {
96                                 if (tmp_rel == rel) {
97                                         ++counter1;
98                                 }
99                         }
100
101                         int counter2 = 0;
102                         foreach (DEG::DepsRelation *tmp_rel, rel->to->inlinks) {
103                                 if (tmp_rel == rel) {
104                                         ++counter2;
105                                 }
106                         }
107
108                         if (counter1 != counter2) {
109                                 printf("Relation exists in outgoing direction but not in incoming (%d vs. %d).\n",
110                                        counter1, counter2);
111                                 return false;
112                         }
113                 }
114         }
115
116         foreach (DEG::OperationDepsNode *node, deg_graph->operations) {
117                 foreach (DEG::DepsRelation *rel, node->inlinks) {
118                         int counter1 = 0;
119                         foreach (DEG::DepsRelation *tmp_rel, node->inlinks) {
120                                 if (tmp_rel == rel) {
121                                         ++counter1;
122                                 }
123                         }
124
125                         int counter2 = 0;
126                         foreach (DEG::DepsRelation *tmp_rel, rel->from->outlinks) {
127                                 if (tmp_rel == rel) {
128                                         ++counter2;
129                                 }
130                         }
131
132                         if (counter1 != counter2) {
133                                 printf("Relation exists in incoming direction but not in outcoming (%d vs. %d).\n",
134                                        counter1, counter2);
135                         }
136                 }
137         }
138
139         /* Validate node valency calculated in both directions. */
140         foreach (DEG::OperationDepsNode *node, deg_graph->operations) {
141                 node->num_links_pending = 0;
142                 node->done = 0;
143         }
144
145         foreach (DEG::OperationDepsNode *node, deg_graph->operations) {
146                 if (node->done) {
147                         printf("Node %s is twice in the operations!\n",
148                                node->identifier().c_str());
149                         return false;
150                 }
151                 foreach (DEG::DepsRelation *rel, node->outlinks) {
152                         if (rel->to->type == DEG::DEG_NODE_TYPE_OPERATION) {
153                                 DEG::OperationDepsNode *to = (DEG::OperationDepsNode *)rel->to;
154                                 BLI_assert(to->num_links_pending < to->inlinks.size());
155                                 ++to->num_links_pending;
156                         }
157                 }
158                 node->done = 1;
159         }
160
161         foreach (DEG::OperationDepsNode *node, deg_graph->operations) {
162                 int num_links_pending = 0;
163                 foreach (DEG::DepsRelation *rel, node->inlinks) {
164                         if (rel->from->type == DEG::DEG_NODE_TYPE_OPERATION) {
165                                 ++num_links_pending;
166                         }
167                 }
168                 if (node->num_links_pending != num_links_pending) {
169                         printf("Valency mismatch: %s, %u != %d\n",
170                                node->identifier().c_str(),
171                                node->num_links_pending, num_links_pending);
172                         printf("Number of inlinks: %d\n", (int)node->inlinks.size());
173                         return false;
174                 }
175         }
176         return true;
177 }
178
179 /* ------------------------------------------------ */
180
181 /**
182  * Obtain simple statistics about the complexity of the depsgraph
183  * \param[out] r_outer       The number of outer nodes in the graph
184  * \param[out] r_operations  The number of operation nodes in the graph
185  * \param[out] r_relations   The number of relations between (executable) nodes in the graph
186  */
187 void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer,
188                       size_t *r_operations, size_t *r_relations)
189 {
190         const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph);
191
192         /* number of operations */
193         if (r_operations) {
194                 /* All operations should be in this list, allowing us to count the total
195                  * number of nodes.
196                  */
197                 *r_operations = deg_graph->operations.size();
198         }
199
200         /* Count number of outer nodes and/or relations between these. */
201         if (r_outer || r_relations) {
202                 size_t tot_outer = 0;
203                 size_t tot_rels = 0;
204
205                 foreach (DEG::IDDepsNode *id_node, deg_graph->id_nodes) {
206                         tot_outer++;
207                         GHASH_FOREACH_BEGIN(DEG::ComponentDepsNode *, comp_node, id_node->components)
208                         {
209                                 tot_outer++;
210                                 foreach (DEG::OperationDepsNode *op_node, comp_node->operations) {
211                                         tot_rels += op_node->inlinks.size();
212                                 }
213                         }
214                         GHASH_FOREACH_END();
215                 }
216
217                 DEG::TimeSourceDepsNode *time_source = deg_graph->find_time_source();
218                 if (time_source != NULL) {
219                         tot_rels += time_source->inlinks.size();
220                 }
221
222                 if (r_relations) *r_relations = tot_rels;
223                 if (r_outer)     *r_outer     = tot_outer;
224         }
225 }