bazel syntax: simplify StarlarkThread call stack
This change slightly simplifies the stack maintained by StarlarkThread,
and signposts the next steps.
StarlarkThread.Continuation
- rename it to CallFrame
- turn it from linked list into an ArrayList
- clarify but retain its current mostly off-by-one semantics for now
- replace FuncallExpression by just Location
- rename {enter,exit}Scope to push/pop and simplify
- simplify debugger operations in terms of call stack depth
Also:
- rename StarlarkFunction.getDefinitionGlobals -> getModule
- move dummy LexicalFrame for builtins to StarlarkThread.
- move calls to thread.push outside the try block, so we
so don't unintentionally suppress crashes.
Originally reviewed as CL 283349613 but split out.
PiperOrigin-RevId: 283617971
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
index 8913ade..7489bd8 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
@@ -18,6 +18,8 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -90,19 +92,13 @@
// 3) Debugging support (thread name, profiling counters, etc).
// And that is all. See go.starlark.net for the model.
//
-// The Frame interface should be hidden from clients and then eliminated.
-// The dynamic lookup mechanism should go away.
-// The Module class should be redesigned.
-// The concept struggling to get out of it is a Module,
-// which is created before file initialization and
-// populated by execution of the top-level statements in a file;
-// every UserDefinedFunction value should hold a reference to its Module.
+// The Frame interface should eliminated.
// As best I can tell, all the skyframe serialization
// as it applies to LexicalFrames is redundant, as these are transient
// and should not exist after loading.
// We will remove the FuncallExpression parameter from StarlarkFunction.call.
// Clients should use getCallerLocation instead.
-// The Continuation class should be deleted.
+// The only place that still needs an AST is Bazel's generator_name.
// Once the API is small and sound, we can start to represent all
// the lexical frames within a single function using just an array,
// indexed by a small integer computed during the validation pass.
@@ -167,16 +163,6 @@
}
interface LexicalFrame extends Frame {
- static LexicalFrame create(Mutability mutability) {
- return mutability.isFrozen()
- ? ImmutableEmptyLexicalFrame.INSTANCE
- : new MutableLexicalFrame(mutability);
- }
-
- static LexicalFrame create(Mutability mutability, int numArgs) {
- Preconditions.checkState(!mutability.isFrozen());
- return new MutableLexicalFrame(mutability, /*initialCapacity=*/ numArgs);
- }
}
private static final class ImmutableEmptyLexicalFrame implements LexicalFrame {
@@ -288,36 +274,38 @@
return v == null ? null : key.cast(v);
}
- /**
- * A Continuation contains data saved during a function call and restored when the function exits.
- */
- private static final class Continuation {
- /** The {@link BaseFunction} being evaluated that will return into this Continuation. */
- final BaseFunction function;
+ /** A CallFrame records information about an active function call. */
+ // TODO(adonovan): merge LexicalFrame into CallFrame. Every function call should have a frame,
+ // but only Starlark functions need local variables.
+ private static final class CallFrame {
+ final StarlarkCallable fn; // the called function
- /** The {@link FuncallExpression} to which this Continuation will return. */
- @Nullable final FuncallExpression caller;
+ // Note that the inherited design is off-by-one:
+ // the following fields are logically facts about the _enclosing_ frame.
+ // This is a consequence of not representing toplevel statements as a function.
+ // TODO(adonovan): fix that.
- /** The next Continuation after this Continuation. */
- @Nullable final Continuation continuation;
+ final Location callerLoc; // location of the enclosing call (may be Location.BUILTIN)
+ @Nullable final FuncallExpression call; // syntax of the enclosing call
+ final Frame savedLexicals; // the saved lexicals of the parent
+ final Module savedModule; // the saved module of the parent (TODO(adonovan): eliminate)
- /** The lexical Frame of the caller. */
- final Frame lexicalFrame;
+ CallFrame(
+ StarlarkCallable fn,
+ Location callerLoc,
+ @Nullable FuncallExpression call,
+ Frame savedLexicals,
+ Module savedModule) {
+ this.fn = fn;
+ this.callerLoc = callerLoc;
+ this.call = call;
+ this.savedLexicals = savedLexicals;
+ this.savedModule = savedModule;
+ }
- /** The global Frame of the caller. */
- final Module globalFrame;
-
- Continuation(
- @Nullable Continuation continuation,
- BaseFunction function,
- @Nullable FuncallExpression caller,
- Frame lexicalFrame,
- Module globalFrame) {
- this.continuation = continuation;
- this.function = function;
- this.caller = caller;
- this.lexicalFrame = lexicalFrame;
- this.globalFrame = globalFrame;
+ @Override
+ public String toString() {
+ return fn.getName() + "@" + callerLoc;
}
}
@@ -483,18 +471,15 @@
}
}
- /**
- * Static Frame for lexical variables that are always looked up in the current StarlarkThread or
- * for the definition StarlarkThread of the function currently being evaluated.
- */
+ // Local environment of the current active call,
+ // or an alias for globalFrame if no calls are active.
+ // TODO(adonovan): redundant with callstack; eliminate once we fix off-by-one problem.
private Frame lexicalFrame;
- /**
- * Static Frame for global variables; either the current lexical Frame if evaluation is currently
- * happening at the global scope of a BUILD file, or the global Frame at the time of function
- * definition if evaluation is currently happening in the body of a function. Thus functions can
- * close over other functions defined in the same file.
- */
+ // Global environment of the current topmost call frame,
+ // or of the file about to be initialized if no calls are active.
+ // TODO(adonovan): eliminate once we represent even toplevel statements
+ // as a StarlarkFunction that closes over its Module.
private Module globalFrame;
/** The semantics options that affect how Skylark code is evaluated. */
@@ -511,39 +496,51 @@
*/
private final Map<String, Extension> importedExtensions;
- /**
- * When in a lexical (Skylark) frame, this lists the names of the functions in the call stack. We
- * currently use it to artificially disable recursion.
- */
- @Nullable private Continuation continuation;
+ /** Stack of active function calls. */
+ // TODO(adonovan): currently off by one because top-level statements don't have a CallFrame.
+ private final ArrayList<CallFrame> callstack = new ArrayList<>();
/** A hook for notifications of assignments at top level. */
PostAssignHook postAssignHook;
/**
- * Enters a scope by saving state to a new Continuation
+ * Pushes a function onto the call stack.
*
- * @param function the function whose scope to enter
- * @param lexical the lexical frame to use
- * @param caller the source AST node for the caller
- * @param globals the global Frame that this function closes over from its definition
- * StarlarkThread
+ * @param fn the function whose scope to enter
+ * @param loc the source location of the function call.
*/
- void enterScope(
- BaseFunction function, Frame lexical, @Nullable FuncallExpression caller, Module globals) {
- continuation = new Continuation(continuation, function, caller, lexicalFrame, globalFrame);
- lexicalFrame = lexical;
- globalFrame = globals;
+ void push(StarlarkCallable fn, Location loc, @Nullable FuncallExpression call) {
+ callstack.add(new CallFrame(fn, loc, call, this.lexicalFrame, this.globalFrame));
+
+ if (fn instanceof StarlarkFunction) {
+ StarlarkFunction sfn = (StarlarkFunction) fn;
+ this.lexicalFrame =
+ new MutableLexicalFrame(
+ this.mutability(), /*initialCapacity=*/ sfn.getSignature().numParameters());
+ this.globalFrame = sfn.getModule();
+ } else {
+ // built-in function
+ this.lexicalFrame = DUMMY_LEXICAL_FRAME;
+ // this.globalFrame is left as is.
+ // For built-ins, thread.globals() returns the module
+ // of the file from which the built-in was called.
+ // Really they have no business knowing about that.
+ }
}
- /** Exits a scope by restoring state from the current continuation */
- void exitScope() {
- Preconditions.checkNotNull(continuation);
- lexicalFrame = continuation.lexicalFrame;
- globalFrame = continuation.globalFrame;
- continuation = continuation.continuation;
+ /** Pops a function off the call stack. */
+ void pop() {
+ int last = callstack.size() - 1;
+ CallFrame top = callstack.get(last);
+ callstack.remove(last); // pop
+ this.lexicalFrame = top.savedLexicals;
+ this.globalFrame = top.savedModule;
}
+ // Builtins cannot create or modify variable bindings,
+ // so it's sufficient to use a shared instance.
+ private static final LexicalFrame DUMMY_LEXICAL_FRAME = ImmutableEmptyLexicalFrame.INSTANCE;
+
private final String transitiveHashCode;
/**
@@ -583,33 +580,29 @@
* supplied function is already on the stack.
*/
boolean isRecursiveCall(StarlarkFunction function) {
- for (Continuation k = continuation; k != null; k = k.continuation) {
+ for (CallFrame fr : callstack) {
// TODO(adonovan): compare code, not closure values, otherwise
// one can defeat this check by writing the Y combinator.
- if (k.function.equals(function)) {
+ if (fr.fn.equals(function)) {
return true;
}
}
return false;
}
- /** Returns the current function call, if it exists. */
- @Nullable
- BaseFunction getCurrentFunction() {
- return continuation != null ? continuation.function : null;
+ /** Returns the current called function, which must exist. */
+ StarlarkCallable getCurrentFunction() {
+ return Iterables.getLast(callstack).fn;
}
- /** Returns the FuncallExpression and the BaseFunction for the top-level call being evaluated. */
- // TODO(adonovan): replace this by an API for walking the call stack.
- public Pair<FuncallExpression, BaseFunction> getTopCall() {
- Continuation continuation = this.continuation;
- if (continuation == null) {
+ /** Returns the call expression and called function for the outermost call being evaluated. */
+ // TODO(adonovan): replace this by an API for walking the call stack, then move to lib.packages.
+ public Pair<FuncallExpression, StarlarkCallable> getOutermostCall() {
+ if (callstack.isEmpty()) {
return null;
}
- while (continuation.continuation != null) {
- continuation = continuation.continuation;
- }
- return new Pair<>(continuation.caller, continuation.function);
+ CallFrame outermost = callstack.get(0);
+ return new Pair<>(outermost.call, outermost.fn);
}
/**
@@ -864,8 +857,7 @@
* Returns a set of all names of variables that are accessible in this {@code StarlarkThread}, in
* a deterministic order.
*/
- // TODO(adonovan): eliminate sole external call from docgen.
- public Set<String> getVariableNames() {
+ Set<String> getVariableNames() {
LinkedHashSet<String> vars = new LinkedHashSet<>();
vars.addAll(lexicalFrame.getTransitiveBindings().keySet());
// No-op when globalFrame = lexicalFrame
@@ -886,33 +878,29 @@
* current context. The innermost frame's location must be supplied as {@code currentLocation} by
* the caller.
*/
- public ImmutableList<DebugFrame> listFrames(Location currentLocation) {
+ public ImmutableList<DebugFrame> listFrames(Location loc) {
ImmutableList.Builder<DebugFrame> frameListBuilder = ImmutableList.builder();
- Continuation currentContinuation = continuation;
- Frame currentFrame = lexicalFrame;
-
- // if there's a continuation then the current frame is a lexical frame
- while (currentContinuation != null) {
+ Frame lex = this.lexicalFrame;
+ for (CallFrame fr : Lists.reverse(callstack)) {
frameListBuilder.add(
DebugFrame.builder()
- .setLexicalFrameBindings(ImmutableMap.copyOf(currentFrame.getTransitiveBindings()))
+ .setLexicalFrameBindings(ImmutableMap.copyOf(lex.getTransitiveBindings()))
.setGlobalBindings(ImmutableMap.copyOf(getGlobals().getTransitiveBindings()))
- .setFunctionName(currentContinuation.function.getName())
- .setLocation(currentLocation)
+ .setFunctionName(fr.fn.getName())
+ .setLocation(loc)
.build());
-
- currentFrame = currentContinuation.lexicalFrame;
- currentLocation =
- currentContinuation.caller != null ? currentContinuation.caller.getLocation() : null;
- currentContinuation = currentContinuation.continuation;
+ lex = fr.savedLexicals;
+ loc = fr.callerLoc;
}
-
+ // TODO(adonovan): simplify by fixing the callstack's off-by-one problem.
+ // We won't need to pass in 'loc' nor add a fake <top level> frame, nor
+ // suffer a loop-carried dependence.
frameListBuilder.add(
DebugFrame.builder()
.setGlobalBindings(ImmutableMap.copyOf(getGlobals().getTransitiveBindings()))
.setFunctionName("<top level>")
- .setLocation(currentLocation)
+ .setLocation(loc)
.build());
return frameListBuilder.build();
@@ -930,8 +918,7 @@
*/
@Nullable
public ReadyToPause stepControl(Stepping stepping) {
- final Continuation pausedContinuation = continuation;
-
+ final int depth = callstack.size();
switch (stepping) {
case NONE:
return null;
@@ -939,10 +926,10 @@
// pause at the very next statement
return thread -> true;
case OVER:
- return thread -> isAt(thread, pausedContinuation) || isOutside(thread, pausedContinuation);
+ return thread -> thread.callstack.size() <= depth;
case OUT:
- // if we're at the outer-most frame, same as NONE
- return pausedContinuation == null ? null : thread -> isOutside(thread, pausedContinuation);
+ // if we're at the outermost frame, same as NONE
+ return depth == 0 ? null : thread -> thread.callstack.size() < depth;
}
throw new IllegalArgumentException("Unsupported stepping type: " + stepping);
}
@@ -975,17 +962,6 @@
OUT,
}
- /** Returns true if {@code thread} is in a parent frame of {@code pausedContinuation}. */
- private static boolean isOutside(
- StarlarkThread thread, @Nullable Continuation pausedContinuation) {
- return pausedContinuation != null && thread.continuation == pausedContinuation.continuation;
- }
-
- /** Returns true if {@code thread} is at the same frame as {@code pausedContinuation. */
- private static boolean isAt(StarlarkThread thread, @Nullable Continuation pausedContinuation) {
- return thread.continuation == pausedContinuation;
- }
-
@Override
public int hashCode() {
throw new UnsupportedOperationException(); // avoid nondeterminism
