Opaque type combined with match type has unexpected behavior

[mrdziuban]

Compiler version

3.3.0, also tested with the latest nightly 3.3.2-RC1-bin-20230606-5d2812a-NIGHTLY

Minimized code

I'm splitting this into two snippets because for some reason the code to actually reproduce the error doesn't compile when it's compiled at the same time as the setup code

Setup code

Save this to a file and load a REPL with it

package test

import types._

object types {
  opaque type ->>[K, V] = V
  extension [K <: Singleton](k: K) def ->>[V](v: V): K ->> V = v.asInstanceOf[K ->> V]
}

type FindField[T <: Tuple, K] = FindField0[T, K, 0]

type FindField0[T <: Tuple, K, I <: Int] <: (Any, Int) = T match {
  case (K ->> f) *: _ => (f, I)
  case _ *: t => FindField0[t, K, compiletime.ops.int.S[I]]
}

trait Selector[T, Key] {
  type Out
  def apply(t: T): Out
}

object Selector {
  type Aux[T, K, O] = Selector[T, K] { type Out = O }

  inline def apply[T, K](using s: Selector[T, K]): Aux[T, K, s.Out] = s

  inline given selectorInst[T <: Tuple, K](
    using idx: ValueOf[Tuple.Elem[FindField[T, K], 1]],
  ): Selector.Aux[T, K, Tuple.Head[FindField[T, K]]] =
    new Selector[T, K] {
      type Out = Tuple.Head[FindField[T, K]]
      def apply(t: T): Out = t.productElement(idx.value).asInstanceOf[Out]
    }
}

Error code

Run this code in the REPL

import test._
import test.types._

val t = ("s" ->> "foo") *: ("i" ->> 3) *: EmptyTuple
val s = Selector[("s" ->> String) *: ("i" ->> Int) *: EmptyTuple, "i"]
s(t)

Output

scala> s(t)
java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
  at rs$line$4$$anon$1.apply(rs$line$4:1)
  at rs$line$4$$anon$1.apply(rs$line$4:1)
  ... 66 elided

Expectation

The code should run without error and return an Int. Interestingly, if you make a small change to the definition of opaque type ->>, then the error goes away:

diff --git a/Selector.scala b/Selector.scala
index 69bd8a3..314e219 100644
--- a/Selector.scala
+++ b/Selector.scala
@@ -3,7 +3,8 @@ package test
 import types._
 
 object types {
-  opaque type ->>[K, V] = V
+  type Tag[A]
+  opaque type ->>[K, V] = V & Tag[K]
   extension [K <: Singleton](k: K) def ->>[V](v: V): K ->> V = v.asInstanceOf[K ->> V]
 }

[sjrd]

The setup code does not compile for me on the latest main:

-- [E007] Type Mismatch Error: tests/run/i17994.scala:32:50 --------------------
32 |      def apply(t: T): Out = t.productElement(idx.value).asInstanceOf[Out]
   |                                              ^^^^^^^^^
   |Found:    Tuple.Elem[test.FindField[T, K], (1 : Int)]
   |Required: Int
   |
   |where:    T is a type in given instance selectorInst with bounds <: Tuple
   |
   |
   |Note: a match type could not be fully reduced:
   |
   |  trying to reduce  Tuple.Elem[test.FindField[T, K], (1 : Int)]
   |  trying to reduce  test.FindField[T, K]
   |  trying to reduce  test.FindField0[T, K, (0 : Int)]
   |  failed since selector T
   |  does not match  case (K ->> f) *: _ => (f, (0 : Int))
   |  and cannot be shown to be disjoint from it either.
   |  Therefore, reduction cannot advance to the remaining case
   |
   |    case _ *: t => test.FindField0[t, K, scala.compiletime.ops.int.S[(0 : Int)]]
   |  trying to reduce  test.FindField[T, K]
   |  trying to reduce  test.FindField0[T, K, (0 : Int)]
   |  failed since selector T
   |  does not match  case (K ->> f) *: _ => (f, (0 : Int))
   |  and cannot be shown to be disjoint from it either.
   |  Therefore, reduction cannot advance to the remaining case
   |
   |    case _ *: t => test.FindField0[t, K, scala.compiletime.ops.int.S[(0 : Int)]]
   |  trying to reduce  test.FindField0[T, K, (0 : Int)]
   |  failed since selector T
   |  does not match  case (K ->> f) *: _ => (f, (0 : Int))
   |  and cannot be shown to be disjoint from it either.
   |  Therefore, reduction cannot advance to the remaining case
   |
   |    case _ *: t => test.FindField0[t, K, scala.compiletime.ops.int.S[(0 : Int)]]
   |
   | longer explanation available when compiling with `-explain`
1 error found

[sjrd]

With the following single file (and a cast to Int for idx.value), I can reproduce:

package test {

  import types._

  object types {
    opaque type ->>[K, V] = V
    extension [K <: Singleton](k: K) def ->>[V](v: V): K ->> V = v.asInstanceOf[K ->> V]
  }

  type FindField[T <: Tuple, K] = FindField0[T, K, 0]

  type FindField0[T <: Tuple, K, I <: Int] <: (Any, Int) = T match {
    case (K ->> f) *: _ => (f, I)
    case _ *: t => FindField0[t, K, compiletime.ops.int.S[I]]
  }

  trait Selector[T, Key] {
    type Out
    def apply(t: T): Out
  }

  object Selector {
    type Aux[T, K, O] = Selector[T, K] { type Out = O }

    inline def apply[T, K](using s: Selector[T, K]): Aux[T, K, s.Out] = s

    inline given selectorInst[T <: Tuple, K](
      using idx: ValueOf[Tuple.Elem[FindField[T, K], 1]],
    ): Selector.Aux[T, K, Tuple.Head[FindField[T, K]]] =
      new Selector[T, K] {
        type Out = Tuple.Head[FindField[T, K]]
        def apply(t: T): Out =
          val i: Int = idx.value.asInstanceOf[Int]
          t.productElement(i).asInstanceOf[Out]
      }
  }

}

object Test {
  def main(args: Array[String]): Unit = {
    import test._
    import test.types._

    val t = ("s" ->> "foo") *: ("i" ->> 3) *: EmptyTuple
    val s = Selector[("s" ->> String) *: ("i" ->> Int) *: EmptyTuple, "i"]
    s(t)
  }
}

Note that I'm fairly convinced this will be declared won't-fix anyway, because type-matching on something that does not reduce to a class/trait applied to captures seems outside of what we can deterministically support. It will probably warn at definition site in the future.

[sjrd]

A version with less moving parts (no given, no Aux):

package test {

  import types._

  object types {
    opaque type ->>[K, V] = V
    extension [K <: Singleton](k: K) def ->>[V](v: V): K ->> V = v.asInstanceOf[K ->> V]
  }

  type FindField[T <: Tuple, K] = FindField0[T, K, 0]

  type FindField0[T <: Tuple, K, I <: Int] <: (Any, Int) = T match {
    case (K ->> f) *: _ => (f, I)
    case _ *: t => FindField0[t, K, compiletime.ops.int.S[I]]
  }

  trait Selector[T, Key, Out] {
    def apply(t: T): Out
  }

  object Selector {
    inline def selectorInst[T <: Tuple, K](
      using idx: ValueOf[Tuple.Elem[FindField[T, K], 1]],
    ): Selector[T, K, Tuple.Head[FindField[T, K]]] =
      new Selector[T, K, Tuple.Head[FindField[T, K]]] {
        def apply(t: T): Tuple.Head[FindField[T, K]] =
          val i: Int = idx.value.asInstanceOf[Int]
          t.productElement(i).asInstanceOf[Tuple.Head[FindField[T, K]]]
      }
  }

}

object Test {
  def main(args: Array[String]): Unit = {
    import test._
    import test.types._

    val t = ("s" ->> "foo") *: ("i" ->> 3) *: EmptyTuple
    val s = Selector.selectorInst[("s" ->> String) *: ("i" ->> Int) *: EmptyTuple, "i"]
    val r = s(t)
    println(r)
  }
}

After getters, we have:

        val s:
          
            test.Selector[(("s" : String) ->> String, ("i" : String) ->> Int),
              ("i" : String), Int]
          
         =
          {
            val idx$proxy1: ValueOf[(1 : Int)] = new ValueOf[(1 : Int)](1)
            {
              final class $anon() extends Object(), 
                test.Selector[
                  (("s" : String) ->> String, ("i" : String) ->> Int),
                  ("i" : String), Int]
               {
                def apply(t: (("s" : String) ->> String, ("i" : String) ->> Int)
                  ): Int = // NOTICE Int here
                  {
                    val i: Int = 1.asInstanceOf[Int]
                    t.productElement(i).asInstanceOf[Int]
                  }
              }
              new 
                Object with 
                  test.Selector[
                    (("s" : String) ->> String, ("i" : String) ->> Int),
                    ("i" : String),
                    Tuple.Head[
                      test.FindField[
                        (("s" : String) ->> String, ("i" : String) ->> Int),
                        ("i" : String)]
                    ]
                  ]
                 {...}
              ():
                
                  test.Selector[
                    (("s" : String) ->> String, ("i" : String) ->> Int),
                    ("i" : String), Int]
                
            }:
              
                test.Selector[
                  (("s" : String) ->> String, ("i" : String) ->> Int),
                  ("i" : String), Int]
              
          }

but after erasure we have

        val s: test.Selector =
          {
            val idx$proxy1: ErasedValueType(ValueOf, Integer) =
              ValueOf.u2evt(new ValueOf(Int.box(1)).value()).asInstanceOf[
                ErasedValueType(ValueOf, Integer)]
            {
              final class $anon() extends Object(), test.Selector {
                def apply(t: Product): String = // NOTICE String here
                  {
                    val i: Int = 1:Int
                    Int.box(Int.unbox(t.productElement(i):Object)).asInstanceOf[
                      String] // NOTICE cast to String here
                  }
                def apply(t: Object): Object =
                  this.apply(t.asInstanceOf[Product])
              }
              new Object with test.Selector {...}():test.Selector
            }:test.Selector
          }

It's kind of hilarious TBH. A very concrete Int in one phase becomes a String after erasure.

The problem goes away if selectorInt is not inline.

@nicolasstucki I have no idea whether this is more opaque type aliases, match types, or inlining-related. But perhaps you see something here?

[mrdziuban]

@sjrd thanks for taking a look at this!

The setup code does not compile for me on the latest main

I found this as well when I tested the latest nightly -- would you consider this a regression and should I open a different issue for it?

type-matching on something that does not reduce to a class/trait applied to captures seems outside of what we can deterministically support

I don't fully understand this, but I'm curious if you have any idea why the error goes away after adding & Tag[K]?

[sjrd]

The setup code does not compile for me on the latest main

I found this as well when I tested the latest nightly -- would you consider this a regression and should I open a different issue for it?

It might be a regression, yes. Definitely a different issue.

I don't fully understand this, but I'm curious if you have any idea why the error goes away after adding & Tag[K]?

Like I said ... we don't know how to make it deterministic when the type constructors used in a match types are not classes or traits. So ... it might be that non-determinism at play. 🤷‍♂️

[dwijnand]

This looks like match type simplification with or without Mode.Type. But I might be biased... #17937

[mrdziuban]

and a cast to Int for idx.value

Filed an issue for this at #18202

[sjrd]

The new match types of SIP-56 make the minimization not compile, instead of crashing at run-time:

-- [E172] Type Error: tests/neg/i17944.scala:40:87 ---------------------------------------------------------------------
40 |    val s = Selector.selectorInst[("s" ->> String) *: ("i" ->> Int) *: EmptyTuple, "i"] // error
   |                                                                                       ^
   |No singleton value available for Tuple.Elem[test.FindField[(("s" : String) ->> String, ("i" : String) ->> Int), ("i" : String)], (1 : Int)]; eligible singleton types for `ValueOf` synthesis include literals and stable paths.
   |
   |Note: a match type could not be fully reduced:
   |
   |  trying to reduce  Tuple.Elem[test.FindField[(("s" : String) ->> String, ("i" : String) ->> Int), ("i" : String)], (1 : Int)]
   |  trying to reduce  test.FindField[(("s" : String) ->> String, ("i" : String) ->> Int), ("i" : String)]
   |  trying to reduce  test.FindField0[(("s" : String) ->> String, ("i" : String) ->> Int), ("i" : String), (0 : Int)]
   |  failed since selector (("s" : String) ->> String, ("i" : String) ->> Int)
   |  does not match  case (("i" : String) ->> f) *: _ => (f, (0 : Int))
   |  and cannot be shown to be disjoint from it either.
   |  Therefore, reduction cannot advance to the remaining case
   |
   |    case _ *: t => test.FindField0[t, ("i" : String), scala.compiletime.ops.int.S[(0 : Int)]]

"s" ->> String cannot be shown disjoint from "i" ->> f. Both are opaque type aliases with public bounds >: Nothing <: Any, so that makes sense. And if we do see through the opaque type alias, it's worse since we then know them to reduce to String and f, which are not disjoint either.

[dwijnand]

"s" ->> String cannot be shown disjoint from "i" ->> f. Both are opaque type aliases with public bounds >: Nothing <: Any, so that makes sense. And if we do see through the opaque type alias, it's worse since we then know them to reduce to String and f, which are not disjoint either.

Interesting example. Because I see the intent as trying to use compile time to decide what product element index to dispatch to, but also holding onto what that element type is. But match types are heavily tied to match trees, which are all about runtime dispatching, using runtime behaviour. So while "s" is clearly disjoint from "i", that part (the "s" key) is phantom. So I think it's just match types not having the right semantics for the desired behaviour.