No workaround to dependent-type match types after SIP-56

[WojciechMazur]

Based on the problem found in akka/akka and apache/pekko

In the snippet we can come up with workaround to TypedMultiMap.get by using transparent inline however there seems to be no workaround for the TypedMultiMap.inserted method.

Compiler version

All Scala 3.4+ versions

Minimized code

abstract class AbstractServiceKey:
  type Protocol

abstract class ServiceKey[T] extends AbstractServiceKey:
  type Protocol = T

type Aux[P] = AbstractServiceKey { type Protocol = P }
type Service[K <: Aux[?]] = K match
  case Aux[t] => ActorRef[t]
type Subscriber[K <: Aux[?]] = K match
  case Aux[t] => ActorRef[ReceptionistMessages.Listing[t]]

trait ActorRef[-T]

object ReceptionistMessages:
  final case class Listing[T](key: ServiceKey[T])

class TypedMultiMap[T <: AnyRef, K[_ <: T]]:
  def get(key: T): Set[K[key.type]] = ???
  transparent inline def getInlined(key: T): Set[K[key.type]] = ???
  inline def inserted(key: T, value: K[key.type]): TypedMultiMap[T, K] = ???

object LocalReceptionist {
  final case class State(
      services: TypedMultiMap[AbstractServiceKey, Service],
      subscriptions: TypedMultiMap[AbstractServiceKey, Subscriber]
  ):
    def testInsert(key: AbstractServiceKey)(serviceInstance: ActorRef[key.Protocol]): State = {
      val fails = services.inserted(key, serviceInstance) // error
      ???
    }

  def testGet[T](key: AbstractServiceKey): Unit = {
    val newState: State = ???
    val fails: Set[ActorRef[key.Protocol]] = newState.services.get(key) // error
    val works: Set[ActorRef[key.Protocol]] = newState.services.getInlined(key) // workaround

    val fails2: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]] = newState.subscriptions.get(key) // error
    val works2: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]] = newState.subscriptions.getInlined(key) // workaround
  }
}

Output

[error] ./test.scala:29:42
[error] Found:    (serviceInstance : ActorRef[key.Protocol])
[error] Required: Service[(key : AbstractServiceKey)]
[error] 
[error] Note: a match type could not be fully reduced:
[error] 
[error]   trying to reduce  Service[(key : AbstractServiceKey)]
[error]   failed since selector (key : AbstractServiceKey)
[error]   does not uniquely determine parameter t in
[error]     case Aux[t] => ActorRef[t]
[error]   The computed bounds for the parameter are:
[error]     t
[error]       val fails = services.inserted(key, serviceInstance) // error
[error]                                          ^^^^^^^^^^^^^^^
[error] ./test.scala:35:46
[error] Found:    Set[Service[(key : AbstractServiceKey)]]
[error] Required: Set[ActorRef[key.Protocol]]
[error] 
[error] Note: a match type could not be fully reduced:
[error] 
[error]   trying to reduce  Service[(key : AbstractServiceKey)]
[error]   failed since selector (key : AbstractServiceKey)
[error]   does not uniquely determine parameter t in
[error]     case Aux[t] => ActorRef[t]
[error]   The computed bounds for the parameter are:
[error]     t
[error]     val fails: Set[ActorRef[key.Protocol]] = newState.services.get(key) // error
[error]                                              ^^^^^^^^^^^^^^^^^^^^^^^^^^
[error] ./test.scala:38:77
[error] Found:    Set[Subscriber[(key : AbstractServiceKey)]]
[error] Required: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]]
[error] 
[error] Note: a match type could not be fully reduced:
[error] 
[error]   trying to reduce  Subscriber[(key : AbstractServiceKey)]
[error]   failed since selector (key : AbstractServiceKey)
[error]   does not uniquely determine parameter t in
[error]     case Aux[t] => ActorRef[ReceptionistMessages.Listing[t]]
[error]   The computed bounds for the parameter are:
[error]     t
[error]     val fails2: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]] = newState.subscriptions.get(key) // error
[error]                                         

Expectation

This kind of issues might pop-up more often as projects would migrate to Scala 3.4+. It would be great if we could propose some workarounds that would allow for their compilation..

[sjrd]

Isn't there a way to work around using a cast, at least?

[SethTisue]

fyi @patriknw

[dwijnand]

In the snippet we can come up with workaround to TypedMultiMap.get by using transparent inline however there seems to be no workaround for the TypedMultiMap.inserted method.

Btw, the only reason your getInlined works is because ???, being of type Nothing, conforms to Set[ActorRef[key.Protocol]]. But if you use the original, whose RHS is typed as Set[K[key.type]], then you get the same type mismatch error

    val works2: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]] = newState.subscriptions.getInlined(key) // workaround
                                                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     Found:    Set[Subscriber[(key : AbstractServiceKey)]]
     Required: Set[ActorRef[ReceptionistMessages.Listing[key.Protocol]]]

The problem is these are type projections, reimplemented with match types. We have the same problem captured in tests/pos/i15155.scala, which is trying to reimplement Enumeration#Value using a match type aliased as EnumValue. So, another workaround is:

import scala.language.`3.3`

[smarter]

The fundamental abstraction we're missing here is lambdas from terms to types:

class TypedMultiMap[T <: AnyRef, K <: (x: T) =>> Any]:
  def get(key: T): Set[K(key)] = ???
  transparent inline def getInlined(key: T): Set[K(key)] = ???
  inline def inserted(key: T, value: K(key)): TypedMultiMap[T, K] = ???

object LocalReceptionist {
  final case class State(
      services: TypedMultiMap[AbstractServiceKey, x =>> ActorRef[x.Protocol]],
      subscriptions: TypedMultiMap[AbstractServiceKey, x =>> ActorRef[ReceptionistMessages.Listing[x.Protocol]]
  )

I don't think there's a way to encode this currently ([k <: AbstractServiceKey & Singleton] =>> ActorRef[k#Protocol]] doesn't help because a subtype of Singleton is not necessarily a singleton type)

[dwijnand]

How about with the new -language:experimental.modularity and : Singleton context bound?

[smarter]

The context bound itself is a term parameter, for Singleton in particular it's an erased term parameter, but we still have the same issue about not being able to go from a term to a type

[dwijnand]

@sjrd I'm looking at the spec (https://github.com/scala/improvement-proposals/pull/65/files), in lines 280-289:

  * If `T` is a refined type of the form `Base { type Y = ti }`:
    * Let `q` be `X` if `X` is a stable type, or the skolem type `∃α:X` otherwise.
    * If `q` does not have a type member `Y`, fail as not matching (that implies that `X <:< Base` is false, because `Base` must have a type member `Y` for the pattern to be legal).
    * If `q.Y` is abstract, fail as not specific.
    * If `q.Y` is a class member:
      * If `q` is a skolem type `∃α:X`, fail as not specific.
      * Otherwise, compute `matchPattern(ti, q.Y, 0, scrutIsWidenedAbstract)`.
    * Otherwise, the underlying type definition of `q.Y` is of the form `= U`:
      * If `q` is a skolem type `∃α:X` and `U` refers to `α`, fail as not specific.
      * Otherwise, compute `matchPattern(ti, U, 0, scrutIsWidenedAbstract)`.

The failures in the example are all Service[(key : AbstractServiceKey)] and Subscriber[(key : AbstractServiceKey)] which fall into line 283 "If q.Y is abstract". But the next two branches (L284 & L290) take into account whether the scrutinee type X is stable or not (via whether q is a skolem). Why don't we also that that into consideration in our branch? That keeps Service[AbstractServiceKey] as failing and makes Service[(key : AbstractServiceKey)] equivalent to ActorRef[key.Protocol]. This would allow TypedMultiMap to be defined with an abstract function from key type to value type, and it could be successfully used with a member type extracting MT as long as we provide it with stable key types as input.

[sjrd]

Yes, I think I thought about that as well when I initially looked at the Pekko issue a while ago. AFAICT it should be sound, but it requires a new round of amending that SIP.