From c806db63130b362284a90e96610939a8e2572deb Mon Sep 17 00:00:00 2001
From: Jacques Lucke <jacques@blender.org>
Date: Fri, 10 Jul 2020 14:22:35 +0200
Subject: Functions: add utility to find dependencies of input sockets

---
 .../blender/functions/FN_multi_function_network.hh |  4 +++
 .../functions/intern/multi_function_network.cc     | 31 ++++++++++++++++++++++
 2 files changed, 35 insertions(+)

(limited to 'source/blender')

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;
-- 
cgit v1.2.3