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.

11 files changed, 34 insertions, 733 deletions

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_transitive.h b/source/blender/depsgraph/util/deg_util_hash.h
index a80a1d783d7..e490be1a7a1 100644
--- a/source/blender/depsgraph/util/depsgraph_util_transitive.h
+++ b/source/blender/depsgraph/util/deg_util_hash.h
@@ -15,24 +15,27 @@
  * 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.
+ * The Original Code is Copyright (C) 2014 Blender Foundation.
  * All rights reserved.
  *
+ * Original Author: Brecht van Lommel
  * Contributor(s): Lukas Toenne
- *                 Sergey Sharybin,
  *
  * ***** END GPL LICENSE BLOCK *****
  */
 
-/** \file blender/depsgraph/util/depsgraph_util_transitive.h
+/** \file blender/depsgraph/util/deg_util_hash.h
  *  \ingroup depsgraph
  */
 
-#ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__
-#define __DEPSGRAPH_UTIL_TRANSITIVE_H__
+#pragma once
 
-struct Depsgraph;
+#include "BLI_utildefines.h"
 
-void deg_graph_transitive_reduction(Depsgraph *graph);
+#include "BLI_ghash.h"
 
-#endif  /* __DEPSGRAPH_UTIL_TRANSITIVE_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_cycle.cc b/source/blender/depsgraph/util/depsgraph_util_cycle.cc
deleted file mode 100644
index 5eae8c087ad..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_cycle.cc
+++ /dev/null
@@ -1,140 +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) 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
deleted file mode 100644
index fac38b61057..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_cycle.h
+++ /dev/null
@@ -1,37 +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) 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_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__ */
diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc
deleted file mode 100644
index 80b37ec622d..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc
+++ /dev/null
@@ -1,136 +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) 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
deleted file mode 100644
index b7f4c495933..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h
+++ /dev/null
@@ -1,59 +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) 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
deleted file mode 100644
index 008ec6b74ca..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_set.h
+++ /dev/null
@@ -1,66 +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_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
deleted file mode 100644
index 98192a9540f..00000000000
--- a/source/blender/depsgraph/util/depsgraph_util_transitive.cc
+++ /dev/null
@@ -1,139 +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) 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);
-			}
-		}
-	}
-}