28 enum eCyclicCheckVisitedState {
43 struct CyclesSolverState {
53 printf(
"Detected %d dependency cycles\n",
num_cycles);
61 inline void set_node_visited_state(
Node *
node, eCyclicCheckVisitedState
state)
66 inline eCyclicCheckVisitedState get_node_visited_state(
Node *
node)
71 inline void set_node_num_visited_children(
Node *
node,
int num_children)
76 inline int get_node_num_visited_children(
Node *
node)
81 void schedule_node_to_stack(CyclesSolverState *
state, OperationNode *
node)
86 entry.via_relation =
nullptr;
88 set_node_visited_state(
node, NODE_IN_STACK);
92 void schedule_leaf_nodes(CyclesSolverState *
state)
94 for (OperationNode *
node :
state->graph->operations) {
95 bool has_inlinks =
false;
102 if (has_inlinks ==
false) {
106 set_node_visited_state(
node, NODE_NOT_VISITED);
114 bool schedule_non_checked_node(CyclesSolverState *
state)
116 for (OperationNode *
node :
state->graph->operations) {
117 if (get_node_visited_state(
node) == NODE_NOT_VISITED) {
125 bool check_relation_can_murder(Relation *relation)
133 Relation *select_relation_to_murder(Relation *relation, StackEntry *cycle_start_entry)
139 if (check_relation_can_murder(relation)) {
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;
148 current = current->from;
154 void solve_cycles(CyclesSolverState *
state)
159 OperationNode *
node = entry->node;
160 bool all_child_traversed =
true;
161 const int num_visited = get_node_num_visited_children(
node);
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 " +
170 StackEntry *current = entry;
171 while (current->node != to) {
173 cycle_str +=
" " + current->from->node->full_identifier() +
" via '" +
174 current->via_relation->name +
"'\n";
175 current = current->from;
177 printf(
"Dependency cycle detected:\n%s", cycle_str.c_str());
178 Relation *sacrificial_relation = select_relation_to_murder(rel, entry);
182 else if (to_state == NODE_NOT_VISITED) {
183 StackEntry new_entry;
185 new_entry.from = entry;
186 new_entry.via_relation = rel;
188 set_node_visited_state(
node, NODE_IN_STACK);
189 all_child_traversed =
false;
190 set_node_num_visited_children(
node, i);
195 if (all_child_traversed) {
196 set_node_visited_state(
node, NODE_VISITED);
208 schedule_leaf_nodes(&
state);
209 solve_cycles(&
state);
214 while (schedule_non_checked_node(&
state)) {
215 solve_cycles(&
state);
void * BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
void BLI_stack_discard(BLI_Stack *stack) ATTR_NONNULL()
#define BLI_stack_new(esize, descr)
struct Depsgraph Depsgraph
BLI_Stack * traversal_stack
void deg_graph_detect_cycles(Depsgraph *graph)
string full_identifier() const