Functions: refactor virtual array data structures

When a function is executed for many elements (e.g. per point) it is often the case
that some parameters are different for every element and other parameters are
the same (there are some more less common cases). To simplify writing such
functions one can use a "virtual array". This is a data structure that has a value
for every index, but might not be stored as an actual array internally. Instead, it
might be just a single value or is computed on the fly. There are various tradeoffs
involved when using this data structure which are mentioned in `BLI_virtual_array.hh`.
It is called "virtual", because it uses inheritance and virtual methods.

Furthermore, there is a new virtual vector array data structure, which is an array
of vectors. Both these types have corresponding generic variants, which can be used
when the data type is not known at compile time. This is typically the case when
building a somewhat generic execution system. The function system used these virtual
data structures before, but now they are more versatile.

I've done this refactor in preparation for the attribute processor and other features of
geometry nodes. I moved the typed virtual arrays to blenlib, so that they can be used
independent of the function system.

One open question for me is whether all the generic data structures (and `CPPType`)
should be moved to blenlib as well. They are well isolated and don't really contain
any business logic. That can be done later if necessary.

1 files changed, 211 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh
new file mode 100644
index 00000000000..51d2e820504
--- /dev/null
+++ b/source/blender/blenlib/BLI_virtual_array.hh
@@ -0,0 +1,211 @@
+/*
+ * 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.
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A virtual array is a data structure that behaves similar to an array, but its elements are
+ * accessed through virtual methods. This improves the decoupling of a function from its callers,
+ * because it does not have to know exactly how the data is layed out in memory, or if it is stored
+ * in memory at all. It could just as well be computed on the fly.
+ *
+ * Taking a virtual array as parameter instead of a more specific non-virtual type has some
+ * tradeoffs. Access to individual elements of the individual elements is higher due to function
+ * call overhead. On the other hand, potential callers don't have to convert the data into the
+ * specific format required for the function. This can be a costly conversion if only few of the
+ * elements are accessed in the end.
+ *
+ * Functions taking a virtual array as input can still optimize for different data layouts. For
+ * example, they can check if the array is stored as an array internally or if it is the same
+ * element for all indices. Whether it is worth to optimize for different data layouts in a
+ * function has to be decided on a case by case basis. One should always do some benchmarking to
+ * see of the increased compile time and binary size is worth it.
+ */
+
+#include "BLI_span.hh"
+
+namespace blender {
+
+/* An immutable virtual array. */
+template<typename T> class VArray {
+ protected:
+  int64_t size_;
+
+ public:
+  VArray(const int64_t size) : size_(size)
+  {
+    BLI_assert(size_ >= 0);
+  }
+
+  virtual ~VArray() = default;
+
+  T get(const int64_t index) const
+  {
+    BLI_assert(index >= 0);
+    BLI_assert(index < size_);
+    return this->get_impl(index);
+  }
+
+  int64_t size() const
+  {
+    return size_;
+  }
+
+  bool is_empty() const
+  {
+    return size_ == 0;
+  }
+
+  /* Returns true when the virtual array is stored as a span internally. */
+  bool is_span() const
+  {
+    if (size_ == 0) {
+      return true;
+    }
+    return this->is_span_impl();
+  }
+
+  /* Returns the internally used span of the virtual array. This invokes undefined behavior is the
+   * virtual array is not stored as a span internally. */
+  Span<T> get_span() const
+  {
+    BLI_assert(this->is_span());
+    if (size_ == 0) {
+      return {};
+    }
+    return this->get_span_impl();
+  }
+
+  /* Returns true when the virtual array returns the same value for every index. */
+  bool is_single() const
+  {
+    if (size_ == 1) {
+      return true;
+    }
+    return this->is_single_impl();
+  }
+
+  /* Returns the value that is returned for every index. This invokes undefined behavior if the
+   * virtual array would not return the same value for every index. */
+  T get_single() const
+  {
+    BLI_assert(this->is_single());
+    if (size_ == 1) {
+      return this->get(0);
+    }
+    return this->get_single_impl();
+  }
+
+  T operator[](const int64_t index) const
+  {
+    return this->get(index);
+  }
+
+ protected:
+  virtual T get_impl(const int64_t index) const = 0;
+
+  virtual bool is_span_impl() const
+  {
+    return false;
+  }
+
+  virtual Span<T> get_span_impl() const
+  {
+    BLI_assert(false);
+    return {};
+  }
+
+  virtual bool is_single_impl() const
+  {
+    return false;
+  }
+
+  virtual T get_single_impl() const
+  {
+    /* Provide a default implementation, so that subclasses don't have to provide it. This method
+     * should never be called because `is_single_impl` returns false by default. */
+    BLI_assert(false);
+    return T();
+  }
+};
+
+/* A virtual array implementation for a span. */
+template<typename T> class VArrayForSpan : public VArray<T> {
+ private:
+  const T *data_;
+
+ public:
+  VArrayForSpan(const Span<T> data) : VArray<T>(data.size()), data_(data.data())
+  {
+  }
+
+ protected:
+  T get_impl(const int64_t index) const override
+  {
+    return data_[index];
+  }
+
+  bool is_span_impl() const override
+  {
+    return true;
+  }
+
+  Span<T> get_span_impl() const override
+  {
+    return Span<T>(data_, this->size_);
+  }
+};
+
+/* A virtual array implementation that returns the same value for every index. */
+template<typename T> class VArrayForSingle : public VArray<T> {
+ private:
+  T value_;
+
+ public:
+  VArrayForSingle(T value, const int64_t size) : VArray<T>(size), value_(std::move(value))
+  {
+  }
+
+ protected:
+  T get_impl(const int64_t UNUSED(index)) const override
+  {
+    return value_;
+  }
+
+  bool is_span_impl() const override
+  {
+    return this->size_ == 1;
+  }
+
+  Span<T> get_span_impl() const override
+  {
+    return Span<T>(&value_, 1);
+  }
+
+  bool is_single_impl() const override
+  {
+    return true;
+  }
+
+  T get_single_impl() const override
+  {
+    return value_;
+  }
+};
+
+}  // namespace blender