为什么 scalac 会在这里出现 "diverging implicit expansion" 错误？

Question

在下面的代码中，我尝试派生 typeclass 具有 shapeless 的实例。但是，在更复杂的情况下 class （转换为更复杂的 HList），编译器给了我一个 "diverging implicit expansion" 即使它似乎没有解析同一种隐式类型两次。也许我遗漏了编译器的其他一些规则？

(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
}

当试图解析 the[TC[Trait1]] 时，编译器应该做这样的事情：

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

这似乎有效。然而，对于 2-field 的情况 class，编译器无法做这样的事情 - 所以我想知道：为什么我必须在这里使用 Lazy 才能让它工作？

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

我已经创建了一些 fiddle 所以你可以直接执行代码。

Answer 1

几年前，当我研究 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 时，我们可以将最后一行替换为这样的内容：

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
})

然后我们可以 sbt publishLocal scalac 并尝试编译您的代码：

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

这里的问题是我们正在为 String :: String :: HNil（树中的最低节点）寻找 TC 实例，但我们有一个开放搜索 ComplexClass :+: CNil（上三步）。编译器认为 String :: String :: HNil 与 ComplexClass :+: CNil 重叠并支配 ComplexClass :+: CNil，它会退出，因为这看起来是递归的。

这听起来很荒谬，所以我们可以做一个实验来说服自己，给余积部分增加一些复杂性，看看会发生什么。让我们添加一个构造函数：

case class Foo(i: Int) extends Trait2

现在一切正常，我们在编译期间收到此消息：

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

因此 ComplexClass hlist 表示仍然重叠 Trait2 余积表示，但它并不支配它，因为 Trait2表示（我们担心的开放式隐式 TC 搜索的主题）现在更加复杂。

检查器在这里及其行为显然过于偏执 may change in the future，但现在我们坚持使用它。正如您所注意到的，最直接且 fool-proof 的解决方法是在其中粘贴一个 Lazy 以隐藏散度检查器假定的递归。

不过，在这种情况下，看起来只是将实例放在 TC 伴随对象中也是可行的：

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] = ???
}

然后：

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

为什么像这样移动东西会增加联积的复杂性？我不知道。

为什么 scalac 会在这里出现 "diverging implicit expansion" 错误？

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

scala

typeclass

implicit

shapeless