Depsgraph: Iterates over ID Nodes instead of Bases

Although this works by itself, it should actually happen after:

"Reshuffle collections base flags evaluation, make it so object is gathering
its base flags from collections."

Meanwhile we have one single hacky function (deg_flush_base_flags_and_settings)
to be removed once the task above is tackled.

Reviewers: sergey

Differential Revision: https://developer.blender.org/D2899

10 files changed, 172 insertions, 96 deletions

diff --git a/source/blender/depsgraph/DEG_depsgraph_query.h b/source/blender/depsgraph/DEG_depsgraph_query.h
index 1020d4e606e..59158ef0454 100644
--- a/source/blender/depsgraph/DEG_depsgraph_query.h
+++ b/source/blender/depsgraph/DEG_depsgraph_query.h
@@ -33,6 +33,8 @@
 #ifndef __DEG_DEPSGRAPH_QUERY_H__
 #define __DEG_DEPSGRAPH_QUERY_H__
 
+#include "BLI_ghash.h"
+
 #include "DEG_depsgraph.h"
 
 struct ID;
@@ -81,9 +83,6 @@ typedef struct DEGObjectsIteratorData {
 	struct Scene *scene;
 	struct EvaluationContext eval_ctx;
 
-	/* TODO(sergey): Base should never be a thing coming FROM depsgraph. */
-	struct Base *base;
-	int base_flag;
 	int flag;
 
 	/* **** Iteration over dupli-list. *** */
@@ -102,13 +101,16 @@ typedef struct DEGObjectsIteratorData {
 	 * other users of the iterator.
 	 */
 	struct Object temp_dupli_object;
+
+	/* **** ghash **** */
+	struct GHashIterator gh_iter;
+
 } DEGObjectsIteratorData;
 
 void DEG_objects_iterator_begin(struct BLI_Iterator *iter, DEGObjectsIteratorData *data);
 void DEG_objects_iterator_next(struct BLI_Iterator *iter);
 void DEG_objects_iterator_end(struct BLI_Iterator *iter);
 
-/* Temporary hacky solution waiting for cow depsgraph implementation. */
 #define DEG_OBJECT_ITER(graph_, instance_, flag_)                                 \
 	{                                                                             \
 		DEGObjectsIteratorData data_ = {                                          \
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
index ec60d86ec82..464a1454749 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
@@ -128,7 +128,7 @@ static void modifier_walk(void *user_data,
 {
 	BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
 	if (*obpoin) {
-		data->builder->build_object(data->scene, *obpoin);
+		data->builder->build_object(data->scene, *obpoin, DEG_ID_LINKED_INDIRECTLY);
 	}
 }
 
@@ -141,7 +141,7 @@ void constraint_walk(bConstraint * /*con*/,
 	if (*idpoin) {
 		ID *id = *idpoin;
 		if (GS(id->name) == ID_OB) {
-			data->builder->build_object(data->scene, (Object *)id);
+			data->builder->build_object(data->scene, (Object *)id, DEG_ID_LINKED_INDIRECTLY);
 		}
 	}
 }
@@ -203,6 +203,11 @@ IDDepsNode *DepsgraphNodeBuilder::add_id_node(ID *id, bool do_tag)
 	return id_node;
 }
 
+IDDepsNode *DepsgraphNodeBuilder::find_id_node(ID *id)
+{
+	return m_graph->find_id_node(id);
+}
+
 TimeSourceDepsNode *DepsgraphNodeBuilder::add_time_source()
 {
 	return m_graph->add_time_source();
@@ -392,27 +397,33 @@ void DepsgraphNodeBuilder::build_group(Scene *scene, Group *group)
 	group_id->tag |= LIB_TAG_DOIT;
 
 	LINKLIST_FOREACH (GroupObject *, go, &group->gobject) {
-		build_object(scene, go->ob);
+		build_object(scene, go->ob, DEG_ID_LINKED_INDIRECTLY);
 	}
 }
 
-void DepsgraphNodeBuilder::build_object(Scene *scene, Object *ob)
+void DepsgraphNodeBuilder::build_object(Scene *scene,
+                                        Object *ob,
+                                        eDepsNode_LinkedState_Type linked_state)
 {
 	/* Skip rest of components if the ID node was already there. */
 	if (ob->id.tag & LIB_TAG_DOIT) {
+		IDDepsNode *id_node = find_id_node(&ob->id);
+		id_node->linked_state = std::max(id_node->linked_state, linked_state);
 		return;
 	}
 	ob->id.tag |= LIB_TAG_DOIT;
 
-	/* Create ID node for obejct and begin init. */
+	/* Create ID node for object and begin init. */
 	IDDepsNode *id_node = add_id_node(&ob->id);
+	id_node->linked_state = linked_state;
+
 	ob->customdata_mask = 0;
 
 	/* Standard components. */
 	build_object_transform(scene, ob);
 
 	if (ob->parent != NULL) {
-		build_object(scene, ob->parent);
+		build_object(scene, ob->parent, linked_state);
 	}
 	if (ob->modifiers.first != NULL) {
 		BuilderWalkUserData data;
@@ -502,7 +513,7 @@ void DepsgraphNodeBuilder::build_object(Scene *scene, Object *ob)
 	/* Object that this is a proxy for. */
 	if (ob->proxy) {
 		ob->proxy->proxy_from = ob;
-		build_object(scene, ob->proxy);
+		build_object(scene, ob->proxy, DEG_ID_LINKED_INDIRECTLY);
 	}
 
 	/* Object dupligroup. */
@@ -1003,13 +1014,13 @@ void DepsgraphNodeBuilder::build_obdata_geom(Scene *scene, Object *ob)
 			 */
 			Curve *cu = (Curve *)obdata;
 			if (cu->bevobj != NULL) {
-				build_object(scene, cu->bevobj);
+				build_object(scene, cu->bevobj, DEG_ID_LINKED_INDIRECTLY);
 			}
 			if (cu->taperobj != NULL) {
-				build_object(scene, cu->taperobj);
+				build_object(scene, cu->taperobj, DEG_ID_LINKED_INDIRECTLY);
 			}
 			if (ob->type == OB_FONT && cu->textoncurve != NULL) {
-				build_object(scene, cu->textoncurve);
+				build_object(scene, cu->textoncurve, DEG_ID_LINKED_INDIRECTLY);
 			}
 			break;
 		}
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
index dbb126e2078..e7bf8c9998d 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
@@ -111,6 +111,7 @@ struct DepsgraphNodeBuilder {
 	void begin_build(Main *bmain);
 
 	IDDepsNode *add_id_node(ID *id, bool do_tag = true);
+	IDDepsNode *find_id_node(ID *id);
 	TimeSourceDepsNode *add_time_source();
 
 	ComponentDepsNode *add_component_node(ID *id,
@@ -156,9 +157,13 @@ struct DepsgraphNodeBuilder {
 	                                       const char *name = "",
 	                                       int name_tag = -1);
 
-	void build_scene(Main *bmain, Scene *scene);
+	void build_scene(Main *bmain,
+	                 Scene *scene,
+	                 eDepsNode_LinkedState_Type linked_state);
 	void build_group(Scene *scene, Group *group);
-	void build_object(Scene *scene, Object *ob);
+	void build_object(Scene *scene,
+	                  Object *ob,
+	                  eDepsNode_LinkedState_Type linked_state);
 	void build_object_transform(Scene *scene, Object *ob);
 	void build_object_constraints(Scene *scene, Object *ob);
 	void build_pose_constraints(Scene *scene, Object *ob, bPoseChannel *pchan);
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
index 20263e1d751..dabebb9d4a9 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes_rig.cc
@@ -304,7 +304,7 @@ void DepsgraphNodeBuilder::build_rig(Scene *scene, Object *object)
 		/* Custom shape. */
 		/* NOTE: Custom shape datablock is already remapped to CoW version. */
 		if (pchan->custom != NULL) {
-			build_object(scene, get_orig_datablock(pchan->custom));
+			build_object(scene, get_orig_datablock(pchan->custom), DEG_ID_LINKED_INDIRECTLY);
 		}
 	}
 }
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes_scene.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes_scene.cc
index a8acc88f7f3..097720f514a 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes_scene.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes_scene.cc
@@ -65,7 +65,7 @@ extern "C" {
 
 namespace DEG {
 
-void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene)
+void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene, eDepsNode_LinkedState_Type linked_state)
 {
 	/* scene ID block */
 	add_id_node(&scene->id);
@@ -77,7 +77,7 @@ void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene)
 	// XXX: depending on how this goes, that scene itself could probably store its
 	//      own little partial depsgraph?
 	if (scene->set) {
-		build_scene(bmain, scene->set);
+		build_scene(bmain, scene->set, DEG_ID_LINKED_VIA_SET);
 	}
 
 	/* scene objects */
@@ -85,12 +85,12 @@ void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene)
 	for (SceneLayer *sl = (SceneLayer *)scene->render_layers.first; sl; sl = sl->next) {
 		for (Base *base = (Base *)sl->object_bases.first; base; base = base->next) {
 			/* object itself */
-			build_object(scene, base->object);
+			build_object(scene, base->object, linked_state);
 			base->object->select_color = select_color++;
 		}
 	}
 	if (scene->camera != NULL) {
-		build_object(scene, scene->camera);
+		build_object(scene, scene->camera, linked_state);
 	}
 
 	/* rigidbody */
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index d58f61a5077..e58a5707bc9 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -209,7 +209,7 @@ void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene)
 	/* 1) Generate all the nodes in the graph first */
 	DEG::DepsgraphNodeBuilder node_builder(bmain, deg_graph);
 	node_builder.begin_build(bmain);
-	node_builder.build_scene(bmain, scene);
+	node_builder.build_scene(bmain, scene, DEG::DEG_ID_LINKED_DIRECTLY);
 
 	/* 2) Hook up relationships between operations - to determine evaluation
 	 *    order.
diff --git a/source/blender/depsgraph/intern/depsgraph_query.cc b/source/blender/depsgraph/intern/depsgraph_query.cc
index 9e9a2c38993..156b98a6421 100644
--- a/source/blender/depsgraph/intern/depsgraph_query.cc
+++ b/source/blender/depsgraph/intern/depsgraph_query.cc
@@ -33,6 +33,7 @@
 #include "MEM_guardedalloc.h"
 
 extern "C" {
+#include "BLI_ghash.h"
 #include "BLI_math.h"
 #include "BKE_anim.h"
 #include "BKE_idcode.h"
@@ -116,42 +117,57 @@ ID *DEG_get_evaluated_id(struct Depsgraph *depsgraph, ID *id)
 	return id_node->id_cow;
 }
 
-/* ************************ DAG ITERATORS ********************* */
+/* ************************ DEG ITERATORS ********************* */
 
-#define BASE_FLUSH_FLAGS (BASE_FROM_SET | BASE_FROMDUPLI)
-
-void DEG_objects_iterator_begin(BLI_Iterator *iter, DEGObjectsIteratorData *data)
+/**
+ * XXX (dfelinto/sergey) big hack, waiting for:
+ * "Reshuffle collections base flags evaluation, make it so object is gathering its base flags from collections."
+ *
+ * Returns false if object shouldn't be found (which should never happen in the final implementation
+ * and instead we should have a tag to the objects that were not directly part of the depsgraph).
+ *
+ * That means that the object is not in a collection but it's part of depsgraph, or the object is simply
+ * not in the current SceneLayer - Depsgraph at the moment includes all the SceneLayer in the Scene.
+ */
+static bool deg_flush_base_flags_and_settings(
+        DEGObjectsIteratorData *data, Object *ob_dst, Object *ob_src, const bool is_dupli)
 {
+	Base *base;
 	Depsgraph *graph = data->graph;
 	SceneLayer *scene_layer = DEG_get_evaluated_scene_layer(graph);
+	int flag = is_dupli ? BASE_FROMDUPLI : 0;
+
+	/* First attempt, see if object is in the current SceneLayer. */
+	base = (Base *)BLI_findptr(&scene_layer->object_bases, ob_src, offsetof(Base, object));
+
+	/* Next attempt, see if object is in one of the sets. */
+	if (base == NULL) {
+		Scene *scene_iter, *scene = DEG_get_evaluated_scene(graph);
+		scene_iter = scene;
+
+		while ((scene_iter = (scene_iter)->set)) {
+			SceneLayer *scene_layer_set = BKE_scene_layer_from_scene_get(scene_iter);
+			base = (Base *)BLI_findptr(&scene_layer_set->object_bases, ob_src, offsetof(Base, object));
+			if (base != NULL) {
+				flag |= BASE_FROM_SET;
+				flag &= ~(BASE_SELECTED | BASE_SELECTABLED);
+				break;
+			}
+		}
+	}
 
-	iter->data = data;
-	iter->valid = true;
-
-	data->scene = DEG_get_evaluated_scene(graph);
-	DEG_evaluation_context_init(&data->eval_ctx, DAG_EVAL_RENDER);
-
-	/* TODO(sergey): It's really confusing to store pointer to a local data. */
-	Base base = {(Base *)scene_layer->object_bases.first, NULL};
-	data->base = &base;
-
-	data->base_flag = ~(BASE_FLUSH_FLAGS);
-
-	data->dupli_parent = NULL;
-	data->dupli_list = NULL;
-	data->dupli_object_next = NULL;
-	data->dupli_object_current = NULL;
+	if (base == NULL) {
+		return false;
+	}
 
-	DEG_objects_iterator_next(iter);
-}
+	/* Make sure we have the base collection settings is already populated.
+	 * This will fail when BKE_layer_eval_layer_collection_pre hasn't run yet
+	 * Which usually means a missing call to DEG_id_tag_update(). */
+	BLI_assert(!BLI_listbase_is_empty(&base->collection_properties->data.group));
 
-/**
- * Temporary function to flush depsgraph until we get copy on write (CoW)
- */
-static void deg_flush_base_flags_and_settings(Object *ob, Base *base, const int flag)
-{
-	ob->base_flag = (base->flag | BASE_FLUSH_FLAGS) & flag;
-	ob->base_collection_properties = base->collection_properties;
+	ob_dst->base_flag = base->flag | flag;
+	ob_dst->base_collection_properties = base->collection_properties;
+	return true;
 }
 
 static bool deg_objects_dupli_iterator_next(BLI_Iterator *iter)
@@ -181,9 +197,10 @@ static bool deg_objects_dupli_iterator_next(BLI_Iterator *iter)
 		data->temp_dupli_object.select_color = data->dupli_parent->select_color;
 		copy_m4_m4(data->temp_dupli_object.obmat, dob->mat);
 
-		deg_flush_base_flags_and_settings(&data->temp_dupli_object,
-		                                  data->base,
-		                                  data->base_flag | BASE_FROMDUPLI);
+		deg_flush_base_flags_and_settings(data,
+		                                  &data->temp_dupli_object,
+		                                  data->dupli_parent,
+		                                  true);
 		iter->current = &data->temp_dupli_object;
 		BLI_assert(DEG::deg_validate_copy_on_write_datablock(&data->temp_dupli_object.id));
 		return true;
@@ -192,10 +209,72 @@ static bool deg_objects_dupli_iterator_next(BLI_Iterator *iter)
 	return false;
 }
 
+static void def_objects_iterator_step(BLI_Iterator *iter, DEG::IDDepsNode *id_node)
+{
+	DEGObjectsIteratorData *data = (DEGObjectsIteratorData *)iter->data;
+	const ID_Type id_type = GS(id_node->id_orig->name);
+
+	if (id_type != ID_OB) {
+		iter->skip = true;
+		return;
+	}
+
+	switch (id_node->linked_state) {
+		case DEG::DEG_ID_LINKED_DIRECTLY:
+			break;
+		case DEG::DEG_ID_LINKED_VIA_SET:
+			if (data->flag & DEG_OBJECT_ITER_FLAG_SET) {
+				break;
+			}
+			else {
+				ATTR_FALLTHROUGH;
+			}
+		case DEG::DEG_ID_LINKED_INDIRECTLY:
+			iter->skip = true;
+			return;
+	}
+
+	Object *ob = (Object *)id_node->id_cow;
+	BLI_assert(DEG::deg_validate_copy_on_write_datablock(&ob->id));
+
+	if (deg_flush_base_flags_and_settings(data, ob, ob, false) == false) {
+		iter->skip = true;
+		return;
+	}
+
+	if ((data->flag & DEG_OBJECT_ITER_FLAG_DUPLI) && (ob->transflag & OB_DUPLI)) {
+		data->dupli_parent = ob;
+		data->dupli_list = object_duplilist(&data->eval_ctx, data->scene, ob);
+		data->dupli_object_next = (DupliObject *)data->dupli_list->first;
+	}
+
+	iter->current = ob;
+}
+
+void DEG_objects_iterator_begin(BLI_Iterator *iter, DEGObjectsIteratorData *data)
+{
+	Depsgraph *graph = data->graph;
+
+	iter->data = data;
+	iter->valid = true;
+
+	DEG_evaluation_context_init(&data->eval_ctx, DAG_EVAL_RENDER);
+
+	data->dupli_parent = NULL;
+	data->dupli_list = NULL;
+	data->dupli_object_next = NULL;
+	data->dupli_object_current = NULL;
+
+	DEG::Depsgraph *deg_graph = reinterpret_cast<DEG::Depsgraph *>(graph);
+	BLI_ghashIterator_init(&data->gh_iter, deg_graph->id_hash);
+
+	DEG::IDDepsNode *id_node = (DEG::IDDepsNode *) BLI_ghashIterator_getValue(&data->gh_iter);
+	def_objects_iterator_step(iter, id_node);
+}
+
 void DEG_objects_iterator_next(BLI_Iterator *iter)
 {
 	DEGObjectsIteratorData *data = (DEGObjectsIteratorData *)iter->data;
-	Base *base;
 
 	if (data->dupli_list) {
 		if (deg_objects_dupli_iterator_next(iter)) {
@@ -210,50 +289,15 @@ void DEG_objects_iterator_next(BLI_Iterator *iter)
 		}
 	}
 
-	base = data->base->next;
-	if (base != NULL) {
-		// Object *ob = DEG_get_evaluated_object(data->graph, base->object);
-		Object *ob = base->object;
-		iter->current = ob;
-		data->base = base;
-
-		BLI_assert(DEG::deg_validate_copy_on_write_datablock(&ob->id));
-
-		/* Make sure we have the base collection settings is already populated.
-		 * This will fail when BKE_layer_eval_layer_collection_pre hasn't run yet
-		 * Which usually means a missing call to DEG_id_tag_update(). */
-		BLI_assert(!BLI_listbase_is_empty(&base->collection_properties->data.group));
-
-		/* Flushing depsgraph data. */
-		deg_flush_base_flags_and_settings(
-		        ob, base, data->base_flag);
-
-		if ((data->flag & DEG_OBJECT_ITER_FLAG_DUPLI) && (ob->transflag & OB_DUPLI)) {
-			data->dupli_parent = ob;
-			data->dupli_list = object_duplilist(&data->eval_ctx, data->scene, ob);
-			data->dupli_object_next = (DupliObject *)data->dupli_list->first;
-		}
-		return;
-	}
-
-	/* Look for an object in the next set. */
-	if ((data->flag & DEG_OBJECT_ITER_FLAG_SET) && data->scene->set) {
-		SceneLayer *scene_layer;
-		data->scene = data->scene->set;
-		data->base_flag = ~(BASE_SELECTED | BASE_SELECTABLED);
-
-		/* For the sets we use the layer used for rendering. */
-		scene_layer = BKE_scene_layer_from_scene_get(data->scene);
-
-		/* TODO(sergey): It's really confusing to store pointer to a local data. */
-		Base base = {(Base *)scene_layer->object_bases.first, NULL};
-		data->base = &base;
-		DEG_objects_iterator_next(iter);
+	BLI_ghashIterator_step(&data->gh_iter);
+	if (BLI_ghashIterator_done(&data->gh_iter)) {
+		iter->current = NULL;
+		iter->valid = false;
 		return;
 	}
 
-	iter->current = NULL;
-	iter->valid = false;
+	DEG::IDDepsNode *id_node = (DEG::IDDepsNode *) BLI_ghashIterator_getValue(&data->gh_iter);
+	def_objects_iterator_step(iter, id_node);
 }
 
 void DEG_objects_iterator_end(BLI_Iterator *iter)
diff --git a/source/blender/depsgraph/intern/depsgraph_types.h b/source/blender/depsgraph/intern/depsgraph_types.h
index 6f5eeff43df..a3d3863621b 100644
--- a/source/blender/depsgraph/intern/depsgraph_types.h
+++ b/source/blender/depsgraph/intern/depsgraph_types.h
@@ -79,6 +79,17 @@ typedef enum eDepsNode_Class {
 	DEG_NODE_CLASS_OPERATION       = 2,
 } eDepsNode_Class;
 
+/* Note: We use max comparison to mark an id node that is linked more than once
+ * So keep this enum ordered accordingly. */
+typedef enum eDepsNode_LinkedState_Type {
+	/* Generic indirectly linked id node. */
+	DEG_ID_LINKED_INDIRECTLY       = 0,
+	/* Id node present in the set (background) only. */
+	DEG_ID_LINKED_VIA_SET          = 1,
+	/* Id node directly linked via the ScenLayer. */
+	DEG_ID_LINKED_DIRECTLY         = 2,
+} eDepsNode_LinkedState_Type;
+
 /* Types of Nodes */
 typedef enum eDepsNode_Type {
 	/* Fallback type for invalid return value */
diff --git a/source/blender/depsgraph/intern/nodes/deg_node.cc b/source/blender/depsgraph/intern/nodes/deg_node.cc
index b313059e1bd..05138d90a7b 100644
--- a/source/blender/depsgraph/intern/nodes/deg_node.cc
+++ b/source/blender/depsgraph/intern/nodes/deg_node.cc
@@ -169,6 +169,7 @@ void IDDepsNode::init(const ID *id, const char *UNUSED(subdata))
 	/* Store ID-pointer. */
 	id_orig = (ID *)id;
 	eval_flags = 0;
+	linked_state = DEG_ID_LINKED_INDIRECTLY;
 
 	components = BLI_ghash_new(id_deps_node_hash_key,
 	                           id_deps_node_hash_key_cmp,
diff --git a/source/blender/depsgraph/intern/nodes/deg_node.h b/source/blender/depsgraph/intern/nodes/deg_node.h
index 16e75b2b5e7..fd3ed694c9c 100644
--- a/source/blender/depsgraph/intern/nodes/deg_node.h
+++ b/source/blender/depsgraph/intern/nodes/deg_node.h
@@ -164,6 +164,8 @@ struct IDDepsNode : public DepsNode {
 	 */
 	int eval_flags;
 
+	eDepsNode_LinkedState_Type linked_state;
+
 	DEG_DEPSNODE_DECLARE;
 };