PriorityQueue(collection) should throw NPE

[David Holmes]

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 oracle.com> wrote:
>>> Fix:
>>>
>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/
>> 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)
                 break;
             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.

Cheers,
David

> Martin
> 
>> David
>>