Depsgraph: Comb code to a better state all over
[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 "intern/node/deg_node.h"
40 #include "intern/node/deg_node_component.h"
41 #include "intern/node/deg_node_operation.h"
42
43 #include "intern/depsgraph.h"
44
45 namespace DEG {
46
47 namespace {
48
49 enum eCyclicCheckVisitedState {
50         /* Not is not visited at all during traversal. */
51         NODE_NOT_VISITED = 0,
52         /* Node has been visited during traversal and not in current stack. */
53         NODE_VISITED = 1,
54         /* Node has been visited during traversal and is in current stack. */
55         NODE_IN_STACK = 2,
56 };
57
58 struct StackEntry {
59         OperationNode *node;
60         StackEntry *from;
61         Relation *via_relation;
62 };
63
64 struct CyclesSolverState {
65         CyclesSolverState(Depsgraph *graph)
66                 : graph(graph),
67                   traversal_stack(BLI_stack_new(sizeof(StackEntry),
68                                                 "DEG detect cycles stack")),
69                   num_cycles(0)
70         {
71                 /* pass */
72         }
73         ~CyclesSolverState() {
74                 BLI_stack_free(traversal_stack);
75                 if (num_cycles != 0) {
76                         printf("Detected %d dependency cycles\n", num_cycles);
77                 }
78         }
79         Depsgraph *graph;
80         BLI_Stack *traversal_stack;
81         int num_cycles;
82 };
83
84 BLI_INLINE void set_node_visited_state(Node *node,
85                                        eCyclicCheckVisitedState state)
86 {
87         node->custom_flags = (node->custom_flags & ~0x3) | (int)state;
88 }
89
90 BLI_INLINE eCyclicCheckVisitedState get_node_visited_state(Node *node)
91 {
92         return (eCyclicCheckVisitedState)(node->custom_flags & 0x3);
93 }
94
95 BLI_INLINE void set_node_num_visited_children(Node *node, int num_children)
96 {
97         node->custom_flags = (node->custom_flags & 0x3) | (num_children << 2);
98 }
99
100 BLI_INLINE int get_node_num_visited_children(Node *node)
101 {
102         return node->custom_flags >> 2;
103 }
104
105 void schedule_node_to_stack(CyclesSolverState *state, OperationNode *node)
106 {
107         StackEntry entry;
108         entry.node = node;
109         entry.from = NULL;
110         entry.via_relation = NULL;
111         BLI_stack_push(state->traversal_stack, &entry);
112         set_node_visited_state(node, NODE_IN_STACK);
113 }
114
115 /* Schedule leaf nodes (node without input links) for traversal. */
116 void schedule_leaf_nodes(CyclesSolverState *state)
117 {
118         for (OperationNode *node : state->graph->operations) {
119                 bool has_inlinks = false;
120                 for (Relation *rel : node->inlinks) {
121                         if (rel->from->type == NodeType::OPERATION) {
122                                 has_inlinks = true;
123                         }
124                 }
125                 node->custom_flags = 0;
126                 if (has_inlinks == false) {
127                         schedule_node_to_stack(state, node);
128                 }
129                 else {
130                         set_node_visited_state(node, NODE_NOT_VISITED);
131                 }
132         }
133 }
134
135 /* Schedule node which was not checked yet for being belong to
136  * any of dependency cycle.
137  */
138 bool schedule_non_checked_node(CyclesSolverState *state)
139 {
140         for (OperationNode *node : state->graph->operations) {
141                 if (get_node_visited_state(node) == NODE_NOT_VISITED) {
142                         schedule_node_to_stack(state, node);
143                         return true;
144                 }
145         }
146         return false;
147 }
148
149 bool check_relation_can_murder(Relation *relation)
150 {
151         if (relation->flag & RELATION_FLAG_GODMODE) {
152                 return false;
153         }
154         return true;
155 }
156
157 Relation *select_relation_to_murder(Relation *relation,
158                                     StackEntry *cycle_start_entry)
159 {
160         /* More or less russian roulette solver, which will make sure only
161          * specially marked relations are kept alive.
162          *
163          * TODO(sergey): There might be better strategies here. */
164         if (check_relation_can_murder(relation)) {
165                 return relation;
166         }
167         StackEntry *current = cycle_start_entry;
168         OperationNode *to_node = (OperationNode *)relation->to;
169         while (current->node != to_node) {
170                 if (check_relation_can_murder(current->via_relation)) {
171                         return current->via_relation;
172                 }
173                 current = current->from;
174         }
175         return relation;
176 }
177
178 /* Solve cycles with all nodes which are scheduled for traversal. */
179 void solve_cycles(CyclesSolverState *state)
180 {
181         BLI_Stack *traversal_stack = state->traversal_stack;
182         while (!BLI_stack_is_empty(traversal_stack)) {
183                 StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
184                 OperationNode *node = entry->node;
185                 bool all_child_traversed = true;
186                 const int num_visited = get_node_num_visited_children(node);
187                 for (int i = num_visited; i < node->outlinks.size(); ++i) {
188                         Relation *rel = node->outlinks[i];
189                         if (rel->to->type == NodeType::OPERATION) {
190                                 OperationNode *to = (OperationNode *)rel->to;
191                                 eCyclicCheckVisitedState to_state = get_node_visited_state(to);
192                                 if (to_state == NODE_IN_STACK) {
193                                         printf("Dependency cycle detected:\n");
194                                         printf("  '%s' depends on '%s' through '%s'\n",
195                                                to->full_identifier().c_str(),
196                                                node->full_identifier().c_str(),
197                                                rel->name);
198                                         StackEntry *current = entry;
199                                         while (current->node != to) {
200                                                 BLI_assert(current != NULL);
201                                                 printf("  '%s' depends on '%s' through '%s'\n",
202                                                        current->node->full_identifier().c_str(),
203                                                        current->from->node->full_identifier().c_str(),
204                                                        current->via_relation->name);
205                                                 current = current->from;
206                                         }
207                                         Relation *sacrificial_relation =
208                                                 select_relation_to_murder(rel, entry);
209                                         sacrificial_relation->flag |= RELATION_FLAG_CYCLIC;
210                                         ++state->num_cycles;
211                                 }
212                                 else if (to_state == NODE_NOT_VISITED) {
213                                         StackEntry new_entry;
214                                         new_entry.node = to;
215                                         new_entry.from = entry;
216                                         new_entry.via_relation = rel;
217                                         BLI_stack_push(traversal_stack, &new_entry);
218                                         set_node_visited_state(node, NODE_IN_STACK);
219                                         all_child_traversed = false;
220                                         set_node_num_visited_children(node, i);
221                                         break;
222                                 }
223                         }
224                 }
225                 if (all_child_traversed) {
226                         set_node_visited_state(node, NODE_VISITED);
227                         BLI_stack_discard(traversal_stack);
228                 }
229         }
230 }
231
232 }  // namespace
233
234 void deg_graph_detect_cycles(Depsgraph *graph)
235 {
236         CyclesSolverState state(graph);
237         /* First we solve cycles which are reachable from leaf nodes. */
238         schedule_leaf_nodes(&state);
239         solve_cycles(&state);
240         /* We are not done yet. It is possible to have closed loop cycle,
241          * for example A -> B -> C -> A. These nodes were not scheduled
242          * yet (since they all have inlinks), and were not traversed since
243          * nobody else points to them. */
244         while (schedule_non_checked_node(&state)) {
245                 solve_cycles(&state);
246         }
247 }
248
249 }  // namespace DEG