[implicit search] Comparison method violates its general contract!

[scf37]

Compiler version

3.0.0-RC3

Minimized code

No minimized code, sorry.

Output (click arrow to expand)

scalac: Error: Comparison method violates its general contract!
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:1438)
	at scala.collection.SeqOps.sorted(Seq.scala:700)
	at scala.collection.SeqOps.sorted$(Seq.scala:692)
	at scala.collection.immutable.List.scala$collection$immutable$StrictOptimizedSeqOps$$super$sorted(List.scala:79)
	at scala.collection.immutable.StrictOptimizedSeqOps.sorted(StrictOptimizedSeqOps.scala:78)
	at scala.collection.immutable.StrictOptimizedSeqOps.sorted$(StrictOptimizedSeqOps.scala:78)
	at scala.collection.immutable.List.sorted(List.scala:79)
	at scala.collection.SeqOps.sortWith(Seq.scala:727)
	at scala.collection.SeqOps.sortWith$(Seq.scala:727)
	at scala.collection.AbstractSeq.sortWith(Seq.scala:1149)
	at dotty.tools.dotc.typer.Implicits$ImplicitSearch.sort$1(Implicits.scala:1283)
	at dotty.tools.dotc.typer.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:1298)
	at dotty.tools.dotc.typer.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:1305)
	at dotty.tools.dotc.typer.Implicits$ImplicitSearch.bestImplicit(Implicits.scala:1338)
	at dotty.tools.dotc.typer.Implicits.inferImplicit(Implicits.scala:974)
	at dotty.tools.dotc.typer.Implicits.inferImplicit$(Implicits.scala:769)
	at dotty.tools.dotc.typer.Typer.inferImplicit(Typer.scala:103)
	at dotty.tools.dotc.typer.Implicits.inferImplicitArg(Implicits.scala:843)
	at dotty.tools.dotc.typer.Implicits.inferImplicitArg$(Implicits.scala:769)
	at dotty.tools.dotc.typer.Typer.inferImplicitArg(Typer.scala:103)
	at dotty.tools.dotc.typer.Typer.implicitArgs$1(Typer.scala:3287)
	at dotty.tools.dotc.typer.Typer.addImplicitArgs$3(Typer.scala:3323)
	at dotty.tools.dotc.typer.Typer.adaptNoArgsImplicitMethod$2(Typer.scala:3402)
	at dotty.tools.dotc.typer.Typer.adaptNoArgs$1(Typer.scala:3580)
	at dotty.tools.dotc.typer.Typer.adapt1(Typer.scala:3793)
	at dotty.tools.dotc.typer.Typer.adapt(Typer.scala:3134)
	at dotty.tools.dotc.typer.Typer.readapt$1(Typer.scala:3145)
	at dotty.tools.dotc.typer.Typer.adapt1(Typer.scala:3780)
	at dotty.tools.dotc.typer.Typer.adapt(Typer.scala:3134)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2800)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2804)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2920)
	at dotty.tools.dotc.typer.Typer.$anonfun$35(Typer.scala:2146)
	at dotty.tools.dotc.typer.PrepareInlineable$.dropInlineIfError(PrepareInlineable.scala:225)
	at dotty.tools.dotc.typer.Typer.typedDefDef(Typer.scala:2146)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2650)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2734)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2800)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2804)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2826)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2876)
	at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:2332)
	at dotty.tools.dotc.typer.Typer.typedTypeOrClassDef$2(Typer.scala:2661)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2665)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2734)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2800)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2804)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2826)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2876)
	at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:2455)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2706)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2735)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2800)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2804)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2920)
	at dotty.tools.dotc.typer.FrontEnd.liftedTree1$1(FrontEnd.scala:79)
	at dotty.tools.dotc.typer.FrontEnd.typeCheck$$anonfun$1(FrontEnd.scala:84)
	at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:43)
	at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:85)
	at dotty.tools.dotc.typer.FrontEnd.runOn$$anonfun$3(FrontEnd.scala:120)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.immutable.List.foreach(List.scala:333)
	at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:120)
	at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:205)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
	at dotty.tools.dotc.Run.runPhases$5(Run.scala:215)
	at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:223)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.scala:18)
	at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:67)
	at dotty.tools.dotc.Run.compileUnits(Run.scala:230)
	at dotty.tools.dotc.Run.compileSources(Run.scala:166)
	at dotty.tools.dotc.Run.compile(Run.scala:150)
	at dotty.tools.dotc.Driver.doCompile(Driver.scala:39)
	at dotty.tools.dotc.Driver.process(Driver.scala:199)
	at dotty.tools.dotc.Main.process(Main.scala)

[smarter]

Even if you can't minimize it, could you give us a link to a git branch where the problem is reproducible?

[scf37]

Unfortunately I can't, it is hard to track. For example, sbt compile generally works fine but IDEA build does not, full rebuild does no t fix the problem.

I was hoping it can be investigated by looking at comparator of whatever is being sorted.

[kubukoz]

I have a smaller input that reproduces this on 3.0.0 with Cats.

import cats.implicits._

trait Interpreter[F]

object Interpreter:
  def apply[F](using Interpreter[F]): Interpreter[F] = summon

Requires "org.typelevel" %% "cats-core" % "2.6.1", and I can only see the error in bloop (after ~10 seconds of compiling just this file):

[E] Unexpected error when compiling root: 'Comparison method violates its general contract!'
[E] Failed to compile 'root'

Removing the summon or the import fixes the problem. I have no idea what's so specific about that import, cats.syntax.all._ + cats.instances.all._ combined work just fine.

To save anyone a couple seconds, here's the object we're importing from: https://github.com/typelevel/cats/blob/v2.6.1/core/src/main/scala/cats/implicits.scala

Bloop: 1.4.8

generated with sbt 1.5.2

Update: this seems to happen if the bloop server is running on a 11.x JVM (tested with GraalVM Community Java 11.0.10, didn't happen on Azul Java 8)

[smarter]

What's the full compiler output? Besides the exception there should be some a line starting with "transitivity violated" with more information: https://github.com/lampepfl/dotty/blob/b9773d62497f2da1410581a094d661b6f58547af/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L1284-L1295

[kubukoz]

I'm not getting anything else, maybe there's a flag I can turn on?

[smarter]

It's literally a println so no, but I don't know what bloop does with it (check its logs?)

[kubukoz]

well now we've angered the reproducibility gods and it's not failing any more. Some global state in bloop?

[smarter]

OK, I think the reason no one saw a println is likely that none was actually printed. When we catch IllegalArgumentException we check that our comparison function is transitive, but this isn't the only property that the underlying Java sort requires: the documentation of Comparator#compare says:

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

Which our comparison function on implicits does not respect: just because we don't prefer an implicit x to another implicit y, doesn't mean that we can't find an implicit z such that x will be preferred to it but y won't. In fact if I explicitly check for this in your example code I get plenty of counter-examples:

diff --git compiler/src/dotty/tools/dotc/typer/Implicits.scala compiler/src/dotty/tools/dotc/typer/Implicits.scala
index 2b01a724596..28c830aaed3 100644
--- compiler/src/dotty/tools/dotc/typer/Implicits.scala
+++ compiler/src/dotty/tools/dotc/typer/Implicits.scala
@@ -1280,6 +1280,17 @@ trait Implicits:
           if (prefer(e2, e1)) e2 :: e1 :: Nil
           else eligible
         case _ =>
+          val ord = Ordering.fromLessThan(prefer)
+          for
+            e1 <- eligible
+            e2 <- eligible
+            if ord.compare(e1, e2) == 0
+            e3 <- eligible
+            if Integer.signum(ord.compare(e1, e3)) != Integer.signum(ord.compare(e2, e3))
+          do
+            val es = List(e1, e2, e3)
+            println(i"Property violated for $es%, %\n ${es.map(_.implicitRef.underlyingRef.symbol.showLocated)}%, %")
+
           try eligible.sortWith(prefer)
           catch case ex: IllegalArgumentException =>
             // diagnostic to see what went wrong

Property violated for Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class <root>)),object cats),object implicits),method catsKernelBandForFunction0),1,3), Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class <root>)),object cats),object implicits),method catsKernelStdBoundedSemilatticeForTuple1),1,3), Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class <root>)),object cats),object implicits),method catsKernelOrderForFunction0),1,3)
 method catsKernelBandForFunction0 in trait FunctionInstances2,
method catsKernelStdBoundedSemilatticeForTuple1 in trait TupleInstances,
method catsKernelOrderForFunction0 in trait FunctionInstance

I can't really think of a way to salvage this besides rolling our own sorting function that has less strict requirements. WDYT @odersky ?

[smarter]

One way to fix this might be to tweak prefer to ensure prefer(e1, e2) == prefer(e2, e1) == true implies e1 =:= e2, this could perhaps be done by using the full name of the implicit reference as a tie-breaker (but even that isn't enough since implicits might be local, so you'd have to take into account the names of their owners too).

[smarter]

Another way to see this is that prefer induces a partial and not a total ordering on implicit references. A topological sort can be used to sort elements with a partial ordering, and in fact we already have one in the compiler courtesy of @sjrd : https://github.com/lampepfl/dotty/blob/83e17f110bfaa2fe876bacc90eca208f23930f98/compiler/src/dotty/tools/backend/sjs/JSExportsGen.scala#L977-L994

[smarter]

(that topological sort being O(n^2) isn't great for our usecase though since in the cats testcase above we end up sorting a list of 498 elements, if there isn't an algorithm with better time complexity then we're probably better off tweaking prefer into a total ordering as mentioned above instead).

[odersky]

I believe we might be able to tweak prefer as follows

1. level (as before)
2. arity (as before)
3. length of baseclass sequence of owner (in reverse, larger comes first)
4. simple name
5. fully qualified name

For (3), the function could be

• if symbol is in a module, max(sym.owner.baseClasses.length, sym.owner.companionClass.baseClasses.length)
• otherwise just sym.owner.baseClasses.length

I believe that would be a decent approximation of compareOwner. To avoid inefficient length computations on lists, we could export the length directly from ClassDenotation. It can be computed more efficiently as cls.baseData.._2.classIds.length (but baseData is private, so we can't do that at the call-site).

The reason to do simple name before fully qualified is that simple name should discriminate faster.