Regressions in fingo/spata for match types

[WojciechMazur]

The last good compiler version 3.4.2-RC1-bin-20240229-9fe0111-NIGHTLY
There are 2 issues related to the same reproducer

Reproducer

import scala.deriving.Mirror
import scala.annotation.unused
import scala.compiletime.{constValue, erasedValue, *}

type Key = String & Singleton

trait StringParser[+A]

private inline def getLabels[T <: Tuple]: List[String] = inline erasedValue[T] match
  case _: EmptyTuple => Nil
  case _: (t *: ts) => constValue[t].toString :: getLabels[ts]

private inline def getTypes[T <: Tuple]: List[StringParser[?]] = inline erasedValue[T] match
  case _: EmptyTuple => Nil
  case _: (t *: ts) => summonInline[StringParser[t]] :: getTypes[ts]

import TypedRecord.*
final class TypedRecord[KS <: Tuple, VS <: Tuple](
  keys: KS,
  values: VS,
)(using @unused ev1: Tuple.Size[KS] =:= Tuple.Size[VS], @unused ev2: Tuple.Union[KS] <:< Key):

  inline def to[P <: Product](using
    m: Mirror.ProductOf[P],
    ev: Tuple.Union[Tuple.Zip[m.MirroredElemLabels, m.MirroredElemTypes]] <:< Tuple.Union[Tuple.Zip[KS, VS]]
  ): P =
    val labels = getLabels[m.MirroredElemLabels]
    val vals = labels.map(l => get(l, keys, values)) // error: issue 2
    m.fromProduct(Tuple.fromArray(vals.toArray)) // error: issue 1

  private def get[K <: Key, KS <: Tuple, VS <: Tuple](key: K, keys: KS, values: VS): Select[K, KS, VS] =
    val selected = (keys: @unchecked) match
      case `key` *: _ => getH(values)
      case _ *: tk => getT(key, tk, values)
    selected.asInstanceOf[Select[K, KS, VS]]

  private def getT[K <: Key, KS <: Tuple, VS <: Tuple](key: K, keys: KS, values: VS): SelectT[K, KS, VS] =
    (values: @unchecked) match
      case vs: (h *: t) => get(key, keys, vs.tail[h *: t])

  private def getH[VS <: Tuple](values: VS): SelectH[VS] =
    (values: @unchecked) match
      case vs: *:[h, t] => vs.head[h *: t]

object TypedRecord:
  type Select[K <: Key, KS <: Tuple, VS <: Tuple] = KS match
    case K *: ? => SelectH[VS]
    case h *: t => SelectT[K, t, VS]

  type SelectT[K <: Key, KS <: Tuple, VS <: Tuple] = VS match
    case ? *: tv => Select[K, KS, tv]

  type SelectH[VS <: Tuple] = VS match
    case h *: ? => h

Outputs

Issue 1

[error] -- [E172] Type Error: /Users/wmazur/projects/community-build3/repo/src/main/scala/info/fingo/spata/schema/TypedRecord.scala:93:46 
[error] 93 |    m.fromProduct(Tuple.fromArray(vals.toArray))
[error]    |                                              ^
[error]    |No ClassTag available for T
[error]    |
[error]    |where:    T is a type variable with constraint >: info.fingo.spata.schema.TypedRecord.SelectH[VS] | info.fingo.spata.schema.TypedRecord.SelectT[String, t, VS]

Introduced in #19761 and described in #20972 (comment)
Before that change, the toArray was inferred to be toArray[Any] which even though it allowed for compilation it was probably incorrect, but I'd like to request confirmation.

Issue 2

After using explicit `toArray[Any] to mitigate issue 1 in some later versions of compiler
Last good release: 3.4.2-RC1-bin-20240302-c7a0459-NIGHTLY
First bad release: 3.4.2-RC1-bin-20240305-beba585-NIGHTLY
No exact bisect result due to issues with the compiler builds

-- [E057] Type Mismatch Error: /Users/wmazur/projects/dotty/bisect/test.scala:28:12 
28 |    val vals = labels.map(l => get(l, keys, values))
   |            ^
   |Type argument String does not conform to upper bound Key in subpart TypedRecord.SelectT[String, t, VS] of inferred type List[TypedRecord.SelectH[VS] | TypedRecord.SelectT[String, t, VS]]

or with later versions

-- [E007] Type Mismatch Error: /Users/wmazur/projects/dotty/bisect/test.scala:28:34 
28 |    val vals = labels.map(l => get(l, keys, values))
   |                               ^^^^^^^^^^^^^^^^^^^^
   |     Found:    TypedRecord.Select[(l : String), KS, VS]
   |     Required: KS match {
   |       case ? <: String *: _ => TypedRecord.SelectH[VS]
   |       case h *: t => TypedRecord.SelectT[String, t, VS]
   |     } <: TypedRecord.SelectH[VS] | TypedRecord.SelectT[String, t², VS]
   |
   |     where:    KS is a type in class TypedRecord with bounds <: Tuple
   |               VS is a type in class TypedRecord with bounds <: Tuple
   |               t  is a type variable with constraint <: Tuple
   |               t² is a type in type Select with bounds <: Tuple
   |
   |
   |     Note: a match type could not be fully reduced:
   |
   |       trying to reduce  TypedRecord.Select[(l : String), KS, VS]
   |       failed since selector KS
   |       does not match  case (l : String) *: _ => TypedRecord.SelectH[VS]
   |       and cannot be shown to be disjoint from it either.
   |       Therefore, reduction cannot advance to the remaining case
   |
   |         case h *: t => TypedRecord.SelectT[(l : String), t, VS]
   |

[EugeneFlesselle]

Minimization:

type Select[K <: String] = Tuple match
  case K *: _ => Int

def Test: Unit =
  val labels: List[String] = ???

  val vals = labels.map: l =>
    ??? : Select[l.type] // error: Required: Tuple match { case ? <: String *: _ => Int } <: Int

  Tuple.fromArray(vals.toArray) // error: No ClassTag available for T

[EugeneFlesselle]

The issue comes down to applications of higher kinded types to wildcard arguments:

type M1[K] = Double match
  case K => Int

type M2[K] = Double match
  case Option[K] => Int

def Test =
  // Issue A: `M1[Int] <:< M1[?]` fails
  val x1: M1[?] = ??? // application to `?` is accepted
  val x2: M1[Int] = x1 // error

  // Issue B: `M2[?]` reported as unreducible but accepted when manually inlined
  type R2 = M2[?] // error: unreducible application to wildcard arguments
  type R1 = Int match
    case Option[?] => Int // ok

  // Original issue
  def foo[B](f: String => B): Unit = ???
  foo: l =>
    ??? : M1[l.type] // ok
    ??? : M2[l.type] // error:
    // gets widened to the inlining of M2[?] for the inferred B,
    // issue B is somehow avoided, but then runs into issue A

[sjrd]

IMO this is the actual issue:

  val x1: M1[?] = ??? // application to `?` is accepted

I don't think this should be accepted. The expansion is not valid:

scala> type M1[K] = Double match { case K => Int }
                                                                                                    
scala> type M2 = Double match { case ? => Int }
-- [E035] Syntax Error: --------------------------------------------------------
1 |type M2 = Double match { case ? => Int }
  |                              ^
  |                              Unbound wildcard type
  |
  | longer explanation available when compiling with `-explain`
                                                                                                    
scala> type M3 = M1[?]

clearly is not consistent.

[EugeneFlesselle]

I don't think this should be accepted. The expansion is not valid

Agreed.

But R2, and hence M2[?], should be legal, right ?

Although perhaps a separate issue, I still think avoidance yielding the expansion of M2[?] from M2[l.type], despite the invariance of match types, is suspicious.

[sjrd]

But R2, and hence M2[?], should be legal, right ?

Unclear. In fact it's unclear that substituting a ? for a type parameter inside a match type pattern is valid at all. That's irrespective of whether the result is a valid pattern. I'm talking about the substitution itself. The same distinction exists without match types, for example:

type T = (?, ?) // valid
type U[X] = (X, X) // valid
type V = U[?] // invalid!

Analogously, it's possible--and I'd say likely--that the following should hold as well:

type T = Double match { case Option[?] => Int } // valid
type U[X] = Double match { case Option[X] => Int } // valid
type V = U[?] // invalid!

Although perhaps a separate issue, I still think avoidance yielding the expansion of M2[?] from M2[l.type], despite the invariance of match types, is suspicious.

Assuming M2[?] is valid per se, then the above avoidance is definitely fine. It's the same with invariant class types: you can type-avoid Array[x.type] into Array[?] despite Array being invariant (but not Array[String]! for that you need covariance).

[EugeneFlesselle]

In fact it's unclear that substituting a ? for a type parameter inside a match type pattern is valid at all.

Not arguing against this or anything, but this is all still admittedly a bit unclear to me.
Do you know if/where substitution is specified ?

In the non match type example, the explanation of the error msg states:

-- [E043] Type Error: tests/playground/example.scala:3:9 -----------------------
3 |type V = U[?] // invalid!
  |         ^^^^
  |unreducible application of higher-kinded type [X] =>> (X, X) to wildcard arguments
  |-----------------------------------------------------------------------------
  | Explanation (enabled by `-explain`)
  |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  | An abstract type constructor cannot be applied to wildcard arguments.
  | Such applications are equivalent to existential types, which are not
  | supported in Scala 3.
   -----------------------------------------------------------------------------

but U is not an abstract tycon right ? Is the message incorrect, and if so is the error also incorrect ?

Assuming M2[?] is valid per se, then the above avoidance is definitely fine.

For clarity, you mean avoiding M2[l.type] to M2[?], not to Double match case Option[?] => Int ? The latter being the one we get for now (although a bit unclear from the comment of my minimization).

It's the same with invariant class types: you can type-avoid Array[x.type] into Array[?] despite Array being invariant

Good point! A follow up question would be, we always expect avoidance to yield a type to which the original one conforms?

[sjrd]

but U is not an abstract tycon right ? Is the message incorrect, and if so is the error also incorrect ?

Looks like the message incorrect. It should say "non-class type constructor" instead of "abstract type constructor". The message was probably written like that because we allow concrete type constructors that are eta-expansions of classes, but spec-wise we basically consider those as class types.

Assuming M2[?] is valid per se, then the above avoidance is definitely fine.

For clarity, you mean avoiding M2[l.type] to M2[?], not to Double match case Option[?] => Int ? The latter being the one we get for now (although a bit unclear from the comment of my minimization).

Yes, I mean to M2[?].

A follow up question would be, we always expect avoidance to yield a type to which the original one conforms?

Yes, that is a strong requirement. Type avoidance must abide by this rule.

---

In fact I become increasingly skeptical of the exemption for match aliases in isUnreducibleWild:

scala3/compiler/src/dotty/tools/dotc/core/Types.scala

Lines 4609 to 4617 in 2ea90c6

	/** Is this an unreducible application to wildcard arguments?
	* This is the case if tycon is higher-kinded. This means
	* it is a subtype of a hk-lambda, but not a match alias.
	* (normal parameterized aliases are removed in `appliedTo`).
	* Applications of higher-kinded type constructors to wildcard arguments
	* are equivalent to existential types, which are not supported.
	*/
	def isUnreducibleWild(using Context): Boolean =
	tycon.isLambdaSub && hasWildcardArg && !isMatchAlias

There could be a (X, X) even in a case body. Substituting ? for X in such a case is definitely unsound.

[sjrd]

Looks like the exemption was added in 6871cff by @odersky. Quoting from the commit message:

If M[_] is a match type alias, it was rejected for being an unreducible
application of wildcard types. It is now accepted. I believe that is sound
-- this is siply an unreducible match type. The situation is not the same
as F[_] where F is an abstract type that can be refined in several ways
in subclasses.

Well ... I believe it's unsound, actually.

[odersky]

I think the idea behind 6871cff was that a match type alias where the scrutinee was a wildcard is simply an unreducible match type, which should be sound. But I overlooked the case where the wildcard appears in the patterns, that is indeed unsound. Can we refine the restriction to reject this?

[sjrd]

It's more than just the patterns, though. If you have

type F[X, Y] = X match { case Int => (Y, Y) }

and you now apply F[Int, ?], you basically get the prototypical unsound substitution of ? for Y in (Y, Y).

In general, a match type can hide an arbitrary type computation that substitutes its type parameters in arbitrary places, including ones where ? is invalid.

[odersky]

Right. So the only case where the application is sound is if the type variable appears only in the scrutinee. We'd have to go back to the original motivation for introducing this change in 6871cff to decide whether this exemption is still worthwhile, or we should outlaw wildcards also in match aliases.

[odersky]

Going back to #9999 it seems there was a strong community demand to allow wildcard in match aliases so I believe we need to work hard not to overshoot in the revert or there will be backlash.