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, 383 insertions, 22 deletions

diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 869404ae4a6..9ee9f3d57af 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -88,16 +88,25 @@
 
 #include "depsgraph_private.h"
 
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_build.h"
+#include "DEG_depsgraph_debug.h"
+#include "DEG_depsgraph_query.h"
+
+#ifdef WITH_LEGACY_DEPSGRAPH
+
 static SpinLock threaded_update_lock;
 
 void DAG_init(void)
 {
 	BLI_spin_init(&threaded_update_lock);
+	DEG_register_node_types();
 }
 
 void DAG_exit(void)
 {
 	BLI_spin_end(&threaded_update_lock);
+	DEG_free_node_types();
 }
 
 /* Queue and stack operations for dag traversal 
@@ -1329,8 +1338,14 @@ static void (*EditorsUpdateSceneCb)(Main *bmain, Scene *scene, int updated) = NU
 
 void DAG_editors_update_cb(void (*id_func)(Main *bmain, ID *id), void (*scene_func)(Main *bmain, Scene *scene, int updated))
 {
-	EditorsUpdateIDCb = id_func;
-	EditorsUpdateSceneCb = scene_func;
+	if (DEG_depsgraph_use_legacy()) {
+		EditorsUpdateIDCb = id_func;
+		EditorsUpdateSceneCb = scene_func;
+	}
+	else {
+		/* New dependency graph. */
+		DEG_editors_set_update_cb(id_func, scene_func);
+	}
 }
 
 static void dag_editors_id_update(Main *bmain, ID *id)
@@ -1529,7 +1544,7 @@ static void dag_scene_build(Main *bmain, Scene *sce)
 	Base *base;
 
 	BLI_listbase_clear(&tempbase);
-	
+
 	build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
 	
 	dag_check_cycle(sce->theDag);
@@ -1621,32 +1636,65 @@ static void dag_scene_build(Main *bmain, Scene *sce)
 /* clear all dependency graphs */
 void DAG_relations_tag_update(Main *bmain)
 {
-	Scene *sce;
-
-	for (sce = bmain->scene.first; sce; sce = sce->id.next)
-		dag_scene_free(sce);
+	if (DEG_depsgraph_use_legacy()) {
+		Scene *sce;
+		for (sce = bmain->scene.first; sce; sce = sce->id.next) {
+			dag_scene_free(sce);
+		}
+	}
+	else {
+		/* New dependency graph. */
+		DEG_relations_tag_update(bmain);
+	}
 }
 
 /* rebuild dependency graph only for a given scene */
 void DAG_scene_relations_rebuild(Main *bmain, Scene *sce)
 {
-	dag_scene_free(sce);
-	DAG_scene_relations_update(bmain, sce);
+	if (DEG_depsgraph_use_legacy()) {
+		dag_scene_free(sce);
+		DAG_scene_relations_update(bmain, sce);
+	}
+	else {
+		/* New dependency graph. */
+		DEG_scene_relations_rebuild(bmain, sce);
+	}
 }
 
 /* create dependency graph if it was cleared or didn't exist yet */
 void DAG_scene_relations_update(Main *bmain, Scene *sce)
 {
-	if (!sce->theDag)
-		dag_scene_build(bmain, sce);
+	if (DEG_depsgraph_use_legacy()) {
+		if (!sce->theDag)
+			dag_scene_build(bmain, sce);
+	}
+	else {
+		/* New dependency graph. */
+		DEG_scene_relations_update(bmain, sce);
+	}
+}
+
+void DAG_scene_relations_validate(Main *bmain, Scene *sce)
+{
+	if (!DEG_depsgraph_use_legacy()) {
+		DEG_debug_scene_relations_validate(bmain, sce);
+	}
 }
 
 void DAG_scene_free(Scene *sce)
 {
-	if (sce->theDag) {
-		free_forest(sce->theDag);
-		MEM_freeN(sce->theDag);
-		sce->theDag = NULL;
+	if (DEG_depsgraph_use_legacy()) {
+		if (sce->theDag) {
+			free_forest(sce->theDag);
+			MEM_freeN(sce->theDag);
+			sce->theDag = NULL;
+		}
+	}
+	else {
+		if (sce->depsgraph) {
+			DEG_graph_free(sce->depsgraph);
+			sce->depsgraph = NULL;
+		}
 	}
 }
 
@@ -1889,7 +1937,11 @@ void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const sho
 	DagAdjList *itA;
 	Object *ob;
 	int lasttime;
-	
+
+	if (!DEG_depsgraph_use_legacy()) {
+		return;
+	}
+
 	if (sce->theDag == NULL) {
 		printf("DAG zero... not allowed to happen!\n");
 		DAG_scene_relations_update(bmain, sce);
@@ -2300,7 +2352,7 @@ static void dag_current_scene_layers(Main *bmain, ListBase *lb)
 	}
 }
 
-static void dag_group_on_visible_update(Group *group)
+static void dag_group_on_visible_update(Scene *scene, Group *group)
 {
 	GroupObject *go;
 
@@ -2322,7 +2374,7 @@ static void dag_group_on_visible_update(Group *group)
 		}
 
 		if (go->ob->dup_group)
-			dag_group_on_visible_update(go->ob->dup_group);
+			dag_group_on_visible_update(scene, go->ob->dup_group);
 	}
 }
 
@@ -2330,7 +2382,13 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
 {
 	ListBase listbase;
 	DagSceneLayer *dsl;
-	
+
+	if (!DEG_depsgraph_use_legacy()) {
+		/* Inform new dependnecy graphs about visibility changes. */
+		DEG_on_visible_update(bmain, do_time);
+		return;
+	}
+
 	/* get list of visible scenes and layers */
 	dag_current_scene_layers(bmain, &listbase);
 	
@@ -2357,7 +2415,8 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
 			oblay = (node) ? node->lay : ob->lay;
 
 			if ((oblay & lay) & ~scene->lay_updated) {
-				if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE)) {
+				/* TODO(sergey): Why do we need armature here now but didn't need before? */
+				if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE, OB_ARMATURE)) {
 					ob->recalc |= OB_RECALC_DATA;
 					lib_id_recalc_tag(bmain, &ob->id);
 				}
@@ -2375,7 +2434,7 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
 					lib_id_recalc_tag(bmain, &ob->id);
 				}
 				if (ob->dup_group)
-					dag_group_on_visible_update(ob->dup_group);
+					dag_group_on_visible_update(scene, ob->dup_group);
 			}
 		}
 
@@ -2609,7 +2668,12 @@ void DAG_ids_flush_tagged(Main *bmain)
 	ListBase *lbarray[MAX_LIBARRAY];
 	int a;
 	bool do_flush = false;
-	
+
+	if (!DEG_depsgraph_use_legacy()) {
+		DEG_ids_flush_tagged(bmain);
+		return;
+	}
+
 	/* get list of visible scenes and layers */
 	dag_current_scene_layers(bmain, &listbase);
 
@@ -2653,6 +2717,11 @@ void DAG_ids_check_recalc(Main *bmain, Scene *scene, bool time)
 	int a;
 	bool updated = false;
 
+	if (!DEG_depsgraph_use_legacy()) {
+		DEG_ids_check_recalc(bmain, scene, time);
+		return;
+	}
+
 	/* loop over all ID types */
 	a  = set_listbasepointers(bmain, lbarray);
 
@@ -2769,6 +2838,11 @@ void DAG_ids_clear_recalc(Main *bmain)
 
 void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
 {
+	if (!DEG_depsgraph_use_legacy()) {
+		DEG_id_tag_update_ex(bmain, id, flag);
+		return;
+	}
+
 	if (id == NULL) return;
 
 	if (G.debug & G_DEBUG_DEPSGRAPH) {
@@ -3160,6 +3234,10 @@ short DAG_get_eval_flags_for_object(Scene *scene, void *object)
 {
 	DagNode *node;
 
+	if (!DEG_depsgraph_use_legacy()) {
+		return DEG_get_eval_flags_for_id(scene->depsgraph, (ID*)object);
+	}
+
 	if (scene->theDag == NULL) {
 		/* Happens when converting objects to mesh from a python script
 		 * after modifying scene graph.
@@ -3198,3 +3276,286 @@ bool DAG_is_acyclic(Scene *scene)
 {
 	return scene->theDag->is_acyclic;
 }
+
+#else
+
+/* *********************************************************************
+ * Stubs to avoid linking issues and make sure legacy crap is not used *
+ * *********************************************************************
+ */
+
+DagNodeQueue *queue_create(int UNUSED(slots))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+void queue_raz(DagNodeQueue *UNUSED(queue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void queue_delete(DagNodeQueue *UNUSED(queue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void push_queue(DagNodeQueue *UNUSED(queue), DagNode *UNUSED(node))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void push_stack(DagNodeQueue *UNUSED(queue), DagNode *UNUSED(node))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+DagNode *pop_queue(DagNodeQueue *UNUSED(queue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagNode *get_top_node_queue(DagNodeQueue *UNUSED(queue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagForest *dag_init(void)
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagForest *build_dag(Main *UNUSED(bmain),
+                     Scene *UNUSED(sce),
+                     short UNUSED(mask))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+void free_forest(DagForest *UNUSED(Dag))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+DagNode *dag_find_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagNode *dag_add_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagNode *dag_get_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+DagNode *dag_get_sub_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+void dag_add_relation(DagForest *UNUSED(forest),
+                      DagNode *UNUSED(fob1),
+                      DagNode *UNUSED(fob2),
+                      short UNUSED(rel),
+                      const char *UNUSED(name))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* debug test functions */
+
+void graph_print_queue(DagNodeQueue *UNUSED(nqueue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void graph_print_queue_dist(DagNodeQueue *UNUSED(nqueue))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void graph_print_adj_list(DagForest *UNUSED(dag))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void DAG_scene_flush_update(Main *UNUSED(bmain),
+                            Scene *UNUSED(sce),
+                            unsigned int UNUSED(lay),
+                            const short UNUSED(time))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void DAG_scene_update_flags(Main *UNUSED(bmain),
+                            Scene *UNUSED(scene),
+                            unsigned int UNUSED(lay),
+                            const bool UNUSED(do_time),
+                            const bool UNUSED(do_invisible_flush))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* ******************* DAG FOR ARMATURE POSE ***************** */
+
+void DAG_pose_sort(Object *UNUSED(ob))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* ************************  DAG FOR THREADED UPDATE  ********************* */
+
+void DAG_threaded_update_begin(Scene *UNUSED(scene),
+                               void (*func)(void *node, void *user_data),
+                               void *UNUSED(user_data))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	(void)func;
+}
+
+void DAG_threaded_update_handle_node_updated(void *UNUSED(node_v),
+                                             void (*func)(void *node, void *user_data),
+                                             void *UNUSED(user_data))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	(void)func;
+}
+
+/* ************************ DAG querying ********************* */
+
+Object *DAG_get_node_object(void *UNUSED(node_v))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return NULL;
+}
+
+const char *DAG_get_node_name(Scene *UNUSED(scene), void *UNUSED(node_v))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return "INVALID";
+}
+
+bool DAG_is_acyclic(Scene *UNUSED(scene))
+{
+	BLI_assert(!"Should not be used with new dependnecy graph");
+	return false;
+}
+
+/* ************************************
+ * This functions are to be supported *
+ * ************************************
+ */
+
+void DAG_init(void)
+{
+	DEG_register_node_types();
+}
+
+void DAG_exit(void)
+{
+	DEG_free_node_types();
+}
+
+/* ************************ API *********************** */
+
+void DAG_editors_update_cb(DEG_EditorUpdateIDCb id_func,
+                           DEG_EditorUpdateSceneCb scene_func)
+{
+	DEG_editors_set_update_cb(id_func, scene_func);
+}
+
+/* Tag all relations for update. */
+void DAG_relations_tag_update(Main *bmain)
+{
+	DEG_relations_tag_update(bmain);
+}
+
+/* Rebuild dependency graph only for a given scene. */
+void DAG_scene_relations_rebuild(Main *bmain, Scene *scene)
+{
+	DEG_scene_relations_rebuild(bmain, scene);
+}
+
+/* Create dependency graph if it was cleared or didn't exist yet. */
+void DAG_scene_relations_update(Main *bmain, Scene *scene)
+{
+	DEG_scene_relations_update(bmain, scene);
+}
+
+void DAG_scene_relations_validate(Main *bmain, Scene *scene)
+{
+	DEG_debug_scene_relations_validate(bmain, scene);
+}
+
+void DAG_scene_free(Scene *scene)
+{
+	DEG_scene_graph_free(scene);
+}
+
+void DAG_on_visible_update(Main *bmain, const bool do_time)
+{
+	DEG_on_visible_update(bmain, do_time);
+}
+
+void DAG_ids_check_recalc(Main *bmain, Scene *scene, bool time)
+{
+	DEG_ids_check_recalc(bmain, scene, time);
+}
+
+void DAG_id_tag_update(ID *id, short flag)
+{
+	DEG_id_tag_update_ex(G.main, id, flag);
+}
+
+void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
+{
+	DEG_id_tag_update_ex(bmain, id, flag);
+}
+
+void DAG_id_type_tag(Main *bmain, short idtype)
+{
+	DEG_id_type_tag(bmain, idtype);
+}
+
+int DAG_id_type_tagged(Main *bmain, short idtype)
+{
+	return DEG_id_type_tagged(bmain, idtype);
+}
+
+void DAG_ids_clear_recalc(Main *bmain)
+{
+	DEG_ids_clear_recalc(bmain);
+}
+
+short DAG_get_eval_flags_for_object(Scene *scene, void *object)
+{
+	return DEG_get_eval_flags_for_id(scene->depsgraph, (ID*)object);
+}
+
+void DAG_ids_flush_tagged(Main *bmain)
+{
+	DEG_ids_flush_tagged(bmain);
+}
+
+/* ************************ DAG DEBUGGING ********************* */
+
+void DAG_print_dependencies(Main *UNUSED(bmain),
+                            Scene *scene,
+                            Object *UNUSED(ob))
+{
+	DEG_debug_graphviz(scene->depsgraph, stdout, "Depsgraph", false);
+}
+
+#endif