More powerful implicit resolution in case matches

[adampauls]

Consider the following code (compiled with 3.1.0-RC2):

object Test {
  
  trait Foo[Self]

  case class Impl1(a: String)
  given Foo[Impl1] with {}
  case class Impl2(b: Int)
  given Foo[Impl2] with {}

  object Foo {
    class Type private (t: Any)

    object Type {
        def apply[T: Foo](t: T) = new Type(t)
        def unapply[T: Foo](t: Type): Option[T] = ???
    }
  }

  val x = Foo.Type(Impl1("x"))
  val matched: Option[Impl2] = Foo.Type.unapply(x) // compiles
  val matchedNoType = Foo.Type.unapply(x) // ambiguous implicit arguments (understandable)
  x match {
    case Foo.Type(_: Impl2) => ??? // ambiguous implicit arguments (could do better)
    case Foo.Type(Impl2(_)) => ??? // ambiguous implicit arguments (could do better)
  }
}

In the above, Foo.Type.unapply takes an implicit type parameter that only shows up on the output. When directly invoking unapply in a context where the expected type constrains the output type, everything works. However, in a case match where the output type of unapply is effectively constrained by a nested matcher, implicit resolution still fails.

I'm not sure if there is a good reason for this. In cases where the nested unapply and/or type ascription unambiguously specifies a type constraint, I think implicit resolution could be successful.

Of course there are ambiguous cases -- for example, if we have

case Foo.Type(SomeAmbiguousUnapply(_)) => ???

where SomeAmbiguousUnapply has both unapply(Impl1) and unapply(Impl2), there is insufficient information to constrain the implicit search and it's reasonable to fail in that case.

[adampauls]

On a related note: I am a little confused about the behavior of the auto-generated unapply method on case classes. Consider the following code (similar to the above, also on 3.1.0-RC2)

object Test {
  trait Foo[Self]
  class ExplicitClass(val a: String)
  object ExplicitClass {
    def unapply(i: ExplicitClass): Option[String] = Some(i.a)
  }
  given Foo[ExplicitClass] with {}
  case class CaseClass(val b: Int)
 
  given Foo[CaseClass] with {}
  object Foo {
    class Type private (t: Any)

    object Type {
      def apply[T: Foo](t: T) = new Type(t)
      def unapply[T: Foo](t: Type): Option[T] = ???
    }
  }

  val x = Foo.Type(ExplicitClass("x"))
  val matched: Option[CaseClass] = Foo.Type.unapply(x)
  val compiles = Foo.Type.unapply(x).flatMap(ExplicitClass.unapply _)
  val doesntCompile = Foo.Type.unapply(x).flatMap(CaseClass.unapply _) // ambiguous implicits
}

Looking at what I think is the code for for the auto-generated unapply, I see that the return type of the generated method is not an Option anymore in Scala 3. I'm surprised that it affects compilation here though. I'm not clear if this counts as a bug or not.

[som-snytt]

@adampauls https://docs.scala-lang.org/scala3/reference/changed-features/pattern-matching.html

note that normal usage of case classes for pattern cases is constructor pattern, not extractor pattern.

[adampauls]

@som-snytt thanks, I'm familiar with the new pattern matching facilities (though I don't understand all the implications). I don't understand why it would affect implicit resolution as it does in my second example. I think the only thing that should matter is the input to unapply, since that's what disambiguates in the example that does compile.

To double check: "constructor pattern" is what's called Product Match in the page you linked correct?

[som-snytt]

My eyes are tired at the moment, but I see what you mean now that I've read it through.

Since Foo.Type.unapply(x).map(CaseClass.unapply) works, you expect flatMap to give a better error by correctly inferring the type arg to Type.unapply albeit correctly failing to infer it for flatMap.

And for the first example, the test pattern should type check because the res expression does.

  val res: CaseClass = Foo.Type.unapply(x).get
  def test =
    x match
    case Foo.Type(CaseClass(_)) =>

Just from the form of the pattern, it can't know if it's a constructor or an extractor or which flavor of extraction.

An Option result must be type R with single match (isEmpty and get).

If it were a Product match, case P(x: A, y: B), then you'd have a series of P.unapply(x)._1: A to infer type args to unapply.

On terminology, constructor pattern case C(x) => for a case class is case c: C => val x = c.x, not an invocation of extractor C.unapply. The Scala 2 spec distinguishes https://scala-lang.org/files/archive/spec/2.13/08-pattern-matching.html#constructor-patterns But I also see the section on case classes does specify unapply. You're right to be surprised.

[adampauls]

you expect flatMap to give a better error by correctly inferring the type arg to Type.unapply albeit correctly failing to infer it for flatMap.

Not following what you mean here. Why should flatMap fail? It succeeds with the manually defined unapply?

Just from the form of the pattern, it can't know if it's a constructor or an extractor or which flavor of extraction.

Again, sorry, not following what you mean. At some point, the compiler must resolve whether to call unapply, apply a constructor pattern, or apply a type (if doing _: CaseClass). At that point, based on the expected input type of the inner pattern, you might have enough information to infer the implicits the call to Foo.Type.unapply. I had thought until now that all patterns were compiled down to calls to unapply and flatMap (along with isInstanceOf and asInstanceOf). My second code snippet was trying to explicitly write out what that desugaring would be, and indeed it does compile in some cases. That's why I thought it might not be so unreasonable to beef up implicit resolution inside pattern matches. It sounds like there's more going on that I realized, though it still doesn't seem unreasonable as a feature?

Is the issue that implicit resolution happens before the compiler resolves the compiler to one of the pattern matching options? That seems unlikely to me, but I'm out of my depth here.

[som-snytt]

flatMap fails because CaseClass.unapply no longer is x => Option[?], as you showed me.

The shape of the extraction is known from Type.unapply, but it wouldn't surprise me if inferring type args while type checking the pattern would depend on the kind of extractor.

For Product, if it's Product2 then Type.unapply(x).get: Product[X, Y] where some type params are constrained. But it doesn't have to be a ProductN, only a Product with members named _1 etc.

But I won't speculate. Not only am I out of my depth, I just read that nytimes piece about great white sharks: who knows what may be down there.

[adampauls]

Oh, derp, of course flatMap doesn't compile if there is no Option. Now I see what you mean by I might want a better error message.

In any case, I think the extra power in pattern matching is theoretically achievable but possibly very hard to implement. Could you by chance point me to the part of the code that performs type inference on pattern matches (or that compiles it to non-pattern matching code before type inference) so I could see for myself? I see this, but I'm not sure where implicit resolution happens or if the that link is the whole story

[adampauls]

It looks like the limiting code is here. This code doesn't even look at args while typing the call to unapply. I wouldn't know how to fix though. One heavy duty way to handle is to run type inference on args first and use that information to constraint the output type. For the more narrow case in the code above, one could special-case on single-argument matches with known types. What I don't know is whether getting a tighter type bound in this code will cause implicit resolution to do the right thing.