Changeset View
Standalone View
source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
| Show All 20 Lines | |||||
| * \ingroup depsgraph | * \ingroup depsgraph | ||||
| */ | */ | ||||
| #include "intern/builder/deg_builder_cycle.h" | #include "intern/builder/deg_builder_cycle.h" | ||||
| // TOO(sergey): Use some wrappers over those? | // TOO(sergey): Use some wrappers over those? | ||||
| #include <cstdio> | #include <cstdio> | ||||
| #include <cstdlib> | #include <cstdlib> | ||||
| #include <cstring> | |||||
| #include "BLI_utildefines.h" | #include "BLI_utildefines.h" | ||||
| #include "BLI_stack.h" | #include "BLI_stack.h" | ||||
| #include "intern/node/deg_node.h" | #include "intern/node/deg_node.h" | ||||
| #include "intern/node/deg_node_id.h" | |||||
| #include "intern/node/deg_node_component.h" | #include "intern/node/deg_node_component.h" | ||||
| #include "intern/node/deg_node_operation.h" | #include "intern/node/deg_node_operation.h" | ||||
| #include "intern/depsgraph.h" | #include "intern/depsgraph.h" | ||||
| namespace DEG { | namespace DEG { | ||||
| namespace { | namespace { | ||||
| enum eCyclicCheckVisitedState { | enum eCyclicCheckVisitedState { | ||||
| /* Not is not visited at all during traversal. */ | /* Not is not visited at all during traversal. */ | ||||
| NODE_NOT_VISITED = 0, | NODE_NOT_VISITED = 0, | ||||
| /* Node has been visited during traversal and not in current stack. */ | /* Node has been visited during traversal and not in current stack. */ | ||||
| NODE_VISITED = 1, | NODE_VISITED = 1, | ||||
| /* Node has been visited during traversal and is in current stack. */ | /* Node has been visited during traversal and is in current stack. */ | ||||
| NODE_IN_STACK = 2, | NODE_IN_STACK = 2, | ||||
| /* Node processing has been started during traversal, but its incoming edge has been removed. */ | |||||
sergey: It's `relation`, not `edge`. We should keep terminology consistent.
What is a node have… | |||||
angavrilovAuthorUnsubmitted Done Inline ActionsIt is stashed if during DFS we kill a relation that is already in the stack (rather than the 'leaf' currently being checked), and thus must abandon the subtree. Potentially it could even go to NOT_VISITED, but although I didn't try to prove it, I have a hunch that it's safe to retain the num_visited_children counter values, so the state of such nodes is in fact distinct, and thus I added a new enum value. angavrilov: It is stashed if during DFS we kill a relation that is already in the stack (rather than the… | |||||
sergeyUnsubmitted Not Done Inline ActionsSuch description should be easier to discover than looking into code review page. IO.e. by being written in the comment in the code itself. sergey: Such description should be easier to discover than looking into code review page. IO.e. by… | |||||
| NODE_STASHED = 3, | |||||
| }; | }; | ||||
| struct StackEntry { | struct StackEntry { | ||||
| OperationNode *node; | OperationNode *node; | ||||
| StackEntry *from; | StackEntry *from; | ||||
| Relation *via_relation; | Relation *via_relation; | ||||
| }; | }; | ||||
| struct CyclesSolverState { | struct CyclesSolverState { | ||||
| CyclesSolverState(Depsgraph *graph) | CyclesSolverState(Depsgraph *graph) | ||||
| : graph(graph), | : graph(graph), | ||||
| traversal_stack(BLI_stack_new(sizeof(StackEntry), "DEG detect cycles stack")), | traversal_stack(BLI_stack_new(sizeof(StackEntry), "DEG detect cycles stack")), | ||||
| stash_stack(BLI_stack_new(sizeof(OperationNode *), "DEG detect cycles stash stack")), | |||||
| num_cycles(0) | num_cycles(0) | ||||
| { | { | ||||
| /* pass */ | /* pass */ | ||||
| } | } | ||||
| ~CyclesSolverState() | ~CyclesSolverState() | ||||
| { | { | ||||
| BLI_stack_free(traversal_stack); | BLI_stack_free(traversal_stack); | ||||
| BLI_stack_free(stash_stack); | |||||
| if (num_cycles != 0) { | if (num_cycles != 0) { | ||||
| printf("Detected %d dependency cycles\n", num_cycles); | printf("Detected %d dependency cycles\n", num_cycles); | ||||
| } | } | ||||
| } | } | ||||
| Depsgraph *graph; | Depsgraph *graph; | ||||
| BLI_Stack *traversal_stack; | BLI_Stack *traversal_stack; | ||||
| BLI_Stack *stash_stack; | |||||
| int num_cycles; | int num_cycles; | ||||
| }; | }; | ||||
| BLI_INLINE void set_node_visited_state(Node *node, eCyclicCheckVisitedState state) | BLI_INLINE void set_node_visited_state(Node *node, eCyclicCheckVisitedState state) | ||||
| { | { | ||||
| node->custom_flags = (node->custom_flags & ~0x3) | (int)state; | node->custom_flags = (node->custom_flags & ~0x3) | (int)state; | ||||
| } | } | ||||
| ▲ Show 20 Lines • Show All 42 Lines • ▼ Show 20 Lines | void schedule_leaf_nodes(CyclesSolverState *state) | ||||
| } | } | ||||
| } | } | ||||
| /* Schedule node which was not checked yet for being belong to | /* Schedule node which was not checked yet for being belong to | ||||
| * any of dependency cycle. | * any of dependency cycle. | ||||
| */ | */ | ||||
| bool schedule_non_checked_node(CyclesSolverState *state) | bool schedule_non_checked_node(CyclesSolverState *state) | ||||
| { | { | ||||
| /* First, try unstashing nodes. */ | |||||
| while (!BLI_stack_is_empty(state->stash_stack)) { | |||||
| OperationNode *node; | |||||
| BLI_stack_pop(state->stash_stack, &node); | |||||
| if (get_node_visited_state(node) == NODE_STASHED) { | |||||
| schedule_node_to_stack(state, node); | |||||
| return true; | |||||
| } | |||||
| } | |||||
| for (OperationNode *node : state->graph->operations) { | for (OperationNode *node : state->graph->operations) { | ||||
| if (get_node_visited_state(node) == NODE_NOT_VISITED) { | if (get_node_visited_state(node) == NODE_NOT_VISITED) { | ||||
| schedule_node_to_stack(state, node); | schedule_node_to_stack(state, node); | ||||
| return true; | return true; | ||||
| } | } | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| bool check_relation_can_murder(Relation *relation) | bool check_relation_can_murder(Relation *relation) | ||||
| { | { | ||||
| if (relation->flag & RELATION_FLAG_GODMODE) { | if (relation->flag & RELATION_FLAG_GODMODE) { | ||||
| return false; | return false; | ||||
| } | } | ||||
| return true; | return true; | ||||
| } | } | ||||
| Relation *select_relation_to_murder(Relation *relation, StackEntry *cycle_start_entry) | bool check_relation_can_murder_physics(Relation *relation) | ||||
| { | |||||
| /* In physics collision cycles, resolve cycles by sorting objects in their name | |||||
| * order, and making relations in one direction first candidates for removal. */ | |||||
| if ((relation->flag & RELATION_FLAG_PHYSICS_BREAK_CYCLES) && | |||||
| check_relation_can_murder(relation) && relation->from->type == NodeType::OPERATION && | |||||
| relation->to->type == NodeType::OPERATION) { | |||||
| OperationNode *from = (OperationNode *)relation->from; | |||||
| OperationNode *to = (OperationNode *)relation->to; | |||||
| return strcmp(from->owner->owner->name.c_str() + 2, to->owner->owner->name.c_str() + 2) > 0; | |||||
| } | |||||
| return false; | |||||
| } | |||||
| Relation *select_relation(Relation *relation, | |||||
sergeyUnsubmitted Not Done Inline ActionsUse clear naming which will indicate what exactly you are selecting the relation. Are you selecting it to be the one which will be used to break cycle? select_relation_to_break_cycle. sergey: Use clear naming which will indicate what exactly you are selecting the relation.
Are you… | |||||
angavrilovAuthorUnsubmitted Done Inline ActionsActually, I completely disagree. With the addition of a function argument, this is a generic 'select first relation that matches predicate' function. The name exactly reflects what it does. angavrilov: Actually, I completely disagree. With the addition of a function argument, this is a generic… | |||||
sergeyUnsubmitted Not Done Inline Actions
No, it doesn't. Trying to be too abstract and generic for no reason does not help understanding what's going on. sergey: > The name exactly reflects what it does.
No, it doesn't.
Even as you've mentioned in this… | |||||
| StackEntry *cycle_start_entry, | |||||
| bool (*check)(Relation *)) | |||||
sergeyUnsubmitted Not Done Inline Actionscheck is too generic. Are you checking for the relation being valid? Relation being suitable for breaking a cycle? sergey: `check` is too generic. Are you checking for the relation being valid? Relation being suitable… | |||||
angavrilovAuthorUnsubmitted Done Inline Actionspredicate would be more appropriate I guess. angavrilov: `predicate` would be more appropriate I guess. | |||||
| { | { | ||||
| /* More or less Russian roulette solver, which will make sure only | /* More or less Russian roulette solver, which will make sure only | ||||
| * specially marked relations are kept alive. | * specially marked relations are kept alive. | ||||
| * | * | ||||
| * TODO(sergey): There might be better strategies here. */ | * TODO(sergey): There might be better strategies here. */ | ||||
| if (check_relation_can_murder(relation)) { | if (check(relation)) { | ||||
| return relation; | return relation; | ||||
| } | } | ||||
| StackEntry *current = cycle_start_entry; | StackEntry *current = cycle_start_entry; | ||||
| OperationNode *to_node = (OperationNode *)relation->to; | OperationNode *to_node = (OperationNode *)relation->to; | ||||
| while (current->node != to_node) { | while (current->node != to_node) { | ||||
| if (check_relation_can_murder(current->via_relation)) { | if (check(current->via_relation)) { | ||||
| return current->via_relation; | return current->via_relation; | ||||
| } | } | ||||
| current = current->from; | current = current->from; | ||||
| } | } | ||||
| return relation; | return NULL; | ||||
| } | |||||
| void report_cycle( | |||||
| Relation *rel, StackEntry *entry, OperationNode *to, Relation *mark, const char *message) | |||||
| { | |||||
| string cycle_str = " " + to->full_identifier() + " depends on\n"; | |||||
| cycle_str += (rel == mark ? "* " : " ") + entry->node->full_identifier() + " via '" + | |||||
| rel->name + "'\n"; | |||||
| StackEntry *current = entry; | |||||
| while (current->node != to) { | |||||
| BLI_assert(current != NULL); | |||||
| cycle_str += (current->via_relation == mark ? "* " : " ") + | |||||
| current->from->node->full_identifier() + " via '" + current->via_relation->name + | |||||
| "'\n"; | |||||
| current = current->from; | |||||
| } | |||||
| printf("%s:\n%s", message, cycle_str.c_str()); | |||||
| } | } | ||||
sergeyUnsubmitted Not Done Inline ActionsSuch refactor can (and likely should) happen separately. sergey: Such refactor can (and likely should) happen separately. | |||||
| /* Solve cycles with all nodes which are scheduled for traversal. */ | /* Solve cycles with all nodes which are scheduled for traversal. */ | ||||
| void solve_cycles(CyclesSolverState *state) | void solve_cycles(CyclesSolverState *state) | ||||
| { | { | ||||
| BLI_Stack *traversal_stack = state->traversal_stack; | BLI_Stack *traversal_stack = state->traversal_stack; | ||||
| while (!BLI_stack_is_empty(traversal_stack)) { | while (!BLI_stack_is_empty(traversal_stack)) { | ||||
| StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack); | StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack); | ||||
| OperationNode *node = entry->node; | OperationNode *node = entry->node; | ||||
| bool all_child_traversed = true; | bool all_child_traversed = true; | ||||
| const int num_visited = get_node_num_visited_children(node); | const int num_visited = get_node_num_visited_children(node); | ||||
| for (int i = num_visited; i < node->outlinks.size(); i++) { | for (int i = num_visited; i < node->outlinks.size(); i++) { | ||||
| Relation *rel = node->outlinks[i]; | Relation *rel = node->outlinks[i]; | ||||
| /* Ignore already removed relations (can happen due to stashing). */ | |||||
| if (rel->flag & RELATION_FLAG_CYCLIC) { | |||||
| continue; | |||||
| } | |||||
| if (rel->to->type == NodeType::OPERATION) { | if (rel->to->type == NodeType::OPERATION) { | ||||
| OperationNode *to = (OperationNode *)rel->to; | OperationNode *to = (OperationNode *)rel->to; | ||||
| eCyclicCheckVisitedState to_state = get_node_visited_state(to); | eCyclicCheckVisitedState to_state = get_node_visited_state(to); | ||||
| if (to_state == NODE_IN_STACK) { | if (to_state == NODE_IN_STACK) { | ||||
| string cycle_str = " " + to->full_identifier() + " depends on\n " + | /* Try removing a physics (collision) relation. */ | ||||
| node->full_identifier() + " via '" + rel->name + "'\n"; | Relation *sacrificial_relation = select_relation( | ||||
| StackEntry *current = entry; | rel, entry, check_relation_can_murder_physics); | ||||
| while (current->node != to) { | if (sacrificial_relation) { | ||||
| BLI_assert(current != NULL); | printf("Ignoring physics dependency of %s on %s (%s)\n", | ||||
| cycle_str += " " + current->from->node->full_identifier() + " via '" + | ((OperationNode *)sacrificial_relation->to)->owner->owner->name.c_str() + 2, | ||||
| current->via_relation->name + "'\n"; | ((OperationNode *)sacrificial_relation->from)->owner->owner->name.c_str() + 2, | ||||
| current = current->from; | sacrificial_relation->name); | ||||
| } | |||||
| /* Remove a random relation. */ | |||||
| else { | |||||
| sacrificial_relation = select_relation(rel, entry, check_relation_can_murder); | |||||
| if (!sacrificial_relation) { | |||||
| sacrificial_relation = rel; | |||||
| } | |||||
| report_cycle(rel, entry, to, sacrificial_relation, "Dependency cycle detected"); | |||||
| } | } | ||||
| printf("Dependency cycle detected:\n%s", cycle_str.c_str()); | |||||
| Relation *sacrificial_relation = select_relation_to_murder(rel, entry); | |||||
| sacrificial_relation->flag |= RELATION_FLAG_CYCLIC; | sacrificial_relation->flag |= RELATION_FLAG_CYCLIC; | ||||
| ++state->num_cycles; | ++state->num_cycles; | ||||
| /* If removing a relation deep in the stack, it is necessary to unwind. */ | |||||
| if (sacrificial_relation != rel) { | |||||
| StackEntry cur_entry; | |||||
| set_node_num_visited_children(node, i); | |||||
| do { | |||||
| BLI_stack_pop(traversal_stack, &cur_entry); | |||||
| set_node_visited_state(cur_entry.node, NODE_STASHED); | |||||
| BLI_stack_push(state->stash_stack, &cur_entry.node); | |||||
| } while (cur_entry.via_relation != sacrificial_relation && | |||||
| !BLI_stack_is_empty(traversal_stack)); | |||||
| all_child_traversed = false; | |||||
| break; | |||||
| } | |||||
| } | } | ||||
| else if (to_state == NODE_NOT_VISITED) { | else if (to_state == NODE_NOT_VISITED || to_state == NODE_STASHED) { | ||||
| StackEntry new_entry; | StackEntry new_entry; | ||||
| new_entry.node = to; | new_entry.node = to; | ||||
| new_entry.from = entry; | new_entry.from = entry; | ||||
| new_entry.via_relation = rel; | new_entry.via_relation = rel; | ||||
| BLI_stack_push(traversal_stack, &new_entry); | BLI_stack_push(traversal_stack, &new_entry); | ||||
| set_node_visited_state(node, NODE_IN_STACK); | set_node_visited_state(node, NODE_IN_STACK); | ||||
| all_child_traversed = false; | all_child_traversed = false; | ||||
| set_node_num_visited_children(node, i); | set_node_num_visited_children(node, i); | ||||
| Show All 29 Lines | |||||
It's relation, not edge. We should keep terminology consistent.
What is a node have multiple input relations? Is it get stashed when ANY or ALL input relations are removed?