Почему скалак вызывает ошибку «расходящегося неявного расширения»?

Question

В следующем коде я пытаюсь получить экземпляры типов с бесформенными. Однако в случае более сложного класса case (который преобразуется в более сложный HList) компилятор дает мне «расходящееся неявное расширение», хотя он, кажется, не разрешает один и тот же тип неявного типа дважды. Может быть, мне не хватает другого правила компилятора?

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

, который, кажется, работает. Однако, с классом case 2-поля, компилятор не может сделать что-то вроде этого - так что мне интересно: почему я должен использовать 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) 
=========================== 

проблема в том, что мы ищем экземпляр 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) 

Так представление ComplexClass hlist еще перекрывается представление Trait2 Копроизведения, но это Безразлично доминировать над ним, поскольку представление Trait2 (тема открытого неявного поиска TC, о котором мы беспокоимся) теперь сложнее.

Checker явно находится здесь слишком параноидально, и его поведение 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) 

Почему перемещения вещи вокруг как это повышает сложность копроизведения? Понятия не имею.