RFR: 8256397: MultipleSelectionModel throws IndexOutOfBoundException

[Ajit Ghaisas]

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, can you please review as well?

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

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