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

[braunse]

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 true if 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

[braunse]

When I opened this issue, I had not found #4287, which seems to be the same problem.

[lihaoyi]

Should be fixed by #4287. I didn't add a test case since the repro we have is kind of heavy, but at least manual testing it seems to fix the issue.

[braunse]

Can confirm it now builds both the repro I shared and the unpublished original repo which surfaced the bug for me. Thank you for the super-quick fix @lihaoyi!