Revert "Revert "Workaround bogus TreeMap Comparators.""

An app that is popular among testers is still broken.
This CL re-establishes the work-around to give the
app a little bit of time to update their dependencies
to the fixed versions.

This reverts commit 3733bc930b4f8a02b278dde1109d0cd42f7c4c08.

By reverting that revert, this CL re-applies the changes from
commit 78562a12977fc4d81cd31e7c5af05d66bb701ccd

*** THIS CHANGE IS TEMPORARY AND WILL LIKELY BE ***
*** REVERTED BEFORE THE NEXT ANDROID RELEASE    ***

Test: cts-tradefed run cts -m CtsLibcoreTestCases -a arm64-v8a
Test: these tests from guava-testlib 21.0-rc2's TestsForMapsInJavaUtil:
      - testsForTreeMapNatural()
      - testsForTreeMapWithComparator()

Bug: 34084348

Change-Id: I3d120f00bf5a14e89cf3d50c3931557191aa5f37
(cherry picked from commit 48b8a257f78d6def94079b592000f9f5ff17fb3c)
diff --git a/luni/src/test/java/libcore/java/util/TreeMapTest.java b/luni/src/test/java/libcore/java/util/TreeMapTest.java
index bd31a61..9384d56 100644
--- a/luni/src/test/java/libcore/java/util/TreeMapTest.java
+++ b/luni/src/test/java/libcore/java/util/TreeMapTest.java
@@ -612,6 +612,33 @@
         return bound == '[' || bound == '(';
     }
 
+    // http://b//26336181
+    //
+    // Note that this is only worth working around because these bogus comparators worked
+    // somewhat-fine on M and below provided that :
+    //
+    // (1) put was called with distinct elements (i.e, with no two elements equal() to each other)
+    // (2) get or get-like methods are never called
+    //
+    // These comparators are clearly bogus but are somewhat common.
+    public void testTreeMapWithBogusComparator() {
+        TreeMap<String, String> treeMap = new TreeMap<String, String>(
+                new Comparator<String>() {
+                    @Override
+                    public int compare(String o1, String o2) {
+                        if (o1.equals(o2)) {
+                            throw new IllegalArgumentException("Expected unequal elements");
+                        }
+
+                        return o1.compareTo(o2);
+                    }
+                }
+        );
+
+        treeMap.put("candy", "floss");
+        treeMap.put("cheddar", "cheese");
+    }
+
     public void test_spliterator_keySet() {
         TreeMap<String, String> treeMap = new TreeMap<>();
         treeMap.put("a", "1");
diff --git a/ojluni/src/main/java/java/util/TreeMap.java b/ojluni/src/main/java/java/util/TreeMap.java
index b1e7e21..6b18547 100644
--- a/ojluni/src/main/java/java/util/TreeMap.java
+++ b/ojluni/src/main/java/java/util/TreeMap.java
@@ -536,7 +536,31 @@
     public V put(K key, V value) {
         TreeMapEntry<K,V> t = root;
         if (t == null) {
-            compare(key, key); // type (and possibly null) check
+            // We could just call compare(key, key) for its side effect of checking the type and
+            // nullness of the input key. However, several applications seem to have written comparators
+            // that only expect to be called on elements that aren't equal to each other (after
+            // making assumptions about the domain of the map). Clearly, such comparators are bogus
+            // because get() would never work, but TreeSets are frequently used for sorting a set
+            // of distinct elements.
+            //
+            // As a temporary work around, we perform the null & instanceof checks by hand so that
+            // we can guarantee that elements are never compared against themselves.
+            //
+            // compare(key, key);
+            //
+            // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
+            if (comparator != null) {
+                if (key == null) {
+                    comparator.compare(key, key);
+                }
+            } else {
+                if (key == null) {
+                    throw new NullPointerException("key == null");
+                } else if (!(key instanceof Comparable)) {
+                    throw new ClassCastException(
+                            "Cannot cast" + key.getClass().getName() + " to Comparable.");
+                }
+            }
 
             root = new TreeMapEntry<>(key, value, null);
             size = 1;