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, 1047 insertions, 0 deletions

diff --git a/source/blender/depsgraph/intern/eval/deg_eval.cc b/source/blender/depsgraph/intern/eval/deg_eval.cc
new file mode 100644
index 00000000000..198cd349002
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval.cc
@@ -0,0 +1,409 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/depsgraph_eval.cc
+ *  \ingroup depsgraph
+ *
+ * Evaluation engine entrypoints for Depsgraph Engine.
+ */
+
+#include "intern/eval/deg_eval.h"
+
+#include "PIL_time.h"
+
+extern "C" {
+#include "BLI_utildefines.h"
+#include "BLI_task.h"
+#include "BLI_ghash.h"
+
+#include "BKE_depsgraph.h"
+#include "BKE_global.h"
+
+#include "DEG_depsgraph.h"
+} /* extern "C" */
+
+#include "atomic_ops.h"
+
+#include "intern/eval/deg_eval_debug.h"
+#include "intern/eval/deg_eval_flush.h"
+#include "intern/nodes/deg_node.h"
+#include "intern/nodes/deg_node_component.h"
+#include "intern/nodes/deg_node_operation.h"
+#include "intern/depsgraph.h"
+#include "util/deg_util_foreach.h"
+
+/* Unfinished and unused, and takes quite some pre-processing time. */
+#undef USE_EVAL_PRIORITY
+
+/* Use integrated debugger to keep track how much each of the nodes was
+ * evaluating.
+ */
+#undef USE_DEBUGGER
+
+namespace DEG {
+
+/* ********************** */
+/* Evaluation Entrypoints */
+
+/* Forward declarations. */
+static void schedule_children(TaskPool *pool,
+                              Depsgraph *graph,
+                              OperationDepsNode *node,
+                              const int layers,
+                              const int thread_id);
+
+struct DepsgraphEvalState {
+	EvaluationContext *eval_ctx;
+	Depsgraph *graph;
+	int layers;
+};
+
+static void deg_task_run_func(TaskPool *pool,
+                              void *taskdata,
+                              int thread_id)
+{
+	DepsgraphEvalState *state =
+	        reinterpret_cast<DepsgraphEvalState *>(BLI_task_pool_userdata(pool));
+	OperationDepsNode *node = reinterpret_cast<OperationDepsNode *>(taskdata);
+
+	BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled");
+
+	/* Should only be the case for NOOPs, which never get to this point. */
+	BLI_assert(node->evaluate);
+
+	while (true) {
+		/* Get context. */
+		/* TODO: Who initialises this? "Init" operations aren't able to
+		 * initialise it!!!
+		 */
+		/* TODO(sergey): We don't use component contexts at this moment. */
+		/* ComponentDepsNode *comp = node->owner; */
+		BLI_assert(node->owner != NULL);
+
+		/* Since we're not leaving the thread for until the graph branches it is
+		 * possible to have NO-OP on the way. for which evaluate() will be NULL.
+		 * but that's all fine, we'll just scheduler it's children.
+		 */
+		if (node->evaluate) {
+			/* Take note of current time. */
+#ifdef USE_DEBUGGER
+			double start_time = PIL_check_seconds_timer();
+			DepsgraphDebug::task_started(state->graph, node);
+#endif
+
+			/* Perform operation. */
+			node->evaluate(state->eval_ctx);
+
+			/* Note how long this took. */
+#ifdef USE_DEBUGGER
+			double end_time = PIL_check_seconds_timer();
+			DepsgraphDebug::task_completed(state->graph,
+			                               node,
+			                               end_time - start_time);
+#endif
+		}
+
+		/* If there's only one outgoing link we try to immediately switch to
+		 * that node evaluation, without leaving the thread.
+		 *
+		 * It's only doable if the child don't have extra relations or all they
+		 * are satisfied.
+		 *
+		 * TODO(sergey): Checks here can be de-duplicated with the ones from
+		 * schedule_node(), however, how to do it nicely?
+		 */
+		if (node->outlinks.size() == 1) {
+			DepsRelation *rel = node->outlinks[0];
+			OperationDepsNode *child = (OperationDepsNode *)rel->to;
+			BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
+			if (!child->scheduled) {
+				int id_layers = child->owner->owner->layers;
+				if (!((child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 &&
+				      (id_layers & state->layers) != 0))
+				{
+					/* Node does not need an update, so can;t continue with the
+					 * chain and need to switch to another one by leaving the
+					 * thread.
+					 */
+					break;
+				}
+				if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
+					BLI_assert(child->num_links_pending > 0);
+					atomic_sub_uint32(&child->num_links_pending, 1);
+				}
+				if (child->num_links_pending == 0) {
+					bool is_scheduled = atomic_fetch_and_or_uint8(
+					        (uint8_t *)&child->scheduled, (uint8_t)true);
+					if (!is_scheduled) {
+						/* Node was not scheduled, switch to it! */
+						node = child;
+					}
+					else {
+						/* Someone else scheduled the node, leaving us
+						 * unemployed in this thread, we're leaving.
+						 */
+						break;
+					}
+				}
+				else {
+					/* There are other dependencies on the child, can't do
+					 * anything in the current thread.
+					 */
+					break;
+				}
+			}
+			else {
+				/* Happens when having cyclic dependencies.
+				 *
+				 * Nothing to do here, single child was already scheduled, we
+				 * can leave the thread now.
+				 */
+				break;
+			}
+		}
+		else {
+			/* TODO(sergey): It's possible to use one of the outgoing relations
+			 * as a chain which we'll try to keep alive, but it's a bit more
+			 * involved change.
+			 */
+			schedule_children(pool, state->graph, node, state->layers, thread_id);
+			break;
+		}
+	}
+}
+
+typedef struct CalculatePengindData {
+	Depsgraph *graph;
+	int layers;
+} CalculatePengindData;
+
+static void calculate_pending_func(void *data_v, int i)
+{
+	CalculatePengindData *data = (CalculatePengindData *)data_v;
+	Depsgraph *graph = data->graph;
+	int layers = data->layers;
+	OperationDepsNode *node = graph->operations[i];
+	IDDepsNode *id_node = node->owner->owner;
+
+	node->num_links_pending = 0;
+	node->scheduled = false;
+
+	/* count number of inputs that need updates */
+	if ((id_node->layers & layers) != 0 &&
+	    (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
+	{
+		foreach (DepsRelation *rel, node->inlinks) {
+			if (rel->from->type == DEPSNODE_TYPE_OPERATION &&
+			    (rel->flag & DEPSREL_FLAG_CYCLIC) == 0)
+			{
+				OperationDepsNode *from = (OperationDepsNode *)rel->from;
+				IDDepsNode *id_from_node = from->owner->owner;
+				if ((id_from_node->layers & layers) != 0 &&
+				    (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
+				{
+					++node->num_links_pending;
+				}
+			}
+		}
+	}
+}
+
+static void calculate_pending_parents(Depsgraph *graph, int layers)
+{
+	const int num_operations = graph->operations.size();
+	const bool do_threads = num_operations > 256;
+	CalculatePengindData data;
+	data.graph = graph;
+	data.layers = layers;
+	BLI_task_parallel_range(0,
+	                        num_operations,
+	                        &data,
+	                        calculate_pending_func,
+	                        do_threads);
+}
+
+#ifdef USE_EVAL_PRIORITY
+static void calculate_eval_priority(OperationDepsNode *node)
+{
+	if (node->done) {
+		return;
+	}
+	node->done = 1;
+
+	if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+		/* XXX standard cost of a node, could be estimated somewhat later on */
+		const float cost = 1.0f;
+		/* NOOP nodes have no cost */
+		node->eval_priority = node->is_noop() ? cost : 0.0f;
+
+		foreach (DepsRelation *rel, node->outlinks) {
+			OperationDepsNode *to = (OperationDepsNode *)rel->to;
+			BLI_assert(to->type == DEPSNODE_TYPE_OPERATION);
+			calculate_eval_priority(to);
+			node->eval_priority += to->eval_priority;
+		}
+	}
+	else {
+		node->eval_priority = 0.0f;
+	}
+}
+#endif
+
+/* Schedule a node if it needs evaluation.
+ *   dec_parents: Decrement pending parents count, true when child nodes are
+ *                scheduled after a task has been completed.
+ */
+static void schedule_node(TaskPool *pool, Depsgraph *graph, int layers,
+                          OperationDepsNode *node, bool dec_parents,
+                          const int thread_id)
+{
+	int id_layers = node->owner->owner->layers;
+
+	if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 &&
+	    (id_layers & layers) != 0)
+	{
+		if (dec_parents) {
+			BLI_assert(node->num_links_pending > 0);
+			atomic_sub_uint32(&node->num_links_pending, 1);
+		}
+
+		if (node->num_links_pending == 0) {
+			bool is_scheduled = atomic_fetch_and_or_uint8(
+			        (uint8_t *)&node->scheduled, (uint8_t)true);
+			if (!is_scheduled) {
+				if (node->is_noop()) {
+					/* skip NOOP node, schedule children right away */
+					schedule_children(pool, graph, node, layers, thread_id);
+				}
+				else {
+					/* children are scheduled once this task is completed */
+					BLI_task_pool_push_from_thread(pool,
+					                               deg_task_run_func,
+					                               node,
+					                               false,
+					                               TASK_PRIORITY_LOW,
+					                               thread_id);
+				}
+			}
+		}
+	}
+}
+
+static void schedule_graph(TaskPool *pool,
+                           Depsgraph *graph,
+                           const int layers)
+{
+	foreach (OperationDepsNode *node, graph->operations) {
+		schedule_node(pool, graph, layers, node, false, 0);
+	}
+}
+
+static void schedule_children(TaskPool *pool,
+                              Depsgraph *graph,
+                              OperationDepsNode *node,
+                              const int layers,
+                              const int thread_id)
+{
+	foreach (DepsRelation *rel, node->outlinks) {
+		OperationDepsNode *child = (OperationDepsNode *)rel->to;
+		BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
+		if (child->scheduled) {
+			/* Happens when having cyclic dependencies. */
+			continue;
+		}
+		schedule_node(pool,
+		              graph,
+		              layers,
+		              child,
+		              (rel->flag & DEPSREL_FLAG_CYCLIC) == 0,
+		              thread_id);
+	}
+}
+
+/**
+ * Evaluate all nodes tagged for updating,
+ * \warning This is usually done as part of main loop, but may also be
+ * called from frame-change update.
+ *
+ * \note Time sources should be all valid!
+ */
+void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
+                             Depsgraph *graph,
+                             const int layers)
+{
+	/* Generate base evaluation context, upon which all the others are derived. */
+	// TODO: this needs both main and scene access...
+
+	/* Nothing to update, early out. */
+	if (BLI_gset_size(graph->entry_tags) == 0) {
+		return;
+	}
+
+	/* Set time for the current graph evaluation context. */
+	TimeSourceDepsNode *time_src = graph->find_time_source();
+	eval_ctx->ctime = time_src->cfra;
+
+	/* XXX could use a separate pool for each eval context */
+	DepsgraphEvalState state;
+	state.eval_ctx = eval_ctx;
+	state.graph = graph;
+	state.layers = layers;
+
+	TaskScheduler *task_scheduler = BLI_task_scheduler_get();
+	TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state);
+
+	if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) {
+		BLI_pool_set_num_threads(task_pool, 1);
+	}
+
+	calculate_pending_parents(graph, layers);
+
+	/* Clear tags. */
+	foreach (OperationDepsNode *node, graph->operations) {
+		node->done = 0;
+	}
+
+	/* Calculate priority for operation nodes. */
+#ifdef USE_EVAL_PRIORITY
+	foreach (OperationDepsNode *node, graph->operations) {
+		calculate_eval_priority(node);
+	}
+#endif
+
+	DepsgraphDebug::eval_begin(eval_ctx);
+
+	schedule_graph(task_pool, graph, layers);
+
+	BLI_task_pool_work_and_wait(task_pool);
+	BLI_task_pool_free(task_pool);
+
+	DepsgraphDebug::eval_end(eval_ctx);
+
+	/* Clear any uncleared tags - just in case. */
+	deg_graph_clear_tags(graph);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/eval/deg_eval.h b/source/blender/depsgraph/intern/eval/deg_eval.h
new file mode 100644
index 00000000000..0d42f63433f
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval.h
@@ -0,0 +1,52 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/eval/deg_eval.cc
+ *  \ingroup depsgraph
+ *
+ * Evaluation engine entrypoints for Depsgraph Engine.
+ */
+
+#pragma once
+
+struct EvaluationContext;
+
+namespace DEG {
+
+struct Depsgraph;
+
+/**
+ * Evaluate all nodes tagged for updating,
+ * \warning This is usually done as part of main loop, but may also be
+ * called from frame-change update.
+ *
+ * \note Time sources should be all valid!
+ */
+void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
+                             Depsgraph *graph,
+                             const int layers);
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/eval/deg_eval_debug.cc b/source/blender/depsgraph/intern/eval/deg_eval_debug.cc
new file mode 100644
index 00000000000..cfadf74da4d
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval_debug.cc
@@ -0,0 +1,247 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Lukas Toenne
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/eval/deg_eval_debug.cc
+ *  \ingroup depsgraph
+ *
+ * Implementation of tools for debugging the depsgraph
+ */
+
+#include "intern/eval/deg_eval_debug.h"
+
+extern "C" {
+#include "BLI_listbase.h"
+#include "BLI_ghash.h"
+
+#include "DEG_depsgraph_debug.h"
+
+#include "WM_api.h"
+#include "WM_types.h"
+}  /* extern "C" */
+
+#include "intern/nodes/deg_node.h"
+#include "intern/nodes/deg_node_component.h"
+#include "intern/nodes/deg_node_operation.h"
+#include "intern/depsgraph_intern.h"
+
+namespace DEG {
+
+DepsgraphStats *DepsgraphDebug::stats = NULL;
+
+static string get_component_name(eDepsNode_Type type, const string &name = "")
+{
+	DepsNodeFactory *factory = deg_get_node_factory(type);
+	if (name.empty()) {
+		return string(factory->tname());
+	}
+	else {
+		return string(factory->tname()) + " | " + name;
+	}
+}
+
+static void times_clear(DepsgraphStatsTimes &times)
+{
+	times.duration_last = 0.0f;
+}
+
+static void times_add(DepsgraphStatsTimes &times, float time)
+{
+	times.duration_last += time;
+}
+
+void DepsgraphDebug::eval_begin(const EvaluationContext *UNUSED(eval_ctx))
+{
+	/* TODO(sergey): Stats are currently globally disabled. */
+	/* verify_stats(); */
+	reset_stats();
+}
+
+void DepsgraphDebug::eval_end(const EvaluationContext *UNUSED(eval_ctx))
+{
+	WM_main_add_notifier(NC_SPACE | ND_SPACE_INFO_REPORT, NULL);
+}
+
+void DepsgraphDebug::eval_step(const EvaluationContext *UNUSED(eval_ctx),
+                               const char *message)
+{
+#ifdef DEG_DEBUG_BUILD
+	if (deg_debug_eval_cb)
+		deg_debug_eval_cb(deg_debug_eval_userdata, message);
+#else
+	(void)message;  /* Ignored. */
+#endif
+}
+
+void DepsgraphDebug::task_started(Depsgraph *graph,
+                                  const OperationDepsNode *node)
+{
+	if (stats) {
+		BLI_spin_lock(&graph->lock);
+
+		ComponentDepsNode *comp = node->owner;
+		ID *id = comp->owner->id;
+
+		DepsgraphStatsID *id_stats = get_id_stats(id, true);
+		times_clear(id_stats->times);
+
+		/* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */
+		if (0) {
+			/* XXX component name usage needs cleanup! currently mixes identifier
+			 * and description strings!
+			 */
+			DepsgraphStatsComponent *comp_stats =
+			        get_component_stats(id, get_component_name(comp->type,
+			                                                   comp->name),
+			                            true);
+			times_clear(comp_stats->times);
+		}
+
+		BLI_spin_unlock(&graph->lock);
+	}
+}
+
+void DepsgraphDebug::task_completed(Depsgraph *graph,
+                                    const OperationDepsNode *node,
+                                    double time)
+{
+	if (stats) {
+		BLI_spin_lock(&graph->lock);
+
+		ComponentDepsNode *comp = node->owner;
+		ID *id = comp->owner->id;
+
+		DepsgraphStatsID *id_stats = get_id_stats(id, true);
+		times_add(id_stats->times, time);
+
+		/* XXX TODO use something like: if (id->flag & ID_DEG_DETAILS) {...} */
+		if (0) {
+			/* XXX component name usage needs cleanup! currently mixes identifier
+			 * and description strings!
+			 */
+			DepsgraphStatsComponent *comp_stats =
+			        get_component_stats(id,
+			                            get_component_name(comp->type,
+			                                               comp->name),
+			                            true);
+			times_add(comp_stats->times, time);
+		}
+
+		BLI_spin_unlock(&graph->lock);
+	}
+}
+
+/* ********** */
+/* Statistics */
+
+
+/* GHash callback */
+static void deg_id_stats_free(void *val)
+{
+	DepsgraphStatsID *id_stats = (DepsgraphStatsID *)val;
+
+	if (id_stats) {
+		BLI_freelistN(&id_stats->components);
+		MEM_freeN(id_stats);
+	}
+}
+
+void DepsgraphDebug::stats_init()
+{
+	if (!stats) {
+		stats = (DepsgraphStats *)MEM_callocN(sizeof(DepsgraphStats),
+		                                      "Depsgraph Stats");
+		stats->id_stats = BLI_ghash_new(BLI_ghashutil_ptrhash,
+		                                BLI_ghashutil_ptrcmp,
+		                                "Depsgraph ID Stats Hash");
+	}
+}
+
+void DepsgraphDebug::stats_free()
+{
+	if (stats) {
+		BLI_ghash_free(stats->id_stats, NULL, deg_id_stats_free);
+		MEM_freeN(stats);
+		stats = NULL;
+	}
+}
+
+void DepsgraphDebug::verify_stats()
+{
+	stats_init();
+}
+
+void DepsgraphDebug::reset_stats()
+{
+	if (!stats) {
+		return;
+	}
+
+	/* XXX this doesn't work, will immediately clear all info,
+	 * since most depsgraph updates have none or very few updates to handle.
+	 *
+	 * Could consider clearing only zero-user ID blocks here
+	 */
+//	BLI_ghash_clear(stats->id_stats, NULL, deg_id_stats_free);
+}
+
+DepsgraphStatsID *DepsgraphDebug::get_id_stats(ID *id, bool create)
+{
+	DepsgraphStatsID *id_stats = (DepsgraphStatsID *)BLI_ghash_lookup(stats->id_stats, id);
+
+	if (!id_stats && create) {
+		id_stats = (DepsgraphStatsID *)MEM_callocN(sizeof(DepsgraphStatsID),
+		                                           "Depsgraph ID Stats");
+		id_stats->id = id;
+
+		BLI_ghash_insert(stats->id_stats, id, id_stats);
+	}
+
+	return id_stats;
+}
+
+DepsgraphStatsComponent *DepsgraphDebug::get_component_stats(
+        DepsgraphStatsID *id_stats,
+        const string &name,
+        bool create)
+{
+	DepsgraphStatsComponent *comp_stats;
+	for (comp_stats = (DepsgraphStatsComponent *)id_stats->components.first;
+	     comp_stats != NULL;
+	     comp_stats = comp_stats->next)
+	{
+		if (STREQ(comp_stats->name, name.c_str()))
+			break;
+	}
+	if (!comp_stats && create) {
+		comp_stats = (DepsgraphStatsComponent *)MEM_callocN(sizeof(DepsgraphStatsComponent),
+		                                                    "Depsgraph Component Stats");
+		BLI_strncpy(comp_stats->name, name.c_str(), sizeof(comp_stats->name));
+		BLI_addtail(&id_stats->components, comp_stats);
+	}
+	return comp_stats;
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/eval/deg_eval_debug.h b/source/blender/depsgraph/intern/eval/deg_eval_debug.h
new file mode 100644
index 00000000000..9109019eb2d
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval_debug.h
@@ -0,0 +1,79 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/eval/deg_eval_debug.h
+ *  \ingroup depsgraph
+ */
+
+#pragma once
+
+#include "intern/depsgraph_types.h"
+
+struct ID;
+struct EvaluationContext;
+
+struct DepsgraphStats;
+struct DepsgraphStatsID;
+struct DepsgraphStatsComponent;
+
+namespace DEG {
+
+struct Depsgraph;
+struct DepsgraphSettings;
+struct OperationDepsNode;
+
+struct DepsgraphDebug {
+	static DepsgraphStats *stats;
+
+	static void stats_init();
+	static void stats_free();
+
+	static void verify_stats();
+	static void reset_stats();
+
+	static void eval_begin(const EvaluationContext *eval_ctx);
+	static void eval_end(const EvaluationContext *eval_ctx);
+	static void eval_step(const EvaluationContext *eval_ctx,
+	                      const char *message);
+
+	static void task_started(Depsgraph *graph, const OperationDepsNode *node);
+	static void task_completed(Depsgraph *graph,
+	                           const OperationDepsNode *node,
+	                           double time);
+
+	static DepsgraphStatsID *get_id_stats(ID *id, bool create);
+	static DepsgraphStatsComponent *get_component_stats(DepsgraphStatsID *id_stats,
+	                                                    const string &name,
+	                                                    bool create);
+	static DepsgraphStatsComponent *get_component_stats(ID *id,
+	                                                    const string &name,
+	                                                    bool create)
+	{
+		return get_component_stats(get_id_stats(id, create), name, create);
+	}
+};
+
+} // namespace DEG
diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc
new file mode 100644
index 00000000000..87313826763
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc
@@ -0,0 +1,211 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/depsgraph_tag.cc
+ *  \ingroup depsgraph
+ *
+ * Core routines for how the Depsgraph works.
+ */
+
+#include "intern/eval/deg_eval_flush.h"
+
+// TODO(sergey): Use some sort of wrapper.
+#include <queue>
+
+extern "C" {
+#include "DNA_object_types.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_task.h"
+#include "BLI_ghash.h"
+
+#include "DEG_depsgraph.h"
+} /* extern "C" */
+
+#include "intern/nodes/deg_node.h"
+#include "intern/nodes/deg_node_component.h"
+#include "intern/nodes/deg_node_operation.h"
+
+#include "intern/depsgraph_intern.h"
+#include "util/deg_util_foreach.h"
+
+namespace DEG {
+
+namespace {
+
+// TODO(sergey): De-duplicate with depsgraph_tag,cc
+void lib_id_recalc_tag(Main *bmain, ID *id)
+{
+	id->tag |= LIB_TAG_ID_RECALC;
+	DEG_id_type_tag(bmain, GS(id->name));
+}
+
+void lib_id_recalc_data_tag(Main *bmain, ID *id)
+{
+	id->tag |= LIB_TAG_ID_RECALC_DATA;
+	DEG_id_type_tag(bmain, GS(id->name));
+}
+
+}  /* namespace */
+
+typedef std::queue<OperationDepsNode *> FlushQueue;
+
+static void flush_init_func(void *data_v, int i)
+{
+	/* ID node's done flag is used to avoid multiple editors update
+	 * for the same ID.
+	 */
+	Depsgraph *graph = (Depsgraph *)data_v;
+	OperationDepsNode *node = graph->operations[i];
+	IDDepsNode *id_node = node->owner->owner;
+	id_node->done = 0;
+	node->scheduled = false;
+	node->owner->flags &= ~DEPSCOMP_FULLY_SCHEDULED;
+}
+
+/* Flush updates from tagged nodes outwards until all affected nodes
+ * are tagged.
+ */
+void deg_graph_flush_updates(Main *bmain, Depsgraph *graph)
+{
+	/* Sanity check. */
+	if (graph == NULL) {
+		return;
+	}
+
+	/* Nothing to update, early out. */
+	if (BLI_gset_size(graph->entry_tags) == 0) {
+		return;
+	}
+
+	/* TODO(sergey): With a bit of flag magic we can get rid of this
+	 * extra loop.
+	 */
+	const int num_operations = graph->operations.size();
+	const bool do_threads = num_operations > 256;
+	BLI_task_parallel_range(0,
+	                        num_operations,
+	                        graph,
+	                        flush_init_func,
+	                        do_threads);
+
+	FlushQueue queue;
+	/* Starting from the tagged "entry" nodes, flush outwards... */
+	/* NOTE: Also need to ensure that for each of these, there is a path back to
+	 *       root, or else they won't be done.
+	 * NOTE: Count how many nodes we need to handle - entry nodes may be
+	 *       component nodes which don't count for this purpose!
+	 */
+	GSET_FOREACH_BEGIN(OperationDepsNode *, node, graph->entry_tags)
+	{
+		IDDepsNode *id_node = node->owner->owner;
+		queue.push(node);
+		if (id_node->done == 0) {
+			deg_editors_id_update(bmain, id_node->id);
+			id_node->done = 1;
+		}
+		node->scheduled = true;
+	}
+	GSET_FOREACH_END();
+
+	while (!queue.empty()) {
+		OperationDepsNode *node = queue.front();
+		queue.pop();
+
+		IDDepsNode *id_node = node->owner->owner;
+		lib_id_recalc_tag(bmain, id_node->id);
+		/* TODO(sergey): For until we've got proper data nodes in the graph. */
+		lib_id_recalc_data_tag(bmain, id_node->id);
+
+		ID *id = id_node->id;
+		/* This code is used to preserve those areas which does direct
+		 * object update,
+		 *
+		 * Plus it ensures visibility changes and relations and layers
+		 * visibility update has proper flags to work with.
+		 */
+		if (GS(id->name) == ID_OB) {
+			Object *object = (Object *)id;
+			ComponentDepsNode *comp_node = node->owner;
+			if (comp_node->type == DEPSNODE_TYPE_ANIMATION) {
+				object->recalc |= OB_RECALC_TIME;
+			}
+			else if (comp_node->type == DEPSNODE_TYPE_TRANSFORM) {
+				object->recalc |= OB_RECALC_OB;
+			}
+			else {
+				object->recalc |= OB_RECALC_DATA;
+			}
+		}
+
+		/* Flush to nodes along links... */
+		foreach (DepsRelation *rel, node->outlinks) {
+			OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
+			if (to_node->scheduled == false) {
+				to_node->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
+				queue.push(to_node);
+				to_node->scheduled = true;
+				if (id_node->done == 0) {
+					deg_editors_id_update(bmain, id_node->id);
+					id_node->done = 1;
+				}
+			}
+		}
+
+		/* TODO(sergey): For until incremental updates are possible
+		 * witin a component at least we tag the whole component
+		 * for update.
+		 */
+		ComponentDepsNode *component = node->owner;
+		if ((component->flags & DEPSCOMP_FULLY_SCHEDULED) == 0) {
+			foreach (OperationDepsNode *op, component->operations) {
+				op->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
+			}
+			component->flags |= DEPSCOMP_FULLY_SCHEDULED;
+		}
+	}
+}
+
+static void graph_clear_func(void *data_v, int i)
+{
+	Depsgraph *graph = (Depsgraph *)data_v;
+	OperationDepsNode *node = graph->operations[i];
+	/* Clear node's "pending update" settings. */
+	node->flag &= ~(DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE);
+}
+
+/* Clear tags from all operation nodes. */
+void deg_graph_clear_tags(Depsgraph *graph)
+{
+	/* Go over all operation nodes, clearing tags. */
+	const int num_operations = graph->operations.size();
+	const bool do_threads = num_operations > 256;
+	BLI_task_parallel_range(0, num_operations, graph, graph_clear_func, do_threads);
+	/* Clear any entry tags which haven't been flushed. */
+	BLI_gset_clear(graph->entry_tags, NULL);
+}
+
+}  // namespace DEG
diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.h b/source/blender/depsgraph/intern/eval/deg_eval_flush.h
new file mode 100644
index 00000000000..8912aebee7d
--- /dev/null
+++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.h
@@ -0,0 +1,49 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/depsgraph/intern/eval/deg_eval_flush.cc
+ *  \ingroup depsgraph
+ *
+ * Core routines for how the Depsgraph works.
+ */
+
+#pragma once
+
+struct Main;
+
+namespace DEG {
+
+struct Depsgraph;
+
+/* Flush updates from tagged nodes outwards until all affected nodes
+ * are tagged.
+ */
+void deg_graph_flush_updates(struct Main *bmain, struct Depsgraph *graph);
+
+/* Clear tags from all operation nodes. */
+void deg_graph_clear_tags(struct Depsgraph *graph);
+
+}  // namespace DEG