Geometry Nodes: initial scattering and geometry nodes

This is the initial merge from the geometry-nodes branch.
Nodes:
* Attribute Math
* Boolean
* Edge Split
* Float Compare
* Object Info
* Point Distribute
* Point Instance
* Random Attribute
* Random Float
* Subdivision Surface
* Transform
* Triangulate

It includes the initial evaluation of geometry node groups in the Geometry Nodes modifier.

Notes on the Generic attribute access API

The API adds an indirection for attribute access. That has the following benefits:
* Most code does not have to care about how an attribute is stored internally.
  This is mainly necessary, because we have to deal with "legacy" attributes
  such as vertex weights and attributes that are embedded into other structs
  such as vertex positions.
* When reading from an attribute, we generally don't care what domain the
  attribute is stored on. So we want to abstract away the interpolation that
  that adapts attributes from one domain to another domain (this is not
  actually implemented yet).

Other possible improvements for later iterations include:
* Actually implement interpolation between domains.
* Don't use inheritance for the different attribute types. A single class for read
  access and one for write access might be enough, because we know all the ways
  in which attributes are stored internally. We don't want more different internal
  structures in the future. On the contrary, ideally we can consolidate the different
  storage formats in the future to reduce the need for this indirection.
* Remove the need for heap allocations when creating attribute accessors.

It includes commits from:
* Dalai Felinto
* Hans Goudey
* Jacques Lucke
* Léo Depoix

7 files changed, 566 insertions, 70 deletions

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/math_functions.cc b/source/blender/nodes/intern/math_functions.cc
new file mode 100644
index 00000000000..cc5e9547a96
--- /dev/null
+++ b/source/blender/nodes/intern/math_functions.cc
@@ -0,0 +1,117 @@
+/*
+ * 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 "NOD_math_functions.hh"
+
+namespace blender::nodes {
+
+const FloatMathOperationInfo *get_float_math_operation_info(const int operation)
+{
+
+#define RETURN_OPERATION_INFO(title_case_name, shader_name) \
+  { \
+    static const FloatMathOperationInfo info{title_case_name, shader_name}; \
+    return &info; \
+  } \
+  ((void)0)
+
+  switch (operation) {
+    case NODE_MATH_ADD:
+      RETURN_OPERATION_INFO("Add", "math_add");
+    case NODE_MATH_SUBTRACT:
+      RETURN_OPERATION_INFO("Subtract", "math_subtract");
+    case NODE_MATH_MULTIPLY:
+      RETURN_OPERATION_INFO("Multiply", "math_multiply");
+    case NODE_MATH_DIVIDE:
+      RETURN_OPERATION_INFO("Divide", "math_divide");
+    case NODE_MATH_SINE:
+      RETURN_OPERATION_INFO("Sine", "math_sine");
+    case NODE_MATH_COSINE:
+      RETURN_OPERATION_INFO("Cosine", "math_cosine");
+    case NODE_MATH_ARCSINE:
+      RETURN_OPERATION_INFO("Arc Sine", "math_arcsine");
+    case NODE_MATH_ARCCOSINE:
+      RETURN_OPERATION_INFO("Arc Cosine", "math_arccosine");
+    case NODE_MATH_ARCTANGENT:
+      RETURN_OPERATION_INFO("Arc Tangent", "math_arctangent");
+    case NODE_MATH_POWER:
+      RETURN_OPERATION_INFO("Power", "math_power");
+    case NODE_MATH_LOGARITHM:
+      RETURN_OPERATION_INFO("Logarithm", "math_logarithm");
+    case NODE_MATH_MINIMUM:
+      RETURN_OPERATION_INFO("Minimum", "math_minimum");
+    case NODE_MATH_MAXIMUM:
+      RETURN_OPERATION_INFO("Maximum", "math_maximum");
+    case NODE_MATH_ROUND:
+      RETURN_OPERATION_INFO("Round", "math_round");
+    case NODE_MATH_LESS_THAN:
+      RETURN_OPERATION_INFO("Less Than", "math_less_than");
+    case NODE_MATH_GREATER_THAN:
+      RETURN_OPERATION_INFO("Greater Than", "math_greater_than");
+    case NODE_MATH_MODULO:
+      RETURN_OPERATION_INFO("Modulo", "math_modulo");
+    case NODE_MATH_ABSOLUTE:
+      RETURN_OPERATION_INFO("Absolute", "math_absolute");
+    case NODE_MATH_ARCTAN2:
+      RETURN_OPERATION_INFO("Arc Tangent 2", "math_arctan2");
+    case NODE_MATH_FLOOR:
+      RETURN_OPERATION_INFO("Floor", "math_floor");
+    case NODE_MATH_CEIL:
+      RETURN_OPERATION_INFO("Ceil", "math_ceil");
+    case NODE_MATH_FRACTION:
+      RETURN_OPERATION_INFO("Fraction", "math_fraction");
+    case NODE_MATH_SQRT:
+      RETURN_OPERATION_INFO("Sqrt", "math_sqrt");
+    case NODE_MATH_INV_SQRT:
+      RETURN_OPERATION_INFO("Inverse Sqrt", "math_inversesqrt");
+    case NODE_MATH_SIGN:
+      RETURN_OPERATION_INFO("Sign", "math_sign");
+    case NODE_MATH_EXPONENT:
+      RETURN_OPERATION_INFO("Exponent", "math_exponent");
+    case NODE_MATH_RADIANS:
+      RETURN_OPERATION_INFO("Radians", "math_radians");
+    case NODE_MATH_DEGREES:
+      RETURN_OPERATION_INFO("Degrees", "math_degrees");
+    case NODE_MATH_SINH:
+      RETURN_OPERATION_INFO("Hyperbolic Sine", "math_sinh");
+    case NODE_MATH_COSH:
+      RETURN_OPERATION_INFO("Hyperbolic Cosine", "math_cosh");
+    case NODE_MATH_TANH:
+      RETURN_OPERATION_INFO("Hyperbolic Tangent", "math_tanh");
+    case NODE_MATH_TRUNC:
+      RETURN_OPERATION_INFO("Truncate", "math_trunc");
+    case NODE_MATH_SNAP:
+      RETURN_OPERATION_INFO("Snap", "math_snap");
+    case NODE_MATH_WRAP:
+      RETURN_OPERATION_INFO("Wrap", "math_wrap");
+    case NODE_MATH_COMPARE:
+      RETURN_OPERATION_INFO("Compare", "math_compare");
+    case NODE_MATH_MULTIPLY_ADD:
+      RETURN_OPERATION_INFO("Multiply Add", "math_multiply_add");
+    case NODE_MATH_PINGPONG:
+      RETURN_OPERATION_INFO("Ping Pong", "math_pingpong");
+    case NODE_MATH_SMOOTH_MIN:
+      RETURN_OPERATION_INFO("Smooth Min", "math_smoothmin");
+    case NODE_MATH_SMOOTH_MAX:
+      RETURN_OPERATION_INFO("Smooth Max", "math_smoothmax");
+  }
+
+#undef RETURN_OPERATION_INFO
+
+  return nullptr;
+}
+
+}  // namespace blender::nodes
diff --git a/source/blender/nodes/intern/node_geometry_exec.cc b/source/blender/nodes/intern/node_geometry_exec.cc
new file mode 100644
index 00000000000..50292cb8cfb
--- /dev/null
+++ b/source/blender/nodes/intern/node_geometry_exec.cc
@@ -0,0 +1,103 @@
+/*
+ * 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 "NOD_geometry_exec.hh"
+#include "NOD_type_callbacks.hh"
+
+namespace blender::nodes {
+
+void GeoNodeExecParams::check_extract_input(StringRef identifier,
+                                            const CPPType *requested_type) const
+{
+  bNodeSocket *found_socket = nullptr;
+  LISTBASE_FOREACH (bNodeSocket *, socket, &node_.inputs) {
+    if (identifier == socket->identifier) {
+      found_socket = socket;
+      break;
+    }
+  }
+  if (found_socket == nullptr) {
+    std::cout << "Did not find an input socket with the identifier '" << identifier << "'.\n";
+    std::cout << "Possible identifiers are: ";
+    LISTBASE_FOREACH (bNodeSocket *, socket, &node_.inputs) {
+      if ((socket->flag & SOCK_UNAVAIL) == 0) {
+        std::cout << "'" << socket->identifier << "', ";
+      }
+    }
+    std::cout << "\n";
+    BLI_assert(false);
+  }
+  else if (found_socket->flag & SOCK_UNAVAIL) {
+    std::cout << "The socket corresponding to the identifier '" << identifier
+              << "' is disabled.\n";
+    BLI_assert(false);
+  }
+  else if (!input_values_.contains(identifier)) {
+    std::cout << "The identifier '" << identifier
+              << "' is valid, but there is no value for it anymore.\n";
+    std::cout << "Most likely it has been extracted before.\n";
+    BLI_assert(false);
+  }
+  else if (requested_type != nullptr) {
+    const CPPType &expected_type = *socket_cpp_type_get(*found_socket->typeinfo);
+    if (*requested_type != expected_type) {
+      std::cout << "The requested type '" << requested_type->name() << "' is incorrect. Expected '"
+                << expected_type.name() << "'.\n";
+      BLI_assert(false);
+    }
+  }
+}
+
+void GeoNodeExecParams::check_set_output(StringRef identifier, const CPPType &value_type) const
+{
+  bNodeSocket *found_socket = nullptr;
+  LISTBASE_FOREACH (bNodeSocket *, socket, &node_.outputs) {
+    if (identifier == socket->identifier) {
+      found_socket = socket;
+      break;
+    }
+  }
+  if (found_socket == nullptr) {
+    std::cout << "Did not find an output socket with the identifier '" << identifier << "'.\n";
+    std::cout << "Possible identifiers are: ";
+    LISTBASE_FOREACH (bNodeSocket *, socket, &node_.outputs) {
+      if ((socket->flag & SOCK_UNAVAIL) == 0) {
+        std::cout << "'" << socket->identifier << "', ";
+      }
+    }
+    std::cout << "\n";
+    BLI_assert(false);
+  }
+  else if (found_socket->flag & SOCK_UNAVAIL) {
+    std::cout << "The socket corresponding to the identifier '" << identifier
+              << "' is disabled.\n";
+    BLI_assert(false);
+  }
+  else if (output_values_.contains(identifier)) {
+    std::cout << "The identifier '" << identifier << "' has been set already.\n";
+    BLI_assert(false);
+  }
+  else {
+    const CPPType &expected_type = *socket_cpp_type_get(*found_socket->typeinfo);
+    if (value_type != expected_type) {
+      std::cout << "The value type '" << value_type.name() << "' is incorrect. Expected '"
+                << expected_type.name() << "'.\n";
+      BLI_assert(false);
+    }
+  }
+}
+
+}  // namespace blender::nodes
diff --git a/source/blender/nodes/intern/node_socket.cc b/source/blender/nodes/intern/node_socket.cc
index b3803b20ac1..d4b1df2f3f0 100644
--- a/source/blender/nodes/intern/node_socket.cc
+++ b/source/blender/nodes/intern/node_socket.cc
@@ -32,6 +32,7 @@
 #include "BLI_string.h"
 #include "BLI_utildefines.h"
 
+#include "BKE_geometry_set.hh"
 #include "BKE_lib_id.h"
 #include "BKE_node.h"
 #include "BKE_persistent_data_handle.hh"
@@ -552,10 +553,9 @@ static bNodeSocketType *make_socket_type_virtual()
 static bNodeSocketType *make_socket_type_bool()
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_BOOLEAN, PROP_NONE);
-  socktype->get_mf_data_type = []() { return blender::fn::MFDataType::ForSingle<bool>(); };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    bool value = builder.socket_default_value<bNodeSocketValueBoolean>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<bool>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    *(bool *)r_value = ((bNodeSocketValueBoolean *)socket.default_value)->value;
   };
   return socktype;
 }
@@ -563,10 +563,9 @@ static bNodeSocketType *make_socket_type_bool()
 static bNodeSocketType *make_socket_type_float(PropertySubType subtype)
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_FLOAT, subtype);
-  socktype->get_mf_data_type = []() { return blender::fn::MFDataType::ForSingle<float>(); };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    float value = builder.socket_default_value<bNodeSocketValueFloat>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<float>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    *(float *)r_value = ((bNodeSocketValueFloat *)socket.default_value)->value;
   };
   return socktype;
 }
@@ -574,10 +573,9 @@ static bNodeSocketType *make_socket_type_float(PropertySubType subtype)
 static bNodeSocketType *make_socket_type_int(PropertySubType subtype)
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_INT, subtype);
-  socktype->get_mf_data_type = []() { return blender::fn::MFDataType::ForSingle<int>(); };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    int value = builder.socket_default_value<bNodeSocketValueInt>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<int>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    *(int *)r_value = ((bNodeSocketValueInt *)socket.default_value)->value;
   };
   return socktype;
 }
@@ -585,12 +583,9 @@ static bNodeSocketType *make_socket_type_int(PropertySubType subtype)
 static bNodeSocketType *make_socket_type_vector(PropertySubType subtype)
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_VECTOR, subtype);
-  socktype->get_mf_data_type = []() {
-    return blender::fn::MFDataType::ForSingle<blender::float3>();
-  };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    blender::float3 value = builder.socket_default_value<bNodeSocketValueVector>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<blender::float3>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    *(blender::float3 *)r_value = ((bNodeSocketValueVector *)socket.default_value)->value;
   };
   return socktype;
 }
@@ -598,12 +593,9 @@ static bNodeSocketType *make_socket_type_vector(PropertySubType subtype)
 static bNodeSocketType *make_socket_type_rgba()
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_RGBA, PROP_NONE);
-  socktype->get_mf_data_type = []() {
-    return blender::fn::MFDataType::ForSingle<blender::Color4f>();
-  };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    blender::Color4f value = builder.socket_default_value<bNodeSocketValueRGBA>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<blender::Color4f>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    *(blender::Color4f *)r_value = ((bNodeSocketValueRGBA *)socket.default_value)->value;
   };
   return socktype;
 }
@@ -611,10 +603,9 @@ static bNodeSocketType *make_socket_type_rgba()
 static bNodeSocketType *make_socket_type_string()
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_STRING, PROP_NONE);
-  socktype->get_mf_data_type = []() { return blender::fn::MFDataType::ForSingle<std::string>(); };
-  socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
-    std::string value = builder.socket_default_value<bNodeSocketValueString>()->value;
-    builder.set_constant_value(value);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<std::string>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &socket, void *r_value) {
+    new (r_value) std::string(((bNodeSocketValueString *)socket.default_value)->value);
   };
   return socktype;
 }
@@ -661,9 +652,9 @@ MAKE_CPP_TYPE(PersistentObjectHandle, blender::bke::PersistentObjectHandle);
 static bNodeSocketType *make_socket_type_object()
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_OBJECT, PROP_NONE);
-  socktype->get_mf_data_type = []() {
+  socktype->get_cpp_type = []() {
     /* Objects are not passed along as raw pointers, but as handles. */
-    return blender::fn::MFDataType::ForSingle<blender::bke::PersistentObjectHandle>();
+    return &blender::fn::CPPType::get<blender::bke::PersistentObjectHandle>();
   };
   socktype->expand_in_mf_network = [](blender::nodes::SocketMFNetworkBuilder &builder) {
     Object *object = builder.socket_default_value<bNodeSocketValueObject>()->value;
@@ -675,6 +666,10 @@ static bNodeSocketType *make_socket_type_object()
 static bNodeSocketType *make_socket_type_geometry()
 {
   bNodeSocketType *socktype = make_standard_socket_type(SOCK_GEOMETRY, PROP_NONE);
+  socktype->get_cpp_type = []() { return &blender::fn::CPPType::get<GeometrySet>(); };
+  socktype->get_cpp_value = [](const bNodeSocket &UNUSED(socket), void *r_value) {
+    new (r_value) GeometrySet();
+  };
   return socktype;
 }
 
diff --git a/source/blender/nodes/intern/node_tree_multi_function.cc b/source/blender/nodes/intern/node_tree_multi_function.cc
index 09a80fd23f4..8440e996651 100644
--- a/source/blender/nodes/intern/node_tree_multi_function.cc
+++ b/source/blender/nodes/intern/node_tree_multi_function.cc
@@ -16,21 +16,13 @@
 
 #include "NOD_node_tree_multi_function.hh"
 
+#include "FN_multi_function_network_evaluation.hh"
+
 #include "BLI_color.hh"
 #include "BLI_float3.hh"
 
 namespace blender::nodes {
 
-/* Maybe this should be moved to BKE_node.h. */
-static std::optional<fn::MFDataType> try_get_multi_function_data_type_of_socket(
-    const bNodeSocket *bsocket)
-{
-  if (bsocket->typeinfo->get_mf_data_type == nullptr) {
-    return {};
-  }
-  return bsocket->typeinfo->get_mf_data_type();
-}
-
 const fn::MultiFunction &NodeMFNetworkBuilder::get_default_fn(StringRef name)
 {
   Vector<fn::MFDataType, 10> input_types;
@@ -38,8 +30,7 @@ const fn::MultiFunction &NodeMFNetworkBuilder::get_default_fn(StringRef name)
 
   for (const DInputSocket *dsocket : dnode_.inputs()) {
     if (dsocket->is_available()) {
-      std::optional<fn::MFDataType> data_type = try_get_multi_function_data_type_of_socket(
-          dsocket->bsocket());
+      std::optional<fn::MFDataType> data_type = socket_mf_type_get(*dsocket->bsocket()->typeinfo);
       if (data_type.has_value()) {
         input_types.append(*data_type);
       }
@@ -47,8 +38,7 @@ const fn::MultiFunction &NodeMFNetworkBuilder::get_default_fn(StringRef name)
   }
   for (const DOutputSocket *dsocket : dnode_.outputs()) {
     if (dsocket->is_available()) {
-      std::optional<fn::MFDataType> data_type = try_get_multi_function_data_type_of_socket(
-          dsocket->bsocket());
+      std::optional<fn::MFDataType> data_type = socket_mf_type_get(*dsocket->bsocket()->typeinfo);
       if (data_type.has_value()) {
         output_types.append(*data_type);
       }
@@ -70,8 +60,7 @@ static void insert_dummy_node(CommonMFNetworkBuilderData &common, const DNode &d
 
   for (const DInputSocket *dsocket : dnode.inputs()) {
     if (dsocket->is_available()) {
-      std::optional<fn::MFDataType> data_type = try_get_multi_function_data_type_of_socket(
-          dsocket->bsocket());
+      std::optional<fn::MFDataType> data_type = socket_mf_type_get(*dsocket->bsocket()->typeinfo);
       if (data_type.has_value()) {
         input_types.append(*data_type);
         input_names.append(dsocket->name());
@@ -86,8 +75,7 @@ static void insert_dummy_node(CommonMFNetworkBuilderData &common, const DNode &d
 
   for (const DOutputSocket *dsocket : dnode.outputs()) {
     if (dsocket->is_available()) {
-      std::optional<fn::MFDataType> data_type = try_get_multi_function_data_type_of_socket(
-          dsocket->bsocket());
+      std::optional<fn::MFDataType> data_type = socket_mf_type_get(*dsocket->bsocket()->typeinfo);
       if (data_type.has_value()) {
         output_types.append(*data_type);
         output_names.append(dsocket->name());
@@ -106,12 +94,12 @@ static void insert_dummy_node(CommonMFNetworkBuilderData &common, const DNode &d
 static bool has_data_sockets(const DNode &dnode)
 {
   for (const DInputSocket *socket : dnode.inputs()) {
-    if (is_multi_function_data_socket(socket->bsocket())) {
+    if (socket_is_mf_data_socket(*socket->bsocket()->typeinfo)) {
       return true;
     }
   }
   for (const DOutputSocket *socket : dnode.outputs()) {
-    if (is_multi_function_data_socket(socket->bsocket())) {
+    if (socket_is_mf_data_socket(*socket->bsocket()->typeinfo)) {
       return true;
     }
   }
@@ -140,7 +128,7 @@ static void insert_group_inputs(CommonMFNetworkBuilderData &common)
 {
   for (const DGroupInput *group_input : common.tree.group_inputs()) {
     bNodeSocket *bsocket = group_input->bsocket();
-    if (is_multi_function_data_socket(bsocket)) {
+    if (socket_is_mf_data_socket(*bsocket->typeinfo)) {
       bNodeSocketType *socktype = bsocket->typeinfo;
       BLI_assert(socktype->expand_in_mf_network != nullptr);
 
@@ -171,44 +159,43 @@ static fn::MFOutputSocket *try_find_origin(CommonMFNetworkBuilderData &common,
     if (!from_dsocket.is_available()) {
       return nullptr;
     }
-    if (is_multi_function_data_socket(from_dsocket.bsocket())) {
+    if (socket_is_mf_data_socket(*from_dsocket.bsocket()->typeinfo)) {
       return &common.network_map.lookup(from_dsocket);
     }
     return nullptr;
   }
 
   const DGroupInput &from_group_input = *from_group_inputs[0];
-  if (is_multi_function_data_socket(from_group_input.bsocket())) {
+  if (socket_is_mf_data_socket(*from_group_input.bsocket()->typeinfo)) {
     return &common.network_map.lookup(from_group_input);
   }
   return nullptr;
 }
 
-using ImplicitConversionsMap =
-    Map<std::pair<fn::MFDataType, fn::MFDataType>, const fn::MultiFunction *>;
-
 template<typename From, typename To>
-static void add_implicit_conversion(ImplicitConversionsMap &map)
+static void add_implicit_conversion(DataTypeConversions &conversions)
 {
   static fn::CustomMF_Convert<From, To> function;
-  map.add({fn::MFDataType::ForSingle<From>(), fn::MFDataType::ForSingle<To>()}, &function);
+  conversions.add(fn::MFDataType::ForSingle<From>(), fn::MFDataType::ForSingle<To>(), function);
 }
 
 template<typename From, typename To, typename ConversionF>
-static void add_implicit_conversion(ImplicitConversionsMap &map,
+static void add_implicit_conversion(DataTypeConversions &conversions,
                                     StringRef name,
                                     ConversionF conversion)
 {
   static fn::CustomMF_SI_SO<From, To> function{name, conversion};
-  map.add({fn::MFDataType::ForSingle<From>(), fn::MFDataType::ForSingle<To>()}, &function);
+  conversions.add(fn::MFDataType::ForSingle<From>(), fn::MFDataType::ForSingle<To>(), function);
 }
 
-static ImplicitConversionsMap get_implicit_conversions()
+static DataTypeConversions create_implicit_conversions()
 {
-  ImplicitConversionsMap conversions;
+  DataTypeConversions conversions;
   add_implicit_conversion<float, int32_t>(conversions);
   add_implicit_conversion<float, float3>(conversions);
   add_implicit_conversion<int32_t, float>(conversions);
+  add_implicit_conversion<float, bool>(conversions);
+  add_implicit_conversion<bool, float>(conversions);
   add_implicit_conversion<float3, float>(
       conversions, "Vector Length", [](float3 a) { return a.length(); });
   add_implicit_conversion<int32_t, float3>(
@@ -220,11 +207,26 @@ static ImplicitConversionsMap get_implicit_conversions()
   return conversions;
 }
 
-static const fn::MultiFunction *try_get_conversion_function(fn::MFDataType from, fn::MFDataType to)
+const DataTypeConversions &get_implicit_type_conversions()
 {
-  static const ImplicitConversionsMap conversions = get_implicit_conversions();
-  const fn::MultiFunction *function = conversions.lookup_default({from, to}, nullptr);
-  return function;
+  static const DataTypeConversions conversions = create_implicit_conversions();
+  return conversions;
+}
+
+void DataTypeConversions::convert(const CPPType &from_type,
+                                  const CPPType &to_type,
+                                  const void *from_value,
+                                  void *to_value) const
+{
+  const fn::MultiFunction *fn = this->get_conversion(MFDataType::ForSingle(from_type),
+                                                     MFDataType::ForSingle(to_type));
+  BLI_assert(fn != nullptr);
+
+  fn::MFContextBuilder context;
+  fn::MFParamsBuilder params{*fn, 1};
+  params.add_readonly_single_input(fn::GSpan(from_type, from_value, 1));
+  params.add_uninitialized_single_output(fn::GMutableSpan(to_type, to_value, 1));
+  fn->call({0}, params, context);
 }
 
 static fn::MFOutputSocket &insert_default_value_for_type(CommonMFNetworkBuilderData &common,
@@ -253,7 +255,7 @@ static void insert_links(CommonMFNetworkBuilderData &common)
     if (!to_dsocket->is_linked()) {
       continue;
     }
-    if (!is_multi_function_data_socket(to_dsocket->bsocket())) {
+    if (!socket_is_mf_data_socket(*to_dsocket->bsocket()->typeinfo)) {
       continue;
     }
 
@@ -269,7 +271,8 @@ static void insert_links(CommonMFNetworkBuilderData &common)
     fn::MFDataType from_type = from_socket->data_type();
 
     if (from_type != to_type) {
-      const fn::MultiFunction *conversion_fn = try_get_conversion_function(from_type, to_type);
+      const fn::MultiFunction *conversion_fn = get_implicit_type_conversions().get_conversion(
+          from_type, to_type);
       if (conversion_fn != nullptr) {
         fn::MFNode &node = common.network.add_function(*conversion_fn);
         common.network.add_link(*from_socket, node.input(0));
@@ -308,7 +311,7 @@ static void insert_unlinked_inputs(CommonMFNetworkBuilderData &common)
   Vector<const DInputSocket *> unlinked_data_inputs;
   for (const DInputSocket *dsocket : common.tree.input_sockets()) {
     if (dsocket->is_available()) {
-      if (is_multi_function_data_socket(dsocket->bsocket())) {
+      if (socket_is_mf_data_socket(*dsocket->bsocket()->typeinfo)) {
         if (!dsocket->is_linked()) {
           insert_unlinked_input(common, *dsocket);
         }
@@ -340,4 +343,150 @@ MFNetworkTreeMap insert_node_tree_into_mf_network(fn::MFNetwork &network,
   return network_map;
 }
 
+/**
+ * A single node is allowed to expand into multiple nodes before evaluation. Depending on what
+ * nodes it expands to, it belongs a different type of the ones below.
+ */
+enum class NodeExpandType {
+  SingleFunctionNode,
+  MultipleFunctionNodes,
+  HasDummyNodes,
+};
+
+/**
+ * Checks how the given node expanded in the multi-function network. If it is only a single
+ * function node, the corresponding function is returned as well.
+ */
+static NodeExpandType get_node_expand_type(MFNetworkTreeMap &network_map,
+                                           const DNode &dnode,
+                                           const fn::MultiFunction **r_single_function)
+{
+  const fn::MFFunctionNode *single_function_node = nullptr;
+  bool has_multiple_nodes = false;
+  bool has_dummy_nodes = false;
+
+  auto check_mf_node = [&](fn::MFNode &mf_node) {
+    if (mf_node.is_function()) {
+      if (single_function_node == nullptr) {
+        single_function_node = &mf_node.as_function();
+      }
+      if (&mf_node != single_function_node) {
+        has_multiple_nodes = true;
+      }
+    }
+    else {
+      BLI_assert(mf_node.is_dummy());
+      has_dummy_nodes = true;
+    }
+  };
+
+  for (const DInputSocket *dsocket : dnode.inputs()) {
+    if (dsocket->is_available()) {
+      for (fn::MFInputSocket *mf_input : network_map.lookup(*dsocket)) {
+        check_mf_node(mf_input->node());
+      }
+    }
+  }
+  for (const DOutputSocket *dsocket : dnode.outputs()) {
+    if (dsocket->is_available()) {
+      fn::MFOutputSocket &mf_output = network_map.lookup(*dsocket);
+      check_mf_node(mf_output.node());
+    }
+  }
+
+  if (has_dummy_nodes) {
+    return NodeExpandType::HasDummyNodes;
+  }
+  if (has_multiple_nodes) {
+    return NodeExpandType::MultipleFunctionNodes;
+  }
+  *r_single_function = &single_function_node->function();
+  return NodeExpandType::SingleFunctionNode;
+}
+
+static const fn::MultiFunction &create_function_for_node_that_expands_into_multiple(
+    const DNode &dnode,
+    fn::MFNetwork &network,
+    MFNetworkTreeMap &network_map,
+    ResourceCollector &resources)
+{
+  Vector<const fn::MFOutputSocket *> dummy_fn_inputs;
+  for (const DInputSocket *dsocket : dnode.inputs()) {
+    if (dsocket->is_available()) {
+      MFDataType data_type = *socket_mf_type_get(*dsocket->typeinfo());
+      fn::MFOutputSocket &fn_input = network.add_input(data_type.to_string(), data_type);
+      for (fn::MFInputSocket *mf_input : network_map.lookup(*dsocket)) {
+        network.add_link(fn_input, *mf_input);
+        dummy_fn_inputs.append(&fn_input);
+      }
+    }
+  }
+  Vector<const fn::MFInputSocket *> dummy_fn_outputs;
+  for (const DOutputSocket *dsocket : dnode.outputs()) {
+    if (dsocket->is_available()) {
+      fn::MFOutputSocket &mf_output = network_map.lookup(*dsocket);
+      MFDataType data_type = mf_output.data_type();
+      fn::MFInputSocket &fn_output = network.add_output(data_type.to_string(), data_type);
+      network.add_link(mf_output, fn_output);
+      dummy_fn_outputs.append(&fn_output);
+    }
+  }
+
+  fn::MFNetworkEvaluator &fn_evaluator = resources.construct<fn::MFNetworkEvaluator>(
+      __func__, std::move(dummy_fn_inputs), std::move(dummy_fn_outputs));
+  return fn_evaluator;
+}
+
+/**
+ * Returns a single multi-function for every node that supports it. This makes it easier to reuse
+ * the multi-function implementation of nodes in different contexts.
+ */
+MultiFunctionByNode get_multi_function_per_node(const DerivedNodeTree &tree,
+                                                ResourceCollector &resources)
+{
+  /* Build a network that nodes can insert themselves into. However, the individual nodes are not
+   * connected. */
+  fn::MFNetwork &network = resources.construct<fn::MFNetwork>(__func__);
+  MFNetworkTreeMap network_map{tree, network};
+  MultiFunctionByNode functions_by_node;
+
+  CommonMFNetworkBuilderData common{resources, network, network_map, tree};
+
+  for (const DNode *dnode : tree.nodes()) {
+    const bNodeType *node_type = dnode->typeinfo();
+    if (node_type->expand_in_mf_network == nullptr) {
+      /* This node does not have a multi-function implementation. */
+      continue;
+    }
+
+    NodeMFNetworkBuilder builder{common, *dnode};
+    node_type->expand_in_mf_network(builder);
+
+    const fn::MultiFunction *single_function = nullptr;
+    const NodeExpandType expand_type = get_node_expand_type(network_map, *dnode, &single_function);
+
+    switch (expand_type) {
+      case NodeExpandType::HasDummyNodes: {
+        /* Dummy nodes cannot be executed, so skip them. */
+        break;
+      }
+      case NodeExpandType::SingleFunctionNode: {
+        /* This is the common case. Most nodes just expand to a single function. */
+        functions_by_node.add_new(dnode, single_function);
+        break;
+      }
+      case NodeExpandType::MultipleFunctionNodes: {
+        /* If a node expanded into multiple functions, a new function has to be created that
+         * combines those. */
+        const fn::MultiFunction &fn = create_function_for_node_that_expands_into_multiple(
+            *dnode, network, network_map, resources);
+        functions_by_node.add_new(dnode, &fn);
+        break;
+      }
+    }
+  }
+
+  return functions_by_node;
+}
+
 }  // namespace blender::nodes
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;
diff --git a/source/blender/nodes/intern/type_callbacks.cc b/source/blender/nodes/intern/type_callbacks.cc
new file mode 100644
index 00000000000..1f207f880bc
--- /dev/null
+++ b/source/blender/nodes/intern/type_callbacks.cc
@@ -0,0 +1,76 @@
+/*
+ * 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 "NOD_node_tree_multi_function.hh"
+#include "NOD_type_callbacks.hh"
+
+namespace blender::nodes {
+
+const CPPType *socket_cpp_type_get(const bNodeSocketType &stype)
+{
+  if (stype.get_cpp_type != nullptr) {
+    return stype.get_cpp_type();
+  }
+  return nullptr;
+}
+
+std::optional<MFDataType> socket_mf_type_get(const bNodeSocketType &stype)
+{
+  const CPPType *cpp_type = socket_cpp_type_get(stype);
+  if (cpp_type != nullptr) {
+    return MFDataType::ForSingle(*cpp_type);
+  }
+  return {};
+}
+
+bool socket_is_mf_data_socket(const bNodeSocketType &stype)
+{
+  if (!socket_mf_type_get(stype).has_value()) {
+    return false;
+  }
+  if (stype.expand_in_mf_network == nullptr && stype.get_cpp_value == nullptr) {
+    return false;
+  }
+  return true;
+}
+
+bool socket_cpp_value_get(const bNodeSocket &socket, void *r_value)
+{
+  if (socket.typeinfo->get_cpp_value != nullptr) {
+    socket.typeinfo->get_cpp_value(socket, r_value);
+    return true;
+  }
+  return false;
+}
+
+void socket_expand_in_mf_network(SocketMFNetworkBuilder &builder)
+{
+  bNodeSocket &socket = builder.bsocket();
+  if (socket.typeinfo->expand_in_mf_network != nullptr) {
+    socket.typeinfo->expand_in_mf_network(builder);
+  }
+  else if (socket.typeinfo->get_cpp_value != nullptr) {
+    const CPPType &type = *socket_cpp_type_get(*socket.typeinfo);
+    void *buffer = builder.resources().linear_allocator().allocate(type.size(), type.alignment());
+    socket.typeinfo->get_cpp_value(socket, buffer);
+    builder.set_constant_value(type, buffer);
+  }
+  else {
+    BLI_assert(false);
+  }
+}
+
+}  // namespace blender::nodes