Environment guarantees determinism when retrieving its bindings
Added a little javadoc and tests.
RELNOTES: None
PiperOrigin-RevId: 185569985
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 4132f4e..858ae01 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.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 @@
/** 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 cafa8a0..73d79a0 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.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 @@
@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 @@
/**
* 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 @@
/**
* 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 @@
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 @@
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 @@
return transitiveContentHashCode;
}
+ /** Retrieves all bindings, in a deterministic order. */
public ImmutableMap<String, Object> getBindings() {
return bindings;
}
@@ -507,7 +514,7 @@
* 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 @@
// parent?
lexicalFrame = new Frame(mutability(), null);
globalFrame = globals;
- knownGlobalVariables = new HashSet<>();
+ knownGlobalVariables = new LinkedHashSet<>();
}
/**
@@ -592,14 +599,12 @@
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 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 @@
}
/**
- * @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 @@
}
/**
- * @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 @@
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 @@
}
}
+ /**
+ * 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 e6c0bd1..3cd9099 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 @@
}
@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"),
