PriorityQueue(collection) should throw NPE

David Holmes David.Holmes at
Thu May 6 23:53:05 UTC 2010

Hi Martin,

Martin Buchholz said the following on 05/07/10 09:13:
> On Thu, May 6, 2010 at 15:58, David Holmes <David.Holmes at> wrote:
>>> Fix:
>> I'm not sure this is necessarily the right fix. It seems to me that
>> incidental nulls will be caught in many/most cases by the sorting code for
>> collections assumed to contain Comparable's.
> The comparator might accept nulls.

True but a Comparator is only used if the Collection is a SortedSet or a 
PriorityQueue. For any other Collection the elements must implement 
Comparable and the code in:

    private void siftDownComparable(int k, E x) {
         Comparable<? super E> key = (Comparable<? super E>)x;
         int half = size >>> 1;        // loop while a non-leaf
         while (k < half) {
             int child = (k << 1) + 1; // assume left child is least
             Object c = queue[child];
             int right = child + 1;
             if (right < size &&
                 ((Comparable<? super E>) c).compareTo((E) queue[right]) 
 > 0)
                 c = queue[child = right];
             if (key.compareTo((E) c) <= 0)
             queue[k] = c;
             k = child;
         queue[k] = key;

will throw NPE at key.compareTo if the item is null. (There's probably a 
missed case where the collection contains only a null element).

> But even if it doesn't, it is possible to create a "corrupted" PQ
> using the PQ(collection) constructor, and we don't allow
> that sort of thing in java.util.

But that's the hole we're fixing now.

>> And we don't need to check when
>> filling from an existing PriorityQueue.
> Strictly speaking, the source PriorityQueue might be a subclass that
> has been modified to accept nulls.

Yes I suppose. So we could change from an instanceof test to a 
getClass() test.

> But yes, we could have a version of the fix that only checks for nulls
> if the source is not a PQ.
>> So is it only the case for filling
>> from a SortedSet that needs the explicit null check?
> The source can be an arbitrary Collection.

But as noted above for anything other than a SortedSet (or corrupt PQ) 
the sorting code will already catch nulls.


> Martin
>> David

More information about the core-libs-dev mailing list