[Bf-blender-cvs] [c806db63130] master: Functions: add utility to find dependencies of input sockets

[Jacques Lucke]

Commit: c806db63130b362284a90e96610939a8e2572deb
Author: Jacques Lucke
Date:   Fri Jul 10 14:22:35 2020 +0200
Branches: master
https://developer.blender.org/rBc806db63130b362284a90e96610939a8e2572deb

Functions: add utility to find dependencies of input sockets

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

M	source/blender/functions/FN_multi_function_network.hh
M	source/blender/functions/intern/multi_function_network.cc

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

diff --git a/source/blender/functions/FN_multi_function_network.hh b/source/blender/functions/FN_multi_function_network.hh
index 42f24d9c44c..e47c8260057 100644
--- a/source/blender/functions/FN_multi_function_network.hh
+++ b/source/blender/functions/FN_multi_function_network.hh
@@ -229,6 +229,10 @@ class MFNetwork : NonCopyable, NonMovable {
   MFSocket *socket_or_null_by_id(uint id);
   const MFSocket *socket_or_null_by_id(uint id) const;
 
+  void find_dependencies(Span<const MFInputSocket *> sockets,
+                         VectorSet<const MFOutputSocket *> &r_dummy_sockets,
+                         VectorSet<const MFInputSocket *> &r_unlinked_inputs) const;
+
   std::string to_dot(Span<const MFNode *> marked_nodes = {}) const;
 };
 
diff --git a/source/blender/functions/intern/multi_function_network.cc b/source/blender/functions/intern/multi_function_network.cc
index 2078fbaaa08..47e3bf4d0b5 100644
--- a/source/blender/functions/intern/multi_function_network.cc
+++ b/source/blender/functions/intern/multi_function_network.cc
@@ -15,6 +15,8 @@
  */
 
 #include "BLI_dot_export.hh"
+#include "BLI_stack.hh"
+
 #include "FN_multi_function_network.hh"
 
 namespace blender::fn {
@@ -237,6 +239,35 @@ void MFNetwork::remove(Span<MFNode *> nodes)
   }
 }
 
+void MFNetwork::find_dependencies(Span<const MFInputSocket *> sockets,
+                                  VectorSet<const MFOutputSocket *> &r_dummy_sockets,
+                                  VectorSet<const MFInputSocket *> &r_unlinked_inputs) const
+{
+  Set<const MFNode *> visited_nodes;
+  Stack<const MFInputSocket *> sockets_to_check;
+  sockets_to_check.push_multiple(sockets);
+
+  while (!sockets_to_check.is_empty()) {
+    const MFInputSocket &socket = *sockets_to_check.pop();
+    const MFOutputSocket *origin_socket = socket.origin();
+    if (origin_socket == nullptr) {
+      r_unlinked_inputs.add(&socket);
+      continue;
+    }
+
+    const MFNode &origin_node = origin_socket->node();
+
+    if (origin_node.is_dummy()) {
+      r_dummy_sockets.add(origin_socket);
+      continue;
+    }
+
+    if (visited_nodes.add(&origin_node)) {
+      sockets_to_check.push_multiple(origin_node.inputs());
+    }
+  }
+}
+
 std::string MFNetwork::to_dot(Span<const MFNode *> marked_nodes) const
 {
   dot::DirectedGraph digraph;