diff options
Diffstat (limited to 'source/blender/depsgraph/util/depsgraph_util_cycle.cc')
| -rw-r--r-- | source/blender/depsgraph/util/depsgraph_util_cycle.cc | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cc b/source/blender/depsgraph/util/depsgraph_util_cycle.cc new file mode 100644 index 00000000000..5eae8c087ad --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_cycle.cc @@ -0,0 +1,140 @@ +/* + * ***** 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 + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_cycle.cc + * \ingroup depsgraph + */ + +#include <cstdio> +#include <cstdlib> +#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; +}; + +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"); + printf(" '%s' depends on '%s' through '%s'\n", + to->full_identifier().c_str(), + node->full_identifier().c_str(), + rel->name); + + StackEntry *current = &entry; + while (current->node != to) { + BLI_assert(current != NULL); + printf(" '%s' depends on '%s' through '%s'\n", + current->node->full_identifier().c_str(), + current->from->node->full_identifier().c_str(), + current->via_relation->name); + 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(); + } + } +} |