Merge branch 'master' into temp-chunk-list

13 files changed, 383 insertions, 16 deletions

diff --git a/source/blender/blenlib/BLI_array_utils.hh b/source/blender/blenlib/BLI_array_utils.hh
new file mode 100644
index 00000000000..cf2f948b0b4
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_utils.hh
@@ -0,0 +1,35 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+#include "BLI_generic_span.hh"
+#include "BLI_generic_virtual_array.hh"
+#include "BLI_index_mask.hh"
+#include "BLI_task.hh"
+
+namespace blender::array_utils {
+
+/**
+ * Fill the destination span by copying masked values from the `src` array. Threaded based on
+ * grain-size.
+ */
+void copy(const GVArray &src, IndexMask selection, GMutableSpan dst, int64_t grain_size = 4096);
+
+/**
+ * Fill the destination span by copying values from the `src` array. Threaded based on
+ * grain-size.
+ */
+template<typename T>
+inline void copy(const Span<T> src,
+                 const IndexMask selection,
+                 MutableSpan<T> dst,
+                 const int64_t grain_size = 4096)
+{
+  threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) {
+    for (const int64_t index : selection.slice(range)) {
+      dst[index] = src[index];
+    }
+  });
+}
+
+}  // namespace blender::array_utils
diff --git a/source/blender/blenlib/BLI_compute_context.hh b/source/blender/blenlib/BLI_compute_context.hh
new file mode 100644
index 00000000000..e3e5b6f9e85
--- /dev/null
+++ b/source/blender/blenlib/BLI_compute_context.hh
@@ -0,0 +1,173 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * When logging computed values, we generally want to know where the value was computed. For
+ * example, geometry nodes logs socket values so that they can be displayed in the ui. For that we
+ * can combine the logged value with a `ComputeContext`, which identifies the place where the value
+ * was computed.
+ *
+ * This is not a trivial problem because e.g. just storing a pointer to the socket a value
+ * belongs to is not enough. That's because the same socket may correspond to many different values
+ * when the socket is used in a node group that is used multiple times. In this case, not only does
+ * the socket have to be stored but also the entire nested node group path that led to the
+ * evaluation of the socket.
+ *
+ * Storing the entire "context path" for every logged value is not feasible, because that path can
+ * become quite long. So that would need much more memory, more compute overhead and makes it
+ * complicated to compare if two contexts are the same. If the identifier for a compute context
+ * would have a variable size, it would also be much harder to create a map from context to values.
+ *
+ * The solution implemented below uses the following key ideas:
+ * - Every compute context can be hashed to a unique fixed size value (`ComputeContextHash`). While
+ *   technically there could be hash collisions, the hashing algorithm has to be chosen to make
+ *   that practically impossible. This way an entire context path, possibly consisting of many
+ *   nested contexts, is represented by a single value that can be stored easily.
+ * - A nested compute context is build as singly linked list, where every compute context has a
+ *   pointer to the parent compute context. Note that a link in the other direction is not possible
+ *   because the same parent compute context may be used by many different children which possibly
+ *   run on different threads.
+ */
+
+#include "BLI_array.hh"
+#include "BLI_linear_allocator.hh"
+#include "BLI_stack.hh"
+#include "BLI_string_ref.hh"
+
+namespace blender {
+
+/**
+ * A hash that uniquely identifies a specific (non-fixed-size) compute context. The hash has to
+ * have enough bits to make collisions practically impossible.
+ */
+struct ComputeContextHash {
+  static constexpr int64_t HashSizeInBytes = 16;
+  uint64_t v1 = 0;
+  uint64_t v2 = 0;
+
+  uint64_t hash() const
+  {
+    return v1;
+  }
+
+  friend bool operator==(const ComputeContextHash &a, const ComputeContextHash &b)
+  {
+    return a.v1 == b.v1 && a.v2 == b.v2;
+  }
+
+  void mix_in(const void *data, int64_t len);
+
+  friend std::ostream &operator<<(std::ostream &stream, const ComputeContextHash &hash);
+};
+
+static_assert(sizeof(ComputeContextHash) == ComputeContextHash::HashSizeInBytes);
+
+/**
+ * Identifies the context in which a computation happens. This context can be used to identify
+ * values logged during the computation. For more details, see the comment at the top of the file.
+ *
+ * This class should be subclassed to implement specific contexts.
+ */
+class ComputeContext {
+ private:
+  /**
+   * Only used for debugging currently.
+   */
+  const char *static_type_;
+  /**
+   * Pointer to the context that this context is child of. That allows nesting compute contexts.
+   */
+  const ComputeContext *parent_ = nullptr;
+
+ protected:
+  /**
+   * The hash that uniquely identifies this context. It's a combined hash of this context as well
+   * as all the parent contexts.
+   */
+  ComputeContextHash hash_;
+
+ public:
+  ComputeContext(const char *static_type, const ComputeContext *parent)
+      : static_type_(static_type), parent_(parent)
+  {
+    if (parent != nullptr) {
+      hash_ = parent_->hash_;
+    }
+  }
+  virtual ~ComputeContext() = default;
+
+  const ComputeContextHash &hash() const
+  {
+    return hash_;
+  }
+
+  const char *static_type() const
+  {
+    return static_type_;
+  }
+
+  const ComputeContext *parent() const
+  {
+    return parent_;
+  }
+
+  /**
+   * Print the entire nested context stack.
+   */
+  void print_stack(std::ostream &stream, StringRef name) const;
+
+  /**
+   * Print information about this specific context. This has to be implemented by each subclass.
+   */
+  virtual void print_current_in_line(std::ostream &stream) const = 0;
+
+  friend std::ostream &operator<<(std::ostream &stream, const ComputeContext &compute_context);
+};
+
+/**
+ * Utility class to build a context stack in one place. This is typically used to get the hash that
+ * corresponds to a specific nested compute context, in order to look up corresponding logged
+ * values.
+ */
+class ComputeContextBuilder {
+ private:
+  LinearAllocator<> allocator_;
+  Stack<destruct_ptr<ComputeContext>> contexts_;
+
+ public:
+  bool is_empty() const
+  {
+    return contexts_.is_empty();
+  }
+
+  const ComputeContext *current() const
+  {
+    if (contexts_.is_empty()) {
+      return nullptr;
+    }
+    return contexts_.peek().get();
+  }
+
+  const ComputeContextHash hash() const
+  {
+    BLI_assert(!contexts_.is_empty());
+    return this->current()->hash();
+  }
+
+  template<typename T, typename... Args> void push(Args &&...args)
+  {
+    const ComputeContext *current = this->current();
+    destruct_ptr<T> context = allocator_.construct<T>(current, std::forward<Args>(args)...);
+    contexts_.push(std::move(context));
+  }
+
+  void pop()
+  {
+    contexts_.pop();
+  }
+};
+
+}  // namespace blender
diff --git a/source/blender/blenlib/BLI_generic_span.hh b/source/blender/blenlib/BLI_generic_span.hh
index 143ab235d2e..e7a08988c46 100644
--- a/source/blender/blenlib/BLI_generic_span.hh
+++ b/source/blender/blenlib/BLI_generic_span.hh
@@ -100,6 +100,34 @@ class GSpan {
   {
     return this->slice(range.start(), range.size());
   }
+
+  GSpan drop_front(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::max<int64_t>(0, size_ - n);
+    return GSpan(*type_, POINTER_OFFSET(data_, type_->size() * n), new_size);
+  }
+
+  GSpan drop_back(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::max<int64_t>(0, size_ - n);
+    return GSpan(*type_, data_, new_size);
+  }
+
+  GSpan take_front(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::min<int64_t>(size_, n);
+    return GSpan(*type_, data_, new_size);
+  }
+
+  GSpan take_back(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::min<int64_t>(size_, n);
+    return GSpan(*type_, POINTER_OFFSET(data_, type_->size() * (size_ - new_size)), new_size);
+  }
 };
 
 /**
@@ -199,6 +227,35 @@ class GMutableSpan {
     return this->slice(range.start(), range.size());
   }
 
+  GMutableSpan drop_front(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::max<int64_t>(0, size_ - n);
+    return GMutableSpan(*type_, POINTER_OFFSET(data_, type_->size() * n), new_size);
+  }
+
+  GMutableSpan drop_back(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::max<int64_t>(0, size_ - n);
+    return GMutableSpan(*type_, data_, new_size);
+  }
+
+  GMutableSpan take_front(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::min<int64_t>(size_, n);
+    return GMutableSpan(*type_, data_, new_size);
+  }
+
+  GMutableSpan take_back(const int64_t n) const
+  {
+    BLI_assert(n >= 0);
+    const int64_t new_size = std::min<int64_t>(size_, n);
+    return GMutableSpan(
+        *type_, POINTER_OFFSET(data_, type_->size() * (size_ - new_size)), new_size);
+  }
+
   /**
    * Copy all values from another span into this span. This invokes undefined behavior when the
    * destination contains uninitialized data and T is not trivially copy constructible.
diff --git a/source/blender/blenlib/BLI_multi_value_map.hh b/source/blender/blenlib/BLI_multi_value_map.hh
index 1fc5a797574..81b536e7d3c 100644
--- a/source/blender/blenlib/BLI_multi_value_map.hh
+++ b/source/blender/blenlib/BLI_multi_value_map.hh
@@ -115,6 +115,14 @@ template<typename Key, typename Value> class MultiValueMap {
   }
 
   /**
+   * Get the number of keys.
+   */
+  int64_t size() const
+  {
+    return map_.size();
+  }
+
+  /**
    * NOTE: This signature will change when the implementation changes.
    */
   typename MapType::ItemIterator items() const
diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h
index 75002f52d94..1e45e76afe1 100644
--- a/source/blender/blenlib/BLI_path_util.h
+++ b/source/blender/blenlib/BLI_path_util.h
@@ -84,10 +84,18 @@ void BLI_join_dirfile(char *__restrict dst,
  * Join multiple strings into a path, ensuring only a single path separator between each,
  * and trailing slash is kept.
  *
+ * \param path: The first patch which has special treatment,
+ * allowing `//` prefix which is kept intact unlike double-slashes which are stripped
+ * from the bounds of all other paths passed in.
+ * Passing in the following paths all result in the same output (`//a/b/c`):
+ * - `"//", "a", "b", "c"`.
+ * - `"//", "/a/", "/b/", "/c"`.
+ * - `"//a", "b/c"`.
+ *
  * \note If you want a trailing slash, add `SEP_STR` as the last path argument,
  * duplicate slashes will be cleaned up.
  */
-size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path_first, ...)
+size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path, ...)
     ATTR_NONNULL(1, 3) ATTR_SENTINEL(0);
 /**
  * Like Python's `os.path.basename()`
@@ -98,10 +106,10 @@ size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path_firs
 const char *BLI_path_basename(const char *path) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT;
 /**
  * Get an element of the path at an index, eg:
- * "/some/path/file.txt" where an index of:
- * - 0 or -3: "some"
- * - 1 or -2: "path"
- * - 2 or -1: "file.txt"
+ * `/some/path/file.txt` where an index of:
+ * - 0 or -3: `some`
+ * - 1 or -2: `path`
+ * - 2 or -1: `file.txt`
  *
  * Ignores multiple slashes at any point in the path (including start/end).
  */
@@ -357,8 +365,8 @@ void BLI_path_normalize_unc(char *path_16, int maxlen);
 /**
  * Appends a suffix to the string, fitting it before the extension
  *
- * string = Foo.png, suffix = 123, separator = _
- * Foo.png -> Foo_123.png
+ * string = `Foo.png`, suffix = `123`, separator = `_`.
+ * `Foo.png` -> `Foo_123.png`.
  *
  * \param string: original (and final) string
  * \param maxlen: Maximum length of string
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index 7f9470a9111..9f68795a4a2 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -589,7 +589,7 @@ extern "C" {
 
 /** Performs `offsetof(typeof(data), member) + sizeof((data)->member)` for non-gcc compilers. */
 #define OFFSETOF_STRUCT_AFTER(_struct, _member) \
-  ((((const char *)&((_struct)->_member)) - ((const char *)(_struct))) + \
+  ((size_t)(((const char *)&((_struct)->_member)) - ((const char *)(_struct))) + \
    sizeof((_struct)->_member))
 
 /**
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 9e5ad4d9efe..a82a86183d0 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -23,7 +23,6 @@ set(INC_SYS
 )
 
 set(SRC
-  intern/BLI_args.c
   intern/BLI_array.c
   intern/BLI_assert.c
   intern/BLI_color.cc
@@ -48,11 +47,13 @@ set(SRC
   intern/array_store.c
   intern/array_store_utils.c
   intern/array_utils.c
+  intern/array_utils.cc
   intern/astar.c
   intern/bitmap.c
   intern/bitmap_draw_2d.c
   intern/boxpack_2d.c
   intern/buffer.c
+  intern/compute_context.cc
   intern/convexhull_2d.c
   intern/cpp_type.cc
   intern/delaunay_2d.cc
@@ -159,12 +160,12 @@ set(SRC
   BLI_alloca.h
   BLI_allocator.hh
   BLI_any.hh
-  BLI_args.h
   BLI_array.h
   BLI_array.hh
   BLI_array_store.h
   BLI_array_store_utils.h
   BLI_array_utils.h
+  BLI_array_utils.hh
   BLI_asan.h
   BLI_assert.h
   BLI_astar.h
@@ -180,6 +181,7 @@ set(SRC
   BLI_compiler_attrs.h
   BLI_compiler_compat.h
   BLI_compiler_typecheck.h
+  BLI_compute_context.hh
   BLI_console.h
   BLI_convexhull_2d.h
   BLI_cpp_type.hh
@@ -354,6 +356,14 @@ set(LIB
   ${ZSTD_LIBRARIES}
 )
 
+if(NOT WITH_PYTHON_MODULE)
+  list(APPEND SRC
+    intern/BLI_args.c
+
+    BLI_args.h
+  )
+endif()
+
 if(WITH_MEM_VALGRIND)
   add_definitions(-DWITH_MEM_VALGRIND)
 endif()
diff --git a/source/blender/blenlib/intern/array_utils.cc b/source/blender/blenlib/intern/array_utils.cc
new file mode 100644
index 00000000000..a0fc8810199
--- /dev/null
+++ b/source/blender/blenlib/intern/array_utils.cc
@@ -0,0 +1,20 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BLI_array_utils.hh"
+#include "BLI_task.hh"
+
+namespace blender::array_utils {
+
+void copy(const GVArray &src,
+          const IndexMask selection,
+          GMutableSpan dst,
+          const int64_t grain_size)
+{
+  BLI_assert(src.type() == dst.type());
+  BLI_assert(src.size() == dst.size());
+  threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) {
+    src.materialize_to_uninitialized(selection.slice(range), dst.data());
+  });
+}
+
+}  // namespace blender::array_utils
diff --git a/source/blender/blenlib/intern/compute_context.cc b/source/blender/blenlib/intern/compute_context.cc
new file mode 100644
index 00000000000..50a4a90a4a9
--- /dev/null
+++ b/source/blender/blenlib/intern/compute_context.cc
@@ -0,0 +1,48 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BLI_compute_context.hh"
+#include "BLI_hash_md5.h"
+
+namespace blender {
+
+void ComputeContextHash::mix_in(const void *data, int64_t len)
+{
+  DynamicStackBuffer<> buffer_owner(HashSizeInBytes + len, 8);
+  char *buffer = static_cast<char *>(buffer_owner.buffer());
+  memcpy(buffer, this, HashSizeInBytes);
+  memcpy(buffer + HashSizeInBytes, data, len);
+
+  BLI_hash_md5_buffer(buffer, HashSizeInBytes + len, this);
+}
+
+std::ostream &operator<<(std::ostream &stream, const ComputeContextHash &hash)
+{
+  std::stringstream ss;
+  ss << "0x" << std::hex << hash.v1 << hash.v2;
+  stream << ss.str();
+  return stream;
+}
+
+void ComputeContext::print_stack(std::ostream &stream, StringRef name) const
+{
+  Stack<const ComputeContext *> stack;
+  for (const ComputeContext *current = this; current; current = current->parent_) {
+    stack.push(current);
+  }
+  stream << "Context Stack: " << name << "\n";
+  while (!stack.is_empty()) {
+    const ComputeContext *current = stack.pop();
+    stream << "-> ";
+    current->print_current_in_line(stream);
+    const ComputeContextHash &current_hash = current->hash_;
+    stream << " \t(hash: " << current_hash << ")\n";
+  }
+}
+
+std::ostream &operator<<(std::ostream &stream, const ComputeContext &compute_context)
+{
+  compute_context.print_stack(stream, "");
+  return stream;
+}
+
+}  // namespace blender
diff --git a/source/blender/blenlib/intern/cpp_type.cc b/source/blender/blenlib/intern/cpp_type.cc
index d6a087cf175..38de32d3ec8 100644
--- a/source/blender/blenlib/intern/cpp_type.cc
+++ b/source/blender/blenlib/intern/cpp_type.cc
@@ -26,3 +26,4 @@ BLI_CPP_TYPE_MAKE(ColorGeometry4f, blender::ColorGeometry4f, CPPTypeFlags::Basic
 BLI_CPP_TYPE_MAKE(ColorGeometry4b, blender::ColorGeometry4b, CPPTypeFlags::BasicType)
 
 BLI_CPP_TYPE_MAKE(string, std::string, CPPTypeFlags::BasicType)
+BLI_CPP_TYPE_MAKE(StringVector, blender::Vector<std::string>, CPPTypeFlags::None)
diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c
index 1e95aa3b7b0..9b91636b055 100644
--- a/source/blender/blenlib/intern/path_util.c
+++ b/source/blender/blenlib/intern/path_util.c
@@ -466,8 +466,8 @@ void BLI_path_rel(char *file, const char *relfile)
 #ifdef WIN32
   if (BLI_strnlen(relfile, 3) > 2 && !BLI_path_is_abs(relfile)) {
     char *ptemp;
-    /* fix missing volume name in relative base,
-     * can happen with old recent-files.txt files */
+    /* Fix missing volume name in relative base,
+     * can happen with old `recent-files.txt` files. */
     BLI_windows_get_default_root_dir(temp);
     ptemp = &temp[2];
     if (!ELEM(relfile[0], '\\', '/')) {
@@ -1505,8 +1505,8 @@ size_t BLI_path_join(char *__restrict dst, const size_t dst_len, const char *pat
     return ofs;
   }
 
-  /* remove trailing slashes, unless there are _only_ trailing slashes
-   * (allow "//" as the first argument). */
+  /* Remove trailing slashes, unless there are *only* trailing slashes
+   * (allow `//` or `//some_path` as the first argument). */
   bool has_trailing_slash = false;
   if (ofs != 0) {
     size_t len = ofs;
diff --git a/source/blender/blenlib/intern/system.c b/source/blender/blenlib/intern/system.c
index 781b38f713a..f7249e491d7 100644
--- a/source/blender/blenlib/intern/system.c
+++ b/source/blender/blenlib/intern/system.c
@@ -154,12 +154,12 @@ void BLI_hostname_get(char *buffer, size_t bufsize)
   if (gethostname(buffer, bufsize - 1) < 0) {
     BLI_strncpy(buffer, "-unknown-", bufsize);
   }
-  /* When gethostname() truncates, it doesn't guarantee the trailing \0. */
+  /* When `gethostname()` truncates, it doesn't guarantee the trailing `\0`. */
   buffer[bufsize - 1] = '\0';
 #else
   DWORD bufsize_inout = bufsize;
   if (!GetComputerName(buffer, &bufsize_inout)) {
-    strncpy(buffer, "-unknown-", bufsize);
+    BLI_strncpy(buffer, "-unknown-", bufsize);
   }
 #endif
 }
diff --git a/source/blender/blenlib/tests/BLI_path_util_test.cc b/source/blender/blenlib/tests/BLI_path_util_test.cc
index 4f6f4a5c413..54afc3d975d 100644
--- a/source/blender/blenlib/tests/BLI_path_util_test.cc
+++ b/source/blender/blenlib/tests/BLI_path_util_test.cc
@@ -298,6 +298,13 @@ TEST(path_util, JoinComplex)
   JOIN("1/2/3/", 100, "1", "////////", "", "2", "3\\");
 }
 
+TEST(path_util, JoinRelativePrefix)
+{
+  JOIN("//a/b/c", 100, "//a", "b", "c");
+  JOIN("//a/b/c", 100, "//", "//a//", "//b//", "//c");
+  JOIN("//a/b/c", 100, "//", "//", "a", "//", "b", "//", "c");
+}
+
 #undef JOIN
 
 /* BLI_path_frame */