Dotty: Unminimized OOM

[djspiewak]

Working on minimizing this. Still a ways to go but I'm getting much closer. Please see this branch: https://github.com/djspiewak/cats-effect/tree/bug/dotty-compiler-oom You can reproduce the OOM by running sbt ++3.0.0-M3 kernelJVM/clean kernelJVM/compile (ignore the errors; that code could just be deleted but I haven't done it yet).

The offending call site appears to be this one: https://github.com/djspiewak/cats-effect/blob/bug/dotty-compiler-oom/kernel/shared/src/main/scala/cats/effect/kernel/Resource.scala#L33 If you uncomment the explicit type parameters, it compiles reasonably quickly. Forcing the compiler to make this inference for us (which 2.13 does just fine) causes it to spin its wheels for about a minute (on my laptop) before running out of memory.

Note that the import Resource._ and the implicit in the companion object are also necessary. I haven't minimized the other imports, but I suspect most of them are unneeded.

In case it's helpful, I coaxed this stack trace out of it:

java.lang.OutOfMemoryError: GC overhead limit exceeded
  at scala.collection.immutable.List.$colon$colon(List.scala:97)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5070)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5102)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda(Types.scala:5080)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5105)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy13$1(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5102)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda(Types.scala:5080)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5105)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy13$1(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5102)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda(Types.scala:5080)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5105)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy13$1(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5067)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5102)
  at dotty.tools.dotc.core.Substituters$.substParam(Substituters.scala:145)
  at dotty.tools.dotc.core.Substituters$SubstParamMap.apply(Substituters.scala:193)

This reproduces against both M2 and M3.

[griggt]

It's probably not fully minimized, but this self-contained example seems to trigger the issue:

trait Monoid[A]
trait Semigroup[A]
trait Applicative[F[_]]

trait OptionT[F[_], A]
trait EitherT[F[_], A, B]
trait IorT[F[_], A, B]
trait WriterT[F[_], L, V]
trait Kleisli[F[_], A, B]

final class ApplicativeIdOps[A](private val a: A) extends AnyVal {
  def pure[F[_]](implicit F: Applicative[F]): F[A] = ???
}

object ApplicativeSyntax {
  implicit final def syntaxApplicativeId[A](a: A): ApplicativeIdOps[A] = new ApplicativeIdOps[A](a)
}

trait Sync[F[_]]

object Sync {
  implicit def syncForOptionT[F[_]](implicit F0: Sync[F]): Sync[OptionT[F, *]] = ???
  implicit def syncForEitherT[F[_], E](implicit F0: Sync[F]): Sync[EitherT[F, E, *]] = ???
  implicit def syncForIorT[F[_], L](implicit F0: Sync[F], L0: Semigroup[L]): Sync[IorT[F, L, *]] = ???
  implicit def syncForWriterT[F[_], L](implicit F0: Sync[F], L0: Monoid[L]): Sync[WriterT[F, L, *]] = ???
  implicit def syncForKleisli[F[_], R](implicit F0: Sync[F]): Sync[Kleisli[F, R, *]] = ???
}

trait Async[F[_]] extends Sync[F]

object Async {
  implicit def asyncForOptionT[F[_]](implicit F0: Async[F]): Async[OptionT[F, *]] = ???
  implicit def asyncForEitherT[F[_], E](implicit F0: Async[F]): Async[EitherT[F, E, *]] = ???
  implicit def asyncForIorT[F[_], L](implicit F0: Async[F], L0: Semigroup[L]): Async[IorT[F, L, *]] = ???
  implicit def asyncForWriterT[F[_], L](implicit F0: Async[F], L0: Monoid[L]): Async[WriterT[F, L, *]] = ???
  implicit def asyncForKleisli[F[_], R](implicit F0: Async[F]): Async[Kleisli[F, R, *]] = ???
}

trait Concurrent[F[_], E] extends Applicative[F]

trait Ref[F[_], A]

object Ref {
  trait Make[F[_]]
  object Make extends MakeInstances

  trait MakeInstances extends MakeLowPriorityInstances {
    implicit def concurrentInstance[F[_]](implicit F: Concurrent[F, _]): Make[F] = ???
  }

  trait MakeLowPriorityInstances {
    implicit def syncInstance[F[_]](implicit F: Sync[F]): Make[F] = ???
  }

  def of[F[_], A](a: A)(implicit mk: Make[F]): F[Ref[F, A]] = ???
}


class Resource[F[_], A] {
  import ApplicativeSyntax._

  implicit def asyncForResource[F[_]](implicit F0: Async[F]): Async[Resource[F, *]] = ???

  def parZip(implicit F: Concurrent[F, Throwable]) = {
    Ref.of /*[F, (F[Unit], F[Unit])]*/ (().pure[F] -> ().pure[F])
    ()
  }
}

[djspiewak]

Thank you! That's a huge step closer to minimal.

[griggt]

Minimized further. This seems to be a regression introduced by #9065.

trait Applicative[F[_]]

trait FooT[F[_], A]
trait BarT[F[_], A]
trait QuxT[F[_], A]
trait BazT[F[_], A]
trait ZepT[F[_], A]
trait JazT[F[_], A]
trait LafT[F[_], A]
trait PogT[F[_], A]

trait Sync[F[_]]
object Sync {
  implicit def syncForFooT[F[_]](implicit F0: Sync[F]): Sync[FooT[F, *]] = ???
  implicit def syncForBarT[F[_]](implicit F0: Sync[F]): Sync[BarT[F, *]] = ???
  implicit def syncForQuxT[F[_]](implicit F0: Sync[F]): Sync[QuxT[F, *]] = ???
  implicit def syncForBazT[F[_]](implicit F0: Sync[F]): Sync[BazT[F, *]] = ???
  implicit def syncForZepT[F[_]](implicit F0: Sync[F]): Sync[ZepT[F, *]] = ???
  implicit def syncForJazT[F[_]](implicit F0: Sync[F]): Sync[JazT[F, *]] = ???
  // defining additional implicits beyond the 6 above seems to result in hang/OOM
  implicit def syncForLafT[F[_]](implicit F0: Sync[F]): Sync[LafT[F, *]] = ???
  implicit def syncForPogT[F[_]](implicit F0: Sync[F]): Sync[PogT[F, *]] = ???
}

trait Ref[F[_], A]
object Ref {
  trait Make[F[_]]
  object Make extends MakeInstances

  trait MakeInstances extends MakeLowPriorityInstances {
    implicit def applicativeInstance[F[_]](implicit F: Applicative[F]): Make[F] = ???
  }

  trait MakeLowPriorityInstances {
    implicit def syncInstance[F[_]](implicit F: Sync[F]): Make[F] = ???
  }

  def of[F[_], A](a: A)(implicit mk: Make[F]): F[Ref[F, A]] = ???
}

class Resource[F[_], A] {
  implicit def syncForResource[F[_]](implicit F0: Sync[F]): Sync[Resource[F, *]] = ???

  def foo(x: F[Unit])(implicit F: Applicative[F]) = {
    Ref.of /*[F, (F[Unit], F[Unit])]*/ ((x, x))
    ()
  }
}

[odersky]

Thanks for digging deep here @griggt! I had a look at the previous semi-minimized example. It works if we have 4 of everything (trait, and implicit defs in Sync and Async) and fails if we have 5. So, it's a very highly branching search graph and it seems that graph gets traversed in a less efficient order with #9065 implemented. #9065 simply changed the order in which outstanding implicit searches were tried so that the comparison was transitive.

[odersky]

I found the cause. It was a rather stupid mistake where we compared the wrong symbols. But all the real work was done by @griggt here.