[Bf-blender-cvs] [e7ae3f9a7ed] temp-modifiers-instancing: Fix T82622: detect link cycles

[Jacques Lucke]

Commit: e7ae3f9a7edbf8d9b63f0a93910ba03452cb1a2e
Author: Jacques Lucke
Date:   Wed Nov 11 18:36:54 2020 +0100
Branches: temp-modifiers-instancing
https://developer.blender.org/rBe7ae3f9a7edbf8d9b63f0a93910ba03452cb1a2e

Fix T82622: detect link cycles

===================================================================

M	source/blender/modifiers/intern/MOD_nodes.cc
M	source/blender/nodes/NOD_derived_node_tree.hh
M	source/blender/nodes/NOD_node_tree_ref.hh
M	source/blender/nodes/intern/derived_node_tree.cc
M	source/blender/nodes/intern/node_tree_ref.cc

===================================================================

diff --git a/source/blender/modifiers/intern/MOD_nodes.cc b/source/blender/modifiers/intern/MOD_nodes.cc
index ce5d2984735..60b346671c3 100644
--- a/source/blender/modifiers/intern/MOD_nodes.cc
+++ b/source/blender/modifiers/intern/MOD_nodes.cc
@@ -813,7 +813,11 @@ static GeometrySetPtr modifyGeometry(ModifierData *md,
 
   NodeTreeRefMap tree_refs;
   DerivedNodeTree tree{nmd->node_group, tree_refs};
-  ResourceCollector resources;
+
+  if (tree.has_link_cycles()) {
+    BKE_modifier_set_error(ctx->object, md, "Node group has cycles");
+    return input_geometry_set;
+  }
 
   Span<const DNode *> input_nodes = tree.nodes_by_type("NodeGroupInput");
   Span<const DNode *> output_nodes = tree.nodes_by_type("NodeGroupOutput");
diff --git a/source/blender/nodes/NOD_derived_node_tree.hh b/source/blender/nodes/NOD_derived_node_tree.hh
index e7ff5d6b9f8..de1d5c84715 100644
--- a/source/blender/nodes/NOD_derived_node_tree.hh
+++ b/source/blender/nodes/NOD_derived_node_tree.hh
@@ -207,6 +207,8 @@ class DerivedNodeTree : NonCopyable, NonMovable {
 
   Span<const NodeTreeRef *> used_node_tree_refs() const;
 
+  bool has_link_cycles() const;
+
   std::string to_dot() const;
 
  private:
diff --git a/source/blender/nodes/NOD_node_tree_ref.hh b/source/blender/nodes/NOD_node_tree_ref.hh
index c3fc95d98e4..ebdd8b7fe49 100644
--- a/source/blender/nodes/NOD_node_tree_ref.hh
+++ b/source/blender/nodes/NOD_node_tree_ref.hh
@@ -177,6 +177,8 @@ class NodeTreeRef : NonCopyable, NonMovable {
   Span<const InputSocketRef *> input_sockets() const;
   Span<const OutputSocketRef *> output_sockets() const;
 
+  bool has_link_cycles() const;
+
   bNodeTree *btree() const;
 
   std::string to_dot() const;
diff --git a/source/blender/nodes/intern/derived_node_tree.cc b/source/blender/nodes/intern/derived_node_tree.cc
index 69e417868fb..5a380897e3f 100644
--- a/source/blender/nodes/intern/derived_node_tree.cc
+++ b/source/blender/nodes/intern/derived_node_tree.cc
@@ -362,6 +362,16 @@ DerivedNodeTree::~DerivedNodeTree()
   }
 }
 
+bool DerivedNodeTree::has_link_cycles() const
+{
+  for (const NodeTreeRef *tree : used_node_tree_refs_) {
+    if (tree->has_link_cycles()) {
+      return true;
+    }
+  }
+  return false;
+}
+
 static dot::Cluster *get_cluster_for_parent(dot::DirectedGraph &graph,
                                             Map<const DParentNode *, dot::Cluster *> &clusters,
                                             const DParentNode *parent)
diff --git a/source/blender/nodes/intern/node_tree_ref.cc b/source/blender/nodes/intern/node_tree_ref.cc
index 96ad1e0280e..9dcd90f9f50 100644
--- a/source/blender/nodes/intern/node_tree_ref.cc
+++ b/source/blender/nodes/intern/node_tree_ref.cc
@@ -137,6 +137,48 @@ void NodeTreeRef::find_targets_skipping_reroutes(OutputSocketRef &socket,
   }
 }
 
+static bool has_link_cycles_recursive(const NodeRef &node,
+                                      MutableSpan<bool> visited,
+                                      MutableSpan<bool> is_in_stack)
+{
+  const int node_id = node.id();
+  if (is_in_stack[node_id]) {
+    return true;
+  }
+  if (visited[node_id]) {
+    return false;
+  }
+
+  visited[node_id] = true;
+  is_in_stack[node_id] = true;
+
+  for (const OutputSocketRef *from_socket : node.outputs()) {
+    for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
+      const NodeRef &to_node = to_socket->node();
+      if (has_link_cycles_recursive(to_node, visited, is_in_stack)) {
+        return true;
+      }
+    }
+  }
+
+  is_in_stack[node_id] = false;
+  return false;
+}
+
+bool NodeTreeRef::has_link_cycles() const
+{
+  const int node_amount = nodes_by_id_.size();
+  Array<bool> visited(node_amount, false);
+  Array<bool> is_in_stack(node_amount, false);
+
+  for (const NodeRef *node : nodes_by_id_) {
+    if (has_link_cycles_recursive(*node, visited, is_in_stack)) {
+      return true;
+    }
+  }
+  return false;
+}
+
 std::string NodeTreeRef::to_dot() const
 {
   dot::DirectedGraph digraph;