Match type failure on opaque types prevents zero-cost abstractions in arbitrary tuples

[Ichoran]

Compiler version

3.6.4 (or 3.7-RC4)

Minimized example

Runnable example

object OpaqueScope:
  opaque type Opaque[A, B] = Unit
  trait Trait[A, B] {}

object OtherScope:
  import OpaqueScope.*

  type OpaqueLeft[Tp <: Tuple] = Tp match
    case EmptyTuple => Nothing
    case Opaque[l, _] *: _ => l
    case _ *: rest => OpaqueLeft[rest]

  type TraitLeft[Tp <: Tuple] = Tp match
    case EmptyTuple => Nothing
    case Trait[l, _] *: _ => l
    case _ *: rest => TraitLeft[rest]

  def leftO[Tp <: Tuple](x: OpaqueLeft[Tp]): Int = x.##
  def leftT[Tp <: Tuple](x: TraitLeft[Tp]): Int = x.##

  val traited = leftT[(Int, Trait[Char, Boolean], String)]('e')
  val opaqued = leftO[(Int, Opaque[Char, Boolean], String)]('e')

Output

Found:    ('e' : Char)
Required: Playground.OtherScope.OpaqueLeft[(Int,
  Playground.OpaqueScope.Opaque[Char, Boolean], String)]

Note: a match type could not be fully reduced:

  trying to reduce  Playground.OtherScope.OpaqueLeft[(Int,
  Playground.OpaqueScope.Opaque[Char, Boolean], String)]
  failed since selector (Int, Playground.OpaqueScope.Opaque[Char, Boolean], String)
  does not match  case Playground.OpaqueScope.Opaque[l, _] *: _ => l
  and cannot be shown to be disjoint from it either.
  Therefore, reduction cannot advance to the remaining case

    case _ *: rest => Playground.OtherScope.OpaqueLeft[rest]

Expectation

The compiler will treat type-level computations on types the same way, regardless of type, so it is irrelevant whether the type is opaque or not when doing a match type computation.

Alternatively, case Opaque[l, _] *: _ => ... will fail to compile. If it is intrinsically unmatchable, it should complain when you try to match on it and not leave you wondering why two things of the same shape behave differently.

Because opaque types are the primary mechanism for zero-cost abstraction in Scala, the former is strongly preferred.

[Ichoran]

Note that the reasoning in #21366 explains why it ended up in the state it is in, but not why it should be this way (which makes opaque types poison match types). For instance, you can use tuples in match types, but named tuples poison match types. If nobody ever uses match types, or nobody ever uses opaque types, this isn't a problem. But named tuples and IArray are now opaque types, so match types are in increasing danger:

scala> type Same[A, B, C] = A match
     |   case B => C
     |   case _ => A
     | 
                                                                                
scala> def check[A, B](x: Same[A, B, Boolean]): Unit = {}
def check[A, B](x: Same[A, B, Boolean]): Unit
                                                                                
scala> check[(Int, Int), (Int, Int)](true)
                                                                                
scala> check[(a: Int, b: Int), (a: Int, b: Int)](true)
                                                                                
scala> check[String, (a: Int, b: Int)]("oops")
-- [E007] Type Mismatch Error: -------------------------------------------------
1 |check[String, (a: Int, b: Int)]("oops")
  |                                ^^^^^^
  |             Found:    ("oops" : String)
  |             Required: Same[String, (a : Int, b : Int), Boolean]
  |
  |             Note: a match type could not be fully reduced:
  |
  |               trying to reduce  Same[String, (a : Int, b : Int), Boolean]
  |               failed since selector String
  |               does not match  case (a : Int, b : Int) => Boolean
  |               and cannot be shown to be disjoint from it either.
  |               Therefore, reduction cannot advance to the remaining case
  |
  |                 case _ => String
  |
  | longer explanation available when compiling with `-explain`
1 error found
                                                                                
scala> check[Int, Array[Int]](2)
                                                                                
scala> check[Int, IArray[Int]](3)
-- [E007] Type Mismatch Error: -------------------------------------------------
1 |check[Int, IArray[Int]](3)
  |                        ^
  |               Found:    (3 : Int)
  |               Required: Same[Int, IArray[Int], Boolean]
  |
  |               Note: a match type could not be fully reduced:
  |
  |                 trying to reduce  Same[Int, IArray[Int], Boolean]
  |                 failed since selector Int
  |                 does not match  case IArray[Int] => Boolean
  |                 and cannot be shown to be disjoint from it either.
  |                 Therefore, reduction cannot advance to the remaining case
  |
  |                   case _ => Int
  |
  | longer explanation available when compiling with `-explain`
1 error found

[Ichoran]

Note that most other places where types are supplied, the matching even of opaque types works as you would normally expect. For instance,

scala> object Opaques:
     |   opaque type I = Int
     |   opaque type J = Int
     | 
     |   val i: I = 1
     |   val j: J = 2
     | 
     | inline def kind(ij: Opaques.I | Opaques.J) = inline ij match
     |   case _: Opaques.I => "x-axis"
     |   case _: Opaques.J => "y-axis"
     | type Kind[X <: (Opaques.I | Opaques.J)] <: String = X match
     |   case Opaques.I => "x-axis"
     |   case Opaques.J => "y-axis"
     | inline def kind2[X <: (Opaques.I | Opaques.J)](ij: X): String =
     |   compiletime.constValue[Kind[X]]
     | 
// defined object Opaques
def kind(ij: Opaques.I | Opaques.J): String
def kind2[X <: Opaques.I | Opaques.J](ij: X): String
                                                                                
scala> kind(Opaques.i)
val res1: String = x-axis
                                                                                
scala> kind2(Opaques.j)
-- [E182] Type Error: ----------------------------------------------------------
 1 |kind2(Opaques.j)
   |^^^^^^^^^^^^^^^^
   |Kind[Opaques.J] is not a constant type; cannot take constValue
   |
   |Note: a match type could not be fully reduced:
   |
   |  trying to reduce  Kind[Opaques.J]
   |  failed since selector Opaques.J
   |  does not match  case Opaques.I => ("x-axis" : String)
   |  and cannot be shown to be disjoint from it either.
   |  Therefore, reduction cannot advance to the remaining case
   |
   |    case Opaques.J => ("y-axis" : String)
   |----------------------------------------------------------------------------
   |Inline stack trace
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   |This location contains code that was inlined from rs$line$25:15
15 |  compiletime.constValue[Kind[X]]
   |                         ^^^^^^^
    ----------------------------------------------------------------------------
1 error found

Here, we have two computations, producing identical results, apparently being computed entirely from type information at compiletime, and yet one works and the other fails. It would seem that there should at least be a workaround so that one could talk about the type that the inline computation produces, if it is necessary that match types by default obey strict disjunction at each step including when opaque types are involved. (I understand why that might be necessary when dealing with type parameters--you might resolve to a fallthrough case when "I don't know the reality of the situation" is the correct answer. But the point with opaque types is that you are never allowed to know so "I don't know the reality" isn't a useful observation. "I know as much as I ever possibly could" is the best one can hope for.)

[bishabosha]

Why use opaque types at all when they seem to be a phantom erased type here, is this based on an example somewhere where you actually use them as a data type?

[Ichoran]

@bishabosha The case where I ran into this most acutely (this isn't the only time, though) is where I was trying to use opaque types to add names to individual items and then was trying to unify this with named tuples. (For safety, it is very important that the named type be a newtype--the entire point is to use it when it is a critical error to mess things up. Kind of like units of measurement.)

But I would also run into this if I were trying to flatten named tuples where not all entries were there own named tuples, because the match type would need to match on a tuple entry being a named tuple. E.g. (a = "eel", b = (x = 2, y = true)) can't be flattened to (a = "eel", x = 2, y = true) because you can't write the match type that would express this concept.

And I would also run into this if I were trying to do something as simple as extract the element type from Array vs IArray as one of the cases.

scala> type Etype[A] = A match
     |   case Array[b] => b
     |   case _ => A
     | 
                                                                                
scala> val x: Etype[Array[Int]] = 3
val x: Int = 3
                                                                                
scala> val x: Etype[String] = 3
-- [E007] Type Mismatch Error: -------------------------------------------------
1 |val x: Etype[String] = 3
  |                       ^
  |                       Found:    (3 : Int)
  |                       Required: String
  |
  | longer explanation available when compiling with `-explain`
1 error found
                                                                                
scala> type Etype[A] = A match
     |   case IArray[b] => b
     |   case _ => A
     | 
                                                                                
scala> val x: Etype[IArray[Int]] = 3
val x: Int = 3
                                                                                
scala> val x: Etype[String] = 3
-- [E007] Type Mismatch Error: -------------------------------------------------
1 |val x: Etype[String] = 3
  |                       ^
  |               Found:    (3 : Int)
  |               Required: Etype[String]
  |
  |               Note: a match type could not be fully reduced:
  |
  |                 trying to reduce  Etype[String]
  |                 failed since selector String
  |                 does not match  case IArray[b] => b
  |                 and cannot be shown to be disjoint from it either.
  |                 Therefore, reduction cannot advance to the remaining case
  |
  |                   case _ => String
  |
  | longer explanation available when compiling with `-explain`
1 error found

[bishabosha]

@Ichoran i know it's not a solution with match types but have you tried using a macro to compute the type instead, and store it in a type member refinement? i.e. you use implicit search to fetch the result.

[Ichoran]

@bishabosha - No, I haven't tried that. I assume that practically anything can be done with macros given enough effort. I try to use the simplest language features that will accomplish the goal, which match types would be if they weren't poisoned by opaque types.

Maybe a Known[] type would be enough, where it matches if it does, and always proceeds (because it is disjoint with being known) if not, would be enough.

But I really doubt this is the right solution conceptually. If someone is trying to match a 2-tuple out in a match type, why would they want it to fail if someone throws an opaque type in?

Edit: I have one answer to my own question, which is if someone is trying to use reflective matching, sans type information, at the same time as using a match type, which contains type information, hoping that the two will line up. One of the ways this can go wrong is if they isInstanceOf a Tuple2 but it is typed as an opaque type. Then, indeed, the two will fail to align. But this is fragile anyway. So having some approach that faithfully follows the types with instances is desirable anyway, at which point there isn't any reason to discriminate against opaque types.

[bishabosha]

I'd recommend someone show some love to my PR #22431 if they can convince @sjrd it can't be fooled

[Katrix]

I just want to echo the sentiment here. I have become increasingly wary of exposing any types using match types in my libraries, as I have myself experienced that opaque types just poison them and make them useless. Personally I have been thinking of maybe returning to the Scala 2 way of doing opaque types, as those are AFAIK more immune to these issues.

[sjrd]

From a public API point of view, opaque type aliases are abstract type members, possibly with bounds. They will behave as abstract type members. Match types have to consider them not-provably-disjoint, otherwise it breaks narrowing, a very important property of type systems.

Note that the semantics of match types are meant to be sound with respect to term-level match constructs. NOT inline match constructs. inline match has different semantics.

So yes: don't use opaque type aliases in match types. In fact, in the same way that you should only use match with sealed type hierarchies of testable cases, your match types should only use sealed, provably-disjoint cases. And opaque types are not provably disjoint from their public upper bound.

[Katrix]

So yes: don't use opaque type aliases in match types. In fact, in the same way that you should only use match with sealed type hierarchies of testable cases, your match types should only use sealed, provably-disjoint cases. And opaque types are not provably disjoint from their public upper bound.

If that's the case, would it then maybe be worth it to at least add a warning on, if not deprecate match types in the standard library that break this rule? Only examples I can think of currently are Tuple.Contains and Tuple.Disjoint, but there might be others.