Differential D6494 Diff 20528 source/blender/depsgraph/intern/builder/deg_builder_cycle.cc

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. */
		sergeyUnsubmitted Not Done Inline Actions 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? sergey: It's `relation`, not `edge`. We should keep terminology consistent. What is a node have…
		angavrilovAuthorUnsubmitted Done Inline Actions It 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 Actions Such 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 Actions Use 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 Actions Actually, 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 The name exactly reflects what it does. No, it doesn't. Even as you've mentioned in this comment, there is a difference between `select relation` and `select first relation that matches predicate`. 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 Actions `check` 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 Actions `predicate` 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 Actions Such 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