search

scala / scala3

The Scala 3 compiler, also known as Dotty.
https://dotty.epfl.ch
Apache License 2.0
5.89k stars 1.06k forks source link

Recursive match type causes unhandled stack overflow #20205

Open EugeneFlesselle opened 7 months ago

EugeneFlesselle commented 7 months ago

Compiler version

3.5.0-RC1

Minimized code

type Rec[A] = A match
  case String => Array[Rec[String]]

type Json = Rec[String]
val x: Json = ???

When run with -Yforce-sbt-phases

Output (click arrow to expand)

```scala unhandled exception while running sbt-deps on tests/neg-deep-subtype/i17435.scala An unhandled exception was thrown in the compiler. Please file a crash report here: https://github.com/scala/scala3/issues/new/choose For non-enriched exceptions, compile with -Yno-enrich-error-messages. while compiling: tests/neg-deep-subtype/i17435.scala during phase: sbt-deps mode: Mode(ImplicitsEnabled) library version: version 2.13.12 compiler version: version 3.5.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-d148973 settings: -Yforce-sbt-phases true -classpath /Users/eugeneflesselle/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.12/scala-library-2.13.12.jar:/Users/eugeneflesselle/Documents/dotty/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.5.0-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.5.0-RC1-bin-SNAPSHOT.jar -d / at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) at dotty.tools.dotc.core.Types$LazyRef.ref(Types.scala:3244) at dotty.tools.dotc.core.Types$TypeMap.mapOver$$anonfun$1(Types.scala:6265) ... at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy28$1(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$3(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy28$1(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$3(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy28$1(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$3(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy28$1(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$3(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy28$1(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$3(Types.scala:6705) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6778) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) ... at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6709) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeTraverser.apply(Types.scala:6794) at dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy29$1(Types.scala:6731) at dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:6731) at dotty.tools.dotc.core.Types$TypeTraverser.traverseChildren(Types.scala:6795) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:294) at dotty.tools.dotc.sbt.ExtractDependenciesCollector$TypeDependencyTraverser.traverse(ExtractDependencies.scala:285) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.addTypeDependency(ExtractDependencies.scala:303) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse(ExtractDependencies.scala:205) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1746) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1799) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse(ExtractDependencies.scala:226) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse$$anonfun$5(ExtractDependencies.scala:224) at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15) at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10) at scala.collection.immutable.List.foreach(List.scala:333) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse(ExtractDependencies.scala:224) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1754) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1799) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse(ExtractDependencies.scala:226) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.apply(Trees.scala:1798) at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.fold$1(Trees.scala:1662) at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.apply(Trees.scala:1664) at dotty.tools.dotc.ast.Trees$Instance$TreeAccumulator.foldOver(Trees.scala:1763) at dotty.tools.dotc.ast.Trees$Instance$TreeTraverser.traverseChildren(Trees.scala:1799) at dotty.tools.dotc.sbt.ExtractDependenciesCollector.traverse(ExtractDependencies.scala:226) at dotty.tools.dotc.sbt.ExtractDependencies.run(ExtractDependencies.scala:79) at dotty.tools.dotc.core.Phases$Phase.runOn$$anonfun$1(Phases.scala:380) at scala.runtime.function.JProcedure1.apply(JProcedure1.java:15) at scala.runtime.function.JProcedure1.apply(JProcedure1.java:10) at scala.collection.immutable.List.foreach(List.scala:333) at dotty.tools.dotc.core.Phases$Phase.runOn(Phases.scala:386) at dotty.tools.dotc.Run.runPhases$1$$anonfun$1(Run.scala:319) 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:341) at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:351) at dotty.tools.dotc.Run.compileUnits$$anonfun$adapted$1(Run.scala:361) at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:69) at dotty.tools.dotc.Run.compileUnits(Run.scala:361) at dotty.tools.dotc.Run.compileSources(Run.scala:262) at dotty.tools.dotc.Run.compile(Run.scala:247) at dotty.tools.dotc.Driver.doCompile(Driver.scala:37) at dotty.tools.dotc.Driver.process(Driver.scala:199) at dotty.tools.dotc.Driver.process(Driver.scala:167) at dotty.tools.dotc.Driver.process(Driver.scala:179) at dotty.tools.dotc.Driver.main(Driver.scala:209) at dotty.tools.dotc.Main.main(Main.scala) ```

If we remove x then we get a an error as expected .. as long as we don't enable any other options. It also overflows without x in testCompilation.

dwijnand commented 3 months ago

Is the bug just a LazyRef-ignoring behaviour of ExtractDependenciesCollector$TypeDependencyTraverser? I'm not sure if there's anything upstream we can do for it.