为什么scalac在这里出现"分歧的隐式扩展"错误？

Question

在下面的代码中,我尝试使用shapeless派生类型类实例.但是,在更复杂的案例类(转换为更复杂的HList)的情况下,编译器给我一个"分歧的隐式扩展",即使它似乎没有两次解析相同类型的隐式类型.也许我错过了编译器的其他一些规则？

(小提琴: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字段的case类,编译器无法做到这样的事情 - 所以我想知道:为什么我必须在Lazy这里使用才能使它工作？

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

我已经创建了一些小提琴,因此您可以直接执行代码.

Answer 1

几年前,当我处理这样的问题时,我发现找出分歧检查器正在做的最简单的方法就是将一些printlns扔进编译器并在本地发布.在2.12中,相关代码是这里的dominates方法,我们可以用这样的方法替换最后一行:

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 publishLocalscalac并尝试编译您的代码:

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

这里的问题是我们正在寻找(树中最低节点)的TC实例String :: String :: HNil,但我们有一个开放搜索ComplexClass :+: CNil(三步).编译器认为它们String :: String :: HNil都重叠并占据主导地位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)

所以ComplexClasshlist表示仍然重叠的Trait2副产品表示,但并不支配它,因为Trait2代表(开放隐含的主题TC,我们即将担心搜索)现在更加复杂.

检查员显然在这里过于偏执,其行为可能在未来发生变化,但现在我们仍然坚持下去.正如您所指出的,最直接和最简单的解决方法是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)

为什么像这样移动东西会增加副产品的复杂性？我不知道.