[Bf-blender-cvs] [8ecc1bea4c0] geometry-nodes: Nodes: add utility to check for link cycles in derived node trees

[Jacques Lucke]

Commit: 8ecc1bea4c0e813433230e77ce26673fc5489aa7
Author: Jacques Lucke
Date:   Thu Nov 12 11:35:46 2020 +0100
Branches: geometry-nodes
https://developer.blender.org/rB8ecc1bea4c0e813433230e77ce26673fc5489aa7

Nodes: add utility to check for link cycles in derived node trees

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

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/nodes/NOD_derived_node_tree.hh b/source/blender/nodes/NOD_derived_node_tree.hh
index 1a9f223cf6c..de1d5c84715 100644
--- a/source/blender/nodes/NOD_derived_node_tree.hh
+++ b/source/blender/nodes/NOD_derived_node_tree.hh
@@ -31,6 +31,8 @@
 
 #include "NOD_node_tree_ref.hh"
 
+#include "BLI_vector_set.hh"
+
 namespace blender::nodes {
 
 class DSocket;
@@ -184,11 +186,15 @@ class DerivedNodeTree : NonCopyable, NonMovable {
   Vector<DOutputSocket *> output_sockets_;
 
   MultiValueMap<const bNodeType *, DNode *> nodes_by_type_;
+  VectorSet<const NodeTreeRef *> used_node_tree_refs_;
+  bNodeTree *btree_;
 
  public:
   DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs);
   ~DerivedNodeTree();
 
+  bNodeTree *btree() const;
+
   Span<const DNode *> nodes() const;
   Span<const DNode *> nodes_by_type(StringRefNull idname) const;
   Span<const DNode *> nodes_by_type(const bNodeType *nodetype) const;
@@ -199,6 +205,10 @@ class DerivedNodeTree : NonCopyable, NonMovable {
 
   Span<const DGroupInput *> group_inputs() const;
 
+  Span<const NodeTreeRef *> used_node_tree_refs() const;
+
+  bool has_link_cycles() const;
+
   std::string to_dot() const;
 
  private:
@@ -492,6 +502,11 @@ inline int DParentNode::id() const
  * DerivedNodeTree inline methods.
  */
 
+inline bNodeTree *DerivedNodeTree::btree() const
+{
+  return btree_;
+}
+
 inline Span<const DNode *> DerivedNodeTree::nodes() const
 {
   return nodes_by_id_;
@@ -528,4 +543,9 @@ inline Span<const DGroupInput *> DerivedNodeTree::group_inputs() const
   return group_inputs_;
 }
 
+inline Span<const NodeTreeRef *> DerivedNodeTree::used_node_tree_refs() const
+{
+  return used_node_tree_refs_;
+}
+
 }  // namespace blender::nodes
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 4612a479ebc..5a380897e3f 100644
--- a/source/blender/nodes/intern/derived_node_tree.cc
+++ b/source/blender/nodes/intern/derived_node_tree.cc
@@ -28,9 +28,12 @@ static const NodeTreeRef &get_tree_ref(NodeTreeRefMap &node_tree_refs, bNodeTree
                                           [&]() { return std::make_unique<NodeTreeRef>(btree); });
 }
 
-DerivedNodeTree::DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs)
+DerivedNodeTree::DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs) : btree_(btree)
 {
+  BLI_assert(btree != nullptr);
+
   const NodeTreeRef &main_tree_ref = get_tree_ref(node_tree_refs, btree);
+  used_node_tree_refs_.add_new(&main_tree_ref);
 
   Vector<DNode *> all_nodes;
   Vector<DGroupInput *> all_group_inputs;
@@ -137,6 +140,7 @@ BLI_NOINLINE void DerivedNodeTree::expand_group_node(DNode &group_node,
   }
 
   const NodeTreeRef &group_ref = get_tree_ref(node_tree_refs, btree);
+  used_node_tree_refs_.add(&group_ref);
 
   DParentNode &parent = *allocator_.construct<DParentNode>();
   parent.id_ = all_parent_nodes.append_and_get_index(&parent);
@@ -358,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;