[implicit search] Comparison method violates its general contract! #12479
Comments
|
Even if you can't minimize it, could you give us a link to a git branch where the problem is reproducible? |
|
Unfortunately I can't, it is hard to track. For example, I was hoping it can be investigated by looking at comparator of whatever is being sorted. |
|
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 Removing the 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) |
|
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 |
|
I'm not getting anything else, maybe there's a flag I can turn on? |
|
It's literally a println so no, but I don't know what bloop does with it (check its logs?) |
|
well now we've angered the reproducibility gods and it's not failing any more. Some global state in bloop? |
|
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:
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 wrongProperty 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 FunctionInstanceI can't really think of a way to salvage this besides rolling our own sorting function that has less strict requirements. WDYT @odersky ? |
|
One way to fix this might be to tweak |
|
Another way to see this is that |
|
(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 |
|
I believe we might be able to tweak
For (3), the function could be
I believe that would be a decent approximation of The reason to do simple name before fully qualified is that simple name should discriminate faster. |
|
Sounds good to me, I can give it a shot tomorrow if you're not planning to already. |
|
No, please go ahead! |
Before this commit, we sorted implicits using `prefer` which relied on `compareOwner`, but compareOwner does not induce a total ordering: just because `compareOwner(x, y) == 0` does not mean that `compareOwner(x, z)` and `compareOwner(y, z)` have the same sign, this violates the contract of `java.util.Comparator#compare` and lead to an IllegalArgumentException sometimes being thrown (although I wasn't able to reproduce that, see scala#12479) This commit fixes by this by replacing the usage of `compareOwner` by a new `compareBaseClassesLength` which does induce a total ordering while still hopefully approximating `compareOwner` well enough for our purposes. We also replace `prefer` which returned a Boolean by `compareEligibles` which is directly usable as an Ordering we can pass to `sorted`, this is more efficient than using `sortBy(prefer)` because the latter might end up calling `prefer` twice for a single comparison. Fixes scala#12479 (I hope).
Before this commit, we sorted implicits using `prefer` which relied on `compareOwner`, but compareOwner does not induce a total ordering: just because `compareOwner(x, y) == 0` does not mean that `compareOwner(x, z)` and `compareOwner(y, z)` have the same sign, this violates the contract of `java.util.Comparator#compare` and lead to an IllegalArgumentException sometimes being thrown (although I wasn't able to reproduce that, see scala#12479) This commit fixes by this by replacing the usage of `compareOwner` by a new `compareBaseClassesLength` which does induce a total ordering while still hopefully approximating `compareOwner` well enough for our purposes. We also replace `prefer` which returned a Boolean by `compareEligibles` which is directly usable as an Ordering we can pass to `sorted`, this is more efficient than using `sortWith(prefer)` because the latter might end up calling `prefer` twice for a single comparison. Fixes scala#12479 (I hope).
Before this commit, we sorted implicits using `prefer` which relied on `compareOwner`, but compareOwner does not induce a total ordering: just because `compareOwner(x, y) == 0` does not mean that `compareOwner(x, z)` and `compareOwner(y, z)` have the same sign, this violates the contract of `java.util.Comparator#compare` and lead to an IllegalArgumentException sometimes being thrown (although I wasn't able to reproduce that, see scala#12479) This commit fixes by this by replacing the usage of `compareOwner` by a new `compareBaseClassesLength` which does induce a total ordering while still hopefully approximating `compareOwner` well enough for our purposes. We also replace `prefer` which returned a Boolean by `compareEligibles` which is directly usable as an Ordering we can pass to `sorted`, this is more efficient than using `sortWith(prefer)` because the latter might end up calling `prefer` twice for a single comparison. Fixes scala#12479 (I hope).
Compiler version
3.0.0-RC3
Minimized code
No minimized code, sorry.
Output (click arrow to expand)
The text was updated successfully, but these errors were encountered: