changeset 39039:9dea20ff2dee

8066070: PriorityQueue corrupted when adding non-Comparable Reviewed-by: martin, chegar
author dl
date Wed, 01 Jun 2016 19:03:15 -0700
parents fcd3b93b265f
children a6f5ef42ecda
files jdk/src/java.base/share/classes/java/util/PriorityQueue.java jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java jdk/test/java/util/PriorityQueue/AddNonComparable.java jdk/test/java/util/concurrent/tck/ConcurrentSkipListSetTest.java jdk/test/java/util/concurrent/tck/PriorityBlockingQueueTest.java jdk/test/java/util/concurrent/tck/PriorityQueueTest.java
diffstat 6 files changed, 175 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/jdk/src/java.base/share/classes/java/util/PriorityQueue.java	Wed Jun 15 12:47:50 2016 -0700
+++ b/jdk/src/java.base/share/classes/java/util/PriorityQueue.java	Wed Jun 01 19:03:15 2016 -0700
@@ -337,11 +337,8 @@
         int i = size;
         if (i >= queue.length)
             grow(i + 1);
+        siftUp(i, e);
         size = i + 1;
-        if (i == 0)
-            queue[0] = e;
-        else
-            siftUp(i, e);
         return true;
     }
 
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Wed Jun 15 12:47:50 2016 -0700
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Wed Jun 01 19:03:15 2016 -0700
@@ -840,6 +840,9 @@
                         break; // restart if lost race to replace value
                     }
                     // else c < 0; fall through
+                } else if (b == head.node) {
+                    // map is empty, so type check key now
+                    cpr(cmp, key, key);
                 }
 
                 z = new Node<K,V>(key, value, n);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/PriorityQueue/AddNonComparable.java	Wed Jun 01 19:03:15 2016 -0700
@@ -0,0 +1,153 @@
+/*
+ * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8066070
+ * @run testng AddNonComparable
+ */
+
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.SortedMap;
+import java.util.SortedSet;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.ConcurrentSkipListSet;
+import java.util.concurrent.PriorityBlockingQueue;
+import java.util.function.BiConsumer;
+import java.util.function.Supplier;
+
+import static org.testng.Assert.*;
+import org.testng.annotations.Test;
+
+public class AddNonComparable {
+
+    static <E> void test(Queue<E> queue, Supplier<E> supplier,
+                         BiConsumer<? super Queue<E>, Throwable> checker) {
+        Throwable x = null;
+        try { queue.add(supplier.get()); }
+        catch (Throwable e) { x = e; }
+        checker.accept(queue, x);
+    }
+
+    @Test
+    public void queues() {
+        test(new PriorityQueue<>(), NonComparable::new,
+             (q, e) -> {
+                 assertEquals(q.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new PriorityQueue<>(), AComparable::new,
+             (q, e) -> {
+                 assertEquals(q.size(), 1);
+                 assertTrue(e == null);
+             });
+
+        test(new PriorityBlockingQueue<>(), NonComparable::new,
+             (q, e) -> {
+                 assertEquals(q.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new PriorityBlockingQueue<>(), AComparable::new,
+             (q, e) -> {
+                 assertEquals(q.size(), 1);
+                 assertTrue(e == null);
+             });
+    }
+
+    static <E> void test(SortedSet<E> set, Supplier<E> supplier,
+                         BiConsumer<? super SortedSet<E>, Throwable> checker) {
+        Throwable x = null;
+        try { set.add(supplier.get()); }
+        catch (Throwable e) { x = e; }
+        checker.accept(set, x);
+    }
+
+
+    @Test
+    public void sets() {
+        test(new TreeSet<>(), NonComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new TreeSet<>(), AComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 1);
+                 assertTrue(e == null);
+             });
+
+        test(new ConcurrentSkipListSet<>(), NonComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new ConcurrentSkipListSet<>(), AComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 1);
+                 assertTrue(e == null);
+             });
+    }
+
+    static <K> void test(SortedMap<K,Boolean> map, Supplier<K> supplier,
+                         BiConsumer<? super SortedMap<K,Boolean>, Throwable> checker) {
+        Throwable x = null;
+        try { map.put(supplier.get(), Boolean.TRUE); }
+        catch (Throwable e) { x = e; }
+        checker.accept(map, x);
+    }
+
+    @Test
+    public void maps() {
+        test(new TreeMap<>(), NonComparable::new,
+             (m, e) -> {
+                 assertEquals(m.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new TreeMap<>(), AComparable::new,
+             (m, e) -> {
+                 assertEquals(m.size(), 1);
+                 assertTrue(e == null);
+             });
+
+        test(new ConcurrentSkipListMap<>(), NonComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 0);
+                 assertTrue(e instanceof ClassCastException);
+             });
+        test(new ConcurrentSkipListMap<>(), AComparable::new,
+             (s, e) -> {
+                 assertEquals(s.size(), 1);
+                 assertTrue(e == null);
+             });
+    }
+
+    static class NonComparable { }
+
+    static class AComparable implements Comparable<AComparable> {
+        @Override public int compareTo(AComparable v) { return 0; }
+    }
+
+}
--- a/jdk/test/java/util/concurrent/tck/ConcurrentSkipListSetTest.java	Wed Jun 15 12:47:50 2016 -0700
+++ b/jdk/test/java/util/concurrent/tck/ConcurrentSkipListSetTest.java	Wed Jun 01 19:03:15 2016 -0700
@@ -226,7 +226,14 @@
             q.add(new Object());
             q.add(new Object());
             shouldThrow();
-        } catch (ClassCastException success) {}
+        } catch (ClassCastException success) {
+            assertTrue(q.size() < 2);
+            for (int i = 0, size = q.size(); i < size; i++)
+                assertTrue(q.pollFirst().getClass() == Object.class);
+            assertNull(q.pollFirst());
+            assertTrue(q.isEmpty());
+            assertEquals(0, q.size());
+        }
     }
 
     /**
--- a/jdk/test/java/util/concurrent/tck/PriorityBlockingQueueTest.java	Wed Jun 15 12:47:50 2016 -0700
+++ b/jdk/test/java/util/concurrent/tck/PriorityBlockingQueueTest.java	Wed Jun 01 19:03:15 2016 -0700
@@ -227,9 +227,12 @@
         PriorityBlockingQueue q = new PriorityBlockingQueue(1);
         try {
             q.offer(new Object());
-            q.offer(new Object());
             shouldThrow();
-        } catch (ClassCastException success) {}
+        } catch (ClassCastException success) {
+            assertTrue(q.isEmpty());
+            assertEquals(0, q.size());
+            assertNull(q.poll());
+        }
     }
 
     /**
--- a/jdk/test/java/util/concurrent/tck/PriorityQueueTest.java	Wed Jun 15 12:47:50 2016 -0700
+++ b/jdk/test/java/util/concurrent/tck/PriorityQueueTest.java	Wed Jun 01 19:03:15 2016 -0700
@@ -218,9 +218,12 @@
         PriorityQueue q = new PriorityQueue(1);
         try {
             q.offer(new Object());
-            q.offer(new Object());
             shouldThrow();
-        } catch (ClassCastException success) {}
+        } catch (ClassCastException success) {
+            assertTrue(q.isEmpty());
+            assertEquals(0, q.size());
+            assertNull(q.poll());
+        }
     }
 
     /**