Blender  V3.3
deg_builder_cycle.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2015 Blender Foundation. All rights reserved. */
3 
9 
10 // TOO(sergey): Use some wrappers over those?
11 #include <cstdio>
12 #include <cstdlib>
13 
14 #include "BLI_stack.h"
15 #include "BLI_utildefines.h"
16 
17 #include "intern/node/deg_node.h"
20 
21 #include "intern/depsgraph.h"
23 
24 namespace blender::deg {
25 
26 namespace {
27 
28 enum eCyclicCheckVisitedState {
29  /* Not is not visited at all during traversal. */
30  NODE_NOT_VISITED = 0,
31  /* Node has been visited during traversal and not in current stack. */
32  NODE_VISITED = 1,
33  /* Node has been visited during traversal and is in current stack. */
34  NODE_IN_STACK = 2,
35 };
36 
37 struct StackEntry {
38  OperationNode *node;
39  StackEntry *from;
40  Relation *via_relation;
41 };
42 
43 struct CyclesSolverState {
44  CyclesSolverState(Depsgraph *graph)
45  : graph(graph), traversal_stack(BLI_stack_new(sizeof(StackEntry), "DEG detect cycles stack"))
46  {
47  /* pass */
48  }
49  ~CyclesSolverState()
50  {
52  if (num_cycles != 0) {
53  printf("Detected %d dependency cycles\n", num_cycles);
54  }
55  }
58  int num_cycles = 0;
59 };
60 
61 inline void set_node_visited_state(Node *node, eCyclicCheckVisitedState state)
62 {
63  node->custom_flags = (node->custom_flags & ~0x3) | (int)state;
64 }
65 
66 inline eCyclicCheckVisitedState get_node_visited_state(Node *node)
67 {
68  return (eCyclicCheckVisitedState)(node->custom_flags & 0x3);
69 }
70 
71 inline void set_node_num_visited_children(Node *node, int num_children)
72 {
73  node->custom_flags = (node->custom_flags & 0x3) | (num_children << 2);
74 }
75 
76 inline int get_node_num_visited_children(Node *node)
77 {
78  return node->custom_flags >> 2;
79 }
80 
81 void schedule_node_to_stack(CyclesSolverState *state, OperationNode *node)
82 {
83  StackEntry entry;
84  entry.node = node;
85  entry.from = nullptr;
86  entry.via_relation = nullptr;
87  BLI_stack_push(state->traversal_stack, &entry);
88  set_node_visited_state(node, NODE_IN_STACK);
89 }
90 
91 /* Schedule leaf nodes (node without input links) for traversal. */
92 void schedule_leaf_nodes(CyclesSolverState *state)
93 {
94  for (OperationNode *node : state->graph->operations) {
95  bool has_inlinks = false;
96  for (Relation *rel : node->inlinks) {
97  if (rel->from->type == NodeType::OPERATION) {
98  has_inlinks = true;
99  }
100  }
101  node->custom_flags = 0;
102  if (has_inlinks == false) {
103  schedule_node_to_stack(state, node);
104  }
105  else {
106  set_node_visited_state(node, NODE_NOT_VISITED);
107  }
108  }
109 }
110 
111 /* Schedule node which was not checked yet for being belong to
112  * any of dependency cycle.
113  */
114 bool schedule_non_checked_node(CyclesSolverState *state)
115 {
116  for (OperationNode *node : state->graph->operations) {
117  if (get_node_visited_state(node) == NODE_NOT_VISITED) {
118  schedule_node_to_stack(state, node);
119  return true;
120  }
121  }
122  return false;
123 }
124 
125 bool check_relation_can_murder(Relation *relation)
126 {
127  if (relation->flag & RELATION_FLAG_GODMODE) {
128  return false;
129  }
130  return true;
131 }
132 
133 Relation *select_relation_to_murder(Relation *relation, StackEntry *cycle_start_entry)
134 {
135  /* More or less Russian roulette solver, which will make sure only
136  * specially marked relations are kept alive.
137  *
138  * TODO(sergey): There might be better strategies here. */
139  if (check_relation_can_murder(relation)) {
140  return relation;
141  }
142  StackEntry *current = cycle_start_entry;
143  OperationNode *to_node = (OperationNode *)relation->to;
144  while (current->node != to_node) {
145  if (check_relation_can_murder(current->via_relation)) {
146  return current->via_relation;
147  }
148  current = current->from;
149  }
150  return relation;
151 }
152 
153 /* Solve cycles with all nodes which are scheduled for traversal. */
154 void solve_cycles(CyclesSolverState *state)
155 {
156  BLI_Stack *traversal_stack = state->traversal_stack;
158  StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
159  OperationNode *node = entry->node;
160  bool all_child_traversed = true;
161  const int num_visited = get_node_num_visited_children(node);
162  for (int i = num_visited; i < node->outlinks.size(); i++) {
163  Relation *rel = node->outlinks[i];
164  if (rel->to->type == NodeType::OPERATION) {
165  OperationNode *to = (OperationNode *)rel->to;
166  eCyclicCheckVisitedState to_state = get_node_visited_state(to);
167  if (to_state == NODE_IN_STACK) {
168  string cycle_str = " " + to->full_identifier() + " depends on\n " +
169  node->full_identifier() + " via '" + rel->name + "'\n";
170  StackEntry *current = entry;
171  while (current->node != to) {
172  BLI_assert(current != nullptr);
173  cycle_str += " " + current->from->node->full_identifier() + " via '" +
174  current->via_relation->name + "'\n";
175  current = current->from;
176  }
177  printf("Dependency cycle detected:\n%s", cycle_str.c_str());
178  Relation *sacrificial_relation = select_relation_to_murder(rel, entry);
179  sacrificial_relation->flag |= RELATION_FLAG_CYCLIC;
180  ++state->num_cycles;
181  }
182  else if (to_state == NODE_NOT_VISITED) {
183  StackEntry new_entry;
184  new_entry.node = to;
185  new_entry.from = entry;
186  new_entry.via_relation = rel;
187  BLI_stack_push(traversal_stack, &new_entry);
188  set_node_visited_state(node, NODE_IN_STACK);
189  all_child_traversed = false;
190  set_node_num_visited_children(node, i);
191  break;
192  }
193  }
194  }
195  if (all_child_traversed) {
196  set_node_visited_state(node, NODE_VISITED);
198  }
199  }
200 }
201 
202 } // namespace
203 
205 {
206  CyclesSolverState state(graph);
207  /* First we solve cycles which are reachable from leaf nodes. */
208  schedule_leaf_nodes(&state);
209  solve_cycles(&state);
210  /* We are not done yet. It is possible to have closed loop cycle,
211  * for example A -> B -> C -> A. These nodes were not scheduled
212  * yet (since they all have inlinks), and were not traversed since
213  * nobody else points to them. */
214  while (schedule_non_checked_node(&state)) {
215  solve_cycles(&state);
216  }
217 }
218 
219 } // namespace blender::deg
#define BLI_assert(a)
Definition: BLI_assert.h:46
void * BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:166
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition: stack.c:129
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:247
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:94
void BLI_stack_discard(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:173
#define BLI_stack_new(esize, descr)
struct Depsgraph Depsgraph
Definition: DEG_depsgraph.h:35
int64_t size() const
Definition: BLI_vector.hh:694
int num_cycles
OperationNode * node
BLI_Stack * traversal_stack
Depsgraph * graph
StackEntry * from
Relation * via_relation
const int state
void deg_graph_detect_cycles(Depsgraph *graph)
Relations inlinks
Definition: deg_node.h:173
Relations outlinks
Definition: deg_node.h:174