scala3
scala3 copied to clipboard
Published
20 hours ago •
scala
scala
Problem with Type of `Tuple.map` (was: type inference regression)
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.
Bisect points to https://github.com/lampepfl/dotty/commit/46e3d773ce1cae594196dc984356e2629d3fd74a
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))
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 https://github.com/lampepfl/dotty/commit/46e3d773ce1cae594196dc984356e2629d3fd74a the approximation logic had holes, that's why this case was overlooked. https://github.com/lampepfl/dotty/commit/46e3d773ce1cae594196dc984356e2629d3fd74a was done to fix weird error messages but we see here that it fixes a soundness problem as well.
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?
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.
@anatoliykmetyuk Is your fix complete? Is there a reason why it wasn't put into a pr?
It seems we've fixed int in 3.5.0. The compilation passes since 3.5.0-RC1. What remains is to port the fix to LTS. cc @WojciechMazur
Fixed in https://github.com/scala/scala3/pull/19954 - not yet sure if it would be back portable, it seems to depend on the Scala 3.4 match type changes.
The fix cannot be backported to the LTS - it does course regressions, probably due to missing PR backports and what's important it does not fix this issue. I'm closing this issue as there is nothing more we can do in the LTS line and it's already fixed in the Next line