java.lang.IllegalArgumentException: Comparison method violates its general contract! #4329
Description
I have been trying to factor out some common code to define cross-platform builds in a maximally concise way. In at least one configuration involving rather involved trait inheritance to define Mill modules, I get the following exception:
$ mill resolve __
[mill-build/build.mill-64/68] compile
[mill-build/build.mill-64] [info] compiling 1 Scala source to /.../repro/out/mill-build/mill-build/compile.dest/classes ...
[mill-build/build.mill-64] [info] done compiling
[build.mill-64/68] compile
[build.mill-64] [info] compiling 4 Scala sources to /.../repro/out/mill-build/compile.dest/classes ...
[build.mill-64] [info] done compiling
[1/1] resolve
[1/1] ============================== resolve __ ============================== 8s
1 tasks failed
resolve java.lang.IllegalArgumentException: Comparison method violates its general contract!
java.base/java.util.TimSort.mergeHi(TimSort.java:903)
java.base/java.util.TimSort.mergeAt(TimSort.java:520)
java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
java.base/java.util.TimSort.sort(TimSort.java:254)
java.base/java.util.Arrays.sort(Arrays.java:1308)
scala.util.Sorting$.stableSort(Sorting.scala:240)
scala.collection.mutable.ArraySeq.sortInPlace(ArraySeq.scala:92)
scala.collection.mutable.ArraySeq.sortInPlace(ArraySeq.scala:35)
scala.collection.mutable.IndexedSeqOps.sortInPlaceWith(IndexedSeq.scala:74)
scala.collection.mutable.IndexedSeqOps.sortInPlaceWith$(IndexedSeq.scala:74)
scala.collection.mutable.ArraySeq.sortInPlaceWith(ArraySeq.scala:35)
mill.define.Reflect$.reflect(Reflect.scala:60)
... (full stacktrace below) ...Full Stack Trace
java.lang.IllegalArgumentException: Comparison method violates its general contract!
java.base/java.util.TimSort.mergeHi(TimSort.java:903)
java.base/java.util.TimSort.mergeAt(TimSort.java:520)
java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
java.base/java.util.TimSort.sort(TimSort.java:254)
java.base/java.util.Arrays.sort(Arrays.java:1308)
scala.util.Sorting$.stableSort(Sorting.scala:240)
scala.collection.mutable.ArraySeq.sortInPlace(ArraySeq.scala:92)
scala.collection.mutable.ArraySeq.sortInPlace(ArraySeq.scala:35)
scala.collection.mutable.IndexedSeqOps.sortInPlaceWith(IndexedSeq.scala:74)
scala.collection.mutable.IndexedSeqOps.sortInPlaceWith$(IndexedSeq.scala:74)
scala.collection.mutable.ArraySeq.sortInPlaceWith(ArraySeq.scala:35)
mill.define.Reflect$.reflect(Reflect.scala:60)
mill.resolve.ResolveCore$.resolveDirectChildren0(ResolveCore.scala:445)
mill.resolve.ResolveCore$.$anonfun$resolveDirectChildren$6(ResolveCore.scala:398)
scala.util.Either.flatMap(Either.scala:360)
mill.resolve.ResolveCore$.resolveDirectChildren(ResolveCore.scala:394)
mill.resolve.ResolveCore$.resolveTransitiveChildren(ResolveCore.scala:299)
mill.resolve.ResolveCore$.$anonfun$resolveTransitiveChildren$3(ResolveCore.scala:319)
scala.collection.StrictOptimizedIterableOps.flatMap(StrictOptimizedIterableOps.scala:118)
scala.collection.StrictOptimizedIterableOps.flatMap$(StrictOptimizedIterableOps.scala:105)
scala.collection.immutable.ArraySeq.flatMap(ArraySeq.scala:35)
mill.resolve.ResolveCore$.resolveTransitiveChildren(ResolveCore.scala:311)
mill.resolve.ResolveCore$.$anonfun$resolveTransitiveChildren$3(ResolveCore.scala:319)
scala.collection.StrictOptimizedIterableOps.flatMap(StrictOptimizedIterableOps.scala:118)
scala.collection.StrictOptimizedIterableOps.flatMap$(StrictOptimizedIterableOps.scala:105)
scala.collection.immutable.ArraySeq.flatMap(ArraySeq.scala:35)
mill.resolve.ResolveCore$.resolveTransitiveChildren(ResolveCore.scala:311)
mill.resolve.ResolveCore$.$anonfun$resolveTransitiveChildren$3(ResolveCore.scala:319)
scala.collection.StrictOptimizedIterableOps.flatMap(StrictOptimizedIterableOps.scala:118)
scala.collection.StrictOptimizedIterableOps.flatMap$(StrictOptimizedIterableOps.scala:105)
scala.collection.immutable.ArraySeq.flatMap(ArraySeq.scala:35)
mill.resolve.ResolveCore$.resolveTransitiveChildren(ResolveCore.scala:311)
mill.resolve.ResolveCore$.resolve(ResolveCore.scala:154)
mill.resolve.Resolve.resolveNonEmptyAndHandle(Resolve.scala:302)
mill.resolve.Resolve.resolveNonEmptyAndHandle$(Resolve.scala:285)
mill.resolve.Resolve$Segments$.resolveNonEmptyAndHandle(Resolve.scala:20)
mill.resolve.Resolve.$anonfun$resolve0$4(Resolve.scala:268)
scala.util.Either.map(Either.scala:390)
mill.resolve.Resolve.$anonfun$resolve0$3(Resolve.scala:261)
scala.collection.immutable.List.map(List.scala:247)
scala.collection.immutable.List.map(List.scala:79)
mill.resolve.Resolve.$anonfun$resolve0$2(Resolve.scala:260)
scala.collection.immutable.List.map(List.scala:247)
scala.collection.immutable.List.map(List.scala:79)
mill.resolve.Resolve.$anonfun$resolve0$1(Resolve.scala:259)
scala.util.Either.flatMap(Either.scala:360)
mill.resolve.Resolve.resolve0(Resolve.scala:258)
mill.resolve.Resolve.resolve0$(Resolve.scala:250)
mill.resolve.Resolve$Segments$.resolve0(Resolve.scala:20)
mill.resolve.Resolve.resolve(Resolve.scala:247)
mill.resolve.Resolve.resolve$(Resolve.scala:242)
mill.resolve.Resolve$Segments$.resolve(Resolve.scala:20)
mill.main.MainModule.$anonfun$resolve$1(MainModule.scala:106)
mill.define.Task$TraverseCtx.evaluate(Task.scala:219)
There is a small-ish repo with code that reproduces the problem here: https://github.com/braunse/mill-timsort-repro
The error occurs on current versions of Eclipse Temurin 17, 21, 22 and 23, but not on Temurin 8 or 11.
The error occurs with Mill 0.12.5 and a recent checkout of the Mill git repository.
I believe that the error is caused by this code snippet: Reflect.scala, lines 60-66
arr.sortInPlaceWith((m1, m2) =>
if (m1.getDeclaringClass.equals(m2.getDeclaringClass)) {
m1.getReturnType.isAssignableFrom(m2.getReturnType)
} else {
m1.getDeclaringClass.isAssignableFrom(m2.getDeclaringClass)
}
)as the given comparison function does not correctly define a total order (compare java.util.Comparator Javadoc, specifying that a total ordering is required). Specifically, referring to the definition on Wikipedia, at least the following properties are violated:
- Irreflexivity: the given comparison will return
trueif called with identical arguments, implying m1 < m2 - Asymmetry: the given comparison will return m1 < m2 and m2 < m1 if m1 and m2 are declared in the same class and have identical return types
It seems that many real-world projects do not trigger the conditions leading to the exception in this case. I do not know what exactly happens in my code that causes TimSort to throw while Mill handles much more complex builds without triggering this problem.
I have experimented with a cluelessly-patched mill build that contains an extended comparison function, and while I have zero familiarity with the mill code base, it seemed to fix this problem:
$ ./mill dist.run ../repro -i resolve __
[3025/3025] dist.run
Mill version SNAPSHOT is different than configured for this directory!
Configured version is 0.12.5 (.../repro/.mill-version)
============================== resolve __ ==============================
[mill-build/build.mill-64/68] compile
[mill-build/build.mill-64] [info] compiling 1 Scala source to /.../repro/out/mill-build/mill-build/compile.dest/classes ...
[mill-build/build.mill-64] [info] done compiling
[build.mill-64/68] compile
[build.mill-64] [info] compiling 4 Scala sources to /.../repro/out/mill-build/compile.dest/classes ...
[build.mill-64] [info] done compiling
[1/1] resolve
clean
init
inspect
mod1
[...many lines...]
mod1.tests.testFramework
path
plan
resolve
selective
selective.prepare
selective.resolve
selective.run
show
showNamed
shutdown
version
visualize
visualizePlan