Re: RFR: 8256397: MultipleSelectionModel throws IndexOutOfBoundException

[Michael Strauß]

On Tue, 17 Nov 2020 12:38:32 GMT, Jeanette Winzenburg <faste...@openjdk.org> 
wrote:

>> Fixing IndexOutOfBoundsException in the MultipleSelectionModelBase and added 
>> a unit-test for it.
>> ticket: https://bugs.openjdk.java.net/browse/JDK-8256397
>> run test: `./gradlew --continue -PFULL_TEST=true controls:test --tests 
>> "*MultipleSelectionModelImplTest*"`
>
> 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 }

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

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