Possible regression in typer or implicits resolution

[WojciechMazur]

Compiler version

3.1.2
Works in 3.1.1
Fails in 3.2.0-RC1-bin-20220512-9dbe2d3-NIGHTLY

First bad commit 3ab18a9

Minimized code

Based on https://github.com/eed3si9n/sjson-new/blob/3c8e15b504145de07b9a46a87a21b85fbdd97c53/support/scalajson/src/test/scala/sjsonnew/support/scalajson/unsafe/LListFormatSpec.scala#L11-L16

Might need further minimization

//> using scala "3.1.2"
// //> using scala "3.1.1" // Last working stable version

def test() = {
  given JsonFormat[LCons[Seq[String], LNil]] = ???
  case class Foo(xs: Seq[String])
  implicit val isoLList: IsoLList[Foo] = LList.isoCurried((a: Foo) => "xs" -> a.xs :*: LNil ){ 
    case (_, xs) :*: LNil => Foo(xs) 
  }
}

trait JsonFormat[T]
object JsonFormat{
  import collection.{immutable => imm}
  implicit def immSeqFormat[T :JsonFormat]: JsonFormat[imm.Seq[T]]  = ???

  import collection._
  implicit def iterableFormat[T :JsonFormat]: JsonFormat[Iterable[T]]   = ??? 

  given JsonFormat[String] = ???
}

sealed trait LList
object LList{
  val LNil0: LNil0 = new LNil0 {}
  sealed trait LNil0 extends LList {
    def :*:[A1: JsonFormat](labelled: (String, A1)): LCons[A1, LNil] = ???
  }
  def isoCurried[A, R0 <: LList: JsonFormat](to0: A => R0)(from0: R0 => A): IsoLList.Aux[A, R0] = ???
}
type LNil = LList.LNil0
val LNil = LList.LNil0

final class LCons[A1: JsonFormat, A2 <: LList: JsonFormat] extends LList
type :*:[A1, A2 <: LList] = LCons[A1, A2]
object :*: {
  def unapply[H, T <: LList](x: H :*: T): Some[((String, H), T)] = ???
}

trait IsoLList[A]
object IsoLList {
  type Aux[A, R0] = IsoLList[A]{ type R = R0 }
}

Output

[error] ./test.scala:40:92: ambiguous implicit arguments: both method immSeqFormat in object JsonFormat and method iterableFormat in object JsonFormat match type JsonFormat[(avoid)A1] of an implicit parameter of method :*: in trait LNil0
[error]   implicit val isoLList: IsoLList[Foo] = LList.isoCurried((a: Foo) => "xs" -> a.xs :*: LNil ){ 
[error]                                                                                            ^
Error compiling project (Scala 3.1.2, JVM)

Expectation

Should correctly resolve correct implicit, in 3.1.1 compiler choosed JsonFormat.immSeqFormat

[griggt]

Started with 3ab18a9

[KacperFKorban]

Minimized a bit more

//> using scala "3.1.2"
// //> using scala "3.1.1" // Last working stable version

def test() = {
  func(_ => Box(Seq.empty[String]) )
}

def func[R0](to0: Unit => R0): Unit = ???

trait JsonFormat[T]
object JsonFormat{
  implicit def immSeqFormat: JsonFormat[Seq[String]]  = ???

  implicit def iterableFormat: JsonFormat[Iterable[String]]   = ??? 
}

case class Box[A1: JsonFormat](elem: A1)

[odersky]

@smarter Not sure anything can be done here?

[smarter]

I don't know, is there a rationale for preferring immSeqFormat over iterableFormat, given that both are applicable and neither is more specific than the other? What logic was the compiler following before?

[KacperFKorban]

@smarter Is it correct then, that when we change the argument of func to be a value (instead of a function) the program compiles? i.e. should the following program compile?

//> using scala "3.1.2"
// //> using scala "3.1.1" // Last working stable version

def test() = {
  func(Box(Seq.empty[String]) ) // change here
}

def func[R0](to0: R0): Unit = ??? // change here

trait JsonFormat[T]
object JsonFormat{
  implicit def immSeqFormat: JsonFormat[Seq[String]]  = ???

  implicit def iterableFormat: JsonFormat[Iterable[String]]   = ??? 
}

case class Box[A1: JsonFormat](elem: A1)

[smarter]

Ah, it's true that we instantiate constrained type variables before doing the implicit search, so we should know that A1 is a Seq before the search starts. The problem is that the heuristic we use to decide which variables to instantiate isn't good enough here:
https://github.com/lampepfl/dotty/blob/e7f4db5edee751bf5550715d761d8a1c14cbacb3/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L325-L365
This doesn't handle the extra avoidance type variables generated by the compiler in 3ab18a9, although they don't appear in the tree they always correspond to some existing type variable.

While it would be possible to find for each variable in the tree the corresponding avoidance variable (using logic similar to findParam in legalVar in 3ab18a9), that would be quadratic in the number of variables so best avoided. We already know tvarsInParams is problematic (#7586, #7999), so a larger rethinking of this logic might be warranted, but it's not something I'll have time to look at before September.

[odersky]

Can we come up with a simpler fix before September? We should avoid having regressions like this if possible.

[smarter]

I can't think of anything, except attempting a partial revert of 3ab18a9 but even that is beyond what little time I have available right now. It's unfortunate that we're finding out about all these regressions now as opposed to when they were introduced or in a few months, timing-wise this is the worst-case scenario and there isn't anything I can do about it really.