Type inference bug in Scala 3.1.2

[alexandru]

I'm unsure if I'm reporting this issue in the right place.

Compiler version

3.1.2 — the issue does not happen in 3.0.x or in 3.1.1.

First bad commit db5956b in #13886

Minimized code

Noticed it while upgrading to 3.1.2 in monix/newtypes:

trait Eq[A] {
  def eqv(a1: A, a2: A): Boolean
}

given stringEq: Eq[String] with {
  def eqv(a1: String, a2: String) = a1 == a2
}

abstract class Newtype[Src] {
  opaque type Type = Src

  protected final def derive[F[_]](using ev: F[Src]): F[Type] = ev
}

object Sample extends Newtype[String] {
  given eq: Eq[Type] = derive
}

Output

[error] -- Error: .../Sample.scala:16:29
[error] 16 |  given eq: Eq[Type] = derive
[error]    |                             ^
[error]    |no implicit argument of type F[String] was found for parameter ev of method derive in class Newtype
[error]    |
[error]    |where:    F is a type variable with constraint <: Eq
[error] one error found

Expectation

The code should compile just fine, as it does with 3.1.1, 3.0.2, or 2.13.x.

[smarter]

@bishabosha assigned smarter 3 days ago

I won't be able to look at new issues for the next few months, so I recommend not assigning me, but feel free to re-assign me if a bisection points to one of my commits and no one else can figure it out.

[griggt]

Bisected to db5956b

[odersky]

This seems to be intentional. In the interest of not allowing compile-times to blow up, we do not perform implicit searches for uninstantiated top-level type variables.

[smarter]

While it's uninstantied it can be fully determined by its expected type, so it seems like we could allow it (also this restriction isn't communicated by the error message)

[odersky]

I am not sure what the criterion could be to allow it here. We have a type variable that's bounded by Eq, and that's OK. But if it was bounded by a wider type it might well lead to a search explosion. Where do we stop?

Also, note that there is a simple workaround:

given eq: Eq[Type] = derive[Eq]

[odersky]

I don't think I'll be able to work on this for the time being.

[alexandru]

👋 from my perspective as a user, if you say there are technical challenges that make this impractical, I believe you. It was surprising to me, as it used to work, and now it doesn't.

If this helps compile times, then that may be a useful trade-off.

But maybe you can improve the error message a little? I'm beginning to be spoiled by Scala 3's cool error message. IDK 🤷‍♂️

[smarter]

But if it was bounded by a wider type it might well lead to a search explosion. Where do we stop?

If I understand correctly, the current logic simply does no implicit search if the type passed to it is an uninstantiated type variable, but could we instead force the type variable to be instantiated (recursively, until isUnderspecified returns false) before doing the implicit search?

[odersky]

If I understand correctly, the current logic simply does no implicit search if the type passed to it is an uninstantiated type variable, but could we instead force the type variable to be instantiated (recursively, until isUnderspecified returns false) before doing the implicit search?

Maybe, but where? You can't very well do it during implicit search, the type variable might be in a nested subgoal and there might be another branch that succeeds. So the only viable scheme is to handle global search failure by looking at the variables and selectively instantiating some of them. Similarly to what we do in typedSelect. That could possibly work. It will be very tricky though to get all the info to the points where it is needed. Once could start improving the error message but even that looks hard.

[smarter]

In fact, shouldn't tvarsInParams already take care of selecting F for instantiation in our example?
https://github.com/lampepfl/dotty/blob/72352dc621282a4f9a51eed56e3326d7e80781de/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L325-L333
It looks like the implementation only looks for type variables in MethodTypes right now, but it seems like it could look in PolyTypes too.

[odersky]

It looks like the implementation only looks for type variables in MethodTypes right now, but it seems like it could look in PolyTypes too.

Not sure I understand. Type variables bound in polytypes are usually meant to be instantiated by the implicit search, no?