8066070: PriorityQueue corrupted when adding non-Comparable
Reviewed-by: martin, chegar
--- 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());
+ }
}
/**