PriorityQueue(collection) should throw NPE

[Chris Hegarty]

Hi David, Martin,

Thanks for filing the bug David, I'll just add a link to the email 
thread in the archive for reference.

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?

-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
>>>>>