Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Overloading resolution incorrectly drops alternative with match type result when a target type is provided #21410

Open
smarter opened this issue Aug 21, 2024 · 1 comment · May be fixed by #21744

Comments

@smarter
Copy link
Member

smarter commented Aug 21, 2024

Compiler version

a2c53a1

Minimized code

(Minimized from the two map methods in https://github.com/aherlihy/tyql/blob/10401e8162f59543a6fe1b960d449f72c409612a/src/main/scala/repro/overloadedmap.scala that lead to q2 not compiling).

object Test:
  def foo[T](x: Option[T]): T = ???
  def foo[T <: Tuple](x: T): Tuple.Map[T, List] = ???

  val tup: (Int, String) = (1, "")

  val x = foo(tup)
  val y: (List[Int], List[String]) = x

  val x2: (List[Int], List[String]) = foo(tup) // error

Output

10 |  val x2: (List[Int], List[String]) = foo(tup)
   |                                          ^^^
   |                             Found:    (Test.tup : (Int, String))
   |                             Required: Option[(List[Int], List[String])]

Expectation

x2 should behave like x: overloading resolution should end up using the second overload since the first is clearly not appicable.

The overloading changes in #20054 do not have an impact on this issue (/cc @EugeneFlesselle).

@EugeneFlesselle
Copy link
Contributor

Minimized a bit further:

class A
type F[X] <: Any = X match
  case A => Int

def foo[T](x: String): T = ???
def foo[U](x: U): F[U] = ???

val x1 = foo(A())
val y: Int = x1

val x2: Int = foo(A()) // error

smarter added a commit to dotty-staging/dotty that referenced this issue Oct 9, 2024
… alt

If an overloaded alternative in `alts` does not end up being part of the
`candidate` list in `resolveOverloaded1`, then it is not applicable to the
current arguments and should not be considered by `adaptByResult`. This avoids
discarding working solutions in favor of invalid ones when the working solution
involves a match type in the method result type that will fail `resultConforms`.

Fixes scala#21410.
smarter added a commit to dotty-staging/dotty that referenced this issue Oct 9, 2024
`adaptByResult` was introduced in 2015 in
54835b6 as a last step in overloading
resolution:

> Take expected result type into account more often for overloading resolution
>
> Previously, the expected result type of a FunProto type was ignored and taken into
> account only in case of ambiguities. arrayclone-new.scala shows that this is not enough.
> In a case like
>
>     val x: Array[Byte] = Array(1, 2)
>
> we typed 1, 2 to be Int, so overloading resulution would give the Array.apply of
> type (Int, Int*)Array[Int]. But that's a dead end, since Array[Int] is not a subtype
> of Array[Byte].
>
> This commit proposes the following modified rule for overloading resulution:
>
>   A method alternative is applicable if ... (as before), and if its result type
>   is copmpatible with the expected type of the method application.
>
> The commit does not pre-select alternatives based on comparing with the expected
> result type. I tried that but it slowed down typechecking by a factor of at least 4.
> Instead, we proceed as usual, ignoring the result type except in case of
> ambiguities, but check whether the result of overloading resolution has a
> compatible result type. If that's not the case, we filter all alternatives
> for result type compatibility and try again.

In i21410.scala this means we end up checking:

    F[?U] <:< Int
    (where ?U is unconstrained, because the check is done without looking at the
    argument types)

The problem is that the subtype check returning false does not mean that there
is no instantiation of `?U` that would make this check return true, just that
type inference was not able to come up with one. This could happen for any
number of reason but commonly will happen with match types since inference
cannot do much with them.

We cannot avoid this by taking the argument types into account, because this
logic was added precisely to handle cases where the argument types mislead you
because adaptation isn't taken into account. Instead, we can approximate type
variables in the result type to trade false negatives for false positives which
should be less problematic here.

Fixes scala#21410.
smarter added a commit to smarter/dotty that referenced this issue Oct 10, 2024
`adaptByResult` was introduced in 2015 in
54835b6 as a last step in overloading
resolution:

> Take expected result type into account more often for overloading resolution
>
> Previously, the expected result type of a FunProto type was ignored and taken into
> account only in case of ambiguities. arrayclone-new.scala shows that this is not enough.
> In a case like
>
>     val x: Array[Byte] = Array(1, 2)
>
> we typed 1, 2 to be Int, so overloading resulution would give the Array.apply of
> type (Int, Int*)Array[Int]. But that's a dead end, since Array[Int] is not a subtype
> of Array[Byte].
>
> This commit proposes the following modified rule for overloading resulution:
>
>   A method alternative is applicable if ... (as before), and if its result type
>   is copmpatible with the expected type of the method application.
>
> The commit does not pre-select alternatives based on comparing with the expected
> result type. I tried that but it slowed down typechecking by a factor of at least 4.
> Instead, we proceed as usual, ignoring the result type except in case of
> ambiguities, but check whether the result of overloading resolution has a
> compatible result type. If that's not the case, we filter all alternatives
> for result type compatibility and try again.

In i21410.scala this means we end up checking:

    F[?U] <:< Int
    (where ?U is unconstrained, because the check is done without looking at the
    argument types)

The problem is that the subtype check returning false does not mean that there
is no instantiation of `?U` that would make this check return true, just that
type inference was not able to come up with one. This could happen for any
number of reason but commonly will happen with match types since inference
cannot do much with them.

We cannot avoid this by taking the argument types into account, because this
logic was added precisely to handle cases where the argument types mislead you
because adaptation isn't taken into account. Instead, we can approximate type
variables in the result type to trade false negatives for false positives which
should be less problematic here.

Fixes scala#21410.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment