Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
Adam-Vandervorst opened this issue Sep 7, 2022 · 10 comments
Closed

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

Adam-Vandervorst opened this issue Sep 7, 2022 · 10 comments
Assignees
@WojciechMazur
Labels
area:tuples itype:bug regression This worked in a previous version but doesn't anymore stat:fixed in next The issue was fixed in Next and only still applies to LTS.

Comments

@Adam-Vandervorst
Copy link

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.
@Adam-Vandervorst Adam-Vandervorst added itype:bug stat:needs triage Every issue needs to have an "area" and "itype" label labels Sep 7, 2022
@odersky
Copy link
Contributor

odersky commented Sep 8, 2022

I think we'll need a bisect on this one

@WojciechMazur
Copy link
Contributor

Bisect points to 46e3d77

@odersky
Copy link
Contributor

odersky commented Sep 8, 2022 •
edited
Loading

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 odersky added itype:invalid and removed itype:bug stat:needs triage Every issue needs to have an "area" and "itype" label labels Sep 8, 2022
@odersky
Copy link
Contributor

odersky commented Sep 8, 2022 •
edited
Loading

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
Copy link
Author

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
Copy link
Contributor

odersky commented Sep 12, 2022

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.

@odersky odersky changed the title Typing (inference?) regressions Problem with Type of Tuple.map (was: type inference regression) Sep 12, 2022
anatoliykmetyuk added a commit to dotty-staging/dotty that referenced this issue Sep 12, 2022
@anatoliykmetyuk
Fix scala#15992: Map on Tuples must widen its keys.
3dad7b5
anatoliykmetyuk added a commit to dotty-staging/dotty that referenced this issue Sep 12, 2022
@anatoliykmetyuk
Fix scala#15992: Map on Tuples must widen its keys.
aee8a9f
@Kordyjan Kordyjan added the regression This worked in a previous version but doesn't anymore label Dec 5, 2022
@Kordyjan
Copy link
Contributor

Kordyjan commented Dec 5, 2022

@anatoliykmetyuk Is your fix complete? Is there a reason why it wasn't put into a pr?

@mbovel mbovel mentioned this issue May 26, 2023
Closed
nicolasstucki added a commit to dotty-staging/dotty that referenced this issue Dec 4, 2023
@nicolasstucki
Redefine Tuple operations
fd413fd 
This provides a way forward to fixing the signatures of some tuple
methods, and removes the inlining from the tuple methods. Optimization
will be implemented later directly on these method calls, which avoids
unnecessary complications due to inlining artifacts.

Old definitions are made tasty compatible and just delegate to the new
representation.

Fixes scala#12721
Fixes scala#15992
Fixes scala#16207
@nicolasstucki nicolasstucki mentioned this issue Dec 4, 2023
Closed
nicolasstucki added a commit to dotty-staging/dotty that referenced this issue Dec 7, 2023
@nicolasstucki
Redefine Tuple operations
585d7a0 
This provides a way forward to fixing the signatures of some tuple
methods, and removes the inlining from the tuple methods. Optimization
will be implemented later directly on these method calls, which avoids
unnecessary complications due to inlining artifacts.

Old definitions are made tasty compatible and just delegate to the new
representation.

Fixes scala#12721
Fixes scala#15992
Fixes scala#16207
nicolasstucki added a commit to dotty-staging/dotty that referenced this issue Dec 7, 2023
@nicolasstucki
Redefine Tuple operations
6ede644 
This provides a way forward to fixing the signatures of some tuple
methods, and removes the inlining from the tuple methods. Optimization
will be implemented later directly on these method calls, which avoids
unnecessary complications due to inlining artifacts.

Old definitions are made tasty compatible and just delegate to the new
representation.

Fixes scala#12721
Fixes scala#15992
Fixes scala#16207
@Adam-Vandervorst Adam-Vandervorst mentioned this issue Jan 18, 2024
Closed
@Gedochao Gedochao added the stat:fixed in next The issue was fixed in Next and only still applies to LTS. label Jul 3, 2024
@Gedochao
Copy link
Contributor

Gedochao commented Jul 3, 2024 •
edited
Loading

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

@WojciechMazur
Copy link
Contributor

Fixed in #19954 - not yet sure if it would be back portable, it seems to depend on the Scala 3.4 match type changes.

@WojciechMazur
Copy link
Contributor

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@WojciechMazur WojciechMazur

Labels
area:tuples itype:bug regression This worked in a previous version but doesn't anymore stat:fixed in next The issue was fixed in Next and only still applies to LTS.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@odersky @anatoliykmetyuk @Adam-Vandervorst @Kordyjan @Gedochao @WojciechMazur