Functions: Run-time type system and index mask

This adds a new `CPPType` that encapsulates information about how to handle
instances of a specific data type. This is necessary for the function evaluation
system, which will be used to evaluate most of the particle node trees.

Furthermore, this adds an `IndexMask` class which offers a surprisingly useful
abstraction over an array containing unsigned integers. It makes two assumptions
about the underlying integer array:
* The integers are in ascending order.
* There are no duplicates.

`IndexMask` will be used to "select" certain particles that will be
processed in a data-oriented way. Sometimes, operations don't have to
be applied to all particles, but only some, those that are in the indexed by
the `IndexMask`. The two limitations imposed by an `IndexMask` allow for
better performance.

Reviewers: brecht

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

5 files changed, 379 insertions, 0 deletions

diff --git a/tests/gtests/CMakeLists.txt b/tests/gtests/CMakeLists.txt
index c02bad471ff..0dfe041974e 100644
--- a/tests/gtests/CMakeLists.txt
+++ b/tests/gtests/CMakeLists.txt
@@ -17,6 +17,7 @@ if(WITH_GTESTS)
   add_subdirectory(blenloader)
   add_subdirectory(guardedalloc)
   add_subdirectory(bmesh)
+  add_subdirectory(functions)
   if(WITH_CODEC_FFMPEG)
     add_subdirectory(ffmpeg)
   endif()
diff --git a/tests/gtests/blenlib/BLI_index_mask_test.cc b/tests/gtests/blenlib/BLI_index_mask_test.cc
new file mode 100644
index 00000000000..057aed091a1
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_index_mask_test.cc
@@ -0,0 +1,39 @@
+#include "BLI_index_mask.hh"
+#include "testing/testing.h"
+
+using namespace BLI;
+
+TEST(index_mask, DefaultConstructor)
+{
+  IndexMask mask;
+  EXPECT_EQ(mask.min_array_size(), 0);
+  EXPECT_EQ(mask.size(), 0);
+}
+
+TEST(index_mask, ArrayConstructor)
+{
+  [](IndexMask mask) {
+    EXPECT_EQ(mask.size(), 4);
+    EXPECT_EQ(mask.min_array_size(), 8);
+    EXPECT_FALSE(mask.is_range());
+    EXPECT_EQ(mask[0], 3);
+    EXPECT_EQ(mask[1], 5);
+    EXPECT_EQ(mask[2], 6);
+    EXPECT_EQ(mask[3], 7);
+  }({3, 5, 6, 7});
+}
+
+TEST(index_mask, RangeConstructor)
+{
+  IndexMask mask = IndexRange(3, 5);
+  EXPECT_EQ(mask.size(), 5);
+  EXPECT_EQ(mask.min_array_size(), 8);
+  EXPECT_EQ(mask.last(), 7);
+  EXPECT_TRUE(mask.is_range());
+  EXPECT_EQ(mask.as_range().first(), 3);
+  EXPECT_EQ(mask.as_range().last(), 7);
+  ArrayRef<uint> indices = mask.indices();
+  EXPECT_EQ(indices[0], 3);
+  EXPECT_EQ(indices[1], 4);
+  EXPECT_EQ(indices[2], 5);
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index 6fbb304581d..fd0dca37bf6 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -50,6 +50,7 @@ BLENDER_TEST(BLI_ghash "bf_blenlib")
 BLENDER_TEST(BLI_hash_mm2a "bf_blenlib")
 BLENDER_TEST(BLI_heap "bf_blenlib")
 BLENDER_TEST(BLI_heap_simple "bf_blenlib")
+BLENDER_TEST(BLI_index_mask "bf_blenlib")
 BLENDER_TEST(BLI_index_range "bf_blenlib")
 BLENDER_TEST(BLI_kdopbvh "bf_blenlib;bf_intern_numaapi")
 BLENDER_TEST(BLI_linear_allocator "bf_blenlib")
diff --git a/tests/gtests/functions/CMakeLists.txt b/tests/gtests/functions/CMakeLists.txt
new file mode 100644
index 00000000000..413761ed0c8
--- /dev/null
+++ b/tests/gtests/functions/CMakeLists.txt
@@ -0,0 +1,39 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# 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.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC
+  .
+  ..
+  ../../../source/blender/blenlib
+  ../../../source/blender/functions
+  ../../../source/blender/makesdna
+  ../../../intern/guardedalloc
+)
+
+setup_libdirs()
+include_directories(${INC})
+
+
+set(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${PLATFORM_LINKFLAGS}")
+set(CMAKE_EXE_LINKER_FLAGS_DEBUG "${CMAKE_EXE_LINKER_FLAGS_DEBUG} ${PLATFORM_LINKFLAGS_DEBUG}")
+
+if(WITH_BUILDINFO)
+  set(BUILDINFO buildinfoobj)
+endif()
+
+BLENDER_TEST(FN_cpp_type "bf_blenlib;bf_functions;${BUILDINFO}")
diff --git a/tests/gtests/functions/FN_cpp_type_test.cc b/tests/gtests/functions/FN_cpp_type_test.cc
new file mode 100644
index 00000000000..ca8583bdc92
--- /dev/null
+++ b/tests/gtests/functions/FN_cpp_type_test.cc
@@ -0,0 +1,299 @@
+/*
+ * 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_type.hh"
+
+static const int default_constructed_value = 1;
+static const int copy_constructed_value = 2;
+static const int move_constructed_value = 3;
+static const int copy_constructed_from_value = 4;
+static const int move_constructed_from_value = 5;
+static const int copy_assigned_value = 6;
+static const int copy_assigned_from_value = 7;
+static const int move_assigned_value = 8;
+static const int move_assigned_from_value = 9;
+static const int destructed_value = 10;
+
+struct TestType {
+  mutable volatile int value;
+
+  TestType()
+  {
+    value = default_constructed_value;
+  }
+
+  ~TestType()
+  {
+    value = destructed_value;
+  }
+
+  TestType(const TestType &other)
+  {
+    value = copy_constructed_value;
+    other.value = copy_constructed_from_value;
+  }
+
+  TestType(TestType &&other)
+  {
+    value = move_constructed_value;
+    other.value = move_constructed_from_value;
+  }
+
+  TestType &operator=(const TestType &other)
+  {
+    value = copy_assigned_value;
+    other.value = copy_assigned_from_value;
+    return *this;
+  }
+
+  TestType &operator=(TestType &&other)
+  {
+    value = move_assigned_value;
+    other.value = move_assigned_from_value;
+    return *this;
+  }
+};
+
+MAKE_CPP_TYPE(TestType, TestType)
+
+TEST(cpp_type, Size)
+{
+  EXPECT_EQ(CPPType_TestType.size(), sizeof(TestType));
+}
+
+TEST(cpp_type, Alignment)
+{
+  EXPECT_EQ(CPPType_TestType.alignment(), alignof(TestType));
+}
+
+TEST(cpp_type, DefaultConstruction)
+{
+  int buffer[10] = {0};
+  CPPType_TestType.construct_default((void *)buffer);
+  EXPECT_EQ(buffer[0], default_constructed_value);
+  EXPECT_EQ(buffer[1], 0);
+  CPPType_TestType.construct_default_n((void *)buffer, 3);
+  EXPECT_EQ(buffer[0], default_constructed_value);
+  EXPECT_EQ(buffer[1], default_constructed_value);
+  EXPECT_EQ(buffer[2], default_constructed_value);
+  EXPECT_EQ(buffer[3], 0);
+  CPPType_TestType.construct_default_indices((void *)buffer, {2, 5, 7});
+  EXPECT_EQ(buffer[2], default_constructed_value);
+  EXPECT_EQ(buffer[4], 0);
+  EXPECT_EQ(buffer[5], default_constructed_value);
+  EXPECT_EQ(buffer[6], 0);
+  EXPECT_EQ(buffer[7], default_constructed_value);
+  EXPECT_EQ(buffer[8], 0);
+}
+
+TEST(cpp_type, Destruct)
+{
+  int buffer[10] = {0};
+  CPPType_TestType.destruct((void *)buffer);
+  EXPECT_EQ(buffer[0], destructed_value);
+  EXPECT_EQ(buffer[1], 0);
+  CPPType_TestType.destruct_n((void *)buffer, 3);
+  EXPECT_EQ(buffer[0], destructed_value);
+  EXPECT_EQ(buffer[1], destructed_value);
+  EXPECT_EQ(buffer[2], destructed_value);
+  EXPECT_EQ(buffer[3], 0);
+  CPPType_TestType.destruct_indices((void *)buffer, {2, 5, 7});
+  EXPECT_EQ(buffer[2], destructed_value);
+  EXPECT_EQ(buffer[4], 0);
+  EXPECT_EQ(buffer[5], destructed_value);
+  EXPECT_EQ(buffer[6], 0);
+  EXPECT_EQ(buffer[7], destructed_value);
+  EXPECT_EQ(buffer[8], 0);
+}
+
+TEST(cpp_type, CopyToUninitialized)
+{
+  int buffer1[10] = {0};
+  int buffer2[10] = {0};
+  CPPType_TestType.copy_to_uninitialized((void *)buffer1, (void *)buffer2);
+  EXPECT_EQ(buffer1[0], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[0], copy_constructed_value);
+  CPPType_TestType.copy_to_uninitialized_n((void *)buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1[0], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[0], copy_constructed_value);
+  EXPECT_EQ(buffer1[1], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[1], copy_constructed_value);
+  EXPECT_EQ(buffer1[2], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[2], copy_constructed_value);
+  EXPECT_EQ(buffer1[3], 0);
+  EXPECT_EQ(buffer2[3], 0);
+  CPPType_TestType.copy_to_uninitialized_indices((void *)buffer1, (void *)buffer2, {2, 5, 7});
+  EXPECT_EQ(buffer1[2], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[2], copy_constructed_value);
+  EXPECT_EQ(buffer1[4], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer1[5], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[5], copy_constructed_value);
+  EXPECT_EQ(buffer1[6], 0);
+  EXPECT_EQ(buffer2[6], 0);
+  EXPECT_EQ(buffer1[7], copy_constructed_from_value);
+  EXPECT_EQ(buffer2[7], copy_constructed_value);
+  EXPECT_EQ(buffer1[8], 0);
+  EXPECT_EQ(buffer2[8], 0);
+}
+
+TEST(cpp_type, CopyToInitialized)
+{
+  int buffer1[10] = {0};
+  int buffer2[10] = {0};
+  CPPType_TestType.copy_to_initialized((void *)buffer1, (void *)buffer2);
+  EXPECT_EQ(buffer1[0], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[0], copy_assigned_value);
+  CPPType_TestType.copy_to_initialized_n((void *)buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1[0], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[0], copy_assigned_value);
+  EXPECT_EQ(buffer1[1], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[1], copy_assigned_value);
+  EXPECT_EQ(buffer1[2], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[2], copy_assigned_value);
+  EXPECT_EQ(buffer1[3], 0);
+  EXPECT_EQ(buffer2[3], 0);
+  CPPType_TestType.copy_to_initialized_indices((void *)buffer1, (void *)buffer2, {2, 5, 7});
+  EXPECT_EQ(buffer1[2], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[2], copy_assigned_value);
+  EXPECT_EQ(buffer1[4], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer1[5], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[5], copy_assigned_value);
+  EXPECT_EQ(buffer1[6], 0);
+  EXPECT_EQ(buffer2[6], 0);
+  EXPECT_EQ(buffer1[7], copy_assigned_from_value);
+  EXPECT_EQ(buffer2[7], copy_assigned_value);
+  EXPECT_EQ(buffer1[8], 0);
+  EXPECT_EQ(buffer2[8], 0);
+}
+
+TEST(cpp_type, RelocateToUninitialized)
+{
+  int buffer1[10] = {0};
+  int buffer2[10] = {0};
+  CPPType_TestType.relocate_to_uninitialized((void *)buffer1, (void *)buffer2);
+  EXPECT_EQ(buffer1[0], destructed_value);
+  EXPECT_EQ(buffer2[0], move_constructed_value);
+  CPPType_TestType.relocate_to_uninitialized_n((void *)buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1[0], destructed_value);
+  EXPECT_EQ(buffer2[0], move_constructed_value);
+  EXPECT_EQ(buffer1[1], destructed_value);
+  EXPECT_EQ(buffer2[1], move_constructed_value);
+  EXPECT_EQ(buffer1[2], destructed_value);
+  EXPECT_EQ(buffer2[2], move_constructed_value);
+  EXPECT_EQ(buffer1[3], 0);
+  EXPECT_EQ(buffer2[3], 0);
+  CPPType_TestType.relocate_to_uninitialized_indices((void *)buffer1, (void *)buffer2, {2, 5, 7});
+  EXPECT_EQ(buffer1[2], destructed_value);
+  EXPECT_EQ(buffer2[2], move_constructed_value);
+  EXPECT_EQ(buffer1[4], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer1[5], destructed_value);
+  EXPECT_EQ(buffer2[5], move_constructed_value);
+  EXPECT_EQ(buffer1[6], 0);
+  EXPECT_EQ(buffer2[6], 0);
+  EXPECT_EQ(buffer1[7], destructed_value);
+  EXPECT_EQ(buffer2[7], move_constructed_value);
+  EXPECT_EQ(buffer1[8], 0);
+  EXPECT_EQ(buffer2[8], 0);
+}
+
+TEST(cpp_type, RelocateToInitialized)
+{
+  int buffer1[10] = {0};
+  int buffer2[10] = {0};
+  CPPType_TestType.relocate_to_initialized((void *)buffer1, (void *)buffer2);
+  EXPECT_EQ(buffer1[0], destructed_value);
+  EXPECT_EQ(buffer2[0], move_assigned_value);
+  CPPType_TestType.relocate_to_initialized_n((void *)buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1[0], destructed_value);
+  EXPECT_EQ(buffer2[0], move_assigned_value);
+  EXPECT_EQ(buffer1[1], destructed_value);
+  EXPECT_EQ(buffer2[1], move_assigned_value);
+  EXPECT_EQ(buffer1[2], destructed_value);
+  EXPECT_EQ(buffer2[2], move_assigned_value);
+  EXPECT_EQ(buffer1[3], 0);
+  EXPECT_EQ(buffer2[3], 0);
+  CPPType_TestType.relocate_to_initialized_indices((void *)buffer1, (void *)buffer2, {2, 5, 7});
+  EXPECT_EQ(buffer1[2], destructed_value);
+  EXPECT_EQ(buffer2[2], move_assigned_value);
+  EXPECT_EQ(buffer1[4], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer1[5], destructed_value);
+  EXPECT_EQ(buffer2[5], move_assigned_value);
+  EXPECT_EQ(buffer1[6], 0);
+  EXPECT_EQ(buffer2[6], 0);
+  EXPECT_EQ(buffer1[7], destructed_value);
+  EXPECT_EQ(buffer2[7], move_assigned_value);
+  EXPECT_EQ(buffer1[8], 0);
+  EXPECT_EQ(buffer2[8], 0);
+}
+
+TEST(cpp_type, FillInitialized)
+{
+  int buffer1 = 0;
+  int buffer2[10] = {0};
+  CPPType_TestType.fill_initialized((void *)&buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1, copy_assigned_from_value);
+  EXPECT_EQ(buffer2[0], copy_assigned_value);
+  EXPECT_EQ(buffer2[1], copy_assigned_value);
+  EXPECT_EQ(buffer2[2], copy_assigned_value);
+  EXPECT_EQ(buffer2[3], 0);
+
+  buffer1 = 0;
+  CPPType_TestType.fill_initialized_indices((void *)&buffer1, (void *)buffer2, {1, 6, 8});
+  EXPECT_EQ(buffer1, copy_assigned_from_value);
+  EXPECT_EQ(buffer2[0], copy_assigned_value);
+  EXPECT_EQ(buffer2[1], copy_assigned_value);
+  EXPECT_EQ(buffer2[2], copy_assigned_value);
+  EXPECT_EQ(buffer2[3], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer2[5], 0);
+  EXPECT_EQ(buffer2[6], copy_assigned_value);
+  EXPECT_EQ(buffer2[7], 0);
+  EXPECT_EQ(buffer2[8], copy_assigned_value);
+  EXPECT_EQ(buffer2[9], 0);
+}
+
+TEST(cpp_type, FillUninitialized)
+{
+  int buffer1 = 0;
+  int buffer2[10] = {0};
+  CPPType_TestType.fill_uninitialized((void *)&buffer1, (void *)buffer2, 3);
+  EXPECT_EQ(buffer1, copy_constructed_from_value);
+  EXPECT_EQ(buffer2[0], copy_constructed_value);
+  EXPECT_EQ(buffer2[1], copy_constructed_value);
+  EXPECT_EQ(buffer2[2], copy_constructed_value);
+  EXPECT_EQ(buffer2[3], 0);
+
+  buffer1 = 0;
+  CPPType_TestType.fill_uninitialized_indices((void *)&buffer1, (void *)buffer2, {1, 6, 8});
+  EXPECT_EQ(buffer1, copy_constructed_from_value);
+  EXPECT_EQ(buffer2[0], copy_constructed_value);
+  EXPECT_EQ(buffer2[1], copy_constructed_value);
+  EXPECT_EQ(buffer2[2], copy_constructed_value);
+  EXPECT_EQ(buffer2[3], 0);
+  EXPECT_EQ(buffer2[4], 0);
+  EXPECT_EQ(buffer2[5], 0);
+  EXPECT_EQ(buffer2[6], copy_constructed_value);
+  EXPECT_EQ(buffer2[7], 0);
+  EXPECT_EQ(buffer2[8], copy_constructed_value);
+  EXPECT_EQ(buffer2[9], 0);
+}