Depsgraph: New dependency graph integration commit

This commit integrates the work done so far on the new dependency graph system,
where goal was to replace legacy depsgraph with the new one, supporting loads of
neat features like:

- More granular dependency relation nature, which solves issues with fake cycles
  in the dependencies.

- Move towards all-animatable, by better integration of drivers into the system.

- Lay down some basis for upcoming copy-on-write, overrides and so on.

The new system is living side-by-side with the previous one and disabled by
default, so nothing will become suddenly broken. The way to enable new depsgraph
is to pass `--new-depsgraph` command line argument.

It's a bit early to consider the system production-ready, there are some TODOs
and issues were discovered during the merge period, they'll be addressed ASAP.
But it's important to merge, because it's the only way to attract artists to
really start testing this system.

There are number of assorted documents related on the design of the new system:

* http://wiki.blender.org/index.php/User:Aligorith/GSoC2013_Depsgraph#Design_Documents
* http://wiki.blender.org/index.php/User:Nazg-gul/DependencyGraph

There are also some user-related information online:

* http://code.blender.org/2015/02/blender-dependency-graph-branch-for-users/
* http://code.blender.org/2015/03/more-dependency-graph-tricks/

Kudos to everyone who was involved into the project:

- Joshua "Aligorith" Leung -- design specification, initial code
- Lukas "lukas_t" Toenne -- integrating code into blender, with further fixes
- Sergey "Sergey" "Sharybin" -- some mocking around, trying to wrap up the
  project and so
- Bassam "slikdigit" Kurdali -- stressing the new system, reporting all the
  issues and recording/writing documentation.
- Everyone else who i forgot to mention here :)

1 files changed, 386 insertions, 0 deletions

diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cc b/source/blender/depsgraph/intern/depsgraph_eval.cc
new file mode 100644
index 00000000000..11fd02376a3
--- /dev/null
+++ b/source/blender/depsgraph/intern/depsgraph_eval.cc
@@ -0,0 +1,386 @@
+/*
+ * ***** 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 *****
+ *
+ * Evaluation engine entrypoints for Depsgraph Engine
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "PIL_time.h"
+
+extern "C" {
+#include "BLI_utildefines.h"
+#include "BLI_task.h"
+
+#include "BKE_depsgraph.h"
+#include "BKE_scene.h"
+
+#include "DEG_depsgraph.h"
+} /* extern "C" */
+
+#include "atomic_ops.h"
+
+#include "depsgraph.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+#include "depsgraph_debug.h"
+
+#ifdef WITH_LEGACY_DEPSGRAPH
+static bool use_legacy_depsgraph = true;
+#endif
+
+bool DEG_depsgraph_use_legacy(void)
+{
+#ifdef DISABLE_NEW_DEPSGRAPH
+	return true;
+#elif defined(WITH_LEGACY_DEPSGRAPH)
+	return use_legacy_depsgraph;
+#else
+	BLI_assert(!"Should not be used with new depsgraph");
+	return false;
+#endif
+}
+
+void DEG_depsgraph_switch_to_legacy(void)
+{
+#ifdef WITH_LEGACY_DEPSGRAPH
+	use_legacy_depsgraph = true;
+#else
+	BLI_assert(!"Should not be used with new depsgraph");
+#endif
+}
+
+void DEG_depsgraph_switch_to_new(void)
+{
+#ifdef WITH_LEGACY_DEPSGRAPH
+	use_legacy_depsgraph = false;
+#else
+	BLI_assert(!"Should not be used with new depsgraph");
+#endif
+}
+
+/* ****************** */
+/* Evaluation Context */
+
+/* Create new evaluation context. */
+EvaluationContext *DEG_evaluation_context_new(int mode)
+{
+	EvaluationContext *eval_ctx =
+		(EvaluationContext *)MEM_callocN(sizeof(EvaluationContext),
+		                                 "EvaluationContext");
+	eval_ctx->mode = mode;
+	return eval_ctx;
+}
+
+/**
+ * Initialize evaluation context.
+ * Used by the areas which currently overrides the context or doesn't have
+ * access to a proper one.
+ */
+void DEG_evaluation_context_init(EvaluationContext *eval_ctx, int mode)
+{
+	eval_ctx->mode = mode;
+}
+
+/* Free evaluation context. */
+void DEG_evaluation_context_free(EvaluationContext *eval_ctx)
+{
+	MEM_freeN(eval_ctx);
+}
+
+/* ********************** */
+/* Evaluation Entrypoints */
+
+/* Forward declarations. */
+static void schedule_children(TaskPool *pool,
+                              Depsgraph *graph,
+                              OperationDepsNode *node,
+                              const int layers);
+
+struct DepsgraphEvalState {
+	EvaluationContext *eval_ctx;
+	Depsgraph *graph;
+	int layers;
+};
+
+static void deg_task_run_func(TaskPool *pool,
+                              void *taskdata,
+                              int UNUSED(threadid))
+{
+	DepsgraphEvalState *state = (DepsgraphEvalState *)BLI_task_pool_userdata(pool);
+	OperationDepsNode *node = (OperationDepsNode *)taskdata;
+
+	if (!node->is_noop()) {
+		/* Get context. */
+		// TODO: who initialises this? "Init" operations aren't able to initialise it!!!
+		/* TODO(sergey): Wedon't use component contexts at this moment. */
+		/* ComponentDepsNode *comp = node->owner; */
+		BLI_assert(node->owner != NULL);
+
+		/* Take note of current time. */
+		double start_time = PIL_check_seconds_timer();
+		DepsgraphDebug::task_started(state->graph, node);
+
+		/* Should only be the case for NOOPs, which never get to this point. */
+		BLI_assert(node->evaluate);
+
+		/* Perform operation. */
+		node->evaluate(state->eval_ctx);
+
+		/* Note how long this took. */
+		double end_time = PIL_check_seconds_timer();
+		DepsgraphDebug::task_completed(state->graph,
+		                               node,
+		                               end_time - start_time);
+	}
+
+	schedule_children(pool, state->graph, node, state->layers);
+}
+
+static void calculate_pending_parents(Depsgraph *graph, int layers)
+{
+	for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
+	     it_op != graph->operations.end();
+	     ++it_op)
+	{
+		OperationDepsNode *node = *it_op;
+		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)
+		{
+			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 &&
+				    (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_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;
+
+		for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin();
+		     it != node->outlinks.end();
+		     ++it)
+		{
+			DepsRelation *rel = *it;
+			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;
+	}
+}
+
+static void schedule_graph(TaskPool *pool,
+                           Depsgraph *graph,
+                           const int layers)
+{
+	BLI_spin_lock(&graph->lock);
+	for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
+	     it != graph->operations.end();
+	     ++it)
+	{
+		OperationDepsNode *node = *it;
+		IDDepsNode *id_node = node->owner->owner;
+		if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) &&
+		    node->num_links_pending == 0 &&
+		    (id_node->layers & layers) != 0)
+		{
+			BLI_task_pool_push(pool, deg_task_run_func, node, false, TASK_PRIORITY_LOW);
+			node->scheduled = true;
+		}
+	}
+	BLI_spin_unlock(&graph->lock);
+}
+
+static void schedule_children(TaskPool *pool,
+                              Depsgraph *graph,
+                              OperationDepsNode *node,
+                              const int layers)
+{
+	for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin();
+	     it != node->outlinks.end();
+	     ++it)
+	{
+		DepsRelation *rel = *it;
+		OperationDepsNode *child = (OperationDepsNode *)rel->to;
+		BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
+
+		if (child->scheduled) {
+			/* Happens when having cyclic dependencies. */
+			continue;
+		}
+
+		IDDepsNode *id_child = child->owner->owner;
+		if ((id_child->layers & layers) != 0 &&
+		    (child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
+		{
+			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) {
+				BLI_spin_lock(&graph->lock);
+				bool need_schedule = !child->scheduled;
+				child->scheduled = true;
+				BLI_spin_unlock(&graph->lock);
+
+				if (need_schedule) {
+					BLI_task_pool_push(pool, deg_task_run_func, child, false, TASK_PRIORITY_LOW);
+				}
+			}
+		}
+	}
+}
+
+/**
+ * Evaluate all nodes tagged for updating,
+ * \warning This is usually done as part of main loop, but may also be
+ * called from frame-change update.
+ *
+ * \note Time sources should be all valid!
+ */
+void DEG_evaluate_on_refresh_ex(EvaluationContext *eval_ctx,
+                                Depsgraph *graph,
+                                const int layers)
+{
+	/* Generate base evaluation context, upon which all the others are derived. */
+	// TODO: this needs both main and scene access...
+
+	/* Nothing to update, early out. */
+	if (graph->entry_tags.size() == 0) {
+		return;
+	}
+
+	/* Set time for the current graph evaluation context. */
+	TimeSourceDepsNode *time_src = graph->find_time_source();
+	eval_ctx->ctime = time_src->cfra;
+
+	/* XXX could use a separate pool for each eval context */
+	DepsgraphEvalState state;
+	state.eval_ctx = eval_ctx;
+	state.graph = graph;
+	state.layers = layers;
+
+	TaskScheduler *task_scheduler = BLI_task_scheduler_get();
+	TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state);
+
+	calculate_pending_parents(graph, layers);
+
+	/* Clear tags. */
+	for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
+	     it != graph->operations.end();
+	     ++it)
+	{
+		OperationDepsNode *node = *it;
+		node->done = 0;
+	}
+
+	/* Calculate priority for operation nodes. */
+	for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
+	     it != graph->operations.end();
+	     ++it)
+	{
+		OperationDepsNode *node = *it;
+		calculate_eval_priority(node);
+	}
+
+	DepsgraphDebug::eval_begin(eval_ctx);
+
+	schedule_graph(task_pool, graph, layers);
+
+	BLI_task_pool_work_and_wait(task_pool);
+	BLI_task_pool_free(task_pool);
+
+	DepsgraphDebug::eval_end(eval_ctx);
+
+	/* Clear any uncleared tags - just in case. */
+	DEG_graph_clear_tags(graph);
+}
+
+/* Evaluate all nodes tagged for updating. */
+void DEG_evaluate_on_refresh(EvaluationContext *eval_ctx,
+                             Depsgraph *graph,
+                             Scene *scene)
+{
+	/* Update time on primary timesource. */
+	TimeSourceDepsNode *tsrc = graph->find_time_source();
+	tsrc->cfra = BKE_scene_frame_get(scene);;
+
+	DEG_evaluate_on_refresh_ex(eval_ctx, graph, graph->layers);
+}
+
+/* Frame-change happened for root scene that graph belongs to. */
+void DEG_evaluate_on_framechange(EvaluationContext *eval_ctx,
+                                 Main *bmain,
+                                 Depsgraph *graph,
+                                 float ctime,
+                                 const int layers)
+{
+	/* Update time on primary timesource. */
+	TimeSourceDepsNode *tsrc = graph->find_time_source();
+	tsrc->cfra = ctime;
+
+	tsrc->tag_update(graph);
+
+	DEG_graph_flush_updates(bmain, graph);
+
+	/* Perform recalculation updates. */
+	DEG_evaluate_on_refresh_ex(eval_ctx, graph, layers);
+}