Comportamento strano che cerca di convertire ricorsivamente case class class in liste eterogenee con Shapeless

Question

Ho dormito troppo tardi la scorsa notte cercando di capire questo problema di Shapeless e temo che mangerà la mia serata se non lo tolgo il mio petto, quindi ecco qui.

In questa versione minimizzata io sono solo la definizione di una classe tipo che ricorsivamente convertire classi case in heterogeneous liste:

import shapeless._ 

trait DeepHLister[R <: HList] extends DepFn1[R] { type Out <: HList } 

trait LowPriorityDeepHLister { 
    type Aux[R <: HList, Out0 <: HList] = DeepHLister[R] { type Out = Out0 } 

    implicit def headNotCaseClassDeepHLister[H, T <: HList](implicit 
    dht: DeepHLister[T] 
): Aux[H :: T, H :: dht.Out] = new DeepHLister[H :: T] { 
    type Out = H :: dht.Out 
    def apply(r: H :: T) = r.head :: dht(r.tail) 
    } 
} 

object DeepHLister extends LowPriorityDeepHLister { 
    implicit object hnilDeepHLister extends DeepHLister[HNil] { 
    type Out = HNil 
    def apply(r: HNil) = HNil 
    } 

    implicit def headCaseClassDeepHLister[H, R <: HList, T <: HList](implicit 
    gen: Generic.Aux[H, R], 
    dhh: DeepHLister[R], 
    dht: DeepHLister[T] 
): Aux[H :: T, dhh.Out :: dht.Out] = new DeepHLister[H :: T] { 
    type Out = dhh.Out :: dht.Out 
    def apply(r: H :: T) = dhh(gen.to(r.head)) :: dht(r.tail) 
    } 

    def apply[R <: HList](implicit dh: DeepHLister[R]): Aux[R, dh.Out] = dh 
} 

Proviamo it out! In primo luogo abbiamo bisogno di alcuni classi case:

case class A(x: Int, y: String) 
case class B(x: A, y: A) 
case class C(b: B, a: A) 
case class D(a: A, b: B) 

E poi (si noti che ho ripulito la sintassi tipo per il bene di questo non essere un pasticcio del tutto illeggibile):

scala> DeepHLister[A :: HNil] 
res0: DeepHLister[A :: HNil]{ 
    type Out = (Int :: String :: HNil) :: HNil 
} = DeepHLister$$anon$2@634bf0bf 

scala> DeepHLister[B :: HNil] 
res1: DeepHLister[B :: HNil] { 
    type Out = (
    (Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil 
) :: HNil 
} = DeepHLister$$anon$2@69d6b3e1 

scala> DeepHLister[C :: HNil] 
res2: DeepHLister[C :: HNil] { 
    type Out = (
    ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: 
    (Int :: String :: HNil) :: 
    HNil 
) :: HNil 
} = DeepHLister$$anon$2@4d062faa 

Fin qui tutto bene. Ma poi:

scala> DeepHLister[D :: HNil] 
res3: DeepHLister[D :: HNil] { 
    type Out = ((Int :: String :: HNil) :: B :: HNil) :: HNil 
} = DeepHLister$$anon$2@5b2ab49a 

Il B non ha ottenuto convertito. Se si accende -Xlog-implicits questo è l'ultimo messaggio:

<console>:25: this.DeepHLister.headCaseClassDeepHLister is not a valid implicit value for DeepHLister[shapeless.::[B,shapeless.HNil]] because: 
hasMatchingSymbol reported error: diverging implicit expansion for type DeepHLister[this.Repr] 
starting with method headNotCaseClassDeepHLister in trait LowPriorityDeepHLister 
       DeepHLister[D :: HNil] 
         ^

Il che non ha senso per me- headCaseClassDeepHLister dovrebbe essere in grado di generare DeepHLister[B :: HNil] bene, e lo fa se chiedete direttamente.

Questo succede sia su 2.10.4 che su 2.11.2, sia con versione 2.0.0 sia master. Sono abbastanza sicuro che questo deve essere un bug, ma non escludo la possibilità che sto facendo qualcosa di sbagliato. Qualcuno ha mai visto qualcosa di simile prima? C'è qualcosa di sbagliato nella mia logica o qualche restrizione su Generic Mi manca?

Ok, grazie per l'ascolto, forse ora posso andare a leggere un libro o qualcosa del genere.

Answer 1

Questo ora funziona più o meno come scritto usando recente informe-2.1.0-SNAPSHOT costruisce, e un parente stretto del campione in questa domanda ha stato aggiunto lì come example.

Il problema con l'originale è che ogni espansione di un Generic introduce un nuovo HList tipo nella risoluzione implicita delle istanze DeepHLister tipo di classe e, in linea di principio, potrebbe produrre un HList tipo che è legato al ma più complesso rispetto ad alcuni tipo visto in precedenza durante la stessa risoluzione. Questa condizione interrompe il controllo della divergenza e interrompe il processo di risoluzione.

I dettagli esatti del perché questo accade per D ma non per C è in agguato nei dettagli l'attuazione delle coontrollore dei tipo di Scala, ma, ad una prima approssimazione, l'elemento di differenziazione è che durante la risoluzione per C vediamo il B (più grande) prima dello A (più piccolo), quindi il controllore della divergenza è felice che i nostri tipi stiano convergendo; viceversa durante la risoluzione per D vediamo lo A (più piccolo) prima dello B (più grande), quindi i checker di divergenza (prudenzialmente).

La correzione per questo in 2.1.0 senza forma è il costruttore di tipo Lazy recentemente perfezionato e l'infrastruttura di macro implicita associata. Ciò consente un controllo molto più utente sulla divergenza e supporta l'uso della risoluzione implicita per costruire i valori impliciti ricorsivi che sono cruciali per la capacità di derivare automaticamente istanze di classe tipo per tipi ricorsivi. Molti esempi di questo possono essere trovati nella base di codice informe, in particolare l'infrastruttura di derivazione di classe type rielaborata e l'implementazione Scrap Your Boilerplate, che non richiede più il supporto macro dedicato, ma sono implementati interamente in termini di primitive Generic e Lazy. Varie applicazioni di questi meccanismi possono essere trovate nel sottoprogetto di esempi senza forma.

Answer 2

Ho seguito un approccio leggermente diverso.

trait CaseClassToHList[X] { 
    type Out <: HList 
} 

trait LowerPriorityCaseClassToHList { 
    implicit def caseClass[X](implicit gen: Generic[X]): CaseClassToHList[X] { 
    type Out = generic.Repr 
    } = null 
} 

object CaseClassToHList extends LowerPriorityCaseClassToHList { 
    type Aux[X, R <: HList] = CaseClassToHList[X] { type Out = R } 

    implicit def caseClassWithCaseClasses[X, R <: HList](
    implicit toHList: CaseClassToHList.Aux[X, R], 
    nested: DeepHLister[R]): CaseClassToHList[X] { 
    type Out = nested.Out 
    } = null 
} 

trait DeepHLister[R <: HList] { 
    type Out <: HList 
} 

object DeepHLister { 

    implicit def hnil: DeepHLister[HNil] { type Out = HNil } = null 

    implicit def caseClassAtHead[H, T <: HList](
    implicit head: CaseClassToHList[H], 
    tail: DeepHLister[T]): DeepHLister[H :: T] { 
    type Out = head.Out :: tail.Out 
    } = null 

    def apply[X <: HList](implicit d: DeepHLister[X]): d.type = null 
} 

testato con il seguente codice:

case class A(x: Int, y: String) 
case class B(x: A, y: A) 
case class C(b: B, a: A) 
case class D(a: A, b: B) 

object Test { 

    val z = DeepHLister[HNil] 
    val typedZ: DeepHLister[HNil] { 
    type Out = HNil 
    } = z 

    val a = DeepHLister[A :: HNil] 
    val typedA: DeepHLister[A :: HNil] { 
    type Out = (Int :: String :: HNil) :: HNil 
    } = a 

    val b = DeepHLister[B :: HNil] 
    val typedB: DeepHLister[B :: HNil] { 
    type Out = ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil 
    } = b 

    val c = DeepHLister[C :: HNil] 
    val typedC: DeepHLister[C :: HNil] { 
    type Out = (((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil 
    } = c 

    val d = DeepHLister[D :: HNil] 
    val typedD: DeepHLister[D :: HNil] { 
    type Out = ((Int :: String :: HNil) :: ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil) :: HNil 
    } = d 
}