Dotty: Quoted Matching does not match overridden method calls

[deusaquilus]

Minimized code

Let's say we have a class and implementation:

trait Person:
  def name: String

case class PersonA(name: String) extends Person
case class PersonB(name: String) extends Person

In our macro, we intend to match any kind of Person.name invocation:

object MatchMac {
    inline def apply(inline any: Any): Unit = ${ printMacImpl('any) }
    def printMacImpl(any: Expr[Any])(implicit qctx: QuoteContext): Expr[Unit] = {
      import qctx.tasty._
      any match {
        case '{ ($f: Person).name } => println("matched!")
        case _ => println("not matched")
      }
      '{ () }
    }
}

Then we create an instance of Person and apply the macro:

MatchMac(PersonA("Joe").name)

Output

The macro will not match the statement:

MatchMac(PersonA("Joe").name)
// not matched

In fact, it will only match if it is directly casted first.

MatchMac(PersonA("Joe").asInstanceOf[Person].name)
// matched!

Expectation

It should match any instance of Person.

MatchMac(PersonA("Joe").name)
// matched!

While theoretically, it is possible to manually cast all instances down to the base type and this will indeed happen with type-hierarchies based on the new 'enum', this is not always possible with existing domain models. In order for quoted matching to be useful, there needs to be some way to make the mechanism match on the the sub-types of an object i.e. be covariant instead of invariant.

[deusaquilus]

Just as an important footnote, in Quill this issue is particularly salient because we have EntityQuery and just Query which have many of the same methods, but EntityQuery has methods for modification such as Entity.insert, Entity.update etc... For this reason, in some constructs, it is important to preserve the type of an entity as EntityQuery, otherwise doing write-operations on it will not be properly encoded in the API. Unfortunately, however, due to this issue, the pattern matching code for Query needs to be reproduced as EntityQuery which leads to an intractable amount of verbosity.

For example, normally we would encode a parse-block for Query.join as something like this:

queryExpression match {
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).join[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).leftJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).rightJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).fullJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
}

However, since Query[$t1] only matches a Query and not an EntityQuery, we need to have three more variations for every single join type. This turns into a monstrosity that looks like this:

queryExpression match {
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).join[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).leftJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).rightJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).fullJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...

    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).join[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).leftJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).rightJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).fullJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...

    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).join[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).leftJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).rightJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: Query[`$t1`]).fullJoin[`$t1`, `$t2`](($q2: EntityQuery[`$t2`])) } => ...

    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).join[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).leftJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).rightJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
    case '{ type $t1; type $t2; ($q1: EntityQuery[`$t1`]).fullJoin[`$t1`, `$t2`](($q2: Query[`$t2`])) } => ...
}

Essentially this means that in the vast majority of cases, we cannot use Quoted matching and have to fall back to matching on tasty trees directly (imagine what happens if we have even more sub-types of Query). That is definitely not the preferable solution!

[deusaquilus]

I even tried something like this. Hoping that the Expr[Person] from my unapply would satisfy the quoted matcher:

object MatchMac {
    inline def apply(inline any: Any): Unit = ${ printMacImpl('any) }
    def printMacImpl(any: Expr[Any])(implicit qctx: QuoteContext): Expr[Unit] = {
      import qctx.tasty._

      object PersonExpr {
        def unapply(expr: Expr[_]): Option[Expr[Person]] =
          if (expr.unseal.tpe <:< '[Person].unseal.tpe)
            Some(expr.asInstanceOf[Expr[Person]])
          else
            None
      }

      any match {
        case '{ (${PersonExpr(personExpr)}).name } => println("matched!")
        case _ => println("not matched!")
      }

      '{ () }
    }
}

Unfortunately it did not:

sbt:dotty-simple> compile
[info] Compiling 1 Scala source to /home/alexander/git/dotty/dotty_test_metals/target/scala-0.27/classes ...
[error] -- Error: /home/alexander/git/dotty/dotty_test_metals/src/main/scala/miniquill/parser/PrintMac.scala:26:29 
[error] 26 |        case '{ (${PersonExpr(personExpr)}).name } => println("matched!")
[error]    |                   ^^^^^^^^^^^^^^^^^^^^^^
[error]    |                 Type must be fully defined.
[error]    |                 Consider annotating the splice using a type ascription:
[error]    |                   (${PersonExpr(personExpr)}: XYZ).
[error] one error found
[error] (Compile / compileIncremental) Compilation failed
[error] Total time: 0 s, completed Nov 24, 2020 2:33:04 AM

[LPTK]

Quoted matching is actually covariant. You can check it for yourself with:

    def printMacImpl(any: Expr[Any])(implicit qctx: QuoteContext): Expr[Unit] = {
      import qctx.tasty._
      any match {
        case '{ Some($f: Person) } => println("matched!")
        case _ => println("not matched")
      }
      '{ () }
    }

MatchMac(Some(PersonA("Joe"))) // matched!

But your code _should_ match. I suspect the problem is that you are matching on the name symbol defined in Person, which is not the same as the subclass' name symbol, and the matcher does not equate the two symbols.

It's a problem I solved in Squid by using a union-find data structure of overriding/overridden symbols. I think it's sound to equate all symbols related by an overriding relationship, as long as the matcher also properly tests the types of matched expressions, as it should.

For more details and rationale, see: https://github.com/epfldata/squid/issues/51

[deusaquilus]

@LPTK So actual symbols are covariant but not when using overridden methods because the original method resolves against the original type as opposed to the overriding one? I think I get it, but that's really confusing and probably not in line with how a typical user would expect to use quoted matching.

I could change the title of the issue to something like "Overridden methods do not match for sub-types in Quoted Matching" if that makes more sense.

[LPTK]

I think it's not about typing or variance. It's just about allowing a method symbol m0 in a patterns to match a distinct method symbol m1 which happen to override m0 (so they should morally match). This needs confirmation by @nicolasstucki, though – I haven't had time to look into the symbol matching implementation.

[nicolasstucki]

I have not looked into it yet, but @LPTK is probably right. The issue is probably in the symbol == at Matcher.scala#L234 and Matcher.scala#L243.

[deusaquilus]

Yeah. That makes sense.

[deusaquilus]

I modified the name of the issue accordingly.

[nicolasstucki]

Fun detail, MatchMac(PersonA("Joe").name) is optimized to MatchMac("Joe") before we try to match on it.

We can reproduce the issue using

  val personA: PersonA = PersonA("JoeA")
  val personB: PersonB = PersonB("JoeB")
  val person: Person = personA
  MatchMac(personA.name) // currently fails
  MatchMac(personB.name) // currently fails
  MatchMac(person.name) // ok

[deusaquilus]

@nicolasstucki Yeah, I noticed that when down-casing EntityQuery[T] to Query[T] it started working.
Not sure I can do anything meaningful with that. Interesting though!

[nicolasstucki]

It should match without the upcasting.

[LPTK]

Note: I added a post-hoc review on the PR showing that the implementation is still incomplete. Having holes in the implementation will deliver bad user experience, similar to what @deusaquilus experienced.

[deusaquilus]

It's nice that at least it works for overridden classes. There are many new patterns that this fix makes possible e.g:

case Lambda1(_, '{ ($prop: Any).->[v](${ConstExpr(alias: String)}) } ) =>

In this case I don't know what the type of prop is and it really doesn't matter.
Thanks again @nicolasstucki for this fix!

[LPTK]

@deusaquilus I don't think the change does anything to your example. -> is an extension method, so it normally won't be overridden, unless I am missing something.

[deusaquilus]

@LPTK I’m fairly certain that this construct wasn’t working before but I could be wrong so I’ll double check.