java.lang.ArrayIndexOutOfBoundsException when calling List.sort on custom enum with Order

[Andriamanitra]

I ran into this issue while solving advent of code 2023 day 7 using Flix version 0.42.0. I was still working on the code so the Order was not well defined, but I would still expect it to run and return some kind of list (even if it's in a weird order) instead of running into index out of bounds exception.

Here's a sort of minimized reproduction:

enum Hand with ToString, Eq {
    case FiveOfAKind(String)
    case FourOfAKind(String)
    case FullHouse(String)
    case ThreeOfAKind(String)
    case TwoPair(String)
    case OnePair(String)
    case HighCard(String)
}

instance Order[Hand] {
    pub def compare(x: Hand, y: Hand): Comparison =
        match (x, y) {
            case (Hand.FiveOfAKind(_), Hand.FiveOfAKind(_)) => Comparison.GreaterThan
            case _ => Comparison.LessThan
        }
}

def main(): Unit \ IO =
    let testHands = Hand.FiveOfAKind("JJJJJ") :: Hand.HighCard("29QA4") :: Hand.TwoPair("6A9A9") :: Nil;
    testHands |> List.sort |> ToString.toString |> println

It crashes with the following error:

java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3                
    at Array.Def$swap$exclamation$405956.applyFrame(Unknown Source)
    at Array.Def$swap$exclamation$405956.invoke(Unknown Source)
    at Array.Def$sortWithin$exclamation$405879.applyFrame(Unknown Source)
    at Array.Def$sortWithin$exclamation$405879.invoke(Unknown Source)
    at List.Def$sort$405690.applyFrame(Unknown Source)
    at List.Def$sort$405690.invoke(Unknown Source)
    at Def$main$.applyFrame(Unknown Source)
    at Def$main$.invoke(Unknown Source)
    at Ns.m_main$(Unknown Source)
    at Main.main(Main)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
    at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.base/java.lang.reflect.Method.invoke(Method.java:568)
    at ca.uwaterloo.flix.language.phase.jvm.Loader$.mainFunction$1(Loader.scala:73)
    at ca.uwaterloo.flix.language.phase.jvm.Loader$.$anonfun$load$10(Loader.scala:82)
    at ca.uwaterloo.flix.language.phase.jvm.Loader$.$anonfun$load$10$adapted(Loader.scala:82)
    at ca.uwaterloo.flix.runtime.shell.Shell.run(Shell.scala:377)
    at ca.uwaterloo.flix.runtime.shell.Shell.execEval(Shell.scala:305)
    at ca.uwaterloo.flix.runtime.shell.Shell.execReloadAndEval(Shell.scala:320)
    at ca.uwaterloo.flix.runtime.shell.Shell.execute(Shell.scala:162)
    at ca.uwaterloo.flix.runtime.shell.Shell.loop(Shell.scala:113)
    at ca.uwaterloo.flix.Main$.main(Main.scala:240)
    at ca.uwaterloo.flix.Main.main(Main.scala)

[JonathanStarup]

I think Array.quicksortPartition has the bug. in the case that anything is less than the pivot it adds one, but that is a bug if pivot is less than itself

[magnus-madsen]

The definition of Order is not reflexive. Can you try with an updated version of Order?

[magnus-madsen]

This seems to work:

enum Hand with ToString, Eq {
    case FiveOfAKind(String)
    case FourOfAKind(String)
    case FullHouse(String)
    case ThreeOfAKind(String)
    case TwoPair(String)
    case OnePair(String)
    case HighCard(String)
}

instance Order[Hand] {
    pub def compare(x: Hand, y: Hand): Comparison =
        def toN(h) = match h {
            case Hand.FiveOfAKind(_elem) => 1
            case Hand.FourOfAKind(_elem) => 2
            case Hand.FullHouse(_elem) => 3
            case Hand.ThreeOfAKind(_elem) => 4
            case Hand.TwoPair(_elem) => 5
            case Hand.OnePair(_elem) => 6
            case Hand.HighCard(_elem) => 7
        };
        toN(x) <=> toN(y)
}

def main(): Unit \ IO =
    let testHands = Hand.FiveOfAKind("JJJJJ") :: Hand.HighCard("29QA4") :: Hand.TwoPair("6A9A9") :: Nil;
    testHands |> List.sort |> ToString.toString |> println

[JonathanStarup]

I think the comment is that even if order is wrong, you shouldn't crash the program.

[Andriamanitra]

It works once the definition is reflexive, but the point is that it shouldn't crash at runtime even when it isn't. A compile time crash / error would be fine I guess but I don't think compilers can prove whether the definition is reflexive or not.