Optimize recursive call detection

No need to contruct a list for each function call

RELNOTES: None
PiperOrigin-RevId: 173144689

2 files changed, 16 insertions, 9 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index 3d092532ac..2ec8d23dbb 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -554,15 +553,24 @@ public final class Environment implements Freezable {
     return eventHandler;
   }
 
-  /** @return the current stack trace as a list of functions. */
-  ImmutableList<BaseFunction> getStackTrace() {
-    ImmutableList.Builder<BaseFunction> builder = new ImmutableList.Builder<>();
+  /**
+   * Returns if calling the supplied function would be a recursive call, or in other words if the
+   * supplied function is already on the stack.
+   */
+  boolean isRecursiveCall(UserDefinedFunction function) {
     for (Continuation k = continuation; k != null; k = k.continuation) {
-      builder.add(k.function);
+      if (k.function.equals(function)) {
+        return true;
+      }
     }
-    return builder.build().reverse();
+    return false;
   }
 
+  /** Returns the current function call, if it exists. */
+  @Nullable
+  BaseFunction getCurrentFunction() {
+    return continuation != null ? continuation.function : null;
+  }
 
   /**
    * Returns the FuncallExpression and the BaseFunction for the top-level call being evaluated.
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index 2b64d7c14b..ccdb879997 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.profiler.Profiler;
@@ -58,10 +57,10 @@ public class UserDefinedFunction extends BaseFunction {
     if (env.mutability().isFrozen()) {
       throw new EvalException(getLocation(), "Trying to call in frozen environment");
     }
-    if (env.getStackTrace().contains(this)) {
+    if (env.isRecursiveCall(this)) {
       throw new EvalException(getLocation(),
           String.format("Recursion was detected when calling '%s' from '%s'",
-              getName(), Iterables.getLast(env.getStackTrace()).getName()));
+              getName(), env.getCurrentFunction().getName()));
     }
 
     Profiler.instance().startTask(ProfilerTask.SKYLARK_USER_FN, getName());