Dependency Graph: some refactoring which should have no user visible impact

besides performance in some cases.

* DAG_scene_sort is now removed and replaced by DAG_relations_tag_update in
  most cases. This will clear the dependency graph, and only rebuild it right
  before it's needed again when the scene is re-evaluated.

  This is done because DAG_scene_sort is slow when called many times from
  python operators. Further the scene argument is not needed because most
  operations can potentially affect more than the current scene.

* DAG_scene_relations_update will now rebuild the dependency graph if it's not
  there yet, and DAG_scene_relations_rebuild will force a rebuild for the rare
  cases that need it.

* Remove various places where ob->recalc was set manually. This should go
  through DAG_id_tag_update() in nearly all cases instead since this is now
  a fast operation. Also removed DAG_ids_flush_update that goes along with
  such manual tagging of ob->recalc.

7 files changed, 74 insertions, 50 deletions

diff --git a/source/blender/blenkernel/intern/anim.c b/source/blender/blenkernel/intern/anim.c
index a6b3008e00a..50fe1f7a433 100644
--- a/source/blender/blenkernel/intern/anim.c
+++ b/source/blender/blenkernel/intern/anim.c
@@ -320,7 +320,7 @@ static void motionpaths_calc_optimise_depsgraph(Scene *scene, ListBase *targets)
 	}
 	
 	/* "brew me a list that's sorted a bit faster now depsy" */
-	DAG_scene_sort(G.main, scene);
+	DAG_scene_relations_rebuild(G.main, scene);
 }
 
 /* update scene for current frame */
diff --git a/source/blender/blenkernel/intern/blender.c b/source/blender/blenkernel/intern/blender.c
index fb2d1a3aaf7..be316197078 100644
--- a/source/blender/blenkernel/intern/blender.c
+++ b/source/blender/blenkernel/intern/blender.c
@@ -1000,8 +1000,7 @@ int BKE_copybuffer_paste(bContext *C, char *libname, ReportList *reports)
 	flag_all_listbases_ids(LIB_PRE_EXISTING, 0);
 	
 	/* recreate dependency graph to include new objects */
-	DAG_scene_sort(bmain, scene);
-	DAG_ids_flush_update(bmain, 0);
+	DAG_relations_tag_update(bmain);
 	
 	BLO_blendhandle_close(bh);
 	/* remove library... */
diff --git a/source/blender/blenkernel/intern/constraint.c b/source/blender/blenkernel/intern/constraint.c
index 1a25def3829..48ad3f51389 100644
--- a/source/blender/blenkernel/intern/constraint.c
+++ b/source/blender/blenkernel/intern/constraint.c
@@ -4261,7 +4261,7 @@ static void con_unlink_refs_cb(bConstraint *UNUSED(con), ID **idpoin, short isRe
 
 /* Free data of a specific constraint if it has any info.
  * be sure to run BIK_clear_data() when freeing an IK constraint,
- * unless DAG_scene_sort is called. 
+ * unless DAG_relations_tag_update is called. 
  */
 void BKE_free_constraint_data(bConstraint *con)
 {
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 99d0c5ed964..56600069aa0 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -837,7 +837,6 @@ DagForest *build_dag(Main *bmain, Scene *sce, short mask)
 	DagAdjList *itA;
 
 	dag = sce->theDag;
-	sce->dagisvalid = 1;
 	if (dag)
 		free_forest(dag);
 	else {
@@ -1846,8 +1845,18 @@ static void scene_sort_groups(Main *bmain, Scene *sce)
 	}
 }
 
+/* free the depency graph */
+static void dag_scene_free(Scene *sce)
+{
+	if (sce->theDag) {
+		free_forest(sce->theDag);
+		MEM_freeN(sce->theDag);
+		sce->theDag = NULL;
+	}
+}
+
 /* sort the base list on dependency order */
-void DAG_scene_sort(Main *bmain, Scene *sce)
+static void dag_scene_build(Main *bmain, Scene *sce)
 {
 	DagNode *node, *rootnode;
 	DagNodeQueue *nqueue;
@@ -1856,7 +1865,7 @@ void DAG_scene_sort(Main *bmain, Scene *sce)
 	int skip = 0;
 	ListBase tempbase;
 	Base *base;
-	
+
 	tempbase.first = tempbase.last = NULL;
 	
 	build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
@@ -1936,10 +1945,34 @@ void DAG_scene_sort(Main *bmain, Scene *sce)
 			printf(" %s\n", base->object->id.name);
 		}
 	}
+
 	/* temporal...? */
 	sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
 }
 
+/* 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);
+}
+
+/* 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);
+}
+
+/* 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);
+}
+
 static void lib_id_recalc_tag(Main *bmain, ID *id)
 {
 	id->flag |= LIB_ID_RECALC;
@@ -2177,7 +2210,7 @@ void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const sho
 	
 	if (sce->theDag == NULL) {
 		printf("DAG zero... not allowed to happen!\n");
-		DAG_scene_sort(bmain, sce);
+		DAG_scene_relations_update(bmain, sce);
 	}
 	
 	firstnode = sce->theDag->DagNode.first;  /* always scene node */
@@ -2545,20 +2578,6 @@ static void dag_current_scene_layers(Main *bmain, ListBase *lb)
 	}
 }
 
-void DAG_ids_flush_update(Main *bmain, int time)
-{
-	ListBase listbase;
-	DagSceneLayer *dsl;
-	
-	/* get list of visible scenes and layers */
-	dag_current_scene_layers(bmain, &listbase);
-
-	for (dsl = listbase.first; dsl; dsl = dsl->next)
-		DAG_scene_flush_update(bmain, dsl->scene, dsl->layer, time);
-	
-	BLI_freelistN(&listbase);
-}
-
 void DAG_on_visible_update(Main *bmain, const short do_time)
 {
 	ListBase listbase;
@@ -3169,7 +3188,7 @@ void DAG_print_dependencies(Main *bmain, Scene *scene, Object *ob)
 	}
 	else {
 		printf("\nDEPENDENCY RELATIONS for %s\n\n", scene->id.name + 2);
-		DAG_scene_sort(bmain, scene);
+		DAG_scene_relations_rebuild(bmain, scene);
 	}
 	
 	dag_print_dependencies = 0;
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 58b47398a7d..95b1809bbae 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -74,6 +74,7 @@
 #include "BKE_bullet.h"
 #include "BKE_colortools.h"
 #include "BKE_deform.h"
+#include "BKE_depsgraph.h"
 #include "BKE_DerivedMesh.h"
 #include "BKE_animsys.h"
 #include "BKE_anim.h"
@@ -406,7 +407,8 @@ static void unlink_object__unlinkModifierLinks(void *userData, Object *ob, Objec
 
 	if (*obpoin == unlinkOb) {
 		*obpoin = NULL;
-		ob->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME; // XXX: should this just be OB_RECALC_DATA?
+		// XXX: should this just be OB_RECALC_DATA?
+		DAG_id_tag_update(&ob->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 	}
 }
 
@@ -440,14 +442,14 @@ void BKE_object_unlink(Object *ob)
 			obt->proxy = NULL;
 		if (obt->proxy_from == ob) {
 			obt->proxy_from = NULL;
-			obt->recalc |= OB_RECALC_OB;
+			DAG_id_tag_update(&obt->id, OB_RECALC_OB);
 		}
 		if (obt->proxy_group == ob)
 			obt->proxy_group = NULL;
 		
 		if (obt->parent == ob) {
 			obt->parent = NULL;
-			obt->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+			DAG_id_tag_update(&obt->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 		}
 		
 		modifiers_foreachObjectLink(obt, unlink_object__unlinkModifierLinks, ob);
@@ -457,15 +459,15 @@ void BKE_object_unlink(Object *ob)
 
 			if (cu->bevobj == ob) {
 				cu->bevobj = NULL;
-				obt->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+				DAG_id_tag_update(&obt->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 			}
 			if (cu->taperobj == ob) {
 				cu->taperobj = NULL;
-				obt->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+				DAG_id_tag_update(&obt->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 			}
 			if (cu->textoncurve == ob) {
 				cu->textoncurve = NULL;
-				obt->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+				DAG_id_tag_update(&obt->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 			}
 		}
 		else if (obt->type == OB_ARMATURE && obt->pose) {
@@ -483,7 +485,7 @@ void BKE_object_unlink(Object *ob)
 							if (ct->tar == ob) {
 								ct->tar = NULL;
 								ct->subtarget[0] = '\0';
-								obt->recalc |= OB_RECALC_DATA;
+								DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 							}
 						}
 						
@@ -497,7 +499,7 @@ void BKE_object_unlink(Object *ob)
 		}
 		else if (ELEM(OB_MBALL, ob->type, obt->type)) {
 			if (BKE_mball_is_basis_for(obt, ob))
-				obt->recalc |= OB_RECALC_DATA;
+				DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 		}
 		
 		sca_remove_ob_poin(obt, ob);
@@ -514,7 +516,7 @@ void BKE_object_unlink(Object *ob)
 					if (ct->tar == ob) {
 						ct->tar = NULL;
 						ct->subtarget[0] = '\0';
-						obt->recalc |= OB_RECALC_DATA;
+						DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 					}
 				}
 				
@@ -526,12 +528,12 @@ void BKE_object_unlink(Object *ob)
 		/* object is deflector or field */
 		if (ob->pd) {
 			if (obt->soft)
-				obt->recalc |= OB_RECALC_DATA;
+				DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 
 			/* cloth */
 			for (md = obt->modifiers.first; md; md = md->next)
 				if (md->type == eModifierType_Cloth)
-					obt->recalc |= OB_RECALC_DATA;
+					DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 		}
 		
 		/* strips */
@@ -560,14 +562,14 @@ void BKE_object_unlink(Object *ob)
 				for (; pt; pt = pt->next) {
 					if (pt->ob == ob) {
 						pt->ob = NULL;
-						obt->recalc |= OB_RECALC_DATA;
+						DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 						break;
 					}
 				}
 
 				if (tpsys->target_ob == ob) {
 					tpsys->target_ob = NULL;
-					obt->recalc |= OB_RECALC_DATA;
+					DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 				}
 
 				if (tpsys->part->dup_ob == ob)
@@ -602,7 +604,7 @@ void BKE_object_unlink(Object *ob)
 				}
 			}
 			if (ob->pd)
-				obt->recalc |= OB_RECALC_DATA;
+				DAG_id_tag_update(&obt->id, OB_RECALC_DATA);
 		}
 
 		obt = obt->id.next;
@@ -970,7 +972,7 @@ Object *BKE_object_add(struct Scene *scene, int type)
 	base = BKE_scene_base_add(scene, ob);
 	BKE_scene_base_deselect_all(scene);
 	BKE_scene_base_select(scene, base);
-	ob->recalc |= OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+	DAG_id_tag_update(&ob->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 
 	return ob;
 }
@@ -1480,7 +1482,8 @@ void BKE_object_make_proxy(Object *ob, Object *target, Object *gob)
 	ob->proxy_group = gob;
 	id_lib_extern(&target->id);
 	
-	ob->recalc = target->recalc = OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME;
+	DAG_id_tag_update(&ob->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
+	DAG_id_tag_update(&target->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 	
 	/* copy transform
 	 * - gob means this proxy comes from a group, just apply the matrix
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index c01ea4e518d..f90fde983aa 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -3509,12 +3509,12 @@ ModifierData *object_add_particle_system(Scene *scene, Object *ob, const char *n
 	psys->flag = PSYS_ENABLED | PSYS_CURRENT;
 	psys->cfra = BKE_scene_frame_get_from_ctime(scene, CFRA + 1);
 
-	DAG_scene_sort(G.main, scene);
+	DAG_relations_tag_update(G.main);
 	DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
 
 	return md;
 }
-void object_remove_particle_system(Scene *scene, Object *ob)
+void object_remove_particle_system(Scene *UNUSED(scene), Object *ob)
 {
 	ParticleSystem *psys = psys_get_current(ob);
 	ParticleSystemModifierData *psmd;
@@ -3552,7 +3552,7 @@ void object_remove_particle_system(Scene *scene, Object *ob)
 	else
 		ob->mode &= ~OB_MODE_PARTICLE_EDIT;
 
-	DAG_scene_sort(G.main, scene);
+	DAG_relations_tag_update(G.main);
 	DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
 }
 static void default_particle_settings(ParticleSettings *part)
diff --git a/source/blender/blenkernel/intern/scene.c b/source/blender/blenkernel/intern/scene.c
index 279c321d371..9a1a146c271 100644
--- a/source/blender/blenkernel/intern/scene.c
+++ b/source/blender/blenkernel/intern/scene.c
@@ -649,12 +649,11 @@ void BKE_scene_set_background(Main *bmain, Scene *scene)
 	}
 
 	/* sort baselist */
-	DAG_scene_sort(bmain, scene);
+	DAG_scene_relations_rebuild(bmain, scene);
 	
 	/* ensure dags are built for sets */
-	for (sce = scene->set; sce; sce = sce->set)
-		if (sce->theDag == NULL)
-			DAG_scene_sort(bmain, sce);
+	for (sce = scene; sce; sce = sce->set)
+		DAG_scene_relations_update(bmain, sce);
 
 	/* copy layers and flags from bases to objects */
 	for (base = scene->base.first; base; base = base->next) {
@@ -1150,9 +1149,15 @@ static void scene_update_tagged_recursive(Main *bmain, Scene *scene, Scene *scen
 /* this is called in main loop, doing tagged updates before redraw */
 void BKE_scene_update_tagged(Main *bmain, Scene *scene)
 {
+	Scene *sce_iter;
+	
 	/* keep this first */
 	BLI_callback_exec(bmain, &scene->id, BLI_CB_EVT_SCENE_UPDATE_PRE);
 
+	/* (re-)build dependency graph if needed */
+	for (sce_iter = scene; sce_iter; sce_iter = sce_iter->set)
+		DAG_scene_relations_update(bmain, sce_iter);
+
 	/* flush recalc flags to dependencies */
 	DAG_ids_flush_tagged(bmain);
 
@@ -1203,10 +1208,8 @@ void BKE_scene_update_for_newframe(Main *bmain, Scene *sce, unsigned int lay)
 	/* clear animation overrides */
 	/* XXX TODO... */
 
-	for (sce_iter = sce; sce_iter; sce_iter = sce_iter->set) {
-		if (sce_iter->theDag == NULL)
-			DAG_scene_sort(bmain, sce_iter);
-	}
+	for (sce_iter = sce; sce_iter; sce_iter = sce_iter->set)
+		DAG_scene_relations_update(bmain, sce_iter);
 
 	/* flush recalc flags to dependencies, if we were only changing a frame
 	 * this would not be necessary, but if a user or a script has modified