Geometry Nodes: new evaluation system

This refactors the geometry nodes evaluation system. No changes for the
user are expected. At a high level the goals are:
* Support using geometry nodes outside of the geometry nodes modifier.
* Support using the evaluator infrastructure for other purposes like field evaluation.
* Support more nodes, especially when many of them are disabled behind switch nodes.
* Support doing preprocessing on node groups.

For more details see T98492.

There are fairly detailed comments in the code, but here is a high level overview
for how it works now:
* There is a new "lazy-function" system. It is similar in spirit to the multi-function
  system but with different goals. Instead of optimizing throughput for highly
  parallelizable work, this system is designed to compute only the data that is actually
  necessary. What data is necessary can be determined dynamically during evaluation.
  Many lazy-functions can be composed in a graph to form a new lazy-function, which can
  again be used in a graph etc.
* Each geometry node group is converted into a lazy-function graph prior to evaluation.
  To evaluate geometry nodes, one then just has to evaluate that graph. Node groups are
  no longer inlined into their parents.

Next steps for the evaluation system is to reduce the use of threads in some situations
to avoid overhead. Many small node groups don't benefit from multi-threading at all.
This is much easier to do now because not everything has to be inlined in one huge
node tree anymore.

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

5 files changed, 232 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_compute_context.hh b/source/blender/blenlib/BLI_compute_context.hh
new file mode 100644
index 00000000000..7422467e400
--- /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 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_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/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index d87c60e6099..4cd222165be 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -53,6 +53,7 @@ set(SRC
   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
@@ -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
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)