diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Module.java b/src/main/java/com/google/devtools/build/lib/syntax/Module.java
index 2411fd2..96e5be8 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Module.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Module.java
@@ -21,7 +21,6 @@
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.Map;
-import java.util.Map.Entry;
 import java.util.Set;
 import javax.annotation.Nullable;
 
@@ -166,10 +165,13 @@
     if (parent == null) {
       return new Module(mutability);
     }
+    Preconditions.checkArgument(parent.mutability().isFrozen(), "parent frame must be frozen");
+    Preconditions.checkArgument(parent.universe == null);
+
     Map<String, Object> filteredBindings = new LinkedHashMap<>();
     Map<String, FlagGuardedValue> restrictedBindings = new LinkedHashMap<>();
 
-    for (Entry<String, Object> binding : parent.getTransitiveBindings().entrySet()) {
+    for (Map.Entry<String, Object> binding : parent.bindings.entrySet()) {
       if (binding.getValue() instanceof FlagGuardedValue) {
         FlagGuardedValue val = (FlagGuardedValue) binding.getValue();
         if (val.isObjectAccessibleUsingSemantics(semantics)) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
index b354107..d70f47d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
@@ -196,8 +196,6 @@
      * StarlarkThread}, and that {@code StarlarkThread}'s transitive hash code.
      */
     public Extension(StarlarkThread thread) {
-      // Legacy behavior: all symbols from the global Frame are exported (including symbols
-      // introduced by load).
       this(
           ImmutableMap.copyOf(thread.module.getExportedBindings()),
           thread.getTransitiveContentHashCode());
@@ -270,9 +268,16 @@
           continue;
         }
         if (value instanceof Depset) {
-          if (otherValue instanceof Depset
-              && ((Depset) value).toCollection().equals(((Depset) otherValue).toCollection())) {
-            continue;
+          if (otherValue instanceof Depset) {
+            // Widen to Object to avoid static checker warning
+            // about Collection.equals(Collection). We may assume
+            // these collections have the same class, even if we
+            // can't assume its equality is List-like or Set-like.
+            Object x = ((Depset) value).toCollection();
+            Object y = ((Depset) otherValue).toCollection();
+            if (x.equals(y)) {
+              continue;
+            }
           }
         } else if (value instanceof Dict) {
           if (otherValue instanceof Dict) {
@@ -605,21 +610,6 @@
       if (semantics == null) {
         throw new IllegalArgumentException("must call either setSemantics or useDefaultSemantics");
       }
-      if (parent != null) {
-        Preconditions.checkArgument(parent.mutability().isFrozen(), "parent frame must be frozen");
-        if (parent.universe != null) { // This code path doesn't happen in Bazel.
-
-          // Flatten the frame, ensure all builtins are in the same frame.
-          parent =
-              new Module(
-                  parent.mutability(),
-                  null /* parent */,
-                  parent.label,
-                  parent.getTransitiveBindings(),
-                  parent.restrictedBindings);
-        }
-      }
-
       // Filter out restricted objects from the universe scope. This cannot be done in-place in
       // creation of the input global universe scope, because this environment's semantics may not
       // have been available during its creation. Thus, create a new universe scope for 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 167be97..5b8d0ed 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
@@ -40,9 +40,9 @@
  * nodes. (In the future, it will attach additional information to functions to support lexical
  * scope, and even compilation of the trees to bytecode.) Validation errors are reported in the
  * analogous manner to scan/parse errors: for a StarlarkFile, they are appended to {@code
- * StarlarkFile.errors}; for an expression they will be [TODO(adonovan): implement] reported by an
- * SyntaxError exception. It is legal to validate a file that already contains scan/parse errors,
- * though it may lead to secondary validation errors.
+ * StarlarkFile.errors}; for an expression they are reported by an SyntaxError exception. It is
+ * legal to validate a file that already contains scan/parse errors, though it may lead to secondary
+ * validation errors.
  */
 // TODO(adonovan): make this class private. Call it through the EvalUtils facade.
 public final class ValidationEnvironment extends NodeVisitor {
@@ -71,6 +71,16 @@
    * use during name resolution.
    */
   public interface Module {
+
+    // TODO(adonovan): opt: for efficiency, turn this into a predicate, not an enumerable set,
+    // and look up bindings as they are needed, not preemptively.
+    // Otherwise we must do work proportional to the number of bindings in the
+    // environment, not the number of free variables of the file/expression.
+    //
+    // A single method will then suffice:
+    //   Scope resolve(String name) throws Undeclared
+    // This requires that the Module retain its semantics.
+
     /** Returns the set of names defined by this module. The caller must not modify the set. */
     Set<String> getNames();
 
@@ -492,9 +502,7 @@
     ValidationEnvironment venv =
         new ValidationEnvironment(errors, module, semantics, /*isBuildFile=*/ false);
 
-    venv.openBlock(Scope.Local); // needed?
     venv.visit(expr);
-    venv.closeBlock();
 
     if (!errors.isEmpty()) {
       throw new SyntaxError(errors);
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkThreadTest.java b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkThreadTest.java
index 12fb0d7..700d9e3 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkThreadTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkThreadTest.java
@@ -196,31 +196,6 @@
   }
 
   @Test
-  public void testVarOrderDeterminism() throws Exception {
-    Mutability parentMutability = Mutability.create("parent env");
-    StarlarkThread parentThread =
-        StarlarkThread.builder(parentMutability).useDefaultSemantics().build();
-    parentThread.getGlobals().put("a", 1);
-    parentThread.getGlobals().put("c", 2);
-    parentThread.getGlobals().put("b", 3);
-    Module parentFrame = parentThread.getGlobals();
-    parentMutability.freeze();
-    Mutability mutability = Mutability.create("testing");
-    StarlarkThread thread =
-        StarlarkThread.builder(mutability).useDefaultSemantics().setGlobals(parentFrame).build();
-    thread.getGlobals().put("x", 4);
-    thread.getGlobals().put("z", 5);
-    thread.getGlobals().put("y", 6);
-    // The order just has to be deterministic, but for definiteness this test spells out the exact
-    // order returned by the implementation: parent frame before current environment, and bindings
-    // within a frame ordered by when they were added.
-    assertThat(thread.getVariableNames()).containsExactly("a", "c", "b", "x", "z", "y").inOrder();
-    assertThat(thread.getGlobals().getTransitiveBindings())
-        .containsExactly("a", 1, "c", 2, "b", 3, "x", 4, "z", 5, "y", 6)
-        .inOrder();
-  }
-
-  @Test
   public void testTransitiveHashCodeDeterminism() throws Exception {
     // As a proxy for determinism, test that changing the order of imports doesn't change the hash
     // code (within any one execution).