爲什麼scalac在這裏出現「分歧的隱含擴展」錯誤？

Question

在下面的代碼中，我嘗試導出無形狀的類型實例。然而，對於更復雜的案例類（它被轉換爲更復雜的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] 

我創造了一些小提琴這樣你就可以執行的代碼有directy。

Answer 1

幾年前，當我通過some issues like this工作時，我發現找出分歧檢查器所做的最簡單的方法就是將一些println s放入編譯器並在本地發佈。在2.12的相關代碼是dominates方法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，並且它因爲看起來遞歸而退出。

這聽起來很可笑，所以我們可以做一個實驗，試圖通過添加一些複雜的副產品部分，看會發生什麼來說服自己。讓我們只需添加一個構造函數：

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餘積表示，但它不「T主宰它，因爲Trait2表示（開隱含TC搜索，我們即將擔心的主題）現在更加複雜。

檢查者顯然是過於偏執這裏，其行爲may change in the future，但現在我們還是堅持了下來。正如你所注意到的，最直接和最簡單的解決方法是在其中粘貼一個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) 

爲什麼移動的東西，周圍像這提高了副產品的複雜性？我不知道。