`Exception: java.lang.OutOfMemoryError` (diverging implicits) #13838

armanbilge · 2021-10-28T01:19:50Z

Compiler version

3.1.1-RC1

Minimized code

armanbilge/schrodinger@ed9a8ba

Clone project in clean workspace and run sbt compile.

Apologies that this isn't further minimized, not entirely sure how to approach this one. I'd appreciate any pointers.

FWIW it's not a big project, and the module that seems to have the problem is 4 files with < 1k LOC total.

Output

[warn] In the last 8 seconds, 6.706 (86.2%) were spent in GC. [Heap: 0.10GB free of 4.00GB, max 4.00GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.

  | => monteCarlo / Compile / compileIncremental 312s

...

[warn] In the last 6 seconds, 5.215 (99.8%) were spent in GC. [Heap: 0.00GB free of 4.00GB, max 4.00GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.

Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "classloader-cache-cleanup-0

Note this occurs frequently, but not always. Sometimes it compiles just fine.

Expectation

My code compiles the first time and everything is hunky-dory :)

The text was updated successfully, but these errors were encountered:

SethTisue · 2021-10-28T01:28:12Z

Is it a regression, was some previous Scala 3 version able to compile the code?

armanbilge · 2021-10-28T01:34:17Z

Thanks for the response. No, not a regression to my knowledge but can't know for sure. I've been on 3.1.1 nightlies until the RC1 because I needed this fix in #13650.

Looking through commit history/ci the earliest I saw this was actually when I bumped to 3.1.1-RC1 in armanbilge/schrodinger@48e93d2, but that's also around the commits where I started fleshing out the monteCarlo module that seems to have the problem.

Update: tried armanbilge/schrodinger@1f34ede which is using 3.1.1-RC1-bin-20211014-af9594d-NIGHTLY and same issue.

Update 2: I tried bisecting but the non-determinism is confounding things. I couldn't get anything before armanbilge/schrodinger@1f34ede to have this problem, but then I just tried that commit again and this time it compiled fine 🙃

dwijnand · 2021-10-28T09:09:10Z

Other than minimising the code, you could also approach it by "minimising" it by removing sbt (and thus zinc) usage by switching to cli scala. Also, removing dependencies (which makes removing sbt/zinc easier).

armanbilge · 2021-10-28T21:28:16Z

Thanks for the advice. I did some trivial minimizing in https://github.com/armanbilge/schrodinger/tree/dotty/issue/13838, I'll keep chipping away at it.

I also captured a heapdump, not sure if there's anything useful in there?

armanbilge · 2021-10-29T05:32:13Z

@dwijnand's advice was spot on: I removed sbt/zinc from the equation and started using the cli scala3-compiler. This made results deterministic, and much easier to minimize.

Current progress is in: https://github.com/armanbilge/schrodinger/tree/dotty/issue/13838

This is starting to get really weird: for example, there is an empty file UInt128.scala in there. If I delete it or rename it everything compiles fine. But as long as it's there, the problem persists. I suspect there are other files like that as well.

armanbilge · 2021-10-29T08:27:51Z

Ok, minimized down to 14 SLOC w/ a cats dependency, I hope this is sufficient 😅

import cats.kernel.Eq
import cats.kernel.Order
import cats.syntax.all.*

sealed abstract class Foo[A]
object Foo:
  given [A: Eq]: Eq[Foo[A]] = ???

opaque type FooT[F[_], A] = F[Foo[A]]
object FooT:
  def liftF[F[_], A](fa: F[A]): FooT[F, A] =
    fa.map(???)

  extension [F[_], A](ffa: FooT[F, A])
    def map[B](f: A => B): FooT[F, B] =
      ???
  
  given [F[_], A](using Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???

nicolasstucki · 2021-11-02T11:12:12Z

Nice minimization. But we will need to have a version that does not have dependencies. A good way to start is to just copy the parts of the cats library that are involved and then trim everything that is not used.

armanbilge · 2021-11-02T11:53:09Z

Thanks. I got it down to this, unfortunately still with a cats-kernel dependency. I don't know if I have what it takes to minimize this any further: bringing in Eq and Order from cats-kernel also needs PartialOrder, Hash, Band, and Semigroup, as well as several auto-generated boilerplate sources for tuples. This is complicated by circular dependencies (Order extends Eq, but Eq's companion object defines implicit Orders). Untangling all of that is going be a challenge.

Edit: yup, untangling this is very messy. Actually you pretty much need everything to start—Eq depends on the instances package, which itself depends on all of kernel. It's very difficult to delete stuff without working surgically.

import cats.kernel.Eq
import cats.kernel.Order

trait EqSyntax {
  implicit def catsSyntaxEq[A: Eq](a: A): EqOps[A] = ???
}

final class EqOps[A]

object eq extends EqSyntax

import eq.*

sealed abstract class Foo[A]
object Foo:
  given [A: Eq]: Eq[Foo[A]] = ???

opaque type FooT[F[_], A] = F[Foo[A]]
object FooT:
  def liftF[F[_], A](fa: F[A]): FooT[F, A] =
    fa.map(???)

  extension [F[_], A](ffa: FooT[F, A])
    def map[B](f: A => B): FooT[F, B] =
      ???
  
  given [F[_], A](using Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???

armanbilge · 2021-11-02T22:43:57Z

@nicolasstucki ok, dependency free-minimization 😅

This no longer crashes with java.lang.OutOfMemoryError or even leaks memory AFAICT. I think it's just taking a very long time to compile (minutes??). Removing some of those tuple instances speeds things up.

trait EqSyntax {
  implicit def catsSyntaxEq[A: Eq](a: A): EqOps[A] = ???
}

final class EqOps[A]

object eq extends EqSyntax

import eq.*

sealed abstract class Foo[A]
object Foo:
  given [A: Eq]: Eq[Foo[A]] = ???

opaque type FooT[F[_], A] = F[Foo[A]]
object FooT:
  def liftF[F[_], A](fa: F[A]): FooT[F, A] =
    fa.map(???)

  extension [F[_], A](ffa: FooT[F, A])
    def map[B](f: A => B): FooT[F, B] =
      ???
  
  given [F[_], A](using Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???  

trait Order[A] extends Eq[A]

trait Eq[A]

object Eq {
  implicit def catsKernelOrderForTuple1[A0](implicit A0: Order[A0]): Order[Tuple1[A0]] = ???
  implicit def catsKernelOrderForTuple2[A0, A1](implicit A0: Order[A0], A1: Order[A1]): Order[(A0, A1)] = ???
  implicit def catsKernelOrderForTuple3[A0, A1, A2](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2]): Order[(A0, A1, A2)] = ???
  implicit def catsKernelOrderForTuple4[A0, A1, A2, A3](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3]): Order[(A0, A1, A2, A3)] = ???
  implicit def catsKernelOrderForTuple5[A0, A1, A2, A3, A4](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4]): Order[(A0, A1, A2, A3, A4)] = ???
  implicit def catsKernelOrderForTuple6[A0, A1, A2, A3, A4, A5](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5]): Order[(A0, A1, A2, A3, A4, A5)] = ???
  implicit def catsKernelOrderForTuple7[A0, A1, A2, A3, A4, A5, A6](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6]): Order[(A0, A1, A2, A3, A4, A5, A6)] = ???
  implicit def catsKernelOrderForTuple8[A0, A1, A2, A3, A4, A5, A6, A7](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7]): Order[(A0, A1, A2, A3, A4, A5, A6, A7)] = ???
  implicit def catsKernelOrderForTuple9[A0, A1, A2, A3, A4, A5, A6, A7, A8](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8)] = ???
  implicit def catsKernelOrderForTuple10[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9)] = ???
  implicit def catsKernelOrderForTuple11[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10)] = ???
  implicit def catsKernelOrderForTuple12[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11)] = ???
  implicit def catsKernelOrderForTuple13[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12)] = ???
  implicit def catsKernelOrderForTuple14[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13)] = ???
  implicit def catsKernelOrderForTuple15[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14)] = ???
  implicit def catsKernelOrderForTuple16[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15)] = ???
  implicit def catsKernelOrderForTuple17[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16)] = ???
  implicit def catsKernelOrderForTuple18[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17)] = ???
  implicit def catsKernelOrderForTuple19[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18)] = ???
  implicit def catsKernelOrderForTuple20[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19)] = ???
  implicit def catsKernelOrderForTuple21[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20)] = ???
  implicit def catsKernelOrderForTuple22[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20], A21: Order[A21]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21)] = ???
}

nicolasstucki · 2021-11-03T10:20:30Z

If we only have implicit instances from catsKernelOrderForTuple1 to catsKernelOrderForTupleN the compilation time is as follows

N=0:   5 seconds
N=1:   6 seconds
N=2:   7 seconds
N=3:   8 seconds
N=4:  10 seconds
N=5:  32 seconds
N=6: 256 seconds

Seems to grow exponentially

nicolasstucki · 2021-11-03T10:52:46Z

Minimized

implicit def catsSyntaxEq[A: Eq](a: A): Foo[A] = ???

class Foo[A]
object Foo:
  given [A: Eq]: Eq[Foo[A]] = ???

object FooT:
  def liftF[F[_], A](fa: F[A]): F[Foo[A]] = map(fa)(???)

  def map[F[_], A](ffa: F[Foo[A]])(f: A): Nothing = ???

  given OrderFFooA[F[_], A](using Ord: Order[F[Foo[A]]]): Order[F[Foo[A]]] = ???

trait Eq[A]
trait Order[A] extends Eq[A]

object Eq {
  given catsKernelOrderForTuple1[A0](using A0: Order[A0]): Order[Tuple1[A0]] = ???
  given catsKernelOrderForTuple2[A0, A1](using A0: Order[A0], A1: Order[A1]): Order[(A0, A1)] = ???
  given catsKernelOrderForTuple3[A0, A1, A2](using A0: Order[A0], A1: Order[A1], A2: Order[A2]): Order[(A0, A1, A2)] = ???
  given catsKernelOrderForTuple4[A0, A1, A2, A3](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3]): Order[(A0, A1, A2, A3)] = ???
  given catsKernelOrderForTuple5[A0, A1, A2, A3, A4](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4]): Order[(A0, A1, A2, A3, A4)] = ???
  given catsKernelOrderForTuple6[A0, A1, A2, A3, A4, A5](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5]): Order[(A0, A1, A2, A3, A4, A5)] = ???
  given catsKernelOrderForTuple7[A0, A1, A2, A3, A4, A5, A6](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6]): Order[(A0, A1, A2, A3, A4, A5, A6)] = ???
  given catsKernelOrderForTuple8[A0, A1, A2, A3, A4, A5, A6, A7](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7]): Order[(A0, A1, A2, A3, A4, A5, A6, A7)] = ???
  given catsKernelOrderForTuple9[A0, A1, A2, A3, A4, A5, A6, A7, A8](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8)] = ???
  given catsKernelOrderForTuple10[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9)] = ???
  given catsKernelOrderForTuple11[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10)] = ???
  given catsKernelOrderForTuple12[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11)] = ???
  given catsKernelOrderForTuple13[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12)] = ???
  given catsKernelOrderForTuple14[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13)] = ???
  given catsKernelOrderForTuple15[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14)] = ???
  given catsKernelOrderForTuple16[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15)] = ???
  given catsKernelOrderForTuple17[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16)] = ???
  given catsKernelOrderForTuple18[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17)] = ???
  given catsKernelOrderForTuple19[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18)] = ???
  given catsKernelOrderForTuple20[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19)] = ???
  given catsKernelOrderForTuple21[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20)] = ???
  given catsKernelOrderForTuple22[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21](using A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20], A21: Order[A21]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21)] = ???
}

The following change fixes the performance issue

- implicit def catsSyntaxEq[A: Eq](a: A): Foo[A] = ???
+ given catsSyntaxEq[A: Eq]: Conversion[A, Foo[A]] = ???

Not sure if this is a compiler but or a fundamental limitation of implicit conversions that we fixed with the introduction of the Conversion type class.

Note that the program fails to compile and tries the implicit conversion with all combinations of Eq it can find.

armanbilge · 2021-11-03T15:42:35Z

Not sure if it's a fair comparison, but the following code quickly (fails to) compile with scalac 2.13.7.

package object bug {
  implicit def catsSyntaxEq[A: Eq](a: A): Foo[A] = ???

  class Foo[A]
  object Foo {
    implicit def fooEq[A: Eq]: Eq[Foo[A]] = ???
  }

  type FooT[F[_], A] = F[Foo[A]]
  object FooT {
    def liftF[F[_], A](fa: F[A]): F[Foo[A]] = map(fa)(???)

    def map[F[_], A](ffa: F[Foo[A]])(f: A): Nothing = ???
    
    implicit def fooOrder[F[_], A](implicit Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???  
  }

  trait Order[A] extends Eq[A]

  trait Eq[A]

  object Eq {
    implicit def catsKernelOrderForTuple1[A0](implicit A0: Order[A0]): Order[Tuple1[A0]] = ???
    implicit def catsKernelOrderForTuple2[A0, A1](implicit A0: Order[A0], A1: Order[A1]): Order[(A0, A1)] = ???
    implicit def catsKernelOrderForTuple3[A0, A1, A2](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2]): Order[(A0, A1, A2)] = ???
    implicit def catsKernelOrderForTuple4[A0, A1, A2, A3](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3]): Order[(A0, A1, A2, A3)] = ???
    implicit def catsKernelOrderForTuple5[A0, A1, A2, A3, A4](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4]): Order[(A0, A1, A2, A3, A4)] = ???
    implicit def catsKernelOrderForTuple6[A0, A1, A2, A3, A4, A5](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5]): Order[(A0, A1, A2, A3, A4, A5)] = ???
    implicit def catsKernelOrderForTuple7[A0, A1, A2, A3, A4, A5, A6](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6]): Order[(A0, A1, A2, A3, A4, A5, A6)] = ???
    implicit def catsKernelOrderForTuple8[A0, A1, A2, A3, A4, A5, A6, A7](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7]): Order[(A0, A1, A2, A3, A4, A5, A6, A7)] = ???
    implicit def catsKernelOrderForTuple9[A0, A1, A2, A3, A4, A5, A6, A7, A8](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8)] = ???
    implicit def catsKernelOrderForTuple10[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9)] = ???
    implicit def catsKernelOrderForTuple11[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10)] = ???
    implicit def catsKernelOrderForTuple12[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11)] = ???
    implicit def catsKernelOrderForTuple13[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12)] = ???
    implicit def catsKernelOrderForTuple14[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13)] = ???
    implicit def catsKernelOrderForTuple15[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14)] = ???
    implicit def catsKernelOrderForTuple16[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15)] = ???
    implicit def catsKernelOrderForTuple17[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16)] = ???
    implicit def catsKernelOrderForTuple18[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17)] = ???
    implicit def catsKernelOrderForTuple19[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18)] = ???
    implicit def catsKernelOrderForTuple20[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19)] = ???
    implicit def catsKernelOrderForTuple21[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20)] = ???
    implicit def catsKernelOrderForTuple22[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13], A14: Order[A14], A15: Order[A15], A16: Order[A16], A17: Order[A17], A18: Order[A18], A19: Order[A19], A20: Order[A20], A21: Order[A21]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21)] = ???
  }
}

foo.scala:11: error: diverging implicit expansion for type bug.package.Order[Any]
starting with method fooOrder in object FooT
    def liftF[F[_], A](fa: F[A]): F[Foo[A]] = map(fa)(???)
                                                     ^
foo.scala:11: error: no type parameters for method map: (ffa: F[bug.package.Foo[A]])(f: A): Nothing exist so that it can be applied to arguments (F[A])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : F[A]
 required: ?F[bug.package.Foo[?A]]
    def liftF[F[_], A](fa: F[A]): F[Foo[A]] = map(fa)(???)
                                              ^
foo.scala:11: error: type mismatch;
 found   : F[A(in method liftF)]
 required: F[bug.package.Foo[A(in method map)]]
    def liftF[F[_], A](fa: F[A]): F[Foo[A]] = map(fa)(???)
                                                  ^
3 errors

odersky · 2021-11-03T17:36:23Z

@armanbilge Scala 2.13 treats diverging implicits differently from Scala 3 (and in a wrong way). I fear there's not much we can do here. It's a crazy combinatorial explosion of possibilities. The best thing to do would be to drop all these implicits and provide a general Order for :* instead. But that can only work in Scala 3 of course.

I won't have the time to work on this, unfortunately. If nobody else takes this over until 30.11.2010, we will have to close the issue.

armanbilge · 2021-11-03T17:40:07Z

Thank you both. I'll raise an issue on cats about this so a workaround can be implemented there.

nicolasstucki · 2021-11-04T09:19:08Z

Cats will need to change their code to avoid hitting this combinatorial explosion. This has been reported in typelevel/cats#4035.

From our side, the only thing we could do is to find ways for users to debug their implicits.

odersky · 2021-11-05T10:35:34Z

We'll try to get some better diagnostics for that case.

Impose a configurable limit on the total number of nodes constructed during an implicit search. Fixes scala#13838

joroKr21 · 2021-11-07T17:36:25Z

~~FWIW this minimisation which is closer to the existing code in Cats doesn't fail with a diverging implicit error on Scala 2:~~

```scala trait EqSyntax { implicit def catsSyntaxEq[A: Eq](a: A): EqOps[A] = ??? }

final class EqOps[A]

object eq extends EqSyntax

import eq._

sealed abstract class Foo[A]
object Foo { implicit def foo[A: Eq]: Eq[Foo[A]] = ??? }

case class FooT[F[], A](f: F[Foo[A]])
object FooT {
def liftF[F[], A](fa: F[A]): FooT[F, A] =
map(fa)

def map[F[_], A, B](ffa: FooT[F, A])(f: A => B): FooT[F, B] =
  ???

implicit def bar[F[_], A](implicit Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???

}

trait Order[A] extends Eq[A]

trait Eq[A]

object Eq {
implicit def catsKernelOrderForTuple1[A0](implicit A0: Order[A0]): Order[Tuple1[A0]] = ???
implicit def catsKernelOrderForTuple2[A0, A1](implicit A0: Order[A0], A1: Order[A1]): Order[(A0, A1)] = ???
implicit def catsKernelOrderForTuple3[A0, A1, A2](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2]): Order[(A0, A1, A2)] = ???
implicit def catsKernelOrderForTuple4[A0, A1, A2, A3](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3]): Order[(A0, A1, A2, A3)] = ???
implicit def catsKernelOrderForTuple5[A0, A1, A2, A3, A4](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4]): Order[(A0, A1, A2, A3, A4)] = ???
implicit def catsKernelOrderForTuple6[A0, A1, A2, A3, A4, A5](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5]): Order[(A0, A1, A2, A3, A4, A5)] = ???
implicit def catsKernelOrderForTuple7[A0, A1, A2, A3, A4, A5, A6](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6]): Order[(A0, A1, A2, A3, A4, A5, A6)] = ???
implicit def catsKernelOrderForTuple8[A0, A1, A2, A3, A4, A5, A6, A7](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7]): Order[(A0, A1, A2, A3, A4, A5, A6, A7)] = ???
implicit def catsKernelOrderForTuple9[A0, A1, A2, A3, A4, A5, A6, A7, A8](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8)] = ???
implicit def catsKernelOrderForTuple10[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9)] = ???
implicit def catsKernelOrderForTuple11[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10)] = ???
implicit def catsKernelOrderForTuple12[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11)] = ???
implicit def catsKernelOrderForTuple13[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12)] = ???
implicit def catsKernelOrderForTuple14[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13)] = ???
}


But with a type mismatch error:
```scala
             map(fa)
                 ^
On line 18: error: type mismatch;
        found   : F[A]
        required: TooSlow.FooT[?,?]
           implicit def catsSyntaxEq[A: Eq](a: A): EqOps[A] = ???

Scratch that, the type alias is the crucial part - my bad.

~~I think we should be able to avoid expanding the implicit conversion because it returns an incompatible type. Any pointers where to look for the responsible code in the Scala 3 codebase?~~

joroKr21 · 2021-11-07T18:04:52Z

Ok this time for real - minimisation which fails fast on Scala 2.13 (no diverging implicit) and takes too long on Scala 3.
Scala 2 doesn't have opaque types so of course the following tautological definition was causing a diverging implicit error: implicit def f[F[_], A](implicit Ord: Order[F[Foo[A]]]): Order[FooT[F, A]] = ???

object TooSlow {
  trait EqSyntax {
    implicit def catsSyntaxEq[A: Eq](a: A): EqOps[A] = ???
  }

  final class EqOps[A]

  object eq extends EqSyntax

  import eq._

  sealed abstract class Foo[A]
  object Foo {
    implicit def eqFoo[A: Eq]: Eq[Foo[A]] = ???
  }

  type FooT[F[_], A] = F[Foo[A]]
  object FooT {
    def liftF[F[_], A](fa: F[A]): F[Foo[A]] =
      map(fa)(???)

    def map[F[_], A, B](ffa: F[Foo[A]])(f: A => B): F[Foo[B]] =
      ???
  }

  trait Order[A] extends Eq[A]

  trait Eq[A]

  object Eq {
    implicit def catsKernelOrderForTuple14[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12], A13: Order[A13]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13)] = ???
    implicit def catsKernelOrderForTuple13[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11], A12: Order[A12]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12)] = ???
    implicit def catsKernelOrderForTuple12[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10], A11: Order[A11]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11)] = ???
    implicit def catsKernelOrderForTuple11[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9], A10: Order[A10]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10)] = ???
    implicit def catsKernelOrderForTuple10[A0, A1, A2, A3, A4, A5, A6, A7, A8, A9](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8], A9: Order[A9]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8, A9)] = ???
    implicit def catsKernelOrderForTuple9[A0, A1, A2, A3, A4, A5, A6, A7, A8](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7], A8: Order[A8]): Order[(A0, A1, A2, A3, A4, A5, A6, A7, A8)] = ???
    implicit def catsKernelOrderForTuple8[A0, A1, A2, A3, A4, A5, A6, A7](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6], A7: Order[A7]): Order[(A0, A1, A2, A3, A4, A5, A6, A7)] = ???
    implicit def catsKernelOrderForTuple7[A0, A1, A2, A3, A4, A5, A6](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5], A6: Order[A6]): Order[(A0, A1, A2, A3, A4, A5, A6)] = ???
    implicit def catsKernelOrderForTuple6[A0, A1, A2, A3, A4, A5](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4], A5: Order[A5]): Order[(A0, A1, A2, A3, A4, A5)] = ???
    implicit def catsKernelOrderForTuple5[A0, A1, A2, A3, A4](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3], A4: Order[A4]): Order[(A0, A1, A2, A3, A4)] = ???
    implicit def catsKernelOrderForTuple4[A0, A1, A2, A3](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2], A3: Order[A3]): Order[(A0, A1, A2, A3)] = ???
    implicit def catsKernelOrderForTuple3[A0, A1, A2](implicit A0: Order[A0], A1: Order[A1], A2: Order[A2]): Order[(A0, A1, A2)] = ???
    implicit def catsKernelOrderForTuple2[A0, A1](implicit A0: Order[A0], A1: Order[A1]): Order[(A0, A1)] = ???
    implicit def catsKernelOrderForTuple1[A0](implicit A0: Order[A0]): Order[Tuple1[A0]] = ???
  }

}

joroKr21 · 2021-11-07T19:05:09Z

My intuition from Scala 2 is that inside the method:

def liftF[F[_], A](fa: F[A]): F[Foo[A]] =
      map(fa)(???)

F and A are skolems and there is no matching Eq[F[A]] anywhere in scope. There is no point in trying any of the tuple implicits because they return tuples, not F[A] (which is fixed inside the method).

joroKr21 · 2021-11-08T09:04:16Z

@odersky btw - we don't need the implicit method. The same issue can be reproduced if we make catsSyntaxEq a normal method and call map(catsSyntaxEq(fa))(???) explicitly. I tried to debug last night and I noticed that a the inferred type argument ends up as catsSyntaxEq[Foo[A]](fa) which is not compatible with fa. The type variable instance is committed here:
https://github.com/lampepfl/dotty/blob/master/compiler/src/dotty/tools/dotc/typer/Applications.scala#L980
So we know that type checking has already failed but we still do the implicit search.
I think we should bail already then and there to avoid doing the extra work.
But I struggle to tell what is the correct way to do it.

odersky · 2021-11-09T21:09:59Z

I found a way to make the original test cases work without the search limit, by improving the way we recognize underspecified queries. The search limit is still there since there are other test cases where we need it.

Impose a configurable limit on the total number of nodes constructed during an implicit search. Fixes scala#13838

armanbilge added the itype:bug label Oct 28, 2021

armanbilge changed the title ~~Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "classloader-cache-cleanup-0~~ Exception: java.lang.OutOfMemoryError Oct 28, 2021

nicolasstucki added the stat:needs minimization Needs a self contained minimization label Oct 28, 2021

nicolasstucki removed the stat:needs minimization Needs a self contained minimization label Nov 3, 2021

nicolasstucki assigned odersky Nov 3, 2021

odersky removed their assignment Nov 3, 2021

armanbilge mentioned this issue Nov 3, 2021

Implicit conversions + tuple instances cause combinatorial explosion in Scala 3 typelevel/cats#4035

Closed

nicolasstucki removed the itype:bug label Nov 4, 2021

nicolasstucki changed the title ~~Exception: java.lang.OutOfMemoryError~~ Exception: java.lang.OutOfMemoryError (diverging implicits) Nov 4, 2021

nicolasstucki added the itype:enhancement label Nov 4, 2021

odersky added a commit to dotty-staging/dotty that referenced this issue Nov 5, 2021

Impose implicit search limit

34ee767

Impose a configurable limit on the total number of nodes constructed during an implicit search. Fixes scala#13838

odersky mentioned this issue Nov 5, 2021

Impose implicit search limit #13886

Merged

odersky closed this as completed in #13886 Nov 9, 2021

smarter mentioned this issue Jan 24, 2022

Compilation is very slow on some files due to implicit search repeatedly diverging #14333

Closed

olsdavis pushed a commit to olsdavis/dotty that referenced this issue Apr 4, 2022

Impose implicit search limit

399c3d1

Impose a configurable limit on the total number of nodes constructed during an implicit search. Fixes scala#13838

Kordyjan added this to the 3.1.2 milestone Aug 2, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

`Exception: java.lang.OutOfMemoryError` (diverging implicits) #13838

`Exception: java.lang.OutOfMemoryError` (diverging implicits) #13838

armanbilge commented Oct 28, 2021

SethTisue commented Oct 28, 2021

armanbilge commented Oct 28, 2021 •

edited

Loading

dwijnand commented Oct 28, 2021

armanbilge commented Oct 28, 2021

armanbilge commented Oct 29, 2021

armanbilge commented Oct 29, 2021 •

edited

Loading

nicolasstucki commented Nov 2, 2021

armanbilge commented Nov 2, 2021 •

edited

Loading

armanbilge commented Nov 2, 2021 •

edited

Loading

nicolasstucki commented Nov 3, 2021 •

edited

Loading

nicolasstucki commented Nov 3, 2021

armanbilge commented Nov 3, 2021

odersky commented Nov 3, 2021

armanbilge commented Nov 3, 2021

nicolasstucki commented Nov 4, 2021

odersky commented Nov 5, 2021

joroKr21 commented Nov 7, 2021 •

edited

Loading

joroKr21 commented Nov 7, 2021

joroKr21 commented Nov 7, 2021

joroKr21 commented Nov 8, 2021

odersky commented Nov 9, 2021

Exception: java.lang.OutOfMemoryError (diverging implicits) #13838

Exception: java.lang.OutOfMemoryError (diverging implicits) #13838

Comments

armanbilge commented Oct 28, 2021

Compiler version

Minimized code

Output

Expectation

SethTisue commented Oct 28, 2021

armanbilge commented Oct 28, 2021 • edited Loading

dwijnand commented Oct 28, 2021

armanbilge commented Oct 28, 2021

armanbilge commented Oct 29, 2021

armanbilge commented Oct 29, 2021 • edited Loading

nicolasstucki commented Nov 2, 2021

armanbilge commented Nov 2, 2021 • edited Loading

armanbilge commented Nov 2, 2021 • edited Loading

nicolasstucki commented Nov 3, 2021 • edited Loading

nicolasstucki commented Nov 3, 2021

armanbilge commented Nov 3, 2021

odersky commented Nov 3, 2021

armanbilge commented Nov 3, 2021

nicolasstucki commented Nov 4, 2021

odersky commented Nov 5, 2021

joroKr21 commented Nov 7, 2021 • edited Loading

joroKr21 commented Nov 7, 2021

joroKr21 commented Nov 7, 2021

joroKr21 commented Nov 8, 2021

odersky commented Nov 9, 2021

`Exception: java.lang.OutOfMemoryError` (diverging implicits) #13838

`Exception: java.lang.OutOfMemoryError` (diverging implicits) #13838

armanbilge commented Oct 28, 2021 •

edited

Loading

armanbilge commented Oct 29, 2021 •

edited

Loading

armanbilge commented Nov 2, 2021 •

edited

Loading

armanbilge commented Nov 2, 2021 •

edited

Loading

nicolasstucki commented Nov 3, 2021 •

edited

Loading

joroKr21 commented Nov 7, 2021 •

edited

Loading