"Comparison method violates its general contract" on Array.sort() with randomize

[Finomosec]

Here: http://stackoverflow.com/a/18650169
Someone demonstrates how to use the Array.sort() function to randomize an array.

1. But when we try this with Rhino this happens:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeLo(TimSort.java:747)
        at java.util.TimSort.mergeAt(TimSort.java:483)
        at java.util.TimSort.mergeCollapse(TimSort.java:408)
        at java.util.TimSort.sort(TimSort.java:214)
        at java.util.TimSort.sort(TimSort.java:173)
        at java.util.Arrays.sort(Arrays.java:659)
        at org.mozilla.javascript.NativeArray.js_sort(NativeArray.java:1024)
        at org.mozilla.javascript.NativeArray.execIdCall(NativeArray.java:284)
        at org.mozilla.javascript.IdFunctionObject.call(IdFunctionObject.java:97)
        at org.mozilla.javascript.Interpreter.interpretLoop(Interpreter.java:1473)
        at org.mozilla.javascript.Interpreter.interpret(Interpreter.java:815)
        at org.mozilla.javascript.InterpretedFunction.call(InterpretedFunction.java:109)
        at org.mozilla.javascript.ContextFactory.doTopCall(ContextFactory.java:394)
        ... 15 more

2. In addition to that we can not get a Script-Stacktrace for this Exception.
   Which made it very hard to find the cause of it.
   We are using interpreted mode here.
   Can you adjust the error-handling of this case (or maybe in general for all similar cases) so that the Exception is properly wrapped in a JavaScriptException with the proper JS-stacktrace?

Greetings Fred;

[gbrail]

I tried this with the code in "master":

./gradlew jar
$ java -jar buildGradle/libs/rhino-1.7.8-SNAPSHOT.jar
Rhino 1.7.8-SNAPSHOT 2016 01 15
js> [1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
6,4,3,5,2,1

It looks like it works for me. But if you have a specific test case then please attach it. Thanks!

[Finomosec]

We are using 1.7R4.
And: Java java version "1.7.0_67"
Java(TM) SE Runtime Environment (build 1.7.0_67-b01)
Java HotSpot(TM) 64-Bit Server VM (build 24.65-b04, mixed mode).

It may not trigger on every execution. It depends on the randomization.
How many times did you try?

Can you take a quick look at this method: org.mozilla.javascript.NativeArray.js_sort(NativeArray.java:1024)
To see wether it still uses Arrays.sort() or not. If not then i'd say the chance is high that it is fixed.
Otherwise it might also depend on the Java-Version in use.

Thanks!

[gbrail]

It looks like "js_sort" hasn't changed much in many years. But still I can't reproduce this, even if I call the code a few million times in a loop. But if you have any ideas we can keep trying.

[githideoyon]

If the problem is consistant, i will put some notes.
I have encountered the same issue on JDK7 and JDK8( i guess it is not rhino problem). I thought there are sort algorithm changes made on past JDK. Only the way to work around I found is set

      java.util.Arrays.useLegacyMergeSort = true

On enviroment variable to enforce jvm to use legacy sort algorithm.

[gbrail]

This old, old issue is coming up in other places now!

In your example, do you pass a comparator function to "sort"? If not then we have some work to do on the default comparator and how it handles "undefined..."

[Finomosec]

As linked in the initial post the code is this:
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });

So yes this is a custom comparator.

The problem is as follows:

Java's sort method has a certain "general contract" about comparators. https://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html

That is: if a < b and b < c then a < c

Or this (i'm not 100% sure): (the one above is much more likely)

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

But with the above (random) comparator this is obviously not the case.

This old, old issue is coming up in other places now!

From your statement i can derive that there are other comparators in the wild, that also violate this contract.

Now the point is: This is Java's interpretation of how things should be.

But in JavaScript there is no such thing. The above random sort code should work in JavaScript.
So the bug IMHO is using Java's sort method in the first place.
It might have been convenient, but it is not consistent with standard JavaScript:
https://www.w3schools.com/jsref/jsref_sort.asp

At very least we can see, that the above random sort code works on other JS-engines (like Google Chrome).
Plus there is no mention of any constraints in the docs.

[gbrail]

I agree and sorry for reading so fast. The comparator there is not good code, obviously, but according to the JavaScript spec it should not throw an exception. The solution is to replace Arrays.sort with a different sorting algorithm. Any suggestions on which one would be best? In the meantime, I created a new PR that does two things: Makes doubly-sure that the default case (non-comparator) does not behave badly, and throws a proper JavaScript exception instead of IllegalArgumentException. I'd appreciate a look before I merge it! #311

…

On Fri, Jul 28, 2017 at 1:06 AM, Finomosec ***@***.***> wrote: As linked in the initial post the code is this: [1,2,3,4,5,6].sort(function() { return .5 - Math.random(); }); So yes this is a custom comparator. The problem is as follows: Java's sort method has a certain "general contract" about comparators. https://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html That is: if a < b and b < c then a < c Or this (i'm not 100% sure): (the one above is much more likely) The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S. But with the above (random) comparator this is obviously not the case. This old, old issue is coming up in other places now! From your statement i can derive that there are other comparators in the wild, that also violate this contract. Now the point is: This is Java's interpretation of how things should be. But in JavaScript there is no such thing. The above random sort code should work in JavaScript. So the bug IMHO is using using Java's sort method in the first place. It might have been convenient, but it is not consistent with standard JavaScript: https://www.w3schools.com/jsref/jsref_sort.asp — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#255 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAf0a3JwbqiRw1GJ9KTHmWHz_2jHXS6jks5sSZaXgaJpZM4GkD2x> .

[whitlockjc]

Can we close this since #311 was merged?

[gbrail]

Array.sort now uses a custom sort method that will happily sort things according to whatever crazy ordering the caller provides.

[eduardoels]

I have a solution, when I want to sort numbers and an array element is null, then I put 0, and the error disappears, is needed to care that the size of each row in the bidimensional arrays must be the same

[vinayhegde2013]

@Finomosec Thanks for your answer.