Fix serialization of reverse-ordered TreeSets.

Bug: http://b/5552608
Change-Id: I949c2ab11fea391987217dfd5f8dad0cd3fe3fbf

3 files changed, 166 insertions, 30 deletions

diff --git a/luni/src/main/java/java/util/TreeMap.java b/luni/src/main/java/java/util/TreeMap.java
index 7809110..0cd94dc 100644
--- a/luni/src/main/java/java/util/TreeMap.java
+++ b/luni/src/main/java/java/util/TreeMap.java
@@ -1364,11 +1364,12 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         }
 
         public Comparator<? super K> comparator() {
-          if (ascending) {
-            return TreeMap.this.comparator();
-          } else {
-            return Collections.reverseOrder(comparator);
-          }
+            Comparator<? super K> forward = TreeMap.this.comparator();
+            if (ascending) {
+                return forward;
+            } else {
+                return Collections.reverseOrder(forward);
+            }
         }
 
         /*
@@ -1665,7 +1666,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     private static final long serialVersionUID = 919286545866124006L;
 
     private void writeObject(ObjectOutputStream stream) throws IOException {
-        stream.putFields().put("comparator", comparator != NATURAL_ORDER ? comparator : null);
+        stream.putFields().put("comparator", comparator());
         stream.writeFields();
         stream.writeInt(size);
         for (Map.Entry<K, V> entry : entrySet()) {
diff --git a/luni/src/test/java/libcore/java/util/TreeMapTest.java b/luni/src/test/java/libcore/java/util/TreeMapTest.java
index 4a048f5..9e92b0f 100644
--- a/luni/src/test/java/libcore/java/util/TreeMapTest.java
+++ b/luni/src/test/java/libcore/java/util/TreeMapTest.java
@@ -30,7 +30,7 @@ import junit.framework.TestCase;
 public class TreeMapTest extends TestCase {
 
     /**
-     * Test that the entrySet() method produces correctly mutable Entrys.
+     * Test that the entrySet() method produces correctly mutable entries.
      */
     public void testEntrySetSetValue() {
         TreeMap<String, String> map = new TreeMap<String, String>();
@@ -38,7 +38,7 @@ public class TreeMapTest extends TestCase {
         map.put("B", "b");
         map.put("C", "c");
 
-        Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
+        Iterator<Entry<String, String>> iterator = map.entrySet().iterator();
         Entry<String, String> entryA = iterator.next();
         assertEquals("a", entryA.setValue("x"));
         assertEquals("x", entryA.getValue());
@@ -54,8 +54,8 @@ public class TreeMapTest extends TestCase {
     }
 
     /**
-     * Test that the entrySet() method of a submap produces correctly mutable Entrys that
-     * propagate changes to the original map.
+     * Test that the entrySet() method of a sub map produces correctly mutable
+     * entries that propagate changes to the original map.
      */
     public void testSubMapEntrySetSetValue() {
         TreeMap<String, String> map = new TreeMap<String, String>();
@@ -65,7 +65,7 @@ public class TreeMapTest extends TestCase {
         map.put("D", "d");
         NavigableMap<String, String> subMap = map.subMap("A", true, "C", true);
 
-        Iterator<Entry<String,String>> iterator = subMap.entrySet().iterator();
+        Iterator<Entry<String, String>> iterator = subMap.entrySet().iterator();
         Entry<String, String> entryA = iterator.next();
         assertEquals("a", entryA.setValue("x"));
         assertEquals("x", entryA.getValue());
@@ -96,7 +96,7 @@ public class TreeMapTest extends TestCase {
     }
 
     /**
-     * Test that an Entry given by any method except entrySet() of a submap is immutable.
+     * Test that an Entry given by any method except entrySet() of a sub map is immutable.
      */
     public void testExceptionsOnSubMapSetValue() {
         TreeMap<String, String> map = new TreeMap<String, String>();
@@ -279,7 +279,7 @@ public class TreeMapTest extends TestCase {
                 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
                 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
                 + "e02000078707704000000027400016171007e00057400016271007e000678";
-        TreeMap<String,String> map = new TreeMap<String, String>(
+        TreeMap<String, String> map = new TreeMap<String, String>(
                 String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
@@ -290,7 +290,7 @@ public class TreeMapTest extends TestCase {
         }.test();
     }
 
-    public void testSubmapSerialization() {
+    public void testSubMapSerialization() {
         String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
                 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
                 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
@@ -304,25 +304,25 @@ public class TreeMapTest extends TestCase {
                 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
                 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
                 + "07e000d78";
-        TreeMap<String,String> map = new TreeMap<String, String>(
+        TreeMap<String, String> map = new TreeMap<String, String>(
                 String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
         map.put("c", "c");
         map.put("d", "d");
-        SortedMap<String, String> submap = map.subMap("a", "c");
-        new SerializableTester<SortedMap<String, String>>(submap, s) {
+        SortedMap<String, String> subMap = map.subMap("a", "c");
+        new SerializableTester<SortedMap<String, String>>(subMap, s) {
             @Override protected void verify(SortedMap<String, String> deserialized) {
                 try {
                     deserialized.put("e", "e");
                     fail();
-                } catch (IllegalArgumentException e) {
+                } catch (IllegalArgumentException expected) {
                 }
             }
         }.test();
     }
 
-    public void testNavigableSubmapSerialization() {
+    public void testNavigableSubMapSerialization() {
         String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
                 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
                 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
@@ -336,19 +336,19 @@ public class TreeMapTest extends TestCase {
                 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
                 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
                 + "07e000d78";
-        TreeMap<String,String> map = new TreeMap<String, String>(
+        TreeMap<String, String> map = new TreeMap<String, String>(
                 String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
         map.put("c", "c");
         map.put("d", "d");
-        SortedMap<String, String> submap = map.subMap("a", false, "c", true);
-        new SerializableTester<SortedMap<String, String>>(submap, s) {
+        SortedMap<String, String> subMap = map.subMap("a", false, "c", true);
+        new SerializableTester<SortedMap<String, String>>(subMap, s) {
             @Override protected void verify(SortedMap<String, String> deserialized) {
                 try {
                     deserialized.put("e", "e");
                     fail();
-                } catch (IllegalArgumentException e) {
+                } catch (IllegalArgumentException expected) {
                 }
             }
         }.test();
@@ -370,7 +370,7 @@ public class TreeMapTest extends TestCase {
                 + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657"
                 + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707"
                 + "1007e0001787071007e0009";
-        TreeMap<String,String> map = new TreeMap<String, String>(
+        TreeMap<String, String> map = new TreeMap<String, String>(
                 String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
@@ -388,7 +388,7 @@ public class TreeMapTest extends TestCase {
                 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
                 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
                 + "e02000078707704000000027400016171007e00057400016271007e000678";
-        TreeMap<String,String> map = new TreeMap<String, String>(
+        TreeMap<String, String> map = new TreeMap<String, String>(
                 String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
@@ -402,7 +402,7 @@ public class TreeMapTest extends TestCase {
     /**
      * On JDK5, this fails with a NullPointerException after deserialization!
      */
-    public void testJava5SubmapSerialization() {
+    public void testJava5SubMapSerialization() {
         String s = "aced0005737200186a6176612e7574696c2e547265654d6170245375624d6170"
                 + "a5818343a213c27f0200055a000966726f6d53746172745a0005746f456e644c0"
                 + "00766726f6d4b65797400124c6a6176612f6c616e672f4f626a6563743b4c0006"
@@ -414,18 +414,18 @@ public class TreeMapTest extends TestCase {
                 + "261746f7277035c7d5c50e5ce020000787077040000000471007e000471007e00"
                 + "047400016271007e000a7400016371007e000b7400016471007e000c7871007e0"
                 + "00b";
-        TreeMap<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
+        TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
         map.put("a", "a");
         map.put("b", "b");
         map.put("c", "c");
         map.put("d", "d");
-        SortedMap<String, String> submap = map.subMap("a", "c");
-        new SerializableTester<SortedMap<String, String>>(submap, s) {
+        SortedMap<String, String> subMap = map.subMap("a", "c");
+        new SerializableTester<SortedMap<String, String>>(subMap, s) {
             @Override protected void verify(SortedMap<String, String> deserialized) {
                 try {
                     deserialized.put("e", "e");
                     fail();
-                } catch (IllegalArgumentException e) {
+                } catch (IllegalArgumentException expected) {
                 }
             }
         }.test();
diff --git a/luni/src/test/java/libcore/java/util/TreeSetTest.java b/luni/src/test/java/libcore/java/util/TreeSetTest.java
new file mode 100644
index 0000000..251864c
--- /dev/null
+++ b/luni/src/test/java/libcore/java/util/TreeSetTest.java
@@ -0,0 +1,135 @@
+/*
+ * Copyright (C) 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package libcore.java.util;
+
+import java.util.NavigableSet;
+import java.util.SortedSet;
+import java.util.TreeSet;
+import junit.framework.TestCase;
+
+public final class TreeSetTest extends TestCase {
+
+    public void testEmptySetSerialization() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b03000078707077040000000078";
+        TreeSet<String> set = new TreeSet<String>();
+        new SerializableTester<TreeSet<String>>(set, s).test();
+    }
+
+    public void testSerializationWithComparator() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b03000078707372002a6a6176612e6c616e672e537472696e672443617365496"
+                + "e73656e736974697665436f6d70617261746f7277035c7d5c50e5ce0200007870"
+                + "770400000002740001617400016278";
+        TreeSet<String> set = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
+        set.add("a");
+        set.add("b");
+        new SerializableTester<NavigableSet<String>>(set, s) {
+            @Override protected void verify(NavigableSet<String> deserialized) {
+                assertEquals(0, deserialized.comparator().compare("X", "x"));
+            }
+        }.test();
+    }
+
+    public void testSubSetSerialization() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b03000078707372002a6a6176612e6c616e672e537472696e672443617365496"
+                + "e73656e736974697665436f6d70617261746f7277035c7d5c50e5ce0200007870"
+                + "770400000002740001617400016278";
+        TreeSet<String> set = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
+        set.add("a");
+        set.add("b");
+        set.add("c");
+        set.add("d");
+        final SortedSet<String> subSet = set.subSet("a", "c");
+        new SerializableTester<SortedSet<String>>(subSet, s) {
+            @Override protected void verify(SortedSet<String> deserialized) {
+                assertBounded(deserialized, deserialized == subSet);
+            }
+        }.test();
+    }
+
+    public void testNavigableSubSetSerialization() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b03000078707372002a6a6176612e6c616e672e537472696e672443617365496"
+                + "e73656e736974697665436f6d70617261746f7277035c7d5c50e5ce0200007870"
+                + "770400000002740001627400016378";
+        TreeSet<String> set = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
+        set.add("a");
+        set.add("b");
+        set.add("c");
+        set.add("d");
+        final SortedSet<String> subSet = set.subSet("a", false, "c", true);
+        new SerializableTester<SortedSet<String>>(subSet, s) {
+            @Override protected void verify(SortedSet<String> deserialized) {
+                assertBounded(deserialized, deserialized == subSet);
+            }
+        }.test();
+    }
+
+    /**
+     * Regrettably, serializing a TreeSet causes it to forget its bounds. This
+     * is unlike a serialized TreeMap which retains its bounds when serialized.
+     */
+    private void assertBounded(SortedSet<String> deserialized, boolean bounded) {
+        if (bounded) {
+            try {
+                deserialized.add("e");
+                fail();
+            } catch (IllegalArgumentException expected) {
+            }
+        } else {
+            assertTrue(deserialized.add("e"));
+            assertTrue(deserialized.remove("e"));
+        }
+    }
+
+    /**
+     * Test that TreeSet never attempts to serialize a non-serializable
+     * comparator. http://b/5552608
+     */
+    public void testDescendingSetSerialization() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b0300007870737200276a6176612e7574696c2e436f6c6c656374696f6e73245"
+                + "2657665727365436f6d70617261746f7264048af0534e4ad00200007870770400"
+                + "000002740001627400016178";
+        TreeSet<String> set = new TreeSet<String>();
+        set.add("a");
+        set.add("b");
+        NavigableSet<String> descendingSet = set.descendingSet();
+        new SerializableTester<NavigableSet<String>>(descendingSet, s) {
+            @Override protected void verify(NavigableSet<String> deserialized) {
+                assertEquals("b", deserialized.first());
+            }
+        }.test();
+    }
+
+    public void testJava5SerializationWithComparator() {
+        String s = "aced0005737200116a6176612e7574696c2e54726565536574dd98509395ed87"
+                + "5b03000078707372002a6a6176612e6c616e672e537472696e672443617365496"
+                + "e73656e736974697665436f6d70617261746f7277035c7d5c50e5ce0200007870"
+                + "770400000002740001617400016278";
+        TreeSet<String> set = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
+        set.add("a");
+        set.add("b");
+        new SerializableTester<TreeSet<String>>(set, s) {
+            @Override protected void verify(TreeSet<String> deserialized) {
+                assertEquals(0, deserialized.comparator().compare("X", "x"));
+            }
+        }.test();
+    }
+}