Refactor Skylark Environment-s

Make Environment-s freezable: Introduce a class Mutability
as a revokable capability to mutate objects in an Environment.
For now, only Environment-s carry this capability.
Make sure that every Mutability is revoked in the same function that creates it,
so no Environment is left open for modification after being created and exported;
exceptions for tests, the shell and initialization contexts.

Unify Environment, SkylarkEnvironment and EvaluationContext into Environment.
Have a notion of Frame for the bindings + parent + mutability.
Replace the updateAndPropagate mechanism by a dynamicFrame.
Simplify ValidationEnvironment, that is now always deduced from the Environment.

--
MOS_MIGRATED_REVID=102363438

18 files changed, 973 insertions, 750 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
index 8d5f48f2e0..d28d4d30a7 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -407,35 +407,29 @@ public abstract class BaseFunction {
    * @param args a list of all positional arguments (as in *starArg)
    * @param kwargs a map for key arguments (as in **kwArgs)
    * @param ast the expression for this function's definition
-   * @param parentEnv the lexical Environment for the function call
+   * @param env the Environment in the function is called
    * @return the value resulting from evaluating the function with the given arguments
    * @throws construction of EvalException-s containing source information.
    */
   public Object call(List<Object> args,
       @Nullable Map<String, Object> kwargs,
       @Nullable FuncallExpression ast,
-      @Nullable Environment parentEnv)
+      Environment env)
       throws EvalException, InterruptedException {
-    Environment env = getOrCreateChildEnvironment(parentEnv);
-    env.addToStackTrace(new StackTraceElement(this, kwargs));
-    try {
-      Preconditions.checkState(isConfigured(), "Function %s was not configured", getName());
+    Preconditions.checkState(isConfigured(), "Function %s was not configured", getName());
 
-      // ast is null when called from Java (as there's no Skylark call site).
-      Location loc = ast == null ? location : ast.getLocation();
+    // ast is null when called from Java (as there's no Skylark call site).
+    Location loc = ast == null ? Location.BUILTIN : ast.getLocation();
 
-      Object[] arguments = processArguments(args, kwargs, loc);
-      canonicalizeArguments(arguments, loc);
+    Object[] arguments = processArguments(args, kwargs, loc);
+    canonicalizeArguments(arguments, loc);
 
-      try {
-        return call(arguments, ast, env);
-      } catch (EvalExceptionWithStackTrace ex) {
-        throw updateStackTrace(ex, loc);
-      } catch (EvalException | RuntimeException | InterruptedException ex) {
-        throw updateStackTrace(new EvalExceptionWithStackTrace(ex, loc), loc);
-      }
-    } finally {
-      env.removeStackTraceElement();
+    try {
+      return call(arguments, ast, env);
+    } catch (EvalExceptionWithStackTrace ex) {
+      throw updateStackTrace(ex, loc);
+    } catch (EvalException | RuntimeException | InterruptedException ex) {
+      throw updateStackTrace(new EvalExceptionWithStackTrace(ex, loc), loc);
     }
   }
 
@@ -556,7 +550,7 @@ public abstract class BaseFunction {
       if (pos < howManyArgsToPrint - 1) {
         builder.append(", ");
       }
-    }  
+    }
     builder.append(")");
     return builder.toString();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
index a7547deca3..aa9b151f99 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
@@ -122,9 +122,11 @@ public class BuiltinFunction extends BaseFunction {
   @Override
   @Nullable
   public Object call(Object[] args,
-      @Nullable FuncallExpression ast, @Nullable Environment env)
+      FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    final Location loc = (ast == null) ? location : ast.getLocation();
+    Preconditions.checkNotNull(ast);
+    Preconditions.checkNotNull(env);
+    Location loc = ast.getLocation();
 
     // Add extra arguments, if needed
     if (extraArgs != null) {
@@ -150,6 +152,7 @@ public class BuiltinFunction extends BaseFunction {
     long startTime = Profiler.nanoTimeMaybe();
     // Last but not least, actually make an inner call to the function with the resolved arguments.
     try {
+      env.enterScope(this, ast, env.getGlobals());
       return invokeMethod.invoke(this, args);
     } catch (InvocationTargetException x) {
       Throwable e = x.getCause();
@@ -193,6 +196,7 @@ public class BuiltinFunction extends BaseFunction {
           startTime,
           ProfilerTask.SKYLARK_BUILTIN_FN,
           this.getClass().getName() + "#" + getName());
+      env.exitScope();
     }
   }
 
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 ed30671273..25be3fd996 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
@@ -15,18 +15,26 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+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.packages.CachingPackageLocator;
+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.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Deque;
+import java.io.Serializable;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -34,54 +42,280 @@ import java.util.Set;
 import javax.annotation.Nullable;
 
 /**
- * The BUILD environment.
+ * An Environment is the main entry point to evaluating code in the BUILD language or Skylark.
+ * It embodies all the state that is required to evaluate such code,
+ * except for the current instruction pointer, which is an {@link ASTNode}
+ * whose {@link Statement#exec exec} or {@link Expression#eval eval} method is invoked with
+ * this Environment, in a straightforward direct-style AST-walking interpreter.
+ * {@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.
+ *
+ * <p>Every 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 Environment;
+ * when closed at the end of the computation freezes the Environment and all those objects that
+ * then become forever immutable. The pattern enforces the discipline that there should be no
+ * dangling mutable Environment, or concurrency between interacting Environment-s.
+ * It is also an error to try to mutate an Environment and its objects from another Environment,
+ * before the {@link Mutability} is closed.
+ *
+ * <p>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 #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}.
+ *
+ * <p>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 class Environment {
+public final class Environment implements Freezable, Serializable {
 
-  protected final Map<String, Object> env = new HashMap<>();
+  /**
+   * A Frame is a Map of bindings, plus a {@link Mutability} and a parent Frame
+   * from which to inherit bindings.
+   *
+   * <p>A Frame contains bindings mapping variable name to variable value in a given scope.
+   * It may also inherit bindings from a parent Frame corresponding to a parent scope,
+   * which in turn may inherit bindings from its own parent, etc., transitively.
+   * Bindings may shadow bindings from the parent. In Skylark, you may only mutate
+   * bindings from the current Frame, which always got its {@link Mutability} with the
+   * current {@link Environment}; but future extensions may make it more like Python
+   * and allow mutation of bindings in outer Frame-s (or then again may not).
+   *
+   * <p>A Frame inherits the {@link Mutability} from the {@link Environment} in which it was
+   * originally created. When that {@link Environment} is finalized and its {@link Mutability}
+   * is closed, it becomes immutable, including the Frame, which can be shared in other
+   * {@link Environment}-s. Indeed, a {@link UserDefinedFunction} will close over the global
+   * Frame of its definition {@link Environment}, which will thus be reused (immutably)
+   * in all any {@link Environment} in which this function is called, so it's important to
+   * preserve the {@link Mutability} to make sure no Frame is modified after it's been finalized.
+   */
+  public static final class Frame implements Freezable {
+
+    private final Mutability mutability;
+    final Frame parent;
+    final Map<String, Object> bindings = new HashMap<>();
+
+    Frame(Mutability mutability, Frame parent) {
+      this.mutability = mutability;
+      this.parent = parent;
+    }
+
+    @Override
+    public final Mutability mutability() {
+      return mutability;
+    }
+
+    /**
+     * Gets a binding from the current frame or if not found its parent.
+     * @param varname the name of the variable to be bound
+     * @return the value bound to variable
+     */
+    public Object get(String varname) {
+      if (bindings.containsKey(varname)) {
+        return bindings.get(varname);
+      }
+      if (parent != null) {
+        return parent.get(varname);
+      }
+      return null;
+    }
+
+    /**
+     * Modifies a binding in the current Frame.
+     * Does not try to modify an inherited binding.
+     * This will shadow any inherited binding, which may be an error
+     * that you want to guard against before calling this function.
+     * @param env the Environment attempting the mutation
+     * @param varname the name of the variable to be bound
+     * @param value the value to bind to the variable
+     */
+    public void put(Environment env, String varname, Object value)
+        throws MutabilityException {
+      Mutability.checkMutable(this, env);
+      bindings.put(varname, value);
+    }
+
+    /**
+     * Adds the variable names of this Frame and its transitive parents to the given set.
+     * This provides a O(n) way of extracting the list of all variables visible in an Environment.
+     * @param vars the set of visible variables in the Environment, being computed.
+     */
+    public void addVariableNamesTo(Set<String> vars) {
+      vars.addAll(bindings.keySet());
+      if (parent != null) {
+        parent.addVariableNamesTo(vars);
+      }
+    }
+
+    public Set<String> getDirectVariableNames() {
+      return bindings.keySet();
+    }
+
+    @Override
+    public String toString() {
+      String prefix = "Frame";
+      StringBuilder sb = new StringBuilder();
+      for (Frame f = this; f != null; f = f.parent) {
+        Printer.formatTo(sb, "%s%s%r",
+            ImmutableList.<Object>of(prefix, f.mutability(), f.bindings));
+        prefix = "=>";
+      }
+      return sb.toString();
+    }
+  }
 
   /**
-   * The parent environment. For Skylark it's the global environment,
-   * used for global read only variable lookup.
+   * A Continuation contains data saved during a function call and restored when the function exits.
    */
-  protected final Environment parent;
+  private static final class Continuation {
+    /** The {@link BaseFunction} being evaluated that will return into this Continuation. */
+    BaseFunction function;
+
+    /** The {@link FuncallExpression} to which this Continuation will return. */
+    FuncallExpression caller;
+
+    /** The next Continuation after this Continuation. */
+    @Nullable Continuation continuation;
+
+    /** The lexical Frame of the caller. */
+    Frame lexicalFrame;
+
+    /** The global Frame of the caller. */
+    Frame globalFrame;
+
+    /** The set of known global variables of the caller. */
+    @Nullable Set<String> knownGlobalVariables;
+
+    /** Whether the caller is in Skylark mode. */
+    boolean isSkylark;
+
+    Continuation(
+        Continuation continuation,
+        BaseFunction function,
+        FuncallExpression caller,
+        Frame lexicalFrame,
+        Frame globalFrame,
+        Set<String> knownGlobalVariables,
+        boolean isSkylark) {
+      this.continuation = continuation;
+      this.function = function;
+      this.caller = caller;
+      this.lexicalFrame = lexicalFrame;
+      this.globalFrame = globalFrame;
+      this.isSkylark = isSkylark;
+    }
+  }
 
   /**
-   * Map from a Skylark extension to an environment, which contains all symbols defined in the
-   * extension.
+   * Static Frame for lexical variables that are always looked up in the current Environment
+   * or for the definition Environment of the function currently being evaluated.
    */
-  protected Map<PathFragment, SkylarkEnvironment> importedExtensions;
+  private Frame lexicalFrame;
 
   /**
-   * A set of variables propagating through function calling. It's only used to call
-   * native rules from Skylark build extensions.
+   * 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.
    */
-  protected Set<String> propagatingVariables = new HashSet<>();
+  private Frame globalFrame;
 
-  // Only used in the global environment.
-  // TODO(bazel-team): make this a final field part of constructor.
-  private boolean isLoadingPhase = false;
+  /**
+   * Dynamic Frame for variables that are always looked up in the runtime Environment,
+   * and never in the lexical or "global" Environment as it was at the time of function definition.
+   * For instance, PACKAGE_NAME.
+   */
+  private final Frame dynamicFrame;
 
   /**
-   * Is this Environment being evaluated during the loading phase?
-   * This is fixed during environment setup, and enables various functions
-   * that are not available during the analysis phase.
-   * @return true if this environment corresponds to code during the loading phase.
+   * An EventHandler for errors and warnings. This is not used in the BUILD language,
+   * however it might be used in Skylark code called from the BUILD language, so shouldn't be null.
    */
-  boolean isLoadingPhase() {
-    return isLoadingPhase;
+  private final EventHandler eventHandler;
+
+  /**
+   * For each imported extensions, a global Skylark frame from which to load() individual bindings.
+   */
+  private final Map<PathFragment, Environment> importedExtensions;
+
+  /**
+   * Is this Environment being executed in Skylark context?
+   */
+  private boolean isSkylark;
+
+  /**
+   * Is this Environment being executed during the loading phase?
+   * Many builtin functions are only enabled during the loading phase, and check this flag.
+   */
+  private final boolean isLoadingPhase;
+
+  /**
+   * When in a lexical (Skylark) Frame, this set contains the variable names that are global,
+   * as determined not by global declarations (not currently supported),
+   * but by previous lookups that ended being global or dynamic.
+   * This is necessary because if in a function definition something
+   * reads a global variable after which a local variable with the same name is assigned an
+   * Exception needs to be thrown.
+   */
+  @Nullable private Set<String> knownGlobalVariables;
+
+  /**
+   * 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;
+
+  /**
+   * Enters a scope by saving state to a new Continuation
+   * @param function the function whose scope to enter
+   * @param caller the source AST node for the caller
+   * @param globals the global Frame that this function closes over from its definition Environment
+   */
+  void enterScope(BaseFunction function, FuncallExpression caller, Frame globals) {
+    continuation = new Continuation(
+        continuation, function, caller, lexicalFrame, globalFrame, knownGlobalVariables, isSkylark);
+    lexicalFrame = new Frame(mutability(), null);
+    globalFrame = globals;
+    knownGlobalVariables = new HashSet<String>();
+    isSkylark = true;
   }
 
   /**
-   * Enable loading phase only functions in this Environment.
-   * This should only be done during setup before code is evaluated.
+   * Exits a scope by restoring state from the current continuation
    */
-  public void setLoadingPhase() {
-    isLoadingPhase = true;
+  void exitScope() {
+    Preconditions.checkNotNull(continuation);
+    lexicalFrame = continuation.lexicalFrame;
+    globalFrame = continuation.globalFrame;
+    knownGlobalVariables = continuation.knownGlobalVariables;
+    isSkylark = continuation.isSkylark;
+    continuation = continuation.continuation;
   }
 
   /**
-   * Checks that the current Evaluation context is in loading phase.
+   * When evaluating code from a file, this contains a hash of the file.
+   */
+  @Nullable private String fileContentHashCode;
+
+  /**
+   * Is this Environment being evaluated during the loading phase?
+   * This is fixed during Environment setup, and enables various functions
+   * that are not available during the analysis phase.
+   * @return true if this Environment corresponds to code during the loading phase.
+   */
+  private boolean isLoadingPhase() {
+    return isLoadingPhase;
+  }
+
+  /**
+   * Checks that the current Environment is in the loading phase.
    * @param symbol name of the function being only authorized thus.
    */
   public void checkLoadingPhase(String symbol, Location loc) throws EvalException {
@@ -91,168 +325,378 @@ public class Environment {
   }
 
   /**
-   * Is this a global environment?
-   * @return true if this is a global (top-level) environment
-   * as opposed to inside the body of a function
+   * Is this a global Environment?
+   * @return true if the current code is being executed at the top-level,
+   * as opposed to inside the body of a function.
    */
-  public boolean isGlobal() {
-    return true;
+  boolean isGlobal() {
+    return lexicalFrame == null;
   }
 
   /**
-   * An EventHandler for errors and warnings. This is not used in the BUILD language,
-   * however it might be used in Skylark code called from the BUILD language.
+   * Is the current code Skylark?
+   * @return true if Skylark was enabled when this code was read.
    */
-  @Nullable protected EventHandler eventHandler;
-
-  /**
-   * A stack trace containing the current history of functions and the calling rule.
-   *
-   * <p>For the rule, the stack trace has two elements: one for the call to the rule in the BUILD
-   * file and one for the actual rule implementation.
-   */
-  private Deque<StackTraceElement> stackTrace;
+  // TODO(bazel-team): Delete this function.
+  // This function is currently used in various functions that change their behavior with respect to
+  // lists depending on the Skylark-ness of the code; lists should be unified between the two modes.
+  boolean isSkylark() {
+    return isSkylark;
+  }
 
   /**
-   * Constructs an empty root non-Skylark environment.
-   * The root environment is also the global environment.
+   * Is the caller of the current function executing Skylark code?
+   * @return true if this is skylark was enabled when this code was read.
    */
-  public Environment(Deque<StackTraceElement> stackTrace) {
-    this.parent = null;
-    this.importedExtensions = new HashMap<>();
-    this.stackTrace = stackTrace;
-    setupGlobal();
+  // TODO(bazel-team): Delete this function.
+  // This function is currently used by MethodLibrary to modify behavior of lists
+  // depending on the Skylark-ness of the code; lists should be unified between the two modes.
+  boolean isCallerSkylark() {
+    return continuation.isSkylark;
   }
 
-  public Environment() {
-    this(new LinkedList<StackTraceElement>());
+  @Override
+  public Mutability mutability() {
+    // the mutability of the environment is that of its dynamic frame.
+    return dynamicFrame.mutability();
   }
 
   /**
-   * Constructs an empty child environment.
+   * @return the current Frame, in which variable side-effects happen.
    */
-  public Environment(Environment parent, Deque<StackTraceElement> stackTrace) {
-    Preconditions.checkNotNull(parent);
-    this.parent = parent;
-    this.importedExtensions = new HashMap<>();
-    this.stackTrace = stackTrace;
-  }
-
-  public Environment(Environment parent) {
-    this(parent, new LinkedList<StackTraceElement>());
+  private Frame currentFrame() {
+    return isGlobal() ? globalFrame : lexicalFrame;
   }
 
   /**
-   * Constructs an empty child environment with an EventHandler.
+   * @return the global variables for the Environment (not including dynamic bindings).
    */
-  public Environment(Environment parent, EventHandler eventHandler) {
-    this(parent);
-    this.eventHandler = Preconditions.checkNotNull(eventHandler);
+  public Frame getGlobals() {
+    return globalFrame;
   }
 
+  /**
+   * Returns an EventHandler for errors and warnings.
+   * The BUILD language doesn't use it directly, but can call Skylark code that does use it.
+   * @return an EventHandler
+   */
   public EventHandler getEventHandler() {
     return eventHandler;
   }
 
-  // Sets up the global environment
-  private void setupGlobal() {
-    // In Python 2.x, True and False are global values and can be redefined by the user.
-    // In Python 3.x, they are keywords. We implement them as values, for the sake of
-    // simplicity. We define them as Boolean objects.
-    update("False", Runtime.FALSE);
-    update("True", Runtime.TRUE);
-    update("None", Runtime.NONE);
+  /**
+   * @return the current stack trace as a list of functions.
+   */
+  public ImmutableList<BaseFunction> getStackTrace() {
+    ImmutableList.Builder<BaseFunction> builder = new ImmutableList.Builder<>();
+    for (Continuation k = continuation; k != null; k = k.continuation) {
+      builder.add(k.function);
+    }
+    return builder.build().reverse();
   }
 
-  public boolean isSkylark() {
-    return false;
+  /**
+   * Return the name of the top-level function being called and the location of the call.
+   */
+  public Pair<BaseFunction, Location> getTopCall() {
+    Continuation continuation = this.continuation;
+    if (continuation == null) {
+      return null;
+    }
+    while (continuation.continuation != null) {
+      continuation = continuation.continuation;
+    }
+    return new Pair<>(continuation.function, continuation.caller.getLocation());
   }
 
-  protected boolean hasVariable(String varname) {
-    return env.containsKey(varname);
+  /**
+   * Constructs an Environment.
+   * This is the main, most basic constructor.
+   * @param globalFrame a frame for the global Environment
+   * @param dynamicFrame a frame for the dynamic Environment
+   * @param eventHandler an EventHandler for warnings, errors, etc
+   * @param importedExtensions frames for extensions from which to import bindings with load()
+   * @param isSkylark true if in Skylark context
+   * @param fileContentHashCode a hash for the source file being evaluated, if any
+   * @param isLoadingPhase true if in loading phase
+   */
+  private Environment(
+      Frame globalFrame,
+      Frame dynamicFrame,
+      EventHandler eventHandler,
+      Map<PathFragment, Environment> importedExtensions,
+      boolean isSkylark,
+      @Nullable String fileContentHashCode,
+      boolean isLoadingPhase) {
+    this.globalFrame = Preconditions.checkNotNull(globalFrame);
+    this.dynamicFrame = Preconditions.checkNotNull(dynamicFrame);
+    Preconditions.checkArgument(globalFrame.mutability().isMutable());
+    Preconditions.checkArgument(dynamicFrame.mutability().isMutable());
+    this.eventHandler = eventHandler;
+    this.importedExtensions = importedExtensions;
+    this.isSkylark = isSkylark;
+    this.fileContentHashCode = fileContentHashCode;
+    this.isLoadingPhase = isLoadingPhase;
   }
 
   /**
-   * @return the value from the environment whose name is "varname".
-   * @throws NoSuchVariableException if the variable is not defined in the Environment.
-   *
+   * A Builder class for Environment
    */
-  public Object lookup(String varname) throws NoSuchVariableException {
-    Object value = env.get(varname);
-    if (value == null) {
+  public static class Builder {
+    private final Mutability mutability;
+    private boolean isSkylark = false;
+    private boolean isLoadingPhase = false;
+    @Nullable private Frame parent;
+    @Nullable private EventHandler eventHandler;
+    @Nullable private Map<PathFragment, Environment> importedExtensions;
+    @Nullable private String fileContentHashCode;
+
+    Builder(Mutability mutability) {
+      this.mutability = mutability;
+    }
+
+    /** Enables Skylark for code read in this Environment. */
+    public Builder setSkylark() {
+      Preconditions.checkState(!isSkylark);
+      isSkylark = true;
+      return this;
+    }
+
+    /** Enables loading phase only functions in this Environment. */
+    public Builder setLoadingPhase() {
+      Preconditions.checkState(!isLoadingPhase);
+      isLoadingPhase = true;
+      return this;
+    }
+
+    /** Inherits global bindings from the given parent Frame. */
+    public Builder setGlobals(Frame parent) {
+      Preconditions.checkState(this.parent == null);
+      this.parent = parent;
+      return this;
+    }
+
+    /** Sets an EventHandler for errors and warnings. */
+    public Builder setEventHandler(EventHandler eventHandler) {
+      Preconditions.checkState(this.eventHandler == null);
+      this.eventHandler = eventHandler;
+      return this;
+    }
+
+    /** Declares imported extensions for load() statements. */
+    public Builder setImportedExtensions (Map<PathFragment, Environment> importedExtensions) {
+      Preconditions.checkState(this.importedExtensions == null);
+      this.importedExtensions = importedExtensions;
+      return this;
+    }
+
+    /** Declares content hash for the source file for this Environment. */
+    public Builder setFileContentHashCode(String fileContentHashCode) {
+      this.fileContentHashCode = fileContentHashCode;
+      return this;
+    }
+
+    /** Builds the Environment. */
+    public Environment build() {
+      Preconditions.checkArgument(mutability.isMutable());
       if (parent != null) {
-        return parent.lookup(varname);
+        Preconditions.checkArgument(!parent.mutability().isMutable());
       }
-      throw new NoSuchVariableException(varname);
+      Frame globalFrame = new Frame(mutability, parent);
+      Frame dynamicFrame = new Frame(mutability, null);
+      if (importedExtensions == null) {
+        importedExtensions = ImmutableMap.of();
+      }
+      Environment env = new Environment(
+          globalFrame,
+          dynamicFrame,
+          eventHandler,
+          importedExtensions,
+          isSkylark,
+          fileContentHashCode,
+          isLoadingPhase);
+      return env;
     }
-    return value;
+  }
+
+  public static Builder builder(Mutability mutability) {
+    return new Builder(mutability);
   }
 
   /**
-   * Like <code>lookup(String)</code>, but instead of throwing an exception in
-   * the case where "varname" is not defined, "defaultValue" is returned instead.
-   *
+   * Sets a binding for a special dynamic variable in this Environment.
+   * This is not for end-users, and will throw an AssertionError in case of conflict.
+   * @param varname the name of the dynamic variable to be bound
+   * @param value a value to bind to the variable
+   * @return this Environment, in fluid style
    */
-  public Object lookup(String varname, Object defaultValue) {
-    Object value = env.get(varname);
-    if (value == null) {
-      if (parent != null) {
-        return parent.lookup(varname, defaultValue);
-      }
-      return defaultValue;
+  public Environment setupDynamic(String varname, Object value) {
+    if (dynamicFrame.get(varname) != null) {
+      throw new AssertionError(
+          String.format("Trying to bind dynamic variable '%s' but it is already bound",
+              varname));
     }
-    return value;
+    if (lexicalFrame != null && lexicalFrame.get(varname) != null) {
+      throw new AssertionError(
+          String.format("Trying to bind dynamic variable '%s' but it is already bound lexically",
+              varname));
+    }
+    if (globalFrame.get(varname) != null) {
+      throw new AssertionError(
+          String.format("Trying to bind dynamic variable '%s' but it is already bound globally",
+              varname));
+    }
+    try {
+      dynamicFrame.put(this, varname, value);
+    } catch (MutabilityException e) {
+      // End users don't have access to setupDynamic, and it is an implementation error
+      // if we encounter a mutability exception.
+      throw new AssertionError(
+          Printer.format(
+              "Trying to bind dynamic variable '%s' in frozen environment %r", varname, this),
+          e);
+    }
+    return this;
   }
 
+
   /**
-   * Updates the value of variable "varname" in the environment, corresponding
-   * to an {@link AssignmentStatement}.
+   * Modifies a binding in the current Frame of this Environment, as would an
+   * {@link AssignmentStatement}. Does not try to modify an inherited binding.
+   * This will shadow any inherited binding, which may be an error
+   * that you want to guard against before calling this function.
+   * @param varname the name of the variable to be bound
+   * @param value the value to bind to the variable
+   * @return this Environment, in fluid style
    */
-  public Environment update(String varname, Object value) {
+  public Environment update(String varname, Object value) throws EvalException {
     Preconditions.checkNotNull(value, "update(value == null)");
-    env.put(varname, value);
+    // prevents clashes between static and dynamic variables.
+    if (dynamicFrame.get(varname) != null) {
+      throw new EvalException(
+          null, String.format("Trying to update special read-only global variable '%s'", varname));
+    }
+    if (isKnownGlobalVariable(varname)) {
+      throw new EvalException(
+          null, String.format("Trying to update read-only global variable '%s'", varname));
+    }
+    try {
+      currentFrame().put(this, varname, Preconditions.checkNotNull(value));
+    } catch (MutabilityException e) {
+      // Note that since at this time we don't accept the global keyword, and don't have closures,
+      // end users should never be able to mutate a frozen Environment, and a MutabilityException
+      // is therefore a failed assertion for Bazel. However, it is possible to shadow a binding
+      // imported from a parent Environment by updating the current Environment, which will not
+      // trigger a MutabilityException.
+      throw new AssertionError(
+          Printer.format("Can't update %s to %r in frozen environment", varname, value),
+          e);
+    }
     return this;
   }
 
+  private boolean hasVariable(String varname) {
+    try {
+      lookup(varname);
+      return true;
+    } catch (NoSuchVariableException e) {
+      return false;
+    }
+  }
+
+  /**
+   * Initializes a binding in this Environment. It is an error if the variable is already bound.
+   * This is not for end-users, and will throw an AssertionError in case of conflict.
+   * @param varname the name of the variable to be bound
+   * @param value the value to bind to the variable
+   * @return this Environment, in fluid style
+   */
+  public Environment setup(String varname, Object value) {
+    if (hasVariable(varname)) {
+      throw new AssertionError(String.format("variable '%s' already bound", varname));
+    }
+    return setupOverride(varname, value);
+  }
+
   /**
-   * Same as {@link #update}, but also marks the variable propagating, meaning it will
-   * be present in the execution environment of a UserDefinedFunction called from this
-   * Environment. Using this method is discouraged.
+   * Initializes a binding in this environment. Overrides any previous binding.
+   * This is not for end-users, and will throw an AssertionError in case of conflict.
+   * @param varname the name of the variable to be bound
+   * @param value the value to bind to the variable
+   * @return this Environment, in fluid style
    */
-  public void updateAndPropagate(String varname, Object value) {
-    update(varname, value);
-    propagatingVariables.add(varname);
+  public Environment setupOverride(String varname, Object value) {
+    try {
+      return update(varname, value);
+    } catch (EvalException ee) {
+      throw new AssertionError(ee);
+    }
+  }
+
+  /**
+   * @return the value from the environment whose name is "varname".
+   * @throws NoSuchVariableException if the variable is not defined in the Environment.
+   */
+  public Object lookup(String varname) throws NoSuchVariableException {
+    // Which Frame to lookup first doesn't matter because update prevents clashes.
+    if (lexicalFrame != null) {
+      Object lexicalValue = lexicalFrame.get(varname);
+      if (lexicalValue != null) {
+        return lexicalValue;
+      }
+    }
+    Object globalValue = globalFrame.get(varname);
+    Object dynamicValue = dynamicFrame.get(varname);
+    if (globalValue == null && dynamicValue == null) {
+      throw new NoSuchVariableException(varname);
+    }
+    if (knownGlobalVariables != null) {
+      knownGlobalVariables.add(varname);
+    }
+    if (globalValue != null) {
+      return globalValue;
+    }
+    return dynamicValue;
   }
 
   /**
-   * Remove the variable from the environment, returning
-   * any previous mapping (null if there was none).
+   * Like {@link #lookup(String)}, but instead of throwing an exception in the case
+   * where <code>varname</code> is not defined, <code>defaultValue</code> is returned instead.
    */
-  public Object remove(String varname) {
-    return env.remove(varname);
+  public Object lookup(String varname, Object defaultValue) {
+    Preconditions.checkState(!isSkylark);
+    try {
+      return lookup(varname);
+    } catch (NoSuchVariableException e) {
+      return defaultValue;
+    }
   }
 
   /**
-   * Returns the (immutable) set of names of all variables directly defined in this environment.
+   * @return true if varname is a known global variable,
+   * because it has been read in the context of the current function.
    */
-  public Set<String> getDirectVariableNames() {
-    return env.keySet();
+  boolean isKnownGlobalVariable(String varname) {
+    return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
+  }
+
+  public void handleEvent(Event event) {
+    eventHandler.handle(event);
   }
 
   /**
-   * Returns the (immutable) set of names of all variables defined in this
-   * environment. Exposed for testing; not very efficient!
+   * @return the (immutable) set of names of all variables defined in this
+   * Environment. Exposed for testing.
    */
   @VisibleForTesting
   public Set<String> getVariableNames() {
-    if (parent == null) {
-      return env.keySet();
-    } else {
-      Set<String> vars = new HashSet<>();
-      vars.addAll(env.keySet());
-      vars.addAll(parent.getVariableNames());
-      return vars;
+    Set<String> vars = new HashSet<>();
+    if (lexicalFrame != null) {
+      lexicalFrame.addVariableNamesTo(vars);
     }
+    globalFrame.addVariableNamesTo(vars);
+    dynamicFrame.addVariableNamesTo(vars);
+    return vars;
   }
 
   @Override
@@ -268,23 +712,29 @@ public class Environment {
   @Override
   public String toString() {
     StringBuilder out = new StringBuilder();
-    out.append("Environment{");
-    List<String> keys = new ArrayList<>(env.keySet());
-    Collections.sort(keys);
-    for (String key : keys) {
-      out.append(key).append(" -> ").append(env.get(key)).append(", ");
-    }
-    out.append("}");
-    if (parent != null) {
-      out.append("=>");
-      out.append(parent);
-    }
+    out.append("Environment(lexicalFrame=");
+    out.append(lexicalFrame);
+    out.append(", globalFrame=");
+    out.append(globalFrame);
+    out.append(", dynamicFrame=");
+    out.append(dynamicFrame);
+    out.append(", eventHandler.getClass()=");
+    out.append(eventHandler.getClass());
+    out.append(", importedExtensions=");
+    out.append(importedExtensions);
+    out.append(", isSkylark=");
+    out.append(isSkylark);
+    out.append(", fileContentHashCode=");
+    out.append(fileContentHashCode);
+    out.append(", isLoadingPhase=");
+    out.append(isLoadingPhase);
+    out.append(")");
     return out.toString();
   }
 
   /**
-   * An exception thrown when an attempt is made to lookup a non-existent
-   * variable in the environment.
+   * An Exception thrown when an attempt is made to lookup a non-existent
+   * variable in the Environment.
    */
   public static class NoSuchVariableException extends Exception {
     NoSuchVariableException(String variable) {
@@ -293,7 +743,7 @@ public class Environment {
   }
 
   /**
-   * An exception thrown when an attempt is made to import a symbol from a file
+   * An Exception thrown when an attempt is made to import a symbol from a file
    * that was not properly loaded.
    */
   public static class LoadFailedException extends Exception {
@@ -303,78 +753,156 @@ public class Environment {
     }
   }
 
-  public void setImportedExtensions(Map<PathFragment, SkylarkEnvironment> importedExtensions) {
-    this.importedExtensions = importedExtensions;
-  }
-
   public void importSymbol(PathFragment extension, Identifier symbol, String nameInLoadedFile)
       throws NoSuchVariableException, LoadFailedException {
+    Preconditions.checkState(isGlobal()); // loading is only allowed at global scope.
+
     if (!importedExtensions.containsKey(extension)) {
       throw new LoadFailedException(extension.toString());
     }
 
     Object value = importedExtensions.get(extension).lookup(nameInLoadedFile);
-    if (!isSkylark()) {
+    // TODO(bazel-team): Unify data structures between Skylark and BUILD,
+    // and stop doing the conversions below:
+    if (!isSkylark) {
       value = SkylarkType.convertFromSkylark(value);
     }
 
-    update(symbol.getName(), value);
+    try {
+      update(symbol.getName(), value);
+    } catch (EvalException e) {
+      throw new LoadFailedException(extension.toString());
+    }
+  }
+
+  /**
+   * Returns a hash code calculated from the hash code of this Environment and the
+   * transitive closure of other Environments it loads.
+   */
+  // TODO(bazel-team): to avoid O(n^2) worst case, cache this transitive hash code.
+  public String getTransitiveFileContentHashCode() {
+    Fingerprint fingerprint = new Fingerprint();
+    fingerprint.addString(Preconditions.checkNotNull(fileContentHashCode));
+    // Calculate a new hash from the hash of the loaded Environments.
+    for (Environment env : importedExtensions.values()) {
+      fingerprint.addString(env.getTransitiveFileContentHashCode());
+    }
+    return fingerprint.hexDigestAndReset();
+  }
+
+
+  /** A read-only Environment.Frame with global constants in it only */
+  public static final Frame CONSTANTS_ONLY = createConstantsGlobals();
+
+  /** A read-only Environment.Frame with initial globals for the BUILD language */
+  public static final Frame BUILD = createBuildGlobals();
+
+  /** A read-only Environment.Frame with initial globals for Skylark */
+  public static final Frame SKYLARK = createSkylarkGlobals();
+
+  private static Environment.Frame createConstantsGlobals() {
+    try (Mutability mutability = Mutability.create("CONSTANTS")) {
+      Environment env = Environment.builder(mutability).build();
+      Runtime.setupConstants(env);
+      return env.getGlobals();
+    }
   }
 
-  public ImmutableList<StackTraceElement> getStackTrace() {
-    return ImmutableList.copyOf(stackTrace);
+  private static Environment.Frame createBuildGlobals() {
+    try (Mutability mutability = Mutability.create("BUILD")) {
+      Environment env = Environment.builder(mutability).build();
+      Runtime.setupConstants(env);
+      Runtime.setupMethodEnvironment(env, MethodLibrary.buildGlobalFunctions);
+      return env.getGlobals();
+    }
   }
 
-  protected Deque<StackTraceElement> getCopyOfStackTrace() {
-    return new LinkedList<>(stackTrace);
+  private static Environment.Frame createSkylarkGlobals() {
+    try (Mutability mutability = Mutability.create("SKYLARK")) {
+      Environment env = Environment.builder(mutability).setSkylark().build();
+      Runtime.setupConstants(env);
+      Runtime.setupMethodEnvironment(env, MethodLibrary.skylarkGlobalFunctions);
+      return env.getGlobals();
+    }
   }
 
+
   /**
-   * Adds the given element to the stack trace (iff the stack is empty) and returns whether it was
-   * successful.
+   * The fail fast handler, which throws a AssertionError whenever an error or warning occurs.
    */
-  public boolean tryAddingStackTraceRoot(StackTraceElement element) {
-    if (stackTrace.isEmpty()) {
-      stackTrace.add(element);
-      return true;
+  public static final EventHandler FAIL_FAST_HANDLER = new EventHandler() {
+      @Override
+      public void handle(Event event) {
+        Preconditions.checkArgument(
+            !EventKind.ERRORS_AND_WARNINGS.contains(event.getKind()), event);
+      }
+    };
+
+  /** Mock package locator class */
+  private static final class EmptyPackageLocator implements CachingPackageLocator {
+    @Override
+    public Path getBuildFileForPackage(PackageIdentifier packageName) {
+      return null;
     }
-    return false;
   }
-  
-  public void addToStackTrace(StackTraceElement element)    {
-    stackTrace.add(element);
+
+  /** A mock package locator */
+  @VisibleForTesting
+  static final CachingPackageLocator EMPTY_PACKAGE_LOCATOR = new EmptyPackageLocator();
+
+  /**
+   * Creates a Lexer without a supporting file.
+   * @param input a list of lines of code
+   */
+  @VisibleForTesting
+  Lexer createLexer(String... input) {
+    return new Lexer(ParserInputSource.create(Joiner.on("\n").join(input), null),
+        eventHandler);
   }
 
   /**
-   * Removes the only remaining element from the stack trace.
-   *
-   * <p>This particular element describes the outer-most calling function (usually a rule).
-   *
-   * <p> This method is required since {@link FuncallExpression} does not create a new {@link
-   * Environment}, hence it has to add and remove its {@link StackTraceElement} from an existing
-   * one.
+   * Parses some String input without a supporting file, returning statements and comments.
+   * @param input a list of lines of code
    */
-  public void removeStackTraceRoot() {
-    Preconditions.checkArgument(stackTrace.size() == 1);
-    stackTrace.clear();
+  @VisibleForTesting
+  Parser.ParseResult parseFileWithComments(String... input) {
+    return isSkylark
+        ? Parser.parseFileForSkylark(
+            createLexer(input),
+            eventHandler,
+            EMPTY_PACKAGE_LOCATOR,
+            new ValidationEnvironment(this))
+        : Parser.parseFile(
+              createLexer(input),
+              eventHandler,
+              EMPTY_PACKAGE_LOCATOR,
+              /*parsePython=*/false);
   }
 
-  public void removeStackTraceElement() {
-    // TODO(fwe): find out why the precond doesn't work
-    //    Preconditions.checkArgument(stackTrace.size() > 1);
-    stackTrace.removeLast();
+  /**
+   * Parses some String input without a supporting file, returning statements only.
+   * @param input a list of lines of code
+   */
+  @VisibleForTesting
+  List<Statement> parseFile(String... input) {
+    return parseFileWithComments(input).statements;
   }
 
   /**
-   * Returns whether the given {@link BaseFunction} is part of this {@link Environment}'s stack
-   * trace.
+   * Evaluates code some String input without a supporting file.
+   * @param input a list of lines of code to evaluate
+   * @return the value of the last statement if it's an Expression or else null
    */
-  public boolean stackTraceContains(BaseFunction function) {
-    for (StackTraceElement element : stackTrace) {
-      if (element.hasFunction(function)) {
-        return true;
+  @Nullable public Object eval(String... input) throws EvalException, InterruptedException {
+    Object last = null;
+    for (Statement statement : parseFile(input)) {
+      if (statement instanceof ExpressionStatement) {
+        last = ((ExpressionStatement) statement).getExpression().eval(this);
+      } else {
+        statement.exec(this);
+        last = null;
       }
     }
-    return false;
+    return last;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java
index 82ca835ccd..714556e476 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java
@@ -200,7 +200,7 @@ public class EvalExceptionWithStackTrace extends EvalException {
       return String.format(
           "\tFile \"%s\", line %d, in %s%n\t\t%s",
           printPath(location.getPath()),
-          location.getStartLineAndColumn().getLine(),
+          location.getStartLine(),
           element.getLabel(),
           element.getCause().getLabel());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
deleted file mode 100644
index 6a24cb3cac..0000000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
+++ /dev/null
@@ -1,195 +0,0 @@
-// Copyright 2015 Google Inc. 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.annotations.VisibleForTesting;
-import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-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.packages.CachingPackageLocator;
-import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
-import com.google.devtools.build.lib.vfs.Path;
-
-import java.util.List;
-
-import javax.annotation.Nullable;
-
-/**
- * Context for the evaluation of programs.
- */
-public final class EvaluationContext {
-
-  @Nullable private EventHandler eventHandler;
-  private Environment env;
-  @Nullable private ValidationEnvironment validationEnv;
-  private boolean parsePython;
-
-  private EvaluationContext(EventHandler eventHandler, Environment env,
-      @Nullable ValidationEnvironment validationEnv, boolean parsePython) {
-    this.eventHandler = eventHandler;
-    this.env = env;
-    this.validationEnv = validationEnv;
-    this.parsePython = parsePython;
-  }
-
-  /**
-   * The fail fast handler, which throws a runtime exception whenever we encounter an error event.
-   */
-  public static final EventHandler FAIL_FAST_HANDLER = new EventHandler() {
-      @Override
-      public void handle(Event event) {
-        Preconditions.checkArgument(
-            !EventKind.ERRORS_AND_WARNINGS.contains(event.getKind()), event);
-      }
-    };
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env,
-      boolean parsePython) {
-    return new EvaluationContext(eventHandler, env, null, parsePython);
-  }
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env) {
-    return newBuildContext(eventHandler, env, false);
-  }
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler) {
-    return newBuildContext(eventHandler, new Environment());
-  }
-
-  public static EvaluationContext newSkylarkContext(
-      Environment env, ValidationEnvironment validationEnv) {
-    return new EvaluationContext(env.getEventHandler(), env, validationEnv, false);
-  }
-
-  public static EvaluationContext newSkylarkContext(EventHandler eventHandler) {
-    return newSkylarkContext(new SkylarkEnvironment(eventHandler), new ValidationEnvironment());
-  }
-
-  /** Base context for Skylark evaluation for internal use only, while initializing builtins */
-  static final EvaluationContext SKYLARK_INITIALIZATION = newSkylarkContext(FAIL_FAST_HANDLER);
-
-  @VisibleForTesting
-  public Environment getEnvironment() {
-    return env;
-  }
-
-  /** Mock package locator */
-  private static final class EmptyPackageLocator implements CachingPackageLocator {
-    @Override
-    public Path getBuildFileForPackage(PackageIdentifier packageName) {
-      return null;
-    }
-  }
-
-  /** An empty package locator */
-  private static final CachingPackageLocator EMPTY_PACKAGE_LOCATOR = new EmptyPackageLocator();
-
-  /** Create a Lexer without a supporting file */
-  @VisibleForTesting
-  Lexer createLexer(String... input) {
-    return new Lexer(ParserInputSource.create(Joiner.on("\n").join(input), null),
-        eventHandler);
-  }
-
-  /** Is this a Skylark evaluation context? */
-  public boolean isSkylark() {
-    return env.isSkylark();
-  }
-
-  /** Parse a string without a supporting file, returning statements and comments */
-  @VisibleForTesting
-  Parser.ParseResult parseFileWithComments(String... input) {
-    return isSkylark()
-        ? Parser.parseFileForSkylark(createLexer(input), eventHandler, null, validationEnv)
-        : Parser.parseFile(createLexer(input), eventHandler, EMPTY_PACKAGE_LOCATOR, parsePython);
-  }
-
-  /** Parse a string without a supporting file, returning statements only */
-  @VisibleForTesting
-  List<Statement> parseFile(String... input) {
-    return parseFileWithComments(input).statements;
-  }
-
-  /** Parse an Expression from string without a supporting file */
-  @VisibleForTesting
-  Expression parseExpression(String... input) {
-    return Parser.parseExpression(createLexer(input), eventHandler);
-  }
-
-  /** Evaluate an Expression */
-  @VisibleForTesting
-  Object evalExpression(Expression expression) throws EvalException, InterruptedException {
-    return expression.eval(env);
-  }
-
-  /** Evaluate an Expression as parsed from String-s */
-  Object evalExpression(String... input) throws EvalException, InterruptedException {
-    return evalExpression(parseExpression(input));
-  }
-
-  /** Parse a build (not Skylark) Statement from string without a supporting file */
-  @VisibleForTesting
-  Statement parseStatement(String... input) {
-    return Parser.parseStatement(createLexer(input), eventHandler);
-  }
-
-  /**
-   * Evaluate a Statement
-   * @param statement the Statement
-   * @return the value of the evaluation, if it's an Expression, or else null
-   */
-  @Nullable private Object eval(Statement statement) throws EvalException, InterruptedException {
-    if (statement instanceof ExpressionStatement) {
-      return evalExpression(((ExpressionStatement) statement).getExpression());
-    }
-    statement.exec(env);
-    return null;
-  }
-
-  /**
-   * Evaluate a list of Statement-s
-   * @return the value of the last statement if it's an Expression or else null
-   */
-  @Nullable private Object eval(List<Statement> statements)
-      throws EvalException, InterruptedException {
-    Object last = null;
-    for (Statement statement : statements) {
-      last = eval(statement);
-    }
-    return last;
-  }
-
-  /** Update a variable in the environment, in fluent style */
-  public EvaluationContext update(String varname, Object value) throws EvalException {
-    env.update(varname, value);
-    if (validationEnv != null) {
-      validationEnv.declare(varname, null);
-    }
-    return this;
-  }
-
-  /** Lookup a variable in the environment */
-  public Object lookup(String varname) throws NoSuchVariableException {
-    return env.lookup(varname);
-  }
-
-  /** Evaluate a series of statements */
-  public Object eval(String... input) throws EvalException, InterruptedException {
-    return eval(parseFile(input));
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
index b7842d4c4c..1886843e86 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
@@ -42,8 +42,8 @@ public abstract class Expression extends ASTNode {
   /**
    * Returns the inferred type of the result of the Expression.
    *
-   * <p>Checks the semantics of the Expression using the SkylarkEnvironment according to
-   * the rules of the Skylark language, throws EvalException in case of a semantical error.
+   * <p>Checks the semantics of the Expression using the {@link Environment} according to
+   * the rules of the Skylark language, throws {@link EvalException} in case of a semantical error.
    *
    * @see Statement
    */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 8d1eb56f9c..76737dd4c1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -353,21 +353,11 @@ public final class FuncallExpression extends Expression {
   // TODO(bazel-team): If there's exactly one usable method, this works. If there are multiple
   // matching methods, it still can be a problem. Figure out how the Java compiler does it
   // exactly and copy that behaviour.
-  // TODO(bazel-team): check if this and SkylarkBuiltInFunctions.createObject can be merged.
-  private Object invokeJavaMethod(
-      Object obj, Class<?> objClass, String methodName, List<Object> args, boolean hasKwArgs)
-      throws EvalException {
+  private MethodDescriptor findJavaMethod(
+      Class<?> objClass, String methodName, List<Object> args) throws EvalException {
     MethodDescriptor matchingMethod = null;
     List<MethodDescriptor> methods = getMethods(objClass, methodName, args.size(), getLocation());
     if (methods != null) {
-      if (hasKwArgs) {
-        throw new EvalException(
-            func.getLocation(),
-            String.format(
-                "Keyword arguments are not allowed when calling a java method"
-                + "\nwhile calling method '%s' on object of type %s",
-                func.getName(), EvalUtils.getDataTypeNameFromClass(objClass)));
-      }
       for (MethodDescriptor method : methods) {
         Class<?>[] params = method.getMethod().getParameterTypes();
         int i = 0;
@@ -391,12 +381,11 @@ public final class FuncallExpression extends Expression {
       }
     }
     if (matchingMethod != null && !matchingMethod.getAnnotation().structField()) {
-      return callMethod(matchingMethod, methodName, obj, args.toArray(), getLocation());
-    } else {
-      throw new EvalException(getLocation(), "No matching method found for "
-          + formatMethod(methodName, args) + " in "
-          + EvalUtils.getDataTypeNameFromClass(objClass));
+      return matchingMethod;
     }
+    throw new EvalException(getLocation(), "No matching method found for "
+        + formatMethod(methodName, args) + " in "
+        + EvalUtils.getDataTypeNameFromClass(objClass));
   }
 
   private String formatMethod(String methodName, List<Object> args) {
@@ -490,20 +479,7 @@ public final class FuncallExpression extends Expression {
 
   @Override
   Object eval(Environment env) throws EvalException, InterruptedException {
-    // Adds the calling rule to the stack trace of the Environment if it is a BUILD environment.
-    // There are two reasons for this:
-    // a) When using aliases in load(), the rule class name in the BUILD file will differ from
-    //    the implementation name in the bzl file. Consequently, we need to store the calling name.
-    // b) We need the location of the calling rule inside the BUILD file.
-    boolean hasAddedElement =
-        env.isSkylark() ? false : env.tryAddingStackTraceRoot(new StackTraceElement(func, args));
-    try {
-      return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
-    } finally {
-      if (hasAddedElement) {
-        env.removeStackTraceRoot();
-      }
-    }
+    return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
   }
 
   /**
@@ -550,15 +526,28 @@ public final class FuncallExpression extends Expression {
       // When calling a Java method, the name is not in the Environment,
       // so evaluating 'func' would fail.
       evalArguments(posargs, kwargs, env, null);
+      Class<?> objClass;
+      Object obj;
       if (objValue instanceof Class<?>) {
-        // Static Java method call. We can return the value from here directly because
-        // invokeJavaMethod() has special checks.
-        return invokeJavaMethod(
-            null, (Class<?>) objValue, func.getName(), posargs.build(), !kwargs.isEmpty());
+        // Static call
+        obj = null;
+        objClass = (Class<?>) objValue;
       } else {
-        return invokeJavaMethod(
-            objValue, objValue.getClass(), func.getName(), posargs.build(), !kwargs.isEmpty());
+        obj = objValue;
+        objClass = objValue.getClass();
+      }
+      String name = func.getName();
+      ImmutableList<Object> args = posargs.build();
+      MethodDescriptor method = findJavaMethod(objClass, name, args);
+      if (!kwargs.isEmpty()) {
+        throw new EvalException(
+            func.getLocation(),
+            String.format(
+                "Keyword arguments are not allowed when calling a java method"
+                + "\nwhile calling method '%s' for type %s",
+                name, EvalUtils.getDataTypeNameFromClass(objClass)));
       }
+      return callMethod(method, name, obj, args.toArray(), getLocation());
     } else {
       throw new EvalException(
           getLocation(),
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
index ae7c0272ef..acc09c9859 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
@@ -50,10 +50,14 @@ public class FunctionDefStatement extends Statement {
         defaultValues.add(expr.eval(env));
       }
     }
-    env.update(ident.getName(), new UserDefinedFunction(
-        ident, FunctionSignature.WithValues.<Object, SkylarkType>create(
-            signature.getSignature(), defaultValues, types),
-        statements, (SkylarkEnvironment) env));
+    env.update(
+        ident.getName(),
+        new UserDefinedFunction(
+            ident,
+            FunctionSignature.WithValues.<Object, SkylarkType>create(
+                signature.getSignature(), defaultValues, types),
+            statements,
+            env.getGlobals()));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index df5f486e0b..1a39755b5a 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -84,8 +84,7 @@ public class LValue implements Serializable {
     if (env.isSkylark()) {
       // The variable may have been referenced successfully if a global variable
       // with the same name exists. In this case an Exception needs to be thrown.
-      SkylarkEnvironment skylarkEnv = (SkylarkEnvironment) env;
-      if (skylarkEnv.hasBeenReadGlobalVariable(ident.getName())) {
+      if (env.isKnownGlobalVariable(ident.getName())) {
         throw new EvalException(
             loc,
             String.format(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 996ae41bbe..b1ca1f60a0 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -776,7 +776,7 @@ public class MethodLibrary {
       new BuiltinFunction("append") {
         public Runtime.NoneType invoke(List<Object> self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isSkylark()) {
+          if (env.isCallerSkylark()) {
             throw new EvalException(loc,
                 "function 'append' is not available in Skylark");
           }
@@ -806,7 +806,7 @@ public class MethodLibrary {
       new BuiltinFunction("extend") {
         public Runtime.NoneType invoke(List<Object> self, List<Object> items,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isSkylark()) {
+          if (env.isCallerSkylark()) {
             throw new EvalException(loc,
                 "function 'append' is not available in Skylark");
           }
@@ -920,7 +920,7 @@ public class MethodLibrary {
       List<Object> list = Lists.newArrayListWithCapacity(dict.size());
       for (Map.Entry<?, ?> entries : dict.entrySet()) {
         List<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
-        list.add(env.isSkylark() ? SkylarkList.tuple(item) : item);
+        list.add(env.isCallerSkylark() ? SkylarkList.tuple(item) : item);
       }
       return convert(list, env, loc);
     }
@@ -966,7 +966,7 @@ public class MethodLibrary {
   @SuppressWarnings("unchecked")
   private static Iterable<Object> convert(Collection<?> list, Environment env, Location loc)
       throws EvalException {
-    if (env.isSkylark()) {
+    if (env.isCallerSkylark()) {
       return SkylarkList.list(list, loc);
     } else {
       return Lists.newArrayList(list);
@@ -1386,7 +1386,7 @@ public class MethodLibrary {
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction print = new BuiltinFunction("print") {
     public Runtime.NoneType invoke(String sep, SkylarkList starargs,
-        Location loc, SkylarkEnvironment env) throws EvalException {
+        Location loc, Environment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
                 @Override
@@ -1493,19 +1493,6 @@ public class MethodLibrary {
 
 
   /**
-   * Set up a given environment for supported class methods.
-   */
-  public static void setupMethodEnvironment(Environment env) {
-    setupMethodEnvironment(env, env.isSkylark() ? skylarkGlobalFunctions : buildGlobalFunctions);
-  }
-
-  private static void setupMethodEnvironment(Environment env, Iterable<BaseFunction> functions) {
-    for (BaseFunction function : functions) {
-      env.update(function.getName(), function);
-    }
-  }
-
-  /**
    * Collect global functions for the validation environment.
    */
   public static void setupValidationEnvironment(Set<String> builtIn) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
new file mode 100644
index 0000000000..5120f8d0d2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
@@ -0,0 +1,136 @@
+// Copyright 2015 Google Inc. 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.Preconditions;
+
+/**
+ * A Mutability is a resource associated with an {@link Environment} during an evaluation,
+ * that gives those who possess it a revokable capability to mutate this Environment and
+ * the objects created within that {@link Environment}. At the end of the evaluation,
+ * the resource is irreversibly closed, at which point the capability is revoked,
+ * and it is not possible to mutate either this {@link Environment} or these objects.
+ *
+ * <p>Evaluation in an {@link Environment} may thus mutate objects created in the same
+ * {@link Environment}, but may not mutate {@link Freezable} objects (lists, sets, dicts)
+ * created in a previous, concurrent or future {@link Environment}, and conversely,
+ * the bindings and objects in this {@link Environment} will be protected from
+ * mutation by evaluation in a different {@link Environment}.
+ *
+ * <p>Only a single thread may use the {@link Environment} and objects created within it while the
+ * Mutability is still mutable as tested by {@link #isMutable}. Once the Mutability resource
+ * is closed, the {@link Environment} and its objects are immutable and can be simultaneously used
+ * by arbitrarily many threads.
+ *
+ * <p>The safe usage of a Mutability requires to always use try-with-resource style:
+ * <code>try(Mutability mutability = Mutability.create(fmt, ...)) { ... }</code>
+ * Thus, you can create a Mutability, build an {@link Environment}, mutate that {@link Environment}
+ * and create mutable objects as you evaluate in that {@link Environment}, and finally return the
+ * resulting {@link Environment}, at which point the resource is closed, and the {@link Environment}
+ * and the objects it contains all become immutable.
+ * (Unsafe usage is allowed only in test code that is not part of the Bazel jar.)
+ */
+// TODO(bazel-team): When we start using Java 8, this safe usage pattern can be enforced
+// through the use of a higher-order function.
+public final class Mutability implements AutoCloseable {
+  private boolean isMutable;
+  private final Object annotation; // For error reporting
+
+  /**
+   * Creates a Mutability.
+   * @param annotation an Object used for error reporting,
+   * describing to the user the context in which this Mutability was active.
+   */
+  private Mutability(Object annotation) {
+    this.isMutable = true;
+    this.annotation = Preconditions.checkNotNull(annotation);
+  }
+
+  /**
+   * Creates a Mutability.
+   * @param pattern is a {@link Printer#format} pattern used to lazily produce a string
+   * for error reporting
+   * @param arguments are the optional {@link Printer#format} arguments to produce that string
+   */
+  public static Mutability create(String pattern, Object... arguments) {
+    return new Mutability(Printer.formattable(pattern, arguments));
+  }
+
+  Object getAnnotation() {
+    return annotation;
+  }
+
+  @Override
+  public String toString() {
+    return String.format(isMutable ? "[%s]" : "(%s)", annotation);
+  }
+
+  boolean isMutable() {
+    return isMutable;
+  }
+
+  /**
+   * Freezes this Mutability, marking as immutable all {@link Freezable} objects that use it.
+   */
+  @Override
+  public void close() {
+    isMutable = false;
+  }
+
+  /**
+   * A MutabilityException will be thrown when the user attempts to mutate an object he shouldn't.
+   */
+  static class MutabilityException extends Exception {
+    MutabilityException(String message) {
+      super(message);
+    }
+  }
+
+  /**
+   * Each {@link Freezable} object possesses a revokable Mutability attribute telling whether
+   * the object is still mutable. All {@link Freezable} objects created in the same
+   * {@link Environment} will share the same Mutability, inherited from this {@link Environment}.
+   * Only evaluation in the same {@link Environment} is allowed to mutate these objects,
+   * and only until the Mutability is irreversibly revoked.
+   */
+  public interface Freezable {
+    /**
+     * Returns the {@link Mutability} capability associated with this Freezable object.
+     */
+    Mutability mutability();
+  }
+
+  /**
+   * Checks that this Freezable object can be mutated from the given {@link Environment}.
+   * @param object a Freezable object that we check is still mutable.
+   * @param env the {@link Environment} attempting the mutation.
+   * @throws MutabilityException when the object was frozen already, or is from another context.
+   */
+  public static void checkMutable(Freezable object, Environment env)
+      throws MutabilityException {
+    if (!object.mutability().isMutable()) {
+      throw new MutabilityException("trying to mutate a frozen object");
+    }
+    // Consider an {@link Environment} e1, in which is created {@link UserDefinedFunction} f1,
+    // that closes over some variable v1 bound to list l1. If somehow, via the magic of callbacks,
+    // f1 or l1 is passed as argument to some function f2 evaluated in {@link environment} e2
+    // while e1 is be mutable, e2, being a different {@link Environment}, should not be
+    // allowed to mutate objects from e1. It's a bug, that shouldn't happen in our current code
+    // base, so we throw an AssertionError. If in the future such situations are allowed to happen,
+    // then we should throw a MutabilityException instead.
+    if (!object.mutability().equals(env.mutability())) {
+      throw new AssertionError("trying to mutate an object from a different context");
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 50ef2546d5..9230d6be72 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -33,11 +33,11 @@ public final class Runtime {
 
   @SkylarkSignature(name = "True", returnType = Boolean.class,
       doc = "Literal for the boolean true.")
-  static final Boolean TRUE = true;
+  private static final Boolean TRUE = true;
 
   @SkylarkSignature(name = "False", returnType = Boolean.class,
       doc = "Literal for the boolean false.")
-  static final Boolean FALSE = false;
+  private static final Boolean FALSE = false;
 
   /**
    * There should be only one instance of this type to allow "== None" tests.
@@ -70,11 +70,11 @@ public final class Runtime {
   /**
    * Set up a given environment for supported class methods.
    */
-  static Environment setupConstants(Environment env) throws EvalException {
+  static Environment setupConstants(Environment env) {
     // In Python 2.x, True and False are global values and can be redefined by the user.
     // In Python 3.x, they are keywords. We implement them as values, for the sake of
     // simplicity. We define them as Boolean objects.
-    return env.update("False", FALSE).update("True", TRUE).update("None", NONE);
+    return env.setup("False", FALSE).setup("True", TRUE).setup("None", NONE);
   }
 
 
@@ -128,7 +128,7 @@ public final class Runtime {
   public static void registerModuleGlobals(Environment env, Class<?> moduleClass) {
     try {
       if (moduleClass.isAnnotationPresent(SkylarkModule.class)) {
-        env.update(
+        env.setup(
             moduleClass.getAnnotation(SkylarkModule.class).name(), moduleClass.newInstance());
       }
       for (Field field : moduleClass.getDeclaredFields()) {
@@ -142,7 +142,7 @@ public final class Runtime {
           if (!(value instanceof BuiltinFunction.Factory
               || (value instanceof BaseFunction
                   && !annotation.objectType().equals(Object.class)))) {
-            env.update(annotation.name(), value);
+            env.setup(annotation.name(), value);
           }
         }
       }
@@ -168,9 +168,9 @@ public final class Runtime {
   }
 
   static void setupMethodEnvironment(
-      Environment env, Iterable<BaseFunction> functions) throws EvalException {
+      Environment env, Iterable<BaseFunction> functions) {
     for (BaseFunction function : functions) {
-      env.update(function.getName(), function);
+      env.setup(function.getName(), function);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
index 94b1917ab6..6140acb0b0 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
@@ -22,21 +22,25 @@ public class SkylarkCallbackFunction {
 
   private final BaseFunction callback;
   private final FuncallExpression ast;
-  private final SkylarkEnvironment funcallEnv;
+  private final Environment funcallEnv;
 
-  public SkylarkCallbackFunction(BaseFunction callback, FuncallExpression ast,
-      SkylarkEnvironment funcallEnv) {
+  public SkylarkCallbackFunction(
+      BaseFunction callback, FuncallExpression ast, Environment funcallEnv) {
     this.callback = callback;
     this.ast = ast;
     this.funcallEnv = funcallEnv;
   }
 
   public Object call(ClassObject ctx, Object... arguments) throws EvalException {
-    try {
+    try (Mutability mutability = Mutability.create("callback %s", callback)) {
+      Environment env = Environment.builder(mutability)
+          .setSkylark()
+          .setEventHandler(funcallEnv.getEventHandler())
+          .setGlobals(funcallEnv.getGlobals())
+          .build();
       return callback.call(
-          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, funcallEnv);
-    } catch (InterruptedException | ClassCastException
-        | IllegalArgumentException e) {
+          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, env);
+    } catch (InterruptedException | ClassCastException | IllegalArgumentException e) {
       throw new EvalException(ast.getLocation(), e.getMessage());
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
deleted file mode 100644
index 0ff19f90c4..0000000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
+++ /dev/null
@@ -1,205 +0,0 @@
-// Copyright 2014 Google Inc. 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.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.util.Fingerprint;
-
-import java.io.Serializable;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map.Entry;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * The environment for Skylark.
- */
-public class SkylarkEnvironment extends Environment implements Serializable {
-
-  /**
-   * This set contains the variable names of all the successful lookups from the global
-   * environment. This is necessary because if in a function definition something
-   * reads a global variable after which a local variable with the same name is assigned an
-   * Exception needs to be thrown.
-   */
-  private final Set<String> readGlobalVariables = new HashSet<>();
-
-  @Nullable private String fileContentHashCode;
-
-  /**
-   * Creates a Skylark Environment for function calling, from the global Environment of the
-   * caller Environment (which must be a Skylark Environment).
-   */
-  public static SkylarkEnvironment createEnvironmentForFunctionCalling(
-      Environment callerEnv, SkylarkEnvironment definitionEnv,
-      UserDefinedFunction function) throws EvalException {
-    if (callerEnv.stackTraceContains(function)) {
-      throw new EvalException(
-          function.getLocation(),
-          "Recursion was detected when calling '" + function.getName() + "' from '"
-          + Iterables.getLast(callerEnv.getStackTrace()).getName() + "'");
-    }
-    SkylarkEnvironment childEnv =
-        // Always use the caller Environment's EventHandler. We cannot assume that the
-        // definition Environment's EventHandler is still working properly.
-        new SkylarkEnvironment(
-            definitionEnv, callerEnv.getCopyOfStackTrace(), callerEnv.eventHandler);
-    if (callerEnv.isLoadingPhase()) {
-      childEnv.setLoadingPhase();
-    }
-
-    try {
-      for (String varname : callerEnv.propagatingVariables) {
-        childEnv.updateAndPropagate(varname, callerEnv.lookup(varname));
-      }
-    } catch (NoSuchVariableException e) {
-      // This should never happen.
-      throw new IllegalStateException(e);
-    }
-    return childEnv;
-  }
-
-  private SkylarkEnvironment(SkylarkEnvironment definitionEnv,
-      Deque<StackTraceElement> stackTrace, EventHandler eventHandler) {
-    super(definitionEnv.getGlobalEnvironment(), stackTrace);
-    this.eventHandler = Preconditions.checkNotNull(eventHandler,
-        "EventHandler cannot be null in an Environment which calls into Skylark");
-  }
-
-  /**
-   * Creates a global SkylarkEnvironment.
-   */
-  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode,
-      Deque<StackTraceElement> stackTrace) {
-    super(stackTrace);
-    this.eventHandler = eventHandler;
-    this.fileContentHashCode = astFileContentHashCode;
-  }
-
-  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode) {
-    this(eventHandler, astFileContentHashCode, new LinkedList<StackTraceElement>());
-  }
-
-  @VisibleForTesting
-  public SkylarkEnvironment(EventHandler eventHandler) {
-    this(eventHandler, null);
-  }
-
-  public SkylarkEnvironment(SkylarkEnvironment globalEnv) {
-    super(globalEnv);
-    this.eventHandler = globalEnv.eventHandler;
-  }
-
-  /**
-   * Clones this Skylark global environment.
-   */
-  public SkylarkEnvironment cloneEnv(EventHandler eventHandler) {
-    Preconditions.checkArgument(isGlobal());
-    SkylarkEnvironment newEnv =
-        new SkylarkEnvironment(eventHandler, this.fileContentHashCode, getCopyOfStackTrace());
-    for (Entry<String, Object> entry : env.entrySet()) {
-      newEnv.env.put(entry.getKey(), entry.getValue());
-    }
-    return newEnv;
-  }
-
-  /**
-   * Returns the global environment. Only works for Skylark environments. For the global Skylark
-   * environment this method returns this Environment.
-   */
-  public SkylarkEnvironment getGlobalEnvironment() {
-    // If there's a parent that's the global environment, otherwise this is.
-    return parent != null ? (SkylarkEnvironment) parent : this;
-  }
-
-  /**
-   * Returns true if this is a Skylark global environment.
-   */
-  @Override
-  public boolean isGlobal() {
-    return parent == null;
-  }
-
-  /**
-   * Returns true if varname has been read as a global variable.
-   */
-  public boolean hasBeenReadGlobalVariable(String varname) {
-    return readGlobalVariables.contains(varname);
-  }
-
-  @Override
-  public boolean isSkylark() {
-    return true;
-  }
-
-  /**
-   * @return the value from the environment whose name is "varname".
-   * @throws NoSuchVariableException if the variable is not defined in the environment.
-   */
-  @Override
-  public Object lookup(String varname) throws NoSuchVariableException {
-    Object value = env.get(varname);
-    if (value == null) {
-      if (parent != null && parent.hasVariable(varname)) {
-        readGlobalVariables.add(varname);
-        return parent.lookup(varname);
-      }
-      throw new NoSuchVariableException(varname);
-    }
-    return value;
-  }
-
-  /**
-   * Like <code>lookup(String)</code>, but instead of throwing an exception in
-   * the case where "varname" is not defined, "defaultValue" is returned instead.
-   */
-  @Override
-  public Object lookup(String varname, Object defaultValue) {
-    throw new UnsupportedOperationException();
-  }
-
-  /**
-   * Returns the class of the variable or null if the variable does not exist. This function
-   * works only in the local Environment, it doesn't check the global Environment.
-   */
-  public Class<?> getVariableType(String varname) {
-    Object variable = env.get(varname);
-    return variable != null ? EvalUtils.getSkylarkType(variable.getClass()) : null;
-  }
-
-  public void handleEvent(Event event) {
-    eventHandler.handle(event);
-  }
-
-  /**
-   * Returns a hash code calculated from the hash code of this Environment and the
-   * transitive closure of other Environments it loads.
-   */
-  public String getTransitiveFileContentHashCode() {
-    Fingerprint fingerprint = new Fingerprint();
-    fingerprint.addString(Preconditions.checkNotNull(fileContentHashCode));
-    // Calculate a new hash from the hash of the loaded Environments.
-    for (SkylarkEnvironment env : importedExtensions.values()) {
-      fingerprint.addString(env.getTransitiveFileContentHashCode());
-    }
-    return fingerprint.hexDigestAndReset();
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index bf3c8321c0..6b316258ee 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -204,8 +204,13 @@ public class SkylarkSignatureProcessor {
     } else if (param.defaultValue().isEmpty()) {
       return Runtime.NONE;
     } else {
-      try {
-        return EvaluationContext.SKYLARK_INITIALIZATION.evalExpression(param.defaultValue());
+      try (Mutability mutability = Mutability.create("initialization")) {
+        return Environment.builder(mutability)
+            .setSkylark()
+            .setGlobals(Environment.CONSTANTS_ONLY)
+            .setEventHandler(Environment.FAIL_FAST_HANDLER)
+            .build()
+            .eval(param.defaultValue());
       } catch (Exception e) {
         throw new RuntimeException(String.format(
             "Exception while processing @SkylarkSignature.Param %s, default value %s",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
index ca89b1ab43..2c99209b3e 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
@@ -27,8 +27,8 @@ public abstract class Statement extends ASTNode {
   abstract void exec(Environment env) throws EvalException, InterruptedException;
 
   /**
-   * Checks the semantics of the Statement using the SkylarkEnvironment according to
-   * the rules of the Skylark language. The SkylarkEnvironment can be used e.g. to check
+   * Checks the semantics of the Statement using the Environment according to
+   * the rules of the Skylark language. The Environment can be used e.g. to check
    * variable type collision, read only variables, detecting recursion, existence of
    * built-in variables, functions, etc.
    *
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 f50e6ee5f1..537f29f632 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,6 +14,7 @@
 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.events.Location.LineAndColumn;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
@@ -26,15 +27,16 @@ import com.google.devtools.build.lib.vfs.PathFragment;
 public class UserDefinedFunction extends BaseFunction {
 
   private final ImmutableList<Statement> statements;
-  private final SkylarkEnvironment definitionEnv;
+
+  // we close over the globals at the time of definition
+  private final Environment.Frame definitionGlobals;
 
   protected UserDefinedFunction(Identifier function,
       FunctionSignature.WithValues<Object, SkylarkType> signature,
-      ImmutableList<Statement> statements, SkylarkEnvironment definitionEnv) {
+      ImmutableList<Statement> statements, Environment.Frame definitionGlobals) {
     super(function.getName(), signature, function.getLocation());
-
     this.statements = statements;
-    this.definitionEnv = definitionEnv;
+    this.definitionGlobals = definitionGlobals;
   }
 
   public FunctionSignature.WithValues<Object, SkylarkType> getFunctionSignature() {
@@ -48,23 +50,36 @@ public class UserDefinedFunction extends BaseFunction {
   @Override
   public Object call(Object[] arguments, FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    ImmutableList<String> names = signature.getSignature().getNames();
-
-    // Registering the functions's arguments as variables in the local Environment
-    int i = 0;
-    for (String name : names) {
-      env.update(name, arguments[i++]);
+    if (!env.mutability().isMutable()) {
+      throw new EvalException(getLocation(), "Trying to call in frozen environment");
+    }
+    if (env.getStackTrace().contains(this)) {
+      throw new EvalException(getLocation(),
+          String.format("Recursion was detected when calling '%s' from '%s'",
+              getName(), Iterables.getLast(env.getStackTrace()).getName()));
     }
 
     long startTimeProfiler = Profiler.nanoTimeMaybe();
     Statement lastStatement = null;
     try {
-      for (Statement stmt : statements) {
-        lastStatement = stmt;
-        stmt.exec(env);
+      env.enterScope(this, ast, definitionGlobals);
+      ImmutableList<String> names = signature.getSignature().getNames();
+
+      // Registering the functions's arguments as variables in the local Environment
+      int i = 0;
+      for (String name : names) {
+        env.update(name, arguments[i++]);
+      }
+
+      try {
+        for (Statement stmt : statements) {
+          lastStatement = stmt;
+          stmt.exec(env);
+        }
+      } catch (ReturnStatement.ReturnException e) {
+        return e.getValue();
       }
-    } catch (ReturnStatement.ReturnException e) {
-      return e.getValue();
+      return Runtime.NONE;
     } catch (EvalExceptionWithStackTrace ex) {
       // We need this block since the next "catch" must only catch EvalExceptions that don't have a
       // stack trace yet.
@@ -79,8 +94,8 @@ public class UserDefinedFunction extends BaseFunction {
           startTimeProfiler,
           ProfilerTask.SKYLARK_USER_FN,
           getLocationPathAndLine() + "#" + getName());
+      env.exitScope();
     }
-    return Runtime.NONE;
   }
 
   /**
@@ -105,14 +120,4 @@ public class UserDefinedFunction extends BaseFunction {
     }
     return builder.toString();
   }
-
-
-  /**
-   * Creates a new environment for the execution of this function.
-   */
-  @Override
-  protected Environment getOrCreateChildEnvironment(Environment parent) throws EvalException {
-   return SkylarkEnvironment.createEnvironmentForFunctionCalling(
-       parent, definitionEnv, this);
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
index 9b71f96acc..9d56271434 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
@@ -15,7 +15,6 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.events.Location;
 
 import java.util.HashMap;
@@ -31,7 +30,7 @@ import java.util.Stack;
  * @see Statement#validate
  * @see Expression#validate
  */
-public class ValidationEnvironment {
+public final class ValidationEnvironment {
 
   private final ValidationEnvironment parent;
 
@@ -45,9 +44,6 @@ public class ValidationEnvironment {
   // branches of if-else statements.
   private Stack<Set<String>> futureReadOnlyVariables = new Stack<>();
 
-  // Whether this validation environment is not modified therefore clonable or not.
-  private boolean clonable;
-
   /**
    * Tracks the number of nested for loops that contain the statement that is currently being
    * validated
@@ -55,38 +51,14 @@ public class ValidationEnvironment {
   private int loopCount = 0;
 
   /**
-   * Create a ValidationEnvironment for a given global Environment
+   * Create a ValidationEnvironment for a given global Environment.
    */
   public ValidationEnvironment(Environment env) {
-    this(env.getVariableNames());
     Preconditions.checkArgument(env.isGlobal());
-  }
-
-  public ValidationEnvironment(Set<String> builtinVariables) {
     parent = null;
+    Set<String> builtinVariables = env.getVariableNames();
     variables.addAll(builtinVariables);
     readOnlyVariables.addAll(builtinVariables);
-    clonable = true;
-  }
-
-  private ValidationEnvironment(Set<String> builtinVariables, Set<String> readOnlyVariables) {
-    parent = null;
-    this.variables = new HashSet<>(builtinVariables);
-    this.readOnlyVariables = new HashSet<>(readOnlyVariables);
-    clonable = false;
-  }
-
-  // ValidationEnvironment for a new Environment()
-  private static ImmutableSet<String> globalTypes = ImmutableSet.of("False", "True", "None");
-
-  public ValidationEnvironment() {
-    this(globalTypes);
-  }
-
-  @Override
-  public ValidationEnvironment clone() {
-    Preconditions.checkState(clonable);
-    return new ValidationEnvironment(variables, readOnlyVariables);
   }
 
   /**
@@ -95,7 +67,6 @@ public class ValidationEnvironment {
   public ValidationEnvironment(ValidationEnvironment parent) {
     // Don't copy readOnlyVariables: Variables may shadow global values.
     this.parent = parent;
-    this.clonable = false;
   }
 
   /**
@@ -120,7 +91,6 @@ public class ValidationEnvironment {
     }
     variables.add(varname);
     variableLocations.put(varname, location);
-    clonable = false;
   }
 
   private void checkReadonly(String varname, Location location) throws EvalException {
@@ -133,7 +103,8 @@ public class ValidationEnvironment {
    * Returns true if the symbol exists in the validation environment.
    */
   public boolean hasSymbolInEnvironment(String varname) {
-    return variables.contains(varname) || topLevel().variables.contains(varname);
+    return variables.contains(varname)
+        || (parent != null && topLevel().variables.contains(varname));
   }
 
   private ValidationEnvironment topLevel() {
@@ -147,7 +118,6 @@ public class ValidationEnvironment {
    */
   public void startTemporarilyDisableReadonlyCheckSession() {
     futureReadOnlyVariables.add(new HashSet<String>());
-    clonable = false;
   }
 
   /**
@@ -159,7 +129,6 @@ public class ValidationEnvironment {
     if (!futureReadOnlyVariables.isEmpty()) {
       futureReadOnlyVariables.peek().addAll(variables);
     }
-    clonable = false;
   }
 
   /**
@@ -167,7 +136,6 @@ public class ValidationEnvironment {
    */
   public void finishTemporarilyDisableReadonlyCheckBranch() {
     readOnlyVariables.removeAll(futureReadOnlyVariables.peek());
-    clonable = false;
   }
 
   /**