Exponential growth of compilation time with number of inferred types of `List` element

[WojciechMazur]

When creating list using local values without declared types the compilation time can grow exponentially when infered types are complex. Upon creating List(...) compiler seems to be stuck TypeComparer for long time.

Compiler version

3.3.3

Minimized code

Not yet minimised, reproduction using source generator:
tl;dr

def fast: List[ServerEndpoint[Any, Future] {
   val route1 = ???
   val routeN = ???
  List[ServerEndpoint[Any, Future](route1, ..., routeN)
}
def slow: List[ServerEndpoint[Any, Future] {
   val route1 = ???
   val routeN = ???
  List(route1, ..., routeN)
}

We generate N Tapir routes without declaring explicitly their type (each of them should infer to ServerEndpoint[Any, Future]
We combine all the N routes into a List. hintType parameter controls if we'd combine them using List[ServerEndpoint[Any, Future](route1, route2, ...) or List(route1, route2, ...) in which case the compile time skyrockets

@main def GenSources(routesSize: Int, hintType: Boolean) = 
  System.err.println(s"Size=$routesSize, hintType=$hintType")
  val EndpointType = s"ServerEndpoint[Any, Future]"
  val routes = List.tabulate(routesSize)(n => s"route_$n")
  val routesDefs = routes.map{ routeName =>
    val paramType = scala.util.Random.shuffle(Array("Int", "String", "Float", "Long")).head
    val OutType = s"Out_$routeName"   
    s"""
    class $OutType
    given io.circe.Encoder[$OutType] = ???
    given io.circe.Decoder[$OutType] = ???
    given sttp.tapir.Schema[$OutType] = ???
    val $routeName = endpoint.get.in("$routeName").in(path[$paramType]("paramId")).out(jsonBody[$OutType]).serverLogicSuccess{_ =>Future{new $OutType }}
    """
  }

  val code = s"""
  //> using dep "com.softwaremill.sttp.tapir::tapir-server:1.9.11"
  //> using dep "com.softwaremill.sttp.tapir::tapir-json-circe:1.9.11"

  import scala.concurrent.* 
  import sttp.tapir.server.ServerEndpoint
  import sttp.tapir._
  import sttp.tapir.generic.auto._
  import sttp.tapir.json.circe._

  def routes(implicit ec: ExecutionContext): List[$EndpointType] = {
    ${routesDefs.mkString}
    List${if(hintType)s"[$EndpointType]" else ""}(
    ${routes.mkString(", ")}
    )
  }
  """

  println(code)

Run using

scala-cli run genSources.scala -- 100 false | scala-cli compile -O -Ystop-after:typer - `

Measures

Hinted List[T](...)

> for N in 10 20 40 80 160; do (scala-cli run genSources.scala -- $N true | time scala-cli compile -O -Ystop-after:typer - ) ; done

Size=10, hintType=true
scala-cli compile -O -Ystop-after:typer -  0.10s user 0.05s system 18% cpu 0.829 total

Size=20, hintType=true
scala-cli compile -O -Ystop-after:typer -  0.10s user 0.05s system 20% cpu 0.729 total

Size=40, hintType=true
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.05s system 20% cpu 0.799 total

Size=80, hintType=true
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.05s system 16% cpu 0.946 total

Size=160, hintType=true
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.06s system 10% cpu 1.550 total

Infered `List(...)

> for N in 10 20 40 80 160; do (scala-cli run genSources.scala -- $N false | time scala-cli compile -O -Ystop-after:typer - ) ; done
Size=10, hintType=false
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.06s system 21% cpu 0.809 total

Size=20, hintType=false
scala-cli compile -O -Ystop-after:typer -  0.10s user 0.06s system 18% cpu 0.901 total

Size=40, hintType=false
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.05s system 7% cpu 2.259 total

Size=80, hintType=false
scala-cli compile -O -Ystop-after:typer -  0.11s user 0.05s system 1% cpu 15.577 total

Size=160, hintType=false
scala-cli compile -O -Ystop-after:typer -  0.12s user 0.07s system 0% cpu 2:22.15 total

Thread stacktrace

Collected when compiler was stuck in calculating type of infered elements.

"pool-41-thread-4" #220 prio=5 os_prio=31 cpu=574386.62ms elapsed=703.63s tid=0x000000016700ee00 nid=0x15103 runnable  [0x00000002d7072000]
   java.lang.Thread.State: RUNNABLE
	at dotty.tools.dotc.util.SimpleIdentityMap$myEmpty$.apply(SimpleIdentityMap.scala:37)
	at dotty.tools.dotc.core.GadtConstraint.bounds(GadtConstraint.scala:51)
	at dotty.tools.dotc.core.TypeComparer.gadtBounds(TypeComparer.scala:122)
	at dotty.tools.dotc.core.TypeComparer.dotty$tools$dotc$core$TypeComparer$$inline$gadtBounds(TypeComparer.scala:122)
	at dotty.tools.dotc.core.TypeComparer.byGadtBounds$2(TypeComparer.scala:197)
	at dotty.tools.dotc.core.TypeComparer.compareAppliedType1$1(TypeComparer.scala:1456)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:968)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1$$anonfun$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer$$Lambda$12765/0x0000000801e58690.apply(Unknown Source)
	at scala.Function0.apply$mcZ$sp(Function0.scala:42)
	at dotty.tools.dotc.core.TypeComparer.sufficientEither(TypeComparer.scala:1883)
	at dotty.tools.dotc.core.TypeComparer.either(TypeComparer.scala:1844)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1$$anonfun$2(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer$$Lambda$12766/0x0000000801e58950.apply(Unknown Source)
	at scala.Function0.apply$mcZ$sp(Function0.scala:42)
	at dotty.tools.dotc.core.TypeComparer.sufficientEither(TypeComparer.scala:1883)
	at dotty.tools.dotc.core.TypeComparer.either(TypeComparer.scala:1844)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isNewSubType$1(TypeComparer.scala:1525)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:994)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isNewSubType$1(TypeComparer.scala:1525)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:994)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1$$anonfun$2(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer$$Lambda$12766/0x0000000801e58950.apply(Unknown Source)
	at scala.Function0.apply$mcZ$sp(Function0.scala:42)
	at dotty.tools.dotc.core.TypeComparer.sufficientEither(TypeComparer.scala:1883)
	at dotty.tools.dotc.core.TypeComparer.either(TypeComparer.scala:1844)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1$$anonfun$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer$$Lambda$12765/0x0000000801e58690.apply(Unknown Source)
	at scala.Function0.apply$mcZ$sp(Function0.scala:42)
	at dotty.tools.dotc.core.TypeComparer.sufficientEither(TypeComparer.scala:1883)
	at dotty.tools.dotc.core.TypeComparer.either(TypeComparer.scala:1844)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isNewSubType$1(TypeComparer.scala:1525)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:994)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isNewSubType$1(TypeComparer.scala:1525)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:994)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isNewSubType$1(TypeComparer.scala:1525)
	at dotty.tools.dotc.core.TypeComparer.fourthTry$1(TypeComparer.scala:994)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1$$anonfun$2(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer$$Lambda$12766/0x0000000801e58950.apply(Unknown Source)
	at scala.Function0.apply$mcZ$sp(Function0.scala:42)
	at dotty.tools.dotc.core.TypeComparer.sufficientEither(TypeComparer.scala:1883)
	at dotty.tools.dotc.core.TypeComparer.either(TypeComparer.scala:1844)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:786)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:769)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:390)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:224)
	at dotty.tools.dotc.core.TypeComparer.isSub(TypeComparer.scala:226)
	at dotty.tools.dotc.core.ConstraintHandling.op$proxy3$1(ConstraintHandling.scala:471)
	at dotty.tools.dotc.core.ConstraintHandling.isSubTypeWhenFrozen(ConstraintHandling.scala:471)
	at dotty.tools.dotc.core.ConstraintHandling.isSubTypeWhenFrozen$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.isSubTypeWhenFrozen(TypeComparer.scala:30)
	at dotty.tools.dotc.core.ConstraintHandling.isSubType(ConstraintHandling.scala:455)
	at dotty.tools.dotc.core.ConstraintHandling.isSubType$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:30)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2490)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2493)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2497)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2497)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2497)
	at dotty.tools.dotc.core.TypeComparer.mergedLub$1(TypeComparer.scala:2379)
	at dotty.tools.dotc.core.TypeComparer.lub(TypeComparer.scala:2388)
	at dotty.tools.dotc.core.TypeComparer.mergeIfSuper(TypeComparer.scala:2499)
	at dotty.tools.dotc.core.TypeComparer.mergedLub$1(TypeComparer.scala:2379)
	at dotty.tools.dotc.core.TypeComparer.lub(TypeComparer.scala:2388)
	at dotty.tools.dotc.core.TypeComparer$.lub(TypeComparer.scala:3177)
	at dotty.tools.dotc.core.Types$Type.$bar(Types.scala:1236)
	at dotty.tools.dotc.core.ConstraintHandling.op$proxy2$1(ConstraintHandling.scala:322)
	at dotty.tools.dotc.core.ConstraintHandling.addOneBound(ConstraintHandling.scala:322)
	at dotty.tools.dotc.core.ConstraintHandling.addOneBound$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.addOneBound(TypeComparer.scala:30)
	at dotty.tools.dotc.core.ConstraintHandling.addBoundTransitively(ConstraintHandling.scala:378)
	at dotty.tools.dotc.core.ConstraintHandling.addBoundTransitively$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.addBoundTransitively(TypeComparer.scala:30)
	at dotty.tools.dotc.core.ConstraintHandling.addConstraint(ConstraintHandling.scala:862)
	at dotty.tools.dotc.core.ConstraintHandling.addConstraint$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.addConstraint(TypeComparer.scala:30)
	at dotty.tools.dotc.core.TypeComparer.compareTypeParamRef$2(TypeComparer.scala:619)
	at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:629)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:552)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:504)
	at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:347)
	at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1553)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:214)
	at dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:224)
	at dotty.tools.dotc.core.TypeComparer.topLevelSubType(TypeComparer.scala:132)
	at dotty.tools.dotc.core.TypeComparer$.topLevelSubType(TypeComparer.scala:3144)
	at dotty.tools.dotc.core.Types$Type.$less$colon$less(Types.scala:1099)
	at dotty.tools.dotc.core.ConstraintHandling.widenSingle$1(ConstraintHandling.scala:659)
	at dotty.tools.dotc.core.ConstraintHandling.widenInferred(ConstraintHandling.scala:668)
	at dotty.tools.dotc.core.ConstraintHandling.widenInferred$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.widenInferred(TypeComparer.scala:30)
	at dotty.tools.dotc.core.ConstraintHandling.instanceType(ConstraintHandling.scala:708)
	at dotty.tools.dotc.core.ConstraintHandling.instanceType$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.instanceType(TypeComparer.scala:30)
	at dotty.tools.dotc.core.TypeComparer$.instanceType(TypeComparer.scala:3214)
	at dotty.tools.dotc.core.Types$TypeVar.typeToInstantiateWith(Types.scala:4931)
	at dotty.tools.dotc.core.Types$TypeVar.instantiate(Types.scala:4941)
	at dotty.tools.dotc.typer.Inferencing.tryInstantiate$1(Inferencing.scala:790)
	at dotty.tools.dotc.typer.Inferencing.doInstantiate$1(Inferencing.scala:793)
	at dotty.tools.dotc.typer.Inferencing.interpolateTypeVars(Inferencing.scala:796)
	at dotty.tools.dotc.typer.Inferencing.interpolateTypeVars$(Inferencing.scala:611)
	at dotty.tools.dotc.typer.Typer.interpolateTypeVars(Typer.scala:120)
	at dotty.tools.dotc.typer.Typer.simplify(Typer.scala:3234)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3219)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3408)
	at dotty.tools.dotc.typer.Typer.typeSelectOnTerm$1(Typer.scala:767)
	at dotty.tools.dotc.typer.Typer.typedSelect(Typer.scala:805)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3107)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3215)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3408)
	at dotty.tools.dotc.typer.Applications.realApply$1(Applications.scala:957)
	at dotty.tools.dotc.typer.Applications.typedApply(Applications.scala:1117)
	at dotty.tools.dotc.typer.Applications.typedApply$(Applications.scala:351)
	at dotty.tools.dotc.typer.Typer.typedApply(Typer.scala:120)
	at dotty.tools.dotc.typer.Typer.typedInfixOp(Typer.scala:3022)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3172)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3216)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3408)
	at dotty.tools.dotc.typer.Typer.typedBlock(Typer.scala:1204)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3140)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3216)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3408)
	at dotty.tools.dotc.typer.Typer.$anonfun$63(Typer.scala:2617)
	at dotty.tools.dotc.typer.Typer$$Lambda$12328/0x0000000801db6740.apply(Unknown Source)
	at dotty.tools.dotc.inlines.PrepareInlineable$.dropInlineIfError(PrepareInlineable.scala:256)
	at dotty.tools.dotc.typer.Typer.typedDefDef(Typer.scala:2617)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3114)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3215)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:3319)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:3365)
	at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:2809)
	at dotty.tools.dotc.typer.Typer.typedTypeOrClassDef$1(Typer.scala:3120)
	at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:3124)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3215)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:3319)
	at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:3365)
	at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:2942)
	at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:3166)
	at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:3216)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3293)
	at dotty.tools.dotc.typer.Typer.typed(Typer.scala:3297)
	at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:3408)
	at dotty.tools.dotc.typer.TyperPhase.typeCheck$$anonfun$1(TyperPhase.scala:47)
	at dotty.tools.dotc.typer.TyperPhase$$Lambda$12139/0x0000000801d4ebe8.applyVoid(Unknown Source)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at dotty.tools.dotc.core.Phases$Phase.monitor(Phases.scala:480)
	at dotty.tools.dotc.typer.TyperPhase.typeCheck(TyperPhase.scala:53)
	at dotty.tools.dotc.typer.TyperPhase.$anonfun$4(TyperPhase.scala:99)
	at dotty.tools.dotc.typer.TyperPhase$$Lambda$12136/0x0000000801d4e048.apply(Unknown Source)
	at scala.collection.Iterator$$anon$6.hasNext(Iterator.scala:479)
	at scala.collection.Iterator$$anon$9.hasNext(Iterator.scala:583)
	at scala.collection.immutable.List.prependedAll(List.scala:155)
	at scala.collection.immutable.List$.from(List.scala:684)
	at scala.collection.immutable.List$.from(List.scala:681)
	at scala.collection.IterableOps$WithFilter.map(Iterable.scala:898)
	at dotty.tools.dotc.typer.TyperPhase.runOn(TyperPhase.scala:100)
	at dotty.tools.dotc.Run.runPhases$1$$anonfun$1(Run.scala:315)
	at dotty.tools.dotc.Run$$Lambda$11901/0x0000000801cd3390.applyVoid(Unknown Source)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15)
	at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10)
	at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
	at dotty.tools.dotc.Run.runPhases$1(Run.scala:337)
	at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:350)
	at dotty.tools.dotc.Run.compileUnits$$anonfun$adapted$1(Run.scala:360)
	at dotty.tools.dotc.Run$$Lambda$11825/0x0000000801ca7b48.apply(Unknown Source)
	at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:69)
	at dotty.tools.dotc.Run.compileUnits(Run.scala:360)
	at dotty.tools.dotc.Run.compileSources(Run.scala:261)
	at dotty.tools.dotc.Run.compile(Run.scala:246)
	at dotty.tools.dotc.Driver.doCompile(Driver.scala:37)
	at dotty.tools.xsbt.CompilerBridgeDriver.run(CompilerBridgeDriver.java:141)
	- locked <0x00000004b1116808> (a dotty.tools.xsbt.CompilerBridgeDriver)
	at dotty.tools.xsbt.CompilerBridge.run(CompilerBridge.java:22)
	at sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:91)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$7(MixedAnalyzingCompiler.scala:193)
	at sbt.internal.inc.MixedAnalyzingCompiler$$Lambda$5007/0x0000000800d1cb90.apply$mcV$sp(Unknown Source)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
	at sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:248)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$4(MixedAnalyzingCompiler.scala:183)
	at sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$4$adapted(MixedAnalyzingCompiler.scala:163)
	at sbt.internal.inc.MixedAnalyzingCompiler$$Lambda$5003/0x0000000800d17b48.apply(Unknown Source)
	at sbt.internal.inc.JarUtils$.withPreviousJar(JarUtils.scala:239)
	at sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:163)
	at sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:211)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:534)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:534)
	at sbt.internal.inc.IncrementalCompilerImpl$$Lambda$3230/0x00000008009da480.apply(Unknown Source)
	at sbt.internal.inc.Incremental$.$anonfun$apply$5(Incremental.scala:179)
	at sbt.internal.inc.Incremental$.$anonfun$apply$5$adapted(Incremental.scala:177)
	at sbt.internal.inc.Incremental$$$Lambda$3237/0x00000008009e0600.apply(Unknown Source)
	at sbt.internal.inc.Incremental$$anon$2.run(Incremental.scala:463)
	at sbt.internal.inc.IncrementalCommon$CycleState.next(IncrementalCommon.scala:116)
	at sbt.internal.inc.IncrementalCommon$$anon$1.next(IncrementalCommon.scala:56)
	at sbt.internal.inc.IncrementalCommon$$anon$1.next(IncrementalCommon.scala:52)
	at sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:263)
	at sbt.internal.inc.Incremental$.$anonfun$incrementalCompile$8(Incremental.scala:418)
	at sbt.internal.inc.Incremental$$$Lambda$3273/0x00000008009f92c0.apply(Unknown Source)
	at sbt.internal.inc.Incremental$.withClassfileManager(Incremental.scala:506)
	at sbt.internal.inc.Incremental$.incrementalCompile(Incremental.scala:405)
	at sbt.internal.inc.Incremental$.apply(Incremental.scala:171)
	at sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:534)
	at sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:488)
	at sbt.internal.inc.IncrementalCompilerImpl$$Lambda$3149/0x00000008009a3a20.apply(Unknown Source)
	at sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:332)
	at sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:425)
	at sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:137)
	at sbt.Defaults$.compileIncrementalTaskImpl(Defaults.scala:2363)
	at sbt.Defaults$.$anonfun$compileIncrementalTask$2(Defaults.scala:2313)
	at sbt.Defaults$$$Lambda$3142/0x0000000800991f30.apply(Unknown Source)
	at sbt.internal.server.BspCompileTask$.$anonfun$compute$1(BspCompileTask.scala:30)
	at sbt.internal.server.BspCompileTask$$$Lambda$3144/0x00000008009a1f70.apply(Unknown Source)
	at sbt.internal.io.Retry$.apply(Retry.scala:46)
	at sbt.internal.io.Retry$.apply(Retry.scala:28)
	at sbt.internal.io.Retry$.apply(Retry.scala:23)
	at sbt.internal.server.BspCompileTask$.compute(BspCompileTask.scala:30)
	at sbt.Defaults$.$anonfun$compileIncrementalTask$1(Defaults.scala:2311)
	at sbt.Defaults$$$Lambda$880/0x00000008005095c8.apply(Unknown Source)
	at scala.Function1.$anonfun$compose$1(Function1.scala:49)
	at scala.Function1$$Lambda$344/0x00000008003a87b0.apply(Unknown Source)
	at sbt.internal.util.$tilde$greater.$anonfun$$u2219$1(TypeFunctions.scala:62)
	at sbt.internal.util.$tilde$greater$$Lambda$2693/0x00000008008cf690.apply(Unknown Source)
	at sbt.std.Transform$$anon$4.work(Transform.scala:68)
	at sbt.Execute.$anonfun$submit$2(Execute.scala:282)
	at sbt.Execute$$Lambda$2719/0x00000008008d56d0.apply(Unknown Source)
	at sbt.internal.util.ErrorHandling$.wideConvert(ErrorHandling.scala:23)
	at sbt.Execute.work(Execute.scala:291)
	at sbt.Execute.$anonfun$submit$1(Execute.scala:282)
	at sbt.Execute$$Lambda$2703/0x00000008008d27a8.apply(Unknown Source)
	at sbt.ConcurrentRestrictions$$anon$4.$anonfun$submitValid$1(ConcurrentRestrictions.scala:265)
	at sbt.ConcurrentRestrictions$$anon$4$$Lambda$2714/0x00000008008d6af8.apply(Unknown Source)
	at sbt.CompletionService$$anon$2.call(CompletionService.scala:64)
	at java.util.concurrent.FutureTask.run(java.base@17.0.7/FutureTask.java:264)
	at java.util.concurrent.Executors$RunnableAdapter.call(java.base@17.0.7/Executors.java:539)
	at java.util.concurrent.FutureTask.run(java.base@17.0.7/FutureTask.java:264)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(java.base@17.0.7/ThreadPoolExecutor.java:1136)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(java.base@17.0.7/ThreadPoolExecutor.java:635)
	at java.lang.Thread.run(java.base@17.0.7/Thread.java:833)

[Gedochao]

@WojciechMazur can you try to minimise this?

[SethTisue]

reminiscent of #12915, #7034

also somewhat reminiscent of scala/bug#10908, which also links to a number of similar bugs — I don't know if there's anything to be learned from them as the Scala 3 typer internals are so different

[WojciechMazur]

The issue seems to be mostly related to number of member types, there needs to be at least 2 different member types (can be Int and Unit), these seem to have the biggest impact on compilation time. Number of member types has no effect on Scala 2.13 compilation time

Generator for safe-contained minimisation:

import scala.util.Random

val random = Random(19907)
// We need to have at least 2 member types of different types
val paramTypes = Array("Int", "Unit" /*, "String", "Float", "Long" */)
def nextParam = paramTypes(random.between(0, paramTypes.length))

@main def GenSources(instances: Int, memberTypes: Int, hintType: Boolean) =
  System.err.println(s"Size=$instances, memberTypes=$memberTypes")
  val EndpointType = s"ServerEndpoint[Any, Option]"
  val instanceNames = List.tabulate(instances)(n => s"instance$n")
  def delimited(seq: Seq[String]) = if seq.isEmpty then "" else seq.mkString("", ", ", ",")
  val instanceDefs = instanceNames.map { routeName =>
    s"""\n    val $routeName = ServerEndpoint[${delimited(List.fill(memberTypes)(nextParam))} Any, Option]"""
  }

  val paramTypes = delimited(0.until(memberTypes).map(n => s"_T$n"))
  val maybeHint = if hintType then s"[$EndpointType]" else ""
  val code = s"""

abstract class ServerEndpoint[-R, F[_]] {
  ${0.until(memberTypes).map(n => s"type T$n").mkString("\n  ")}
}
object ServerEndpoint {
  type Full[$paramTypes -R, F[_]] =
    ServerEndpoint[R, F] { ${0.until(memberTypes).map(n => s"\n    type T$n = _T$n").mkString}
    }
  def apply[$paramTypes R, F[_]]: ServerEndpoint.Full[$paramTypes R, F] = ???
}

object Test { 
  type Route = ServerEndpoint[Any, Option]
  def routes: List[$EndpointType] = { ${instanceDefs.mkString("")}
    List${maybeHint}(${instanceNames.mkString(", ")})
  }
}
"""
  println(code)

Run using

scala-cli run genSources.scala -- 1000 3 false | time scala-cli compile - --server=false -S 3

Results for 1000 insances with 1-3 member types:

> scala-cli run genSources.scala -- 1000 1 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=1
scala-cli compile - --server=false -S 3  10.65s user 0.41s system 313% cpu 3.528 total

> scala-cli run genSources.scala -- 1000 2 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=2
scala-cli compile - --server=false -S 3  14.12s user 0.42s system 227% cpu 6.387 total

> scala-cli run genSources.scala -- 1000 3 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=3
scala-cli compile - --server=false -S 3  36.90s user 0.43s system 129% cpu 28.795 total

[odersky]

It would be good to get a self-contained minimization. I tried to run the script but got:

~/workspace/dotty/tests/new> scala-cli run GenSources.scala -- 100 false | scala-cli compile -O -Ystop-after:typer
[error] No inputs provided (expected files with .scala, .sc, .java or .md extensions, and / or directories).
Size=100, hintType=false

Also, there's still an external reference to sttp. This makes it too hard to debug for me.