5498043673377eca069100844f559deb8a07f639
[blender-staging.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 <stdlib.h>
34 #include <string.h>
35
36 extern "C" {
37 #include "BLI_utildefines.h"
38 #include "BLI_listbase.h"
39 #include "BLI_ghash.h"
40 #include "BLI_string.h"
41
42 #include "DNA_scene_types.h"
43 #include "DNA_userdef_types.h"
44
45 #include "DEG_depsgraph.h"
46 #include "DEG_depsgraph_debug.h"
47 #include "DEG_depsgraph_build.h"
48
49 #include "WM_api.h"
50 #include "WM_types.h"
51 }  /* extern "C" */
52
53 #include "depsgraph_debug.h"
54 #include "depsnode.h"
55 #include "depsnode_component.h"
56 #include "depsnode_operation.h"
57 #include "depsgraph_intern.h"
58
59 /* ****************** */
60 /* Graphviz Debugging */
61
62 static SpinLock lock;
63
64 #define NL "\r\n"
65
66 /* Only one should be enabled, defines whether graphviz nodes
67  * get colored by individual types or classes.
68  */
69 #define COLOR_SCHEME_NODE_CLASS 1
70 //#define COLOR_SCHEME_NODE_TYPE  2
71
72 static const char *deg_debug_graphviz_fontname = "helvetica";
73 static float deg_debug_graphviz_graph_label_size = 20.0f;
74 static float deg_debug_graphviz_node_label_size = 14.0f;
75 static const int deg_debug_max_colors = 12;
76 #if 0
77 static const char *deg_debug_colors_dark[] = {
78     "#6e8997", "#144f77", "#76945b",
79     "#216a1d", "#a76665", "#971112",
80     "#a87f49", "#0a9540", "#86768e",
81     "#462866", "#a9a965", "#753b1a",
82 };
83 #endif
84 #ifdef COLOR_SCHEME_NODE_TYPE
85 static const char *deg_debug_colors[] = {
86     "#a6cee3", "#1f78b4", "#b2df8a",
87     "#33a02c", "#fb9a99", "#e31a1c",
88     "#fdbf6f", "#ff7f00", "#cab2d6",
89     "#6a3d9a", "#ffff99", "#b15928",
90 };
91 #endif
92 static const char *deg_debug_colors_light[] = {
93     "#8dd3c7", "#ffffb3", "#bebada",
94     "#fb8072", "#80b1d3", "#fdb462",
95     "#b3de69", "#fccde5", "#d9d9d9",
96     "#bc80bd", "#ccebc5", "#ffed6f",
97 };
98
99 #ifdef COLOR_SCHEME_NODE_TYPE
100 static const int deg_debug_node_type_color_map[][2] = {
101     {DEPSNODE_TYPE_ROOT,         0},
102     {DEPSNODE_TYPE_TIMESOURCE,   1},
103     {DEPSNODE_TYPE_ID_REF,       2},
104     {DEPSNODE_TYPE_SUBGRAPH,     3},
105
106     /* Outer Types */
107     {DEPSNODE_TYPE_PARAMETERS,   4},
108     {DEPSNODE_TYPE_PROXY,        5},
109     {DEPSNODE_TYPE_ANIMATION,    6},
110     {DEPSNODE_TYPE_TRANSFORM,    7},
111     {DEPSNODE_TYPE_GEOMETRY,     8},
112     {DEPSNODE_TYPE_SEQUENCER,    9},
113     {DEPSNODE_TYPE_SHADING,      10},
114     {-1,                         0}
115 };
116 #endif
117
118 #if 0 /* unused */
119 static const int deg_debug_relation_type_color_map[][2] = {
120     {DEPSREL_TYPE_STANDARD,         0},
121     {DEPSREL_TYPE_ROOT_TO_ACTIVE,   1},
122     {DEPSREL_TYPE_DATABLOCK,        2},
123     {DEPSREL_TYPE_TIME,             3},
124     {DEPSREL_TYPE_COMPONENT_ORDER,  4},
125     {DEPSREL_TYPE_OPERATION,        5},
126     {DEPSREL_TYPE_DRIVER,           6},
127     {DEPSREL_TYPE_DRIVER_TARGET,    7},
128     {DEPSREL_TYPE_TRANSFORM,        8},
129     {DEPSREL_TYPE_GEOMETRY_EVAL,    9},
130     {DEPSREL_TYPE_UPDATE,           10},
131     {DEPSREL_TYPE_UPDATE_UI,        11},
132     {-1,                            0}
133 };
134 #endif
135
136 static int deg_debug_node_color_index(const DepsNode *node)
137 {
138 #ifdef COLOR_SCHEME_NODE_CLASS
139         /* Some special types. */
140         switch (node->type) {
141                 case DEPSNODE_TYPE_ID_REF:
142                         return 5;
143                 case DEPSNODE_TYPE_OPERATION:
144                 {
145                         OperationDepsNode *op_node = (OperationDepsNode *)node;
146                         if (op_node->is_noop())
147                                 return 8;
148                 }
149
150                 default:
151                         break;
152         }
153         /* Do others based on class. */
154         switch (node->tclass) {
155                 case DEPSNODE_CLASS_OPERATION:
156                         return 4;
157                 case DEPSNODE_CLASS_COMPONENT:
158                         return 1;
159                 default:
160                         return 9;
161         }
162 #endif
163
164 #ifdef COLOR_SCHEME_NODE_TYPE
165         const int (*pair)[2];
166         for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) {
167                 if ((*pair)[0] == node->type) {
168                         return (*pair)[1];
169                 }
170         }
171         return -1;
172 #endif
173 }
174
175 struct DebugContext {
176         FILE *file;
177         bool show_tags;
178         bool show_eval_priority;
179 };
180
181 static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) ATTR_PRINTF_FORMAT(2, 3);
182 static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...)
183 {
184         va_list args;
185         va_start(args, fmt);
186         vfprintf(ctx.file, fmt, args);
187         va_end(args);
188 }
189
190 static void deg_debug_graphviz_legend_color(const DebugContext &ctx,
191                                             const char *name,
192                                             const char *color)
193 {
194         deg_debug_fprintf(ctx, "<TR>");
195         deg_debug_fprintf(ctx, "<TD>%s</TD>", name);
196         deg_debug_fprintf(ctx, "<TD BGCOLOR=\"%s\"></TD>", color);
197         deg_debug_fprintf(ctx, "</TR>" NL);
198 }
199
200 #if 0
201 static void deg_debug_graphviz_legend_line(const DebugContext &ctx,
202                                            const char *name,
203                                            const char *color,
204                                            const char *style)
205 {
206         /* XXX TODO */
207         deg_debug_fprintf(ctx, "" NL);
208 }
209
210 static void deg_debug_graphviz_legend_cluster(const DebugContext &ctx,
211                                               const char *name,
212                                               const char *color,
213                                               const char *style)
214 {
215         deg_debug_fprintf(ctx, "<TR>");
216         deg_debug_fprintf(ctx, "<TD>%s</TD>", name);
217         deg_debug_fprintf(ctx, "<TD CELLPADDING=\"4\"><TABLE BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"0\">");
218         deg_debug_fprintf(ctx, "<TR><TD BGCOLOR=\"%s\"></TD></TR>", color);
219         deg_debug_fprintf(ctx, "</TABLE></TD>");
220         deg_debug_fprintf(ctx, "</TR>" NL);
221 }
222 #endif
223
224 static void deg_debug_graphviz_legend(const DebugContext &ctx)
225 {
226         deg_debug_fprintf(ctx, "{" NL);
227         deg_debug_fprintf(ctx, "rank = sink;" NL);
228         deg_debug_fprintf(ctx, "Legend [shape=none, margin=0, label=<" NL);
229         deg_debug_fprintf(ctx, "  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">" NL);
230         deg_debug_fprintf(ctx, "<TR><TD COLSPAN=\"2\"><B>Legend</B></TD></TR>" NL);
231
232 #ifdef COLOR_SCHEME_NODE_CLASS
233         const char **colors = deg_debug_colors_light;
234         deg_debug_graphviz_legend_color(ctx, "Operation", colors[4]);
235         deg_debug_graphviz_legend_color(ctx, "Component", colors[1]);
236         deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]);
237         deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]);
238 #endif
239
240 #ifdef COLOR_SCHEME_NODE_TYPE
241         const int (*pair)[2];
242         for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) {
243                 DepsNodeFactory *nti = DEG_get_node_factory((eDepsNode_Type)(*pair)[0]);
244                 deg_debug_graphviz_legend_color(ctx,
245                                                 nti->tname().c_str(),
246                                                 deg_debug_colors_light[(*pair)[1] % deg_debug_max_colors]);
247         }
248 #endif
249
250         deg_debug_fprintf(ctx, "</TABLE>" NL);
251         deg_debug_fprintf(ctx, ">" NL);
252         deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
253         deg_debug_fprintf(ctx, "];" NL);
254         deg_debug_fprintf(ctx, "}" NL);
255 }
256
257 #if 0 /* unused */
258 static int deg_debug_relation_type_color_index(eDepsRelation_Type type)
259 {
260         const int (*pair)[2];
261         for (pair = deg_debug_relation_type_color_map; (*pair)[0] >= 0; ++pair) {
262                 if ((*pair)[0] == type) {
263                         return (*pair)[1];
264                 }
265         }
266         return -1;
267 }
268 #endif
269
270 static void deg_debug_graphviz_node_color(const DebugContext &ctx,
271                                           const DepsNode *node)
272 {
273         const char *color_default = "black";
274         const char *color_modified = "orangered4";
275         const char *color_update = "dodgerblue3";
276         const char *color = color_default;
277         if (ctx.show_tags) {
278                 if (node->tclass == DEPSNODE_CLASS_OPERATION) {
279                         OperationDepsNode *op_node = (OperationDepsNode *)node;
280                         if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) {
281                                 color = color_modified;
282                         }
283                         else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
284                                 color = color_update;
285                         }
286                 }
287         }
288         deg_debug_fprintf(ctx, "\"%s\"", color);
289 }
290
291 static void deg_debug_graphviz_node_penwidth(const DebugContext &ctx,
292                                              const DepsNode *node)
293 {
294         float penwidth_default = 1.0f;
295         float penwidth_modified = 4.0f;
296         float penwidth_update = 4.0f;
297         float penwidth = penwidth_default;
298         if (ctx.show_tags) {
299                 if (node->tclass == DEPSNODE_CLASS_OPERATION) {
300                         OperationDepsNode *op_node = (OperationDepsNode *)node;
301                         if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) {
302                                 penwidth = penwidth_modified;
303                         }
304                         else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
305                                 penwidth = penwidth_update;
306                         }
307                 }
308         }
309         deg_debug_fprintf(ctx, "\"%f\"", penwidth);
310 }
311
312 static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx,
313                                               const DepsNode *node)
314 {
315         const char *defaultcolor = "gainsboro";
316         int color_index = deg_debug_node_color_index(node);
317         const char *fillcolor = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors];
318         deg_debug_fprintf(ctx, "\"%s\"", fillcolor);
319 }
320
321 #if 0 /* implementation using stripes, a bit too noisy ... */
322 static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx,
323                                               const DepsNode *node)
324 {
325         const char *defaultcolor = "gainsboro";
326         const char *color_needs_update = "orange";
327         const int num_stripes = 10;
328         int color_index = deg_debug_node_color_index(node);
329         const char *base_color = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors];
330         if (ctx.show_tags &&
331             (node->flag & (DEPSNODE_FLAG_DIRECTLY_MODIFIED | DEPSNODE_FLAG_NEEDS_UPDATE))) {
332                 deg_debug_fprintf(ctx, "\"");
333                 for (int i = 0; i < num_stripes; ++i) {
334                         if (i > 0) {
335                                 deg_debug_fprintf(ctx, ":");
336                         }
337                         deg_debug_fprintf(ctx, "%s:%s", base_color, color_needs_update);
338                 }
339                 deg_debug_fprintf(ctx, "\"");
340         }
341         else {
342                 deg_debug_fprintf(ctx, "\"%s\"", base_color);
343         }
344 }
345 #endif
346
347 static void deg_debug_graphviz_relation_color(const DebugContext &ctx,
348                                               const DepsRelation *rel)
349 {
350         const char *color_default = "black";
351         const char *color_error = "red4";
352         const char *color = color_default;
353 #if 0 /* disabled for now, edge colors are hardly distinguishable */
354         int color = deg_debug_relation_type_color_index(rel->type);
355         if (color < 0) {
356                 deg_debug_fprintf(ctx, "%s", defaultcolor);
357         }
358         else {
359                 deg_debug_fprintf(ctx, "\"%s\"", deg_debug_colors_dark[color % deg_debug_max_colors]);
360         }
361 #else
362         if (rel->flag & DEPSREL_FLAG_CYCLIC)
363                 color = color_error;
364         
365         deg_debug_fprintf(ctx, "%s", color);
366 #endif
367 }
368
369 static void deg_debug_graphviz_node_style(const DebugContext &ctx, const DepsNode *node)
370 {
371         const char *base_style = "filled"; /* default style */
372         if (ctx.show_tags) {
373                 if (node->tclass == DEPSNODE_CLASS_OPERATION) {
374                         OperationDepsNode *op_node = (OperationDepsNode *)node;
375                         if (op_node->flag & (DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE)) {
376                                 base_style = "striped";
377                         }
378                 }
379         }
380         switch (node->tclass) {
381                 case DEPSNODE_CLASS_GENERIC:
382                         deg_debug_fprintf(ctx, "\"%s\"", base_style);
383                         break;
384                 case DEPSNODE_CLASS_COMPONENT:
385                         deg_debug_fprintf(ctx, "\"%s\"", base_style);
386                         break;
387                 case DEPSNODE_CLASS_OPERATION:
388                         deg_debug_fprintf(ctx, "\"%s,rounded\"", base_style);
389                         break;
390         }
391 }
392
393 static void deg_debug_graphviz_node_single(const DebugContext &ctx,
394                                            const DepsNode *node)
395 {
396         const char *shape = "box";
397         string name = node->identifier();
398         float priority = -1.0f;
399         if (node->type == DEPSNODE_TYPE_ID_REF) {
400                 IDDepsNode *id_node = (IDDepsNode *)node;
401                 char buf[256];
402                 BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers);
403                 name += buf;
404         }
405         if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION) {
406                 priority = ((OperationDepsNode *)node)->eval_priority;
407         }
408         deg_debug_fprintf(ctx, "// %s\n", name.c_str());
409         deg_debug_fprintf(ctx, "\"node_%p\"", node);
410         deg_debug_fprintf(ctx, "[");
411 //      deg_debug_fprintf(ctx, "label=<<B>%s</B>>", name);
412         if (priority >= 0.0f) {
413                 deg_debug_fprintf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>",
414                                  name.c_str(),
415                                  priority);
416         }
417         else {
418                 deg_debug_fprintf(ctx, "label=<%s>", name.c_str());
419         }
420         deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
421         deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size);
422         deg_debug_fprintf(ctx, ",shape=%s", shape);
423         deg_debug_fprintf(ctx, ",style="); deg_debug_graphviz_node_style(ctx, node);
424         deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_node_color(ctx, node);
425         deg_debug_fprintf(ctx, ",fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node);
426         deg_debug_fprintf(ctx, ",penwidth="); deg_debug_graphviz_node_penwidth(ctx, node);
427         deg_debug_fprintf(ctx, "];" NL);
428         deg_debug_fprintf(ctx, NL);
429 }
430
431 static void deg_debug_graphviz_node_cluster_begin(const DebugContext &ctx,
432                                                   const DepsNode *node)
433 {
434         string name = node->identifier().c_str();
435         if (node->type == DEPSNODE_TYPE_ID_REF) {
436                 IDDepsNode *id_node = (IDDepsNode *)node;
437                 char buf[256];
438                 BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers);
439                 name += buf;
440         }
441         deg_debug_fprintf(ctx, "// %s\n", name.c_str());
442         deg_debug_fprintf(ctx, "subgraph \"cluster_%p\" {" NL, node);
443 //      deg_debug_fprintf(ctx, "label=<<B>%s</B>>;" NL, name);
444         deg_debug_fprintf(ctx, "label=<%s>;" NL, name.c_str());
445         deg_debug_fprintf(ctx, "fontname=\"%s\";" NL, deg_debug_graphviz_fontname);
446         deg_debug_fprintf(ctx, "fontsize=%f;" NL, deg_debug_graphviz_node_label_size);
447         deg_debug_fprintf(ctx, "margin=\"%d\";" NL, 16);
448         deg_debug_fprintf(ctx, "style="); deg_debug_graphviz_node_style(ctx, node); deg_debug_fprintf(ctx, ";" NL);
449         deg_debug_fprintf(ctx, "color="); deg_debug_graphviz_node_color(ctx, node); deg_debug_fprintf(ctx, ";" NL);
450         deg_debug_fprintf(ctx, "fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); deg_debug_fprintf(ctx, ";" NL);
451         deg_debug_fprintf(ctx, "penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); deg_debug_fprintf(ctx, ";" NL);
452         /* dummy node, so we can add edges between clusters */
453         deg_debug_fprintf(ctx, "\"node_%p\"", node);
454         deg_debug_fprintf(ctx, "[");
455         deg_debug_fprintf(ctx, "shape=%s", "point");
456         deg_debug_fprintf(ctx, ",style=%s", "invis");
457         deg_debug_fprintf(ctx, "];" NL);
458         deg_debug_fprintf(ctx, NL);
459 }
460
461 static void deg_debug_graphviz_node_cluster_end(const DebugContext &ctx)
462 {
463         deg_debug_fprintf(ctx, "}" NL);
464         deg_debug_fprintf(ctx, NL);
465 }
466
467 static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx,
468                                            const Depsgraph *graph);
469 static void deg_debug_graphviz_graph_relations(const DebugContext &ctx,
470                                                const Depsgraph *graph);
471
472 static void deg_debug_graphviz_node(const DebugContext &ctx,
473                                     const DepsNode *node)
474 {
475         switch (node->type) {
476                 case DEPSNODE_TYPE_ID_REF:
477                 {
478                         const IDDepsNode *id_node = (const IDDepsNode *)node;
479                         if (id_node->components.empty()) {
480                                 deg_debug_graphviz_node_single(ctx, node);
481                         }
482                         else {
483                                 deg_debug_graphviz_node_cluster_begin(ctx, node);
484                                 for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin();
485                                      it != id_node->components.end();
486                                      ++it)
487                                 {
488                                         const ComponentDepsNode *comp = it->second;
489                                         deg_debug_graphviz_node(ctx, comp);
490                                 }
491                                 deg_debug_graphviz_node_cluster_end(ctx);
492                         }
493                         break;
494                 }
495                 case DEPSNODE_TYPE_SUBGRAPH:
496                 {
497                         SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node;
498                         if (sub_node->graph) {
499                                 deg_debug_graphviz_node_cluster_begin(ctx, node);
500                                 deg_debug_graphviz_graph_nodes(ctx, sub_node->graph);
501                                 deg_debug_graphviz_node_cluster_end(ctx);
502                         }
503                         else {
504                                 deg_debug_graphviz_node_single(ctx, node);
505                         }
506                         break;
507                 }
508                 case DEPSNODE_TYPE_PARAMETERS:
509                 case DEPSNODE_TYPE_ANIMATION:
510                 case DEPSNODE_TYPE_TRANSFORM:
511                 case DEPSNODE_TYPE_PROXY:
512                 case DEPSNODE_TYPE_GEOMETRY:
513                 case DEPSNODE_TYPE_SEQUENCER:
514                 case DEPSNODE_TYPE_EVAL_POSE:
515                 case DEPSNODE_TYPE_BONE:
516                 case DEPSNODE_TYPE_SHADING:
517                 {
518                         ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
519                         if (!comp_node->operations.empty()) {
520                                 deg_debug_graphviz_node_cluster_begin(ctx, node);
521                                 for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin();
522                                      it != comp_node->operations.end();
523                                      ++it)
524                                 {
525                                         const DepsNode *op_node = it->second;
526                                         deg_debug_graphviz_node(ctx, op_node);
527                                 }
528                                 deg_debug_graphviz_node_cluster_end(ctx);
529                         }
530                         else {
531                                 deg_debug_graphviz_node_single(ctx, node);
532                         }
533                         break;
534                 }
535                 default:
536                         deg_debug_graphviz_node_single(ctx, node);
537                         break;
538         }
539 }
540
541 static bool deg_debug_graphviz_is_cluster(const DepsNode *node)
542 {
543         switch (node->type) {
544                 case DEPSNODE_TYPE_ID_REF:
545                 {
546                         const IDDepsNode *id_node = (const IDDepsNode *)node;
547                         return !id_node->components.empty();
548                 }
549                 case DEPSNODE_TYPE_SUBGRAPH:
550                 {
551                         SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node;
552                         return sub_node->graph != NULL;
553                 }
554                 case DEPSNODE_TYPE_PARAMETERS:
555                 case DEPSNODE_TYPE_ANIMATION:
556                 case DEPSNODE_TYPE_TRANSFORM:
557                 case DEPSNODE_TYPE_PROXY:
558                 case DEPSNODE_TYPE_GEOMETRY:
559                 case DEPSNODE_TYPE_SEQUENCER:
560                 case DEPSNODE_TYPE_EVAL_POSE:
561                 case DEPSNODE_TYPE_BONE:
562                 {
563                         ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
564                         return !comp_node->operations.empty();
565                 }
566                 default:
567                         return false;
568         }
569 }
570
571 static bool deg_debug_graphviz_is_owner(const DepsNode *node,
572                                         const DepsNode *other)
573 {
574         switch (node->tclass) {
575                 case DEPSNODE_CLASS_COMPONENT:
576                 {
577                         ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
578                         if (comp_node->owner == other)
579                                 return true;
580                         break;
581                 }
582                 case DEPSNODE_CLASS_OPERATION:
583                 {
584                         OperationDepsNode *op_node = (OperationDepsNode *)node;
585                         if (op_node->owner == other)
586                                 return true;
587                         else if (op_node->owner->owner == other)
588                                 return true;
589                         break;
590                 }
591                 default: break;
592         }
593         return false;
594 }
595
596 static void deg_debug_graphviz_node_relations(const DebugContext &ctx,
597                                               const DepsNode *node)
598 {
599         DEPSNODE_RELATIONS_ITER_BEGIN(node->inlinks, rel)
600         {
601                 float penwidth = 2.0f;
602                 
603                 const DepsNode *tail = rel->to; /* same as node */
604                 const DepsNode *head = rel->from;
605                 deg_debug_fprintf(ctx, "// %s -> %s\n",
606                                  head->identifier().c_str(),
607                                  tail->identifier().c_str());
608                 deg_debug_fprintf(ctx, "\"node_%p\"", head);
609                 deg_debug_fprintf(ctx, " -> ");
610                 deg_debug_fprintf(ctx, "\"node_%p\"", tail);
611
612                 deg_debug_fprintf(ctx, "[");
613                 /* XXX labels on relations are not very helpful:
614                  * - they tend to appear too far away to be associated with the edge lines
615                  * - names are mostly redundant, reflecting simply their from/to nodes
616                  * - no behavior or typing of relations themselves to justify labels
617                  */
618 #if 0
619                 deg_debug_fprintf(ctx, "label=\"%s\"", rel->name);
620                 deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
621 #else
622                 /* Note: without label an id seem necessary to avoid bugs in graphviz/dot */
623                 deg_debug_fprintf(ctx, "id=\"%s\"", rel->name);
624 #endif
625                 deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_relation_color(ctx, rel);
626                 deg_debug_fprintf(ctx, ",penwidth=\"%f\"", penwidth);
627                 /* NOTE: edge from node to own cluster is not possible and gives graphviz
628                  * warning, avoid this here by just linking directly to the invisible
629                  * placeholder node
630                  */
631                 if (deg_debug_graphviz_is_cluster(tail) && !deg_debug_graphviz_is_owner(head, tail)) {
632                         deg_debug_fprintf(ctx, ",ltail=\"cluster_%p\"", tail);
633                 }
634                 if (deg_debug_graphviz_is_cluster(head) && !deg_debug_graphviz_is_owner(tail, head)) {
635                         deg_debug_fprintf(ctx, ",lhead=\"cluster_%p\"", head);
636                 }
637                 deg_debug_fprintf(ctx, "];" NL);
638                 deg_debug_fprintf(ctx, NL);
639         }
640         DEPSNODE_RELATIONS_ITER_END;
641
642 #if 0
643         if (node->tclass == DEPSNODE_CLASS_COMPONENT) {
644                 const ComponentDepsNode *comp_node = (const ComponentDepsNode *)node;
645                 for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin();
646                      it != comp_node->operations.end();
647                      ++it)
648                 {
649                         OperationDepsNode *op_node = it->second;
650                         deg_debug_graphviz_node_relations(ctx, op_node);
651                 }
652         }
653         else if (node->type == DEPSNODE_TYPE_ID_REF) {
654                 const IDDepsNode *id_node = (const IDDepsNode *)node;
655                 for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin();
656                      it != id_node->components.end();
657                      ++it)
658                 {
659                         const ComponentDepsNode *comp = it->second;
660                         deg_debug_graphviz_node_relations(ctx, comp);
661                 }
662         }
663         else if (node->type == DEPSNODE_TYPE_SUBGRAPH) {
664                 SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node;
665                 if (sub_node->graph) {
666                         deg_debug_graphviz_graph_relations(ctx, sub_node->graph);
667                 }
668         }
669 #endif
670 }
671
672 static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx,
673                                            const Depsgraph *graph)
674 {
675         if (graph->root_node) {
676                 deg_debug_graphviz_node(ctx, graph->root_node);
677         }
678         for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
679              it != graph->id_hash.end();
680              ++it)
681         {
682                 DepsNode *node = it->second;
683                 deg_debug_graphviz_node(ctx, node);
684         }
685         TimeSourceDepsNode *time_source = graph->find_time_source(NULL);
686         if (time_source != NULL) {
687                 deg_debug_graphviz_node(ctx, time_source);
688         }
689 }
690
691 static void deg_debug_graphviz_graph_relations(const DebugContext &ctx,
692                                                const Depsgraph *graph)
693 {
694 #if 0
695         if (graph->root_node) {
696                 deg_debug_graphviz_node_relations(ctx, graph->root_node);
697         }
698         for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
699              it != graph->id_hash.end();
700              ++it)
701         {
702                 DepsNode *id_node = it->second;
703                 deg_debug_graphviz_node_relations(ctx, id_node);
704         }
705 #else
706         /* XXX not in use yet */
707 //      for (Depsgraph::OperationNodes::const_iterator it = graph->all_opnodes.begin();
708 //           it != graph->all_opnodes.end();
709 //           ++it)
710 //      {
711 //              OperationDepsNode *op_node = *it;
712 //              deg_debug_graphviz_node_relations(ctx, op_node);
713 //      }
714         for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
715              it != graph->id_hash.end();
716              ++it)
717         {
718                 IDDepsNode *id_node = it->second;
719                 for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin();
720                      it != id_node->components.end();
721                      ++it)
722                 {
723                         ComponentDepsNode *comp_node = it->second;
724                         for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin();
725                              it != comp_node->operations.end();
726                              ++it)
727                         {
728                                 OperationDepsNode *op_node = it->second;
729                                 deg_debug_graphviz_node_relations(ctx, op_node);
730                         }
731                 }
732         }
733
734         TimeSourceDepsNode *time_source = graph->find_time_source(NULL);
735         if (time_source != NULL) {
736                 deg_debug_graphviz_node_relations(ctx, time_source);
737         }
738 #endif
739 }
740
741 void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_eval)
742 {
743 #if 0 /* generate shaded color set */
744         static char colors[][3] = {{0xa6, 0xce, 0xe3},{0x1f, 0x78, 0xb4},{0xb2, 0xdf, 0x8a},{0x33, 0xa0, 0x2c},
745                                    {0xfb, 0x9a, 0x99},{0xe3, 0x1a, 0x1c},{0xfd, 0xbf, 0x6f},{0xff, 0x7f, 0x00},
746                                    {0xca, 0xb2, 0xd6},{0x6a, 0x3d, 0x9a},{0xff, 0xff, 0x99},{0xb1, 0x59, 0x28}};
747         int i;
748         const float factor = 0.666f;
749         for (i=0; i < 12; ++i)
750                 printf("\"#%x%x%x\"\n", (char)(colors[i][0] * factor), (char)(colors[i][1] * factor), (char)(colors[i][2] * factor));
751 #endif
752
753         if (!graph) {
754                 return;
755         }
756
757         DebugContext ctx;
758         ctx.file = f;
759         ctx.show_tags = show_eval;
760         ctx.show_eval_priority = show_eval;
761
762         deg_debug_fprintf(ctx, "digraph depgraph {" NL);
763         deg_debug_fprintf(ctx, "rankdir=LR;" NL);
764         deg_debug_fprintf(ctx, "graph [");
765         deg_debug_fprintf(ctx, "compound=true");
766         deg_debug_fprintf(ctx, ",labelloc=\"t\"");
767         deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_graph_label_size);
768         deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
769         deg_debug_fprintf(ctx, ",label=\"%s\"", label);
770         deg_debug_fprintf(ctx, ",splines=ortho");
771         deg_debug_fprintf(ctx, ",overlap=scalexy"); // XXX: only when using neato
772         deg_debug_fprintf(ctx, "];" NL);
773
774         deg_debug_graphviz_graph_nodes(ctx, graph);
775         deg_debug_graphviz_graph_relations(ctx, graph);
776
777         deg_debug_graphviz_legend(ctx);
778
779         deg_debug_fprintf(ctx, "}" NL);
780 }
781
782 #undef NL
783
784 /* ************************************************ */
785
786 static string get_component_name(eDepsNode_Type type, const string &name = "")
787 {
788         DepsNodeFactory *factory = DEG_get_node_factory(type);
789         if (name.empty()) {
790                 return string(factory->tname());
791         }
792         else {
793                 return string(factory->tname()) + " | " + name;
794         }
795 }
796
797 static void times_clear(DepsgraphStatsTimes &times)
798 {
799         times.duration_last = 0.0f;
800 }
801
802 static void times_add(DepsgraphStatsTimes &times, float time)
803 {
804         times.duration_last += time;
805 }
806
807 void DepsgraphDebug::eval_begin(const EvaluationContext *UNUSED(eval_ctx))
808 {
809         /* TODO(sergey): Stats are currently globally disabled. */
810         /* verify_stats(); */
811         reset_stats();
812 }
813
814 void DepsgraphDebug::eval_end(const EvaluationContext *UNUSED(eval_ctx))
815 {
816         WM_main_add_notifier(NC_SPACE | ND_SPACE_INFO_REPORT, NULL);
817 }
818
819 void DepsgraphDebug::eval_step(const EvaluationContext *UNUSED(eval_ctx),
820                                const char *message)
821 {
822 #ifdef DEG_DEBUG_BUILD
823         if (deg_debug_eval_cb)
824                 deg_debug_eval_cb(deg_debug_eval_userdata, message);
825 #else
826         (void)message;  /* Ignored. */
827 #endif
828 }
829
830 void DepsgraphDebug::task_started(Depsgraph *graph,
831                                   const OperationDepsNode *node)
832 {
833         if (stats) {
834                 BLI_spin_lock(&graph->lock);
835
836                 ComponentDepsNode *comp = node->owner;
837                 ID *id = comp->owner->id;
838
839                 DepsgraphStatsID *id_stats = get_id_stats(id, true);
840                 times_clear(id_stats->times);
841
842                 /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */
843                 if (0) {
844                         /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */
845                         DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true);
846                         times_clear(comp_stats->times);
847                 }
848
849                 BLI_spin_unlock(&graph->lock);
850         }
851 }
852
853 void DepsgraphDebug::task_completed(Depsgraph *graph,
854                                     const OperationDepsNode *node,
855                                     double time)
856 {
857         if (stats) {
858                 BLI_spin_lock(&graph->lock);
859
860                 ComponentDepsNode *comp = node->owner;
861                 ID *id = comp->owner->id;
862
863                 DepsgraphStatsID *id_stats = get_id_stats(id, true);
864                 times_add(id_stats->times, time);
865
866                 /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */
867                 if (0) {
868                         /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */
869                         DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true);
870                         times_add(comp_stats->times, time);
871                 }
872
873                 BLI_spin_unlock(&graph->lock);
874         }
875 }
876
877 /* ********** */
878 /* Statistics */
879
880 DepsgraphStats *DepsgraphDebug::stats = NULL;
881
882 /* GHash callback */
883 static void deg_id_stats_free(void *val)
884 {
885         DepsgraphStatsID *id_stats = (DepsgraphStatsID *)val;
886
887         if (id_stats) {
888                 BLI_freelistN(&id_stats->components);
889                 MEM_freeN(id_stats);
890         }
891 }
892
893 void DepsgraphDebug::stats_init()
894 {
895         if (!stats) {
896                 stats = (DepsgraphStats *)MEM_callocN(sizeof(DepsgraphStats), "Depsgraph Stats");
897                 stats->id_stats = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "Depsgraph ID Stats Hash");
898         }
899 }
900
901 void DepsgraphDebug::stats_free()
902 {
903         if (stats) {
904                 BLI_ghash_free(stats->id_stats, NULL, deg_id_stats_free);
905                 MEM_freeN(stats);
906                 stats = NULL;
907         }
908 }
909
910 void DepsgraphDebug::verify_stats()
911 {
912         stats_init();
913 }
914
915 void DepsgraphDebug::reset_stats()
916 {
917         if (!stats) {
918                 return;
919         }
920
921         /* XXX this doesn't work, will immediately clear all info,
922          * since most depsgraph updates have none or very few updates to handle.
923          *
924          * Could consider clearing only zero-user ID blocks here
925          */
926 //      BLI_ghash_clear(stats->id_stats, NULL, deg_id_stats_free);
927 }
928
929 DepsgraphStatsID *DepsgraphDebug::get_id_stats(ID *id, bool create)
930 {
931         DepsgraphStatsID *id_stats = (DepsgraphStatsID *)BLI_ghash_lookup(stats->id_stats, id);
932
933         if (!id_stats && create) {
934                 id_stats = (DepsgraphStatsID *)MEM_callocN(sizeof(DepsgraphStatsID), "Depsgraph ID Stats");
935                 id_stats->id = id;
936
937                 BLI_ghash_insert(stats->id_stats, id, id_stats);
938         }
939
940         return id_stats;
941 }
942
943 DepsgraphStatsComponent *DepsgraphDebug::get_component_stats(
944         DepsgraphStatsID *id_stats,
945         const string &name,
946         bool create)
947 {
948         DepsgraphStatsComponent *comp_stats;
949         for (comp_stats = (DepsgraphStatsComponent *)id_stats->components.first;
950              comp_stats != NULL;
951              comp_stats = comp_stats->next)
952         {
953                 if (STREQ(comp_stats->name, name.c_str()))
954                         break;
955         }
956         if (!comp_stats && create) {
957                 comp_stats = (DepsgraphStatsComponent *)MEM_callocN(sizeof(DepsgraphStatsComponent), "Depsgraph Component Stats");
958                 BLI_strncpy(comp_stats->name, name.c_str(), sizeof(comp_stats->name));
959                 BLI_addtail(&id_stats->components, comp_stats);
960         }
961         return comp_stats;
962 }
963
964 /* ------------------------------------------------ */
965
966 DepsgraphStats *DEG_stats(void)
967 {
968         return DepsgraphDebug::stats;
969 }
970
971 void DEG_stats_verify()
972 {
973         DepsgraphDebug::verify_stats();
974 }
975
976 DepsgraphStatsID *DEG_stats_id(ID *id)
977 {
978         if (!DepsgraphDebug::stats) {
979                 return NULL;
980         }
981         return DepsgraphDebug::get_id_stats(id, false);
982 }
983
984 bool DEG_debug_compare(const struct Depsgraph *graph1,
985                        const struct Depsgraph *graph2)
986 {
987         BLI_assert(graph1 != NULL);
988         BLI_assert(graph2 != NULL);
989         if (graph1->operations.size() != graph2->operations.size()) {
990                 return false;
991         }
992         /* TODO(sergey): Currently we only do real stupid check,
993          * which is fast but which isn't 100% reliable.
994          *
995          * Would be cool to make it more robust, but it's good enough
996          * for now. Also, proper graph check is actually NP-complex
997          * problem..
998          */
999         return true;
1000 }
1001
1002 bool DEG_debug_scene_relations_validate(Main *bmain,
1003                                         Scene *scene)
1004 {
1005         Depsgraph *depsgraph = DEG_graph_new();
1006         bool valid = true;
1007         DEG_graph_build_from_scene(depsgraph, bmain, scene);
1008         if (!DEG_debug_compare(depsgraph, scene->depsgraph)) {
1009                 fprintf(stderr, "ERROR! Depsgraph wasn't tagged for update when it should have!\n");
1010                 BLI_assert(!"This should not happen!");
1011                 valid = false;
1012         }
1013         DEG_graph_free(depsgraph);
1014         return valid;
1015 }
1016
1017 bool DEG_debug_consistency_check(Depsgraph *graph)
1018 {
1019         /* Validate links exists in both directions. */
1020         for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
1021              it_op != graph->operations.end();
1022              ++it_op)
1023         {
1024                 OperationDepsNode *node = *it_op;
1025                 for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
1026                      it_rel != node->outlinks.end();
1027                      ++it_rel)
1028                 {
1029                         DepsRelation *rel = *it_rel;
1030
1031                         int counter1 = 0;
1032                         for (OperationDepsNode::Relations::const_iterator tmp_rel = node->outlinks.begin();
1033                              tmp_rel != node->outlinks.end();
1034                              ++tmp_rel)
1035                         {
1036                                 if (*tmp_rel == rel) {
1037                                         ++counter1;
1038                                 }
1039                         }
1040
1041                         int counter2 = 0;
1042                         for (OperationDepsNode::Relations::const_iterator tmp_rel = rel->to->inlinks.begin();
1043                              tmp_rel != rel->to->inlinks.end();
1044                              ++tmp_rel)
1045                         {
1046                                 if (*tmp_rel == rel) {
1047                                         ++counter2;
1048                                 }
1049                         }
1050
1051                         if (counter1 != counter2) {
1052                                 printf("Relation exists in outgoing direction but not in incoming (%d vs. %d).\n",
1053                                        counter1, counter2);
1054                                 return false;
1055                         }
1056                 }
1057         }
1058
1059         for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
1060              it_op != graph->operations.end();
1061              ++it_op)
1062         {
1063                 OperationDepsNode *node = *it_op;
1064                 for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
1065                      it_rel != node->inlinks.end();
1066                      ++it_rel)
1067                 {
1068                         DepsRelation *rel = *it_rel;
1069
1070                         int counter1 = 0;
1071                         for (OperationDepsNode::Relations::const_iterator tmp_rel = node->inlinks.begin();
1072                              tmp_rel != node->inlinks.end();
1073                              ++tmp_rel)
1074                         {
1075                                 if (*tmp_rel == rel) {
1076                                         ++counter1;
1077                                 }
1078                         }
1079
1080                         int counter2 = 0;
1081                         for (OperationDepsNode::Relations::const_iterator tmp_rel = rel->from->outlinks.begin();
1082                              tmp_rel != rel->from->outlinks.end();
1083                              ++tmp_rel)
1084                         {
1085                                 if (*tmp_rel == rel) {
1086                                         ++counter2;
1087                                 }
1088                         }
1089
1090                         if (counter1 != counter2) {
1091                                 printf("Relation exists in incoming direction but not in outcoming (%d vs. %d).\n",
1092                                        counter1, counter2);
1093                         }
1094                 }
1095         }
1096
1097         /* Validate node valency calculated in both directions. */
1098         for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
1099              it_op != graph->operations.end();
1100              ++it_op)
1101         {
1102                 OperationDepsNode *node = *it_op;
1103                 node->num_links_pending = 0;
1104                 node->done = 0;
1105         }
1106
1107         for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
1108              it_op != graph->operations.end();
1109              ++it_op)
1110         {
1111                 OperationDepsNode *node = *it_op;
1112                 if (node->done) {
1113                         printf("Node %s is twice in the operations!\n",
1114                                node->identifier().c_str());
1115                         return false;
1116                 }
1117                 for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
1118                      it_rel != node->outlinks.end();
1119                      ++it_rel)
1120                 {
1121                         DepsRelation *rel = *it_rel;
1122                         if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
1123                                 OperationDepsNode *to = (OperationDepsNode *)rel->to;
1124                                 BLI_assert(to->num_links_pending < to->inlinks.size());
1125                                 ++to->num_links_pending;
1126                         }
1127                 }
1128                 node->done = 1;
1129         }
1130
1131         for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
1132              it_op != graph->operations.end();
1133              ++it_op)
1134         {
1135                 OperationDepsNode *node = *it_op;
1136                 int num_links_pending = 0;
1137                 for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
1138                      it_rel != node->inlinks.end();
1139                      ++it_rel)
1140                 {
1141                         DepsRelation *rel = *it_rel;
1142                         if (rel->from->type == DEPSNODE_TYPE_OPERATION) {
1143                                 ++num_links_pending;
1144                         }
1145                 }
1146                 if (node->num_links_pending != num_links_pending) {
1147                         printf("Valency mismatch: %s, %u != %d\n",
1148                                node->identifier().c_str(),
1149                                node->num_links_pending, num_links_pending);
1150                         printf("Number of inlinks: %d\n", (int)node->inlinks.size());
1151                         return false;
1152                 }
1153         }
1154         return true;
1155 }
1156
1157 /* ------------------------------------------------ */
1158
1159 /**
1160  * Obtain simple statistics about the complexity of the depsgraph
1161  * \param[out] r_outer       The number of outer nodes in the graph
1162  * \param[out] r_operations  The number of operation nodes in the graph
1163  * \param[out] r_relations   The number of relations between (executable) nodes in the graph
1164  */
1165 void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer,
1166                       size_t *r_operations, size_t *r_relations)
1167 {
1168         /* number of operations */
1169         if (r_operations) {
1170                 /* All operations should be in this list, allowing us to count the total
1171                  * number of nodes.
1172                  */
1173                 *r_operations = graph->operations.size();
1174         }
1175
1176         /* Count number of outer nodes and/or relations between these. */
1177         if (r_outer || r_relations) {
1178                 size_t tot_outer = 0;
1179                 size_t tot_rels = 0;
1180
1181                 for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
1182                      it != graph->id_hash.end();
1183                      ++it)
1184                 {
1185                         IDDepsNode *id_node = it->second;
1186                         tot_outer++;
1187                         for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin();
1188                              it != id_node->components.end();
1189                              ++it)
1190                         {
1191                                 ComponentDepsNode *comp_node = it->second;
1192                                 tot_outer++;
1193                                 for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin();
1194                                      it != comp_node->operations.end();
1195                                      ++it)
1196                                 {
1197                                         OperationDepsNode *op_node = it->second;
1198                                         tot_rels += op_node->inlinks.size();
1199                                 }
1200                         }
1201                 }
1202
1203                 TimeSourceDepsNode *time_source = graph->find_time_source(NULL);
1204                 if (time_source != NULL) {
1205                         tot_rels += time_source->inlinks.size();
1206                 }
1207
1208                 if (r_relations) *r_relations = tot_rels;
1209                 if (r_outer)     *r_outer     = tot_outer;
1210         }
1211 }
1212