JDK-8087508 : SortedList is fragile when Comparator is poorly implemented (ArrayIndexOutOfBoundsException)
  • Type: Bug
  • Component: javafx
  • Sub-Component: base
  • Affected Version: 8u40
  • Priority: P3
  • Status: Closed
  • Resolution: Duplicate
  • Submitted: 2015-01-30
  • Updated: 2016-05-12
  • Resolved: 2016-05-12
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 9
9Resolved
Related Reports
Duplicate :  
Duplicate :  
Description
When using SortedList on a ListView, it can happen that ListView won't update anymore, if the Comparator is poorly implemented. SortedList throws an ArrayIndexOutOfBoundsException.

I've seen this with a more complex Comparator, which returned inconsistent results, e.g. o1 didn't always compare to o2 in the opposite way as the o2 compares to the o1.
Implemeting well-behaved complex comparators is not always easy, so things like this can happen and I wonder if you can protect against it.

(for some reason I didn't even seen any stacktrace in my real app, my ListView just stopped udating itself and I wondered what's up).

Stacktrace:
Exception in thread "JavaFX Application Thread" java.lang.ArrayIndexOutOfBoundsException: -5
	at javafx.collections.transformation.SortedList.findPosition(SortedList.java:318)
	at javafx.collections.transformation.SortedList.removeFromMapping(SortedList.java:359)
	at javafx.collections.transformation.SortedList.addRemove(SortedList.java:389)
	at javafx.collections.transformation.SortedList.sourceChanged(SortedList.java:105)
	at javafx.collections.transformation.TransformationList.lambda$getListener$16(TransformationList.java:106)
	at javafx.collections.transformation.TransformationList$$Lambda$77/10143061.onChanged(Unknown Source)
	at javafx.collections.WeakListChangeListener.onChanged(WeakListChangeListener.java:88)
	at com.sun.javafx.collections.ListListenerHelper$SingleChange.fireValueChangedEvent(ListListenerHelper.java:164)
	at com.sun.javafx.collections.ListListenerHelper.fireValueChangedEvent(ListListenerHelper.java:73)
	at javafx.collections.ObservableListBase.fireChange(ObservableListBase.java:233)
	at javafx.collections.ListChangeBuilder.commit(ListChangeBuilder.java:482)
	at javafx.collections.ListChangeBuilder.endChange(ListChangeBuilder.java:541)
	at javafx.collections.ObservableListBase.endChange(ObservableListBase.java:205)
	at javafx.collections.ModifiableObservableListBase.remove(ModifiableObservableListBase.java:183)


Sample Code (just click the button a few times). You can also always return 1 from the comparator to trigger it immediately:


import javafx.application.Application;
import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.ListView;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;

import java.util.Random;

public class TestApp3 extends Application {
    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(final Stage stage) throws Exception {

        ObservableList<Integer> list = FXCollections.observableArrayList();
        list.addAll(0, 2, 9, 6, 4, 5, 3, 1, 7, 8);

        ListView<Integer> listView = new ListView<>();
        listView.setItems(list.sorted((o1, o2) ->
                // This is the bad comparator.
                // if o1 = 7 and o2 == 8 returns 1
                // if o1 = 8 and o2 == 7 also returns 1
                // This seems to confuse SortedList
                o1 < 5 ? o1.compareTo(o2) : 1));

        Button button = new Button("Click me");
        button.setOnAction(actionEvent -> {
            // Remove the first item from list.
            list.remove(0);
            // Add new random integer between 0 (inclusive) and 10 (exclusive).
            list.add(new Random().nextInt(10));
            System.out.println(list);
        });

        Scene scene = new Scene(new VBox(listView, button));
        stage.setScene(scene);
        stage.show();
    }
}
Comments
Regarding initial issue, I don't think it's reasonable to try to support Comparators which don't follow the spec which clearly states that 'The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.' As for the other use case, this can be done by using FXCollections.observableArrayList(Callback<E, Observable[]> extractor) method which attaches a listener to elements of the list and is intended to use in these scenarios.
17-02-2016

Regarding the above comments, I still think that P3 is the correct priority since it is seems not a primary use case for SortedList. I worry that your proposed solution will lead to O(n^2) performance, so that would need to be taken into account. Vadim can comment on it when he evaluates the bug.
14-01-2016

Also from David Gilbert: ------------------------------------ In my opinion the bug is more serious than the bug report suggests since, as the test case shows, it does not require a ���bad��� comparator. It seems that SortedList makes assumptions about its internal state (that the elements are always in their correct sorted order) which cannot be guaranteed when the elements are mutable objects.
14-01-2016

Also from David Gilbert: ------------- Just a followup on this. In the end, we copied the SortedList.java into our own CustomSortedList.java file and added the following code to the findPosition() method to resolve the issue. The call to findPosition() on line 318 can fail if the elements in the ���sorted��� array are not in fact in order (because of a change to a field of one of the elements). In this case, we find the actual position by iterating over the items in the array���not so efficient, but I don���t see a way around that because there is no way to guarantee that the elements are in any particular order. [see attached "code-sample.png" image] Update: line 321 should read ���if (sorted[i].e == e) {��� otherwise the fix won���t work.
14-01-2016

Also from David Gilbert: ---------- A better (I think) workaround to trigger the list re-sort is: // Comparator c = sorted.getComparator(); // sorted.setComparator(null); // sorted.setComparator(c);
14-01-2016

The following comment is from David Gilbert: ------------------------------- I have been looking into a JavaFX issue at work, which is the same as this existing bug (it is related to removing items from an ObservableList that is wrapped in a SortedList --- we hit the issue because this is a the setup for JavaFX TableViews with sortable columns): The bug analysis is a bit misleading since it suggests that you need to have a poorly implemented Comparator for this exception to occur, but that is not the case (see my Junit test case below). The real issue is that the SortedList assumes that it has the correct order for the items in the source list, but this can be messed up easily if the items in the source list are mutable. As you know, the ObservableList only triggers events when items are added or removed from the list, but not when an item has some modification made to it. In the latter case, the SortedList has no way to know that the source list has changed, and so it cannot update its state to reflect a potentially new sort order. I have created a simple Junit test to reproduce the problem: import static org.junit.Assert.assertEquals; import javafx.collections.FXCollections; import javafx.collections.ObservableList; import javafx.collections.transformation.SortedList; import org.junit.Test; public class SortedListTest { static class Item { private String name; public Item(String name) { this.name = name; } public String getName() { return this.name; } public void setName(String name) { this.name = name; } public boolean equals(Object obj) { if (!(obj instanceof Item)) { return false; } Item that = (Item) obj; return this.name.equals(that.name); } public String toString() { return "[" + this.name + "]"; } } @Test public void testSortedListBug() { Item item1 = new Item("A"); Item item2 = new Item("B"); Item item3 = new Item("C"); ObservableList<Item> source = FXCollections.observableArrayList(item1, item2, item3); SortedList<Item> sorted = new SortedList<>(source); sorted.setComparator((s1, s2) -> { return s1.getName().compareTo(s2.getName()); }); item1.setName("Evil"); // SortedList doesn't know we did this // a workaround - uncomment this, it will trigger a resort for the SortedList, then everything is in a good state for the remove(item1) call //ObservableList<Item> copy = FXCollections.observableArrayList(source); //source.setAll(copy); source.remove(item1); assertEquals(item2, sorted.get(0)); assertEquals(item3, sorted.get(1)); } } This bug is causing us to have to rethink how we provide sorting on editable tables in our application (workaround for now is to call tableView.sort() before any row is removed from a table).
14-01-2016