Geometry Nodes: remove accidental exponential time algorithm

Calling `foreach_field_input` on a highly nested field (we do that
often) has an exponential running time in the number of nodes.
That is because the same node may be visited many times.
This made Blender freeze on some setups that should work just fine.
Now every field keeps track of its inputs all the time. That replaces
the exponential algorithm with constant time access.

source/blender/functions/FN_field.hh

@@ -49,6 +49,7 @@
 #include "BLI_function_ref.hh"
 #include "BLI_string_ref.hh"
 #include "BLI_vector.hh"
+#include "BLI_vector_set.hh"
 
 #include "FN_generic_virtual_array.hh"
 #include "FN_multi_function_builder.hh"
@@ -59,6 +60,7 @@
 namespace blender::fn {
 
 class FieldInput;
+class FieldInputs;
 
 /**
  * A node in a field-tree. It has at least one output that can be referenced by fields.
@@ -66,18 +68,18 @@ class FieldInput;
 class FieldNode {
  private:
   bool is_input_;
+
+ protected:
   /**
-   * True when this node is a #FieldInput or (potentially indirectly) depends on one. This could
-   * always be derived again later by traversing the field-tree, but keeping track of it while the
-   * field is built is cheaper.
-   *
-   * If this is false, the field is constant. Note that even when this is true, the field may be
-   * constant when all inputs are constant.
+   * Keeps track of the inputs that this node depends on. This avoids recomputing it every time the
+   * data is required. It is a shared pointer, because very often multiple nodes depend on the same
+   * inputs.
+   * Might contain null.
    */
-  bool depends_on_input_;
+  std::shared_ptr<const FieldInputs> field_inputs_;
 
  public:
-  FieldNode(bool is_input, bool depends_on_input);
+  FieldNode(bool is_input);
 
   virtual ~FieldNode() = default;
 
@@ -87,11 +89,7 @@ class FieldNode {
   bool is_operation() const;
   bool depends_on_input() const;
 
-  /**
-   * Invoke callback for every field input. It might be called multiple times for the same input.
-   * The caller is responsible for deduplication if required.
-   */
-  virtual void foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const = 0;
+  const std::shared_ptr<const FieldInputs> &field_inputs() const;
 
   virtual uint64_t hash() const;
   virtual bool is_equal_to(const FieldNode &other) const;
@@ -231,7 +229,6 @@ class FieldOperation : public FieldNode {
   const MultiFunction &multi_function() const;
 
   const CPPType &output_cpp_type(int output_index) const override;
-  void foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const override;
 };
 
 class FieldContext;
@@ -271,7 +268,19 @@ class FieldInput : public FieldNode {
   Category category() const;
 
   const CPPType &output_cpp_type(int output_index) const override;
-  void foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const override;
+};
+
+/**
+ * Keeps track of the inputs of a field.
+ */
+struct FieldInputs {
+  /** All #FieldInput nodes that a field (possibly indirectly) depends on. */
+  VectorSet<const FieldInput *> nodes;
+  /**
+   * Same as above but the inputs are deduplicated. For example, when there are two separate index
+   * input nodes, only one will show up in this list.
+   */
+  VectorSet<std::reference_wrapper<const FieldInput>> deduplicated_nodes;
 };
 
 /**
@@ -529,8 +538,7 @@ template<typename T> struct ValueOrField {
 /** \name #FieldNode Inline Methods
  * \{ */
 
-inline FieldNode::FieldNode(bool is_input, bool depends_on_input)
-    : is_input_(is_input), depends_on_input_(depends_on_input)
+inline FieldNode::FieldNode(bool is_input) : is_input_(is_input)
 {
 }
 
@@ -546,7 +554,12 @@ inline bool FieldNode::is_operation() const
 
 inline bool FieldNode::depends_on_input() const
 {
-  return depends_on_input_;
+  return field_inputs_ && !field_inputs_->nodes.is_empty();
+}
+
+inline const std::shared_ptr<const FieldInputs> &FieldNode::field_inputs() const
+{
+  return field_inputs_;
 }
 
 inline uint64_t FieldNode::hash() const

source/blender/functions/intern/field.cc

@@ -540,28 +540,65 @@ FieldOperation::FieldOperation(std::shared_ptr<const MultiFunction> function,
   owned_function_ = std::move(function);
 }
 
-static bool any_field_depends_on_input(Span<GField> fields)
+/**
+ * Returns the field inputs used by all the provided fields.
+ * This tries to reuse an existing #FieldInputs whenever possible to avoid copying it.
+ */
+static std::shared_ptr<const FieldInputs> combine_field_inputs(Span<GField> fields)
 {
+  /* The #FieldInputs that we try to reuse if possible. */
+  const std::shared_ptr<const FieldInputs> *field_inputs_candidate = nullptr;
   for (const GField &field : fields) {
-    if (field.node().depends_on_input()) {
-      return true;
+    const std::shared_ptr<const FieldInputs> &field_inputs = field.node().field_inputs();
+    /* Only try to reuse non-empty #FieldInputs. */
+    if (field_inputs && !field_inputs->nodes.is_empty()) {
+      if (field_inputs_candidate == nullptr) {
+        field_inputs_candidate = &field_inputs;
+      }
+      else if ((*field_inputs_candidate)->nodes.size() < field_inputs->nodes.size()) {
+        /* Always try to reuse the #FieldInputs that has the most nodes already. */
+        field_inputs_candidate = &field_inputs;
+      }
     }
   }
-  return false;
+  if (field_inputs_candidate == nullptr) {
+    /* None of the field depends on an input. */
+    return {};
+  }
+  /* Check if all inputs are in the */
+  Vector<const FieldInput *> inputs_not_in_candidate;
+  for (const GField &field : fields) {
+    const std::shared_ptr<const FieldInputs> &field_inputs = field.node().field_inputs();
+    if (!field_inputs) {
+      continue;
+    }
+    if (&field_inputs == field_inputs_candidate) {
+      continue;
+    }
+    for (const FieldInput *field_input : field_inputs->nodes) {
+      if (!(*field_inputs_candidate)->nodes.contains(field_input)) {
+        inputs_not_in_candidate.append(field_input);
+      }
+    }
+  }
+  if (inputs_not_in_candidate.is_empty()) {
+    /* The existing #FieldInputs can be reused, because no other field has additional inputs. */
+    return *field_inputs_candidate;
+  }
+  /* Create new #FieldInputs that contains all of the inputs that the fields depend on. */
+  std::shared_ptr<FieldInputs> new_field_inputs = std::make_shared<FieldInputs>(
+      **field_inputs_candidate);
+  for (const FieldInput *field_input : inputs_not_in_candidate) {
+    new_field_inputs->nodes.add(field_input);
+    new_field_inputs->deduplicated_nodes.add(*field_input);
+  }
+  return new_field_inputs;
 }
 
 FieldOperation::FieldOperation(const MultiFunction &function, Vector<GField> inputs)
-    : FieldNode(false, any_field_depends_on_input(inputs)),
-      function_(&function),
-      inputs_(std::move(inputs))
+    : FieldNode(false), function_(&function), inputs_(std::move(inputs))
 {
-}
-
-void FieldOperation::foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const
-{
-  for (const GField &field : inputs_) {
-    field.node().foreach_field_input(foreach_fn);
-  }
+  field_inputs_ = combine_field_inputs(inputs);
 }
 
 /* --------------------------------------------------------------------
@@ -569,13 +606,12 @@ void FieldOperation::foreach_field_input(FunctionRef<void(const FieldInput &)> f
  */
 
 FieldInput::FieldInput(const CPPType &type, std::string debug_name)
-    : FieldNode(true, true), type_(&type), debug_name_(std::move(debug_name))
+    : FieldNode(true), type_(&type), debug_name_(std::move(debug_name))
 {
-}
-
-void FieldInput::foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const
-{
-  foreach_fn(*this);
+  std::shared_ptr<FieldInputs> field_inputs = std::make_shared<FieldInputs>();
+  field_inputs->nodes.add_new(this);
+  field_inputs->deduplicated_nodes.add_new(*this);
+  field_inputs_ = std::move(field_inputs);
 }
 
 /* --------------------------------------------------------------------

source/blender/nodes/intern/geometry_nodes_eval_log.cc

@@ -191,12 +191,14 @@ const SocketLog *NodeLog::lookup_socket_log(const bNode &node, const bNodeSocket
 
 GFieldValueLog::GFieldValueLog(fn::GField field, bool log_full_field) : type_(field.cpp_type())
 {
-  Set<std::reference_wrapper<const FieldInput>> field_inputs_set;
-  field.node().foreach_field_input(
-      [&](const FieldInput &field_input) { field_inputs_set.add(field_input); });
+  const std::shared_ptr<const fn::FieldInputs> &field_input_nodes = field.node().field_inputs();
 
+  /* Put the deduplicated field inputs into a vector so that they can be sorted below. */
   Vector<std::reference_wrapper<const FieldInput>> field_inputs;
-  field_inputs.extend(field_inputs_set.begin(), field_inputs_set.end());
+  if (field_input_nodes) {
+    field_inputs.extend(field_input_nodes->deduplicated_nodes.begin(),
+                        field_input_nodes->deduplicated_nodes.end());
+  }
 
   std::sort(
       field_inputs.begin(), field_inputs.end(), [](const FieldInput &a, const FieldInput &b) {