Behaviour of Scala Compiler when Type-checking Casts in F-bounded Polymorphism

Language Design
1

I am a newcomer to using F-bounded polymorphism in Scala 3. The following code arose when I was trying to use it to prevent type-erasure in a parametrized trait.

sealed trait T0[X <: T0[X]]

case class T1() extends T0[T1]
case class T2() extends T0[T2]

def hCast[X <: T0[X], Y <: T0[Y]](y : Y) : Option[X] = {
      y match {
      case x : X => {
        println("check passed")
        Some(x)
      }
      case _ => None
    }
}

The Scala compiler produces a stack-overflow exception when compiling / type-checking this code (Scalastie link). In particular, the Scala 3 compiler outputs the following stacktrace:

java.lang.StackOverflowError
dotty.tools.dotc.core.Types$Type.dealias(Types.scala:1461)
dotty.tools.dotc.core.Definitions.isTupleNType(Definitions.scala:1725)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2924)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2931)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2931)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2931)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2927)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2927)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2927)
dotty.tools.dotc.core.TypeComparer.invariantDisjoint$1(TypeComparer.scala:2860)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint$$anonfun$3(TypeComparer.scala:2875)
scala.collection.LazyZip3.exists(LazyZipOps.scala:235)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2866)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2927)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint(TypeComparer.scala:2927)
dotty.tools.dotc.core.TypeComparer.invariantDisjoint$1(TypeComparer.scala:2860)
dotty.tools.dotc.core.TypeComparer.provablyDisjoint$$anonfun$3(TypeComparer.scala:2875)
<...>

I’m curious if there is a good explanation about this compiler behavior. Alternatively, I know I can use TypeTest[A, B] to prevent type-erasure as well (as long as A and B themselves are not parametric), but it seems to me that some use-cases of TypeTest would over-lap with F-bounded polymorphism, but the two are somewhat incompatible due to how the above code is rejected by the scala compiler. Any help would be appreciated.

1 Like
2

This is really a scala-users style question. The stack overflow is unfortunate, but fundamentally you can’t match on generic type parameters because they are known only by the compiler at compile-time while the code you’re writing decides upon the branch at runtime. Somehow you have to get that compile-time information to the runtime control flow.

If you have an inline method and do an inline match, then the compiler will use the compile-time value of X and do the match if possible:

inline def iCast[X <: T0[X], Y <: T0[Y]](y: Y): Option[X] =
  inline y match
    case x: X => Some(x)
    case _ => None

The inlining has to go all the way through to the use site–any place that isn’t inlined and just leaves you with generic type parameters will thwart your ability to tell who is whom. There won’t even be a branch at runtime! You’ll just have the appropriate expansion applied at compile-time depending on context.

Alternatively, you can use a TypeTest or ClassTag to do the match you want:

def hCast[X <: T0[X], Y <: T0[Y]](y: Y)(using tt: reflect.TypeTest[Y, X]): Option[X] =
  tt.unapply(y)

(There’s no point taking it apart in a match only to put it back together again–a TypeTest unapply already produces what you want.)

Again, the TypeTest context has to be propagated all the way up from the use site, but it’s more flexible since the context is a parameter and can be passed around instead of requiring arbitrarily deep inlining.

3 Likes
3

Thank you — this is a very helpful and clarifying post. This is indeed a more scala-users question, and I should have posted somewhere else in retrospect, except maybe one would hope for a slightly more helpful error message instead of a stack-overflow. :slight_smile:

1 Like
4

Note: I could not reproduce the stackoverflow on a stand-alone program in the latest main.