Problem with Type of `Tuple.map` (was: type inference regression)

[Adam-Vandervorst]

Compiler version

Works fine in 3.2.0, fails in 3.2.1-RC1-bin-20220904-b5fea82-NIGHTLY

Minimized code

import language.implicitConversions

class Inverse[F[_], G[_]]
type MatchSome[X] = X match { case Some[t] => t }
def matchSome[X](x: X): MatchSome[X] = x match { case k: Some[t] => k.get }
given Inverse[MatchSome, Some] = new Inverse

extension [T](x: T) inline def widen[S >: T]: S = x

given [X, Y](using ev: X =:= Y): Conversion[X, Y] = ev(_)
inline def rel[A] = <:<.refl[Any].asInstanceOf[A]
given simplify_map_map[T <: Tuple, F[_], G[_]]: (Tuple.Map[Tuple.Map[T, G], F] =:= Tuple.Map[T, [X] =>> F[G[X]]]) = rel
given simplify_map_id[T <: Tuple]: (Tuple.Map[T, [X] =>> X] =:= T) = rel
given mapinverse_inversemap[T <: Tuple, F[_], G[_]](using Inverse[F, G]): (Tuple.Map[T, F] =:= Tuple.InverseMap[T, G]) = rel
given simplify_map_inversemap[T <: Tuple, F[_]]: (Tuple.InverseMap[Tuple.Map[T, F], F] =:= T) = rel
given map_ismappedby[O <: Tuple, F[_], M <: Tuple.Map[O, F]]: Tuple.IsMappedBy[F][M] = rel


def f[T <: Tuple](t: T): Tuple.Map[T, [X] =>> Option[List[X]]] =
  val tl: Tuple.Map[T, List] = t.widen.map([X] => (x: X) => List(x))
  val tol: Tuple.Map[Tuple.Map[T, List], Option] = tl.widen.map([X] => (x: X) => Option(x))
  tol

def g[T <: Tuple](t: T): T =
  val nt: Tuple.Map[T, [X] =>> X] = t.widen.map[[X] =>> X]([X] => (x: X) => {println(x); x})
  nt

def h[T <: Tuple](to: T)(using Tuple.IsMappedBy[Some][T]): Tuple.InverseMap[T, Some] =
  val t: Tuple.Map[T, MatchSome] = to.widen.map([X] => (x: X) => matchSome(x))
  t

def back_forth[T <: Tuple](t: T): T =
  val ts: Tuple.Map[T, Some] = t.widen.map([X] => (x: X) => Some(x))
  val nt = h(ts)
  nt


@main def example =
  println(f(4, 2))
  println(g(4, 2))
  println(back_forth(4, 2))
  println(h(Some(1), Some(2)))

Output

[error] -- [E007] Type Mismatch Error: /home/adamv/IdeaProjects/Test/src/main/scala/tuple_laws.scala:22:42 
[error] 22 |  val tl: Tuple.Map[T, List] = t.widen.map([X] => (x: X) => List(x))
[error]    |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |Found:    <root>.this.scala.Tuple.Map[(?1 : T), List]
[error]    |Required: <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |
[error]    |where:    ?1 is an unknown value of type T
[error]    |          T  is a type in method f with bounds <: <root>.this.scala.Tuple
[error]    |
[error]    |
[error]    |Note: a match type could not be fully reduced:
[error]    |
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[(?1 : T), List]
[error]    |  failed since selector  (?1 : T)
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => List[h] *: LazyRef(Tuple$.this.Map[t, List])
[error]    |
[error]    | longer explanation available when compiling with `-explain`
[error] -- [E007] Type Mismatch Error: /home/adamv/IdeaProjects/Test/src/main/scala/tuple_laws.scala:23:63 
[error] 23 |  val tol: Tuple.Map[Tuple.Map[T, List], Option] = tl.widen.map([X] => (x: X) => Option(x))
[error]    |                                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |Found:    <root>.this.scala.Tuple.Map[
[error]    |  (?2 : <root>.this.scala.Tuple.Map[T, scala.this.package.List])
[error]    |, scala.this.Option]
[error]    |Required: <root>.this.scala.Tuple.Map[
[error]    |  <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |, [A] =>> <root>.this.scala.Option[A]]
[error]    |
[error]    |where:    ?2 is an unknown value of type <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |          T  is a type in method f with bounds <: <root>.this.scala.Tuple
[error]    |
[error]    |
[error]    |Note: a match type could not be fully reduced:
[error]    |
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[
[error]    |  (?2 : <root>.this.scala.Tuple.Map[T, scala.this.package.List])
[error]    |, scala.this.Option]
[error]    |  failed since selector  T
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => List[h] *: LazyRef(Tuple$.this.Map[t, scala.this.package.List])
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |  failed since selector  T
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => List[h] *: LazyRef(Tuple$.this.Map[t, scala.this.package.List])
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |  failed since selector  T
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => List[h] *: LazyRef(Tuple$.this.Map[t, scala.this.package.List])
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[T, scala.this.package.List]
[error]    |  failed since selector  T
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => List[h] *: LazyRef(Tuple$.this.Map[t, scala.this.package.List])
[error]    |
[error]    | longer explanation available when compiling with `-explain`
[error] -- [E007] Type Mismatch Error: /home/adamv/IdeaProjects/Test/src/main/scala/tuple_laws.scala:27:58 
[error] 27 |  val nt: Tuple.Map[T, [X] =>> X] = t.widen.map[[X] =>> X]([X] => (x: X) => {println(x); x})
[error]    |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |Found:    <root>.this.scala.Tuple.Map[(?3 : T), [X] =>> X]
[error]    |Required: <root>.this.scala.Tuple.Map[T, [X] =>> X]
[error]    |
[error]    |where:    ?3 is an unknown value of type T
[error]    |          T  is a type in method g with bounds <: <root>.this.scala.Tuple
[error]    |
[error]    |
[error]    |Note: a match type could not be fully reduced:
[error]    |
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[(?3 : T), [X] =>> X]
[error]    |  failed since selector  (?3 : T)
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => h *: LazyRef(Tuple$.this.Map[t, [X] =>> X])
[error]    |
[error]    | longer explanation available when compiling with `-explain`
[error] -- [E007] Type Mismatch Error: /home/adamv/IdeaProjects/Test/src/main/scala/tuple_laws.scala:31:47 
[error] 31 |  val t: Tuple.Map[T, MatchSome] = to.widen.map([X] => (x: X) => matchSome(x))
[error]    |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |Found:    <root>.this.scala.Tuple.Map[(?4 : T), 
[error]    |  tuple_laws.this.tuple_laws$package.MatchSome
[error]    |]
[error]    |Required: <root>.this.scala.Tuple.Map[T, tuple_laws.this.tuple_laws$package.MatchSome]
[error]    |
[error]    |where:    ?4 is an unknown value of type T
[error]    |          T  is a type in method h with bounds <: <root>.this.scala.Tuple
[error]    |
[error]    |
[error]    |Note: a match type could not be fully reduced:
[error]    |
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[(?4 : T), 
[error]    |  tuple_laws.this.tuple_laws$package.MatchSome
[error]    |]
[error]    |  failed since selector  (?4 : T)
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => tuple_laws.this.tuple_laws$package.MatchSome[h] *: 
[error]    |  LazyRef(Tuple$.this.Map[t, tuple_laws.this.tuple_laws$package.MatchSome])
[error]    |
[error]    | longer explanation available when compiling with `-explain`
[error] -- [E007] Type Mismatch Error: /home/adamv/IdeaProjects/Test/src/main/scala/tuple_laws.scala:35:42 
[error] 35 |  val ts: Tuple.Map[T, Some] = t.widen.map([X] => (x: X) => Some(x))
[error]    |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |Found:    <root>.this.scala.Tuple.Map[(?5 : T), scala.this.Some]
[error]    |Required: <root>.this.scala.Tuple.Map[T, [A] =>> <root>.this.scala.Some[A]]
[error]    |
[error]    |where:    ?5 is an unknown value of type T
[error]    |          T  is a type in method back_forth with bounds <: <root>.this.scala.Tuple
[error]    |
[error]    |
[error]    |Note: a match type could not be fully reduced:
[error]    |
[error]    |  trying to reduce  <root>.this.scala.Tuple.Map[(?5 : T), scala.this.Some]
[error]    |  failed since selector  (?5 : T)
[error]    |  does not match  case <root>.this.scala.Tuple$package.EmptyTuple => <root>.this.scala.Tuple$package.EmptyTuple
[error]    |  and cannot be shown to be disjoint from it either.
[error]    |  Therefore, reduction cannot advance to the remaining case
[error]    |
[error]    |    case h *: t => scala.this.Some[h] *: LazyRef(Tuple$.this.Map[t, scala.this.Some])
[error]    |
[error]    | longer explanation available when compiling with `-explain`

Expectation

Work as defined in 3.2.0.

[odersky]

I think we'll need a bisect on this one

[WojciechMazur]

Bisect points to 46e3d77

[odersky]

Minimized:

def widen[T](x: T): T = x

def f[T <: Tuple](t: T): Unit =
  val tl: Tuple.Map[T, List] = widen(t).map([X] => (x: X) => List(x))

[odersky]

I think the new behavior is correct, unfortunately. widen(t) has type ?: T (i.e. unknown value of type T) and that type appears in invariant position in the type of map. That means we cannot approximate to T. And since Map is invariant in its first parameter we get the expected error message:

5 |  val tl: Tuple.Map[T, List] = widen(t).map([X] => (x: X) => List(x))
  |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |               Found:    Tuple.Map[(?2 : T), List]
  |               Required: Tuple.Map[T, List]
  |
  |               where:    ?2 is an unknown value of type T
  |                         T  is a type in method f with bounds <: Tuple

Previous to 46e3d77 the approximation logic had holes, that's why this case was overlooked. 46e3d77 was done to fix weird error messages but we see here that it fixes a soundness problem as well.

[Adam-Vandervorst]

I use widen a lot, and this makes me worried upgrading other projects past 3.2.0 @odersky

Specifically, without the widen the minimized code fails with

  val tl: Tuple.Map[T, List] = t.map([X] => (x: X) => List(x))
                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Found:    <root>.this.scala.Tuple.Map[(t : T), List]
Required: <root>.this.scala.Tuple.Map[T, scala.this.package.List]

where:    T is a type in method f with bounds <: <root>.this.scala.Tuple

which is expected behavior too?

It's very hard to do anything nontrivial with the new Tuple constructs at the moment, is there any workaround?

[odersky]

After digging deeper it looks like a fundamental problem with Tuple.map to me, which was only hidden by a hole in asSeenFrom. To recap:

t.map([X] => (x: X) => List(x))

is of type

Tuple.Map[t.type, List]

Map is invariant so this is not compatible with Tuple.Map[T, List]. The previous trick of using

(t: T).map([X] => (x: X) => List(x))

(which is essentially what widen does) does not work either. Because the prefix T occurs invariantly in the type of
map it has to be narrowed to a skolem. So you get

Tuple.Map[?1: T, List]

The problem seems to be that map does not widen the key type of the map. Indeed it is defined like this:

  /** Called on a tuple `(a1, ..., an)`, returns a new tuple `(f(a1), ..., f(an))`.
   *  The result is typed as `(F[A1], ..., F[An])` if the tuple type is fully known.
   *  If the tuple is of the form `a1 *: ... *: Tuple` (that is, the tail is not known
   *  to be the cons type.
   */
  inline def map[F[_]](f: [t] => t => F[t]): Map[this.type, F] =
    runtime.Tuples.map(this, f).asInstanceOf[Map[this.type, F]]

So the result is this.type. I believe it should be This instead.

Also the doc comment is ill-formed and incomplete, so that needs to be fixed as well.