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.