RFR [8014066] Mistake in documentation of ArrayList#removeRange
David Holmes
david.holmes at oracle.com
Fri Mar 14 08:31:09 UTC 2014
Hi Ivan,
On 14/03/2014 5:05 PM, Ivan Gerasimov wrote:
> Thank you David for your reply!
>
> On 14.03.2014 8:56, David Holmes wrote:
>> Hi Ivan,
>>
>> I think we need to apply the brakes here and back up a bit :)
>>
>> First of all these aren't typo fixes they are spec changes and they
>> will need to go through CCC for approval.
>>
> Yes, sure. I haven't done that before, so will need to find someone to
> assist me for the first time.
>
>> Second point is that the condition "fromIndex >= size()" is already
>> captured by the condition "if {@code fromIndex} or {@code toIndex} is
>> out of range". By definition fromIndex is out-of-range if it is < 0 or
>> >= size(). So I don't see any error here even if there is some
>> redundancy.
>>
> I don't think that 'fromIndex < size()' restriction is quite natural.
Seems perfectly natural to ensure the fromIndex is somewhere in the
available range.
> I've scanned through several other methods in JDK, where the pair
> 'fromIndex, toIndex' is used as the arguments.
> For example, List.subList(), BitSet.clear(), BitSet.flip(),
> BitSet.get(), BitSet.set(), Arrays.sort(), Arrays.binarySearch(),
> Arrays.fill() and several others.
> None of these methods have this kind of restriction, at least in the
> documentation.
List.subList states:
IndexOutOfBoundsException - for an illegal endpoint index value
(fromIndex < 0 || toIndex > size || fromIndex > toIndex)
which means that fromIndex <= toIndex <= size; hence fromIndex > size()
is illegal.
Also CharSequence.subSequence:
IndexOutOfBoundsException - if start or end are negative, if end is
greater than length(), or if start is greater than end
As I said fromIndex >= size() is actually captured by saying fromIndex
must be in range.
>> Third, a call a.removeRange(a.size(), a.size()) hits the normal
>> dilemma of "what should be checked first?". The spec states that
>> removeRange(n,n) is a no-op, so if we do that check first we just
>> return, even for bad things like removeRange(-5, -5). Of course if we
>> check all the preconditions first then we would in fact throw the
>> IOOBE. I'm in the camp that says we check preconditions first because
>> it detects silly mistakes sooner.
>>
> In my opinion a.removeRange(a.size(), a.size()) is a valid expression,
> while removeRange(-5, -5) is not.
> For example, if had a need to remove some elements up to the end of the
> list, I would have toIndex fixed to 'a.end()': a.remove(fromIndex,
> a.end()).
> In this situation, I would need to have a way to specify an empty set of
> items to be removed, thus having fromIndex == a.end().
That's a good point. I think the prohibition on fromIndex==size() is
wrong, as per the other examples (subList, subSequence).
> I agree that preconditions should be checked first, so removeRange(-5,
> -5) should throw an exception.
>
>
>> Fourth, your code change to add the additional pre-condition check:
>>
>> protected void removeRange(int fromIndex, int toIndex) {
>> modCount++;
>> + if (fromIndex > toIndex)
>> + throw new IndexOutOfBoundsException(
>>
>> needs to be done _before_ the change to modCount!
>>
> I placed it right before a call to System.copyarray(), where all other
> checks are performed.
That is a bug in the existing code then. If a precondition fails then
the data structure is not modified and the modCount should not be
changed. This is what happens when you piggy-back pre-condition checks.
> But I don't mind moving it to the top of the method.
Thanks - every little helps :)
>> And finally, the AbstractList.removeRange change:
>>
>> + * @throws NoSuchElementException if {@code (toIndex > size())}
>>
>> seems to reflect an implementation accident rather than a clear API
>> design choice. If the toIndex is out of range then
>> IndexOutOfBoundsException is what should be thrown. Otherwise you
>> constrain any subtypes that override this to throw an exception type
>> that only has meaning with the AbstractList implementation strategy -
>> and by doing so you are making ArrayList.removeRange violate this new
>> specification.
>>
>> It is unfortunate that the existing specification(s) for removeRange
>> are lacking this key detail on exception processing, and lack
>> consistency between AbstractList and it's sublcass ArrayList. I think
>> ArrayList has the better/cleaner specification and that should be
>> pushed up AbstractList and AbstractList's implementation should be
>> modified to explicitly check the pre-conditions.
>>
> Again, I agree with you.
> One thing I noticed is that some methods I mentioned above
> (List.subList(), Arrays.sort(), etc) throw IllegalArgumentException when
> fromIndex > toIndex, not IndexOutOfBoundException.
> Wouldn't it be more correct to adopt this into removeRange() too?
Unfortunately there are a lot of inconsistencies in the API design
throughout the JDK - even in classes that are somewhat related. That
said List.subList throws IOOBE, But I do see examples of:
IllegalArgumentException - if fromIndex > toIndex
which is definitely more correct if both values are in range, but then
what if both are out of range?
Anyway you can't just arbitrarily make changes to the specifications of
these methods - even if trying to fix obvious inconsistencies. The main
priority is that specs and implementations agree; and that specs in
subtypes are consistent with the spec in the supertypes.
I see a number of issues here that may be tricky to reconcile having
regard for compatability.
Cheers,
David
> Sincerely yours,
> Ivan
>
>
>> David
>> -----
>>
>> On 14/03/2014 5:42 AM, Ivan Gerasimov wrote:
>>> Sorry, I forgot to incorporate changes to AbstractList.removeRange()
>>> documentation, which you Martin had suggested.
>>>
>>> Here's the webrev with those included:
>>> http://cr.openjdk.java.net/~igerasim/8014066/2/webrev/
>>>
>>> Sincerely yours,
>>> Ivan
>>>
>>>
>>> On 13.03.2014 23:03, Ivan Gerasimov wrote:
>>>> Would you please take a look at the updated webrev:
>>>> http://cr.openjdk.java.net/~igerasim/8014066/1/webrev/
>>>>
>>>> In addition to the javadoc correction, it includes a regression test
>>>> and a check for (fromIndex > toIndex).
>>>> The last check turns out to be sufficient for removeRange() method to
>>>> agree with the javadoc.
>>>> Other checks are handled by the following System.arraycopy() call.
>>>>
>>>> Sincerely yours,
>>>> Ivan
>>>>
>>>>
>>>> On 13.03.2014 22:27, Ivan Gerasimov wrote:
>>>>>
>>>>> On 13.03.2014 22:16, Ivan Gerasimov wrote:
>>>>>>
>>>>>> On 13.03.2014 20:37, Martin Buchholz wrote:
>>>>>>> The corner case for removeRange(SIZE, SIZE) does seem rather
>>>>>>> tricky, and it's easy for an implementation to get it wrong. All
>>>>>>> the more reason to add tests!
>>>>>>>
>>>>>> It was a good idea to add a test for removeRange().
>>>>>> I just discovered that IOOB isn't thrown when you call
>>>>>> removeRange(1, 0) or removeRange(4, 0).
>>>>>> However, the exception is thrown when you call removeRange(5, 0).
>>>>>>
>>>>>> The fix seems to become a bit more than just a doc typo fix :-)
>>>>>>
>>>>>
>>>>> And when you do list.removeRange(1, 0), the list becomes longer.
>>>>>
>>>>>
>>>>>> Sincerely yours,
>>>>>> Ivan
>>>>>>
>>>>>>>
>>>>>>> On Thu, Mar 13, 2014 at 9:15 AM, Ivan Gerasimov
>>>>>>> <ivan.gerasimov at oracle.com <mailto:ivan.gerasimov at oracle.com>>
>>>>>>> wrote:
>>>>>>>
>>>>>>> Thank you Chris!
>>>>>>>
>>>>>>> It is System.arraycopy() method, where checking is performed and
>>>>>>> the exception is thrown.
>>>>>>> Here's this code:
>>>>>>> if ( (((unsigned int) length + (unsigned int) src_pos) >
>>>>>>> (unsigned int) s->length())
>>>>>>> || (((unsigned int) length + (unsigned int) dst_pos) >
>>>>>>> (unsigned int) d->length()) ) {
>>>>>>> THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException());
>>>>>>> }
>>>>>>>
>>>>>>> This confirms that size() is a valid value for fromIndex.
>>>>>>>
>>>>>>> Another way to think of it is that fromIndex <= toIndex, and
>>>>>>> toIndex can be equal to size().
>>>>>>> Therefore, fromIndex can be equal to size() too.
>>>>>>>
>>>>>>> The documentation also says that 'If toIndex==fromIndex, this
>>>>>>> operation has no effect.', so removeRange(size(), size()) is a
>>>>>>> valid expression and should not cause an exception be thrown
>>>>>>> (and
>>>>>>> it actually does not).
>>>>>>>
>>>>>>> Sincerely yours,
>>>>>>> Ivan
>>>>>>>
>>>>>>>
>>>>>>> On 13.03.2014 19:47, Chris Hegarty wrote:
>>>>>>>
>>>>>>> Ivan,
>>>>>>>
>>>>>>> This does look a little odd, but since fromIndex is
>>>>>>> inclusive
>>>>>>> I would think that it should throw if passed a value of
>>>>>>> size() ??
>>>>>>>
>>>>>>> -Chris.
>>>>>>>
>>>>>>> On 13 Mar 2014, at 15:29, Ivan Gerasimov
>>>>>>> <ivan.gerasimov at oracle.com
>>>>>>> <mailto:ivan.gerasimov at oracle.com>>
>>>>>>> wrote:
>>>>>>>
>>>>>>> Hello!
>>>>>>>
>>>>>>> Would you please review a simple fix of the javadoc for
>>>>>>> ArrayList#removeRange() method?
>>>>>>>
>>>>>>> The doc says that IndexOutOfBoundsException is thrown if
>>>>>>> fromIndex or toIndex is out of range (fromIndex < 0 ||
>>>>>>> fromIndex >= size() || toIndex > size() || toIndex <
>>>>>>> fromIndex).
>>>>>>>
>>>>>>> The condition 'fromIndex >= size()' isn't true and
>>>>>>> should
>>>>>>> be removed from the doc.
>>>>>>>
>>>>>>> For example, the code list.removeRange(size(), size())
>>>>>>> does not throw any exception.
>>>>>>>
>>>>>>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8014066
>>>>>>> WEBREV:
>>>>>>> http://cr.openjdk.java.net/~igerasim/8014066/0/webrev/
>>>>>>> <http://cr.openjdk.java.net/%7Eigerasim/8014066/0/webrev/>
>>>>>>>
>>>>>>> Sincerely yours,
>>>>>>> Ivan
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>
>>
>>
>
More information about the core-libs-dev
mailing list