Why does scalac rise a "diverging implicit expansion" error here?

Question

In the following code I try to derive typeclass instances with shapeless. However, in the case of a more complex case class (which is converted to a more complex HList), the compiler gives me a "diverging implicit expansion" even though it does not seem to resolve the same kind of implicit type twice. Maybe I am missing some other rule of the compiler?

(Fiddle: https://scalafiddle.io/sf/WEpnAXN/0)

import shapeless._

trait TC[T]

sealed trait Trait1
case class SimpleClass(a: String) extends Trait1

sealed trait Trait2
case class ComplexClass(a: String, b: String) extends Trait2

object Serialization extends App {

    //Instances for HList
    implicit val hnilInstance: TC[HNil] = ???
    implicit def hconsInstance[H, T <: HList] (implicit t: TC[T]): TC[H :: T] = ???

    //Instances for CoProduct
    implicit val cnilInstance: TC[CNil] = ???
    implicit def cconsInstance[H, T <: Coproduct] (implicit h: TC[H], t: TC[T]): TC[H :+: T] = ???

    //Instances for Generic, relying on HNil & HCons
    implicit def genericInstance[T, H] (implicit g: Generic.Aux[T, H], t: TC[H]): TC[T] = ???

    the[TC[SimpleClass :+: CNil]]  //Works
    the[TC[Trait1]]                //Works
    the[TC[ComplexClass :+: CNil]] //Works
    the[TC[Trait2]]                //Fails with diverging implicit expansion
}

When trying to resolve the[TC[Trait1]] the compiler should do something like that:

TC[Trait1]
    Generic[Trait1]
    TC[SimpleClass :+: CNil]
        TC[SimpleClass]
            Generic[SimpleClass]
            TC[String :: HNil]
        TC[CNil]

which seems to work. However, with the 2-field case class, the compiler fails to do something like this - so I wonder: why do I have to use Lazy here already to make it work?

TC[Trait2]
    Generic[Trait2]
    TC[ComplexClass :+: CNil]
        TC[ComplexClass]
            Generic[ComplexClass]
            TC[String :: String :: HNil]
        TC[CNil]

I have created some fiddle so you can execute the code there directy.

I suspect Miles's answer here is the explanation, although the case isn't exactly the same as mine in that question. — Travis Brown

Travis Brown Travis Brown · Accepted Answer · 2017-02-16T16:46:56

A couple of years ago when I was working through some issues like this I found that the easiest way to figure out what the divergence checker was doing was just to throw some printlns into the compiler and publish it locally. In 2.12 the relevant code is the dominates method here, where we can replace the last line with something like this:

overlaps(dtor1, dted1) && (dtor1 =:= dted1 || {
  val dtorC = complexity(dtor1)
  val dtedC = complexity(dted1)
  val result = dtorC > dtedC

  println(if (result) "Dominates:" else "Does not dominate:")
  println(s"$dtor (complexity: $dtorC)")
  println(s"$dted (complexity: $dtedC)")
  println("===========================")
  result
})

Then we can sbt publishLocal scalac and try to compile your code:

Dominates:
TC[shapeless.::[String,shapeless.::[String,shapeless.HNil]]] (complexity: 7)
TC[shapeless.:+:[ComplexClass,shapeless.CNil]] (complexity: 6)
===========================

The problem here is that we're looking for a TC instance for String :: String :: HNil (the lowest node in your tree), but we have an open search for ComplexClass :+: CNil (three steps up). The compiler thinks that String :: String :: HNil both overlaps and dominates ComplexClass :+: CNil, and it bails out because that looks recursive.

This sounds ridiculous, so we can do an experiment to try to convince ourselves by adding some complexity to the coproduct part and seeing what happens. Let's just add a constructor:

case class Foo(i: Int) extends Trait2

Now everything works fine, and we get this message during compilation:

Does not dominate:
TC[shapeless.::[String,shapeless.::[String,shapeless.HNil]]] (complexity: 7)
TC[shapeless.:+:[ComplexClass,shapeless.:+:[Foo,shapeless.CNil]]] (complexity: 9)

So the ComplexClass hlist representation still overlaps the Trait2 coproduct representation, but it doesn't dominate it, since the Trait2 representation (the subject of the open implicit TC search we're worried about) is now more complex.

The checker is clearly being much too paranoid here, and its behavior may change in the future, but for now we're stuck with it. As you note, the most straightforward and fool-proof workaround is to stick a Lazy in there to hide the supposed recursion from the divergence checker.

In this case specifically, though, it looks like just putting the instances in the TC companion object works as well:

import shapeless._

sealed trait Trait1
case class SimpleClass(a: String) extends Trait1

sealed trait Trait2
case class ComplexClass(a: String, b: String) extends Trait2

trait TC[T]

object TC {
  //Instances for HList
  implicit def hnilInstance: TC[HNil] = ???
  implicit def hconsInstance[H, T <: HList](implicit t: TC[T]): TC[H :: T] = ???

  //Instances for CoProduct
  implicit def cnilInstance: TC[CNil] = ???
  implicit def cconsInstance[H, T <: Coproduct](implicit
    h: TC[H], t: TC[T]
  ): TC[H :+: T] = ???

  //Instances for Generic, relying on HNil & HCons
  implicit def genericInstance[T, H](implicit
    g: Generic.Aux[T, H], t: TC[H]
  ): TC[T] = ???
}

And then:

Does not dominate:
TC[shapeless.::[String,shapeless.::[String,shapeless.HNil]]] (complexity: 7)
TC[shapeless.:+:[ComplexClass,shapeless.CNil]] (complexity: 16)

Why does moving stuff around like this raise the complexity of the coproduct? I have no idea.

Why does scalac rise a "diverging implicit expansion" error here?

1 Answers