search

scala / scala3

The Scala 3 compiler, also known as Dotty.
https://dotty.epfl.ch
Apache License 2.0
5.86k stars 1.06k forks source link

Compiler hang with covariant type constructor in GADT #14287

Closed mpilquist closed 1 year ago

mpilquist commented 2 years ago

Compiler version

3.1.1-RC2

Minimized code

// using scala 3.1.1-RC2

enum Free[+F[_], A]:
  case Return(a: A)
  case Suspend(s: F[A])
  case FlatMap[F[_], A, B](
    s: Free[F, A],
    f: A => Free[F, B]) extends Free[F, B]

  def flatMap[F2[x] >: F[x], B](f: A => Free[F2,B]): Free[F2,B] =
    FlatMap(this, f)

  @annotation.tailrec
  final def step: Free[F, A] = this match
    case FlatMap(FlatMap(fx, f), g) => fx.flatMap(x => f(x).flatMap(y => g(y))).step
    case FlatMap(Return(x), f) => f(x).step
    case _ => this

Output

Compilation hangs when using scala-cli. In a larger code base, I've seen crashes with stacks like the following, though I haven't reproduced the crash in a standalone program. The hang & crash are both related to making F covariant in the definition of Free.

In the example above, changing the left-associated flatMap case to case FlatMap(FlatMap(fx, f), g) => ??? fixes the issue.

[error] dotty.tools.dotc.core.TypeOps$.dotty$tools$dotc$core$TypeOps$$anon$1$$_$op$proxy5$1(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$.dotty$tools$dotc$core$TypeOps$$anon$1$$_$op$proxy5$1(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$.dotty$tools$dotc$core$TypeOps$$anon$1$$_$op$proxy5$1(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$$anon$1.apply(TypeOps.scala:451)
[error] dotty.tools.dotc.core.TypeOps$.dotty$tools$dotc$core$TypeOps$$anon$1$$_$op$proxy5$1(TypeOps.scala:451)

Another workaround is explicitly providing types to the flatMap calls in the problematic expression:

    case FlatMap(FlatMap(fx, f), g) =>
      fx.flatMap[F, A](x => f(x).flatMap[F, A](g)).step
dwijnand commented 2 years ago

Minimised to

enum Foo[+H[_]]:
  case Bar[F[_]](f: Foo[F]) extends Foo[F]
  case Baz()

  def test: Foo[H] = this match
    case Bar(Bar(f)) => Bar(f)
    case _           => this

It's a case of TypeBounds with circular infos:

avoid F$1 #18787  >: F$2 <: F
avoid F$2 #18891  <: F$1
avoid F$1 #18787  >: F$2 <: F
avoid F$2 #18891  <: F$1