a8768c899adeed6e55b8b027e7fb295c83321b44
[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->custom_flags = (node->custom_flags & ~0x3) | (int)state;
90 }
91
92 BLI_INLINE eCyclicCheckVisitedState get_node_visited_state(DepsNode *node)
93 {
94         return (eCyclicCheckVisitedState)(node->custom_flags & 0x3);
95 }
96
97 BLI_INLINE void set_node_num_visited_children(DepsNode *node, int num_children)
98 {
99         node->custom_flags = (node->custom_flags & 0x3) | (num_children << 2);
100 }
101
102 BLI_INLINE int get_node_num_visited_children(DepsNode *node)
103 {
104         return node->custom_flags >> 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->custom_flags = 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 bool check_relation_can_murder(DepsRelation *relation)
152 {
153         if (relation->flag & DEPSREL_FLAG_GODMODE) {
154                 return false;
155         }
156         return true;
157 }
158
159 DepsRelation *select_relation_to_murder(DepsRelation *relation,
160                                         StackEntry *cycle_start_entry)
161 {
162         /* More or less russian roulette solver, which will make sure only
163          * specially marked relations are kept alive.
164          *
165          * TODO(sergey): There might be better strategies here. */
166         if (check_relation_can_murder(relation)) {
167                 return relation;
168         }
169         StackEntry *current = cycle_start_entry;
170         OperationDepsNode *to_node = (OperationDepsNode *)relation->to;
171         while (current->node != to_node) {
172                 if (check_relation_can_murder(current->via_relation)) {
173                         return current->via_relation;
174                 }
175                 current = current->from;
176         }
177         return relation;
178 }
179
180 /* Solve cycles with all nodes which are scheduled for traversal. */
181 void solve_cycles(CyclesSolverState *state)
182 {
183         BLI_Stack *traversal_stack = state->traversal_stack;
184         while (!BLI_stack_is_empty(traversal_stack)) {
185                 StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
186                 OperationDepsNode *node = entry->node;
187                 bool all_child_traversed = true;
188                 const int num_visited = get_node_num_visited_children(node);
189                 for (int i = num_visited; i < node->outlinks.size(); ++i) {
190                         DepsRelation *rel = node->outlinks[i];
191                         if (rel->to->type == DEG_NODE_TYPE_OPERATION) {
192                                 OperationDepsNode *to = (OperationDepsNode *)rel->to;
193                                 eCyclicCheckVisitedState to_state = get_node_visited_state(to);
194                                 if (to_state == NODE_IN_STACK) {
195                                         printf("Dependency cycle detected:\n");
196                                         printf("  '%s' depends on '%s' through '%s'\n",
197                                                to->full_identifier().c_str(),
198                                                node->full_identifier().c_str(),
199                                                rel->name);
200                                         StackEntry *current = entry;
201                                         while (current->node != to) {
202                                                 BLI_assert(current != NULL);
203                                                 printf("  '%s' depends on '%s' through '%s'\n",
204                                                        current->node->full_identifier().c_str(),
205                                                        current->from->node->full_identifier().c_str(),
206                                                        current->via_relation->name);
207                                                 current = current->from;
208                                         }
209                                         DepsRelation *sacrificial_relation =
210                                                 select_relation_to_murder(rel, entry);
211                                         sacrificial_relation->flag |= DEPSREL_FLAG_CYCLIC;
212                                         ++state->num_cycles;
213                                 }
214                                 else if (to_state == NODE_NOT_VISITED) {
215                                         StackEntry new_entry;
216                                         new_entry.node = to;
217                                         new_entry.from = entry;
218                                         new_entry.via_relation = rel;
219                                         BLI_stack_push(traversal_stack, &new_entry);
220                                         set_node_visited_state(node, NODE_IN_STACK);
221                                         all_child_traversed = false;
222                                         set_node_num_visited_children(node, i);
223                                         break;
224                                 }
225                         }
226                 }
227                 if (all_child_traversed) {
228                         set_node_visited_state(node, NODE_VISITED);
229                         BLI_stack_discard(traversal_stack);
230                 }
231         }
232 }
233
234 }  // namespace
235
236 void deg_graph_detect_cycles(Depsgraph *graph)
237 {
238         CyclesSolverState state(graph);
239         /* First we solve cycles which are reachable from leaf nodes. */
240         schedule_leaf_nodes(&state);
241         solve_cycles(&state);
242         /* We are not done yet. It is possible to have closed loop cycle,
243          * for example A -> B -> C -> A. These nodes were not scheduled
244          * yet (since they all have inlinks), and were not traversed since
245          * nobody else points to them.
246          */
247         while (schedule_non_checked_node(&state)) {
248                 solve_cycles(&state);
249         }
250 }
251
252 }  // namespace DEG