Unexpected type widening during inference (behaves differently in Scala 2)

[kitlangton]

Compiler version

3.1.1

Minimized code

Here's a Scastie with the unexpected behavior in Scala 3. And here's a Scastie with the expected behavior in Scala 2.

Here's the gist:

// Given a constructor that infers types from given a function
def fromFunction[A, B, C](f: (A, B) => C)(implicit tagA: Tag[A], tagB: Tag[B]): Box[A with B] =
  Box(Map("a" -> tagA, "b" -> tagB))
 
// It behaves differently depending on whether or not the call site is ascribed a type

// No type ascription
val box1 = fromFunction((int: Int, string: String) => true)
println(box2) // Infers A and B correctly

// With a type ascription
val box2: Box[Int with String] = fromFunction((int: Int, string: String) => true)
println(box3) // Infers A and B to both be (A & B)

Output

 // In the case without the type ascription
Box(Map(a -> Tag[Int], b -> Tag[String]))

// In the case with the type ascription
Box(Map(a -> Tag[{String & Int}], b -> Tag[{String & Int}])) 

Expectation

I would expect both cases to infer with a bias toward the input type, which is function of type (Int, String) => Boolean. So I would expect both cases to print Box(Map(a -> Tag[Int], b -> Tag[String])), as it does in the linked Scala 2 version.

Concretely, this is used in ZIO to generate "Layers" from functions. For now, in Scala 3, it is necessary to either remove the type ascription or create an intermediate val without an ascription.

[smarter]

Minimized to not depend on external code:

class Tag[A]
class Box[-A]

class A {
  implicit val tagInt: Tag[Int] = ???
  implicit val tagString: Tag[String] = ???

  def fromFunction[A, B, C](f: (A, B) => C)(implicit tagA: Tag[A], tagB: Tag[B]): Box[A with B] = ???
  
  val box2 =
    fromFunction((int: Int, string: String) => true) // OK: Infers ?A := Int, ?B = String
  val box3: Box[Int with String] =
    fromFunction((int: Int, string: String) => true) // error: Infers ?A := Int & String, ?B = Int & String
}

When we get to the implicit parameter block we have as constraints:

     ?A >: Int & String <: Int
     ?B >: Int & String <: String

(the lower bound constraints come from the expected type, the upper bound constraints come from the lambda parameter types).

The logic used to instantiate type variables before implicit search is:
https://github.com/lampepfl/dotty/blob/f4822ac22bd7bc8eecb134ca5dc39585be9ff357/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L56-L65
Here, 1. applies: ?A is constrained from below to Int & String so we instantiate it to Int & String, same for ?B. The heuristic is that doing an implicit search with more precisely constrained types is more likely to yield the result you're looking for. It turns out that in this particular case this isn't true, but it's not clear to me if there's anything we can do to handle this case differently without breaking other things.

In conclusion, I don't recommend relying on type inference implementation details, especially when intersection/union types are involved 😅

[smarter]

For reference, this isn't the first time that we have inference issues involving intersections in the expected type, I was able to significantly improve the situation in #8635, the key difference here is the interaction between type inference and implicit search which is poorly understood.