Depsgraph: fix crash caused by removing too many NO-OP nodes

Unused no-op operation nodes are not bound to a callback function, and
have no outgoing relations. Incoming relations of such nodes are removed
since ff60dd8b18ed00902e5bdfd36882072db7af8735. However, this was done
too broadly, causing too many relations to be lost and indirectly linked
objects to be unevaluated.

This commit introduces a `DEPSOP_FLAG_FAKE_USER` flag for operation
nodes, which indicates they are not to be removed, even when they appear
to be unused.

Reviewed By: sergey

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

6 files changed, 27 insertions, 5 deletions

diff --git a/source/blender/depsgraph/intern/builder/deg_builder.cc b/source/blender/depsgraph/intern/builder/deg_builder.cc
index 7eca04112e7..765a6e1006a 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder.cc
@@ -46,6 +46,7 @@ extern "C" {
 #include "intern/depsgraph_tag.h"
 #include "intern/depsgraph_type.h"
 #include "intern/builder/deg_builder_cache.h"
+#include "intern/builder/deg_builder_remove_noop.h"
 #include "intern/eval/deg_eval_copy_on_write.h"
 #include "intern/node/deg_node.h"
 #include "intern/node/deg_node_id.h"
@@ -212,6 +213,8 @@ void deg_graph_build_finalize(Main *bmain, Depsgraph *graph)
 {
   /* Make sure dependencies of visible ID datablocks are visible. */
   deg_graph_build_flush_visibility(graph);
+  deg_graph_remove_unused_noops(graph);
+
   /* Re-tag IDs for update if it was tagged before the relations
    * update tag. */
   for (IDNode *id_node : graph->id_nodes) {
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
index b976875508c..687ee492c3b 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
@@ -624,7 +624,9 @@ void DepsgraphNodeBuilder::build_object(int base_index,
     is_parent_collection_visible_ = is_visible;
     build_collection(nullptr, object->instance_collection);
     is_parent_collection_visible_ = is_current_parent_collection_visible;
-    add_operation_node(&object->id, NodeType::DUPLI, OperationCode::DUPLI);
+    OperationNode *op_node = add_operation_node(
+        &object->id, NodeType::DUPLI, OperationCode::DUPLI);
+    op_node->flag |= OperationFlag::DEPSOP_FLAG_PINNED;
   }
   /* Synchronization back to original object. */
   add_operation_node(&object->id,
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc
index 33de20133db..aa0cb66a38f 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc
@@ -35,13 +35,24 @@
 
 namespace DEG {
 
+static inline bool is_unused_noop(OperationNode *op_node)
+{
+  if (op_node == nullptr) {
+    return false;
+  }
+  if (op_node->flag & OperationFlag::DEPSOP_FLAG_PINNED) {
+    return false;
+  }
+  return op_node->is_noop() && op_node->outlinks.empty();
+}
+
 void deg_graph_remove_unused_noops(Depsgraph *graph)
 {
   int num_removed_relations = 0;
   deque<OperationNode *> queue;
 
   for (OperationNode *node : graph->operations) {
-    if (node->is_noop() && node->outlinks.empty()) {
+    if (is_unused_noop(node)) {
       queue.push_back(node);
     }
   }
@@ -61,7 +72,7 @@ void deg_graph_remove_unused_noops(Depsgraph *graph)
 
       /* Queue parent no-op node that has now become unused. */
       OperationNode *operation = dependency->get_exit_operation();
-      if (operation != nullptr && operation->is_noop() && operation->outlinks.empty()) {
+      if (is_unused_noop(operation)) {
         queue.push_back(operation);
       }
     }
diff --git a/source/blender/depsgraph/intern/debug/deg_debug_relations_graphviz.cc b/source/blender/depsgraph/intern/debug/deg_debug_relations_graphviz.cc
index b08281b755e..73b99213005 100644
--- a/source/blender/depsgraph/intern/debug/deg_debug_relations_graphviz.cc
+++ b/source/blender/depsgraph/intern/debug/deg_debug_relations_graphviz.cc
@@ -125,6 +125,9 @@ static int deg_debug_node_color_index(const Node *node)
     case NodeType::OPERATION: {
       OperationNode *op_node = (OperationNode *)node;
       if (op_node->is_noop()) {
+        if (op_node->flag & OperationFlag::DEPSOP_FLAG_PINNED) {
+          return 7;
+        }
         return 8;
       }
       break;
@@ -195,6 +198,7 @@ static void deg_debug_graphviz_legend(const DebugContext &ctx)
   deg_debug_graphviz_legend_color(ctx, "Component", colors[1]);
   deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]);
   deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]);
+  deg_debug_graphviz_legend_color(ctx, "Pinned OP", colors[7]);
 #endif
 
 #ifdef COLOR_SCHEME_NODE_TYPE
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index 75031a2140e..3fe585ff73c 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -50,7 +50,6 @@ extern "C" {
 #include "builder/deg_builder_cycle.h"
 #include "builder/deg_builder_nodes.h"
 #include "builder/deg_builder_relations.h"
-#include "builder/deg_builder_remove_noop.h"
 #include "builder/deg_builder_transitive.h"
 
 #include "intern/debug/deg_debug.h"
@@ -211,7 +210,6 @@ static void graph_build_finalize_common(DEG::Depsgraph *deg_graph, Main *bmain)
   if (G.debug_value == 799) {
     DEG::deg_graph_transitive_reduction(deg_graph);
   }
-  DEG::deg_graph_remove_unused_noops(deg_graph);
   /* Store pointers to commonly used valuated datablocks. */
   deg_graph->scene_cow = (Scene *)deg_graph->get_cow_id(&deg_graph->scene->id);
   /* Flush visibility layer and re-schedule nodes for update. */
diff --git a/source/blender/depsgraph/intern/node/deg_node_operation.h b/source/blender/depsgraph/intern/node/deg_node_operation.h
index cedbad3715a..bdc0df7f399 100644
--- a/source/blender/depsgraph/intern/node/deg_node_operation.h
+++ b/source/blender/depsgraph/intern/node/deg_node_operation.h
@@ -210,6 +210,10 @@ enum OperationFlag {
   DEPSOP_FLAG_DIRECTLY_MODIFIED = (1 << 1),
   /* Node was updated due to user input. */
   DEPSOP_FLAG_USER_MODIFIED = (1 << 2),
+  /* Node may not be removed, even when it has no evaluation callback and no
+   * outgoing relations. This is for NO-OP nodes that are purely used to indicate a
+   * relation between components/IDs, and not for connecting to an operation. */
+  DEPSOP_FLAG_PINNED = (1 << 3),
 
   /* Set of flags which gets flushed along the relations. */
   DEPSOP_FLAG_FLUSH = (DEPSOP_FLAG_USER_MODIFIED),