Regression in Scala 3.5.0-RC1 related to implicit search and match types that return type lambdas

[mrdziuban]

Compiler version

3.5.0-RC1, the issue is not present in 3.4.2

Minimized code

https://scastie.scala-lang.org/mrdziuban/lnO61Y1VSSy2xu5NuyAg8w

trait WrapperType[A]

case class Foo[A]()

case class Bar[A]()

type FooToBar[D[_]] = [A] =>> D[Unit] match {
  case Foo[Unit] => Bar[A]
}

case class Test()
object Test {
  implicit val wrapperType: WrapperType[Bar[Test]] = new WrapperType[Bar[Test]] {}
}

val test = summon[WrapperType[FooToBar[Foo][Test]]]

Output

16 |val test = summon[WrapperType[FooToBar[Foo][Test]]]
   |                                                   ^
   |No given instance of type WrapperType[FooToBar[Foo][Test]] was found for parameter x of method summon in object Predef
   |
   |The following import might fix the problem:
   |
   |  import Test.wrapperType
   |

Expectation

Test.wrapperType should satisfy the implicit search of the summon call.

Interestingly, if I change FooToBar to not return a type lambda, then everything compiles correctly, i.e.

type FooToBar[D[_], A] = D[Unit] match {
  case Foo[Unit] => Bar[A]
}
// ...
val test = summon[WrapperType[FooToBar[Foo, Test]]]

[mrdziuban]

A git bisect suggests that d421f88 (from #20147) is the culprit. /cc @EugeneFlesselle and @smarter in case you have any thoughts

[EugeneFlesselle]

The issue is fixed on #20268

Unfortunately, that PR now has issues with the named tuples, which happen to trigger the following problem with caching of super types:

scala3/compiler/src/dotty/tools/dotc/core/Types.scala

Lines 113 to 118 in c6fbe6f

	* FIXME: The semantics of this flag are broken by the existence of `TypeVar#resetInst`,
	* a non-provisional type could go back to being provisional after
	* a call to `resetInst`. This means all caches that rely on `isProvisional`
	* can likely end up returning stale results.
	*/
	def isProvisional(using Context): Boolean = mightBeProvisional && testProvisional

Really not sure what to do with that \cc @smarter

[smarter]

Hmm yeah I forgot about that, it seems we have to get rid of resetInst (which is only used in resetTo after a snapshot()). First we should check if using a nested TyperState instead of snapshot/resetTo fixes the issue you encounter, then we can see if that's good enough performance-wise or we need something more complicated.

[smarter]

Note that in theory at least resetInst shouldn't be needed during subtyping because of the check for subtypeCheckInProgress in

scala3/compiler/src/dotty/tools/dotc/core/Types.scala

Lines 5035 to 5036 in c6fbe6f

	if ((ctx.typerState eq owningState.nn.get.uncheckedNN) && !TypeComparer.subtypeCheckInProgress)
	setPermanentInst(tp)

, this flag could perhaps be generalized to always be set when calling snapshot() in a specific scope.

[EugeneFlesselle]

I may have blamed resetInst too hastily after seeing it was resetting some things post match type reduction. Either way there seems to be something wrong with the caching of super types of applied types as the problems disappear when disabling it.

[EugeneFlesselle]

this flag could perhaps be generalized to always be set when calling snapshot() in a specific scope

Or also during match type reduction specifically I suppose.