StackOverflow probably during implicit resolution

[LPTK]

The code below never seems to finish type checking. It just hangs forever.

But when the line marked "Dotty never finishes compiling" is commented, compilation finishes.

abstract class Code_In[+T,-Ctx] {
  val eval: T
}

class Scope { outer =>
  type Ctx
  type Code[T] = T Code_In Ctx
  
  def $[T](expr: implicit (scope: Scope) => T Code_In (outer.Ctx & scope.Ctx)): T = {
    expr(outer).eval
  }  
}

object TopLevel {
  implicit object Scope extends Scope {
    type Ctx = Any
  }
  def code[T](expr: implicit Scope => T): T Code_In Any = new{val eval = expr}
}

object Main {
  
  def code[T](expr: implicit Scope => T)(implicit scope: Scope): scope.Code[T] = {
    new{ val eval = expr(scope) }
  }

  def scope(implicit scope: Scope): scope.type = scope

  def main(args: Array[String]): Unit = {
    
    TopLevel.code {
      scope.${
        var x = code{0}
        code{ scope.${
          var y = code{1}
          x: scope.Code[Int] // Dotty never finishes compiling
          ???
        }}
      }
    }
    
  }

}

Sorry, haven't had time to minimize this further. It seems related to #864

[biboudis]

Thx for reporting! This code snippet is a bit convoluted. It would be great to minimize it and update it when you have time.

BTW I get this:

java.lang.StackOverflowError while compiling /Users/bibou/Projects/dotty/tests/pos/test.scala
Exception in thread "main" java.lang.StackOverflowError
        at dotty.tools.dotc.core.Types$Type.findMember(Types.scala:703)
        at dotty.tools.dotc.core.Types$Type.memberBasedOnFlags(Types.scala:533)
        at dotty.tools.dotc.core.Types$Type.$anonfun$member$1(Types.scala:518)
        at dotty.tools.dotc.util.Stats$.track(Stats.scala:37)
        at dotty.tools.dotc.core.Types$Type.member(Types.scala:518)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.select$1(Denotations.scala:1309)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.recurSimple$1(Denotations.scala:1339)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.recurSimple$1(Denotations.scala:1336)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.recur$1(Denotations.scala:1341)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.staticRef(Denotations.scala:1343)
        at dotty.tools.dotc.core.Denotations$DenotationsBase.staticRef$(Denotations.scala:1298)
        at dotty.tools.dotc.core.Contexts$ContextBase.staticRef(Contexts.scala:576)
        at dotty.tools.dotc.core.Symbols.requiredClass(Symbols.scala:375)
        at dotty.tools.dotc.core.Symbols.requiredClass$(Symbols.scala:373)
        at dotty.tools.dotc.core.Contexts$Context.requiredClass(Contexts.scala:69)
        at dotty.tools.dotc.core.Definitions.FunctionClass(Definitions.scala:936)
        at dotty.tools.dotc.core.Definitions.FunctionType(Definitions.scala:949)
        at dotty.tools.dotc.core.Definitions.isNonDepFunctionType(Definitions.scala:1107)
        at dotty.tools.dotc.core.Definitions.isFunctionType(Definitions.scala:1112)
        at dotty.tools.dotc.core.Definitions.asImplicitFunctionType(Definitions.scala:1165)
        at dotty.tools.dotc.core.Definitions.asImplicitFunctionType(Definitions.scala:1163)
        at dotty.tools.dotc.typer.ProtoTypes$.$anonfun$normalize$1(ProtoTypes.scala:566)
        at dotty.tools.dotc.util.Stats$.track(Stats.scala:37)
        at dotty.tools.dotc.typer.ProtoTypes$.normalize(ProtoTypes.scala:544)
        at dotty.tools.dotc.typer.ProtoTypes$.$anonfun$normalize$1(ProtoTypes.scala:567)
        at dotty.tools.dotc.util.Stats$.track(Stats.scala:37)

[LPTK]

Weird, for me it just never finishes. Maybe we compiled Dotty differently and it does a tail call for me and not for you.

[Blaisorblade]

On the different crashes: I think I’ve seen such differences between Scalac and Dotty. For instance, Dotty recognizes and implements Dotty’s inline (unlike Scalac), and then some calls (IIRC like track, seen in the stack-trace) don’t consume stack frames (and some recursive calls can become recursive tail calls and then recursive loops).

[nicolasstucki]

Can be minimized to

class Scope {
  type Code
}

object Main {

  def code[T](expr: (given DummyImplicit) => T): Any = ???
  def $[T](expr: Scope => Any): T = ???

  def main(args: Array[String]): Unit = {
    code {
      ${ (scope1: Scope) => (??? : scope1.Code) }
    }
  }

}

[nicolasstucki]

Renaming the method $ to anything else fixes the issue.

Note that $ in member names is reserved for compiler generated names. As stated in https://scala-lang.org/files/archive/spec/2.12/01-lexical-syntax.html

The ‘$’ character is reserved for compiler-synthesized identifiers. User programs should not define identifiers which contain ‘$’ characters.