8256397: MultipleSelectionModel throws IndexOutOfBoundException

[FlorianKirmaier]

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*"

---

Progress

• [x] Change must not contain extraneous whitespace
• [x] Commit message must refer to an issue
• [ ] Change must be properly reviewed (2 reviews required, with at least 1 Reviewer, 1 Author)

Issue

• JDK-8256397: MultipleSelectionModel throws IndexOutOfBoundException

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jfx pull/353/head:pull/353
$ git checkout pull/353

Update a local copy of the PR:
$ git checkout pull/353
$ git pull https://git.openjdk.org/jfx pull/353/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 353

View PR using the GUI difftool:
$ git pr show -t 353

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jfx/pull/353.diff

[bridgekeeper[bot]]

:wave: Welcome back fkirmaier! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

[mlbridge[bot]]

Webrevs

• 06: Full - Incremental (b39d212c)
• 05: Full - Incremental (991b114f)
• 04: Full - Incremental (833afbb1)
• 03: Full (3a4e2f0b)
• 02: Full - Incremental (42807262)
• 01: Full - Incremental (2f6dd153)
• 00: Full (08f6abbf7eeec1347163b967964281fccd3eaed4)

[kleopatra]

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 }

[kevinrushforth]

/reviewers 2

[openjdk[bot]]

@kevinrushforth The number of required reviews for this PR is now set to 2 (with at least 1 of role reviewers).

[FlorianKirmaier]

I've rebased the PR to the current master. I've also added some more test-cases. It would be great if we could finish the PR, because it's already a year old.

If I make the following call, I get the following changes:

selectionModel.selectIndices(0,2,3);
c.getAddedSubList() -> [0, 2, 3]
selectionModel.selectIndices(1,4,5);
c.getAddedSubList() -> [1, 2, 3]

This looks wrong to me, but I don't know the logic too well, can this be somehow correct? On the other side, I would like to finish it, without looking for other bugs.

[christianheilmann]

How to proceed to get this PR reviewed?

[FlorianKirmaier]

I've just merged it with master I hope someone will find time to review this.

[mstr2]

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 }

[FlorianKirmaier]

@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!

[aghaisas]

@mstr2, can you please review as well?

[FlorianKirmaier]

First, thank you all for the code review and the suggestions.

I guess writing a TestFactory with randomly generated numbers would make sense. But it's also not trivial, because it requires reprogramming the logic of how the events are created, to ensure it's correct.

If someone finds time to do it, it's probably worth the time. Wouldn't be surprised if there is another error in this spaghetti code.

Because this PR is now 2 Years old ... I can tell you that it's tested for that time in a huge application with thousands of users.

This PR fixes an issue when editing entries in a ListView.

I don't really plan to extend the test further, unless someone points out an error, or suggests a simple modification.

[openjdk[bot]]

@FlorianKirmaier This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8256397: MultipleSelectionModel throws IndexOutOfBoundException

Reviewed-by: aghaisas, mstrauss

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 118 new commits pushed to the master branch:

• 4a697f1afc5f8e850425f5934ee1bcb73dd5da9f: 8297130: ComboBox popup doesn't close after selecting value that was added with 'runLater'
• cce85806c61f8b2a9bc18996a9922daf6daa9cd8: 8254676: Alert disables Tab selection when TabDragPolicy REORDER is used
• a0ea8743eb20bf4791f7a8bf627416aa97c002e5: 8279214: Memory leak in Scene after dragging a cell
• 9819d45bb1eb63253be5e951c6e10a779dc71a1e: 8297332: Remove easy warnings in javafx.base
• 086dac0b12233f31db33bb9fc43d821724710f70: 8297213: Robot capture tests should move mouse to corner of screen
• e3e0dfdb1b945844691c79e512dbae285027ff6c: 8297166: [TestBug] Fix some ignored unit test from TableViewTest
• 626227dc1029a0d984f2ed89a4397954bd71d676: 8296330: Tests: Add layout container snapping tests
• 1ec06a80d13c8a33a1e998baa9942fbfc5035432: 8206430: Use consistent pattern for startup in FX system tests
• 74af45d69828bf5bd8cea5b7fbf8e8c6cac4f689: 8296556: Mark two RobotTest methods as unstable on HiDPI Windows systems
• 6cc9c4d1b9a46432f1568a54d7dcdf51e224559b: 8297042: gradle -PBUILD_SDK_FOR_TEST=false fails with gradle 7.6
• ... and 108 more: https://git.openjdk.org/jfx/compare/da5bd3716441f201691377c52abba59ce03bc322...master

As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

As you do not have Committer status in this project an existing Committer must agree to sponsor your change. Possible candidates are the reviewers of this PR (@aghaisas, @mstr2) but any other Committer may sponsor as well.

➡️ To flag this PR as ready for integration with the above commit message, type /integrate in a new comment. (Afterwards, your sponsor types /sponsor in a new comment to perform the integration).

[FlorianKirmaier]

/integrate

[openjdk[bot]]

@FlorianKirmaier Your change (at version b39d212cb526d8bba76d2067c2df92f2f979652c) is now ready to be sponsored by a Committer.

[mstr2]

/sponsor

[openjdk[bot]]

Going to push as commit 67088beae1fea63b1e2ad72e88bb3fd96cf50bbd. Since your change was applied there have been 118 commits pushed to the master branch:

• 4a697f1afc5f8e850425f5934ee1bcb73dd5da9f: 8297130: ComboBox popup doesn't close after selecting value that was added with 'runLater'
• cce85806c61f8b2a9bc18996a9922daf6daa9cd8: 8254676: Alert disables Tab selection when TabDragPolicy REORDER is used
• a0ea8743eb20bf4791f7a8bf627416aa97c002e5: 8279214: Memory leak in Scene after dragging a cell
• 9819d45bb1eb63253be5e951c6e10a779dc71a1e: 8297332: Remove easy warnings in javafx.base
• 086dac0b12233f31db33bb9fc43d821724710f70: 8297213: Robot capture tests should move mouse to corner of screen
• e3e0dfdb1b945844691c79e512dbae285027ff6c: 8297166: [TestBug] Fix some ignored unit test from TableViewTest
• 626227dc1029a0d984f2ed89a4397954bd71d676: 8296330: Tests: Add layout container snapping tests
• 1ec06a80d13c8a33a1e998baa9942fbfc5035432: 8206430: Use consistent pattern for startup in FX system tests
• 74af45d69828bf5bd8cea5b7fbf8e8c6cac4f689: 8296556: Mark two RobotTest methods as unstable on HiDPI Windows systems
• 6cc9c4d1b9a46432f1568a54d7dcdf51e224559b: 8297042: gradle -PBUILD_SDK_FOR_TEST=false fails with gradle 7.6
• ... and 108 more: https://git.openjdk.org/jfx/compare/da5bd3716441f201691377c52abba59ce03bc322...master

Your commit was automatically rebased without conflicts.

[openjdk[bot]]

@mstr2 @FlorianKirmaier Pushed as commit 67088beae1fea63b1e2ad72e88bb3fd96cf50bbd.

:bulb: You may see a message that your pull request was closed with unmerged commits. This can be safely ignored.