JDK-8134655 : SortedList wrapping a FilteredList causes AIOOBE
  • Type: Bug
  • Component: javafx
  • Sub-Component: base
  • Affected Version: 8u60
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: windows_7
  • CPU: x86_64
  • Submitted: 2015-08-27
  • Updated: 2016-06-03
  • 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 8 JDK 9
8u112Fixed 9Fixed
Related Reports
Duplicate :  
Duplicate :  
Duplicate :  
Description
FULL PRODUCT VERSION :
java version "1.8.0_60"
Java(TM) SE Runtime Environment (build 1.8.0_60-b27)
Java HotSpot(TM) 64-Bit Server VM (build 25.60-b23, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]

A DESCRIPTION OF THE PROBLEM :
The Bug can be observed when:
1. Using a TableView that displays items in a SortedList (with the SortedList's Comperator set to the Comperator of the TableView)
2. The SortedList wraps a FilteredList which wraps a ObservableList that is created with FXCollections.observableArrayList() and an extractor.
3.  If the Predicate of the FilteredList uses the same property as the Table's SortOrder, updating an Item so that it is removed from the filteredList will cause the SortedList to throw an ArrayIndexOutOfBoundsException in the findPosition method. 

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Compile the minimal example
2. Run the minimal example
3. java.lang.ArrayIndexOutOfBoundsExceptions are thrown

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The TableView should show the updated entries
ACTUAL -
ArrayIndexOutOfBoundsExceptions are  thrown when running the minimal example and the TableView is no longer updated correctly


ERROR MESSAGES/STACK TRACES THAT OCCUR :

Exception in thread "JavaFX Application Thread" java.lang.ArrayIndexOutOfBoundsException: -1
	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$15(TransformationList.java:106)
	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.transformation.FilteredList.sourceChanged(FilteredList.java:147)
	at javafx.collections.transformation.TransformationList.lambda$getListener$15(TransformationList.java:106)
	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:485)
	at javafx.collections.ListChangeBuilder.endChange(ListChangeBuilder.java:541)
	at javafx.collections.ObservableListBase.endChange(ObservableListBase.java:205)
	at com.sun.javafx.collections.ObservableListWrapper.access$200(ObservableListWrapper.java:45)
	at com.sun.javafx.collections.ObservableListWrapper$1$1.invalidated(ObservableListWrapper.java:75)
	at com.sun.javafx.binding.ExpressionHelper$Generic.fireValueChangedEvent(ExpressionHelper.java:349)
	at com.sun.javafx.binding.ExpressionHelper.fireValueChangedEvent(ExpressionHelper.java:81)
	at javafx.beans.property.ObjectPropertyBase.fireValueChangedEvent(ObjectPropertyBase.java:105)
	at javafx.beans.property.ObjectPropertyBase.markInvalid(ObjectPropertyBase.java:112)
	at javafx.beans.property.ObjectPropertyBase.set(ObjectPropertyBase.java:146)
	at eu.over9000.skadi.ui.DebugSortedBug$TestEntry.setOnline(DebugSortedBug.java:96)
	at eu.over9000.skadi.ui.DebugSortedBug$EntryUpdateService.lambda$new$4(DebugSortedBug.java:130)
	at com.sun.javafx.event.CompositeEventHandler.dispatchBubblingEvent(CompositeEventHandler.java:86)
	at com.sun.javafx.event.EventHandlerManager.dispatchBubblingEvent(EventHandlerManager.java:238)
	at com.sun.javafx.event.EventHandlerManager.dispatchBubblingEvent(EventHandlerManager.java:191)
	at com.sun.javafx.event.BasicEventDispatcher.dispatchEvent(BasicEventDispatcher.java:58)
	at com.sun.javafx.event.EventDispatchChainImpl.dispatchEvent(EventDispatchChainImpl.java:114)
	at com.sun.javafx.event.EventUtil.fireEventImpl(EventUtil.java:74)
	at com.sun.javafx.event.EventUtil.fireEvent(EventUtil.java:54)
	at javafx.event.Event.fireEvent(Event.java:198)
	at javafx.concurrent.EventHelper.fireEvent(EventHelper.java:219)
	at javafx.concurrent.Service.fireEvent(Service.java:853)
	at javafx.concurrent.Service.lambda$new$491(Service.java:554)
	at com.sun.javafx.binding.ExpressionHelper$SingleChange.fireValueChangedEvent(ExpressionHelper.java:182)
	at com.sun.javafx.binding.ExpressionHelper.fireValueChangedEvent(ExpressionHelper.java:81)
	at javafx.beans.property.ObjectPropertyBase.fireValueChangedEvent(ObjectPropertyBase.java:105)
	at javafx.beans.property.ObjectPropertyBase.markInvalid(ObjectPropertyBase.java:112)
	at javafx.beans.property.ObjectPropertyBase.access$000(ObjectPropertyBase.java:51)
	at javafx.beans.property.ObjectPropertyBase$Listener.invalidated(ObjectPropertyBase.java:233)
	at com.sun.javafx.binding.ExpressionHelper$SingleInvalidation.fireValueChangedEvent(ExpressionHelper.java:137)
	at com.sun.javafx.binding.ExpressionHelper.fireValueChangedEvent(ExpressionHelper.java:81)
	at javafx.beans.property.ObjectPropertyBase.fireValueChangedEvent(ObjectPropertyBase.java:105)
	at javafx.beans.property.ObjectPropertyBase.markInvalid(ObjectPropertyBase.java:112)
	at javafx.beans.property.ObjectPropertyBase.set(ObjectPropertyBase.java:146)
	at javafx.concurrent.Task.setState(Task.java:696)
	at javafx.concurrent.Task$TaskCallable.lambda$call$501(Task.java:1434)
	at com.sun.javafx.application.PlatformImpl.lambda$null$174(PlatformImpl.java:295)
	at java.security.AccessController.doPrivileged(Native Method)
	at com.sun.javafx.application.PlatformImpl.lambda$runLater$175(PlatformImpl.java:294)
	at com.sun.glass.ui.InvokeLaterDispatcher$Future.run(InvokeLaterDispatcher.java:95)
	at com.sun.glass.ui.win.WinApplication._runLoop(Native Method)
	at com.sun.glass.ui.win.WinApplication.lambda$null$149(WinApplication.java:191)
	at java.lang.Thread.run(Thread.java:745)


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
package eu.over9000.skadi.ui;

import java.util.Objects;
import java.util.Random;

import javafx.application.Application;
import javafx.beans.Observable;
import javafx.beans.property.ObjectProperty;
import javafx.beans.property.ReadOnlyStringWrapper;
import javafx.beans.property.SimpleObjectProperty;
import javafx.beans.property.StringProperty;
import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.collections.transformation.FilteredList;
import javafx.collections.transformation.SortedList;
import javafx.concurrent.ScheduledService;
import javafx.concurrent.Task;
import javafx.geometry.Insets;
import javafx.scene.Scene;
import javafx.scene.control.TableColumn;
import javafx.scene.control.TableView;
import javafx.scene.layout.Border;
import javafx.stage.Stage;
import javafx.util.Duration;

public class DebugSortedBug extends Application {

	private static final int NUM_CHANNELS = 10;
	private final ObservableList<TestEntry> entryList = FXCollections.observableArrayList(c -> new Observable[]{c.nameProperty(), c.onlineProperty()});

	public static void main(final String[] args) {
		Application.launch(args);
	}

	@Override
	public void start(final Stage stage) throws Exception {
		
		for (int i = 0; i < NUM_CHANNELS; i++) {
			final TestEntry entry = new TestEntry("Entry" + i);
			entryList.add(entry);
			final EntryUpdateService updateService = new EntryUpdateService(entry);
			updateService.start();
		}

		final TableView<TestEntry> table = new TableView<>();
		table.setBorder(Border.EMPTY);
		table.setPadding(Insets.EMPTY);

		final TableColumn<TestEntry, TestEntry.EntryState> onlineColumn = new TableColumn<>("State");
		onlineColumn.setCellValueFactory(p -> p.getValue().onlineProperty());

		final TableColumn<TestEntry, String> nameColumn = new TableColumn<>("Name");
		nameColumn.setCellValueFactory(p -> p.getValue().nameProperty());

		table.getColumns().add(onlineColumn);
		table.getColumns().add(nameColumn);
		
		table.getSortOrder().add(onlineColumn);  // if commented out the bug disappears
		table.getSortOrder().add(nameColumn);

		final FilteredList<TestEntry> filteredList = entryList.filtered(c -> TestEntry.EntryState.ONLINE == c.getOnline());
		final SortedList<TestEntry> sortedList = new SortedList<>(filteredList);
		sortedList.comparatorProperty().bind(table.comparatorProperty());
		table.setItems(sortedList);

		final Scene scene = new Scene(table, 800, 600);
		stage.setScene(scene);
		stage.show();
	}

	private static class TestEntry {

		public enum EntryState {UNKNOWN, OFFLINE, ONLINE}

		private final StringProperty name;
		private final ObjectProperty<EntryState> online;

		public TestEntry(final String channelName) {
			name = new ReadOnlyStringWrapper(channelName);
			online = new SimpleObjectProperty<>(EntryState.UNKNOWN);
		}

		public String getName() {
			return name.get();
		}

		public StringProperty nameProperty() {
			return name;
		}

		public EntryState getOnline() {
			return online.get();
		}

		public void setOnline(final EntryState online) {
			this.online.set(online);
		}

		public ObjectProperty<EntryState> onlineProperty() {
			return online;
		}

		@Override
		public boolean equals(final Object o) {
			if (this == o) {
				return true;
			}
			if (o == null || getClass() != o.getClass()) {
				return false;
			}
			final TestEntry that = (TestEntry) o;
			return Objects.equals(name, that.name);
		}

		@Override
		public int hashCode() {
			return Objects.hash(name);
		}

	}

	private class EntryUpdateService extends ScheduledService<Void> {

		private final Random RND = new Random();

		public EntryUpdateService(final TestEntry toUpdate) {
			setPeriod(Duration.seconds(1));
			setOnSucceeded(event -> {
				final TestEntry.EntryState newState = TestEntry.EntryState.values()[RND.nextInt(TestEntry.EntryState.values().length)];
				toUpdate.setOnline(newState);
			});
		}

		@Override
		protected Task<Void> createTask() {
			return new Task<Void>() {
				@Override
				protected Void call() throws Exception {
					Thread.sleep(RND.nextInt(100)); // simulate REST request
					return null;
				}
			};
		}
	}
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
removing the column that contains the property that is also used for filtering from the table's sort order leads to the expected result


Comments
Approved to backport to 8u-dev (8u112).
03-06-2016

Kevin, could you please approve this identical backport? http://cr.openjdk.java.net/~vadim/8134655/webrev.8u/
03-06-2016

Changeset: b6a7c8d60dbd Author: vadim Date: 2016-05-12 14:53 +0300 URL: http://hg.openjdk.java.net/openjfx/9-dev/rt/rev/b6a7c8d60dbd
12-05-2016

OK, I can see what you are doing now, and it makes sense. +1 on the .00 version
11-05-2016

BTW, the testing of that is performed by the modified tests which are prepared for the JDK-8139848 enhancement which I intend to fix as soon as this gets reviewed.
11-05-2016

I mean it was correct initially where these two lines sets the corresponding this.perm elements values to identity. So the .00 webrev is still ok and .01 is wrong.
11-05-2016

Oops, disregard that, it's really wrong.
11-05-2016

Kevin, this piece of code essentially unsorts the list, so in the end this.perm should be identity. Basically this loop finds the elements which changed places due to the sort and swaps them to their correct positions. While this looks like a usual swap it's actually just setting the element in its position. So while the intermediate perm array could look wrong, the result should be correct. In fact, this.perm[idx] = idx is unneccessary - removed in this webrev http://cr.openjdk.java.net/~vadim/8134655/webrev.01/.
11-05-2016

Btw, the rest looks good and I verified that the test program and new tests pass.
11-05-2016

I think the following is not right, unless I really don't understand it: 207 this.perm[idx] = idx; 208 this.perm[otherIdx] = otherIdx; I would have expected reassigning them as follows: this.perm[sorted[idx].index] = idx; this.perm[sorted[otherIdx].index] = otherIdx; My testing seems to bear this out as the existing patch will cause duplicate elements in the perm array which seems wrong.
11-05-2016

Kevin, Chien, Please review the fix: http://cr.openjdk.java.net/~vadim/8134655/webrev.00/ The immediate cause of this bug was that findPosition method couldn't find the position of the updated element in some cases. If the element in the source list was updated in such a way that it results in removal the element in the sorted list (in this case, the element get filtered out) and also results in changing its position in the sorted list, then this exception would arise. The internal source->sorted permutation array was introduced which simplified searching a lot, with a small added memory burden. In addition this will enable very easy addition of getViewIndex method requested in the JDK-8139848. This fix also fixes JDK-8087508. The test for this particular bug is testMutableElementSortedFilteredChain. Testing of the refactoring is done in all test cases by adding compareIndices method which checks that all source/view indices and corresponding elements are correct. This testing uncovered an issue with the permutation on the unsorted list, the source indices in this case were incorrect, so one check in the testPermutation was removed and this line fixes the issue: 243 sortedTmp[p].index = p;
10-05-2016

Actually this is not a complete duplicate. Wrapping SortedList around FilteredList results in exception even with an extractor.
26-04-2016