bug
bug copied to clipboard
Incorrect diverging implicit failure using type projects in scala 2.13
Reproduction steps
Scala version: 2.13.8 (But I think all scala 2.13 releases have this issue)
trait Base {
type T
def value: T
}
object Base {
implicit def ordering[F <: Base](implicit o: Ordering[F#T]): Ordering[F] = new Ordering[F] {
def compare(x: F, y: F): Int = o.compare(x.value, y.value)
}
}
final case class Derived(value: String) extends Base {
type T = String
}
object Test {
def hasOrdering[X](implicit o: Ordering[X] = null): Boolean = { o != null}
def main(args: Array[String]): Unit = {
println(hasOrdering[List[Derived]])
}
}
Problem
The code above compiles fine on scala 2.12.16 but with scala 2.13.8 it fails with
diverging implicit expansion for type Ordering[List[Derived]#T#T]
starting with method comparatorToOrdering in trait LowPriorityOrderingImplicits
println(hasOrdering[List[Derived]])
The expected behavior is that the code should compile and if executed it should output false
.
I bisected the scala repo using the snippet above and it points to that the bug being introduced in this commit: https://github.com/scala/scala/commit/8272151ac87628e2f1165547ff4b794f3226bbbc
minimizes, at least partway, to:
trait Base { type T }
class Derived extends Base { type T = String }
object Base {
implicit def ordering[F <: Base](implicit o: Ordering[F#T]): Ordering[F] = ???
}
object Test {
def hasOrdering[X](implicit o: Ordering[X] = null): Boolean = { o != null}
println(hasOrdering[List[Derived]])
}
one puzzling thing is here is that this change makes the problem go away:
- println(hasOrdering[List[Derived]])
+ def foo = hasOrdering[List[Derived]]
this is the sort of thing one discovers when minimizing.
of course it's not println
in particular, it's the expected type being Any
. the error also occurs with hasOrdering[List[Derived]]: Any
The same thing happens if we use a type parameter instead of a type member:
trait Base[T]
object Test {
implicit def ordering[T, F <: Base[T]](implicit o: Ordering[T]): Ordering[F] = ???
def hasOrdering[X](implicit o: Ordering[X] = null) = o != null
hasOrdering[List[Base[String]]]: Any
}
and eliminating the type projection (F#T
) means we can try it in Scala 3, where it compiles.
@lrytz any idea what the connection with https://github.com/scala/scala/pull/6092 is? There is something really peculiar going on here that I don't understand.
It gets weirder!
If we simplify the code even further, then it fails in both 2.12.16 and 2.13.8, yet succeeds in 3:
trait Base[T]
object Test {
implicit def ordering[T, F <: Base[T]](implicit o: Ordering[T]): Ordering[F] = ???
implicitly[Ordering[Base[String]]]
}
One way in which this isn't minimal yet is that it involves a standard library trait, Ordering
. A minimal version of that ought to be part of the minimization.
Seems like Ordering
can just be replace with some other type class. This still fails on both 2.12.16 and 2.13.8
trait A[T]
trait B[T]
object Test {
implicit def provideA[T, F <: B[T]](implicit o: A[T]): A[F] = ???
implicitly[A[B[String]]]
}
If we simplify the code even further, then it fails in both 2.12.16 and 2.13.8
How do we no know that we are still triggering the same issue and not just found another similar bug?
In the last example, the implicit instance is missing; for the version with Ordering
, there's Ordering.String: Ordering[String]
, but in the last one there's no implicit A[T]
.
Adding an instance makes it compile on 2.12 / 2.13.
trait A[T]
object A {
implicit object as extends A[String]
}
trait B[T]
object Test {
implicit def provideA[T, F <: B[T]](implicit o: A[T]): A[F] = ???
implicitly[A[B[String]]]
}
So comparing what the compiler does on this, vs the version with Ordering
seems to be a good way to find out more.
Yeah, that is true that it differnt from the Ordering
version in that way. But the compiler error it gives
diverging implicit expansion for type A[B[String]]
starting with method ordering in object Test
implicitly[A[B[String]]]
looks incorrect to me. The correct failure would have been implicit not found?
There's multiple things going on here.
@SethTisue if you replace Ordering
with TypeClass
as defined here:
trait TypeClass[A]
object TypeClass {
implicit val int: TypeClass[Int] = ???
implicit val string: TypeClass[String] = ???
}
in your example, it works as expected. The issue is a bug(?) with Ordering
coupled with your code. The type parameter A
is inferred to something exotic - Null
or _
or something - and then Ordering
's very generous self-satisfying implicit comparatorToOrdering
takes over and diverges. Not sure on precisely why but that is what is happening. I don't know precisely what A
is inferred to be but it's something exotic.
@eejbyfeldt's issue is genuinely different. Replace Ordering
with TypeClass
in their example and they get the same error:
diverging implicit expansion for type TypeClass[List[Derived]#T#T]
Note the double #T#T
here. Once scala 2.13 considers ordering
as a candidate (as it should, since it's on the search path) the compiler apparently throws a fit and starts looking for any type member T
recursively, causing divergence.
If you run @eejbyfeldt's code with TypeClass
instead of Ordering
in 2.12.x, it does indeed do the right thing.
Why these two bugs exist or what causes them is beyond me, just wanted to clear up the two different issues at play (plus I'm interested in answers for both)