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

--
MOS_MIGRATED_REVID=88924033
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 4c5c23d..c4c3b08 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.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 @@
   }
 
   @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 @@
   }
 
   @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 @@
     } 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");