scala - Weird behavior trying to convert case classes to heterogeneous lists recursively with Shapeless

Question

I stayed up way too late last night trying to figure out this Shapeless issue and I'm afraid it's going to eat my evening if I don't get it off my chest, so here goes.

In this minimized version I'm just defining a type class that will recursively convert case classes into heterogeneous lists:

import shapeless._

trait DeepHLister[R <: HList] extends DepFn1[R] { type Out <: HList }

trait LowPriorityDeepHLister {
  type Aux[R <: HList, Out0 <: HList] = DeepHLister[R] { type Out = Out0 }

  implicit def headNotCaseClassDeepHLister[H, T <: HList](implicit
    dht: DeepHLister[T]
  ): Aux[H :: T, H :: dht.Out] = new DeepHLister[H :: T] {
    type Out = H :: dht.Out
    def apply(r: H :: T) = r.head :: dht(r.tail)
  }
}

object DeepHLister extends LowPriorityDeepHLister {
  implicit object hnilDeepHLister extends DeepHLister[HNil] {
    type Out = HNil
    def apply(r: HNil) = HNil
  }

  implicit def headCaseClassDeepHLister[H, R <: HList, T <: HList](implicit
    gen: Generic.Aux[H, R],
    dhh: DeepHLister[R],
    dht: DeepHLister[T]
  ): Aux[H :: T, dhh.Out :: dht.Out] = new DeepHLister[H :: T] {
    type Out = dhh.Out :: dht.Out
    def apply(r: H :: T) = dhh(gen.to(r.head)) :: dht(r.tail)
  }

  def apply[R <: HList](implicit dh: DeepHLister[R]): Aux[R, dh.Out] = dh
}

Let's try it out! First we need some case classes:

case class A(x: Int, y: String)
case class B(x: A, y: A)
case class C(b: B, a: A)
case class D(a: A, b: B)

And then (note that I've cleaned up the type syntax for the sake of this not being a totally unreadable mess):

scala> DeepHLister[A :: HNil]
res0: DeepHLister[A :: HNil]{
  type Out = (Int :: String :: HNil) :: HNil
} = DeepHLister$$anon$2@634bf0bf

scala> DeepHLister[B :: HNil]
res1: DeepHLister[B :: HNil] {
  type Out = (
    (Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil
  ) :: HNil
} = DeepHLister$$anon$2@69d6b3e1

scala> DeepHLister[C :: HNil]
res2: DeepHLister[C :: HNil] {
  type Out = (
    ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) ::
    (Int :: String :: HNil) ::
    HNil
  ) :: HNil
} = DeepHLister$$anon$2@4d062faa

So far so good. But then:

scala> DeepHLister[D :: HNil]
res3: DeepHLister[D :: HNil] {
  type Out = ((Int :: String :: HNil) :: B :: HNil) :: HNil
} = DeepHLister$$anon$2@5b2ab49a

The B didn't get converted. If we turn on -Xlog-implicits this is the last message:

<console>:25: this.DeepHLister.headCaseClassDeepHLister is not a valid implicit value for DeepHLister[shapeless.::[B,shapeless.HNil]] because:
hasMatchingSymbol reported error: diverging implicit expansion for type DeepHLister[this.Repr]
starting with method headNotCaseClassDeepHLister in trait LowPriorityDeepHLister
              DeepHLister[D :: HNil]
                         ^

Which doesn't make sense to me—headCaseClassDeepHLister should be able to generate DeepHLister[B :: HNil] just fine, and it does if you ask it directly.

This happens on both 2.10.4 and 2.11.2, and with both the 2.0.0 release and master. I'm pretty sure this has to be a bug, but I'm not ruling out the possibility that I'm doing something wrong. Has anyone seen anything like this before? Is there something wrong with my logic or some restriction on Generic I'm missing?

Okay, thanks for listening—maybe now I can go read a book or something.

Answer 1

This now works more or less as written using recent shapeless-2.1.0-SNAPSHOT builds, and a close relative of the sample in this question has been added there as an example.

The problem with the original is that each expansion of a Generic introduces a new HList type into the implicit resolution of the DeepHLister type class instances and, in principle, could produce an HList type that is related to but more complex than some type seen previously during the same resolution. This condition trips the divergence checker and aborts the resolution process.

The exact details of why this happens for D but not for C is lurking in the details of the implementation of Scala's typechecker but, to a rough approximation, the differentiator is that during the resolution for C we see the B (larger) before the A (smaller) so the divergence checker is happy that our types are converging; conversely during the resolution for D we see the A (smaller) before the B (larger) so the divergence checker (conservatively) bails.

The fix for this in shapeless 2.1.0 is the recently enhanced Lazy type constructor and associated implicit macro infrastructure. This allows much more user control over divergence and supports the use of implicit resolution to construct the recursive implicit values which are crucial to the ability to automatically derive type class instances for recursive types. Many examples of this can be found in the shapeless code base, in particular the reworked type class derivation infrastructure and Scrap Your Boilerplate implementation, which no longer require dedicated macro support, but are implemented entirely in terms of the Generic and Lazy primitives. Various applications of these mechanisms can be found in the shapeless examples sub-project.