IllegalArgumentException: Comparison method violates its general contract

Question

I haven't faced this issue ever. I just wanted to understand the cause of this error. As per this answer on SO, the following scenario is a violation:

    A > B
    A == C
    B == C

So I tried writing a simple code to create this scenario and see if it throws this error. Here's what I wrote.

    import java.util.*;

    public class Main {
        public static void main(String[] args) {
          List<A> a = new ArrayList<>();
        
            a.add(new A(0,1)); // this is A
            a.add(new A(0,0)); // this is B
            a.add(new A(0,null)); // And this is C
        
        
            Collections.sort(a, new Comparator<A>(){
                public int compare(A a, A b){
                    if(a.i.equals(b.i) && a.j != null && b.j != null){
                        return a.j.compareTo(b.j);
                    }else{
                        return a.i.compareTo(b.i);
                    }
                }
            });
        
            System.out.println(a);
      }
    }

    class A{
        Integer i;
        Integer j;
        A(Integer i, Integer j){
            this.i = i;
            this.j = j;
        }
    
        public String toString(){
            return "["+i+","+j+"]";
        }
    }

But this doesn't throw any violation error and runs successfully. Any idea why?

Answer 1

Collections.sort is not required to throw this exception. It may or may not. Essentially, if you attempt to do sorting operations (such as invoking Collections.sort, or passing a broken comparator to the constructor of TreeSet, then adding some elements) with a broken comparator, undefined behaviour is 'allowed' by the JVM.

The exception is simply a kindness, and not one you can reliably get. The spec doesn't explain in which specific circumstances you would.

This should be somewhat obvious: If you have a list with 2 elements in it, and you ask to sort it, it's only going to call your comparator just the one time, and that is by definition insufficient to figure out that your comparator is broken. Java certainly isn't going to do some sort of code analysis prior to accepting the comparator (halting problem and such kinda make that impossible in any case).

But I really wanna see it!

No problem. Just toss a few more in there! Wrap

for (int i = 0; i < 100; i++) {
 // your 3 add statements here
}

around your add statements and, voila, a funny exception. Funny, in that it is itself broken - the message ends in an exclamation point which violates the exception messaging style guide. If you feel endeavourous, you should file a bug report over at OpenJDK about it:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
    at java.base/java.util.TimSort.sort(TimSort.java:245)
    at java.base/java.util.Arrays.sort(Arrays.java:1307)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1721)
    at java.base/java.util.Collections.sort(Collections.java:179)
    at Main.main(Main.java:13)