Fix T56673: Tara.blend from Blender cloud crashes on load

The issue was caused by dependency cycle solver killing relation
which was guaranteed various things: i.e. copy-on-write component
orders and pose evaluation order (which must first run pose init
function).

Now it is possible to prevent such relations from being ignored.

This is not a complete fix, but is enough to make this specific
rig to work. Ideally, we also need to run copy-on-write operation
prior to anything else.

source/blender/depsgraph/intern/builder/deg_builder_cycle.cc

@@ -148,6 +148,35 @@ bool schedule_non_checked_node(CyclesSolverState *state)
 	return false;
 }
 
+bool check_relation_can_murder(DepsRelation *relation)
+{
+	if (relation->flag & DEPSREL_FLAG_GODMODE) {
+		return false;
+	}
+	return true;
+}
+
+DepsRelation *select_relation_to_murder(DepsRelation *relation,
+                                        StackEntry *cycle_start_entry)
+{
+	/* More or less russian roulette solver, which will make sure only
+	 * specially marked relations are kept alive.
+	 *
+	 * TODO(sergey): There might be better strategies here. */
+	if (check_relation_can_murder(relation)) {
+		return relation;
+	}
+	StackEntry *current = cycle_start_entry;
+	OperationDepsNode *to_node = (OperationDepsNode *)relation->to;
+	while (current->node != to_node) {
+		if (check_relation_can_murder(current->via_relation)) {
+			return current->via_relation;
+		}
+		current = current->from;
+	}
+	return relation;
+}
+
 /* Solve cycles with all nodes which are scheduled for traversal. */
 void solve_cycles(CyclesSolverState *state)
 {
@@ -168,7 +197,6 @@ void solve_cycles(CyclesSolverState *state)
 					       to->full_identifier().c_str(),
 					       node->full_identifier().c_str(),
 					       rel->name);
-
 					StackEntry *current = entry;
 					while (current->node != to) {
 						BLI_assert(current != NULL);
@@ -178,8 +206,9 @@ void solve_cycles(CyclesSolverState *state)
 						       current->via_relation->name);
 						current = current->from;
 					}
-					/* TODO(sergey): So called russian roulette cycle solver. */
-					rel->flag |= DEPSREL_FLAG_CYCLIC;
+					DepsRelation *sacrificial_relation =
+					        select_relation_to_murder(rel, entry);
+					sacrificial_relation->flag |= DEPSREL_FLAG_CYCLIC;
 					++state->num_cycles;
 				}
 				else if (to_state == NODE_NOT_VISITED) {

source/blender/depsgraph/intern/builder/deg_builder_relations.cc

@@ -2389,8 +2389,7 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node
 	/* XXX: This is a quick hack to make Alt-A to work. */
 	// add_relation(time_source_key, copy_on_write_key, "Fluxgate capacitor hack");
 	/* Resat of code is using rather low level trickery, so need to get some
-	 * explicit pointers.
-	 */
+	 * explicit pointers. */
 	DepsNode *node_cow = find_node(copy_on_write_key);
 	OperationDepsNode *op_cow = node_cow->get_exit_operation();
 	/* Plug any other components to this one. */
@@ -2404,7 +2403,7 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node
 			/* Component explicitly requests to not add relation. */
 			continue;
 		}
-		int rel_flag = DEPSREL_FLAG_NO_FLUSH;
+		int rel_flag = (DEPSREL_FLAG_NO_FLUSH | DEPSREL_FLAG_GODMODE);
 		if (id_type == ID_ME && comp_node->type == DEG_NODE_TYPE_GEOMETRY) {
 			rel_flag &= ~DEPSREL_FLAG_NO_FLUSH;
 		}
@@ -2412,7 +2411,6 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node
 		if (id_type == ID_MA) {
 			rel_flag &= ~DEPSREL_FLAG_NO_FLUSH;
 		}
-
 		/* Notes on exceptions:
 		 * - Parameters component is where drivers are living. Changing any
 		 *   of the (custom) properties in the original datablock (even the
@@ -2493,7 +2491,9 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node
 			OperationKey data_copy_on_write_key(object_data_id,
 			                                    DEG_NODE_TYPE_COPY_ON_WRITE,
 			                                    DEG_OPCODE_COPY_ON_WRITE);
-			add_relation(data_copy_on_write_key, copy_on_write_key, "Eval Order");
+			DepsRelation *rel = add_relation(
+			        data_copy_on_write_key, copy_on_write_key, "Eval Order");
+			rel->flag |= DEPSREL_FLAG_GODMODE;
 		}
 		else {
 			BLI_assert(object->type == OB_EMPTY);

source/blender/depsgraph/intern/builder/deg_builder_relations_rig.cc

@@ -385,6 +385,7 @@ void DepsgraphRelationBuilder::build_rig(Object *object)
 	}
 	/* Links between operations for each bone. */
 	LISTBASE_FOREACH (bPoseChannel *, pchan, &object->pose->chanbase) {
+		DepsRelation *relation;
 		OperationKey bone_local_key(&object->id,
 		                            DEG_NODE_TYPE_BONE,
 		                            pchan->name,
@@ -403,7 +404,9 @@ void DepsgraphRelationBuilder::build_rig(Object *object)
 		                           DEG_OPCODE_BONE_DONE);
 		pchan->flag &= ~POSE_DONE;
 		/* Pose init to bone local. */
-		add_relation(pose_init_key, bone_local_key, "Pose Init - Bone Local");
+		relation = add_relation(
+		        pose_init_key, bone_local_key, "Pose Init - Bone Local");
+		relation->flag |= DEPSREL_FLAG_GODMODE;
 		/* Local to pose parenting operation. */
 		add_relation(bone_local_key, bone_pose_key, "Bone Local - Bone Pose");
 		/* Parent relation. */

source/blender/depsgraph/intern/debug/deg_debug_relations_graphviz.cc

@@ -254,10 +254,14 @@ static void deg_debug_graphviz_relation_color(const DebugContext &ctx,
                                               const DepsRelation *rel)
 {
 	const char *color_default = "black";
-	const char *color_error = "red4";
+	const char *color_cyclic = "red4";  /* The color of crime scene. */
+	const char *color_godmode = "blue4";  /* The color of beautiful sky. */
 	const char *color = color_default;
 	if (rel->flag & DEPSREL_FLAG_CYCLIC) {
-		color = color_error;
+		color = color_cyclic;
+	}
+	else if (rel->flag & DEPSREL_FLAG_GODMODE) {
+		color = color_godmode;
 	}
 	deg_debug_fprintf(ctx, "%s", color);
 }

source/blender/depsgraph/intern/depsgraph.h

@@ -79,6 +79,8 @@ typedef enum eDepsRelation_Flag {
 	/* Only flush along the relation is update comes from a node which was
 	 * affected by user input. */
 	DEPSREL_FLAG_FLUSH_USER_EDIT_ONLY = (1 << 2),
+	/* The relation can not be killed by the cyclic dependencies solver. */
+	DEPSREL_FLAG_GODMODE              = (1 << 3),
 } eDepsRelation_Flag;
 
 /* B depends on A (A -> B) */