34enum eCyclicCheckVisitedState {
46 Relation *via_relation;
49struct CyclesSolverState {
50 CyclesSolverState(Depsgraph *graph) : graph(graph) {}
53 if (num_cycles != 0) {
54 CLOG_WARN(&
LOG,
"Detected %d dependency cycles", num_cycles);
58 Stack<StackEntry> traversal_stack;
62inline void set_node_visited_state(
Node *
node, eCyclicCheckVisitedState
state)
64 node->custom_flags = (
node->custom_flags & ~0x3) |
int(
state);
67inline eCyclicCheckVisitedState get_node_visited_state(
Node *
node)
69 return eCyclicCheckVisitedState(
node->custom_flags & 0x3);
72inline void set_node_num_visited_children(
Node *
node,
int num_children)
74 node->custom_flags = (
node->custom_flags & 0x3) | (num_children << 2);
77inline int get_node_num_visited_children(
Node *
node)
79 return node->custom_flags >> 2;
87 entry.via_relation =
nullptr;
88 state->traversal_stack.push(entry);
89 set_node_visited_state(
node, NODE_IN_STACK);
93void schedule_leaf_nodes(CyclesSolverState *
state)
96 bool has_inlinks =
false;
102 node->custom_flags = 0;
103 if (has_inlinks ==
false) {
107 set_node_visited_state(
node, NODE_NOT_VISITED);
115bool schedule_non_checked_node(CyclesSolverState *
state)
118 if (get_node_visited_state(
node) == NODE_NOT_VISITED) {
126bool check_relation_can_murder(
Relation *relation)
134Relation *select_relation_to_murder(
Relation *relation, StackEntry *cycle_start_entry)
140 if (check_relation_can_murder(relation)) {
143 StackEntry *current = cycle_start_entry;
145 while (current->node != to_node) {
146 if (check_relation_can_murder(current->via_relation)) {
147 return current->via_relation;
149 current = current->from;
155void solve_cycles(CyclesSolverState *
state)
157 Stack<StackEntry> &traversal_stack =
state->traversal_stack;
158 while (!traversal_stack.is_empty()) {
159 StackEntry *entry = &traversal_stack.peek();
161 bool all_child_traversed =
true;
162 const int num_visited = get_node_num_visited_children(
node);
163 for (
int i = num_visited; i <
node->outlinks.size(); i++) {
167 eCyclicCheckVisitedState to_state = get_node_visited_state(to);
168 if (to_state == NODE_IN_STACK) {
169 std::string cycle_str =
" " + to->full_identifier() +
" depends on\n " +
170 node->full_identifier() +
" via '" + rel->name +
"'\n";
171 StackEntry *current = entry;
172 while (current->node != to) {
174 cycle_str +=
" " + current->from->node->full_identifier() +
" via '" +
175 current->via_relation->name +
"'\n";
176 current = current->from;
178 CLOG_WARN(&
LOG,
"Dependency cycle detected:\n%s", cycle_str.c_str());
179 Relation *sacrificial_relation = select_relation_to_murder(rel, entry);
183 else if (to_state == NODE_NOT_VISITED) {
184 StackEntry new_entry;
186 new_entry.from = entry;
187 new_entry.via_relation = rel;
188 traversal_stack.push(new_entry);
189 set_node_visited_state(
node, NODE_IN_STACK);
190 all_child_traversed =
false;
191 set_node_num_visited_children(
node, i);
196 if (all_child_traversed) {
197 set_node_visited_state(
node, NODE_VISITED);
198 traversal_stack.pop();
207 CyclesSolverState
state(graph);
209 schedule_leaf_nodes(&
state);
210 solve_cycles(&
state);
215 while (schedule_non_checked_node(&
state)) {
216 solve_cycles(&
state);
#define CLOG_WARN(clg_ref,...)
void deg_graph_detect_cycles(Depsgraph *graph)