Merge branch 'master' into temp-ghash-setopstemp-ghash-setops

10 files changed, 866 insertions, 0 deletions

diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cc b/source/blender/depsgraph/util/depsgraph_util_cycle.cc
new file mode 100644
index 00000000000..5eae8c087ad
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_cycle.cc
@@ -0,0 +1,140 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_cycle.cc
+ *  \ingroup depsgraph
+ */
+
+#include <cstdio>
+#include <cstdlib>
+#include <stack>
+
+extern "C" {
+#include "BLI_utildefines.h"
+
+#include "DNA_ID.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+}
+
+#include "depsgraph_util_cycle.h"
+#include "depsgraph.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+
+struct StackEntry {
+	OperationDepsNode *node;
+	StackEntry *from;
+	DepsRelation *via_relation;
+};
+
+void deg_graph_detect_cycles(Depsgraph *graph)
+{
+	/* Not is not visited at all during traversal. */
+	const int NODE_NOT_VISITED = 0;
+	/* Node has been visited during traversal and not in current stack. */
+	const int NODE_VISITED = 1;
+	/* Node has been visited during traversal and is in current stack. */
+	const int NODE_IN_STACK = 2;
+
+	std::stack<StackEntry> traversal_stack;
+	for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
+	     it_op != graph->operations.end();
+	     ++it_op)
+	{
+		OperationDepsNode *node = *it_op;
+		bool has_inlinks = false;
+		for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
+		     it_rel != node->inlinks.end();
+		     ++it_rel)
+		{
+			DepsRelation *rel = *it_rel;
+			if (rel->from->type == DEPSNODE_TYPE_OPERATION) {
+				has_inlinks = true;
+			}
+		}
+		if (has_inlinks == false) {
+			StackEntry entry;
+			entry.node = node;
+			entry.from = NULL;
+			entry.via_relation = NULL;
+			traversal_stack.push(entry);
+			node->done = NODE_IN_STACK;
+		}
+		else {
+			node->done = NODE_NOT_VISITED;
+		}
+	}
+
+	while (!traversal_stack.empty()) {
+		StackEntry &entry = traversal_stack.top();
+		OperationDepsNode *node = entry.node;
+		bool all_child_traversed = true;
+		for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
+		     it_rel != node->outlinks.end();
+		     ++it_rel)
+		{
+			DepsRelation *rel = *it_rel;
+			if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
+				OperationDepsNode *to = (OperationDepsNode *)rel->to;
+				if (to->done == NODE_IN_STACK) {
+					printf("Dependency cycle detected:\n");
+					printf("  '%s' depends on '%s' through '%s'\n",
+					       to->full_identifier().c_str(),
+					       node->full_identifier().c_str(),
+					       rel->name);
+
+					StackEntry *current = &entry;
+					while (current->node != to) {
+						BLI_assert(current != NULL);
+						printf("  '%s' depends on '%s' through '%s'\n",
+						       current->node->full_identifier().c_str(),
+						       current->from->node->full_identifier().c_str(),
+						       current->via_relation->name);
+						current = current->from;
+					}
+					/* TODO(sergey): So called roussian rlette cycle solver. */
+					rel->flag |= DEPSREL_FLAG_CYCLIC;
+				}
+				else if (to->done == NODE_NOT_VISITED) {
+					StackEntry new_entry;
+					new_entry.node = to;
+					new_entry.from = &entry;
+					new_entry.via_relation = rel;
+					traversal_stack.push(new_entry);
+					to->done = NODE_IN_STACK;
+					all_child_traversed = false;
+					break;
+				}
+			}
+		}
+		if (all_child_traversed) {
+			node->done = NODE_VISITED;
+			traversal_stack.pop();
+		}
+	}
+}
diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.h b/source/blender/depsgraph/util/depsgraph_util_cycle.h
new file mode 100644
index 00000000000..fac38b61057
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_cycle.h
@@ -0,0 +1,37 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_cycle.h
+ *  \ingroup depsgraph
+ */
+
+#ifndef __DEPSGRAPH_UTIL_CYCLE_H__
+#define __DEPSGRAPH_UTIL_CYCLE_H__
+
+struct Depsgraph;
+
+void deg_graph_detect_cycles(Depsgraph *graph);
+
+#endif  /* __DEPSGRAPH_UTIL_CYCLE_H__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h
new file mode 100644
index 00000000000..a4301833408
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_function.h
@@ -0,0 +1,112 @@
+/*
+ * ***** 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): 
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_function.h
+ *  \ingroup depsgraph
+ */
+
+#ifndef __DEPSGRAPH_UTIL_FUNCTION_H__
+#define __DEPSGRAPH_UTIL_FUNCTION_H__
+
+#if (__cplusplus > 199711L)
+
+#include <functional>
+
+using std::function;
+using namespace std::placeholders;
+#define function_bind std::bind
+
+#elif defined(HAVE_BOOST_FUNCTION_BINDINGS)
+
+#include <boost/bind.hpp>
+#include <boost/function.hpp>
+
+using boost::function;
+#define function_bind boost::bind
+
+#else
+
+#pragma message("No available function binding implementation. Using stub instead, disabling new depsgraph")
+
+#ifndef WITH_LEGACY_DEPSGRAPH
+#  error "Unable to build new depsgraph and legacy one is disabled."
+#endif
+
+#define DISABLE_NEW_DEPSGRAPH
+
+#include <cstdlib>
+
+template<typename T>
+class function {
+public:
+	function() {};
+	function(void *) {}
+	operator bool() const { return false; }
+	bool operator== (void *) { return false; }
+
+	template<typename T1>
+	void operator() (T1) {
+		BLI_assert(!"Should not be used");
+	}
+};
+
+class Wrap {
+public:
+	Wrap() {}
+	template <typename T>
+	Wrap(T /*arg*/) {}
+};
+
+template <typename T>
+void *function_bind(T func,
+                    Wrap arg1 = Wrap(),
+                    Wrap arg2 = Wrap(),
+                    Wrap arg3 = Wrap(),
+                    Wrap arg4 = Wrap(),
+                    Wrap arg5 = Wrap(),
+                    Wrap arg6 = Wrap(),
+                    Wrap arg7 = Wrap())
+{
+	BLI_assert(!"Should not be used");
+	(void)func;
+	(void)arg1;
+	(void)arg2;
+	(void)arg3;
+	(void)arg4;
+	(void)arg5;
+	(void)arg6;
+	(void)arg7;
+	return NULL;
+}
+
+#define _1 Wrap()
+#define _2 Wrap()
+#define _3 Wrap()
+#define _4 Wrap()
+
+#endif
+
+#endif  /* __DEPSGRAPH_UTIL_FUNCTION_H__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_hash.h b/source/blender/depsgraph/util/depsgraph_util_hash.h
new file mode 100644
index 00000000000..bc75627a026
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_hash.h
@@ -0,0 +1,72 @@
+/*
+ * ***** 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
new file mode 100644
index 00000000000..0eae1d79e34
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_map.h
@@ -0,0 +1,67 @@
+/*
+ * ***** 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__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc
new file mode 100644
index 00000000000..80b37ec622d
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc
@@ -0,0 +1,136 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Sergey Sharybin
+ * Contributor(s): Joshua Leung
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_pchanmap.cc
+ *  \ingroup depsgraph
+ */
+
+#include "depsgraph_util_pchanmap.h"
+
+#include <stdio.h>
+#include <string.h>
+
+extern "C" {
+#include "BLI_utildefines.h"
+#include "BLI_ghash.h"
+}
+
+static void free_rootpchanmap_valueset(void *val)
+{
+	/* Just need to free the set itself - the names stored are all references. */
+	GSet *values = (GSet *)val;
+	BLI_gset_free(values, NULL);
+}
+
+RootPChanMap::RootPChanMap()
+{
+	/* Just create empty map. */
+	m_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);
+}
+
+/* Debug contents of map */
+void RootPChanMap::print_debug()
+{
+	GHashIterator it1;
+	GSetIterator it2;
+
+	printf("Root PChan Map:\n");
+	GHASH_ITER(it1, m_map) {
+		const char *item = (const char *)BLI_ghashIterator_getKey(&it1);
+		GSet *values = (GSet *)BLI_ghashIterator_getValue(&it1);
+
+		printf("  %s : { ", item);
+		GSET_ITER(it2, values) {
+			const char *val = (const char *)BLI_gsetIterator_getKey(&it2);
+			printf("%s, ", val);
+		}
+		printf("}\n");
+	}
+}
+
+/* Add a mapping. */
+void RootPChanMap::add_bone(const char *bone, const char *root)
+{
+	if (BLI_ghash_haskey(m_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);
+		BLI_gset_add(values, (void *)root);
+	}
+	else {
+		/* Create new set and mapping. */
+		GSet *values = BLI_gset_new(BLI_ghashutil_strhash_p,
+		                            BLI_ghashutil_strcmp,
+		                            "RootPChanMap Value Set");
+		BLI_ghash_insert(m_map, (void *)bone, (void *)values);
+
+		/* Add new entry now. */
+		BLI_gset_insert(values, (void *)root);
+	}
+}
+
+/* Check if there's a common root bone between two bones. */
+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) {
+		//fprintf("RootPChanMap: bone1 '%s' not found (%s => %s)\n", bone1, bone1, bone2);
+		//print_debug();
+		return false;
+	}
+
+	if (BLI_ghash_haskey(m_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);
+
+	GSetIterator it1, it2;
+	GSET_ITER(it1, bone1_roots) {
+		GSET_ITER(it2, bone2_roots) {
+			const char *v1 = (const char *)BLI_gsetIterator_getKey(&it1);
+			const char *v2 = (const char *)BLI_gsetIterator_getKey(&it2);
+
+			if (strcmp(v1, v2) == 0) {
+				//fprintf("RootPchanMap: %s in common for %s => %s\n", v1, bone1, bone2);
+				return true;
+			}
+		}
+	}
+
+	//fprintf("RootPChanMap: No common root found (%s => %s)\n", bone1, bone2);
+	return false;
+}
diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h
new file mode 100644
index 00000000000..b7f4c495933
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h
@@ -0,0 +1,59 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Sergey Sharybin
+ * Contributor(s): Joshua Leung
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_pchanmap.h
+ *  \ingroup depsgraph
+ */
+
+#ifndef __DEPSGRAPH_UTIL_PCHANMAP_H__
+#define __DEPSGRAPH_UTIL_PCHANMAP_H__
+
+struct RootPChanMap {
+	/* ctor and dtor - Create and free the internal map respectively. */
+	RootPChanMap();
+	~RootPChanMap();
+
+	/* Debug contents of map. */
+	void print_debug();
+
+	/* Add a mapping. */
+	void add_bone(const char *bone, const char *root);
+
+	/* Check if there's a common root bone between two bones. */
+	bool has_common_root(const char *bone1, const char *bone2);
+
+private:
+	/* The actual map:
+	 * - Keys are "strings" (const char *) - not dynamically allocated.
+	 * - Values are "sets" (const char *) - not dynamically allocated.
+	 *
+	 * 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;
+};
+
+#endif  /* __DEPSGRAPH_UTIL_PCHANMAP_H__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_set.h b/source/blender/depsgraph/util/depsgraph_util_set.h
new file mode 100644
index 00000000000..008ec6b74ca
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_set.h
@@ -0,0 +1,66 @@
+/*
+ * ***** 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_set.h
+ *  \ingroup depsgraph
+ */
+
+#ifndef __DEPSGRAPH_UTIL_SET_H__
+#define __DEPSGRAPH_UTIL_SET_H__
+
+#include <set>
+
+#include "depsgraph_util_hash.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__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.cc b/source/blender/depsgraph/util/depsgraph_util_transitive.cc
new file mode 100644
index 00000000000..98192a9540f
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_transitive.cc
@@ -0,0 +1,139 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Lukas Toenne,
+ *                 Sergey Sharybin,
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_transitive.cc
+ *  \ingroup depsgraph
+ */
+
+extern "C" {
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+
+#include "DNA_ID.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+}
+
+#include "depsgraph_util_transitive.h"
+#include "depsgraph.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+
+/* -------------------------------------------------- */
+
+/* Performs a transitive reduction to remove redundant relations.
+ * http://en.wikipedia.org/wiki/Transitive_reduction
+ *
+ * XXX The current implementation is somewhat naive and has O(V*E) worst case
+ * runtime.
+ * A more optimized algorithm can be implemented later, e.g.
+ *
+ *   http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
+ *
+ * Care has to be taken to make sure the algorithm can handle the cyclic case
+ * too! (unless we can to prevent this case early on).
+ */
+
+enum {
+	OP_VISITED = 1,
+	OP_REACHABLE = 2,
+};
+
+static void deg_graph_tag_paths_recursive(DepsNode *node)
+{
+	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;
+
+		deg_graph_tag_paths_recursive(rel->from);
+		/* Do this only in inlinks loop, so the target node does not get
+		 * flagged.
+		 */
+		rel->from->done |= OP_REACHABLE;
+	}
+}
+
+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;
+
+		/* Clear tags. */
+		for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
+		     it != graph->operations.end();
+		     ++it)
+		{
+			OperationDepsNode *node = *it;
+			node->done = 0;
+		}
+
+		/* mark nodes from which we can reach the target
+		 * start with children, so the target node and direct children are not
+		 * flagged.
+		 */
+		target->done |= OP_VISITED;
+		for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin();
+		     it != target->inlinks.end();
+		     ++it)
+		{
+			DepsRelation *rel = *it;
+
+			deg_graph_tag_paths_recursive(rel->from);
+		}
+
+		/* Eemove 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. */
+			++it_rel;
+
+			if (rel->from->type == DEPSNODE_TYPE_TIMESOURCE) {
+				/* HACK: time source nodes don't get "done" flag set/cleared. */
+				/* TODO: there will be other types in future, so iterators above
+				 * need modifying.
+				 */
+			}
+			else if (rel->from->done & OP_REACHABLE) {
+				OBJECT_GUARDED_DELETE(rel, DepsRelation);
+			}
+		}
+	}
+}
diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.h b/source/blender/depsgraph/util/depsgraph_util_transitive.h
new file mode 100644
index 00000000000..a80a1d783d7
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_transitive.h
@@ -0,0 +1,38 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Lukas Toenne
+ *                 Sergey Sharybin,
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/util/depsgraph_util_transitive.h
+ *  \ingroup depsgraph
+ */
+
+#ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__
+#define __DEPSGRAPH_UTIL_TRANSITIVE_H__
+
+struct Depsgraph;
+
+void deg_graph_transitive_reduction(Depsgraph *graph);
+
+#endif  /* __DEPSGRAPH_UTIL_TRANSITIVE_H__ */