[Bf-blender-cvs] [3db13dc] depsgraph_refactor: Depsgraph: Move cycle detection into own file
Sergey Sharybin
noreply at git.blender.org
Mon Mar 16 14:34:55 CET 2015
Commit: 3db13dc6cb7b2ea6292b70728fb4f7a761e895b2
Author: Sergey Sharybin
Date: Mon Mar 16 17:56:39 2015 +0500
Branches: depsgraph_refactor
https://developer.blender.org/rB3db13dc6cb7b2ea6292b70728fb4f7a761e895b2
Depsgraph: Move cycle detection into own file
This way depagraph building code becomes a bit less cluttered and
it makes it simplier to play around with different cycle solving
strategies.
===================================================================
M source/blender/depsgraph/CMakeLists.txt
M source/blender/depsgraph/intern/depsgraph_build.cpp
M source/blender/depsgraph/intern/depsgraph_build.h
A source/blender/depsgraph/util/depsgraph_util_cycle.cpp
A source/blender/depsgraph/util/depsgraph_util_cycle.h
===================================================================
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt
index 951a536..f842a61 100644
--- a/source/blender/depsgraph/CMakeLists.txt
+++ b/source/blender/depsgraph/CMakeLists.txt
@@ -57,6 +57,7 @@ set(SRC
intern/depsgraph_queue.cpp
intern/depsgraph_tag.cpp
intern/depsgraph_type_defines.cpp
+ util/depsgraph_util_cycle.cpp
util/depsgraph_util_pchanmap.cpp
DEG_depsgraph.h
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cpp b/source/blender/depsgraph/intern/depsgraph_build.cpp
index 9ab8755..1cb53b8 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_build.cpp
@@ -27,9 +27,6 @@
*/
#include <stack>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
#include "MEM_guardedalloc.h"
@@ -99,6 +96,8 @@ extern "C" {
#include "depsgraph_eval.h"
#include "depsgraph_intern.h"
+#include "depsgraph_util_cycle.h"
+
/* ****************** */
/* External Build API */
@@ -333,128 +332,6 @@ static void deg_graph_build_finalize(Depsgraph *graph)
}
}
-/* *************** */
-/* Cycle detection */
-
-static void deg_graph_print_cycle_rel(const OperationDepsNode *to,
- const OperationDepsNode *from,
- const DepsRelation *rel)
-{
- string to_owner = "", from_owner = "";
-
- /* NOTE: subdata name only matters for bones; all other components currently
- * should just use the ID instead/
- **/
- if (to->owner->type == DEPSNODE_TYPE_BONE) {
- to_owner = to->owner->owner->name + "." + to->owner->name + ".";
- }
- else {
- to_owner = to->owner->owner->name + ".";
- }
-
- if (from->owner->type == DEPSNODE_TYPE_BONE) {
- from_owner = from->owner->owner->name + "." + from->owner->name + ".";
- }
- else {
- from_owner = from->owner->owner->name + ".";
- }
-
- printf(" '%s%s' depends on '%s%s' through '%s'\n",
- to_owner.c_str(),
- to->identifier().c_str(),
- from_owner.c_str(),
- from->identifier().c_str(),
- rel->name.c_str());
-}
-
-/* TODO(sergey): Consider moving to proper location. */
-struct StackEntry {
- OperationDepsNode *node;
- StackEntry *from;
- DepsRelation *via_relation;
-};
-
-static void deg_graph_detect_cycles(Depsgraph *graph)
-{
- /* Not is not visited at all during traversal. */
- const int NODE_NOT_VISITED = 0;
- /* Node has been visited during traversal and not in current stack. */
- const int NODE_VISITED = 1;
- /* Node has been visited during traversal and is in current stack. */
- const int NODE_IN_STACK = 2;
-
- std::stack<StackEntry> traversal_stack;
- for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
- it_op != graph->operations.end();
- ++it_op)
- {
- OperationDepsNode *node = *it_op;
- bool has_inlinks = false;
- for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
- it_rel != node->inlinks.end();
- ++it_rel)
- {
- DepsRelation *rel = *it_rel;
- if (rel->from->type == DEPSNODE_TYPE_OPERATION) {
- has_inlinks = true;
- }
- }
- if (has_inlinks == false) {
- StackEntry entry;
- entry.node = node;
- entry.from = NULL;
- entry.via_relation = NULL;
- traversal_stack.push(entry);
- node->done = NODE_IN_STACK;
- }
- else {
- node->done = NODE_NOT_VISITED;
- }
- }
-
- while (!traversal_stack.empty()) {
- StackEntry &entry = traversal_stack.top();
- OperationDepsNode *node = entry.node;
- bool all_child_traversed = true;
- for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
- it_rel != node->outlinks.end();
- ++it_rel)
- {
- DepsRelation *rel = *it_rel;
- if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
- OperationDepsNode *to = (OperationDepsNode *)rel->to;
- if (to->done == NODE_IN_STACK) {
- printf("Dependency cycle detected:\n");
- deg_graph_print_cycle_rel(to, node, rel);
-
- StackEntry *current = &entry;
- while (current->node != to) {
- BLI_assert(current != NULL);
- deg_graph_print_cycle_rel(current->node, current->from->node, current->via_relation);
- current = current->from;
- }
- /* TODO(sergey): So called roussian rlette cycle solver. */
- rel->flag |= DEPSREL_FLAG_CYCLIC;
- }
- else if (to->done == NODE_NOT_VISITED) {
- StackEntry new_entry;
- new_entry.node = to;
- new_entry.from = &entry;
- new_entry.via_relation = rel;
- traversal_stack.push(new_entry);
- to->done = NODE_IN_STACK;
- all_child_traversed = false;
- break;
- }
- }
- }
- if (all_child_traversed) {
- node->done = NODE_VISITED;
- traversal_stack.pop();
- }
- }
-}
-
/* ******************** */
/* Graph Building API's */
diff --git a/source/blender/depsgraph/intern/depsgraph_build.h b/source/blender/depsgraph/intern/depsgraph_build.h
index 447a934..edcbcc1 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.h
+++ b/source/blender/depsgraph/intern/depsgraph_build.h
@@ -27,6 +27,8 @@
#ifndef __DEPSGRAPH_BUILD_H__
#define __DEPSGRAPH_BUILD_H__
+struct Base;
+struct bGPdata;
struct ListBase;
struct GHash;
struct ID;
@@ -44,6 +46,8 @@ struct Scene;
struct Tex;
struct World;
+struct PropertyRNA;
+
struct Depsgraph;
struct DepsNode;
struct DepsNodeHandle;
diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cpp b/source/blender/depsgraph/util/depsgraph_util_cycle.cpp
new file mode 100644
index 0000000..aafad0b
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_cycle.cpp
@@ -0,0 +1,160 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Sergey Sharybin
+ */
+
+#include <cstdio>
+#include <stack>
+
+extern "C" {
+#include "BLI_utildefines.h"
+
+#include "DNA_ID.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+}
+
+#include "depsgraph_util_cycle.h"
+#include "depsgraph.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+
+struct StackEntry {
+ OperationDepsNode *node;
+ StackEntry *from;
+ DepsRelation *via_relation;
+};
+
+static void deg_graph_print_cycle_rel(const OperationDepsNode *to,
+ const OperationDepsNode *from,
+ const DepsRelation *rel)
+{
+ string to_owner = "", from_owner = "";
+
+ /* NOTE: subdata name only matters for bones; all other components currently
+ * should just use the ID instead.
+ */
+ if (to->owner->type == DEPSNODE_TYPE_BONE) {
+ to_owner = to->owner->owner->name + "." + to->owner->name + ".";
+ }
+ else {
+ to_owner = to->owner->owner->name + ".";
+ }
+
+ if (from->owner->type == DEPSNODE_TYPE_BONE) {
+ from_owner = from->owner->owner->name + "." + from->owner->name + ".";
+ }
+ else {
+ from_owner = from->owner->owner->name + ".";
+ }
+
+ printf(" '%s%s' depends on '%s%s' through '%s'\n",
+ to_owner.c_str(),
+ to->identifier().c_str(),
+ from_owner.c_str(),
+ from->identifier().c_str(),
+ rel->name.c_str());
+}
+
+void deg_graph_detect_cycles(Depsgraph *graph)
+{
+ /* Not is not visited at all during traversal. */
+ const int NODE_NOT_VISITED = 0;
+ /* Node has been visited during traversal and not in current stack. */
+ const int NODE_VISITED = 1;
+ /* Node has been visited during traversal and is in current stack. */
+ const int NODE_IN_STACK = 2;
+
+ std::stack<StackEntry> traversal_stack;
+ for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
+ it_op != graph->operations.end();
+ ++it_op)
+ {
+ OperationDepsNode *node = *it_op;
+ bool has_inlinks = false;
+ for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
+ it_rel != node->inlinks.end();
+ ++it_rel)
+ {
+ DepsRelation *rel = *it_rel;
+ if (rel->from->type == DEPSNODE_TYPE_OPERATION) {
+ has_inlinks = true;
+ }
+ }
+ if (has_inlinks == false) {
+ StackEntry entry;
+ entry.node = node;
+ entry.from = NULL;
+ entry.via_relation = NULL;
+ traversal_stack.push(entry);
+ node->done = NODE_IN_STACK;
+ }
+ else {
+ node->done = NODE_NOT_VISITED;
+ }
+ }
+
+ while (!traversal_stack.empty()) {
+ StackEntry &entry = traversal_stack.top();
+ OperationDepsNode *node = entry.node;
+ bool all_child_traversed = true;
+ for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
+ it_rel != node->outlinks.end();
+ ++it_rel)
+ {
+ DepsRelation *rel = *it_rel;
+ if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
+ OperationDepsNode *to = (OperationDepsNode *)rel->to;
+ if (to->done == NODE_IN_STACK) {
+ printf("Dependency cycle detected:\n");
+ deg_graph_print_cycle_rel(to, node, rel);
+
+ StackEntry *current = &entry;
+ while (current->node != to) {
+ BLI_assert(current != NULL);
+ deg_graph_print_cycle_rel(current->node,
+ current->from->node,
+ current->via_relation);
+ current = current->from;
+ }
+ /* TODO(sergey): So called roussian rlette cycle solver. */
+ rel->flag |= DEPSREL_FLAG_CYCLIC;
+ }
+ else if (to->done == NODE_NOT_VISITED) {
+ StackEntry new_entry;
+ new_entry.node = to;
+ new_entry.from = &entry;
+ new_entry.via_relation = rel;
+ traversal_stack.push(new_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list