RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]

[Kevin Rushforth]

On Sun, 4 Oct 2020 09:24:16 GMT, Jeanette Winzenburg <fastegal at openjdk.org> wrote:

>> the problem was (and still is) in MultipleSelectionModelBase:
>> 
>>         selectedItems = new SelectedItemsReadOnlyObservableList<T>(selectedIndices, () -> getItemCount()) {
>>             @Override protected T getModelItem(int index) {
>>                 return MultipleSelectionModelBase.this.getModelItem(index);
>>             }
>>         };
>> 
>> meaning that the selectedItems change during the removal of items (that's plain wrong!) which shows when removing the
>> items from the start:
>>        
>>         // removeAll before fix of
>>         for (int i = 0; i < size(); ++i) {
>>             if (c.contains(get(i))) {
>>                 remove(i);
>>                 --i;
>>                 modified = true;
>>             }
>>         }
>> 
>> doing so is basically valid (note the decremented i). Just the selectedItems look into the underlying model, so **c**
>> is changing during the removal which is a no-go.
>> Returning to the old (pre [JDK-8093144](https://bugs.openjdk.java.net/browse/JDK-8093144)) still makes the tests
>> against it fail (ListViewTest.test_rt35857 f.i.).
>> Still wondering why the detour over the BitSet was choosen as fix (vs. the more natural remove-from-last). The listView
>> test is passing for the bitSet and for the back-to-front approach. Can we imagine a context where the broken
>> selectedItems impl would add wreckage to the latter?
>
>> The listView test is passing for the bitSet and for the back-to-front approach. Can we imagine a context where the
>> broken selectedItems impl would add wreckage to the latter?
> 
> To answer my own question: yes. A failing test with the back-to-front approach (the existing test in ListViewTest
> modified in having the last item selected)
>     @Test public void test_rt35857Back() {
>         ObservableList<String> fxList = FXCollections.observableArrayList("A", "B", "C");
>         final ListView<String> listView = new ListView<String>(fxList);
>         
>         listView.getSelectionModel().select(2);
>         
>         ObservableList<String> selectedItems =
>                 listView.getSelectionModel().getSelectedItems();
>         assertEquals(1, selectedItems.size());
>         assertEquals("C", selectedItems.get(0));
>         
>         listView.getItems().removeAll(selectedItems);
>         assertEquals(2, fxList.size());
>         assertEquals("A", fxList.get(0));
>         assertEquals("B", fxList.get(1));
>     }
>     
> Feels like coming nearer to the why of the BitSet approach: it guards against the scenario where changing the current
> list implicitly changes the list given as parameter - in that case, it's unsafe to query the parameter list while
> removing items (c.contains simply reports nonsense).  This may happen whenever the parameter list does some kind of
> live lookup into the current list (such as f.i. SelectedItemsReadOnlyObservableList) - which is not as evil as I
> thought yesterday (did it myself in custom selectionModels ;) The BitSet solves it by a two-pass approach: first
> collect all items to remove/retain without (that is keep the parameter list in a valid state, allowing to safely access
> it), then do the removal without further accessing the (then invalid) parameter list.   The fix at that time was a
> deliberate decision by the designer of the collections, so the context when it happens was deemed a valid use-case.
> Looks like we should **not** revert it.

Nice catch! So now it's clear that the current approach was adopted because the source list itself can change as a
result of removing an element from the target list in some cases, such as the one you pointed out above. I filed
[JDK-8254040](https://bugs.openjdk.java.net/browse/JDK-8254040) to add the test case you listed above so we avoid a
possible future regression.

So a two-pass algorithm is still needed: the first one to collect the elements to be removed, the second to actually
remove them. While it isn't necessary to use a BitSet to collect the indexes to be removed, that does seems a
reasonable approach. Unless there is a good reason to change it to some other two-pass algorithm, it's probably best to
leave it as-is, in which case this PR and the associated JBS issue can be withdrawn.

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

PR: https://git.openjdk.java.net/jfx/pull/305