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.

1 files changed, 56 insertions, 20 deletions

diff --git a/source/blender/functions/intern/field.cc b/source/blender/functions/intern/field.cc
index f55b9cd92ff..3274af4a7be 100644
--- a/source/blender/functions/intern/field.cc
+++ b/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;
+      }
+    }
+  }
+  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;
   }
-  return false;
+  /* 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))
-{
-}
-
-void FieldInput::foreach_field_input(FunctionRef<void(const FieldInput &)> foreach_fn) const
+    : FieldNode(true), type_(&type), debug_name_(std::move(debug_name))
 {
-  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);
 }
 
 /* --------------------------------------------------------------------