Rollback of commit 5a94e59f02833f9142bad9203acd72626b089535.

*** Reason for rollback ***

Breaks serialization of SkyValues.

--
MOS_MIGRATED_REVID=102457225

18 files changed, 750 insertions, 973 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 d28d4d30a7..8d5f48f2e0 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,29 +407,35 @@ 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 env the Environment in the function is called
+   * @param parentEnv the lexical Environment for the function call
    * @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,
-      Environment env)
+      @Nullable Environment parentEnv)
       throws EvalException, InterruptedException {
-    Preconditions.checkState(isConfigured(), "Function %s was not configured", getName());
+    Environment env = getOrCreateChildEnvironment(parentEnv);
+    env.addToStackTrace(new StackTraceElement(this, kwargs));
+    try {
+      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.BUILTIN : ast.getLocation();
+      // ast is null when called from Java (as there's no Skylark call site).
+      Location loc = ast == null ? location : 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);
+      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();
     }
   }
 
@@ -550,7 +556,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 aa9b151f99..a7547deca3 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,11 +122,9 @@ public class BuiltinFunction extends BaseFunction {
   @Override
   @Nullable
   public Object call(Object[] args,
-      FuncallExpression ast, Environment env)
+      @Nullable FuncallExpression ast, @Nullable Environment env)
       throws EvalException, InterruptedException {
-    Preconditions.checkNotNull(ast);
-    Preconditions.checkNotNull(env);
-    Location loc = ast.getLocation();
+    final Location loc = (ast == null) ? location : ast.getLocation();
 
     // Add extra arguments, if needed
     if (extraArgs != null) {
@@ -152,7 +150,6 @@ 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();
@@ -196,7 +193,6 @@ 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 25be3fd996..ed30671273 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,26 +15,18 @@
 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.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -42,280 +34,54 @@ import java.util.Set;
 import javax.annotation.Nullable;
 
 /**
- * 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.
+ * The BUILD environment.
  */
-public final class Environment implements Freezable, Serializable {
+public class Environment {
 
-  /**
-   * 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();
-    }
-  }
-
-  /**
-   * A Continuation contains data saved during a function call and restored when the function exits.
-   */
-  private static final class Continuation {
-    /** The {@link BaseFunction} being evaluated that will return into this Continuation. */
-    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;
-    }
-  }
-
-  /**
-   * 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.
-   */
-  private Frame lexicalFrame;
-
-  /**
-   * Static Frame for global variables; either the current lexical Frame if evaluation is currently
-   * happening at the global scope of a BUILD file, or the global Frame at the time of function
-   * definition if evaluation is currently happening in the body of a function. Thus functions can
-   * close over other functions defined in the same file.
-   */
-  private Frame globalFrame;
-
-  /**
-   * 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;
-
-  /**
-   * 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.
-   */
-  private final EventHandler eventHandler;
-
-  /**
-   * For each imported extensions, a global Skylark frame from which to load() individual bindings.
-   */
-  private final Map<PathFragment, Environment> importedExtensions;
+  protected final Map<String, Object> env = new HashMap<>();
 
   /**
-   * Is this Environment being executed in Skylark context?
+   * The parent environment. For Skylark it's the global environment,
+   * used for global read only variable lookup.
    */
-  private boolean isSkylark;
+  protected final Environment parent;
 
   /**
-   * Is this Environment being executed during the loading phase?
-   * Many builtin functions are only enabled during the loading phase, and check this flag.
+   * Map from a Skylark extension to an environment, which contains all symbols defined in the
+   * extension.
    */
-  private final boolean isLoadingPhase;
+  protected Map<PathFragment, SkylarkEnvironment> importedExtensions;
 
   /**
-   * 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.
+   * A set of variables propagating through function calling. It's only used to call
+   * native rules from Skylark build extensions.
    */
-  @Nullable private Set<String> knownGlobalVariables;
+  protected Set<String> propagatingVariables = new HashSet<>();
 
-  /**
-   * 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;
+  // Only used in the global environment.
+  // TODO(bazel-team): make this a final field part of constructor.
+  private boolean isLoadingPhase = false;
 
   /**
-   * 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
+   * 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.
    */
-  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;
+  boolean isLoadingPhase() {
+    return isLoadingPhase;
   }
 
   /**
-   * Exits a scope by restoring state from the current continuation
+   * Enable loading phase only functions in this Environment.
+   * This should only be done during setup before code is evaluated.
    */
-  void exitScope() {
-    Preconditions.checkNotNull(continuation);
-    lexicalFrame = continuation.lexicalFrame;
-    globalFrame = continuation.globalFrame;
-    knownGlobalVariables = continuation.knownGlobalVariables;
-    isSkylark = continuation.isSkylark;
-    continuation = continuation.continuation;
+  public void setLoadingPhase() {
+    isLoadingPhase = true;
   }
 
   /**
-   * 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.
+   * Checks that the current Evaluation context is in loading phase.
    * @param symbol name of the function being only authorized thus.
    */
   public void checkLoadingPhase(String symbol, Location loc) throws EvalException {
@@ -325,378 +91,168 @@ public final class Environment implements Freezable, Serializable {
   }
 
   /**
-   * 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.
+   * Is this a global environment?
+   * @return true if this is a global (top-level) environment
+   * as opposed to inside the body of a function
    */
-  boolean isGlobal() {
-    return lexicalFrame == null;
+  public boolean isGlobal() {
+    return true;
   }
 
   /**
-   * Is the current code Skylark?
-   * @return true if Skylark was enabled when this code was read.
+   * 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.
    */
-  // 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;
-  }
+  @Nullable protected EventHandler eventHandler;
 
   /**
-   * Is the caller of the current function executing Skylark code?
-   * @return true if this is skylark was enabled when this code was read.
+   * 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.
    */
-  // 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;
+  private Deque<StackTraceElement> stackTrace;
+
+  /**
+   * Constructs an empty root non-Skylark environment.
+   * The root environment is also the global environment.
+   */
+  public Environment(Deque<StackTraceElement> stackTrace) {
+    this.parent = null;
+    this.importedExtensions = new HashMap<>();
+    this.stackTrace = stackTrace;
+    setupGlobal();
   }
 
-  @Override
-  public Mutability mutability() {
-    // the mutability of the environment is that of its dynamic frame.
-    return dynamicFrame.mutability();
+  public Environment() {
+    this(new LinkedList<StackTraceElement>());
   }
 
   /**
-   * @return the current Frame, in which variable side-effects happen.
+   * Constructs an empty child environment.
    */
-  private Frame currentFrame() {
-    return isGlobal() ? globalFrame : lexicalFrame;
+  public Environment(Environment parent, Deque<StackTraceElement> stackTrace) {
+    Preconditions.checkNotNull(parent);
+    this.parent = parent;
+    this.importedExtensions = new HashMap<>();
+    this.stackTrace = stackTrace;
   }
 
-  /**
-   * @return the global variables for the Environment (not including dynamic bindings).
-   */
-  public Frame getGlobals() {
-    return globalFrame;
+  public Environment(Environment parent) {
+    this(parent, new LinkedList<StackTraceElement>());
   }
 
   /**
-   * 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
+   * Constructs an empty child environment with an EventHandler.
    */
+  public Environment(Environment parent, EventHandler eventHandler) {
+    this(parent);
+    this.eventHandler = Preconditions.checkNotNull(eventHandler);
+  }
+
   public EventHandler getEventHandler() {
     return eventHandler;
   }
 
-  /**
-   * @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();
+  // 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 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());
+  public boolean isSkylark() {
+    return false;
   }
 
-  /**
-   * 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;
+  protected boolean hasVariable(String varname) {
+    return env.containsKey(varname);
   }
 
   /**
-   * A Builder class for Environment
+   * @return the value from the environment whose name is "varname".
+   * @throws NoSuchVariableException if the variable is not defined in the Environment.
+   *
    */
-  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());
+  public Object lookup(String varname) throws NoSuchVariableException {
+    Object value = env.get(varname);
+    if (value == null) {
       if (parent != null) {
-        Preconditions.checkArgument(!parent.mutability().isMutable());
+        return parent.lookup(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;
+      throw new NoSuchVariableException(varname);
     }
-  }
-
-  public static Builder builder(Mutability mutability) {
-    return new Builder(mutability);
+    return value;
   }
 
   /**
-   * 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
+   * Like <code>lookup(String)</code>, but instead of throwing an exception in
+   * the case where "varname" is not defined, "defaultValue" is returned instead.
+   *
    */
-  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));
-    }
-    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);
+  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;
     }
-    return this;
+    return value;
   }
 
-
   /**
-   * 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
+   * Updates the value of variable "varname" in the environment, corresponding
+   * to an {@link AssignmentStatement}.
    */
-  public Environment update(String varname, Object value) throws EvalException {
+  public Environment update(String varname, Object value) {
     Preconditions.checkNotNull(value, "update(value == null)");
-    // 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);
-    }
+    env.put(varname, value);
     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);
-  }
-
   /**
-   * 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
+   * 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.
    */
-  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;
+  public void updateAndPropagate(String varname, Object value) {
+    update(varname, value);
+    propagatingVariables.add(varname);
   }
 
   /**
-   * 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.
+   * Remove the variable from the environment, returning
+   * any previous mapping (null if there was none).
    */
-  public Object lookup(String varname, Object defaultValue) {
-    Preconditions.checkState(!isSkylark);
-    try {
-      return lookup(varname);
-    } catch (NoSuchVariableException e) {
-      return defaultValue;
-    }
+  public Object remove(String varname) {
+    return env.remove(varname);
   }
 
   /**
-   * @return true if varname is a known global variable,
-   * because it has been read in the context of the current function.
+   * Returns the (immutable) set of names of all variables directly defined in this environment.
    */
-  boolean isKnownGlobalVariable(String varname) {
-    return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
-  }
-
-  public void handleEvent(Event event) {
-    eventHandler.handle(event);
+  public Set<String> getDirectVariableNames() {
+    return env.keySet();
   }
 
   /**
-   * @return the (immutable) set of names of all variables defined in this
-   * Environment. Exposed for testing.
+   * Returns the (immutable) set of names of all variables defined in this
+   * environment. Exposed for testing; not very efficient!
    */
   @VisibleForTesting
   public Set<String> getVariableNames() {
-    Set<String> vars = new HashSet<>();
-    if (lexicalFrame != null) {
-      lexicalFrame.addVariableNamesTo(vars);
+    if (parent == null) {
+      return env.keySet();
+    } else {
+      Set<String> vars = new HashSet<>();
+      vars.addAll(env.keySet());
+      vars.addAll(parent.getVariableNames());
+      return vars;
     }
-    globalFrame.addVariableNamesTo(vars);
-    dynamicFrame.addVariableNamesTo(vars);
-    return vars;
   }
 
   @Override
@@ -712,29 +268,23 @@ public final class Environment implements Freezable, Serializable {
   @Override
   public String toString() {
     StringBuilder out = new StringBuilder();
-    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(")");
+    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);
+    }
     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) {
@@ -743,7 +293,7 @@ public final class Environment implements Freezable, Serializable {
   }
 
   /**
-   * 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 {
@@ -753,156 +303,78 @@ public final class Environment implements Freezable, Serializable {
     }
   }
 
+  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);
-    // TODO(bazel-team): Unify data structures between Skylark and BUILD,
-    // and stop doing the conversions below:
-    if (!isSkylark) {
+    if (!isSkylark()) {
       value = SkylarkType.convertFromSkylark(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();
-    }
+    update(symbol.getName(), value);
   }
 
-  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();
-    }
+  public ImmutableList<StackTraceElement> getStackTrace() {
+    return ImmutableList.copyOf(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();
-    }
+  protected Deque<StackTraceElement> getCopyOfStackTrace() {
+    return new LinkedList<>(stackTrace);
   }
 
-
   /**
-   * The fail fast handler, which throws a AssertionError whenever an error or warning occurs.
+   * Adds the given element to the stack trace (iff the stack is empty) and returns whether it was
+   * successful.
    */
-  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;
+  public boolean tryAddingStackTraceRoot(StackTraceElement element) {
+    if (stackTrace.isEmpty()) {
+      stackTrace.add(element);
+      return true;
     }
+    return false;
   }
-
-  /** 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);
+  
+  public void addToStackTrace(StackTraceElement element)    {
+    stackTrace.add(element);
   }
 
   /**
-   * Parses some String input without a supporting file, returning statements and comments.
-   * @param input a list of lines of code
+   * 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.
    */
-  @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 removeStackTraceRoot() {
+    Preconditions.checkArgument(stackTrace.size() == 1);
+    stackTrace.clear();
   }
 
-  /**
-   * 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;
+  public void removeStackTraceElement() {
+    // TODO(fwe): find out why the precond doesn't work
+    //    Preconditions.checkArgument(stackTrace.size() > 1);
+    stackTrace.removeLast();
   }
 
   /**
-   * 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
+   * Returns whether the given {@link BaseFunction} is part of this {@link Environment}'s stack
+   * trace.
    */
-  @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;
+  public boolean stackTraceContains(BaseFunction function) {
+    for (StackTraceElement element : stackTrace) {
+      if (element.hasFunction(function)) {
+        return true;
       }
     }
-    return last;
+    return false;
   }
 }
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 714556e476..82ca835ccd 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.getStartLine(),
+          location.getStartLineAndColumn().getLine(),
           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
new file mode 100644
index 0000000000..6a24cb3cac
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
@@ -0,0 +1,195 @@
+// 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 1886843e86..b7842d4c4c 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 {@link Environment} according to
-   * the rules of the Skylark language, throws {@link EvalException} in case of a semantical error.
+   * <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.
    *
    * @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 76737dd4c1..8d1eb56f9c 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,11 +353,21 @@ 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.
-  private MethodDescriptor findJavaMethod(
-      Class<?> objClass, String methodName, List<Object> args) throws EvalException {
+  // 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 {
     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;
@@ -381,11 +391,12 @@ public final class FuncallExpression extends Expression {
       }
     }
     if (matchingMethod != null && !matchingMethod.getAnnotation().structField()) {
-      return matchingMethod;
+      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));
     }
-    throw new EvalException(getLocation(), "No matching method found for "
-        + formatMethod(methodName, args) + " in "
-        + EvalUtils.getDataTypeNameFromClass(objClass));
   }
 
   private String formatMethod(String methodName, List<Object> args) {
@@ -479,7 +490,20 @@ public final class FuncallExpression extends Expression {
 
   @Override
   Object eval(Environment env) throws EvalException, InterruptedException {
-    return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
+    // 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();
+      }
+    }
   }
 
   /**
@@ -526,28 +550,15 @@ 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 call
-        obj = null;
-        objClass = (Class<?>) objValue;
+        // 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());
       } else {
-        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 invokeJavaMethod(
+            objValue, objValue.getClass(), func.getName(), posargs.build(), !kwargs.isEmpty());
       }
-      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 acc09c9859..ae7c0272ef 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,14 +50,10 @@ 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,
-            env.getGlobals()));
+    env.update(ident.getName(), new UserDefinedFunction(
+        ident, FunctionSignature.WithValues.<Object, SkylarkType>create(
+            signature.getSignature(), defaultValues, types),
+        statements, (SkylarkEnvironment) env));
   }
 
   @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 1a39755b5a..df5f486e0b 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,7 +84,8 @@ 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.
-      if (env.isKnownGlobalVariable(ident.getName())) {
+      SkylarkEnvironment skylarkEnv = (SkylarkEnvironment) env;
+      if (skylarkEnv.hasBeenReadGlobalVariable(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 b1ca1f60a0..996ae41bbe 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.isCallerSkylark()) {
+          if (env.isSkylark()) {
             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.isCallerSkylark()) {
+          if (env.isSkylark()) {
             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.isCallerSkylark() ? SkylarkList.tuple(item) : item);
+        list.add(env.isSkylark() ? 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.isCallerSkylark()) {
+    if (env.isSkylark()) {
       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, Environment env) throws EvalException {
+        Location loc, SkylarkEnvironment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
                 @Override
@@ -1493,6 +1493,19 @@ 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
deleted file mode 100644
index 5120f8d0d2..0000000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
+++ /dev/null
@@ -1,136 +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.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 9230d6be72..50ef2546d5 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.")
-  private static final Boolean TRUE = true;
+  static final Boolean TRUE = true;
 
   @SkylarkSignature(name = "False", returnType = Boolean.class,
       doc = "Literal for the boolean false.")
-  private static final Boolean FALSE = false;
+  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) {
+  static Environment setupConstants(Environment env) throws EvalException {
     // 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.setup("False", FALSE).setup("True", TRUE).setup("None", NONE);
+    return env.update("False", FALSE).update("True", TRUE).update("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.setup(
+        env.update(
             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.setup(annotation.name(), value);
+            env.update(annotation.name(), value);
           }
         }
       }
@@ -168,9 +168,9 @@ public final class Runtime {
   }
 
   static void setupMethodEnvironment(
-      Environment env, Iterable<BaseFunction> functions) {
+      Environment env, Iterable<BaseFunction> functions) throws EvalException {
     for (BaseFunction function : functions) {
-      env.setup(function.getName(), function);
+      env.update(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 6140acb0b0..94b1917ab6 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,25 +22,21 @@ public class SkylarkCallbackFunction {
 
   private final BaseFunction callback;
   private final FuncallExpression ast;
-  private final Environment funcallEnv;
+  private final SkylarkEnvironment funcallEnv;
 
-  public SkylarkCallbackFunction(
-      BaseFunction callback, FuncallExpression ast, Environment funcallEnv) {
+  public SkylarkCallbackFunction(BaseFunction callback, FuncallExpression ast,
+      SkylarkEnvironment funcallEnv) {
     this.callback = callback;
     this.ast = ast;
     this.funcallEnv = funcallEnv;
   }
 
   public Object call(ClassObject ctx, Object... arguments) throws EvalException {
-    try (Mutability mutability = Mutability.create("callback %s", callback)) {
-      Environment env = Environment.builder(mutability)
-          .setSkylark()
-          .setEventHandler(funcallEnv.getEventHandler())
-          .setGlobals(funcallEnv.getGlobals())
-          .build();
+    try {
       return callback.call(
-          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, env);
-    } catch (InterruptedException | ClassCastException | IllegalArgumentException e) {
+          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, funcallEnv);
+    } 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
new file mode 100644
index 0000000000..0ff19f90c4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
@@ -0,0 +1,205 @@
+// 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 6b316258ee..bf3c8321c0 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,13 +204,8 @@ public class SkylarkSignatureProcessor {
     } else if (param.defaultValue().isEmpty()) {
       return Runtime.NONE;
     } else {
-      try (Mutability mutability = Mutability.create("initialization")) {
-        return Environment.builder(mutability)
-            .setSkylark()
-            .setGlobals(Environment.CONSTANTS_ONLY)
-            .setEventHandler(Environment.FAIL_FAST_HANDLER)
-            .build()
-            .eval(param.defaultValue());
+      try {
+        return EvaluationContext.SKYLARK_INITIALIZATION.evalExpression(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 2c99209b3e..ca89b1ab43 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 Environment according to
-   * the rules of the Skylark language. The Environment can be used e.g. to check
+   * 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
    * 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 537f29f632..f50e6ee5f1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location.LineAndColumn;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
@@ -27,16 +26,15 @@ import com.google.devtools.build.lib.vfs.PathFragment;
 public class UserDefinedFunction extends BaseFunction {
 
   private final ImmutableList<Statement> statements;
-
-  // we close over the globals at the time of definition
-  private final Environment.Frame definitionGlobals;
+  private final SkylarkEnvironment definitionEnv;
 
   protected UserDefinedFunction(Identifier function,
       FunctionSignature.WithValues<Object, SkylarkType> signature,
-      ImmutableList<Statement> statements, Environment.Frame definitionGlobals) {
+      ImmutableList<Statement> statements, SkylarkEnvironment definitionEnv) {
     super(function.getName(), signature, function.getLocation());
+
     this.statements = statements;
-    this.definitionGlobals = definitionGlobals;
+    this.definitionEnv = definitionEnv;
   }
 
   public FunctionSignature.WithValues<Object, SkylarkType> getFunctionSignature() {
@@ -50,36 +48,23 @@ public class UserDefinedFunction extends BaseFunction {
   @Override
   public Object call(Object[] arguments, FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    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()));
+    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++]);
     }
 
     long startTimeProfiler = Profiler.nanoTimeMaybe();
     Statement lastStatement = null;
     try {
-      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();
+      for (Statement stmt : statements) {
+        lastStatement = stmt;
+        stmt.exec(env);
       }
-      return Runtime.NONE;
+    } catch (ReturnStatement.ReturnException e) {
+      return e.getValue();
     } catch (EvalExceptionWithStackTrace ex) {
       // We need this block since the next "catch" must only catch EvalExceptions that don't have a
       // stack trace yet.
@@ -94,8 +79,8 @@ public class UserDefinedFunction extends BaseFunction {
           startTimeProfiler,
           ProfilerTask.SKYLARK_USER_FN,
           getLocationPathAndLine() + "#" + getName());
-      env.exitScope();
     }
+    return Runtime.NONE;
   }
 
   /**
@@ -120,4 +105,14 @@ 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 9d56271434..9b71f96acc 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,6 +15,7 @@
 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;
@@ -30,7 +31,7 @@ import java.util.Stack;
  * @see Statement#validate
  * @see Expression#validate
  */
-public final class ValidationEnvironment {
+public class ValidationEnvironment {
 
   private final ValidationEnvironment parent;
 
@@ -44,6 +45,9 @@ public final 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
@@ -51,14 +55,38 @@ public final 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);
   }
 
   /**
@@ -67,6 +95,7 @@ public final class ValidationEnvironment {
   public ValidationEnvironment(ValidationEnvironment parent) {
     // Don't copy readOnlyVariables: Variables may shadow global values.
     this.parent = parent;
+    this.clonable = false;
   }
 
   /**
@@ -91,6 +120,7 @@ public final class ValidationEnvironment {
     }
     variables.add(varname);
     variableLocations.put(varname, location);
+    clonable = false;
   }
 
   private void checkReadonly(String varname, Location location) throws EvalException {
@@ -103,8 +133,7 @@ public final class ValidationEnvironment {
    * Returns true if the symbol exists in the validation environment.
    */
   public boolean hasSymbolInEnvironment(String varname) {
-    return variables.contains(varname)
-        || (parent != null && topLevel().variables.contains(varname));
+    return variables.contains(varname) || topLevel().variables.contains(varname);
   }
 
   private ValidationEnvironment topLevel() {
@@ -118,6 +147,7 @@ public final class ValidationEnvironment {
    */
   public void startTemporarilyDisableReadonlyCheckSession() {
     futureReadOnlyVariables.add(new HashSet<String>());
+    clonable = false;
   }
 
   /**
@@ -129,6 +159,7 @@ public final class ValidationEnvironment {
     if (!futureReadOnlyVariables.isEmpty()) {
       futureReadOnlyVariables.peek().addAll(variables);
     }
+    clonable = false;
   }
 
   /**
@@ -136,6 +167,7 @@ public final class ValidationEnvironment {
    */
   public void finishTemporarilyDisableReadonlyCheckBranch() {
     readOnlyVariables.removeAll(futureReadOnlyVariables.peek());
+    clonable = false;
   }
 
   /**