PriorityQueue(collection) should throw NPE

[David Holmes]

Hi Chris,

Chris Hegarty said the following on 05/07/10 19:55:
> Hi David, Martin,
> 
> Thanks for filing the bug David, I'll just add a link to the email 
> thread in the archive for reference.

Thanks.

> Just one minor observation while reviewing the changes. Is it necessary 
> for initFromPriorityQueue to call initFromCollection ( in the case where 
> you're given a PriorityQueue subclass), or can it simply call 
> initElementsFromCollection?

It's possible that the subclass overrides toArray to return an array 
that doesn't preserve the internal order. Hence we need to re-sort, 
hence initFromCollection.

David

> -Chris.
> 
> On 07/05/2010 03:37, David Holmes wrote:
>> 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
>>>>>>