How to use Scala 3 Recursive Match Types on tuples

I am trying to build a small library for representing typed paths. I have a reduced version below to try to express the concept of what I want.

Is there a way to get make not emit errors?

package bar

object XX {

  @FunctionalInterface
  trait SegmentDecoder[A] {
    self =>
    def decode(segment: String): Either[String, A]

    final def map[B](f: A => B): SegmentDecoder[B] = (s) => self.decode(s).map(f)

    final def flatMap[B](f: A => SegmentDecoder[B]): SegmentDecoder[B] = (s) => self.decode(s).flatMap(a => f(a).decode(s))
  }

  object SegmentDecoder {
    given SegmentDecoder[Int] = (seg) => seg.toIntOption.toRight(s"'$seg' is not a valid int")

    given SegmentDecoder[Long] = (seg) => seg.toLongOption.toRight(s"'$seg' is not a valid long")

    given SegmentDecoder[String] = (seg) => Right(seg)

    given SegmentDecoder[Unit] = (_) => Right(())
  }

  case class Param[A](name: String, converter: SegmentDecoder[A])

  def param[A](name: String)(using S: SegmentDecoder[A]) = Param(name, S)


  enum P[A <: Tuple] {
    def /(segment: String) = Static(this, segment)

    def /[A](param: Param[A]) = Variable(this, param.name, param.converter)


    case Root extends P[EmptyTuple]
    case Static[T <: Tuple](parent: P[T], name: String) extends P[T]
    case Variable[H, T <: Tuple](parent: P[T], name: String, decoder: SegmentDecoder[H]) extends P[Tuple.Append[T, H]]
  }

  type Elem[X <: Tuple] = X match {
    case EmptyTuple => P.Root.type
    case String *: xs => P.Static[xs]
    case Param[y] *: xs => P.Variable[y, xs]
  }

  def makeBroken[T <: Tuple](t: T): Elem[T] = {
    t match {
      case _: EmptyTuple => P.Root
      case (x *: xx): (String *: xs) => P.Static(makeBroken[xs](xx).asInstanceOf[P[xs]], x)
      case (x *: xx): (Param[t] *: xs) => P.Variable(makeBroken[xs](xx).asInstanceOf[P[xs]], x.name, x.converter)
    }
  }

  def make[T <: Tuple](t: T): P[T] = {
    t match {
      case _: EmptyTuple => P.Root.asInstanceOf[P[T]]
      case (x: String) *: xx => P.Static(make(xx).asInstanceOf[P[xx.type]], x).asInstanceOf[P[T]]
      case (x: Param[a]) *: xx => P.Variable(make(xx).asInstanceOf[P[xx.type]], x.name, x.converter).asInstanceOf[P[T]]
    }
  }
}

usage

object Main {
  import XX.*

  val link1 = make("foo", param[Int]("bar"), param[String]("bar"))
  val link2 = P.Root / "foo" / param[Int]("bar") / param[String]("bar"))
  //val link3 = makeBroken("foo", param[Int]("bar"), param[String]("bar")) //fails runtime with class cast exception
}

make and makeBroken causes a warning

XX.scala:50:5: match may not be exhaustive.

It would fail on pattern case: _: *:[Any,Tuple]
 [50:5]

XX.scala:58:5: match may not be exhaustive.

It would fail on pattern case: *:(_, _)
 [58:5]

Solution

Compiling your code with the version 3.2.2 of the Scala compiler, I get the following additional warning:

-- Unchecked Warning: /Users/mbovel/scala-snippets-2/so76236049.scala:50:11 -------
50 |      case (x *: xx): (String *: xs) => P.Static(makeBroken[xs](xx).asInstanceOf[P[xs]], x)
   |           ^
   |the type test for (String *: xs) @xs cannot be checked at runtime because its type arguments can't be determined from T

This explains the exception you get: the compiler cannot check the type (String *: xs) at runtime. In general, due to type erasure, runtime type checking in Scala can't distinguish between parameterized types. Therefore, the compiler generates code that only checks that t is a tuple and then directly casts t.head to String without checking that this is the case. You can see it by printing the generated code for example with scala -Xprint:genBCode so76236049.scala:

...
def makeBroken(t: Product): Object = 
      {
        (matchResult11[XX.XX$P]: 
          {
            case val x14: Product = t
            if x14.eq(EmptyTuple) then 
              {
                return[matchResult11] XX$P#Root
              }
             else ()
            if scala.runtime.Tuples.isInstanceOfNonEmptyTuple(x14) then 
              {
                case val x20: Tuple2 = *:.unapply(x14:Product)
                case val x: String = x20._1().asInstanceOf[String]
...

Your best bet to avoid this shortcoming and still have your makeBroken method type-check as Elem[T] is to split your match type and your term-level match in two levels:

type Elem[X <: Tuple] = X match {
  case EmptyTuple => P.Root.type
  case x *: xs =>
      x match {
          case String => P.Static[xs]
          case Param[y] => P.Variable[y, xs]
      }
}

def makeUnbroken[T <: Tuple](t: T): Elem[T] = {
  t match {
    case _: EmptyTuple => P.Root
    case t: (x *: xs) =>
      t.head match {
        case head: String => P.Static(makeUnbroken[xs](t.tail).asInstanceOf[P[xs]], head)
        case head: Param[t] => P.Variable(make(t.tail).asInstanceOf[P[xs]], head.name, head.converter)
      }
  }
}