Allow dicts to contain non-comparable objects as keys

RELNOTES: Skylark dicts internally don't rely on keys order anymore and accept
any hashable values (i.e. structs with immutable values) as keys. Iteration order of dictionaries is no longer specified.

--
PiperOrigin-RevId: 141055080
MOS_MIGRATED_REVID=141055080
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 c83ed98..c95df57 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
@@ -16,6 +16,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 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.concurrent.ThreadSafety.Immutable;
@@ -72,6 +73,9 @@
       o1 = SkylarkType.convertToSkylark(o1, /*env=*/ null);
       o2 = SkylarkType.convertToSkylark(o2, /*env=*/ null);
 
+      if (o1 instanceof ClassObject && o2 instanceof ClassObject) {
+        throw new ComparisonException("Cannot compare structs");
+      }
       if (o1 instanceof SkylarkNestedSet && o2 instanceof SkylarkNestedSet) {
         throw new ComparisonException("Cannot compare sets");
       }
@@ -312,6 +316,15 @@
       return ((SkylarkList) o).getImmutableList();
     } else if (o instanceof Map) {
       // For dictionaries we iterate through the keys only
+      if (o instanceof SkylarkDict) {
+        // SkylarkDicts handle ordering themselves
+        SkylarkDict<?, ?> dict = (SkylarkDict) o;
+        List<Object> list = Lists.newArrayListWithCapacity(dict.size());
+        for (Map.Entry<?, ?> entries : dict.entrySet()) {
+          list.add(entries.getKey());
+        }
+        return  ImmutableList.copyOf(list);
+      }
       // For determinism, we sort the keys.
       try {
         return SKYLARK_COMPARATOR.sortedCopy(((Map<?, ?>) o).keySet());
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 5748f63..7ca5793 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -801,7 +801,7 @@
     ImmutableList.Builder<Object> posargs = new ImmutableList.Builder<>();
     // We copy this into an ImmutableMap in the end, but we can't use an ImmutableMap.Builder, or
     // we'd still have to have a HashMap on the side for the sake of properly handling duplicates.
-    Map<String, Object> kwargs = new HashMap<>();
+    Map<String, Object> kwargs = new LinkedHashMap<>();
     BaseFunction function = checkCallable(funcValue, getLocation());
     evalArguments(posargs, kwargs, env);
     return function.call(posargs.build(), ImmutableMap.copyOf(kwargs), this, env);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index b2a33c5..fd79759 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -1314,12 +1314,7 @@
             + "<code>popitem()</code> is useful to destructively iterate over a dictionary, "
             + "as often used in set algorithms. "
             + "If the dictionary is empty, calling <code>popitem()</code> fails. "
-            + "Note that in Skylark, as opposed to Python, "
-            + "the dictionary keys are actually sorted, "
-            + "and it is deterministic which pair will returned: that with the first key, "
-            + "according to the builtin total order. "
-            + "Thus if keys are numbers, the smallest key is returned first; "
-            + "if they are lists or strings, they are compared lexicographically, etc.",
+            + "It is deterministic which pair is returned.",
     parameters = {
       @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")
     },
@@ -1432,9 +1427,9 @@
     objectType = SkylarkDict.class,
     returnType = MutableList.class,
     doc =
-        "Returns the list of values. Dictionaries are always sorted by their keys:"
+        "Returns the list of values:"
             + "<pre class=\"language-python\">"
-            + "{2: \"a\", 4: \"b\", 1: \"c\"}.values() == [\"c\", \"a\", \"b\"]</pre>\n",
+            + "{2: \"a\", 4: \"b\", 1: \"c\"}.values() == [\"a\", \"b\", \"c\"]</pre>\n",
     parameters = {@Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
     useEnvironment = true
   )
@@ -1450,9 +1445,9 @@
     objectType = SkylarkDict.class,
     returnType = MutableList.class,
     doc =
-        "Returns the list of key-value tuples. Dictionaries are always sorted by their keys:"
+        "Returns the list of key-value tuples:"
             + "<pre class=\"language-python\">"
-            + "{2: \"a\", 4: \"b\", 1: \"c\"}.items() == [(1, \"c\"), (2, \"a\"), (4, \"b\")]"
+            + "{2: \"a\", 4: \"b\", 1: \"c\"}.items() == [(2, \"a\"), (4, \"b\"), (1, \"c\")]"
             + "</pre>\n",
     parameters = {@Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
     useEnvironment = true
@@ -1470,8 +1465,8 @@
 
   @SkylarkSignature(name = "keys", objectType = SkylarkDict.class,
       returnType = MutableList.class,
-      doc = "Returns the list of keys. Dictionaries are always sorted by their keys:"
-          + "<pre class=\"language-python\">{2: \"a\", 4: \"b\", 1: \"c\"}.keys() == [1, 2, 4]"
+      doc = "Returns the list of keys:"
+          + "<pre class=\"language-python\">{2: \"a\", 4: \"b\", 1: \"c\"}.keys() == [2, 4, 1]"
           + "</pre>\n",
       parameters = {
         @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
@@ -1482,9 +1477,11 @@
     @SuppressWarnings("unchecked")
     public MutableList<?> invoke(SkylarkDict<?, ?> self,
         Environment env) throws EvalException {
-      return new MutableList(
-          Ordering.natural().sortedCopy((Set<Comparable<?>>) (Set<?>) self.keySet()),
-          env);
+      List<Object> list = Lists.newArrayListWithCapacity(self.size());
+      for (Map.Entry<?, ?> entries : self.entrySet()) {
+        list.add(entries.getKey());
+      }
+      return new MutableList(list, env);
     }
   };
 
@@ -1678,8 +1675,7 @@
     doc =
         "Creates a <a href=\"#modules.dict\">dictionary</a> from an optional positional "
             + "argument and an optional set of keyword arguments. Values from the keyword argument "
-            + "will overwrite values from the positional argument if a key appears multiple times. "
-            + "Dictionaries are always sorted by their keys",
+            + "will overwrite values from the positional argument if a key appears multiple times.",
     parameters = {
       @Param(
         name = "args",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
index 6ae2ae5..af75d43 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
@@ -18,8 +18,8 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableMap;
+import java.util.LinkedHashMap;
 import java.util.Map;
-import java.util.TreeMap;
 import javax.annotation.Nullable;
 
 /**
@@ -38,7 +38,7 @@
     + "d = {\"a\" : 1} + {\"b\" : 2}   # d == {\"a\" : 1, \"b\" : 2}\n"
     + "d += {\"c\" : 3}              # d == {\"a\" : 1, \"b\" : 2, \"c\" : 3}\n"
     + "d = d + {\"c\" : 5}           # d == {\"a\" : 1, \"b\" : 2, \"c\" : 5}</pre>"
-    + "Iterating on a dict is equivalent to iterating on its keys (in sorted order).<br>"
+    + "Iterating on a dict is equivalent to iterating on its keys (order is not specified).<br>"
     + "Dicts support the <code>in</code> operator, testing membership in the keyset of the dict. "
     + "Example:<br>"
     + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
@@ -46,7 +46,7 @@
 public final class SkylarkDict<K, V>
     extends MutableMap<K, V> implements Map<K, V>, SkylarkIndexable {
 
-  private final TreeMap<K, V> contents = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
+  private final LinkedHashMap<K, V> contents = new LinkedHashMap<>();
 
   private final Mutability mutability;
 
@@ -139,7 +139,7 @@
 
   /** @return the first key in the dict */
   K firstKey() {
-    return contents.firstKey();
+    return contents.entrySet().iterator().next().getKey();
   }
 
   /**