starlark resolver: implement "flat globals" optimization
This change reworks the Resolver.Module interface (which abstracts
eval.Module) so that each global is statically mapped to a small integer,
so that they can be represented during execution as a flat array,
not a hash table, similar to the treatment of locals in CL 343371120.
It also resolves PREDECLARED and UNIVERSE references distinctly, so that
we needn't try both maps during execution. And it sets the stage for
those maps to be treated as flat arrays too.
Furthermore, it materializes for the first time a "file-local block",
which will be used to hold bindings created by load statements, when
we make loads bind locally and eliminate the getExportedGlobals hack.
The Resolver.Module interface no longer requires the implementation to
enumerate all the defined names; names are looked up on demand as
references are encountered in the program during resolution, and
Bindings are created for them. This reduces unnecessary allocation and
copying when a small program is executed in a big environment.
The resolver still provides spelling suggestions over all available
names; it does this by having the Module implementation provide
the set of top-level candidates lazily: only when resolve() fails.
PiperOrigin-RevId: 343776166
diff --git a/src/main/java/net/starlark/java/eval/Eval.java b/src/main/java/net/starlark/java/eval/Eval.java
index c4e6b70..2dc35d7 100644
--- a/src/main/java/net/starlark/java/eval/Eval.java
+++ b/src/main/java/net/starlark/java/eval/Eval.java
@@ -90,9 +90,8 @@
if (stmt instanceof AssignmentStatement) {
AssignmentStatement assign = (AssignmentStatement) stmt;
for (Identifier id : Identifier.boundIdentifiers(assign.getLHS())) {
- String name = id.getName();
- Object value = fn(fr).getModule().getGlobal(name);
- fr.thread.postAssignHook.assign(name, value);
+ Object value = fn(fr).getGlobal(id.getBinding().getIndex());
+ fr.thread.postAssignHook.assign(id.getName(), value);
}
}
}
@@ -176,10 +175,13 @@
defaults = EMPTY;
}
+ // Nested functions use the same globalIndex as their enclosing function,
+ // since both were compiled from the same Program.
+ StarlarkFunction fn = fn(fr);
assignIdentifier(
fr,
node.getIdentifier(),
- new StarlarkFunction(rfn, Tuple.wrap(defaults), fn(fr).getModule()));
+ new StarlarkFunction(rfn, Tuple.wrap(defaults), fn.getModule(), fn.globalIndex));
}
private static TokenKind execIf(StarlarkThread.Frame fr, IfStatement node)
@@ -231,7 +233,7 @@
// simply assign(binding.getLocalName(), value).
// Currently, we update the module but not module.exportedGlobals;
// changing it to fr.locals.put breaks a test. TODO(adonovan): find out why.
- fn(fr).getModule().setGlobal(binding.getLocalName().getName(), value);
+ fn(fr).setGlobal(binding.getLocalName().getBinding().getIndex(), value);
}
}
@@ -330,11 +332,8 @@
// Updates a module binding and sets its 'exported' flag.
// (Only load bindings are not exported.
// But exportedGlobals does at run time what should be done in the resolver.)
- // TODO(adonovan): use a flat array for Module.globals too.
- Module module = fn(fr).getModule();
- String name = id.getName();
- module.setGlobal(name, value);
- module.exportedGlobals.add(name);
+ fn(fr).setGlobal(bind.getIndex(), value);
+ fn(fr).getModule().exportedGlobals.add(id.getName());
break;
default:
throw new IllegalStateException(bind.getScope().toString());
@@ -639,20 +638,13 @@
result = fr.locals[bind.getIndex()];
break;
case GLOBAL:
- result = fn(fr).getModule().getGlobal(id.getName());
+ result = fn(fr).getGlobal(bind.getIndex());
break;
case PREDECLARED:
- // TODO(adonovan): don't call getGlobal. This requires the Resolver to distinguish
- // "predeclared" vars from "already defined module globals" instead of lumping them
- // together via getNames. The latter odd category exists in the REPL, and
- // in EvaluationTestCase, which calls Starlark.execFile repeatedly on the same Module.
- // The REPL could just create a new module for each chunk, whose predeclared vars
- // are the previous module's globals, but things may be trickier in EvaluationTestCase.
- Module module = fn(fr).getModule();
- result = module.getGlobal(id.getName());
- if (result == null) {
- result = module.getPredeclared(id.getName());
- }
+ result = fn(fr).getModule().getPredeclared(id.getName());
+ break;
+ case UNIVERSAL:
+ result = Starlark.UNIVERSE.get(id.getName());
break;
default:
throw new IllegalStateException(bind.toString());
diff --git a/src/main/java/net/starlark/java/eval/Module.java b/src/main/java/net/starlark/java/eval/Module.java
index fd9cc560..f87bfc2 100644
--- a/src/main/java/net/starlark/java/eval/Module.java
+++ b/src/main/java/net/starlark/java/eval/Module.java
@@ -16,9 +16,10 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableMap;
-import java.util.Collections;
+import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashMap;
+import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
@@ -51,11 +52,13 @@
// The module's predeclared environment. Excludes UNIVERSE bindings.
private ImmutableMap<String, Object> predeclared;
- // The module's global bindings, in order of creation.
- private final LinkedHashMap<String, Object> globals = new LinkedHashMap<>();
+ // The module's global variables, in order of creation.
+ private final LinkedHashMap<String, Integer> globalIndex = new LinkedHashMap<>();
+ private Object[] globals = new Object[8];
// Names of globals that are exported and can be loaded from other modules.
- // TODO(adonovan): eliminate this field when the resolver does its job properly.
+ // TODO(adonovan): eliminate this field when the resolver treats loads as local bindings.
+ // Then all globals are exported.
final HashSet<String> exportedGlobals = new HashSet<>();
// An optional piece of metadata associated with the module/file.
@@ -138,13 +141,9 @@
return clientData;
}
- /** Returns the value of a predeclared (or universal) binding in this module. */
+ /** Returns the value of a predeclared (not universal) binding in this module. */
Object getPredeclared(String name) {
- Object v = predeclared.get(name);
- if (v != null) {
- return v;
- }
- return Starlark.UNIVERSE.get(name);
+ return predeclared.get(name);
}
/**
@@ -158,13 +157,21 @@
}
/**
- * Returns a read-only view of this module's global bindings.
+ * Returns an immutable mapping containing the global variables of this module.
*
* <p>The bindings are returned in a deterministic order (for a given sequence of initial values
* and updates).
*/
- public Map<String, Object> getGlobals() {
- return Collections.unmodifiableMap(globals);
+ public ImmutableMap<String, Object> getGlobals() {
+ int n = globalIndex.size();
+ ImmutableMap.Builder<String, Object> m = ImmutableMap.builderWithExpectedSize(n);
+ for (Map.Entry<String, Integer> e : globalIndex.entrySet()) {
+ Object v = getGlobalByIndex(e.getValue());
+ if (v != null) {
+ m.put(e.getKey(), v);
+ }
+ }
+ return m.build();
}
/**
@@ -176,7 +183,7 @@
// once loads bind locally (then all globals will be exported).
public ImmutableMap<String, Object> getExportedGlobals() {
ImmutableMap.Builder<String, Object> result = new ImmutableMap.Builder<>();
- for (Map.Entry<String, Object> entry : globals.entrySet()) {
+ for (Map.Entry<String, Object> entry : getGlobals().entrySet()) {
if (exportedGlobals.contains(entry.getKey())) {
result.put(entry);
}
@@ -186,30 +193,33 @@
/** Implements the resolver's module interface. */
@Override
- public Set<String> getNames() {
- // TODO(adonovan): for now, the resolver treats all predeclared/universe
- // and global names as one bucket (Scope.PREDECLARED). Fix that.
- // TODO(adonovan): opt: change the resolver to request names on
- // demand to avoid all this set copying.
- HashSet<String> names = new HashSet<>();
- names.addAll(Starlark.UNIVERSE.keySet());
- for (Map.Entry<String, Object> bind : getPredeclaredBindings().entrySet()) {
- if (bind.getValue() instanceof FlagGuardedValue) {
- continue; // disabled
- }
- names.add(bind.getKey());
+ public Resolver.Scope resolve(String name) throws Undefined {
+ // global?
+ if (globalIndex.containsKey(name)) {
+ return Resolver.Scope.GLOBAL;
}
- names.addAll(globals.keySet());
- return names;
- }
- @Override
- @Nullable
- public String getUndeclaredNameError(String name) {
- Object v = getPredeclared(name);
- return v instanceof FlagGuardedValue
- ? ((FlagGuardedValue) v).getErrorFromAttemptingAccess(name)
- : null;
+ // predeclared?
+ Object v = predeclared.get(name);
+ if (v != null) {
+ if (v instanceof FlagGuardedValue) {
+ // Name is correctly spelled, but access is disabled by a flag.
+ throw new Undefined(((FlagGuardedValue) v).getErrorFromAttemptingAccess(name), null);
+ }
+ return Resolver.Scope.PREDECLARED;
+ }
+
+ // universal?
+ if (Starlark.UNIVERSE.containsKey(name)) {
+ return Resolver.Scope.UNIVERSAL;
+ }
+
+ // undefined
+ Set<String> candidates = new HashSet<>();
+ candidates.addAll(globalIndex.keySet());
+ candidates.addAll(predeclared.keySet());
+ candidates.addAll(Starlark.UNIVERSE.keySet());
+ throw new Undefined(String.format("name '%s' is not defined", name), candidates);
}
/**
@@ -217,13 +227,61 @@
* predeclared environment.
*/
public Object getGlobal(String name) {
- return globals.get(name);
+ Integer i = globalIndex.get(name);
+ return i != null ? globals[i] : null;
+ }
+
+ /**
+ * Sets the value of a global variable based on its index in this module ({@see
+ * getIndexOfGlobal}).
+ */
+ void setGlobalByIndex(int i, Object v) {
+ Preconditions.checkArgument(i < globalIndex.size());
+ this.globals[i] = v;
+ }
+
+ /**
+ * Returns the value of a global variable based on its index in this module ({@see
+ * getIndexOfGlobal}.) Returns null if the variable has not been assigned a value.
+ */
+ @Nullable
+ Object getGlobalByIndex(int i) {
+ Preconditions.checkArgument(i < globalIndex.size());
+ return this.globals[i];
+ }
+
+ /**
+ * Returns the index within this Module of a global variable, given its name, creating a new slot
+ * for it if needed. The numbering of globals used by these functions is not the same as the
+ * numbering within any compiled Program. Thus each StarlarkFunction must contain a secondary
+ * index mapping Program indices (from Binding.index) to Module indices.
+ */
+ int getIndexOfGlobal(String name) {
+ int i = globalIndex.size();
+ Integer prev = globalIndex.putIfAbsent(name, i);
+ if (prev != null) {
+ return prev;
+ }
+ if (i == globals.length) {
+ globals = Arrays.copyOf(globals, globals.length << 1); // grow by doubling
+ }
+ return i;
+ }
+
+ /** Returns a list of indices of a list of globals; {@see getIndexOfGlobal}. */
+ int[] getIndicesOfGlobals(List<String> globals) {
+ int n = globals.size();
+ int[] array = new int[n];
+ for (int i = 0; i < n; i++) {
+ array[i] = getIndexOfGlobal(globals.get(i));
+ }
+ return array;
}
/** Updates a global binding in the module environment. */
public void setGlobal(String name, Object value) {
Preconditions.checkNotNull(value, "Module.setGlobal(%s, null)", name);
- globals.put(name, value);
+ setGlobalByIndex(getIndexOfGlobal(name), value);
}
@Override
diff --git a/src/main/java/net/starlark/java/eval/Starlark.java b/src/main/java/net/starlark/java/eval/Starlark.java
index cfdcb45..ab10afb 100644
--- a/src/main/java/net/starlark/java/eval/Starlark.java
+++ b/src/main/java/net/starlark/java/eval/Starlark.java
@@ -39,6 +39,7 @@
import net.starlark.java.syntax.FileOptions;
import net.starlark.java.syntax.ParserInput;
import net.starlark.java.syntax.Program;
+import net.starlark.java.syntax.Resolver;
import net.starlark.java.syntax.StarlarkFile;
import net.starlark.java.syntax.SyntaxError;
@@ -858,8 +859,22 @@
public static Object execFileProgram(Program prog, Module module, StarlarkThread thread)
throws EvalException, InterruptedException {
Tuple defaultValues = Tuple.empty();
- StarlarkFunction toplevel =
- new StarlarkFunction(prog.getResolvedFunction(), defaultValues, module);
+
+ Resolver.Function rfn = prog.getResolvedFunction();
+
+ // A given Module may be passed to execFileProgram multiple times in sequence,
+ // for different compiled Programs. (This happens in the REPL, and in
+ // EvaluationTestCase scenarios. It is not true of the go.starlark.net
+ // implementation, and it complicates things significantly.
+ // It would be nice to stop doing that.)
+ //
+ // Therefore StarlarkFunctions from different Programs (files) but initializing
+ // the same Module need different mappings from the Program's numbering of
+ // globals to the Module's numbering of globals, and to access a global requires
+ // two array lookups.
+ int[] globalIndex = module.getIndicesOfGlobals(rfn.getGlobals());
+
+ StarlarkFunction toplevel = new StarlarkFunction(rfn, defaultValues, module, globalIndex);
return Starlark.fastcall(thread, toplevel, NOARGS, NOARGS);
}
@@ -904,7 +919,9 @@
Expression expr = Expression.parse(input, options);
Program prog = Program.compileExpr(expr, module, options);
Tuple defaultValues = Tuple.empty();
- return new StarlarkFunction(prog.getResolvedFunction(), defaultValues, module);
+ Resolver.Function rfn = prog.getResolvedFunction();
+ int[] globalIndex = module.getIndicesOfGlobals(rfn.getGlobals()); // see execFileProgram
+ return new StarlarkFunction(rfn, defaultValues, module, globalIndex);
}
/**
diff --git a/src/main/java/net/starlark/java/eval/StarlarkFunction.java b/src/main/java/net/starlark/java/eval/StarlarkFunction.java
index afd5077..0889d8c 100644
--- a/src/main/java/net/starlark/java/eval/StarlarkFunction.java
+++ b/src/main/java/net/starlark/java/eval/StarlarkFunction.java
@@ -36,15 +36,28 @@
public final class StarlarkFunction implements StarlarkCallable {
final Resolver.Function rfn;
+ final int[] globalIndex; // index in Module.globals of ith Program global (binding index)
private final Module module; // a function closes over its defining module
private final Tuple defaultValues;
- StarlarkFunction(Resolver.Function rfn, Tuple defaultValues, Module module) {
+ StarlarkFunction(Resolver.Function rfn, Tuple defaultValues, Module module, int[] globalIndex) {
this.rfn = rfn;
+ this.globalIndex = globalIndex;
this.module = module;
this.defaultValues = defaultValues;
}
+ // Sets a global variable, given its index in this function's compiled Program.
+ void setGlobal(int progIndex, Object value) {
+ module.setGlobalByIndex(globalIndex[progIndex], value);
+ }
+
+ // Gets the value of a global variable, given its index in this function's compiled Program.
+ @Nullable
+ Object getGlobal(int progIndex) {
+ return module.getGlobalByIndex(globalIndex[progIndex]);
+ }
+
boolean isToplevel() {
return rfn.isToplevel();
}
diff --git a/src/main/java/net/starlark/java/syntax/Resolver.java b/src/main/java/net/starlark/java/syntax/Resolver.java
index fe3c634..e3b0a62 100644
--- a/src/main/java/net/starlark/java/syntax/Resolver.java
+++ b/src/main/java/net/starlark/java/syntax/Resolver.java
@@ -16,6 +16,7 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.errorprone.annotations.FormatMethod;
import java.util.ArrayList;
import java.util.HashMap;
@@ -56,20 +57,18 @@
/** Scope discriminates the scope of a binding: global, local, etc. */
public enum Scope {
- // TODO(adonovan): Add UNIVERSAL. Separating PREDECLARED from UNIVERSAL allows
- // us to represent the app-dependent and fixed parts of the predeclared
- // environment separately, reducing the amount of copying.
-
/** Binding is local to a function, comprehension, or file (e.g. load). */
LOCAL,
/** Binding occurs outside any function or comprehension. */
GLOBAL,
- /** Binding is local to a function, comprehension, or file, plus its nested functions. */
+ /** Binding is local to a function, comprehension, or file, but shared with nested functions. */
CELL, // TODO(adonovan): implement nested def
- /** Binding is a CELL of some enclosing function. */
+ /** Binding is an implicit parameter whose value is the CELL of some enclosing function. */
FREE, // TODO(adonovan): implement nested def
- /** Binding is predeclared by the core or application. */
- PREDECLARED;
+ /** Binding is predeclared by the application (e.g. glob in Bazel). */
+ PREDECLARED,
+ /** Binding is predeclared by the core (e.g. None). */
+ UNIVERSAL;
@Override
public String toString() {
@@ -82,15 +81,14 @@
* Binding.
*/
public static final class Binding {
-
private final Scope scope;
+ private final int index; // index within function (LOCAL) or module (GLOBAL)
@Nullable private final Identifier first; // first binding use, if syntactic
- final int index; // index within function (LOCAL) or module (GLOBAL)
- private Binding(Scope scope, @Nullable Identifier first, int index) {
+ private Binding(Scope scope, int index, @Nullable Identifier first) {
this.scope = scope;
- this.first = first;
this.index = index;
+ this.first = first;
}
/** Returns the name of this binding's identifier. */
@@ -131,6 +129,10 @@
private final ImmutableList<String> parameterNames;
private final boolean isToplevel;
private final ImmutableList<Binding> locals;
+ // TODO(adonovan): move this to Program, but that requires communication
+ // between resolveFile and compileFile, which depends on use doing the TODO
+ // described at Program.compileResolvedFile and eliminating that function.
+ private final ImmutableList<String> globals;
private Function(
String name,
@@ -140,7 +142,8 @@
boolean hasVarargs,
boolean hasKwargs,
int numKeywordOnlyParams,
- List<Binding> locals) {
+ List<Binding> locals,
+ List<String> globals) {
this.name = name;
this.location = loc;
this.params = params;
@@ -157,6 +160,7 @@
this.isToplevel = name.equals("<toplevel>");
this.locals = ImmutableList.copyOf(locals);
+ this.globals = ImmutableList.copyOf(globals);
}
/**
@@ -173,6 +177,14 @@
return locals;
}
+ /**
+ * Returns the list of names of globals referenced by this function. The order matches the
+ * indices used in compiled code.
+ */
+ public ImmutableList<String> getGlobals() {
+ return globals;
+ }
+
/** Returns the location of the function's identifier. */
public Location getLocation() {
return location;
@@ -231,64 +243,83 @@
}
/**
- * Module is a static abstraction of a Starlark module. It describes the set of variable names for
- * use during name resolution.
+ * A Module is a static abstraction of a Starlark module (see {@link
+ * net.starlark.java.eval.Module})). It describes, for the resolver and compiler, the set of
+ * variable names that are predeclared, either by the interpreter (UNIVERSAL) or by the
+ * application (PREDECLARED), plus the set of pre-defined global names (which is typically empty,
+ * except in a REPL or EvaluationTestCase scenario).
*/
public interface Module {
- // TODO(adonovan): opt: for efficiency, turn this into a predicate, not an enumerable set,
- // and look up bindings as they are needed, not preemptively.
- // Otherwise we must do work proportional to the number of bindings in the
- // environment, not the number of free variables of the file/expression.
- //
- // A single method will then suffice:
- // Scope resolve(String name) throws Undeclared
-
- /** Returns the set of names defined by this module. The caller must not modify the set. */
- Set<String> getNames();
+ /**
+ * Resolves a name to a GLOBAL, PREDECLARED, or UNIVERSAL binding.
+ *
+ * @throws Undefined if the name is not defined.
+ */
+ Scope resolve(String name) throws Undefined;
/**
- * Returns (optionally) a more specific error for an undeclared name than the generic message.
- * This hook allows the module to implement flag-enabled names without any knowledge in this
- * file.
+ * An Undefined exception indicates a failure to resolve a top-level name. If {@code candidates}
+ * is non-null, it provides the set of accessible top-level names, which, along with local
+ * names, will be used as candidates for spelling suggestions.
*/
- @Nullable
- default String getUndeclaredNameError(String name) {
- return null;
+ final class Undefined extends Exception {
+ @Nullable private final Set<String> candidates;
+
+ public Undefined(String message, @Nullable Set<String> candidates) {
+ super(message);
+ this.candidates = candidates;
+ }
}
}
- private static class Block {
- private final Map<String, Binding> bindings = new HashMap<>();
- private final ArrayList<Binding> locals; // of enclosing function
- private final Scope scope;
- @Nullable private final Block parent;
+ // A simple implementation of the Module for testing.
+ // It defines only the predeclared names---no "universal" names (e.g. None)
+ // or initially-defined globals (as happens in a REPL).
+ // Realistically, most clients will use an eval.Module.
+ // TODO(adonovan): move into test/ tree.
+ public static Module moduleWithPredeclared(String... names) {
+ ImmutableSet<String> predeclared = ImmutableSet.copyOf(names);
+ return (name) -> {
+ if (predeclared.contains(name)) {
+ return Scope.PREDECLARED;
+ }
+ throw new Resolver.Module.Undefined(
+ String.format("name '%s' is not defined", name), predeclared);
+ };
+ }
- Block(Scope scope, @Nullable Block parent, ArrayList<Binding> locals) {
- this.scope = scope;
+ private static class Block {
+ @Nullable private final Block parent; // enclosing block, or null for tail of list
+ @Nullable Node syntax; // Comprehension, DefStatement, StarlarkFile, or null
+ private final ArrayList<Binding> frame; // accumulated locals of enclosing function
+
+ // Bindings for names defined in this block.
+ // Also, as an optimization, memoized lookups of enclosing bindings.
+ private final Map<String, Binding> bindings = new HashMap<>();
+
+ Block(@Nullable Block parent, @Nullable Node syntax, ArrayList<Binding> frame) {
this.parent = parent;
- this.locals = locals;
+ this.syntax = syntax;
+ this.frame = frame;
}
}
private final List<SyntaxError> errors;
private final FileOptions options;
private final Module module;
- private Block block;
+ // List whose order defines the numbering of global variables in this program.
+ private final ArrayList<String> globals = new ArrayList<>();
+ // A cache of PREDECLARED, UNIVERSAL, and GLOBAL bindings queried from the module.
+ private final Map<String, Binding> toplevel = new HashMap<>();
+ // Linked list of blocks, innermost first, for functions and comprehensions and (finally) file.
+ private Block locals;
private int loopCount;
- // Shared binding for all predeclared names.
- private static final Binding PREDECLARED = new Binding(Scope.PREDECLARED, null, 0);
-
private Resolver(List<SyntaxError> errors, Module module, FileOptions options) {
this.errors = errors;
this.module = module;
this.options = options;
-
- this.block = new Block(Scope.PREDECLARED, /*parent=*/ null, /*locals=*/ null);
- for (String name : module.getNames()) {
- block.bindings.put(name, PREDECLARED);
- }
}
// Formats and reports an error at the start of the specified node.
@@ -381,10 +412,8 @@
private void assign(Expression lhs) {
if (lhs instanceof Identifier) {
- Identifier id = (Identifier) lhs;
// Bindings are created by the first pass (createBindings),
// so there's nothing to do here.
- Preconditions.checkNotNull(block.bindings.get(id.getName()));
} else if (lhs instanceof IndexExpression) {
visit(lhs);
} else if (lhs instanceof ListExpression) {
@@ -400,37 +429,73 @@
@Override
public void visit(Identifier id) {
- for (Block b = block; b != null; b = b.parent) {
- Binding bind = b.bindings.get(id.getName());
+ Binding bind = use(id);
+ if (bind != null) {
+ id.setBinding(bind);
+ return;
+ }
+ }
+
+ // Resolves a non-binding identifier to an existing binding, or null.
+ private Binding use(Identifier id) {
+ String name = id.getName();
+
+ // local (to function, comprehension, or file)?
+ for (Block b = locals; b != null; b = b.parent) {
+ Binding bind = b.bindings.get(name);
if (bind != null) {
- id.setBinding(bind);
- return;
+ // Optimization: memoize lookup of an outer local
+ // in an inner block, to avoid repeated walks.
+ if (b != locals) {
+ locals.bindings.put(name, bind);
+ }
+ return bind;
}
}
- // The identifier might not exist because it was restricted (hidden) by flags.
- // If this is the case, output a more helpful error message than 'not found'.
- String error = module.getUndeclaredNameError(id.getName());
- if (error == null) {
- // generic error
- error = createInvalidIdentifierException(id.getName(), getAllSymbols());
+ // toplevel (global, predeclared, universal)?
+ Binding bind = toplevel.get(name);
+ if (bind != null) {
+ return bind;
}
- errorf(id, "%s", error);
- }
-
- private static String createInvalidIdentifierException(String name, Set<String> candidates) {
- if (!Identifier.isValid(name)) {
- // Identifier was created by Parser.makeErrorExpression and contains misparsed text.
- return "contains syntax errors";
+ Scope scope;
+ try {
+ scope = module.resolve(name);
+ } catch (Resolver.Module.Undefined ex) {
+ if (!Identifier.isValid(name)) {
+ // If Identifier was created by Parser.makeErrorExpression, it
+ // contains misparsed text. Ignore ex and report an appropriate error.
+ errorf(id, "contains syntax errors");
+ } else if (ex.candidates != null) {
+ // Exception provided toplevel candidates.
+ // Show spelling suggestions of all symbols in scope,
+ String suggestion = SpellChecker.didYouMean(name, getAllSymbols(ex.candidates));
+ errorf(id, "%s%s", ex.getMessage(), suggestion);
+ } else {
+ errorf(id, "%s", ex.getMessage());
+ }
+ return null;
}
-
- String suggestion = SpellChecker.didYouMean(name, candidates);
- return "name '" + name + "' is not defined" + suggestion;
+ switch (scope) {
+ case GLOBAL:
+ bind = new Binding(scope, globals.size(), id);
+ // Accumulate globals in module.
+ globals.add(name);
+ break;
+ case PREDECLARED:
+ case UNIVERSAL:
+ bind = new Binding(scope, 0, id); // index not used
+ break;
+ default:
+ throw new IllegalStateException("bad scope: " + scope);
+ }
+ toplevel.put(name, bind);
+ return bind;
}
@Override
public void visit(ReturnStatement node) {
- if (block.scope != Scope.LOCAL) {
+ if (locals.syntax instanceof StarlarkFile) {
errorf(node, "return statements must be inside a function");
}
super.visit(node);
@@ -487,7 +552,7 @@
@Override
public void visit(ForStatement node) {
- if (block.scope != Scope.LOCAL) {
+ if (locals.syntax instanceof StarlarkFile) {
errorf(
node,
"for loops are not allowed at the top level. You may move it inside a function "
@@ -503,7 +568,7 @@
@Override
public void visit(LoadStatement node) {
- if (block.scope == Scope.LOCAL) {
+ if (!(locals.syntax instanceof StarlarkFile)) {
errorf(node, "load statement not at top level");
}
// Skip super.visit: don't revisit local Identifier as a use.
@@ -534,8 +599,9 @@
Comprehension.For for0 = (Comprehension.For) clauses.get(0);
visit(for0.getIterable());
- // A comprehension defines a distinct lexical block in the same function.
- openBlock(Scope.LOCAL, this.block.locals);
+ // A comprehension defines a distinct lexical block
+ // in the same function's frame.
+ pushLocalBlock(node, this.locals.frame);
for (Comprehension.Clause clause : clauses) {
if (clause instanceof Comprehension.For) {
@@ -557,16 +623,17 @@
}
}
visit(node.getBody());
- closeBlock();
+ popLocalBlock();
}
@Override
public void visit(DefStatement node) {
- if (block.scope == Scope.LOCAL) {
+ if (!(locals.syntax instanceof StarlarkFile)) {
errorf(node, "nested functions are not allowed. Move the function to the top level.");
}
node.setResolvedFunction(
resolveFunction(
+ node,
node.getIdentifier().getName(),
node.getIdentifier().getStartLocation(),
node.getParameters(),
@@ -574,6 +641,7 @@
}
private Function resolveFunction(
+ DefStatement def,
String name,
Location loc,
ImmutableList<Parameter> parameters,
@@ -587,8 +655,8 @@
}
// Enter function block.
- ArrayList<Binding> locals = new ArrayList<>();
- openBlock(Scope.LOCAL, locals);
+ ArrayList<Binding> frame = new ArrayList<>();
+ pushLocalBlock(def, frame);
// Check parameter order and convert to run-time order:
// positionals, keyword-only, *args, **kwargs.
@@ -664,7 +732,7 @@
createBindingsForBlock(body);
visitAll(body);
- closeBlock();
+ popLocalBlock();
return new Function(
name,
@@ -674,7 +742,8 @@
star != null && star.getIdentifier() != null,
starStar != null,
numKeywordOnlyParams,
- locals);
+ frame,
+ globals);
}
private void bindParam(ImmutableList.Builder<Parameter> params, Parameter param) {
@@ -686,7 +755,7 @@
@Override
public void visit(IfStatement node) {
- if (block.scope != Scope.LOCAL) {
+ if (locals.syntax instanceof StarlarkFile) {
errorf(
node,
"if statements are not allowed at the top level. You may move it inside a function "
@@ -712,48 +781,61 @@
/**
* Process a binding use of a name by adding a binding to the current block if not already bound,
- * and associate the identifier with it. Reports whether the name was already bound in this block.
+ * and associate the identifier with it. Reports whether the name was already locally bound in
+ * this block.
*/
private boolean bind(Identifier id) {
- Binding bind = block.bindings.get(id.getName());
+ String name = id.getName();
+ boolean isNew = false;
+ Binding bind;
- // Already bound in this block?
- if (bind != null) {
- // Symbols defined in the module block cannot be reassigned.
- if (block.scope == Scope.GLOBAL && !options.allowToplevelRebinding()) {
+ // outside any function/comprehension? => GLOBAL binding.
+ if (locals.syntax instanceof StarlarkFile) {
+ // TODO(adonovan): make load statements bind locally.
+ // (Will need 'boolean local' param.)
+ bind = toplevel.get(name);
+ if (bind == null) {
+ isNew = true; // new global binding
+ bind = new Binding(Scope.GLOBAL, globals.size(), id);
+ // Accumulate globals in module.
+ globals.add(name);
+ toplevel.put(name, bind);
+ } else if (!options.allowToplevelRebinding()) {
+ // TODO(adonovan): rephrase error in terms of spec.
errorf(
id,
"cannot reassign global '%s' (read more at"
+ " https://bazel.build/versions/master/docs/skylark/errors/read-only-variable.html)",
- id.getName());
+ name);
if (bind.first != null) {
- errorf(bind.first, "'%s' previously declared here", id.getName());
+ errorf(bind.first, "'%s' previously declared here", name);
}
}
- id.setBinding(bind);
- return true;
+ } else {
+ // Binding is local to function or comprehension.
+ bind = locals.bindings.get(name);
+ if (bind == null) {
+ isNew = true; // new local binding
+ bind = new Binding(Scope.LOCAL, locals.frame.size(), id);
+ locals.bindings.put(name, bind);
+ // Accumulate locals in frame of enclosing function.
+ locals.frame.add(bind);
+ }
}
- // new binding
- if (block.scope == Scope.LOCAL) {
- // Accumulate local bindings in the enclosing function.
- bind = new Binding(block.scope, id, block.locals.size());
- block.locals.add(bind);
- } else { // GLOBAL
- bind = new Binding(block.scope, id, block.bindings.size());
- }
- block.bindings.put(id.getName(), bind);
id.setBinding(bind);
- return false;
+ return !isNew;
}
- /** Returns the set of all accessible symbols (both local and global) */
- private Set<String> getAllSymbols() {
+ // Returns the union of accessible local and top-level symbols.
+ private Set<String> getAllSymbols(Set<String> predeclared) {
Set<String> all = new HashSet<>();
- for (Block b = block; b != null; b = b.parent) {
+ for (Block b = locals; b != null; b = b.parent) {
all.addAll(b.bindings.keySet());
}
+ all.addAll(predeclared);
+ all.addAll(toplevel.keySet());
return all;
}
@@ -789,23 +871,23 @@
*/
public static void resolveFile(StarlarkFile file, Module module) {
Resolver r = new Resolver(file.errors, module, file.getOptions());
-
- ArrayList<Binding> locals = new ArrayList<>();
- r.openBlock(Scope.GLOBAL, locals);
-
ImmutableList<Statement> stmts = file.getStatements();
- // Check that load() statements are on top.
+ // Check that load statements are on top.
if (r.options.requireLoadStatementsFirst()) {
r.checkLoadAfterStatement(stmts);
}
+ ArrayList<Binding> frame = new ArrayList<>();
+ r.pushLocalBlock(file, frame);
+
// First pass: creating bindings for statements in this block.
r.createBindingsForBlock(stmts);
// Second pass: visit all references.
r.visitAll(stmts);
- r.closeBlock();
+
+ r.popLocalBlock();
// If the final statement is an expression, synthesize a return statement.
int n = stmts.size();
@@ -828,7 +910,8 @@
/*hasVarargs=*/ false,
/*hasKwargs=*/ false,
/*numKeywordOnlyParams=*/ 0,
- locals));
+ frame,
+ r.globals));
}
/**
@@ -841,10 +924,10 @@
List<SyntaxError> errors = new ArrayList<>();
Resolver r = new Resolver(errors, module, options);
- ArrayList<Binding> locals = new ArrayList<>();
- r.openBlock(Scope.LOCAL, locals); // for bindings in list comprehensions
+ ArrayList<Binding> frame = new ArrayList<>();
+ r.pushLocalBlock(null, frame); // for bindings in list comprehensions
r.visit(expr);
- r.closeBlock();
+ r.popLocalBlock();
if (!errors.isEmpty()) {
throw new SyntaxError.Exception(errors);
@@ -859,17 +942,15 @@
/*hasVarargs=*/ false,
/*hasKwargs=*/ false,
/*numKeywordOnlyParams=*/ 0,
- locals);
+ frame,
+ r.globals);
}
- /** Open a new lexical block for future bindings. Local bindings will be added to locals. */
- private void openBlock(Scope scope, ArrayList<Binding> locals) {
- block = new Block(scope, block, locals);
+ private void pushLocalBlock(Node syntax, ArrayList<Binding> frame) {
+ locals = new Block(locals, syntax, frame);
}
- /** Close a lexical block (and lose all declarations it contained). */
- private void closeBlock() {
- block = Preconditions.checkNotNull(block.parent);
+ private void popLocalBlock() {
+ locals = locals.parent;
}
-
}
diff --git a/src/test/java/net/starlark/java/eval/Examples.java b/src/test/java/net/starlark/java/eval/Examples.java
index 00a5cac..e73f4e9 100644
--- a/src/test/java/net/starlark/java/eval/Examples.java
+++ b/src/test/java/net/starlark/java/eval/Examples.java
@@ -14,13 +14,13 @@
package net.starlark.java.eval;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
import java.io.IOException;
import net.starlark.java.annot.Param;
import net.starlark.java.annot.StarlarkMethod;
import net.starlark.java.syntax.FileOptions;
import net.starlark.java.syntax.ParserInput;
import net.starlark.java.syntax.Program;
+import net.starlark.java.syntax.Resolver;
import net.starlark.java.syntax.StarlarkFile;
import net.starlark.java.syntax.SyntaxError;
@@ -89,7 +89,8 @@
StarlarkFile file = StarlarkFile.parse(input);
// Compile the program, with additional predeclared environment bindings.
- Program prog = Program.compileFile(file, () -> ImmutableSet.of("zero", "square"));
+ // TODO(adonovan): supply Starlark.UNIVERSE somehow.
+ Program prog = Program.compileFile(file, Resolver.moduleWithPredeclared("zero", "square"));
// . . .
diff --git a/src/test/java/net/starlark/java/syntax/ResolverTest.java b/src/test/java/net/starlark/java/syntax/ResolverTest.java
index 6df2f2e..784a847 100644
--- a/src/test/java/net/starlark/java/syntax/ResolverTest.java
+++ b/src/test/java/net/starlark/java/syntax/ResolverTest.java
@@ -17,7 +17,6 @@
import static net.starlark.java.syntax.LexerTest.assertContainsError;
import com.google.common.base.Joiner;
-import com.google.common.collect.ImmutableSet;
import java.util.List;
import org.junit.Test;
import org.junit.runner.RunWith;
@@ -35,7 +34,7 @@
private StarlarkFile resolveFile(String... lines) throws SyntaxError.Exception {
ParserInput input = ParserInput.fromLines(lines);
StarlarkFile file = StarlarkFile.parse(input, options.build());
- Resolver.resolveFile(file, () -> ImmutableSet.of("pre"));
+ Resolver.resolveFile(file, Resolver.moduleWithPredeclared("pre"));
return file;
}
@@ -185,6 +184,11 @@
List<SyntaxError> errors = getResolutionErrors("a = 1", "a = 2");
assertContainsError(errors, ":2:1: cannot reassign global 'a'");
assertContainsError(errors, ":1:1: 'a' previously declared here");
+
+ // global 'pre' shadows predeclared of same name.
+ errors = getResolutionErrors("pre; pre = 1; pre = 2");
+ assertContainsError(errors, ":1:15: cannot reassign global 'pre'");
+ assertContainsError(errors, ":1:6: 'pre' previously declared here");
}
@Test
@@ -403,6 +407,11 @@
// Note: loads bind globally, for now.
checkBindings("load('module', aᴳ₀='a', bᴳ₁='b')");
+ // If a name is bound globally, all toplevel references
+ // resolve to it, even those that precede it.
+ checkBindings("preᴾ₀");
+ checkBindings("preᴳ₀; preᴳ₀=1; preᴳ₀");
+
checkBindings(
"aᴳ₀, bᴳ₁ = 0, 0", //
"def fᴳ₂(aᴸ₀=bᴳ₁):",
@@ -419,7 +428,7 @@
// the spaces. The resulting string must match the input.
private void checkBindings(String... lines) throws Exception {
String src = Joiner.on("\n").join(lines);
- StarlarkFile file = resolveFile(src.replaceAll("[₀₁₂₃₄₅₆₇₈₉ᴳᴸᴾᶠᶜ]", " "));
+ StarlarkFile file = resolveFile(src.replaceAll("[₀₁₂₃₄₅₆₇₈₉ᴸᴳᶜᶠᴾᵁ]", " "));
if (!file.ok()) {
throw new AssertionError("resolution failed: " + file.errors());
}
@@ -430,8 +439,8 @@
// Replace ...x__... with ...xᴸ₀...
out[0] =
out[0].substring(0, id.getEndOffset())
- + "ᴸᴳᶜᶠᴾ".charAt(id.getBinding().getScope().ordinal()) // follow order of enum
- + "₀₁₂₃₄₅₆₇₈₉".charAt(id.getBinding().index) // 10 is plenty
+ + "ᴸᴳᶜᶠᴾᵁ".charAt(id.getBinding().getScope().ordinal()) // follow order of enum
+ + "₀₁₂₃₄₅₆₇₈₉".charAt(id.getBinding().getIndex()) // 10 is plenty
+ out[0].substring(id.getEndOffset() + 2);
}
}.visit(file);
