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.

6 files changed, 1341 insertions, 0 deletions

diff --git a/source/blender/depsgraph/intern/nodes/deg_node.cc b/source/blender/depsgraph/intern/nodes/deg_node.cc
new file mode 100644
index 00000000000..78293f7f483
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node.cc
@@ -0,0 +1,315 @@
+/*
+ * ***** 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/depsnode.cc
+ *  \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"
+#include "DNA_anim_types.h"
+
+#include "BKE_animsys.h"
+
+#include "DEG_depsgraph.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 */
+
+/* Add ------------------------------------------------ */
+
+DepsNode::TypeInfo::TypeInfo(eDepsNode_Type type, const char *tname)
+{
+	this->type = type;
+	if (type == DEPSNODE_TYPE_OPERATION)
+		this->tclass = DEPSNODE_CLASS_OPERATION;
+	else if (type < DEPSNODE_TYPE_PARAMETERS)
+		this->tclass = DEPSNODE_CLASS_GENERIC;
+	else
+		this->tclass = DEPSNODE_CLASS_COMPONENT;
+	this->tname = tname;
+}
+
+DepsNode::DepsNode()
+{
+	name[0] = '\0';
+}
+
+DepsNode::~DepsNode()
+{
+	/* Free links. */
+	/* NOTE: We only free incoming links. This is to avoid double-free of links
+	 * 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.
+	 */
+	foreach (DepsRelation *rel, inlinks) {
+		OBJECT_GUARDED_DELETE(rel, DepsRelation);
+	}
+}
+
+
+/* Generic identifier for Depsgraph Nodes. */
+string DepsNode::identifier() const
+{
+	char typebuf[7];
+	sprintf(typebuf, "(%d)", type);
+
+	return string(typebuf) + " : " + name;
+}
+
+/* ************* */
+/* Generic Nodes */
+
+/* Time Source Node ============================================== */
+
+void TimeSourceDepsNode::tag_update(Depsgraph *graph)
+{
+	foreach (DepsRelation *rel, outlinks) {
+		DepsNode *node = rel->to;
+		node->tag_update(graph);
+	}
+}
+
+
+/* Root Node ============================================== */
+
+RootDepsNode::RootDepsNode() : scene(NULL), time_source(NULL)
+{
+}
+
+RootDepsNode::~RootDepsNode()
+{
+	OBJECT_GUARDED_DELETE(time_source, TimeSourceDepsNode);
+}
+
+TimeSourceDepsNode *RootDepsNode::add_time_source(const string &name)
+{
+	if (!time_source) {
+		DepsNodeFactory *factory = deg_get_node_factory(DEPSNODE_TYPE_TIMESOURCE);
+		time_source = (TimeSourceDepsNode *)factory->create_node(NULL, "", name);
+		/*time_source->owner = this;*/ // XXX
+	}
+	return time_source;
+}
+
+DEG_DEPSNODE_DEFINE(RootDepsNode, DEPSNODE_TYPE_ROOT, "Root DepsNode");
+static DepsNodeFactoryImpl<RootDepsNode> DNTI_ROOT;
+
+/* Time Source Node ======================================= */
+
+DEG_DEPSNODE_DEFINE(TimeSourceDepsNode, DEPSNODE_TYPE_TIMESOURCE, "Time Source");
+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))
+{
+	/* Store ID-pointer. */
+	BLI_assert(id != NULL);
+	this->id = (ID *)id;
+	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...
+	 */
+}
+
+/* Free 'id' node. */
+IDDepsNode::~IDDepsNode()
+{
+	clear_components();
+	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);
+	return reinterpret_cast<ComponentDepsNode *>(BLI_ghash_lookup(components, &key));
+}
+
+ComponentDepsNode *IDDepsNode::add_component(eDepsNode_Type type,
+                                             const string &name)
+{
+	ComponentDepsNode *comp_node = find_component(type, name);
+	if (!comp_node) {
+		DepsNodeFactory *factory = deg_get_node_factory(type);
+		comp_node = (ComponentDepsNode *)factory->create_node(this->id, "", name);
+
+		/* Register. */
+		ComponentIDKey *key = OBJECT_GUARDED_NEW(ComponentIDKey, type, name);
+		BLI_ghash_insert(components, key, comp_node);
+		comp_node->owner = this;
+	}
+	return comp_node;
+}
+
+void IDDepsNode::remove_component(eDepsNode_Type type, const string &name)
+{
+	ComponentDepsNode *comp_node = find_component(type, name);
+	if (comp_node) {
+		/* Unregister. */
+		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()
+{
+	BLI_ghash_clear(components,
+	                id_deps_node_hash_key_free,
+	                id_deps_node_hash_value_free);
+}
+
+void IDDepsNode::tag_update(Depsgraph *graph)
+{
+	GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, components)
+	{
+		/* TODO(sergey): What about drievrs? */
+		bool do_component_tag = comp_node->type != DEPSNODE_TYPE_ANIMATION;
+		if (comp_node->type == DEPSNODE_TYPE_ANIMATION) {
+			AnimData *adt = BKE_animdata_from_id(id);
+			/* Animation data might be null if relations are tagged for update. */
+			if (adt != NULL && (adt->recalc & ADT_RECALC_ANIM)) {
+				do_component_tag = true;
+			}
+		}
+		if (do_component_tag) {
+			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");
+static DepsNodeFactoryImpl<IDDepsNode> DNTI_ID_REF;
+
+/* Subgraph Node ========================================== */
+
+/* Initialize 'subgraph' node - from pointer data given. */
+void SubgraphDepsNode::init(const ID *id, const string &UNUSED(subdata))
+{
+	/* Store ID-ref if provided. */
+	this->root_id = (ID *)id;
+
+	/* NOTE: graph will need to be added manually,
+	 * as we don't have any way of passing this down.
+	 */
+}
+
+/* Free 'subgraph' node */
+SubgraphDepsNode::~SubgraphDepsNode()
+{
+	/* Only free if graph not shared, of if this node is the first
+	 * reference to it...
+	 */
+	// XXX: prune these flags a bit...
+	if ((this->flag & SUBGRAPH_FLAG_FIRSTREF) || !(this->flag & SUBGRAPH_FLAG_SHARED)) {
+		/* Free the referenced graph. */
+		DEG_graph_free(reinterpret_cast< ::Depsgraph* >(graph));
+		graph = NULL;
+	}
+}
+
+DEG_DEPSNODE_DEFINE(SubgraphDepsNode, DEPSNODE_TYPE_SUBGRAPH, "Subgraph Node");
+static DepsNodeFactoryImpl<SubgraphDepsNode> DNTI_SUBGRAPH;
+
+void deg_register_base_depsnodes()
+{
+	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);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/nodes/deg_node.h b/source/blender/depsgraph/intern/nodes/deg_node.h
new file mode 100644
index 00000000000..d79d3d2348d
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node.h
@@ -0,0 +1,227 @@
+/*
+ * ***** 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/depsnode.h
+ *  \ingroup depsgraph
+ */
+
+#pragma once
+
+#include "intern/depsgraph_types.h"
+
+struct ID;
+struct GHash;
+struct Scene;
+
+namespace DEG {
+
+struct Depsgraph;
+struct DepsRelation;
+struct OperationDepsNode;
+
+/* *********************************** */
+/* Base-Defines for Nodes in Depsgraph */
+
+/* All nodes in Depsgraph are descended from this. */
+struct DepsNode {
+	/* Helper class for static typeinfo in subclasses. */
+	struct TypeInfo {
+		TypeInfo(eDepsNode_Type type, const char *tname);
+
+		eDepsNode_Type type;
+		eDepsNode_Class tclass;
+		const char *tname;
+	};
+
+	/* Identifier - mainly for debugging purposes. */
+	string name;
+
+	/* Structural type of node. */
+	eDepsNode_Type type;
+
+	/* Type of data/behaviour represented by node... */
+	eDepsNode_Class tclass;
+
+	/* Relationships between nodes
+	 * The reason why all depsgraph nodes are descended from this type (apart
+	 * from basic serialization benefits - from the typeinfo) is that we can have
+	 * relationships between these nodes!
+	 */
+	typedef vector<DepsRelation *> Relations;
+
+	/* Nodes which this one depends on. */
+	Relations inlinks;
+
+	/* Nodes which depend on this one. */
+	Relations outlinks;
+
+	/* Generic tag for traversal algorithms */
+	int done;
+
+	/* Methods. */
+
+	DepsNode();
+	virtual ~DepsNode();
+
+	virtual string identifier() const;
+	string full_identifier() const;
+
+	virtual void init(const ID * /*id*/,
+	                  const string &/*subdata*/) {}
+
+	virtual void tag_update(Depsgraph * /*graph*/) {}
+
+	virtual OperationDepsNode *get_entry_operation() { return NULL; }
+	virtual OperationDepsNode *get_exit_operation() { return NULL; }
+};
+
+/* Macros for common static typeinfo. */
+#define DEG_DEPSNODE_DECLARE \
+	static const DepsNode::TypeInfo typeinfo
+#define DEG_DEPSNODE_DEFINE(NodeType, type_, tname_) \
+	const DepsNode::TypeInfo NodeType::typeinfo = DepsNode::TypeInfo(type_, tname_)
+
+/* Generic Nodes ======================= */
+
+struct ComponentDepsNode;
+struct IDDepsNode;
+
+/* Time Source Node. */
+struct TimeSourceDepsNode : public DepsNode {
+	/* New "current time". */
+	float cfra;
+
+	/* time-offset relative to the "official" time source that this one has. */
+	float offset;
+
+	// TODO: evaluate() operation needed
+
+	void tag_update(Depsgraph *graph);
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+/* Root Node. */
+struct RootDepsNode : public DepsNode {
+	RootDepsNode();
+	~RootDepsNode();
+
+	TimeSourceDepsNode *add_time_source(const string &name = "");
+
+	/* scene that this corresponds to */
+	Scene *scene;
+
+	/* Entrypoint node for time-changed. */
+	TimeSourceDepsNode *time_source;
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+/* ID-Block Reference */
+struct IDDepsNode : public DepsNode {
+	struct ComponentIDKey {
+		ComponentIDKey(eDepsNode_Type type, const string &name = "")
+		    : type(type), name(name) {}
+
+		bool operator== (const ComponentIDKey &other) const
+		{
+			return type == other.type && name == other.name;
+		}
+
+		eDepsNode_Type type;
+		string name;
+	};
+
+	void init(const ID *id, const string &subdata);
+	~IDDepsNode();
+
+	ComponentDepsNode *find_component(eDepsNode_Type type,
+	                                  const string &name = "") const;
+	ComponentDepsNode *add_component(eDepsNode_Type type,
+	                                 const string &name = "");
+	void remove_component(eDepsNode_Type type, const string &name = "");
+	void clear_components();
+
+	void tag_update(Depsgraph *graph);
+
+	void finalize_build();
+
+	/* ID Block referenced. */
+	ID *id;
+
+	/* Hash to make it faster to look up components. */
+	GHash *components;
+
+	/* Layers of this node with accumulated layers of it's output relations. */
+	int layers;
+
+	/* Additional flags needed for scene evaluation.
+	 * TODO(sergey): Only needed for until really granular updates
+	 * of all the entities.
+	 */
+	int eval_flags;
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+/* Subgraph Reference. */
+struct SubgraphDepsNode : public DepsNode {
+	void init(const ID *id, const string &subdata);
+	~SubgraphDepsNode();
+
+	/* Instanced graph. */
+	Depsgraph *graph;
+
+	/* ID-block at root of subgraph (if applicable). */
+	ID *root_id;
+
+	/* Number of nodes which use/reference this subgraph - if just 1, it may be
+	 * possible to merge into main,
+	 */
+	size_t num_users;
+
+	/* (eSubgraphRef_Flag) assorted settings for subgraph node. */
+	int flag;
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+/* Flags for subgraph node */
+typedef enum eSubgraphRef_Flag {
+	/* Subgraph referenced is shared with another reference, so shouldn't
+	 * free on exit.
+	 */
+	SUBGRAPH_FLAG_SHARED      = (1 << 0),
+
+	/* Node is first reference to subgraph, so it can be freed when we are
+	 * removed.
+	 */
+	SUBGRAPH_FLAG_FIRSTREF    = (1 << 1),
+} eSubgraphRef_Flag;
+
+void deg_register_base_depsnodes();
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/nodes/deg_node_component.cc b/source/blender/depsgraph/intern/nodes/deg_node_component.cc
new file mode 100644
index 00000000000..d18047c5112
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node_component.cc
@@ -0,0 +1,377 @@
+/*
+ * ***** 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/depsnode_component.cc
+ *  \ingroup depsgraph
+ */
+
+#include "intern/nodes/deg_node_component.h"
+
+#include <stdio.h>
+#include <string.h>
+
+extern "C" {
+#include "BLI_utildefines.h"
+
+#include "DNA_object_types.h"
+
+#include "BKE_action.h"
+} /* extern "C" */
+
+#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 */
+void ComponentDepsNode::init(const ID * /*id*/,
+                             const string & /*subdata*/)
+{
+	/* hook up eval context? */
+	// XXX: maybe this needs a special API?
+}
+
+/* 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
+{
+	string &idname = this->owner->name;
+
+	char typebuf[7];
+	sprintf(typebuf, "(%d)", type);
+
+	return string(typebuf) + name + " : " + idname;
+}
+
+OperationDepsNode *ComponentDepsNode::find_operation(OperationIDKey key) const
+{
+	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",
+		        this->identifier().c_str(), key.identifier().c_str());
+		BLI_assert(!"Request for non-existing operation, should not happen");
+		return NULL;
+	}
+}
+
+OperationDepsNode *ComponentDepsNode::find_operation(eDepsOperation_Code opcode, const string &name) const
+{
+	OperationIDKey key(opcode, name);
+	return find_operation(key);
+}
+
+OperationDepsNode *ComponentDepsNode::has_operation(OperationIDKey key) const
+{
+	return reinterpret_cast<OperationDepsNode *>(BLI_ghash_lookup(operations_map, &key));
+}
+
+OperationDepsNode *ComponentDepsNode::has_operation(eDepsOperation_Code opcode,
+                                                    const string &name) const
+{
+	OperationIDKey key(opcode, name);
+	return has_operation(key);
+}
+
+OperationDepsNode *ComponentDepsNode::add_operation(eDepsOperation_Type optype, DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &name)
+{
+	OperationDepsNode *op_node = has_operation(opcode, name);
+	if (!op_node) {
+		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 = 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) {
+			BLI_assert(this->entry_operation == NULL);
+			this->entry_operation = op_node;
+		}
+		else if (optype == DEPSOP_TYPE_POST) {
+			// XXX: review whether DEPSOP_TYPE_OUT is better than DEPSOP_TYPE_POST, or maybe have both?
+			BLI_assert(this->exit_operation == NULL);
+			this->exit_operation = op_node;
+		}
+
+		/* set backlink */
+		op_node->owner = this;
+	}
+	else {
+		fprintf(stderr, "add_operation: Operation already exists - %s has %s at %p\n",
+		        this->identifier().c_str(), op_node->identifier().c_str(), op_node);
+		BLI_assert(!"Should not happen!");
+	}
+
+	/* attach extra data */
+	op_node->evaluate = op;
+	op_node->optype = optype;
+	op_node->opcode = opcode;
+	op_node->name = name;
+
+	return op_node;
+}
+
+void ComponentDepsNode::remove_operation(eDepsOperation_Code opcode, const string &name)
+{
+	/* 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()
+{
+	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();
+}
+
+void ComponentDepsNode::tag_update(Depsgraph *graph)
+{
+	OperationDepsNode *entry_op = get_entry_operation();
+	if (entry_op != NULL && entry_op->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+		return;
+	}
+	foreach (OperationDepsNode *op_node, operations) {
+		op_node->tag_update(graph);
+	}
+}
+
+OperationDepsNode *ComponentDepsNode::get_entry_operation()
+{
+	if (entry_operation) {
+		return entry_operation;
+	}
+	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) {
+		return exit_operation;
+	}
+	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");
+static DepsNodeFactoryImpl<ParametersComponentDepsNode> DNTI_PARAMETERS;
+
+/* Animation Component Defines ============================ */
+
+DEG_DEPSNODE_DEFINE(AnimationComponentDepsNode, DEPSNODE_TYPE_ANIMATION, "Animation Component");
+static DepsNodeFactoryImpl<AnimationComponentDepsNode> DNTI_ANIMATION;
+
+/* Transform Component Defines ============================ */
+
+DEG_DEPSNODE_DEFINE(TransformComponentDepsNode, DEPSNODE_TYPE_TRANSFORM, "Transform Component");
+static DepsNodeFactoryImpl<TransformComponentDepsNode> DNTI_TRANSFORM;
+
+/* Proxy Component Defines ================================ */
+
+DEG_DEPSNODE_DEFINE(ProxyComponentDepsNode, DEPSNODE_TYPE_PROXY, "Proxy Component");
+static DepsNodeFactoryImpl<ProxyComponentDepsNode> DNTI_PROXY;
+
+/* Geometry Component Defines ============================= */
+
+DEG_DEPSNODE_DEFINE(GeometryComponentDepsNode, DEPSNODE_TYPE_GEOMETRY, "Geometry Component");
+static DepsNodeFactoryImpl<GeometryComponentDepsNode> DNTI_GEOMETRY;
+
+/* Sequencer Component Defines ============================ */
+
+DEG_DEPSNODE_DEFINE(SequencerComponentDepsNode, DEPSNODE_TYPE_SEQUENCER, "Sequencer Component");
+static DepsNodeFactoryImpl<SequencerComponentDepsNode> DNTI_SEQUENCER;
+
+/* Pose Component ========================================= */
+
+DEG_DEPSNODE_DEFINE(PoseComponentDepsNode, DEPSNODE_TYPE_EVAL_POSE, "Pose Eval Component");
+static DepsNodeFactoryImpl<PoseComponentDepsNode> DNTI_EVAL_POSE;
+
+/* Bone Component ========================================= */
+
+/* Initialize 'bone component' node - from pointer data given */
+void BoneComponentDepsNode::init(const ID *id, const string &subdata)
+{
+	/* generic component-node... */
+	ComponentDepsNode::init(id, subdata);
+
+	/* name of component comes is bone name */
+	/* TODO(sergey): This sets name to an empty string because subdata is
+	 * empty. Is it a bug?
+	 */
+	//this->name = subdata;
+
+	/* bone-specific node data */
+	Object *ob = (Object *)id;
+	this->pchan = BKE_pose_channel_find_name(ob->pose, subdata.c_str());
+}
+
+DEG_DEPSNODE_DEFINE(BoneComponentDepsNode, DEPSNODE_TYPE_BONE, "Bone Component");
+static DepsNodeFactoryImpl<BoneComponentDepsNode> DNTI_BONE;
+
+/* Particles Component Defines ============================ */
+
+DEG_DEPSNODE_DEFINE(ParticlesComponentDepsNode, DEPSNODE_TYPE_EVAL_PARTICLES, "Particles Component");
+static DepsNodeFactoryImpl<ParticlesComponentDepsNode> DNTI_EVAL_PARTICLES;
+
+/* Shading Component Defines ============================ */
+
+DEG_DEPSNODE_DEFINE(ShadingComponentDepsNode, DEPSNODE_TYPE_SHADING, "Shading Component");
+static DepsNodeFactoryImpl<ShadingComponentDepsNode> DNTI_SHADING;
+
+
+/* Node Types Register =================================== */
+
+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);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/nodes/deg_node_component.h b/source/blender/depsgraph/intern/nodes/deg_node_component.h
new file mode 100644
index 00000000000..17e6e7e0030
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node_component.h
@@ -0,0 +1,221 @@
+/*
+ * ***** 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/depsnode_component.h
+ *  \ingroup depsgraph
+ */
+
+#pragma once
+
+#include "intern/nodes/deg_node.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_string.h"
+
+struct ID;
+struct bPoseChannel;
+struct GHash;
+
+struct EvaluationContext;
+
+namespace DEG {
+
+struct Depsgraph;
+struct OperationDepsNode;
+struct BoneComponentDepsNode;
+
+typedef enum eDepsComponent_Flag {
+	/* Temporary flags, meaning all the component's operations has been
+	 * scheduled for update.
+	 */
+	DEPSCOMP_FULLY_SCHEDULED = 1,
+} eDepsComponent_Flag;
+
+/* ID Component - Base type for all components */
+struct ComponentDepsNode : public DepsNode {
+	/* Key used to look up operations within a component */
+	struct OperationIDKey
+	{
+		eDepsOperation_Code opcode;
+		string name;
+
+
+		OperationIDKey() :
+			opcode(DEG_OPCODE_OPERATION), name("")
+		{}
+		OperationIDKey(eDepsOperation_Code opcode) :
+			opcode(opcode), name("")
+		{}
+		OperationIDKey(eDepsOperation_Code opcode, const string &name) :
+		   opcode(opcode), name(name)
+		{}
+
+		string identifier() const
+		{
+			char codebuf[5];
+			BLI_snprintf(codebuf, sizeof(codebuf), "%d", opcode);
+
+			return string("OperationIDKey(") + codebuf + ", " + name + ")";
+		}
+
+		bool operator==(const OperationIDKey &other) const
+		{
+			return (opcode == other.opcode) && (name == other.name);
+		}
+	};
+
+	/* Typedef for container of operations */
+	ComponentDepsNode();
+	~ComponentDepsNode();
+
+	void init(const ID *id, const string &subdata);
+
+	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;
+
+	/* Check operation exists and return it. */
+	OperationDepsNode *has_operation(OperationIDKey key) 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)
+	 *
+	 * \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);
+
+	void remove_operation(eDepsOperation_Code opcode, const string &name);
+	void clear_operations();
+
+	void tag_update(Depsgraph *graph);
+
+	/* Evaluation Context Management .................. */
+
+	/* 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
+	 *
+	 * NOTE: this does not free the actual context in question
+	 */
+	virtual void eval_context_free(EvaluationContext * /*eval_ctx*/) {}
+
+	OperationDepsNode *get_entry_operation();
+	OperationDepsNode *get_exit_operation();
+
+	void finalize_build();
+
+	IDDepsNode *owner;
+
+	/* ** 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;
+
+	// XXX: a poll() callback to check if component's first node can be started?
+
+	int flags;
+};
+
+/* ---------------------------------------- */
+
+struct ParametersComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct AnimationComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct TransformComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct ProxyComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct GeometryComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct SequencerComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct PoseComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+/* Bone Component */
+struct BoneComponentDepsNode : public ComponentDepsNode {
+	void init(const ID *id, const string &subdata);
+
+	struct bPoseChannel *pchan;     /* the bone that this component represents */
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct ParticlesComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+struct ShadingComponentDepsNode : public ComponentDepsNode {
+	DEG_DEPSNODE_DECLARE;
+};
+
+
+void deg_register_component_depsnodes();
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/nodes/deg_node_operation.cc b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc
new file mode 100644
index 00000000000..a9f9703bb3b
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc
@@ -0,0 +1,97 @@
+/*
+ * ***** 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/depsnode_operation.cc
+ *  \ingroup depsgraph
+ */
+
+#include "intern/nodes/deg_node_operation.h"
+
+#include "MEM_guardedalloc.h"
+
+extern "C" {
+#include "BLI_utildefines.h"
+} /* extern "C" */
+
+#include "intern/depsgraph.h"
+#include "intern/depsgraph_intern.h"
+#include "util/deg_util_hash.h"
+
+namespace DEG {
+
+/* *********** */
+/* Inner Nodes */
+
+OperationDepsNode::OperationDepsNode() :
+    eval_priority(0.0f),
+    flag(0),
+    customdata_mask(0)
+{
+}
+
+OperationDepsNode::~OperationDepsNode()
+{
+}
+
+string OperationDepsNode::identifier() const
+{
+	return string(DEG_OPNAMES[opcode]) + "(" + name + ")";
+}
+
+/* Full node identifier, including owner name.
+ * used for logging and debug prints.
+ */
+string OperationDepsNode::full_identifier() const
+{
+	string owner_str = "";
+	if (owner->type == DEPSNODE_TYPE_BONE) {
+		owner_str = owner->owner->name + "." + owner->name;
+	}
+	else {
+		owner_str = owner->owner->name;
+	}
+	return owner_str + "." + identifier();
+}
+
+void OperationDepsNode::tag_update(Depsgraph *graph)
+{
+	if (flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+		return;
+	}
+	/* Tag for update, but also note that this was the source of an update. */
+	flag |= (DEPSOP_FLAG_NEEDS_UPDATE | DEPSOP_FLAG_DIRECTLY_MODIFIED);
+	graph->add_entry_tag(this);
+}
+
+DEG_DEPSNODE_DEFINE(OperationDepsNode, DEPSNODE_TYPE_OPERATION, "Operation");
+static DepsNodeFactoryImpl<OperationDepsNode> DNTI_OPERATION;
+
+void deg_register_operation_depsnodes()
+{
+	deg_register_node_typeinfo(&DNTI_OPERATION);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/nodes/deg_node_operation.h b/source/blender/depsgraph/intern/nodes/deg_node_operation.h
new file mode 100644
index 00000000000..f03078fc3db
--- /dev/null
+++ b/source/blender/depsgraph/intern/nodes/deg_node_operation.h
@@ -0,0 +1,104 @@
+/*
+ * ***** 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/depsnode_operation.h
+ *  \ingroup depsgraph
+ */
+
+#pragma once
+
+#include "intern/nodes/deg_node.h"
+
+struct ID;
+
+struct Depsgraph;
+
+namespace DEG {
+
+/* Flags for Depsgraph Nodes */
+typedef enum eDepsOperation_Flag {
+	/* node needs to be updated */
+	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.
+	 */
+	DEPSOP_FLAG_DIRECTLY_MODIFIED  = (1 << 1),
+
+	/* Operation is evaluated using CPython; has GIL and security
+	 * implications...
+	 */
+	DEPSOP_FLAG_USES_PYTHON   = (1 << 2),
+} eDepsOperation_Flag;
+
+/* Atomic Operation - Base type for all operations */
+struct OperationDepsNode : public DepsNode {
+
+
+	OperationDepsNode();
+	~OperationDepsNode();
+
+	string identifier() const;
+	string full_identifier() const;
+
+	void tag_update(Depsgraph *graph);
+
+	bool is_noop() const { return (bool)evaluate == false; }
+
+	OperationDepsNode *get_entry_operation() { return this; }
+	OperationDepsNode *get_exit_operation() { return this; }
+
+	/* Component that contains the operation. */
+	ComponentDepsNode *owner;
+
+	/* Callback for operation. */
+	DepsEvalOperationCb evaluate;
+
+
+	/* How many inlinks are we still waiting on before we can be evaluated. */
+	uint32_t num_links_pending;
+	float eval_priority;
+	bool scheduled;
+
+	/* Stage of evaluation */
+	eDepsOperation_Type optype;
+
+	/* Identifier for the operation being performed. */
+	eDepsOperation_Code opcode;
+
+	/* (eDepsOperation_Flag) extra settings affecting evaluation. */
+	int flag;
+
+	/* Extra customdata mask which needs to be evaluated for the object. */
+	uint64_t customdata_mask;
+
+	DEG_DEPSNODE_DECLARE;
+};
+
+void deg_register_operation_depsnodes();
+
+}  // namespace DEG