[Regression in 3.1.2-RC1] Inferred union in type argument position gets widened

[ansvonwa]

Compiler version

3.1.2-RC1

First bad commit 3ab18a9 in #14026

Minimized code

object ImplNotFound:
  def main(args: Array[String]): Unit =
    val res: Seq[String | Int] = (??? : Seq[Int]).collect {
      case 1 => Seq("")
      case 2 => Seq(1)
    }.flatten

Output

[error] -- Error: /.../ImplNotFound.scala:6:13 
[error] 6 |    }.flatten
[error]   |             ^
[error]   |no implicit argument of type Seq[Matchable] => IterableOnce[B] was found for parameter asIterable of method flatten in trait IterableOps
[error]   |
[error]   |where:    B is a type variable with constraint <: String | Int

Expectation

Successful compilation as in 3.0.0 to 3.1.1

[odersky]

It would be good to identify the commit that caused this.

[ansvonwa]

It is Create fresh type variables to keep constraints level-correct from #14026

[odersky]

@ansvonwa Thanks for the bisect! @smarter I guess that's for you then 😉

[smarter]

In 3.1.1 the following code used to infer a result type of Seq[Seq[String | Int]]:

object ImplNotFound:
  def main(args: Array[String]): Unit =
    val res = (??? : Seq[Int]).collect {
      case 1 => Seq("")
      case 2 => Seq(1)
    }

[[syntax trees at end of                     typer]] // try/i14494.scala
package <empty> {
  final lazy module val ImplNotFound: ImplNotFound = new ImplNotFound()
  final module class ImplNotFound() extends Object() {
    this: ImplNotFound.type =>
    def main(args: Array[String]): Unit =
      {
        val res: Seq[Seq[String | Int]] =
          (??? :Seq[Int]).collect[Seq[String | Int]](
            {
              def $anonfun(x$1: Int): Seq[String | Int] =
                x$1:(x$1 : Int) @unchecked match
                  {
                    case 1 =>
                      Seq.apply[String](["" : String]*)
                    case 2 =>
                      Seq.apply[Int]([1 : Int]*)
                  }
              closure($anonfun:PartialFunction[Int, Seq[String | Int]])
            }
          )
        ()
      }
  }
}

But now the union gets widened to Matchable:

package <empty> {
  final lazy module val ImplNotFound: ImplNotFound = new ImplNotFound()
  final module class ImplNotFound() extends Object() {
    this: ImplNotFound.type =>
    def main(args: Array[String]): Unit =
      {
        val res: Seq[Seq[Matchable]] =
          (??? :Seq[Int]).collect[Seq[Matchable]](
            {
              def $anonfun(x$1: Int): Seq[Matchable] =
                x$1:(x$1 : Int) @unchecked match
                  {
                    case 1 =>
                      Seq.apply[String](["" : String]*)
                    case 2 =>
                      Seq.apply[Int]([1 : Int]*)
                  }
              closure($anonfun:PartialFunction[Int, Seq[Matchable]])
            }
          )
        ()
      }
  }

No idea why.

[smarter]

I don't believe I'll have time to fix this for 3.1.2 (or any time before September of this year really!)

[smarter]

I guess the root of the problem is that type variable avoidance and widenUnion do not commute, as widenUnion is happy to widen any union it sees at the top-level when instantiating a type variable, and adding more type variables create more opportunity for it to run. Perhaps we can simply not run widenUnion when instantiating a type variable created by avoidance (which can be identified by checking for AvoidNameKind on its name)

[smarter]

In fact, it's not even that we have more type variables which causes issues, it's that we're instantiating them in a different order, given:

?A1 >: String
?A2 >: Int
?B >: Seq[?A1] | Seq[?A2]

If we instantiate ?A1 and ?A2 first we're left with ?B >: Seq[Int] | Seq[String] which leads to ?B := Seq[Int | String].
But if we instantiate ?B first, we get:

?B := Seq[?A1]
?A1 >: String | Int

And then of course we instantiate to ?A1 := Matchable. We could try to come up with some heuristic to change the order in which we do the instantiations, but that seems likely to break as many things as it fixes. Perhaps we should mark the inferred union String | Int to be a hard union since it came from comparing the arguments of two AppliedTypes?