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 57bc5e8..18d605d 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.Mutability;
+import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 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,6 +312,8 @@
 
   private final ImmutableMap<String, SkylarkType> skylarkAccessibleJavaClasses;
 
+  private final ValidationEnvironment skylarkValidationEnvironment;
+
   public ConfiguredRuleClassProvider(
       PathFragment preludePath,
       String runfilesPrefix,
@@ -337,6 +339,9 @@
     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() {
@@ -421,26 +426,22 @@
   }
 
   @Override
-  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();
+  public SkylarkEnvironment createSkylarkRuleClassEnvironment(
+      EventHandler eventHandler, String astFileContentHashCode) {
+    SkylarkEnvironment env = SkylarkModules.getNewEnvironment(eventHandler, astFileContentHashCode);
     for (Map.Entry<String, SkylarkType> entry : skylarkAccessibleJavaClasses.entrySet()) {
-      env.setup(entry.getKey(), entry.getValue().getType());
+      env.update(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 1b9110d..74b04a9 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,18 +149,6 @@
   }
 
   /**
-   * 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 49852ee..fda1a83 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,7 +24,6 @@
 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;
@@ -121,8 +120,7 @@
         attributes.put("actual", actual);
       }
       StoredEventHandler handler = new StoredEventHandler();
-      Rule rule = RuleFactory.createRule(
-          this, bindRuleClass, attributes, handler, null, location, null);
+      Rule rule = RuleFactory.createRule(this, bindRuleClass, attributes, handler, null, location);
       overwriteRule(rule);
       rule.setVisibility(ConstantRuleVisibility.PUBLIC);
     }
@@ -132,11 +130,11 @@
      * WORKSPACE files to overwrite "earlier" ones.
      */
     public Builder createAndAddRepositoryRule(RuleClass ruleClass, RuleClass bindRuleClass,
-        Map<String, Object> kwargs, FuncallExpression ast, Environment env)
+        Map<String, Object> kwargs, FuncallExpression ast)
         throws InvalidRuleException, NameConflictException, SyntaxException {
       StoredEventHandler eventHandler = new StoredEventHandler();
-      Rule tempRule = RuleFactory.createRule(
-          this, ruleClass, kwargs, eventHandler, ast, ast.getLocation(), env);
+      Rule tempRule = RuleFactory.createRule(this, ruleClass, kwargs, eventHandler, ast,
+          ast.getLocation());
       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 cde726b..ffea0bd 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,9 +46,10 @@
 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.Mutability;
+import com.google.devtools.build.lib.syntax.MethodLibrary;
 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;
@@ -325,6 +326,7 @@
 
   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;
@@ -365,6 +367,7 @@
     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());
@@ -399,6 +402,15 @@
 
 
   /**
+   * 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.
    */
@@ -619,8 +631,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,
@@ -898,7 +910,7 @@
                               Environment env)
       throws RuleFactory.InvalidRuleException, Package.NameConflictException {
     RuleClass ruleClass = getBuiltInRuleClass(ruleClassName, ruleFactory);
-    RuleFactory.createAndAddRule(context, ruleClass, kwargs, ast, env);
+    RuleFactory.createAndAddRule(context, ruleClass, kwargs, ast, env.getStackTrace());
   }
 
   private static RuleClass getBuiltInRuleClass(String ruleClassName, RuleFactory ruleFactory) {
@@ -946,6 +958,16 @@
     };
   }
 
+  /**
+   * 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.
    */
@@ -973,7 +995,7 @@
       Preprocessor.Result preprocessingResult,
       Iterable<Event> preprocessingEvents,
       List<Statement> preludeStatements,
-      Map<PathFragment, Environment> imports,
+      Map<PathFragment, SkylarkEnvironment> imports,
       ImmutableList<Label> skylarkFileDependencies,
       CachingPackageLocator locator,
       RuleVisibility defaultVisibility,
@@ -1042,12 +1064,12 @@
                 packageId,
                 buildFile,
                 preprocessingResult,
-                /*preprocessingEvents=*/localReporter.getEvents(),
-                /*preludeStatements=*/ImmutableList.<Statement>of(),
-                /*imports=*/ImmutableMap.<PathFragment, Environment>of(),
-                /*skylarkFileDependencies=*/ImmutableList.<Label>of(),
+                localReporter.getEvents(), /* preprocessingEvents */
+                ImmutableList.<Statement>of(), /* preludeStatements */
+                ImmutableMap.<PathFragment, SkylarkEnvironment>of(), /* imports */
+                ImmutableList.<Label>of(), /* skylarkFileDependencies */
                 locator,
-                /*defaultVisibility=*/ConstantRuleVisibility.PUBLIC,
+                ConstantRuleVisibility.PUBLIC, /* defaultVisibility */
                 globber)
             .build();
     Event.replayEventsOn(eventHandler, result.getEvents());
@@ -1088,13 +1110,8 @@
       return Preprocessor.Result.noPreprocessing(inputSource);
     }
     try {
-      return preprocessor.preprocess(
-          inputSource,
-          packageId.toString(),
-          globber,
-          eventHandler,
-          Environment.BUILD,
-          ruleFactory.getRuleClassNames());
+      return preprocessor.preprocess(inputSource, packageId.toString(), globber, eventHandler,
+          globalEnv, ruleFactory.getRuleClassNames());
     } catch (IOException e) {
       eventHandler.handle(Event.error(Location.fromFile(buildFile),
                      "preprocessing failed: " + e.getMessage()));
@@ -1195,20 +1212,19 @@
     // 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
-        .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));
+    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));
 
     for (String ruleClass : ruleFactory.getRuleClassNames()) {
       BaseFunction ruleFunction = newRuleFunction(ruleFactory, ruleClass);
-      pkgEnv.setup(ruleClass, ruleFunction);
+      pkgEnv.update(ruleClass, ruleFunction);
     }
 
     for (EnvironmentExtension extension : environmentExtensions) {
@@ -1239,65 +1255,62 @@
       PackageIdentifier packageId, BuildFileAST buildFileAST, Path buildFilePath, Globber globber,
       Iterable<Event> pastEvents, RuleVisibility defaultVisibility, boolean containsError,
       boolean containsTransientError, MakeEnvironment.Builder pkgMakeEnv,
-      Map<PathFragment, Environment> imports,
+      Map<PathFragment, SkylarkEnvironment> 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();
 
-    try (Mutability mutability = Mutability.create("package %s", packageId)) {
-      Environment pkgEnv = Environment.builder(mutability)
-          .setGlobals(Environment.BUILD)
-          .setEventHandler(eventHandler)
-          .setImportedExtensions(imports)
-          .setLoadingPhase()
-          .build();
+    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());
 
-      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());
+    Event.replayEventsOn(eventHandler, pastEvents);
 
-      Event.replayEventsOn(eventHandler, pastEvents);
+    // Stuff that closes over the package context:`
+    PackageContext context = new PackageContext(pkgBuilder, globber, eventHandler);
+    buildPkgEnv(pkgEnv, context, ruleFactory);
 
-      // 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 (containsError) {
+      pkgBuilder.setContainsErrors();
+    }
 
-      if (containsError) {
-        pkgBuilder.setContainsErrors();
-      }
+    if (containsTransientError) {
+      pkgBuilder.setContainsTemporaryErrors();
+    }
 
-      if (containsTransientError) {
-        pkgBuilder.setContainsTemporaryErrors();
-      }
+    if (!validatePackageIdentifier(packageId, buildFileAST.getLocation(), eventHandler)) {
+      pkgBuilder.setContainsErrors();
+    }
 
-      if (!validatePackageIdentifier(packageId, buildFileAST.getLocation(), eventHandler)) {
-        pkgBuilder.setContainsErrors();
-      }
+    pkgEnv.setImportedExtensions(imports);
+    pkgEnv.updateAndPropagate(PKG_CONTEXT, context);
+    pkgEnv.updateAndPropagate(Runtime.PKG_NAME, packageId.toString());
 
-      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());
@@ -1316,36 +1329,29 @@
       // of all globs.
       return;
     }
-    try (Mutability mutability = Mutability.create("prefetchGlobs for %s", packageId)) {
-      Environment pkgEnv = Environment.builder(mutability)
-          .setGlobals(Environment.BUILD)
-          .setEventHandler(NullEventHandler.INSTANCE)
-          .setLoadingPhase()
-          .build();
+    // Important: Environment should be unreachable by the end of this method!
+    Environment pkgEnv = new Environment();
+    pkgEnv.setLoadingPhase();
 
-      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);
-      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);
-    }
+    // 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);
   }
 
 
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 c44776a..a479ca9 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 globals the global bindings for the Python environment.
+   * @param globalEnv the GLOBALS 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.Frame globals,
+      Environment globalEnv,
       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 7906a2b..59fcbb5 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 Environment ruleDefinitionEnvironment = null;
+    private SkylarkEnvironment 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(Environment env) {
+    public Builder setRuleDefinitionEnvironment(SkylarkEnvironment 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 Environment ruleDefinitionEnvironment;
+  @Nullable private final SkylarkEnvironment 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 Environment ruleDefinitionEnvironment,
+      @Nullable SkylarkEnvironment 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 Environment ruleDefinitionEnvironment,
+      @Nullable SkylarkEnvironment ruleDefinitionEnvironment,
       Set<Class<?>> allowedConfigurationFragments,
       Set<String> allowedConfigurationFragmentNames,
       @Nullable FragmentClassNameResolver fragmentNameResolver,
@@ -1725,7 +1725,7 @@
   /**
    * Returns this RuleClass's rule definition environment.
    */
-  @Nullable public Environment getRuleDefinitionEnvironment() {
+  @Nullable public SkylarkEnvironment 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 b3ca83f..958d88a 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,14 +15,12 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.syntax.Mutability;
+import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
+import com.google.devtools.build.lib.syntax.ValidationEnvironment;
 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.
  */
@@ -49,19 +47,17 @@
   Map<String, Class<? extends AspectFactory<?, ?, ?>>> getAspectFactoryMap();
 
   /**
-   * 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.
+   * Returns a new Skylark Environment instance for rule creation. Implementations need to be
+   * thread safe.
    */
-  Environment createSkylarkRuleClassEnvironment(
-      Mutability mutability,
-      EventHandler eventHandler,
-      @Nullable String astFileContentHashCode,
-      @Nullable Map<PathFragment, Environment> importMap);
+  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();
 
   /**
    * 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 2eb94b1..33f9d49 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,24 +15,20 @@
 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.UserDefinedFunction;
-import com.google.devtools.build.lib.util.Pair;
+import com.google.devtools.build.lib.syntax.StackTraceElement;
 
 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
@@ -82,7 +78,7 @@
       EventHandler eventHandler,
       FuncallExpression ast,
       Location location,
-      @Nullable Environment env)
+      ImmutableList<StackTraceElement> stackTrace)
       throws InvalidRuleException {
     Preconditions.checkNotNull(ruleClass);
     String ruleClassName = ruleClass.getName();
@@ -112,19 +108,31 @@
     }
 
     try {
-      return ruleClass.createRuleWithLabel(
-          pkgBuilder,
-          label,
-          addGeneratorAttributesForMacros(attributeValues, env),
-          eventHandler,
-          ast,
+      Rule rule = ruleClass.createRuleWithLabel(pkgBuilder, label,
+          addGeneratorAttributesForMacros(attributeValues, stackTrace), 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
@@ -137,40 +145,34 @@
    *        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 InvalidRuleException, NameConflictException
+   * @throws NameConflictException
    */
-  static Rule createAndAddRule(
-      Package.Builder pkgBuilder,
-      RuleClass ruleClass,
-      Map<String, Object> attributeValues,
-      EventHandler eventHandler,
-      FuncallExpression ast,
-      Location location,
-      Environment env)
+  static Rule createAndAddRule(Package.Builder pkgBuilder,
+                  RuleClass ruleClass,
+                  Map<String, Object> attributeValues,
+                  EventHandler eventHandler,
+                  FuncallExpression ast,
+                  Location location,
+                  ImmutableList<StackTraceElement> stackTrace)
       throws InvalidRuleException, NameConflictException {
     Rule rule = createRule(
-        pkgBuilder, ruleClass, attributeValues, eventHandler, ast, location, env);
+        pkgBuilder, ruleClass, attributeValues, eventHandler, ast, location, stackTrace);
     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,
-      Environment env)
+      ImmutableList<StackTraceElement> stackTrace)
       throws InvalidRuleException, NameConflictException {
-    return createAndAddRule(
-        context.pkgBuilder,
-        ruleClass,
-        attributeValues,
-        context.eventHandler,
-        ast,
-        ast.getLocation(),
-        env);
+    return createAndAddRule(context.pkgBuilder, ruleClass, attributeValues, context.eventHandler,
+        ast, ast.getLocation(), stackTrace);
   }
 
   /**
@@ -190,28 +192,22 @@
    * <p>Otherwise, it returns the given attributes without any changes.
    */
   private static Map<String, Object> addGeneratorAttributesForMacros(
-      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)) {
+      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.
       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", topCall.first.getName());
-    builder.put("generator_location", topCall.second.toString());
+    builder.put("generator_function", generator.getName());
+    builder.put("generator_location", Location.printPathAndLine(generator.getLocation()));
 
     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 abbbdf8..054865f 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.Mutability;
+import com.google.devtools.build.lib.syntax.MethodLibrary;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 
 import java.io.File;
@@ -44,30 +44,14 @@
   private final Builder builder;
   private final Environment environment;
 
-  /**
-   * @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);
+  public WorkspaceFactory(Builder builder, RuleClassProvider ruleClassProvider) {
+    this(builder, ruleClassProvider, 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,
-      Mutability mutability,
-      @Nullable String installDir) {
+      Builder builder, RuleClassProvider ruleClassProvider, @Nullable String installDir) {
     this.builder = builder;
-    this.environment = createWorkspaceEnv(builder, ruleClassProvider, mutability, installDir);
+    this.environment = createWorkspaceEnv(builder, ruleClassProvider, installDir);
   }
 
   public void parse(ParserInputSource source)
@@ -138,13 +122,13 @@
   private static BuiltinFunction newRuleFunction(
       final RuleFactory ruleFactory, final Builder builder, final String ruleClassName) {
     return new BuiltinFunction(ruleClassName,
-        FunctionSignature.KWARGS, BuiltinFunction.USE_AST_ENV) {
-      public Object invoke(Map<String, Object> kwargs, FuncallExpression ast, Environment env)
+        FunctionSignature.KWARGS, BuiltinFunction.USE_AST) {
+      public Object invoke(Map<String, Object> kwargs, FuncallExpression ast)
           throws EvalException {
         try {
           RuleClass ruleClass = ruleFactory.getRuleClass(ruleClassName);
           RuleClass bindRuleClass = ruleFactory.getRuleClass("bind");
-          builder.createAndAddRepositoryRule(ruleClass, bindRuleClass, kwargs, ast, env);
+          builder.createAndAddRepositoryRule(ruleClass, bindRuleClass, kwargs, ast);
         } catch (RuleFactory.InvalidRuleException | Package.NameConflictException |
             Label.SyntaxException e) {
           throw new EvalException(ast.getLocation(), e.getMessage());
@@ -155,30 +139,25 @@
   }
 
   private Environment createWorkspaceEnv(
-      Builder builder,
-      RuleClassProvider ruleClassProvider,
-      Mutability mutability,
-      String installDir) {
-    Environment workspaceEnv = Environment.builder(mutability)
-        .setGlobals(Environment.BUILD)
-        .setLoadingPhase()
-        .build();
+      Builder builder, RuleClassProvider ruleClassProvider, String installDir) {
+    Environment workspaceEnv = new Environment();
+    MethodLibrary.setupMethodEnvironment(workspaceEnv);
+    workspaceEnv.setLoadingPhase();
+
     RuleFactory ruleFactory = new RuleFactory(ruleClassProvider);
-    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);
+    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;
   }
 }
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 fbe9267..1fb8782 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));
       }
 
-      Environment env = rule.getRuleClassObject().getRuleDefinitionEnvironment();
+      SkylarkEnvironment 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 e6d8f3c..75afd45 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,6 +31,7 @@
 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;
@@ -104,7 +105,7 @@
   }
 
   private static Attribute.Builder<?> createAttribute(
-      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, Environment env)
+      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, SkylarkEnvironment 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).
@@ -184,7 +185,7 @@
       Map<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
       throws EvalException {
     try {
-      return createAttribute(type, kwargs, ast, env);
+      return createAttribute(type, kwargs, ast, (SkylarkEnvironment) 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 3054420..c52c58c 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,8 +19,11 @@
 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.Mutability;
+import com.google.devtools.build.lib.syntax.EvaluationContext;
+import com.google.devtools.build.lib.syntax.MethodLibrary;
 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.
@@ -41,43 +44,41 @@
       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();
-    }
-  }
-
-
   /**
-   * 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.
+   * Returns a new SkylarkEnvironment with the elements of the Skylark modules.
    */
-  public static Environment getNewEnvironment(
-      EventHandler eventHandler, String astFileContentHashCode, Mutability mutability) {
-    return Environment.builder(mutability)
-        .setSkylark()
-        .setGlobals(GLOBALS)
-        .setEventHandler(eventHandler)
-        .setFileContentHashCode(astFileContentHashCode)
-        .build();
+  public static SkylarkEnvironment getNewEnvironment(
+      EventHandler eventHandler, String astFileContentHashCode) {
+    SkylarkEnvironment env = new SkylarkEnvironment(eventHandler, astFileContentHashCode);
+    setupEnvironment(env);
+    return env;
   }
 
   @VisibleForTesting
-  public static Environment getNewEnvironment(
-      EventHandler eventHandler, Mutability mutability) {
-    return getNewEnvironment(eventHandler, null, mutability);
+  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());
   }
 }
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 c9e2cee..e254034 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,6 +70,7 @@
 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;
@@ -271,7 +272,7 @@
           if (implicitOutputs instanceof BaseFunction) {
             BaseFunction func = (BaseFunction) implicitOutputs;
             final SkylarkCallbackFunction callback =
-                new SkylarkCallbackFunction(func, ast, funcallEnv);
+                new SkylarkCallbackFunction(func, ast, (SkylarkEnvironment) funcallEnv);
             builder.setImplicitOutputsFunction(
                 new SkylarkImplicitOutputsFunctionWithCallback(callback, ast.getLocation()));
           } else {
@@ -292,7 +293,8 @@
         }
 
         builder.setConfiguredTargetFunction(implementation);
-        builder.setRuleDefinitionEnvironment(funcallEnv);
+        builder.setRuleDefinitionEnvironment(
+            ((SkylarkEnvironment) funcallEnv).getGlobalEnvironment());
         return new RuleFunction(builder, type);
         }
       };
@@ -330,7 +332,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);
+            pkgContext, ruleClass, (Map<String, Object>) args[0], ast, env.getStackTrace());
       } catch (InvalidRuleException | NameConflictException | NoSuchVariableException e) {
         throw new EvalException(ast.getLocation(), e.getMessage());
       }
@@ -350,8 +352,8 @@
     }
   }
 
-  public static void exportRuleFunctions(Environment env, PathFragment skylarkFile) {
-    for (String name : env.getGlobals().getDirectVariableNames()) {
+  public static void exportRuleFunctions(SkylarkEnvironment env, PathFragment skylarkFile) {
+    for (String name : env.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 405abe4..409b408 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,12 +34,11 @@
 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;
 
@@ -55,19 +54,13 @@
   public static ConfiguredTarget buildRule(RuleContext ruleContext,
       BaseFunction ruleImplementation) {
     String expectFailure = ruleContext.attributes().get("expect_failure", Type.STRING);
-    try (Mutability mutability = Mutability.create("configured target")) {
+    try {
       SkylarkRuleContext skylarkRuleContext = new SkylarkRuleContext(ruleContext);
-      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);
+      SkylarkEnvironment env = ruleContext.getRule().getRuleClassObject()
+          .getRuleDefinitionEnvironment().cloneEnv(
+              ruleContext.getAnalysisEnvironment().getEventHandler());
+      Object target = ruleImplementation.call(ImmutableList.<Object>of(skylarkRuleContext),
+          ImmutableMap.<String, Object>of(), 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 fe44617..2b33904 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,9 +20,6 @@
 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;
@@ -116,33 +113,26 @@
     if (lookupResult == null) {
       return null;
     }
+
+    BuildFileAST ast = null;
     if (!lookupResult.lookupSuccessful()) {
       return ASTFileLookupValue.noFile();
-    }
-    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) {
+    } 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) {
         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 ac3a6e9..9e3b8d5 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,6 +49,7 @@
 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;
@@ -552,8 +553,7 @@
     if (eventHandler.hasErrors()) {
       importResult =
           new SkylarkImportResult(
-              ImmutableMap.<PathFragment, com.google.devtools.build.lib.syntax.Environment>of(),
-              ImmutableList.<Label>of());
+              ImmutableMap.<PathFragment, SkylarkEnvironment>of(), ImmutableList.<Label>of());
       includeRepositoriesFetched = true;
     } else {
       importResult =
@@ -581,7 +581,7 @@
       Environment env)
       throws PackageFunctionException {
     ImmutableMap<Location, PathFragment> imports = buildFileAST.getImports();
-    Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap = new HashMap<>();
+    Map<PathFragment, SkylarkEnvironment> importMap = new HashMap<>();
     ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
     try {
       for (Map.Entry<Location, PathFragment> entry : imports.entrySet()) {
@@ -884,11 +884,9 @@
 
   /** A simple value class to store the result of the Skylark imports.*/
   private static final class SkylarkImportResult {
-    private final Map<PathFragment, com.google.devtools.build.lib.syntax.Environment> importMap;
+    private final Map<PathFragment, SkylarkEnvironment> importMap;
     private final ImmutableList<Label> fileDependencies;
-    private SkylarkImportResult(
-        Map<PathFragment,
-        com.google.devtools.build.lib.syntax.Environment> importMap,
+    private SkylarkImportResult(Map<PathFragment, SkylarkEnvironment> 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 b3eb957..0bd16ae 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.Mutability;
+import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 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, com.google.devtools.build.lib.syntax.Environment> importMap = new HashMap<>();
+    Map<PathFragment, SkylarkEnvironment> 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,11 +114,10 @@
           file));
     }
 
-    // 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);
-
+    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.
     return new SkylarkImportLookupValue(
         extensionEnv, new SkylarkFileDependency(label, fileDependencies.build()));
   }
@@ -165,34 +164,29 @@
   }
 
   /**
-   * Creates the Environment to be imported.
-   * After it's returned, the Environment must not be modified.
+   * Creates the SkylarkEnvironment to be imported. After it's returned, the Environment
+   * must not be modified.
    */
-  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)
+  private SkylarkEnvironment createEnv(BuildFileAST ast, PathFragment file,
+      Map<PathFragment, SkylarkEnvironment> 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.
-    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);
+    SkylarkEnvironment extensionEnv = ruleClassProvider
+        .createSkylarkRuleClassEnvironment(eventHandler, ast.getContentHashCode());
+    extensionEnv.update("native", packageFactory.getNativeModule());
+    extensionEnv.setImportedExtensions(importMap);
+    ast.exec(extensionEnv, eventHandler);
+    SkylarkRuleClassFunctions.exportRuleFunctions(extensionEnv, file);
 
-      Event.replayEventsOn(env.getListener(), eventHandler.getEvents());
-      if (eventHandler.hasErrors()) {
-        throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.errors(file));
-      }
-      return extensionEnv;
+    Event.replayEventsOn(env.getListener(), eventHandler.getEvents());
+    if (eventHandler.hasErrors()) {
+      throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.errors(file));
     }
+    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 86db054..020a426 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 Environment importedEnvironment;
+  private final SkylarkEnvironment 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(
-      Environment importedEnvironment, SkylarkFileDependency dependency) {
+      SkylarkEnvironment importedEnvironment, SkylarkFileDependency dependency) {
     this.importedEnvironment = Preconditions.checkNotNull(importedEnvironment);
     this.dependency = Preconditions.checkNotNull(dependency);
   }
 
   /**
-   * Returns the imported Environment.
+   * Returns the imported SkylarkEnvironment.
    */
-  public Environment getImportedEnvironment() {
+  public SkylarkEnvironment 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 ce45ca2..30f0c6a 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,7 +20,6 @@
 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;
@@ -63,25 +62,18 @@
     Path repoWorkspace = workspaceRoot.getRoot().getRelative(workspaceRoot.getRelativePath());
     Builder builder = new Builder(repoWorkspace,
         packageFactory.getRuleClassProvider().getRunfilesPrefix());
-    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());
-      }
+    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 {
-        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 d28d4d3..8d5f48f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -407,29 +407,35 @@
    * @param args a list of all positional arguments (as in *starArg)
    * @param kwargs a map for key arguments (as in **kwArgs)
    * @param ast the expression for this function's definition
-   * @param env the Environment in the function is called
+   * @param parentEnv the lexical Environment for the function call
    * @return the value resulting from evaluating the function with the given arguments
    * @throws construction of EvalException-s containing source information.
    */
   public Object call(List<Object> args,
       @Nullable Map<String, Object> kwargs,
       @Nullable FuncallExpression ast,
-      Environment env)
+      @Nullable Environment parentEnv)
       throws EvalException, InterruptedException {
-    Preconditions.checkState(isConfigured(), "Function %s was not configured", getName());
-
-    // 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);
-
+    Environment env = getOrCreateChildEnvironment(parentEnv);
+    env.addToStackTrace(new StackTraceElement(this, kwargs));
     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);
+      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();
     }
   }
 
@@ -550,7 +556,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 aa9b151..a7547de 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
@@ -122,11 +122,9 @@
   @Override
   @Nullable
   public Object call(Object[] args,
-      FuncallExpression ast, Environment env)
+      @Nullable FuncallExpression ast, @Nullable Environment env)
       throws EvalException, InterruptedException {
-    Preconditions.checkNotNull(ast);
-    Preconditions.checkNotNull(env);
-    Location loc = ast.getLocation();
+    final Location loc = (ast == null) ? location : ast.getLocation();
 
     // Add extra arguments, if needed
     if (extraArgs != null) {
@@ -152,7 +150,6 @@
     long startTime = Profiler.nanoTimeMaybe();
     // Last but not least, actually make an inner call to the function with the resolved arguments.
     try {
-      env.enterScope(this, ast, env.getGlobals());
       return invokeMethod.invoke(this, args);
     } catch (InvocationTargetException x) {
       Throwable e = x.getCause();
@@ -196,7 +193,6 @@
           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 25be3fd..ed30671 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -15,26 +15,18 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.packages.CachingPackageLocator;
-import com.google.devtools.build.lib.syntax.Mutability.Freezable;
-import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
-import com.google.devtools.build.lib.util.Fingerprint;
-import com.google.devtools.build.lib.util.Pair;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
-import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -42,280 +34,54 @@
 import javax.annotation.Nullable;
 
 /**
- * An Environment is the main entry point to evaluating code in the BUILD language or Skylark.
- * It embodies all the state that is required to evaluate such code,
- * except for the current instruction pointer, which is an {@link ASTNode}
- * whose {@link Statement#exec exec} or {@link Expression#eval eval} method is invoked with
- * this Environment, in a straightforward direct-style AST-walking interpreter.
- * {@link Continuation}-s are explicitly represented, but only partly, with another part being
- * implicit in a series of try-catch statements, to maintain the direct style. One notable trick
- * is how a {@link UserDefinedFunction} implements returning values as the function catching a
- * {@link ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the body.
- *
- * <p>Every Environment has a {@link Mutability} field, and must be used within a function that
- * creates and closes this {@link Mutability} with the try-with-resource pattern.
- * This {@link Mutability} is also used when initializing mutable objects within that Environment;
- * when closed at the end of the computation freezes the Environment and all those objects that
- * then become forever immutable. The pattern enforces the discipline that there should be no
- * dangling mutable Environment, or concurrency between interacting Environment-s.
- * It is also an error to try to mutate an Environment and its objects from another Environment,
- * before the {@link Mutability} is closed.
- *
- * <p>One creates an Environment using the {@link #builder} function, then
- * populates it with {@link #setup}, {@link #setupDynamic} and sometimes {@link #setupOverride},
- * before to evaluate code in it with {@link #eval}, or with {@link BuildFileAST#exec}
- * (where the AST was obtained by passing a {@link ValidationEnvironment} constructed from the
- * Environment to {@link BuildFileAST#parseBuildFile} or {@link BuildFileAST#parseSkylarkFile}).
- * When the computation is over, the frozen Environment can still be queried with {@link #lookup}.
- *
- * <p>Final fields of an Environment represent its dynamic state, i.e. state that remains the same
- * throughout a given evaluation context, and don't change with source code location,
- * while mutable fields embody its static state, that change with source code location.
- * The seeming paradox is that the words "dynamic" and "static" refer to the point of view
- * of the source code, and here we have a dual point of view.
+ * The BUILD environment.
  */
-public final class Environment implements Freezable, Serializable {
+public class Environment {
+
+  protected final Map<String, Object> env = new HashMap<>();
 
   /**
-   * A Frame is a Map of bindings, plus a {@link Mutability} and a parent Frame
-   * from which to inherit bindings.
-   *
-   * <p>A Frame contains bindings mapping variable name to variable value in a given scope.
-   * It may also inherit bindings from a parent Frame corresponding to a parent scope,
-   * which in turn may inherit bindings from its own parent, etc., transitively.
-   * Bindings may shadow bindings from the parent. In Skylark, you may only mutate
-   * bindings from the current Frame, which always got its {@link Mutability} with the
-   * current {@link Environment}; but future extensions may make it more like Python
-   * and allow mutation of bindings in outer Frame-s (or then again may not).
-   *
-   * <p>A Frame inherits the {@link Mutability} from the {@link Environment} in which it was
-   * originally created. When that {@link Environment} is finalized and its {@link Mutability}
-   * is closed, it becomes immutable, including the Frame, which can be shared in other
-   * {@link Environment}-s. Indeed, a {@link UserDefinedFunction} will close over the global
-   * Frame of its definition {@link Environment}, which will thus be reused (immutably)
-   * in all any {@link Environment} in which this function is called, so it's important to
-   * preserve the {@link Mutability} to make sure no Frame is modified after it's been finalized.
+   * The parent environment. For Skylark it's the global environment,
+   * used for global read only variable lookup.
    */
-  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();
-    }
-  }
+  protected final Environment parent;
 
   /**
-   * A Continuation contains data saved during a function call and restored when the function exits.
+   * Map from a Skylark extension to an environment, which contains all symbols defined in the
+   * extension.
    */
-  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;
-    }
-  }
+  protected Map<PathFragment, SkylarkEnvironment> importedExtensions;
 
   /**
-   * 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.
+   * A set of variables propagating through function calling. It's only used to call
+   * native rules from Skylark build extensions.
    */
-  private Frame lexicalFrame;
+  protected Set<String> propagatingVariables = new HashSet<>();
 
-  /**
-   * 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;
+  // Only used in the global environment.
+  // TODO(bazel-team): make this a final field part of constructor.
+  private boolean isLoadingPhase = false;
 
   /**
    * 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.
    */
-  private boolean isLoadingPhase() {
+  boolean isLoadingPhase() {
     return isLoadingPhase;
   }
 
   /**
-   * Checks that the current Environment is in the loading phase.
+   * 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.
    * @param symbol name of the function being only authorized thus.
    */
   public void checkLoadingPhase(String symbol, Location loc) throws EvalException {
@@ -325,378 +91,168 @@
   }
 
   /**
-   * Is this a global Environment?
-   * @return true if the current code is being executed at the top-level,
-   * as opposed to inside the body of a function.
+   * Is this a global environment?
+   * @return true if this is a global (top-level) environment
+   * as opposed to inside the body of a function
    */
-  boolean isGlobal() {
-    return lexicalFrame == null;
+  public boolean isGlobal() {
+    return true;
   }
 
   /**
-   * Is the current code Skylark?
-   * @return true if Skylark was enabled when this code was read.
+   * An EventHandler for errors and warnings. This is not used in the BUILD language,
+   * however it might be used in Skylark code called from the BUILD language.
    */
-  // TODO(bazel-team): Delete this function.
-  // This function is currently used in various functions that change their behavior with respect to
-  // lists depending on the Skylark-ness of the code; lists should be unified between the two modes.
-  boolean isSkylark() {
-    return isSkylark;
+  @Nullable protected EventHandler eventHandler;
+
+  /**
+   * 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>());
   }
 
   /**
-   * Is the caller of the current function executing Skylark code?
-   * @return true if this is skylark was enabled when this code was read.
+   * Constructs an empty child environment.
    */
-  // 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, Deque<StackTraceElement> stackTrace) {
+    Preconditions.checkNotNull(parent);
+    this.parent = parent;
+    this.importedExtensions = new HashMap<>();
+    this.stackTrace = stackTrace;
   }
 
-  @Override
-  public Mutability mutability() {
-    // the mutability of the environment is that of its dynamic frame.
-    return dynamicFrame.mutability();
+  public Environment(Environment parent) {
+    this(parent, new LinkedList<StackTraceElement>());
   }
 
   /**
-   * @return the current Frame, in which variable side-effects happen.
+   * Constructs an empty child environment with an EventHandler.
    */
-  private Frame currentFrame() {
-    return isGlobal() ? globalFrame : lexicalFrame;
+  public Environment(Environment parent, EventHandler eventHandler) {
+    this(parent);
+    this.eventHandler = Preconditions.checkNotNull(eventHandler);
   }
 
-  /**
-   * @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;
   }
 
-  /**
-   * @return the current stack trace as a list of functions.
-   */
-  public ImmutableList<BaseFunction> getStackTrace() {
-    ImmutableList.Builder<BaseFunction> builder = new ImmutableList.Builder<>();
-    for (Continuation k = continuation; k != null; k = k.continuation) {
-      builder.add(k.function);
-    }
-    return builder.build().reverse();
+  // Sets up the global environment
+  private void setupGlobal() {
+    // In Python 2.x, True and False are global values and can be redefined by the user.
+    // In Python 3.x, they are keywords. We implement them as values, for the sake of
+    // simplicity. We define them as Boolean objects.
+    update("False", Runtime.FALSE);
+    update("True", Runtime.TRUE);
+    update("None", Runtime.NONE);
   }
 
-  /**
-   * Return the name of the top-level function being called and the location of the call.
-   */
-  public Pair<BaseFunction, Location> getTopCall() {
-    Continuation continuation = this.continuation;
-    if (continuation == null) {
-      return null;
-    }
-    while (continuation.continuation != null) {
-      continuation = continuation.continuation;
-    }
-    return new Pair<>(continuation.function, continuation.caller.getLocation());
+  public boolean isSkylark() {
+    return false;
   }
 
-  /**
-   * Constructs an Environment.
-   * This is the main, most basic constructor.
-   * @param globalFrame a frame for the global Environment
-   * @param dynamicFrame a frame for the dynamic Environment
-   * @param eventHandler an EventHandler for warnings, errors, etc
-   * @param importedExtensions frames for extensions from which to import bindings with load()
-   * @param isSkylark true if in Skylark context
-   * @param fileContentHashCode a hash for the source file being evaluated, if any
-   * @param isLoadingPhase true if in loading phase
-   */
-  private Environment(
-      Frame globalFrame,
-      Frame dynamicFrame,
-      EventHandler eventHandler,
-      Map<PathFragment, Environment> importedExtensions,
-      boolean isSkylark,
-      @Nullable String fileContentHashCode,
-      boolean isLoadingPhase) {
-    this.globalFrame = Preconditions.checkNotNull(globalFrame);
-    this.dynamicFrame = Preconditions.checkNotNull(dynamicFrame);
-    Preconditions.checkArgument(globalFrame.mutability().isMutable());
-    Preconditions.checkArgument(dynamicFrame.mutability().isMutable());
-    this.eventHandler = eventHandler;
-    this.importedExtensions = importedExtensions;
-    this.isSkylark = isSkylark;
-    this.fileContentHashCode = fileContentHashCode;
-    this.isLoadingPhase = isLoadingPhase;
-  }
-
-  /**
-   * 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);
-    }
+  protected boolean hasVariable(String varname) {
+    return env.containsKey(varname);
   }
 
   /**
    * @return the value from the environment whose name is "varname".
    * @throws NoSuchVariableException if the variable is not defined in the Environment.
+   *
    */
   public Object lookup(String varname) throws NoSuchVariableException {
-    // Which Frame to lookup first doesn't matter because update prevents clashes.
-    if (lexicalFrame != null) {
-      Object lexicalValue = lexicalFrame.get(varname);
-      if (lexicalValue != null) {
-        return lexicalValue;
+    Object value = env.get(varname);
+    if (value == null) {
+      if (parent != null) {
+        return parent.lookup(varname);
       }
-    }
-    Object globalValue = globalFrame.get(varname);
-    Object dynamicValue = dynamicFrame.get(varname);
-    if (globalValue == null && dynamicValue == null) {
       throw new NoSuchVariableException(varname);
     }
-    if (knownGlobalVariables != null) {
-      knownGlobalVariables.add(varname);
-    }
-    if (globalValue != null) {
-      return globalValue;
-    }
-    return dynamicValue;
+    return value;
   }
 
   /**
-   * 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.
+   * Like <code>lookup(String)</code>, but instead of throwing an exception in
+   * the case where "varname" is not defined, "defaultValue" is returned instead.
+   *
    */
   public Object lookup(String varname, Object defaultValue) {
-    Preconditions.checkState(!isSkylark);
-    try {
-      return lookup(varname);
-    } catch (NoSuchVariableException e) {
+    Object value = env.get(varname);
+    if (value == null) {
+      if (parent != null) {
+        return parent.lookup(varname, defaultValue);
+      }
       return defaultValue;
     }
+    return value;
   }
 
   /**
-   * @return true if varname is a known global variable,
-   * because it has been read in the context of the current function.
+   * Updates the value of variable "varname" in the environment, corresponding
+   * to an {@link AssignmentStatement}.
    */
-  boolean isKnownGlobalVariable(String varname) {
-    return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
-  }
-
-  public void handleEvent(Event event) {
-    eventHandler.handle(event);
+  public Environment update(String varname, Object value) {
+    Preconditions.checkNotNull(value, "update(value == null)");
+    env.put(varname, value);
+    return this;
   }
 
   /**
-   * @return the (immutable) set of names of all variables defined in this
-   * Environment. Exposed for testing.
+   * 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!
    */
   @VisibleForTesting
   public Set<String> getVariableNames() {
-    Set<String> vars = new HashSet<>();
-    if (lexicalFrame != null) {
-      lexicalFrame.addVariableNamesTo(vars);
+    if (parent == null) {
+      return env.keySet();
+    } else {
+      Set<String> vars = new HashSet<>();
+      vars.addAll(env.keySet());
+      vars.addAll(parent.getVariableNames());
+      return vars;
     }
-    globalFrame.addVariableNamesTo(vars);
-    dynamicFrame.addVariableNamesTo(vars);
-    return vars;
   }
 
   @Override
@@ -712,29 +268,23 @@
   @Override
   public String toString() {
     StringBuilder out = new StringBuilder();
-    out.append("Environment(lexicalFrame=");
-    out.append(lexicalFrame);
-    out.append(", globalFrame=");
-    out.append(globalFrame);
-    out.append(", dynamicFrame=");
-    out.append(dynamicFrame);
-    out.append(", eventHandler.getClass()=");
-    out.append(eventHandler.getClass());
-    out.append(", importedExtensions=");
-    out.append(importedExtensions);
-    out.append(", isSkylark=");
-    out.append(isSkylark);
-    out.append(", fileContentHashCode=");
-    out.append(fileContentHashCode);
-    out.append(", isLoadingPhase=");
-    out.append(isLoadingPhase);
-    out.append(")");
+    out.append("Environment{");
+    List<String> keys = new ArrayList<>(env.keySet());
+    Collections.sort(keys);
+    for (String key : keys) {
+      out.append(key).append(" -> ").append(env.get(key)).append(", ");
+    }
+    out.append("}");
+    if (parent != null) {
+      out.append("=>");
+      out.append(parent);
+    }
     return out.toString();
   }
 
   /**
-   * An Exception thrown when an attempt is made to lookup a non-existent
-   * variable in the Environment.
+   * An exception thrown when an attempt is made to lookup a non-existent
+   * variable in the environment.
    */
   public static class NoSuchVariableException extends Exception {
     NoSuchVariableException(String variable) {
@@ -743,7 +293,7 @@
   }
 
   /**
-   * An Exception thrown when an attempt is made to import a symbol from a file
+   * An exception thrown when an attempt is made to import a symbol from a file
    * that was not properly loaded.
    */
   public static class LoadFailedException extends Exception {
@@ -753,156 +303,78 @@
     }
   }
 
+  public void setImportedExtensions(Map<PathFragment, SkylarkEnvironment> importedExtensions) {
+    this.importedExtensions = importedExtensions;
+  }
+
   public void importSymbol(PathFragment extension, Identifier symbol, String nameInLoadedFile)
       throws NoSuchVariableException, LoadFailedException {
-    Preconditions.checkState(isGlobal()); // loading is only allowed at global scope.
-
     if (!importedExtensions.containsKey(extension)) {
       throw new LoadFailedException(extension.toString());
     }
 
     Object value = importedExtensions.get(extension).lookup(nameInLoadedFile);
-    // TODO(bazel-team): Unify data structures between Skylark and BUILD,
-    // and stop doing the conversions below:
-    if (!isSkylark) {
+    if (!isSkylark()) {
       value = SkylarkType.convertFromSkylark(value);
     }
 
-    try {
-      update(symbol.getName(), value);
-    } catch (EvalException e) {
-      throw new LoadFailedException(extension.toString());
-    }
+    update(symbol.getName(), value);
+  }
+
+  public ImmutableList<StackTraceElement> getStackTrace() {
+    return ImmutableList.copyOf(stackTrace);
+  }
+
+  protected Deque<StackTraceElement> getCopyOfStackTrace() {
+    return new LinkedList<>(stackTrace);
   }
 
   /**
-   * Returns a hash code calculated from the hash code of this Environment and the
-   * transitive closure of other Environments it loads.
+   * Adds the given element to the stack trace (iff the stack is empty) and returns whether it was
+   * successful.
    */
-  // 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());
+  public boolean tryAddingStackTraceRoot(StackTraceElement element) {
+    if (stackTrace.isEmpty()) {
+      stackTrace.add(element);
+      return true;
     }
-    return fingerprint.hexDigestAndReset();
+    return false;
   }
-
-
-  /** 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);
+  
+  public void addToStackTrace(StackTraceElement element)    {
+    stackTrace.add(element);
   }
 
   /**
-   * Parses some String input without a supporting file, returning statements and comments.
-   * @param input a list of lines of code
+   * Removes the only remaining element from the stack trace.
+   *
+   * <p>This particular element describes the outer-most calling function (usually a rule).
+   *
+   * <p> This method is required since {@link FuncallExpression} does not create a new {@link
+   * Environment}, hence it has to add and remove its {@link StackTraceElement} from an existing
+   * one.
    */
-  @VisibleForTesting
-  Parser.ParseResult parseFileWithComments(String... input) {
-    return isSkylark
-        ? Parser.parseFileForSkylark(
-            createLexer(input),
-            eventHandler,
-            EMPTY_PACKAGE_LOCATOR,
-            new ValidationEnvironment(this))
-        : Parser.parseFile(
-              createLexer(input),
-              eventHandler,
-              EMPTY_PACKAGE_LOCATOR,
-              /*parsePython=*/false);
+  public void removeStackTraceRoot() {
+    Preconditions.checkArgument(stackTrace.size() == 1);
+    stackTrace.clear();
+  }
+
+  public void removeStackTraceElement() {
+    // TODO(fwe): find out why the precond doesn't work
+    //    Preconditions.checkArgument(stackTrace.size() > 1);
+    stackTrace.removeLast();
   }
 
   /**
-   * Parses some String input without a supporting file, returning statements only.
-   * @param input a list of lines of code
+   * Returns whether the given {@link BaseFunction} is part of this {@link Environment}'s stack
+   * trace.
    */
-  @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;
+  public boolean stackTraceContains(BaseFunction function) {
+    for (StackTraceElement element : stackTrace) {
+      if (element.hasFunction(function)) {
+        return true;
       }
     }
-    return last;
+    return false;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalExceptionWithStackTrace.java
index 714556e..82ca835 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.getStartLine(),
+          location.getStartLineAndColumn().getLine(),
           element.getLabel(),
           element.getCause().getLabel());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
new file mode 100644
index 0000000..6a24cb3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
@@ -0,0 +1,195 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.syntax;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Joiner;
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.events.EventKind;
+import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.util.List;
+
+import javax.annotation.Nullable;
+
+/**
+ * Context for the evaluation of programs.
+ */
+public final class EvaluationContext {
+
+  @Nullable private EventHandler eventHandler;
+  private Environment env;
+  @Nullable private ValidationEnvironment validationEnv;
+  private boolean parsePython;
+
+  private EvaluationContext(EventHandler eventHandler, Environment env,
+      @Nullable ValidationEnvironment validationEnv, boolean parsePython) {
+    this.eventHandler = eventHandler;
+    this.env = env;
+    this.validationEnv = validationEnv;
+    this.parsePython = parsePython;
+  }
+
+  /**
+   * The fail fast handler, which throws a runtime exception whenever we encounter an error event.
+   */
+  public static final EventHandler FAIL_FAST_HANDLER = new EventHandler() {
+      @Override
+      public void handle(Event event) {
+        Preconditions.checkArgument(
+            !EventKind.ERRORS_AND_WARNINGS.contains(event.getKind()), event);
+      }
+    };
+
+  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env,
+      boolean parsePython) {
+    return new EvaluationContext(eventHandler, env, null, parsePython);
+  }
+
+  public static EvaluationContext newBuildContext(EventHandler eventHandler, Environment env) {
+    return newBuildContext(eventHandler, env, false);
+  }
+
+  public static EvaluationContext newBuildContext(EventHandler eventHandler) {
+    return newBuildContext(eventHandler, new Environment());
+  }
+
+  public static EvaluationContext newSkylarkContext(
+      Environment env, ValidationEnvironment validationEnv) {
+    return new EvaluationContext(env.getEventHandler(), env, validationEnv, false);
+  }
+
+  public static EvaluationContext newSkylarkContext(EventHandler eventHandler) {
+    return newSkylarkContext(new SkylarkEnvironment(eventHandler), new ValidationEnvironment());
+  }
+
+  /** Base context for Skylark evaluation for internal use only, while initializing builtins */
+  static final EvaluationContext SKYLARK_INITIALIZATION = newSkylarkContext(FAIL_FAST_HANDLER);
+
+  @VisibleForTesting
+  public Environment getEnvironment() {
+    return env;
+  }
+
+  /** Mock package locator */
+  private static final class EmptyPackageLocator implements CachingPackageLocator {
+    @Override
+    public Path getBuildFileForPackage(PackageIdentifier packageName) {
+      return null;
+    }
+  }
+
+  /** An empty package locator */
+  private static final CachingPackageLocator EMPTY_PACKAGE_LOCATOR = new EmptyPackageLocator();
+
+  /** Create a Lexer without a supporting file */
+  @VisibleForTesting
+  Lexer createLexer(String... input) {
+    return new Lexer(ParserInputSource.create(Joiner.on("\n").join(input), null),
+        eventHandler);
+  }
+
+  /** Is this a Skylark evaluation context? */
+  public boolean isSkylark() {
+    return env.isSkylark();
+  }
+
+  /** Parse a string without a supporting file, returning statements and comments */
+  @VisibleForTesting
+  Parser.ParseResult parseFileWithComments(String... input) {
+    return isSkylark()
+        ? Parser.parseFileForSkylark(createLexer(input), eventHandler, null, validationEnv)
+        : Parser.parseFile(createLexer(input), eventHandler, EMPTY_PACKAGE_LOCATOR, parsePython);
+  }
+
+  /** Parse a string without a supporting file, returning statements only */
+  @VisibleForTesting
+  List<Statement> parseFile(String... input) {
+    return parseFileWithComments(input).statements;
+  }
+
+  /** Parse an Expression from string without a supporting file */
+  @VisibleForTesting
+  Expression parseExpression(String... input) {
+    return Parser.parseExpression(createLexer(input), eventHandler);
+  }
+
+  /** Evaluate an Expression */
+  @VisibleForTesting
+  Object evalExpression(Expression expression) throws EvalException, InterruptedException {
+    return expression.eval(env);
+  }
+
+  /** Evaluate an Expression as parsed from String-s */
+  Object evalExpression(String... input) throws EvalException, InterruptedException {
+    return evalExpression(parseExpression(input));
+  }
+
+  /** Parse a build (not Skylark) Statement from string without a supporting file */
+  @VisibleForTesting
+  Statement parseStatement(String... input) {
+    return Parser.parseStatement(createLexer(input), eventHandler);
+  }
+
+  /**
+   * Evaluate a Statement
+   * @param statement the Statement
+   * @return the value of the evaluation, if it's an Expression, or else null
+   */
+  @Nullable private Object eval(Statement statement) throws EvalException, InterruptedException {
+    if (statement instanceof ExpressionStatement) {
+      return evalExpression(((ExpressionStatement) statement).getExpression());
+    }
+    statement.exec(env);
+    return null;
+  }
+
+  /**
+   * Evaluate a list of Statement-s
+   * @return the value of the last statement if it's an Expression or else null
+   */
+  @Nullable private Object eval(List<Statement> statements)
+      throws EvalException, InterruptedException {
+    Object last = null;
+    for (Statement statement : statements) {
+      last = eval(statement);
+    }
+    return last;
+  }
+
+  /** Update a variable in the environment, in fluent style */
+  public EvaluationContext update(String varname, Object value) throws EvalException {
+    env.update(varname, value);
+    if (validationEnv != null) {
+      validationEnv.declare(varname, null);
+    }
+    return this;
+  }
+
+  /** Lookup a variable in the environment */
+  public Object lookup(String varname) throws NoSuchVariableException {
+    return env.lookup(varname);
+  }
+
+  /** Evaluate a series of statements */
+  public Object eval(String... input) throws EvalException, InterruptedException {
+    return eval(parseFile(input));
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
index 1886843..b7842d4 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 {@link Environment} according to
-   * the rules of the Skylark language, throws {@link EvalException} in case of a semantical error.
+   * <p>Checks the semantics of the Expression using the SkylarkEnvironment according to
+   * the rules of the Skylark language, throws EvalException in case of a semantical error.
    *
    * @see Statement
    */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 76737dd..8d1eb56 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -353,11 +353,21 @@
   // TODO(bazel-team): If there's exactly one usable method, this works. If there are multiple
   // matching methods, it still can be a problem. Figure out how the Java compiler does it
   // exactly and copy that behaviour.
-  private MethodDescriptor findJavaMethod(
-      Class<?> objClass, String methodName, List<Object> args) throws EvalException {
+  // TODO(bazel-team): check if this and SkylarkBuiltInFunctions.createObject can be merged.
+  private Object invokeJavaMethod(
+      Object obj, Class<?> objClass, String methodName, List<Object> args, boolean hasKwArgs)
+      throws EvalException {
     MethodDescriptor matchingMethod = null;
     List<MethodDescriptor> methods = getMethods(objClass, methodName, args.size(), getLocation());
     if (methods != null) {
+      if (hasKwArgs) {
+        throw new EvalException(
+            func.getLocation(),
+            String.format(
+                "Keyword arguments are not allowed when calling a java method"
+                + "\nwhile calling method '%s' on object of type %s",
+                func.getName(), EvalUtils.getDataTypeNameFromClass(objClass)));
+      }
       for (MethodDescriptor method : methods) {
         Class<?>[] params = method.getMethod().getParameterTypes();
         int i = 0;
@@ -381,11 +391,12 @@
       }
     }
     if (matchingMethod != null && !matchingMethod.getAnnotation().structField()) {
-      return matchingMethod;
+      return callMethod(matchingMethod, methodName, obj, args.toArray(), getLocation());
+    } else {
+      throw new EvalException(getLocation(), "No matching method found for "
+          + formatMethod(methodName, args) + " in "
+          + EvalUtils.getDataTypeNameFromClass(objClass));
     }
-    throw new EvalException(getLocation(), "No matching method found for "
-        + formatMethod(methodName, args) + " in "
-        + EvalUtils.getDataTypeNameFromClass(objClass));
   }
 
   private String formatMethod(String methodName, List<Object> args) {
@@ -479,7 +490,20 @@
 
   @Override
   Object eval(Environment env) throws EvalException, InterruptedException {
-    return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
+    // Adds the calling rule to the stack trace of the Environment if it is a BUILD environment.
+    // There are two reasons for this:
+    // a) When using aliases in load(), the rule class name in the BUILD file will differ from
+    //    the implementation name in the bzl file. Consequently, we need to store the calling name.
+    // b) We need the location of the calling rule inside the BUILD file.
+    boolean hasAddedElement =
+        env.isSkylark() ? false : env.tryAddingStackTraceRoot(new StackTraceElement(func, args));
+    try {
+      return (obj != null) ? invokeObjectMethod(env) : invokeGlobalFunction(env);
+    } finally {
+      if (hasAddedElement) {
+        env.removeStackTraceRoot();
+      }
+    }
   }
 
   /**
@@ -526,28 +550,15 @@
       // When calling a Java method, the name is not in the Environment,
       // so evaluating 'func' would fail.
       evalArguments(posargs, kwargs, env, null);
-      Class<?> objClass;
-      Object obj;
       if (objValue instanceof Class<?>) {
-        // Static call
-        obj = null;
-        objClass = (Class<?>) objValue;
+        // Static Java method call. We can return the value from here directly because
+        // invokeJavaMethod() has special checks.
+        return invokeJavaMethod(
+            null, (Class<?>) objValue, func.getName(), posargs.build(), !kwargs.isEmpty());
       } else {
-        obj = objValue;
-        objClass = objValue.getClass();
+        return invokeJavaMethod(
+            objValue, objValue.getClass(), func.getName(), posargs.build(), !kwargs.isEmpty());
       }
-      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 acc09c9..ae7c027 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
@@ -50,14 +50,10 @@
         defaultValues.add(expr.eval(env));
       }
     }
-    env.update(
-        ident.getName(),
-        new UserDefinedFunction(
-            ident,
-            FunctionSignature.WithValues.<Object, SkylarkType>create(
-                signature.getSignature(), defaultValues, types),
-            statements,
-            env.getGlobals()));
+    env.update(ident.getName(), new UserDefinedFunction(
+        ident, FunctionSignature.WithValues.<Object, SkylarkType>create(
+            signature.getSignature(), defaultValues, types),
+        statements, (SkylarkEnvironment) env));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index 1a39755..df5f486 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -84,7 +84,8 @@
     if (env.isSkylark()) {
       // The variable may have been referenced successfully if a global variable
       // with the same name exists. In this case an Exception needs to be thrown.
-      if (env.isKnownGlobalVariable(ident.getName())) {
+      SkylarkEnvironment skylarkEnv = (SkylarkEnvironment) env;
+      if (skylarkEnv.hasBeenReadGlobalVariable(ident.getName())) {
         throw new EvalException(
             loc,
             String.format(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index b1ca1f6..996ae41 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.isCallerSkylark()) {
+          if (env.isSkylark()) {
             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.isCallerSkylark()) {
+          if (env.isSkylark()) {
             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.isCallerSkylark() ? SkylarkList.tuple(item) : item);
+        list.add(env.isSkylark() ? 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.isCallerSkylark()) {
+    if (env.isSkylark()) {
       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, Environment env) throws EvalException {
+        Location loc, SkylarkEnvironment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
                 @Override
@@ -1493,6 +1493,19 @@
 
 
   /**
+   * Set up a given environment for supported class methods.
+   */
+  public static void setupMethodEnvironment(Environment env) {
+    setupMethodEnvironment(env, env.isSkylark() ? skylarkGlobalFunctions : buildGlobalFunctions);
+  }
+
+  private static void setupMethodEnvironment(Environment env, Iterable<BaseFunction> functions) {
+    for (BaseFunction function : functions) {
+      env.update(function.getName(), function);
+    }
+  }
+
+  /**
    * Collect global functions for the validation environment.
    */
   public static void setupValidationEnvironment(Set<String> builtIn) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
deleted file mode 100644
index 5120f8d..0000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
+++ /dev/null
@@ -1,136 +0,0 @@
-// Copyright 2015 Google Inc. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.syntax;
-
-import com.google.common.base.Preconditions;
-
-/**
- * A Mutability is a resource associated with an {@link Environment} during an evaluation,
- * that gives those who possess it a revokable capability to mutate this Environment and
- * the objects created within that {@link Environment}. At the end of the evaluation,
- * the resource is irreversibly closed, at which point the capability is revoked,
- * and it is not possible to mutate either this {@link Environment} or these objects.
- *
- * <p>Evaluation in an {@link Environment} may thus mutate objects created in the same
- * {@link Environment}, but may not mutate {@link Freezable} objects (lists, sets, dicts)
- * created in a previous, concurrent or future {@link Environment}, and conversely,
- * the bindings and objects in this {@link Environment} will be protected from
- * mutation by evaluation in a different {@link Environment}.
- *
- * <p>Only a single thread may use the {@link Environment} and objects created within it while the
- * Mutability is still mutable as tested by {@link #isMutable}. Once the Mutability resource
- * is closed, the {@link Environment} and its objects are immutable and can be simultaneously used
- * by arbitrarily many threads.
- *
- * <p>The safe usage of a Mutability requires to always use try-with-resource style:
- * <code>try(Mutability mutability = Mutability.create(fmt, ...)) { ... }</code>
- * Thus, you can create a Mutability, build an {@link Environment}, mutate that {@link Environment}
- * and create mutable objects as you evaluate in that {@link Environment}, and finally return the
- * resulting {@link Environment}, at which point the resource is closed, and the {@link Environment}
- * and the objects it contains all become immutable.
- * (Unsafe usage is allowed only in test code that is not part of the Bazel jar.)
- */
-// TODO(bazel-team): When we start using Java 8, this safe usage pattern can be enforced
-// through the use of a higher-order function.
-public final class Mutability implements AutoCloseable {
-  private boolean isMutable;
-  private final Object annotation; // For error reporting
-
-  /**
-   * Creates a Mutability.
-   * @param annotation an Object used for error reporting,
-   * describing to the user the context in which this Mutability was active.
-   */
-  private Mutability(Object annotation) {
-    this.isMutable = true;
-    this.annotation = Preconditions.checkNotNull(annotation);
-  }
-
-  /**
-   * Creates a Mutability.
-   * @param pattern is a {@link Printer#format} pattern used to lazily produce a string
-   * for error reporting
-   * @param arguments are the optional {@link Printer#format} arguments to produce that string
-   */
-  public static Mutability create(String pattern, Object... arguments) {
-    return new Mutability(Printer.formattable(pattern, arguments));
-  }
-
-  Object getAnnotation() {
-    return annotation;
-  }
-
-  @Override
-  public String toString() {
-    return String.format(isMutable ? "[%s]" : "(%s)", annotation);
-  }
-
-  boolean isMutable() {
-    return isMutable;
-  }
-
-  /**
-   * Freezes this Mutability, marking as immutable all {@link Freezable} objects that use it.
-   */
-  @Override
-  public void close() {
-    isMutable = false;
-  }
-
-  /**
-   * A MutabilityException will be thrown when the user attempts to mutate an object he shouldn't.
-   */
-  static class MutabilityException extends Exception {
-    MutabilityException(String message) {
-      super(message);
-    }
-  }
-
-  /**
-   * Each {@link Freezable} object possesses a revokable Mutability attribute telling whether
-   * the object is still mutable. All {@link Freezable} objects created in the same
-   * {@link Environment} will share the same Mutability, inherited from this {@link Environment}.
-   * Only evaluation in the same {@link Environment} is allowed to mutate these objects,
-   * and only until the Mutability is irreversibly revoked.
-   */
-  public interface Freezable {
-    /**
-     * Returns the {@link Mutability} capability associated with this Freezable object.
-     */
-    Mutability mutability();
-  }
-
-  /**
-   * Checks that this Freezable object can be mutated from the given {@link Environment}.
-   * @param object a Freezable object that we check is still mutable.
-   * @param env the {@link Environment} attempting the mutation.
-   * @throws MutabilityException when the object was frozen already, or is from another context.
-   */
-  public static void checkMutable(Freezable object, Environment env)
-      throws MutabilityException {
-    if (!object.mutability().isMutable()) {
-      throw new MutabilityException("trying to mutate a frozen object");
-    }
-    // Consider an {@link Environment} e1, in which is created {@link UserDefinedFunction} f1,
-    // that closes over some variable v1 bound to list l1. If somehow, via the magic of callbacks,
-    // f1 or l1 is passed as argument to some function f2 evaluated in {@link environment} e2
-    // while e1 is be mutable, e2, being a different {@link Environment}, should not be
-    // allowed to mutate objects from e1. It's a bug, that shouldn't happen in our current code
-    // base, so we throw an AssertionError. If in the future such situations are allowed to happen,
-    // then we should throw a MutabilityException instead.
-    if (!object.mutability().equals(env.mutability())) {
-      throw new AssertionError("trying to mutate an object from a different context");
-    }
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 9230d6b..50ef2546 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.")
-  private static final Boolean TRUE = true;
+  static final Boolean TRUE = true;
 
   @SkylarkSignature(name = "False", returnType = Boolean.class,
       doc = "Literal for the boolean false.")
-  private static final Boolean FALSE = false;
+  static final Boolean FALSE = false;
 
   /**
    * There should be only one instance of this type to allow "== None" tests.
@@ -70,11 +70,11 @@
   /**
    * Set up a given environment for supported class methods.
    */
-  static Environment setupConstants(Environment env) {
+  static Environment setupConstants(Environment env) throws EvalException {
     // In Python 2.x, True and False are global values and can be redefined by the user.
     // In Python 3.x, they are keywords. We implement them as values, for the sake of
     // simplicity. We define them as Boolean objects.
-    return env.setup("False", FALSE).setup("True", TRUE).setup("None", NONE);
+    return env.update("False", FALSE).update("True", TRUE).update("None", NONE);
   }
 
 
@@ -128,7 +128,7 @@
   public static void registerModuleGlobals(Environment env, Class<?> moduleClass) {
     try {
       if (moduleClass.isAnnotationPresent(SkylarkModule.class)) {
-        env.setup(
+        env.update(
             moduleClass.getAnnotation(SkylarkModule.class).name(), moduleClass.newInstance());
       }
       for (Field field : moduleClass.getDeclaredFields()) {
@@ -142,7 +142,7 @@
           if (!(value instanceof BuiltinFunction.Factory
               || (value instanceof BaseFunction
                   && !annotation.objectType().equals(Object.class)))) {
-            env.setup(annotation.name(), value);
+            env.update(annotation.name(), value);
           }
         }
       }
@@ -168,9 +168,9 @@
   }
 
   static void setupMethodEnvironment(
-      Environment env, Iterable<BaseFunction> functions) {
+      Environment env, Iterable<BaseFunction> functions) throws EvalException {
     for (BaseFunction function : functions) {
-      env.setup(function.getName(), function);
+      env.update(function.getName(), function);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
index 6140acb..94b1917 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkCallbackFunction.java
@@ -22,25 +22,21 @@
 
   private final BaseFunction callback;
   private final FuncallExpression ast;
-  private final Environment funcallEnv;
+  private final SkylarkEnvironment funcallEnv;
 
-  public SkylarkCallbackFunction(
-      BaseFunction callback, FuncallExpression ast, Environment funcallEnv) {
+  public SkylarkCallbackFunction(BaseFunction callback, FuncallExpression ast,
+      SkylarkEnvironment funcallEnv) {
     this.callback = callback;
     this.ast = ast;
     this.funcallEnv = funcallEnv;
   }
 
   public Object call(ClassObject ctx, Object... arguments) throws EvalException {
-    try (Mutability mutability = Mutability.create("callback %s", callback)) {
-      Environment env = Environment.builder(mutability)
-          .setSkylark()
-          .setEventHandler(funcallEnv.getEventHandler())
-          .setGlobals(funcallEnv.getGlobals())
-          .build();
+    try {
       return callback.call(
-          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, env);
-    } catch (InterruptedException | ClassCastException | IllegalArgumentException e) {
+          ImmutableList.<Object>builder().add(ctx).add(arguments).build(), null, ast, funcallEnv);
+    } catch (InterruptedException | ClassCastException
+        | IllegalArgumentException e) {
       throw new EvalException(ast.getLocation(), e.getMessage());
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
new file mode 100644
index 0000000..0ff19f9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
@@ -0,0 +1,205 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.syntax;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.util.Fingerprint;
+
+import java.io.Serializable;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * The environment for Skylark.
+ */
+public class SkylarkEnvironment extends Environment implements Serializable {
+
+  /**
+   * This set contains the variable names of all the successful lookups from the global
+   * environment. This is necessary because if in a function definition something
+   * reads a global variable after which a local variable with the same name is assigned an
+   * Exception needs to be thrown.
+   */
+  private final Set<String> readGlobalVariables = new HashSet<>();
+
+  @Nullable private String fileContentHashCode;
+
+  /**
+   * Creates a Skylark Environment for function calling, from the global Environment of the
+   * caller Environment (which must be a Skylark Environment).
+   */
+  public static SkylarkEnvironment createEnvironmentForFunctionCalling(
+      Environment callerEnv, SkylarkEnvironment definitionEnv,
+      UserDefinedFunction function) throws EvalException {
+    if (callerEnv.stackTraceContains(function)) {
+      throw new EvalException(
+          function.getLocation(),
+          "Recursion was detected when calling '" + function.getName() + "' from '"
+          + Iterables.getLast(callerEnv.getStackTrace()).getName() + "'");
+    }
+    SkylarkEnvironment childEnv =
+        // Always use the caller Environment's EventHandler. We cannot assume that the
+        // definition Environment's EventHandler is still working properly.
+        new SkylarkEnvironment(
+            definitionEnv, callerEnv.getCopyOfStackTrace(), callerEnv.eventHandler);
+    if (callerEnv.isLoadingPhase()) {
+      childEnv.setLoadingPhase();
+    }
+
+    try {
+      for (String varname : callerEnv.propagatingVariables) {
+        childEnv.updateAndPropagate(varname, callerEnv.lookup(varname));
+      }
+    } catch (NoSuchVariableException e) {
+      // This should never happen.
+      throw new IllegalStateException(e);
+    }
+    return childEnv;
+  }
+
+  private SkylarkEnvironment(SkylarkEnvironment definitionEnv,
+      Deque<StackTraceElement> stackTrace, EventHandler eventHandler) {
+    super(definitionEnv.getGlobalEnvironment(), stackTrace);
+    this.eventHandler = Preconditions.checkNotNull(eventHandler,
+        "EventHandler cannot be null in an Environment which calls into Skylark");
+  }
+
+  /**
+   * Creates a global SkylarkEnvironment.
+   */
+  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode,
+      Deque<StackTraceElement> stackTrace) {
+    super(stackTrace);
+    this.eventHandler = eventHandler;
+    this.fileContentHashCode = astFileContentHashCode;
+  }
+
+  public SkylarkEnvironment(EventHandler eventHandler, String astFileContentHashCode) {
+    this(eventHandler, astFileContentHashCode, new LinkedList<StackTraceElement>());
+  }
+
+  @VisibleForTesting
+  public SkylarkEnvironment(EventHandler eventHandler) {
+    this(eventHandler, null);
+  }
+
+  public SkylarkEnvironment(SkylarkEnvironment globalEnv) {
+    super(globalEnv);
+    this.eventHandler = globalEnv.eventHandler;
+  }
+
+  /**
+   * Clones this Skylark global environment.
+   */
+  public SkylarkEnvironment cloneEnv(EventHandler eventHandler) {
+    Preconditions.checkArgument(isGlobal());
+    SkylarkEnvironment newEnv =
+        new SkylarkEnvironment(eventHandler, this.fileContentHashCode, getCopyOfStackTrace());
+    for (Entry<String, Object> entry : env.entrySet()) {
+      newEnv.env.put(entry.getKey(), entry.getValue());
+    }
+    return newEnv;
+  }
+
+  /**
+   * Returns the global environment. Only works for Skylark environments. For the global Skylark
+   * environment this method returns this Environment.
+   */
+  public SkylarkEnvironment getGlobalEnvironment() {
+    // If there's a parent that's the global environment, otherwise this is.
+    return parent != null ? (SkylarkEnvironment) parent : this;
+  }
+
+  /**
+   * Returns true if this is a Skylark global environment.
+   */
+  @Override
+  public boolean isGlobal() {
+    return parent == null;
+  }
+
+  /**
+   * Returns true if varname has been read as a global variable.
+   */
+  public boolean hasBeenReadGlobalVariable(String varname) {
+    return readGlobalVariables.contains(varname);
+  }
+
+  @Override
+  public boolean isSkylark() {
+    return true;
+  }
+
+  /**
+   * @return the value from the environment whose name is "varname".
+   * @throws NoSuchVariableException if the variable is not defined in the environment.
+   */
+  @Override
+  public Object lookup(String varname) throws NoSuchVariableException {
+    Object value = env.get(varname);
+    if (value == null) {
+      if (parent != null && parent.hasVariable(varname)) {
+        readGlobalVariables.add(varname);
+        return parent.lookup(varname);
+      }
+      throw new NoSuchVariableException(varname);
+    }
+    return value;
+  }
+
+  /**
+   * Like <code>lookup(String)</code>, but instead of throwing an exception in
+   * the case where "varname" is not defined, "defaultValue" is returned instead.
+   */
+  @Override
+  public Object lookup(String varname, Object defaultValue) {
+    throw new UnsupportedOperationException();
+  }
+
+  /**
+   * Returns the class of the variable or null if the variable does not exist. This function
+   * works only in the local Environment, it doesn't check the global Environment.
+   */
+  public Class<?> getVariableType(String varname) {
+    Object variable = env.get(varname);
+    return variable != null ? EvalUtils.getSkylarkType(variable.getClass()) : null;
+  }
+
+  public void handleEvent(Event event) {
+    eventHandler.handle(event);
+  }
+
+  /**
+   * Returns a hash code calculated from the hash code of this Environment and the
+   * transitive closure of other Environments it loads.
+   */
+  public String getTransitiveFileContentHashCode() {
+    Fingerprint fingerprint = new Fingerprint();
+    fingerprint.addString(Preconditions.checkNotNull(fileContentHashCode));
+    // Calculate a new hash from the hash of the loaded Environments.
+    for (SkylarkEnvironment env : importedExtensions.values()) {
+      fingerprint.addString(env.getTransitiveFileContentHashCode());
+    }
+    return fingerprint.hexDigestAndReset();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index 6b31625..bf3c832 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -204,13 +204,8 @@
     } else if (param.defaultValue().isEmpty()) {
       return Runtime.NONE;
     } else {
-      try (Mutability mutability = Mutability.create("initialization")) {
-        return Environment.builder(mutability)
-            .setSkylark()
-            .setGlobals(Environment.CONSTANTS_ONLY)
-            .setEventHandler(Environment.FAIL_FAST_HANDLER)
-            .build()
-            .eval(param.defaultValue());
+      try {
+        return EvaluationContext.SKYLARK_INITIALIZATION.evalExpression(param.defaultValue());
       } catch (Exception e) {
         throw new RuntimeException(String.format(
             "Exception while processing @SkylarkSignature.Param %s, default value %s",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
index 2c99209..ca89b1a 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 Environment according to
-   * the rules of the Skylark language. The Environment can be used e.g. to check
+   * Checks the semantics of the Statement using the SkylarkEnvironment according to
+   * the rules of the Skylark language. The SkylarkEnvironment can be used e.g. to check
    * variable type collision, read only variables, detecting recursion, existence of
    * built-in variables, functions, etc.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index 537f29f..f50e6ee 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location.LineAndColumn;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
@@ -27,16 +26,15 @@
 public class UserDefinedFunction extends BaseFunction {
 
   private final ImmutableList<Statement> statements;
-
-  // we close over the globals at the time of definition
-  private final Environment.Frame definitionGlobals;
+  private final SkylarkEnvironment definitionEnv;
 
   protected UserDefinedFunction(Identifier function,
       FunctionSignature.WithValues<Object, SkylarkType> signature,
-      ImmutableList<Statement> statements, Environment.Frame definitionGlobals) {
+      ImmutableList<Statement> statements, SkylarkEnvironment definitionEnv) {
     super(function.getName(), signature, function.getLocation());
+
     this.statements = statements;
-    this.definitionGlobals = definitionGlobals;
+    this.definitionEnv = definitionEnv;
   }
 
   public FunctionSignature.WithValues<Object, SkylarkType> getFunctionSignature() {
@@ -50,36 +48,23 @@
   @Override
   public Object call(Object[] arguments, FuncallExpression ast, Environment env)
       throws EvalException, InterruptedException {
-    if (!env.mutability().isMutable()) {
-      throw new EvalException(getLocation(), "Trying to call in frozen environment");
-    }
-    if (env.getStackTrace().contains(this)) {
-      throw new EvalException(getLocation(),
-          String.format("Recursion was detected when calling '%s' from '%s'",
-              getName(), Iterables.getLast(env.getStackTrace()).getName()));
+    ImmutableList<String> names = signature.getSignature().getNames();
+
+    // Registering the functions's arguments as variables in the local Environment
+    int i = 0;
+    for (String name : names) {
+      env.update(name, arguments[i++]);
     }
 
     long startTimeProfiler = Profiler.nanoTimeMaybe();
     Statement lastStatement = null;
     try {
-      env.enterScope(this, ast, definitionGlobals);
-      ImmutableList<String> names = signature.getSignature().getNames();
-
-      // Registering the functions's arguments as variables in the local Environment
-      int i = 0;
-      for (String name : names) {
-        env.update(name, arguments[i++]);
+      for (Statement stmt : statements) {
+        lastStatement = stmt;
+        stmt.exec(env);
       }
-
-      try {
-        for (Statement stmt : statements) {
-          lastStatement = stmt;
-          stmt.exec(env);
-        }
-      } catch (ReturnStatement.ReturnException e) {
-        return e.getValue();
-      }
-      return Runtime.NONE;
+    } catch (ReturnStatement.ReturnException e) {
+      return e.getValue();
     } catch (EvalExceptionWithStackTrace ex) {
       // We need this block since the next "catch" must only catch EvalExceptions that don't have a
       // stack trace yet.
@@ -94,8 +79,8 @@
           startTimeProfiler,
           ProfilerTask.SKYLARK_USER_FN,
           getLocationPathAndLine() + "#" + getName());
-      env.exitScope();
     }
+    return Runtime.NONE;
   }
 
   /**
@@ -120,4 +105,14 @@
     }
     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 9d56271..9b71f96 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.events.Location;
 
 import java.util.HashMap;
@@ -30,7 +31,7 @@
  * @see Statement#validate
  * @see Expression#validate
  */
-public final class ValidationEnvironment {
+public class ValidationEnvironment {
 
   private final ValidationEnvironment parent;
 
@@ -44,6 +45,9 @@
   // branches of if-else statements.
   private Stack<Set<String>> futureReadOnlyVariables = new Stack<>();
 
+  // Whether this validation environment is not modified therefore clonable or not.
+  private boolean clonable;
+
   /**
    * Tracks the number of nested for loops that contain the statement that is currently being
    * validated
@@ -51,14 +55,38 @@
   private int loopCount = 0;
 
   /**
-   * Create a ValidationEnvironment for a given global Environment.
+   * Create a ValidationEnvironment for a given global Environment
    */
   public ValidationEnvironment(Environment env) {
+    this(env.getVariableNames());
     Preconditions.checkArgument(env.isGlobal());
+  }
+
+  public ValidationEnvironment(Set<String> builtinVariables) {
     parent = null;
-    Set<String> builtinVariables = env.getVariableNames();
     variables.addAll(builtinVariables);
     readOnlyVariables.addAll(builtinVariables);
+    clonable = true;
+  }
+
+  private ValidationEnvironment(Set<String> builtinVariables, Set<String> readOnlyVariables) {
+    parent = null;
+    this.variables = new HashSet<>(builtinVariables);
+    this.readOnlyVariables = new HashSet<>(readOnlyVariables);
+    clonable = false;
+  }
+
+  // ValidationEnvironment for a new Environment()
+  private static ImmutableSet<String> globalTypes = ImmutableSet.of("False", "True", "None");
+
+  public ValidationEnvironment() {
+    this(globalTypes);
+  }
+
+  @Override
+  public ValidationEnvironment clone() {
+    Preconditions.checkState(clonable);
+    return new ValidationEnvironment(variables, readOnlyVariables);
   }
 
   /**
@@ -67,6 +95,7 @@
   public ValidationEnvironment(ValidationEnvironment parent) {
     // Don't copy readOnlyVariables: Variables may shadow global values.
     this.parent = parent;
+    this.clonable = false;
   }
 
   /**
@@ -91,6 +120,7 @@
     }
     variables.add(varname);
     variableLocations.put(varname, location);
+    clonable = false;
   }
 
   private void checkReadonly(String varname, Location location) throws EvalException {
@@ -103,8 +133,7 @@
    * Returns true if the symbol exists in the validation environment.
    */
   public boolean hasSymbolInEnvironment(String varname) {
-    return variables.contains(varname)
-        || (parent != null && topLevel().variables.contains(varname));
+    return variables.contains(varname) || topLevel().variables.contains(varname);
   }
 
   private ValidationEnvironment topLevel() {
@@ -118,6 +147,7 @@
    */
   public void startTemporarilyDisableReadonlyCheckSession() {
     futureReadOnlyVariables.add(new HashSet<String>());
+    clonable = false;
   }
 
   /**
@@ -129,6 +159,7 @@
     if (!futureReadOnlyVariables.isEmpty()) {
       futureReadOnlyVariables.peek().addAll(variables);
     }
+    clonable = false;
   }
 
   /**
@@ -136,6 +167,7 @@
    */
   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 c7f85d6..aa8d8f8 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.Environment;
+import com.google.devtools.build.lib.syntax.EvaluationContext;
 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(Environment.FAIL_FAST_HANDLER);
+      reporter.addHandler(EvaluationContext.FAIL_FAST_HANDLER);
     } else {
-      reporter.removeHandler(Environment.FAIL_FAST_HANDLER);
+      reporter.removeHandler(EvaluationContext.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 2f29851..24ac455 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, Environment>of(),
+        new MakeEnvironment.Builder(), ImmutableMap.<PathFragment, SkylarkEnvironment>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 00e9062..eff5bad 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,7 +22,11 @@
 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;
 
@@ -33,14 +37,13 @@
 import java.io.IOException;
 import java.util.Arrays;
 
-/**
- * Unit tests for BuildFileAST.
- */
 @RunWith(JUnit4.class)
-public class BuildFileASTTest extends EvaluationTestCase {
+public class BuildFileASTTest {
 
   private Scratch scratch = new Scratch();
 
+  private EventCollectionApparatus events = new EventCollectionApparatus(EventKind.ALL_EVENTS);
+
   private class ScratchPathPackageLocator implements CachingPackageLocator {
     @Override
     public Path getBuildFileForPackage(PackageIdentifier packageName) {
@@ -50,18 +53,13 @@
 
   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, getEventHandler(), locator, false);
+    return BuildFileAST.parseBuildFile(file, events.reporter(), locator, false);
   }
 
   @Test
@@ -71,9 +69,11 @@
         "",
         "x = [1,2,'foo',4] + [1,2, \"%s%d\" % ('foo', 1)]");
 
-    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, getEventHandler(), null, false);
+    Environment env = new Environment();
+    Reporter reporter = new Reporter();
+    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, reporter, null, false);
 
-    assertTrue(buildfile.exec(env, getEventHandler()));
+    assertTrue(buildfile.exec(env, reporter));
 
     // Test final environment is correctly modified:
     //
@@ -91,11 +91,15 @@
         "",
         "z = x + y");
 
-    setFailFast(false);
-    BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, getEventHandler(), null, false);
+    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);
 
-    assertFalse(buildfile.exec(env, getEventHandler()));
-    Event e = assertContainsEvent("unsupported operand type(s) for +: 'int' and 'List'");
+    assertFalse(buildfile.exec(env, reporter));
+    Event e = MoreAsserts.assertContainsEvent(collector,
+        "unsupported operand type(s) for +: 'int' and 'List'");
     assertEquals(4, e.getLocation().getStartLineAndColumn().getLine());
   }
 
@@ -110,12 +114,13 @@
 
   @Test
   public void testFailsIfNewlinesAreMissing() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
 
     BuildFileAST buildFileAST =
       parseBuildFile("foo() bar() something = baz() bar()");
 
-    Event event = assertContainsEvent("syntax error at \'bar\': expected newline");
+    Event event = events.collector().iterator().next();
+    assertEquals("syntax error at \'bar\': expected newline", event.getMessage());
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(1, event.getLocation().getStartLineAndColumn().getLine());
@@ -124,10 +129,11 @@
 
   @Test
   public void testImplicitStringConcatenationFails() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("a = 'foo' 'bar'");
-    Event event = assertContainsEvent(
-        "Implicit string concatenation is forbidden, use the + operator");
+    Event event = events.collector().iterator().next();
+    assertEquals("Implicit string concatenation is forbidden, use the + operator",
+        event.getMessage());
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(1, event.getLocation().getStartLineAndColumn().getLine());
@@ -137,10 +143,11 @@
 
   @Test
   public void testImplicitStringConcatenationAcrossLinesIsIllegal() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("a = 'foo'\n  'bar'");
 
-    Event event = assertContainsEvent("indentation error");
+    Event event = events.collector().iterator().next();
+    assertEquals("indentation error", event.getMessage());
     assertEquals("/a/build/file/BUILD",
                  event.getLocation().getPath().toString());
     assertEquals(2, event.getLocation().getStartLineAndColumn().getLine());
@@ -165,7 +172,7 @@
 
   @Test
   public void testWithSyntaxErrorsDoesNotPrintDollarError() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     BuildFileAST buildFile = parseBuildFile(
         "abi = cxx_abi + '-glibc-' + glibc_version + '-' + generic_cpu + '-' + sysname",
         "libs = [abi + opt_level + '/lib/libcc.a']",
@@ -175,11 +182,14 @@
         "           srcs = libs,",
         "           includes = [ abi + opt_level + '/include' ])");
     assertTrue(buildFile.containsErrors());
-    assertContainsEvent("syntax error at '+': expected expression");
-    assertFalse(buildFile.exec(env, getEventHandler()));
-    assertNull(findEvent(getEventCollector(), "$error$"));
+    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$"));
     // This message should not be printed anymore.
-    assertNull(findEvent(getEventCollector(), "contains syntax error(s)"));
+    Event event2 = findEvent(events.collector(), "contains syntax error(s)");
+    assertNull(event2);
   }
 
   @Test
@@ -192,7 +202,7 @@
         + "include(\"//foo/bar:BUILD\")\n"
         + "b = 4\n");
 
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, getEventHandler(),
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
                                                             locator, false);
 
     assertFalse(buildFileAST.containsErrors());
@@ -207,14 +217,15 @@
         "include(\"//foo/bar:defs\")\n"
         + "b = a + 1\n");
 
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, getEventHandler(),
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
                                                             locator, false);
 
     assertFalse(buildFileAST.containsErrors());
     assertThat(buildFileAST.getStatements()).hasSize(3);
 
-    setFailFast(false);
-    assertFalse(buildFileAST.exec(env, getEventHandler()));
+    Environment env = new Environment();
+    Reporter reporter = new Reporter();
+    assertFalse(buildFileAST.exec(env, reporter));
     assertEquals(2, env.lookup("b"));
   }
 
@@ -236,53 +247,63 @@
     assertFalse(buildFileAST.containsErrors());
     assertThat(buildFileAST.getStatements()).hasSize(8);
 
-    setFailFast(false);
-    assertFalse(buildFileAST.exec(env, getEventHandler()));
+    Environment env = new Environment();
+    Reporter reporter = new Reporter();
+    assertFalse(buildFileAST.exec(env, reporter));
     assertEquals(5, env.lookup("b"));
     assertEquals(7, env.lookup("c"));
   }
 
   @Test
   public void testFailInclude() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("include(\"//nonexistent\")");
     assertThat(buildFileAST.getStatements()).hasSize(1);
-    assertContainsEvent("Include of '//nonexistent' failed");
+    events.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 {
-    setFailFast(false);
+    events.setFailFast(false);
     Path buildFile = scratch.file("/foo/bar/BUILD",
         "include(\"//nonexistent:foo\")\n");
-    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(
-        buildFile, getEventHandler(), Environment.EMPTY_PACKAGE_LOCATOR, false);
+    BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(buildFile, events.reporter(),
+                                                            emptyLocator, false);
     assertThat(buildFileAST.getStatements()).hasSize(1);
-    assertContainsEvent("Package 'nonexistent' not found");
+    events.assertContainsEvent("Package 'nonexistent' not found");
   }
 
   @Test
   public void testInvalidInclude() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     BuildFileAST buildFileAST = parseBuildFile("include(2)");
     assertThat(buildFileAST.getStatements()).isEmpty();
-    assertContainsEvent("syntax error at '2'");
+    events.assertContainsEvent("syntax error at '2'");
   }
 
   @Test
   public void testRecursiveInclude() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
     Path buildFile = scratch.file("/foo/bar/BUILD",
         "include(\"//foo/bar:BUILD\")\n");
 
-    BuildFileAST.parseBuildFile(buildFile, getEventHandler(), locator, false);
-    assertContainsEvent("Recursive inclusion");
+    BuildFileAST.parseBuildFile(buildFile, events.reporter(), locator, false);
+    events.assertContainsEvent("Recursive inclusion");
   }
 
   @Test
   public void testParseErrorInclude() throws Exception {
-    setFailFast(false);
+    events.setFailFast(false);
 
     scratch.file("/foo/bar/file",
         "a = 2 + % 3\n"); // parse error
@@ -290,13 +311,14 @@
     parseBuildFile("include(\"//foo/bar:file\")");
 
     // Check the location is properly reported
-    Event event = assertContainsEvent("syntax error at '%': expected expression");
+    Event event = events.collector().iterator().next();
     assertEquals("/foo/bar/file:1:9", event.getLocation().print());
+    assertEquals("syntax error at '%': expected expression", event.getMessage());
   }
 
   @Test
   public void testNonExistentIncludeReported() throws Exception {
-    setFailFast(false);
+    events.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 0202124..a324b13 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 Environment newEnvironment() {
-    return newBuildEnvironment();
+  public EvaluationContext newEvaluationContext() {
+    return EvaluationContext.newBuildContext(getEventHandler());
   }
 
   // Test the API directly
@@ -104,41 +104,25 @@
 
   @Test
   public void testGetVariableNames() throws Exception {
-    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);
-    }
+    update("foo", "bar");
+    update("wiz", 3);
 
-    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());
+    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());
   }
 
   @Test
   public void testToString() throws Exception {
     update("subject", new StringLiteral("Hello, 'world'.", '\''));
     update("from", new StringLiteral("Java", '"'));
-    assertThat(getEnvironment().toString())
-        .startsWith("Environment(lexicalFrame=null, "
-            + "globalFrame=Frame[test]{\"from\": \"Java\", \"subject\": 'Hello, \\'world\\'.'}=>"
-            + "(BUILD){");
+    assertEquals("Environment{False -> false, None -> None, True -> true, from -> \"Java\", "
+        + "subject -> 'Hello, \\'world\\'.', }", getEnvironment().toString());
   }
 
   @Test
@@ -150,58 +134,4 @@
       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 83a55be..cf23858 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]}",
-        parseExpression("{x : x for x in [1, 2]}").toString());
+        evaluationContext.parseExpression("{x : x for x in [1, 2]}").toString());
     assertEquals("{x + 'a': x for x in [1, 2]}",
-        parseExpression("{x + 'a' : x for x in [1, 2]}").toString());
+        evaluationContext.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 e26234a..b2d661b 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,76 +35,48 @@
  * 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 Environment env;
-  protected Mutability mutability = Mutability.create("test");
+  
+  protected EvaluationContext evaluationContext;
 
   public EvaluationTestCase()   {
     createNewInfrastructure();
   }
-
+  
   @Before
   public void setUp() throws Exception {
     createNewInfrastructure();
-    env = newEnvironment();
+    evaluationContext = newEvaluationContext();
   }
 
-  /**
-   * 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 {
+  public EvaluationContext newEvaluationContext() throws Exception {
     if (testMode == null) {
       throw new IllegalArgumentException(
           "TestMode is null. Please set a Testmode via setMode() or set the "
-          + "Environment manually by overriding newEnvironment()");
+          + "evaluatenContext manually by overriding newEvaluationContext()");
     }
-    return testMode.createEnvironment(getEventHandler(), null);
+
+    return testMode.createContext(getEventHandler(), factory.getEnvironment());
   }
 
   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 Environment}
+   * Sets the specified {@code TestMode} and tries to create the appropriate {@code
+   * EvaluationContext}
+   * 
    * @param testMode
    * @throws Exception
    */
   protected void setMode(TestMode testMode) throws Exception {
     this.testMode = testMode;
-    env = newEnvironment();
+    evaluationContext = newEvaluationContext();
   }
 
   protected void enableSkylarkMode() throws Exception {
@@ -124,33 +96,32 @@
   }
 
   public Environment getEnvironment() {
-    return env;
+    return evaluationContext.getEnvironment();
   }
-
+  
   public boolean isSkylark() {
-    return env.isSkylark();
+    return evaluationContext.isSkylark();
   }
 
   protected List<Statement> parseFile(String... input) {
-    return env.parseFile(input);
+    return evaluationContext.parseFile(input);
   }
 
-  /** Parses an Expression from string without a supporting file */
   Expression parseExpression(String... input) {
-    return Parser.parseExpression(env.createLexer(input), getEventHandler());
+    return evaluationContext.parseExpression(input);
   }
 
   public EvaluationTestCase update(String varname, Object value) throws Exception {
-    env.update(varname, value);
+    evaluationContext.update(varname, value);
     return this;
   }
 
   public Object lookup(String varname) throws Exception {
-    return env.lookup(varname);
+    return evaluationContext.lookup(varname);
   }
 
   public Object eval(String... input) throws Exception {
-    return env.eval(input);
+    return evaluationContext.eval(input);
   }
 
   public void checkEvalError(String msg, String... input) throws Exception {
@@ -218,14 +189,15 @@
 
   /**
    * 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
@@ -246,7 +218,7 @@
       setup.registerUpdate(name, value);
       return this;
     }
-
+    
     /**
      * Evaluates two parameters and compares their results.
      * @param statement The statement to be evaluated
@@ -283,7 +255,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
@@ -437,7 +409,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 {
@@ -508,7 +480,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 5137b45..e0c074a 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,44 +32,42 @@
 import java.util.LinkedList;
 import java.util.List;
 
+
 /**
  *  Tests of parser behaviour.
  */
 @RunWith(JUnit4.class)
 public class ParserTest extends EvaluationTestCase {
 
-  Environment buildEnvironment;
+  EvaluationContext buildContext;
+  EvaluationContext buildContextWithPython;
 
   @Before
   @Override
   public void setUp() throws Exception {
     super.setUp();
-    buildEnvironment = newBuildEnvironment();
+    buildContext = EvaluationContext.newBuildContext(getEventHandler());
+    buildContextWithPython = EvaluationContext.newBuildContext(
+        getEventHandler(), new Environment(), /*parsePython*/true);
   }
 
   private Parser.ParseResult parseFileWithComments(String... input) {
-    return buildEnvironment.parseFileWithComments(input);
+    return buildContext.parseFileWithComments(input);
   }
-
-  /** Parses build code (not Skylark) */
   @Override
   protected List<Statement> parseFile(String... input) {
-    return buildEnvironment.parseFile(input);
+    return buildContext.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;
+    return buildContextWithPython.parseFile(input);
+  }
+  private List<Statement> parseFileForSkylark(String... input) {
+    return evaluationContext.parseFile(input);
+  }
+  private Statement parseStatement(String... input) {
+    return buildContext.parseStatement(input);
   }
 
-  /** 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(),
@@ -709,7 +707,7 @@
   @Test
   public void testParserContainsErrors() throws Exception {
     setFailFast(false);
-    parseFile("+");
+    parseStatement("+");
     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 a473f95..16bcb80 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' for type Mock",
+            + "\nwhile calling method 'string' on object of 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 7558b6c..86ad1fb 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 Environment newEnvironment() throws Exception {
-    return newSkylarkEnvironment().update("lazy", list);
+  public EvaluationContext newEvaluationContext() throws Exception {
+    return super.newEvaluationContext().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 b12f51b..c4bb7d8 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,6 +15,7 @@
 
 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;
@@ -41,9 +42,8 @@
 
   private final BufferedReader reader = new BufferedReader(
       new InputStreamReader(System.in, Charset.defaultCharset()));
-  private final Mutability mutability = Mutability.create("shell");
-  private final Environment env = Environment.builder(mutability)
-      .setSkylark().setGlobals(Environment.SKYLARK).setEventHandler(PRINT_HANDLER).build();
+  private final EvaluationContext ev =
+      SkylarkModules.newEvaluationContext(PRINT_HANDLER);
 
   public String read() {
     StringBuilder input = new StringBuilder();
@@ -70,7 +70,7 @@
     String input;
     while ((input = read()) != null) {
       try {
-        Object result = env.eval(input);
+        Object result = ev.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 3ebdf8d..57b341f 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 repr is read only", "repr = 1");
+    checkError("Variable rule is read only", "rule = 1");
   }
 
   @Test
@@ -300,8 +300,8 @@
   @Test
   public void testFunctionReturnsFunction() {
     parse(
-        "def rule(*, implementation): return None",
-        "def impl(ctx): 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 ea887f9..5ec7ac2 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,36 +14,31 @@
 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.Mutability;
+import com.google.devtools.build.lib.syntax.EvaluationContext;
 
 /**
  * Describes a particular testing mode by determining how the
- * appropriate {@code Environment} has to be created
+ * appropriate {@code EvaluationContext} has to be created
  */
 public abstract class TestMode {
-  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 BUILD = new TestMode() {
+    @Override
+    public EvaluationContext createContext(EventHandler eventHandler, Environment environment)
+        throws Exception {
+      return EvaluationContext.newBuildContext(eventHandler, environment);
+    }
+  };
 
-  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 static final TestMode SKYLARK = new TestMode() {
+    @Override
+    public EvaluationContext createContext(EventHandler eventHandler, Environment environment)
+        throws Exception {
+      return SkylarkModules.newEvaluationContext(eventHandler);
+    }
+  };
 
-  public abstract Environment createEnvironment(EventHandler eventHandler, Environment environment);
-}
+  public abstract EvaluationContext createContext(
+      EventHandler eventHandler, Environment environment) throws Exception;
+}
\ No newline at end of file
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 0feebe2..2fd1ffe 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,7 +30,6 @@
 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;
@@ -70,9 +69,9 @@
     resolver.addHeader(workspacePath.getPathString());
     ExternalPackage.Builder builder = new ExternalPackage.Builder(workspacePath,
         ruleClassProvider.getRunfilesPrefix());
-    try (Mutability mutability = Mutability.create("External Package %s", workspacePath)) {
-      new WorkspaceFactory(builder, ruleClassProvider, mutability)
-          .parse(ParserInputSource.create(workspacePath));
+    WorkspaceFactory parser = new WorkspaceFactory(builder, ruleClassProvider);
+    try {
+      parser.parse(ParserInputSource.create(workspacePath));
     } catch (IOException | InterruptedException e) {
       handler.handle(Event.error(Location.fromFile(workspacePath), e.getMessage()));
     }