Infinite loop with OutOfMemory error while inlining givens

[anatoliykmetyuk]

trait Foo { def g(x: Int): Any }

inline given f[T <: Foo] as T = ??? match {
  case x: T => x.g(10)
}

@main def Test = f

Says:

Error

-- [E007] Type Mismatch Error: ../pg/i4.scala:4:18 -----------------------------
4 |  case x: T => x.g(10)
  |               ^^^^^^^
  |               Found:    Any
  |               Required: T
  |
  |               where:    T is a type in method f with bounds <: Foo
-- Error: ../pg/i4.scala:7:17 --------------------------------------------------
7 |@main def Test = f
  |                 ^
  |                 Maximal number of successive inlines (32) exceeded,
  |                 Maybe this is caused by a recursive inline method?
  |                 You can use -Xmax-inlines to change the limit.
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:7
-- [E005] Naming Error: ../pg/i4.scala:4:7 -------------------------------------
4 |  case x: T => x.g(10)
  |       ^^^^
  |       duplicate pattern variable: x
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:4
  | This location is in code that was inlined at i4.scala:7

longer explanation available when compiling with `-explain`
three errors found
[error] Nonzero exit code returned from runner: 1
[error] (dotty-compiler / Compile / runMain) Nonzero exit code returned from runner: 1
[error] Total time: 14 s, completed Sep 23, 2019 2:41:14 PM

Also, if you replace the definition of trait Foo with the following one (notice the parameter's type of g has changed):

trait Foo { def g(x: Any): Any }

Then the output is identical – up to the line "three errors found". The compiler hangs before this line and after waiting ~30 seconds, says:

OutOfMemoryError

java.lang.OutOfMemoryError: GC overhead limit exceeded while compiling ../pg/i5.scala
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
	at dotty.tools.dotc.typer.Inliner$$anon$5$$Lambda$810/1857126088.get$Lambda(Unknown Source)
	at java.lang.invoke.LambdaForm$DMH/314265080.invokeStatic_LL_L(LambdaForm$DMH)
	at java.lang.invoke.LambdaForm$MH/1241276575.linkToTargetMethod(LambdaForm$MH)
	at dotty.tools.dotc.typer.Inliner$$anon$5.updateTermRefCounts$1(Inliner.scala:1180)
	at dotty.tools.dotc.typer.Inliner$$anon$5.traverse(Inliner.scala:1186)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1388)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1483)
	at dotty.tools.dotc.typer.Inliner$$anon$5.traverse(Inliner.scala:1191)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1380)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1483)
	at dotty.tools.dotc.typer.Inliner$$anon$5.traverse(Inliner.scala:1191)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1386)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1483)
	at dotty.tools.dotc.typer.Inliner$$anon$5.traverse(Inliner.scala:1191)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.apply$$anonfun$1(Trees.scala:1368)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator$$Lambda$525/795273218.apply(Unknown Source)
	at scala.collection.LinearSeqOps.foldLeft(LinearSeq.scala:169)
	at scala.collection.LinearSeqOps.foldLeft$(LinearSeq.scala:165)
	at scala.collection.immutable.List.foldLeft(List.scala:79)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.apply(Trees.scala:1368)
	at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1386)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1483)
	at dotty.tools.dotc.typer.Inliner$$anon$5.traverse(Inliner.scala:1191)
	at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1482)

Copy-pastable example for tests:

trait Foo { def g(x: Any): Any }

inline given f[T <: Foo]: T = ??? match {
  case x: T => x.g(10)
}

@main def Test = f

[odersky]

So, you get a recursive inlining error, but afterwards it dies with OutOfMemoryError.

[anatoliykmetyuk]

It is not quite obvious to me why recursion should take place in that scenario

[nicolasstucki]

The issue is that we are materializing a ClassTag from thin air using f itself. The starts the infinite inlining.

    final inline given def f[T >: Nothing <: foo.Foo]: T = 
      (??? match 
        {
          case foo.Foo$package.f[foo.Foo & scala.reflect.ClassTag[T]](x @ _) => 
            x.g(10)
        }
      ):T

[nicolasstucki]

In the second case we do the same on the x.g(10) and insert another inlining which triggers exponential growth of the program.

    final inline given def f[T >: Nothing <: foo.Foo]: T = 
      (??? match 
        {
          case foo.Foo$package.f[foo.Foo & scala.reflect.ClassTag[T]](x @ _) => 
            x.g(
              foo.Foo$package.f[foo.Foo & scala.util.FromDigits[Any]].fromDigits
                (
              "10")
            )
        }
      ):T

[nicolasstucki]

Similarly, the following code generates an infinite recursion at runtime.

given f[T] as T = "" match {
  case x: T => x
}

@main def Test = f