java.lang.IllegalArgumentException: Comparison method violates its general contract!

自作の Comparator でリストをソートしたら初めて見るエラーメッセージが。

java.lang.IllegalArgumentException: Comparison method violates its general contract!

再現コード

Java 1.8.0_92 です。

なかなか再現できずいろいろ試した結果、以下のようになりました。

public class Foo {
    private String name;
    public Foo(String name) {
        this.name = name;
    }
    public String getName() {
        return name;
    }
}
public class Sample {
    void execute(List<Foo> list) {
        list.stream()
                .map(o -> map(o.getName()))
                .sorted((o1, o2) -> compare(o1.getName(), o2.getName()))
                .count();
    }
    static Foo map(String name) {
        return new Foo(name.startsWith("a") ? name.toUpperCase() : null);
    }
    static int compare(String str, String other) {
        if (str == null) {
            return 1;
        }
        if (other == null) {
            return -1;
        }
        return str.compareTo(other);
    }
}
// リストの要素は32個以上
List<Foo> list = Arrays.asList(
        new Foo("xyz"), new Foo("abc"), new Foo("xyz"), ... , new Foo("xyz"), new Foo("abc"), new Foo("xyz"));

new Sample().execute(list);

解決 (とりあえず)

compare メソッドを以下のように変更するとエラーが発生しなくなります。

static int compare(String str, String other) {
    // ここから
    if (str == null && other == null) {
        return 0;
    }
    // ここまでを追加
    if (str == null) {
        return 1;
    }
    if (other == null) {
        return -1;
    }
    return str.compareTo(other);
}

TimSort

詳しくは理解してなくて申し訳ないですが、sort メソッドでは TimSort というアルゴリズムが使われており、Comparator のロジックに矛盾がある場合に今回のエラーが発生するようです。

上の再現コードでは、compare に渡す要素が両方 null になるケースの考慮が抜けており、これらの比較結果を返すロジックを含める必要があります。

その他

尚、リストの要素が32個未満の場合、別のアルゴリズム (mini-TimSort) に切り替わるようで、この場合には同様のエラーは発生しませんでした。