Diverging implicit expansion

Question
1

Can you tell me the literal meaning of “diverging implicit expansion”? I am familiar with implicits and that they resolve. Is expansion the same as finding an implicit? How does an implicit or implicit expansion diverge?

The problem I am working on is ordering a case class, But, I haven’t read enough about Ordered and Ordering to form a question about that yet.

2

Implicit expansion is the process of finding the series of calls to implicits that is necessary for constructing a value of a certain type.

Take for instance this code:

case class A(i: Int) {
  def toB = B(i)
}
object A {
  implicit def orderingA(implicit ord: Ordering[Int]): Ordering[A] = Ordering.by(a => a.i)
}

case class B(i: Int) {
  def toA = A(i)
}
object B {
  implicit def orderingB(implicit ord: Ordering[A]): Ordering[B] = Ordering.by(_.toA)
}

Now if you ask the compiler for an implicit Ordering[B], it will find B.orderingB. But that def requires an implicit Ordering[A], so the compiler will look for one and find A.orderingA. That one has a dependency on Ordering[Int] so again the compiler goes looking for one and finds Ordering.Int, which has no dependencies. Now the compiler knows it can provide a value of type Ordering[B] by constructing the call B.orderingB(A.orderingA(Ordering.Int)).

A diverging implicit expansion is what happens when the compiler suspects that this implicit search process is going to get stuck in an infinite cycle (its suspicion is not always correct).

For an example, let’s change the previous code to:

case class A(i: Int) {
  def toB = B(i)
}
object A {
  implicit def orderingA(implicit ord: Ordering[B]): Ordering[A] = Ordering.by(_.toB)
}

case class B(i: Int) {
  def toA = A(i)
}
object B {
  implicit def orderingB(implicit ord: Ordering[A]): Ordering[B] = Ordering.by(_.toA)
}

Now when asking the compiler for an implicit Ordering[B] implicit expansion will go more or less like this:

looking for Ordering[B]
found B.orderingB
looking for Ordering[A]
found A.orderingA
looking for Ordering[B] --> diverging implicit expansion

The compiler detects that it’s looking for an Ordering[B] for the second time in the same expansion and throws an error.
There are some more rules to this, like that the complexity of the type parameters may only decrease.

3

Thank you. That helps me understand the error message. I don’t see any divergence happening in that scenario though. Am I missing where something is diverging

4

The scala language spec gives an example that shows divergence at the end of the section about implicit parameters: 7.2.

As implicits are being expanded a stack of open implicit types is maintained. So, like in the explanation above, at the end there would be a fork of types ot expand:

Ordering[B]
Ordering[B]

which means that it would be diverging if it were to continue into infinite recursion.

“Possible infiniite recursion” might make more sense to people as an error message, than diverging implicit expansion. But, it does make sense.