Macro type mismatch recovering precise type: underlying type does not match

[hmf]

Minimized code

Don't know if this is a bug or if I simply do not know how to deal with this issue. The aim is to concatenate 2 HLists using transparent inline so that the resulting type is fully defined (we know all elements' types).

  sealed trait HList
  case class HCons[+HD, TL <: HList](hd: HD, tl: TL) extends HList
  case object HNil extends HList

  private def concatImpl[Xs <: HList, Ys <: HList](e: Expr[Xs], acc: Expr[Ys])
                                                   (using xt:Type[Xs], yt:Type[Ys], qctx:QuoteContext):
  Expr[_ <: HList] = {
    import qctx.reflect._

    e match {
      case '{HCons($a:$t, HNil)} =>
        '{HCons($a:t,$acc)}


      case '{HCons($a:$t,$tl:$ttl)} =>
        val ntl = concatImpl(tl,acc)
        '{HCons($a:t, $ntl:ttl)}

    }
  } 

  inline def concatM[Xs <: HList, Ys <: HList](inline xs: Xs, inline ys: Ys): Any = {
    ${ concatImpl('xs, 'ys) }
  }

    val rhl5: HCons[(String, Int),
                  HCons[(String, Double),
                    HCons[(String, Char), automl.Recorder.HNil.type]
                  ]
              ] = concatM(HCons(1, HCons(2.0,HNil)), HCons('3', HNil))

Output

[error] -- [E007] Type Mismatch Error: RecordMacro.scala:455:25 
[error] 455 |      case '{HCons($a:$t,$tl:$ttl)} =>
[error]     |                         ^^^^^^^^
[error]     |                         Found:    ev$6.Underlying
[error]     |                         Required: automl.Recorder.HList
[error] -- [E007] Type Mismatch Error: RecordMacro.scala:456:29 
[error] 456 |        val ntl = concatImpl(tl,acc)
[error]     |                             ^^
[error]     |                          Found:    (tl : scala.quoted.Expr[ttl])
[error]     |                          Required: quoted.Expr[automl.Recorder.HList]
[error] -- [E007] Type Mismatch Error: RecordMacro.scala:457:23 
[error] 457 |        '{HCons($a:t, $ntl:ttl)}
[error]     |                       ^^^
[error]     |Found:    quoted.Expr[?1.CAP]
[error]     |Required: quoted.Expr[ttl]
[error]     |
[error]     |where:    ?1 is an unknown value of type scala.internal.TypeBox[Nothing, automl.Recorder.HList]

Expectation

I would expect that the line:

      case '{HCons($a:$t,$tl)} =>
        val ntl = concatImpl(tl,acc)
        '{HCons($a:t, $nt:ttll)}

would compile and generate all types correctly. Note that if I use the following code:

      case '{HCons($a:$t,$tl)} =>
        val ntl = concatImpl(tl,acc)
        '{HCons($a:t, $ntl)}

the macro does compile, but compilation fails with:

[error] -- [E007] Type Mismatch Error: HyperParameters.scala:360:25 
[error] 360 |              ] = concatM(HCons(1, HCons(2.0,HNil)), HCons('3', HNil))
[error]     |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]     |  Found:    automl.Recorder.HCons[Int, automl.Recorder.HList]
[error]     |  Required: automl.Recorder.HCons[(String, Int), 
[error]     |    automl.Recorder.HCons[(String, Double), 
[error]     |      automl.Recorder.HCons[(String, Char), automl.Recorder.HNil.type]
[error]     |    ]
[error]     |  ]
[error] one error found

because I was not able to extract the tail's type.

Tested on 3.0.0-M1.

[adpi2]

This comment contains 2 updated versions of this issue.

Minimized code

Preliminary definitions

sealed trait HList
case class HCons[+HD, TL <: HList](hd: HD, tl: TL) extends HList
case object HNil extends HList

1. With inline match

transparent inline def concat[Xs <: HList, Ys <: HList](inline xs: Xs, inline ys: Ys): HList =
  inline xs match
  case HNil => ys
  case HCons(xhd, xtl) => HCons(xhd, concat(xtl, ys))

2. With a macro

transparent inline def concatM[Xs <: HList, Ys <: HList](inline xs: Xs, inline ys: Ys) =
  ${concatImpl('{xs}, '{ys})}

private def concatImpl[Xs <: HList: Type, Ys <: HList: Type](xs: Expr[Xs], ys: Expr[Ys])(using Quotes): Expr[HList] =
  xs match
  case '{HNil} => ys
  case '{
    type tl <: HList
    HCons[hd, `tl`]($xh, $xt)
  } =>
    val tail = concatImpl(xt, ys) 
    '{HCons($xh :hd, $tail)}

Output

In both cases, the type of the transparent inline call is one level deep.

val x1 = concat(HCons(1, HCons(2.0, HNil)), HCons('3', HNil)) // HCons[Any, HList]
val x2 = concatM(HCons(1, HCons(2.0, HNil)), HCons('3', HNil)) // HCons[Int, HList]

The return type is not refined recursively.

@nicolasstucki is this a limitation of transparent inline in the Scala 3 compiler? Will it ever be possible to overcome this limitation?

[adpi2]

As an alternative one can use recursive implicit search to concatenate types recursively.

With implicit search

trait Concat[XS <: HList, YS <: HList, R <: HList]:
  def concat(xs: XS, ys: YS): R

given [YS <: HList]: Concat[HNil.type, YS, YS] with
  def concat(xs: HNil.type, ys: YS): YS = ys

given [HD, XS <: HList, YS <: HList, TL <: HList](using rec: Concat[XS, YS, TL]): Concat[HCons[HD, XS], YS, HCons[HD, TL]] with
  def concat(xs: HCons[HD, XS], ys: YS): HCons[HD, TL] = HCons(xs.hd, rec.concat(xs.tl, ys))

def concat[XS <: HList, YS <: HList, R <: HList](xs: XS, ys: YS)(using impl: Concat[XS, YS, R]) =
  impl.concat(xs, ys)

In this case a call to concat is fully typed:

val x: HCons[Int, HCons[Double, HCons[Char, HNil.type]]] = concat(HCons(1, HCons(2.0, HNil)), HCons('a', HNil))

But the concatenation is not inlined, and because of the rec parameter, I have not been able to inline everything down to an HCons.apply.

[nicolasstucki]

@nicolasstucki is this a limitation of transparent inline in the Scala 3 compiler? Will it ever be possible to overcome this limitation?

In theory, it should be possible. This is a general limitation of the current implementation where we are not refining the types of bindings (val/pattern) enough after inlining (see #8739 and lampepfl/dotty-feature-requests#189).

[adpi2]

Thanks! So this is a duplicate of #8739.