A diverging implicit expansion in Scala, involving chained implicits

Question

(note: this problem is fixed as of Scala 2.13, see here: https://github.com/scala/scala/pull/6050)

I am working on a system of Scala types that involves chained implicits. This system behaves as I expected in many cases, but fails via diverging expansion in others. So far I haven't come up with a good explanation for the divergence, and I'm hoping the community can explain it for me!

Here is a simplified system of types that reproduces the problem:

object repro {
  import scala.reflect.runtime.universe._

  trait +[L, R]

  case class Atomic[V](val name: String)
  object Atomic {
    def apply[V](implicit vtt: TypeTag[V]): Atomic[V] = Atomic[V](vtt.tpe.typeSymbol.name.toString)
  }

  case class Assign[V, X](val name: String)
  object Assign {
    def apply[V, X](implicit vtt: TypeTag[V]): Assign[V, X] = Assign[V, X](vtt.tpe.typeSymbol.name.toString)
  }

  trait AsString[X] {
    def str: String
  }
  object AsString {
    implicit def atomic[V](implicit a: Atomic[V]): AsString[V] =
      new AsString[V] { val str = a.name }
    implicit def assign[V, X](implicit a: Assign[V, X], asx: AsString[X]): AsString[V] =
      new AsString[V] { val str = asx.str }
    implicit def plus[L, R](implicit asl: AsString[L], asr: AsString[R]): AsString[+[L, R]] =
      new AsString[+[L, R]] { val str = s"(${asl.str}) + (${asr.str})" }
  }

  trait X
  implicit val declareX = Atomic[X]
  trait Y
  implicit val declareY = Atomic[Y]
  trait Z
  implicit val declareZ = Atomic[Z]

  trait Q
  implicit val declareQ = Assign[Q, (X + Y) + Z]
  trait R
  implicit val declareR = Assign[R, Q + Z]
}

Following is a demo of the behavior, with some working cases and then the diverging failure:

scala> :load /home/eje/divergence-repro.scala
Loading /home/eje/divergence-repro.scala...
defined module repro

scala> import repro._
import repro._

scala> implicitly[AsString[X]].str
res0: String = X

scala> implicitly[AsString[X + Y]].str
res1: String = (X) + (Y)

scala> implicitly[AsString[Q]].str
res2: String = ((X) + (Y)) + (Z)

scala> implicitly[AsString[R]].str
<console>:12: error: diverging implicit expansion for type repro.AsString[repro.R]
starting with method assign in object AsString
              implicitly[AsString[R]].str

Answer 1

You'll be surprised to know you haven't done anything wrong! Well on a logical level at least. What you've encountered as error here is a known behavior of the Scala compiler when resolving implicits for recursive data structures. a good explanation of this behavior is given in the book The Type Astronaut's Guide to Shapeless:

Implicit resolution is a search process. The compiler uses heuristics to determine whether it is “converging” on a solution. If the heuristics don’t yield favorable results for a particular branch of search, the compiler assumes the branch is not converging and moves onto another.

One heuristic is specifically designed to avoid infinite loops. If the compiler sees the same target type twice in a particular branch of search, it gives up and moves on. We can see this happening if we look at the expansion for CsvEncoder[Tree[Int]] The implicit resolution process goes through the following types:

CsvEncoder[Tree[Int]] // 1
CsvEncoder[Branch[Int] :+: Leaf[Int] :+: CNil] // 2
CsvEncoder[Branch[Int]] // 3
CsvEncoder[Tree[Int] :: Tree[Int] :: HNil] // 4
CsvEncoder[Tree[Int]] // 5 uh oh

We see Tree[A] twice in lines 1 and 5, so the compiler moves onto another branch of search. The eventual consequence is that it fails to find a suitable implicit.

In your case if the compiler had kept going and not given up on so early it would have eventually reached the solution! But remember not every diverging implicit error is false compiler alarm. some are in fact diverging / infinitely expanding.

I know of two solutions to this issue:

1. macro based lazy evaluation of recursive types:

The shapeless library has a Lazy type that differs evaluation of it's Hlists head to runtime and as a result prevents this diverging implicit error. I find explaining or providing examples of it is beyond the OP topic. but you should check it.

2. create implicit checkpoints so that the implicit for the recursive type is available to the compiler beforehand:

implicitly[AsString[X]].str

implicitly[AsString[X + Y]].str

val asQ = implicitly[AsString[Q]]

asQ.str

{
  implicit val asQImplicitCheckpoint: AsString[Q] = asQ

  implicitly[AsString[R]].str
}

It's not a shame if you are a fan of neither of these solutions. the shapeless's Lazy solution while tried and true is still a third party library dependency and also with the removal of macros in scala 3.0 I'm not certain what'll become of all these macro based technics.