Cleanup: style
[blender.git] / source / blender / depsgraph / intern / builder / deg_builder_cycle.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) 2015 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Sergey Sharybin
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/depsgraph/intern/builder/deg_builder_cycle.cc
27  *  \ingroup depsgraph
28  */
29
30 #include "intern/builder/deg_builder_cycle.h"
31
32 // TOO(sergey): Use some wrappers over those?
33 #include <cstdio>
34 #include <cstdlib>
35
36 #include "BLI_utildefines.h"
37 #include "BLI_stack.h"
38
39 #include "util/deg_util_foreach.h"
40
41 #include "intern/nodes/deg_node.h"
42 #include "intern/nodes/deg_node_component.h"
43 #include "intern/nodes/deg_node_operation.h"
44
45 #include "intern/depsgraph.h"
46
47 namespace DEG {
48
49 namespace {
50
51 typedef enum eCyclicCheckVisitedState {
52         /* Not is not visited at all during traversal. */
53         NODE_NOT_VISITED = 0,
54         /* Node has been visited during traversal and not in current stack. */
55         NODE_VISITED = 1,
56         /* Node has been visited during traversal and is in current stack. */
57         NODE_IN_STACK = 2,
58 } eCyclicCheckVisitedState;
59
60 struct StackEntry {
61         OperationDepsNode *node;
62         StackEntry *from;
63         DepsRelation *via_relation;
64 };
65
66 struct CyclesSolverState {
67         CyclesSolverState(Depsgraph *graph)
68                 : graph(graph),
69                   traversal_stack(BLI_stack_new(sizeof(StackEntry),
70                                                 "DEG detect cycles stack")),
71                   num_cycles(0)
72         {
73                 /* pass */
74         }
75         ~CyclesSolverState() {
76                 BLI_stack_free(traversal_stack);
77                 if (num_cycles != 0) {
78                         printf("Detected %d dependency cycles\n", num_cycles);
79                 }
80         }
81         Depsgraph *graph;
82         BLI_Stack *traversal_stack;
83         int num_cycles;
84 };
85
86 BLI_INLINE void set_node_visited_state(DepsNode *node,
87                                        eCyclicCheckVisitedState state)
88 {
89         node->done = (node->done & ~0x3) | (int)state;
90 }
91
92 BLI_INLINE eCyclicCheckVisitedState get_node_visited_state(DepsNode *node)
93 {
94         return (eCyclicCheckVisitedState)(node->done & 0x3);
95 }
96
97 BLI_INLINE void set_node_num_visited_children(DepsNode *node, int num_children)
98 {
99         node->done = (node->done & 0x3) | (num_children << 2);
100 }
101
102 BLI_INLINE int get_node_num_visited_children(DepsNode *node)
103 {
104         return node->done >> 2;
105 }
106
107 void schedule_node_to_stack(CyclesSolverState *state, OperationDepsNode *node)
108 {
109         StackEntry entry;
110         entry.node = node;
111         entry.from = NULL;
112         entry.via_relation = NULL;
113         BLI_stack_push(state->traversal_stack, &entry);
114         set_node_visited_state(node, NODE_IN_STACK);
115 }
116
117 /* Schedule leaf nodes (node without input links) for traversal. */
118 void schedule_leaf_nodes(CyclesSolverState *state)
119 {
120         foreach (OperationDepsNode *node, state->graph->operations) {
121                 bool has_inlinks = false;
122                 foreach (DepsRelation *rel, node->inlinks) {
123                         if (rel->from->type == DEG_NODE_TYPE_OPERATION) {
124                                 has_inlinks = true;
125                         }
126                 }
127                 node->done = 0;
128                 if (has_inlinks == false) {
129                         schedule_node_to_stack(state, node);
130                 }
131                 else {
132                         set_node_visited_state(node, NODE_NOT_VISITED);
133                 }
134         }
135 }
136
137 /* Schedule node which was not checked yet for being belong to
138  * any of dependency cycle.
139  */
140 bool schedule_non_checked_node(CyclesSolverState *state)
141 {
142         foreach (OperationDepsNode *node, state->graph->operations) {
143                 if (get_node_visited_state(node) == NODE_NOT_VISITED) {
144                         schedule_node_to_stack(state, node);
145                         return true;
146                 }
147         }
148         return false;
149 }
150
151 /* Solve cycles with all nodes which are scheduled for traversal. */
152 void solve_cycles(CyclesSolverState *state)
153 {
154         BLI_Stack *traversal_stack = state->traversal_stack;
155         while (!BLI_stack_is_empty(traversal_stack)) {
156                 StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
157                 OperationDepsNode *node = entry->node;
158                 bool all_child_traversed = true;
159                 const int num_visited = get_node_num_visited_children(node);
160                 for (int i = num_visited; i < node->outlinks.size(); ++i) {
161                         DepsRelation *rel = node->outlinks[i];
162                         if (rel->to->type == DEG_NODE_TYPE_OPERATION) {
163                                 OperationDepsNode *to = (OperationDepsNode *)rel->to;
164                                 eCyclicCheckVisitedState to_state = get_node_visited_state(to);
165                                 if (to_state == NODE_IN_STACK) {
166                                         printf("Dependency cycle detected:\n");
167                                         printf("  '%s' depends on '%s' through '%s'\n",
168                                                to->full_identifier().c_str(),
169                                                node->full_identifier().c_str(),
170                                                rel->name);
171
172                                         StackEntry *current = entry;
173                                         while (current->node != to) {
174                                                 BLI_assert(current != NULL);
175                                                 printf("  '%s' depends on '%s' through '%s'\n",
176                                                        current->node->full_identifier().c_str(),
177                                                        current->from->node->full_identifier().c_str(),
178                                                        current->via_relation->name);
179                                                 current = current->from;
180                                         }
181                                         /* TODO(sergey): So called russian roulette cycle solver. */
182                                         rel->flag |= DEPSREL_FLAG_CYCLIC;
183                                         ++state->num_cycles;
184                                 }
185                                 else if (to_state == NODE_NOT_VISITED) {
186                                         StackEntry new_entry;
187                                         new_entry.node = to;
188                                         new_entry.from = entry;
189                                         new_entry.via_relation = rel;
190                                         BLI_stack_push(traversal_stack, &new_entry);
191                                         set_node_visited_state(node, NODE_IN_STACK);
192                                         all_child_traversed = false;
193                                         set_node_num_visited_children(node, i);
194                                         break;
195                                 }
196                         }
197                 }
198                 if (all_child_traversed) {
199                         set_node_visited_state(node, NODE_VISITED);
200                         BLI_stack_discard(traversal_stack);
201                 }
202         }
203 }
204
205 }  // namespace
206
207 void deg_graph_detect_cycles(Depsgraph *graph)
208 {
209         CyclesSolverState state(graph);
210         /* First we solve cycles which are reachable from leaf nodes. */
211         schedule_leaf_nodes(&state);
212         solve_cycles(&state);
213         /* We are not done yet. It is possible to have closed loop cycle,
214          * for example A -> B -> C -> A. These nodes were not scheduled
215          * yet (since they all have inlinks), and were not traversed since
216          * nobody else points to them.
217          */
218         while (schedule_non_checked_node(&state)) {
219                 solve_cycles(&state);
220         }
221 }
222
223 }  // namespace DEG