RFR: 8253086: Optimization of removeAll and retainAll of ObservableListWrapper [v4]
Nir Lisker
nlisker at openjdk.java.net
Tue Oct 6 17:13:04 UTC 2020
On Mon, 5 Oct 2020 19:22:41 GMT, Kevin Rushforth <kcr at openjdk.org> wrote:
>>> 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.
@kleopatra Thanks for the investigation. I had a feeling there is a practical reason and not a lack of skill :)
If there is no way to do removal simultaneously then we indeed need to keep the 2-pass approach.
-------------
PR: https://git.openjdk.java.net/jfx/pull/305
More information about the openjfx-dev
mailing list