Shapeless HList implicit resolution - diverging implicit expansion

Question

This is really bugging me. I am getting a diverging implicit expansion for type Meta[Field2 :: HNil] error which I try and compile the following:

case class Field() extends StaticAnnotation
case class Group() extends StaticAnnotation
case class Message() extends StaticAnnotation

@Field case class Field1(value: String)
@Field case class Field2(value: String)
@Field case class Field3(value: String)
@Group case class Group1(field1: Field1, field2: Field2)
@Message case class Message1(field3: Field3, group1: Group1)

trait Meta[T]

object Meta {
  implicit val hNil: Meta[HNil] = new Meta[HNil] {}
  implicit def field[TField](implicit a: Annotation[Field, TField]): Meta[TField] = new Meta[TField] {}
  implicit def hcons[Head, Tail <: HList](implicit h: Meta[Head], t: Meta[Tail]) : Meta[H :: T] = new Meta[H :: T] {}
  implicit def group[TGroup, ParamList <: HList](implicit a: Annotation[Group, TGroup], g: Generic.Aux[TGroup, ParamList], p: Meta[ParamList]): Meta[TGroup] = new Meta[TGroup] {}
  implicit def message[TMessage, ParamList <: HList](implicit a: Annotation[Message, TMessage], g: Generic.Aux[TMessage, ParamList], p: Meta[ParamList]): Meta[TMessage] = new Meta[TMessage] {}
}

object TestApp extends App {
  // throws compile exception here...
  implicitly[Meta[Message1]]
}

Kolmar Kolmar · Accepted Answer · 2018-11-20T23:19:55

Consider the process of expanding Meta[Message1]:

When expanding Meta[Message1] with message the compiler needs Meta[Field3 :: Group1 :: HNil]
Later, when expanding Meta[Group1] with group it needs Meta[Field1 :: Field2 :: HNil]

The compiler sees, that in this branch it has already expanded type constructor :: of at least the same complexity (i.e., with the same number of elements in the HList). So it assumes, that this expansion branch results in an infinite loop, and reports implicit divergence.

To prevent this behaviour you can use shapeless.Lazy. From the documentation:

Wraps a lazily computed value. Also circumvents cycles during implicit search, or wrong implicit divergences as illustrated below, and holds the corresponding implicit value lazily.

So to fix this problem you can wrap in Lazy the expansion of Head in hcons:

implicit def hcons[Head, Tail <: HList](implicit 
  h: Lazy[Meta[Head]], 
  t: Meta[Tail]
): Meta[Head :: Tail] = 
  new Meta[Head :: Tail] {}

Usually you should wrap in Lazy the expansions of heads in HList and Coproduct rules, and also the expansion of Repr in Generic rules. The latter is not necessary here, I think, because you'll necessary go through hcons rule, that already has Lazy, to get from one Group or Message to another).

Shapeless HList implicit resolution - diverging implicit expansion

1 Answers