Functions: extend virtual array functionality

This adds support for mutable virtual arrays and provides many utilities
for creating virtual arrays for various kinds of data. This commit is
preparation for D10994.

1 files changed, 351 insertions, 30 deletions

diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh
index f9b0aaa7de6..3868f5acae9 100644
--- a/source/blender/blenlib/BLI_virtual_array.hh
+++ b/source/blender/blenlib/BLI_virtual_array.hh
@@ -37,6 +37,7 @@
  * see of the increased compile time and binary size is worth it.
  */
 
+#include "BLI_array.hh"
 #include "BLI_span.hh"
 
 namespace blender {
@@ -71,6 +72,11 @@ template<typename T> class VArray {
     return size_ == 0;
   }
 
+  IndexRange index_range() const
+  {
+    return IndexRange(size_);
+  }
+
   /* Returns true when the virtual array is stored as a span internally. */
   bool is_span() const
   {
@@ -82,13 +88,13 @@ template<typename T> class VArray {
 
   /* 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
+  Span<T> get_internal_span() const
   {
     BLI_assert(this->is_span());
     if (size_ == 0) {
       return {};
     }
-    return this->get_span_impl();
+    return this->get_internal_span_impl();
   }
 
   /* Returns true when the virtual array returns the same value for every index. */
@@ -102,20 +108,35 @@ template<typename T> class VArray {
 
   /* 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
+  T get_internal_single() const
   {
     BLI_assert(this->is_single());
     if (size_ == 1) {
       return this->get(0);
     }
-    return this->get_single_impl();
+    return this->get_internal_single_impl();
   }
 
+  /* Get the element at a specific index. Note that this operator cannot be used to assign values
+   * to an index, because the return value is not a reference. */
   T operator[](const int64_t index) const
   {
     return this->get(index);
   }
 
+  /* Copy the entire virtual array into a span. */
+  void materialize(MutableSpan<T> r_span) const
+  {
+    BLI_assert(size_ == r_span.size());
+    this->materialize_impl(r_span);
+  }
+
+  void materialize_to_uninitialized(MutableSpan<T> r_span) const
+  {
+    BLI_assert(size_ == r_span.size());
+    this->materialize_to_uninitialized_impl(r_span);
+  }
+
  protected:
   virtual T get_impl(const int64_t index) const = 0;
 
@@ -124,7 +145,7 @@ template<typename T> class VArray {
     return false;
   }
 
-  virtual Span<T> get_span_impl() const
+  virtual Span<T> get_internal_span_impl() const
   {
     BLI_assert_unreachable();
     return {};
@@ -135,56 +156,198 @@ template<typename T> class VArray {
     return false;
   }
 
-  virtual T get_single_impl() const
+  virtual T get_internal_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_unreachable();
     return T();
   }
+
+  virtual void materialize_impl(MutableSpan<T> r_span) const
+  {
+    if (this->is_span()) {
+      const Span<T> span = this->get_internal_span();
+      initialized_copy_n(span.data(), size_, r_span.data());
+    }
+    else if (this->is_single()) {
+      const T single = this->get_internal_single();
+      initialized_fill_n(r_span.data(), size_, single);
+    }
+    else {
+      const int64_t size = size_;
+      for (int64_t i = 0; i < size; i++) {
+        r_span[i] = this->get(i);
+      }
+    }
+  }
+
+  virtual void materialize_to_uninitialized_impl(MutableSpan<T> r_span) const
+  {
+    if (this->is_span()) {
+      const Span<T> span = this->get_internal_span();
+      uninitialized_copy_n(span.data(), size_, r_span.data());
+    }
+    else if (this->is_single()) {
+      const T single = this->get_internal_single();
+      uninitialized_fill_n(r_span.data(), size_, single);
+    }
+    else {
+      const int64_t size = size_;
+      T *dst = r_span.data();
+      for (int64_t i = 0; i < size; i++) {
+        new (dst + i) T(this->get(i));
+      }
+    }
+  }
+};
+
+/* Similar to VArray, but the elements are mutable. */
+template<typename T> class VMutableArray : public VArray<T> {
+ public:
+  VMutableArray(const int64_t size) : VArray<T>(size)
+  {
+  }
+
+  void set(const int64_t index, T value)
+  {
+    BLI_assert(index >= 0);
+    BLI_assert(index < this->size_);
+    this->set_impl(index, std::move(value));
+  }
+
+  /* Copy the values from the source span to all elements in the virtual array. */
+  void set_all(Span<T> src)
+  {
+    BLI_assert(src.size() == this->size_);
+    this->set_all_impl(src);
+  }
+
+  MutableSpan<T> get_internal_span()
+  {
+    BLI_assert(this->is_span());
+    Span<T> span = static_cast<const VArray<T> *>(this)->get_internal_span();
+    return MutableSpan<T>(const_cast<T *>(span.data()), span.size());
+  }
+
+ protected:
+  virtual void set_impl(const int64_t index, T value) = 0;
+
+  virtual void set_all_impl(Span<T> src)
+  {
+    if (this->is_span()) {
+      const MutableSpan<T> span = this->get_internal_span();
+      initialized_copy_n(src.data(), this->size_, span.data());
+    }
+    else {
+      const int64_t size = this->size_;
+      for (int64_t i = 0; i < size; i++) {
+        this->set(i, src[i]);
+      }
+    }
+  }
 };
 
 /**
- * A virtual array implementation for a span. This class is final so that it can be devirtualized
- * by the compiler in some cases (e.g. when #devirtualize_varray is used).
+ * A virtual array implementation for a span. Methods in this class are final so that it can be
+ * devirtualized by the compiler in some cases (e.g. when #devirtualize_varray is used).
  */
-template<typename T> class VArrayForSpan final : public VArray<T> {
- private:
-  const T *data_;
+template<typename T> class VArray_For_Span : public VArray<T> {
+ protected:
+  const T *data_ = nullptr;
 
  public:
-  VArrayForSpan(const Span<T> data) : VArray<T>(data.size()), data_(data.data())
+  VArray_For_Span(const Span<T> data) : VArray<T>(data.size()), data_(data.data())
   {
   }
 
  protected:
-  T get_impl(const int64_t index) const override
+  VArray_For_Span(const int64_t size) : VArray<T>(size)
+  {
+  }
+
+  T get_impl(const int64_t index) const final
+  {
+    return data_[index];
+  }
+
+  bool is_span_impl() const final
+  {
+    return true;
+  }
+
+  Span<T> get_internal_span_impl() const final
+  {
+    return Span<T>(data_, this->size_);
+  }
+};
+
+template<typename T> class VMutableArray_For_MutableSpan : public VMutableArray<T> {
+ protected:
+  T *data_ = nullptr;
+
+ public:
+  VMutableArray_For_MutableSpan(const MutableSpan<T> data)
+      : VMutableArray<T>(data.size()), data_(data.data())
+  {
+  }
+
+ protected:
+  VMutableArray_For_MutableSpan(const int64_t size) : VMutableArray<T>(size)
+  {
+  }
+
+  T get_impl(const int64_t index) const final
   {
     return data_[index];
   }
 
+  void set_impl(const int64_t index, T value) final
+  {
+    data_[index] = value;
+  }
+
   bool is_span_impl() const override
   {
     return true;
   }
 
-  Span<T> get_span_impl() const override
+  Span<T> get_internal_span_impl() const override
   {
     return Span<T>(data_, this->size_);
   }
 };
 
 /**
+ * A variant of `VArray_For_Span` that owns the underlying data.
+ * The `Container` type has to implement a `size()` and `data()` method.
+ * The `data()` method has to return a pointer to the first element in the continuous array of
+ * elements.
+ */
+template<typename Container, typename T = typename Container::value_type>
+class VArray_For_ArrayContainer : public VArray_For_Span<T> {
+ private:
+  Container container_;
+
+ public:
+  VArray_For_ArrayContainer(Container container)
+      : VArray_For_Span<T>((int64_t)container.size()), container_(std::move(container))
+  {
+    this->data_ = container_.data();
+  }
+};
+
+/**
  * A virtual array implementation that returns the same value for every index. This class is final
  * so that it can be devirtualized by the compiler in some cases (e.g. when #devirtualize_varray is
  * used).
  */
-template<typename T> class VArrayForSingle final : public VArray<T> {
+template<typename T> class VArray_For_Single final : public VArray<T> {
  private:
   T value_;
 
  public:
-  VArrayForSingle(T value, const int64_t size) : VArray<T>(size), value_(std::move(value))
+  VArray_For_Single(T value, const int64_t size) : VArray<T>(size), value_(std::move(value))
   {
   }
 
@@ -199,7 +362,7 @@ template<typename T> class VArrayForSingle final : public VArray<T> {
     return this->size_ == 1;
   }
 
-  Span<T> get_span_impl() const override
+  Span<T> get_internal_span_impl() const override
   {
     return Span<T>(&value_, 1);
   }
@@ -209,13 +372,171 @@ template<typename T> class VArrayForSingle final : public VArray<T> {
     return true;
   }
 
-  T get_single_impl() const override
+  T get_internal_single_impl() const override
   {
     return value_;
   }
 };
 
 /**
+ * In many cases a virtual array is a span internally. In those cases, access to individual could
+ * be much more efficient than calling a virtual method. When the underlying virtual array is not a
+ * span, this class allocates a new array and copies the values over.
+ *
+ * This should be used in those cases:
+ *  - All elements in the virtual array are accessed multiple times.
+ *  - In most cases, the underlying virtual array is a span, so no copy is necessary to benefit
+ *    from faster access.
+ *  - An API is called, that does not accept virtual arrays, but only spans.
+ */
+template<typename T> class VArray_Span final : public Span<T> {
+ private:
+  const VArray<T> &varray_;
+  Array<T> owned_data_;
+
+ public:
+  VArray_Span(const VArray<T> &varray) : Span<T>(), varray_(varray)
+  {
+    this->size_ = varray_.size();
+    if (varray_.is_span()) {
+      this->data_ = varray_.get_internal_span().data();
+    }
+    else {
+      owned_data_.~Array();
+      new (&owned_data_) Array<T>(varray_.size(), NoInitialization{});
+      varray_.materialize_to_uninitialized(owned_data_);
+      this->data_ = owned_data_.data();
+    }
+  }
+};
+
+/**
+ * Same as VArray_Span, but for a mutable span.
+ * The important thing to note is that when changing this span, the results might not be
+ * immediately reflected in the underlying virtual array (only when the virtual array is a span
+ * internally). The #save method can be used to write all changes to the underlying virtual array,
+ * if necessary.
+ */
+template<typename T> class VMutableArray_Span final : public MutableSpan<T> {
+ private:
+  VMutableArray<T> &varray_;
+  Array<T> owned_data_;
+  bool save_has_been_called_ = false;
+  bool show_not_saved_warning_ = true;
+
+ public:
+  /* Create a span for any virtual array. This is cheap when the virtual array is a span itself. If
+   * not, a new array has to be allocated as a wrapper for the underlying virtual array. */
+  VMutableArray_Span(VMutableArray<T> &varray, const bool copy_values_to_span = true)
+      : MutableSpan<T>(), varray_(varray)
+  {
+    this->size_ = varray_.size();
+    if (varray_.is_span()) {
+      this->data_ = varray_.get_internal_span().data();
+    }
+    else {
+      if (copy_values_to_span) {
+        owned_data_.~Array();
+        new (&owned_data_) Array<T>(varray_.size(), NoInitialization{});
+        varray_.materialize_to_uninitialized(owned_data_);
+      }
+      else {
+        owned_data_.reinitialize(varray_.size());
+      }
+      this->data_ = owned_data_.data();
+    }
+  }
+
+  ~VMutableArray_Span()
+  {
+    if (show_not_saved_warning_) {
+      if (!save_has_been_called_) {
+        std::cout << "Warning: Call `save()` to make sure that changes persist in all cases.\n";
+      }
+    }
+  }
+
+  /* Write back all values from a temporary allocated array to the underlying virtual array. */
+  void save()
+  {
+    save_has_been_called_ = true;
+    if (this->data_ != owned_data_.data()) {
+      return;
+    }
+    varray_.set_all(owned_data_);
+  }
+
+  void disable_not_applied_warning()
+  {
+    show_not_saved_warning_ = false;
+  }
+};
+
+/**
+ * This class makes it easy to create a virtual array for an existing function or lambda. The
+ * `GetFunc` should take a single `index` argument and return the value at that index.
+ */
+template<typename T, typename GetFunc> class VArray_For_Func final : public VArray<T> {
+ private:
+  GetFunc get_func_;
+
+ public:
+  VArray_For_Func(const int64_t size, GetFunc get_func)
+      : VArray<T>(size), get_func_(std::move(get_func))
+  {
+  }
+
+ private:
+  T get_impl(const int64_t index) const override
+  {
+    return get_func_(index);
+  }
+};
+
+template<typename StructT, typename ElemT, ElemT (*GetFunc)(const StructT &)>
+class VArray_For_DerivedSpan : public VArray<ElemT> {
+ private:
+  const StructT *data_;
+
+ public:
+  VArray_For_DerivedSpan(const Span<StructT> data) : VArray<ElemT>(data.size()), data_(data.data())
+  {
+  }
+
+ private:
+  ElemT get_impl(const int64_t index) const override
+  {
+    return GetFunc(data_[index]);
+  }
+};
+
+template<typename StructT,
+         typename ElemT,
+         ElemT (*GetFunc)(const StructT &),
+         void (*SetFunc)(StructT &, ElemT)>
+class VMutableArray_For_DerivedSpan : public VMutableArray<ElemT> {
+ private:
+  StructT *data_;
+
+ public:
+  VMutableArray_For_DerivedSpan(const MutableSpan<StructT> data)
+      : VMutableArray<ElemT>(data.size()), data_(data.data())
+  {
+  }
+
+ private:
+  ElemT get_impl(const int64_t index) const override
+  {
+    return GetFunc(data_[index]);
+  }
+
+  void set_impl(const int64_t index, ElemT value) override
+  {
+    SetFunc(data_[index], std::move(value));
+  }
+};
+
+/**
  * Generate multiple versions of the given function optimized for different virtual arrays.
  * One has to be careful with nesting multiple devirtualizations, because that results in an
  * exponential number of function instantiations (increasing compile time and binary size).
@@ -229,14 +550,14 @@ inline void devirtualize_varray(const VArray<T> &varray, const Func &func, bool
   /* Support disabling the devirtualization to simplify benchmarking. */
   if (enable) {
     if (varray.is_single()) {
-      /* `VArrayForSingle` can be used for devirtualization, because it is declared `final`. */
-      const VArrayForSingle<T> varray_single{varray.get_single(), varray.size()};
+      /* `VArray_For_Single` can be used for devirtualization, because it is declared `final`. */
+      const VArray_For_Single<T> varray_single{varray.get_internal_single(), varray.size()};
       func(varray_single);
       return;
     }
     if (varray.is_span()) {
-      /* `VArrayForSpan` can be used for devirtualization, because it is declared `final`. */
-      const VArrayForSpan<T> varray_span{varray.get_span()};
+      /* `VArray_For_Span` can be used for devirtualization, because it is declared `final`. */
+      const VArray_For_Span<T> varray_span{varray.get_internal_span()};
       func(varray_span);
       return;
     }
@@ -262,26 +583,26 @@ inline void devirtualize_varray2(const VArray<T1> &varray1,
     const bool is_single1 = varray1.is_single();
     const bool is_single2 = varray2.is_single();
     if (is_span1 && is_span2) {
-      const VArrayForSpan<T1> varray1_span{varray1.get_span()};
-      const VArrayForSpan<T2> varray2_span{varray2.get_span()};
+      const VArray_For_Span<T1> varray1_span{varray1.get_internal_span()};
+      const VArray_For_Span<T2> varray2_span{varray2.get_internal_span()};
       func(varray1_span, varray2_span);
       return;
     }
     if (is_span1 && is_single2) {
-      const VArrayForSpan<T1> varray1_span{varray1.get_span()};
-      const VArrayForSingle<T2> varray2_single{varray2.get_single(), varray2.size()};
+      const VArray_For_Span<T1> varray1_span{varray1.get_internal_span()};
+      const VArray_For_Single<T2> varray2_single{varray2.get_internal_single(), varray2.size()};
       func(varray1_span, varray2_single);
       return;
     }
     if (is_single1 && is_span2) {
-      const VArrayForSingle<T1> varray1_single{varray1.get_single(), varray1.size()};
-      const VArrayForSpan<T2> varray2_span{varray2.get_span()};
+      const VArray_For_Single<T1> varray1_single{varray1.get_internal_single(), varray1.size()};
+      const VArray_For_Span<T2> varray2_span{varray2.get_internal_span()};
       func(varray1_single, varray2_span);
       return;
     }
     if (is_single1 && is_single2) {
-      const VArrayForSingle<T1> varray1_single{varray1.get_single(), varray1.size()};
-      const VArrayForSingle<T2> varray2_single{varray2.get_single(), varray2.size()};
+      const VArray_For_Single<T1> varray1_single{varray1.get_internal_single(), varray1.size()};
+      const VArray_For_Single<T2> varray2_single{varray2.get_internal_single(), varray2.size()};
       func(varray1_single, varray2_single);
       return;
     }