Refactor Skylark Environment-s

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

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

--
MOS_MIGRATED_REVID=102363438
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
index 18d605d..57bc5e8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
@@ -38,10 +38,10 @@
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory;
 import com.google.devtools.build.lib.rules.SkylarkModules;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.Label;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.SkylarkType;
-import com.google.devtools.build.lib.syntax.ValidationEnvironment;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.common.options.OptionsClassProvider;
 
@@ -312,8 +312,6 @@
 
   private final ImmutableMap<String, SkylarkType> skylarkAccessibleJavaClasses;
 
-  private final ValidationEnvironment skylarkValidationEnvironment;
-
   public ConfiguredRuleClassProvider(
       PathFragment preludePath,
       String runfilesPrefix,
@@ -339,9 +337,6 @@
     this.configurationCollectionFactory = configurationCollectionFactory;
     this.prerequisiteValidator = prerequisiteValidator;
     this.skylarkAccessibleJavaClasses = skylarkAccessibleJavaClasses;
-    this.skylarkValidationEnvironment = new ValidationEnvironment(
-        // TODO(bazel-team): refactor constructors so we don't have those null-s
-        createSkylarkRuleClassEnvironment(null, null));
   }
 
   public PrerequisiteValidator getPrerequisiteValidator() {
@@ -426,22 +421,26 @@
   }
 
   @Override
-  public SkylarkEnvironment createSkylarkRuleClassEnvironment(
-      EventHandler eventHandler, String astFileContentHashCode) {
-    SkylarkEnvironment env = SkylarkModules.getNewEnvironment(eventHandler, astFileContentHashCode);
+  public Environment createSkylarkRuleClassEnvironment(
+      Mutability mutability,
+      EventHandler eventHandler,
+      String astFileContentHashCode,
+      Map<PathFragment, Environment> importMap) {
+    Environment env = Environment.builder(mutability)
+        .setSkylark()
+        .setGlobals(SkylarkModules.GLOBALS)
+        .setEventHandler(eventHandler)
+        .setFileContentHashCode(astFileContentHashCode)
+        .setImportedExtensions(importMap)
+        .setLoadingPhase()
+        .build();
     for (Map.Entry<String, SkylarkType> entry : skylarkAccessibleJavaClasses.entrySet()) {
-      env.update(entry.getKey(), entry.getValue().getType());
+      env.setup(entry.getKey(), entry.getValue().getType());
     }
-    env.setLoadingPhase();
     return env;
   }
 
   @Override
-  public ValidationEnvironment getSkylarkValidationEnvironment() {
-    return skylarkValidationEnvironment;
-  }
-
-  @Override
   public String getDefaultWorkspaceFile() {
     return defaultWorkspaceFile;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/events/Location.java b/src/main/java/com/google/devtools/build/lib/events/Location.java
index 74b04a9..1b9110d 100644
--- a/src/main/java/com/google/devtools/build/lib/events/Location.java
+++ b/src/main/java/com/google/devtools/build/lib/events/Location.java
@@ -149,6 +149,18 @@
   }
 
   /**
+   * Returns a line corresponding to the position denoted by getStartOffset.
+   * Returns null if this information is not available.
+   */
+  public Integer getStartLine() {
+    LineAndColumn lac = getStartLineAndColumn();
+    if (lac == null) {
+      return null;
+    }
+    return lac.getLine();
+  }
+
+  /**
    * Returns a (line, column) pair corresponding to the position denoted by
    * getEndOffset.  Returns null if this information is not available.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
index fda1a83..49852ee 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.RuleFactory.InvalidRuleException;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
@@ -120,7 +121,8 @@
         attributes.put("actual", actual);
       }
       StoredEventHandler handler = new StoredEventHandler();
-      Rule rule = RuleFactory.createRule(this, bindRuleClass, attributes, handler, null, location);
+      Rule rule = RuleFactory.createRule(
+          this, bindRuleClass, attributes, handler, null, location, null);
       overwriteRule(rule);
       rule.setVisibility(ConstantRuleVisibility.PUBLIC);
     }
@@ -130,11 +132,11 @@
      * WORKSPACE files to overwrite "earlier" ones.
      */
     public Builder createAndAddRepositoryRule(RuleClass ruleClass, RuleClass bindRuleClass,
-        Map<String, Object> kwargs, FuncallExpression ast)
+        Map<String, Object> kwargs, FuncallExpression ast, Environment env)
         throws InvalidRuleException, NameConflictException, SyntaxException {
       StoredEventHandler eventHandler = new StoredEventHandler();
-      Rule tempRule = RuleFactory.createRule(this, ruleClass, kwargs, eventHandler, ast,
-          ast.getLocation());
+      Rule tempRule = RuleFactory.createRule(
+          this, ruleClass, kwargs, eventHandler, ast, ast.getLocation(), env);
       addEvents(eventHandler.getEvents());
       try {
         repositoryMap.put(RepositoryName.create("@" + tempRule.getName()), tempRule);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index ffea0bd..cde726b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -46,10 +46,9 @@
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Identifier;
 import com.google.devtools.build.lib.syntax.Label;
-import com.google.devtools.build.lib.syntax.MethodLibrary;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
@@ -326,7 +325,6 @@
 
   private final RuleFactory ruleFactory;
   private final RuleClassProvider ruleClassProvider;
-  private final Environment globalEnv;
 
   private AtomicReference<? extends UnixGlob.FilesystemCalls> syscalls;
   private Preprocessor.Factory preprocessorFactory = Preprocessor.Factory.NullFactory.INSTANCE;
@@ -367,7 +365,6 @@
     this.platformSetRegexps = platformSetRegexps;
     this.ruleFactory = new RuleFactory(ruleClassProvider);
     this.ruleClassProvider = ruleClassProvider;
-    globalEnv = newGlobalEnvironment();
     threadPool = new ThreadPoolExecutor(100, 100, 15L, TimeUnit.SECONDS,
         new LinkedBlockingQueue<Runnable>(),
         new ThreadFactoryBuilder().setNameFormat("Legacy globber %d").build());
@@ -402,15 +399,6 @@
 
 
   /**
-   * Returns the static environment initialized once and shared by all packages
-   * created by this factory. No updates occur to this environment once created.
-   */
-  @VisibleForTesting
-  public Environment getEnvironment() {
-    return globalEnv;
-  }
-
-  /**
    * Returns the immutable, unordered set of names of all the known rule
    * classes.
    */
@@ -631,8 +619,8 @@
                   "'environment_group argument'", context.pkgBuilder.getBuildFileLabel());
 
               try {
-                context.pkgBuilder.addEnvironmentGroup(name, environments, defaults,
-                    context.eventHandler, loc);
+                context.pkgBuilder.addEnvironmentGroup(
+                    name, environments, defaults, context.eventHandler, loc);
                 return Runtime.NONE;
               } catch (Label.SyntaxException e) {
                 throw new EvalException(loc,
@@ -910,7 +898,7 @@
                               Environment env)
       throws RuleFactory.InvalidRuleException, Package.NameConflictException {
     RuleClass ruleClass = getBuiltInRuleClass(ruleClassName, ruleFactory);
-    RuleFactory.createAndAddRule(context, ruleClass, kwargs, ast, env.getStackTrace());
+    RuleFactory.createAndAddRule(context, ruleClass, kwargs, ast, env);
   }
 
   private static RuleClass getBuiltInRuleClass(String ruleClassName, RuleFactory ruleFactory) {
@@ -958,16 +946,6 @@
     };
   }
 
-  /**
-   * Returns a new environment populated with common entries that can be shared
-   * across packages and that don't require the context.
-   */
-  private static Environment newGlobalEnvironment() {
-    Environment env = new Environment();
-    MethodLibrary.setupMethodEnvironment(env);
-    return env;
-  }
-
   /****************************************************************************
    * Package creation.
    */
@@ -995,7 +973,7 @@
       Preprocessor.Result preprocessingResult,
       Iterable<Event> preprocessingEvents,
       List<Statement> preludeStatements,
-      Map<PathFragment, SkylarkEnvironment> imports,
+      Map<PathFragment, Environment> imports,
       ImmutableList<Label> skylarkFileDependencies,
       CachingPackageLocator locator,
       RuleVisibility defaultVisibility,
@@ -1064,12 +1042,12 @@
                 packageId,
                 buildFile,
                 preprocessingResult,
-                localReporter.getEvents(), /* preprocessingEvents */
-                ImmutableList.<Statement>of(), /* preludeStatements */
-                ImmutableMap.<PathFragment, SkylarkEnvironment>of(), /* imports */
-                ImmutableList.<Label>of(), /* skylarkFileDependencies */
+                /*preprocessingEvents=*/localReporter.getEvents(),
+                /*preludeStatements=*/ImmutableList.<Statement>of(),
+                /*imports=*/ImmutableMap.<PathFragment, Environment>of(),
+                /*skylarkFileDependencies=*/ImmutableList.<Label>of(),
                 locator,
-                ConstantRuleVisibility.PUBLIC, /* defaultVisibility */
+                /*defaultVisibility=*/ConstantRuleVisibility.PUBLIC,
                 globber)
             .build();
     Event.replayEventsOn(eventHandler, result.getEvents());
@@ -1110,8 +1088,13 @@
       return Preprocessor.Result.noPreprocessing(inputSource);
     }
     try {
-      return preprocessor.preprocess(inputSource, packageId.toString(), globber, eventHandler,
-          globalEnv, ruleFactory.getRuleClassNames());
+      return preprocessor.preprocess(
+          inputSource,
+          packageId.toString(),
+          globber,
+          eventHandler,
+          Environment.BUILD,
+          ruleFactory.getRuleClassNames());
     } catch (IOException e) {
       eventHandler.handle(Event.error(Location.fromFile(buildFile),
                      "preprocessing failed: " + e.getMessage()));
@@ -1212,19 +1195,20 @@
     // or if not possible, at least make them straight copies from the native module variant.
     // or better, use a common Environment.Frame for these common bindings
     // (that shares a backing ImmutableMap for the bindings?)
-    pkgEnv.update("native", nativeModule);
-    pkgEnv.update("distribs", newDistribsFunction.apply(context));
-    pkgEnv.update("glob", newGlobFunction.apply(context, /*async=*/false));
-    pkgEnv.update("mocksubinclude", newMockSubincludeFunction.apply(context));
-    pkgEnv.update("licenses", newLicensesFunction.apply(context));
-    pkgEnv.update("exports_files", newExportsFilesFunction.apply());
-    pkgEnv.update("package_group", newPackageGroupFunction.apply());
-    pkgEnv.update("package", newPackageFunction(packageArguments));
-    pkgEnv.update("environment_group", newEnvironmentGroupFunction.apply(context));
+    pkgEnv
+        .setup("native", nativeModule)
+        .setup("distribs", newDistribsFunction.apply(context))
+        .setup("glob", newGlobFunction.apply(context, /*async=*/false))
+        .setup("mocksubinclude", newMockSubincludeFunction.apply(context))
+        .setup("licenses", newLicensesFunction.apply(context))
+        .setup("exports_files", newExportsFilesFunction.apply())
+        .setup("package_group", newPackageGroupFunction.apply())
+        .setup("package", newPackageFunction(packageArguments))
+        .setup("environment_group", newEnvironmentGroupFunction.apply(context));
 
     for (String ruleClass : ruleFactory.getRuleClassNames()) {
       BaseFunction ruleFunction = newRuleFunction(ruleFactory, ruleClass);
-      pkgEnv.update(ruleClass, ruleFunction);
+      pkgEnv.setup(ruleClass, ruleFunction);
     }
 
     for (EnvironmentExtension extension : environmentExtensions) {
@@ -1255,62 +1239,65 @@
       PackageIdentifier packageId, BuildFileAST buildFileAST, Path buildFilePath, Globber globber,
       Iterable<Event> pastEvents, RuleVisibility defaultVisibility, boolean containsError,
       boolean containsTransientError, MakeEnvironment.Builder pkgMakeEnv,
-      Map<PathFragment, SkylarkEnvironment> imports,
+      Map<PathFragment, Environment> imports,
       ImmutableList<Label> skylarkFileDependencies) throws InterruptedException {
-    // Important: Environment should be unreachable by the end of this method!
-    StoredEventHandler eventHandler = new StoredEventHandler();
-    Environment pkgEnv = new Environment(globalEnv, eventHandler);
-    pkgEnv.setLoadingPhase();
-
     Package.LegacyBuilder pkgBuilder = new Package.LegacyBuilder(
         packageId, ruleClassProvider.getRunfilesPrefix());
+    StoredEventHandler eventHandler = new StoredEventHandler();
 
-    pkgBuilder.setGlobber(globber)
-        .setFilename(buildFilePath)
-        .setMakeEnv(pkgMakeEnv)
-        .setDefaultVisibility(defaultVisibility)
-        // "defaultVisibility" comes from the command line. Let's give the BUILD file a chance to
-        // set default_visibility once, be reseting the PackageBuilder.defaultVisibilitySet flag.
-        .setDefaultVisibilitySet(false)
-        .setSkylarkFileDependencies(skylarkFileDependencies)
-        .setWorkspaceName(externalPkg.getWorkspaceName());
+    try (Mutability mutability = Mutability.create("package %s", packageId)) {
+      Environment pkgEnv = Environment.builder(mutability)
+          .setGlobals(Environment.BUILD)
+          .setEventHandler(eventHandler)
+          .setImportedExtensions(imports)
+          .setLoadingPhase()
+          .build();
 
-    Event.replayEventsOn(eventHandler, pastEvents);
+      pkgBuilder.setGlobber(globber)
+          .setFilename(buildFilePath)
+          .setMakeEnv(pkgMakeEnv)
+          .setDefaultVisibility(defaultVisibility)
+          // "defaultVisibility" comes from the command line. Let's give the BUILD file a chance to
+          // set default_visibility once, be reseting the PackageBuilder.defaultVisibilitySet flag.
+          .setDefaultVisibilitySet(false)
+          .setSkylarkFileDependencies(skylarkFileDependencies)
+          .setWorkspaceName(externalPkg.getWorkspaceName());
 
-    // Stuff that closes over the package context:`
-    PackageContext context = new PackageContext(pkgBuilder, globber, eventHandler);
-    buildPkgEnv(pkgEnv, context, ruleFactory);
+      Event.replayEventsOn(eventHandler, pastEvents);
 
-    if (containsError) {
-      pkgBuilder.setContainsErrors();
-    }
+      // Stuff that closes over the package context:
+      PackageContext context = new PackageContext(pkgBuilder, globber, eventHandler);
+      buildPkgEnv(pkgEnv, context, ruleFactory);
+      pkgEnv.setupDynamic(PKG_CONTEXT, context);
+      pkgEnv.setupDynamic(Runtime.PKG_NAME, packageId.toString());
 
-    if (containsTransientError) {
-      pkgBuilder.setContainsTemporaryErrors();
-    }
+      if (containsError) {
+        pkgBuilder.setContainsErrors();
+      }
 
-    if (!validatePackageIdentifier(packageId, buildFileAST.getLocation(), eventHandler)) {
-      pkgBuilder.setContainsErrors();
-    }
+      if (containsTransientError) {
+        pkgBuilder.setContainsTemporaryErrors();
+      }
 
-    pkgEnv.setImportedExtensions(imports);
-    pkgEnv.updateAndPropagate(PKG_CONTEXT, context);
-    pkgEnv.updateAndPropagate(Runtime.PKG_NAME, packageId.toString());
+      if (!validatePackageIdentifier(packageId, buildFileAST.getLocation(), eventHandler)) {
+        pkgBuilder.setContainsErrors();
+      }
 
-    if (!validateAssignmentStatements(pkgEnv, buildFileAST, eventHandler)) {
-      pkgBuilder.setContainsErrors();
-    }
+      if (!validateAssignmentStatements(pkgEnv, buildFileAST, eventHandler)) {
+        pkgBuilder.setContainsErrors();
+      }
 
-    if (buildFileAST.containsErrors()) {
-      pkgBuilder.setContainsErrors();
-    }
+      if (buildFileAST.containsErrors()) {
+        pkgBuilder.setContainsErrors();
+      }
 
-    // TODO(bazel-team): (2009) the invariant "if errors are reported, mark the package
-    // as containing errors" is strewn all over this class.  Refactor to use an
-    // event sensor--and see if we can simplify the calling code in
-    // createPackage().
-    if (!buildFileAST.exec(pkgEnv, eventHandler)) {
-      pkgBuilder.setContainsErrors();
+      // TODO(bazel-team): (2009) the invariant "if errors are reported, mark the package
+      // as containing errors" is strewn all over this class.  Refactor to use an
+      // event sensor--and see if we can simplify the calling code in
+      // createPackage().
+      if (!buildFileAST.exec(pkgEnv, eventHandler)) {
+        pkgBuilder.setContainsErrors();
+      }
     }
 
     pkgBuilder.addEvents(eventHandler.getEvents());
@@ -1329,29 +1316,36 @@
       // of all globs.
       return;
     }
-    // Important: Environment should be unreachable by the end of this method!
-    Environment pkgEnv = new Environment();
-    pkgEnv.setLoadingPhase();
+    try (Mutability mutability = Mutability.create("prefetchGlobs for %s", packageId)) {
+      Environment pkgEnv = Environment.builder(mutability)
+          .setGlobals(Environment.BUILD)
+          .setEventHandler(NullEventHandler.INSTANCE)
+          .setLoadingPhase()
+          .build();
 
-    Package.LegacyBuilder pkgBuilder = new Package.LegacyBuilder(packageId,
-        ruleClassProvider.getRunfilesPrefix());
+      Package.LegacyBuilder pkgBuilder = new Package.LegacyBuilder(packageId,
+          ruleClassProvider.getRunfilesPrefix());
 
-    pkgBuilder.setFilename(buildFilePath)
-        .setMakeEnv(pkgMakeEnv)
-        .setDefaultVisibility(defaultVisibility)
-        // "defaultVisibility" comes from the command line. Let's give the BUILD file a chance to
-        // set default_visibility once, be reseting the PackageBuilder.defaultVisibilitySet flag.
-        .setDefaultVisibilitySet(false);
+      pkgBuilder.setFilename(buildFilePath)
+          .setMakeEnv(pkgMakeEnv)
+          .setDefaultVisibility(defaultVisibility)
+          // "defaultVisibility" comes from the command line. Let's give the BUILD file a chance to
+          // set default_visibility once, be reseting the PackageBuilder.defaultVisibilitySet flag.
+          .setDefaultVisibilitySet(false);
 
-    // Stuff that closes over the package context:
-    PackageContext context = new PackageContext(pkgBuilder, globber, NullEventHandler.INSTANCE);
-    buildPkgEnv(pkgEnv, context, ruleFactory);
-    pkgEnv.update("glob", newGlobFunction.apply(context, /*async=*/true));
-    // The Fileset function is heavyweight in that it can run glob(). Avoid this during the
-    // preloading phase.
-    pkgEnv.remove("FilesetEntry");
-
-    buildFileAST.exec(pkgEnv, NullEventHandler.INSTANCE);
+      // Stuff that closes over the package context:
+      PackageContext context = new PackageContext(pkgBuilder, globber, NullEventHandler.INSTANCE);
+      buildPkgEnv(pkgEnv, context, ruleFactory);
+      try {
+        pkgEnv.update("glob", newGlobFunction.apply(context, /*async=*/true));
+        // The Fileset function is heavyweight in that it can run glob(). Avoid this during the
+        // preloading phase.
+        pkgEnv.update("FilesetEntry", Runtime.NONE);
+      } catch (EvalException e) {
+        throw new AssertionError(e);
+      }
+      buildFileAST.exec(pkgEnv, NullEventHandler.INSTANCE);
+    }
   }
 
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Preprocessor.java b/src/main/java/com/google/devtools/build/lib/packages/Preprocessor.java
index a479ca9..c44776a 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Preprocessor.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Preprocessor.java
@@ -141,7 +141,7 @@
    * @param packageName the BUILD file's package.
    * @param globber a globber for evaluating globs.
    * @param eventHandler a eventHandler on which to report warnings/errors.
-   * @param globalEnv the GLOBALS Python environment.
+   * @param globals the global bindings for the Python environment.
    * @param ruleNames the set of names of all rules in the build language.
    * @throws IOException if there was an I/O problem during preprocessing.
    * @return a pair of the ParserInputSource and a map of subincludes seen during the evaluation
@@ -151,7 +151,7 @@
       String packageName,
       Globber globber,
       EventHandler eventHandler,
-      Environment globalEnv,
+      Environment.Frame globals,
       Set<String> ruleNames)
     throws IOException, InterruptedException;
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 59fcbb5..7906a2b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -34,13 +34,13 @@
 import com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType;
 import com.google.devtools.build.lib.syntax.Argument;
 import com.google.devtools.build.lib.syntax.BaseFunction;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.FragmentClassNameResolver;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -498,7 +498,7 @@
     private BaseFunction configuredTargetFunction = null;
     private Function<? super Rule, Map<String, Label>> externalBindingsFunction =
         NO_EXTERNAL_BINDINGS;
-    private SkylarkEnvironment ruleDefinitionEnvironment = null;
+    private Environment ruleDefinitionEnvironment = null;
     private Set<Class<?>> configurationFragments = new LinkedHashSet<>();
     private MissingFragmentPolicy missingFragmentPolicy = MissingFragmentPolicy.FAIL_ANALYSIS;
     private Set<String> requiredFragmentNames = new LinkedHashSet<>();
@@ -792,7 +792,7 @@
     /**
      *  Sets the rule definition environment. Meant for Skylark usage.
      */
-    public Builder setRuleDefinitionEnvironment(SkylarkEnvironment env) {
+    public Builder setRuleDefinitionEnvironment(Environment env) {
       this.ruleDefinitionEnvironment = env;
       return this;
     }
@@ -964,7 +964,7 @@
    * The Skylark rule definition environment of this RuleClass.
    * Null for non Skylark executable RuleClasses.
    */
-  @Nullable private final SkylarkEnvironment ruleDefinitionEnvironment;
+  @Nullable private final Environment ruleDefinitionEnvironment;
 
   /**
    * The set of required configuration fragments; this should list all fragments that can be
@@ -1015,7 +1015,7 @@
       ImmutableSet<Class<?>> advertisedProviders,
       @Nullable BaseFunction configuredTargetFunction,
       Function<? super Rule, Map<String, Label>> externalBindingsFunction,
-      @Nullable SkylarkEnvironment ruleDefinitionEnvironment,
+      @Nullable Environment ruleDefinitionEnvironment,
       Set<Class<?>> allowedConfigurationFragments,
       MissingFragmentPolicy missingFragmentPolicy,
       boolean supportsConstraintChecking,
@@ -1076,7 +1076,7 @@
       ImmutableSet<Class<?>> advertisedProviders,
       @Nullable BaseFunction configuredTargetFunction,
       Function<? super Rule, Map<String, Label>> externalBindingsFunction,
-      @Nullable SkylarkEnvironment ruleDefinitionEnvironment,
+      @Nullable Environment ruleDefinitionEnvironment,
       Set<Class<?>> allowedConfigurationFragments,
       Set<String> allowedConfigurationFragmentNames,
       @Nullable FragmentClassNameResolver fragmentNameResolver,
@@ -1725,7 +1725,7 @@
   /**
    * Returns this RuleClass's rule definition environment.
    */
-  @Nullable public SkylarkEnvironment getRuleDefinitionEnvironment() {
+  @Nullable public Environment getRuleDefinitionEnvironment() {
     return ruleDefinitionEnvironment;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
index 958d88a..b3ca83f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
@@ -15,12 +15,14 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
-import com.google.devtools.build.lib.syntax.ValidationEnvironment;
+import com.google.devtools.build.lib.syntax.Environment;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.Map;
 
+import javax.annotation.Nullable;
+
 /**
  * The collection of the supported build rules. Provides an Environment for Skylark rule creation.
  */
@@ -47,17 +49,19 @@
   Map<String, Class<? extends AspectFactory<?, ?, ?>>> getAspectFactoryMap();
 
   /**
-   * Returns a new Skylark Environment instance for rule creation. Implementations need to be
-   * thread safe.
+   * Returns a new Skylark Environment instance for rule creation.
+   * Implementations need to be thread safe.
+   * Be sure to close() the mutability before you return the results of said evaluation.
+   * @param mutability the Mutability for the current evaluation context
+   * @param eventHandler the EventHandler for warnings, errors, etc.
+   * @param astFileContentHashCode the hash code identifying this environment.
+   * @return an Environment, in which to evaluate load time skylark forms.
    */
-  SkylarkEnvironment createSkylarkRuleClassEnvironment(
-      EventHandler eventHandler, String astFileContentHashCode);
-
-  /**
-   * Returns a validation environment for static analysis of skylark files.
-   * The environment has to contain all built-in functions and objects.
-   */
-  ValidationEnvironment getSkylarkValidationEnvironment();
+  Environment createSkylarkRuleClassEnvironment(
+      Mutability mutability,
+      EventHandler eventHandler,
+      @Nullable String astFileContentHashCode,
+      @Nullable Map<PathFragment, Environment> importMap);
 
   /**
    * Returns the default content of the WORKSPACE file.
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java b/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
index 33f9d49..2eb94b1 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
@@ -15,20 +15,24 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.Package.NameConflictException;
 import com.google.devtools.build.lib.packages.PackageFactory.PackageContext;
+import com.google.devtools.build.lib.syntax.BaseFunction;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
-import com.google.devtools.build.lib.syntax.StackTraceElement;
+import com.google.devtools.build.lib.syntax.UserDefinedFunction;
+import com.google.devtools.build.lib.util.Pair;
 
 import java.util.Map;
 import java.util.Set;
 
+import javax.annotation.Nullable;
+
 /**
  * Given a rule class and a set of attributes, returns a Rule instance. Also
  * performs a number of checks and associates the rule and the owning package
@@ -78,7 +82,7 @@
       EventHandler eventHandler,
       FuncallExpression ast,
       Location location,
-      ImmutableList<StackTraceElement> stackTrace)
+      @Nullable Environment env)
       throws InvalidRuleException {
     Preconditions.checkNotNull(ruleClass);
     String ruleClassName = ruleClass.getName();
@@ -108,31 +112,19 @@
     }
 
     try {
-      Rule rule = ruleClass.createRuleWithLabel(pkgBuilder, label,
-          addGeneratorAttributesForMacros(attributeValues, stackTrace), eventHandler, ast,
+      return ruleClass.createRuleWithLabel(
+          pkgBuilder,
+          label,
+          addGeneratorAttributesForMacros(attributeValues, env),
+          eventHandler,
+          ast,
           location);
-      return rule;
     } catch (SyntaxException e) {
       throw new RuleFactory.InvalidRuleException(ruleClass + " " + e.getMessage());
     }
   }
 
   /**
-   * Creates and returns a rule instance (without a stack trace).
-   */
-  static Rule createRule(
-      Package.Builder pkgBuilder,
-      RuleClass ruleClass,
-      Map<String, Object> attributeValues,
-      EventHandler eventHandler,
-      FuncallExpression ast,
-      Location location)
-      throws InvalidRuleException {
-    return createRule(pkgBuilder, ruleClass, attributeValues, eventHandler, ast, location,
-        ImmutableList.<StackTraceElement>of());
-  }
-
-  /**
    * Creates a rule instance, adds it to the package and returns it.
    *
    * @param pkgBuilder the under-construction package to which the rule belongs
@@ -145,34 +137,40 @@
    *        rule creation
    * @param ast the abstract syntax tree of the rule expression (optional)
    * @param location the location at which this rule was declared
-   * @param stackTrace the stack trace containing all functions that led to the creation of
-   *        this rule (optional)
    * @throws InvalidRuleException if the rule could not be constructed for any
    *         reason (e.g. no <code>name</code> attribute is defined)
-   * @throws NameConflictException
+   * @throws InvalidRuleException, NameConflictException
    */
-  static Rule createAndAddRule(Package.Builder pkgBuilder,
-                  RuleClass ruleClass,
-                  Map<String, Object> attributeValues,
-                  EventHandler eventHandler,
-                  FuncallExpression ast,
-                  Location location,
-                  ImmutableList<StackTraceElement> stackTrace)
+  static Rule createAndAddRule(
+      Package.Builder pkgBuilder,
+      RuleClass ruleClass,
+      Map<String, Object> attributeValues,
+      EventHandler eventHandler,
+      FuncallExpression ast,
+      Location location,
+      Environment env)
       throws InvalidRuleException, NameConflictException {
     Rule rule = createRule(
-        pkgBuilder, ruleClass, attributeValues, eventHandler, ast, location, stackTrace);
+        pkgBuilder, ruleClass, attributeValues, eventHandler, ast, location, env);
     pkgBuilder.addRule(rule);
     return rule;
   }
 
-  public static Rule createAndAddRule(PackageContext context,
+  public static Rule createAndAddRule(
+      PackageContext context,
       RuleClass ruleClass,
       Map<String, Object> attributeValues,
       FuncallExpression ast,
-      ImmutableList<StackTraceElement> stackTrace)
+      Environment env)
       throws InvalidRuleException, NameConflictException {
-    return createAndAddRule(context.pkgBuilder, ruleClass, attributeValues, context.eventHandler,
-        ast, ast.getLocation(), stackTrace);
+    return createAndAddRule(
+        context.pkgBuilder,
+        ruleClass,
+        attributeValues,
+        context.eventHandler,
+        ast,
+        ast.getLocation(),
+        env);
   }
 
   /**
@@ -192,22 +190,28 @@
    * <p>Otherwise, it returns the given attributes without any changes.
    */
   private static Map<String, Object> addGeneratorAttributesForMacros(
-      Map<String, Object> args, ImmutableList<StackTraceElement> stackTrace) {
-    if (stackTrace.size() <= 2 || args.containsKey("generator_name")
-        || args.containsKey("generator_function")) {
-      // Returns the original arguments if a) there is only the rule itself on the stack
-      // trace (=> no macro) or b) the attributes have already been set by Python pre-processing.
-      // The stack trace will always have at least two entries: one for the call to the rule and one
-      // for its implementation. Consequently, we check for size <= 2.
+      Map<String, Object> args, @Nullable Environment env) {
+    // Returns the original arguments if a) there is only the rule itself on the stack
+    // trace (=> no macro) or b) the attributes have already been set by Python pre-processing.
+    if (env == null) {
+      return args;
+    }
+    boolean hasName = args.containsKey("generator_name");
+    boolean hasFunc = args.containsKey("generator_function");
+    // TODO(bazel-team): resolve cases in our code where hasName && !hasFunc, or hasFunc && !hasName
+    if (hasName || hasFunc) {
+      return args;
+    }
+    Pair<BaseFunction, Location> topCall = env.getTopCall();
+    if (topCall == null || !(topCall.first instanceof UserDefinedFunction)) {
       return args;
     }
 
-    StackTraceElement generator = stackTrace.get(0);
     ImmutableMap.Builder<String, Object> builder = ImmutableMap.builder();
     builder.putAll(args);
     builder.put("generator_name", args.get("name"));
-    builder.put("generator_function", generator.getName());
-    builder.put("generator_location", Location.printPathAndLine(generator.getLocation()));
+    builder.put("generator_function", topCall.first.getName());
+    builder.put("generator_location", topCall.second.toString());
 
     try {
       return builder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
index 054865f..abbbdf8 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
@@ -29,7 +29,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.FunctionSignature;
 import com.google.devtools.build.lib.syntax.Label;
-import com.google.devtools.build.lib.syntax.MethodLibrary;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 
 import java.io.File;
@@ -44,14 +44,30 @@
   private final Builder builder;
   private final Environment environment;
 
-  public WorkspaceFactory(Builder builder, RuleClassProvider ruleClassProvider) {
-    this(builder, ruleClassProvider, null);
+  /**
+   * @param builder a builder for the Workspace
+   * @param ruleClassProvider a provider for known rule classes
+   * @param mutability the Mutability for the current evaluation context
+   */
+  public WorkspaceFactory(
+      Builder builder, RuleClassProvider ruleClassProvider, Mutability mutability) {
+    this(builder, ruleClassProvider, mutability, null);
   }
 
+  // TODO(bazel-team): document installDir
+  /**
+   * @param builder a builder for the Workspace
+   * @param ruleClassProvider a provider for known rule classes
+   * @param mutability the Mutability for the current evaluation context
+   * @param installDir an optional directory into which to install software
+   */
   public WorkspaceFactory(
-      Builder builder, RuleClassProvider ruleClassProvider, @Nullable String installDir) {
+      Builder builder,
+      RuleClassProvider ruleClassProvider,
+      Mutability mutability,
+      @Nullable String installDir) {
     this.builder = builder;
-    this.environment = createWorkspaceEnv(builder, ruleClassProvider, installDir);
+    this.environment = createWorkspaceEnv(builder, ruleClassProvider, mutability, installDir);
   }
 
   public void parse(ParserInputSource source)
@@ -122,13 +138,13 @@
   private static BuiltinFunction newRuleFunction(
       final RuleFactory ruleFactory, final Builder builder, final String ruleClassName) {
     return new BuiltinFunction(ruleClassName,
-        FunctionSignature.KWARGS, BuiltinFunction.USE_AST) {
-      public Object invoke(Map<String, Object> kwargs, FuncallExpression ast)
+        FunctionSignature.KWARGS, BuiltinFunction.USE_AST_ENV) {
+      public Object invoke(Map<String, Object> kwargs, FuncallExpression ast, Environment env)
           throws EvalException {
         try {
           RuleClass ruleClass = ruleFactory.getRuleClass(ruleClassName);
           RuleClass bindRuleClass = ruleFactory.getRuleClass("bind");
-          builder.createAndAddRepositoryRule(ruleClass, bindRuleClass, kwargs, ast);
+          builder.createAndAddRepositoryRule(ruleClass, bindRuleClass, kwargs, ast, env);
         } catch (RuleFactory.InvalidRuleException | Package.NameConflictException |
             Label.SyntaxException e) {
           throw new EvalException(ast.getLocation(), e.getMessage());
@@ -139,25 +155,30 @@
   }
 
   private Environment createWorkspaceEnv(
-      Builder builder, RuleClassProvider ruleClassProvider, String installDir) {
-    Environment workspaceEnv = new Environment();
-    MethodLibrary.setupMethodEnvironment(workspaceEnv);
-    workspaceEnv.setLoadingPhase();
-
+      Builder builder,
+      RuleClassProvider ruleClassProvider,
+      Mutability mutability,
+      String installDir) {
+    Environment workspaceEnv = Environment.builder(mutability)
+        .setGlobals(Environment.BUILD)
+        .setLoadingPhase()
+        .build();
     RuleFactory ruleFactory = new RuleFactory(ruleClassProvider);
-    for (String ruleClass : ruleFactory.getRuleClassNames()) {
-      BaseFunction ruleFunction = newRuleFunction(ruleFactory, builder, ruleClass);
-      workspaceEnv.update(ruleClass, ruleFunction);
+    try {
+      for (String ruleClass : ruleFactory.getRuleClassNames()) {
+        BaseFunction ruleFunction = newRuleFunction(ruleFactory, builder, ruleClass);
+        workspaceEnv.update(ruleClass, ruleFunction);
+      }
+      if (installDir != null) {
+        workspaceEnv.update("__embedded_dir__", installDir);
+      }
+      File jreDirectory = new File(System.getProperty("java.home"));
+      workspaceEnv.update("DEFAULT_SERVER_JAVABASE", jreDirectory.getParentFile().toString());
+      workspaceEnv.update("bind", newBindFunction(ruleFactory, builder));
+      workspaceEnv.update("workspace", newWorkspaceNameFunction(builder));
+      return workspaceEnv;
+    } catch (EvalException e) {
+      throw new AssertionError(e);
     }
-
-    if (installDir != null) {
-      workspaceEnv.update("__embedded_dir__", installDir);
-    }
-    File jreDirectory = new File(System.getProperty("java.home"));
-    workspaceEnv.update("DEFAULT_SERVER_JAVABASE", jreDirectory.getParentFile().toString());
-
-    workspaceEnv.update("bind", newBindFunction(ruleFactory, builder));
-    workspaceEnv.update("workspace", newWorkspaceNameFunction(builder));
-    return workspaceEnv;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
index 1fb8782..fbe9267 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
@@ -37,8 +37,8 @@
 import com.google.devtools.build.lib.query2.output.OutputFormatter.UnorderedFormatter;
 import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.Label;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.io.IOException;
@@ -141,7 +141,7 @@
             rule.isAttributeValueExplicitlySpecified(attr), false));
       }
 
-      SkylarkEnvironment env = rule.getRuleClassObject().getRuleDefinitionEnvironment();
+      Environment env = rule.getRuleClassObject().getRuleDefinitionEnvironment();
       if (env != null) {
         // The RuleDefinitionEnvironment is always defined for Skylark rules and
         // always null for non Skylark rules.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
index 75afd45..e6d8f3c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
@@ -31,7 +31,6 @@
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -105,7 +104,7 @@
   }
 
   private static Attribute.Builder<?> createAttribute(
-      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, SkylarkEnvironment env)
+      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, Environment env)
       throws EvalException, ConversionException {
     // We use an empty name now so that we can set it later.
     // This trick makes sense only in the context of Skylark (builtin rules should not use it).
@@ -185,7 +184,7 @@
       Map<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
       throws EvalException {
     try {
-      return createAttribute(type, kwargs, ast, (SkylarkEnvironment) env);
+      return createAttribute(type, kwargs, ast, env);
     } catch (ConversionException e) {
       throw new EvalException(ast.getLocation(), e.getMessage());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
index c52c58c..3054420 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
@@ -19,11 +19,8 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.SkylarkNativeModule;
 import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.syntax.EvaluationContext;
-import com.google.devtools.build.lib.syntax.MethodLibrary;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
-import com.google.devtools.build.lib.syntax.ValidationEnvironment;
 
 /**
  * The basis for a Skylark Environment with all build-related modules registered.
@@ -44,41 +41,43 @@
       SkylarkRuleClassFunctions.class,
       SkylarkRuleImplementationFunctions.class);
 
+  /** Global bindings for all Skylark modules */
+  public static final Environment.Frame GLOBALS = createGlobals();
+
+  private static Environment.Frame createGlobals() {
+    try (Mutability mutability = Mutability.create("SkylarkModules")) {
+      Environment env = Environment.builder(mutability)
+          .setSkylark()
+          .setGlobals(Environment.SKYLARK)
+          .build();
+      for (Class<?> moduleClass : MODULES) {
+        Runtime.registerModuleGlobals(env, moduleClass);
+      }
+      return env.getGlobals();
+    }
+  }
+
+
   /**
-   * Returns a new SkylarkEnvironment with the elements of the Skylark modules.
+   * Create an {@link Environment} in which to load a Skylark file.
+   * @param eventHandler an EventHandler for warnings, errors, etc.
+   * @param astFileContentHashCode a hash code identifying the file being evaluated
+   * @param mutability the Mutability for the current evaluation context
+   * @return a new Environment with the elements of the Skylark modules.
    */
-  public static SkylarkEnvironment getNewEnvironment(
-      EventHandler eventHandler, String astFileContentHashCode) {
-    SkylarkEnvironment env = new SkylarkEnvironment(eventHandler, astFileContentHashCode);
-    setupEnvironment(env);
-    return env;
+  public static Environment getNewEnvironment(
+      EventHandler eventHandler, String astFileContentHashCode, Mutability mutability) {
+    return Environment.builder(mutability)
+        .setSkylark()
+        .setGlobals(GLOBALS)
+        .setEventHandler(eventHandler)
+        .setFileContentHashCode(astFileContentHashCode)
+        .build();
   }
 
   @VisibleForTesting
-  public static SkylarkEnvironment getNewEnvironment(EventHandler eventHandler) {
-    return getNewEnvironment(eventHandler, null);
-  }
-
-  private static void setupEnvironment(Environment env) {
-    MethodLibrary.setupMethodEnvironment(env);
-    for (Class<?> moduleClass : MODULES) {
-      Runtime.registerModuleGlobals(env, moduleClass);
-    }
-    // Even though PACKAGE_NAME has no value _now_ and will be bound later,
-    // it needs to be visible for the ValidationEnvironment to be happy.
-    env.update(Runtime.PKG_NAME, Runtime.NONE);
-  }
-
-  /**
-   * Returns a new ValidationEnvironment with the elements of the Skylark modules.
-   */
-  public static ValidationEnvironment getValidationEnvironment() {
-    // TODO(bazel-team): refactor constructors so we don't have those null-s
-    return new ValidationEnvironment(getNewEnvironment(null));
-  }
-
-  public static EvaluationContext newEvaluationContext(EventHandler eventHandler) {
-    return EvaluationContext.newSkylarkContext(
-        getNewEnvironment(eventHandler), getValidationEnvironment());
+  public static Environment getNewEnvironment(
+      EventHandler eventHandler, Mutability mutability) {
+    return getNewEnvironment(eventHandler, null, mutability);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
index e254034..c9e2cee 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
@@ -70,7 +70,6 @@
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModuleNameResolver;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -272,7 +271,7 @@
           if (implicitOutputs instanceof BaseFunction) {
             BaseFunction func = (BaseFunction) implicitOutputs;
             final SkylarkCallbackFunction callback =
-                new SkylarkCallbackFunction(func, ast, (SkylarkEnvironment) funcallEnv);
+                new SkylarkCallbackFunction(func, ast, funcallEnv);
             builder.setImplicitOutputsFunction(
                 new SkylarkImplicitOutputsFunctionWithCallback(callback, ast.getLocation()));
           } else {
@@ -293,8 +292,7 @@
         }
 
         builder.setConfiguredTargetFunction(implementation);
-        builder.setRuleDefinitionEnvironment(
-            ((SkylarkEnvironment) funcallEnv).getGlobalEnvironment());
+        builder.setRuleDefinitionEnvironment(funcallEnv);
         return new RuleFunction(builder, type);
         }
       };
@@ -332,7 +330,7 @@
         RuleClass ruleClass = builder.build(ruleClassName);
         PackageContext pkgContext = (PackageContext) env.lookup(PackageFactory.PKG_CONTEXT);
         return RuleFactory.createAndAddRule(
-            pkgContext, ruleClass, (Map<String, Object>) args[0], ast, env.getStackTrace());
+            pkgContext, ruleClass, (Map<String, Object>) args[0], ast, env);
       } catch (InvalidRuleException | NameConflictException | NoSuchVariableException e) {
         throw new EvalException(ast.getLocation(), e.getMessage());
       }
@@ -352,8 +350,8 @@
     }
   }
 
-  public static void exportRuleFunctions(SkylarkEnvironment env, PathFragment skylarkFile) {
-    for (String name : env.getDirectVariableNames()) {
+  public static void exportRuleFunctions(Environment env, PathFragment skylarkFile) {
+    for (String name : env.getGlobals().getDirectVariableNames()) {
       try {
         Object value = env.lookup(name);
         if (value instanceof RuleFunction) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
index 409b408..405abe4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
@@ -34,11 +34,12 @@
 import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalExceptionWithStackTrace;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkType;
 
@@ -54,13 +55,19 @@
   public static ConfiguredTarget buildRule(RuleContext ruleContext,
       BaseFunction ruleImplementation) {
     String expectFailure = ruleContext.attributes().get("expect_failure", Type.STRING);
-    try {
+    try (Mutability mutability = Mutability.create("configured target")) {
       SkylarkRuleContext skylarkRuleContext = new SkylarkRuleContext(ruleContext);
-      SkylarkEnvironment env = ruleContext.getRule().getRuleClassObject()
-          .getRuleDefinitionEnvironment().cloneEnv(
-              ruleContext.getAnalysisEnvironment().getEventHandler());
-      Object target = ruleImplementation.call(ImmutableList.<Object>of(skylarkRuleContext),
-          ImmutableMap.<String, Object>of(), null, env);
+      Environment env = Environment.builder(mutability)
+          .setSkylark()
+          .setGlobals(
+              ruleContext.getRule().getRuleClassObject().getRuleDefinitionEnvironment().getGlobals())
+          .setEventHandler(ruleContext.getAnalysisEnvironment().getEventHandler())
+          .build(); // NB: we do *not* setLoadingPhase()
+      Object target = ruleImplementation.call(
+          ImmutableList.<Object>of(skylarkRuleContext),
+          ImmutableMap.<String, Object>of(),
+          /*ast=*/null,
+          env);
 
       if (ruleContext.hasErrors()) {
         return null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
index 2b33904..fe44617 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
@@ -20,6 +20,9 @@
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
+import com.google.devtools.build.lib.syntax.Mutability;
+import com.google.devtools.build.lib.syntax.Runtime;
+import com.google.devtools.build.lib.syntax.ValidationEnvironment;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -113,26 +116,33 @@
     if (lookupResult == null) {
       return null;
     }
-
-    BuildFileAST ast = null;
     if (!lookupResult.lookupSuccessful()) {
       return ASTFileLookupValue.noFile();
-    } else {
-      Path path = lookupResult.rootedPath().asPath();
-      // Skylark files end with bzl.
-      boolean parseAsSkylark = astFilePathFragment.getPathString().endsWith(".bzl");
-      try {
-        ast = parseAsSkylark
-            ? BuildFileAST.parseSkylarkFile(path, env.getListener(),
-                packageManager, ruleClassProvider.getSkylarkValidationEnvironment().clone())
-            : BuildFileAST.parseBuildFile(path, env.getListener(),
-                packageManager, false);
-      } catch (IOException e) {
+    }
+    BuildFileAST ast = null;
+    Path path = lookupResult.rootedPath().asPath();
+    // Skylark files end with bzl.
+    boolean parseAsSkylark = astFilePathFragment.getPathString().endsWith(".bzl");
+    try {
+      if (parseAsSkylark) {
+        try (Mutability mutability = Mutability.create("validate")) {
+            ast = BuildFileAST.parseSkylarkFile(path, env.getListener(),
+                packageManager, new ValidationEnvironment(
+                    ruleClassProvider.createSkylarkRuleClassEnvironment(
+                        mutability,
+                        env.getListener(),
+                        // the two below don't matter for extracting the ValidationEnvironment:
+                        /*astFileContentHashCode=*/null,
+                        /*importMap=*/null)
+                    .setupDynamic(Runtime.PKG_NAME, Runtime.NONE)));
+        }
+      } else {
+        ast = BuildFileAST.parseBuildFile(path, env.getListener(), packageManager, false);
+      }
+    } catch (IOException e) {
         throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(
             e.getMessage()), Transience.TRANSIENT);
-      }
     }
-
     return ASTFileLookupValue.withFile(ast);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 9e3b8d5..ac3a6e9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -49,7 +49,6 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.Statement;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.Path;
@@ -553,7 +552,8 @@
     if (eventHandler.hasErrors()) {
       importResult =
           new SkylarkImportResult(
-              ImmutableMap.<PathFragment, SkylarkEnvironment>of(), ImmutableList.<Label>of());
+              ImmutableMap.<PathFragment, com.google.devtools.build.lib.syntax.Environment>of(),
+              ImmutableList.<Label>of());
       includeRepositoriesFetched = true;
     } else {
       importResult =
@@ -581,7 +581,7 @@
       Environment env)
       throws PackageFunctionException {
     ImmutableMap<Location, PathFragment> imports = buildFileAST.getImports();
-    Map<PathFragment, SkylarkEnvironment> importMap = new HashMap<>();
+    Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap = new HashMap<>();
     ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
     try {
       for (Map.Entry<Location, PathFragment> entry : imports.entrySet()) {
@@ -884,9 +884,11 @@
 
   /** A simple value class to store the result of the Skylark imports.*/
   private static final class SkylarkImportResult {
-    private final Map<PathFragment, SkylarkEnvironment> importMap;
+    private final Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap;
     private final ImmutableList<Label> fileDependencies;
-    private SkylarkImportResult(Map<PathFragment, SkylarkEnvironment> importMap,
+    private SkylarkImportResult(
+        Map<PathFragment,
+        com.google.devtools.build.lib.syntax.Environment> importMap,
         ImmutableList<Label> fileDependencies) {
       this.importMap = importMap;
       this.fileDependencies = fileDependencies;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
index 0bd16ae..b3eb957 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
@@ -27,7 +27,7 @@
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -76,7 +76,7 @@
       throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.noFile(file));
     }
 
-    Map<PathFragment, SkylarkEnvironment> importMap = new HashMap<>();
+    Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap = new HashMap<>();
     ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
     BuildFileAST ast = astLookupValue.getAST();
     // TODO(bazel-team): Refactor this code and PackageFunction to reduce code duplications.
@@ -114,10 +114,11 @@
           file));
     }
 
-    SkylarkEnvironment extensionEnv = createEnv(ast, file, importMap, env);
-    // Skylark UserDefinedFunctions are sharing function definition Environments, so it's extremely
-    // important not to modify them from this point. Ideally they should be only used to import
-    // symbols and serve as global Environments of UserDefinedFunctions.
+    // Skylark UserDefinedFunction-s in that file will share this function definition Environment,
+    // which will be frozen by the time it is returned by createEnv.
+    com.google.devtools.build.lib.syntax.Environment extensionEnv =
+        createEnv(ast, file, importMap, env);
+
     return new SkylarkImportLookupValue(
         extensionEnv, new SkylarkFileDependency(label, fileDependencies.build()));
   }
@@ -164,29 +165,34 @@
   }
 
   /**
-   * Creates the SkylarkEnvironment to be imported. After it's returned, the Environment
-   * must not be modified.
+   * Creates the Environment to be imported.
+   * After it's returned, the Environment must not be modified.
    */
-  private SkylarkEnvironment createEnv(BuildFileAST ast, PathFragment file,
-      Map<PathFragment, SkylarkEnvironment> importMap, Environment env)
+  private com.google.devtools.build.lib.syntax.Environment createEnv(
+      BuildFileAST ast,
+      PathFragment file,
+      Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap,
+      Environment env)
           throws InterruptedException, SkylarkImportLookupFunctionException {
     StoredEventHandler eventHandler = new StoredEventHandler();
     // TODO(bazel-team): this method overestimates the changes which can affect the
     // Skylark RuleClass. For example changes to comments or unused functions can modify the hash.
     // A more accurate - however much more complicated - way would be to calculate a hash based on
     // the transitive closure of the accessible AST nodes.
-    SkylarkEnvironment extensionEnv = ruleClassProvider
-        .createSkylarkRuleClassEnvironment(eventHandler, ast.getContentHashCode());
-    extensionEnv.update("native", packageFactory.getNativeModule());
-    extensionEnv.setImportedExtensions(importMap);
-    ast.exec(extensionEnv, eventHandler);
-    SkylarkRuleClassFunctions.exportRuleFunctions(extensionEnv, file);
+    try (Mutability mutability = Mutability.create("importing %s", file)) {
+      com.google.devtools.build.lib.syntax.Environment extensionEnv =
+          ruleClassProvider.createSkylarkRuleClassEnvironment(
+              mutability, eventHandler, ast.getContentHashCode(), importMap)
+          .setupOverride("native", packageFactory.getNativeModule());
+      ast.exec(extensionEnv, eventHandler);
+      SkylarkRuleClassFunctions.exportRuleFunctions(extensionEnv, file);
 
-    Event.replayEventsOn(env.getListener(), eventHandler.getEvents());
-    if (eventHandler.hasErrors()) {
-      throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.errors(file));
+      Event.replayEventsOn(env.getListener(), eventHandler.getEvents());
+      if (eventHandler.hasErrors()) {
+        throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.errors(file));
+      }
+      return extensionEnv;
     }
-    return extensionEnv;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
index 020a426..86db054 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
@@ -18,8 +18,8 @@
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.LoadStatement;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -30,7 +30,7 @@
  */
 public class SkylarkImportLookupValue implements SkyValue {
 
-  private final SkylarkEnvironment importedEnvironment;
+  private final Environment importedEnvironment;
   /**
    * The immediate Skylark file dependency descriptor class corresponding to this value.
    * Using this reference it's possible to reach the transitive closure of Skylark files
@@ -39,15 +39,15 @@
   private final SkylarkFileDependency dependency;
 
   public SkylarkImportLookupValue(
-      SkylarkEnvironment importedEnvironment, SkylarkFileDependency dependency) {
+      Environment importedEnvironment, SkylarkFileDependency dependency) {
     this.importedEnvironment = Preconditions.checkNotNull(importedEnvironment);
     this.dependency = Preconditions.checkNotNull(dependency);
   }
 
   /**
-   * Returns the imported SkylarkEnvironment.
+   * Returns the imported Environment.
    */
-  public SkylarkEnvironment getImportedEnvironment() {
+  public Environment getImportedEnvironment() {
     return importedEnvironment;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
index 30f0c6a..ce45ca2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.packages.WorkspaceFactory;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -62,18 +63,25 @@
     Path repoWorkspace = workspaceRoot.getRoot().getRelative(workspaceRoot.getRelativePath());
     Builder builder = new Builder(repoWorkspace,
         packageFactory.getRuleClassProvider().getRunfilesPrefix());
-    WorkspaceFactory parser = new WorkspaceFactory(
-        builder, packageFactory.getRuleClassProvider(), installDir.getPathString());
-    parser.parse(ParserInputSource.create(
-        ruleClassProvider.getDefaultWorkspaceFile(), new PathFragment("DEFAULT.WORKSPACE")));
-    if (!workspaceFileValue.exists()) {
-      return new PackageValue(builder.build());
-    }
+    try (Mutability mutability = Mutability.create("workspace %s", repoWorkspace)) {
+      WorkspaceFactory parser =
+          new WorkspaceFactory(
+              builder,
+              packageFactory.getRuleClassProvider(),
+              mutability,
+              installDir.getPathString());
+      parser.parse(
+          ParserInputSource.create(
+              ruleClassProvider.getDefaultWorkspaceFile(), new PathFragment("DEFAULT.WORKSPACE")));
+      if (!workspaceFileValue.exists()) {
+        return new PackageValue(builder.build());
+      }
 
-    try {
-      parser.parse(ParserInputSource.create(repoWorkspace));
-    } catch (IOException e) {
-      throw new WorkspaceFileFunctionException(e, Transience.TRANSIENT);
+      try {
+        parser.parse(ParserInputSource.create(repoWorkspace));
+      } catch (IOException e) {
+        throw new WorkspaceFileFunctionException(e, Transience.TRANSIENT);
+      }
     }
 
     return new PackageValue(builder.build());
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 8d5f48f..d28d4d3 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -407,35 +407,29 @@
    * @param args a list of all positional arguments (as in *starArg)
    * @param kwargs a map for key arguments (as in **kwArgs)
    * @param ast the expression for this function's definition
-   * @param parentEnv the lexical Environment for the function call
+   * @param env the Environment in the function is called
    * @return the value resulting from evaluating the function with the given arguments
    * @throws construction of EvalException-s containing source information.
    */
   public Object call(List<Object> args,
       @Nullable Map<String, Object> kwargs,
       @Nullable FuncallExpression ast,
-      @Nullable Environment parentEnv)
+      Environment env)
       throws EvalException, InterruptedException {
-    Environment env = getOrCreateChildEnvironment(parentEnv);
-    env.addToStackTrace(new StackTraceElement(this, kwargs));
+    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();
+
+    Object[] arguments = processArguments(args, kwargs, loc);
+    canonicalizeArguments(arguments, loc);
+
     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 : ast.getLocation();
-
-      Object[] arguments = processArguments(args, kwargs, loc);
-      canonicalizeArguments(arguments, loc);
-
-      try {
-        return call(arguments, ast, env);
-      } catch (EvalExceptionWithStackTrace ex) {
-        throw updateStackTrace(ex, loc);
-      } catch (EvalException | RuntimeException | InterruptedException ex) {
-        throw updateStackTrace(new EvalExceptionWithStackTrace(ex, loc), loc);
-      }
-    } finally {
-      env.removeStackTraceElement();
+      return call(arguments, ast, env);
+    } catch (EvalExceptionWithStackTrace ex) {
+      throw updateStackTrace(ex, loc);
+    } catch (EvalException | RuntimeException | InterruptedException ex) {
+      throw updateStackTrace(new EvalExceptionWithStackTrace(ex, loc), loc);
     }
   }
 
@@ -556,7 +550,7 @@
       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 a7547de..aa9b151 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
@@ -122,9 +122,11 @@
   @Override
   @Nullable
   public Object call(Object[] args,
-      @Nullable FuncallExpression ast, @Nullable Environment env)
+      FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    final Location loc = (ast == null) ? location : ast.getLocation();
+    Preconditions.checkNotNull(ast);
+    Preconditions.checkNotNull(env);
+    Location loc = ast.getLocation();
 
     // Add extra arguments, if needed
     if (extraArgs != null) {
@@ -150,6 +152,7 @@
     long startTime = Profiler.nanoTimeMaybe();
     // Last but not least, actually make an inner call to the function with the resolved arguments.
     try {
+      env.enterScope(this, ast, env.getGlobals());
       return invokeMethod.invoke(this, args);
     } catch (InvocationTargetException x) {
       Throwable e = x.getCause();
@@ -193,6 +196,7 @@
           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 ed30671..25be3fd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -15,18 +15,26 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.syntax.Mutability.Freezable;
+import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
+import com.google.devtools.build.lib.util.Fingerprint;
+import com.google.devtools.build.lib.util.Pair;
+import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Deque;
+import java.io.Serializable;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -34,54 +42,280 @@
 import javax.annotation.Nullable;
 
 /**
- * The BUILD environment.
+ * An Environment is the main entry point to evaluating code in the BUILD language or Skylark.
+ * It embodies all the state that is required to evaluate such code,
+ * except for the current instruction pointer, which is an {@link ASTNode}
+ * whose {@link Statement#exec exec} or {@link Expression#eval eval} method is invoked with
+ * this Environment, in a straightforward direct-style AST-walking interpreter.
+ * {@link Continuation}-s are explicitly represented, but only partly, with another part being
+ * implicit in a series of try-catch statements, to maintain the direct style. One notable trick
+ * is how a {@link UserDefinedFunction} implements returning values as the function catching a
+ * {@link ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the body.
+ *
+ * <p>Every Environment has a {@link Mutability} field, and must be used within a function that
+ * creates and closes this {@link Mutability} with the try-with-resource pattern.
+ * This {@link Mutability} is also used when initializing mutable objects within that Environment;
+ * when closed at the end of the computation freezes the Environment and all those objects that
+ * then become forever immutable. The pattern enforces the discipline that there should be no
+ * dangling mutable Environment, or concurrency between interacting Environment-s.
+ * It is also an error to try to mutate an Environment and its objects from another Environment,
+ * before the {@link Mutability} is closed.
+ *
+ * <p>One creates an Environment using the {@link #builder} function, then
+ * populates it with {@link #setup}, {@link #setupDynamic} and sometimes {@link #setupOverride},
+ * before to evaluate code in it with {@link #eval}, or with {@link BuildFileAST#exec}
+ * (where the AST was obtained by passing a {@link ValidationEnvironment} constructed from the
+ * Environment to {@link BuildFileAST#parseBuildFile} or {@link BuildFileAST#parseSkylarkFile}).
+ * When the computation is over, the frozen Environment can still be queried with {@link #lookup}.
+ *
+ * <p>Final fields of an Environment represent its dynamic state, i.e. state that remains the same
+ * throughout a given evaluation context, and don't change with source code location,
+ * while mutable fields embody its static state, that change with source code location.
+ * The seeming paradox is that the words "dynamic" and "static" refer to the point of view
+ * of the source code, and here we have a dual point of view.
  */
-public class Environment {
-
-  protected final Map<String, Object> env = new HashMap<>();
+public final class Environment implements Freezable, Serializable {
 
   /**
-   * The parent environment. For Skylark it's the global environment,
-   * used for global read only variable lookup.
+   * 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.
    */
-  protected final Environment parent;
+  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();
+    }
+  }
 
   /**
-   * Map from a Skylark extension to an environment, which contains all symbols defined in the
-   * extension.
+   * A Continuation contains data saved during a function call and restored when the function exits.
    */
-  protected Map<PathFragment, SkylarkEnvironment> importedExtensions;
+  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;
+    }
+  }
 
   /**
-   * A set of variables propagating through function calling. It's only used to call
-   * native rules from Skylark build extensions.
+   * Static Frame for lexical variables that are always looked up in the current Environment
+   * or for the definition Environment of the function currently being evaluated.
    */
-  protected Set<String> propagatingVariables = new HashSet<>();
+  private Frame lexicalFrame;
 
-  // Only used in the global environment.
-  // TODO(bazel-team): make this a final field part of constructor.
-  private boolean isLoadingPhase = false;
+  /**
+   * 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;
+
+  /**
+   * Is this Environment being executed in Skylark context?
+   */
+  private boolean isSkylark;
+
+  /**
+   * Is this Environment being executed during the loading phase?
+   * Many builtin functions are only enabled during the loading phase, and check this flag.
+   */
+  private final boolean isLoadingPhase;
+
+  /**
+   * When in a lexical (Skylark) Frame, this set contains the variable names that are global,
+   * as determined not by global declarations (not currently supported),
+   * but by previous lookups that ended being global or dynamic.
+   * This is necessary because if in a function definition something
+   * reads a global variable after which a local variable with the same name is assigned an
+   * Exception needs to be thrown.
+   */
+  @Nullable private Set<String> knownGlobalVariables;
+
+  /**
+   * When in a lexical (Skylark) frame, this lists the names of the functions in the call stack.
+   * We currently use it to artificially disable recursion.
+   */
+  @Nullable private Continuation continuation;
+
+  /**
+   * Enters a scope by saving state to a new Continuation
+   * @param function the function whose scope to enter
+   * @param caller the source AST node for the caller
+   * @param globals the global Frame that this function closes over from its definition Environment
+   */
+  void enterScope(BaseFunction function, FuncallExpression caller, Frame globals) {
+    continuation = new Continuation(
+        continuation, function, caller, lexicalFrame, globalFrame, knownGlobalVariables, isSkylark);
+    lexicalFrame = new Frame(mutability(), null);
+    globalFrame = globals;
+    knownGlobalVariables = new HashSet<String>();
+    isSkylark = true;
+  }
+
+  /**
+   * Exits a scope by restoring state from the current continuation
+   */
+  void exitScope() {
+    Preconditions.checkNotNull(continuation);
+    lexicalFrame = continuation.lexicalFrame;
+    globalFrame = continuation.globalFrame;
+    knownGlobalVariables = continuation.knownGlobalVariables;
+    isSkylark = continuation.isSkylark;
+    continuation = continuation.continuation;
+  }
+
+  /**
+   * 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
+   * 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.
+   * @return true if this Environment corresponds to code during the loading phase.
    */
-  boolean isLoadingPhase() {
+  private boolean isLoadingPhase() {
     return isLoadingPhase;
   }
 
   /**
-   * Enable loading phase only functions in this Environment.
-   * This should only be done during setup before code is evaluated.
-   */
-  public void setLoadingPhase() {
-    isLoadingPhase = true;
-  }
-
-  /**
-   * Checks that the current Evaluation context is in loading phase.
+   * Checks that the current Environment is in the loading phase.
    * @param symbol name of the function being only authorized thus.
    */
   public void checkLoadingPhase(String symbol, Location loc) throws EvalException {
@@ -91,168 +325,378 @@
   }
 
   /**
-   * Is this a global environment?
-   * @return true if this is a global (top-level) environment
-   * as opposed to inside the body of a function
+   * Is this a global Environment?
+   * @return true if the current code is being executed at the top-level,
+   * as opposed to inside the body of a function.
    */
-  public boolean isGlobal() {
-    return true;
+  boolean isGlobal() {
+    return lexicalFrame == null;
   }
 
   /**
-   * An EventHandler for errors and warnings. This is not used in the BUILD language,
-   * however it might be used in Skylark code called from the BUILD language.
+   * Is the current code Skylark?
+   * @return true if Skylark was enabled when this code was read.
    */
-  @Nullable protected EventHandler eventHandler;
-
-  /**
-   * A stack trace containing the current history of functions and the calling rule.
-   *
-   * <p>For the rule, the stack trace has two elements: one for the call to the rule in the BUILD
-   * file and one for the actual rule implementation.
-   */
-  private Deque<StackTraceElement> stackTrace;
-
-  /**
-   * 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();
-  }
-
-  public Environment() {
-    this(new LinkedList<StackTraceElement>());
+  // TODO(bazel-team): Delete this function.
+  // This function is currently used in various functions that change their behavior with respect to
+  // lists depending on the Skylark-ness of the code; lists should be unified between the two modes.
+  boolean isSkylark() {
+    return isSkylark;
   }
 
   /**
-   * Constructs an empty child environment.
+   * Is the caller of the current function executing Skylark code?
+   * @return true if this is skylark was enabled when this code was read.
    */
-  public Environment(Environment parent, Deque<StackTraceElement> stackTrace) {
-    Preconditions.checkNotNull(parent);
-    this.parent = parent;
-    this.importedExtensions = new HashMap<>();
-    this.stackTrace = stackTrace;
+  // TODO(bazel-team): Delete this function.
+  // This function is currently used by MethodLibrary to modify behavior of lists
+  // depending on the Skylark-ness of the code; lists should be unified between the two modes.
+  boolean isCallerSkylark() {
+    return continuation.isSkylark;
   }
 
-  public Environment(Environment parent) {
-    this(parent, new LinkedList<StackTraceElement>());
+  @Override
+  public Mutability mutability() {
+    // the mutability of the environment is that of its dynamic frame.
+    return dynamicFrame.mutability();
   }
 
   /**
-   * Constructs an empty child environment with an EventHandler.
+   * @return the current Frame, in which variable side-effects happen.
    */
-  public Environment(Environment parent, EventHandler eventHandler) {
-    this(parent);
-    this.eventHandler = Preconditions.checkNotNull(eventHandler);
+  private Frame currentFrame() {
+    return isGlobal() ? globalFrame : lexicalFrame;
   }
 
+  /**
+   * @return the global variables for the Environment (not including dynamic bindings).
+   */
+  public Frame getGlobals() {
+    return globalFrame;
+  }
+
+  /**
+   * Returns an EventHandler for errors and warnings.
+   * The BUILD language doesn't use it directly, but can call Skylark code that does use it.
+   * @return an EventHandler
+   */
   public EventHandler getEventHandler() {
     return eventHandler;
   }
 
-  // Sets up the global environment
-  private void setupGlobal() {
-    // In Python 2.x, True and False are global values and can be redefined by the user.
-    // In Python 3.x, they are keywords. We implement them as values, for the sake of
-    // simplicity. We define them as Boolean objects.
-    update("False", Runtime.FALSE);
-    update("True", Runtime.TRUE);
-    update("None", Runtime.NONE);
+  /**
+   * @return the current stack trace as a list of functions.
+   */
+  public ImmutableList<BaseFunction> getStackTrace() {
+    ImmutableList.Builder<BaseFunction> builder = new ImmutableList.Builder<>();
+    for (Continuation k = continuation; k != null; k = k.continuation) {
+      builder.add(k.function);
+    }
+    return builder.build().reverse();
   }
 
-  public boolean isSkylark() {
-    return false;
+  /**
+   * Return the name of the top-level function being called and the location of the call.
+   */
+  public Pair<BaseFunction, Location> getTopCall() {
+    Continuation continuation = this.continuation;
+    if (continuation == null) {
+      return null;
+    }
+    while (continuation.continuation != null) {
+      continuation = continuation.continuation;
+    }
+    return new Pair<>(continuation.function, continuation.caller.getLocation());
   }
 
-  protected boolean hasVariable(String varname) {
-    return env.containsKey(varname);
+  /**
+   * Constructs an Environment.
+   * This is the main, most basic constructor.
+   * @param globalFrame a frame for the global Environment
+   * @param dynamicFrame a frame for the dynamic Environment
+   * @param eventHandler an EventHandler for warnings, errors, etc
+   * @param importedExtensions frames for extensions from which to import bindings with load()
+   * @param isSkylark true if in Skylark context
+   * @param fileContentHashCode a hash for the source file being evaluated, if any
+   * @param isLoadingPhase true if in loading phase
+   */
+  private Environment(
+      Frame globalFrame,
+      Frame dynamicFrame,
+      EventHandler eventHandler,
+      Map<PathFragment, Environment> importedExtensions,
+      boolean isSkylark,
+      @Nullable String fileContentHashCode,
+      boolean isLoadingPhase) {
+    this.globalFrame = Preconditions.checkNotNull(globalFrame);
+    this.dynamicFrame = Preconditions.checkNotNull(dynamicFrame);
+    Preconditions.checkArgument(globalFrame.mutability().isMutable());
+    Preconditions.checkArgument(dynamicFrame.mutability().isMutable());
+    this.eventHandler = eventHandler;
+    this.importedExtensions = importedExtensions;
+    this.isSkylark = isSkylark;
+    this.fileContentHashCode = fileContentHashCode;
+    this.isLoadingPhase = isLoadingPhase;
+  }
+
+  /**
+   * A Builder class for 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());
+      if (parent != null) {
+        Preconditions.checkArgument(!parent.mutability().isMutable());
+      }
+      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;
+    }
+  }
+
+  public static Builder builder(Mutability mutability) {
+    return new Builder(mutability);
+  }
+
+  /**
+   * Sets a binding for a special dynamic variable in this Environment.
+   * This is not for end-users, and will throw an AssertionError in case of conflict.
+   * @param varname the name of the dynamic variable to be bound
+   * @param value a value to bind to the variable
+   * @return this Environment, in fluid style
+   */
+  public 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);
+    }
+    return this;
+  }
+
+
+  /**
+   * Modifies a binding in the current Frame of this Environment, as would an
+   * {@link AssignmentStatement}. Does not try to modify an inherited binding.
+   * This will shadow any inherited binding, which may be an error
+   * that you want to guard against before calling this function.
+   * @param varname the name of the variable to be bound
+   * @param value the value to bind to the variable
+   * @return this Environment, in fluid style
+   */
+  public Environment update(String varname, Object value) throws EvalException {
+    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);
+    }
+    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
+   */
+  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 {
-    Object value = env.get(varname);
-    if (value == null) {
-      if (parent != null) {
-        return parent.lookup(varname);
+    // 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);
     }
-    return value;
+    if (knownGlobalVariables != null) {
+      knownGlobalVariables.add(varname);
+    }
+    if (globalValue != null) {
+      return globalValue;
+    }
+    return dynamicValue;
   }
 
   /**
-   * Like <code>lookup(String)</code>, but instead of throwing an exception in
-   * the case where "varname" is not defined, "defaultValue" is returned instead.
-   *
+   * Like {@link #lookup(String)}, but instead of throwing an exception in the case
+   * where <code>varname</code> is not defined, <code>defaultValue</code> is returned instead.
    */
   public Object lookup(String varname, Object defaultValue) {
-    Object value = env.get(varname);
-    if (value == null) {
-      if (parent != null) {
-        return parent.lookup(varname, defaultValue);
-      }
+    Preconditions.checkState(!isSkylark);
+    try {
+      return lookup(varname);
+    } catch (NoSuchVariableException e) {
       return defaultValue;
     }
-    return value;
   }
 
   /**
-   * Updates the value of variable "varname" in the environment, corresponding
-   * to an {@link AssignmentStatement}.
+   * @return true if varname is a known global variable,
+   * because it has been read in the context of the current function.
    */
-  public Environment update(String varname, Object value) {
-    Preconditions.checkNotNull(value, "update(value == null)");
-    env.put(varname, value);
-    return this;
+  boolean isKnownGlobalVariable(String varname) {
+    return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
+  }
+
+  public void handleEvent(Event event) {
+    eventHandler.handle(event);
   }
 
   /**
-   * 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 void updateAndPropagate(String varname, Object value) {
-    update(varname, value);
-    propagatingVariables.add(varname);
-  }
-
-  /**
-   * Remove the variable from the environment, returning
-   * any previous mapping (null if there was none).
-   */
-  public Object remove(String varname) {
-    return env.remove(varname);
-  }
-
-  /**
-   * Returns the (immutable) set of names of all variables directly defined in this environment.
-   */
-  public Set<String> getDirectVariableNames() {
-    return env.keySet();
-  }
-
-  /**
-   * Returns the (immutable) set of names of all variables defined in this
-   * environment. Exposed for testing; not very efficient!
+   * @return the (immutable) set of names of all variables defined in this
+   * Environment. Exposed for testing.
    */
   @VisibleForTesting
   public Set<String> getVariableNames() {
-    if (parent == null) {
-      return env.keySet();
-    } else {
-      Set<String> vars = new HashSet<>();
-      vars.addAll(env.keySet());
-      vars.addAll(parent.getVariableNames());
-      return vars;
+    Set<String> vars = new HashSet<>();
+    if (lexicalFrame != null) {
+      lexicalFrame.addVariableNamesTo(vars);
     }
+    globalFrame.addVariableNamesTo(vars);
+    dynamicFrame.addVariableNamesTo(vars);
+    return vars;
   }
 
   @Override
@@ -268,23 +712,29 @@
   @Override
   public String toString() {
     StringBuilder out = new StringBuilder();
-    out.append("Environment{");
-    List<String> keys = new ArrayList<>(env.keySet());
-    Collections.sort(keys);
-    for (String key : keys) {
-      out.append(key).append(" -> ").append(env.get(key)).append(", ");
-    }
-    out.append("}");
-    if (parent != null) {
-      out.append("=>");
-      out.append(parent);
-    }
+    out.append("Environment(lexicalFrame=");
+    out.append(lexicalFrame);
+    out.append(", globalFrame=");
+    out.append(globalFrame);
+    out.append(", dynamicFrame=");
+    out.append(dynamicFrame);
+    out.append(", eventHandler.getClass()=");
+    out.append(eventHandler.getClass());
+    out.append(", importedExtensions=");
+    out.append(importedExtensions);
+    out.append(", isSkylark=");
+    out.append(isSkylark);
+    out.append(", fileContentHashCode=");
+    out.append(fileContentHashCode);
+    out.append(", isLoadingPhase=");
+    out.append(isLoadingPhase);
+    out.append(")");
     return out.toString();
   }
 
   /**
-   * An exception thrown when an attempt is made to lookup a non-existent
-   * variable in the environment.
+   * An Exception thrown when an attempt is made to lookup a non-existent
+   * variable in the Environment.
    */
   public static class NoSuchVariableException extends Exception {
     NoSuchVariableException(String variable) {
@@ -293,7 +743,7 @@
   }
 
   /**
-   * An exception thrown when an attempt is made to import a symbol from a file
+   * An Exception thrown when an attempt is made to import a symbol from a file
    * that was not properly loaded.
    */
   public static class LoadFailedException extends Exception {
@@ -303,78 +753,156 @@
     }
   }
 
-  public void setImportedExtensions(Map<PathFragment, SkylarkEnvironment> importedExtensions) {
-    this.importedExtensions = importedExtensions;
-  }
-
   public void importSymbol(PathFragment extension, Identifier symbol, String nameInLoadedFile)
       throws NoSuchVariableException, LoadFailedException {
+    Preconditions.checkState(isGlobal()); // loading is only allowed at global scope.
+
     if (!importedExtensions.containsKey(extension)) {
       throw new LoadFailedException(extension.toString());
     }
 
     Object value = importedExtensions.get(extension).lookup(nameInLoadedFile);
-    if (!isSkylark()) {
+    // TODO(bazel-team): Unify data structures between Skylark and BUILD,
+    // and stop doing the conversions below:
+    if (!isSkylark) {
       value = SkylarkType.convertFromSkylark(value);
     }
 
-    update(symbol.getName(), value);
-  }
-
-  public ImmutableList<StackTraceElement> getStackTrace() {
-    return ImmutableList.copyOf(stackTrace);
-  }
-
-  protected Deque<StackTraceElement> getCopyOfStackTrace() {
-    return new LinkedList<>(stackTrace);
-  }
-
-  /**
-   * Adds the given element to the stack trace (iff the stack is empty) and returns whether it was
-   * successful.
-   */
-  public boolean tryAddingStackTraceRoot(StackTraceElement element) {
-    if (stackTrace.isEmpty()) {
-      stackTrace.add(element);
-      return true;
+    try {
+      update(symbol.getName(), value);
+    } catch (EvalException e) {
+      throw new LoadFailedException(extension.toString());
     }
-    return false;
-  }
-  
-  public void addToStackTrace(StackTraceElement element)    {
-    stackTrace.add(element);
   }
 
   /**
-   * 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.
+   * Returns a hash code calculated from the hash code of this Environment and the
+   * transitive closure of other Environments it loads.
    */
-  public void removeStackTraceRoot() {
-    Preconditions.checkArgument(stackTrace.size() == 1);
-    stackTrace.clear();
+  // 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();
   }
 
-  public void removeStackTraceElement() {
-    // TODO(fwe): find out why the precond doesn't work
-    //    Preconditions.checkArgument(stackTrace.size() > 1);
-    stackTrace.removeLast();
+
+  /** 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();
+    }
+  }
+
+  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();
+    }
+  }
+
+  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();
+    }
+  }
+
+
+  /**
+   * The fail fast handler, which throws a AssertionError whenever an error or warning occurs.
+   */
+  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;
+    }
+  }
+
+  /** 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);
   }
 
   /**
-   * Returns whether the given {@link BaseFunction} is part of this {@link Environment}'s stack
-   * trace.
+   * Parses some String input without a supporting file, returning statements and comments.
+   * @param input a list of lines of code
    */
-  public boolean stackTraceContains(BaseFunction function) {
-    for (StackTraceElement element : stackTrace) {
-      if (element.hasFunction(function)) {
-        return true;
+  @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);
+  }
+
+  /**
+   * 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;
+  }
+
+  /**
+   * 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
+   */
+  @Nullable public Object eval(String... input) throws EvalException, InterruptedException {
+    Object last = null;
+    for (Statement statement : parseFile(input)) {
+      if (statement instanceof ExpressionStatement) {
+        last = ((ExpressionStatement) statement).getExpression().eval(this);
+      } else {
+        statement.exec(this);
+        last = null;
       }
     }
-    return false;
+    return last;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java
index 82ca835..714556e 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 @@
       return String.format(
           "\tFile \"%s\", line %d, in %s%n\t\t%s",
           printPath(location.getPath()),
-          location.getStartLineAndColumn().getLine(),
+          location.getStartLine(),
           element.getLabel(),
           element.getCause().getLabel());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
deleted file mode 100644
index 6a24cb3..0000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
+++ /dev/null
@@ -1,195 +0,0 @@
-// Copyright 2015 Google Inc. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.devtools.build.lib.syntax;
-
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.events.EventKind;
-import com.google.devtools.build.lib.packages.CachingPackageLocator;
-import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
-import com.google.devtools.build.lib.vfs.Path;
-
-import java.util.List;
-
-import javax.annotation.Nullable;
-
-/**
- * Context for the evaluation of programs.
- */
-public final class EvaluationContext {
-
-  @Nullable private EventHandler eventHandler;
-  private Environment env;
-  @Nullable private ValidationEnvironment validationEnv;
-  private boolean parsePython;
-
-  private EvaluationContext(EventHandler eventHandler, Environment env,
-      @Nullable ValidationEnvironment validationEnv, boolean parsePython) {
-    this.eventHandler = eventHandler;
-    this.env = env;
-    this.validationEnv = validationEnv;
-    this.parsePython = parsePython;
-  }
-
-  /**
-   * The fail fast handler, which throws a runtime exception whenever we encounter an error event.
-   */
-  public static final EventHandler FAIL_FAST_HANDLER = new EventHandler() {
-      @Override
-      public void handle(Event event) {
-        Preconditions.checkArgument(
-            !EventKind.ERRORS_AND_WARNINGS.contains(event.getKind()), event);
-      }
-    };
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env,
-      boolean parsePython) {
-    return new EvaluationContext(eventHandler, env, null, parsePython);
-  }
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env) {
-    return newBuildContext(eventHandler, env, false);
-  }
-
-  public static EvaluationContext newBuildContext(EventHandler eventHandler) {
-    return newBuildContext(eventHandler, new Environment());
-  }
-
-  public static EvaluationContext newSkylarkContext(
-      Environment env, ValidationEnvironment validationEnv) {
-    return new EvaluationContext(env.getEventHandler(), env, validationEnv, false);
-  }
-
-  public static EvaluationContext newSkylarkContext(EventHandler eventHandler) {
-    return newSkylarkContext(new SkylarkEnvironment(eventHandler), new ValidationEnvironment());
-  }
-
-  /** Base context for Skylark evaluation for internal use only, while initializing builtins */
-  static final EvaluationContext SKYLARK_INITIALIZATION = newSkylarkContext(FAIL_FAST_HANDLER);
-
-  @VisibleForTesting
-  public Environment getEnvironment() {
-    return env;
-  }
-
-  /** Mock package locator */
-  private static final class EmptyPackageLocator implements CachingPackageLocator {
-    @Override
-    public Path getBuildFileForPackage(PackageIdentifier packageName) {
-      return null;
-    }
-  }
-
-  /** An empty package locator */
-  private static final CachingPackageLocator EMPTY_PACKAGE_LOCATOR = new EmptyPackageLocator();
-
-  /** Create a Lexer without a supporting file */
-  @VisibleForTesting
-  Lexer createLexer(String... input) {
-    return new Lexer(ParserInputSource.create(Joiner.on("\n").join(input), null),
-        eventHandler);
-  }
-
-  /** Is this a Skylark evaluation context? */
-  public boolean isSkylark() {
-    return env.isSkylark();
-  }
-
-  /** Parse a string without a supporting file, returning statements and comments */
-  @VisibleForTesting
-  Parser.ParseResult parseFileWithComments(String... input) {
-    return isSkylark()
-        ? Parser.parseFileForSkylark(createLexer(input), eventHandler, null, validationEnv)
-        : Parser.parseFile(createLexer(input), eventHandler, EMPTY_PACKAGE_LOCATOR, parsePython);
-  }
-
-  /** Parse a string without a supporting file, returning statements only */
-  @VisibleForTesting
-  List<Statement> parseFile(String... input) {
-    return parseFileWithComments(input).statements;
-  }
-
-  /** Parse an Expression from string without a supporting file */
-  @VisibleForTesting
-  Expression parseExpression(String... input) {
-    return Parser.parseExpression(createLexer(input), eventHandler);
-  }
-
-  /** Evaluate an Expression */
-  @VisibleForTesting
-  Object evalExpression(Expression expression) throws EvalException, InterruptedException {
-    return expression.eval(env);
-  }
-
-  /** Evaluate an Expression as parsed from String-s */
-  Object evalExpression(String... input) throws EvalException, InterruptedException {
-    return evalExpression(parseExpression(input));
-  }
-
-  /** Parse a build (not Skylark) Statement from string without a supporting file */
-  @VisibleForTesting
-  Statement parseStatement(String... input) {
-    return Parser.parseStatement(createLexer(input), eventHandler);
-  }
-
-  /**
-   * Evaluate a Statement
-   * @param statement the Statement
-   * @return the value of the evaluation, if it's an Expression, or else null
-   */
-  @Nullable private Object eval(Statement statement) throws EvalException, InterruptedException {
-    if (statement instanceof ExpressionStatement) {
-      return evalExpression(((ExpressionStatement) statement).getExpression());
-    }
-    statement.exec(env);
-    return null;
-  }
-
-  /**
-   * Evaluate a list of Statement-s
-   * @return the value of the last statement if it's an Expression or else null
-   */
-  @Nullable private Object eval(List<Statement> statements)
-      throws EvalException, InterruptedException {
-    Object last = null;
-    for (Statement statement : statements) {
-      last = eval(statement);
-    }
-    return last;
-  }
-
-  /** Update a variable in the environment, in fluent style */
-  public EvaluationContext update(String varname, Object value) throws EvalException {
-    env.update(varname, value);
-    if (validationEnv != null) {
-      validationEnv.declare(varname, null);
-    }
-    return this;
-  }
-
-  /** Lookup a variable in the environment */
-  public Object lookup(String varname) throws NoSuchVariableException {
-    return env.lookup(varname);
-  }
-
-  /** Evaluate a series of statements */
-  public Object eval(String... input) throws EvalException, InterruptedException {
-    return eval(parseFile(input));
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
index b7842d4..1886843 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 @@
   /**
    * Returns the inferred type of the result of the Expression.
    *
-   * <p>Checks the semantics of the Expression using the SkylarkEnvironment according to
-   * the rules of the Skylark language, throws EvalException in case of a semantical error.
+   * <p>Checks the semantics of the Expression using the {@link Environment} according to
+   * the rules of the Skylark language, throws {@link EvalException} in case of a semantical error.
    *
    * @see Statement
    */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 8d1eb56..76737dd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -353,21 +353,11 @@
   // TODO(bazel-team): If there's exactly one usable method, this works. If there are multiple
   // matching methods, it still can be a problem. Figure out how the Java compiler does it
   // exactly and copy that behaviour.
-  // TODO(bazel-team): check if this and SkylarkBuiltInFunctions.createObject can be merged.
-  private Object invokeJavaMethod(
-      Object obj, Class<?> objClass, String methodName, List<Object> args, boolean hasKwArgs)
-      throws EvalException {
+  private MethodDescriptor findJavaMethod(
+      Class<?> objClass, String methodName, List<Object> args) throws EvalException {
     MethodDescriptor matchingMethod = null;
     List<MethodDescriptor> methods = getMethods(objClass, methodName, args.size(), getLocation());
     if (methods != null) {
-      if (hasKwArgs) {
-        throw new EvalException(
-            func.getLocation(),
-            String.format(
-                "Keyword arguments are not allowed when calling a java method"
-                + "\nwhile calling method '%s' on object of type %s",
-                func.getName(), EvalUtils.getDataTypeNameFromClass(objClass)));
-      }
       for (MethodDescriptor method : methods) {
         Class<?>[] params = method.getMethod().getParameterTypes();
         int i = 0;
@@ -391,12 +381,11 @@
       }
     }
     if (matchingMethod != null && !matchingMethod.getAnnotation().structField()) {
-      return callMethod(matchingMethod, methodName, obj, args.toArray(), getLocation());
-    } else {
-      throw new EvalException(getLocation(), "No matching method found for "
-          + formatMethod(methodName, args) + " in "
-          + EvalUtils.getDataTypeNameFromClass(objClass));
+      return matchingMethod;
     }
+    throw new EvalException(getLocation(), "No matching method found for "
+        + formatMethod(methodName, args) + " in "
+        + EvalUtils.getDataTypeNameFromClass(objClass));
   }
 
   private String formatMethod(String methodName, List<Object> args) {
@@ -490,20 +479,7 @@
 
   @Override
   Object eval(Environment env) throws EvalException, InterruptedException {
-    // Adds the calling rule to the stack trace of the Environment if it is a BUILD environment.
-    // There are two reasons for this:
-    // a) When using aliases in load(), the rule class name in the BUILD file will differ from
-    //    the implementation name in the bzl file. Consequently, we need to store the calling name.
-    // b) We need the location of the calling rule inside the BUILD file.
-    boolean hasAddedElement =
-        env.isSkylark() ? false : env.tryAddingStackTraceRoot(new StackTraceElement(func, args));
-    try {
-      return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
-    } finally {
-      if (hasAddedElement) {
-        env.removeStackTraceRoot();
-      }
-    }
+    return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
   }
 
   /**
@@ -550,15 +526,28 @@
       // When calling a Java method, the name is not in the Environment,
       // so evaluating 'func' would fail.
       evalArguments(posargs, kwargs, env, null);
+      Class<?> objClass;
+      Object obj;
       if (objValue instanceof Class<?>) {
-        // Static Java method call. We can return the value from here directly because
-        // invokeJavaMethod() has special checks.
-        return invokeJavaMethod(
-            null, (Class<?>) objValue, func.getName(), posargs.build(), !kwargs.isEmpty());
+        // Static call
+        obj = null;
+        objClass = (Class<?>) objValue;
       } else {
-        return invokeJavaMethod(
-            objValue, objValue.getClass(), func.getName(), posargs.build(), !kwargs.isEmpty());
+        obj = objValue;
+        objClass = objValue.getClass();
       }
+      String name = func.getName();
+      ImmutableList<Object> args = posargs.build();
+      MethodDescriptor method = findJavaMethod(objClass, name, args);
+      if (!kwargs.isEmpty()) {
+        throw new EvalException(
+            func.getLocation(),
+            String.format(
+                "Keyword arguments are not allowed when calling a java method"
+                + "\nwhile calling method '%s' for type %s",
+                name, EvalUtils.getDataTypeNameFromClass(objClass)));
+      }
+      return callMethod(method, name, obj, args.toArray(), getLocation());
     } else {
       throw new EvalException(
           getLocation(),
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
index ae7c027..acc09c9 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
@@ -50,10 +50,14 @@
         defaultValues.add(expr.eval(env));
       }
     }
-    env.update(ident.getName(), new UserDefinedFunction(
-        ident, FunctionSignature.WithValues.<Object, SkylarkType>create(
-            signature.getSignature(), defaultValues, types),
-        statements, (SkylarkEnvironment) env));
+    env.update(
+        ident.getName(),
+        new UserDefinedFunction(
+            ident,
+            FunctionSignature.WithValues.<Object, SkylarkType>create(
+                signature.getSignature(), defaultValues, types),
+            statements,
+            env.getGlobals()));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index df5f486..1a39755 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -84,8 +84,7 @@
     if (env.isSkylark()) {
       // The variable may have been referenced successfully if a global variable
       // with the same name exists. In this case an Exception needs to be thrown.
-      SkylarkEnvironment skylarkEnv = (SkylarkEnvironment) env;
-      if (skylarkEnv.hasBeenReadGlobalVariable(ident.getName())) {
+      if (env.isKnownGlobalVariable(ident.getName())) {
         throw new EvalException(
             loc,
             String.format(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 996ae41..b1ca1f6 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 @@
       new BuiltinFunction("append") {
         public Runtime.NoneType invoke(List<Object> self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isSkylark()) {
+          if (env.isCallerSkylark()) {
             throw new EvalException(loc,
                 "function 'append' is not available in Skylark");
           }
@@ -806,7 +806,7 @@
       new BuiltinFunction("extend") {
         public Runtime.NoneType invoke(List<Object> self, List<Object> items,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isSkylark()) {
+          if (env.isCallerSkylark()) {
             throw new EvalException(loc,
                 "function 'append' is not available in Skylark");
           }
@@ -920,7 +920,7 @@
       List<Object> list = Lists.newArrayListWithCapacity(dict.size());
       for (Map.Entry<?, ?> entries : dict.entrySet()) {
         List<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
-        list.add(env.isSkylark() ? SkylarkList.tuple(item) : item);
+        list.add(env.isCallerSkylark() ? SkylarkList.tuple(item) : item);
       }
       return convert(list, env, loc);
     }
@@ -966,7 +966,7 @@
   @SuppressWarnings("unchecked")
   private static Iterable<Object> convert(Collection<?> list, Environment env, Location loc)
       throws EvalException {
-    if (env.isSkylark()) {
+    if (env.isCallerSkylark()) {
       return SkylarkList.list(list, loc);
     } else {
       return Lists.newArrayList(list);
@@ -1386,7 +1386,7 @@
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction print = new BuiltinFunction("print") {
     public Runtime.NoneType invoke(String sep, SkylarkList starargs,
-        Location loc, SkylarkEnvironment env) throws EvalException {
+        Location loc, Environment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
                 @Override
@@ -1493,19 +1493,6 @@
 
 
   /**
-   * Set up a given environment for supported class methods.
-   */
-  public static void setupMethodEnvironment(Environment env) {
-    setupMethodEnvironment(env, env.isSkylark() ? skylarkGlobalFunctions : buildGlobalFunctions);
-  }
-
-  private static void setupMethodEnvironment(Environment env, Iterable<BaseFunction> functions) {
-    for (BaseFunction function : functions) {
-      env.update(function.getName(), function);
-    }
-  }
-
-  /**
    * Collect global functions for the validation environment.
    */
   public static void setupValidationEnvironment(Set<String> builtIn) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
new file mode 100644
index 0000000..5120f8d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
@@ -0,0 +1,136 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.syntax;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * A Mutability is a resource associated with an {@link Environment} during an evaluation,
+ * that gives those who possess it a revokable capability to mutate this Environment and
+ * the objects created within that {@link Environment}. At the end of the evaluation,
+ * the resource is irreversibly closed, at which point the capability is revoked,
+ * and it is not possible to mutate either this {@link Environment} or these objects.
+ *
+ * <p>Evaluation in an {@link Environment} may thus mutate objects created in the same
+ * {@link Environment}, but may not mutate {@link Freezable} objects (lists, sets, dicts)
+ * created in a previous, concurrent or future {@link Environment}, and conversely,
+ * the bindings and objects in this {@link Environment} will be protected from
+ * mutation by evaluation in a different {@link Environment}.
+ *
+ * <p>Only a single thread may use the {@link Environment} and objects created within it while the
+ * Mutability is still mutable as tested by {@link #isMutable}. Once the Mutability resource
+ * is closed, the {@link Environment} and its objects are immutable and can be simultaneously used
+ * by arbitrarily many threads.
+ *
+ * <p>The safe usage of a Mutability requires to always use try-with-resource style:
+ * <code>try(Mutability mutability = Mutability.create(fmt, ...)) { ... }</code>
+ * Thus, you can create a Mutability, build an {@link Environment}, mutate that {@link Environment}
+ * and create mutable objects as you evaluate in that {@link Environment}, and finally return the
+ * resulting {@link Environment}, at which point the resource is closed, and the {@link Environment}
+ * and the objects it contains all become immutable.
+ * (Unsafe usage is allowed only in test code that is not part of the Bazel jar.)
+ */
+// TODO(bazel-team): When we start using Java 8, this safe usage pattern can be enforced
+// through the use of a higher-order function.
+public final class Mutability implements AutoCloseable {
+  private boolean isMutable;
+  private final Object annotation; // For error reporting
+
+  /**
+   * Creates a Mutability.
+   * @param annotation an Object used for error reporting,
+   * describing to the user the context in which this Mutability was active.
+   */
+  private Mutability(Object annotation) {
+    this.isMutable = true;
+    this.annotation = Preconditions.checkNotNull(annotation);
+  }
+
+  /**
+   * Creates a Mutability.
+   * @param pattern is a {@link Printer#format} pattern used to lazily produce a string
+   * for error reporting
+   * @param arguments are the optional {@link Printer#format} arguments to produce that string
+   */
+  public static Mutability create(String pattern, Object... arguments) {
+    return new Mutability(Printer.formattable(pattern, arguments));
+  }
+
+  Object getAnnotation() {
+    return annotation;
+  }
+
+  @Override
+  public String toString() {
+    return String.format(isMutable ? "[%s]" : "(%s)", annotation);
+  }
+
+  boolean isMutable() {
+    return isMutable;
+  }
+
+  /**
+   * Freezes this Mutability, marking as immutable all {@link Freezable} objects that use it.
+   */
+  @Override
+  public void close() {
+    isMutable = false;
+  }
+
+  /**
+   * A MutabilityException will be thrown when the user attempts to mutate an object he shouldn't.
+   */
+  static class MutabilityException extends Exception {
+    MutabilityException(String message) {
+      super(message);
+    }
+  }
+
+  /**
+   * Each {@link Freezable} object possesses a revokable Mutability attribute telling whether
+   * the object is still mutable. All {@link Freezable} objects created in the same
+   * {@link Environment} will share the same Mutability, inherited from this {@link Environment}.
+   * Only evaluation in the same {@link Environment} is allowed to mutate these objects,
+   * and only until the Mutability is irreversibly revoked.
+   */
+  public interface Freezable {
+    /**
+     * Returns the {@link Mutability} capability associated with this Freezable object.
+     */
+    Mutability mutability();
+  }
+
+  /**
+   * Checks that this Freezable object can be mutated from the given {@link Environment}.
+   * @param object a Freezable object that we check is still mutable.
+   * @param env the {@link Environment} attempting the mutation.
+   * @throws MutabilityException when the object was frozen already, or is from another context.
+   */
+  public static void checkMutable(Freezable object, Environment env)
+      throws MutabilityException {
+    if (!object.mutability().isMutable()) {
+      throw new MutabilityException("trying to mutate a frozen object");
+    }
+    // Consider an {@link Environment} e1, in which is created {@link UserDefinedFunction} f1,
+    // that closes over some variable v1 bound to list l1. If somehow, via the magic of callbacks,
+    // f1 or l1 is passed as argument to some function f2 evaluated in {@link environment} e2
+    // while e1 is be mutable, e2, being a different {@link Environment}, should not be
+    // allowed to mutate objects from e1. It's a bug, that shouldn't happen in our current code
+    // base, so we throw an AssertionError. If in the future such situations are allowed to happen,
+    // then we should throw a MutabilityException instead.
+    if (!object.mutability().equals(env.mutability())) {
+      throw new AssertionError("trying to mutate an object from a different context");
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 50ef2546..9230d6b 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 @@
 
   @SkylarkSignature(name = "True", returnType = Boolean.class,
       doc = "Literal for the boolean true.")
-  static final Boolean TRUE = true;
+  private static final Boolean TRUE = true;
 
   @SkylarkSignature(name = "False", returnType = Boolean.class,
       doc = "Literal for the boolean false.")
-  static final Boolean FALSE = false;
+  private static final Boolean FALSE = false;
 
   /**
    * There should be only one instance of this type to allow "== None" tests.
@@ -70,11 +70,11 @@
   /**
    * Set up a given environment for supported class methods.
    */
-  static Environment setupConstants(Environment env) throws EvalException {
+  static Environment setupConstants(Environment env) {
     // In Python 2.x, True and False are global values and can be redefined by the user.
     // In Python 3.x, they are keywords. We implement them as values, for the sake of
     // simplicity. We define them as Boolean objects.
-    return env.update("False", FALSE).update("True", TRUE).update("None", NONE);
+    return env.setup("False", FALSE).setup("True", TRUE).setup("None", NONE);
   }
 
 
@@ -128,7 +128,7 @@
   public static void registerModuleGlobals(Environment env, Class<?> moduleClass) {
     try {
       if (moduleClass.isAnnotationPresent(SkylarkModule.class)) {
-        env.update(
+        env.setup(
             moduleClass.getAnnotation(SkylarkModule.class).name(), moduleClass.newInstance());
       }
       for (Field field : moduleClass.getDeclaredFields()) {
@@ -142,7 +142,7 @@
           if (!(value instanceof BuiltinFunction.Factory
               || (value instanceof BaseFunction
                   && !annotation.objectType().equals(Object.class)))) {
-            env.update(annotation.name(), value);
+            env.setup(annotation.name(), value);
           }
         }
       }
@@ -168,9 +168,9 @@
   }
 
   static void setupMethodEnvironment(
-      Environment env, Iterable<BaseFunction> functions) throws EvalException {
+      Environment env, Iterable<BaseFunction> functions) {
     for (BaseFunction function : functions) {
-      env.update(function.getName(), function);
+      env.setup(function.getName(), function);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
index 94b1917..6140acb 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
@@ -22,21 +22,25 @@
 
   private final BaseFunction callback;
   private final FuncallExpression ast;
-  private final SkylarkEnvironment funcallEnv;
+  private final Environment funcallEnv;
 
-  public SkylarkCallbackFunction(BaseFunction callback, FuncallExpression ast,
-      SkylarkEnvironment funcallEnv) {
+  public SkylarkCallbackFunction(
+      BaseFunction callback, FuncallExpression ast, Environment funcallEnv) {
     this.callback = callback;
     this.ast = ast;
     this.funcallEnv = funcallEnv;
   }
 
   public Object call(ClassObject ctx, Object... arguments) throws EvalException {
-    try {
+    try (Mutability mutability = Mutability.create("callback %s", callback)) {
+      Environment env = Environment.builder(mutability)
+          .setSkylark()
+          .setEventHandler(funcallEnv.getEventHandler())
+          .setGlobals(funcallEnv.getGlobals())
+          .build();
       return callback.call(
-          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, funcallEnv);
-    } catch (InterruptedException | ClassCastException
-        | IllegalArgumentException e) {
+          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, env);
+    } catch (InterruptedException | ClassCastException | IllegalArgumentException e) {
       throw new EvalException(ast.getLocation(), e.getMessage());
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
deleted file mode 100644
index 0ff19f9..0000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
+++ /dev/null
@@ -1,205 +0,0 @@
-// Copyright 2014 Google Inc. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.syntax;
-
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.util.Fingerprint;
-
-import java.io.Serializable;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map.Entry;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * The environment for Skylark.
- */
-public class SkylarkEnvironment extends Environment implements Serializable {
-
-  /**
-   * This set contains the variable names of all the successful lookups from the global
-   * environment. This is necessary because if in a function definition something
-   * reads a global variable after which a local variable with the same name is assigned an
-   * Exception needs to be thrown.
-   */
-  private final Set<String> readGlobalVariables = new HashSet<>();
-
-  @Nullable private String fileContentHashCode;
-
-  /**
-   * Creates a Skylark Environment for function calling, from the global Environment of the
-   * caller Environment (which must be a Skylark Environment).
-   */
-  public static SkylarkEnvironment createEnvironmentForFunctionCalling(
-      Environment callerEnv, SkylarkEnvironment definitionEnv,
-      UserDefinedFunction function) throws EvalException {
-    if (callerEnv.stackTraceContains(function)) {
-      throw new EvalException(
-          function.getLocation(),
-          "Recursion was detected when calling '" + function.getName() + "' from '"
-          + Iterables.getLast(callerEnv.getStackTrace()).getName() + "'");
-    }
-    SkylarkEnvironment childEnv =
-        // Always use the caller Environment's EventHandler. We cannot assume that the
-        // definition Environment's EventHandler is still working properly.
-        new SkylarkEnvironment(
-            definitionEnv, callerEnv.getCopyOfStackTrace(), callerEnv.eventHandler);
-    if (callerEnv.isLoadingPhase()) {
-      childEnv.setLoadingPhase();
-    }
-
-    try {
-      for (String varname : callerEnv.propagatingVariables) {
-        childEnv.updateAndPropagate(varname, callerEnv.lookup(varname));
-      }
-    } catch (NoSuchVariableException e) {
-      // This should never happen.
-      throw new IllegalStateException(e);
-    }
-    return childEnv;
-  }
-
-  private SkylarkEnvironment(SkylarkEnvironment definitionEnv,
-      Deque<StackTraceElement> stackTrace, EventHandler eventHandler) {
-    super(definitionEnv.getGlobalEnvironment(), stackTrace);
-    this.eventHandler = Preconditions.checkNotNull(eventHandler,
-        "EventHandler cannot be null in an Environment which calls into Skylark");
-  }
-
-  /**
-   * Creates a global SkylarkEnvironment.
-   */
-  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode,
-      Deque<StackTraceElement> stackTrace) {
-    super(stackTrace);
-    this.eventHandler = eventHandler;
-    this.fileContentHashCode = astFileContentHashCode;
-  }
-
-  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode) {
-    this(eventHandler, astFileContentHashCode, new LinkedList<StackTraceElement>());
-  }
-
-  @VisibleForTesting
-  public SkylarkEnvironment(EventHandler eventHandler) {
-    this(eventHandler, null);
-  }
-
-  public SkylarkEnvironment(SkylarkEnvironment globalEnv) {
-    super(globalEnv);
-    this.eventHandler = globalEnv.eventHandler;
-  }
-
-  /**
-   * Clones this Skylark global environment.
-   */
-  public SkylarkEnvironment cloneEnv(EventHandler eventHandler) {
-    Preconditions.checkArgument(isGlobal());
-    SkylarkEnvironment newEnv =
-        new SkylarkEnvironment(eventHandler, this.fileContentHashCode, getCopyOfStackTrace());
-    for (Entry<String, Object> entry : env.entrySet()) {
-      newEnv.env.put(entry.getKey(), entry.getValue());
-    }
-    return newEnv;
-  }
-
-  /**
-   * Returns the global environment. Only works for Skylark environments. For the global Skylark
-   * environment this method returns this Environment.
-   */
-  public SkylarkEnvironment getGlobalEnvironment() {
-    // If there's a parent that's the global environment, otherwise this is.
-    return parent != null ? (SkylarkEnvironment) parent : this;
-  }
-
-  /**
-   * Returns true if this is a Skylark global environment.
-   */
-  @Override
-  public boolean isGlobal() {
-    return parent == null;
-  }
-
-  /**
-   * Returns true if varname has been read as a global variable.
-   */
-  public boolean hasBeenReadGlobalVariable(String varname) {
-    return readGlobalVariables.contains(varname);
-  }
-
-  @Override
-  public boolean isSkylark() {
-    return true;
-  }
-
-  /**
-   * @return the value from the environment whose name is "varname".
-   * @throws NoSuchVariableException if the variable is not defined in the environment.
-   */
-  @Override
-  public Object lookup(String varname) throws NoSuchVariableException {
-    Object value = env.get(varname);
-    if (value == null) {
-      if (parent != null && parent.hasVariable(varname)) {
-        readGlobalVariables.add(varname);
-        return parent.lookup(varname);
-      }
-      throw new NoSuchVariableException(varname);
-    }
-    return value;
-  }
-
-  /**
-   * Like <code>lookup(String)</code>, but instead of throwing an exception in
-   * the case where "varname" is not defined, "defaultValue" is returned instead.
-   */
-  @Override
-  public Object lookup(String varname, Object defaultValue) {
-    throw new UnsupportedOperationException();
-  }
-
-  /**
-   * Returns the class of the variable or null if the variable does not exist. This function
-   * works only in the local Environment, it doesn't check the global Environment.
-   */
-  public Class<?> getVariableType(String varname) {
-    Object variable = env.get(varname);
-    return variable != null ? EvalUtils.getSkylarkType(variable.getClass()) : null;
-  }
-
-  public void handleEvent(Event event) {
-    eventHandler.handle(event);
-  }
-
-  /**
-   * Returns a hash code calculated from the hash code of this Environment and the
-   * transitive closure of other Environments it loads.
-   */
-  public String getTransitiveFileContentHashCode() {
-    Fingerprint fingerprint = new Fingerprint();
-    fingerprint.addString(Preconditions.checkNotNull(fileContentHashCode));
-    // Calculate a new hash from the hash of the loaded Environments.
-    for (SkylarkEnvironment env : importedExtensions.values()) {
-      fingerprint.addString(env.getTransitiveFileContentHashCode());
-    }
-    return fingerprint.hexDigestAndReset();
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index bf3c832..6b31625 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -204,8 +204,13 @@
     } else if (param.defaultValue().isEmpty()) {
       return Runtime.NONE;
     } else {
-      try {
-        return EvaluationContext.SKYLARK_INITIALIZATION.evalExpression(param.defaultValue());
+      try (Mutability mutability = Mutability.create("initialization")) {
+        return Environment.builder(mutability)
+            .setSkylark()
+            .setGlobals(Environment.CONSTANTS_ONLY)
+            .setEventHandler(Environment.FAIL_FAST_HANDLER)
+            .build()
+            .eval(param.defaultValue());
       } catch (Exception e) {
         throw new RuntimeException(String.format(
             "Exception while processing @SkylarkSignature.Param %s, default value %s",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
index ca89b1a..2c99209 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 @@
   abstract void exec(Environment env) throws EvalException, InterruptedException;
 
   /**
-   * Checks the semantics of the Statement using the SkylarkEnvironment according to
-   * the rules of the Skylark language. The SkylarkEnvironment can be used e.g. to check
+   * Checks the semantics of the Statement using the Environment according to
+   * the rules of the Skylark language. The Environment can be used e.g. to check
    * variable type collision, read only variables, detecting recursion, existence of
    * built-in variables, functions, etc.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index f50e6ee..537f29f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location.LineAndColumn;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
@@ -26,15 +27,16 @@
 public class UserDefinedFunction extends BaseFunction {
 
   private final ImmutableList<Statement> statements;
-  private final SkylarkEnvironment definitionEnv;
+
+  // we close over the globals at the time of definition
+  private final Environment.Frame definitionGlobals;
 
   protected UserDefinedFunction(Identifier function,
       FunctionSignature.WithValues<Object, SkylarkType> signature,
-      ImmutableList<Statement> statements, SkylarkEnvironment definitionEnv) {
+      ImmutableList<Statement> statements, Environment.Frame definitionGlobals) {
     super(function.getName(), signature, function.getLocation());
-
     this.statements = statements;
-    this.definitionEnv = definitionEnv;
+    this.definitionGlobals = definitionGlobals;
   }
 
   public FunctionSignature.WithValues<Object, SkylarkType> getFunctionSignature() {
@@ -48,23 +50,36 @@
   @Override
   public Object call(Object[] arguments, FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    ImmutableList<String> names = signature.getSignature().getNames();
-
-    // Registering the functions's arguments as variables in the local Environment
-    int i = 0;
-    for (String name : names) {
-      env.update(name, arguments[i++]);
+    if (!env.mutability().isMutable()) {
+      throw new EvalException(getLocation(), "Trying to call in frozen environment");
+    }
+    if (env.getStackTrace().contains(this)) {
+      throw new EvalException(getLocation(),
+          String.format("Recursion was detected when calling '%s' from '%s'",
+              getName(), Iterables.getLast(env.getStackTrace()).getName()));
     }
 
     long startTimeProfiler = Profiler.nanoTimeMaybe();
     Statement lastStatement = null;
     try {
-      for (Statement stmt : statements) {
-        lastStatement = stmt;
-        stmt.exec(env);
+      env.enterScope(this, ast, definitionGlobals);
+      ImmutableList<String> names = signature.getSignature().getNames();
+
+      // Registering the functions's arguments as variables in the local Environment
+      int i = 0;
+      for (String name : names) {
+        env.update(name, arguments[i++]);
       }
-    } catch (ReturnStatement.ReturnException e) {
-      return e.getValue();
+
+      try {
+        for (Statement stmt : statements) {
+          lastStatement = stmt;
+          stmt.exec(env);
+        }
+      } catch (ReturnStatement.ReturnException e) {
+        return e.getValue();
+      }
+      return Runtime.NONE;
     } catch (EvalExceptionWithStackTrace ex) {
       // We need this block since the next "catch" must only catch EvalExceptions that don't have a
       // stack trace yet.
@@ -79,8 +94,8 @@
           startTimeProfiler,
           ProfilerTask.SKYLARK_USER_FN,
           getLocationPathAndLine() + "#" + getName());
+      env.exitScope();
     }
-    return Runtime.NONE;
   }
 
   /**
@@ -105,14 +120,4 @@
     }
     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 9b71f96..9d56271 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
@@ -15,7 +15,6 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.events.Location;
 
 import java.util.HashMap;
@@ -31,7 +30,7 @@
  * @see Statement#validate
  * @see Expression#validate
  */
-public class ValidationEnvironment {
+public final class ValidationEnvironment {
 
   private final ValidationEnvironment parent;
 
@@ -45,9 +44,6 @@
   // branches of if-else statements.
   private Stack<Set<String>> futureReadOnlyVariables = new Stack<>();
 
-  // Whether this validation environment is not modified therefore clonable or not.
-  private boolean clonable;
-
   /**
    * Tracks the number of nested for loops that contain the statement that is currently being
    * validated
@@ -55,38 +51,14 @@
   private int loopCount = 0;
 
   /**
-   * Create a ValidationEnvironment for a given global Environment
+   * Create a ValidationEnvironment for a given global Environment.
    */
   public ValidationEnvironment(Environment env) {
-    this(env.getVariableNames());
     Preconditions.checkArgument(env.isGlobal());
-  }
-
-  public ValidationEnvironment(Set<String> builtinVariables) {
     parent = null;
+    Set<String> builtinVariables = env.getVariableNames();
     variables.addAll(builtinVariables);
     readOnlyVariables.addAll(builtinVariables);
-    clonable = true;
-  }
-
-  private ValidationEnvironment(Set<String> builtinVariables, Set<String> readOnlyVariables) {
-    parent = null;
-    this.variables = new HashSet<>(builtinVariables);
-    this.readOnlyVariables = new HashSet<>(readOnlyVariables);
-    clonable = false;
-  }
-
-  // ValidationEnvironment for a new Environment()
-  private static ImmutableSet<String> globalTypes = ImmutableSet.of("False", "True", "None");
-
-  public ValidationEnvironment() {
-    this(globalTypes);
-  }
-
-  @Override
-  public ValidationEnvironment clone() {
-    Preconditions.checkState(clonable);
-    return new ValidationEnvironment(variables, readOnlyVariables);
   }
 
   /**
@@ -95,7 +67,6 @@
   public ValidationEnvironment(ValidationEnvironment parent) {
     // Don't copy readOnlyVariables: Variables may shadow global values.
     this.parent = parent;
-    this.clonable = false;
   }
 
   /**
@@ -120,7 +91,6 @@
     }
     variables.add(varname);
     variableLocations.put(varname, location);
-    clonable = false;
   }
 
   private void checkReadonly(String varname, Location location) throws EvalException {
@@ -133,7 +103,8 @@
    * Returns true if the symbol exists in the validation environment.
    */
   public boolean hasSymbolInEnvironment(String varname) {
-    return variables.contains(varname) || topLevel().variables.contains(varname);
+    return variables.contains(varname)
+        || (parent != null && topLevel().variables.contains(varname));
   }
 
   private ValidationEnvironment topLevel() {
@@ -147,7 +118,6 @@
    */
   public void startTemporarilyDisableReadonlyCheckSession() {
     futureReadOnlyVariables.add(new HashSet<String>());
-    clonable = false;
   }
 
   /**
@@ -159,7 +129,6 @@
     if (!futureReadOnlyVariables.isEmpty()) {
       futureReadOnlyVariables.peek().addAll(variables);
     }
-    clonable = false;
   }
 
   /**
@@ -167,7 +136,6 @@
    */
   public void finishTemporarilyDisableReadonlyCheckBranch() {
     readOnlyVariables.removeAll(futureReadOnlyVariables.peek());
-    clonable = false;
   }
 
   /**
diff --git a/src/test/java/com/google/devtools/build/lib/events/util/EventCollectionApparatus.java b/src/test/java/com/google/devtools/build/lib/events/util/EventCollectionApparatus.java
index aa8d8f8..c7f85d6 100644
--- a/src/test/java/com/google/devtools/build/lib/events/util/EventCollectionApparatus.java
+++ b/src/test/java/com/google/devtools/build/lib/events/util/EventCollectionApparatus.java
@@ -18,7 +18,7 @@
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.PrintingEventHandler;
 import com.google.devtools.build.lib.events.Reporter;
-import com.google.devtools.build.lib.syntax.EvaluationContext;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.testutil.MoreAsserts;
 import com.google.devtools.build.lib.util.io.OutErr;
 
@@ -67,9 +67,9 @@
    */
   public void setFailFast(boolean failFast) {
     if (failFast) {
-      reporter.addHandler(EvaluationContext.FAIL_FAST_HANDLER);
+      reporter.addHandler(Environment.FAIL_FAST_HANDLER);
     } else {
-      reporter.removeHandler(EvaluationContext.FAIL_FAST_HANDLER);
+      reporter.removeHandler(Environment.FAIL_FAST_HANDLER);
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
index 24ac455..2f29851 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
@@ -30,9 +30,9 @@
 import com.google.devtools.build.lib.packages.PackageFactory.LegacyGlobber;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
-import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.testutil.TestUtils;
@@ -134,7 +134,7 @@
     LegacyBuilder resultBuilder = factory.evaluateBuildFile(
         externalPkg, packageId, buildFileAST, buildFile,
         globber, ImmutableList.<Event>of(), ConstantRuleVisibility.PUBLIC, false, false,
-        new MakeEnvironment.Builder(), ImmutableMap.<PathFragment, SkylarkEnvironment>of(),
+        new MakeEnvironment.Builder(), ImmutableMap.<PathFragment, Environment>of(),
         ImmutableList.<Label>of());
     Package result = resultBuilder.build();
     Event.replayEventsOn(events.reporter(), result.getEvents());
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java b/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
index eff5bad..00e9062 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
@@ -22,11 +22,7 @@
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventCollector;
-import com.google.devtools.build.lib.events.EventKind;
-import com.google.devtools.build.lib.events.Reporter;
-import com.google.devtools.build.lib.events.util.EventCollectionApparatus;
 import com.google.devtools.build.lib.packages.CachingPackageLocator;
-import com.google.devtools.build.lib.testutil.MoreAsserts;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.vfs.Path;
 
@@ -37,13 +33,14 @@
 import java.io.IOException;
 import java.util.Arrays;
 
+/**
+ * Unit tests for BuildFileAST.
+ */
 @RunWith(JUnit4.class)
-public class BuildFileASTTest {
+public class BuildFileASTTest extends EvaluationTestCase {
 
   private Scratch scratch = new Scratch();
 
-  private EventCollectionApparatus events = new EventCollectionApparatus(EventKind.ALL_EVENTS);
-
   private class ScratchPathPackageLocator implements CachingPackageLocator {
     @Override
     public Path getBuildFileForPackage(PackageIdentifier packageName) {
@@ -53,13 +50,18 @@
 
   private CachingPackageLocator locator = new ScratchPathPackageLocator();
 
+  @Override
+  public Environment newEnvironment() throws Exception {
+    return newBuildEnvironment();
+  }
+
   /**
    * Parses the contents of the specified string (using DUMMY_PATH as the fake
    * filename) and returns the AST. Resets the error handler beforehand.
    */
   private BuildFileAST parseBuildFile(String... lines) throws IOException {
     Path file = scratch.file("/a/build/file/BUILD", lines);
-    return BuildFileAST.parseBuildFile(file, events.reporter(), locator, false);
+    return BuildFileAST.parseBuildFile(file, getEventHandler(), locator, false);
   }
 
   @Test
@@ -69,11 +71,9 @@
         "",
         "x = [1,2,'foo',4] + [1,2, \"%s%d\" % ('foo', 1)]");
 
-    Environment env = new Environment();
-    Reporter reporter = new Reporter();
-    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, reporter, null, false);
+    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, getEventHandler(), null, false);
 
-    assertTrue(buildfile.exec(env, reporter));
+    assertTrue(buildfile.exec(env, getEventHandler()));
 
     // Test final environment is correctly modified:
     //
@@ -91,15 +91,11 @@
         "",
         "z = x + y");
 
-    Environment env = new Environment();
-    Reporter reporter = new Reporter();
-    EventCollector collector = new EventCollector(EventKind.ALL_EVENTS);
-    reporter.addHandler(collector);
-    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, reporter, null, false);
+    setFailFast(false);
+    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, getEventHandler(), null, false);
 
-    assertFalse(buildfile.exec(env, reporter));
-    Event e = MoreAsserts.assertContainsEvent(collector,
-        "unsupported operand type(s) for +: 'int' and 'List'");
+    assertFalse(buildfile.exec(env, getEventHandler()));
+    Event e = assertContainsEvent("unsupported operand type(s) for +: 'int' and 'List'");
     assertEquals(4, e.getLocation().getStartLineAndColumn().getLine());
   }
 
@@ -114,13 +110,12 @@
 
   @Test
   public void testFailsIfNewlinesAreMissing() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
 
     BuildFileAST buildFileAST =
       parseBuildFile("foo() bar() something = baz() bar()");
 
-    Event event = events.collector().iterator().next();
-    assertEquals("syntax error at \'bar\': expected newline", event.getMessage());
+    Event event = assertContainsEvent("syntax error at \'bar\': expected newline");
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(1, event.getLocation().getStartLineAndColumn().getLine());
@@ -129,11 +124,10 @@
 
   @Test
   public void testImplicitStringConcatenationFails() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("a = 'foo' 'bar'");
-    Event event = events.collector().iterator().next();
-    assertEquals("Implicit string concatenation is forbidden, use the + operator",
-        event.getMessage());
+    Event event = assertContainsEvent(
+        "Implicit string concatenation is forbidden, use the + operator");
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(1, event.getLocation().getStartLineAndColumn().getLine());
@@ -143,11 +137,10 @@
 
   @Test
   public void testImplicitStringConcatenationAcrossLinesIsIllegal() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("a = 'foo'\n  'bar'");
 
-    Event event = events.collector().iterator().next();
-    assertEquals("indentation error", event.getMessage());
+    Event event = assertContainsEvent("indentation error");
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(2, event.getLocation().getStartLineAndColumn().getLine());
@@ -172,7 +165,7 @@
 
   @Test
   public void testWithSyntaxErrorsDoesNotPrintDollarError() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFile = parseBuildFile(
         "abi = cxx_abi + '-glibc-' + glibc_version + '-' + generic_cpu + '-' + sysname",
         "libs = [abi + opt_level + '/lib/libcc.a']",
@@ -182,14 +175,11 @@
         "           srcs = libs,",
         "           includes = [ abi + opt_level + '/include' ])");
     assertTrue(buildFile.containsErrors());
-    Event event = events.collector().iterator().next();
-    assertEquals("syntax error at '+': expected expression", event.getMessage());
-    Environment env = new Environment();
-    assertFalse(buildFile.exec(env, events.reporter()));
-    assertNull(findEvent(events.collector(), "$error$"));
+    assertContainsEvent("syntax error at '+': expected expression");
+    assertFalse(buildFile.exec(env, getEventHandler()));
+    assertNull(findEvent(getEventCollector(), "$error$"));
     // This message should not be printed anymore.
-    Event event2 = findEvent(events.collector(), "contains syntax error(s)");
-    assertNull(event2);
+    assertNull(findEvent(getEventCollector(), "contains syntax error(s)"));
   }
 
   @Test
@@ -202,7 +192,7 @@
         + "include(\"//foo/bar:BUILD\")\n"
         + "b = 4\n");
 
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, getEventHandler(),
                                                             locator, false);
 
     assertFalse(buildFileAST.containsErrors());
@@ -217,15 +207,14 @@
         "include(\"//foo/bar:defs\")\n"
         + "b = a + 1\n");
 
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, getEventHandler(),
                                                             locator, false);
 
     assertFalse(buildFileAST.containsErrors());
     assertThat(buildFileAST.getStatements()).hasSize(3);
 
-    Environment env = new Environment();
-    Reporter reporter = new Reporter();
-    assertFalse(buildFileAST.exec(env, reporter));
+    setFailFast(false);
+    assertFalse(buildFileAST.exec(env, getEventHandler()));
     assertEquals(2, env.lookup("b"));
   }
 
@@ -247,63 +236,53 @@
     assertFalse(buildFileAST.containsErrors());
     assertThat(buildFileAST.getStatements()).hasSize(8);
 
-    Environment env = new Environment();
-    Reporter reporter = new Reporter();
-    assertFalse(buildFileAST.exec(env, reporter));
+    setFailFast(false);
+    assertFalse(buildFileAST.exec(env, getEventHandler()));
     assertEquals(5, env.lookup("b"));
     assertEquals(7, env.lookup("c"));
   }
 
   @Test
   public void testFailInclude() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("include(\"//nonexistent\")");
     assertThat(buildFileAST.getStatements()).hasSize(1);
-    events.assertContainsEvent("Include of '//nonexistent' failed");
+    assertContainsEvent("Include of '//nonexistent' failed");
   }
 
 
-  private class EmptyPackageLocator implements CachingPackageLocator {
-    @Override
-    public Path getBuildFileForPackage(PackageIdentifier packageName) {
-      return null;
-    }
-  }
-
-  private CachingPackageLocator emptyLocator = new EmptyPackageLocator();
-
   @Test
   public void testFailInclude2() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     Path buildFile = scratch.file("/foo/bar/BUILD",
         "include(\"//nonexistent:foo\")\n");
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
-                                                            emptyLocator, false);
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(
+        buildFile, getEventHandler(), Environment.EMPTY_PACKAGE_LOCATOR, false);
     assertThat(buildFileAST.getStatements()).hasSize(1);
-    events.assertContainsEvent("Package 'nonexistent' not found");
+    assertContainsEvent("Package 'nonexistent' not found");
   }
 
   @Test
   public void testInvalidInclude() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("include(2)");
     assertThat(buildFileAST.getStatements()).isEmpty();
-    events.assertContainsEvent("syntax error at '2'");
+    assertContainsEvent("syntax error at '2'");
   }
 
   @Test
   public void testRecursiveInclude() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     Path buildFile = scratch.file("/foo/bar/BUILD",
         "include(\"//foo/bar:BUILD\")\n");
 
-    BuildFileAST.parseBuildFile(buildFile, events.reporter(), locator, false);
-    events.assertContainsEvent("Recursive inclusion");
+    BuildFileAST.parseBuildFile(buildFile, getEventHandler(), locator, false);
+    assertContainsEvent("Recursive inclusion");
   }
 
   @Test
   public void testParseErrorInclude() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
 
     scratch.file("/foo/bar/file",
         "a = 2 + % 3\n"); // parse error
@@ -311,14 +290,13 @@
     parseBuildFile("include(\"//foo/bar:file\")");
 
     // Check the location is properly reported
-    Event event = events.collector().iterator().next();
+    Event event = assertContainsEvent("syntax error at '%': expected expression");
     assertEquals("/foo/bar/file:1:9", event.getLocation().print());
-    assertEquals("syntax error at '%': expected expression", event.getMessage());
   }
 
   @Test
   public void testNonExistentIncludeReported() throws Exception {
-    events.setFailFast(false);
+    setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("include('//foo:bar')");
     assertThat(buildFileAST.getStatements()).hasSize(1);
   }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
index a324b13..0202124 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
@@ -31,8 +31,8 @@
 public class EnvironmentTest extends EvaluationTestCase {
 
   @Override
-  public EvaluationContext newEvaluationContext() {
-    return EvaluationContext.newBuildContext(getEventHandler());
+  public Environment newEnvironment() {
+    return newBuildEnvironment();
   }
 
   // Test the API directly
@@ -104,25 +104,41 @@
 
   @Test
   public void testGetVariableNames() throws Exception {
-    update("foo", "bar");
-    update("wiz", 3);
+    Environment outerEnv;
+    Environment innerEnv;
+    try (Mutability mut = Mutability.create("outer")) {
+      outerEnv = Environment.builder(mut)
+          .setGlobals(Environment.BUILD).build()
+          .update("foo", "bar")
+          .update("wiz", 3);
+    }
+    try (Mutability mut = Mutability.create("inner")) {
+      innerEnv = Environment.builder(mut)
+          .setGlobals(outerEnv.getGlobals()).build()
+          .update("foo", "bat")
+          .update("quux", 42);
+    }
 
-    Environment nestedEnv = new Environment(getEnvironment());
-    nestedEnv.update("foo", "bat");
-    nestedEnv.update("quux", 42);
-
-    assertEquals(Sets.newHashSet("True", "False", "None", "foo", "wiz"),
-        getEnvironment().getVariableNames());
-    assertEquals(Sets.newHashSet("True", "False", "None", "foo", "wiz", "quux"),
-        nestedEnv.getVariableNames());
+    assertEquals(Sets.newHashSet("foo", "wiz",
+            "False", "None", "True",
+            "-", "bool", "dict", "enumerate", "int", "len", "list",
+            "range", "repr", "select", "sorted", "str", "zip"),
+        outerEnv.getVariableNames());
+    assertEquals(Sets.newHashSet("foo", "wiz", "quux",
+            "False", "None", "True",
+            "-", "bool", "dict", "enumerate", "int", "len", "list",
+            "range", "repr", "select", "sorted", "str", "zip"),
+        innerEnv.getVariableNames());
   }
 
   @Test
   public void testToString() throws Exception {
     update("subject", new StringLiteral("Hello, 'world'.", '\''));
     update("from", new StringLiteral("Java", '"'));
-    assertEquals("Environment{False -> false, None -> None, True -> true, from -> \"Java\", "
-        + "subject -> 'Hello, \\'world\\'.', }", getEnvironment().toString());
+    assertThat(getEnvironment().toString())
+        .startsWith("Environment(lexicalFrame=null, "
+            + "globalFrame=Frame[test]{\"from\": \"Java\", \"subject\": 'Hello, \\'world\\'.'}=>"
+            + "(BUILD){");
   }
 
   @Test
@@ -134,4 +150,58 @@
       assertThat(e).hasMessage("update(value == null)");
     }
   }
+
+  @Test
+  public void testFrozen() throws Exception {
+    Environment env;
+    try (Mutability mutability = Mutability.create("testFrozen")) {
+      env = Environment.builder(mutability)
+          .setGlobals(Environment.BUILD).setEventHandler(Environment.FAIL_FAST_HANDLER).build();
+      env.update("x", 1);
+      assertEquals(env.lookup("x"), 1);
+      env.update("y", 2);
+      assertEquals(env.lookup("y"), 2);
+      assertEquals(env.lookup("x"), 1);
+      env.update("x", 3);
+      assertEquals(env.lookup("x"), 3);
+    }
+    try {
+      // This update to an existing variable should fail because the environment was frozen.
+      env.update("x", 4);
+      throw new Exception("failed to fail"); // not an AssertionError like fail()
+    } catch (AssertionError e) {
+      assertThat(e).hasMessage("Can't update x to 4 in frozen environment");
+    }
+    try {
+      // This update to a new variable should also fail because the environment was frozen.
+      env.update("newvar", 5);
+      throw new Exception("failed to fail"); // not an AssertionError like fail()
+    } catch (AssertionError e) {
+      assertThat(e).hasMessage("Can't update newvar to 5 in frozen environment");
+    }
+  }
+
+  @Test
+  public void testReadOnly() throws Exception {
+    Environment env = newSkylarkEnvironment()
+        .setup("special_var", 42)
+        .update("global_var", 666);
+
+    // We don't even get a runtime exception trying to modify these,
+    // because we get compile-time exceptions even before we reach runtime!
+    try {
+      env.eval("special_var = 41");
+      throw new AssertionError("failed to fail");
+    } catch (IllegalArgumentException e) {
+      assertThat(e).hasMessage("ERROR 1:1: Variable special_var is read only");
+    }
+
+    try {
+      env.eval("def foo(x): x += global_var; global_var = 36; return x", "foo(1)");
+      throw new AssertionError("failed to fail");
+    } catch (EvalExceptionWithStackTrace e) {
+      assertThat(e.getMessage()).contains("Variable 'global_var' is referenced before assignment. "
+          + "The variable is defined in the global scope.");
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
index cf23858..83a55be 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
@@ -482,9 +482,9 @@
   @Test
   public void testDictComprehensions_ToString() throws Exception {
     assertEquals("{x: x for x in [1, 2]}",
-        evaluationContext.parseExpression("{x : x for x in [1, 2]}").toString());
+        parseExpression("{x : x for x in [1, 2]}").toString());
     assertEquals("{x + 'a': x for x in [1, 2]}",
-        evaluationContext.parseExpression("{x + 'a' : x for x in [1, 2]}").toString());
+        parseExpression("{x + 'a' : x for x in [1, 2]}").toString());
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTestCase.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTestCase.java
index b2d661b..e26234a 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTestCase.java
@@ -35,48 +35,76 @@
  * Base class for test cases that use parsing and evaluation services.
  */
 public class EvaluationTestCase {
-  
+
   private EventCollectionApparatus eventCollectionApparatus;
   private PackageFactory factory;
   private TestMode testMode = TestMode.SKYLARK;
-  
-  protected EvaluationContext evaluationContext;
+  protected Environment env;
+  protected Mutability mutability = Mutability.create("test");
 
   public EvaluationTestCase()   {
     createNewInfrastructure();
   }
-  
+
   @Before
   public void setUp() throws Exception {
     createNewInfrastructure();
-    evaluationContext = newEvaluationContext();
+    env = newEnvironment();
   }
 
-  public EvaluationContext newEvaluationContext() throws Exception {
+  /**
+   * Creates a standard Environment for tests in the BUILD language.
+   * No PythonPreprocessing, mostly empty mutable Environment.
+   */
+  public Environment newBuildEnvironment() {
+    return Environment.builder(mutability)
+        .setGlobals(Environment.BUILD)
+        .setEventHandler(getEventHandler())
+        .setLoadingPhase()
+        .build();
+  }
+
+  /**
+   * Creates an Environment for Skylark with a mostly empty initial environment.
+   * For internal initialization or tests.
+   */
+  public Environment newSkylarkEnvironment() {
+    return Environment.builder(mutability)
+        .setSkylark()
+        .setGlobals(Environment.SKYLARK)
+        .setEventHandler(getEventHandler())
+        .build();
+  }
+
+  /**
+   * Creates a new Environment suitable for the test case. Subclasses may override it
+   * to fit their purpose and e.g. call newBuildEnvironment or newSkylarkEnvironment;
+   * or they may play with the testMode to run tests in either or both kinds of Environment.
+   * Note that all Environment-s may share the same Mutability, so don't close it.
+   * @return a fresh Environment.
+   */
+  public Environment newEnvironment() throws Exception {
     if (testMode == null) {
       throw new IllegalArgumentException(
           "TestMode is null. Please set a Testmode via setMode() or set the "
-          + "evaluatenContext manually by overriding newEvaluationContext()");
+          + "Environment manually by overriding newEnvironment()");
     }
-
-    return testMode.createContext(getEventHandler(), factory.getEnvironment());
+    return testMode.createEnvironment(getEventHandler(), null);
   }
 
   protected void createNewInfrastructure()  {
     eventCollectionApparatus = new EventCollectionApparatus(EventKind.ALL_EVENTS);
     factory = new PackageFactory(TestRuleClassProvider.getRuleClassProvider());
   }
-  
+
   /**
-   * Sets the specified {@code TestMode} and tries to create the appropriate {@code
-   * EvaluationContext}
-   * 
+   * Sets the specified {@code TestMode} and tries to create the appropriate {@code Environment}
    * @param testMode
    * @throws Exception
    */
   protected void setMode(TestMode testMode) throws Exception {
     this.testMode = testMode;
-    evaluationContext = newEvaluationContext();
+    env = newEnvironment();
   }
 
   protected void enableSkylarkMode() throws Exception {
@@ -96,32 +124,33 @@
   }
 
   public Environment getEnvironment() {
-    return evaluationContext.getEnvironment();
+    return env;
   }
-  
+
   public boolean isSkylark() {
-    return evaluationContext.isSkylark();
+    return env.isSkylark();
   }
 
   protected List<Statement> parseFile(String... input) {
-    return evaluationContext.parseFile(input);
+    return env.parseFile(input);
   }
 
+  /** Parses an Expression from string without a supporting file */
   Expression parseExpression(String... input) {
-    return evaluationContext.parseExpression(input);
+    return Parser.parseExpression(env.createLexer(input), getEventHandler());
   }
 
   public EvaluationTestCase update(String varname, Object value) throws Exception {
-    evaluationContext.update(varname, value);
+    env.update(varname, value);
     return this;
   }
 
   public Object lookup(String varname) throws Exception {
-    return evaluationContext.lookup(varname);
+    return env.lookup(varname);
   }
 
   public Object eval(String... input) throws Exception {
-    return evaluationContext.eval(input);
+    return env.eval(input);
   }
 
   public void checkEvalError(String msg, String... input) throws Exception {
@@ -189,15 +218,14 @@
 
   /**
    * Base class for test cases that run in specific modes (e.g. Build and/or Skylark)
-   *
-   */  
+   */
   protected abstract class ModalTestCase {
     private final SetupActions setup;
-    
-    protected ModalTestCase()   {
+
+    protected ModalTestCase() {
       setup = new SetupActions();
     }
-    
+
     /**
      * Allows the execution of several statements before each following test
      * @param statements The statement(s) to be executed
@@ -218,7 +246,7 @@
       setup.registerUpdate(name, value);
       return this;
     }
-    
+
     /**
      * Evaluates two parameters and compares their results.
      * @param statement The statement to be evaluated
@@ -255,7 +283,7 @@
       runTest(collectionTestable(statement, false, items));
       return this;
     }
-    
+
     /**
      * Evaluates the given statement and compares its result to the collection of expected objects
      * while considering their order
@@ -409,7 +437,7 @@
   }
 
   /**
-   * A simple decorator that allows the execution of setup actions before running 
+   * A simple decorator that allows the execution of setup actions before running
    * a {@code Testable}
    */
   class TestableDecorator implements Testable {
@@ -480,7 +508,7 @@
       }
     }
   }
-    
+
   /**
    * A class that executes each separate test in both modes (Build and Skylark)
    */
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java b/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
index e0c074a..5137b45 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
@@ -32,42 +32,44 @@
 import java.util.LinkedList;
 import java.util.List;
 
-
 /**
  *  Tests of parser behaviour.
  */
 @RunWith(JUnit4.class)
 public class ParserTest extends EvaluationTestCase {
 
-  EvaluationContext buildContext;
-  EvaluationContext buildContextWithPython;
+  Environment buildEnvironment;
 
   @Before
   @Override
   public void setUp() throws Exception {
     super.setUp();
-    buildContext = EvaluationContext.newBuildContext(getEventHandler());
-    buildContextWithPython = EvaluationContext.newBuildContext(
-        getEventHandler(), new Environment(), /*parsePython*/true);
+    buildEnvironment = newBuildEnvironment();
   }
 
   private Parser.ParseResult parseFileWithComments(String... input) {
-    return buildContext.parseFileWithComments(input);
-  }
-  @Override
-  protected List<Statement> parseFile(String... input) {
-    return buildContext.parseFile(input);
-  }
-  private List<Statement> parseFileWithPython(String... input) {
-    return buildContextWithPython.parseFile(input);
-  }
-  private List<Statement> parseFileForSkylark(String... input) {
-    return evaluationContext.parseFile(input);
-  }
-  private Statement parseStatement(String... input) {
-    return buildContext.parseStatement(input);
+    return buildEnvironment.parseFileWithComments(input);
   }
 
+  /** Parses build code (not Skylark) */
+  @Override
+  protected List<Statement> parseFile(String... input) {
+    return buildEnvironment.parseFile(input);
+  }
+
+  /** Parses a build code (not Skylark) with PythonProcessing enabled */
+  private List<Statement> parseFileWithPython(String... input) {
+    return Parser.parseFile(
+        buildEnvironment.createLexer(input),
+        getEventHandler(),
+        Environment.EMPTY_PACKAGE_LOCATOR,
+        /*parsePython=*/true).statements;
+  }
+
+  /** Parses Skylark code */
+  private List<Statement> parseFileForSkylark(String... input) {
+    return env.parseFile(input);
+  }
 
   private static String getText(String text, ASTNode node) {
     return text.substring(node.getLocation().getStartOffset(),
@@ -707,7 +709,7 @@
   @Test
   public void testParserContainsErrors() throws Exception {
     setFailFast(false);
-    parseStatement("+");
+    parseFile("+");
     assertContainsEvent("syntax error at '+'");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 16bcb80..a473f95 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -526,7 +526,7 @@
     new SkylarkTest()
         .update("mock", new Mock())
         .testIfExactError("Keyword arguments are not allowed when calling a java method"
-            + "\nwhile calling method 'string' on object of type Mock",
+            + "\nwhile calling method 'string' for type Mock",
             "mock.string(key=True)");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
index 86ad1fb..7558b6c 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
@@ -45,8 +45,8 @@
       SkylarkList.lazyList(new CustomIterable(), Integer.class);
 
   @Override
-  public EvaluationContext newEvaluationContext() throws Exception {
-    return super.newEvaluationContext().update("lazy", list);
+  public Environment newEnvironment() throws Exception {
+    return newSkylarkEnvironment().update("lazy", list);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
index c4bb7d8..b12f51b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
@@ -15,7 +15,6 @@
 
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.rules.SkylarkModules;
 
 import java.io.BufferedReader;
 import java.io.IOException;
@@ -42,8 +41,9 @@
 
   private final BufferedReader reader = new BufferedReader(
       new InputStreamReader(System.in, Charset.defaultCharset()));
-  private final EvaluationContext ev =
-      SkylarkModules.newEvaluationContext(PRINT_HANDLER);
+  private final Mutability mutability = Mutability.create("shell");
+  private final Environment env = Environment.builder(mutability)
+      .setSkylark().setGlobals(Environment.SKYLARK).setEventHandler(PRINT_HANDLER).build();
 
   public String read() {
     StringBuilder input = new StringBuilder();
@@ -70,7 +70,7 @@
     String input;
     while ((input = read()) != null) {
       try {
-        Object result = ev.eval(input);
+        Object result = env.eval(input);
         if (result != null) {
           System.out.println(Printer.repr(result));
         }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTests.java b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTests.java
index 57b341f..3ebdf8d 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTests.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTests.java
@@ -95,7 +95,7 @@
 
   @Test
   public void testBuiltinSymbolsAreReadOnly() throws Exception {
-    checkError("Variable rule is read only", "rule = 1");
+    checkError("Variable repr is read only", "repr = 1");
   }
 
   @Test
@@ -300,8 +300,8 @@
   @Test
   public void testFunctionReturnsFunction() {
     parse(
-        "def impl(ctx):",
-        "  return None",
+        "def rule(*, implementation): return None",
+        "def impl(ctx): return None",
         "",
         "skylark_rule = rule(implementation = impl)",
         "",
diff --git a/src/test/java/com/google/devtools/build/lib/testutil/TestMode.java b/src/test/java/com/google/devtools/build/lib/testutil/TestMode.java
index 5ec7ac2..ea887f9 100644
--- a/src/test/java/com/google/devtools/build/lib/testutil/TestMode.java
+++ b/src/test/java/com/google/devtools/build/lib/testutil/TestMode.java
@@ -14,31 +14,36 @@
 package com.google.devtools.build.lib.testutil;
 
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.rules.SkylarkModules;
 import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.syntax.EvaluationContext;
+import com.google.devtools.build.lib.syntax.Mutability;
 
 /**
  * Describes a particular testing mode by determining how the
- * appropriate {@code EvaluationContext} has to be created
+ * appropriate {@code Environment} has to be created
  */
 public abstract class TestMode {
-  public static final TestMode BUILD = new TestMode() {
-    @Override
-    public EvaluationContext createContext(EventHandler eventHandler, Environment environment)
-        throws Exception {
-      return EvaluationContext.newBuildContext(eventHandler, environment);
-    }
-  };
+  public static final TestMode BUILD =
+      new TestMode() {
+        @Override
+        public Environment createEnvironment(EventHandler eventHandler, Environment environment) {
+          return Environment.builder(Mutability.create("build test"))
+              .setGlobals(environment == null ? Environment.BUILD : environment.getGlobals())
+              .setEventHandler(eventHandler)
+              .build();
+        }
+      };
 
-  public static final TestMode SKYLARK = new TestMode() {
-    @Override
-    public EvaluationContext createContext(EventHandler eventHandler, Environment environment)
-        throws Exception {
-      return SkylarkModules.newEvaluationContext(eventHandler);
-    }
-  };
+  public static final TestMode SKYLARK =
+      new TestMode() {
+        @Override
+        public Environment createEnvironment(EventHandler eventHandler, Environment environment) {
+          return Environment.builder(Mutability.create("skylark test"))
+              .setSkylark()
+              .setGlobals(environment == null ? Environment.SKYLARK : environment.getGlobals())
+              .setEventHandler(eventHandler)
+              .build();
+        }
+      };
 
-  public abstract EvaluationContext createContext(
-      EventHandler eventHandler, Environment environment) throws Exception;
-}
\ No newline at end of file
+  public abstract Environment createEnvironment(EventHandler eventHandler, Environment environment);
+}
diff --git a/src/tools/generate_workspace/src/main/java/com/google/devtools/build/workspace/Resolver.java b/src/tools/generate_workspace/src/main/java/com/google/devtools/build/workspace/Resolver.java
index 2fd1ffe..0feebe2 100644
--- a/src/tools/generate_workspace/src/main/java/com/google/devtools/build/workspace/Resolver.java
+++ b/src/tools/generate_workspace/src/main/java/com/google/devtools/build/workspace/Resolver.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.packages.WorkspaceFactory;
 import com.google.devtools.build.lib.runtime.BlazeModule;
 import com.google.devtools.build.lib.runtime.BlazeRuntime;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.workspace.maven.DefaultModelResolver;
@@ -69,9 +70,9 @@
     resolver.addHeader(workspacePath.getPathString());
     ExternalPackage.Builder builder = new ExternalPackage.Builder(workspacePath,
         ruleClassProvider.getRunfilesPrefix());
-    WorkspaceFactory parser = new WorkspaceFactory(builder, ruleClassProvider);
-    try {
-      parser.parse(ParserInputSource.create(workspacePath));
+    try (Mutability mutability = Mutability.create("External Package %s", workspacePath)) {
+      new WorkspaceFactory(builder, ruleClassProvider, mutability)
+          .parse(ParserInputSource.create(workspacePath));
     } catch (IOException | InterruptedException e) {
       handler.handle(Event.error(Location.fromFile(workspacePath), e.getMessage()));
     }