ClassTag-based IsInstanceOf is unsound

ClassTag-based IsInstanceOf is unsound.md

If T is a parameterized type, then isInstanceOf[T] must give an erasure warning, even if we have a ClassTag[T] in scope. Alternatively, we could ensure that ClassTag[T] does not exist for parameterized types, but only for their wildcard versions. More alternatives might be desirable, since ClassTag[T] is also used for array creation and that has different requirements.

This code (files below) demonstrates why.

The issue is that we get heap pollution and a ClassCastException without casts or erasure warnings, and that must not happen, as described by Java's guarantees for erasure warnings, which I expect should apply to us too:

https://docs.oracle.com/javase/tutorial/java/generics/nonReifiableVarargsType.html

Googling instanceof classtag unsound finds nothing, but somebody must have noticed? I expect I never did, but this issue is surprisingly easy to trigger. Apparently shapeless's Typeable takes care of avoiding the issue: https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/typeable.scala

How to restrict ClassTag

The proposals below were collected from Gitter, with some added comments. This summary has no pretense to be complete.

By fiat in the compiler

Scala compiler treat ClassTag specially, so adding further special cases might be acceptable. Designing a more general API is hard.

Downside: using ClassTag[List[Int]] to create an array is fully sound, and would now require a cast on the resulting array even though the compiler knows that cast can't fail.

With the Erasure API

I imagined a special case. @Ichoran on gitter suggests defining a generic type function Erasure such that Erasure[F[A]] was F[_], and using it as implicit def createClassTag[T]: ClassTag[Erasure[T]]. I like that, given at least another good usecase.

For a contrived example, Erasure would allow giving better types to (variants of) safeCast, such as safeCastAs:

  type BetterClassTag[T] = ClassTag[Erasure[T]]
  def safeCastAs[T: BetterClassTag](x: Any, y: T): Option[(Erasure[T], T)] = {
    x match {
      case x: T => Some(x)
      case _ => None
    }
  }

However, @alexknvl remarks that Erasure would be an unusual type function in Scala, since it's neither constant nor injective and it "pattern-matches" into its argument so it's not "parametric" in some sense. (I don't think it's the first, but all the ones I can find require complex encodings). Non-injective type constructors are also problematic in Hindley-Milner type inference (as well-known from Haskell type families); even in Scala, passing an Erasure[B] to a function demanding Erasure[A] doesn't let the compiler infer that A = B.

But these downsides might be smaller than later proposals, right now (iterations pending).

Possibly, this API should be combined with something else so that inference problems can be avoided by coding patterns.

Have distinct ErasedClassTag[A] and ClassTag[A]

Use ErasedClassTag[A] for matching and ClassTag[A] for array creation. But taking ErasedClassTag[A] and ClassTag[A] for related types is still hard, it seems you'd need cta: ClassTag[A], ectea: ErasedClassTag[Erasure[A]].

Have an @erasedType annotation for type arguments

def foo[T @erasedType: ClassTag, U: ClassTag](x: Any) = {
  ...
  x.isInstanceOf[T] //no warning
  x.isInstanceOf[U] //warning
  ...
}

Still can't relate two type arguments except through Erasure. (Not erased because it's a Dotty keyword).

With a type member named Erased in ClassTag

An alternative would be a type member in ClassTag.

object stdlib {
  // I don't propose this annotation, so private.
  private sealed trait erasedType extends scala.annotation.Annotation
  // I'm not sure I propose this type, but I can't make it private.
  type Erasure[T]

  // This is the API I'm looking at, except it has to be special and I can't express how it is special in pure Scala, hence the above
  // ("private") APIs.
  trait MyClassTag[T] {
    type Erased
  }
  object MyClassTag {
    //I propose to restrict this method to erased T arguments.
    //implicit def myClassTag[@erasedType T <: AnyRef]: MyClassTag[T] { type Erased = T } = ???
    implicit def myClassTag[T <: AnyRef]: MyClassTag[T] { type Erased = Erasure[T] } = ???
  }
  implicit def pathDependentImplicitly[T](implicit x: T): x.type = x
  val ctListInt = pathDependentImplicitly[MyClassTag[List[Int]]]
  def f(xs: List[_]): ctListInt.Erased = xs
}

One annoying thing is that type members only work on stable terms, and among implicits only vals are stable; the above code requires pathDependentImplicitly instead of implicitly, and pathDependentImplicitly[MyClassTag[List[Int]]].Erased would also fail.

Consider also what's below:

val t: ClassTag[A] = A // here t.Erased is unconstrained, hence as alternative
val t = A // no type annotation, can trigger warnings
val t: ClassTag[A] { type Erased = A.Erased } = A // requires `Erased` member on all types and type constructors
val t: ClassTag[A] { type Erased = ErasedA } = A //require carrying both A and ErasedA, and it's unclear how to force them to be related

IsInstanceOfClassTag output

pgiarrusso@tsf-436-wpa-1-015:~/git/dotty$ scalac -d out /Users/pgiarrusso/git/dotty-example-project/src/main/scala/playground/IsInstanceOfClassTag.scala
pgiarrusso@tsf-436-wpa-1-015:~/git/dotty$ scala -cp out IsInstanceOfClassTag
java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
	at IsInstanceOfClassTag$.main(IsInstanceOfClassTag.scala:15)
	at IsInstanceOfClassTag.main(IsInstanceOfClassTag.scala)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at scala.reflect.internal.util.ScalaClassLoader.$anonfun$run$2(ScalaClassLoader.scala:99)
	at scala.reflect.internal.util.ScalaClassLoader.asContext(ScalaClassLoader.scala:34)
	at scala.reflect.internal.util.ScalaClassLoader.asContext$(ScalaClassLoader.scala:30)
pgiarrusso@tsf-436-wpa-1-015:~/git/dotty$ /usr/local/bin/dotc -d out /Users/pgiarrusso/git/dotty-example-project/src/main/scala/playground/IsInstanceOfClassTag.scala; cd out; /usr/local/bin/dotr IsInstanceOfClassTag
warning: multiple classpaths are found, dotr only use the last one.
Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
	at IsInstanceOfClassTag$.main(IsInstanceOfClassTag.scala:15)
	at IsInstanceOfClassTag.main(IsInstanceOfClassTag.scala)

IsInstanceOfClassTag.scala

import scala.reflect.ClassTag

object IsInstanceOfClassTag {
  def safeCast[T: ClassTag](x: Any): Option[T] = {
    x match {
      case x: T => Some(x)
      case _ => None
    }
  }

  def main(args: Array[String]): Unit = {
    safeCast[List[String]](List[Int](1)) match {
      case None =>
      case Some(xs) =>
        xs.head.substring(0)
    }

    // If we forbid ClassTag[List[String]] and only allow ClassTag[List[_]],
    // the issue appears fixed:
    safeCast[List[_]](List[Int](1)) match {
      case None =>
      case Some(xs) =>
        //xs.head.substring(0) //compile error:
// 20 |        xs.head.substring(0) //compile error
//    |        ^^^^^^^^^^^^^^^^^
//    |        value `substring` is not a member of xs.A
// one error found
    }
  }
}

Uh, a possible solution would be that the argument for T: ClassTag should not be List[String] but List[_].

Gitter discussion at https://gitter.im/scala/contributors?at=5aa016b5c3c5f8b90d44b6a7

I suggested something similar to "Have distinct ErasedClassTag[A] and ClassTag[A]" in an issue for this, scala/bug#9565.

Thanks @S11001001, I was certain somebody had to have noticed this quickly, and right away.