diff options
48 files changed, 3055 insertions, 3275 deletions
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt index 2b4df85f29c..fd2a521bec5 100644 --- a/source/blender/depsgraph/CMakeLists.txt +++ b/source/blender/depsgraph/CMakeLists.txt @@ -25,8 +25,6 @@ set(INC . - intern - util ../blenkernel ../blenlib ../bmesh @@ -42,45 +40,50 @@ set(INC_SYS ) set(SRC + intern/builder/deg_builder.cc + intern/builder/deg_builder_cycle.cc + intern/builder/deg_builder_nodes.cc + intern/builder/deg_builder_pchanmap.cc + intern/builder/deg_builder_relations.cc + intern/builder/deg_builder_transitive.cc + intern/debug/deg_debug_graphviz.cc + intern/eval/deg_eval.cc + intern/eval/deg_eval_debug.cc + intern/eval/deg_eval_flush.cc + intern/nodes/deg_node.cc + intern/nodes/deg_node_component.cc + intern/nodes/deg_node_operation.cc intern/depsgraph.cc - intern/depsnode.cc - intern/depsnode_component.cc - intern/depsnode_operation.cc intern/depsgraph_build.cc - intern/depsgraph_build_nodes.cc - intern/depsgraph_build_relations.cc intern/depsgraph_debug.cc intern/depsgraph_eval.cc intern/depsgraph_query.cc - intern/depsgraph_queue.cc intern/depsgraph_tag.cc intern/depsgraph_type_defines.cc - util/depsgraph_util_cycle.cc - util/depsgraph_util_pchanmap.cc - util/depsgraph_util_transitive.cc DEG_depsgraph.h DEG_depsgraph_build.h DEG_depsgraph_debug.h DEG_depsgraph_query.h + + intern/builder/deg_builder.h + intern/builder/deg_builder_cycle.h + intern/builder/deg_builder_nodes.h + intern/builder/deg_builder_pchanmap.h + intern/builder/deg_builder_relations.h + intern/builder/deg_builder_transitive.h + intern/eval/deg_eval.h + intern/eval/deg_eval_debug.h + intern/eval/deg_eval_flush.h + intern/nodes/deg_node.h + intern/nodes/deg_node_component.h + intern/nodes/deg_node_operation.h intern/depsgraph.h - intern/depsnode.h - intern/depsnode_component.h - intern/depsnode_operation.h - intern/depsnode_opcodes.h - intern/depsgraph_build.h - intern/depsgraph_debug.h intern/depsgraph_intern.h - intern/depsgraph_queue.h intern/depsgraph_types.h - util/depsgraph_util_cycle.h - util/depsgraph_util_function.h - util/depsgraph_util_hash.h - util/depsgraph_util_map.h - util/depsgraph_util_pchanmap.h - util/depsgraph_util_set.h - util/depsgraph_util_transitive.h + util/deg_util_function.h + util/deg_util_hash.h ) if(WITH_CXX11) diff --git a/source/blender/depsgraph/DEG_depsgraph.h b/source/blender/depsgraph/DEG_depsgraph.h index f37ba71ab65..d1de83ec8a9 100644 --- a/source/blender/depsgraph/DEG_depsgraph.h +++ b/source/blender/depsgraph/DEG_depsgraph.h @@ -131,9 +131,6 @@ void DEG_ids_clear_recalc(struct Main *bmain); /* Update Flushing ------------------------------- */ -/* Flush updates */ -void DEG_graph_flush_updates(struct Main *bmain, Depsgraph *graph); - /* Flush updates for all IDs */ void DEG_ids_flush_tagged(struct Main *bmain); @@ -144,11 +141,6 @@ void DEG_ids_check_recalc(struct Main *bmain, struct Scene *scene, bool time); -/* Clear all update tags - * - For aborted updates, or after successful evaluation - */ -void DEG_graph_clear_tags(Depsgraph *graph); - /* ************************************************ */ /* Evaluation Engine API */ diff --git a/source/blender/depsgraph/DEG_depsgraph_build.h b/source/blender/depsgraph/DEG_depsgraph_build.h index f680c47247a..49b648c7dae 100644 --- a/source/blender/depsgraph/DEG_depsgraph_build.h +++ b/source/blender/depsgraph/DEG_depsgraph_build.h @@ -43,9 +43,6 @@ struct Depsgraph; struct Main; struct Scene; -struct PointerRNA; -struct PropertyRNA; - #ifdef __cplusplus extern "C" { #endif diff --git a/source/blender/depsgraph/DEG_depsgraph_debug.h b/source/blender/depsgraph/DEG_depsgraph_debug.h index 374fad63c34..0d19b8e1e97 100644 --- a/source/blender/depsgraph/DEG_depsgraph_debug.h +++ b/source/blender/depsgraph/DEG_depsgraph_debug.h @@ -39,13 +39,10 @@ extern "C" { #endif -struct DepsgraphSettings; struct GHash; struct ID; struct Depsgraph; -struct DepsNode; -struct DepsRelation; /* ************************************************ */ /* Statistics */ diff --git a/source/blender/depsgraph/DEG_depsgraph_query.h b/source/blender/depsgraph/DEG_depsgraph_query.h index 60d673d4c5b..ccd204a2083 100644 --- a/source/blender/depsgraph/DEG_depsgraph_query.h +++ b/source/blender/depsgraph/DEG_depsgraph_query.h @@ -19,7 +19,7 @@ * All rights reserved. * * Original Author: Joshua Leung - * Contributor(s): None Yet + * Contributor(s): Sergey Sharybin * * ***** END GPL LICENSE BLOCK ***** */ @@ -33,155 +33,14 @@ #ifndef __DEG_DEPSGRAPH_QUERY_H__ #define __DEG_DEPSGRAPH_QUERY_H__ -struct ListBase; struct ID; struct Depsgraph; -struct DepsNode; -struct DepsRelation; #ifdef __cplusplus extern "C" { #endif -/* ************************************************ */ -/* Type Defines */ - -/* FilterPredicate Callback - * - * Defines a callback function which can be supplied to check whether a - * node is relevant or not. - * - * < graph: Depsgraph that we're traversing - * < node: The node to check - * < userdata: FilterPredicate state data (as needed) - * > returns: True if node is relevant - */ -typedef bool (*DEG_FilterPredicate)(const struct Depsgraph *graph, const struct DepsNode *node, void *userdata); - - -/* Node Operation - * - * Performs some action on the given node, provided that the node was - * deemed to be relevant to operate on. - * - * < graph: Depsgraph that we're traversing - * < node: The node to perform operation on/with - * < userdata: Node Operation's state data (as needed) - * > returns: True if traversal should be aborted at this point - */ -typedef bool (*DEG_NodeOperation)(const struct Depsgraph *graph, struct DepsNode *node, void *userdata); - -/* ************************************************ */ -/* Low-Level Filtering API */ - -/* Create a filtered copy of the given graph which contains only the - * nodes which fulfill the criteria specified using the FilterPredicate - * passed in. - * - * < graph: The graph to be copied and filtered - * < filter: FilterPredicate used to check which nodes should be included - * (If null, full graph is copied as-is) - * < userdata: State data for filter (as necessary) - * - * > returns: a full copy of all the relevant nodes - the matching subgraph - */ -// XXX: is there any need for extra settings/options for how the filtering goes? -Depsgraph *DEG_graph_filter(const struct Depsgraph *graph, DEG_FilterPredicate *filter, void *userdata); - - -/* Traverse nodes in graph which are deemed relevant, - * performing the provided operation on the nodes. - * - * < graph: The graph to perform operations on - * < filter: FilterPredicate used to check which nodes should be included - * (If null, all nodes are considered valid targets) - * < filter_data: Custom state data for FilterPredicate - * (Note: This can be the same as op_data, where appropriate) - * < op: NodeOperation to perform on each node - * (If null, no graph traversal is performed for efficiency) - * < op_data: Custom state data for NodeOperation - * (Note: This can be the same as filter_data, where appropriate) - */ -void DEG_graph_traverse(const struct Depsgraph *graph, - DEG_FilterPredicate *filter, void *filter_data, - DEG_NodeOperation *op, void *op_data); - -/* ************************************************ */ -/* Node-Based Operations */ -// XXX: do we want to be able to attach conditional requirements here? - -/* Find an (outer) node matching given conditions - * ! Assumes that there will only be one such node, or that only the first one matters - * - * < graph: a dependency graph which may or may not contain a node matching these requirements - * < query: query conditions for the criteria that the node must satisfy - */ -//DepsNode *DEG_node_find(const Depsgraph *graph, DEG_QueryConditions *query); - -/* Topology Queries (Direct) ---------------------- */ - -/* Get list of nodes which directly depend on given node - * - * > result: list to write results to - * < node: the node to find the children/dependents of - */ -void DEG_node_get_children(struct ListBase *result, const struct DepsNode *node); - - -/* Get list of nodes which given node directly depends on - * - * > result: list to write results to - * < node: the node to find the dependencies of - */ -void DEG_node_get_dependencies(struct ListBase *result, const struct DepsNode *node); - - -/* Topology Queries (Subgraph) -------------------- */ -// XXX: given that subgraphs potentially involve many interconnected nodes, we currently -// just spit out a copy of the subgraph which matches. This works well for the cases -// where these are used - mostly for efficient updating of subsets of the nodes. - -// XXX: allow supplying a filter predicate to provide further filtering/pruning? - - -/* Get all descendants of a node - * - * That is, get the subgraph / subset of nodes which are dependent - * on the results of the given node. - */ -Depsgraph *DEG_node_get_descendants(const struct Depsgraph *graph, const struct DepsNode *node); - - -/* Get all ancestors of a node - * - * That is, get the subgraph / subset of nodes which the given node - * is dependent on in order to be evaluated. - */ -Depsgraph *DEG_node_get_ancestors(const struct Depsgraph *graph, const struct DepsNode *node); - -/* ************************************************ */ -/* Higher-Level Queries */ - -/* Get ID-blocks which would be affected if specified ID is modified - * < only_direct: True = Only ID-blocks with direct relationships to ID-block will be returned - * - * > result: (LinkData : ID) a list of ID-blocks matching the specified criteria - * > returns: number of matching ID-blocks - */ -size_t DEG_query_affected_ids(struct ListBase *result, const struct ID *id, const bool only_direct); - - -/* Get ID-blocks which are needed to update/evaluate specified ID - * < only_direct: True = Only ID-blocks with direct relationships to ID-block will be returned - * - * > result: (LinkData : ID) a list of ID-blocks matching the specified criteria - * > returns: number of matching ID-blocks - */ -size_t DEG_query_required_ids(struct ListBase *result, const struct ID *id, const bool only_direct); - -/* ************************************************ */ - /* Check if given ID type was tagged for update. */ bool DEG_id_type_tagged(struct Main *bmain, short idtype); diff --git a/source/blender/depsgraph/intern/builder/deg_builder.cc b/source/blender/depsgraph/intern/builder/deg_builder.cc new file mode 100644 index 00000000000..cf9b0cee6b2 --- /dev/null +++ b/source/blender/depsgraph/intern/builder/deg_builder.cc @@ -0,0 +1,125 @@ +/* + * ***** 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) 2016 Blender Foundation. + * All rights reserved. + * + * Original Author: Sergey Sharybin + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/build/deg_builder.cc + * \ingroup depsgraph + */ + +#include "intern/builder/deg_builder.h" + +// TODO(sergey): Use own wrapper over STD. +#include <stack> + +#include "DNA_anim_types.h" + +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + +#include "intern/depsgraph.h" +#include "intern/depsgraph_types.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "util/deg_util_foreach.h" + +namespace DEG { + +string deg_fcurve_id_name(const FCurve *fcu) +{ + char index_buf[32]; + // TODO(sergey): Use int-to-string utility or so. + BLI_snprintf(index_buf, sizeof(index_buf), "[%d]", fcu->array_index); + return string(fcu->rna_path) + index_buf; +} + +void deg_graph_build_finalize(Depsgraph *graph) +{ + std::stack<OperationDepsNode *> stack; + + foreach (OperationDepsNode *node, graph->operations) { + node->done = 0; + node->num_links_pending = 0; + foreach (DepsRelation *rel, node->inlinks) { + if ((rel->from->type == DEPSNODE_TYPE_OPERATION) && + (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) + { + ++node->num_links_pending; + } + } + if (node->num_links_pending == 0) { + stack.push(node); + } + IDDepsNode *id_node = node->owner->owner; + id_node->id->tag |= LIB_TAG_DOIT; + } + + while (!stack.empty()) { + OperationDepsNode *node = stack.top(); + if (node->done == 0 && node->outlinks.size() != 0) { + foreach (DepsRelation *rel, node->outlinks) { + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { + BLI_assert(to->num_links_pending > 0); + --to->num_links_pending; + } + if (to->num_links_pending == 0) { + stack.push(to); + } + } + } + node->done = 1; + } + else { + stack.pop(); + IDDepsNode *id_node = node->owner->owner; + foreach (DepsRelation *rel, node->outlinks) { + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + IDDepsNode *id_to = to->owner->owner; + id_node->layers |= id_to->layers; + } + } + } + } + + /* Re-tag IDs for update if it was tagged before the relations update tag. */ + GHASH_FOREACH_BEGIN(IDDepsNode *, id_node, graph->id_hash) + { + ID *id = id_node->id; + if (id->tag & LIB_TAG_ID_RECALC_ALL && + id->tag & LIB_TAG_DOIT) + { + id_node->tag_update(graph); + id->tag &= ~LIB_TAG_DOIT; + } + id_node->finalize_build(); + } + GHASH_FOREACH_END(); +} + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/builder/deg_builder.h b/source/blender/depsgraph/intern/builder/deg_builder.h new file mode 100644 index 00000000000..7ecb4b20684 --- /dev/null +++ b/source/blender/depsgraph/intern/builder/deg_builder.h @@ -0,0 +1,46 @@ +/* + * ***** 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) 2016 Blender Foundation. + * All rights reserved. + * + * Original Author: Sergey Sharybin + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/build/deg_builder.h + * \ingroup depsgraph + */ + +#pragma once + +#include "intern/depsgraph_types.h" + +struct FCurve; + +namespace DEG { + +struct Depsgraph; + +/* Get unique identifier for FCurves and Drivers */ +string deg_fcurve_id_name(const FCurve *fcu); + +void deg_graph_build_finalize(struct Depsgraph *graph); + +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc index 5eae8c087ad..225cc64ae4d 100644 --- a/source/blender/depsgraph/util/depsgraph_util_cycle.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc @@ -23,28 +23,30 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_cycle.cc +/** \file blender/depsgraph/intern/builder/deg_builder_cycle.cc * \ingroup depsgraph */ +#include "intern/builder/deg_builder_cycle.h" + +// TOO(sergey): Use some wrappers over those? #include <cstdio> #include <cstdlib> #include <stack> extern "C" { #include "BLI_utildefines.h" +} -#include "DNA_ID.h" +#include "util/deg_util_foreach.h" -#include "RNA_access.h" -#include "RNA_types.h" -} +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" -#include "depsgraph_util_cycle.h" -#include "depsgraph.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" +#include "intern/depsgraph.h" + +namespace DEG { struct StackEntry { OperationDepsNode *node; @@ -62,17 +64,9 @@ void deg_graph_detect_cycles(Depsgraph *graph) 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; + foreach (OperationDepsNode *node, graph->operations) { 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; + foreach (DepsRelation *rel, node->inlinks) { if (rel->from->type == DEPSNODE_TYPE_OPERATION) { has_inlinks = true; } @@ -94,11 +88,7 @@ void deg_graph_detect_cycles(Depsgraph *graph) 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; + foreach (DepsRelation *rel, node->outlinks) { if (rel->to->type == DEPSNODE_TYPE_OPERATION) { OperationDepsNode *to = (OperationDepsNode *)rel->to; if (to->done == NODE_IN_STACK) { @@ -138,3 +128,5 @@ void deg_graph_detect_cycles(Depsgraph *graph) } } } + +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.h b/source/blender/depsgraph/intern/builder/deg_builder_cycle.h index fac38b61057..386fbd80d19 100644 --- a/source/blender/depsgraph/util/depsgraph_util_cycle.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.h @@ -23,15 +23,18 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_cycle.h +/** \file blender/depsgraph/intern/builder/deg_builder_cycle.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_CYCLE_H__ -#define __DEPSGRAPH_UTIL_CYCLE_H__ + +#pragma once + +namespace DEG { struct Depsgraph; +/* Detect and solve dependency cycles. */ void deg_graph_detect_cycles(Depsgraph *graph); -#endif /* __DEPSGRAPH_UTIL_CYCLE_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_build_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc index acb873875da..5359cc8754a 100644 --- a/source/blender/depsgraph/intern/depsgraph_build_nodes.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc @@ -24,12 +24,14 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/intern/depsgraph_build_nodes.cc +/** \file blender/depsgraph/intern/builder/deg_build_nodes.cc * \ingroup depsgraph * * Methods for constructing depsgraph's nodes */ +#include "intern/builder/deg_builder_nodes.h" + #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -97,12 +99,14 @@ extern "C" { #include "RNA_types.h" } /* extern "C" */ -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_types.h" -#include "depsgraph_build.h" -#include "depsgraph_intern.h" +#include "intern/builder/deg_builder.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph_types.h" +#include "intern/depsgraph_intern.h" + +namespace DEG { /* ************ */ /* Node Builder */ @@ -217,6 +221,17 @@ OperationDepsNode *DepsgraphNodeBuilder::add_operation_node( return add_operation_node(comp_node, optype, op, opcode, description); } +OperationDepsNode *DepsgraphNodeBuilder::add_operation_node( + ID *id, + eDepsNode_Type comp_type, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string& description) +{ + return add_operation_node(id, comp_type, "", optype, op, opcode, description); +} + bool DepsgraphNodeBuilder::has_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, @@ -237,6 +252,14 @@ OperationDepsNode *DepsgraphNodeBuilder::find_operation_node( return comp_node->has_operation(opcode, description); } +OperationDepsNode *DepsgraphNodeBuilder::find_operation_node( + ID *id, + eDepsNode_Type comp_type, + eDepsOperation_Code opcode, + const string& description) +{ + return find_operation_node(id, comp_type, "", opcode, description); +} /* **** Build functions for entity nodes **** */ @@ -343,7 +366,7 @@ SubgraphDepsNode *DepsgraphNodeBuilder::build_subgraph(Group *group) return NULL; /* create new subgraph's data */ - Depsgraph *subgraph = DEG_graph_new(); + Depsgraph *subgraph = reinterpret_cast<Depsgraph *>(DEG_graph_new()); DepsgraphNodeBuilder subgraph_builder(m_bmain, subgraph); @@ -1234,3 +1257,5 @@ void DepsgraphNodeBuilder::build_gpencil(bGPdata *gpd) */ build_animdata(gpd_id); } + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h new file mode 100644 index 00000000000..6ee0b8406a1 --- /dev/null +++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h @@ -0,0 +1,153 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/builder/deg_builder_nodes.h + * \ingroup depsgraph + */ + +#pragma once + +#include "intern/depsgraph_types.h" + +struct Base; +struct bGPdata; +struct ListBase; +struct GHash; +struct ID; +struct FCurve; +struct Group; +struct Key; +struct Main; +struct Material; +struct MTex; +struct bNodeTree; +struct Object; +struct bPoseChannel; +struct bConstraint; +struct Scene; +struct Tex; +struct World; + +struct PropertyRNA; + +namespace DEG { + +struct Depsgraph; +struct DepsNode; +struct RootDepsNode; +struct SubgraphDepsNode; +struct IDDepsNode; +struct TimeSourceDepsNode; +struct ComponentDepsNode; +struct OperationDepsNode; + +struct DepsgraphNodeBuilder { + DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph); + ~DepsgraphNodeBuilder(); + + RootDepsNode *add_root_node(); + IDDepsNode *add_id_node(ID *id); + TimeSourceDepsNode *add_time_source(ID *id); + + ComponentDepsNode *add_component_node(ID *id, + eDepsNode_Type comp_type, + const string& comp_name = ""); + + OperationDepsNode *add_operation_node(ComponentDepsNode *comp_node, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string& description = ""); + OperationDepsNode *add_operation_node(ID *id, + eDepsNode_Type comp_type, + const string& comp_name, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string& description = ""); + OperationDepsNode *add_operation_node(ID *id, + eDepsNode_Type comp_type, + eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string& description = ""); + + bool has_operation_node(ID *id, + eDepsNode_Type comp_type, + const string& comp_name, + eDepsOperation_Code opcode, + const string& description = ""); + + OperationDepsNode *find_operation_node(ID *id, + eDepsNode_Type comp_type, + const string &comp_name, + eDepsOperation_Code opcode, + const string &description = ""); + + OperationDepsNode *find_operation_node(ID *id, + eDepsNode_Type comp_type, + eDepsOperation_Code opcode, + const string &description = ""); + + void build_scene(Main *bmain, Scene *scene); + SubgraphDepsNode *build_subgraph(Group *group); + void build_group(Scene *scene, Base *base, Group *group); + void build_object(Scene *scene, Base *base, Object *ob); + void build_object_transform(Scene *scene, Object *ob); + void build_object_constraints(Scene *scene, Object *ob); + void build_pose_constraints(Object *ob, bPoseChannel *pchan); + void build_rigidbody(Scene *scene); + void build_particles(Scene *scene, Object *ob); + void build_animdata(ID *id); + OperationDepsNode *build_driver(ID *id, FCurve *fcurve); + void build_ik_pose(Scene *scene, + Object *ob, + bPoseChannel *pchan, + bConstraint *con); + void build_splineik_pose(Scene *scene, + Object *ob, + bPoseChannel *pchan, + bConstraint *con); + void build_rig(Scene *scene, Object *ob); + void build_proxy_rig(Object *ob); + void build_shapekeys(Key *key); + void build_obdata_geom(Scene *scene, Object *ob); + void build_camera(Object *ob); + void build_lamp(Object *ob); + void build_nodetree(DepsNode *owner_node, bNodeTree *ntree); + void build_material(DepsNode *owner_node, Material *ma); + void build_texture(DepsNode *owner_node, Tex *tex); + void build_texture_stack(DepsNode *owner_node, MTex **texture_stack); + void build_world(World *world); + void build_compositor(Scene *scene); + void build_gpencil(bGPdata *gpd); + +protected: + Main *m_bmain; + Depsgraph *m_graph; +}; + +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc b/source/blender/depsgraph/intern/builder/deg_builder_pchanmap.cc index 80b37ec622d..0e78df52ff8 100644 --- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_pchanmap.cc @@ -24,11 +24,11 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_pchanmap.cc +/** \file blender/depsgraph/intern/builder/deg_builder_pchanmap.h * \ingroup depsgraph */ -#include "depsgraph_util_pchanmap.h" +#include "intern/builder/deg_builder_pchanmap.h" #include <stdio.h> #include <string.h> @@ -38,6 +38,8 @@ extern "C" { #include "BLI_ghash.h" } +namespace DEG { + static void free_rootpchanmap_valueset(void *val) { /* Just need to free the set itself - the names stored are all references. */ @@ -48,13 +50,13 @@ static void free_rootpchanmap_valueset(void *val) RootPChanMap::RootPChanMap() { /* Just create empty map. */ - m_map = BLI_ghash_str_new("RootPChanMap"); + map_ = BLI_ghash_str_new("RootPChanMap"); } RootPChanMap::~RootPChanMap() { /* Free the map, and all the value sets. */ - BLI_ghash_free(m_map, NULL, free_rootpchanmap_valueset); + BLI_ghash_free(map_, NULL, free_rootpchanmap_valueset); } /* Debug contents of map */ @@ -64,7 +66,7 @@ void RootPChanMap::print_debug() GSetIterator it2; printf("Root PChan Map:\n"); - GHASH_ITER(it1, m_map) { + GHASH_ITER(it1, map_) { const char *item = (const char *)BLI_ghashIterator_getKey(&it1); GSet *values = (GSet *)BLI_ghashIterator_getValue(&it1); @@ -80,11 +82,11 @@ void RootPChanMap::print_debug() /* Add a mapping. */ void RootPChanMap::add_bone(const char *bone, const char *root) { - if (BLI_ghash_haskey(m_map, bone)) { + if (BLI_ghash_haskey(map_, bone)) { /* Add new entry, but only add the root if it doesn't already * exist in there. */ - GSet *values = (GSet *)BLI_ghash_lookup(m_map, bone); + GSet *values = (GSet *)BLI_ghash_lookup(map_, bone); BLI_gset_add(values, (void *)root); } else { @@ -92,7 +94,7 @@ void RootPChanMap::add_bone(const char *bone, const char *root) GSet *values = BLI_gset_new(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, "RootPChanMap Value Set"); - BLI_ghash_insert(m_map, (void *)bone, (void *)values); + BLI_ghash_insert(map_, (void *)bone, (void *)values); /* Add new entry now. */ BLI_gset_insert(values, (void *)root); @@ -103,20 +105,20 @@ void RootPChanMap::add_bone(const char *bone, const char *root) bool RootPChanMap::has_common_root(const char *bone1, const char *bone2) { /* Ensure that both are in the map... */ - if (BLI_ghash_haskey(m_map, bone1) == false) { + if (BLI_ghash_haskey(map_, bone1) == false) { //fprintf("RootPChanMap: bone1 '%s' not found (%s => %s)\n", bone1, bone1, bone2); //print_debug(); return false; } - if (BLI_ghash_haskey(m_map, bone2) == false) { + if (BLI_ghash_haskey(map_, bone2) == false) { //fprintf("RootPChanMap: bone2 '%s' not found (%s => %s)\n", bone2, bone1, bone2); //print_debug(); return false; } - GSet *bone1_roots = (GSet *)BLI_ghash_lookup(m_map, (void *)bone1); - GSet *bone2_roots = (GSet *)BLI_ghash_lookup(m_map, (void *)bone2); + GSet *bone1_roots = (GSet *)BLI_ghash_lookup(map_, (void *)bone1); + GSet *bone2_roots = (GSet *)BLI_ghash_lookup(map_, (void *)bone2); GSetIterator it1, it2; GSET_ITER(it1, bone1_roots) { @@ -134,3 +136,5 @@ bool RootPChanMap::has_common_root(const char *bone1, const char *bone2) //fprintf("RootPChanMap: No common root found (%s => %s)\n", bone1, bone2); return false; } + +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h b/source/blender/depsgraph/intern/builder/deg_builder_pchanmap.h index b7f4c495933..233d8602fce 100644 --- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_pchanmap.h @@ -24,12 +24,15 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_pchanmap.h +/** \file blender/depsgraph/intern/builder/deg_builder_pchanmap.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_PCHANMAP_H__ -#define __DEPSGRAPH_UTIL_PCHANMAP_H__ +#pragma once + +struct GHash; + +namespace DEG { struct RootPChanMap { /* ctor and dtor - Create and free the internal map respectively. */ @@ -45,7 +48,7 @@ struct RootPChanMap { /* Check if there's a common root bone between two bones. */ bool has_common_root(const char *bone1, const char *bone2); -private: +protected: /* The actual map: * - Keys are "strings" (const char *) - not dynamically allocated. * - Values are "sets" (const char *) - not dynamically allocated. @@ -53,7 +56,7 @@ private: * We don't use the C++ maps here, as it's more convenient to use * Blender's GHash and be able to compare by-value instead of by-ref. */ - struct GHash *m_map; + struct GHash *map_; }; -#endif /* __DEPSGRAPH_UTIL_PCHANMAP_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_build_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc index 126b34cc9df..10aebb75fbf 100644 --- a/source/blender/depsgraph/intern/depsgraph_build_relations.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc @@ -24,12 +24,14 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/intern/depsgraph_build_relations.cc +/** \file blender/depsgraph/intern/builder/deg_builder_relations.cc * \ingroup depsgraph * * Methods for constructing depsgraph */ +#include "intern/builder/deg_builder_relations.h" + #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -93,15 +95,19 @@ extern "C" { #include "RNA_types.h" } /* extern "C" */ -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_build.h" -#include "depsgraph_debug.h" -#include "depsgraph_intern.h" -#include "depsgraph_types.h" +#include "intern/builder/deg_builder.h" +#include "intern/builder/deg_builder_pchanmap.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "intern/depsgraph_intern.h" +#include "intern/depsgraph_types.h" -#include "depsgraph_util_pchanmap.h" +#include "util/deg_util_foreach.h" + +namespace DEG { /* ***************** */ /* Relations Builder */ @@ -786,8 +792,7 @@ void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu) if (arm_node && bone_name) { /* find objects which use this, and make their eval callbacks depend on this */ - DEPSNODE_RELATIONS_ITER_BEGIN(arm_node->outlinks, rel) - { + foreach (DepsRelation *rel, arm_node->outlinks) { IDDepsNode *to_node = (IDDepsNode *)rel->to; /* we only care about objects with pose data which use this... */ @@ -801,7 +806,6 @@ void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu) } } } - DEPSNODE_RELATIONS_ITER_END; /* free temp data */ MEM_freeN(bone_name); @@ -1636,13 +1640,18 @@ void DepsgraphRelationBuilder::build_obdata_geom(Main *bmain, Scene *scene, Obje if (mti->updateDepsgraph) { DepsNodeHandle handle = create_node_handle(mod_key); - mti->updateDepsgraph(md, bmain, scene, ob, &handle); + mti->updateDepsgraph( + md, + bmain, + scene, + ob, + reinterpret_cast< ::DepsNodeHandle* >(&handle)); } if (BKE_object_modifier_use_time(ob, md)) { TimeSourceKey time_src_key; add_relation(time_src_key, mod_key, DEPSREL_TYPE_TIME, "Time Source"); - + /* Hacky fix for T45633 (Animated modifiers aren't updated) * * This check works because BKE_object_modifier_use_time() tests @@ -1952,3 +1961,4 @@ bool DepsgraphRelationBuilder::needs_animdata_node(ID *id) return false; } +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_build.h b/source/blender/depsgraph/intern/builder/deg_builder_relations.h index 14b1b0f643c..c0bf82becda 100644 --- a/source/blender/depsgraph/intern/depsgraph_build.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.h @@ -24,12 +24,27 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/intern/depsgraph_build.h +/** \file blender/depsgraph/intern/builder/deg_builder_relations.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_BUILD_H__ -#define __DEPSGRAPH_BUILD_H__ +#pragma once + +#include <cstdio> + +#include "intern/depsgraph_types.h" + +#include "DNA_ID.h" + +#include "RNA_access.h" +#include "RNA_types.h" + +#include "BLI_utildefines.h" +#include "BLI_string.h" + +#include "intern/depsgraph_types.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_operation.h" struct Base; struct bGPdata; @@ -52,6 +67,8 @@ struct World; struct PropertyRNA; +namespace DEG { + struct Depsgraph; struct DepsNode; struct DepsNodeHandle; @@ -63,75 +80,6 @@ struct ComponentDepsNode; struct OperationDepsNode; struct RootPChanMap; -struct DepsgraphNodeBuilder { - DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph); - ~DepsgraphNodeBuilder(); - - RootDepsNode *add_root_node(); - IDDepsNode *add_id_node(ID *id); - TimeSourceDepsNode *add_time_source(ID *id); - - ComponentDepsNode *add_component_node(ID *id, eDepsNode_Type comp_type, const string &comp_name = ""); - - OperationDepsNode *add_operation_node(ComponentDepsNode *comp_node, eDepsOperation_Type optype, - DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = ""); - OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, eDepsOperation_Type optype, - DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = ""); - OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, eDepsOperation_Type optype, - DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = "") - { - return add_operation_node(id, comp_type, "", optype, op, opcode, description); - } - - bool has_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, - eDepsOperation_Code opcode, const string &description = ""); - - OperationDepsNode *find_operation_node(ID *id, - eDepsNode_Type comp_type, - const string &comp_name, - eDepsOperation_Code opcode, - const string &description = ""); - - OperationDepsNode *find_operation_node(ID *id, - eDepsNode_Type comp_type, - eDepsOperation_Code opcode, - const string &description = "") - { - return find_operation_node(id, comp_type, "", opcode, description); - } - - void build_scene(Main *bmain, Scene *scene); - SubgraphDepsNode *build_subgraph(Group *group); - void build_group(Scene *scene, Base *base, Group *group); - void build_object(Scene *scene, Base *base, Object *ob); - void build_object_transform(Scene *scene, Object *ob); - void build_object_constraints(Scene *scene, Object *ob); - void build_pose_constraints(Object *ob, bPoseChannel *pchan); - void build_rigidbody(Scene *scene); - void build_particles(Scene *scene, Object *ob); - void build_animdata(ID *id); - OperationDepsNode *build_driver(ID *id, FCurve *fcurve); - void build_ik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con); - void build_splineik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con); - void build_rig(Scene *scene, Object *ob); - void build_proxy_rig(Object *ob); - void build_shapekeys(Key *key); - void build_obdata_geom(Scene *scene, Object *ob); - void build_camera(Object *ob); - void build_lamp(Object *ob); - void build_nodetree(DepsNode *owner_node, bNodeTree *ntree); - void build_material(DepsNode *owner_node, Material *ma); - void build_texture(DepsNode *owner_node, Tex *tex); - void build_texture_stack(DepsNode *owner_node, MTex **texture_stack); - void build_world(World *world); - void build_compositor(Scene *scene); - void build_gpencil(bGPdata *gpd); - -private: - Main *m_bmain; - Depsgraph *m_graph; -}; - struct RootKey { RootKey() {} @@ -164,7 +112,7 @@ struct ComponentKey const char *idname = (id) ? id->name : "<None>"; char typebuf[5]; - sprintf(typebuf, "%d", type); + BLI_snprintf(typebuf, sizeof(typebuf), "%d", type); return string("ComponentKey(") + idname + ", " + typebuf + ", '" + name + "')"; } @@ -204,7 +152,7 @@ struct OperationKey string identifier() const { char typebuf[5]; - sprintf(typebuf, "%d", component_type); + BLI_snprintf(typebuf, sizeof(typebuf), "%d", component_type); return string("OperationKey(") + "t: " + typebuf + ", cn: '" + component_name + "', c: " + DEG_OPNAMES[opcode] + ", n: '" + name + "')"; } @@ -245,30 +193,45 @@ struct DepsgraphRelationBuilder DepsgraphRelationBuilder(Depsgraph *graph); template <typename KeyFrom, typename KeyTo> - void add_relation(const KeyFrom &key_from, const KeyTo &key_to, - eDepsRelation_Type type, const char *description); + void add_relation(const KeyFrom& key_from, + const KeyTo& key_to, + eDepsRelation_Type type, + const char *description); template <typename KeyTo> - void add_relation(const TimeSourceKey &key_from, const KeyTo &key_to, - eDepsRelation_Type type, const char *description); + void add_relation(const TimeSourceKey& key_from, + const KeyTo& key_to, + eDepsRelation_Type type, + const char *description); template <typename KeyType> - void add_node_handle_relation(const KeyType &key_from, const DepsNodeHandle *handle, - eDepsRelation_Type type, const char *description); + void add_node_handle_relation(const KeyType& key_from, + const DepsNodeHandle *handle, + eDepsRelation_Type type, + const char *description); void build_scene(Main *bmain, Scene *scene); void build_group(Main *bmain, Scene *scene, Object *object, Group *group); void build_object(Main *bmain, Scene *scene, Object *ob); void build_object_parent(Object *ob); - void build_constraints(Scene *scene, ID *id, eDepsNode_Type component_type, const char *component_subdata, - ListBase *constraints, RootPChanMap *root_map); + void build_constraints(Scene *scene, ID *id, + eDepsNode_Type component_type, + const char *component_subdata, + ListBase *constraints, + RootPChanMap *root_map); void build_animdata(ID *id); void build_driver(ID *id, FCurve *fcurve); void build_world(World *world); void build_rigidbody(Scene *scene); void build_particles(Scene *scene, Object *ob); - void build_ik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map); - void build_splineik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map); + void build_ik_pose(Object *ob, + bPoseChannel *pchan, + bConstraint *con, + RootPChanMap *root_map); + void build_splineik_pose(Object *ob, + bPoseChannel *pchan, + bConstraint *con, + RootPChanMap *root_map); void build_rig(Scene *scene, Object *ob); void build_proxy_rig(Object *ob); void build_shapekeys(ID *obdata, Key *key); @@ -293,12 +256,17 @@ protected: DepsNode *find_node(const RNAPathKey &key) const; OperationDepsNode *has_node(const OperationKey &key) const; - void add_time_relation(TimeSourceDepsNode *timesrc, DepsNode *node_to, const char *description); - void add_operation_relation(OperationDepsNode *node_from, OperationDepsNode *node_to, - eDepsRelation_Type type, const char *description); + void add_time_relation(TimeSourceDepsNode *timesrc, + DepsNode *node_to, + const char *description); + void add_operation_relation(OperationDepsNode *node_from, + OperationDepsNode *node_to, + eDepsRelation_Type type, + const char *description); template <typename KeyType> - DepsNodeHandle create_node_handle(const KeyType &key, const string &default_name = ""); + DepsNodeHandle create_node_handle(const KeyType& key, + const string& default_name = ""); bool needs_animdata_node(ID *id); @@ -323,9 +291,6 @@ struct DepsNodeHandle /* Utilities for Builders ----------------------------------------------------- */ -/* Get unique identifier for FCurves and Drivers */ -string deg_fcurve_id_name(const FCurve *fcu); - template <typename KeyType> OperationDepsNode *DepsgraphRelationBuilder::find_operation_node(const KeyType& key) { DepsNode *node = find_node(key); @@ -386,10 +351,11 @@ void DepsgraphRelationBuilder::add_relation(const TimeSourceKey &key_from, } template <typename KeyType> -void DepsgraphRelationBuilder::add_node_handle_relation(const KeyType &key_from, - const DepsNodeHandle *handle, - eDepsRelation_Type type, - const char *description) +void DepsgraphRelationBuilder::add_node_handle_relation( + const KeyType &key_from, + const DepsNodeHandle *handle, + eDepsRelation_Type type, + const char *description) { DepsNode *node_from = find_node(key_from); OperationDepsNode *op_from = node_from ? node_from->get_exit_operation() : NULL; @@ -408,10 +374,11 @@ void DepsgraphRelationBuilder::add_node_handle_relation(const KeyType &key_from, } template <typename KeyType> -DepsNodeHandle DepsgraphRelationBuilder::create_node_handle(const KeyType &key, - const string &default_name) +DepsNodeHandle DepsgraphRelationBuilder::create_node_handle( + const KeyType &key, + const string &default_name) { return DepsNodeHandle(this, find_node(key), default_name); } -#endif /* __DEPSGRAPH_BUILD_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.cc b/source/blender/depsgraph/intern/builder/deg_builder_transitive.cc index 98192a9540f..0322ef7fa1d 100644 --- a/source/blender/depsgraph/util/depsgraph_util_transitive.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_transitive.cc @@ -24,26 +24,25 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_transitive.cc +/** \file blender/depsgraph/intern/builder/deg_builder_transitive.cc * \ingroup depsgraph */ +#include "intern/builder/deg_builder_transitive.h" + extern "C" { #include "MEM_guardedalloc.h" +} -#include "BLI_utildefines.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" -#include "DNA_ID.h" +#include "intern/depsgraph.h" -#include "RNA_access.h" -#include "RNA_types.h" -} +#include "util/deg_util_foreach.h" -#include "depsgraph_util_transitive.h" -#include "depsgraph.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" +namespace DEG { /* -------------------------------------------------- */ @@ -67,16 +66,11 @@ enum { static void deg_graph_tag_paths_recursive(DepsNode *node) { - if (node->done & OP_VISITED) + if (node->done & OP_VISITED) { return; + } node->done |= OP_VISITED; - - for (OperationDepsNode::Relations::const_iterator it = node->inlinks.begin(); - it != node->inlinks.end(); - ++it) - { - DepsRelation *rel = *it; - + foreach (DepsRelation *rel, node->inlinks) { deg_graph_tag_paths_recursive(rel->from); /* Do this only in inlinks loop, so the target node does not get * flagged. @@ -87,18 +81,9 @@ static void deg_graph_tag_paths_recursive(DepsNode *node) void deg_graph_transitive_reduction(Depsgraph *graph) { - for (Depsgraph::OperationNodes::const_iterator it_target = graph->operations.begin(); - it_target != graph->operations.end(); - ++it_target) - { - OperationDepsNode *target = *it_target; - + foreach (OperationDepsNode *target, graph->operations) { /* Clear tags. */ - for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); - it != graph->operations.end(); - ++it) - { - OperationDepsNode *node = *it; + foreach (OperationDepsNode *node, graph->operations) { node->done = 0; } @@ -107,19 +92,14 @@ void deg_graph_transitive_reduction(Depsgraph *graph) * flagged. */ target->done |= OP_VISITED; - for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin(); - it != target->inlinks.end(); - ++it) - { - DepsRelation *rel = *it; - + foreach (DepsRelation *rel, target->inlinks) { deg_graph_tag_paths_recursive(rel->from); } - /* Eemove redundant paths to the target. */ + /* Remove redundant paths to the target. */ for (DepsNode::Relations::const_iterator it_rel = target->inlinks.begin(); it_rel != target->inlinks.end(); - ) + ) { DepsRelation *rel = *it_rel; /* Increment in advance, so we can safely remove the relation. */ @@ -137,3 +117,5 @@ void deg_graph_transitive_reduction(Depsgraph *graph) } } } + +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.h b/source/blender/depsgraph/intern/builder/deg_builder_transitive.h index a80a1d783d7..be9d7c3ca9c 100644 --- a/source/blender/depsgraph/util/depsgraph_util_transitive.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_transitive.h @@ -24,15 +24,17 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_transitive.h +/** \file blender/depsgraph/intern/builder/deg_builder_transitive.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__ -#define __DEPSGRAPH_UTIL_TRANSITIVE_H__ +#pragma once + +namespace DEG { struct Depsgraph; +/* Performs a transitive reduction to remove redundant relations. */ void deg_graph_transitive_reduction(Depsgraph *graph); -#endif /* __DEPSGRAPH_UTIL_TRANSITIVE_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/debug/deg_debug_graphviz.cc b/source/blender/depsgraph/intern/debug/deg_debug_graphviz.cc new file mode 100644 index 00000000000..6e932d37f37 --- /dev/null +++ b/source/blender/depsgraph/intern/debug/deg_debug_graphviz.cc @@ -0,0 +1,587 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/debug/deg_debug_graphviz.cc + * \ingroup depsgraph + * + * Implementation of tools for debugging the depsgraph + */ + +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + +extern "C" { +#include "DNA_listBase.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_debug.h" +} /* extern "C" */ + +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" + +/* ****************** */ +/* Graphviz Debugging */ + +namespace DEG { + +#define NL "\r\n" + +/* Only one should be enabled, defines whether graphviz nodes + * get colored by individual types or classes. + */ +#define COLOR_SCHEME_NODE_CLASS 1 +//#define COLOR_SCHEME_NODE_TYPE 2 + +static const char *deg_debug_graphviz_fontname = "helvetica"; +static float deg_debug_graphviz_graph_label_size = 20.0f; +static float deg_debug_graphviz_node_label_size = 14.0f; +static const int deg_debug_max_colors = 12; +#ifdef COLOR_SCHEME_NODE_TYPE +static const char *deg_debug_colors[] = { + "#a6cee3", "#1f78b4", "#b2df8a", + "#33a02c", "#fb9a99", "#e31a1c", + "#fdbf6f", "#ff7f00", "#cab2d6", + "#6a3d9a", "#ffff99", "#b15928", +}; +#endif +static const char *deg_debug_colors_light[] = { + "#8dd3c7", "#ffffb3", "#bebada", + "#fb8072", "#80b1d3", "#fdb462", + "#b3de69", "#fccde5", "#d9d9d9", + "#bc80bd", "#ccebc5", "#ffed6f", +}; + +#ifdef COLOR_SCHEME_NODE_TYPE +static const int deg_debug_node_type_color_map[][2] = { + {DEPSNODE_TYPE_ROOT, 0}, + {DEPSNODE_TYPE_TIMESOURCE, 1}, + {DEPSNODE_TYPE_ID_REF, 2}, + {DEPSNODE_TYPE_SUBGRAPH, 3}, + + /* Outer Types */ + {DEPSNODE_TYPE_PARAMETERS, 4}, + {DEPSNODE_TYPE_PROXY, 5}, + {DEPSNODE_TYPE_ANIMATION, 6}, + {DEPSNODE_TYPE_TRANSFORM, 7}, + {DEPSNODE_TYPE_GEOMETRY, 8}, + {DEPSNODE_TYPE_SEQUENCER, 9}, + {DEPSNODE_TYPE_SHADING, 10}, + {-1, 0} +}; +#endif + +static int deg_debug_node_color_index(const DepsNode *node) +{ +#ifdef COLOR_SCHEME_NODE_CLASS + /* Some special types. */ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + return 5; + case DEPSNODE_TYPE_OPERATION: + { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->is_noop()) + return 8; + break; + } + + default: + break; + } + /* Do others based on class. */ + switch (node->tclass) { + case DEPSNODE_CLASS_OPERATION: + return 4; + case DEPSNODE_CLASS_COMPONENT: + return 1; + default: + return 9; + } +#endif + +#ifdef COLOR_SCHEME_NODE_TYPE + const int (*pair)[2]; + for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { + if ((*pair)[0] == node->type) { + return (*pair)[1]; + } + } + return -1; +#endif +} + +struct DebugContext { + FILE *file; + bool show_tags; + bool show_eval_priority; +}; + +static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) ATTR_PRINTF_FORMAT(2, 3); +static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) +{ + va_list args; + va_start(args, fmt); + vfprintf(ctx.file, fmt, args); + va_end(args); +} + +static void deg_debug_graphviz_legend_color(const DebugContext &ctx, + const char *name, + const char *color) +{ + deg_debug_fprintf(ctx, "<TR>"); + deg_debug_fprintf(ctx, "<TD>%s</TD>", name); + deg_debug_fprintf(ctx, "<TD BGCOLOR=\"%s\"></TD>", color); + deg_debug_fprintf(ctx, "</TR>" NL); +} + +static void deg_debug_graphviz_legend(const DebugContext &ctx) +{ + deg_debug_fprintf(ctx, "{" NL); + deg_debug_fprintf(ctx, "rank = sink;" NL); + deg_debug_fprintf(ctx, "Legend [shape=none, margin=0, label=<" NL); + deg_debug_fprintf(ctx, " <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">" NL); + deg_debug_fprintf(ctx, "<TR><TD COLSPAN=\"2\"><B>Legend</B></TD></TR>" NL); + +#ifdef COLOR_SCHEME_NODE_CLASS + const char **colors = deg_debug_colors_light; + deg_debug_graphviz_legend_color(ctx, "Operation", colors[4]); + deg_debug_graphviz_legend_color(ctx, "Component", colors[1]); + deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]); + deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]); +#endif + +#ifdef COLOR_SCHEME_NODE_TYPE + const int (*pair)[2]; + for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { + DepsNodeFactory *nti = DEG_get_node_factory((eDepsNode_Type)(*pair)[0]); + deg_debug_graphviz_legend_color(ctx, + nti->tname().c_str(), + deg_debug_colors_light[(*pair)[1] % deg_debug_max_colors]); + } +#endif + + deg_debug_fprintf(ctx, "</TABLE>" NL); + deg_debug_fprintf(ctx, ">" NL); + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, "}" NL); +} + +static void deg_debug_graphviz_node_color(const DebugContext &ctx, + const DepsNode *node) +{ + const char *color_default = "black"; + const char *color_modified = "orangered4"; + const char *color_update = "dodgerblue3"; + const char *color = color_default; + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { + color = color_modified; + } + else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + color = color_update; + } + } + } + deg_debug_fprintf(ctx, "\"%s\"", color); +} + +static void deg_debug_graphviz_node_penwidth(const DebugContext &ctx, + const DepsNode *node) +{ + float penwidth_default = 1.0f; + float penwidth_modified = 4.0f; + float penwidth_update = 4.0f; + float penwidth = penwidth_default; + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { + penwidth = penwidth_modified; + } + else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + penwidth = penwidth_update; + } + } + } + deg_debug_fprintf(ctx, "\"%f\"", penwidth); +} + +static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx, + const DepsNode *node) +{ + const char *defaultcolor = "gainsboro"; + int color_index = deg_debug_node_color_index(node); + const char *fillcolor = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors]; + deg_debug_fprintf(ctx, "\"%s\"", fillcolor); +} + +static void deg_debug_graphviz_relation_color(const DebugContext &ctx, + const DepsRelation *rel) +{ + const char *color_default = "black"; + const char *color_error = "red4"; + const char *color = color_default; + if (rel->flag & DEPSREL_FLAG_CYCLIC) { + color = color_error; + } + deg_debug_fprintf(ctx, "%s", color); +} + +static void deg_debug_graphviz_node_style(const DebugContext &ctx, const DepsNode *node) +{ + const char *base_style = "filled"; /* default style */ + if (ctx.show_tags) { + if (node->tclass == DEPSNODE_CLASS_OPERATION) { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->flag & (DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE)) { + base_style = "striped"; + } + } + } + switch (node->tclass) { + case DEPSNODE_CLASS_GENERIC: + deg_debug_fprintf(ctx, "\"%s\"", base_style); + break; + case DEPSNODE_CLASS_COMPONENT: + deg_debug_fprintf(ctx, "\"%s\"", base_style); + break; + case DEPSNODE_CLASS_OPERATION: + deg_debug_fprintf(ctx, "\"%s,rounded\"", base_style); + break; + } +} + +static void deg_debug_graphviz_node_single(const DebugContext &ctx, + const DepsNode *node) +{ + const char *shape = "box"; + string name = node->identifier(); + float priority = -1.0f; + if (node->type == DEPSNODE_TYPE_ID_REF) { + IDDepsNode *id_node = (IDDepsNode *)node; + char buf[256]; + BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); + name += buf; + } + if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION) { + priority = ((OperationDepsNode *)node)->eval_priority; + } + deg_debug_fprintf(ctx, "// %s\n", name.c_str()); + deg_debug_fprintf(ctx, "\"node_%p\"", node); + deg_debug_fprintf(ctx, "["); +// deg_debug_fprintf(ctx, "label=<<B>%s</B>>", name); + if (priority >= 0.0f) { + deg_debug_fprintf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>", + name.c_str(), + priority); + } + else { + deg_debug_fprintf(ctx, "label=<%s>", name.c_str()); + } + deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size); + deg_debug_fprintf(ctx, ",shape=%s", shape); + deg_debug_fprintf(ctx, ",style="); deg_debug_graphviz_node_style(ctx, node); + deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_node_color(ctx, node); + deg_debug_fprintf(ctx, ",fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); + deg_debug_fprintf(ctx, ",penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_node_cluster_begin(const DebugContext &ctx, + const DepsNode *node) +{ + string name = node->identifier().c_str(); + if (node->type == DEPSNODE_TYPE_ID_REF) { + IDDepsNode *id_node = (IDDepsNode *)node; + char buf[256]; + BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); + name += buf; + } + deg_debug_fprintf(ctx, "// %s\n", name.c_str()); + deg_debug_fprintf(ctx, "subgraph \"cluster_%p\" {" NL, node); +// deg_debug_fprintf(ctx, "label=<<B>%s</B>>;" NL, name); + deg_debug_fprintf(ctx, "label=<%s>;" NL, name.c_str()); + deg_debug_fprintf(ctx, "fontname=\"%s\";" NL, deg_debug_graphviz_fontname); + deg_debug_fprintf(ctx, "fontsize=%f;" NL, deg_debug_graphviz_node_label_size); + deg_debug_fprintf(ctx, "margin=\"%d\";" NL, 16); + deg_debug_fprintf(ctx, "style="); deg_debug_graphviz_node_style(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "color="); deg_debug_graphviz_node_color(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); deg_debug_fprintf(ctx, ";" NL); + deg_debug_fprintf(ctx, "penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); deg_debug_fprintf(ctx, ";" NL); + /* dummy node, so we can add edges between clusters */ + deg_debug_fprintf(ctx, "\"node_%p\"", node); + deg_debug_fprintf(ctx, "["); + deg_debug_fprintf(ctx, "shape=%s", "point"); + deg_debug_fprintf(ctx, ",style=%s", "invis"); + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_node_cluster_end(const DebugContext &ctx) +{ + deg_debug_fprintf(ctx, "}" NL); + deg_debug_fprintf(ctx, NL); +} + +static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, + const Depsgraph *graph); +static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, + const Depsgraph *graph); + +static void deg_debug_graphviz_node(const DebugContext &ctx, + const DepsNode *node) +{ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + { + const IDDepsNode *id_node = (const IDDepsNode *)node; + if (BLI_ghash_size(id_node->components) == 0) { + deg_debug_graphviz_node_single(ctx, node); + } + else { + deg_debug_graphviz_node_cluster_begin(ctx, node); + GHASH_FOREACH_BEGIN(const ComponentDepsNode *, comp, id_node->components) + { + deg_debug_graphviz_node(ctx, comp); + } + GHASH_FOREACH_END(); + deg_debug_graphviz_node_cluster_end(ctx); + } + break; + } + case DEPSNODE_TYPE_SUBGRAPH: + { + SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; + if (sub_node->graph) { + deg_debug_graphviz_node_cluster_begin(ctx, node); + deg_debug_graphviz_graph_nodes(ctx, sub_node->graph); + deg_debug_graphviz_node_cluster_end(ctx); + } + else { + deg_debug_graphviz_node_single(ctx, node); + } + break; + } + case DEPSNODE_TYPE_PARAMETERS: + case DEPSNODE_TYPE_ANIMATION: + case DEPSNODE_TYPE_TRANSFORM: + case DEPSNODE_TYPE_PROXY: + case DEPSNODE_TYPE_GEOMETRY: + case DEPSNODE_TYPE_SEQUENCER: + case DEPSNODE_TYPE_EVAL_POSE: + case DEPSNODE_TYPE_BONE: + case DEPSNODE_TYPE_SHADING: + case DEPSNODE_TYPE_EVAL_PARTICLES: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + if (!comp_node->operations.empty()) { + foreach (DepsNode *op_node, comp_node->operations) { + deg_debug_graphviz_node(ctx, op_node); + } + deg_debug_graphviz_node_cluster_end(ctx); + } + else { + deg_debug_graphviz_node_single(ctx, node); + } + break; + } + default: + deg_debug_graphviz_node_single(ctx, node); + break; + } +} + +static bool deg_debug_graphviz_is_cluster(const DepsNode *node) +{ + switch (node->type) { + case DEPSNODE_TYPE_ID_REF: + { + const IDDepsNode *id_node = (const IDDepsNode *)node; + return BLI_ghash_size(id_node->components) > 0; + } + case DEPSNODE_TYPE_SUBGRAPH: + { + SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; + return sub_node->graph != NULL; + } + case DEPSNODE_TYPE_PARAMETERS: + case DEPSNODE_TYPE_ANIMATION: + case DEPSNODE_TYPE_TRANSFORM: + case DEPSNODE_TYPE_PROXY: + case DEPSNODE_TYPE_GEOMETRY: + case DEPSNODE_TYPE_SEQUENCER: + case DEPSNODE_TYPE_EVAL_POSE: + case DEPSNODE_TYPE_BONE: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + return !comp_node->operations.empty(); + } + default: + return false; + } +} + +static bool deg_debug_graphviz_is_owner(const DepsNode *node, + const DepsNode *other) +{ + switch (node->tclass) { + case DEPSNODE_CLASS_COMPONENT: + { + ComponentDepsNode *comp_node = (ComponentDepsNode *)node; + if (comp_node->owner == other) + return true; + break; + } + case DEPSNODE_CLASS_OPERATION: + { + OperationDepsNode *op_node = (OperationDepsNode *)node; + if (op_node->owner == other) + return true; + else if (op_node->owner->owner == other) + return true; + break; + } + default: break; + } + return false; +} + +static void deg_debug_graphviz_node_relations(const DebugContext &ctx, + const DepsNode *node) +{ + foreach (DepsRelation *rel, node->inlinks) { + float penwidth = 2.0f; + + const DepsNode *tail = rel->to; /* same as node */ + const DepsNode *head = rel->from; + deg_debug_fprintf(ctx, "// %s -> %s\n", + head->identifier().c_str(), + tail->identifier().c_str()); + deg_debug_fprintf(ctx, "\"node_%p\"", head); + deg_debug_fprintf(ctx, " -> "); + deg_debug_fprintf(ctx, "\"node_%p\"", tail); + + deg_debug_fprintf(ctx, "["); + /* Note: without label an id seem necessary to avoid bugs in graphviz/dot */ + deg_debug_fprintf(ctx, "id=\"%s\"", rel->name); + deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_relation_color(ctx, rel); + deg_debug_fprintf(ctx, ",penwidth=\"%f\"", penwidth); + /* NOTE: edge from node to own cluster is not possible and gives graphviz + * warning, avoid this here by just linking directly to the invisible + * placeholder node + */ + if (deg_debug_graphviz_is_cluster(tail) && !deg_debug_graphviz_is_owner(head, tail)) { + deg_debug_fprintf(ctx, ",ltail=\"cluster_%p\"", tail); + } + if (deg_debug_graphviz_is_cluster(head) && !deg_debug_graphviz_is_owner(tail, head)) { + deg_debug_fprintf(ctx, ",lhead=\"cluster_%p\"", head); + } + deg_debug_fprintf(ctx, "];" NL); + deg_debug_fprintf(ctx, NL); + } +} + +static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, + const Depsgraph *graph) +{ + if (graph->root_node) { + deg_debug_graphviz_node(ctx, graph->root_node); + } + GHASH_FOREACH_BEGIN (DepsNode *, node, graph->id_hash) + { + deg_debug_graphviz_node(ctx, node); + } + GHASH_FOREACH_END(); + TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + if (time_source != NULL) { + deg_debug_graphviz_node(ctx, time_source); + } +} + +static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, + const Depsgraph *graph) +{ + GHASH_FOREACH_BEGIN(IDDepsNode *, id_node, graph->id_hash) + { + GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components) + { + foreach (OperationDepsNode *op_node, comp_node->operations) { + deg_debug_graphviz_node_relations(ctx, op_node); + } + } + GHASH_FOREACH_END(); + } + GHASH_FOREACH_END(); + + TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + if (time_source != NULL) { + deg_debug_graphviz_node_relations(ctx, time_source); + } +} + +} // namespace DEG + +void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_eval) +{ + if (!graph) { + return; + } + + const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph); + + DEG::DebugContext ctx; + ctx.file = f; + ctx.show_tags = show_eval; + ctx.show_eval_priority = show_eval; + + DEG::deg_debug_fprintf(ctx, "digraph depgraph {" NL); + DEG::deg_debug_fprintf(ctx, "rankdir=LR;" NL); + DEG::deg_debug_fprintf(ctx, "graph ["); + DEG::deg_debug_fprintf(ctx, "compound=true"); + DEG::deg_debug_fprintf(ctx, ",labelloc=\"t\""); + DEG::deg_debug_fprintf(ctx, ",fontsize=%f", DEG::deg_debug_graphviz_graph_label_size); + DEG::deg_debug_fprintf(ctx, ",fontname=\"%s\"", DEG::deg_debug_graphviz_fontname); + DEG::deg_debug_fprintf(ctx, ",label=\"%s\"", label); + DEG::deg_debug_fprintf(ctx, ",splines=ortho"); + DEG::deg_debug_fprintf(ctx, ",overlap=scalexy"); // XXX: only when using neato + DEG::deg_debug_fprintf(ctx, "];" NL); + + DEG::deg_debug_graphviz_graph_nodes(ctx, deg_graph); + DEG::deg_debug_graphviz_graph_relations(ctx, deg_graph); + + DEG::deg_debug_graphviz_legend(ctx); + + DEG::deg_debug_fprintf(ctx, "}" NL); +} + +#undef NL diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc index 87dbb2333a6..2b7c63767ab 100644 --- a/source/blender/depsgraph/intern/depsgraph.cc +++ b/source/blender/depsgraph/intern/depsgraph.cc @@ -30,10 +30,14 @@ * Core routines for how the Depsgraph works. */ +#include "intern/depsgraph.h" /* own include */ + #include <string.h> #include "MEM_guardedalloc.h" +#include "BLI_utildefines.h" +#include "BLI_ghash.h" #include "BLI_listbase.h" extern "C" { @@ -50,12 +54,15 @@ extern "C" { } #include "DEG_depsgraph.h" -#include "depsgraph.h" /* own include */ -#include "depsnode.h" -#include "depsnode_operation.h" -#include "depsnode_component.h" -#include "depsgraph_intern.h" -#include "depsgraph_util_foreach.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" + +namespace DEG { static DEG_EditorUpdateIDCb deg_editor_update_id_cb = NULL; static DEG_EditorUpdateSceneCb deg_editor_update_scene_cb = NULL; @@ -67,6 +74,9 @@ Depsgraph::Depsgraph() layers(0) { BLI_spin_init(&lock); + id_hash = BLI_ghash_ptr_new("Depsgraph id hash"); + subgraphs = BLI_gset_ptr_new("Depsgraph subgraphs"); + entry_tags = BLI_gset_ptr_new("Depsgraph entry_tags"); } Depsgraph::~Depsgraph() @@ -74,6 +84,9 @@ Depsgraph::~Depsgraph() /* Free root node - it won't have been freed yet... */ clear_id_nodes(); clear_subgraph_nodes(); + BLI_ghash_free(id_hash, NULL, NULL); + BLI_gset_free(subgraphs, NULL); + BLI_gset_free(entry_tags, NULL); if (this->root_node != NULL) { OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode); } @@ -236,10 +249,16 @@ DepsNode *Depsgraph::find_node_from_pointer(const PointerRNA *ptr, /* Node Management ---------------------------- */ +static void id_node_deleter(void *value) +{ + IDDepsNode *id_node = reinterpret_cast<IDDepsNode *>(value); + OBJECT_GUARDED_DELETE(id_node, IDDepsNode); +} + RootDepsNode *Depsgraph::add_root_node() { if (!root_node) { - DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ROOT); + DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_ROOT); root_node = (RootDepsNode *)factory->create_node(NULL, "", "Root (Scene)"); } return root_node; @@ -268,12 +287,12 @@ TimeSourceDepsNode *Depsgraph::find_time_source(const ID *id) const SubgraphDepsNode *Depsgraph::add_subgraph_node(const ID *id) { - DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_SUBGRAPH); + DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_SUBGRAPH); SubgraphDepsNode *subgraph_node = (SubgraphDepsNode *)factory->create_node(id, "", id->name + 2); /* Add to subnodes list. */ - this->subgraphs.insert(subgraph_node); + BLI_gset_insert(subgraphs, subgraph_node); /* if there's an ID associated, add to ID-nodes lookup too */ if (id) { @@ -290,33 +309,34 @@ SubgraphDepsNode *Depsgraph::add_subgraph_node(const ID *id) void Depsgraph::remove_subgraph_node(SubgraphDepsNode *subgraph_node) { - subgraphs.erase(subgraph_node); + BLI_gset_remove(subgraphs, subgraph_node, NULL); OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode); } void Depsgraph::clear_subgraph_nodes() { - foreach (SubgraphDepsNode *subgraph_node, subgraphs) { + GSET_FOREACH_BEGIN(SubgraphDepsNode *, subgraph_node, subgraphs) + { OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode); } - subgraphs.clear(); + GSET_FOREACH_END(); + BLI_gset_clear(subgraphs, NULL); } IDDepsNode *Depsgraph::find_id_node(const ID *id) const { - IDNodeMap::const_iterator it = this->id_hash.find(id); - return it != this->id_hash.end() ? it->second : NULL; + return reinterpret_cast<IDDepsNode *>(BLI_ghash_lookup(id_hash, id)); } IDDepsNode *Depsgraph::add_id_node(ID *id, const string &name) { IDDepsNode *id_node = find_id_node(id); if (!id_node) { - DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ID_REF); + DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_ID_REF); id_node = (IDDepsNode *)factory->create_node(id, "", name); id->tag |= LIB_TAG_DOIT; /* register */ - this->id_hash[id] = id_node; + BLI_ghash_insert(id_hash, id, id_node); } return id_node; } @@ -326,21 +346,14 @@ void Depsgraph::remove_id_node(const ID *id) IDDepsNode *id_node = find_id_node(id); if (id_node) { /* unregister */ - this->id_hash.erase(id); + BLI_ghash_remove(id_hash, id, NULL, NULL); OBJECT_GUARDED_DELETE(id_node, IDDepsNode); } } void Depsgraph::clear_id_nodes() { - for (IDNodeMap::const_iterator it = id_hash.begin(); - it != id_hash.end(); - ++it) - { - IDDepsNode *id_node = it->second; - OBJECT_GUARDED_DELETE(id_node, IDDepsNode); - } - id_hash.clear(); + BLI_ghash_clear(id_hash, NULL, id_node_deleter); } /* Add new relationship between two nodes. */ @@ -446,33 +459,52 @@ void Depsgraph::add_entry_tag(OperationDepsNode *node) /* Add to graph-level set of directly modified nodes to start searching from. * NOTE: this is necessary since we have several thousand nodes to play with... */ - this->entry_tags.insert(node); + BLI_gset_insert(entry_tags, node); } void Depsgraph::clear_all_nodes() { clear_id_nodes(); clear_subgraph_nodes(); - id_hash.clear(); + BLI_ghash_clear(id_hash, NULL, NULL); if (this->root_node) { OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode); root_node = NULL; } } +void deg_editors_id_update(Main *bmain, ID *id) +{ + if (deg_editor_update_id_cb != NULL) { + deg_editor_update_id_cb(bmain, id); + } +} + +void deg_editors_scene_update(Main *bmain, Scene *scene, bool updated) +{ + if (deg_editor_update_scene_cb != NULL) { + deg_editor_update_scene_cb(bmain, scene, updated); + } +} + +} // namespace DEG + /* **************** */ /* Public Graph API */ /* Initialize a new Depsgraph */ Depsgraph *DEG_graph_new() { - return OBJECT_GUARDED_NEW(Depsgraph); + DEG::Depsgraph *deg_depsgraph = OBJECT_GUARDED_NEW(DEG::Depsgraph); + return reinterpret_cast<Depsgraph *>(deg_depsgraph); } /* Free graph's contents and graph itself */ void DEG_graph_free(Depsgraph *graph) { - OBJECT_GUARDED_DELETE(graph, Depsgraph); + using DEG::Depsgraph; + DEG::Depsgraph *deg_depsgraph = reinterpret_cast<DEG::Depsgraph *>(graph); + OBJECT_GUARDED_DELETE(deg_depsgraph, Depsgraph); } /* Set callbacks which are being called when depsgraph changes. */ @@ -480,28 +512,14 @@ void DEG_editors_set_update_cb(DEG_EditorUpdateIDCb id_func, DEG_EditorUpdateSceneCb scene_func, DEG_EditorUpdateScenePreCb scene_pre_func) { - deg_editor_update_id_cb = id_func; - deg_editor_update_scene_cb = scene_func; - deg_editor_update_scene_pre_cb = scene_pre_func; + DEG::deg_editor_update_id_cb = id_func; + DEG::deg_editor_update_scene_cb = scene_func; + DEG::deg_editor_update_scene_pre_cb = scene_pre_func; } void DEG_editors_update_pre(Main *bmain, Scene *scene, bool time) { - if (deg_editor_update_scene_pre_cb != NULL) { - deg_editor_update_scene_pre_cb(bmain, scene, time); - } -} - -void deg_editors_id_update(Main *bmain, ID *id) -{ - if (deg_editor_update_id_cb != NULL) { - deg_editor_update_id_cb(bmain, id); - } -} - -void deg_editors_scene_update(Main *bmain, Scene *scene, bool updated) -{ - if (deg_editor_update_scene_cb != NULL) { - deg_editor_update_scene_cb(bmain, scene, updated); + if (DEG::deg_editor_update_scene_pre_cb != NULL) { + DEG::deg_editor_update_scene_pre_cb(bmain, scene, time); } } diff --git a/source/blender/depsgraph/intern/depsgraph.h b/source/blender/depsgraph/intern/depsgraph.h index 9533fbd10d5..213bb304d73 100644 --- a/source/blender/depsgraph/intern/depsgraph.h +++ b/source/blender/depsgraph/intern/depsgraph.h @@ -34,19 +34,20 @@ * in the graph. */ -#ifndef __DEPSGRAPH_H__ -#define __DEPSGRAPH_H__ +#pragma once #include "BLI_threads.h" /* for SpinLock */ -#include "depsgraph_types.h" - -#include "depsgraph_util_map.h" -#include "depsgraph_util_set.h" +#include "intern/depsgraph_types.h" +struct ID; +struct GHash; +struct GSet; struct PointerRNA; struct PropertyRNA; +namespace DEG { + struct DepsNode; struct RootDepsNode; struct TimeSourceDepsNode; @@ -94,9 +95,6 @@ struct DepsRelation { /* Dependency Graph object */ struct Depsgraph { - typedef unordered_map<const ID *, IDDepsNode *> IDNodeMap; - typedef unordered_set<SubgraphDepsNode *> Subgraphs; - typedef unordered_set<OperationDepsNode *> EntryTags; typedef vector<OperationDepsNode *> OperationNodes; Depsgraph(); @@ -163,13 +161,13 @@ struct Depsgraph { /* <ID : IDDepsNode> mapping from ID blocks to nodes representing these blocks * (for quick lookups). */ - IDNodeMap id_hash; + GHash *id_hash; /* "root" node - the one where all evaluation enters from. */ RootDepsNode *root_node; /* Subgraphs referenced in tree. */ - Subgraphs subgraphs; + GSet *subgraphs; /* Indicates whether relations needs to be updated. */ bool need_update; @@ -177,7 +175,7 @@ struct Depsgraph { /* Quick-Access Temp Data ............. */ /* Nodes which have been tagged as "directly modified". */ - EntryTags entry_tags; + GSet *entry_tags; /* Convenience Data ................... */ @@ -198,27 +196,4 @@ struct Depsgraph { // XXX: additional stuff like eval contexts, mempools for allocating nodes from, etc. }; -/** - * Helper macros for iterating over set of relationship links - * incident on each node. - * - * \note it is safe to perform removal operations here... - * - * relations_set[in]: (DepsNode::Relations) set of relationships (in/out links) - * relation[out]: (DepsRelation *) identifier where DepsRelation that we're - * currently accessing comes up - */ -#define DEPSNODE_RELATIONS_ITER_BEGIN(relations_set_, relation_) \ - { \ - OperationDepsNode::Relations::const_iterator __rel_iter = relations_set_.begin(); \ - while (__rel_iter != relations_set_.end()) { \ - DepsRelation *relation_ = *__rel_iter; \ - ++__rel_iter; \ - - /* ... code for iterator body can be written here ... */ - -#define DEPSNODE_RELATIONS_ITER_END \ - } \ - } ((void)0) - -#endif /* __DEPSGRAPH_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc index fed1433840e..b1271c39851 100644 --- a/source/blender/depsgraph/intern/depsgraph_build.cc +++ b/source/blender/depsgraph/intern/depsgraph_build.cc @@ -30,138 +30,128 @@ * Methods for constructing depsgraph. */ -#include <stack> - #include "MEM_guardedalloc.h" extern "C" { -#include "BLI_blenlib.h" -#include "BLI_string.h" -#include "BLI_utildefines.h" - -#include "DNA_action_types.h" -#include "DNA_anim_types.h" -#include "DNA_armature_types.h" -#include "DNA_camera_types.h" -#include "DNA_constraint_types.h" -#include "DNA_curve_types.h" -#include "DNA_effect_types.h" -#include "DNA_group_types.h" -#include "DNA_key_types.h" -#include "DNA_lamp_types.h" -#include "DNA_material_types.h" -#include "DNA_mesh_types.h" -#include "DNA_meta_types.h" -#include "DNA_node_types.h" -#include "DNA_particle_types.h" #include "DNA_object_types.h" -#include "DNA_rigidbody_types.h" #include "DNA_scene_types.h" -#include "DNA_texture_types.h" -#include "DNA_world_types.h" - -#include "BKE_action.h" -#include "BKE_armature.h" -#include "BKE_animsys.h" -#include "BKE_constraint.h" -#include "BKE_curve.h" -#include "BKE_effect.h" -#include "BKE_fcurve.h" -#include "BKE_group.h" -#include "BKE_key.h" -#include "BKE_library.h" + +#include "BLI_utildefines.h" +#include "BLI_ghash.h" + #include "BKE_main.h" -#include "BKE_material.h" -#include "BKE_mball.h" -#include "BKE_modifier.h" -#include "BKE_node.h" -#include "BKE_object.h" -#include "BKE_particle.h" -#include "BKE_rigidbody.h" -#include "BKE_sound.h" -#include "BKE_texture.h" -#include "BKE_tracking.h" -#include "BKE_world.h" #include "DEG_depsgraph.h" #include "DEG_depsgraph_debug.h" #include "DEG_depsgraph_build.h" -#include "RNA_access.h" -#include "RNA_types.h" } /* extern "C" */ -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsgraph_debug.h" -#include "depsnode_operation.h" -#include "depsgraph_types.h" -#include "depsgraph_build.h" -#include "depsgraph_intern.h" +#include "builder/deg_builder.h" +#include "builder/deg_builder_cycle.h" +#include "builder/deg_builder_nodes.h" +#include "builder/deg_builder_relations.h" +#include "builder/deg_builder_transitive.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" -#include "depsgraph_util_cycle.h" -#include "depsgraph_util_foreach.h" -#include "depsgraph_util_transitive.h" +#include "intern/depsgraph_types.h" +#include "intern/depsgraph_intern.h" + +#include "util/deg_util_foreach.h" /* ****************** */ /* External Build API */ -static eDepsNode_Type deg_build_scene_component_type(eDepsSceneComponentType component) +static DEG::eDepsNode_Type deg_build_scene_component_type( + eDepsSceneComponentType component) { switch (component) { - case DEG_SCENE_COMP_PARAMETERS: return DEPSNODE_TYPE_PARAMETERS; - case DEG_SCENE_COMP_ANIMATION: return DEPSNODE_TYPE_ANIMATION; - case DEG_SCENE_COMP_SEQUENCER: return DEPSNODE_TYPE_SEQUENCER; + case DEG_SCENE_COMP_PARAMETERS: return DEG::DEPSNODE_TYPE_PARAMETERS; + case DEG_SCENE_COMP_ANIMATION: return DEG::DEPSNODE_TYPE_ANIMATION; + case DEG_SCENE_COMP_SEQUENCER: return DEG::DEPSNODE_TYPE_SEQUENCER; } - return DEPSNODE_TYPE_UNDEFINED; + return DEG::DEPSNODE_TYPE_UNDEFINED; } -static eDepsNode_Type deg_build_object_component_type(eDepsObjectComponentType component) +static DEG::eDepsNode_Type deg_build_object_component_type( + eDepsObjectComponentType component) { switch (component) { - case DEG_OB_COMP_PARAMETERS: return DEPSNODE_TYPE_PARAMETERS; - case DEG_OB_COMP_PROXY: return DEPSNODE_TYPE_PROXY; - case DEG_OB_COMP_ANIMATION: return DEPSNODE_TYPE_ANIMATION; - case DEG_OB_COMP_TRANSFORM: return DEPSNODE_TYPE_TRANSFORM; - case DEG_OB_COMP_GEOMETRY: return DEPSNODE_TYPE_GEOMETRY; - case DEG_OB_COMP_EVAL_POSE: return DEPSNODE_TYPE_EVAL_POSE; - case DEG_OB_COMP_BONE: return DEPSNODE_TYPE_BONE; - case DEG_OB_COMP_EVAL_PARTICLES: return DEPSNODE_TYPE_EVAL_PARTICLES; - case DEG_OB_COMP_SHADING: return DEPSNODE_TYPE_SHADING; + case DEG_OB_COMP_PARAMETERS: return DEG::DEPSNODE_TYPE_PARAMETERS; + case DEG_OB_COMP_PROXY: return DEG::DEPSNODE_TYPE_PROXY; + case DEG_OB_COMP_ANIMATION: return DEG::DEPSNODE_TYPE_ANIMATION; + case DEG_OB_COMP_TRANSFORM: return DEG::DEPSNODE_TYPE_TRANSFORM; + case DEG_OB_COMP_GEOMETRY: return DEG::DEPSNODE_TYPE_GEOMETRY; + case DEG_OB_COMP_EVAL_POSE: return DEG::DEPSNODE_TYPE_EVAL_POSE; + case DEG_OB_COMP_BONE: return DEG::DEPSNODE_TYPE_BONE; + case DEG_OB_COMP_EVAL_PARTICLES: return DEG::DEPSNODE_TYPE_EVAL_PARTICLES; + case DEG_OB_COMP_SHADING: return DEG::DEPSNODE_TYPE_SHADING; } - return DEPSNODE_TYPE_UNDEFINED; + return DEG::DEPSNODE_TYPE_UNDEFINED; } -void DEG_add_scene_relation(DepsNodeHandle *handle, struct Scene *scene, eDepsSceneComponentType component, const char *description) +static DEG::DepsNodeHandle *get_handle(DepsNodeHandle *handle) { - eDepsNode_Type type = deg_build_scene_component_type(component); - ComponentKey comp_key(&scene->id, type); - handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); + return reinterpret_cast<DEG::DepsNodeHandle *>(handle); } -void DEG_add_object_relation(DepsNodeHandle *handle, struct Object *ob, eDepsObjectComponentType component, const char *description) +void DEG_add_scene_relation(DepsNodeHandle *handle, + Scene *scene, + eDepsSceneComponentType component, + const char *description) { - eDepsNode_Type type = deg_build_object_component_type(component); - ComponentKey comp_key(&ob->id, type); - handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); + DEG::eDepsNode_Type type = deg_build_scene_component_type(component); + DEG::ComponentKey comp_key(&scene->id, type); + DEG::DepsNodeHandle *deg_handle = get_handle(handle); + deg_handle->builder->add_node_handle_relation(comp_key, + deg_handle, + DEG::DEPSREL_TYPE_GEOMETRY_EVAL, + description); } -void DEG_add_bone_relation(DepsNodeHandle *handle, struct Object *ob, const char *bone_name, eDepsObjectComponentType component, const char *description) +void DEG_add_object_relation(DepsNodeHandle *handle, + Object *ob, + eDepsObjectComponentType component, + const char *description) { - eDepsNode_Type type = deg_build_object_component_type(component); - ComponentKey comp_key(&ob->id, type, bone_name); + DEG::eDepsNode_Type type = deg_build_object_component_type(component); + DEG::ComponentKey comp_key(&ob->id, type); + DEG::DepsNodeHandle *deg_handle = get_handle(handle); + deg_handle->builder->add_node_handle_relation(comp_key, + deg_handle, + DEG::DEPSREL_TYPE_GEOMETRY_EVAL, + description); +} - // XXX: "Geometry Eval" might not always be true, but this only gets called from modifier building now - handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description); +void DEG_add_bone_relation(DepsNodeHandle *handle, + Object *ob, + const char *bone_name, + eDepsObjectComponentType component, + const char *description) +{ + DEG::eDepsNode_Type type = deg_build_object_component_type(component); + DEG::ComponentKey comp_key(&ob->id, type, bone_name); + DEG::DepsNodeHandle *deg_handle = get_handle(handle); + /* XXX: "Geometry Eval" might not always be true, but this only gets called + * from modifier building now. + */ + deg_handle->builder->add_node_handle_relation(comp_key, + deg_handle, + DEG::DEPSREL_TYPE_GEOMETRY_EVAL, + description); } void DEG_add_special_eval_flag(Depsgraph *graph, ID *id, short flag) { + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); if (graph == NULL) { BLI_assert(!"Graph should always be valid"); return; } - IDDepsNode *id_node = graph->find_id_node(id); + DEG::IDDepsNode *id_node = deg_graph->find_id_node(id); if (id_node == NULL) { BLI_assert(!"ID should always be valid"); return; @@ -169,94 +159,21 @@ void DEG_add_special_eval_flag(Depsgraph *graph, ID *id, short flag) id_node->eval_flags |= flag; } -/* ********************** */ -/* Utilities for Builders */ - -/* Get unique identifier for FCurves and Drivers */ -string deg_fcurve_id_name(const FCurve *fcu) -{ - char index_buf[32]; - sprintf(index_buf, "[%d]", fcu->array_index); - - return string(fcu->rna_path) + index_buf; -} - -static void deg_graph_build_finalize(Depsgraph *graph) -{ - std::stack<OperationDepsNode *> stack; - - foreach (OperationDepsNode *node, graph->operations) { - node->done = 0; - node->num_links_pending = 0; - foreach (DepsRelation *rel, node->inlinks) { - if ((rel->from->type == DEPSNODE_TYPE_OPERATION) && - (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) - { - ++node->num_links_pending; - } - } - if (node->num_links_pending == 0) { - stack.push(node); - } - IDDepsNode *id_node = node->owner->owner; - id_node->id->tag |= LIB_TAG_DOIT; - } - - while (!stack.empty()) { - OperationDepsNode *node = stack.top(); - if (node->done == 0 && node->outlinks.size() != 0) { - foreach (DepsRelation *rel, node->outlinks) { - if (rel->to->type == DEPSNODE_TYPE_OPERATION) { - OperationDepsNode *to = (OperationDepsNode *)rel->to; - if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { - BLI_assert(to->num_links_pending > 0); - --to->num_links_pending; - } - if (to->num_links_pending == 0) { - stack.push(to); - } - } - } - node->done = 1; - } - else { - stack.pop(); - IDDepsNode *id_node = node->owner->owner; - foreach (DepsRelation *rel, node->outlinks) { - if (rel->to->type == DEPSNODE_TYPE_OPERATION) { - OperationDepsNode *to = (OperationDepsNode *)rel->to; - IDDepsNode *id_to = to->owner->owner; - id_node->layers |= id_to->layers; - } - } - } - } - - /* Re-tag IDs for update if it was tagged before the relations update tag. */ - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) - { - IDDepsNode *id_node = it->second; - ID *id = id_node->id; - if (id->tag & LIB_TAG_ID_RECALC_ALL && - id->tag & LIB_TAG_DOIT) - { - id_node->tag_update(graph); - id->tag &= ~LIB_TAG_DOIT; - } - } -} - /* ******************** */ /* Graph Building API's */ -/* Build depsgraph for the given scene, and dump results in given graph container */ -// XXX: assume that this is called from outside, given the current scene as the "main" scene +/* Build depsgraph for the given scene, and dump results in given + * graph container. + */ +/* XXX: assume that this is called from outside, given the current scene as + * the "main" scene. + */ void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene) { + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + /* 1) Generate all the nodes in the graph first */ - DepsgraphNodeBuilder node_builder(bmain, graph); + DEG::DepsgraphNodeBuilder node_builder(bmain, deg_graph); /* create root node for scene first * - this way it should be the first in the graph, * reflecting its role as the entrypoint @@ -264,29 +181,40 @@ void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene) node_builder.add_root_node(); node_builder.build_scene(bmain, scene); - /* 2) Hook up relationships between operations - to determine evaluation order */ - DepsgraphRelationBuilder relation_builder(graph); - /* hook scene up to the root node as entrypoint to graph */ + /* 2) Hook up relationships between operations - to determine evaluation + * order. + */ + DEG::DepsgraphRelationBuilder relation_builder(deg_graph); + /* Hook scene up to the root node as entrypoint to graph. */ /* XXX what does this relation actually mean? - * it doesnt add any operations anyway and is not clear what part of the scene is to be connected. + * it doesnt add any operations anyway and is not clear what part of the + * scene is to be connected. */ - //relation_builder.add_relation(RootKey(), IDKey(scene), DEPSREL_TYPE_ROOT_TO_ACTIVE, "Root to Active Scene"); +#if 0 + relation_builder.add_relation(RootKey(), + IDKey(scene), + DEPSREL_TYPE_ROOT_TO_ACTIVE, + "Root to Active Scene"); +#endif relation_builder.build_scene(bmain, scene); /* Detect and solve cycles. */ - deg_graph_detect_cycles(graph); + DEG::deg_graph_detect_cycles(deg_graph); - /* 3) Simplify the graph by removing redundant relations (to optimise traversal later) */ - // TODO: it would be useful to have an option to disable this in cases where it is causing trouble + /* 3) Simplify the graph by removing redundant relations (to optimize + * traversal later). */ + /* TODO: it would be useful to have an option to disable this in cases where + * it is causing trouble. + */ if (G.debug_value == 799) { - deg_graph_transitive_reduction(graph); + DEG::deg_graph_transitive_reduction(deg_graph); } /* 4) Flush visibility layer and re-schedule nodes for update. */ - deg_graph_build_finalize(graph); + DEG::deg_graph_build_finalize(deg_graph); #if 0 - if (!DEG_debug_consistency_check(graph)) { + if (!DEG_debug_consistency_check(deg_graph)) { printf("Consistency validation failed, ABORTING!\n"); abort(); } @@ -296,7 +224,8 @@ void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene) /* Tag graph relations for update. */ void DEG_graph_tag_relations_update(Depsgraph *graph) { - graph->need_update = true; + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + deg_graph->need_update = true; } /* Tag all relations for update. */ @@ -324,7 +253,7 @@ void DEG_scene_relations_update(Main *bmain, Scene *scene) return; } - Depsgraph *graph = scene->depsgraph; + DEG::Depsgraph *graph = reinterpret_cast<DEG::Depsgraph *>(scene->depsgraph); if (!graph->need_update) { /* Graph is up to date, nothing to do. */ return; @@ -333,10 +262,12 @@ void DEG_scene_relations_update(Main *bmain, Scene *scene) /* Clear all previous nodes and operations. */ graph->clear_all_nodes(); graph->operations.clear(); - graph->entry_tags.clear(); + BLI_gset_clear(graph->entry_tags, NULL); /* Build new nodes and relations. */ - DEG_graph_build_from_scene(graph, bmain, scene); + DEG_graph_build_from_scene(reinterpret_cast< ::Depsgraph * >(graph), + bmain, + scene); graph->need_update = false; } diff --git a/source/blender/depsgraph/intern/depsgraph_debug.cc b/source/blender/depsgraph/intern/depsgraph_debug.cc index 5d21effe0f6..d3b48930779 100644 --- a/source/blender/depsgraph/intern/depsgraph_debug.cc +++ b/source/blender/depsgraph/intern/depsgraph_debug.cc @@ -30,957 +30,39 @@ * Implementation of tools for debugging the depsgraph */ -//#include <stdlib.h> -#include <string.h> - -extern "C" { #include "BLI_utildefines.h" -#include "BLI_listbase.h" #include "BLI_ghash.h" -#include "BLI_string.h" +extern "C" { #include "DNA_scene_types.h" -#include "DNA_userdef_types.h" #include "DEG_depsgraph.h" #include "DEG_depsgraph_debug.h" #include "DEG_depsgraph_build.h" - -#include "WM_api.h" -#include "WM_types.h" } /* extern "C" */ -#include "depsgraph_debug.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_intern.h" -#include "depsgraph_util_foreach.h" - -/* ****************** */ -/* Graphviz Debugging */ - -#define NL "\r\n" - -/* Only one should be enabled, defines whether graphviz nodes - * get colored by individual types or classes. - */ -#define COLOR_SCHEME_NODE_CLASS 1 -//#define COLOR_SCHEME_NODE_TYPE 2 - -static const char *deg_debug_graphviz_fontname = "helvetica"; -static float deg_debug_graphviz_graph_label_size = 20.0f; -static float deg_debug_graphviz_node_label_size = 14.0f; -static const int deg_debug_max_colors = 12; -#if 0 -static const char *deg_debug_colors_dark[] = { - "#6e8997", "#144f77", "#76945b", - "#216a1d", "#a76665", "#971112", - "#a87f49", "#0a9540", "#86768e", - "#462866", "#a9a965", "#753b1a", -}; -#endif -#ifdef COLOR_SCHEME_NODE_TYPE -static const char *deg_debug_colors[] = { - "#a6cee3", "#1f78b4", "#b2df8a", - "#33a02c", "#fb9a99", "#e31a1c", - "#fdbf6f", "#ff7f00", "#cab2d6", - "#6a3d9a", "#ffff99", "#b15928", -}; -#endif -static const char *deg_debug_colors_light[] = { - "#8dd3c7", "#ffffb3", "#bebada", - "#fb8072", "#80b1d3", "#fdb462", - "#b3de69", "#fccde5", "#d9d9d9", - "#bc80bd", "#ccebc5", "#ffed6f", -}; - -#ifdef COLOR_SCHEME_NODE_TYPE -static const int deg_debug_node_type_color_map[][2] = { - {DEPSNODE_TYPE_ROOT, 0}, - {DEPSNODE_TYPE_TIMESOURCE, 1}, - {DEPSNODE_TYPE_ID_REF, 2}, - {DEPSNODE_TYPE_SUBGRAPH, 3}, - - /* Outer Types */ - {DEPSNODE_TYPE_PARAMETERS, 4}, - {DEPSNODE_TYPE_PROXY, 5}, - {DEPSNODE_TYPE_ANIMATION, 6}, - {DEPSNODE_TYPE_TRANSFORM, 7}, - {DEPSNODE_TYPE_GEOMETRY, 8}, - {DEPSNODE_TYPE_SEQUENCER, 9}, - {DEPSNODE_TYPE_SHADING, 10}, - {-1, 0} -}; -#endif - -#if 0 /* unused */ -static const int deg_debug_relation_type_color_map[][2] = { - {DEPSREL_TYPE_STANDARD, 0}, - {DEPSREL_TYPE_ROOT_TO_ACTIVE, 1}, - {DEPSREL_TYPE_DATABLOCK, 2}, - {DEPSREL_TYPE_TIME, 3}, - {DEPSREL_TYPE_COMPONENT_ORDER, 4}, - {DEPSREL_TYPE_OPERATION, 5}, - {DEPSREL_TYPE_DRIVER, 6}, - {DEPSREL_TYPE_DRIVER_TARGET, 7}, - {DEPSREL_TYPE_TRANSFORM, 8}, - {DEPSREL_TYPE_GEOMETRY_EVAL, 9}, - {DEPSREL_TYPE_UPDATE, 10}, - {DEPSREL_TYPE_UPDATE_UI, 11}, - {-1, 0} -}; -#endif - -static int deg_debug_node_color_index(const DepsNode *node) -{ -#ifdef COLOR_SCHEME_NODE_CLASS - /* Some special types. */ - switch (node->type) { - case DEPSNODE_TYPE_ID_REF: - return 5; - case DEPSNODE_TYPE_OPERATION: - { - OperationDepsNode *op_node = (OperationDepsNode *)node; - if (op_node->is_noop()) - return 8; - break; - } - - default: - break; - } - /* Do others based on class. */ - switch (node->tclass) { - case DEPSNODE_CLASS_OPERATION: - return 4; - case DEPSNODE_CLASS_COMPONENT: - return 1; - default: - return 9; - } -#endif - -#ifdef COLOR_SCHEME_NODE_TYPE - const int (*pair)[2]; - for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { - if ((*pair)[0] == node->type) { - return (*pair)[1]; - } - } - return -1; -#endif -} - -struct DebugContext { - FILE *file; - bool show_tags; - bool show_eval_priority; -}; - -static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) ATTR_PRINTF_FORMAT(2, 3); -static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) -{ - va_list args; - va_start(args, fmt); - vfprintf(ctx.file, fmt, args); - va_end(args); -} - -static void deg_debug_graphviz_legend_color(const DebugContext &ctx, - const char *name, - const char *color) -{ - deg_debug_fprintf(ctx, "<TR>"); - deg_debug_fprintf(ctx, "<TD>%s</TD>", name); - deg_debug_fprintf(ctx, "<TD BGCOLOR=\"%s\"></TD>", color); - deg_debug_fprintf(ctx, "</TR>" NL); -} - -#if 0 -static void deg_debug_graphviz_legend_line(const DebugContext &ctx, - const char *name, - const char *color, - const char *style) -{ - /* XXX TODO */ - deg_debug_fprintf(ctx, "" NL); -} - -static void deg_debug_graphviz_legend_cluster(const DebugContext &ctx, - const char *name, - const char *color, - const char *style) -{ - deg_debug_fprintf(ctx, "<TR>"); - deg_debug_fprintf(ctx, "<TD>%s</TD>", name); - deg_debug_fprintf(ctx, "<TD CELLPADDING=\"4\"><TABLE BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"0\">"); - deg_debug_fprintf(ctx, "<TR><TD BGCOLOR=\"%s\"></TD></TR>", color); - deg_debug_fprintf(ctx, "</TABLE></TD>"); - deg_debug_fprintf(ctx, "</TR>" NL); -} -#endif - -static void deg_debug_graphviz_legend(const DebugContext &ctx) -{ - deg_debug_fprintf(ctx, "{" NL); - deg_debug_fprintf(ctx, "rank = sink;" NL); - deg_debug_fprintf(ctx, "Legend [shape=none, margin=0, label=<" NL); - deg_debug_fprintf(ctx, " <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">" NL); - deg_debug_fprintf(ctx, "<TR><TD COLSPAN=\"2\"><B>Legend</B></TD></TR>" NL); - -#ifdef COLOR_SCHEME_NODE_CLASS - const char **colors = deg_debug_colors_light; - deg_debug_graphviz_legend_color(ctx, "Operation", colors[4]); - deg_debug_graphviz_legend_color(ctx, "Component", colors[1]); - deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]); - deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]); -#endif - -#ifdef COLOR_SCHEME_NODE_TYPE - const int (*pair)[2]; - for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) { - DepsNodeFactory *nti = DEG_get_node_factory((eDepsNode_Type)(*pair)[0]); - deg_debug_graphviz_legend_color(ctx, - nti->tname().c_str(), - deg_debug_colors_light[(*pair)[1] % deg_debug_max_colors]); - } -#endif - - deg_debug_fprintf(ctx, "</TABLE>" NL); - deg_debug_fprintf(ctx, ">" NL); - deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); - deg_debug_fprintf(ctx, "];" NL); - deg_debug_fprintf(ctx, "}" NL); -} - -#if 0 /* unused */ -static int deg_debug_relation_type_color_index(eDepsRelation_Type type) -{ - const int (*pair)[2]; - for (pair = deg_debug_relation_type_color_map; (*pair)[0] >= 0; ++pair) { - if ((*pair)[0] == type) { - return (*pair)[1]; - } - } - return -1; -} -#endif - -static void deg_debug_graphviz_node_color(const DebugContext &ctx, - const DepsNode *node) -{ - const char *color_default = "black"; - const char *color_modified = "orangered4"; - const char *color_update = "dodgerblue3"; - const char *color = color_default; - if (ctx.show_tags) { - if (node->tclass == DEPSNODE_CLASS_OPERATION) { - OperationDepsNode *op_node = (OperationDepsNode *)node; - if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { - color = color_modified; - } - else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { - color = color_update; - } - } - } - deg_debug_fprintf(ctx, "\"%s\"", color); -} - -static void deg_debug_graphviz_node_penwidth(const DebugContext &ctx, - const DepsNode *node) -{ - float penwidth_default = 1.0f; - float penwidth_modified = 4.0f; - float penwidth_update = 4.0f; - float penwidth = penwidth_default; - if (ctx.show_tags) { - if (node->tclass == DEPSNODE_CLASS_OPERATION) { - OperationDepsNode *op_node = (OperationDepsNode *)node; - if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) { - penwidth = penwidth_modified; - } - else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { - penwidth = penwidth_update; - } - } - } - deg_debug_fprintf(ctx, "\"%f\"", penwidth); -} - -static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx, - const DepsNode *node) -{ - const char *defaultcolor = "gainsboro"; - int color_index = deg_debug_node_color_index(node); - const char *fillcolor = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors]; - deg_debug_fprintf(ctx, "\"%s\"", fillcolor); -} - -#if 0 /* implementation using stripes, a bit too noisy ... */ -static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx, - const DepsNode *node) -{ - const char *defaultcolor = "gainsboro"; - const char *color_needs_update = "orange"; - const int num_stripes = 10; - int color_index = deg_debug_node_color_index(node); - const char *base_color = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors]; - if (ctx.show_tags && - (node->flag & (DEPSNODE_FLAG_DIRECTLY_MODIFIED | DEPSNODE_FLAG_NEEDS_UPDATE))) - { - deg_debug_fprintf(ctx, "\""); - for (int i = 0; i < num_stripes; ++i) { - if (i > 0) { - deg_debug_fprintf(ctx, ":"); - } - deg_debug_fprintf(ctx, "%s:%s", base_color, color_needs_update); - } - deg_debug_fprintf(ctx, "\""); - } - else { - deg_debug_fprintf(ctx, "\"%s\"", base_color); - } -} -#endif - -static void deg_debug_graphviz_relation_color(const DebugContext &ctx, - const DepsRelation *rel) -{ - const char *color_default = "black"; - const char *color_error = "red4"; - const char *color = color_default; -#if 0 /* disabled for now, edge colors are hardly distinguishable */ - int color = deg_debug_relation_type_color_index(rel->type); - if (color < 0) { - deg_debug_fprintf(ctx, "%s", defaultcolor); - } - else { - deg_debug_fprintf(ctx, "\"%s\"", deg_debug_colors_dark[color % deg_debug_max_colors]); - } -#else - if (rel->flag & DEPSREL_FLAG_CYCLIC) - color = color_error; - - deg_debug_fprintf(ctx, "%s", color); -#endif -} - -static void deg_debug_graphviz_node_style(const DebugContext &ctx, const DepsNode *node) -{ - const char *base_style = "filled"; /* default style */ - if (ctx.show_tags) { - if (node->tclass == DEPSNODE_CLASS_OPERATION) { - OperationDepsNode *op_node = (OperationDepsNode *)node; - if (op_node->flag & (DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE)) { - base_style = "striped"; - } - } - } - switch (node->tclass) { - case DEPSNODE_CLASS_GENERIC: - deg_debug_fprintf(ctx, "\"%s\"", base_style); - break; - case DEPSNODE_CLASS_COMPONENT: - deg_debug_fprintf(ctx, "\"%s\"", base_style); - break; - case DEPSNODE_CLASS_OPERATION: - deg_debug_fprintf(ctx, "\"%s,rounded\"", base_style); - break; - } -} - -static void deg_debug_graphviz_node_single(const DebugContext &ctx, - const DepsNode *node) -{ - const char *shape = "box"; - string name = node->identifier(); - float priority = -1.0f; - if (node->type == DEPSNODE_TYPE_ID_REF) { - IDDepsNode *id_node = (IDDepsNode *)node; - char buf[256]; - BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); - name += buf; - } - if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION) { - priority = ((OperationDepsNode *)node)->eval_priority; - } - deg_debug_fprintf(ctx, "// %s\n", name.c_str()); - deg_debug_fprintf(ctx, "\"node_%p\"", node); - deg_debug_fprintf(ctx, "["); -// deg_debug_fprintf(ctx, "label=<<B>%s</B>>", name); - if (priority >= 0.0f) { - deg_debug_fprintf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>", - name.c_str(), - priority); - } - else { - deg_debug_fprintf(ctx, "label=<%s>", name.c_str()); - } - deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); - deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size); - deg_debug_fprintf(ctx, ",shape=%s", shape); - deg_debug_fprintf(ctx, ",style="); deg_debug_graphviz_node_style(ctx, node); - deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_node_color(ctx, node); - deg_debug_fprintf(ctx, ",fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); - deg_debug_fprintf(ctx, ",penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); - deg_debug_fprintf(ctx, "];" NL); - deg_debug_fprintf(ctx, NL); -} - -static void deg_debug_graphviz_node_cluster_begin(const DebugContext &ctx, - const DepsNode *node) -{ - string name = node->identifier().c_str(); - if (node->type == DEPSNODE_TYPE_ID_REF) { - IDDepsNode *id_node = (IDDepsNode *)node; - char buf[256]; - BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers); - name += buf; - } - deg_debug_fprintf(ctx, "// %s\n", name.c_str()); - deg_debug_fprintf(ctx, "subgraph \"cluster_%p\" {" NL, node); -// deg_debug_fprintf(ctx, "label=<<B>%s</B>>;" NL, name); - deg_debug_fprintf(ctx, "label=<%s>;" NL, name.c_str()); - deg_debug_fprintf(ctx, "fontname=\"%s\";" NL, deg_debug_graphviz_fontname); - deg_debug_fprintf(ctx, "fontsize=%f;" NL, deg_debug_graphviz_node_label_size); - deg_debug_fprintf(ctx, "margin=\"%d\";" NL, 16); - deg_debug_fprintf(ctx, "style="); deg_debug_graphviz_node_style(ctx, node); deg_debug_fprintf(ctx, ";" NL); - deg_debug_fprintf(ctx, "color="); deg_debug_graphviz_node_color(ctx, node); deg_debug_fprintf(ctx, ";" NL); - deg_debug_fprintf(ctx, "fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); deg_debug_fprintf(ctx, ";" NL); - deg_debug_fprintf(ctx, "penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); deg_debug_fprintf(ctx, ";" NL); - /* dummy node, so we can add edges between clusters */ - deg_debug_fprintf(ctx, "\"node_%p\"", node); - deg_debug_fprintf(ctx, "["); - deg_debug_fprintf(ctx, "shape=%s", "point"); - deg_debug_fprintf(ctx, ",style=%s", "invis"); - deg_debug_fprintf(ctx, "];" NL); - deg_debug_fprintf(ctx, NL); -} - -static void deg_debug_graphviz_node_cluster_end(const DebugContext &ctx) -{ - deg_debug_fprintf(ctx, "}" NL); - deg_debug_fprintf(ctx, NL); -} - -static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, - const Depsgraph *graph); -static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, - const Depsgraph *graph); - -static void deg_debug_graphviz_node(const DebugContext &ctx, - const DepsNode *node) -{ - switch (node->type) { - case DEPSNODE_TYPE_ID_REF: - { - const IDDepsNode *id_node = (const IDDepsNode *)node; - if (id_node->components.empty()) { - deg_debug_graphviz_node_single(ctx, node); - } - else { - deg_debug_graphviz_node_cluster_begin(ctx, node); - for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); - it != id_node->components.end(); - ++it) - { - const ComponentDepsNode *comp = it->second; - deg_debug_graphviz_node(ctx, comp); - } - deg_debug_graphviz_node_cluster_end(ctx); - } - break; - } - case DEPSNODE_TYPE_SUBGRAPH: - { - SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; - if (sub_node->graph) { - deg_debug_graphviz_node_cluster_begin(ctx, node); - deg_debug_graphviz_graph_nodes(ctx, sub_node->graph); - deg_debug_graphviz_node_cluster_end(ctx); - } - else { - deg_debug_graphviz_node_single(ctx, node); - } - break; - } - case DEPSNODE_TYPE_PARAMETERS: - case DEPSNODE_TYPE_ANIMATION: - case DEPSNODE_TYPE_TRANSFORM: - case DEPSNODE_TYPE_PROXY: - case DEPSNODE_TYPE_GEOMETRY: - case DEPSNODE_TYPE_SEQUENCER: - case DEPSNODE_TYPE_EVAL_POSE: - case DEPSNODE_TYPE_BONE: - case DEPSNODE_TYPE_SHADING: - case DEPSNODE_TYPE_EVAL_PARTICLES: - { - ComponentDepsNode *comp_node = (ComponentDepsNode *)node; - if (!comp_node->operations.empty()) { - deg_debug_graphviz_node_cluster_begin(ctx, node); - for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); - it != comp_node->operations.end(); - ++it) - { - const DepsNode *op_node = it->second; - deg_debug_graphviz_node(ctx, op_node); - } - deg_debug_graphviz_node_cluster_end(ctx); - } - else { - deg_debug_graphviz_node_single(ctx, node); - } - break; - } - default: - deg_debug_graphviz_node_single(ctx, node); - break; - } -} - -static bool deg_debug_graphviz_is_cluster(const DepsNode *node) -{ - switch (node->type) { - case DEPSNODE_TYPE_ID_REF: - { - const IDDepsNode *id_node = (const IDDepsNode *)node; - return !id_node->components.empty(); - } - case DEPSNODE_TYPE_SUBGRAPH: - { - SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; - return sub_node->graph != NULL; - } - case DEPSNODE_TYPE_PARAMETERS: - case DEPSNODE_TYPE_ANIMATION: - case DEPSNODE_TYPE_TRANSFORM: - case DEPSNODE_TYPE_PROXY: - case DEPSNODE_TYPE_GEOMETRY: - case DEPSNODE_TYPE_SEQUENCER: - case DEPSNODE_TYPE_EVAL_POSE: - case DEPSNODE_TYPE_BONE: - { - ComponentDepsNode *comp_node = (ComponentDepsNode *)node; - return !comp_node->operations.empty(); - } - default: - return false; - } -} - -static bool deg_debug_graphviz_is_owner(const DepsNode *node, - const DepsNode *other) -{ - switch (node->tclass) { - case DEPSNODE_CLASS_COMPONENT: - { - ComponentDepsNode *comp_node = (ComponentDepsNode *)node; - if (comp_node->owner == other) - return true; - break; - } - case DEPSNODE_CLASS_OPERATION: - { - OperationDepsNode *op_node = (OperationDepsNode *)node; - if (op_node->owner == other) - return true; - else if (op_node->owner->owner == other) - return true; - break; - } - default: break; - } - return false; -} - -static void deg_debug_graphviz_node_relations(const DebugContext &ctx, - const DepsNode *node) -{ - DEPSNODE_RELATIONS_ITER_BEGIN(node->inlinks, rel) - { - float penwidth = 2.0f; - - const DepsNode *tail = rel->to; /* same as node */ - const DepsNode *head = rel->from; - deg_debug_fprintf(ctx, "// %s -> %s\n", - head->identifier().c_str(), - tail->identifier().c_str()); - deg_debug_fprintf(ctx, "\"node_%p\"", head); - deg_debug_fprintf(ctx, " -> "); - deg_debug_fprintf(ctx, "\"node_%p\"", tail); - - deg_debug_fprintf(ctx, "["); - /* XXX labels on relations are not very helpful: - * - they tend to appear too far away to be associated with the edge lines - * - names are mostly redundant, reflecting simply their from/to nodes - * - no behavior or typing of relations themselves to justify labels - */ -#if 0 - deg_debug_fprintf(ctx, "label=\"%s\"", rel->name); - deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); -#else - /* Note: without label an id seem necessary to avoid bugs in graphviz/dot */ - deg_debug_fprintf(ctx, "id=\"%s\"", rel->name); -#endif - deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_relation_color(ctx, rel); - deg_debug_fprintf(ctx, ",penwidth=\"%f\"", penwidth); - /* NOTE: edge from node to own cluster is not possible and gives graphviz - * warning, avoid this here by just linking directly to the invisible - * placeholder node - */ - if (deg_debug_graphviz_is_cluster(tail) && !deg_debug_graphviz_is_owner(head, tail)) { - deg_debug_fprintf(ctx, ",ltail=\"cluster_%p\"", tail); - } - if (deg_debug_graphviz_is_cluster(head) && !deg_debug_graphviz_is_owner(tail, head)) { - deg_debug_fprintf(ctx, ",lhead=\"cluster_%p\"", head); - } - deg_debug_fprintf(ctx, "];" NL); - deg_debug_fprintf(ctx, NL); - } - DEPSNODE_RELATIONS_ITER_END; - -#if 0 - if (node->tclass == DEPSNODE_CLASS_COMPONENT) { - const ComponentDepsNode *comp_node = (const ComponentDepsNode *)node; - for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); - it != comp_node->operations.end(); - ++it) - { - OperationDepsNode *op_node = it->second; - deg_debug_graphviz_node_relations(ctx, op_node); - } - } - else if (node->type == DEPSNODE_TYPE_ID_REF) { - const IDDepsNode *id_node = (const IDDepsNode *)node; - for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); - it != id_node->components.end(); - ++it) - { - const ComponentDepsNode *comp = it->second; - deg_debug_graphviz_node_relations(ctx, comp); - } - } - else if (node->type == DEPSNODE_TYPE_SUBGRAPH) { - SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node; - if (sub_node->graph) { - deg_debug_graphviz_graph_relations(ctx, sub_node->graph); - } - } -#endif -} - -static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx, - const Depsgraph *graph) -{ - if (graph->root_node) { - deg_debug_graphviz_node(ctx, graph->root_node); - } - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) - { - DepsNode *node = it->second; - deg_debug_graphviz_node(ctx, node); - } - TimeSourceDepsNode *time_source = graph->find_time_source(NULL); - if (time_source != NULL) { - deg_debug_graphviz_node(ctx, time_source); - } -} - -static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, - const Depsgraph *graph) -{ -#if 0 - if (graph->root_node) { - deg_debug_graphviz_node_relations(ctx, graph->root_node); - } - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) - { - DepsNode *id_node = it->second; - deg_debug_graphviz_node_relations(ctx, id_node); - } -#else - /* XXX not in use yet */ -// for (Depsgraph::OperationNodes::const_iterator it = graph->all_opnodes.begin(); -// it != graph->all_opnodes.end(); -// ++it) -// { -// OperationDepsNode *op_node = *it; -// deg_debug_graphviz_node_relations(ctx, op_node); -// } - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) - { - IDDepsNode *id_node = it->second; - for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); - it != id_node->components.end(); - ++it) - { - ComponentDepsNode *comp_node = it->second; - for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); - it != comp_node->operations.end(); - ++it) - { - OperationDepsNode *op_node = it->second; - deg_debug_graphviz_node_relations(ctx, op_node); - } - } - } - - TimeSourceDepsNode *time_source = graph->find_time_source(NULL); - if (time_source != NULL) { - deg_debug_graphviz_node_relations(ctx, time_source); - } -#endif -} - -void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_eval) -{ -#if 0 /* generate shaded color set */ - static char colors[][3] = {{0xa6, 0xce, 0xe3},{0x1f, 0x78, 0xb4},{0xb2, 0xdf, 0x8a},{0x33, 0xa0, 0x2c}, - {0xfb, 0x9a, 0x99},{0xe3, 0x1a, 0x1c},{0xfd, 0xbf, 0x6f},{0xff, 0x7f, 0x00}, - {0xca, 0xb2, 0xd6},{0x6a, 0x3d, 0x9a},{0xff, 0xff, 0x99},{0xb1, 0x59, 0x28}}; - int i; - const float factor = 0.666f; - for (i=0; i < 12; ++i) - printf("\"#%x%x%x\"\n", (char)(colors[i][0] * factor), (char)(colors[i][1] * factor), (char)(colors[i][2] * factor)); -#endif - - if (!graph) { - return; - } - - DebugContext ctx; - ctx.file = f; - ctx.show_tags = show_eval; - ctx.show_eval_priority = show_eval; - - deg_debug_fprintf(ctx, "digraph depgraph {" NL); - deg_debug_fprintf(ctx, "rankdir=LR;" NL); - deg_debug_fprintf(ctx, "graph ["); - deg_debug_fprintf(ctx, "compound=true"); - deg_debug_fprintf(ctx, ",labelloc=\"t\""); - deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_graph_label_size); - deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname); - deg_debug_fprintf(ctx, ",label=\"%s\"", label); - deg_debug_fprintf(ctx, ",splines=ortho"); - deg_debug_fprintf(ctx, ",overlap=scalexy"); // XXX: only when using neato - deg_debug_fprintf(ctx, "];" NL); - - deg_debug_graphviz_graph_nodes(ctx, graph); - deg_debug_graphviz_graph_relations(ctx, graph); - - deg_debug_graphviz_legend(ctx); - - deg_debug_fprintf(ctx, "}" NL); -} - -#undef NL +#include "intern/eval/deg_eval_debug.h" +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" /* ************************************************ */ -static string get_component_name(eDepsNode_Type type, const string &name = "") -{ - DepsNodeFactory *factory = DEG_get_node_factory(type); - if (name.empty()) { - return string(factory->tname()); - } - else { - return string(factory->tname()) + " | " + name; - } -} - -static void times_clear(DepsgraphStatsTimes ×) -{ - times.duration_last = 0.0f; -} - -static void times_add(DepsgraphStatsTimes ×, float time) -{ - times.duration_last += time; -} - -void DepsgraphDebug::eval_begin(const EvaluationContext *UNUSED(eval_ctx)) -{ - /* TODO(sergey): Stats are currently globally disabled. */ - /* verify_stats(); */ - reset_stats(); -} - -void DepsgraphDebug::eval_end(const EvaluationContext *UNUSED(eval_ctx)) -{ - WM_main_add_notifier(NC_SPACE | ND_SPACE_INFO_REPORT, NULL); -} - -void DepsgraphDebug::eval_step(const EvaluationContext *UNUSED(eval_ctx), - const char *message) -{ -#ifdef DEG_DEBUG_BUILD - if (deg_debug_eval_cb) - deg_debug_eval_cb(deg_debug_eval_userdata, message); -#else - (void)message; /* Ignored. */ -#endif -} - -void DepsgraphDebug::task_started(Depsgraph *graph, - const OperationDepsNode *node) -{ - if (stats) { - BLI_spin_lock(&graph->lock); - - ComponentDepsNode *comp = node->owner; - ID *id = comp->owner->id; - - DepsgraphStatsID *id_stats = get_id_stats(id, true); - times_clear(id_stats->times); - - /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ - if (0) { - /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */ - DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true); - times_clear(comp_stats->times); - } - - BLI_spin_unlock(&graph->lock); - } -} - -void DepsgraphDebug::task_completed(Depsgraph *graph, - const OperationDepsNode *node, - double time) -{ - if (stats) { - BLI_spin_lock(&graph->lock); - - ComponentDepsNode *comp = node->owner; - ID *id = comp->owner->id; - - DepsgraphStatsID *id_stats = get_id_stats(id, true); - times_add(id_stats->times, time); - - /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ - if (0) { - /* XXX component name usage needs cleanup! currently mixes identifier and description strings! */ - DepsgraphStatsComponent *comp_stats = get_component_stats(id, get_component_name(comp->type, comp->name), true); - times_add(comp_stats->times, time); - } - - BLI_spin_unlock(&graph->lock); - } -} - -/* ********** */ -/* Statistics */ - -DepsgraphStats *DepsgraphDebug::stats = NULL; - -/* GHash callback */ -static void deg_id_stats_free(void *val) -{ - DepsgraphStatsID *id_stats = (DepsgraphStatsID *)val; - - if (id_stats) { - BLI_freelistN(&id_stats->components); - MEM_freeN(id_stats); - } -} - -void DepsgraphDebug::stats_init() -{ - if (!stats) { - stats = (DepsgraphStats *)MEM_callocN(sizeof(DepsgraphStats), "Depsgraph Stats"); - stats->id_stats = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "Depsgraph ID Stats Hash"); - } -} - -void DepsgraphDebug::stats_free() -{ - if (stats) { - BLI_ghash_free(stats->id_stats, NULL, deg_id_stats_free); - MEM_freeN(stats); - stats = NULL; - } -} - -void DepsgraphDebug::verify_stats() -{ - stats_init(); -} - -void DepsgraphDebug::reset_stats() -{ - if (!stats) { - return; - } - - /* XXX this doesn't work, will immediately clear all info, - * since most depsgraph updates have none or very few updates to handle. - * - * Could consider clearing only zero-user ID blocks here - */ -// BLI_ghash_clear(stats->id_stats, NULL, deg_id_stats_free); -} - -DepsgraphStatsID *DepsgraphDebug::get_id_stats(ID *id, bool create) -{ - DepsgraphStatsID *id_stats = (DepsgraphStatsID *)BLI_ghash_lookup(stats->id_stats, id); - - if (!id_stats && create) { - id_stats = (DepsgraphStatsID *)MEM_callocN(sizeof(DepsgraphStatsID), "Depsgraph ID Stats"); - id_stats->id = id; - - BLI_ghash_insert(stats->id_stats, id, id_stats); - } - - return id_stats; -} - -DepsgraphStatsComponent *DepsgraphDebug::get_component_stats( - DepsgraphStatsID *id_stats, - const string &name, - bool create) -{ - DepsgraphStatsComponent *comp_stats; - for (comp_stats = (DepsgraphStatsComponent *)id_stats->components.first; - comp_stats != NULL; - comp_stats = comp_stats->next) - { - if (STREQ(comp_stats->name, name.c_str())) - break; - } - if (!comp_stats && create) { - comp_stats = (DepsgraphStatsComponent *)MEM_callocN(sizeof(DepsgraphStatsComponent), "Depsgraph Component Stats"); - BLI_strncpy(comp_stats->name, name.c_str(), sizeof(comp_stats->name)); - BLI_addtail(&id_stats->components, comp_stats); - } - return comp_stats; -} - -/* ------------------------------------------------ */ - DepsgraphStats *DEG_stats(void) { - return DepsgraphDebug::stats; + return DEG::DepsgraphDebug::stats; } void DEG_stats_verify() { - DepsgraphDebug::verify_stats(); + DEG::DepsgraphDebug::verify_stats(); } DepsgraphStatsID *DEG_stats_id(ID *id) { - if (!DepsgraphDebug::stats) { + if (!DEG::DepsgraphDebug::stats) { return NULL; } - return DepsgraphDebug::get_id_stats(id, false); + return DEG::DepsgraphDebug::get_id_stats(id, false); } bool DEG_debug_compare(const struct Depsgraph *graph1, @@ -988,7 +70,9 @@ bool DEG_debug_compare(const struct Depsgraph *graph1, { BLI_assert(graph1 != NULL); BLI_assert(graph2 != NULL); - if (graph1->operations.size() != graph2->operations.size()) { + const DEG::Depsgraph *deg_graph1 = reinterpret_cast<const DEG::Depsgraph *>(graph1); + const DEG::Depsgraph *deg_graph2 = reinterpret_cast<const DEG::Depsgraph *>(graph2); + if (deg_graph1->operations.size() != deg_graph2->operations.size()) { return false; } /* TODO(sergey): Currently we only do real stupid check, @@ -1018,18 +102,20 @@ bool DEG_debug_scene_relations_validate(Main *bmain, bool DEG_debug_consistency_check(Depsgraph *graph) { + const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph); + /* Validate links exists in both directions. */ - foreach (OperationDepsNode *node, graph->operations) { - foreach (DepsRelation *rel, node->outlinks) { + foreach (DEG::OperationDepsNode *node, deg_graph->operations) { + foreach (DEG::DepsRelation *rel, node->outlinks) { int counter1 = 0; - foreach (DepsRelation *tmp_rel, node->outlinks) { + foreach (DEG::DepsRelation *tmp_rel, node->outlinks) { if (tmp_rel == rel) { ++counter1; } } int counter2 = 0; - foreach (DepsRelation *tmp_rel, rel->to->inlinks) { + foreach (DEG::DepsRelation *tmp_rel, rel->to->inlinks) { if (tmp_rel == rel) { ++counter2; } @@ -1043,17 +129,17 @@ bool DEG_debug_consistency_check(Depsgraph *graph) } } - foreach (OperationDepsNode *node, graph->operations) { - foreach (DepsRelation *rel, node->inlinks) { + foreach (DEG::OperationDepsNode *node, deg_graph->operations) { + foreach (DEG::DepsRelation *rel, node->inlinks) { int counter1 = 0; - foreach (DepsRelation *tmp_rel, node->inlinks) { + foreach (DEG::DepsRelation *tmp_rel, node->inlinks) { if (tmp_rel == rel) { ++counter1; } } int counter2 = 0; - foreach (DepsRelation *tmp_rel, rel->from->outlinks) { + foreach (DEG::DepsRelation *tmp_rel, rel->from->outlinks) { if (tmp_rel == rel) { ++counter2; } @@ -1067,20 +153,20 @@ bool DEG_debug_consistency_check(Depsgraph *graph) } /* Validate node valency calculated in both directions. */ - foreach (OperationDepsNode *node, graph->operations) { + foreach (DEG::OperationDepsNode *node, deg_graph->operations) { node->num_links_pending = 0; node->done = 0; } - foreach (OperationDepsNode *node, graph->operations) { + foreach (DEG::OperationDepsNode *node, deg_graph->operations) { if (node->done) { printf("Node %s is twice in the operations!\n", node->identifier().c_str()); return false; } - foreach (DepsRelation *rel, node->outlinks) { - if (rel->to->type == DEPSNODE_TYPE_OPERATION) { - OperationDepsNode *to = (OperationDepsNode *)rel->to; + foreach (DEG::DepsRelation *rel, node->outlinks) { + if (rel->to->type == DEG::DEPSNODE_TYPE_OPERATION) { + DEG::OperationDepsNode *to = (DEG::OperationDepsNode *)rel->to; BLI_assert(to->num_links_pending < to->inlinks.size()); ++to->num_links_pending; } @@ -1088,10 +174,10 @@ bool DEG_debug_consistency_check(Depsgraph *graph) node->done = 1; } - foreach (OperationDepsNode *node, graph->operations) { + foreach (DEG::OperationDepsNode *node, deg_graph->operations) { int num_links_pending = 0; - foreach (DepsRelation *rel, node->inlinks) { - if (rel->from->type == DEPSNODE_TYPE_OPERATION) { + foreach (DEG::DepsRelation *rel, node->inlinks) { + if (rel->from->type == DEG::DEPSNODE_TYPE_OPERATION) { ++num_links_pending; } } @@ -1117,12 +203,14 @@ bool DEG_debug_consistency_check(Depsgraph *graph) void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer, size_t *r_operations, size_t *r_relations) { + const DEG::Depsgraph *deg_graph = reinterpret_cast<const DEG::Depsgraph *>(graph); + /* number of operations */ if (r_operations) { /* All operations should be in this list, allowing us to count the total * number of nodes. */ - *r_operations = graph->operations.size(); + *r_operations = deg_graph->operations.size(); } /* Count number of outer nodes and/or relations between these. */ @@ -1130,29 +218,21 @@ void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer, size_t tot_outer = 0; size_t tot_rels = 0; - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) + GHASH_FOREACH_BEGIN(DEG::IDDepsNode *, id_node, deg_graph->id_hash) { - IDDepsNode *id_node = it->second; tot_outer++; - for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin(); - it != id_node->components.end(); - ++it) + GHASH_FOREACH_BEGIN(DEG::ComponentDepsNode *, comp_node, id_node->components) { - ComponentDepsNode *comp_node = it->second; tot_outer++; - for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin(); - it != comp_node->operations.end(); - ++it) - { - OperationDepsNode *op_node = it->second; + foreach (DEG::OperationDepsNode *op_node, comp_node->operations) { tot_rels += op_node->inlinks.size(); } } + GHASH_FOREACH_END(); } + GHASH_FOREACH_END(); - TimeSourceDepsNode *time_source = graph->find_time_source(NULL); + DEG::TimeSourceDepsNode *time_source = deg_graph->find_time_source(NULL); if (time_source != NULL) { tot_rels += time_source->inlinks.size(); } @@ -1161,4 +241,3 @@ void DEG_stats_simple(const Depsgraph *graph, size_t *r_outer, if (r_outer) *r_outer = tot_outer; } } - diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cc b/source/blender/depsgraph/intern/depsgraph_eval.cc index e584e8a2a60..f8d40d0e6a8 100644 --- a/source/blender/depsgraph/intern/depsgraph_eval.cc +++ b/source/blender/depsgraph/intern/depsgraph_eval.cc @@ -32,11 +32,9 @@ #include "MEM_guardedalloc.h" -#include "PIL_time.h" - extern "C" { #include "BLI_utildefines.h" -#include "BLI_task.h" +#include "BLI_ghash.h" #include "BKE_depsgraph.h" #include "BKE_scene.h" @@ -44,14 +42,13 @@ extern "C" { #include "DEG_depsgraph.h" } /* extern "C" */ -#include "atomic_ops.h" +#include "intern/eval/deg_eval.h" +#include "intern/eval/deg_eval_flush.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_operation.h" -#include "depsgraph.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_debug.h" -#include "depsgraph_util_foreach.h" +#include "intern/depsgraph.h" #ifdef WITH_LEGACY_DEPSGRAPH static bool use_legacy_depsgraph = true; @@ -119,343 +116,16 @@ void DEG_evaluation_context_free(EvaluationContext *eval_ctx) MEM_freeN(eval_ctx); } -/* ********************** */ -/* Evaluation Entrypoints */ - -/* Forward declarations. */ -static void schedule_children(TaskPool *pool, - Depsgraph *graph, - OperationDepsNode *node, - const int layers, - const int thread_id); - -struct DepsgraphEvalState { - EvaluationContext *eval_ctx; - Depsgraph *graph; - int layers; -}; - -static void deg_task_run_func(TaskPool *pool, - void *taskdata, - int thread_id) -{ - DepsgraphEvalState *state = (DepsgraphEvalState *)BLI_task_pool_userdata(pool); - OperationDepsNode *node = (OperationDepsNode *)taskdata; - - BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled"); - - /* Should only be the case for NOOPs, which never get to this point. */ - BLI_assert(node->evaluate); - - while (true) { - /* Get context. */ - // TODO: who initialises this? "Init" operations aren't able to initialise it!!! - /* TODO(sergey): We don't use component contexts at this moment. */ - /* ComponentDepsNode *comp = node->owner; */ - BLI_assert(node->owner != NULL); - - /* Since we're not leaving the thread for until the graph branches it is - * possible to have NO-OP on the way. for which evaluate() will be NULL. - * but that's all fine, we'll just scheduler it's children. - */ - if (node->evaluate) { - /* Take note of current time. */ - double start_time = PIL_check_seconds_timer(); - DepsgraphDebug::task_started(state->graph, node); - - /* Perform operation. */ - node->evaluate(state->eval_ctx); - - /* Note how long this took. */ - double end_time = PIL_check_seconds_timer(); - DepsgraphDebug::task_completed(state->graph, - node, - end_time - start_time); - } - - /* If there's only one outgoing link we try to immediately switch to - * that node evaluation, without leaving the thread. - * - * It's only doable if the child don't have extra relations or all they - * are satisfied. - * - * TODO(sergey): Checks here can be de-duplicated with the ones from - * schedule_node(), however, how to do it nicely? - */ - if (node->outlinks.size() == 1) { - DepsRelation *rel = node->outlinks[0]; - OperationDepsNode *child = (OperationDepsNode *)rel->to; - BLI_assert(child->type == DEPSNODE_TYPE_OPERATION); - if (!child->scheduled) { - int id_layers = child->owner->owner->layers; - if (!((child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 && - (id_layers & state->layers) != 0)) - { - /* Node does not need an update, so can;t continue with the - * chain and need to switch to another one by leaving the - * thread. - */ - break; - } - if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { - BLI_assert(child->num_links_pending > 0); - atomic_sub_uint32(&child->num_links_pending, 1); - } - if (child->num_links_pending == 0) { - bool is_scheduled = atomic_fetch_and_or_uint8((uint8_t *)&child->scheduled, (uint8_t)true); - if (!is_scheduled) { - /* Node was not scheduled, switch to it! */ - node = child; - } - else { - /* Someone else scheduled the node, leaving us - * unemployed in this thread, we're leaving. - */ - break; - } - } - else { - /* There are other dependencies on the child, can't do - * anything in the current thread. - */ - break; - } - } - else { - /* Happens when having cyclic dependencies. - * - * Nothing to do here, single child was already scheduled, we - * can leave the thread now. - */ - break; - } - } - else { - /* TODO(sergey): It's possible to use one of the outgoing relations - * as a chain which we'll try to keep alive, but it's a bit more - * involved change. - */ - schedule_children(pool, state->graph, node, state->layers, thread_id); - break; - } - } -} - -typedef struct CalculatePengindData { - Depsgraph *graph; - int layers; -} CalculatePengindData; - -static void calculate_pending_func(void *data_v, int i) -{ - CalculatePengindData *data = (CalculatePengindData *)data_v; - Depsgraph *graph = data->graph; - int layers = data->layers; - OperationDepsNode *node = graph->operations[i]; - IDDepsNode *id_node = node->owner->owner; - - node->num_links_pending = 0; - node->scheduled = false; - - /* count number of inputs that need updates */ - if ((id_node->layers & layers) != 0 && - (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) - { - DEPSNODE_RELATIONS_ITER_BEGIN(node->inlinks, rel) - { - if (rel->from->type == DEPSNODE_TYPE_OPERATION && - (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) - { - OperationDepsNode *from = (OperationDepsNode *)rel->from; - IDDepsNode *id_from_node = from->owner->owner; - if ((id_from_node->layers & layers) != 0 && - (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) - { - ++node->num_links_pending; - } - } - } - DEPSNODE_RELATIONS_ITER_END; - } -} - -static void calculate_pending_parents(Depsgraph *graph, int layers) -{ - const int num_operations = graph->operations.size(); - const bool do_threads = num_operations > 256; - CalculatePengindData data; - data.graph = graph; - data.layers = layers; - BLI_task_parallel_range(0, num_operations, &data, calculate_pending_func, do_threads); -} - -#ifdef USE_EVAL_PRIORITY -static void calculate_eval_priority(OperationDepsNode *node) -{ - if (node->done) { - return; - } - node->done = 1; - - if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { - /* XXX standard cost of a node, could be estimated somewhat later on */ - const float cost = 1.0f; - /* NOOP nodes have no cost */ - node->eval_priority = node->is_noop() ? cost : 0.0f; - - foreach (DepsRelation *rel, node->outlinks) { - OperationDepsNode *to = (OperationDepsNode *)rel->to; - BLI_assert(to->type == DEPSNODE_TYPE_OPERATION); - calculate_eval_priority(to); - node->eval_priority += to->eval_priority; - } - } - else { - node->eval_priority = 0.0f; - } -} -#endif - -/* Schedule a node if it needs evaluation. - * dec_parents: Decrement pending parents count, true when child nodes are scheduled - * after a task has been completed. - */ -static void schedule_node(TaskPool *pool, Depsgraph *graph, int layers, - OperationDepsNode *node, bool dec_parents, - const int thread_id) -{ - int id_layers = node->owner->owner->layers; - - if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 && - (id_layers & layers) != 0) - { - if (dec_parents) { - BLI_assert(node->num_links_pending > 0); - atomic_sub_uint32(&node->num_links_pending, 1); - } - - if (node->num_links_pending == 0) { - bool is_scheduled = atomic_fetch_and_or_uint8((uint8_t *)&node->scheduled, (uint8_t)true); - if (!is_scheduled) { - if (node->is_noop()) { - /* skip NOOP node, schedule children right away */ - schedule_children(pool, graph, node, layers, thread_id); - } - else { - /* children are scheduled once this task is completed */ - BLI_task_pool_push_from_thread(pool, - deg_task_run_func, - node, - false, - TASK_PRIORITY_LOW, - thread_id); - } - } - } - } -} - -static void schedule_graph(TaskPool *pool, - Depsgraph *graph, - const int layers) -{ - foreach (OperationDepsNode *node, graph->operations) { - schedule_node(pool, graph, layers, node, false, 0); - } -} - -static void schedule_children(TaskPool *pool, - Depsgraph *graph, - OperationDepsNode *node, - const int layers, - const int thread_id) -{ - DEPSNODE_RELATIONS_ITER_BEGIN(node->outlinks, rel) - { - OperationDepsNode *child = (OperationDepsNode *)rel->to; - BLI_assert(child->type == DEPSNODE_TYPE_OPERATION); - if (child->scheduled) { - /* Happens when having cyclic dependencies. */ - continue; - } - schedule_node(pool, graph, layers, child, (rel->flag & DEPSREL_FLAG_CYCLIC) == 0, thread_id); - } - DEPSNODE_RELATIONS_ITER_END; -} - -/** - * Evaluate all nodes tagged for updating, - * \warning This is usually done as part of main loop, but may also be - * called from frame-change update. - * - * \note Time sources should be all valid! - */ -void DEG_evaluate_on_refresh_ex(EvaluationContext *eval_ctx, - Depsgraph *graph, - const int layers) -{ - /* Generate base evaluation context, upon which all the others are derived. */ - // TODO: this needs both main and scene access... - - /* Nothing to update, early out. */ - if (graph->entry_tags.size() == 0) { - return; - } - - /* Set time for the current graph evaluation context. */ - TimeSourceDepsNode *time_src = graph->find_time_source(); - eval_ctx->ctime = time_src->cfra; - - /* XXX could use a separate pool for each eval context */ - DepsgraphEvalState state; - state.eval_ctx = eval_ctx; - state.graph = graph; - state.layers = layers; - - TaskScheduler *task_scheduler = BLI_task_scheduler_get(); - TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state); - - if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) { - BLI_pool_set_num_threads(task_pool, 1); - } - - calculate_pending_parents(graph, layers); - - /* Clear tags. */ - foreach (OperationDepsNode *node, graph->operations) { - node->done = 0; - } - - /* Calculate priority for operation nodes. */ -#ifdef USE_EVAL_PRIORITY - foreach (OperationDepsNode *node, graph->operations) { - calculate_eval_priority(node); - } -#endif - - DepsgraphDebug::eval_begin(eval_ctx); - - schedule_graph(task_pool, graph, layers); - - BLI_task_pool_work_and_wait(task_pool); - BLI_task_pool_free(task_pool); - - DepsgraphDebug::eval_end(eval_ctx); - - /* Clear any uncleared tags - just in case. */ - DEG_graph_clear_tags(graph); -} - /* Evaluate all nodes tagged for updating. */ void DEG_evaluate_on_refresh(EvaluationContext *eval_ctx, Depsgraph *graph, Scene *scene) { + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); /* Update time on primary timesource. */ - TimeSourceDepsNode *tsrc = graph->find_time_source(); + DEG::TimeSourceDepsNode *tsrc = deg_graph->find_time_source(); tsrc->cfra = BKE_scene_frame_get(scene); - - DEG_evaluate_on_refresh_ex(eval_ctx, graph, graph->layers); + DEG::deg_evaluate_on_refresh(eval_ctx, deg_graph, deg_graph->layers); } /* Frame-change happened for root scene that graph belongs to. */ @@ -465,19 +135,18 @@ void DEG_evaluate_on_framechange(EvaluationContext *eval_ctx, float ctime, const int layers) { + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); /* Update time on primary timesource. */ - TimeSourceDepsNode *tsrc = graph->find_time_source(); + DEG::TimeSourceDepsNode *tsrc = deg_graph->find_time_source(); tsrc->cfra = ctime; - - tsrc->tag_update(graph); - - DEG_graph_flush_updates(bmain, graph); - + tsrc->tag_update(deg_graph); + DEG::deg_graph_flush_updates(bmain, deg_graph); /* Perform recalculation updates. */ - DEG_evaluate_on_refresh_ex(eval_ctx, graph, layers); + DEG::deg_evaluate_on_refresh(eval_ctx, deg_graph, layers); } bool DEG_needs_eval(Depsgraph *graph) { - return graph->entry_tags.size() != 0; + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + return BLI_gset_size(deg_graph->entry_tags) != 0; } diff --git a/source/blender/depsgraph/intern/depsgraph_intern.h b/source/blender/depsgraph/intern/depsgraph_intern.h index 7fdc2454564..e5d3d1f5861 100644 --- a/source/blender/depsgraph/intern/depsgraph_intern.h +++ b/source/blender/depsgraph/intern/depsgraph_intern.h @@ -31,65 +31,26 @@ * - Also, defines for "Node Type Info" */ -#ifndef __DEPSGRAPH_INTERN_H__ -#define __DEPSGRAPH_INTERN_H__ +#pragma once #include <cstdlib> #include "MEM_guardedalloc.h" -#include "depsgraph.h" -#include "depsnode.h" +extern "C" { +#include "BKE_global.h" +} + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph.h" struct Main; struct Group; struct Scene; -/* Graph Building ======================================================== */ - -/** - * Build depsgraph for the given group, and dump results in given graph container - * This is usually used for building subgraphs for groups to use... - */ -void DEG_graph_build_from_group(Depsgraph *graph, struct Main *bmain, struct Group *group); - -/* Build subgraph for group */ -DepsNode *DEG_graph_build_group_subgraph(Depsgraph *graph_main, struct Main *bmain, struct Group *group); - -/* Graph Copying ========================================================= */ -/* (Part of the Filtering API) */ - -/** - * Depsgraph Copying Context (dcc) - * - * Keeps track of node relationships/links/etc. during the copy - * operation so that they can be safely remapped... - */ -typedef struct DepsgraphCopyContext { - struct GHash *nodes_hash; /* <DepsNode, DepsNode> mapping from src node to dst node */ - struct GHash *rels_hash; // XXX: same for relationships? - - // XXX: filtering criteria... -} DepsgraphCopyContext; - -/* Internal Filtering API ---------------------------------------------- */ - -/* Create filtering context */ -// XXX: needs params for conditions? -DepsgraphCopyContext *DEG_filter_init(void); - -/* Free filtering context once filtering is done */ -void DEG_filter_cleanup(DepsgraphCopyContext *dcc); - - -/* Data Copy Operations ------------------------------------------------ */ - -/** - * Make a (deep) copy of provided node and it's little subgraph - * \warning Newly created node is not added to the existing graph - * \param dcc: Context info for helping resolve links - */ -DepsNode *DEG_copy_node(DepsgraphCopyContext *dcc, const DepsNode *src); +namespace DEG { /* Node Types Handling ================================================= */ @@ -101,8 +62,9 @@ struct DepsNodeFactory { virtual eDepsNode_Class tclass() const = 0; virtual const char *tname() const = 0; - virtual DepsNode *create_node(const ID *id, const string &subdata, const string &name) const = 0; - virtual DepsNode *copy_node(DepsgraphCopyContext *dcc, const DepsNode *copy) const = 0; + virtual DepsNode *create_node(const ID *id, + const string &subdata, + const string &name) const = 0; }; template <class NodeType> @@ -130,34 +92,18 @@ struct DepsNodeFactoryImpl : public DepsNodeFactory { return node; } - - virtual DepsNode *copy_node(DepsgraphCopyContext *dcc, const DepsNode *copy) const - { - BLI_assert(copy->type == type()); - DepsNode *node = OBJECT_GUARDED_NEW(NodeType); - - /* populate base node settings */ - node->type = type(); - node->tclass = tclass(); - // XXX: need to review the name here, as we can't have exact duplicates... - node->name = copy->name; - - node->copy(dcc, static_cast<const NodeType *>(copy)); - - return node; - } }; /* Typeinfo Management -------------------------------------------------- */ /* Register typeinfo */ -void DEG_register_node_typeinfo(DepsNodeFactory *factory); +void deg_register_node_typeinfo(DepsNodeFactory *factory); /* Get typeinfo for specified type */ -DepsNodeFactory *DEG_get_node_factory(const eDepsNode_Type type); +DepsNodeFactory *deg_get_node_factory(const eDepsNode_Type type); /* Get typeinfo for provided node */ -DepsNodeFactory *DEG_node_get_factory(const DepsNode *node); +DepsNodeFactory *deg_node_get_factory(const DepsNode *node); /* Editors Integration -------------------------------------------------- */ @@ -165,4 +111,11 @@ void deg_editors_id_update(struct Main *bmain, struct ID *id); void deg_editors_scene_update(struct Main *bmain, struct Scene *scene, bool updated); -#endif /* __DEPSGRAPH_INTERN_H__ */ +#define DEG_DEBUG_PRINTF(...) \ + do { \ + if (G.debug & G_DEBUG_DEPSGRAPH) { \ + fprintf(stderr, __VA_ARGS__); \ + } \ + } while (0) + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_query.cc b/source/blender/depsgraph/intern/depsgraph_query.cc index 73193747b93..cac4eaae215 100644 --- a/source/blender/depsgraph/intern/depsgraph_query.cc +++ b/source/blender/depsgraph/intern/depsgraph_query.cc @@ -33,162 +33,12 @@ #include "MEM_guardedalloc.h" extern "C" { -#include "BLI_utildefines.h" -#include "BLI_ghash.h" - #include "BKE_main.h" #include "DEG_depsgraph_query.h" } /* extern "C" */ -#include "depsgraph_queue.h" -#include "depsnode.h" -#include "depsnode_operation.h" -#include "depsgraph_intern.h" - -/* ************************* */ -/* Low-Level Graph Traversal */ - -#if 0 -/* Prepare for graph traversal, by tagging nodes, etc. */ -static void DEG_graph_traverse_begin(Depsgraph * /*graph*/) -{ - /* go over all nodes, initialising the valence counts */ - // XXX: this will end up being O(|V|), which is bad when we're just updating a few nodes... -} - -/* Perform a traversal of graph from given starting node (in execution order) */ -// TODO: additional flags for controlling the process? -void DEG_graph_traverse_from_node(Depsgraph *graph, OperationDepsNode *start_node, - DEG_FilterPredicate filter, void *filter_data, - DEG_NodeOperation op, void *operation_data) -{ - DepsgraphQueue *q; - - /* sanity checks */ - if (ELEM(NULL, graph, start_node, op)) - return; - - /* add node as starting node to be evaluated, with value of 0 */ - q = DEG_queue_new(); - - start_node->num_links_pending = 0; - DEG_queue_push(q, start_node, 0.0f); - - /* while we still have nodes in the queue, grab and work on next one */ - do { - /* grab item at front of queue */ - // XXX: in practice, we may need to wait until one becomes available... - OperationDepsNode *node = (OperationDepsNode *)DEG_queue_pop(q); - - /* perform operation on node */ - op(graph, node, operation_data); - - /* schedule up operations which depend on this */ - DEPSNODE_RELATIONS_ITER_BEGIN(node->outlinks, rel) - { - /* ensure that relationship is not tagged for ignoring (i.e. cyclic, etc.) */ - // TODO: cyclic refs should probably all get clustered towards the end, so that we can just stop on the first one - if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { - OperationDepsNode *child_node = (OperationDepsNode *)rel->to; - - /* only visit node if the filtering function agrees */ - if ((filter == NULL) || filter(graph, child_node, filter_data)) { - /* schedule up node... */ - child_node->num_links_pending--; - DEG_queue_push(q, child_node, (float)child_node->num_links_pending); - } - } - } - DEPSNODE_RELATIONS_ITER_END; - } while (DEG_queue_is_empty(q) == false); - - /* cleanup */ - DEG_queue_free(q); -} -#endif - -/* ************************************************************** */ -/* Filtering API - Basically, making a copy of the existing graph */ - -/* Create filtering context */ -// TODO: allow passing in a number of criteria? -DepsgraphCopyContext *DEG_filter_init() -{ - DepsgraphCopyContext *dcc = (DepsgraphCopyContext *)MEM_callocN(sizeof(DepsgraphCopyContext), "DepsgraphCopyContext"); - - /* init hashes for easy lookups */ - dcc->nodes_hash = BLI_ghash_ptr_new("Depsgraph Filter NodeHash"); - dcc->rels_hash = BLI_ghash_ptr_new("Depsgraph Filter Relationship Hash"); // XXX? - - /* store filtering criteria? */ - // xxx... - - return dcc; -} - -/* Cleanup filtering context */ -void DEG_filter_cleanup(DepsgraphCopyContext *dcc) -{ - /* sanity check */ - if (dcc == NULL) - return; - - /* free hashes - contents are weren't copied, so are ok... */ - BLI_ghash_free(dcc->nodes_hash, NULL, NULL); - BLI_ghash_free(dcc->rels_hash, NULL, NULL); - - /* clear filtering criteria */ - // ... - - /* free dcc itself */ - MEM_freeN(dcc); -} - -/* -------------------------------------------------- */ - -/* Create a copy of provided node */ -// FIXME: the handling of sub-nodes and links will need to be subject to filtering options... -// XXX: perhaps this really shouldn't be exposed, as it will just be a sub-step of the evaluation process? -DepsNode *DEG_copy_node(DepsgraphCopyContext *dcc, const DepsNode *src) -{ - /* sanity check */ - if (src == NULL) - return NULL; - - DepsNodeFactory *factory = DEG_get_node_factory(src->type); - BLI_assert(factory != NULL); - DepsNode *dst = factory->copy_node(dcc, src); - - /* add this node-pair to the hash... */ - BLI_ghash_insert(dcc->nodes_hash, (DepsNode *)src, dst); - -#if 0 /* XXX TODO */ - /* now, fix up any links in standard "node header" (i.e. DepsNode struct, that all - * all others are derived from) that are now corrupt - */ - { - /* relationships to other nodes... */ - // FIXME: how to handle links? We may only have partial set of all nodes still? - // XXX: the exact details of how to handle this are really part of the querying API... - - // XXX: BUT, for copying subgraphs, we'll need to define an API for doing this stuff anyways - // (i.e. for resolving and patching over links that exist within subtree...) - dst->inlinks.clear(); - dst->outlinks.clear(); - - /* clear traversal data */ - dst->num_links_pending = 0; - dst->lasttime = 0; - } - - /* fix links */ - // XXX... -#endif - - /* return copied node */ - return dst; -} +#include "intern/depsgraph_intern.h" bool DEG_id_type_tagged(Main *bmain, short idtype) { @@ -207,7 +57,9 @@ short DEG_get_eval_flags_for_id(Depsgraph *graph, ID *id) return 0; } - IDDepsNode *id_node = graph->find_id_node(id); + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + + DEG::IDDepsNode *id_node = deg_graph->find_id_node(id); if (id_node == NULL) { /* TODO(sergey): Does it mean we need to check set scene? */ return 0; diff --git a/source/blender/depsgraph/intern/depsgraph_queue.cc b/source/blender/depsgraph/intern/depsgraph_queue.cc deleted file mode 100644 index da60d73bc46..00000000000 --- a/source/blender/depsgraph/intern/depsgraph_queue.cc +++ /dev/null @@ -1,177 +0,0 @@ -/* - * ***** 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) 2013 Blender Foundation. - * All rights reserved. - * - * Original Author: Joshua Leung - * Contributor(s): None Yet - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/depsgraph/intern/depsgraph_queue.cc - * \ingroup depsgraph - * - * Implementation of special queue type for use in Depsgraph traversals. - */ - -#include <stdlib.h> - -#include "MEM_guardedalloc.h" - -extern "C" { -#include "BLI_utildefines.h" -#include "BLI_heap.h" -#include "BLI_ghash.h" -} /* extern "C" */ - -#include "depsgraph_queue.h" - -/* ****************************** */ -/* Depsgraph Queue implementation */ - -/* Data Management ----------------------------------------- */ - -DepsgraphQueue *DEG_queue_new(void) -{ - DepsgraphQueue *q = (DepsgraphQueue *)MEM_callocN(sizeof(DepsgraphQueue), "DEG_queue_new()"); - - /* init data structures for use here */ - q->pending_heap = BLI_heap_new(); - q->pending_hash = BLI_ghash_ptr_new("DEG Queue Pending Hash"); - - q->ready_heap = BLI_heap_new(); - - /* init settings */ - q->idx = 0; - q->tot = 0; - - /* return queue */ - return q; -} - -void DEG_queue_free(DepsgraphQueue *q) -{ - /* free data structures */ - BLI_assert(BLI_heap_size(q->pending_heap) == 0); - BLI_assert(BLI_heap_size(q->ready_heap) == 0); - BLI_assert(BLI_ghash_size(q->pending_hash) == 0); - - BLI_heap_free(q->pending_heap, NULL); - BLI_heap_free(q->ready_heap, NULL); - BLI_ghash_free(q->pending_hash, NULL, NULL); - - /* free queue itself */ - MEM_freeN(q); -} - -/* Statistics --------------------------------------------- */ - -/* Get the number of nodes which are we should visit, but are not able to yet */ -size_t DEG_queue_num_pending(DepsgraphQueue *q) -{ - return BLI_heap_size(q->pending_heap); -} - -/* Get the number of nodes which are now ready to be visited */ -size_t DEG_queue_num_ready(DepsgraphQueue *q) -{ - return BLI_heap_size(q->ready_heap); -} - -/* Get total size of queue */ -size_t DEG_queue_size(DepsgraphQueue *q) -{ - return DEG_queue_num_pending(q) + DEG_queue_num_ready(q); -} - -/* Check if queue has any items in it (still passing through) */ -bool DEG_queue_is_empty(DepsgraphQueue *q) -{ - return DEG_queue_size(q) == 0; -} - -/* Queue Operations --------------------------------------- */ - -/** - * Add DepsNode to the queue - * \param dnode: ``(DepsNode *)`` node to add to the queue - * Each node is only added once to the queue; Subsequent pushes - * merely update its status (e.g. moving it from "pending" to "ready") - * \param cost: new "num_links_pending" count for node *after* it has encountered - * via an outlink from the node currently being visited - * (i.e. we're one of the dependencies which may now be able to be processed) - */ -void DEG_queue_push(DepsgraphQueue *q, void *dnode, float cost) -{ - HeapNode *hnode = NULL; - - /* Shortcut: Directly add to ready if node isn't waiting on anything now... */ - if (cost == 0) { - /* node is now ready to be visited - schedule it up for such */ - if (BLI_ghash_haskey(q->pending_hash, dnode)) { - /* remove from pending queue - we're moving it to the scheduling queue */ - hnode = (HeapNode *)BLI_ghash_lookup(q->pending_hash, dnode); - BLI_heap_remove(q->pending_heap, hnode); - - BLI_ghash_remove(q->pending_hash, dnode, NULL, NULL); - } - - /* schedule up node using latest count (of ready nodes) */ - BLI_heap_insert(q->ready_heap, (float)q->idx, dnode); - q->idx++; - } - else { - /* node is still waiting on some other ancestors, - * so add it to the pending heap in the meantime... - */ - // XXX: is this even necessary now? - if (BLI_ghash_haskey(q->pending_hash, dnode)) { - /* just update cost on pending node */ - hnode = (HeapNode *)BLI_ghash_lookup(q->pending_hash, dnode); - BLI_heap_remove(q->pending_heap, hnode); - BLI_heap_insert(q->pending_heap, cost, hnode); - } - else { - /* add new node to pending queue, and increase size of overall queue */ - hnode = BLI_heap_insert(q->pending_heap, cost, dnode); - q->tot++; - } - } -} - -/* Grab a "ready" node from the queue */ -void *DEG_queue_pop(DepsgraphQueue *q) -{ - /* sanity check: if there are no "ready" nodes, - * start pulling from "pending" to keep things moving, - * but throw a warning so that we know that something's up here... - */ - if (BLI_heap_is_empty(q->ready_heap)) { - // XXX: this should never happen - // XXX: if/when it does happen, we may want instead to just wait until something pops up here... - printf("DepsgraphHeap Warning: No more ready nodes available. Trying from pending (idx = %d, tot = %d, pending = %d, ready = %d)\n", - (int)q->idx, (int)q->tot, (int)DEG_queue_num_pending(q), (int)DEG_queue_num_ready(q)); - - return BLI_heap_popmin(q->pending_heap); - } - else { - /* only grab "ready" nodes */ - return BLI_heap_popmin(q->ready_heap); - } -} diff --git a/source/blender/depsgraph/intern/depsgraph_queue.h b/source/blender/depsgraph/intern/depsgraph_queue.h deleted file mode 100644 index b85d46bd173..00000000000 --- a/source/blender/depsgraph/intern/depsgraph_queue.h +++ /dev/null @@ -1,91 +0,0 @@ -/* - * ***** 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) 2013 Blender Foundation. - * All rights reserved. - * - * Original Author: Joshua Leung - * Contributor(s): None Yet - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/depsgraph/intern/depsgraph_queue.h - * \ingroup depsgraph - * - * Defines for special queue type for use in Depsgraph traversals. - */ - -#ifndef __DEPSGRAPH_QUEUE_H__ -#define __DEPSGRAPH_QUEUE_H__ - -struct DepsNode; - -struct Heap; -struct GHash; - -/* *********************************************** */ -/* Dependency Graph Traversal Queue - * - * There are two parts to this: - * a) "Pending" Nodes - This part contains the set of nodes - * which are related to those which have been visited - * previously, but are not yet ready to actually be visited. - * b) "Scheduled" Nodes - These are the nodes whose ancestors - * have all been evaluated already, which means that any - * or all of them can be picked (in practically in order) to - * be visited immediately. - * - * Internally, the queue makes sure that each node in the graph - * only gets added to the queue once. This is because there can - * be multiple inlinks to each node given the way that the relations - * work. - */ - -/* Depsgraph Queue Type */ -typedef struct DepsgraphQueue { - /* Pending */ - struct Heap *pending_heap; /* (valence:int, DepsNode*) */ - struct GHash *pending_hash; /* (DepsNode* : HeapNode*>) */ - - /* Ready to be visited - fifo */ - struct Heap *ready_heap; /* (idx:int, DepsNode*) */ - - /* Size/Order counts */ - size_t idx; /* total number of nodes which are/have been ready so far (including those already visited) */ - size_t tot; /* total number of nodes which have passed through queue; mainly for debug */ -} DepsgraphQueue; - -/* ************************** */ -/* Depsgraph Queue Operations */ - -/* Data management */ -DepsgraphQueue *DEG_queue_new(void); -void DEG_queue_free(DepsgraphQueue *q); - -/* Statistics */ -size_t DEG_queue_num_pending(DepsgraphQueue *q); -size_t DEG_queue_num_ready(DepsgraphQueue *q); - -size_t DEG_queue_size(DepsgraphQueue *q); -bool DEG_queue_is_empty(DepsgraphQueue *q); - -/* Operations */ -void DEG_queue_push(DepsgraphQueue *q, void *dnode, float cost = 0.0f); -void *DEG_queue_pop(DepsgraphQueue *q); - -#endif /* DEPSGRAPH_QUEUE_H */ diff --git a/source/blender/depsgraph/intern/depsgraph_tag.cc b/source/blender/depsgraph/intern/depsgraph_tag.cc index 9676fb0326c..ea5afaab3f7 100644 --- a/source/blender/depsgraph/intern/depsgraph_tag.cc +++ b/source/blender/depsgraph/intern/depsgraph_tag.cc @@ -55,12 +55,14 @@ extern "C" { #include "DEG_depsgraph.h" } /* extern "C" */ -#include "depsgraph_debug.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_intern.h" -#include "depsgraph_util_foreach.h" +#include "intern/eval/deg_eval_flush.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" /* *********************** */ /* Update Tagging/Flushing */ @@ -155,19 +157,21 @@ void depsgraph_legacy_handle_update_tag(Main *bmain, ID *id, short flag) */ void DEG_graph_id_tag_update(Main *bmain, Depsgraph *graph, ID *id) { - IDDepsNode *node = graph->find_id_node(id); + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + DEG::IDDepsNode *node = deg_graph->find_id_node(id); lib_id_recalc_tag(bmain, id); if (node != NULL) { - node->tag_update(graph); + node->tag_update(deg_graph); } } /* Tag nodes related to a specific piece of data */ void DEG_graph_data_tag_update(Depsgraph *graph, const PointerRNA *ptr) { - DepsNode *node = graph->find_node_from_pointer(ptr, NULL); - if (node) { - node->tag_update(graph); + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + DEG::DepsNode *node = deg_graph->find_node_from_pointer(ptr, NULL); + if (node != NULL) { + node->tag_update(deg_graph); } else { printf("Missing node in %s\n", __func__); @@ -180,9 +184,10 @@ void DEG_graph_property_tag_update(Depsgraph *graph, const PointerRNA *ptr, const PropertyRNA *prop) { - DepsNode *node = graph->find_node_from_pointer(ptr, prop); - if (node) { - node->tag_update(graph); + DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph); + DEG::DepsNode *node = deg_graph->find_node_from_pointer(ptr, prop); + if (node != NULL) { + node->tag_update(deg_graph); } else { printf("Missing node in %s\n", __func__); @@ -260,123 +265,6 @@ void DEG_id_type_tag(Main *bmain, short idtype) bmain->id_tag_update[((unsigned char *)&idtype)[0]] = 1; } -/* Update Flushing ---------------------------------- */ - -/* FIFO queue for tagged nodes that need flushing */ -/* XXX This may get a dedicated implementation later if needed - lukas */ -typedef std::queue<OperationDepsNode *> FlushQueue; - -static void flush_init_func(void *data_v, int i) -{ - /* ID node's done flag is used to avoid multiple editors update - * for the same ID. - */ - Depsgraph *graph = (Depsgraph *)data_v; - OperationDepsNode *node = graph->operations[i]; - IDDepsNode *id_node = node->owner->owner; - id_node->done = 0; - node->scheduled = false; - node->owner->flags &= ~DEPSCOMP_FULLY_SCHEDULED; -} - -/* Flush updates from tagged nodes outwards until all affected nodes are tagged. */ -void DEG_graph_flush_updates(Main *bmain, Depsgraph *graph) -{ - /* sanity check */ - if (graph == NULL) - return; - - /* Nothing to update, early out. */ - if (graph->entry_tags.size() == 0) { - return; - } - - /* TODO(sergey): With a bit of flag magic we can get rid of this - * extra loop. - */ - const int num_operations = graph->operations.size(); - const bool do_threads = num_operations > 256; - BLI_task_parallel_range(0, num_operations, graph, flush_init_func, do_threads); - - FlushQueue queue; - /* Starting from the tagged "entry" nodes, flush outwards... */ - /* NOTE: Also need to ensure that for each of these, there is a path back to - * root, or else they won't be done. - * NOTE: Count how many nodes we need to handle - entry nodes may be - * component nodes which don't count for this purpose! - */ - foreach (OperationDepsNode *node, graph->entry_tags) { - IDDepsNode *id_node = node->owner->owner; - queue.push(node); - if (id_node->done == 0) { - deg_editors_id_update(bmain, id_node->id); - id_node->done = 1; - } - node->scheduled = true; - } - - while (!queue.empty()) { - OperationDepsNode *node = queue.front(); - queue.pop(); - - IDDepsNode *id_node = node->owner->owner; - lib_id_recalc_tag(bmain, id_node->id); - /* TODO(sergey): For until we've got proper data nodes in the graph. */ - lib_id_recalc_data_tag(bmain, id_node->id); - - ID *id = id_node->id; - /* This code is used to preserve those areas which does direct - * object update, - * - * Plus it ensures visibility changes and relations and layers - * visibility update has proper flags to work with. - */ - if (GS(id->name) == ID_OB) { - Object *object = (Object *)id; - ComponentDepsNode *comp_node = node->owner; - if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { - object->recalc |= OB_RECALC_TIME; - } - else if (comp_node->type == DEPSNODE_TYPE_TRANSFORM) { - object->recalc |= OB_RECALC_OB; - } - else { - object->recalc |= OB_RECALC_DATA; - } - } - - /* Flush to nodes along links... */ - foreach (DepsRelation *rel, node->outlinks) { - OperationDepsNode *to_node = (OperationDepsNode *)rel->to; - if (to_node->scheduled == false) { - to_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE; - queue.push(to_node); - to_node->scheduled = true; - if (id_node->done == 0) { - deg_editors_id_update(bmain, id_node->id); - id_node->done = 1; - } - } - } - - /* TODO(sergey): For until incremental updates are possible - * witin a component at least we tag the whole component - * for update. - */ - ComponentDepsNode *component = node->owner; - if ((component->flags & DEPSCOMP_FULLY_SCHEDULED) == 0) { - for (ComponentDepsNode::OperationMap::iterator it = component->operations.begin(); - it != node->owner->operations.end(); - ++it) - { - OperationDepsNode *op = it->second; - op->flag |= DEPSOP_FLAG_NEEDS_UPDATE; - } - component->flags |= DEPSCOMP_FULLY_SCHEDULED; - } - } -} - /* Recursively push updates out to all nodes dependent on this, * until all affected are tagged and/or scheduled up for eval */ @@ -388,34 +276,17 @@ void DEG_ids_flush_tagged(Main *bmain) { /* TODO(sergey): Only visible scenes? */ if (scene->depsgraph != NULL) { - DEG_graph_flush_updates(bmain, scene->depsgraph); + DEG::deg_graph_flush_updates( + bmain, + reinterpret_cast<DEG::Depsgraph *>(scene->depsgraph)); } } } -static void graph_clear_func(void *data_v, int i) -{ - Depsgraph *graph = (Depsgraph *)data_v; - OperationDepsNode *node = graph->operations[i]; - /* Clear node's "pending update" settings. */ - node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE); -} - -/* Clear tags from all operation nodes. */ -void DEG_graph_clear_tags(Depsgraph *graph) -{ - /* Go over all operation nodes, clearing tags. */ - const int num_operations = graph->operations.size(); - const bool do_threads = num_operations > 256; - BLI_task_parallel_range(0, num_operations, graph, graph_clear_func, do_threads); - /* Clear any entry tags which haven't been flushed. */ - graph->entry_tags.clear(); -} - /* Update dependency graph when visible scenes/layers changes. */ void DEG_graph_on_visible_update(Main *bmain, Scene *scene) { - Depsgraph *graph = scene->depsgraph; + DEG::Depsgraph *graph = reinterpret_cast<DEG::Depsgraph *>(scene->depsgraph); wmWindowManager *wm = (wmWindowManager *)bmain->wm.first; int old_layers = graph->layers; if (wm != NULL) { @@ -443,11 +314,8 @@ void DEG_graph_on_visible_update(Main *bmain, Scene *scene) * This is mainly needed on file load only, after that updates of invisible objects * will be stored in the pending list. */ - for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin(); - it != graph->id_hash.end(); - ++it) + GHASH_FOREACH_BEGIN(DEG::IDDepsNode *, id_node, graph->id_hash) { - IDDepsNode *id_node = it->second; ID *id = id_node->id; if ((id->tag & LIB_TAG_ID_RECALC_ALL) != 0 || (id_node->layers & scene->lay_updated) == 0) @@ -465,14 +333,15 @@ void DEG_graph_on_visible_update(Main *bmain, Scene *scene) (object->recalc & OB_RECALC_ALL) != 0) { id_node->tag_update(graph); - ComponentDepsNode *anim_comp = - id_node->find_component(DEPSNODE_TYPE_ANIMATION); + DEG::ComponentDepsNode *anim_comp = + id_node->find_component(DEG::DEPSNODE_TYPE_ANIMATION); if (anim_comp != NULL && object->recalc & OB_RECALC_TIME) { anim_comp->tag_update(graph); } } } } + GHASH_FOREACH_END(); } scene->lay_updated |= graph->layers; } @@ -513,7 +382,7 @@ void DEG_ids_check_recalc(Main *bmain, Scene *scene, bool time) } } - deg_editors_scene_update(bmain, scene, (updated || time)); + DEG::deg_editors_scene_update(bmain, scene, (updated || time)); } void DEG_ids_clear_recalc(Main *bmain) diff --git a/source/blender/depsgraph/intern/depsgraph_type_defines.cc b/source/blender/depsgraph/intern/depsgraph_type_defines.cc index 5a3048a4aa3..97208939e57 100644 --- a/source/blender/depsgraph/intern/depsgraph_type_defines.cc +++ b/source/blender/depsgraph/intern/depsgraph_type_defines.cc @@ -30,6 +30,8 @@ * Defines and code for core node types. */ +#include <cstdlib> // for BLI_assert() + extern "C" { #include "BLI_utildefines.h" #include "BLI_ghash.h" @@ -37,10 +39,13 @@ extern "C" { #include "DEG_depsgraph.h" } /* extern "C" */ -#include "depsgraph_intern.h" -#include "depsnode.h" -#include "depsnode_component.h" -#include "depsnode_operation.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "intern/depsgraph_intern.h" + +namespace DEG { /* ************ */ /* External API */ @@ -59,44 +64,108 @@ static GHash *_depsnode_typeinfo_registry = NULL; /* Registration ------------------------------------------- */ /* Register node type */ -void DEG_register_node_typeinfo(DepsNodeFactory *factory) +void deg_register_node_typeinfo(DepsNodeFactory *factory) { BLI_assert(factory != NULL); BLI_ghash_insert(_depsnode_typeinfo_registry, SET_INT_IN_POINTER(factory->type()), factory); } -/* Register all node types */ -void DEG_register_node_types(void) -{ - /* initialise registry */ - _depsnode_typeinfo_registry = BLI_ghash_int_new("Depsgraph Node Type Registry"); - - /* register node types */ - DEG_register_base_depsnodes(); - DEG_register_component_depsnodes(); - DEG_register_operation_depsnodes(); -} - -/* Free registry on exit */ -void DEG_free_node_types(void) -{ - BLI_ghash_free(_depsnode_typeinfo_registry, NULL, NULL); -} - /* Getters ------------------------------------------------- */ /* Get typeinfo for specified type */ -DepsNodeFactory *DEG_get_node_factory(const eDepsNode_Type type) +DepsNodeFactory *deg_get_node_factory(const eDepsNode_Type type) { /* look up type - at worst, it doesn't exist in table yet, and we fail */ return (DepsNodeFactory *)BLI_ghash_lookup(_depsnode_typeinfo_registry, SET_INT_IN_POINTER(type)); } /* Get typeinfo for provided node */ -DepsNodeFactory *DEG_node_get_factory(const DepsNode *node) +DepsNodeFactory *deg_node_get_factory(const DepsNode *node) { - if (!node) + if (node != NULL) { return NULL; + } + return deg_get_node_factory(node->type); +} + +/* Stringified opcodes ------------------------------------- */ + +DepsOperationStringifier DEG_OPNAMES; - return DEG_get_node_factory(node->type); +static const char *stringify_opcode(eDepsOperation_Code opcode) +{ + switch (opcode) { +#define STRINGIFY_OPCODE(name) case DEG_OPCODE_##name: return #name + STRINGIFY_OPCODE(OPERATION); + STRINGIFY_OPCODE(PLACEHOLDER); + STRINGIFY_OPCODE(NOOP); + STRINGIFY_OPCODE(ANIMATION); + STRINGIFY_OPCODE(DRIVER); + //STRINGIFY_OPCODE(PROXY); + STRINGIFY_OPCODE(TRANSFORM_LOCAL); + STRINGIFY_OPCODE(TRANSFORM_PARENT); + STRINGIFY_OPCODE(TRANSFORM_CONSTRAINTS); + //STRINGIFY_OPCODE(TRANSFORM_CONSTRAINTS_INIT); + //STRINGIFY_OPCODE(TRANSFORM_CONSTRAINT); + //STRINGIFY_OPCODE(TRANSFORM_CONSTRAINTS_DONE); + STRINGIFY_OPCODE(RIGIDBODY_REBUILD); + STRINGIFY_OPCODE(RIGIDBODY_SIM); + STRINGIFY_OPCODE(TRANSFORM_RIGIDBODY); + STRINGIFY_OPCODE(TRANSFORM_FINAL); + STRINGIFY_OPCODE(OBJECT_UBEREVAL); + STRINGIFY_OPCODE(GEOMETRY_UBEREVAL); + STRINGIFY_OPCODE(GEOMETRY_MODIFIER); + STRINGIFY_OPCODE(GEOMETRY_PATH); + STRINGIFY_OPCODE(POSE_INIT); + STRINGIFY_OPCODE(POSE_DONE); + STRINGIFY_OPCODE(POSE_IK_SOLVER); + STRINGIFY_OPCODE(POSE_SPLINE_IK_SOLVER); + STRINGIFY_OPCODE(BONE_LOCAL); + STRINGIFY_OPCODE(BONE_POSE_PARENT); + STRINGIFY_OPCODE(BONE_CONSTRAINTS); + //STRINGIFY_OPCODE(BONE_CONSTRAINTS_INIT); + //STRINGIFY_OPCODE(BONE_CONSTRAINT); + //STRINGIFY_OPCODE(BONE_CONSTRAINTS_DONE); + STRINGIFY_OPCODE(BONE_READY); + STRINGIFY_OPCODE(BONE_DONE); + STRINGIFY_OPCODE(PSYS_EVAL); + + case DEG_NUM_OPCODES: return "SpecialCase"; +#undef STRINGIFY_OPCODE + } + return "UNKNOWN"; +} + +DepsOperationStringifier::DepsOperationStringifier() { + for (int i = 0; i < DEG_NUM_OPCODES; ++i) { + names_[i] = stringify_opcode((eDepsOperation_Code)i); + } +} + +const char *DepsOperationStringifier::operator[](eDepsOperation_Code opcode) { + BLI_assert((opcode > 0) && (opcode < DEG_NUM_OPCODES)); + if (opcode >= 0 && opcode < DEG_NUM_OPCODES) { + return names_[opcode]; + } + return "UnknownOpcode"; +} + +} // namespace DEG + +/* Register all node types */ +void DEG_register_node_types(void) +{ + /* initialise registry */ + DEG::_depsnode_typeinfo_registry = BLI_ghash_int_new("Depsgraph Node Type Registry"); + + /* register node types */ + DEG::deg_register_base_depsnodes(); + DEG::deg_register_component_depsnodes(); + DEG::deg_register_operation_depsnodes(); +} + +/* Free registry on exit */ +void DEG_free_node_types(void) +{ + BLI_ghash_free(DEG::_depsnode_typeinfo_registry, NULL, NULL); } diff --git a/source/blender/depsgraph/intern/depsgraph_types.h b/source/blender/depsgraph/intern/depsgraph_types.h index f5fbf0bcc76..7516ccbfdc2 100644 --- a/source/blender/depsgraph/intern/depsgraph_types.h +++ b/source/blender/depsgraph/intern/depsgraph_types.h @@ -34,10 +34,9 @@ * in the graph. */ -#ifndef __DEPSGRAPH_TYPES_H__ -#define __DEPSGRAPH_TYPES_H__ +#pragma once -#include "depsgraph_util_function.h" +#include "util/deg_util_function.h" /* TODO(sergey): Ideally we'll just use char* and statically allocated strings * to avoid any possible overhead caused by string (re)allocation/formatting. @@ -55,69 +54,232 @@ struct PointerRNA; struct EvaluationContext; struct FCurve; +namespace DEG { + /* Evaluation Operation for atomic operation */ // XXX: move this to another header that can be exposed? typedef function<void(struct EvaluationContext *)> DepsEvalOperationCb; -/* Metatype of Nodes - The general "level" in the graph structure the node serves */ +/* Metatype of Nodes - The general "level" in the graph structure + * the node serves. + */ typedef enum eDepsNode_Class { - DEPSNODE_CLASS_GENERIC = 0, /* Types generally unassociated with user-visible entities, but needed for graph functioning */ - - DEPSNODE_CLASS_COMPONENT = 1, /* [Outer Node] An "aspect" of evaluating/updating an ID-Block, requiring certain types of evaluation behaviours */ - DEPSNODE_CLASS_OPERATION = 2, /* [Inner Node] A glorified function-pointer/callback for scheduling up evaluation operations for components, subject to relationship requirements */ + /* Types generally unassociated with user-visible entities, + * but needed for graph functioning. + */ + DEPSNODE_CLASS_GENERIC = 0, + /* [Outer Node] An "aspect" of evaluating/updating an ID-Block, requiring + * certain types of evaluation behavior. + */ + DEPSNODE_CLASS_COMPONENT = 1, + /* [Inner Node] A glorified function-pointer/callback for scheduling up + * evaluation operations for components, subject to relationship + * requirements. + */ + DEPSNODE_CLASS_OPERATION = 2, } eDepsNode_Class; /* Types of Nodes */ typedef enum eDepsNode_Type { - DEPSNODE_TYPE_UNDEFINED = -1, /* fallback type for invalid return value */ + /* Fallback type for invalid return value */ + DEPSNODE_TYPE_UNDEFINED = -1, + /* Inner Node (Operation) */ + DEPSNODE_TYPE_OPERATION = 0, + + /* **** Generic Types **** */ + + /* "Current Scene" - basically whatever kicks off the evaluation process. */ + DEPSNODE_TYPE_ROOT = 1, + /* Time-Source */ + DEPSNODE_TYPE_TIMESOURCE = 2, + /* ID-Block reference - used as landmarks/collection point for components, + * but not usually part of main graph. + */ + DEPSNODE_TYPE_ID_REF = 3, + /* Isolated sub-graph - used for keeping instanced data separate from + * instances using them. + */ + DEPSNODE_TYPE_SUBGRAPH = 4, - DEPSNODE_TYPE_OPERATION = 0, /* Inner Node (Operation) */ + /* **** Outer Types **** */ - /* Generic Types */ - DEPSNODE_TYPE_ROOT = 1, /* "Current Scene" - basically whatever kicks off the evaluation process */ - DEPSNODE_TYPE_TIMESOURCE = 2, /* Time-Source */ + /* Parameters Component - Default when nothing else fits + * (i.e. just SDNA property setting). + */ + DEPSNODE_TYPE_PARAMETERS = 11, + /* Generic "Proxy-Inherit" Component + * XXX: Also for instancing of subgraphs? + */ + DEPSNODE_TYPE_PROXY = 12, + /* Animation Component + * + * XXX: merge in with parameters? + */ + DEPSNODE_TYPE_ANIMATION = 13, + /* Transform Component (Parenting/Constraints) */ + DEPSNODE_TYPE_TRANSFORM = 14, + /* Geometry Component (DerivedMesh/Displist) */ + DEPSNODE_TYPE_GEOMETRY = 15, + /* Sequencer Component (Scene Only) */ + DEPSNODE_TYPE_SEQUENCER = 16, + + /* **** Evaluation-Related Outer Types (with Subdata) **** */ + + /* Pose Component - Owner/Container of Bones Eval */ + DEPSNODE_TYPE_EVAL_POSE = 21, + /* Bone Component - Child/Subcomponent of Pose */ + DEPSNODE_TYPE_BONE = 22, + /* Particle Systems Component */ + DEPSNODE_TYPE_EVAL_PARTICLES = 23, + /* Material Shading Component */ + DEPSNODE_TYPE_SHADING = 24, +} eDepsNode_Type; - DEPSNODE_TYPE_ID_REF = 3, /* ID-Block reference - used as landmarks/collection point for components, but not usually part of main graph */ - DEPSNODE_TYPE_SUBGRAPH = 4, /* Isolated sub-graph - used for keeping instanced data separate from instances using them */ +/* Identifiers for common operations (as an enum). */ +typedef enum eDepsOperation_Code { + /* Generic Operations ------------------------------ */ - /* Outer Types */ - DEPSNODE_TYPE_PARAMETERS = 11, /* Parameters Component - Default when nothing else fits (i.e. just SDNA property setting) */ - DEPSNODE_TYPE_PROXY = 12, /* Generic "Proxy-Inherit" Component */ // XXX: Also for instancing of subgraphs? - DEPSNODE_TYPE_ANIMATION = 13, /* Animation Component */ // XXX: merge in with parameters? - DEPSNODE_TYPE_TRANSFORM = 14, /* Transform Component (Parenting/Constraints) */ - DEPSNODE_TYPE_GEOMETRY = 15, /* Geometry Component (DerivedMesh/Displist) */ - DEPSNODE_TYPE_SEQUENCER = 16, /* Sequencer Component (Scene Only) */ + /* Placeholder for operations which don't need special mention */ + DEG_OPCODE_OPERATION = 0, - /* Evaluation-Related Outer Types (with Subdata) */ - DEPSNODE_TYPE_EVAL_POSE = 21, /* Pose Component - Owner/Container of Bones Eval */ - DEPSNODE_TYPE_BONE = 22, /* Bone Component - Child/Subcomponent of Pose */ + // XXX: Placeholder while porting depsgraph code + DEG_OPCODE_PLACEHOLDER, - DEPSNODE_TYPE_EVAL_PARTICLES = 23, /* Particle Systems Component */ - DEPSNODE_TYPE_SHADING = 24, /* Material Shading Component */ -} eDepsNode_Type; + DEG_OPCODE_NOOP, -/* Identifiers for common operations (as an enum) */ -typedef enum eDepsOperation_Code { -#define DEF_DEG_OPCODE(label) DEG_OPCODE_##label, -#include "depsnode_opcodes.h" -#undef DEF_DEG_OPCODE + /* Animation, Drivers, etc. ------------------------ */ + + /* NLA + Action */ + DEG_OPCODE_ANIMATION, + + /* Driver */ + DEG_OPCODE_DRIVER, + + /* Proxy Inherit? */ + //DEG_OPCODE_PROXY, + + /* Transform --------------------------------------- */ + + /* Transform entry point - local transforms only */ + DEG_OPCODE_TRANSFORM_LOCAL, + + /* Parenting */ + DEG_OPCODE_TRANSFORM_PARENT, + + /* Constraints */ + DEG_OPCODE_TRANSFORM_CONSTRAINTS, + //DEG_OPCODE_TRANSFORM_CONSTRAINTS_INIT, + //DEG_OPCODE_TRANSFORM_CONSTRAINT, + //DEG_OPCODE_TRANSFORM_CONSTRAINTS_DONE, + + /* Rigidbody Sim - Perform Sim */ + DEG_OPCODE_RIGIDBODY_REBUILD, + DEG_OPCODE_RIGIDBODY_SIM, + + /* Rigidbody Sim - Copy Results to Object */ + DEG_OPCODE_TRANSFORM_RIGIDBODY, + + /* Transform exitpoint */ + DEG_OPCODE_TRANSFORM_FINAL, + + /* XXX: ubereval is for temporary porting purposes only */ + DEG_OPCODE_OBJECT_UBEREVAL, + + /* Geometry ---------------------------------------- */ + + /* XXX: Placeholder - UberEval */ + DEG_OPCODE_GEOMETRY_UBEREVAL, + + /* Modifier */ + DEG_OPCODE_GEOMETRY_MODIFIER, + + /* Curve Objects - Path Calculation (used for path-following tools, */ + DEG_OPCODE_GEOMETRY_PATH, + + /* Pose -------------------------------------------- */ + + /* Init IK Trees, etc. */ + DEG_OPCODE_POSE_INIT, + + /* Free IK Trees + Compute Deform Matrices */ + DEG_OPCODE_POSE_DONE, + + /* IK/Spline Solvers */ + DEG_OPCODE_POSE_IK_SOLVER, + DEG_OPCODE_POSE_SPLINE_IK_SOLVER, + + /* Bone -------------------------------------------- */ + + /* Bone local transforms - Entrypoint */ + DEG_OPCODE_BONE_LOCAL, + + /* Pose-space conversion (includes parent + restpose, */ + DEG_OPCODE_BONE_POSE_PARENT, + + /* Constraints */ + DEG_OPCODE_BONE_CONSTRAINTS, + //DEG_OPCODE_BONE_CONSTRAINTS_INIT, + //DEG_OPCODE_BONE_CONSTRAINT, + //DEG_OPCODE_BONE_CONSTRAINTS_DONE, + + /* Bone transforms are ready + * + * - "READY" This (internal, noop is used to signal that all pre-IK + * operations are done. Its role is to help mediate situations + * where cyclic relations may otherwise form (i.e. one bone in + * chain targetting another in same chain, + * + * - "DONE" This noop is used to signal that the bone's final pose + * transform can be read by others + */ + // TODO: deform mats could get calculated in the final_transform ops... + DEG_OPCODE_BONE_READY, + DEG_OPCODE_BONE_DONE, + + /* Particles --------------------------------------- */ + + /* XXX: placeholder - Particle System eval */ + DEG_OPCODE_PSYS_EVAL, + + DEG_NUM_OPCODES, } eDepsOperation_Code; -/* String defines for these opcodes, defined in depsnode_operation.cpp */ -extern const char *DEG_OPNAMES[]; +/* Some magic to stringify operation codes. */ +class DepsOperationStringifier { +public: + DepsOperationStringifier(); + const char *operator[](eDepsOperation_Code opcodex); +protected: + const char *names_[DEG_NUM_OPCODES]; +}; +/* String defines for these opcodes, defined in depsgraph_type_defines.cpp */ +extern DepsOperationStringifier DEG_OPNAMES; /* Type of operation */ typedef enum eDepsOperation_Type { - /* Primary operation types */ - DEPSOP_TYPE_INIT = 0, /* initialise evaluation data */ - DEPSOP_TYPE_EXEC = 1, /* standard evaluation step */ - DEPSOP_TYPE_POST = 2, /* cleanup evaluation data + flush results */ - - /* Additional operation types */ - DEPSOP_TYPE_OUT = 3, /* indicator for outputting a temporary result that other components can use */ // XXX? - DEPSOP_TYPE_SIM = 4, /* indicator for things like IK Solvers and Rigidbody Sim steps which modify final results of separate entities at once */ - DEPSOP_TYPE_REBUILD = 5, /* rebuild internal evaluation data - used for Rigidbody Reset and Armature Rebuild-On-Load */ + /* **** Primary operation types **** */ + + /* Initialise evaluation data */ + DEPSOP_TYPE_INIT = 0, + /* Standard evaluation step */ + DEPSOP_TYPE_EXEC = 1, + /* Cleanup evaluation data + flush results */ + DEPSOP_TYPE_POST = 2, + + /* **** Additional operation types **** */ + /* Indicator for outputting a temporary result that other components + * can use. // XXX? + */ + DEPSOP_TYPE_OUT = 3, + /* Indicator for things like IK Solvers and Rigidbody Sim steps which + * modify final results of separate entities at once. + */ + DEPSOP_TYPE_SIM = 4, + /* Rebuild internal evaluation data - used for Rigidbody Reset and + * Armature Rebuild-On-Load. + */ + DEPSOP_TYPE_REBUILD = 5, } eDepsOperation_Type; /* Types of relationships between nodes @@ -170,4 +332,4 @@ typedef enum eDepsRelation_Type { DEPSREL_TYPE_UPDATE_UI, } eDepsRelation_Type; -#endif /* __DEPSGRAPH_TYPES_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode_opcodes.h b/source/blender/depsgraph/intern/depsnode_opcodes.h deleted file mode 100644 index b81822c0ac5..00000000000 --- a/source/blender/depsgraph/intern/depsnode_opcodes.h +++ /dev/null @@ -1,145 +0,0 @@ -/* - * ***** 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) 2014 Blender Foundation. - * All rights reserved. - * - * Original Author: Joshua Leung - * Contributor(s): None Yet - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/depsgraph/intern/depsnode_opcodes.h - * \ingroup depsgraph - * - * \par OpCodes for OperationDepsNodes - * - * This file defines all the "operation codes" (opcodes) used to identify - * common operation node types. The intention of these defines is to have - * a fast and reliable way of identifying the relevant nodes within a component - * without having to use fragile dynamic strings. - * - * This file is meant to be used like UI_icons.h. That is, before including - * the file, the host file must define the DEG_OPCODE(_label) macro, which - * is responsible for converting the define into whatever form is suitable. - * Therefore, it intentionally doesn't have header guards. - */ - - -/* Example macro define: */ -/* #define DEF_DEG_OPCODE(label) DEG_OPCODE_##label, */ - -/* Generic Operations ------------------------------ */ - -/* Placeholder for operations which don't need special mention */ -DEF_DEG_OPCODE(OPERATION) - -// XXX: Placeholder while porting depsgraph code -DEF_DEG_OPCODE(PLACEHOLDER) - -DEF_DEG_OPCODE(NOOP) - -/* Animation, Drivers, etc. ------------------------ */ - -/* NLA + Action */ -DEF_DEG_OPCODE(ANIMATION) - -/* Driver */ -DEF_DEG_OPCODE(DRIVER) - -/* Proxy Inherit? */ -//DEF_DEG_OPCODE(PROXY) - -/* Transform --------------------------------------- */ - -/* Transform entry point - local transforms only */ -DEF_DEG_OPCODE(TRANSFORM_LOCAL) - -/* Parenting */ -DEF_DEG_OPCODE(TRANSFORM_PARENT) - -/* Constraints */ -DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS) -//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS_INIT) -//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINT) -//DEF_DEG_OPCODE(TRANSFORM_CONSTRAINTS_DONE) - -/* Rigidbody Sim - Perform Sim */ -DEF_DEG_OPCODE(RIGIDBODY_REBUILD) -DEF_DEG_OPCODE(RIGIDBODY_SIM) - -/* Rigidbody Sim - Copy Results to Object */ -DEF_DEG_OPCODE(TRANSFORM_RIGIDBODY) - -/* Transform exitpoint */ -DEF_DEG_OPCODE(TRANSFORM_FINAL) - -/* XXX: ubereval is for temporary porting purposes only */ -DEF_DEG_OPCODE(OBJECT_UBEREVAL) - -/* Geometry ---------------------------------------- */ - -/* XXX: Placeholder - UberEval */ -DEF_DEG_OPCODE(GEOMETRY_UBEREVAL) - -/* Modifier */ -DEF_DEG_OPCODE(GEOMETRY_MODIFIER) - -/* Curve Objects - Path Calculation (used for path-following tools) */ -DEF_DEG_OPCODE(GEOMETRY_PATH) - -/* Pose -------------------------------------------- */ - -/* Init IK Trees, etc. */ -DEF_DEG_OPCODE(POSE_INIT) - -/* Free IK Trees + Compute Deform Matrices */ -DEF_DEG_OPCODE(POSE_DONE) - -/* IK/Spline Solvers */ -DEF_DEG_OPCODE(POSE_IK_SOLVER) -DEF_DEG_OPCODE(POSE_SPLINE_IK_SOLVER) - -/* Bone -------------------------------------------- */ - -/* Bone local transforms - Entrypoint */ -DEF_DEG_OPCODE(BONE_LOCAL) - -/* Pose-space conversion (includes parent + restpose) */ -DEF_DEG_OPCODE(BONE_POSE_PARENT) - -/* Constraints */ -DEF_DEG_OPCODE(BONE_CONSTRAINTS) -//DEF_DEG_OPCODE(BONE_CONSTRAINTS_INIT) -//DEF_DEG_OPCODE(BONE_CONSTRAINT) -//DEF_DEG_OPCODE(BONE_CONSTRAINTS_DONE) - -/* Bone transforms are ready - * - "READY" This (internal) noop is used to signal that all pre-IK operations are done. - * Its role is to help mediate situations where cyclic relations may otherwise form - * (i.e. one bone in chain targetting another in same chain) - * - "DONE" This noop is used to signal that the bone's final pose transform can be read by others - */ -// TODO: deform mats could get calculated in the final_transform ops... -DEF_DEG_OPCODE(BONE_READY) -DEF_DEG_OPCODE(BONE_DONE) - -/* Particles --------------------------------------- */ - -/* XXX: placeholder - Particle System eval */ -DEF_DEG_OPCODE(PSYS_EVAL) diff --git a/source/blender/depsgraph/intern/eval/deg_eval.cc b/source/blender/depsgraph/intern/eval/deg_eval.cc new file mode 100644 index 00000000000..198cd349002 --- /dev/null +++ b/source/blender/depsgraph/intern/eval/deg_eval.cc @@ -0,0 +1,409 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_eval.cc + * \ingroup depsgraph + * + * Evaluation engine entrypoints for Depsgraph Engine. + */ + +#include "intern/eval/deg_eval.h" + +#include "PIL_time.h" + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_task.h" +#include "BLI_ghash.h" + +#include "BKE_depsgraph.h" +#include "BKE_global.h" + +#include "DEG_depsgraph.h" +} /* extern "C" */ + +#include "atomic_ops.h" + +#include "intern/eval/deg_eval_debug.h" +#include "intern/eval/deg_eval_flush.h" +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph.h" +#include "util/deg_util_foreach.h" + +/* Unfinished and unused, and takes quite some pre-processing time. */ +#undef USE_EVAL_PRIORITY + +/* Use integrated debugger to keep track how much each of the nodes was + * evaluating. + */ +#undef USE_DEBUGGER + +namespace DEG { + +/* ********************** */ +/* Evaluation Entrypoints */ + +/* Forward declarations. */ +static void schedule_children(TaskPool *pool, + Depsgraph *graph, + OperationDepsNode *node, + const int layers, + const int thread_id); + +struct DepsgraphEvalState { + EvaluationContext *eval_ctx; + Depsgraph *graph; + int layers; +}; + +static void deg_task_run_func(TaskPool *pool, + void *taskdata, + int thread_id) +{ + DepsgraphEvalState *state = + reinterpret_cast<DepsgraphEvalState *>(BLI_task_pool_userdata(pool)); + OperationDepsNode *node = reinterpret_cast<OperationDepsNode *>(taskdata); + + BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled"); + + /* Should only be the case for NOOPs, which never get to this point. */ + BLI_assert(node->evaluate); + + while (true) { + /* Get context. */ + /* TODO: Who initialises this? "Init" operations aren't able to + * initialise it!!! + */ + /* TODO(sergey): We don't use component contexts at this moment. */ + /* ComponentDepsNode *comp = node->owner; */ + BLI_assert(node->owner != NULL); + + /* Since we're not leaving the thread for until the graph branches it is + * possible to have NO-OP on the way. for which evaluate() will be NULL. + * but that's all fine, we'll just scheduler it's children. + */ + if (node->evaluate) { + /* Take note of current time. */ +#ifdef USE_DEBUGGER + double start_time = PIL_check_seconds_timer(); + DepsgraphDebug::task_started(state->graph, node); +#endif + + /* Perform operation. */ + node->evaluate(state->eval_ctx); + + /* Note how long this took. */ +#ifdef USE_DEBUGGER + double end_time = PIL_check_seconds_timer(); + DepsgraphDebug::task_completed(state->graph, + node, + end_time - start_time); +#endif + } + + /* If there's only one outgoing link we try to immediately switch to + * that node evaluation, without leaving the thread. + * + * It's only doable if the child don't have extra relations or all they + * are satisfied. + * + * TODO(sergey): Checks here can be de-duplicated with the ones from + * schedule_node(), however, how to do it nicely? + */ + if (node->outlinks.size() == 1) { + DepsRelation *rel = node->outlinks[0]; + OperationDepsNode *child = (OperationDepsNode *)rel->to; + BLI_assert(child->type == DEPSNODE_TYPE_OPERATION); + if (!child->scheduled) { + int id_layers = child->owner->owner->layers; + if (!((child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 && + (id_layers & state->layers) != 0)) + { + /* Node does not need an update, so can;t continue with the + * chain and need to switch to another one by leaving the + * thread. + */ + break; + } + if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) { + BLI_assert(child->num_links_pending > 0); + atomic_sub_uint32(&child->num_links_pending, 1); + } + if (child->num_links_pending == 0) { + bool is_scheduled = atomic_fetch_and_or_uint8( + (uint8_t *)&child->scheduled, (uint8_t)true); + if (!is_scheduled) { + /* Node was not scheduled, switch to it! */ + node = child; + } + else { + /* Someone else scheduled the node, leaving us + * unemployed in this thread, we're leaving. + */ + break; + } + } + else { + /* There are other dependencies on the child, can't do + * anything in the current thread. + */ + break; + } + } + else { + /* Happens when having cyclic dependencies. + * + * Nothing to do here, single child was already scheduled, we + * can leave the thread now. + */ + break; + } + } + else { + /* TODO(sergey): It's possible to use one of the outgoing relations + * as a chain which we'll try to keep alive, but it's a bit more + * involved change. + */ + schedule_children(pool, state->graph, node, state->layers, thread_id); + break; + } + } +} + +typedef struct CalculatePengindData { + Depsgraph *graph; + int layers; +} CalculatePengindData; + +static void calculate_pending_func(void *data_v, int i) +{ + CalculatePengindData *data = (CalculatePengindData *)data_v; + Depsgraph *graph = data->graph; + int layers = data->layers; + OperationDepsNode *node = graph->operations[i]; + IDDepsNode *id_node = node->owner->owner; + + node->num_links_pending = 0; + node->scheduled = false; + + /* count number of inputs that need updates */ + if ((id_node->layers & layers) != 0 && + (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) + { + foreach (DepsRelation *rel, node->inlinks) { + if (rel->from->type == DEPSNODE_TYPE_OPERATION && + (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) + { + OperationDepsNode *from = (OperationDepsNode *)rel->from; + IDDepsNode *id_from_node = from->owner->owner; + if ((id_from_node->layers & layers) != 0 && + (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0) + { + ++node->num_links_pending; + } + } + } + } +} + +static void calculate_pending_parents(Depsgraph *graph, int layers) +{ + const int num_operations = graph->operations.size(); + const bool do_threads = num_operations > 256; + CalculatePengindData data; + data.graph = graph; + data.layers = layers; + BLI_task_parallel_range(0, + num_operations, + &data, + calculate_pending_func, + do_threads); +} + +#ifdef USE_EVAL_PRIORITY +static void calculate_eval_priority(OperationDepsNode *node) +{ + if (node->done) { + return; + } + node->done = 1; + + if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) { + /* XXX standard cost of a node, could be estimated somewhat later on */ + const float cost = 1.0f; + /* NOOP nodes have no cost */ + node->eval_priority = node->is_noop() ? cost : 0.0f; + + foreach (DepsRelation *rel, node->outlinks) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + BLI_assert(to->type == DEPSNODE_TYPE_OPERATION); + calculate_eval_priority(to); + node->eval_priority += to->eval_priority; + } + } + else { + node->eval_priority = 0.0f; + } +} +#endif + +/* Schedule a node if it needs evaluation. + * dec_parents: Decrement pending parents count, true when child nodes are + * scheduled after a task has been completed. + */ +static void schedule_node(TaskPool *pool, Depsgraph *graph, int layers, + OperationDepsNode *node, bool dec_parents, + const int thread_id) +{ + int id_layers = node->owner->owner->layers; + + if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 && + (id_layers & layers) != 0) + { + if (dec_parents) { + BLI_assert(node->num_links_pending > 0); + atomic_sub_uint32(&node->num_links_pending, 1); + } + + if (node->num_links_pending == 0) { + bool is_scheduled = atomic_fetch_and_or_uint8( + (uint8_t *)&node->scheduled, (uint8_t)true); + if (!is_scheduled) { + if (node->is_noop()) { + /* skip NOOP node, schedule children right away */ + schedule_children(pool, graph, node, layers, thread_id); + } + else { + /* children are scheduled once this task is completed */ + BLI_task_pool_push_from_thread(pool, + deg_task_run_func, + node, + false, + TASK_PRIORITY_LOW, + thread_id); + } + } + } + } +} + +static void schedule_graph(TaskPool *pool, + Depsgraph *graph, + const int layers) +{ + foreach (OperationDepsNode *node, graph->operations) { + schedule_node(pool, graph, layers, node, false, 0); + } +} + +static void schedule_children(TaskPool *pool, + Depsgraph *graph, + OperationDepsNode *node, + const int layers, + const int thread_id) +{ + foreach (DepsRelation *rel, node->outlinks) { + OperationDepsNode *child = (OperationDepsNode *)rel->to; + BLI_assert(child->type == DEPSNODE_TYPE_OPERATION); + if (child->scheduled) { + /* Happens when having cyclic dependencies. */ + continue; + } + schedule_node(pool, + graph, + layers, + child, + (rel->flag & DEPSREL_FLAG_CYCLIC) == 0, + thread_id); + } +} + +/** + * Evaluate all nodes tagged for updating, + * \warning This is usually done as part of main loop, but may also be + * called from frame-change update. + * + * \note Time sources should be all valid! + */ +void deg_evaluate_on_refresh(EvaluationContext *eval_ctx, + Depsgraph *graph, + const int layers) +{ + /* Generate base evaluation context, upon which all the others are derived. */ + // TODO: this needs both main and scene access... + + /* Nothing to update, early out. */ + if (BLI_gset_size(graph->entry_tags) == 0) { + return; + } + + /* Set time for the current graph evaluation context. */ + TimeSourceDepsNode *time_src = graph->find_time_source(); + eval_ctx->ctime = time_src->cfra; + + /* XXX could use a separate pool for each eval context */ + DepsgraphEvalState state; + state.eval_ctx = eval_ctx; + state.graph = graph; + state.layers = layers; + + TaskScheduler *task_scheduler = BLI_task_scheduler_get(); + TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state); + + if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) { + BLI_pool_set_num_threads(task_pool, 1); + } + + calculate_pending_parents(graph, layers); + + /* Clear tags. */ + foreach (OperationDepsNode *node, graph->operations) { + node->done = 0; + } + + /* Calculate priority for operation nodes. */ +#ifdef USE_EVAL_PRIORITY + foreach (OperationDepsNode *node, graph->operations) { + calculate_eval_priority(node); + } +#endif + + DepsgraphDebug::eval_begin(eval_ctx); + + schedule_graph(task_pool, graph, layers); + + BLI_task_pool_work_and_wait(task_pool); + BLI_task_pool_free(task_pool); + + DepsgraphDebug::eval_end(eval_ctx); + + /* Clear any uncleared tags - just in case. */ + deg_graph_clear_tags(graph); +} + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/eval/deg_eval.h b/source/blender/depsgraph/intern/eval/deg_eval.h new file mode 100644 index 00000000000..0d42f63433f --- /dev/null +++ b/source/blender/depsgraph/intern/eval/deg_eval.h @@ -0,0 +1,52 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/eval/deg_eval.cc + * \ingroup depsgraph + * + * Evaluation engine entrypoints for Depsgraph Engine. + */ + +#pragma once + +struct EvaluationContext; + +namespace DEG { + +struct Depsgraph; + +/** + * Evaluate all nodes tagged for updating, + * \warning This is usually done as part of main loop, but may also be + * called from frame-change update. + * + * \note Time sources should be all valid! + */ +void deg_evaluate_on_refresh(EvaluationContext *eval_ctx, + Depsgraph *graph, + const int layers); + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/eval/deg_eval_debug.cc b/source/blender/depsgraph/intern/eval/deg_eval_debug.cc new file mode 100644 index 00000000000..cfadf74da4d --- /dev/null +++ b/source/blender/depsgraph/intern/eval/deg_eval_debug.cc @@ -0,0 +1,247 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/eval/deg_eval_debug.cc + * \ingroup depsgraph + * + * Implementation of tools for debugging the depsgraph + */ + +#include "intern/eval/deg_eval_debug.h" + +extern "C" { +#include "BLI_listbase.h" +#include "BLI_ghash.h" + +#include "DEG_depsgraph_debug.h" + +#include "WM_api.h" +#include "WM_types.h" +} /* extern "C" */ + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph_intern.h" + +namespace DEG { + +DepsgraphStats *DepsgraphDebug::stats = NULL; + +static string get_component_name(eDepsNode_Type type, const string &name = "") +{ + DepsNodeFactory *factory = deg_get_node_factory(type); + if (name.empty()) { + return string(factory->tname()); + } + else { + return string(factory->tname()) + " | " + name; + } +} + +static void times_clear(DepsgraphStatsTimes ×) +{ + times.duration_last = 0.0f; +} + +static void times_add(DepsgraphStatsTimes ×, float time) +{ + times.duration_last += time; +} + +void DepsgraphDebug::eval_begin(const EvaluationContext *UNUSED(eval_ctx)) +{ + /* TODO(sergey): Stats are currently globally disabled. */ + /* verify_stats(); */ + reset_stats(); +} + +void DepsgraphDebug::eval_end(const EvaluationContext *UNUSED(eval_ctx)) +{ + WM_main_add_notifier(NC_SPACE | ND_SPACE_INFO_REPORT, NULL); +} + +void DepsgraphDebug::eval_step(const EvaluationContext *UNUSED(eval_ctx), + const char *message) +{ +#ifdef DEG_DEBUG_BUILD + if (deg_debug_eval_cb) + deg_debug_eval_cb(deg_debug_eval_userdata, message); +#else + (void)message; /* Ignored. */ +#endif +} + +void DepsgraphDebug::task_started(Depsgraph *graph, + const OperationDepsNode *node) +{ + if (stats) { + BLI_spin_lock(&graph->lock); + + ComponentDepsNode *comp = node->owner; + ID *id = comp->owner->id; + + DepsgraphStatsID *id_stats = get_id_stats(id, true); + times_clear(id_stats->times); + + /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ + if (0) { + /* XXX component name usage needs cleanup! currently mixes identifier + * and description strings! + */ + DepsgraphStatsComponent *comp_stats = + get_component_stats(id, get_component_name(comp->type, + comp->name), + true); + times_clear(comp_stats->times); + } + + BLI_spin_unlock(&graph->lock); + } +} + +void DepsgraphDebug::task_completed(Depsgraph *graph, + const OperationDepsNode *node, + double time) +{ + if (stats) { + BLI_spin_lock(&graph->lock); + + ComponentDepsNode *comp = node->owner; + ID *id = comp->owner->id; + + DepsgraphStatsID *id_stats = get_id_stats(id, true); + times_add(id_stats->times, time); + + /* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */ + if (0) { + /* XXX component name usage needs cleanup! currently mixes identifier + * and description strings! + */ + DepsgraphStatsComponent *comp_stats = + get_component_stats(id, + get_component_name(comp->type, + comp->name), + true); + times_add(comp_stats->times, time); + } + + BLI_spin_unlock(&graph->lock); + } +} + +/* ********** */ +/* Statistics */ + + +/* GHash callback */ +static void deg_id_stats_free(void *val) +{ + DepsgraphStatsID *id_stats = (DepsgraphStatsID *)val; + + if (id_stats) { + BLI_freelistN(&id_stats->components); + MEM_freeN(id_stats); + } +} + +void DepsgraphDebug::stats_init() +{ + if (!stats) { + stats = (DepsgraphStats *)MEM_callocN(sizeof(DepsgraphStats), + "Depsgraph Stats"); + stats->id_stats = BLI_ghash_new(BLI_ghashutil_ptrhash, + BLI_ghashutil_ptrcmp, + "Depsgraph ID Stats Hash"); + } +} + +void DepsgraphDebug::stats_free() +{ + if (stats) { + BLI_ghash_free(stats->id_stats, NULL, deg_id_stats_free); + MEM_freeN(stats); + stats = NULL; + } +} + +void DepsgraphDebug::verify_stats() +{ + stats_init(); +} + +void DepsgraphDebug::reset_stats() +{ + if (!stats) { + return; + } + + /* XXX this doesn't work, will immediately clear all info, + * since most depsgraph updates have none or very few updates to handle. + * + * Could consider clearing only zero-user ID blocks here + */ +// BLI_ghash_clear(stats->id_stats, NULL, deg_id_stats_free); +} + +DepsgraphStatsID *DepsgraphDebug::get_id_stats(ID *id, bool create) +{ + DepsgraphStatsID *id_stats = (DepsgraphStatsID *)BLI_ghash_lookup(stats->id_stats, id); + + if (!id_stats && create) { + id_stats = (DepsgraphStatsID *)MEM_callocN(sizeof(DepsgraphStatsID), + "Depsgraph ID Stats"); + id_stats->id = id; + + BLI_ghash_insert(stats->id_stats, id, id_stats); + } + + return id_stats; +} + +DepsgraphStatsComponent *DepsgraphDebug::get_component_stats( + DepsgraphStatsID *id_stats, + const string &name, + bool create) +{ + DepsgraphStatsComponent *comp_stats; + for (comp_stats = (DepsgraphStatsComponent *)id_stats->components.first; + comp_stats != NULL; + comp_stats = comp_stats->next) + { + if (STREQ(comp_stats->name, name.c_str())) + break; + } + if (!comp_stats && create) { + comp_stats = (DepsgraphStatsComponent *)MEM_callocN(sizeof(DepsgraphStatsComponent), + "Depsgraph Component Stats"); + BLI_strncpy(comp_stats->name, name.c_str(), sizeof(comp_stats->name)); + BLI_addtail(&id_stats->components, comp_stats); + } + return comp_stats; +} + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_debug.h b/source/blender/depsgraph/intern/eval/deg_eval_debug.h index 64b97855f57..9109019eb2d 100644 --- a/source/blender/depsgraph/intern/depsgraph_debug.h +++ b/source/blender/depsgraph/intern/eval/deg_eval_debug.h @@ -24,27 +24,26 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/intern/depsgraph_debug.h +/** \file blender/depsgraph/intern/eval/deg_eval_debug.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_DEBUG_H__ -#define __DEPSGRAPH_DEBUG_H__ +#pragma once -#include "depsgraph_types.h" +#include "intern/depsgraph_types.h" -extern "C" { -#include "BKE_global.h" -} +struct ID; +struct EvaluationContext; struct DepsgraphStats; struct DepsgraphStatsID; struct DepsgraphStatsComponent; -struct DepsgraphSettings; -struct EvaluationContext; -struct OperationDepsNode; + +namespace DEG { struct Depsgraph; +struct DepsgraphSettings; +struct OperationDepsNode; struct DepsgraphDebug { static DepsgraphStats *stats; @@ -77,11 +76,4 @@ struct DepsgraphDebug { } }; -#define DEG_DEBUG_PRINTF(...) \ - { \ - if (G.debug & G_DEBUG_DEPSGRAPH) { \ - fprintf(stderr, __VA_ARGS__); \ - } \ - } \ - -#endif /* __DEPSGRAPH_DEBUG_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc new file mode 100644 index 00000000000..87313826763 --- /dev/null +++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc @@ -0,0 +1,211 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_tag.cc + * \ingroup depsgraph + * + * Core routines for how the Depsgraph works. + */ + +#include "intern/eval/deg_eval_flush.h" + +// TODO(sergey): Use some sort of wrapper. +#include <queue> + +extern "C" { +#include "DNA_object_types.h" + +#include "BLI_utildefines.h" +#include "BLI_task.h" +#include "BLI_ghash.h" + +#include "DEG_depsgraph.h" +} /* extern "C" */ + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" + +namespace DEG { + +namespace { + +// TODO(sergey): De-duplicate with depsgraph_tag,cc +void lib_id_recalc_tag(Main *bmain, ID *id) +{ + id->tag |= LIB_TAG_ID_RECALC; + DEG_id_type_tag(bmain, GS(id->name)); +} + +void lib_id_recalc_data_tag(Main *bmain, ID *id) +{ + id->tag |= LIB_TAG_ID_RECALC_DATA; + DEG_id_type_tag(bmain, GS(id->name)); +} + +} /* namespace */ + +typedef std::queue<OperationDepsNode *> FlushQueue; + +static void flush_init_func(void *data_v, int i) +{ + /* ID node's done flag is used to avoid multiple editors update + * for the same ID. + */ + Depsgraph *graph = (Depsgraph *)data_v; + OperationDepsNode *node = graph->operations[i]; + IDDepsNode *id_node = node->owner->owner; + id_node->done = 0; + node->scheduled = false; + node->owner->flags &= ~DEPSCOMP_FULLY_SCHEDULED; +} + +/* Flush updates from tagged nodes outwards until all affected nodes + * are tagged. + */ +void deg_graph_flush_updates(Main *bmain, Depsgraph *graph) +{ + /* Sanity check. */ + if (graph == NULL) { + return; + } + + /* Nothing to update, early out. */ + if (BLI_gset_size(graph->entry_tags) == 0) { + return; + } + + /* TODO(sergey): With a bit of flag magic we can get rid of this + * extra loop. + */ + const int num_operations = graph->operations.size(); + const bool do_threads = num_operations > 256; + BLI_task_parallel_range(0, + num_operations, + graph, + flush_init_func, + do_threads); + + FlushQueue queue; + /* Starting from the tagged "entry" nodes, flush outwards... */ + /* NOTE: Also need to ensure that for each of these, there is a path back to + * root, or else they won't be done. + * NOTE: Count how many nodes we need to handle - entry nodes may be + * component nodes which don't count for this purpose! + */ + GSET_FOREACH_BEGIN(OperationDepsNode *, node, graph->entry_tags) + { + IDDepsNode *id_node = node->owner->owner; + queue.push(node); + if (id_node->done == 0) { + deg_editors_id_update(bmain, id_node->id); + id_node->done = 1; + } + node->scheduled = true; + } + GSET_FOREACH_END(); + + while (!queue.empty()) { + OperationDepsNode *node = queue.front(); + queue.pop(); + + IDDepsNode *id_node = node->owner->owner; + lib_id_recalc_tag(bmain, id_node->id); + /* TODO(sergey): For until we've got proper data nodes in the graph. */ + lib_id_recalc_data_tag(bmain, id_node->id); + + ID *id = id_node->id; + /* This code is used to preserve those areas which does direct + * object update, + * + * Plus it ensures visibility changes and relations and layers + * visibility update has proper flags to work with. + */ + if (GS(id->name) == ID_OB) { + Object *object = (Object *)id; + ComponentDepsNode *comp_node = node->owner; + if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { + object->recalc |= OB_RECALC_TIME; + } + else if (comp_node->type == DEPSNODE_TYPE_TRANSFORM) { + object->recalc |= OB_RECALC_OB; + } + else { + object->recalc |= OB_RECALC_DATA; + } + } + + /* Flush to nodes along links... */ + foreach (DepsRelation *rel, node->outlinks) { + OperationDepsNode *to_node = (OperationDepsNode *)rel->to; + if (to_node->scheduled == false) { + to_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE; + queue.push(to_node); + to_node->scheduled = true; + if (id_node->done == 0) { + deg_editors_id_update(bmain, id_node->id); + id_node->done = 1; + } + } + } + + /* TODO(sergey): For until incremental updates are possible + * witin a component at least we tag the whole component + * for update. + */ + ComponentDepsNode *component = node->owner; + if ((component->flags & DEPSCOMP_FULLY_SCHEDULED) == 0) { + foreach (OperationDepsNode *op, component->operations) { + op->flag |= DEPSOP_FLAG_NEEDS_UPDATE; + } + component->flags |= DEPSCOMP_FULLY_SCHEDULED; + } + } +} + +static void graph_clear_func(void *data_v, int i) +{ + Depsgraph *graph = (Depsgraph *)data_v; + OperationDepsNode *node = graph->operations[i]; + /* Clear node's "pending update" settings. */ + node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE); +} + +/* Clear tags from all operation nodes. */ +void deg_graph_clear_tags(Depsgraph *graph) +{ + /* Go over all operation nodes, clearing tags. */ + const int num_operations = graph->operations.size(); + const bool do_threads = num_operations > 256; + BLI_task_parallel_range(0, num_operations, graph, graph_clear_func, do_threads); + /* Clear any entry tags which haven't been flushed. */ + BLI_gset_clear(graph->entry_tags, NULL); +} + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.h b/source/blender/depsgraph/intern/eval/deg_eval_flush.h new file mode 100644 index 00000000000..8912aebee7d --- /dev/null +++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.h @@ -0,0 +1,49 @@ +/* + * ***** 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) 2013 Blender Foundation. + * All rights reserved. + * + * Original Author: Joshua Leung + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/eval/deg_eval_flush.cc + * \ingroup depsgraph + * + * Core routines for how the Depsgraph works. + */ + +#pragma once + +struct Main; + +namespace DEG { + +struct Depsgraph; + +/* Flush updates from tagged nodes outwards until all affected nodes + * are tagged. + */ +void deg_graph_flush_updates(struct Main *bmain, struct Depsgraph *graph); + +/* Clear tags from all operation nodes. */ +void deg_graph_clear_tags(struct Depsgraph *graph); + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode.cc b/source/blender/depsgraph/intern/nodes/deg_node.cc index ca9a7d9bac8..78293f7f483 100644 --- a/source/blender/depsgraph/intern/depsnode.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node.cc @@ -28,10 +28,13 @@ * \ingroup depsgraph */ +#include "intern/nodes/deg_node.h" + #include <stdio.h> #include <string.h> #include "BLI_utildefines.h" +#include "BLI_ghash.h" extern "C" { #include "DNA_ID.h" @@ -42,11 +45,13 @@ extern "C" { #include "DEG_depsgraph.h" } -#include "depsnode.h" /* own include */ -#include "depsnode_component.h" -#include "depsnode_operation.h" -#include "depsgraph_intern.h" -#include "depsgraph_util_foreach.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" +#include "util/deg_util_hash.h" + +namespace DEG { /* *************** */ /* Node Management */ @@ -67,7 +72,7 @@ DepsNode::TypeInfo::TypeInfo(eDepsNode_Type type, const char *tname) DepsNode::DepsNode() { - this->name[0] = '\0'; + name[0] = '\0'; } DepsNode::~DepsNode() @@ -77,11 +82,9 @@ DepsNode::~DepsNode() * when we're trying to free same link from both it's sides. We don't have * dangling links so this is not a problem from memory leaks point of view. */ - DEPSNODE_RELATIONS_ITER_BEGIN(this->inlinks, rel) - { + foreach (DepsRelation *rel, inlinks) { OBJECT_GUARDED_DELETE(rel, DepsRelation); } - DEPSNODE_RELATIONS_ITER_END; } @@ -122,7 +125,7 @@ RootDepsNode::~RootDepsNode() TimeSourceDepsNode *RootDepsNode::add_time_source(const string &name) { if (!time_source) { - DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_TIMESOURCE); + DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_TIMESOURCE); time_source = (TimeSourceDepsNode *)factory->create_node(NULL, "", name); /*time_source->owner = this;*/ // XXX } @@ -139,6 +142,36 @@ static DepsNodeFactoryImpl<TimeSourceDepsNode> DNTI_TIMESOURCE; /* ID Node ================================================ */ +static unsigned int id_deps_node_hash_key(const void *key_v) +{ + const IDDepsNode::ComponentIDKey *key = + reinterpret_cast<const IDDepsNode::ComponentIDKey *>(key_v); + return hash_combine(BLI_ghashutil_uinthash(key->type), + BLI_ghashutil_strhash_p(key->name.c_str())); +} + +static bool id_deps_node_hash_key_cmp(const void *a, const void *b) +{ + const IDDepsNode::ComponentIDKey *key_a = + reinterpret_cast<const IDDepsNode::ComponentIDKey *>(a); + const IDDepsNode::ComponentIDKey *key_b = + reinterpret_cast<const IDDepsNode::ComponentIDKey *>(b); + return !(*key_a == *key_b); +} + +static void id_deps_node_hash_key_free(void *key_v) +{ + typedef IDDepsNode::ComponentIDKey ComponentIDKey; + ComponentIDKey *key = reinterpret_cast<ComponentIDKey *>(key_v); + OBJECT_GUARDED_DELETE(key, ComponentIDKey); +} + +static void id_deps_node_hash_value_free(void *value_v) +{ + ComponentDepsNode *comp_node = reinterpret_cast<ComponentDepsNode *>(value_v); + OBJECT_GUARDED_DELETE(comp_node, ComponentDepsNode); +} + /* Initialize 'id' node - from pointer data given. */ void IDDepsNode::init(const ID *id, const string &UNUSED(subdata)) { @@ -148,6 +181,10 @@ void IDDepsNode::init(const ID *id, const string &UNUSED(subdata)) this->layers = (1 << 20) - 1; this->eval_flags = 0; + components = BLI_ghash_new(id_deps_node_hash_key, + id_deps_node_hash_key_cmp, + "Depsgraph id components hash"); + /* NOTE: components themselves are created if/when needed. * This prevents problems with components getting added * twice if an ID-Ref needs to be created to house it... @@ -158,51 +195,27 @@ void IDDepsNode::init(const ID *id, const string &UNUSED(subdata)) IDDepsNode::~IDDepsNode() { clear_components(); -} - -/* Copy 'id' node. */ -void IDDepsNode::copy(DepsgraphCopyContext *dcc, const IDDepsNode *src) -{ - (void)src; /* Ignored. */ - /* Iterate over items in original hash, adding them to new hash. */ - for (IDDepsNode::ComponentMap::const_iterator it = this->components.begin(); - it != this->components.end(); - ++it) - { - /* Get current <type : component> mapping. */ - ComponentIDKey c_key = it->first; - DepsNode *old_component = it->second; - - /* Make a copy of component. */ - ComponentDepsNode *component = (ComponentDepsNode *)DEG_copy_node(dcc, old_component); - - /* Add new node to hash... */ - this->components[c_key] = component; - } - - // TODO: perform a second loop to fix up links? - BLI_assert(!"Not expected to be used"); + BLI_ghash_free(components, id_deps_node_hash_key_free, NULL); } ComponentDepsNode *IDDepsNode::find_component(eDepsNode_Type type, const string &name) const { ComponentIDKey key(type, name); - ComponentMap::const_iterator it = components.find(key); - return it != components.end() ? it->second : NULL; + return reinterpret_cast<ComponentDepsNode *>(BLI_ghash_lookup(components, &key)); } ComponentDepsNode *IDDepsNode::add_component(eDepsNode_Type type, const string &name) { - ComponentIDKey key(type, name); ComponentDepsNode *comp_node = find_component(type, name); if (!comp_node) { - DepsNodeFactory *factory = DEG_get_node_factory(type); + DepsNodeFactory *factory = deg_get_node_factory(type); comp_node = (ComponentDepsNode *)factory->create_node(this->id, "", name); /* Register. */ - this->components[key] = comp_node; + ComponentIDKey *key = OBJECT_GUARDED_NEW(ComponentIDKey, type, name); + BLI_ghash_insert(components, key, comp_node); comp_node->owner = this; } return comp_node; @@ -210,34 +223,28 @@ ComponentDepsNode *IDDepsNode::add_component(eDepsNode_Type type, void IDDepsNode::remove_component(eDepsNode_Type type, const string &name) { - ComponentIDKey key(type, name); ComponentDepsNode *comp_node = find_component(type, name); if (comp_node) { /* Unregister. */ - this->components.erase(key); - OBJECT_GUARDED_DELETE(comp_node, ComponentDepsNode); + ComponentIDKey key(type, name); + BLI_ghash_remove(components, + &key, + id_deps_node_hash_key_free, + id_deps_node_hash_value_free); } } void IDDepsNode::clear_components() { - for (ComponentMap::const_iterator it = components.begin(); - it != components.end(); - ++it) - { - ComponentDepsNode *comp_node = it->second; - OBJECT_GUARDED_DELETE(comp_node, ComponentDepsNode); - } - components.clear(); + BLI_ghash_clear(components, + id_deps_node_hash_key_free, + id_deps_node_hash_value_free); } void IDDepsNode::tag_update(Depsgraph *graph) { - for (ComponentMap::const_iterator it = components.begin(); - it != components.end(); - ++it) + GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, components) { - ComponentDepsNode *comp_node = it->second; /* TODO(sergey): What about drievrs? */ bool do_component_tag = comp_node->type != DEPSNODE_TYPE_ANIMATION; if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { @@ -251,6 +258,16 @@ void IDDepsNode::tag_update(Depsgraph *graph) comp_node->tag_update(graph); } } + GHASH_FOREACH_END(); +} + +void IDDepsNode::finalize_build() +{ + GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, components) + { + comp_node->finalize_build(); + } + GHASH_FOREACH_END(); } DEG_DEPSNODE_DEFINE(IDDepsNode, DEPSNODE_TYPE_ID_REF, "ID Node"); @@ -278,31 +295,21 @@ SubgraphDepsNode::~SubgraphDepsNode() // XXX: prune these flags a bit... if ((this->flag & SUBGRAPH_FLAG_FIRSTREF) || !(this->flag & SUBGRAPH_FLAG_SHARED)) { /* Free the referenced graph. */ - DEG_graph_free(this->graph); - this->graph = NULL; + DEG_graph_free(reinterpret_cast< ::Depsgraph* >(graph)); + graph = NULL; } } -/* Copy 'subgraph' node - Assume that the subgraph doesn't get copied for now... */ -void SubgraphDepsNode::copy(DepsgraphCopyContext * /*dcc*/, - const SubgraphDepsNode * /*src*/) -{ - //const SubgraphDepsNode *src_node = (const SubgraphDepsNode *)src; - //SubgraphDepsNode *dst_node = (SubgraphDepsNode *)dst; - - /* for now, subgraph itself isn't copied... */ - BLI_assert(!"Not expected to be used"); -} - DEG_DEPSNODE_DEFINE(SubgraphDepsNode, DEPSNODE_TYPE_SUBGRAPH, "Subgraph Node"); static DepsNodeFactoryImpl<SubgraphDepsNode> DNTI_SUBGRAPH; - -void DEG_register_base_depsnodes() +void deg_register_base_depsnodes() { - DEG_register_node_typeinfo(&DNTI_ROOT); - DEG_register_node_typeinfo(&DNTI_TIMESOURCE); + deg_register_node_typeinfo(&DNTI_ROOT); + deg_register_node_typeinfo(&DNTI_TIMESOURCE); - DEG_register_node_typeinfo(&DNTI_ID_REF); - DEG_register_node_typeinfo(&DNTI_SUBGRAPH); + deg_register_node_typeinfo(&DNTI_ID_REF); + deg_register_node_typeinfo(&DNTI_SUBGRAPH); } + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode.h b/source/blender/depsgraph/intern/nodes/deg_node.h index 4a464955384..d79d3d2348d 100644 --- a/source/blender/depsgraph/intern/depsnode.h +++ b/source/blender/depsgraph/intern/nodes/deg_node.h @@ -28,21 +28,18 @@ * \ingroup depsgraph */ -#ifndef __DEPSNODE_H__ -#define __DEPSNODE_H__ +#pragma once -#include "depsgraph_types.h" - -#include "depsgraph_util_hash.h" -#include "depsgraph_util_map.h" -#include "depsgraph_util_set.h" +#include "intern/depsgraph_types.h" struct ID; +struct GHash; struct Scene; +namespace DEG { + struct Depsgraph; struct DepsRelation; -struct DepsgraphCopyContext; struct OperationDepsNode; /* *********************************** */ @@ -94,8 +91,6 @@ struct DepsNode { virtual void init(const ID * /*id*/, const string &/*subdata*/) {} - virtual void copy(DepsgraphCopyContext * /*dcc*/, - const DepsNode * /*src*/) {} virtual void tag_update(Depsgraph * /*graph*/) {} @@ -160,24 +155,7 @@ struct IDDepsNode : public DepsNode { string name; }; - /* XXX can't specialize std::hash for this purpose, because ComponentIDKey is - * a nested type ... - * - * http://stackoverflow.com/a/951245 - */ - struct component_key_hash { - bool operator() (const ComponentIDKey &key) const - { - return hash_combine(hash<int>()(key.type), hash<string>()(key.name)); - } - }; - - typedef unordered_map<ComponentIDKey, - ComponentDepsNode *, - component_key_hash> ComponentMap; - void init(const ID *id, const string &subdata); - void copy(DepsgraphCopyContext *dcc, const IDDepsNode *src); ~IDDepsNode(); ComponentDepsNode *find_component(eDepsNode_Type type, @@ -189,11 +167,13 @@ struct IDDepsNode : public DepsNode { void tag_update(Depsgraph *graph); + void finalize_build(); + /* ID Block referenced. */ ID *id; /* Hash to make it faster to look up components. */ - ComponentMap components; + GHash *components; /* Layers of this node with accumulated layers of it's output relations. */ int layers; @@ -210,7 +190,6 @@ struct IDDepsNode : public DepsNode { /* Subgraph Reference. */ struct SubgraphDepsNode : public DepsNode { void init(const ID *id, const string &subdata); - void copy(DepsgraphCopyContext *dcc, const SubgraphDepsNode *src); ~SubgraphDepsNode(); /* Instanced graph. */ @@ -243,6 +222,6 @@ typedef enum eSubgraphRef_Flag { SUBGRAPH_FLAG_FIRSTREF = (1 << 1), } eSubgraphRef_Flag; -void DEG_register_base_depsnodes(); +void deg_register_base_depsnodes(); -#endif /* __DEPSNODE_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode_component.cc b/source/blender/depsgraph/intern/nodes/deg_node_component.cc index a47a0d29228..d18047c5112 100644 --- a/source/blender/depsgraph/intern/depsnode_component.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node_component.cc @@ -28,6 +28,8 @@ * \ingroup depsgraph */ +#include "intern/nodes/deg_node_component.h" + #include <stdio.h> #include <string.h> @@ -39,20 +41,56 @@ extern "C" { #include "BKE_action.h" } /* extern "C" */ -#include "depsnode_component.h" /* own include */ -#include "depsnode_operation.h" -#include "depsgraph_intern.h" +#include "intern/nodes/deg_node_operation.h" +#include "intern/depsgraph_intern.h" +#include "util/deg_util_foreach.h" +#include "util/deg_util_hash.h" + +namespace DEG { /* *********** */ /* Outer Nodes */ /* Standard Component Methods ============================= */ +static unsigned int comp_node_hash_key(const void *key_v) +{ + const ComponentDepsNode::OperationIDKey *key = + reinterpret_cast<const ComponentDepsNode::OperationIDKey *>(key_v); + return hash_combine(BLI_ghashutil_uinthash(key->opcode), + BLI_ghashutil_strhash_p(key->name.c_str())); +} + +static bool comp_node_hash_key_cmp(const void *a, const void *b) +{ + const ComponentDepsNode::OperationIDKey *key_a = + reinterpret_cast<const ComponentDepsNode::OperationIDKey *>(a); + const ComponentDepsNode::OperationIDKey *key_b = + reinterpret_cast<const ComponentDepsNode::OperationIDKey *>(b); + return !(*key_a == *key_b); +} + +static void comp_node_hash_key_free(void *key_v) +{ + typedef ComponentDepsNode::OperationIDKey OperationIDKey; + OperationIDKey *key = reinterpret_cast<OperationIDKey *>(key_v); + OBJECT_GUARDED_DELETE(key, OperationIDKey); +} + +static void comp_node_hash_value_free(void *value_v) +{ + OperationDepsNode *op_node = reinterpret_cast<OperationDepsNode *>(value_v); + OBJECT_GUARDED_DELETE(op_node, OperationDepsNode); +} + ComponentDepsNode::ComponentDepsNode() : entry_operation(NULL), exit_operation(NULL), flags(0) { + operations_map = BLI_ghash_new(comp_node_hash_key, + comp_node_hash_key_cmp, + "Depsgraph id hash"); } /* Initialize 'component' node - from pointer data given */ @@ -63,37 +101,15 @@ void ComponentDepsNode::init(const ID * /*id*/, // XXX: maybe this needs a special API? } -/* Copy 'component' node */ -void ComponentDepsNode::copy(DepsgraphCopyContext * /*dcc*/, - const ComponentDepsNode * /*src*/) -{ -#if 0 // XXX: remove all this - /* duplicate list of operation nodes */ - this->operations.clear(); - - for (OperationMap::const_iterator it = src->operations.begin(); it != src->operations.end(); ++it) { - const string &pchan_name = it->first; - OperationDepsNode *src_op = it->second; - - /* recursive copy */ - DepsNodeFactory *factory = DEG_node_get_factory(src_op); - OperationDepsNode *dst_op = (OperationDepsNode *)factory->copy_node(dcc, src_op); - this->operations[pchan_name] = dst_op; - - /* fix links... */ - // ... - } - - /* copy evaluation contexts */ - // -#endif - BLI_assert(!"Not expected to be called"); -} - /* Free 'component' node */ ComponentDepsNode::~ComponentDepsNode() { clear_operations(); + if (operations_map != NULL) { + BLI_ghash_free(operations_map, + comp_node_hash_key_free, + comp_node_hash_value_free); + } } string ComponentDepsNode::identifier() const @@ -108,10 +124,9 @@ string ComponentDepsNode::identifier() const OperationDepsNode *ComponentDepsNode::find_operation(OperationIDKey key) const { - OperationMap::const_iterator it = this->operations.find(key); - - if (it != this->operations.end()) { - return it->second; + OperationDepsNode *node = reinterpret_cast<OperationDepsNode *>(BLI_ghash_lookup(operations_map, &key)); + if (node != NULL) { + return node; } else { fprintf(stderr, "%s: find_operation(%s) failed\n", @@ -129,11 +144,7 @@ OperationDepsNode *ComponentDepsNode::find_operation(eDepsOperation_Code opcode, OperationDepsNode *ComponentDepsNode::has_operation(OperationIDKey key) const { - OperationMap::const_iterator it = this->operations.find(key); - if (it != this->operations.end()) { - return it->second; - } - return NULL; + return reinterpret_cast<OperationDepsNode *>(BLI_ghash_lookup(operations_map, &key)); } OperationDepsNode *ComponentDepsNode::has_operation(eDepsOperation_Code opcode, @@ -147,12 +158,12 @@ OperationDepsNode *ComponentDepsNode::add_operation(eDepsOperation_Type optype, { OperationDepsNode *op_node = has_operation(opcode, name); if (!op_node) { - DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_OPERATION); + DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_OPERATION); op_node = (OperationDepsNode *)factory->create_node(this->owner->id, "", name); /* register opnode in this component's operation set */ - OperationIDKey key(opcode, name); - this->operations[key] = op_node; + OperationIDKey *key = OBJECT_GUARDED_NEW(OperationIDKey, opcode, name); + BLI_ghash_insert(operations_map, key, op_node); /* set as entry/exit node of component (if appropriate) */ if (optype == DEPSOP_TYPE_INIT) { @@ -185,18 +196,22 @@ OperationDepsNode *ComponentDepsNode::add_operation(eDepsOperation_Type optype, void ComponentDepsNode::remove_operation(eDepsOperation_Code opcode, const string &name) { - OperationDepsNode *op_node = find_operation(opcode, name); - if (op_node) { - /* unregister */ - this->operations.erase(OperationIDKey(opcode, name)); - OBJECT_GUARDED_DELETE(op_node, OperationDepsNode); - } + /* unregister */ + OperationIDKey key(opcode, name); + BLI_ghash_remove(operations_map, + &key, + comp_node_hash_key_free, + comp_node_hash_key_free); } void ComponentDepsNode::clear_operations() { - for (OperationMap::const_iterator it = operations.begin(); it != operations.end(); ++it) { - OperationDepsNode *op_node = it->second; + if (operations_map != NULL) { + BLI_ghash_clear(operations_map, + comp_node_hash_key_free, + comp_node_hash_value_free); + } + foreach (OperationDepsNode *op_node, operations) { OBJECT_GUARDED_DELETE(op_node, OperationDepsNode); } operations.clear(); @@ -208,30 +223,71 @@ void ComponentDepsNode::tag_update(Depsgraph *graph) if (entry_op != NULL && entry_op->flag & DEPSOP_FLAG_NEEDS_UPDATE) { return; } - for (OperationMap::const_iterator it = operations.begin(); it != operations.end(); ++it) { - OperationDepsNode *op_node = it->second; + foreach (OperationDepsNode *op_node, operations) { op_node->tag_update(graph); } } OperationDepsNode *ComponentDepsNode::get_entry_operation() { - if (entry_operation) + if (entry_operation) { return entry_operation; - else if (operations.size() == 1) - return operations.begin()->second; + } + else if (operations_map != NULL && BLI_ghash_size(operations_map) == 1) { + OperationDepsNode *op_node = NULL; + /* TODO(sergey): This is somewhat slow. */ + GHASH_FOREACH_BEGIN(OperationDepsNode *, tmp, operations_map) + { + op_node = tmp; + } + GHASH_FOREACH_END(); + /* Cache for the subsequent usage. */ + entry_operation = op_node; + return op_node; + } + else if(operations.size() == 1) { + return operations[0]; + } return NULL; } OperationDepsNode *ComponentDepsNode::get_exit_operation() { - if (exit_operation) + if (exit_operation) { return exit_operation; - else if (operations.size() == 1) - return operations.begin()->second; + } + else if (operations_map != NULL && BLI_ghash_size(operations_map) == 1) { + OperationDepsNode *op_node = NULL; + /* TODO(sergey): This is somewhat slow. */ + GHASH_FOREACH_BEGIN(OperationDepsNode *, tmp, operations_map) + { + op_node = tmp; + } + GHASH_FOREACH_END(); + /* Cache for the subsequent usage. */ + exit_operation = op_node; + return op_node; + } + else if(operations.size() == 1) { + return operations[0]; + } return NULL; } +void ComponentDepsNode::finalize_build() +{ + operations.reserve(BLI_ghash_size(operations_map)); + GHASH_FOREACH_BEGIN(OperationDepsNode *, op_node, operations_map) + { + operations.push_back(op_node); + } + GHASH_FOREACH_END(); + BLI_ghash_free(operations_map, + comp_node_hash_key_free, + NULL); + operations_map = NULL; +} + /* Parameter Component Defines ============================ */ DEG_DEPSNODE_DEFINE(ParametersComponentDepsNode, DEPSNODE_TYPE_PARAMETERS, "Parameters Component"); @@ -302,18 +358,20 @@ static DepsNodeFactoryImpl<ShadingComponentDepsNode> DNTI_SHADING; /* Node Types Register =================================== */ -void DEG_register_component_depsnodes() +void deg_register_component_depsnodes() { - DEG_register_node_typeinfo(&DNTI_PARAMETERS); - DEG_register_node_typeinfo(&DNTI_PROXY); - DEG_register_node_typeinfo(&DNTI_ANIMATION); - DEG_register_node_typeinfo(&DNTI_TRANSFORM); - DEG_register_node_typeinfo(&DNTI_GEOMETRY); - DEG_register_node_typeinfo(&DNTI_SEQUENCER); - - DEG_register_node_typeinfo(&DNTI_EVAL_POSE); - DEG_register_node_typeinfo(&DNTI_BONE); - - DEG_register_node_typeinfo(&DNTI_EVAL_PARTICLES); - DEG_register_node_typeinfo(&DNTI_SHADING); + deg_register_node_typeinfo(&DNTI_PARAMETERS); + deg_register_node_typeinfo(&DNTI_PROXY); + deg_register_node_typeinfo(&DNTI_ANIMATION); + deg_register_node_typeinfo(&DNTI_TRANSFORM); + deg_register_node_typeinfo(&DNTI_GEOMETRY); + deg_register_node_typeinfo(&DNTI_SEQUENCER); + + deg_register_node_typeinfo(&DNTI_EVAL_POSE); + deg_register_node_typeinfo(&DNTI_BONE); + + deg_register_node_typeinfo(&DNTI_EVAL_PARTICLES); + deg_register_node_typeinfo(&DNTI_SHADING); } + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode_component.h b/source/blender/depsgraph/intern/nodes/deg_node_component.h index 7f44c0ed03f..17e6e7e0030 100644 --- a/source/blender/depsgraph/intern/depsnode_component.h +++ b/source/blender/depsgraph/intern/nodes/deg_node_component.h @@ -28,21 +28,22 @@ * \ingroup depsgraph */ -#ifndef __DEPSNODE_COMPONENT_H__ -#define __DEPSNODE_COMPONENT_H__ +#pragma once -#include "depsnode.h" +#include "intern/nodes/deg_node.h" -#include "depsgraph_util_hash.h" -#include "depsgraph_util_map.h" -#include "depsgraph_util_set.h" +#include "BLI_utildefines.h" +#include "BLI_string.h" struct ID; struct bPoseChannel; +struct GHash; -struct Depsgraph; -struct DepsgraphCopyContext; struct EvaluationContext; + +namespace DEG { + +struct Depsgraph; struct OperationDepsNode; struct BoneComponentDepsNode; @@ -75,7 +76,7 @@ struct ComponentDepsNode : public DepsNode { string identifier() const { char codebuf[5]; - sprintf(codebuf, "%d", opcode); + BLI_snprintf(codebuf, sizeof(codebuf), "%d", opcode); return string("OperationIDKey(") + codebuf + ", " + name + ")"; } @@ -86,47 +87,41 @@ struct ComponentDepsNode : public DepsNode { } }; - /* XXX can't specialize std::hash for this purpose, because ComponentKey is a nested type ... - * http://stackoverflow.com/a/951245 - */ - struct operation_key_hash { - bool operator() (const OperationIDKey &key) const - { - return hash_combine(hash<int>()(key.opcode), hash<string>()(key.name)); - } - }; - /* Typedef for container of operations */ - typedef unordered_map<OperationIDKey, OperationDepsNode *, operation_key_hash> OperationMap; - - ComponentDepsNode(); ~ComponentDepsNode(); void init(const ID *id, const string &subdata); - void copy(DepsgraphCopyContext *dcc, const ComponentDepsNode *src); string identifier() const; /* Find an existing operation, will throw an assert() if it does not exist. */ OperationDepsNode *find_operation(OperationIDKey key) const; - OperationDepsNode *find_operation(eDepsOperation_Code opcode, const string &name) const; + OperationDepsNode *find_operation(eDepsOperation_Code opcode, + const string &name) const; /* Check operation exists and return it. */ OperationDepsNode *has_operation(OperationIDKey key) const; - OperationDepsNode *has_operation(eDepsOperation_Code opcode, const string &name) const; + OperationDepsNode *has_operation(eDepsOperation_Code opcode, + const string &name) const; /** * Create a new node for representing an operation and add this to graph - * \warning If an existing node is found, it will be modified. This helps when node may - * have been partially created earlier (e.g. parent ref before parent item is added) + * \warning If an existing node is found, it will be modified. This helps + * when node may have been partially created earlier (e.g. parent ref before + * parent item is added) * - * \param type: Operation node type (corresponding to context/component that it operates in) - * \param optype: Role that operation plays within component (i.e. where in eval process) + * \param type: Operation node type (corresponding to context/component that + * it operates in) + * \param optype: Role that operation plays within component + * (i.e. where in eval process) * \param op: The operation to perform * \param name: Identifier for operation - used to find/locate it again */ - OperationDepsNode *add_operation(eDepsOperation_Type optype, DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &name); + OperationDepsNode *add_operation(eDepsOperation_Type optype, + DepsEvalOperationCb op, + eDepsOperation_Code opcode, + const string &name); void remove_operation(eDepsOperation_Code opcode, const string &name); void clear_operations(); @@ -135,9 +130,13 @@ struct ComponentDepsNode : public DepsNode { /* Evaluation Context Management .................. */ - /* Initialize component's evaluation context used for the specified purpose */ + /* Initialize component's evaluation context used for the specified + * purpose. + */ virtual bool eval_context_init(EvaluationContext * /*eval_ctx*/) { return false; } - /* Free data in component's evaluation context which is used for the specified purpose + /* Free data in component's evaluation context which is used for + * the specified purpose + * * NOTE: this does not free the actual context in question */ virtual void eval_context_free(EvaluationContext * /*eval_ctx*/) {} @@ -145,9 +144,22 @@ struct ComponentDepsNode : public DepsNode { OperationDepsNode *get_entry_operation(); OperationDepsNode *get_exit_operation(); + void finalize_build(); + IDDepsNode *owner; - OperationMap operations; /* inner nodes for this component */ + /* ** Inner nodes for this component ** */ + + /* Operations stored as a hash map, for faster build. + * This hash map will be freed when graph is fully built. + */ + GHash *operations_map; + + /* This is a "normal" list of operations, used by evaluation + * and other routines after construction. + */ + vector<OperationDepsNode *> operations; + OperationDepsNode *entry_operation; OperationDepsNode *exit_operation; @@ -204,6 +216,6 @@ struct ShadingComponentDepsNode : public ComponentDepsNode { }; -void DEG_register_component_depsnodes(); +void deg_register_component_depsnodes(); -#endif /* __DEPSNODE_COMPONENT_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode_operation.cc b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc index 6fe0faef788..a9f9703bb3b 100644 --- a/source/blender/depsgraph/intern/depsnode_operation.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc @@ -28,28 +28,19 @@ * \ingroup depsgraph */ +#include "intern/nodes/deg_node_operation.h" + #include "MEM_guardedalloc.h" extern "C" { #include "BLI_utildefines.h" } /* extern "C" */ -#include "depsnode_operation.h" /* own include */ -#include "depsnode_component.h" -#include "depsgraph.h" -#include "depsgraph_intern.h" - -/* ******************************************************************* */ -/* OpNode Identifiers Array - Exported to other depsgraph files too... */ +#include "intern/depsgraph.h" +#include "intern/depsgraph_intern.h" +#include "util/deg_util_hash.h" -/* identifiers for operations */ -const char *DEG_OPNAMES[] = { -#define DEF_DEG_OPCODE(label) #label, -#include "depsnode_opcodes.h" -#undef DEF_DEG_OPCODE - - "<Invalid>" -}; +namespace DEG { /* *********** */ /* Inner Nodes */ @@ -67,7 +58,6 @@ OperationDepsNode::~OperationDepsNode() string OperationDepsNode::identifier() const { - BLI_assert((opcode > 0) && (opcode < ARRAY_SIZE(DEG_OPNAMES))); return string(DEG_OPNAMES[opcode]) + "(" + name + ")"; } @@ -99,7 +89,9 @@ void OperationDepsNode::tag_update(Depsgraph *graph) DEG_DEPSNODE_DEFINE(OperationDepsNode, DEPSNODE_TYPE_OPERATION, "Operation"); static DepsNodeFactoryImpl<OperationDepsNode> DNTI_OPERATION; -void DEG_register_operation_depsnodes() +void deg_register_operation_depsnodes() { - DEG_register_node_typeinfo(&DNTI_OPERATION); + deg_register_node_typeinfo(&DNTI_OPERATION); } + +} // namespace DEG diff --git a/source/blender/depsgraph/intern/depsnode_operation.h b/source/blender/depsgraph/intern/nodes/deg_node_operation.h index 8d819319f4a..f03078fc3db 100644 --- a/source/blender/depsgraph/intern/depsnode_operation.h +++ b/source/blender/depsgraph/intern/nodes/deg_node_operation.h @@ -28,15 +28,15 @@ * \ingroup depsgraph */ -#ifndef __DEPSNODE_OPERATION_H__ -#define __DEPSNODE_OPERATION_H__ +#pragma once -#include "depsnode.h" +#include "intern/nodes/deg_node.h" struct ID; struct Depsgraph; -struct DepsgraphCopyContext; + +namespace DEG { /* Flags for Depsgraph Nodes */ typedef enum eDepsOperation_Flag { @@ -44,10 +44,14 @@ typedef enum eDepsOperation_Flag { DEPSOP_FLAG_NEEDS_UPDATE = (1 << 0), /* node was directly modified, causing need for update */ - /* XXX: intention is to make it easier to tell when we just need to take subgraphs */ + /* XXX: intention is to make it easier to tell when we just need to + * take subgraphs. + */ DEPSOP_FLAG_DIRECTLY_MODIFIED = (1 << 1), - /* Operation is evaluated using CPython; has GIL and security implications... */ + /* Operation is evaluated using CPython; has GIL and security + * implications... + */ DEPSOP_FLAG_USES_PYTHON = (1 << 2), } eDepsOperation_Flag; @@ -68,19 +72,26 @@ struct OperationDepsNode : public DepsNode { OperationDepsNode *get_entry_operation() { return this; } OperationDepsNode *get_exit_operation() { return this; } - ComponentDepsNode *owner; /* component that contains the operation */ + /* Component that contains the operation. */ + ComponentDepsNode *owner; - DepsEvalOperationCb evaluate; /* callback for operation */ + /* Callback for operation. */ + DepsEvalOperationCb evaluate; - uint32_t num_links_pending; /* how many inlinks are we still waiting on before we can be evaluated... */ + /* How many inlinks are we still waiting on before we can be evaluated. */ + uint32_t num_links_pending; float eval_priority; bool scheduled; - short optype; /* (eDepsOperation_Type) stage of evaluation */ - int opcode; /* (eDepsOperation_Code) identifier for the operation being performed */ + /* Stage of evaluation */ + eDepsOperation_Type optype; + + /* Identifier for the operation being performed. */ + eDepsOperation_Code opcode; - int flag; /* (eDepsOperation_Flag) extra settings affecting evaluation */ + /* (eDepsOperation_Flag) extra settings affecting evaluation. */ + int flag; /* Extra customdata mask which needs to be evaluated for the object. */ uint64_t customdata_mask; @@ -88,6 +99,6 @@ struct OperationDepsNode : public DepsNode { DEG_DEPSNODE_DECLARE; }; -void DEG_register_operation_depsnodes(); +void deg_register_operation_depsnodes(); -#endif /* __DEPSNODE_OPERATION_H__ */ +} // namespace DEG diff --git a/source/blender/depsgraph/util/depsgraph_util_foreach.h b/source/blender/depsgraph/util/deg_util_foreach.h index b2f1ebf3ac0..14cf4fc11ed 100644 --- a/source/blender/depsgraph/util/depsgraph_util_foreach.h +++ b/source/blender/depsgraph/util/deg_util_foreach.h @@ -24,12 +24,11 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_foreach.h +/** \file blender/depsgraph/util/deg_util_foreach.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_FOREACH_H__ -#define __DEPSGRAPH_UTIL_FOREACH_H__ +#pragma once #if (__cplusplus > 199711L) || (defined(_MSC_VER) && _MSC_VER >= 1800) # define foreach(x, y) for(x : y) @@ -48,4 +47,22 @@ # define foreach(x, y) for (x; false; (void)y) #endif -#endif /* __DEPSGRAPH_UTIL_FOREACH_H__ */ +#define GHASH_FOREACH_BEGIN(type, var, what) \ + do { \ + GHashIterator gh_iter##var; \ + GHASH_ITER(gh_iter##var, what) { \ + type var = reinterpret_cast<type>(BLI_ghashIterator_getValue(&gh_iter##var)); \ + +#define GHASH_FOREACH_END() \ + } \ + } while(0) + +#define GSET_FOREACH_BEGIN(type, var, what) \ + do { \ + GSetIterator gh_iter##var; \ + GSET_ITER(gh_iter##var, what) { \ + type var = reinterpret_cast<type>(BLI_gsetIterator_getKey(&gh_iter##var)); \ + +#define GSET_FOREACH_END() \ + } \ + } while(0) diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/deg_util_function.h index a4301833408..be7d1e13827 100644 --- a/source/blender/depsgraph/util/depsgraph_util_function.h +++ b/source/blender/depsgraph/util/deg_util_function.h @@ -24,12 +24,11 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_function.h +/** \file blender/depsgraph/util/deg_util_function.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_FUNCTION_H__ -#define __DEPSGRAPH_UTIL_FUNCTION_H__ +#pragma once #if (__cplusplus > 199711L) @@ -108,5 +107,3 @@ void *function_bind(T func, #define _4 Wrap() #endif - -#endif /* __DEPSGRAPH_UTIL_FUNCTION_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_set.h b/source/blender/depsgraph/util/deg_util_hash.h index 008ec6b74ca..e490be1a7a1 100644 --- a/source/blender/depsgraph/util/depsgraph_util_set.h +++ b/source/blender/depsgraph/util/deg_util_hash.h @@ -24,43 +24,18 @@ * ***** END GPL LICENSE BLOCK ***** */ -/** \file blender/depsgraph/util/depsgraph_util_set.h +/** \file blender/depsgraph/util/deg_util_hash.h * \ingroup depsgraph */ -#ifndef __DEPSGRAPH_UTIL_SET_H__ -#define __DEPSGRAPH_UTIL_SET_H__ +#pragma once -#include <set> +#include "BLI_utildefines.h" -#include "depsgraph_util_hash.h" +#include "BLI_ghash.h" -using std::set; - -#if defined(DEG_NO_UNORDERED_MAP) -# include <set> -typedef std::set unordered_set; -#endif - -#if defined(DEG_TR1_UNORDERED_MAP) -# include <tr1/unordered_set> -using std::tr1::unordered_set; -#endif - -#if defined(DEG_STD_UNORDERED_MAP) -# include <unordered_set> -using std::unordered_set; -#endif - -#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) -# include <unordered_set> -using std::tr1::unordered_set; -#endif - -#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ - !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT -# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ - DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT -#endif - -#endif /* __DEPSGRAPH_UTIL_SET_H__ */ +/* XXX this might require 2 different variants for sizeof(size_t) (32 vs 64 bit) */ +BLI_INLINE size_t hash_combine(size_t hash_a, size_t hash_b) +{ + return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2)); +} diff --git a/source/blender/depsgraph/util/depsgraph_util_hash.h b/source/blender/depsgraph/util/depsgraph_util_hash.h deleted file mode 100644 index bc75627a026..00000000000 --- a/source/blender/depsgraph/util/depsgraph_util_hash.h +++ /dev/null @@ -1,72 +0,0 @@ -/* - * ***** 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) 2014 Blender Foundation. - * All rights reserved. - * - * Original Author: Brecht van Lommel - * Contributor(s): Lukas Toenne - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/depsgraph/util/depsgraph_util_hash.h - * \ingroup depsgraph - */ - -#ifndef __DEPSGRAPH_UTIL_HASH_H__ -#define __DEPSGRAPH_UTIL_HASH_H__ - -#if defined(DEG_NO_UNORDERED_MAP) -# define DEG_HASH_NAMESPACE_BEGIN -# define DEG_HASH_NAMESPACE_END -#endif - -#if defined(DEG_TR1_UNORDERED_MAP) -# include <tr1/unordered_map> -# define DEG_HASH_NAMESPACE_BEGIN namespace std { namespace tr1 { -# define DEG_HASH_NAMESPACE_END } } -using std::tr1::hash; -#endif - -#if defined(DEG_STD_UNORDERED_MAP) -# include <unordered_map> -# define DEG_HASH_NAMESPACE_BEGIN namespace std { -# define DEG_HASH_NAMESPACE_END } -using std::hash; -#endif - -#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) -# include <unordered_map> -# define DEG_HASH_NAMESPACE_BEGIN namespace std { namespace tr1 { -# define DEG_HASH_NAMESPACE_END } } -using std::tr1::hash; -#endif - -#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ - !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT -# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ - DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT -#endif - -/* XXX this might require 2 different variants for sizeof(size_t) (32 vs 64 bit) */ -inline size_t hash_combine(size_t hash_a, size_t hash_b) -{ - return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2)); -} - -#endif /* __DEPSGRAPH_UTIL_HASH_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_map.h b/source/blender/depsgraph/util/depsgraph_util_map.h deleted file mode 100644 index 0eae1d79e34..00000000000 --- a/source/blender/depsgraph/util/depsgraph_util_map.h +++ /dev/null @@ -1,67 +0,0 @@ -/* - * ***** 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) 2014 Blender Foundation. - * All rights reserved. - * - * Original Author: Brecht van Lommel - * Contributor(s): Lukas Toenne - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file blender/depsgraph/util/depsgraph_util_map.h - * \ingroup depsgraph - */ - -#ifndef __DEPSGRAPH_UTIL_MAP_H__ -#define __DEPSGRAPH_UTIL_MAP_H__ - -#include <map> - -#include "depsgraph_util_hash.h" - -using std::map; -using std::pair; - -#if defined(DEG_NO_UNORDERED_MAP) -# include <map> -typedef std::map unordered_map; -#endif - -#if defined(DEG_TR1_UNORDERED_MAP) -# include <tr1/unordered_map> -using std::tr1::unordered_map; -#endif - -#if defined(DEG_STD_UNORDERED_MAP) -# include <unordered_map> -using std::unordered_map; -#endif - -#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) -# include <unordered_map> -using std::tr1::unordered_map; -#endif - -#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ - !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT -# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ - DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT -#endif - -#endif /* __DEPSGRAPH_UTIL_MAP_H__ */ |