RFR: 6187113: DefaultListSelectionModel.removeIndexInterval(0, Integer.MAX_VALUE) fails [v8]

[Alexey Ivanov]

On Wed, 26 Oct 2022 04:05:54 GMT, Prasanta Sadhukhan <psadhukhan at openjdk.org> wrote:

>> DefaultListSelectionModel.removeIndexInterva accepts `int` value which allows it to take in Integer.MAX_VALUE theoratically but it does calculation with that value which can results in IOOBE.
>> Fix is to make sure the calculation stays within bounds.
>
> Prasanta Sadhukhan has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Review comment fix

I already mentioned that I wrote a comprehensive unit-test to test the changes to `removeIndexInterval` and `insertIndexInterval`. The latest version of my test [`SelectionModelTest.java`](https://github.com/aivanov-jdk/jdk/blob/f9e8bf592125419d117bd1d6318f9ce909a1dcc1/test/jdk/javax/swing/JList/SelectionModelTest.java).

With the current code in the PR, six (6) test cases still _fail_. The changes I've suggested should resolve those failures. (I've been testing and proposing fixes to resolve test failures since the start of this code review.)

The test can be run as a jtreg test or as a standalone app. Depending on the hardware, it may take up to 10 minutes; the more cores the system has, the faster the test completes as all the test cases are run in parallel. (The minimum time I've ever seen is around 2–3 minutes.)

I can contribute the test to OpenJDK if deemed useful. I believe such a fix can't be done without extensive testing which verifies all the values in the object remain correct.

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 452:

> 450:                 clear(i);
> 451:             }
> 452:             // Integer overlfow

Typo:
Suggestion:

            // Integer overflow

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 453:

> 451:             }
> 452:             // Integer overlfow
> 453:             if (i + 1 < i) {

Suggestion:

            if (i == Integer.MAX_VALUE) {

Will it be clearer this way? (And one less operation: no addition.)

As I mentioned before, I would prefer reversing the loop and iterating from `max` to `min` instead. But it causes a failure in JCK which I can't explain because the effective result is the same. Moreover, I believe iterating from `max` to `min` is more efficient as touching the maximum index will ensure the internal storage in the underlying `BitSet` is allocated right away to fit all the bits whereas the storage gets continuously re-allocated and copied as the accessed indexes grow.

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 651:

> 649:     {
> 650:         if (length < 0 || index < 0) {
> 651:             throw new IndexOutOfBoundsException("index or length is negative");

I suggest updating the spec to state this explicitly. The current implementation throws IOOBE if `index` is negative and if `index + length` is negative. It doesn't throw the exception if `length` is negative but the sum of `index` and `length` remains positive, which doesn't make sense — the updated model becomes corrupted.

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 653:

> 651:             throw new IndexOutOfBoundsException("index or length is negative");
> 652:         }
> 653:         if (index + length < 0) {

I suggested handling the case where `index == Integer.MAX_VALUE  || length == 0` as a special case because there's nothing to update. It's a little optimisation.

If `index == Integer.MAX_VALUE`, there's only one index which can possibly be inserted, that is at `Integer.MAX_VALUE`. By the spec, the inserted index will have the same value which had the index before insertion. So no change occurs.

In addition to the above, special handling of `index == Integer.MAX_VALUE` prevents integer overflow in `insMinIndex` if `before` is `false`.

If `length == 0`, no new indexes are inserted irrespective of the value of `index`. Thus nothing changes in the object state.

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 666:

> 664:          * insMinIndex).
> 665:          */
> 666:         for(int i = maxIndex; (i+length) >= 0 && i >= insMinIndex; i--) {

You break from the loop prematurely and perhaps never enter the loop. The chances for `(i + length)` to be negative are much higher for larger indexes closer to `maxIndex`.

The iteration is to start at the index which ensures `i + length <= Integer.MAX_VALUE`. That is

        int startIndex = maxIndex <= Integer.MAX_VALUE - length
                         ? maxIndex
                         : Integer.MAX_VALUE - length;
        for(int i = startIndex; i >= insMinIndex; i--) {

which can be simplified to

        for(int i = Math.min(maxIndex, Integer.MAX_VALUE - length); i >= insMinIndex; i--) {

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 673:

> 671:          */
> 672:         boolean setInsertedValues = ((getSelectionMode() == SINGLE_SELECTION) ?
> 673:                                         false : value.get(index));

I propose resolving an IDE warning and simplify this condition:
Suggestion:

        boolean setInsertedValues = (getSelectionMode() != SINGLE_SELECTION
                                     && value.get(index));

Although this change is unrelated.

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 674:

> 672:         boolean setInsertedValues = ((getSelectionMode() == SINGLE_SELECTION) ?
> 673:                                         false : value.get(index));
> 674:         for(int i = insMinIndex; i >=0 && i <= insMaxIndex; i++) {

Suggestion:

        for(int i = insMaxIndex; i >= insMinIndex; i--) {

This loop can be reversed to avoid adding `i >= 0` to the condition. (I tested it and it doesn't lead to any failures in JCK as it does when the same is done in the loop in `changeSelection`.)

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 711:

> 709:         int rmMaxIndex = Math.max(index0, index1);
> 710: 
> 711: 

Is one blank line enough?

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 734:

> 732:         }
> 733: 
> 734: 

Not needed?

src/java.desktop/share/classes/javax/swing/DefaultListSelectionModel.java line 758:

> 756: 
> 757:         fireValueChanged();
> 758: 

Not needed?

test/jdk/javax/swing/TestDefListModelException.java line 32:

> 30: import javax.swing.DefaultListSelectionModel;
> 31: 
> 32: public class TestDefListModelException {

I propose moving this test to `JList` folder which already contains several tests which use `ListSelectionModel` via `JList`.

-------------

Changes requested by aivanov (Reviewer).

PR: https://git.openjdk.org/jdk/pull/10409