Functions: Multi Function

This adds the `MultiFunction` type and some smallish utility types that it uses.
A `MultiFunction` encapsulates a function that is optimized for throughput by
always processing many elements at once.

This is an important part of the new particle system, because it allows us to
execute user generated node trees for many particles efficiently.

Reviewers: brecht

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

source/blender/functions/CMakeLists.txt

@@ -29,8 +29,16 @@ set(INC_SYS
 set(SRC
   intern/cpp_types.cc
 
+  FN_array_spans.hh
   FN_cpp_type.hh
   FN_cpp_types.hh
+  FN_multi_function.hh
+  FN_multi_function_context.hh
+  FN_multi_function_data_type.hh
+  FN_multi_function_param_type.hh
+  FN_multi_function_params.hh
+  FN_multi_function_signature.hh
+  FN_spans.hh
 )
 
 set(LIB

source/blender/functions/FN_array_spans.hh

@@ -0,0 +1,220 @@
+/*
+ * 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_ARRAY_SPANS_HH__
+#define __FN_ARRAY_SPANS_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * An ArraySpan is a span where every element contains an array (instead of a single element as is
+ * the case in a normal span). It's main use case is to reference many small arrays.
+ */
+
+#include "FN_spans.hh"
+
+namespace blender {
+namespace fn {
+
+/**
+ * A virtual array span. Every element of this span contains a virtual span. So it behaves like a
+ * blender::Span, but might not be backed up by an actual array.
+ */
+template<typename T> class VArraySpan {
+ private:
+  /**
+   * Depending on the use case, the referenced data might have a different structure. More
+   * categories can be added when necessary.
+   */
+  enum Category {
+    SingleArray,
+    StartsAndSizes,
+  };
+
+  uint m_virtual_size;
+  Category m_category;
+
+  union {
+    struct {
+      const T *start;
+      uint size;
+    } single_array;
+    struct {
+      const T *const *starts;
+      const uint *sizes;
+    } starts_and_sizes;
+  } m_data;
+
+ public:
+  VArraySpan()
+  {
+    m_virtual_size = 0;
+    m_category = StartsAndSizes;
+    m_data.starts_and_sizes.starts = nullptr;
+    m_data.starts_and_sizes.sizes = nullptr;
+  }
+
+  VArraySpan(Span<T> span, uint virtual_size)
+  {
+    m_virtual_size = virtual_size;
+    m_category = SingleArray;
+    m_data.single_array.start = span.data();
+    m_data.single_array.size = span.size();
+  }
+
+  VArraySpan(Span<const T *> starts, Span<uint> sizes)
+  {
+    BLI_assert(starts.size() == sizes.size());
+    m_virtual_size = starts.size();
+    m_category = StartsAndSizes;
+    m_data.starts_and_sizes.starts = starts.begin();
+    m_data.starts_and_sizes.sizes = sizes.begin();
+  }
+
+  bool is_empty() const
+  {
+    return m_virtual_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_virtual_size;
+  }
+
+  VSpan<T> operator[](uint index) const
+  {
+    BLI_assert(index < m_virtual_size);
+    switch (m_category) {
+      case SingleArray:
+        return VSpan<T>(Span<T>(m_data.single_array.start, m_data.single_array.size));
+      case StartsAndSizes:
+        return VSpan<T>(
+            Span<T>(m_data.starts_and_sizes.starts[index], m_data.starts_and_sizes.sizes[index]));
+    }
+    BLI_assert(false);
+    return {};
+  }
+};
+
+/**
+ * A generic virtual array span. It's just like a VArraySpan, but the type is only known at
+ * run-time.
+ */
+class GVArraySpan {
+ private:
+  /**
+   * Depending on the use case, the referenced data might have a different structure. More
+   * categories can be added when necessary.
+   */
+  enum Category {
+    SingleArray,
+    StartsAndSizes,
+  };
+
+  const CPPType *m_type;
+  uint m_virtual_size;
+  Category m_category;
+
+  union {
+    struct {
+      const void *values;
+      uint size;
+    } single_array;
+    struct {
+      const void *const *starts;
+      const uint *sizes;
+    } starts_and_sizes;
+  } m_data;
+
+  GVArraySpan() = default;
+
+ public:
+  GVArraySpan(const CPPType &type)
+  {
+    m_type = &type;
+    m_virtual_size = 0;
+    m_category = StartsAndSizes;
+    m_data.starts_and_sizes.starts = nullptr;
+    m_data.starts_and_sizes.sizes = nullptr;
+  }
+
+  GVArraySpan(GSpan array, uint virtual_size)
+  {
+    m_type = &array.type();
+    m_virtual_size = virtual_size;
+    m_category = SingleArray;
+    m_data.single_array.values = array.buffer();
+    m_data.single_array.size = array.size();
+  }
+
+  GVArraySpan(const CPPType &type, Span<const void *> starts, Span<uint> sizes)
+  {
+    BLI_assert(starts.size() == sizes.size());
+    m_type = &type;
+    m_virtual_size = starts.size();
+    m_category = StartsAndSizes;
+    m_data.starts_and_sizes.starts = starts.begin();
+    m_data.starts_and_sizes.sizes = sizes.begin();
+  }
+
+  bool is_empty() const
+  {
+    return m_virtual_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_virtual_size;
+  }
+
+  const CPPType &type() const
+  {
+    return *m_type;
+  }
+
+  template<typename T> VArraySpan<T> typed() const
+  {
+    BLI_assert(CPPType::get<T>() == *m_type);
+    switch (m_category) {
+      case SingleArray:
+        return VArraySpan<T>(
+            Span<T>((const T *)m_data.single_array.values, m_data.single_array.size));
+      case StartsAndSizes:
+        return VArraySpan<T>(
+            Span<const T *>((const T *const *)m_data.starts_and_sizes.starts, m_virtual_size),
+            Span<uint>(m_data.starts_and_sizes.sizes, m_virtual_size));
+    }
+  }
+
+  GVSpan operator[](uint index) const
+  {
+    BLI_assert(index < m_virtual_size);
+    switch (m_category) {
+      case SingleArray:
+        return GVSpan(GSpan(*m_type, m_data.single_array.values, m_data.single_array.size));
+      case StartsAndSizes:
+        return GVSpan(GSpan(
+            *m_type, m_data.starts_and_sizes.starts[index], m_data.starts_and_sizes.sizes[index]));
+    }
+    BLI_assert(false);
+    return GVSpan(*m_type);
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_ARRAY_SPANS_HH__ */

source/blender/functions/FN_cpp_type.hh

@@ -71,11 +71,7 @@
 #include "BLI_string_ref.hh"
 
 namespace blender {
-namespace FN {
-
-using blender::IndexMask;
-using blender::StringRef;
-using blender::StringRefNull;
+namespace fn {
 
 class CPPType {
  public:
@@ -241,14 +237,14 @@ class CPPType {
 
   void construct_default_n(void *ptr, uint n) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(ptr));
+    BLI_assert(this->pointer_has_valid_alignment(ptr));
 
     m_construct_default_n(ptr, n);
   }
 
   void construct_default_indices(void *ptr, IndexMask index_mask) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(ptr));
+    BLI_assert(this->pointer_has_valid_alignment(ptr));
 
     m_construct_default_indices(ptr, index_mask);
   }
@@ -270,14 +266,14 @@ class CPPType {
 
   void destruct_n(void *ptr, uint n) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(ptr));
+    BLI_assert(this->pointer_has_valid_alignment(ptr));
 
     m_destruct_n(ptr, n);
   }
 
   void destruct_indices(void *ptr, IndexMask index_mask) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(ptr));
+    BLI_assert(this->pointer_has_valid_alignment(ptr));
 
     m_destruct_indices(ptr, index_mask);
   }
@@ -300,8 +296,8 @@ class CPPType {
   void copy_to_initialized_n(const void *src, void *dst, uint n) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_copy_to_initialized_n(src, dst, n);
   }
@@ -309,8 +305,8 @@ class CPPType {
   void copy_to_initialized_indices(const void *src, void *dst, IndexMask index_mask) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_copy_to_initialized_indices(src, dst, index_mask);
   }
@@ -335,8 +331,8 @@ class CPPType {
   void copy_to_uninitialized_n(const void *src, void *dst, uint n) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_copy_to_uninitialized_n(src, dst, n);
   }
@@ -344,8 +340,8 @@ class CPPType {
   void copy_to_uninitialized_indices(const void *src, void *dst, IndexMask index_mask) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_copy_to_uninitialized_indices(src, dst, index_mask);
   }
@@ -370,8 +366,8 @@ class CPPType {
   void relocate_to_initialized_n(void *src, void *dst, uint n) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_relocate_to_initialized_n(src, dst, n);
   }
@@ -379,8 +375,8 @@ class CPPType {
   void relocate_to_initialized_indices(void *src, void *dst, IndexMask index_mask) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_relocate_to_initialized_indices(src, dst, index_mask);
   }
@@ -405,8 +401,8 @@ class CPPType {
   void relocate_to_uninitialized_n(void *src, void *dst, uint n) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_relocate_to_uninitialized_n(src, dst, n);
   }
@@ -414,8 +410,8 @@ class CPPType {
   void relocate_to_uninitialized_indices(void *src, void *dst, IndexMask index_mask) const
   {
     BLI_assert(src != dst);
-    BLI_assert(this->pointer_can_point_to_instance(src));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(src));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_relocate_to_uninitialized_indices(src, dst, index_mask);
   }
@@ -435,8 +431,8 @@ class CPPType {
 
   void fill_initialized_indices(const void *value, void *dst, IndexMask index_mask) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(value));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(value));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_fill_initialized_indices(value, dst, index_mask);
   }
@@ -456,8 +452,8 @@ class CPPType {
 
   void fill_uninitialized_indices(const void *value, void *dst, IndexMask index_mask) const
   {
-    BLI_assert(this->pointer_can_point_to_instance(value));
-    BLI_assert(this->pointer_can_point_to_instance(dst));
+    BLI_assert(this->pointer_has_valid_alignment(value));
+    BLI_assert(this->pointer_has_valid_alignment(dst));
 
     m_fill_uninitialized_indices(value, dst, index_mask);
   }
@@ -719,15 +715,15 @@ static std::unique_ptr<const CPPType> create_cpp_type(StringRef name, const T &d
   return std::unique_ptr<const CPPType>(type);
 }
 
-}  // namespace FN
+}  // namespace fn
 }  // namespace blender
 
 #define MAKE_CPP_TYPE(IDENTIFIER, TYPE_NAME) \
   static TYPE_NAME default_value_##IDENTIFIER; \
-  static std::unique_ptr<const blender::FN::CPPType> CPPTYPE_##IDENTIFIER##_owner = \
-      blender::FN::create_cpp_type<TYPE_NAME>(STRINGIFY(IDENTIFIER), default_value_##IDENTIFIER); \
-  const blender::FN::CPPType &CPPType_##IDENTIFIER = *CPPTYPE_##IDENTIFIER##_owner; \
-  template<> const blender::FN::CPPType &blender::FN::CPPType::get<TYPE_NAME>() \
+  static std::unique_ptr<const blender::fn::CPPType> CPPTYPE_##IDENTIFIER##_owner = \
+      blender::fn::create_cpp_type<TYPE_NAME>(STRINGIFY(IDENTIFIER), default_value_##IDENTIFIER); \
+  const blender::fn::CPPType &CPPType_##IDENTIFIER = *CPPTYPE_##IDENTIFIER##_owner; \
+  template<> const blender::fn::CPPType &blender::fn::CPPType::get<TYPE_NAME>() \
   { \
     return CPPType_##IDENTIFIER; \
   }

source/blender/functions/FN_cpp_types.hh

@@ -27,7 +27,7 @@
 #include "FN_cpp_type.hh"
 
 namespace blender {
-namespace FN {
+namespace fn {
 
 extern const CPPType &CPPType_bool;
 
@@ -44,7 +44,7 @@ extern const CPPType &CPPType_Color4b;
 
 extern const CPPType &CPPType_string;
 
-}  // namespace FN
+}  // namespace fn
 }  // namespace blender
 
 #endif /* __FN_CPP_TYPES_HH__ */

source/blender/functions/FN_generic_vector_array.hh

@@ -0,0 +1,181 @@
+/*
+ * 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_GENERIC_VECTOR_ARRAY_HH__
+#define __FN_GENERIC_VECTOR_ARRAY_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * A `GVectorArray` is a container for a fixed amount of dynamically growing arrays with a generic
+ * type. Its main use case is to store many small vectors with few separate allocations. Using this
+ * structure is generally more efficient than allocating each small vector separately.
+ *
+ * `GVectorArrayRef<T>` is a typed reference to a GVectorArray and makes it easier and safer to
+ * work with the class when the type is known at compile time.
+ */
+
+#include "FN_array_spans.hh"
+#include "FN_cpp_type.hh"
+
+#include "BLI_array.hh"
+#include "BLI_linear_allocator.hh"
+#include "BLI_utility_mixins.hh"
+
+namespace blender {
+namespace fn {
+
+template<typename T> class GVectorArrayRef;
+
+class GVectorArray : NonCopyable, NonMovable {
+ private:
+  const CPPType &m_type;
+  uint m_element_size;
+  Array<void *, 1> m_starts;
+  Array<uint, 1> m_lengths;
+  Array<uint, 1> m_capacities;
+  LinearAllocator<> m_allocator;
+
+  template<typename T> friend class GVectorArrayRef;
+
+ public:
+  GVectorArray() = delete;
+
+  GVectorArray(const CPPType &type, uint array_size)
+      : m_type(type),
+        m_element_size(type.size()),
+        m_starts(array_size),
+        m_lengths(array_size),
+        m_capacities(array_size)
+  {
+    m_starts.fill(nullptr);
+    m_lengths.fill(0);
+    m_capacities.fill(0);
+  }
+
+  ~GVectorArray()
+  {
+    if (m_type.is_trivially_destructible()) {
+      return;
+    }
+
+    for (uint i : m_starts.index_range()) {
+      m_type.destruct_n(m_starts[i], m_lengths[i]);
+    }
+  }
+
+  operator GVArraySpan() const
+  {
+    return GVArraySpan(m_type, m_starts.as_span(), m_lengths);
+  }
+
+  bool is_empty() const
+  {
+    return m_starts.size() == 0;
+  }
+
+  uint size() const
+  {
+    return m_starts.size();
+  }
+
+  const CPPType &type() const
+  {
+    return m_type;
+  }
+
+  Span<const void *> starts() const
+  {
+    return m_starts.as_span();
+  }
+
+  Span<uint> lengths() const
+  {
+    return m_lengths;
+  }
+
+  void append(uint index, const void *src)
+  {
+    uint old_length = m_lengths[index];
+    if (old_length == m_capacities[index]) {
+      this->grow_at_least_one(index);
+    }
+
+    void *dst = POINTER_OFFSET(m_starts[index], m_element_size * old_length);
+    m_type.copy_to_uninitialized(src, dst);
+    m_lengths[index]++;
+  }
+
+  GMutableSpan operator[](uint index)
+  {
+    BLI_assert(index < m_starts.size());
+    return GMutableSpan(m_type, m_starts[index], m_lengths[index]);
+  }
+  template<typename T> GVectorArrayRef<T> typed()
+  {
+    return GVectorArrayRef<T>(*this);
+  }
+
+ private:
+  void grow_at_least_one(uint index)
+  {
+    BLI_assert(m_lengths[index] == m_capacities[index]);
+    uint new_capacity = m_lengths[index] * 2 + 1;
+
+    void *new_buffer = m_allocator.allocate(m_element_size * new_capacity, m_type.alignment());
+    m_type.relocate_to_uninitialized_n(m_starts[index], new_buffer, m_lengths[index]);
+
+    m_starts[index] = new_buffer;
+    m_capacities[index] = new_capacity;
+  }
+};
+
+template<typename T> class GVectorArrayRef {
+ private:
+  GVectorArray *m_vector_array;
+
+ public:
+  GVectorArrayRef(GVectorArray &vector_array) : m_vector_array(&vector_array)
+  {
+    BLI_assert(vector_array.m_type == CPPType::get<T>());
+  }
+
+  void append(uint index, const T &value)
+  {
+    m_vector_array->append(index, &value);
+  }
+
+  MutableSpan<T> operator[](uint index)
+  {
+    BLI_assert(index < m_vector_array->m_starts.size());
+    return MutableSpan<T>((T *)m_vector_array->m_starts[index], m_vector_array->m_lengths[index]);
+  }
+
+  uint size() const
+  {
+    return m_vector_array->size();
+  }
+
+  bool is_empty() const
+  {
+    return m_vector_array->is_empty();
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_GENERIC_VECTOR_ARRAY_HH__ */

source/blender/functions/FN_multi_function.hh

@@ -0,0 +1,106 @@
+/*
+ * 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_HH__
+#define __FN_MULTI_FUNCTION_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * A `MultiFunction` encapsulates a function that is optimized for throughput (instead of latency).
+ * The throughput is optimized by always processing many elements at once, instead of each element
+ * separately. This is ideal for functions that are evaluated often (e.g. for every particle).
+ *
+ * By processing a lot of data at once, individual functions become easier to optimize for humans
+ * and for the compiler. Furthermore, performance profiles become easier to understand and show
+ * better where bottlenecks are.
+ *
+ * Every multi-function has a name and an ordered list of parameters. Parameters are used for input
+ * and output. In fact, there are three kinds of parameters: inputs, outputs and mutable (which is
+ * combination of input and output).
+ *
+ * To call a multi-function, one has to provide three things:
+ * - `MFParams`: This references the input and output arrays that the function works with. The
+ *      arrays are not owned by MFParams.
+ * - `IndexMask`: An array of indices indicating which indices in the provided arrays should be
+ *      touched/processed.
+ * - `MFContext`: Further information for the called function.
+ *
+ * A new multi-function is generally implemented as follows:
+ * 1. Create a new subclass of MultiFunction.
+ * 2. Implement a constructor that initialized the signature of the function.
+ * 3. Override the `call` function.
+ */
+
+#include "FN_multi_function_context.hh"
+#include "FN_multi_function_params.hh"
+
+namespace blender {
+namespace fn {
+
+class MultiFunction {
+ private:
+  MFSignature m_signature;
+
+ public:
+  virtual ~MultiFunction()
+  {
+  }
+
+  virtual void call(IndexMask mask, MFParams params, MFContext context) const = 0;
+
+  IndexRange param_indices() const
+  {
+    return m_signature.param_types.index_range();
+  }
+
+  MFParamType param_type(uint param_index) const
+  {
+    return m_signature.param_types[param_index];
+  }
+
+  StringRefNull param_name(uint param_index) const
+  {
+    return m_signature.param_names[param_index];
+  }
+
+  StringRefNull name() const
+  {
+    return m_signature.function_name;
+  }
+
+  const MFSignature &signature() const
+  {
+    return m_signature;
+  }
+
+ protected:
+  MFSignatureBuilder get_builder(StringRef function_name)
+  {
+    m_signature.function_name = function_name;
+    return MFSignatureBuilder(m_signature);
+  }
+};
+
+inline MFParamsBuilder::MFParamsBuilder(const class MultiFunction &fn, uint min_array_size)
+    : MFParamsBuilder(fn.signature(), min_array_size)
+{
+}
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_HH__ */

source/blender/functions/FN_multi_function_context.hh

@@ -0,0 +1,49 @@
+/*
+ * 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_CONTEXT_HH__
+#define __FN_MULTI_FUNCTION_CONTEXT_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * An MFContext is passed along with every call to a multi-function. Right now it does nothing, but
+ * it can be used for the following purposes:
+ * - Pass debug information up and down the function call stack.
+ * - Pass reusable memory buffers to subfunctions to increase performance.
+ * - Pass cached data to called functions.
+ */
+
+namespace blender {
+namespace fn {
+
+class MFContextBuilder {
+};
+
+class MFContext {
+ private:
+  MFContextBuilder *m_builder;
+
+ public:
+  MFContext(MFContextBuilder &builder) : m_builder(&builder)
+  {
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_CONTEXT_HH__ */

source/blender/functions/FN_multi_function_data_type.hh

@@ -0,0 +1,125 @@
+/*
+ * 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_DATA_TYPE_HH__
+#define __FN_MULTI_FUNCTION_DATA_TYPE_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * A MFDataType describes what type of data a multi-function gets as input, outputs or mutates.
+ * Currently, only individual elements or vectors of elements are supported. Adding more data types
+ * is possible when necessary.
+ */
+
+#include "FN_cpp_type.hh"
+
+namespace blender {
+namespace fn {
+
+class MFDataType {
+ public:
+  enum Category {
+    Single,
+    Vector,
+  };
+
+ private:
+  Category m_category;
+  const CPPType *m_type;
+
+  MFDataType(Category category, const CPPType &type) : m_category(category), m_type(&type)
+  {
+  }
+
+ public:
+  static MFDataType ForSingle(const CPPType &type)
+  {
+    return MFDataType(Single, type);
+  }
+
+  static MFDataType ForVector(const CPPType &type)
+  {
+    return MFDataType(Vector, type);
+  }
+
+  template<typename T> static MFDataType ForSingle()
+  {
+    return MFDataType::ForSingle(CPPType::get<T>());
+  }
+
+  template<typename T> static MFDataType ForVector()
+  {
+    return MFDataType::ForVector(CPPType::get<T>());
+  }
+
+  bool is_single() const
+  {
+    return m_category == Single;
+  }
+
+  bool is_vector() const
+  {
+    return m_category == Vector;
+  }
+
+  Category category() const
+  {
+    return m_category;
+  }
+
+  const CPPType &single_type() const
+  {
+    BLI_assert(this->is_single());
+    return *m_type;
+  }
+
+  const CPPType &vector_base_type() const
+  {
+    BLI_assert(this->is_vector());
+    return *m_type;
+  }
+
+  friend bool operator==(const MFDataType &a, const MFDataType &b);
+  friend bool operator!=(const MFDataType &a, const MFDataType &b);
+
+  std::string to_string() const
+  {
+    switch (m_category) {
+      case Single:
+        return m_type->name();
+      case Vector:
+        return m_type->name() + " Vector";
+    }
+    BLI_assert(false);
+    return "";
+  }
+};
+
+inline bool operator==(const MFDataType &a, const MFDataType &b)
+{
+  return a.m_category == b.m_category && a.m_type == b.m_type;
+}
+
+inline bool operator!=(const MFDataType &a, const MFDataType &b)
+{
+  return !(a == b);
+}
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_DATA_TYPE_HH__ */

source/blender/functions/FN_multi_function_param_type.hh

@@ -0,0 +1,155 @@
+/*
+ * 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_PARAM_TYPE_HH__
+#define __FN_MULTI_FUNCTION_PARAM_TYPE_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * A multi-function has an arbitrary amount of parameters. Every parameter belongs to one of three
+ * interface types:
+ * - Input: An input parameter is readonly inside the function. The values have to be provided by
+ *     the caller.
+ * - Output: An output parameter has to be initialized by the function. However, the caller
+ *     provides the memory where the data has to be constructed.
+ * - Mutable: A mutable parameter can be considered to be an input and output. The caller has to
+ *     initialize the data, but the function is allowed to modify it.
+ *
+ * Furthermore, every parameter has a MFDataType that describes what kind of data is being passed
+ * around.
+ */
+
+#include "FN_multi_function_data_type.hh"
+
+namespace blender {
+namespace fn {
+
+class MFParamType {
+ public:
+  enum InterfaceType {
+    Input,
+    Output,
+    Mutable,
+  };
+
+  enum Category {
+    SingleInput,
+    VectorInput,
+    SingleOutput,
+    VectorOutput,
+    SingleMutable,
+    VectorMutable,
+  };
+
+ private:
+  InterfaceType m_interface_type;
+  MFDataType m_data_type;
+
+ public:
+  MFParamType(InterfaceType interface_type, MFDataType data_type)
+      : m_interface_type(interface_type), m_data_type(data_type)
+  {
+  }
+
+  static MFParamType ForSingleInput(const CPPType &type)
+  {
+    return MFParamType(InterfaceType::Input, MFDataType::ForSingle(type));
+  }
+
+  static MFParamType ForVectorInput(const CPPType &base_type)
+  {
+    return MFParamType(InterfaceType::Input, MFDataType::ForVector(base_type));
+  }
+
+  static MFParamType ForSingleOutput(const CPPType &type)
+  {
+    return MFParamType(InterfaceType::Output, MFDataType::ForSingle(type));
+  }
+
+  static MFParamType ForVectorOutput(const CPPType &base_type)
+  {
+    return MFParamType(InterfaceType::Output, MFDataType::ForVector(base_type));
+  }
+
+  static MFParamType ForMutableSingle(const CPPType &type)
+  {
+    return MFParamType(InterfaceType::Mutable, MFDataType::ForSingle(type));
+  }
+
+  static MFParamType ForMutableVector(const CPPType &base_type)
+  {
+    return MFParamType(InterfaceType::Mutable, MFDataType::ForVector(base_type));
+  }
+
+  MFDataType data_type() const
+  {
+    return m_data_type;
+  }
+
+  InterfaceType interface_type() const
+  {
+    return m_interface_type;
+  }
+
+  Category category() const
+  {
+    switch (m_data_type.category()) {
+      case MFDataType::Single: {
+        switch (m_interface_type) {
+          case Input:
+            return SingleInput;
+          case Output:
+            return SingleOutput;
+          case Mutable:
+            return SingleMutable;
+        }
+        break;
+      }
+      case MFDataType::Vector: {
+        switch (m_interface_type) {
+          case Input:
+            return VectorInput;
+          case Output:
+            return VectorOutput;
+          case Mutable:
+            return VectorMutable;
+        }
+        break;
+      }
+    }
+    BLI_assert(false);
+    return SingleInput;
+  }
+
+  friend bool operator==(const MFParamType &a, const MFParamType &b);
+  friend bool operator!=(const MFParamType &a, const MFParamType &b);
+};
+
+inline bool operator==(const MFParamType &a, const MFParamType &b)
+{
+  return a.m_interface_type == b.m_interface_type && a.m_data_type == b.m_data_type;
+}
+
+inline bool operator!=(const MFParamType &a, const MFParamType &b)
+{
+  return !(a == b);
+}
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_PARAM_TYPE_HH__ */

source/blender/functions/FN_multi_function_params.hh

@@ -0,0 +1,236 @@
+/*
+ * 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_PARAMS_HH__
+#define __FN_MULTI_FUNCTION_PARAMS_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * This file provides an MFParams and MFParamsBuilder structure.
+ *
+ * `MFParamsBuilder` is used by a function caller to be prepare all parameters that are passed into
+ * the function. `MFParams` is then used inside the called function to access the parameters.
+ */
+
+#include "FN_generic_vector_array.hh"
+#include "FN_multi_function_signature.hh"
+
+namespace blender {
+namespace fn {
+
+class MFParamsBuilder {
+ private:
+  const MFSignature *m_signature;
+  uint m_min_array_size;
+  Vector<GVSpan> m_virtual_spans;
+  Vector<GMutableSpan> m_mutable_spans;
+  Vector<GVArraySpan> m_virtual_array_spans;
+  Vector<GVectorArray *> m_vector_arrays;
+
+  friend class MFParams;
+
+ public:
+  MFParamsBuilder(const MFSignature &signature, uint min_array_size)
+      : m_signature(&signature), m_min_array_size(min_array_size)
+  {
+  }
+
+  MFParamsBuilder(const class MultiFunction &fn, uint min_array_size);
+
+  template<typename T> void add_readonly_single_input(const T *value)
+  {
+    this->add_readonly_single_input(
+        GVSpan::FromSingle(CPPType::get<T>(), value, m_min_array_size));
+  }
+  void add_readonly_single_input(GVSpan ref)
+  {
+    this->assert_current_param_type(MFParamType::ForSingleInput(ref.type()));
+    BLI_assert(ref.size() >= m_min_array_size);
+    m_virtual_spans.append(ref);
+  }
+
+  void add_readonly_vector_input(GVArraySpan ref)
+  {
+    this->assert_current_param_type(MFParamType::ForVectorInput(ref.type()));
+    BLI_assert(ref.size() >= m_min_array_size);
+    m_virtual_array_spans.append(ref);
+  }
+
+  void add_uninitialized_single_output(GMutableSpan ref)
+  {
+    this->assert_current_param_type(MFParamType::ForSingleOutput(ref.type()));
+    BLI_assert(ref.size() >= m_min_array_size);
+    m_mutable_spans.append(ref);
+  }
+
+  void add_vector_output(GVectorArray &vector_array)
+  {
+    this->assert_current_param_type(MFParamType::ForVectorOutput(vector_array.type()));
+    BLI_assert(vector_array.size() >= m_min_array_size);
+    m_vector_arrays.append(&vector_array);
+  }
+
+  void add_single_mutable(GMutableSpan ref)
+  {
+    this->assert_current_param_type(MFParamType::ForMutableSingle(ref.type()));
+    BLI_assert(ref.size() >= m_min_array_size);
+    m_mutable_spans.append(ref);
+  }
+
+  void add_vector_mutable(GVectorArray &vector_array)
+  {
+    this->assert_current_param_type(MFParamType::ForMutableVector(vector_array.type()));
+    BLI_assert(vector_array.size() >= m_min_array_size);
+    m_vector_arrays.append(&vector_array);
+  }
+
+  GMutableSpan computed_array(uint param_index)
+  {
+    BLI_assert(ELEM(m_signature->param_types[param_index].category(),
+                    MFParamType::SingleOutput,
+                    MFParamType::SingleMutable));
+    uint data_index = m_signature->data_index(param_index);
+    return m_mutable_spans[data_index];
+  }
+
+  GVectorArray &computed_vector_array(uint param_index)
+  {
+    BLI_assert(ELEM(m_signature->param_types[param_index].category(),
+                    MFParamType::VectorOutput,
+                    MFParamType::VectorMutable));
+    uint data_index = m_signature->data_index(param_index);
+    return *m_vector_arrays[data_index];
+  }
+
+ private:
+  void assert_current_param_type(MFParamType param_type)
+  {
+    UNUSED_VARS_NDEBUG(param_type);
+#ifdef DEBUG
+    uint param_index = this->current_param_index();
+    MFParamType expected_type = m_signature->param_types[param_index];
+    BLI_assert(expected_type == param_type);
+#endif
+  }
+
+  uint current_param_index() const
+  {
+    return m_virtual_spans.size() + m_mutable_spans.size() + m_virtual_array_spans.size() +
+           m_vector_arrays.size();
+  }
+};
+
+class MFParams {
+ private:
+  MFParamsBuilder *m_builder;
+
+ public:
+  MFParams(MFParamsBuilder &builder) : m_builder(&builder)
+  {
+  }
+
+  template<typename T> VSpan<T> readonly_single_input(uint param_index, StringRef name = "")
+  {
+    return this->readonly_single_input(param_index, name).typed<T>();
+  }
+  GVSpan readonly_single_input(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::SingleInput);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return m_builder->m_virtual_spans[data_index];
+  }
+
+  template<typename T>
+  MutableSpan<T> uninitialized_single_output(uint param_index, StringRef name = "")
+  {
+    return this->uninitialized_single_output(param_index, name).typed<T>();
+  }
+  GMutableSpan uninitialized_single_output(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::SingleOutput);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return m_builder->m_mutable_spans[data_index];
+  }
+
+  template<typename T> VArraySpan<T> readonly_vector_input(uint param_index, StringRef name = "")
+  {
+    return this->readonly_vector_input(param_index, name).typed<T>();
+  }
+  GVArraySpan readonly_vector_input(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::VectorInput);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return m_builder->m_virtual_array_spans[data_index];
+  }
+
+  template<typename T> GVectorArrayRef<T> vector_output(uint param_index, StringRef name = "")
+  {
+    return this->vector_output(param_index, name).typed<T>();
+  }
+  GVectorArray &vector_output(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::VectorOutput);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return *m_builder->m_vector_arrays[data_index];
+  }
+
+  template<typename T> MutableSpan<T> single_mutable(uint param_index, StringRef name = "")
+  {
+    return this->single_mutable(param_index, name).typed<T>();
+  }
+  GMutableSpan single_mutable(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::SingleMutable);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return m_builder->m_mutable_spans[data_index];
+  }
+
+  GVectorArray &vector_mutable(uint param_index, StringRef name = "")
+  {
+    this->assert_correct_param(param_index, name, MFParamType::VectorMutable);
+    uint data_index = m_builder->m_signature->data_index(param_index);
+    return *m_builder->m_vector_arrays[data_index];
+  }
+
+ private:
+  void assert_correct_param(uint param_index, StringRef name, MFParamType param_type)
+  {
+    UNUSED_VARS_NDEBUG(param_index, name, param_type);
+#ifdef DEBUG
+    BLI_assert(m_builder->m_signature->param_types[param_index] == param_type);
+    if (name.size() > 0) {
+      BLI_assert(m_builder->m_signature->param_names[param_index] == name);
+    }
+#endif
+  }
+
+  void assert_correct_param(uint param_index, StringRef name, MFParamType::Category category)
+  {
+    UNUSED_VARS_NDEBUG(param_index, name, category);
+#ifdef DEBUG
+    BLI_assert(m_builder->m_signature->param_types[param_index].category() == category);
+    if (name.size() > 0) {
+      BLI_assert(m_builder->m_signature->param_names[param_index] == name);
+    }
+#endif
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_PARAMS_HH__ */

source/blender/functions/FN_multi_function_signature.hh

@@ -0,0 +1,161 @@
+/*
+ * 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_SIGNATURE_HH__
+#define __FN_MULTI_FUNCTION_SIGNATURE_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * The signature of a multi-function contains the functions name and expected parameters. New
+ * signatures should be build using the MFSignatureBuilder class.
+ */
+
+#include "FN_multi_function_param_type.hh"
+
+#include "BLI_vector.hh"
+
+namespace blender {
+namespace fn {
+
+struct MFSignature {
+  std::string function_name;
+  Vector<std::string> param_names;
+  Vector<MFParamType> param_types;
+  Vector<uint> param_data_indices;
+
+  uint data_index(uint param_index) const
+  {
+    return param_data_indices[param_index];
+  }
+};
+
+class MFSignatureBuilder {
+ private:
+  MFSignature &m_data;
+  uint m_span_count = 0;
+  uint m_virtual_span_count = 0;
+  uint m_virtual_array_span_count = 0;
+  uint m_vector_array_count = 0;
+
+ public:
+  MFSignatureBuilder(MFSignature &data) : m_data(data)
+  {
+    BLI_assert(data.param_names.is_empty());
+    BLI_assert(data.param_types.is_empty());
+    BLI_assert(data.param_data_indices.is_empty());
+  }
+
+  /* Input Param Types */
+
+  template<typename T> void single_input(StringRef name)
+  {
+    this->single_input(name, CPPType::get<T>());
+  }
+  void single_input(StringRef name, const CPPType &type)
+  {
+    this->input(name, MFDataType::ForSingle(type));
+  }
+  template<typename T> void vector_input(StringRef name)
+  {
+    this->vector_input(name, CPPType::get<T>());
+  }
+  void vector_input(StringRef name, const CPPType &base_type)
+  {
+    this->input(name, MFDataType::ForVector(base_type));
+  }
+  void input(StringRef name, MFDataType data_type)
+  {
+    m_data.param_names.append(name);
+    m_data.param_types.append(MFParamType(MFParamType::Input, data_type));
+
+    switch (data_type.category()) {
+      case MFDataType::Single:
+        m_data.param_data_indices.append(m_virtual_span_count++);
+        break;
+      case MFDataType::Vector:
+        m_data.param_data_indices.append(m_virtual_array_span_count++);
+        break;
+    }
+  }
+
+  /* Output Param Types */
+
+  template<typename T> void single_output(StringRef name)
+  {
+    this->single_output(name, CPPType::get<T>());
+  }
+  void single_output(StringRef name, const CPPType &type)
+  {
+    this->output(name, MFDataType::ForSingle(type));
+  }
+  template<typename T> void vector_output(StringRef name)
+  {
+    this->vector_output(name, CPPType::get<T>());
+  }
+  void vector_output(StringRef name, const CPPType &base_type)
+  {
+    this->output(name, MFDataType::ForVector(base_type));
+  }
+  void output(StringRef name, MFDataType data_type)
+  {
+    m_data.param_names.append(name);
+    m_data.param_types.append(MFParamType(MFParamType::Output, data_type));
+
+    switch (data_type.category()) {
+      case MFDataType::Single:
+        m_data.param_data_indices.append(m_span_count++);
+        break;
+      case MFDataType::Vector:
+        m_data.param_data_indices.append(m_vector_array_count++);
+        break;
+    }
+  }
+
+  /* Mutable Param Types */
+
+  template<typename T> void single_mutable(StringRef name)
+  {
+    this->single_mutable(name, CPPType::get<T>());
+  }
+  void single_mutable(StringRef name, const CPPType &type)
+  {
+    this->mutable_(name, MFDataType::ForSingle(type));
+  }
+  void vector_mutable(StringRef name, const CPPType &base_type)
+  {
+    this->mutable_(name, MFDataType::ForVector(base_type));
+  }
+  void mutable_(StringRef name, MFDataType data_type)
+  {
+    m_data.param_names.append(name);
+    m_data.param_types.append(MFParamType(MFParamType::Mutable, data_type));
+
+    switch (data_type.category()) {
+      case MFDataType::Single:
+        m_data.param_data_indices.append(m_span_count++);
+        break;
+      case MFDataType::Vector:
+        m_data.param_data_indices.append(m_vector_array_count++);
+        break;
+    }
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_MULTI_FUNCTION_SIGNATURE_HH__ */

source/blender/functions/FN_spans.hh

@@ -0,0 +1,391 @@
+/*
+ * 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_SPANS_HH__
+#define __FN_SPANS_HH__
+
+/** \file
+ * \ingroup fn
+ *
+ * This file implements multiple variants of a span for different use cases. There are two
+ * requirements of the function system that require span implementations other from
+ * blender::Span<T>.
+ * 1. The function system works with a run-time type system (see `CPPType`). Therefore, it has to
+ *   deal with types in a generic way. The type of a Span<T> has to be known at compile time.
+ * 2. Span<T> expects an underlying memory buffer that is as large as the span. However, sometimes
+ *   we can save some memory and processing when we know that all elements are the same.
+ *
+ * The first requirement is solved with generic spans, which use the "G" prefix. Those
+ * store a CPPType instance to keep track of the type that is currently stored.
+ *
+ * The second requirement is solved with virtual spans. A virtual span behaves like a normal span,
+ * but it might not be backed up by an actual array. Elements in a virtual span are always
+ * immutable.
+ *
+ * Different use cases require different combinations of these properties and therefore use
+ * different data structures.
+ */
+
+#include "BLI_span.hh"
+
+#include "FN_cpp_type.hh"
+
+namespace blender {
+namespace fn {
+
+/**
+ * A generic span. It behaves just like a blender::Span<T>, but the type is only known at run-time.
+ */
+class GSpan {
+ private:
+  const CPPType *m_type;
+  const void *m_buffer;
+  uint m_size;
+
+ public:
+  GSpan(const CPPType &type, const void *buffer, uint size)
+      : m_type(&type), m_buffer(buffer), m_size(size)
+  {
+    BLI_assert(buffer != nullptr || size == 0);
+    BLI_assert(type.pointer_has_valid_alignment(buffer));
+  }
+
+  GSpan(const CPPType &type) : GSpan(type, nullptr, 0)
+  {
+  }
+
+  template<typename T>
+  GSpan(Span<T> array) : GSpan(CPPType::get<T>(), (const void *)array.begin(), array.size())
+  {
+  }
+
+  const CPPType &type() const
+  {
+    return *m_type;
+  }
+
+  bool is_empty() const
+  {
+    return m_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_size;
+  }
+
+  const void *buffer() const
+  {
+    return m_buffer;
+  }
+
+  const void *operator[](uint index) const
+  {
+    BLI_assert(index < m_size);
+    return POINTER_OFFSET(m_buffer, m_type->size() * index);
+  }
+
+  template<typename T> Span<T> typed() const
+  {
+    BLI_assert(CPPType::get<T>() == *m_type);
+    return Span<T>((const T *)m_buffer, m_size);
+  }
+};
+
+/**
+ * A generic mutable span. It behaves just like a blender::MutableSpan<T>, but the type is only
+ * known at run-time.
+ */
+class GMutableSpan {
+ private:
+  const CPPType *m_type;
+  void *m_buffer;
+  uint m_size;
+
+ public:
+  GMutableSpan(const CPPType &type, void *buffer, uint size)
+      : m_type(&type), m_buffer(buffer), m_size(size)
+  {
+    BLI_assert(buffer != nullptr || size == 0);
+    BLI_assert(type.pointer_has_valid_alignment(buffer));
+  }
+
+  GMutableSpan(const CPPType &type) : GMutableSpan(type, nullptr, 0)
+  {
+  }
+
+  template<typename T>
+  GMutableSpan(MutableSpan<T> array)
+      : GMutableSpan(CPPType::get<T>(), (void *)array.begin(), array.size())
+  {
+  }
+
+  operator GSpan() const
+  {
+    return GSpan(*m_type, m_buffer, m_size);
+  }
+
+  const CPPType &type() const
+  {
+    return *m_type;
+  }
+
+  bool is_empty() const
+  {
+    return m_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_size;
+  }
+
+  void *buffer()
+  {
+    return m_buffer;
+  }
+
+  void *operator[](uint index)
+  {
+    BLI_assert(index < m_size);
+    return POINTER_OFFSET(m_buffer, m_type->size() * index);
+  }
+
+  template<typename T> MutableSpan<T> typed()
+  {
+    BLI_assert(CPPType::get<T>() == *m_type);
+    return MutableSpan<T>((T *)m_buffer, m_size);
+  }
+};
+
+/**
+ * A virtual span. It behaves like a blender::Span<T>, but might not be backed up by an actual
+ * array.
+ */
+template<typename T> class VSpan {
+ private:
+  enum Category {
+    Single,
+    FullArray,
+    FullPointerArray,
+  };
+
+  uint m_virtual_size;
+  Category m_category;
+
+  union {
+    struct {
+      const T *data;
+    } single;
+    struct {
+      const T *data;
+    } full_array;
+    struct {
+      const T *const *data;
+    } full_pointer_array;
+  } m_data;
+
+ public:
+  VSpan()
+  {
+    m_virtual_size = 0;
+    m_category = FullArray;
+    m_data.full_array.data = nullptr;
+  }
+
+  VSpan(Span<T> values)
+  {
+    m_virtual_size = values.size();
+    m_category = FullArray;
+    m_data.full_array.data = values.begin();
+  }
+
+  VSpan(MutableSpan<T> values) : VSpan(Span<T>(values))
+  {
+  }
+
+  VSpan(Span<const T *> values)
+  {
+    m_virtual_size = values.size();
+    m_category = FullPointerArray;
+    m_data.full_pointer_array.data = values.begin();
+  }
+
+  static VSpan FromSingle(const T *value, uint virtual_size)
+  {
+    VSpan ref;
+    ref.m_virtual_size = virtual_size;
+    ref.m_category = Single;
+    ref.m_data.single.data = value;
+    return ref;
+  }
+
+  const T &operator[](uint index) const
+  {
+    BLI_assert(index < m_virtual_size);
+    switch (m_category) {
+      case Single:
+        return *m_data.single.data;
+      case FullArray:
+        return m_data.full_array.data[index];
+      case FullPointerArray:
+        return *m_data.full_pointer_array.data[index];
+    }
+    BLI_assert(false);
+    return *m_data.single.data;
+  }
+
+  bool is_empty() const
+  {
+    return m_virtual_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_virtual_size;
+  }
+};
+
+/**
+ * A generic virtual span. It behaves like a blender::Span<T>, but the type is only known at
+ * run-time and it might not be backed up by an actual array.
+ */
+class GVSpan {
+ private:
+  enum Category {
+    Single,
+    FullArray,
+    FullPointerArray,
+  };
+
+  const CPPType *m_type;
+  uint m_virtual_size;
+  Category m_category;
+
+  union {
+    struct {
+      const void *data;
+    } single;
+    struct {
+      const void *data;
+    } full_array;
+    struct {
+      const void *const *data;
+    } full_pointer_array;
+  } m_data;
+
+  GVSpan() = default;
+
+ public:
+  GVSpan(const CPPType &type)
+  {
+    m_type = &type;
+    m_virtual_size = 0;
+    m_category = FullArray;
+    m_data.full_array.data = nullptr;
+  }
+
+  GVSpan(GSpan values)
+  {
+    m_type = &values.type();
+    m_virtual_size = values.size();
+    m_category = FullArray;
+    m_data.full_array.data = values.buffer();
+  }
+
+  GVSpan(GMutableSpan values) : GVSpan(GSpan(values))
+  {
+  }
+
+  template<typename T> GVSpan(Span<T> values) : GVSpan(GSpan(values))
+  {
+  }
+
+  template<typename T> GVSpan(MutableSpan<T> values) : GVSpan(GSpan(values))
+  {
+  }
+
+  static GVSpan FromSingle(const CPPType &type, const void *value, uint virtual_size)
+  {
+    GVSpan ref;
+    ref.m_type = &type;
+    ref.m_virtual_size = virtual_size;
+    ref.m_category = Single;
+    ref.m_data.single.data = value;
+    return ref;
+  }
+
+  static GVSpan FromFullPointerArray(const CPPType &type, const void *const *values, uint size)
+  {
+    GVSpan ref;
+    ref.m_type = &type;
+    ref.m_virtual_size = size;
+    ref.m_category = FullPointerArray;
+    ref.m_data.full_pointer_array.data = values;
+    return ref;
+  }
+
+  bool is_empty() const
+  {
+    return m_virtual_size == 0;
+  }
+
+  uint size() const
+  {
+    return m_virtual_size;
+  }
+
+  const CPPType &type() const
+  {
+    return *m_type;
+  }
+
+  const void *operator[](uint index) const
+  {
+    BLI_assert(index < m_virtual_size);
+    switch (m_category) {
+      case Single:
+        return m_data.single.data;
+      case FullArray:
+        return POINTER_OFFSET(m_data.full_array.data, index * m_type->size());
+      case FullPointerArray:
+        return m_data.full_pointer_array.data[index];
+    }
+    BLI_assert(false);
+    return m_data.single.data;
+  }
+
+  template<typename T> VSpan<T> typed() const
+  {
+    BLI_assert(CPPType::get<T>() == *m_type);
+    switch (m_category) {
+      case Single:
+        return VSpan<T>::FromSingle((const T *)m_data.single.data, m_virtual_size);
+      case FullArray:
+        return VSpan<T>(Span<T>((const T *)m_data.full_array.data, m_virtual_size));
+      case FullPointerArray:
+        return VSpan<T>(
+            Span<const T *>((const T *const *)m_data.full_pointer_array.data, m_virtual_size));
+    }
+    BLI_assert(false);
+    return {};
+  }
+};
+
+}  // namespace fn
+}  // namespace blender
+
+#endif /* __FN_SPANS_HH__ */

source/blender/functions/intern/cpp_types.cc

@@ -22,7 +22,7 @@
 #include "BLI_float4x4.hh"
 
 namespace blender {
-namespace FN {
+namespace fn {
 
 MAKE_CPP_TYPE(bool, bool)
 
@@ -39,5 +39,5 @@ MAKE_CPP_TYPE(Color4b, blender::Color4b)
 
 MAKE_CPP_TYPE(string, std::string)
 
-}  // namespace FN
+}  // namespace fn
 }  // namespace blender

tests/gtests/functions/CMakeLists.txt

@@ -36,4 +36,8 @@ if(WITH_BUILDINFO)
   set(BUILDINFO buildinfoobj)
 endif()
 
+BLENDER_TEST(FN_array_spans "bf_blenlib;bf_functions;${BUILDINFO}")
 BLENDER_TEST(FN_cpp_type "bf_blenlib;bf_functions;${BUILDINFO}")
+BLENDER_TEST(FN_generic_vector_array "bf_blenlib;bf_functions;${BUILDINFO}")
+BLENDER_TEST(FN_multi_function "bf_blenlib;bf_functions;${BUILDINFO}")
+BLENDER_TEST(FN_spans "bf_blenlib;bf_functions;${BUILDINFO}")

tests/gtests/functions/FN_array_spans_test.cc

@@ -0,0 +1,92 @@
+/*
+ * 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 "testing/testing.h"
+
+#include "FN_array_spans.hh"
+#include "FN_cpp_types.hh"
+
+namespace blender {
+namespace fn {
+
+TEST(virtual_array_span, EmptyConstructor)
+{
+  VArraySpan<int> span;
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(virtual_array_span, SingleArrayConstructor)
+{
+  std::array<int, 4> values = {3, 4, 5, 6};
+  VArraySpan<int> span{Span<int>(values), 3};
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0].size(), 4);
+  EXPECT_EQ(span[1].size(), 4);
+  EXPECT_EQ(span[2].size(), 4);
+  EXPECT_EQ(span[0][0], 3);
+  EXPECT_EQ(span[0][1], 4);
+  EXPECT_EQ(span[0][2], 5);
+  EXPECT_EQ(span[0][3], 6);
+  EXPECT_EQ(span[1][3], 6);
+  EXPECT_EQ(span[2][1], 4);
+}
+
+TEST(virtual_array_span, MultipleArrayConstructor)
+{
+  std::array<int, 4> values0 = {1, 2, 3, 4};
+  std::array<int, 2> values1 = {6, 7};
+  std::array<int, 1> values2 = {8};
+  std::array<const int *, 3> starts = {values0.data(), values1.data(), values2.data()};
+  std::array<uint, 3> sizes{values0.size(), values1.size(), values2.size()};
+
+  VArraySpan<int> span{starts, sizes};
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0].size(), 4);
+  EXPECT_EQ(span[1].size(), 2);
+  EXPECT_EQ(span[2].size(), 1);
+  EXPECT_EQ(&span[0][0], values0.data());
+  EXPECT_EQ(&span[1][0], values1.data());
+  EXPECT_EQ(&span[2][0], values2.data());
+  EXPECT_EQ(span[2][0], 8);
+  EXPECT_EQ(span[1][1], 7);
+}
+
+TEST(generic_virtual_array_span, TypeConstructor)
+{
+  GVArraySpan span{CPPType_int32};
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(generic_virtual_array_span, GSpanConstructor)
+{
+  std::array<std::string, 3> values = {"hello", "world", "test"};
+  GVArraySpan span{GSpan(CPPType_string, values.data(), 3), 5};
+  EXPECT_EQ(span.size(), 5);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0][0], values.data());
+  EXPECT_EQ(span[1][0], values.data());
+  EXPECT_EQ(span[4][0], values.data());
+  EXPECT_EQ(span[0].size(), 3);
+  EXPECT_EQ(span[2].size(), 3);
+  EXPECT_EQ(*(std::string *)span[3][1], "world");
+}
+
+}  // namespace fn
+}  // namespace blender

tests/gtests/functions/FN_cpp_type_test.cc

@@ -12,7 +12,6 @@
  * 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 "testing/testing.h"
@@ -20,7 +19,7 @@
 #include "FN_cpp_type.hh"
 
 namespace blender {
-namespace FN {
+namespace fn {
 
 static const int default_constructed_value = 1;
 static const int copy_constructed_value = 2;
@@ -301,5 +300,5 @@ TEST(cpp_type, FillUninitialized)
   EXPECT_EQ(buffer2[9], 0);
 }
 
-}  // namespace FN
+}  // namespace fn
 }  // namespace blender

tests/gtests/functions/FN_generic_vector_array_test.cc

@@ -0,0 +1,101 @@
+/*
+ * 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 "FN_cpp_types.hh"
+#include "FN_generic_vector_array.hh"
+
+#include "testing/testing.h"
+
+namespace blender {
+namespace fn {
+
+TEST(generic_vector_array, Constructor)
+{
+  GVectorArray vectors{CPPType_int32, 3};
+  EXPECT_EQ(vectors.size(), 3);
+  EXPECT_EQ(vectors.lengths().size(), 3);
+  EXPECT_EQ(vectors.starts().size(), 3);
+  EXPECT_EQ(vectors.lengths()[0], 0);
+  EXPECT_EQ(vectors.lengths()[1], 0);
+  EXPECT_EQ(vectors.lengths()[2], 0);
+  EXPECT_EQ(vectors.type(), CPPType_int32);
+}
+
+TEST(generic_vector_array, Append)
+{
+  GVectorArray vectors{CPPType_string, 3};
+  std::string value = "hello";
+  vectors.append(0, &value);
+  value = "world";
+  vectors.append(0, &value);
+  vectors.append(2, &value);
+
+  EXPECT_EQ(vectors.lengths()[0], 2);
+  EXPECT_EQ(vectors.lengths()[1], 0);
+  EXPECT_EQ(vectors.lengths()[2], 1);
+  EXPECT_EQ(vectors[0].size(), 2);
+  EXPECT_EQ(vectors[0].typed<std::string>()[0], "hello");
+  EXPECT_EQ(vectors[0].typed<std::string>()[1], "world");
+  EXPECT_EQ(vectors[2].typed<std::string>()[0], "world");
+}
+
+TEST(generic_vector_array, AsArraySpan)
+{
+  GVectorArray vectors{CPPType_int32, 3};
+  int value = 3;
+  vectors.append(0, &value);
+  vectors.append(0, &value);
+  value = 5;
+  vectors.append(2, &value);
+  vectors.append(2, &value);
+  vectors.append(2, &value);
+
+  GVArraySpan span = vectors;
+  EXPECT_EQ(span.type(), CPPType_int32);
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_EQ(span[0].size(), 2);
+  EXPECT_EQ(span[1].size(), 0);
+  EXPECT_EQ(span[2].size(), 3);
+  EXPECT_EQ(span[0].typed<int>()[1], 3);
+  EXPECT_EQ(span[2].typed<int>()[0], 5);
+}
+
+TEST(generic_vector_array, TypedRef)
+{
+  GVectorArray vectors{CPPType_int32, 4};
+  GVectorArrayRef<int> ref = vectors.typed<int>();
+  ref.append(0, 2);
+  ref.append(0, 6);
+  ref.append(0, 7);
+  ref.append(2, 1);
+  ref.append(2, 1);
+  ref.append(3, 5);
+  ref.append(3, 6);
+
+  EXPECT_EQ(ref[0].size(), 3);
+  EXPECT_EQ(vectors[0].size(), 3);
+  EXPECT_EQ(ref[0][0], 2);
+  EXPECT_EQ(ref[0][1], 6);
+  EXPECT_EQ(ref[0][2], 7);
+  EXPECT_EQ(ref[1].size(), 0);
+  EXPECT_EQ(ref[2][0], 1);
+  EXPECT_EQ(ref[2][1], 1);
+  EXPECT_EQ(ref[3][0], 5);
+  EXPECT_EQ(ref[3][1], 6);
+}
+
+}  // namespace fn
+}  // namespace blender

tests/gtests/functions/FN_multi_function_test.cc

@@ -0,0 +1,222 @@
+/*
+ * 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 "testing/testing.h"
+
+#include "FN_cpp_types.hh"
+#include "FN_multi_function.hh"
+
+namespace blender {
+namespace fn {
+
+class AddFunction : public MultiFunction {
+ public:
+  AddFunction()
+  {
+    MFSignatureBuilder builder = this->get_builder("Add");
+    builder.single_input<int>("A");
+    builder.single_input<int>("B");
+    builder.single_output<int>("Result");
+  }
+
+  void call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const override
+  {
+    VSpan<int> a = params.readonly_single_input<int>(0, "A");
+    VSpan<int> b = params.readonly_single_input<int>(1, "B");
+    MutableSpan<int> result = params.uninitialized_single_output<int>(2, "Result");
+
+    for (uint i : mask) {
+      result[i] = a[i] + b[i];
+    }
+  }
+};
+
+TEST(multi_function, AddFunction)
+{
+  AddFunction fn;
+
+  Array<int> input1 = {4, 5, 6};
+  Array<int> input2 = {10, 20, 30};
+  Array<int> output(3, -1);
+
+  MFParamsBuilder params(fn, 3);
+  params.add_readonly_single_input(input1.as_span());
+  params.add_readonly_single_input(input2.as_span());
+  params.add_uninitialized_single_output(output.as_mutable_span());
+
+  MFContextBuilder context;
+
+  fn.call({0, 2}, params, context);
+
+  EXPECT_EQ(output[0], 14);
+  EXPECT_EQ(output[1], -1);
+  EXPECT_EQ(output[2], 36);
+}
+
+class AddPrefixFunction : public MultiFunction {
+ public:
+  AddPrefixFunction()
+  {
+    MFSignatureBuilder builder = this->get_builder("Add Prefix");
+    builder.single_input<std::string>("Prefix");
+    builder.single_mutable<std::string>("Strings");
+  }
+
+  void call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const override
+  {
+    VSpan<std::string> prefixes = params.readonly_single_input<std::string>(0, "Prefix");
+    MutableSpan<std::string> strings = params.single_mutable<std::string>(1, "Strings");
+
+    for (uint i : mask) {
+      strings[i] = prefixes[i] + strings[i];
+    }
+  }
+};
+
+TEST(multi_function, AddPrefixFunction)
+{
+  AddPrefixFunction fn;
+
+  Array<std::string> strings = {
+      "Hello",
+      "World",
+      "This is a test",
+      "Another much longer string to trigger an allocation",
+  };
+
+  std::string prefix = "AB";
+
+  MFParamsBuilder params(fn, strings.size());
+  params.add_readonly_single_input(&prefix);
+  params.add_single_mutable(strings.as_mutable_span());
+
+  MFContextBuilder context;
+
+  fn.call({0, 2, 3}, params, context);
+
+  EXPECT_EQ(strings[0], "ABHello");
+  EXPECT_EQ(strings[1], "World");
+  EXPECT_EQ(strings[2], "ABThis is a test");
+  EXPECT_EQ(strings[3], "ABAnother much longer string to trigger an allocation");
+}
+
+class CreateRangeFunction : public MultiFunction {
+ public:
+  CreateRangeFunction()
+  {
+    MFSignatureBuilder builder = this->get_builder("Create Range");
+    builder.single_input<uint>("Size");
+    builder.vector_output<uint>("Range");
+  }
+
+  void call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const override
+  {
+    VSpan<uint> sizes = params.readonly_single_input<uint>(0, "Size");
+    GVectorArrayRef<uint> ranges = params.vector_output<uint>(1, "Range");
+
+    for (uint i : mask) {
+      uint size = sizes[i];
+      for (uint j : IndexRange(size)) {
+        ranges.append(i, j);
+      }
+    }
+  }
+};
+
+TEST(multi_function, CreateRangeFunction)
+{
+  CreateRangeFunction fn;
+
+  GVectorArray ranges(CPPType_uint32, 5);
+  GVectorArrayRef<uint> ranges_ref(ranges);
+  Array<uint> sizes = {3, 0, 6, 1, 4};
+
+  MFParamsBuilder params(fn, ranges.size());
+  params.add_readonly_single_input(sizes.as_span());
+  params.add_vector_output(ranges);
+
+  MFContextBuilder context;
+
+  fn.call({0, 1, 2, 3}, params, context);
+
+  EXPECT_EQ(ranges_ref[0].size(), 3);
+  EXPECT_EQ(ranges_ref[1].size(), 0);
+  EXPECT_EQ(ranges_ref[2].size(), 6);
+  EXPECT_EQ(ranges_ref[3].size(), 1);
+  EXPECT_EQ(ranges_ref[4].size(), 0);
+
+  EXPECT_EQ(ranges_ref[0][0], 0);
+  EXPECT_EQ(ranges_ref[0][1], 1);
+  EXPECT_EQ(ranges_ref[0][2], 2);
+  EXPECT_EQ(ranges_ref[2][0], 0);
+  EXPECT_EQ(ranges_ref[2][1], 1);
+}
+
+class GenericAppendFunction : public MultiFunction {
+ public:
+  GenericAppendFunction(const CPPType &type)
+  {
+    MFSignatureBuilder builder = this->get_builder("Append");
+    builder.vector_mutable("Vector", type);
+    builder.single_input("Value", type);
+  }
+
+  void call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const override
+  {
+    GVectorArray &vectors = params.vector_mutable(0, "Vector");
+    GVSpan values = params.readonly_single_input(1, "Value");
+
+    for (uint i : mask) {
+      vectors.append(i, values[i]);
+    }
+  }
+};
+
+TEST(multi_function, GenericAppendFunction)
+{
+  GenericAppendFunction fn(CPPType_int32);
+
+  GVectorArray vectors(CPPType_int32, 4);
+  GVectorArrayRef<int> vectors_ref(vectors);
+  vectors_ref.append(0, 1);
+  vectors_ref.append(0, 2);
+  vectors_ref.append(2, 6);
+  Array<int> values = {5, 7, 3, 1};
+
+  MFParamsBuilder params(fn, vectors.size());
+  params.add_vector_mutable(vectors);
+  params.add_readonly_single_input(values.as_span());
+
+  MFContextBuilder context;
+
+  fn.call(IndexRange(vectors.size()), params, context);
+
+  EXPECT_EQ(vectors_ref[0].size(), 3);
+  EXPECT_EQ(vectors_ref[1].size(), 1);
+  EXPECT_EQ(vectors_ref[2].size(), 2);
+  EXPECT_EQ(vectors_ref[3].size(), 1);
+
+  EXPECT_EQ(vectors_ref[0][0], 1);
+  EXPECT_EQ(vectors_ref[0][1], 2);
+  EXPECT_EQ(vectors_ref[0][2], 5);
+  EXPECT_EQ(vectors_ref[1][0], 7);
+  EXPECT_EQ(vectors_ref[2][0], 6);
+  EXPECT_EQ(vectors_ref[2][1], 3);
+  EXPECT_EQ(vectors_ref[3][0], 1);
+}
+
+}  // namespace fn
+}  // namespace blender

tests/gtests/functions/FN_spans_test.cc

@@ -0,0 +1,159 @@
+/*
+ * 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 "testing/testing.h"
+
+#include "FN_cpp_types.hh"
+#include "FN_spans.hh"
+
+namespace blender {
+namespace fn {
+
+TEST(generic_span, TypeConstructor)
+{
+  GSpan span(CPPType_float);
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_EQ(span.typed<float>().size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(generic_span, BufferAndSizeConstructor)
+{
+  int values[4] = {6, 7, 3, 2};
+  void *buffer = (void *)values;
+  GSpan span(CPPType_int32, buffer, 4);
+  EXPECT_EQ(span.size(), 4);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span.typed<int>().size(), 4);
+  EXPECT_EQ(span[0], &values[0]);
+  EXPECT_EQ(span[1], &values[1]);
+  EXPECT_EQ(span[2], &values[2]);
+  EXPECT_EQ(span[3], &values[3]);
+}
+
+TEST(generic_mutable_span, TypeConstructor)
+{
+  GMutableSpan span(CPPType_int32);
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(generic_mutable_span, BufferAndSizeConstructor)
+{
+  int values[4] = {4, 7, 3, 5};
+  void *buffer = (void *)values;
+  GMutableSpan span(CPPType_int32, buffer, 4);
+  EXPECT_EQ(span.size(), 4);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span.typed<int>().size(), 4);
+  EXPECT_EQ(values[2], 3);
+  *(int *)span[2] = 10;
+  EXPECT_EQ(values[2], 10);
+  span.typed<int>()[2] = 20;
+  EXPECT_EQ(values[2], 20);
+}
+
+TEST(virtual_span, EmptyConstructor)
+{
+  VSpan<int> span;
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(virtual_span, SpanConstructor)
+{
+  std::array<int, 5> values = {7, 3, 8, 6, 4};
+  Span<int> span = values;
+  VSpan<int> virtual_span = span;
+  EXPECT_EQ(virtual_span.size(), 5);
+  EXPECT_FALSE(virtual_span.is_empty());
+  EXPECT_EQ(virtual_span[0], 7);
+  EXPECT_EQ(virtual_span[2], 8);
+  EXPECT_EQ(virtual_span[3], 6);
+}
+
+TEST(virtual_span, PointerSpanConstructor)
+{
+  int x0 = 3;
+  int x1 = 6;
+  int x2 = 7;
+  std::array<const int *, 3> pointers = {&x0, &x2, &x1};
+  VSpan<int> span = Span<const int *>(pointers);
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0], 3);
+  EXPECT_EQ(span[1], 7);
+  EXPECT_EQ(span[2], 6);
+  EXPECT_EQ(&span[1], &x2);
+}
+
+TEST(virtual_span, SingleConstructor)
+{
+  int value = 5;
+  VSpan<int> span = VSpan<int>::FromSingle(&value, 3);
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0], 5);
+  EXPECT_EQ(span[1], 5);
+  EXPECT_EQ(span[2], 5);
+  EXPECT_EQ(&span[0], &value);
+  EXPECT_EQ(&span[1], &value);
+  EXPECT_EQ(&span[2], &value);
+}
+
+TEST(generic_virtual_span, TypeConstructor)
+{
+  GVSpan span(CPPType_int32);
+  EXPECT_EQ(span.size(), 0);
+  EXPECT_TRUE(span.is_empty());
+}
+
+TEST(generic_virtual_span, GenericSpanConstructor)
+{
+  int values[4] = {3, 4, 5, 6};
+  GVSpan span{GSpan(CPPType_int32, values, 4)};
+  EXPECT_EQ(span.size(), 4);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0], &values[0]);
+  EXPECT_EQ(span[1], &values[1]);
+  EXPECT_EQ(span[2], &values[2]);
+  EXPECT_EQ(span[3], &values[3]);
+}
+
+TEST(generic_virtual_span, SpanConstructor)
+{
+  std::array<int, 3> values = {6, 7, 8};
+  GVSpan span{Span<int>(values)};
+  EXPECT_EQ(span.type(), CPPType_int32);
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_EQ(span[0], &values[0]);
+  EXPECT_EQ(span[1], &values[1]);
+  EXPECT_EQ(span[2], &values[2]);
+}
+
+TEST(generic_virtual_span, SingleConstructor)
+{
+  int value = 5;
+  GVSpan span = GVSpan::FromSingle(CPPType_int32, &value, 3);
+  EXPECT_EQ(span.size(), 3);
+  EXPECT_FALSE(span.is_empty());
+  EXPECT_EQ(span[0], &value);
+  EXPECT_EQ(span[1], &value);
+  EXPECT_EQ(span[2], &value);
+}
+
+}  // namespace fn
+}  // namespace blender