排序异常: Comparison method violates its general contract

[Bpazy]

背景和异常介绍

先贴异常堆栈:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeHi(TimSort.java:899)
	at java.util.TimSort.mergeAt(TimSort.java:516)
	at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
	at java.util.TimSort.sort(TimSort.java:254)
	at java.util.Arrays.sort(Arrays.java:1512)
	at java.util.ArrayList.sort(ArrayList.java:1462)
	at com.f6car.purchase.service.impl.hwy.HwyCheckBillServiceImpl.orderByBillDate(HwyCheckBillServiceImpl.java:870)

业务背景是货无忧对账单业务，排序规则非常复杂，所以代码中实现了一套自定义排序规则（实现 Comparator 接口），测试通过后上了生产，但是在生产却有一个对账单可以稳定的触发该异常。
那该异常产生的代码场景是什么？在 JDK7 版本以上，Comparator 要满足 自反性、传递性、对称性，不然 Arrays.sort, Collections.sort 会报 IllegalArgumentException 异常。
说明：

1. 自反性：x, y 的比较结果和 y, x 的比较结果相反；
2. 传递性：如果 x > y, y > z, 则 x > z；
3. 对称性：x = y, 则 x, z 比较结果和 y, z 比较结果相同（也叫可逆比较）。

但是实现过程已经注意了这几个点，且通过了测试，为什么生产还是有数据可以触发该问题呢？最快捷的方法就是找到不满足这三个特性的数据，拿到手里做个对比，最好还能结合代码进行 debug。

Debug 方法

我们可以看到，异常堆栈中并未包含任何不满足三个特性的数据。
所以我首先尝试了在测试环境复现问题，通过断点的形式找到问题数据。但是测试环境并未复现，同时由于数据量非常大，代码中也并未在排序前打印日志，复现陷入僵局。
接着我发现此排序本身比较单纯，和业务数据耦合的并不严重，就手动的从生产数据库中拉到对应数据，转成 json 后存储到本地，再通过单元测试反序列化获得生产相同的入参再执行。果不其然，问题复现了。

此时又有新的问题，怎么找到问题数据辅助定位代码缺陷呢？要知道参与排序的有 300 条数据，按照合并排序的复杂度 n*logn来看一个个断点最多要 300*log300 次才能找到数据，不太现实。
不过幸好，生产环境的问题被 @王金龙 通过二分删除再恢复的方法，找到了 2 条数据，我就仅保留这两条数据，结果没复现。没复现？？
仔细思考了一下，才想到在 nlogn 的算法下，2 条数据仅需要排序一次，此时没有机会去触发上述的排序三个特性了，于是只能自己实现一套 $n^3$ 的算法来继续 debug:

public class Comparators {
    public static <T> void verifyTransitivity(Comparator<T> comparator, Collection<T> elements) {
        for (T first : elements) {
            for (T second : elements) {
                int result1 = comparator.compare(first, second);
                int result2 = comparator.compare(second, first);
                if (result1 != -result2) {
                     // debug场景使用：这段代码用于找到不满足特性的数据后，再次进入自定义的排序逻辑
                     result1 = comparator.compare(first, second);
                     result2 = comparator.compare(second, first);
                    throw new AssertionError("compare(" + first + ", " + second + ") == " + result1 +
                            " but swapping the parameters returns " + result2);
                }
            }
        }
        for (T first : elements) {
            for (T second : elements) {
                int firstGreaterThanSecond = comparator.compare(first, second);
                if (firstGreaterThanSecond <= 0)
                    continue;
                for (T third : elements) {
                    int secondGreaterThanThird = comparator.compare(second, third);
                    if (secondGreaterThanThird <= 0)
                        continue;
                    int firstGreaterThanThird = comparator.compare(first, third);
                    if (firstGreaterThanThird <= 0) {
                        // debug场景使用：这段代码用于找到不满足特性的数据后，再次进入自定义的排序逻辑
                        result1 = comparator.compare(first, second);
                        result2 = comparator.compare(second, first);
                        throw new AssertionError("compare(" + first + ", " + second + ") > 0, " +
                                "compare(" + second + ", " + third + ") > 0, but compare(" + first + ", " + third + ") == " +
                                firstGreaterThanThird);
                    }
                }
            }
        }
    }
}

再改造业务代码:

// 原业务代码
list.sort((p1, p2) -> {
  // 自定义的排序规则
});
    
// 修改为
Comparators.sort((p1, p2) -> {
  // 自定义的排序规则
}, list);

此时再次执行单元测试，仅 2 条数据也触发了，最终发现了业务的极端场景，在极端的排序算法中才会触发的诡异异常，是如此的弱智:

总结反思

1. 尽量不要自定义排序规则，当必须时，务必满足 自反性、传递性、对称性；
2. 自定义的排序规则必须有单元测试，且单元测试中的排序算法必须走 $n^3$ 时间复杂度；
3. 待调研：如何动态的将生产环境的 合并排序算法改为 $n^3$ 以便快速定位问题？可以利用 javaagent 吗？