Type infer issue

[vigoo]

Compiler version

Tested with 3.0.2 and 3.1.0-RC2

Minimized code

https://github.com/vigoo/scala3-type-infer-bug

Contains a minimal example (the issue originally came up in a parser library under development) and two files from ZIO, Zippable and Unzippable as the issue seems to be related to these specific implicits.

Output

[error] 26 |    val _ = assertSameType(xy2)
[error]    |                           ^^^
[error]    |                      Found:    (Main.xy2 : Example[Int, (AnyVal, Int)])
[error]    |                      Required: Example[T, T]
[error]    |
[error]    |                      where:    T is a type variable

Expectation

The

 val x = pure(1)
 val y = pure(2)
 val xy1 = x zip y

and

val xy2 = pure(1) zip pure(2)

should both be inferred to the same result, Example[(Int, Int), (Int, Int)].

[vigoo]

Typer output:

[info]     val x: Example[Int, Int] = Example.pure[Int](1)
[info]     val y: Example[Int, Int] = Example.pure[Int](2)
[info]     val xy1: Example[(Int, Int), (Int, Int)] =
[info]       zip[Int, Int](Main.x)[Int, Int, (Int, Int), (Int, Int)](Main.y)(
[info]         zio.Unzippable.Unzippable2[Int, Int]
[info]       , zio.Zippable.Zippable2[Int, Int])
[info]     val xy2: Example[Int, (AnyVal, Int)] =
[info]       zip[Unit, AnyVal](Example.pure[AnyVal](1))[Int, Int, Int, (AnyVal, Int)](
[info]         Example.pure[Int](2)
[info]       )(zio.Unzippable.UnzippableLeftIdentity[Int],
[info]         zio.Zippable.Zippable2[AnyVal, Int]
[info]       )

[soronpo]

Thanks for posting. I believe the code can be minimized significantly more.

[vigoo]

I further minimized it, now it's a single file:

enum Example[-I, +O]:
  case Pure[A](value: A) extends Example[A, A]
  case Zip[I1, O1, I2, O2, RI, RO](a: Example[I1, O1], b: Example[I2, O2]) extends Example[RI, RO]

object Example:
  def pure[A](value: A): Example[A, A] = Example.Pure(value)

extension[I, O] (self: Example[I, O])
  def zip[I2, O2, RI, RO](other: Example[I2, O2])(using Unzippable.In[I, I2, RI], Zippable.Out[O, O2, RO]): Example[RI, RO] =
    Example.Zip(self, other)

trait Unzippable[A, B]:
  type In
  def unzip(in: In): (A, B)

object Unzippable extends UnzippableLowPriority1:
  type In[A, B, C] = Unzippable[A, B] { type In = C }

  implicit def UnzippableLeftIdentity[A]: Unzippable.In[Unit, A, A] =
    new Unzippable[Unit, A] {
      type In = A
      def unzip(in: A): (Unit, A) =
        ((), in)
    }

trait UnzippableLowPriority1 {

  implicit def Unzippable2[A, B]: Unzippable.In[A, B, (A, B)] =
    new Unzippable[A, B] {
      type In = (A, B)
      def unzip(in: (A, B)): (A, B) =
        (in._1, in._2)
    }
}

trait Zippable[-A, -B]:
  type Out
  def zip(left: A, right: B): Out

object Zippable:
  type Out[-A, -B, C] = Zippable[A, B] { type Out = C }

  implicit def Zippable2[A, B]: Zippable.Out[A, B, (A, B)] =
    new Zippable[A, B] {
      type Out = (A, B)
      def zip(left: A, right: B): Out = (left, right)
    }

def assertSameType[T](e: Example[T, T]): Example[T, T] = e

object Main extends App:
  import Example._

    val x = pure(1)
    val y = pure(2)

    val xy1: Example[(Int, Int), (Int, Int)] = x zip y
    // val xy2: Example[(Int, Int), (Int, Int)] = pure(1) zip pure(2)
    val xy2 = pure(1) zip pure(2)

    val _ = assertSameType(xy1)
    val _ = assertSameType(xy2)

[dwijnand]

This isn't a bug in the compiler. The type inferencer is trying to make UnzippableLeftIdentity work and it's able to do so by LUB'ing Int and Unit to AnyVal.

The real bug is in the definition of Unzippable's instances: UnzippableLeftIdentity should be the lower priority implicit, as it's the degenerate case where for the left component Unit is used.

Unzippable.In[Unit, A, A] is isomorphic to Unzippable.In[Unit, A, (Unit, A)], so UnzippableLeftIdentity is the lower priority implicit, for when you don't have a type for the left component and want to use the type Unit (and the value ()) as a fallback.

[mbovel]

Here is the most minimal example I could come up with where val a = A(1); tc(a) does not have the same type as tc(A(1)), due to inference only operating locally:

object Test:
  class A[T](t: T)

  class TC[T]()

  def tc[T](x: T)(using tc: TC[T]) = x

  given intTc: TC[A[Int]] = new TC() // lower priority

  // inner scope
  {
    given anyValTc: TC[A[AnyVal]] = new TC() // higher priority
    val a = A(1) // : Test.A[Int] (type of 1 is inferred to be Int, and tc is resolved to intTc)
    tc(a)        // : Test.A[Int]
    tc(A(1))     // : Test.A[AnyVal] (type of 1 is inferred to be AnyVal, and tc is resolved to anyValTc)
  }

[mbovel]

Similar example without going through the class A:

class TC[T]()

def tc[T](x: T)(using tc: TC[T]) = tc

given intTc: TC[Int] = new TC() // lower priority

// inner scope
{
  given anyValTc: TC[AnyVal] = new TC() // higher priority

  val a = 1
  val b = tc(a)             // : TC[Int]
  val c = tc(1)             // : TC[Int]
  val d: TC[AnyVal] = tc(1) // : TC[AnyVal]
  val e = tc(1: AnyVal)     // : TC[AnyVal]
}

[adamgfraser]

@dwijnand So I don't think switching the order of the instances works here. One of the goals of Unzippable is to eliminate extra Unit values for the In type. So you're right that we can solve this specific problem by making UnzippableLeftIdentity lower priority but then UnzippableLeftIdentity will never trigger since Unzippable2 takes any arbitrary A and B as inputs.

I'm also still not clear on how this is working. UnzippableLeftIdentity should only be available if the left hand side is Unit. So I'm not sure how the compiler is getting that from pure(1). Is it widening 1 to AnyVal and then narrowing it due to contravariance on I in Example back to Unit?

Would appreciate any advice on how to achieve the desired behavior here as this is working on Scala 2 and it seems like this level of local type inference interferes with the ability to use path dependent types to encode type level functions that existed on Scala 2.

[dwijnand]

I'm also still not clear on how this is working. UnzippableLeftIdentity should only be available if the left hand side is Unit. So I'm not sure how the compiler is getting that from pure(1). Is it widening 1 to AnyVal and then narrowing it due to contravariance on I in Example back to Unit?

My reading of it is that while typing pure(1) zip pure(2) it's simultaneously trying to type pure(1) as well as its call to zip and trying its damnedest to make UnzippableLeftIdentity work, which it can do if it lubs Unit and Int into AnyVal.

So I don't think switching the order of the instances works here. One of the goals of Unzippable is to eliminate extra Unit values for the In type. So you're right that we can solve this specific problem by making UnzippableLeftIdentity lower priority but then UnzippableLeftIdentity will never trigger since Unzippable2 takes any arbitrary A and B as inputs.

Yeah, I can see that now. Though I am still having a hard time getting a full picture of the use cases because they sound like opposites but then Zippable2 is creating a tuple and so is Unzippable2 and UnzippableLeftIdentity... (I also only realised now Unzippable2 could less wasteful.). So perhaps if you could expand on its uses we could look again.

[adamgfraser]

Yeah definitely. Sorry I think sometimes we try to isolate the problem and lose the context a little.

So the origin of this was the desire to do "compositional zips" where you can do something like:

val zio1: ZIO[Any, Nothing, Int] = ???
val zio2: ZIO[Any, Nothing, String] = ???
val zio3: ZIO[Any, Nothing, Boolean] = ???

val zio4: ZIO[Any, Nothing, (Int, String, Boolean)] =
  zio1 <*> zio2 <*> zio3
// nested tuples eliminated

val zio5: ZIO[Any, Nothing, (Int, String, Boolean)] =
  zio4 <*> ZIO.unit
// Unit is an identity element and eliminated from computation of result type

The existing encoding of Zippable here seems to accomplish that goal relatively well with respect to covariant types where we have two "parts" and want to combine them into the right type of "whole".

This then led to a similar desire to abstract over composition of contravariant type parameters, where we know the two "parts" and want to figure out the right "whole" that we could split to generate them.

trait Synchronized {
  final def <*>[RA1 <: RA, RB1 <: RB, EA1 >: EA, EB1 >: EB, A2, B2](
    that: Synchronized[RA1, RB1, EA1, EB1, A2, B2]
  )(implicit
    unzippable: Unzippable[A, A2],
    zippable: Zippable[B, B2]
  ): Synchronized[RA1, RB1, EA1, EB1, unzippable.In, zippable.Out] =
    ???
}

// A `Ref` that can have different input and output types and can be composed
// So we can go from a `Ref[Int] and a `Ref[Int]` to a `Ref[(Int, Int)]`

This also seemed to work well until we ran into this issue on Scala 3 in one of the ZIO ecosystem libraries that was trying to use this feature.

[dwijnand]

In terms of typechecking and implicit lookup it does work. I can't say for certain that what the type inferencer is doing now is wrong or a bug, despite seeing how it's impacting the use case... Maybe @smarter knows?

[adamgfraser]

Well it infers some type and finds some instance but it doesn't find the intended instance or the one that was found on Scala 2 and seems like it makes it no longer possible to express this idea of "compute this output type based on this input type" that we could before. If there is another way we can do the same would love to update to reflect that.

[smarter]

If there's an instance which can fit and implicit search finds it, then I don't know why this would qualify as a bug, as opposed to a limitation of scala 2 not being able to find a legitimate (even if unintended in this case) instance.

"compute this output type based on this input type"

Sounds like match types?

[smarter]

If there's an instance which can fit and implicit search finds it, then I don't know why this would qualify as a bug

To be precise, the one area where we have some wiggle room is "which type variable should be instantiated before doing the implicit search?" In Scala 2, I was never able to understand how this is done, in Scala 3 this is determined using a heuristic (https://github.com/lampepfl/dotty/blob/1ed25ce458d36e773f732267975fbddb0a0be26c/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L324-L332) which tries to find all type variables appearing in the same method call or a prefix of the current method call and instantiate only those (if we don't instantiate anything, we risk running into ambiguity, if we instantiate too much then implicit search cannot drive type inference).

[smarter]

In fact, taking a closer look at https://github.com/lampepfl/dotty/issues/13646#issuecomment-933551826, we do have I qualifying to be instantiated in the zip example, but it doesn't get instantiated because of another heuristic: https://github.com/lampepfl/dotty/blob/1ed25ce458d36e773f732267975fbddb0a0be26c/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L184 which relies on: https://github.com/lampepfl/dotty/blob/1ed25ce458d36e773f732267975fbddb0a0be26c/compiler/src/dotty/tools/dotc/core/Types.scala#L4625-L4630

But I does have a more precise upper-bound than Any in fact, it's upper-bounded by a type variable A coming from the pure method. hasNonWildcardUpperBound returns false anyway because it relies on currentEntry which only returns the non-variable bounds, if we instead do something like:

diff --git compiler/src/dotty/tools/dotc/core/Types.scala compiler/src/dotty/tools/dotc/core/Types.scala
index 1d36efcb2a0..ce84ad92840 100644
--- compiler/src/dotty/tools/dotc/core/Types.scala
+++ compiler/src/dotty/tools/dotc/core/Types.scala
@@ -4626,7 +4626,7 @@ object Types {
      *  does it not contain wildcard types?
      */
     def hasNonWildcardUpperBound(using Context): Boolean =
-      val hi = currentEntry.hiBound
+      val hi = TypeComparer.fullUpperBound(origin).orElse(currentEntry.hiBound)
       !hi.isRef(defn.AnyClass) && !hi.containsWildcardTypes

     /** Unwrap to instance (if instantiated) or origin (if not), until result

... then the test case pass. So, probably something worth digging into more.

[SethTisue]

Could someone suggest a better title for the ticket, to make it easier to find in the future?