diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2016-05-27 19:01:18 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2016-05-27 19:01:18 +0300 |
commit | 55b24bef557922b8f51cf993b12047e980e43617 (patch) | |
tree | 7a9dd18a1d096e71e94406fb1ceecf233fa4e3af /source/blender | |
parent | 3d86a5bc72a63b1ef8b165d68a1806d0abf0a8ac (diff) |
Depsgraph: Cleanup and code simplification
This is mainly a maintenance commit which was aimed to make work with
this module more pleasant and solve such issues as:
- Annoyance with looong files, which had craftload in them
- Usage of STL for the data structures we've got in BLI
- Possible symbol conflicts
- Not real clear layout of what is located where
So in this commit the following changes are done:
- STL is prohibited, it's not really predictable on various compilers,
with our BLI algorithms we can predict things much better.
There are still few usages of std::vector, but that we'll be
solving later once we've got similar thing in BLI.
- Simplify foreach loops, avoid using const_iterator all over the place.
- New directory layout, which is hopefully easier to follow.
- Some files were split, some of them will be split soon.
The idea of this is to split huge functions into own files with
good documentation and everything.
- Removed stuff which was planned for use in the future but was never
finished, tested or anything.
Let's wipe it out for now, and bring back once we really start using
it, so it'll be more clear if it solves our needs.
- All the internal routines were moved to DEG namespace to separate
them better from rest of blender.
Some places now annoyingly using DEG::foo, but that we can olve by
moving some utility functions inside of the namespace.
While working on this we've found some hotspot in updates flush, so
now playback of blenrig is few percent faster (something like 96fps
with previous master and around 99-100fps after this change).
Not saying it's something final, there is still room for cleanup and
API simplification, but those might happen as a regular development
now without doing any global changes.
Diffstat (limited to 'source/blender')
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__ */ |