// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.syntax;
import com.google.common.base.Joiner;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
import com.google.devtools.build.lib.events.EventKind;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
import com.google.devtools.build.lib.syntax.Mutability.Freezable;
import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
import com.google.devtools.build.lib.util.Fingerprint;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.util.SpellChecker;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;
import javax.annotation.Nullable;
/**
* An {@code Environment} is the main entry point to evaluating Skylark code. It embodies all the
* state that is required to evaluate such code, except for the current instruction pointer, which
* is an {@link ASTNode} that is evaluated (for expressions) or executed (for statements) with
* respect to this {@code Environment}.
*
*
{@link Continuation}-s are explicitly represented, but only partly, with another part being
* implicit in a series of try-catch statements, to maintain the direct style. One notable trick is
* how a {@link UserDefinedFunction} implements returning values as the function catching a {@link
* ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the body.
*
*
Every {@code Environment} has a {@link Mutability} field, and must be used within a function
* that creates and closes this {@link Mutability} with the try-with-resource pattern. This {@link
* Mutability} is also used when initializing mutable objects within that {@code Environment}. When
* the {@code Mutability} is closed at the end of the computation, it freezes the {@code
* Environment} along with all of those objects. This pattern enforces the discipline that there
* should be no dangling mutable {@code Environment}, or concurrency between interacting {@code
* Environment}s. It is a Skylark-level error to attempt to mutate a frozen {@code Environment} or
* its objects, but it is a Java-level error to attempt to mutate an unfrozen {@code Environment} or
* its objects from within a different {@code Environment}.
*
*
One creates an Environment using the {@link #builder} function, then populates it with {@link
* #setup}, {@link #setupDynamic} and sometimes {@link #setupOverride}, before to evaluate code in
* it with {@link BuildFileAST#eval}, or with {@link BuildFileAST#exec} (where the AST was obtained
* by passing a {@link ValidationEnvironment} constructed from the Environment to {@link
* BuildFileAST#parseBuildFile} or {@link BuildFileAST#parseSkylarkFile}). When the computation is
* over, the frozen Environment can still be queried with {@link #lookup}.
*
*
Final fields of an Environment represent its dynamic state, i.e. state that remains the same
* throughout a given evaluation context, and don't change with source code location, while mutable
* fields embody its static state, that change with source code location. The seeming paradox is
* that the words "dynamic" and "static" refer to the point of view of the source code, and here we
* have a dual point of view.
*/
public final class Environment implements Freezable {
/**
* A phase for enabling or disabling certain builtin functions
*/
public enum Phase { WORKSPACE, LOADING, ANALYSIS }
/**
* A mapping of bindings, either mutable or immutable according to an associated
* {@link Mutability}. The order of the bindings within a single {@link Frame} is deterministic
* but unspecified.
*
*
Any non-frozen {@link Frame} must have the same {@link Mutability} as the current {@link
* Environment}, to avoid interference from other evaluation contexts. For example, a {@link
* UserDefinedFunction} will close over the global frame of the {@link Environment} in which it
* was defined. When the function is called from other {@link Environment}s (possibly
* simultaneously), that global frame must already be frozen; a new local {@link Frame} is created
* to represent the lexical scope of the function.
*
*
A {@link Frame} can have an associated "parent" {@link Frame}, which is used in {@link #get}
* and {@link #getTransitiveBindings()}
*/
public interface Frame extends Freezable {
/**
* Gets a binding from this {@link Frame} or one of its transitive parents.
*
*
In case of conflicts, the binding found in the {@link Frame} closest to the current one is
* used; the remaining bindings are shadowed.
*
* @param varname the name of the variable whose value should be retrieved
* @return the value bound to the variable, or null if no binding is found
*/
@Nullable
Object get(String varname);
/**
* Assigns or reassigns a binding in the current {@code Frame}.
*
*
If the binding has the same name as one in a transitive parent, the parent binding is
* shadowed (i.e., the parent is unaffected).
*
* @param env the {@link Environment} attempting the mutation
* @param varname the name of the variable to be bound
* @param value the value to bind to the variable
*/
void put(Environment env, String varname, Object value) throws MutabilityException;
/**
* TODO(laurentlb): Remove this method when possible. It should probably not
* be part of the public interface.
*/
void remove(Environment env, String varname) throws MutabilityException;
/**
* Returns a map containing all bindings of this {@link Frame} and of its transitive
* parents, taking into account shadowing precedence.
*
*
The bindings are returned in a deterministic order (for a given sequence of initial values
* and updates).
*/
Map getTransitiveBindings();
}
interface LexicalFrame extends Frame {
static LexicalFrame create(Mutability mutability) {
return mutability.isFrozen()
? ImmutableEmptyLexicalFrame.INSTANCE
: new MutableLexicalFrame(mutability);
}
static LexicalFrame createForUserDefinedFunctionCall(Mutability mutability, int numArgs) {
Preconditions.checkState(!mutability.isFrozen());
return new MutableLexicalFrame(mutability, /*initialCapacity=*/ numArgs);
}
}
private static final class ImmutableEmptyLexicalFrame implements LexicalFrame {
private static final ImmutableEmptyLexicalFrame INSTANCE = new ImmutableEmptyLexicalFrame();
@Override
public Mutability mutability() {
return Mutability.IMMUTABLE;
}
@Nullable
@Override
public Object get(String varname) {
return null;
}
@Override
public void put(Environment env, String varname, Object value) throws MutabilityException {
Mutability.checkMutable(this, env.mutability());
throw new IllegalStateException();
}
@Override
public void remove(Environment env, String varname) throws MutabilityException {
Mutability.checkMutable(this, env.mutability());
throw new IllegalStateException();
}
@Override
public Map getTransitiveBindings() {
return ImmutableMap.of();
}
@Override
public String toString() {
return "";
}
}
private static final class MutableLexicalFrame implements LexicalFrame {
private final Mutability mutability;
/** Bindings are maintained in order of creation. */
private final LinkedHashMap bindings;
private MutableLexicalFrame(Mutability mutability, int initialCapacity) {
this.mutability = mutability;
this.bindings = new LinkedHashMap<>(initialCapacity);
}
private MutableLexicalFrame(Mutability mutability) {
this.mutability = mutability;
this.bindings = new LinkedHashMap<>();
}
@Override
public Mutability mutability() {
return mutability;
}
@Nullable
@Override
public Object get(String varname) {
return bindings.get(varname);
}
@Override
public void put(Environment env, String varname, Object value) throws MutabilityException {
Mutability.checkMutable(this, env.mutability());
bindings.put(varname, value);
}
@Override
public void remove(Environment env, String varname) throws MutabilityException {
Mutability.checkMutable(this, env.mutability());
bindings.remove(varname);
}
@Override
public Map getTransitiveBindings() {
return bindings;
}
@Override
public String toString() {
return String.format("", mutability());
}
}
/**
* A {@link Frame} that can have a parent {@link GlobalFrame} from which it inherits bindings.
*
*
Bindings in a {@link GlobalFrame} may shadow those inherited from its parents. A chain of
* {@link GlobalFrame}s can represent different builtin scopes with a linear precedence ordering.
*
*
A {@link GlobalFrame} can also be constructed in a two-phase process. To do this, call the
* nullary constructor to create an uninitialized {@link GlobalFrame}, then call
* {@link #initialize}. It is illegal to use any other method in-between these two calls, or to
* call {@link #initialize} on an already initialized {@link GlobalFrame}.
*/
public static final class GlobalFrame implements Frame {
/**
* Final, except that it may be initialized after instantiation. Null mutability indicates that
* this Frame is uninitialized.
*/
@Nullable
private Mutability mutability;
/** Final, except that it may be initialized after instantiation. */
@Nullable
private GlobalFrame parent;
/**
* If this frame is a global frame, the label for the corresponding target, e.g. {@code
* //foo:bar.bzl}.
*
*
Final, except that it may be initialized after instantiation.
*/
@Nullable
private Label label;
/** Bindings are maintained in order of creation. */
private final LinkedHashMap bindings;
/** Constructs an uninitialized instance; caller must call {@link #initialize} before use. */
public GlobalFrame() {
this.mutability = null;
this.parent = null;
this.label = null;
this.bindings = new LinkedHashMap<>();
}
public GlobalFrame(
Mutability mutability,
@Nullable GlobalFrame parent,
@Nullable Label label,
@Nullable Map bindings) {
this.mutability = Preconditions.checkNotNull(mutability);
this.parent = parent;
this.label = label;
this.bindings = new LinkedHashMap<>();
if (bindings != null) {
this.bindings.putAll(bindings);
}
}
public GlobalFrame(Mutability mutability) {
this(mutability, null, null, null);
}
public GlobalFrame(Mutability mutability, @Nullable GlobalFrame parent) {
this(mutability, parent, null, null);
}
public GlobalFrame(Mutability mutability, @Nullable GlobalFrame parent, @Nullable Label label) {
this(mutability, parent, label, null);
}
/** Constructs a global frame for the given builtin bindings. */
public static GlobalFrame createForBuiltins(Map bindings) {
Mutability mutability = Mutability.create("").freeze();
return new GlobalFrame(mutability, null, null, bindings);
}
private void checkInitialized() {
Preconditions.checkNotNull(mutability, "Attempted to use Frame before initializing it");
}
public void initialize(
Mutability mutability, @Nullable GlobalFrame parent,
@Nullable Label label, Map bindings) {
Preconditions.checkState(this.mutability == null,
"Attempted to initialize an already initialized Frame");
this.mutability = Preconditions.checkNotNull(mutability);
this.parent = parent;
this.label = label;
this.bindings.putAll(bindings);
}
/**
* Returns a new {@link GlobalFrame} that is a descendant of this one with {@link #label} set to
* the given value.
*/
public GlobalFrame withLabel(Label label) {
checkInitialized();
return new GlobalFrame(mutability, this, label);
}
/**
* Returns the {@link Mutability} of this {@link GlobalFrame}, which may be different from its
* parent's.
*/
@Override
public Mutability mutability() {
checkInitialized();
return mutability;
}
/** Returns the parent {@link GlobalFrame}, if it exists. */
@Nullable
public GlobalFrame getParent() {
checkInitialized();
return parent;
}
/**
* Returns the label of this {@code Frame}, which may be null. Parent labels are not consulted.
*
*
Usually you want to use {@link #getTransitiveLabel}; this is just an accessor for
* completeness.
*/
@Nullable
public Label getLabel() {
checkInitialized();
return label;
}
/**
* Walks from this {@link GlobalFrame} up through transitive parents, and returns the first
* non-null label found, or null if all labels are null.
*/
@Nullable
public Label getTransitiveLabel() {
checkInitialized();
if (label != null) {
return label;
} else if (parent != null) {
return parent.getTransitiveLabel();
} else {
return null;
}
}
/**
* Returns a map of direct bindings of this {@link GlobalFrame}, ignoring parents.
*
*
The bindings are returned in a deterministic order (for a given sequence of initial values
* and updates).
*
*
For efficiency an unmodifiable view is returned. Callers should assume that the view is
* invalidated by any subsequent modification to the {@link GlobalFrame}'s bindings.
*/
public Map getBindings() {
checkInitialized();
return Collections.unmodifiableMap(bindings);
}
@Override
public Map getTransitiveBindings() {
checkInitialized();
// Can't use ImmutableMap.Builder because it doesn't allow duplicates.
LinkedHashMap collectedBindings = new LinkedHashMap<>();
accumulateTransitiveBindings(collectedBindings);
return collectedBindings;
}
private void accumulateTransitiveBindings(LinkedHashMap accumulator) {
checkInitialized();
// Put parents first, so child bindings take precedence.
if (parent != null) {
parent.accumulateTransitiveBindings(accumulator);
}
accumulator.putAll(bindings);
}
@Override
public Object get(String varname) {
checkInitialized();
Object val = bindings.get(varname);
if (val != null) {
return val;
}
if (parent != null) {
return parent.get(varname);
}
return null;
}
@Override
public void put(Environment env, String varname, Object value)
throws MutabilityException {
checkInitialized();
Mutability.checkMutable(this, env.mutability());
bindings.put(varname, value);
}
@Override
public void remove(Environment env, String varname) throws MutabilityException {
checkInitialized();
Mutability.checkMutable(this, env.mutability());
bindings.remove(varname);
}
@Override
public String toString() {
if (mutability == null) {
return "";
} else {
return String.format("", mutability());
}
}
}
/**
* 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;
/** The {@link FuncallExpression} to which this Continuation will return. */
final FuncallExpression caller;
/** The next Continuation after this Continuation. */
@Nullable final Continuation continuation;
/** The lexical Frame of the caller. */
final LexicalFrame lexicalFrame;
/** The global Frame of the caller. */
final GlobalFrame globalFrame;
/** The set of known global variables of the caller. */
@Nullable final LinkedHashSet knownGlobalVariables;
Continuation(
Continuation continuation,
BaseFunction function,
FuncallExpression caller,
LexicalFrame lexicalFrame,
GlobalFrame globalFrame,
LinkedHashSet knownGlobalVariables) {
this.continuation = continuation;
this.function = function;
this.caller = caller;
this.lexicalFrame = lexicalFrame;
this.globalFrame = globalFrame;
this.knownGlobalVariables = knownGlobalVariables;
}
}
/** An Extension to be imported with load() into a BUILD or .bzl file. */
@Immutable
// TODO(janakr,brandjon): Do Extensions actually have to start their own memoization? Or can we
// have a node higher up in the hierarchy inject the mutability?
@AutoCodec
public static final class Extension {
private final ImmutableMap bindings;
/**
* Cached hash code for the transitive content of this {@code Extension} and its dependencies.
*
*
Note that "content" refers to the AST content, not the evaluated bindings.
*/
private final String transitiveContentHashCode;
/** Constructs with the given hash code and bindings. */
@AutoCodec.Instantiator
public Extension(ImmutableMap bindings, String transitiveContentHashCode) {
this.bindings = bindings;
this.transitiveContentHashCode = transitiveContentHashCode;
}
/**
* Constructs using the bindings from the global definitions of the given {@link Environment},
* and that {@code Environment}'s transitive hash code.
*/
public Extension(Environment env) {
this(ImmutableMap.copyOf(env.globalFrame.bindings), env.getTransitiveContentHashCode());
}
public String getTransitiveContentHashCode() {
return transitiveContentHashCode;
}
/** Retrieves all bindings, in a deterministic order. */
public ImmutableMap getBindings() {
return bindings;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Extension)) {
return false;
}
Extension other = (Extension) obj;
return transitiveContentHashCode.equals(other.getTransitiveContentHashCode())
&& bindings.equals(other.getBindings());
}
private static boolean skylarkObjectsProbablyEqual(Object obj1, Object obj2) {
// TODO(b/76154791): check this more carefully.
return obj1.equals(obj2)
|| (obj1 instanceof SkylarkValue
&& obj2 instanceof SkylarkValue
&& Printer.repr(obj1).equals(Printer.repr(obj2)));
}
/**
* Throws {@link IllegalStateException} if this {@link Extension} is not equal to {@code obj}.
*
*
The exception explains the reason for the inequality, including all unequal bindings.
*/
public void checkStateEquals(Object obj) {
if (this == obj) {
return;
}
if (!(obj instanceof Extension)) {
throw new IllegalStateException(String.format(
"Expected an equal Extension, but got a %s instead of an Extension",
obj == null ? "null" : obj.getClass().getName()));
}
Extension other = (Extension) obj;
ImmutableMap otherBindings = other.getBindings();
Set names = bindings.keySet();
Set otherNames = otherBindings.keySet();
if (!names.equals(otherNames)) {
throw new IllegalStateException(String.format(
"Expected Extensions to be equal, but they don't define the same bindings: "
+ "in this one but not given one: [%s]; in given one but not this one: [%s]",
Joiner.on(", ").join(Sets.difference(names, otherNames)),
Joiner.on(", ").join(Sets.difference(otherNames, names))));
}
ArrayList badEntries = new ArrayList<>();
for (String name : names) {
Object value = bindings.get(name);
Object otherValue = otherBindings.get(name);
if (value.equals(otherValue)) {
continue;
}
if (value instanceof SkylarkNestedSet) {
if (otherValue instanceof SkylarkNestedSet
&& ((SkylarkNestedSet) value)
.toCollection()
.equals(((SkylarkNestedSet) otherValue).toCollection())) {
continue;
}
} else if (value instanceof SkylarkDict) {
if (otherValue instanceof SkylarkDict) {
@SuppressWarnings("unchecked")
SkylarkDict