Fix T38139: Objects which are in cyclic dependency are not updated

Graph traversal which is based on counting parents which are still
to be updated fails in cases there are cycles in the graph.

If there are cyclic dependencies in the scene all the objects from
the cycles will be updated in a single thread now one by one. This
makes blender behave the same way as it was before multi-threaded
DAG landed to master.

This needed to tweak depsgraph a bit so now dag_check_cycle() sets
is_acyclic field of DAG forest if there are cycles in the graph.

TODO: It might be possible to save some time on evaluation when
      all the tagged objects were updated in multi-threaded DAG
      traversal.

source/blender/blenkernel/BKE_depsgraph.h

@@ -159,6 +159,7 @@ void DAG_print_dependencies(struct Main *bmain, struct Scene *scene, struct Obje
 struct Object *DAG_get_node_object(void *node_v);
 const char *DAG_get_node_name(void *node_v);
 short DAG_get_eval_flags_for_object(struct Scene *scene, void *object);
+bool DAG_is_acyclic(struct Scene *scene);
 
 #ifdef __cplusplus
 }

source/blender/blenkernel/depsgraph_private.h

@@ -127,7 +127,7 @@ typedef struct DagForest {
 	ListBase DagNode;
 	struct GHash *nodeHash;
 	int numNodes;
-	int is_acyclic;
+	bool is_acyclic;
 	int time;  /* for flushing/tagging, compare with node->lasttime */
 } DagForest;
 

source/blender/blenkernel/intern/depsgraph.c

@@ -1193,6 +1193,8 @@ static void dag_check_cycle(DagForest *dag)
 	DagNode *node;
 	DagAdjList *itA;
 
+	dag->is_acyclic = true;
+
 	/* debugging print */
 	if (dag_print_dependencies)
 		for (node = dag->DagNode.first; node; node = node->next)
@@ -1213,6 +1215,7 @@ static void dag_check_cycle(DagForest *dag)
 		for (itA = node->parent; itA; itA = itA->next) {
 			if (itA->node->ancestor_count > node->ancestor_count) {
 				if (node->ob && itA->node->ob) {
+					dag->is_acyclic = false;
 					printf("Dependency cycle detected:\n");
 					dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
 				}
@@ -2904,3 +2907,7 @@ short DAG_get_eval_flags_for_object(struct Scene *scene, void *object)
 	return node->eval_flags;
 }
 
+bool DAG_is_acyclic(Scene *scene)
+{
+	return scene->theDag->is_acyclic;
+}

source/blender/blenkernel/intern/scene.c

@@ -1388,6 +1388,7 @@ static void scene_update_objects(EvaluationContext *eval_ctx, Main *bmain, Scene
 	TaskScheduler *task_scheduler = BLI_task_scheduler_get();
 	TaskPool *task_pool;
 	ThreadedObjectUpdateState state;
+	bool need_singlethread_pass;
 
 	/* Early check for whether we need to invoke all the task-based
 	 * tihngs (spawn new ppol, traverse dependency graph and so on).
@@ -1453,11 +1454,28 @@ static void scene_update_objects(EvaluationContext *eval_ctx, Main *bmain, Scene
 		print_threads_statistics(&state);
 	}
 
+	/* We do single thread pass to update all the objects which are in cyclic dependency.
+	 * Such objects can not be handled by a generic DAG traverse and it's really tricky
+	 * to detect whether cycle could be solved or not.
+	 *
+	 * In this situation we simply update all remaining objects in a single thread and
+	 * it'll happen in the same exact order as it was in single-threaded DAG.
+	 *
+	 * We couldn't use threaded update for objects which are in cycle because they might
+	 * access data of each other which is being re-evaluated.
+	 *
+	 * Also, as was explained above, for now we also update all the mballs in single thread.
+	 *
+	 *                                                                   - sergey -
+	 */
+	need_singlethread_pass = DAG_is_acyclic(scene) == false;
 #ifdef MBALL_SINGLETHREAD_HACK
-	if (state.has_mballs) {
+	need_singlethread_pass |= state.has_mballs;
+#endif
+
+	if (need_singlethread_pass) {
 		scene_update_all_bases(eval_ctx, scene, scene_parent);
 	}
-#endif
 }
 
 static void scene_update_tagged_recursive(EvaluationContext *eval_ctx, Main *bmain, Scene *scene, Scene *scene_parent)