Bugzilla – Full Text Bug Listing
| Summary: | JavaElementComparator: Comparison method violates its general contract (was: Trying to create new working set as part of an import fails (on Java8) | ||
|---|---|---|---|
| Product: | [Eclipse Project] JDT | Reporter: | Thomas Schindl <tom.schindl> |
| Component: | UI | Assignee: | JDT-UI-Inbox <jdt-ui-inbox> |
| Status: | CLOSED WONTFIX | QA Contact: | |
| Severity: | normal | ||
| Priority: | P3 | CC: | daniel_megert, error-reports-inbox, markus.kell.r, noopur_gupta, stephan.herrmann, timo.kinnunen |
| Version: | 4.5 | ||
| Target Milestone: | --- | ||
| Hardware: | PC | ||
| OS: | Mac OS X | ||
| Whiteboard: | stalebug | ||
| Attachments: | |||
|
Description
Thomas Schindl
moveing to JDT because the comparator is from them (In reply to Thomas Schindl from comment #1) > moveing to JDT because the comparator is from them Can you elaborate? As the stack trace doesn't really show any JDT owned comparator did you observe the situation in the debugger? Or did you infer via code inspection that probably a JavaElementComparator was involved? You also didn't say anything about reproducibility, steps and all that :) I looked at the stack which mentions org.eclipse.jdt.internal.ui.workingsets.JavaWorkingSetPage and the comparator is set in JavaWorkingSetPage#configureTree and is of type JavaElementComparator Looking at ViewerComparator I saw that it logs more data Workaround for comparator violation: - set system property java.util.Arrays.useLegacyMergeSort=true - use a 1.6 JRE message: Comparison method violates its general contract! this: org.eclipse.jdt.ui.JavaElementComparator comparator: com.ibm.icu.text.RuleBasedCollator array: > at.bestsolution.fx.slide.show [fxslide NO-HEAD] > at.bestsolution.fx.slide.show.sample [fxslide NO-HEAD] > jfxextras [jfxtras 8.0] > miglayout [miglayout master] at.bestsolution.efxclipse.animation.pop at.bestsolution.efxclipse.jemmy [efxclipse_addons master] at.bestsolution.fx.slide.dsl at.bestsolution.fx.slide.dsl.tests at.bestsolution.fx.slide.dsl.ui at.bestsolution.fx.slide.model at.bestsolution.fx.slide.model.ecore bbb bbb.tests CompilerTest controlsfx controlsfx-samples dummy.app dummy.app.jemmy External Plug-in Libraries fxsampler FXTest nnnnn org.eclipse.fx.core [efxclipse master] org.eclipse.fx.core.databinding [efxclipse master] org.eclipse.fx.core.databinding.tests [efxclipse master] org.eclipse.fx.core.di [efxclipse master] org.eclipse.fx.core.di.context [efxclipse master] org.eclipse.fx.core.di.context.tests [efxclipse master] org.eclipse.fx.core.fxml [efxclipse master] org.eclipse.fx.core.guice [efxclipse master] org.eclipse.fx.core.log4j [efxclipse master] org.eclipse.fx.core.p2 [efxclipse master] org.eclipse.fx.core.slf4j [efxclipse master] org.eclipse.fx.demo.contacts [efxclipse master] org.eclipse.fx.demo.contacts.app [efxclipse master] org.eclipse.fx.demo.contacts.edit [efxclipse master] org.eclipse.fx.demo.contacts.edit.tests [efxclipse master] org.eclipse.fx.emf.databinding [efxclipse master] org.eclipse.fx.emf.edit.ui [efxclipse master] org.eclipse.fx.formats.svg [efxclipse master] org.eclipse.fx.ide.ant [efxclipse master] org.eclipse.fx.ide.converter [efxclipse master] org.eclipse.fx.ide.css [efxclipse master] org.eclipse.fx.ide.css.controlsfx org.eclipse.fx.ide.css.cssext [efxclipse master] org.eclipse.fx.ide.css.cssext.proposals [efxclipse master] org.eclipse.fx.ide.css.cssext.tests [efxclipse master] org.eclipse.fx.ide.css.cssext.ui [efxclipse master] org.eclipse.fx.ide.css.jfx [efxclipse master] org.eclipse.fx.ide.css.jfx2 [efxclipse master] org.eclipse.fx.ide.css.jfx8 [efxclipse master] org.eclipse.fx.ide.css.jfxextras org.eclipse.fx.ide.css.tests [efxclipse master] org.eclipse.fx.ide.css.ui [efxclipse master] org.eclipse.fx.ide.fxgraph [efxclipse master] org.eclipse.fx.ide.fxgraph.tests [efxclipse master] org.eclipse.fx.ide.fxgraph.ui [efxclipse master] org.eclipse.fx.ide.fxml [efxclipse master] org.eclipse.fx.ide.fxml.compiler [efxclipse master] org.eclipse.fx.ide.java6 [efxclipse master] org.eclipse.fx.ide.jdt.core [efxclipse master] org.eclipse.fx.ide.jdt.ui [efxclipse master] SampleForMobile TestFXSample TestNull > org.eclipse.fx.ide.l10n [efxclipse master] > org.eclipse.fx.ide.l10n.ui [efxclipse master] org.eclipse.fx.ide.l10n.tests [efxclipse master] org.eclipse.fx.ide.model [efxclipse master] org.eclipse.fx.ide.pde.core [efxclipse master] org.eclipse.fx.ide.pde.java7 [efxclipse master] org.eclipse.fx.ide.pde.ui [efxclipse master] org.eclipse.fx.ide.pde.ui.e4 [efxclipse master] org.eclipse.fx.ide.rrobot [efxclipse master] org.eclipse.fx.ide.rrobot.dsl [efxclipse master] org.eclipse.fx.ide.rrobot.dsl.tests [efxclipse master] org.eclipse.fx.ide.rrobot.dsl.ui [efxclipse master] org.eclipse.fx.ide.rrobot.model [efxclipse master] org.eclipse.fx.ide.ui [efxclipse master] org.eclipse.fx.ide.ui.mobile.sim.device [efxclipse master] org.eclipse.fx.ide.ui.mobile.sim.launch [efxclipse master] org.eclipse.fx.ide.ui.preview [efxclipse master] org.eclipse.fx.javafx [efxclipse master] org.eclipse.fx.osgi [efxclipse master] org.eclipse.fx.osgi.util [efxclipse master] org.eclipse.fx.runtime.doc [efxclipse master] > org.eclipse.fx.runtime.swt [efxclipse master] BlaBlaBla BlaBlaBlaBla Blum DummyJavaFX HHHHH InferenceProblem MySample.app MySample.app.feature org.eclipse.fx.shared.doc org.eclipse.fx.testcases.e4 org.eclipse.fx.ui.animation org.eclipse.fx.ui.controls org.eclipse.fx.ui.controls.sample org.eclipse.fx.ui.databinding org.eclipse.fx.ui.di org.eclipse.fx.ui.di.interopt org.eclipse.fx.ui.dialogs org.eclipse.fx.ui.keybindings org.eclipse.fx.ui.keybindings.e4 org.eclipse.fx.ui.keybindings.generic org.eclipse.fx.ui.mobile org.eclipse.fx.ui.mobile.sensors.api org.eclipse.fx.ui.modelviewer org.eclipse.fx.ui.panes org.eclipse.fx.ui.services org.eclipse.fx.ui.theme org.eclipse.fx.ui.viewer org.eclipse.fx.ui.viewer.demo org.eclipse.fx.ui.viewer.javafx org.eclipse.fx.ui.workbench.base org.eclipse.fx.ui.workbench.fx org.eclipse.fx.ui.workbench.renderers.base org.eclipse.fx.ui.workbench.renderers.fx org.eclipse.fx.ui.workbench.services org.eclipse.fx.ui.workbench3 org.eclipse.jdt.nullanalysis org.eclipse.jdt.nullanalysis.tests org.eclipse.jdt.nullanalysis.ui org.jemmy.fx.repackaged sssss MySample.app.jemmy MySample.app.jemmy.feature MySample.app.product MySample.app.releng Sample SampleJ8 SampleProject Samplemedia Samplemedia.feature Samplemedia.product Test TestDND TestFX TestJ7 TestJ8 TestJ8Plugin TestLayout TestMe TestSWT addons_homepage at.bestsolution.efxclipse.jemmy.feature at.bestsolution.efxclipse.jemmy.junit.feature at.bestsolution.efxclipse.less at.bestsolution.efxclipse.less.feature at.bestsolution.efxclipse.releng at.bestsolution.efxclipse.releng.assembler at.bestsolution.efxclipse.robovm at.bestsolution.efxclipse.robovm.feature at.bestsolution.efxclipse.updatesite at.bestsolution.fx.slide.dsl.sdk at.bestsolution.lego at.bestsolution.lego.elements at.bestsolution.lego.sdk at.bestsolution.lego.tests at.bestsolution.lego.ui at.bestsolution.swt.css bbbb bla.bla.app bla.bla.app.feature bla.bla.app.product bla.bla.app.releng blabla dummy.app.feature dummy.app.jemmy.feature dummy.app.product dummy.app.releng efxclipse_homepage hgh maven-deploy org.eclipse.fx.code.compensator.hsl org.eclipse.fx.code.compensator.hsl.sdk org.eclipse.fx.code.compensator.hsl.tests org.eclipse.fx.code.compensator.hsl.ui org.eclipse.fx.core.feature org.eclipse.fx.core.shared.feature org.eclipse.fx.core.shared.updatesite org.eclipse.fx.demo.media org.eclipse.fx.emf.edit.ui.tests org.eclipse.fx.experimental.releng org.eclipse.fx.experimental.updatesite org.eclipse.fx.ide.basic.feature org.eclipse.fx.ide.compiler.releng org.eclipse.fx.ide.converter.feature org.eclipse.fx.ide.css.cssext.ui.debug org.eclipse.fx.ide.css.feature org.eclipse.fx.ide.feature org.eclipse.fx.ide.fxgraph.feature org.eclipse.fx.ide.fxml.feature org.eclipse.fx.ide.l10n.feature org.eclipse.fx.ide.mobile.feature org.eclipse.fx.ide.pde.feature org.eclipse.fx.ide.releng org.eclipse.fx.ide.rrobot.feature org.eclipse.fx.ide.updatesite org.eclipse.fx.releng org.eclipse.fx.releng.devsetup org.eclipse.fx.runtime.e4fx.feature org.eclipse.fx.runtime.examples.swt org.eclipse.fx.runtime.feature org.eclipse.fx.runtime.min.feature org.eclipse.fx.runtime.swt.compat org.eclipse.fx.samples.fxml.compiler org.eclipse.fx.shared.releng org.eclipse.fx.swtfx.feature org.eclipse.fx.target.feature org.eclipse.fx.target.rcp.feature org.eclipse.fx.target.rcp4.feature org.eclipse.fx.testcases.dnd.app org.eclipse.fx.testcases.dnd.app.feature org.eclipse.fx.testcases.dnd.app.jemmy org.eclipse.fx.testcases.dnd.app.jemmy.feature org.eclipse.fx.testcases.dnd.app.product org.eclipse.fx.testcases.dnd.app.releng org.eclipse.fx.testcases.l10n.app org.eclipse.fx.testcases.l10n.app.feature org.eclipse.fx.testcases.l10n.app.product org.eclipse.fx.testcases.l10n.app.releng org.eclipse.fx.ui.controls.demo org.eclipse.fx.ui.panes.demo org.eclipse.fx.updatesite org.eclipse.jdt.annotation_v1 org.eclipse.jdt.nullanalysis.sdk org.eclipse.osgi org.eclipse.simrel.build org.eclipse.wst.sse.ui org.eclipse.xtext.example.domainmodel org.eclipse.xtext.example.domainmodel.tests org.eclipse.xtext.example.domainmodel.ui test.app test.app.feature test.app.product test.app.releng twemoji window-context-activation.app window-context-activation.app.feature window-context-activation.app.product Steps would be nice. Tom, can you reproduce the problem? I don't see anything wrong in the JavaElementComparator, but I know that such problems are notoriously hard to find. It's strange that the exception happens in AbstractWorkingSetWizardPage.createControl(AbstractWorkingSetWizardPage.java:223) in the call to "fTree.refresh(true);" and not already on line 212 in "createTree(leftComposite);", where the initial sorting takes place. Could it be that you were checking out projects or switching branches in the background? I don't get an exception when I try to sort the project names from comment 4 using ICU's Collator.getInstance(), so I think ICU is fine. I removed the "> " and " [...]", since they are just artifacts of the label provider, but not used while sorting. Unfortunately today I can not reproduce it (although I'm doing exactly the same i did yesterday), I was not checking out stuff but tried to import some samples from a zip file. Please reopen if you have further information. *** Bug 468921 has been marked as a duplicate of this bug. *** (In reply to comment #6) > I don't get an exception when I try to sort the project names from comment 4 > using ICU's Collator.getInstance(), so I think ICU is fine. I removed the "> " > and " [...]", since they are just artifacts of the label provider, but not used > while sorting. I think they are used in sorting after all. JavaElementComparator calls getNonJavaElementLabel() method, which for ContentViewers calls their label provider's getText() method with the element. The default label provider simply returns what the element's toString() method is returning. JavaElementComparator then compares two such strings with each other and returns the result. This same procedure is followed in ViewerComparator's debug printing code, so the fact that labels beginning with the "> " prefix appear in the printed array strongly suggests such prefixes can influence the sort. The array looks to be partially sorted. In particular, these items are in the correct order and they are at very start of the array: > at.bestsolution.fx.slide.show [fxslide NO-HEAD] > at.bestsolution.fx.slide.show.sample [fxslide NO-HEAD] > jfxextras [jfxtras 8.0] > miglayout [miglayout master] at.bestsolution.efxclipse.animation.pop In contrast, these lines look very suspicious to me: org.eclipse.fx.osgi [efxclipse master] org.eclipse.fx.osgi.util [efxclipse master] org.eclipse.fx.runtime.doc [efxclipse master] > org.eclipse.fx.runtime.swt [efxclipse master] org.eclipse.fx.shared.doc org.eclipse.fx.testcases.e4 org.eclipse.fx.ui.animation If not for that one project in the middle these items would already be correctly sorted with respect to each other. Perhaps the org.eclipse.fx.runtime.swt project was refreshed in the middle of the sort, causing its toString() to change and causing an already sorted region of the array to break in the middle. . (In reply to Timo Kinnunen from comment #10) > I think they are used in sorting after all. JavaElementComparator calls > getNonJavaElementLabel() method, which for ContentViewers calls their label > provider's getText() method with the element. Not in this case. The "if (viewer instanceof ContentViewer)" is just a last-resort branch. When sorting IJavaProjects, it first gets the IWorkbenchAdapter, which is a JavaWorkbenchAdapter whose getLabel(..) method uses JavaElementLabels#getTextLabel(..). I.e. the undecorated project name. To get to the bottom of this, we could better instrument the situation in ViewerComparator#sort(..). Instead of just logging the problem, we could: a) retry the Arrays.sort(..) call. If it doesn't fail the second time, then it's an unstable comparator or the elements to be sorted return unstable data. b) implement a trivial insertion sort as a fallback. During the sort, verify validity of the comparator and report the actual breakage (unlike TimSort's unhelpfully general "Comparison method violates its general contract!" message). Once (b) is implemented, we can even avoid throwing an exception and just log the problem and then continue, even if the elements are not fully ordered in the end (like it was before Java 7). Created attachment 254118 [details]
Small utility function testing that a Comparator implements its contract
Here is a smallish utility function which can be used to test that a Comparator implements its contract correctly. Specifically, that:
"The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0. Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z."
For a given set of objects, it exhaustively checks that the original Comparator satisfies the compareTo method contract for every possible input combination.
The returned Comparator wraps the original and checks that all compared objects have been seen previously (that is, a collection is not modified concurrently) and that the original Comparator returns consistent results. For example, it can be installed in ViewerComparator like this:
Arrays.sort(elements, ComparatorContract.enforce(elements, o -> getLabel(viewer, o), new Comparator() {
@Override
public int compare(Object a, Object b) {
return ViewerComparator.this.compare(viewer, a, b);
}
}));
(In reply to Timo Kinnunen from comment #13) > Created attachment 254118 [details] > Small utility function testing that a Comparator implements its contract Thanks Timo, that looks very helpful! The exhaustive check would be interesting for small and reproducible use cases. Unfortunately there are two problems that make it unacceptable for general use in the ViewerComparator: (1) The index into "byte[] results" starts to overflow at Math.sqrt(Integer.MAX_VALUE), i.e. 46341 elements (2) O(n^3) performance means it already needs 4s to check 1000 elements: public static void main(String[] args) { int N= 1000; Object[] a= Stream.iterate(N, x -> x - 1).limit(N).toArray(); Comparator<Object> sort= (x, y) -> (Integer) x - (Integer) y; System.out.println(Arrays.asList(a)); time("sort: ", () -> Arrays.sort(a, sort)); System.out.println(Arrays.asList(a)); time("enforce: ", () -> ComparatorContract.enforce(a, Object::toString, sort)); System.out.println(Arrays.asList(a)); } static void time(String label, Runnable runnable) { long start= System.currentTimeMillis(); runnable.run(); long time= System.currentTimeMillis() - start; System.out.println(label + time); } Moreover, I think a single witness would usually be enough to pinpoint a problem in the comparator. That's why I suggested to go with a simple sorting algorithm that would still be reasonably quick and that could even run to the end and result in an "almost" sorted array like in Java < 7. Created attachment 254154 [details]
Optimized utility function testing Comparator contract
Good points all around. This is an optimized version of the utility function. On my machine the old version took ~5000ms to run on 1000 items, this one takes about 78ms on a first run and about 30ms on the runs after that. This improvement over time is probably due to JIT compilation.
Unfortunately the O(N^3) nature still means that more than 2000 items takes more than 100ms which is not good for UI use. Dropping checks to get to O(N^2) gives us up to about 10000-20000 items, taking ~1sec while still catching any unstable comparisons. Beyond that requires further optimizations or changing the algorithm. Or just skipping the enforcement for such large views.
Also there's no more integer overflow but w/e :)
Created attachment 254160 [details] Fixed and improved utility function testing Comparator contract This version fixes a bug and improves generated messages by showing the indexes of the involved compared objects in the array being sorted. This helps in case their labels are exactly the same. I've also filed Bug 469547 for JDT UI and Bug 469548 for Mylyn for the problems revealed so far. No sign of this one yet, though. This bug hasn't had any activity in quite some time. Maybe the problem got resolved, was a duplicate of something else, or became less pressing for some reason - or maybe it's still relevant but just hasn't been looked at yet. As such, we're closing this bug. If you have further information on the current state of the bug, please add it and reopen this bug. The information can be, for example, that the problem still occurs, that you still want the feature, that more information is needed, or that the bug is (for whatever reason) no longer relevant. -- The automated Eclipse Genie. |