Geometry Nodes: refactor virtual array system

Goals of this refactor:
* Simplify creating virtual arrays.
* Simplify passing virtual arrays around.
* Simplify converting between typed and generic virtual arrays.
* Reduce memory allocations.

As a quick reminder, a virtual arrays is a data structure that behaves like an
array (i.e. it can be accessed using an index). However, it may not actually
be stored as array internally. The two most important implementations
of virtual arrays are those that correspond to an actual plain array and those
that have the same value for every index. However, many more
implementations exist for various reasons (interfacing with legacy attributes,
unified iterator over all points in multiple splines, ...).

With this refactor the core types (`VArray`, `GVArray`, `VMutableArray` and
`GVMutableArray`) can be used like "normal values". They typically live
on the stack. Before, they were usually inside a `std::unique_ptr`. This makes
passing them around much easier. Creation of new virtual arrays is also
much simpler now due to some constructors. Memory allocations are
reduced by making use of small object optimization inside the core types.

Previously, `VArray` was a class with virtual methods that had to be overridden
to change the behavior of a the virtual array. Now,`VArray` has a fixed size
and has no virtual methods. Instead it contains a `VArrayImpl` that is
similar to the old `VArray`. `VArrayImpl` should rarely ever be used directly,
unless a new virtual array implementation is added.

To support the small object optimization for many `VArrayImpl` classes,
a new `blender::Any` type is added. It is similar to `std::any` with two
additional features. It has an adjustable inline buffer size and alignment.
The inline buffer size of `std::any` can't be relied on and is usually too
small for our use case here. Furthermore, `blender::Any` can store
additional user-defined type information without increasing the
stack size.

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

2 files changed, 150 insertions, 13 deletions

diff --git a/source/blender/blenlib/tests/BLI_any_test.cc b/source/blender/blenlib/tests/BLI_any_test.cc
new file mode 100644
index 00000000000..226088cf3c7
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_any_test.cc
@@ -0,0 +1,108 @@
+/* Apache License, Version 2.0 */
+
+#include "BLI_any.hh"
+#include "BLI_map.hh"
+
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(any, DefaultConstructor)
+{
+  Any a;
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(any, AssignInt)
+{
+  Any<> a = 5;
+  EXPECT_TRUE(a.has_value());
+  EXPECT_TRUE(a.is<int>());
+  EXPECT_FALSE(a.is<float>());
+  const int &value = a.get<int>();
+  EXPECT_EQ(value, 5);
+  a = 10;
+  EXPECT_EQ(value, 10);
+
+  Any b = a;
+  EXPECT_TRUE(b.has_value());
+  EXPECT_EQ(b.get<int>(), 10);
+
+  Any c = std::move(a);
+  EXPECT_TRUE(c);
+  EXPECT_EQ(c.get<int>(), 10);
+
+  EXPECT_EQ(a.get<int>(), 10); /* NOLINT: bugprone-use-after-move */
+
+  a.reset();
+  EXPECT_FALSE(a);
+}
+
+TEST(any, AssignMap)
+{
+  Any<> a = Map<int, int>();
+  EXPECT_TRUE(a.has_value());
+  EXPECT_TRUE((a.is<Map<int, int>>()));
+  EXPECT_FALSE((a.is<Map<int, float>>()));
+  Map<int, int> &map = a.get<Map<int, int>>();
+  map.add(4, 2);
+  EXPECT_EQ((a.get<Map<int, int>>().lookup(4)), 2);
+
+  Any b = a;
+  EXPECT_TRUE(b);
+  EXPECT_EQ((b.get<Map<int, int>>().lookup(4)), 2);
+
+  Any c = std::move(a);
+  c = c;
+  EXPECT_TRUE(b);
+  EXPECT_EQ((c.get<Map<int, int>>().lookup(4)), 2);
+
+  EXPECT_TRUE((a.get<Map<int, int>>().is_empty())); /* NOLINT: bugprone-use-after-move */
+}
+
+TEST(any, AssignAny)
+{
+  Any<> a = 5;
+  Any<> b = std::string("hello");
+  Any c;
+
+  Any z;
+  EXPECT_FALSE(z.has_value());
+
+  z = a;
+  EXPECT_TRUE(z.has_value());
+  EXPECT_EQ(z.get<int>(), 5);
+
+  z = b;
+  EXPECT_EQ(z.get<std::string>(), "hello");
+
+  z = c;
+  EXPECT_FALSE(z.has_value());
+
+  z = Any(std::in_place_type<Any<>>, a);
+  EXPECT_FALSE(z.is<int>());
+  EXPECT_TRUE(z.is<Any<>>());
+  EXPECT_EQ(z.get<Any<>>().get<int>(), 5);
+}
+
+struct ExtraSizeInfo {
+  size_t size;
+
+  template<typename T> static ExtraSizeInfo get()
+  {
+    return {sizeof(T)};
+  }
+};
+
+TEST(any, ExtraInfo)
+{
+  using MyAny = Any<ExtraSizeInfo>;
+
+  MyAny a = 5;
+  EXPECT_EQ(a.extra_info().size, sizeof(int));
+
+  a = std::string("hello");
+  EXPECT_EQ(a.extra_info().size, sizeof(std::string));
+}
+
+}  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_virtual_array_test.cc b/source/blender/blenlib/tests/BLI_virtual_array_test.cc
index a6d2ca10315..7a548e7c434 100644
--- a/source/blender/blenlib/tests/BLI_virtual_array_test.cc
+++ b/source/blender/blenlib/tests/BLI_virtual_array_test.cc
@@ -12,7 +12,7 @@ namespace blender::tests {
 TEST(virtual_array, Span)
 {
   std::array<int, 5> data = {3, 4, 5, 6, 7};
-  VArray_For_Span<int> varray{data};
+  VArray<int> varray = VArray<int>::ForSpan(data);
   EXPECT_EQ(varray.size(), 5);
   EXPECT_EQ(varray.get(0), 3);
   EXPECT_EQ(varray.get(4), 7);
@@ -23,7 +23,7 @@ TEST(virtual_array, Span)
 
 TEST(virtual_array, Single)
 {
-  VArray_For_Single<int> varray{10, 4};
+  VArray<int> varray = VArray<int>::ForSingle(10, 4);
   EXPECT_EQ(varray.size(), 4);
   EXPECT_EQ(varray.get(0), 10);
   EXPECT_EQ(varray.get(3), 10);
@@ -35,7 +35,7 @@ TEST(virtual_array, Array)
 {
   Array<int> array = {1, 2, 3, 5, 8};
   {
-    VArray_For_ArrayContainer varray{array};
+    VArray<int> varray = VArray<int>::ForContainer(array);
     EXPECT_EQ(varray.size(), 5);
     EXPECT_EQ(varray[0], 1);
     EXPECT_EQ(varray[2], 3);
@@ -43,7 +43,7 @@ TEST(virtual_array, Array)
     EXPECT_TRUE(varray.is_span());
   }
   {
-    VArray_For_ArrayContainer varray{std::move(array)};
+    VArray<int> varray = VArray<int>::ForContainer(std::move(array));
     EXPECT_EQ(varray.size(), 5);
     EXPECT_EQ(varray[0], 1);
     EXPECT_EQ(varray[2], 3);
@@ -51,7 +51,7 @@ TEST(virtual_array, Array)
     EXPECT_TRUE(varray.is_span());
   }
   {
-    VArray_For_ArrayContainer varray{array}; /* NOLINT: bugprone-use-after-move */
+    VArray<int> varray = VArray<int>::ForContainer(array); /* NOLINT: bugprone-use-after-move */
     EXPECT_TRUE(varray.is_empty());
   }
 }
@@ -59,7 +59,7 @@ TEST(virtual_array, Array)
 TEST(virtual_array, Vector)
 {
   Vector<int> vector = {9, 8, 7, 6};
-  VArray_For_ArrayContainer varray{std::move(vector)};
+  VArray<int> varray = VArray<int>::ForContainer(std::move(vector));
   EXPECT_EQ(varray.size(), 4);
   EXPECT_EQ(varray[0], 9);
   EXPECT_EQ(varray[3], 6);
@@ -68,7 +68,7 @@ TEST(virtual_array, Vector)
 TEST(virtual_array, StdVector)
 {
   std::vector<int> vector = {5, 6, 7, 8};
-  VArray_For_ArrayContainer varray{std::move(vector)};
+  VArray<int> varray = VArray<int>::ForContainer(std::move(vector));
   EXPECT_EQ(varray.size(), 4);
   EXPECT_EQ(varray[0], 5);
   EXPECT_EQ(varray[1], 6);
@@ -77,7 +77,7 @@ TEST(virtual_array, StdVector)
 TEST(virtual_array, StdArray)
 {
   std::array<int, 4> array = {2, 3, 4, 5};
-  VArray_For_ArrayContainer varray{array};
+  VArray<int> varray = VArray<int>::ForContainer(std::move(array));
   EXPECT_EQ(varray.size(), 4);
   EXPECT_EQ(varray[0], 2);
   EXPECT_EQ(varray[1], 3);
@@ -86,7 +86,7 @@ TEST(virtual_array, StdArray)
 TEST(virtual_array, VectorSet)
 {
   VectorSet<int> vector_set = {5, 3, 7, 3, 3, 5, 1};
-  VArray_For_ArrayContainer varray{std::move(vector_set)};
+  VArray<int> varray = VArray<int>::ForContainer(std::move(vector_set));
   EXPECT_TRUE(vector_set.is_empty()); /* NOLINT: bugprone-use-after-move. */
   EXPECT_EQ(varray.size(), 4);
   EXPECT_EQ(varray[0], 5);
@@ -98,7 +98,7 @@ TEST(virtual_array, VectorSet)
 TEST(virtual_array, Func)
 {
   auto func = [](int64_t index) { return (int)(index * index); };
-  VArray_For_Func<int, decltype(func)> varray{10, func};
+  VArray<int> varray = VArray<int>::ForFunc(10, func);
   EXPECT_EQ(varray.size(), 10);
   EXPECT_EQ(varray[0], 0);
   EXPECT_EQ(varray[3], 9);
@@ -108,7 +108,7 @@ TEST(virtual_array, Func)
 TEST(virtual_array, AsSpan)
 {
   auto func = [](int64_t index) { return (int)(10 * index); };
-  VArray_For_Func<int, decltype(func)> func_varray{10, func};
+  VArray<int> func_varray = VArray<int>::ForFunc(10, func);
   VArray_Span span_varray{func_varray};
   EXPECT_EQ(span_varray.size(), 10);
   Span<int> span = span_varray;
@@ -134,13 +134,14 @@ TEST(virtual_array, DerivedSpan)
   vector.append({3, 4, 5});
   vector.append({1, 1, 1});
   {
-    VArray_For_DerivedSpan<std::array<int, 3>, int, get_x> varray{vector};
+    VArray<int> varray = VArray<int>::ForDerivedSpan<std::array<int, 3>, get_x>(vector);
     EXPECT_EQ(varray.size(), 2);
     EXPECT_EQ(varray[0], 3);
     EXPECT_EQ(varray[1], 1);
   }
   {
-    VMutableArray_For_DerivedSpan<std::array<int, 3>, int, get_x, set_x> varray{vector};
+    VMutableArray<int> varray =
+        VMutableArray<int>::ForDerivedSpan<std::array<int, 3>, get_x, set_x>(vector);
     EXPECT_EQ(varray.size(), 2);
     EXPECT_EQ(varray[0], 3);
     EXPECT_EQ(varray[1], 1);
@@ -151,4 +152,32 @@ TEST(virtual_array, DerivedSpan)
   }
 }
 
+TEST(virtual_array, MutableToImmutable)
+{
+  std::array<int, 4> array = {4, 2, 6, 4};
+  {
+    VMutableArray<int> mutable_varray = VMutableArray<int>::ForSpan(array);
+    VArray<int> varray = mutable_varray;
+    EXPECT_TRUE(varray.is_span());
+    EXPECT_EQ(varray.size(), 4);
+    EXPECT_EQ(varray[1], 2);
+    EXPECT_EQ(mutable_varray.size(), 4);
+  }
+  {
+    VMutableArray<int> mutable_varray = VMutableArray<int>::ForSpan(array);
+    EXPECT_EQ(mutable_varray.size(), 4);
+    VArray<int> varray = std::move(mutable_varray);
+    EXPECT_TRUE(varray.is_span());
+    EXPECT_EQ(varray.size(), 4);
+    EXPECT_EQ(varray[1], 2);
+    EXPECT_EQ(mutable_varray.size(), 0);
+  }
+  {
+    VArray<int> varray = VMutableArray<int>::ForSpan(array);
+    EXPECT_TRUE(varray.is_span());
+    EXPECT_EQ(varray.size(), 4);
+    EXPECT_EQ(varray[1], 2);
+  }
+}
+
 }  // namespace blender::tests