Functions: Multi Function Network

A multi-function network is a graph data structure, where nodes are
multi-functions (or dummies) and links represent data flow.
New multi-functions can be derived from such a network. For that
one just has to specify two sets of sockets in the network that
represent the inputs and outputs of the new function.

It is possible to do optimizations like constant folding on this
data structure, but that is not implemented in this patch yet.

In a next step, user generated node trees are converted into a
MFNetwork, so that they can be evaluated efficiently for many particles.

This patch also includes some tests that cover the majority of the code.
However, this seems to be the kind of code that is best tested by some
.blend files. Building graph structures in code is possible, but is
not easy to understand afterwards.

Reviewers: brecht

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

5 files changed, 1823 insertions, 0 deletions

diff --git a/source/blender/functions/CMakeLists.txt b/source/blender/functions/CMakeLists.txt
index 0a080246d84..acaef1d146a 100644
--- a/source/blender/functions/CMakeLists.txt
+++ b/source/blender/functions/CMakeLists.txt
@@ -28,6 +28,8 @@ set(INC_SYS
 
 set(SRC
   intern/cpp_types.cc
+  intern/multi_function_network.cc
+  intern/multi_function_network_evaluation.cc
 
   FN_array_spans.hh
   FN_cpp_type.hh
@@ -36,6 +38,8 @@ set(SRC
   FN_multi_function_builder.hh
   FN_multi_function_context.hh
   FN_multi_function_data_type.hh
+  FN_multi_function_network.hh
+  FN_multi_function_network_evaluation.hh
   FN_multi_function_param_type.hh
   FN_multi_function_params.hh
   FN_multi_function_signature.hh
diff --git a/source/blender/functions/FN_multi_function_network.hh b/source/blender/functions/FN_multi_function_network.hh
new file mode 100644
index 00000000000..e1d5ce8bd69
--- /dev/null
+++ b/source/blender/functions/FN_multi_function_network.hh
@@ -0,0 +1,448 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __FN_MULTI_FUNCTION_NETWORK_HH__
+#define __FN_MULTI_FUNCTION_NETWORK_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * A multi-function network (`MFNetwork`) allows you to connect multiple multi-functions. The
+ * `MFNetworkEvaluator` is a multi-function that wraps an entire network into a new multi-function
+ * (which can be used in another network and so on).
+ *
+ * A MFNetwork is a graph data structure with two kinds of nodes:
+ * - MFFunctionNode: Represents a multi-function. Its input and output sockets correspond to
+ *       parameters of the referenced multi-function.
+ * - MFDummyNode: Does not reference a multi-function. Instead it just has sockets that can be
+ *       used to represent node group inputs and outputs.
+ *
+ * Links represent data flow. Unlinked input sockets have no value. In order to execute a function
+ * node, all its inputs have to be connected to something.
+ *
+ * Links are only allowed between sockets with the exact same MFDataType. There are no implicit
+ * conversions.
+ *
+ * Every input and output parameter of a multi-function corresponds to exactly one input or output
+ * socket respectively. A multiple parameter belongs to exactly one input AND one output socket.
+ *
+ * There is an .to_dot() method that generates a graph in dot format for debugging purposes.
+ */
+
+#include "FN_multi_function.hh"
+
+#include "BLI_vector_set.hh"
+
+namespace blender {
+namespace fn {
+
+class MFNode;
+class MFFunctionNode;
+class MFDummyNode;
+class MFSocket;
+class MFInputSocket;
+class MFOutputSocket;
+class MFNetwork;
+
+class MFNode : NonCopyable, NonMovable {
+ protected:
+  MFNetwork *m_network;
+  Span<MFInputSocket *> m_inputs;
+  Span<MFOutputSocket *> m_outputs;
+  bool m_is_dummy;
+  uint m_id;
+
+  friend MFNetwork;
+
+ public:
+  StringRefNull name() const;
+
+  uint id() const;
+
+  MFNetwork &network();
+  const MFNetwork &network() const;
+
+  bool is_dummy() const;
+  bool is_function() const;
+
+  MFDummyNode &as_dummy();
+  const MFDummyNode &as_dummy() const;
+
+  MFFunctionNode &as_function();
+  const MFFunctionNode &as_function() const;
+
+  MFInputSocket &input(uint index);
+  const MFInputSocket &input(uint index) const;
+
+  MFOutputSocket &output(uint index);
+  const MFOutputSocket &output(uint index) const;
+
+  Span<MFInputSocket *> inputs();
+  Span<const MFInputSocket *> inputs() const;
+
+  Span<MFOutputSocket *> outputs();
+  Span<const MFOutputSocket *> outputs() const;
+
+  template<typename FuncT> void foreach_origin_socket(const FuncT &func) const;
+
+  bool all_inputs_have_origin() const;
+
+ private:
+  void destruct_sockets();
+};
+
+class MFFunctionNode : public MFNode {
+ private:
+  const MultiFunction *m_function;
+  Span<uint> m_input_param_indices;
+  Span<uint> m_output_param_indices;
+
+  friend MFNetwork;
+
+ public:
+  StringRefNull name() const;
+
+  const MultiFunction &function() const;
+
+  const MFInputSocket &input_for_param(uint param_index) const;
+  const MFOutputSocket &output_for_param(uint param_index) const;
+};
+
+class MFDummyNode : public MFNode {
+ private:
+  StringRefNull m_name;
+  MutableSpan<StringRefNull> m_input_names;
+  MutableSpan<StringRefNull> m_output_names;
+
+  friend MFNetwork;
+
+ public:
+  StringRefNull name() const;
+
+  Span<StringRefNull> input_names() const;
+  Span<StringRefNull> output_names() const;
+};
+
+class MFSocket : NonCopyable, NonMovable {
+ protected:
+  MFNode *m_node;
+  bool m_is_output;
+  uint m_index;
+  MFDataType m_data_type;
+  uint m_id;
+  StringRefNull m_name;
+
+  friend MFNetwork;
+
+ public:
+  StringRefNull name() const;
+
+  uint id() const;
+
+  const MFDataType &data_type() const;
+
+  MFNode &node();
+  const MFNode &node() const;
+};
+
+class MFInputSocket : public MFSocket {
+ private:
+  MFOutputSocket *m_origin;
+
+  friend MFNetwork;
+
+ public:
+  MFOutputSocket *origin();
+  const MFOutputSocket *origin() const;
+};
+
+class MFOutputSocket : public MFSocket {
+ private:
+  Vector<MFInputSocket *, 1> m_targets;
+
+  friend MFNetwork;
+
+ public:
+  Span<MFInputSocket *> targets();
+  Span<const MFInputSocket *> targets() const;
+};
+
+class MFNetwork : NonCopyable, NonMovable {
+ private:
+  LinearAllocator<> m_allocator;
+
+  VectorSet<MFFunctionNode *> m_function_nodes;
+  VectorSet<MFDummyNode *> m_dummy_nodes;
+
+  Vector<MFNode *> m_node_or_null_by_id;
+  Vector<MFSocket *> m_socket_or_null_by_id;
+
+ public:
+  MFNetwork() = default;
+  ~MFNetwork();
+
+  MFFunctionNode &add_function(const MultiFunction &function);
+  MFDummyNode &add_dummy(StringRef name,
+                         Span<MFDataType> input_types,
+                         Span<MFDataType> output_types,
+                         Span<StringRef> input_names,
+                         Span<StringRef> output_names);
+  void add_link(MFOutputSocket &from, MFInputSocket &to);
+
+  MFOutputSocket &add_input(StringRef name, MFDataType data_type);
+  MFInputSocket &add_output(StringRef name, MFDataType data_type);
+
+  uint max_socket_id() const;
+
+  std::string to_dot() const;
+};
+
+/* --------------------------------------------------------------------
+ * MFNode inline methods.
+ */
+
+inline StringRefNull MFNode::name() const
+{
+  if (m_is_dummy) {
+    return this->as_dummy().name();
+  }
+  else {
+    return this->as_function().name();
+  }
+}
+
+inline uint MFNode::id() const
+{
+  return m_id;
+}
+
+inline MFNetwork &MFNode::network()
+{
+  return *m_network;
+}
+
+inline const MFNetwork &MFNode::network() const
+{
+  return *m_network;
+}
+
+inline bool MFNode::is_dummy() const
+{
+  return m_is_dummy;
+}
+
+inline bool MFNode::is_function() const
+{
+  return !m_is_dummy;
+}
+
+inline MFDummyNode &MFNode::as_dummy()
+{
+  BLI_assert(m_is_dummy);
+  return *(MFDummyNode *)this;
+}
+
+inline const MFDummyNode &MFNode::as_dummy() const
+{
+  BLI_assert(m_is_dummy);
+  return *(const MFDummyNode *)this;
+}
+
+inline MFFunctionNode &MFNode::as_function()
+{
+  BLI_assert(!m_is_dummy);
+  return *(MFFunctionNode *)this;
+}
+
+inline const MFFunctionNode &MFNode::as_function() const
+{
+  BLI_assert(!m_is_dummy);
+  return *(const MFFunctionNode *)this;
+}
+
+inline MFInputSocket &MFNode::input(uint index)
+{
+  return *m_inputs[index];
+}
+
+inline const MFInputSocket &MFNode::input(uint index) const
+{
+  return *m_inputs[index];
+}
+
+inline MFOutputSocket &MFNode::output(uint index)
+{
+  return *m_outputs[index];
+}
+
+inline const MFOutputSocket &MFNode::output(uint index) const
+{
+  return *m_outputs[index];
+}
+
+inline Span<MFInputSocket *> MFNode::inputs()
+{
+  return m_inputs;
+}
+
+inline Span<const MFInputSocket *> MFNode::inputs() const
+{
+  return m_inputs;
+}
+
+inline Span<MFOutputSocket *> MFNode::outputs()
+{
+  return m_outputs;
+}
+
+inline Span<const MFOutputSocket *> MFNode::outputs() const
+{
+  return m_outputs;
+}
+
+template<typename FuncT> void MFNode::foreach_origin_socket(const FuncT &func) const
+{
+  for (const MFInputSocket *socket : m_inputs) {
+    const MFOutputSocket *origin = socket->origin();
+    if (origin != nullptr) {
+      func(*origin);
+    }
+  }
+}
+
+inline bool MFNode::all_inputs_have_origin() const
+{
+  for (const MFInputSocket *socket : m_inputs) {
+    if (socket->origin() == nullptr) {
+      return false;
+    }
+  }
+  return true;
+}
+
+/* --------------------------------------------------------------------
+ * MFFunctionNode inline methods.
+ */
+
+inline StringRefNull MFFunctionNode::name() const
+{
+  return m_function->name();
+}
+
+inline const MultiFunction &MFFunctionNode::function() const
+{
+  return *m_function;
+}
+
+inline const MFInputSocket &MFFunctionNode::input_for_param(uint param_index) const
+{
+  return this->input(m_input_param_indices.first_index(param_index));
+}
+
+inline const MFOutputSocket &MFFunctionNode::output_for_param(uint param_index) const
+{
+  return this->output(m_output_param_indices.first_index(param_index));
+}
+
+/* --------------------------------------------------------------------
+ * MFDummyNode inline methods.
+ */
+
+inline StringRefNull MFDummyNode::name() const
+{
+  return m_name;
+}
+
+inline Span<StringRefNull> MFDummyNode::input_names() const
+{
+  return m_input_names;
+}
+
+inline Span<StringRefNull> MFDummyNode::output_names() const
+{
+  return m_output_names;
+}
+
+/* --------------------------------------------------------------------
+ * MFSocket inline methods.
+ */
+
+inline StringRefNull MFSocket::name() const
+{
+  return m_name;
+}
+
+inline uint MFSocket::id() const
+{
+  return m_id;
+}
+
+inline const MFDataType &MFSocket::data_type() const
+{
+  return m_data_type;
+}
+
+inline MFNode &MFSocket::node()
+{
+  return *m_node;
+}
+
+inline const MFNode &MFSocket::node() const
+{
+  return *m_node;
+}
+
+/* --------------------------------------------------------------------
+ * MFInputSocket inline methods.
+ */
+
+inline MFOutputSocket *MFInputSocket::origin()
+{
+  return m_origin;
+}
+
+inline const MFOutputSocket *MFInputSocket::origin() const
+{
+  return m_origin;
+}
+
+/* --------------------------------------------------------------------
+ * MFOutputSocket inline methods.
+ */
+
+inline Span<MFInputSocket *> MFOutputSocket::targets()
+{
+  return m_targets;
+}
+
+inline Span<const MFInputSocket *> MFOutputSocket::targets() const
+{
+  return m_targets.as_span();
+}
+
+/* --------------------------------------------------------------------
+ * MFNetwork inline methods.
+ */
+
+inline uint MFNetwork::max_socket_id() const
+{
+  return m_socket_or_null_by_id.size() - 1;
+}
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_NETWORK_HH__ */
diff --git a/source/blender/functions/FN_multi_function_network_evaluation.hh b/source/blender/functions/FN_multi_function_network_evaluation.hh
new file mode 100644
index 00000000000..85ccd1361ef
--- /dev/null
+++ b/source/blender/functions/FN_multi_function_network_evaluation.hh
@@ -0,0 +1,66 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __FN_MULTI_FUNCTION_NETWORK_EVALUATION_HH__
+#define __FN_MULTI_FUNCTION_NETWORK_EVALUATION_HH__
+
+/** \file
+ * \ingroup fn
+ */
+
+#include "FN_multi_function_network.hh"
+
+namespace blender {
+namespace fn {
+
+class MFNetworkEvaluationStorage;
+
+class MFNetworkEvaluator : public MultiFunction {
+ private:
+  Vector<const MFOutputSocket *> m_inputs;
+  Vector<const MFInputSocket *> m_outputs;
+
+ public:
+  MFNetworkEvaluator(Vector<const MFOutputSocket *> inputs, Vector<const MFInputSocket *> outputs);
+
+  void call(IndexMask mask, MFParams params, MFContext context) const override;
+
+ private:
+  using Storage = MFNetworkEvaluationStorage;
+
+  void copy_inputs_to_storage(MFParams params, Storage &storage) const;
+  void copy_outputs_to_storage(
+      MFParams params,
+      Storage &storage,
+      Vector<const MFInputSocket *> &outputs_to_initialize_in_the_end) const;
+
+  void evaluate_network_to_compute_outputs(MFContext &global_context, Storage &storage) const;
+
+  void evaluate_function(MFContext &global_context,
+                         const MFFunctionNode &function_node,
+                         Storage &storage) const;
+
+  bool can_do_single_value_evaluation(const MFFunctionNode &function_node, Storage &storage) const;
+
+  void initialize_remaining_outputs(MFParams params,
+                                    Storage &storage,
+                                    Span<const MFInputSocket *> remaining_outputs) const;
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_NETWORK_EVALUATION_HH__ */
diff --git a/source/blender/functions/intern/multi_function_network.cc b/source/blender/functions/intern/multi_function_network.cc
new file mode 100644
index 00000000000..136228d0dcd
--- /dev/null
+++ b/source/blender/functions/intern/multi_function_network.cc
@@ -0,0 +1,242 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "BLI_dot_export.hh"
+#include "FN_multi_function_network.hh"
+
+namespace blender {
+namespace fn {
+
+MFNetwork::~MFNetwork()
+{
+  for (MFFunctionNode *node : m_function_nodes) {
+    node->destruct_sockets();
+    node->~MFFunctionNode();
+  }
+  for (MFDummyNode *node : m_dummy_nodes) {
+    node->destruct_sockets();
+    node->~MFDummyNode();
+  }
+}
+
+void MFNode::destruct_sockets()
+{
+  for (MFInputSocket *socket : m_inputs) {
+    socket->~MFInputSocket();
+  }
+  for (MFOutputSocket *socket : m_outputs) {
+    socket->~MFOutputSocket();
+  }
+}
+
+/**
+ * Add a new function node to the network. The caller keeps the ownership of the function. The
+ * function should not be freed before the network. A reference to the new node is returned. The
+ * node is owned by the network.
+ */
+MFFunctionNode &MFNetwork::add_function(const MultiFunction &function)
+{
+  Vector<uint, 16> input_param_indices, output_param_indices;
+
+  for (uint param_index : function.param_indices()) {
+    switch (function.param_type(param_index).interface_type()) {
+      case MFParamType::Input: {
+        input_param_indices.append(param_index);
+        break;
+      }
+      case MFParamType::Output: {
+        output_param_indices.append(param_index);
+        break;
+      }
+      case MFParamType::Mutable: {
+        input_param_indices.append(param_index);
+        output_param_indices.append(param_index);
+        break;
+      }
+    }
+  }
+
+  MFFunctionNode &node = *m_allocator.construct<MFFunctionNode>();
+  m_function_nodes.add_new(&node);
+
+  node.m_network = this;
+  node.m_is_dummy = false;
+  node.m_id = m_node_or_null_by_id.append_and_get_index(&node);
+  node.m_function = &function;
+  node.m_input_param_indices = m_allocator.construct_array_copy<uint>(input_param_indices);
+  node.m_output_param_indices = m_allocator.construct_array_copy<uint>(output_param_indices);
+
+  node.m_inputs = m_allocator.construct_elements_and_pointer_array<MFInputSocket>(
+      input_param_indices.size());
+  node.m_outputs = m_allocator.construct_elements_and_pointer_array<MFOutputSocket>(
+      output_param_indices.size());
+
+  for (uint i : input_param_indices.index_range()) {
+    uint param_index = input_param_indices[i];
+    MFParamType param = function.param_type(param_index);
+    BLI_assert(param.is_input_or_mutable());
+
+    MFInputSocket &socket = *node.m_inputs[i];
+    socket.m_data_type = param.data_type();
+    socket.m_node = &node;
+    socket.m_index = i;
+    socket.m_is_output = false;
+    socket.m_name = function.param_name(param_index);
+    socket.m_origin = nullptr;
+    socket.m_id = m_socket_or_null_by_id.append_and_get_index(&socket);
+  }
+
+  for (uint i : output_param_indices.index_range()) {
+    uint param_index = output_param_indices[i];
+    MFParamType param = function.param_type(param_index);
+    BLI_assert(param.is_output_or_mutable());
+
+    MFOutputSocket &socket = *node.m_outputs[i];
+    socket.m_data_type = param.data_type();
+    socket.m_node = &node;
+    socket.m_index = i;
+    socket.m_is_output = true;
+    socket.m_name = function.param_name(param_index);
+    socket.m_id = m_socket_or_null_by_id.append_and_get_index(&socket);
+  }
+
+  return node;
+}
+
+/**
+ * Add a dummy node with the given input and output sockets.
+ */
+MFDummyNode &MFNetwork::add_dummy(StringRef name,
+                                  Span<MFDataType> input_types,
+                                  Span<MFDataType> output_types,
+                                  Span<StringRef> input_names,
+                                  Span<StringRef> output_names)
+{
+  assert_same_size(input_types, input_names);
+  assert_same_size(output_types, output_names);
+
+  MFDummyNode &node = *m_allocator.construct<MFDummyNode>();
+  m_dummy_nodes.add_new(&node);
+
+  node.m_network = this;
+  node.m_is_dummy = true;
+  node.m_name = m_allocator.copy_string(name);
+  node.m_id = m_node_or_null_by_id.append_and_get_index(&node);
+
+  node.m_inputs = m_allocator.construct_elements_and_pointer_array<MFInputSocket>(
+      input_types.size());
+  node.m_outputs = m_allocator.construct_elements_and_pointer_array<MFOutputSocket>(
+      output_types.size());
+
+  node.m_input_names = m_allocator.allocate_array<StringRefNull>(input_types.size());
+  node.m_output_names = m_allocator.allocate_array<StringRefNull>(output_types.size());
+
+  for (uint i : input_types.index_range()) {
+    MFInputSocket &socket = *node.m_inputs[i];
+    socket.m_data_type = input_types[i];
+    socket.m_node = &node;
+    socket.m_index = i;
+    socket.m_is_output = false;
+    socket.m_name = m_allocator.copy_string(input_names[i]);
+    socket.m_id = m_socket_or_null_by_id.append_and_get_index(&socket);
+    node.m_input_names[i] = socket.m_name;
+  }
+
+  for (uint i : output_types.index_range()) {
+    MFOutputSocket &socket = *node.m_outputs[i];
+    socket.m_data_type = output_types[i];
+    socket.m_node = &node;
+    socket.m_index = i;
+    socket.m_is_output = true;
+    socket.m_name = m_allocator.copy_string(output_names[i]);
+    socket.m_id = m_socket_or_null_by_id.append_and_get_index(&socket);
+    node.m_output_names[i] = socket.m_name;
+  }
+
+  return node;
+}
+
+/**
+ * Connect two sockets. This invokes undefined behavior if the sockets belong to different
+ * networks, the sockets have a different data type, or the `to` socket is connected to something
+ * else already.
+ */
+void MFNetwork::add_link(MFOutputSocket &from, MFInputSocket &to)
+{
+  BLI_assert(to.m_origin == nullptr);
+  BLI_assert(from.m_node->m_network == to.m_node->m_network);
+  BLI_assert(from.m_data_type == to.m_data_type);
+  from.m_targets.append(&to);
+  to.m_origin = &from;
+}
+
+MFOutputSocket &MFNetwork::add_input(StringRef name, MFDataType data_type)
+{
+  return this->add_dummy(name, {}, {data_type}, {}, {name}).output(0);
+}
+
+MFInputSocket &MFNetwork::add_output(StringRef name, MFDataType data_type)
+{
+  return this->add_dummy(name, {data_type}, {}, {name}, {}).input(0);
+}
+
+std::string MFNetwork::to_dot() const
+{
+  namespace Dot = blender::DotExport;
+
+  Dot::DirectedGraph digraph;
+  digraph.set_rankdir(Dot::Attr_rankdir::LeftToRight);
+
+  Map<const MFNode *, Dot::NodeWithSocketsRef> dot_nodes;
+
+  Vector<const MFNode *> all_nodes;
+  all_nodes.extend(m_function_nodes.as_span());
+  all_nodes.extend(m_dummy_nodes.as_span());
+
+  for (const MFNode *node : all_nodes) {
+    Dot::Node &dot_node = digraph.new_node("");
+
+    Vector<std::string> input_names, output_names;
+    for (const MFInputSocket *socket : node->m_inputs) {
+      input_names.append(socket->name() + "(" + socket->data_type().to_string() + ")");
+    }
+    for (const MFOutputSocket *socket : node->m_outputs) {
+      output_names.append(socket->name() + " (" + socket->data_type().to_string() + ")");
+    }
+
+    Dot::NodeWithSocketsRef dot_node_ref{dot_node, node->name(), input_names, output_names};
+    dot_nodes.add_new(node, dot_node_ref);
+  }
+
+  for (const MFNode *to_node : all_nodes) {
+    Dot::NodeWithSocketsRef to_dot_node = dot_nodes.lookup(to_node);
+
+    for (const MFInputSocket *to_socket : to_node->m_inputs) {
+      const MFOutputSocket *from_socket = to_socket->m_origin;
+      if (from_socket != nullptr) {
+        const MFNode *from_node = from_socket->m_node;
+        Dot::NodeWithSocketsRef from_dot_node = dot_nodes.lookup(from_node);
+        digraph.new_edge(from_dot_node.output(from_socket->m_index),
+                         to_dot_node.input(to_socket->m_index));
+      }
+    }
+  }
+
+  return digraph.to_dot_string();
+}
+
+}  // namespace fn
+}  // namespace blender
diff --git a/source/blender/functions/intern/multi_function_network_evaluation.cc b/source/blender/functions/intern/multi_function_network_evaluation.cc
new file mode 100644
index 00000000000..35eda4c157a
--- /dev/null
+++ b/source/blender/functions/intern/multi_function_network_evaluation.cc
@@ -0,0 +1,1063 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup fn
+ *
+ * The `MFNetworkEvaluator` class is a multi-function that consists of potentially many smaller
+ * multi-functions. When called, it traverses the underlying MFNetwork and executes the required
+ * function nodes.
+ *
+ * There are many possible approaches to evaluate a function network. The approach implemented
+ * below has the following features:
+ * - It does not use recursion. Those could become problematic with long node chains.
+ * - It can handle all existing parameter types (including mutable parameters).
+ * - Avoids data copies in many cases.
+ * - Every node is executed at most once.
+ * - Can compute subfunctions on a single element, when the result is the same for all elements.
+ *
+ * Possible improvements:
+ * - Cache and reuse buffers.
+ * - Use "deepest depth first" heuristic to decide which order the inputs of a node should be
+ *   computed. This reduces the number of required temporary buffers when they are reused.
+ */
+
+#include "FN_multi_function_network_evaluation.hh"
+
+#include "BLI_stack.hh"
+
+namespace blender {
+namespace fn {
+
+struct Value;
+
+/**
+ * This keeps track of all the values that flow through the multi-function network. Therefore it
+ * maintains a mapping between output sockets and their corresponding values. Every `value`
+ * references some memory, that is owned either by the caller or this storage.
+ *
+ * A value can be owned by different sockets over time to avoid unnecessary copies.
+ */
+class MFNetworkEvaluationStorage {
+ private:
+  LinearAllocator<> m_allocator;
+  IndexMask m_mask;
+  Array<Value *> m_value_per_output_id;
+  uint m_min_array_size;
+
+ public:
+  MFNetworkEvaluationStorage(IndexMask mask, uint max_socket_id);
+  ~MFNetworkEvaluationStorage();
+
+  /* Add the values that have been provided by the caller of the multi-function network. */
+  void add_single_input_from_caller(const MFOutputSocket &socket, GVSpan virtual_span);
+  void add_vector_input_from_caller(const MFOutputSocket &socket, GVArraySpan virtual_array_span);
+  void add_single_output_from_caller(const MFOutputSocket &socket, GMutableSpan span);
+  void add_vector_output_from_caller(const MFOutputSocket &socket, GVectorArray &vector_array);
+
+  /* Get input buffers for function node evaluations. */
+  GVSpan get_single_input__full(const MFInputSocket &socket);
+  GVSpan get_single_input__single(const MFInputSocket &socket);
+  GVArraySpan get_vector_input__full(const MFInputSocket &socket);
+  GVArraySpan get_vector_input__single(const MFInputSocket &socket);
+
+  /* Get output buffers for function node evaluations. */
+  GMutableSpan get_single_output__full(const MFOutputSocket &socket);
+  GMutableSpan get_single_output__single(const MFOutputSocket &socket);
+  GVectorArray &get_vector_output__full(const MFOutputSocket &socket);
+  GVectorArray &get_vector_output__single(const MFOutputSocket &socket);
+
+  /* Get mutable buffers for function node evaluations. */
+  GMutableSpan get_mutable_single__full(const MFInputSocket &input, const MFOutputSocket &output);
+  GMutableSpan get_mutable_single__single(const MFInputSocket &input,
+                                          const MFOutputSocket &output);
+  GVectorArray &get_mutable_vector__full(const MFInputSocket &input, const MFOutputSocket &output);
+  GVectorArray &get_mutable_vector__single(const MFInputSocket &input,
+                                           const MFOutputSocket &output);
+
+  /* Mark a node as being done with evaluation. This might free temporary buffers that are no
+   * longer needed. */
+  void finish_node(const MFFunctionNode &node);
+  void finish_output_socket(const MFOutputSocket &socket);
+  void finish_input_socket(const MFInputSocket &socket);
+
+  IndexMask mask() const;
+  bool socket_is_computed(const MFOutputSocket &socket);
+  bool is_same_value_for_every_index(const MFOutputSocket &socket);
+  bool socket_has_buffer_for_output(const MFOutputSocket &socket);
+};
+
+MFNetworkEvaluator::MFNetworkEvaluator(Vector<const MFOutputSocket *> inputs,
+                                       Vector<const MFInputSocket *> outputs)
+    : m_inputs(std::move(inputs)), m_outputs(std::move(outputs))
+{
+  BLI_assert(m_outputs.size() > 0);
+  MFSignatureBuilder signature = this->get_builder("Function Tree");
+
+  for (auto socket : m_inputs) {
+    BLI_assert(socket->node().is_dummy());
+
+    MFDataType type = socket->data_type();
+    switch (type.category()) {
+      case MFDataType::Single:
+        signature.single_input("Input", type.single_type());
+        break;
+      case MFDataType::Vector:
+        signature.vector_input("Input", type.vector_base_type());
+        break;
+    }
+  }
+
+  for (auto socket : m_outputs) {
+    BLI_assert(socket->node().is_dummy());
+
+    MFDataType type = socket->data_type();
+    switch (type.category()) {
+      case MFDataType::Single:
+        signature.single_output("Output", type.single_type());
+        break;
+      case MFDataType::Vector:
+        signature.vector_output("Output", type.vector_base_type());
+        break;
+    }
+  }
+}
+
+void MFNetworkEvaluator::call(IndexMask mask, MFParams params, MFContext context) const
+{
+  if (mask.size() == 0) {
+    return;
+  }
+
+  const MFNetwork &network = m_outputs[0]->node().network();
+  Storage storage(mask, network.max_socket_id());
+
+  Vector<const MFInputSocket *> outputs_to_initialize_in_the_end;
+
+  this->copy_inputs_to_storage(params, storage);
+  this->copy_outputs_to_storage(params, storage, outputs_to_initialize_in_the_end);
+  this->evaluate_network_to_compute_outputs(context, storage);
+  this->initialize_remaining_outputs(params, storage, outputs_to_initialize_in_the_end);
+}
+
+BLI_NOINLINE void MFNetworkEvaluator::copy_inputs_to_storage(MFParams params,
+                                                             Storage &storage) const
+{
+  for (uint input_index : m_inputs.index_range()) {
+    uint param_index = input_index + 0;
+    const MFOutputSocket &socket = *m_inputs[input_index];
+    switch (socket.data_type().category()) {
+      case MFDataType::Single: {
+        GVSpan input_list = params.readonly_single_input(param_index);
+        storage.add_single_input_from_caller(socket, input_list);
+        break;
+      }
+      case MFDataType::Vector: {
+        GVArraySpan input_list_list = params.readonly_vector_input(param_index);
+        storage.add_vector_input_from_caller(socket, input_list_list);
+        break;
+      }
+    }
+  }
+}
+
+BLI_NOINLINE void MFNetworkEvaluator::copy_outputs_to_storage(
+    MFParams params,
+    Storage &storage,
+    Vector<const MFInputSocket *> &outputs_to_initialize_in_the_end) const
+{
+  for (uint output_index : m_outputs.index_range()) {
+    uint param_index = output_index + m_inputs.size();
+    const MFInputSocket &socket = *m_outputs[output_index];
+    const MFOutputSocket &origin = *socket.origin();
+
+    if (origin.node().is_dummy()) {
+      BLI_assert(m_inputs.contains(&origin));
+      /* Don't overwrite input buffers. */
+      outputs_to_initialize_in_the_end.append(&socket);
+      continue;
+    }
+
+    if (storage.socket_has_buffer_for_output(origin)) {
+      /* When two outputs will be initialized to the same values. */
+      outputs_to_initialize_in_the_end.append(&socket);
+      continue;
+    }
+
+    switch (socket.data_type().category()) {
+      case MFDataType::Single: {
+        GMutableSpan span = params.uninitialized_single_output(param_index);
+        storage.add_single_output_from_caller(origin, span);
+        break;
+      }
+      case MFDataType::Vector: {
+        GVectorArray &vector_array = params.vector_output(param_index);
+        storage.add_vector_output_from_caller(origin, vector_array);
+        break;
+      }
+    }
+  }
+}
+
+BLI_NOINLINE void MFNetworkEvaluator::evaluate_network_to_compute_outputs(
+    MFContext &global_context, Storage &storage) const
+{
+  Stack<const MFOutputSocket *, 32> sockets_to_compute;
+  for (const MFInputSocket *socket : m_outputs) {
+    sockets_to_compute.push(socket->origin());
+  }
+
+  Vector<const MFOutputSocket *, 32> missing_sockets;
+
+  /* This is the main loop that traverses the MFNetwork. */
+  while (!sockets_to_compute.is_empty()) {
+    const MFOutputSocket &socket = *sockets_to_compute.peek();
+    const MFNode &node = socket.node();
+
+    if (storage.socket_is_computed(socket)) {
+      sockets_to_compute.pop();
+      continue;
+    }
+
+    BLI_assert(node.is_function());
+    BLI_assert(node.all_inputs_have_origin());
+    const MFFunctionNode &function_node = node.as_function();
+
+    missing_sockets.clear();
+    function_node.foreach_origin_socket([&](const MFOutputSocket &origin) {
+      if (!storage.socket_is_computed(origin)) {
+        missing_sockets.append(&origin);
+      }
+    });
+
+    sockets_to_compute.push_multiple(missing_sockets);
+
+    bool all_inputs_are_computed = missing_sockets.size() == 0;
+    if (all_inputs_are_computed) {
+      this->evaluate_function(global_context, function_node, storage);
+      sockets_to_compute.pop();
+    }
+  }
+}
+
+BLI_NOINLINE void MFNetworkEvaluator::evaluate_function(MFContext &global_context,
+                                                        const MFFunctionNode &function_node,
+                                                        Storage &storage) const
+{
+  const MultiFunction &function = function_node.function();
+  // std::cout << "Function: " << function.name() << "\n";
+
+  if (this->can_do_single_value_evaluation(function_node, storage)) {
+    /* The function output would be the same for all elements. Therefore, it is enough to call the
+     * function only on a single element. This can avoid many duplicate computations. */
+    MFParamsBuilder params{function, 1};
+
+    for (uint param_index : function.param_indices()) {
+      MFParamType param_type = function.param_type(param_index);
+      switch (param_type.category()) {
+        case MFParamType::SingleInput: {
+          const MFInputSocket &socket = function_node.input_for_param(param_index);
+          GVSpan values = storage.get_single_input__single(socket);
+          params.add_readonly_single_input(values);
+          break;
+        }
+        case MFParamType::VectorInput: {
+          const MFInputSocket &socket = function_node.input_for_param(param_index);
+          GVArraySpan values = storage.get_vector_input__single(socket);
+          params.add_readonly_vector_input(values);
+          break;
+        }
+        case MFParamType::SingleOutput: {
+          const MFOutputSocket &socket = function_node.output_for_param(param_index);
+          GMutableSpan values = storage.get_single_output__single(socket);
+          params.add_uninitialized_single_output(values);
+          break;
+        }
+        case MFParamType::VectorOutput: {
+          const MFOutputSocket &socket = function_node.output_for_param(param_index);
+          GVectorArray &values = storage.get_vector_output__single(socket);
+          params.add_vector_output(values);
+          break;
+        }
+        case MFParamType::SingleMutable: {
+          const MFInputSocket &input = function_node.input_for_param(param_index);
+          const MFOutputSocket &output = function_node.output_for_param(param_index);
+          GMutableSpan values = storage.get_mutable_single__single(input, output);
+          params.add_single_mutable(values);
+          break;
+        }
+        case MFParamType::VectorMutable: {
+          const MFInputSocket &input = function_node.input_for_param(param_index);
+          const MFOutputSocket &output = function_node.output_for_param(param_index);
+          GVectorArray &values = storage.get_mutable_vector__single(input, output);
+          params.add_vector_mutable(values);
+          break;
+        }
+      }
+    }
+
+    function.call(IndexRange(1), params, global_context);
+  }
+  else {
+    MFParamsBuilder params{function, storage.mask().min_array_size()};
+
+    for (uint param_index : function.param_indices()) {
+      MFParamType param_type = function.param_type(param_index);
+      switch (param_type.category()) {
+        case MFParamType::SingleInput: {
+          const MFInputSocket &socket = function_node.input_for_param(param_index);
+          GVSpan values = storage.get_single_input__full(socket);
+          params.add_readonly_single_input(values);
+          break;
+        }
+        case MFParamType::VectorInput: {
+          const MFInputSocket &socket = function_node.input_for_param(param_index);
+          GVArraySpan values = storage.get_vector_input__full(socket);
+          params.add_readonly_vector_input(values);
+          break;
+        }
+        case MFParamType::SingleOutput: {
+          const MFOutputSocket &socket = function_node.output_for_param(param_index);
+          GMutableSpan values = storage.get_single_output__full(socket);
+          params.add_uninitialized_single_output(values);
+          break;
+        }
+        case MFParamType::VectorOutput: {
+          const MFOutputSocket &socket = function_node.output_for_param(param_index);
+          GVectorArray &values = storage.get_vector_output__full(socket);
+          params.add_vector_output(values);
+          break;
+        }
+        case MFParamType::SingleMutable: {
+          const MFInputSocket &input = function_node.input_for_param(param_index);
+          const MFOutputSocket &output = function_node.output_for_param(param_index);
+          GMutableSpan values = storage.get_mutable_single__full(input, output);
+          params.add_single_mutable(values);
+          break;
+        }
+        case MFParamType::VectorMutable: {
+          const MFInputSocket &input = function_node.input_for_param(param_index);
+          const MFOutputSocket &output = function_node.output_for_param(param_index);
+          GVectorArray &values = storage.get_mutable_vector__full(input, output);
+          params.add_vector_mutable(values);
+          break;
+        }
+      }
+    }
+
+    function.call(storage.mask(), params, global_context);
+  }
+
+  storage.finish_node(function_node);
+}
+
+bool MFNetworkEvaluator::can_do_single_value_evaluation(const MFFunctionNode &function_node,
+                                                        Storage &storage) const
+{
+  for (const MFInputSocket *socket : function_node.inputs()) {
+    if (!storage.is_same_value_for_every_index(*socket->origin())) {
+      return false;
+    }
+  }
+  if (storage.mask().min_array_size() >= 1) {
+    for (const MFOutputSocket *socket : function_node.outputs()) {
+      if (storage.socket_has_buffer_for_output(*socket)) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+BLI_NOINLINE void MFNetworkEvaluator::initialize_remaining_outputs(
+    MFParams params, Storage &storage, Span<const MFInputSocket *> remaining_outputs) const
+{
+  for (const MFInputSocket *socket : remaining_outputs) {
+    uint param_index = m_inputs.size() + m_outputs.first_index_of(socket);
+
+    switch (socket->data_type().category()) {
+      case MFDataType::Single: {
+        GVSpan values = storage.get_single_input__full(*socket);
+        GMutableSpan output_values = params.uninitialized_single_output(param_index);
+        values.materialize_to_uninitialized(storage.mask(), output_values.buffer());
+        break;
+      }
+      case MFDataType::Vector: {
+        GVArraySpan values = storage.get_vector_input__full(*socket);
+        GVectorArray &output_values = params.vector_output(param_index);
+        output_values.extend(storage.mask(), values);
+        break;
+      }
+    }
+  }
+}
+
+/* -------------------------------------------------------------------- */
+/** \name Value Types
+ * \{ */
+
+enum class ValueType {
+  InputSingle,
+  InputVector,
+  OutputSingle,
+  OutputVector,
+  OwnSingle,
+  OwnVector,
+};
+
+struct Value {
+  ValueType type;
+
+  Value(ValueType type) : type(type)
+  {
+  }
+};
+
+struct InputSingleValue : public Value {
+  /** This span has been provided by the code that called the multi-function network. */
+  GVSpan virtual_span;
+
+  InputSingleValue(GVSpan virtual_span) : Value(ValueType::InputSingle), virtual_span(virtual_span)
+  {
+  }
+};
+
+struct InputVectorValue : public Value {
+  /** This span has been provided by the code that called the multi-function network. */
+  GVArraySpan virtual_array_span;
+
+  InputVectorValue(GVArraySpan virtual_array_span)
+      : Value(ValueType::InputVector), virtual_array_span(virtual_array_span)
+  {
+  }
+};
+
+struct OutputValue : public Value {
+  bool is_computed = false;
+
+  OutputValue(ValueType type) : Value(type)
+  {
+  }
+};
+
+struct OutputSingleValue : public OutputValue {
+  /** This span has been provided by the code that called the multi-function network. */
+  GMutableSpan span;
+
+  OutputSingleValue(GMutableSpan span) : OutputValue(ValueType::OutputSingle), span(span)
+  {
+  }
+};
+
+struct OutputVectorValue : public OutputValue {
+  /** This vector array has been provided by the code that called the multi-function network. */
+  GVectorArray *vector_array;
+
+  OutputVectorValue(GVectorArray &vector_array)
+      : OutputValue(ValueType::OutputVector), vector_array(&vector_array)
+  {
+  }
+};
+
+struct OwnSingleValue : public Value {
+  /** This span has been allocated during the evaluation of the multi-function network and contains
+   * intermediate data. It has to be freed once the network evaluation is finished. */
+  GMutableSpan span;
+  int max_remaining_users;
+  bool is_single_allocated;
+
+  OwnSingleValue(GMutableSpan span, int max_remaining_users, bool is_single_allocated)
+      : Value(ValueType::OwnSingle),
+        span(span),
+        max_remaining_users(max_remaining_users),
+        is_single_allocated(is_single_allocated)
+  {
+  }
+};
+
+struct OwnVectorValue : public Value {
+  /** This vector array has been allocated during the evaluation of the multi-function network and
+   * contains intermediate data. It has to be freed once the network evaluation is finished. */
+  GVectorArray *vector_array;
+  int max_remaining_users;
+
+  OwnVectorValue(GVectorArray &vector_array, int max_remaining_users)
+      : Value(ValueType::OwnVector),
+        vector_array(&vector_array),
+        max_remaining_users(max_remaining_users)
+  {
+  }
+};
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Storage methods
+ * \{ */
+
+MFNetworkEvaluationStorage::MFNetworkEvaluationStorage(IndexMask mask, uint max_socket_id)
+    : m_mask(mask),
+      m_value_per_output_id(max_socket_id + 1, nullptr),
+      m_min_array_size(mask.min_array_size())
+{
+}
+
+MFNetworkEvaluationStorage::~MFNetworkEvaluationStorage()
+{
+  for (Value *any_value : m_value_per_output_id) {
+    if (any_value == nullptr) {
+      continue;
+    }
+    else if (any_value->type == ValueType::OwnSingle) {
+      OwnSingleValue *value = (OwnSingleValue *)any_value;
+      GMutableSpan span = value->span;
+      const CPPType &type = span.type();
+      if (value->is_single_allocated) {
+        type.destruct(span.buffer());
+      }
+      else {
+        type.destruct_indices(span.buffer(), m_mask);
+        MEM_freeN(span.buffer());
+      }
+    }
+    else if (any_value->type == ValueType::OwnVector) {
+      OwnVectorValue *value = (OwnVectorValue *)any_value;
+      delete value->vector_array;
+    }
+  }
+}
+
+IndexMask MFNetworkEvaluationStorage::mask() const
+{
+  return m_mask;
+}
+
+bool MFNetworkEvaluationStorage::socket_is_computed(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    return false;
+  }
+  if (ELEM(any_value->type, ValueType::OutputSingle, ValueType::OutputVector)) {
+    return ((OutputValue *)any_value)->is_computed;
+  }
+  return true;
+}
+
+bool MFNetworkEvaluationStorage::is_same_value_for_every_index(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  switch (any_value->type) {
+    case ValueType::OwnSingle:
+      return ((OwnSingleValue *)any_value)->span.size() == 1;
+    case ValueType::OwnVector:
+      return ((OwnVectorValue *)any_value)->vector_array->size() == 1;
+    case ValueType::InputSingle:
+      return ((InputSingleValue *)any_value)->virtual_span.is_single_element();
+    case ValueType::InputVector:
+      return ((InputVectorValue *)any_value)->virtual_array_span.is_single_array();
+    case ValueType::OutputSingle:
+      return ((OutputSingleValue *)any_value)->span.size() == 1;
+    case ValueType::OutputVector:
+      return ((OutputVectorValue *)any_value)->vector_array->size() == 1;
+  }
+  BLI_assert(false);
+  return false;
+}
+
+bool MFNetworkEvaluationStorage::socket_has_buffer_for_output(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    return false;
+  }
+
+  BLI_assert(ELEM(any_value->type, ValueType::OutputSingle, ValueType::OutputVector));
+  return true;
+}
+
+void MFNetworkEvaluationStorage::finish_node(const MFFunctionNode &node)
+{
+  for (const MFInputSocket *socket : node.inputs()) {
+    this->finish_input_socket(*socket);
+  }
+  for (const MFOutputSocket *socket : node.outputs()) {
+    this->finish_output_socket(*socket);
+  }
+}
+
+void MFNetworkEvaluationStorage::finish_output_socket(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    return;
+  }
+
+  if (ELEM(any_value->type, ValueType::OutputSingle, ValueType::OutputVector)) {
+    ((OutputValue *)any_value)->is_computed = true;
+  }
+}
+
+void MFNetworkEvaluationStorage::finish_input_socket(const MFInputSocket &socket)
+{
+  const MFOutputSocket &origin = *socket.origin();
+
+  Value *any_value = m_value_per_output_id[origin.id()];
+  if (any_value == nullptr) {
+    /* Can happen when a value has been forward to the next node. */
+    return;
+  }
+
+  switch (any_value->type) {
+    case ValueType::InputSingle:
+    case ValueType::OutputSingle:
+    case ValueType::InputVector:
+    case ValueType::OutputVector: {
+      break;
+    }
+    case ValueType::OwnSingle: {
+      OwnSingleValue *value = (OwnSingleValue *)any_value;
+      BLI_assert(value->max_remaining_users >= 1);
+      value->max_remaining_users--;
+      if (value->max_remaining_users == 0) {
+        GMutableSpan span = value->span;
+        const CPPType &type = span.type();
+        if (value->is_single_allocated) {
+          type.destruct(span.buffer());
+        }
+        else {
+          type.destruct_indices(span.buffer(), m_mask);
+          MEM_freeN(span.buffer());
+        }
+        m_value_per_output_id[origin.id()] = nullptr;
+      }
+      break;
+    }
+    case ValueType::OwnVector: {
+      OwnVectorValue *value = (OwnVectorValue *)any_value;
+      BLI_assert(value->max_remaining_users >= 1);
+      value->max_remaining_users--;
+      if (value->max_remaining_users == 0) {
+        delete value->vector_array;
+        m_value_per_output_id[origin.id()] = nullptr;
+      }
+      break;
+    }
+  }
+}
+
+void MFNetworkEvaluationStorage::add_single_input_from_caller(const MFOutputSocket &socket,
+                                                              GVSpan virtual_span)
+{
+  BLI_assert(m_value_per_output_id[socket.id()] == nullptr);
+  BLI_assert(virtual_span.size() >= m_min_array_size);
+
+  auto *value = m_allocator.construct<InputSingleValue>(virtual_span);
+  m_value_per_output_id[socket.id()] = value;
+}
+
+void MFNetworkEvaluationStorage::add_vector_input_from_caller(const MFOutputSocket &socket,
+                                                              GVArraySpan virtual_array_span)
+{
+  BLI_assert(m_value_per_output_id[socket.id()] == nullptr);
+  BLI_assert(virtual_array_span.size() >= m_min_array_size);
+
+  auto *value = m_allocator.construct<InputVectorValue>(virtual_array_span);
+  m_value_per_output_id[socket.id()] = value;
+}
+
+void MFNetworkEvaluationStorage::add_single_output_from_caller(const MFOutputSocket &socket,
+                                                               GMutableSpan span)
+{
+  BLI_assert(m_value_per_output_id[socket.id()] == nullptr);
+  BLI_assert(span.size() >= m_min_array_size);
+
+  auto *value = m_allocator.construct<OutputSingleValue>(span);
+  m_value_per_output_id[socket.id()] = value;
+}
+
+void MFNetworkEvaluationStorage::add_vector_output_from_caller(const MFOutputSocket &socket,
+                                                               GVectorArray &vector_array)
+{
+  BLI_assert(m_value_per_output_id[socket.id()] == nullptr);
+  BLI_assert(vector_array.size() >= m_min_array_size);
+
+  auto *value = m_allocator.construct<OutputVectorValue>(vector_array);
+  m_value_per_output_id[socket.id()] = value;
+}
+
+GMutableSpan MFNetworkEvaluationStorage::get_single_output__full(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    const CPPType &type = socket.data_type().single_type();
+    void *buffer = MEM_mallocN_aligned(m_min_array_size * type.size(), type.alignment(), AT);
+    GMutableSpan span(type, buffer, m_min_array_size);
+
+    auto *value = m_allocator.construct<OwnSingleValue>(span, socket.targets().size(), false);
+    m_value_per_output_id[socket.id()] = value;
+
+    return span;
+  }
+  else {
+    BLI_assert(any_value->type == ValueType::OutputSingle);
+    return ((OutputSingleValue *)any_value)->span;
+  }
+}
+
+GMutableSpan MFNetworkEvaluationStorage::get_single_output__single(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    const CPPType &type = socket.data_type().single_type();
+    void *buffer = m_allocator.allocate(type.size(), type.alignment());
+    GMutableSpan span(type, buffer, 1);
+
+    auto *value = m_allocator.construct<OwnSingleValue>(span, socket.targets().size(), true);
+    m_value_per_output_id[socket.id()] = value;
+
+    return value->span;
+  }
+  else {
+    BLI_assert(any_value->type == ValueType::OutputSingle);
+    GMutableSpan span = ((OutputSingleValue *)any_value)->span;
+    BLI_assert(span.size() == 1);
+    return span;
+  }
+}
+
+GVectorArray &MFNetworkEvaluationStorage::get_vector_output__full(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    const CPPType &type = socket.data_type().vector_base_type();
+    GVectorArray *vector_array = new GVectorArray(type, m_min_array_size);
+
+    auto *value = m_allocator.construct<OwnVectorValue>(*vector_array, socket.targets().size());
+    m_value_per_output_id[socket.id()] = value;
+
+    return *value->vector_array;
+  }
+  else {
+    BLI_assert(any_value->type == ValueType::OutputVector);
+    return *((OutputVectorValue *)any_value)->vector_array;
+  }
+}
+
+GVectorArray &MFNetworkEvaluationStorage::get_vector_output__single(const MFOutputSocket &socket)
+{
+  Value *any_value = m_value_per_output_id[socket.id()];
+  if (any_value == nullptr) {
+    const CPPType &type = socket.data_type().vector_base_type();
+    GVectorArray *vector_array = new GVectorArray(type, 1);
+
+    auto *value = m_allocator.construct<OwnVectorValue>(*vector_array, socket.targets().size());
+    m_value_per_output_id[socket.id()] = value;
+
+    return *value->vector_array;
+  }
+  else {
+    BLI_assert(any_value->type == ValueType::OutputVector);
+    GVectorArray &vector_array = *((OutputVectorValue *)any_value)->vector_array;
+    BLI_assert(vector_array.size() == 1);
+    return vector_array;
+  }
+}
+
+GMutableSpan MFNetworkEvaluationStorage::get_mutable_single__full(const MFInputSocket &input,
+                                                                  const MFOutputSocket &output)
+{
+  const MFOutputSocket &from = *input.origin();
+  const MFOutputSocket &to = output;
+  const CPPType &type = from.data_type().single_type();
+
+  Value *from_any_value = m_value_per_output_id[from.id()];
+  Value *to_any_value = m_value_per_output_id[to.id()];
+  BLI_assert(from_any_value != nullptr);
+  BLI_assert(type == to.data_type().single_type());
+
+  if (to_any_value != nullptr) {
+    BLI_assert(to_any_value->type == ValueType::OutputSingle);
+    GMutableSpan span = ((OutputSingleValue *)to_any_value)->span;
+    GVSpan virtual_span = this->get_single_input__full(input);
+    virtual_span.materialize_to_uninitialized(m_mask, span.buffer());
+    return span;
+  }
+
+  if (from_any_value->type == ValueType::OwnSingle) {
+    OwnSingleValue *value = (OwnSingleValue *)from_any_value;
+    if (value->max_remaining_users == 1 && !value->is_single_allocated) {
+      m_value_per_output_id[to.id()] = value;
+      m_value_per_output_id[from.id()] = nullptr;
+      value->max_remaining_users = to.targets().size();
+      return value->span;
+    }
+  }
+
+  GVSpan virtual_span = this->get_single_input__full(input);
+  void *new_buffer = MEM_mallocN_aligned(m_min_array_size * type.size(), type.alignment(), AT);
+  GMutableSpan new_array_ref(type, new_buffer, m_min_array_size);
+  virtual_span.materialize_to_uninitialized(m_mask, new_array_ref.buffer());
+
+  OwnSingleValue *new_value = m_allocator.construct<OwnSingleValue>(
+      new_array_ref, to.targets().size(), false);
+  m_value_per_output_id[to.id()] = new_value;
+  return new_array_ref;
+}
+
+GMutableSpan MFNetworkEvaluationStorage::get_mutable_single__single(const MFInputSocket &input,
+                                                                    const MFOutputSocket &output)
+{
+  const MFOutputSocket &from = *input.origin();
+  const MFOutputSocket &to = output;
+  const CPPType &type = from.data_type().single_type();
+
+  Value *from_any_value = m_value_per_output_id[from.id()];
+  Value *to_any_value = m_value_per_output_id[to.id()];
+  BLI_assert(from_any_value != nullptr);
+  BLI_assert(type == to.data_type().single_type());
+
+  if (to_any_value != nullptr) {
+    BLI_assert(to_any_value->type == ValueType::OutputSingle);
+    GMutableSpan span = ((OutputSingleValue *)to_any_value)->span;
+    BLI_assert(span.size() == 1);
+    GVSpan virtual_span = this->get_single_input__single(input);
+    type.copy_to_uninitialized(virtual_span.as_single_element(), span[0]);
+    return span;
+  }
+
+  if (from_any_value->type == ValueType::OwnSingle) {
+    OwnSingleValue *value = (OwnSingleValue *)from_any_value;
+    if (value->max_remaining_users == 1) {
+      m_value_per_output_id[to.id()] = value;
+      m_value_per_output_id[from.id()] = nullptr;
+      value->max_remaining_users = to.targets().size();
+      BLI_assert(value->span.size() == 1);
+      return value->span;
+    }
+  }
+
+  GVSpan virtual_span = this->get_single_input__single(input);
+
+  void *new_buffer = m_allocator.allocate(type.size(), type.alignment());
+  type.copy_to_uninitialized(virtual_span.as_single_element(), new_buffer);
+  GMutableSpan new_array_ref(type, new_buffer, 1);
+
+  OwnSingleValue *new_value = m_allocator.construct<OwnSingleValue>(
+      new_array_ref, to.targets().size(), true);
+  m_value_per_output_id[to.id()] = new_value;
+  return new_array_ref;
+}
+
+GVectorArray &MFNetworkEvaluationStorage::get_mutable_vector__full(const MFInputSocket &input,
+                                                                   const MFOutputSocket &output)
+{
+  const MFOutputSocket &from = *input.origin();
+  const MFOutputSocket &to = output;
+  const CPPType &base_type = from.data_type().vector_base_type();
+
+  Value *from_any_value = m_value_per_output_id[from.id()];
+  Value *to_any_value = m_value_per_output_id[to.id()];
+  BLI_assert(from_any_value != nullptr);
+  BLI_assert(base_type == to.data_type().vector_base_type());
+
+  if (to_any_value != nullptr) {
+    BLI_assert(to_any_value->type == ValueType::OutputVector);
+    GVectorArray &vector_array = *((OutputVectorValue *)to_any_value)->vector_array;
+    GVArraySpan virtual_array_span = this->get_vector_input__full(input);
+    vector_array.extend(m_mask, virtual_array_span);
+    return vector_array;
+  }
+
+  if (from_any_value->type == ValueType::OwnVector) {
+    OwnVectorValue *value = (OwnVectorValue *)from_any_value;
+    if (value->max_remaining_users == 1) {
+      m_value_per_output_id[to.id()] = value;
+      m_value_per_output_id[from.id()] = nullptr;
+      value->max_remaining_users = to.targets().size();
+      return *value->vector_array;
+    }
+  }
+
+  GVArraySpan virtual_array_span = this->get_vector_input__full(input);
+
+  GVectorArray *new_vector_array = new GVectorArray(base_type, m_min_array_size);
+  new_vector_array->extend(m_mask, virtual_array_span);
+
+  OwnVectorValue *new_value = m_allocator.construct<OwnVectorValue>(*new_vector_array,
+                                                                    to.targets().size());
+  m_value_per_output_id[to.id()] = new_value;
+
+  return *new_vector_array;
+}
+
+GVectorArray &MFNetworkEvaluationStorage::get_mutable_vector__single(const MFInputSocket &input,
+                                                                     const MFOutputSocket &output)
+{
+  const MFOutputSocket &from = *input.origin();
+  const MFOutputSocket &to = output;
+  const CPPType &base_type = from.data_type().vector_base_type();
+
+  Value *from_any_value = m_value_per_output_id[from.id()];
+  Value *to_any_value = m_value_per_output_id[to.id()];
+  BLI_assert(from_any_value != nullptr);
+  BLI_assert(base_type == to.data_type().vector_base_type());
+
+  if (to_any_value != nullptr) {
+    BLI_assert(to_any_value->type == ValueType::OutputVector);
+    GVectorArray &vector_array = *((OutputVectorValue *)to_any_value)->vector_array;
+    BLI_assert(vector_array.size() == 1);
+    GVArraySpan virtual_array_span = this->get_vector_input__single(input);
+    vector_array.extend(0, virtual_array_span[0]);
+    return vector_array;
+  }
+
+  if (from_any_value->type == ValueType::OwnVector) {
+    OwnVectorValue *value = (OwnVectorValue *)from_any_value;
+    if (value->max_remaining_users == 1) {
+      m_value_per_output_id[to.id()] = value;
+      m_value_per_output_id[from.id()] = nullptr;
+      value->max_remaining_users = to.targets().size();
+      return *value->vector_array;
+    }
+  }
+
+  GVArraySpan virtual_array_span = this->get_vector_input__single(input);
+
+  GVectorArray *new_vector_array = new GVectorArray(base_type, 1);
+  new_vector_array->extend(0, virtual_array_span[0]);
+
+  OwnVectorValue *new_value = m_allocator.construct<OwnVectorValue>(*new_vector_array,
+                                                                    to.targets().size());
+  m_value_per_output_id[to.id()] = new_value;
+  return *new_vector_array;
+}
+
+GVSpan MFNetworkEvaluationStorage::get_single_input__full(const MFInputSocket &socket)
+{
+  const MFOutputSocket &origin = *socket.origin();
+  Value *any_value = m_value_per_output_id[origin.id()];
+  BLI_assert(any_value != nullptr);
+
+  if (any_value->type == ValueType::OwnSingle) {
+    OwnSingleValue *value = (OwnSingleValue *)any_value;
+    if (value->is_single_allocated) {
+      return GVSpan::FromSingle(value->span.type(), value->span.buffer(), m_min_array_size);
+    }
+    else {
+      return value->span;
+    }
+  }
+  else if (any_value->type == ValueType::InputSingle) {
+    InputSingleValue *value = (InputSingleValue *)any_value;
+    return value->virtual_span;
+  }
+  else if (any_value->type == ValueType::OutputSingle) {
+    OutputSingleValue *value = (OutputSingleValue *)any_value;
+    BLI_assert(value->is_computed);
+    return value->span;
+  }
+
+  BLI_assert(false);
+  return GVSpan(CPPType::get<float>());
+}
+
+GVSpan MFNetworkEvaluationStorage::get_single_input__single(const MFInputSocket &socket)
+{
+  const MFOutputSocket &origin = *socket.origin();
+  Value *any_value = m_value_per_output_id[origin.id()];
+  BLI_assert(any_value != nullptr);
+
+  if (any_value->type == ValueType::OwnSingle) {
+    OwnSingleValue *value = (OwnSingleValue *)any_value;
+    BLI_assert(value->span.size() == 1);
+    return value->span;
+  }
+  else if (any_value->type == ValueType::InputSingle) {
+    InputSingleValue *value = (InputSingleValue *)any_value;
+    BLI_assert(value->virtual_span.is_single_element());
+    return value->virtual_span;
+  }
+  else if (any_value->type == ValueType::OutputSingle) {
+    OutputSingleValue *value = (OutputSingleValue *)any_value;
+    BLI_assert(value->is_computed);
+    BLI_assert(value->span.size() == 1);
+    return value->span;
+  }
+
+  BLI_assert(false);
+  return GVSpan(CPPType::get<float>());
+}
+
+GVArraySpan MFNetworkEvaluationStorage::get_vector_input__full(const MFInputSocket &socket)
+{
+  const MFOutputSocket &origin = *socket.origin();
+  Value *any_value = m_value_per_output_id[origin.id()];
+  BLI_assert(any_value != nullptr);
+
+  if (any_value->type == ValueType::OwnVector) {
+    OwnVectorValue *value = (OwnVectorValue *)any_value;
+    if (value->vector_array->size() == 1) {
+      GSpan span = (*value->vector_array)[0];
+      return GVArraySpan(span, m_min_array_size);
+    }
+    else {
+      return *value->vector_array;
+    }
+  }
+  else if (any_value->type == ValueType::InputVector) {
+    InputVectorValue *value = (InputVectorValue *)any_value;
+    return value->virtual_array_span;
+  }
+  else if (any_value->type == ValueType::OutputVector) {
+    OutputVectorValue *value = (OutputVectorValue *)any_value;
+    return *value->vector_array;
+  }
+
+  BLI_assert(false);
+  return GVArraySpan(CPPType::get<float>());
+}
+
+GVArraySpan MFNetworkEvaluationStorage::get_vector_input__single(const MFInputSocket &socket)
+{
+  const MFOutputSocket &origin = *socket.origin();
+  Value *any_value = m_value_per_output_id[origin.id()];
+  BLI_assert(any_value != nullptr);
+
+  if (any_value->type == ValueType::OwnVector) {
+    OwnVectorValue *value = (OwnVectorValue *)any_value;
+    BLI_assert(value->vector_array->size() == 1);
+    return *value->vector_array;
+  }
+  else if (any_value->type == ValueType::InputVector) {
+    InputVectorValue *value = (InputVectorValue *)any_value;
+    BLI_assert(value->virtual_array_span.is_single_array());
+    return value->virtual_array_span;
+  }
+  else if (any_value->type == ValueType::OutputVector) {
+    OutputVectorValue *value = (OutputVectorValue *)any_value;
+    BLI_assert(value->vector_array->size() == 1);
+    return *value->vector_array;
+  }
+
+  BLI_assert(false);
+  return GVArraySpan(CPPType::get<float>());
+}
+
+/** \} */
+
+}  // namespace fn
+}  // namespace blender