RFR: 8256397: MultipleSelectionModel throws IndexOutOfBoundException

[Florian Kirmaier]

On Sat, 2 Jul 2022 05:23:22 GMT, Michael Strauß <mstrauss at openjdk.org> wrote:

>> good catch :)
>> 
>> No review, just a couple of comments:
>> 
>> - other subclasses of MultipleSelectionModelBase might have similar issues 
>> - the fix gets rid of the error (good!) but might fire incorrect changes (see below)
>> - there are quite a lot of open issues related to change notification, some might profit from a fix of this
>> - tests, tests, tests .. :)
>> 
>> selectIndices might involve disjoint intervals in the change (even for addition which is unusual in the "normal" implementations of observableLists)
>> 
>>        // initial selection, starting from empty
>>        selectionModel.selectIndices(0, /*1, IMPORTANT: remove some index */ 2,  3);
>>        System.out.println(change);
>>       // expected and actual change 
>>       { [0, 2, 3] added at 0 }
>> 
>>       // add selection of disjoint indices (assuming a longer items list)
>>        selectionModel.selectIndices(1, 5, 7);
>>        System.out.println(change);
>>       // actual
>>        { [1, 2, 3] added at 1 }
>>       // expected
>>      { [1] added at 1, [5, 7] added at 4 }
>
> I don't understand how the original code, as well as the proposed solution, can work at all. Let's take @kleopatra's example:
> 
> selectionModel.selectIndices(0, 2, 3);
> // ---> expected: { [0, 2, 3] added at 0 }
> selectionModel.selectIndices(1, 5, 7);
> // ---> expected: { [1] added at 1, [5, 7] added at 4 }
> 
> In order to find the two sub-ranges `[1]` and `[5, 7]`, we need to compare the _newly added_ indices to the _entire_ list of selected indices. Without doing that, we can't just "know" that there are two contiguous sub-ranges in `[1, 5, 7]`.
> 
> However, the algorithm that supposedly tries to do that, doesn't even look at the current list of selected indices (except for a single `indexOf` call, which doesn't do the trick):
> 
> int pos = 0;
> int start = 0;
> int end = 0;
> 
> // starting from pos, we keep going until the value is
> // not the next value
> int startValue = sortedNewIndices.get(pos++);
> start = indexOf(startValue);
> end = start + 1;
> int endValue = startValue;
> while (pos < size) {
>     int previousEndValue = endValue;
>     endValue = sortedNewIndices.get(pos++);
>     ++end;
>     if (previousEndValue != (endValue - 1)) {
>         _nextAdd(start, end);
>         start = end;
>         continue;
>     }
>     
>     // special case for when we get to the point where the loop is about to end
>     // and we have uncommitted changes to fire.
>     if (pos == size) {
>         _nextAdd(start, end);
>     }
> }
> 
> I think this algorithm mistakenly finds contiguous ranges within the list of _newly added_ indices, which is not what we want.
> 
> Here is an algorithm that works:
> 
> int startIndex = indexOf(sortedNewIndices.get(0));
> int endIndex = startIndex + 1;
> 
> for (int i = 1; i < sortedNewIndices.size(); ++i) {
>     int currentValue = get(endIndex);
>     int currentNewValue = sortedNewIndices.get(i);
>     if (currentValue != currentNewValue) {
>         _nextAdd(startIndex, endIndex);
>         while (get(endIndex) != currentNewValue) ++endIndex;
>         startIndex = endIndex++;
>     } else {
>         ++endIndex;
>     }
> 
>     if (i == sortedNewIndices.size() - 1) {
>         _nextAdd(startIndex, endIndex);
>     }
> }
> 
> 
> Unfortunately, even with the working algorithm, the list change notifications are still not correct in all cases due to another (probably unrelated) bug in `SelectedIndicesList.get(int)`: If I remove the optimization that is implemented in that method, and replace it with a simple lookup, the notifications are always correct in my tests:
> 
> @Override public Integer get(int index) {
>     for (int lastGetIndex = 0, lastGetValue = bitset.nextSetBit(0);
>          lastGetValue >= 0 || lastGetIndex == index;
>          lastGetIndex++, lastGetValue = bitset.nextSetBit(lastGetValue + 1)) {
>         if (lastGetIndex == index) {
>             return lastGetValue;
>         }
>     }
>     return -1;
> }
> 
> 
> Test 1:
> 
> selectionModel.selectIndices(0, 2, 3);
> // ---> { [0, 2, 3] added at 0 }
> selectionModel.selectIndices(1, 5, 7);
> // ---> { [1] added at 1, [5, 7] added at 4 }
> 
> Test 2:
> 
> selectionModel.selectIndices(1, 3, 4);
> // ---> { [1, 3, 4] added at 0 }
> selectionModel.selectIndices(0, 5, 7);
> // ---> { [0] added at 0, [5, 7] added at 4 }
> selectionModel.selectIndices(6, 8, 9);
> // ---> { [6] added at 5, [8, 9] added at 7 }

@mstr2 
Thank you for the corrected version of the algorithm, and also for highlighting further bugs.
I investigated the code a bit, and found the cause why the get method was so unreliable.

It turned out, that the optimization in the get method only works when the bit-set is not changed.
I've added some calls to the "reset" method, which resets the optimization when the bitset is changed.
I've added the correction into the PR.

I've also changed the tests, so we can easily test any case we come up with.
Also all the tests you've provided are now part of the PR and are green!

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

PR: https://git.openjdk.org/jfx/pull/353