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?