PriorityQueue(collection) should throw NPE

[David Holmes]

Hi Martin,

CR 6950540 filed. (Chris might want to tidy it up :) )

Changes look okay to me.

Thanks,
David

Martin Buchholz said the following on 05/07/10 12:19:
> David,
> 
> Of course you're right.
> I didn't realize that the hole was one-element nulls.
> 
> (Why is software always 10 times harder than you'd think?)
> 
> Updated webrev, with lots more tests for corner cases.
> 
> I still need a bug filed in bugtraq.
> 
> Martin
> 
> On Thu, May 6, 2010 at 16:53, David Holmes <David.Holmes at oracle.com> wrote:
>> 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
>>>>