Environment guarantees determinism when retrieving its bindings

Added a little javadoc and tests.

RELNOTES: None
PiperOrigin-RevId: 185569985

3 files changed, 80 insertions, 22 deletions

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 4132f4e58e..858ae01f96 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
@@ -25,7 +25,6 @@ import com.google.common.cache.LoadingCache;
 import com.google.common.collect.ImmutableBiMap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -827,8 +826,7 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
 
   /** Returns all skylark objects in global scope for this RuleClassProvider. */
   public Map<String, Object> getTransitiveGlobalBindings() {
-    // TODO(brandjon): Remove unordered hash maps from Environment so we don't have to sort here.
-    return ImmutableSortedMap.copyOf(globals.getTransitiveBindings());
+    return globals.getTransitiveBindings();
   }
 
   /** Returns all registered {@link BuildConfiguration.Fragment} classes. */
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 cafa8a0abc..73d79a0b36 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
@@ -31,9 +31,8 @@ import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.SpellChecker;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
@@ -125,7 +124,8 @@ public final class Environment implements Freezable {
     @Nullable
     private Label label;
 
-    private final Map<String, Object> bindings;
+    /** Bindings are maintained in order of creation. */
+    private final LinkedHashMap<String, Object> bindings;
 
     /** Constructs an uninitialized instance; caller must call {@link #initialize} before use. */
     public Frame() {
@@ -222,6 +222,9 @@ public final class Environment implements Freezable {
     /**
      * Returns a map of direct bindings of this {@code Frame}, ignoring parents.
      *
+     * <p>The bindings are returned in a deterministic order (for a given sequence of initial values
+     * and updates).
+     *
      * <p>For efficiency an unmodifiable view is returned. Callers should assume that the view is
      * invalidated by any subsequent modification to the {@code Frame}'s bindings.
      */
@@ -233,16 +236,19 @@ public final class Environment implements Freezable {
     /**
      * Returns a map containing all bindings of this {@code Frame} and of its transitive parents,
      * taking into account shadowing precedence.
+     *
+     * <p>The bindings are returned in a deterministic order (for a given sequence of initial values
+     * and updates).
      */
     public Map<String, Object> getTransitiveBindings() {
       checkInitialized();
       // Can't use ImmutableMap.Builder because it doesn't allow duplicates.
-      HashMap<String, Object> collectedBindings = new HashMap<>();
+      LinkedHashMap<String, Object> collectedBindings = new LinkedHashMap<>();
       accumulateTransitiveBindings(collectedBindings);
       return collectedBindings;
     }
 
-    private void accumulateTransitiveBindings(Map<String, Object> accumulator) {
+    private void accumulateTransitiveBindings(LinkedHashMap<String, Object> accumulator) {
       checkInitialized();
       // Put parents first, so child bindings take precedence.
       if (parent != null) {
@@ -328,7 +334,7 @@ public final class Environment implements Freezable {
     final Frame globalFrame;
 
     /** The set of known global variables of the caller. */
-    @Nullable final Set<String> knownGlobalVariables;
+    @Nullable final LinkedHashSet<String> knownGlobalVariables;
 
     Continuation(
         Continuation continuation,
@@ -336,7 +342,7 @@ public final class Environment implements Freezable {
         FuncallExpression caller,
         Frame lexicalFrame,
         Frame globalFrame,
-        Set<String> knownGlobalVariables) {
+        LinkedHashSet<String> knownGlobalVariables) {
       this.continuation = continuation;
       this.function = function;
       this.caller = caller;
@@ -377,6 +383,7 @@ public final class Environment implements Freezable {
       return transitiveContentHashCode;
     }
 
+    /** Retrieves all bindings, in a deterministic order. */
     public ImmutableMap<String, Object> getBindings() {
       return bindings;
     }
@@ -507,7 +514,7 @@ public final class Environment implements Freezable {
    * 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;
+  @Nullable private LinkedHashSet<String> knownGlobalVariables;
 
   /**
    * When in a lexical (Skylark) frame, this lists the names of the functions in the call stack.
@@ -537,7 +544,7 @@ public final class Environment implements Freezable {
     // parent?
     lexicalFrame = new Frame(mutability(), null);
     globalFrame = globals;
-    knownGlobalVariables = new HashSet<>();
+    knownGlobalVariables = new LinkedHashSet<>();
   }
 
   /**
@@ -592,14 +599,12 @@ public final class Environment implements Freezable {
     return dynamicFrame.mutability();
   }
 
-  /** @return the current Frame, in which variable side-effects happen. */
+  /** Returns the current Frame, in which variable side-effects happen. */
   private Frame currentFrame() {
     return isGlobal() ? globalFrame : lexicalFrame;
   }
 
-  /**
-   * @return the global variables for the Environment (not including dynamic bindings).
-   */
+  /** Returns the global variables for the Environment (not including dynamic bindings). */
   public Frame getGlobals() {
     return globalFrame;
   }
@@ -755,7 +760,7 @@ public final class Environment implements Freezable {
     public Environment build() {
       Preconditions.checkArgument(!mutability.isFrozen());
       if (parent != null) {
-        Preconditions.checkArgument(parent.mutability().isFrozen());
+        Preconditions.checkArgument(parent.mutability().isFrozen(), "parent frame must be frozen");
       }
       Frame globalFrame = new Frame(mutability, parent);
       Frame dynamicFrame = new Frame(mutability, null);
@@ -907,7 +912,7 @@ public final class Environment implements Freezable {
   }
 
   /**
-   * @return the value from the environment whose name is "varname" if it exists, otherwise null.
+   * Returns the value from the environment whose name is "varname" if it exists, otherwise null.
    */
   public Object lookup(String varname) {
     // Lexical frame takes precedence, then globals, then dynamics.
@@ -932,8 +937,8 @@ public final class Environment implements Freezable {
   }
 
   /**
-   * @return true if varname is a known global variable,
-   * because it has been read in the context of the current function.
+   * Returns true if varname is a known global variable (i.e., it has been read in the context of
+   * the current function).
    */
   boolean isKnownGlobalVariable(String varname) {
     return knownGlobalVariables != null && knownGlobalVariables.contains(varname);
@@ -947,9 +952,12 @@ public final class Environment implements Freezable {
     eventHandler.handle(event);
   }
 
-  /** Returns a set of all names of variables that are accessible in this {@code Environment}. */
+  /**
+   * Returns a set of all names of variables that are accessible in this {@code Environment}, in a
+   * deterministic order.
+   */
   public Set<String> getVariableNames() {
-    Set<String> vars = new HashSet<>();
+    LinkedHashSet<String> vars = new LinkedHashSet<>();
     if (lexicalFrame != null) {
       vars.addAll(lexicalFrame.getTransitiveBindings().keySet());
     }
@@ -1016,6 +1024,10 @@ public final class Environment implements Freezable {
     }
   }
 
+  /**
+   * Computes a deterministic hash for the given base hash code and extension map (the map's order
+   * does not matter).
+   */
   private static String computeTransitiveContentHashCode(
       @Nullable String baseHashCode, Map<String, Extension> importedExtensions) {
     // Calculate a new hash from the hash of the loaded Extension-s.
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 e6c0bd11e8..3cd9099b41 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
@@ -274,6 +274,54 @@ public class EnvironmentTest extends EvaluationTestCase {
   }
 
   @Test
+  public void testVarOrderDeterminism() throws Exception {
+    Mutability parentMutability = Mutability.create("parent env");
+    Environment parentEnv = Environment.builder(parentMutability)
+        .useDefaultSemantics()
+        .build();
+    parentEnv.update("a", 1);
+    parentEnv.update("c", 2);
+    parentEnv.update("b", 3);
+    Environment.Frame parentFrame = parentEnv.getGlobals();
+    parentMutability.freeze();
+    Mutability mutability = Mutability.create("testing");
+    Environment env = Environment.builder(mutability)
+        .useDefaultSemantics()
+        .setGlobals(parentFrame)
+        .build();
+    env.update("x", 4);
+    env.update("z", 5);
+    env.update("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(env.getVariableNames())
+        .containsExactly("a", "c", "b", "x", "z", "y").inOrder();
+    assertThat(env.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).
+    Extension a = new Extension(ImmutableMap.of(), "a123");
+    Extension b = new Extension(ImmutableMap.of(), "b456");
+    Extension c = new Extension(ImmutableMap.of(), "c789");
+    Environment env1 = Environment.builder(Mutability.create("testing1"))
+        .useDefaultSemantics()
+        .setImportedExtensions(ImmutableMap.of("a", a, "b", b, "c", c))
+        .setFileContentHashCode("z")
+        .build();
+    Environment env2 = Environment.builder(Mutability.create("testing2"))
+        .useDefaultSemantics()
+        .setImportedExtensions(ImmutableMap.of("c", c, "b", b, "a", a))
+        .setFileContentHashCode("z")
+        .build();
+    assertThat(env1.getTransitiveContentHashCode()).isEqualTo(env2.getTransitiveContentHashCode());
+  }
+
+  @Test
   public void testExtensionEqualityDebugging_RhsIsNull() {
     assertCheckStateFailsWithMessage(
         new Extension(ImmutableMap.of(), "abc"),