Unsound use of ClassTag.unapply

[nicolasstucki]

Issue

  /** A ClassTag[T] can serve as an extractor that matches only objects of type T.
   *
   * The compiler tries to turn unchecked type tests in pattern matches into checked ones
   * by wrapping a `(_: T)` type pattern as `ct(_: T)`, where `ct` is the `ClassTag[T]` instance.
   * Type tests necessary before calling other extractors are treated similarly.
   * `SomeExtractor(...)` is turned into `ct(SomeExtractor(...))` if `T` in `SomeExtractor.unapply(x: T)`
   * is uncheckable, but we have an instance of `ClassTag[T]`.
   */
  def unapply(x: Any): Option[T] = 
    ...

This unfortunately is known to break when used with path dependent type.

Example

The following example shows a couple of cases where it fails

trait R {
  type Nat
  type Succ <: Nat
  type Idx
  given ClassTag[Nat]
  given ClassTag[Succ]
  given ClassTag[Idx]
  def n: Nat
  def one: Succ
}
class RI extens R {
  type Nat = Int
  type Succ = Int
  type Idx = Int
  given ClassTag[Nat] = classOf[Integer]
  given ClassTag[Succ] = new ClassTag[Integer] {
    def runtimeClass = classOf[Integer]
    def unapply(x: Any): Option[Succ] = x match
      case n: Int if n > 0 => Some(n)
      case _ => None
  }
  given ClassTag[Idx] = classOf[Integer]
  def n: Nat = 4
  def one: Succ = 1
}
object App {
  val r1: R = new RI
  val r2: R = new RI
  r1.n match {
    case n: r2.Nat => // Should not match or should have an unchecked waring
    case n: r1.Idx => // Should not match or should have an unchecked waring
    case n: r1.Succ => // Should match only if r1.n is an r1.Succ under the constraints set in r1
  }

  r1.one match {
    case n: r2.Nat => // Should not match or should have an unchecked waring
    case n: r1.Idx => // Should not match or should have an unchecked waring
    case n: r1.Nat => // Ok
  }
}

[nicolasstucki]

@sjrd said in this comment

To me, from the last discussion we had, there is only one reasonable path forward that will solve all the problems at once, with a clean design, and no migration issue:

First, introduce a new typeclass

trait TypeTest[A] {
  def isInstance(x: Any): Boolean
}

that can be synthesized by the compiler for A = p.T in exactly the same situations where an x.isInstanceOf[p.T] would be valid, and synthesizes it precisely as

new TypeTest[p.T] {
  def isInstance(x: Any): Boolean = x.isInstanceOf[p.T]
}

Then, in pattern-matching, for case x: A or case Extractor(x) where the Extractor expects an A, if A cannot be tested natively, try summoning a TypeTest[A]. Only if that fails as well, try summoning a ClassTag[A].

Finally, deprecated ClassTag.unapply and summoning a ClassTag[A] to implement a type test, since they are unsound.

ClassTags were designed for Arrays. This is the use case they are widely used for, and they work perfectly for that use case. It is only later on that the type-test feature was bolted on, without giving it more thought than a PR review. Please let's not pretend that ClassTags are broken and need fixing because that bolted-on feature is broken. ClassTags are correct. It's using ClassTags for type tests that's broken. The correct fix is not to fix ClassTags but to fix type-tests.

The above TypeTest typeclass is slightly unsound because one can implement a custom TypeTest for any A that always returns true. The subsequent compiler-generated .asInstanceOf[A] will throw a CCE. We can fix that design by complicating a bit the TypeTest API as follows:

trait TypeTest[A] {
  def isInstance(x: Any): TypeTest.Result[x.type & A]
}
object TypeTest {
  opaque type Result[A] = Boolean

  def success[A](x: A): Result[A] = true
  def failure[A]: Result[A] = false
}

Now a synthesized TypeTest[p.T] would look like

new TypeTest[p.T] {
  def isInstance(x: Any): TypeTest.Result[x.type & p.T] = x match {
    case x: p.T => TypeTest.success(x)
    case _      => TypeTest.failure
  }
}

and we can safely write custom TypeTest[A] instances that are sound down the line.

[nicolasstucki]

Small fix:

new TypeTest[p.T] {
  def isInstance(x: Any): TypeTest.Result[x.type & p.T] = x match {
    case x: (p.T & x.type) => TypeTest.success(x)
    case _                 => TypeTest.failure
  }
}

[nicolasstucki]

There is still something missing, when we do have an implicit p2.Y in scope we can match a p1.Y without an unchecked warning.

object Test {
  def main(args: Array[String]): Unit = {
    val p1: T = T1
    import p1.given

    val p2: T = T1
    import p2.given

    (p1.y: p1.X) match {
      case x: p2.Y => // should be an unchecked cast but is not
      case x: p1.Y =>
      case _ =>
    }
  }

}

trait T {
  type X
  type Y <: X
  def x: X
  def y: Y
  given TypeTest[Y] = typeTestOfY
  protected def typeTestOfY: TypeTest[Y]
}

object T1 extends T {
  type X = Boolean
  type Y = true
  def x: X = false
  def y: Y = true
  protected def typeTestOfY: TypeTest[Y] = new {
    def isInstance(x: Any): TypeTest.Result[x.type & Y] = x match
      case x: (true & x.type) => TypeTest.success(x)
      case _ => TypeTest.failure
  }
}

This can be solved by adding adding a second type parameter like in #7394.

trait TypeTest[S, T <: S] {

  def isInstance(x: S): TypeTest.Result[x.type & T]

  def unapply(x: S): Option[x.type & T] =
    TypeTest.unapply(x)(given this)

}

object TypeTest {

  opaque type Result[A] = Boolean

  def success[A](x: A): Result[A] = true

  def failure[A]: Result[A] = false

  def unapply[S, T <: S](x: S)(given tt: TypeTest[S, T]): Option[x.type & T] =
    if tt.isInstance(x) then Some(x.asInstanceOf[x.type & T])
    else None

}

And using it in the following way

trait T {
  type X
  type Y <: X
  def x: X
  def y: Y
  given TypeTest[X, Y] = typeTestOfY
  protected def typeTestOfY: TypeTest[X, Y]
}
object T1 extends T {
  type X = Boolean
  type Y = true
  def x: X = false
  def y: Y = true
  protected def typeTestOfY: TypeTest[X, Y] = new {
    def isInstance(x: X): TypeTest.Result[x.type & Y] = x match
      case x: (true & x.type) => TypeTest.success(x)
      case _ => TypeTest.failure
  }
}

Though we would need to ensure that S in TypeTest[S, T] is defined locally to ensure we do not get the previous unsoundness.

[nicolasstucki]

We could also consider defining it like

trait TypeTest[S, T <: S] {
  def unapply(x: S): TypeTest.Result[x.type & T]
}

object TypeTest {

  opaque type Result[A] = A | Failure.type

  object Result {
    given [A](res: Result[A]) { // currently fails, not sure where to put the extension methods
      def isEmpty: Boolean = res == Failure
      def get: A = res.asInstanceOf[A]
    }
  }

  private object Failure

  def success[A](x: A): Result[A] = x

  def failure[A]: Result[A] = Failure

}

[smarter]

See also https://gist.github.com/Blaisorblade/a0eebb6a4f35344e48c4c60dc2a14ce6 by @Blaisorblade

[Blaisorblade]

In the links from my gist, there was also another proposal: scala/bug#9565 (comment). IIRC it was sound, so maybe somebody should compare.

Not that I see anything wrong in @sjrd proposal, but I haven't studied it.

Fwiw, re the "Small fix" in #7554 (comment), I thought the original code was supposed to compile: the extra Singleton should be inferred, and that's central to @AleksanderBG's GADT work, even tho that wasn't part of the spec. Isn't that settled by now?

[LPTK]

A less ad-hoc alternative to the opaque type approach that also does not allocate would be to define an abstract base class of <:< called <?< which would have a new Not_<:< subclass.

Then, we can define:

trait TypeTest[A] {
  def isInstance(x: Any): x.type <?< A
}

And GADT pattern matching (ping @AleksanderBG) allows us to recover the x.type <: A relation in the case where the return value is indeed <:<. Like is done today, all <:< instances can be shared behind the scenes.

Implementing TypeTest becomes:

new TypeTest[p.T] {
  def isInstance(x: Any): x.type <?< p.T = x match {
    case x: (p.T & x.type) => implicitly
    case _                 => Not_<:<
  }
}

Maybe we'll need to help the compiler and write implicitly[x.type <:< (p.T & x.type)] though.

[abgruszecki]

Fwiw, re the "Small fix" in #7554 (comment), I thought the original code was supposed to compile: the extra Singleton should be inferred, and that's central to @AleksanderBG's GADT work, even tho that wasn't part of the spec. Isn't that settled by now?

It's settled, but I've never gotten around to actually implementing it in the compiler. So far it's necessary to manually add the singleton type to the pattern.

And GADT pattern matching (ping @AleksanderBG) allows us to recover the x.type <: A relation in the case where the return value is indeed <:<.

That won't work, GADT patmat cannot currently constrain singleton types. A mechanism for constraining singleton types is already implemented for explicit null types in their PR, so after that gets merged, we could look into reusing it for GADTs.

[nicolasstucki]

The least ad-hoc alternative and most straightforward version so far is

trait TypeTest[-S, T] {
  /** A TypeTest[S, T] can serve as an extractor that matches only S of type T.
   *
   * The compiler tries to turn unchecked type tests in pattern matches into checked ones
   * by wrapping a `(_: T)` type pattern as `tt(_: T)`, where `ct` is the `TypeTest[S, T]` instance.
   * Type tests necessary before calling other extractors are treated similarly.
   * `SomeExtractor(...)` is turned into `tt(SomeExtractor(...))` if `T` in `SomeExtractor.unapply(x: T)`
   * is uncheckable, but we have an instance of `TypeTest[S, T]`.
   */
  def unapply(x: S): Option[x.type & T]
}

The semantics are trivial as no extra concept must be added to encode the result. It also seamlessly works as ClassTag use to in the compiler. It's drawback is that we need to instantiate an Option which is the same as with the current ClassTag version.

The synthesized version would be

new TypeTest[S, T] {
  def unapply(x: S): Option[x.type & T] = x match {
    case x: T => Some(x)
    case _      => None
  }
}

which can be synthesised as a SAM

((x: S) => x match { case x: T => Some(x); case _ => None }): TypeTest[S, T]