On Thu, 17 Aug 2023 10:54:07 GMT, Nikita Sakharin <d...@openjdk.org> wrote:
>> `Collections.rotate` method contains a bug. This method throws
>> IndexOutOfBoundsException on arrays larger than $2^{30}$ elements. The way
>> to reproduce:
>>
>> final int size = (1 << 30) + 1;
>> final List<Byte> list = new ArrayList<>(size);
>> for (int i = 0; i < size; ++i)
>> list.add((byte) 0);
>> Collections.rotate(list, size - 1);
>>
>> Output:
>> ```Exception in thread "main" java.lang.IndexOutOfBoundsException: Index
>> -2147483648 out of bounds for length 1073741825```
>>
>> In that case private method `Collections.rotate1` will be called. And the
>> line:
>> `i += distance;`
>> will cause overflow. I fixed this method and wrote a test for it.
>>
>> I've signed the Oracle Contributor Agreement, but I don't have permission to
>> raise a bug in the JDK Bug System.
>>
>> Kindly ask you to raise a bug.
>
> Nikita Sakharin has updated the pull request incrementally with one
> additional commit since the last revision:
>
> 8314236: rewrite test
@nikita-sakharin
Thanks for the updates. With the "Mock List" implementation we can run the test
in-JVM and we can avoid allocating several GB of memory. Great!
The implementation logic in the `rotate1` method looks correct.
Now that an individual test case is much less expensive, it becomes feasible to
add multiple test cases. In particular, for this kind of testing of arithmetic
errors, I like to test a variety of edge cases. The one test case you have is
for size=`(1 << 30) - 1` and distance=`(1 << 30)`. It would be good to have a
few other cases where the existing code fails and where the modified code
should pass. I was able to come up with a few examples quickly:
size distance
Integer.MAX_VALUE 2
Integer.MAX_VALUE Integer.MIN_VALUE
Integer.MAX_VALUE Integer.MAX_VALUE - 1
Please add these cases, and any others that you think might be interesting.
-------------
PR Comment: https://git.openjdk.org/jdk/pull/15270#issuecomment-1690901246
