swift.Array<E>.sort(array, isOrderedBefore) crash

Elements Silver
1

Having trouble providing a minimal replicable sample but I’m getting a crash calling swift.Array<E>.sort(array, { $0 > $1 })

    Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
             at java.util.TimSort.mergeHi(TimSort.java:864)
             at java.util.TimSort.mergeAt(TimSort.java:481)
             at java.util.TimSort.mergeForceCollapse(TimSort.java:422)
             at java.util.TimSort.sort(TimSort.java:219)
             at java.util.TimSort.sort(TimSort.java:169)
             at java.util.Arrays.sort(Arrays.java:2010)
             at java.util.Collections.sort(Collections.java:1883)
             at swift.__Extension_ISequence.sort()

It looks like it might be because the Comparator.compare function never returns 0 for items of equal value (it’s implemented to only ever return 1 or -1)

2

I tried creating a blank android application (api 26), where the JDK for Arrays.sort uses TimSort (the source of the error), with exactly the same array entries I had the crash with (quite a long list, with several duplicated entries) but it didn’t crash.

THEN I changed the comparison function to be { $0?.toUpperCase() > $1?.toUpperCase() } and it crashed. So now I have this set of data:

	let names1=["INCOMPLETE PROFILE","UNVERIFIED PROFILE","SALLY CHEN","UNIT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","桃太郎","PAUL'S IDEA","アンパンマン",
	"TEST CUSTOMER","JIM'S CLONE","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","SAME DOUBLE CARD CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","ECARD LIMIT BEFORE VERIFYING","SAME DOUBLE CARD CUSTOMER","EXPIRY DATE CUSTOMER",
	"EXPIRY DATE CUSTOMER","見張粗末","EXPIRY DATE CUSTOMER","TEST CUSTOMER","TEST","TEST","TEST","RESPONDER","RESPONDER","RESPONDER","RESPONDER","RESPONDER","UNIT TEST","BLUECHAIN","TEST CUSTOMER","UNVERIFIED PROFILE",
	"UNVERIFIED PROFILE","UNVERIFIED PROFILE","WEB PAYMENT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE",
	"SALLY CHEN","SALLY CHEN","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNIT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","桃太郎","PAUL'S IDEA","アンパンマン",
	"TEST CUSTOMER","JIM'S CLONE","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","SAME DOUBLE CARD CUSTOMER","LITTLE SHOES","TEST CUSTOMER","UNVERIFIED PROFILE","TEST CUSTOMER","UNVERIFIED PROFILE",
	"ECARD LIMIT BEFORE VERIFYING","SAME DOUBLE CARD CUSTOMER","EXPIRY DATE CUSTOMER","EXPIRY DATE CUSTOMER","見張粗末","EXPIRY DATE CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST","TEST","BLUECHAIN",
	"TEST CUSTOMER","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","TESTB CUSTOMERB","TESTB CUSTOMERB","TESTA CUSTOMERA","TESTB CUSTOMERB","TESTA CUSTOMERA","TESTC CUSTOMERC",
	"BLUECHAIN","BLUECHAIN","RESPONDER","RESPONDER","RESPONDER","RESPONDER","RESPONDER","UNIT TEST","UNVERIFIED PROFILE","INCOMPLETE PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","INCOMPLETE PROFILE","UNVERIFIED PROFILE",
	"UNVERIFIED PROFILE","Q Q"]

Which definitely does crash

swift.Array<String>.sort(names, { $0 < $1 })

Even just removing the very last element fixes it though, haven’t worked out what the exact culprit is.

3

Can you define “crash”? whats the exact exception/error you are getting? I’ll have a look in a bit.

4

I can repro an exception with this code:

var names1=["INCOMPLETE PROFILE","UNVERIFIED PROFILE","SALLY CHEN","UNIT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","桃太郎","PAUL'S IDEA","アンパンマン",
"TEST CUSTOMER","JIM'S CLONE","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","SAME DOUBLE CARD CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","ECARD LIMIT BEFORE VERIFYING","SAME DOUBLE CARD CUSTOMER","EXPIRY DATE CUSTOMER",
"EXPIRY DATE CUSTOMER","見張粗末","EXPIRY DATE CUSTOMER","TEST CUSTOMER","TEST","TEST","TEST","RESPONDER","RESPONDER","RESPONDER","RESPONDER","RESPONDER","UNIT TEST","BLUECHAIN","TEST CUSTOMER","UNVERIFIED PROFILE",
"UNVERIFIED PROFILE","UNVERIFIED PROFILE","WEB PAYMENT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE",
"SALLY CHEN","SALLY CHEN","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNIT TEST","TEST CUSTOMER","LITTLE SHOES","UNVERIFIED PROFILE","UNVERIFIED PROFILE","桃太郎","PAUL'S IDEA","アンパンマン",
"TEST CUSTOMER","JIM'S CLONE","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","SAME DOUBLE CARD CUSTOMER","LITTLE SHOES","TEST CUSTOMER","UNVERIFIED PROFILE","TEST CUSTOMER","UNVERIFIED PROFILE",
"ECARD LIMIT BEFORE VERIFYING","SAME DOUBLE CARD CUSTOMER","EXPIRY DATE CUSTOMER","EXPIRY DATE CUSTOMER","見張粗末","EXPIRY DATE CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST CUSTOMER","TEST","TEST","BLUECHAIN",
"TEST CUSTOMER","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","TESTB CUSTOMERB","TESTB CUSTOMERB","TESTA CUSTOMERA","TESTB CUSTOMERB","TESTA CUSTOMERA","TESTC CUSTOMERC",
"BLUECHAIN","BLUECHAIN","RESPONDER","RESPONDER","RESPONDER","RESPONDER","RESPONDER","UNIT TEST","UNVERIFIED PROFILE","INCOMPLETE PROFILE","UNVERIFIED PROFILE","UNVERIFIED PROFILE","INCOMPLETE PROFILE","UNVERIFIED PROFILE",
"UNVERIFIED PROFILE","Q Q"]

names1.sort() { $0 < $1 }

it gives a

!> Fatal exception of type java.lang.IllegalArgumentException on thread 0001 ()
!> Message: java.lang.IllegalArgumentException: Comparison method violates its general contract!

I’m guessing this is related to how the underlying java.util.ArrayList class expects three states of comparison (less, greater or equal), but the Swift API only accounts for “less” and “not less”, basically:

    public mutating func sort(by isOrderedBefore: (T, T) -> Bool) {
        makeUnique()
        #if JAVA
        java.util.Collections.sort(list, class java.util.Comparator<T> { func compare(a: T, b: T) -> Int32 {
            if isOrderedBefore(a,b) {
                return 1
            } else {
                return -1
            }
        }})

I suppose we’ll need to rework this and replace it with a custom sort algorithm, in Swift Base Library…

5

Thanks, logged as bugs://80968

6

Confirmed. if I inject, as hack/workaround, this line:

        java.util.Collections.sort(list, class java.util.Comparator<T> { func compare(a: T, b: T) -> Int32 {
            if a == b { return 0 } // HACK
            if isOrderedBefore(a,b) {
                return 1
            } else {
                return -1
            }
        }})

it sorts ok.

7

Fixed on GitHub and for next week.

Note that the latest SBL on GitHub needs .2323 or later, as this contains our switch to [T] being a struct, not a class, and .2323 has compiler fixes necessary for that. Also note that I found/logged some related problems with structs on Java that will need to be addressed next week. (IOW, while you can grab the latest code from GitHib, and it has this fixed, you’ll in general probably want to wait for .2325 next Friday).

8

bugs://80968 got closed with status fixed.

9

Except that sorts in reverse order… (but that’s been like that a long time, and easy to work around)

10

An alternative hack would be

if isOrderedBefore(a, b)
   return -1
else ifOrderedBefore(b, a)
   return 1
else 
   return 0

But might be a bit inefficient…

11

Hm, that would be easily fixed by reversing the Quicksort, off it was the case, but imho its correct?

names1.sort() { $0 < $1 }

sorts ascending which, seems right?