Skylark: Define dict iteration order (sorted by key).

--
MOS_MIGRATED_REVID=88924033

2 files changed, 12 insertions, 7 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
index bb40ac8fce..3156881db4 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
@@ -52,6 +52,7 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.TreeMap;
 import java.util.TreeSet;
 import java.util.concurrent.ExecutionException;
 import java.util.regex.Matcher;
@@ -484,7 +485,8 @@ public class MethodLibrary {
     @Override
     public Object call(Object self, FuncallExpression ast, Environment env)
         throws EvalException, InterruptedException {
-      Map<?, ?> dict = (Map<?, ?>) self;
+      // Use a TreeMap to ensure consistent ordering.
+      Map<?, ?> dict = new TreeMap<>((Map<?, ?>) self);
       return convert(dict.values(), env, ast.getLocation());
     }
   };
@@ -495,7 +497,8 @@ public class MethodLibrary {
     @Override
     public Object call(Object self, FuncallExpression ast, Environment env)
         throws EvalException, InterruptedException {
-      Map<?, ?> dict = (Map<?, ?>) self;
+      // Use a TreeMap to ensure consistent ordering.
+      Map<?, ?> dict = new TreeMap<>((Map<?, ?>) self);
       List<Object> list = Lists.newArrayListWithCapacity(dict.size());
       for (Map.Entry<?, ?> entries : dict.entrySet()) {
         List<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 4c5c23d2d1..c4c3b0822f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -21,6 +21,7 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -597,12 +598,14 @@ public abstract class EvalUtils {
   }
 
   @SuppressWarnings("unchecked")
-  public static Collection<Object> toCollection(Object o, Location loc) throws EvalException {
+  public static Collection<?> toCollection(Object o, Location loc) throws EvalException {
     if (o instanceof Collection) {
       return (Collection<Object>) o;
     } else if (o instanceof Map<?, ?>) {
+      Map<Comparable<?>, Object> dict = (Map<Comparable<?>, Object>) o;
       // For dictionaries we iterate through the keys only
-      return ((Map<Object, Object>) o).keySet();
+      // For determinism, we sort the keys.
+      return Ordering.natural().sortedCopy(dict.keySet());
     } else if (o instanceof SkylarkNestedSet) {
       return ((SkylarkNestedSet) o).toCollection();
     } else {
@@ -612,7 +615,7 @@ public abstract class EvalUtils {
   }
 
   @SuppressWarnings("unchecked")
-  public static Iterable<Object> toIterable(Object o, Location loc) throws EvalException {
+  public static Iterable<?> toIterable(Object o, Location loc) throws EvalException {
     if (o instanceof String) {
       // This is not as efficient as special casing String in for and dict and list comprehension
       // statements. However this is a more unified way.
@@ -622,8 +625,7 @@ public abstract class EvalUtils {
     } else if (o instanceof Iterable) {
       return (Iterable<Object>) o;
     } else if (o instanceof Map<?, ?>) {
-      // For dictionaries we iterate through the keys only
-      return ((Map<Object, Object>) o).keySet();
+      return toCollection(o, loc);
     } else {
       throw new EvalException(loc,
           "type '" + getDataTypeName(o) + "' is not an iterable");