Incorrect diverging implicit failure using type projects in scala 2.13

[eejbyfeldt]

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

[SethTisue]

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

[SethTisue]

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.

[SethTisue]

@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.

[SethTisue]

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]]]
}

[SethTisue]

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.

[eejbyfeldt]

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]]]
}

[eejbyfeldt]

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?

[lrytz]

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.

[eejbyfeldt]

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?

[jdrphillips]

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)