search

scala / scala3

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

Large enum (1000 cases) causes StackOverflowError #10174

Closed bishabosha closed 3 years ago

bishabosha commented 3 years ago

An enum with 1000 value cases will cause a crash:

Minimized code

// generated by `(1 to 1000).map(i => s"  case e$i").mkString("enum LargeEnum {\n", "\n", "\n}")`
enum LargeEnum {
  case e1
  case e2
  case e3
  case e4
  case e5
  case e6
  case e7
  case e8
  ...
  case e996
  case e997
  case e998
  case e999
  case e1000
}

Output (click arrow to expand)

```scala Exception in thread "main" java.lang.StackOverflowError at dotty.tools.dotc.transform.patmat.SpaceLogic$$Lambda$1123/0x0000000840ca8040.(Unknown Source) at dotty.tools.dotc.transform.patmat.SpaceLogic$$Lambda$1123/0x0000000840ca8040.get$Lambda(Unknown Source) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:256) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$(Space.scala:78) at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:323) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$$anonfun$2(Space.scala:256) at scala.collection.LinearSeqOps.foldLeft(LinearSeq.scala:168) at scala.collection.LinearSeqOps.foldLeft$(LinearSeq.scala:164) at scala.collection.immutable.List.foldLeft(List.scala:79) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:256) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$(Space.scala:78) at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:323) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$$anonfun$2(Space.scala:256) at scala.collection.LinearSeqOps.foldLeft(LinearSeq.scala:168) at scala.collection.LinearSeqOps.foldLeft$(LinearSeq.scala:164) at scala.collection.immutable.List.foldLeft(List.scala:79) ... at scala.collection.immutable.List.foldLeft(List.scala:79) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:256) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$(Space.scala:78) at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:323) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$$anonfun$2(Space.scala:256) at scala.collection.LinearSeqOps.foldLeft(LinearSeq.scala:168) at scala.collection.LinearSeqOps.foldLeft$(LinearSeq.scala:164) at scala.collection.immutable.List.foldLeft(List.scala:79) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:256) at dotty.tools.dotc.transform.patmat.SpaceLogic.minus$(Space.scala:78) at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:323) at dotty.tools.dotc.transform.patmat.SpaceEngine.checkRedundancy$$anonfun$1(Space.scala:905) at dotty.runtime.function.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.java:12) at scala.collection.immutable.Range.foreach(Range.scala:190) at dotty.tools.dotc.transform.patmat.SpaceEngine.checkRedundancy(Space.scala:911) at dotty.tools.dotc.transform.PatternMatcher.transformMatch(PatternMatcher.scala:46) at dotty.tools.dotc.transform.MegaPhase.goMatch(MegaPhase.scala:779) at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:369) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:429) at dotty.tools.dotc.transform.MegaPhase.mapDefDef$1(MegaPhase.scala:249) at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:252) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:427) at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:437) at dotty.tools.dotc.transform.MegaPhase.recur$3$$anonfun$1(MegaPhase.scala:442) at scala.collection.immutable.List.mapConserve(List.scala:472) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:362) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:429) at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:256) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:427) at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:437) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:362) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:429) at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:256) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:427) at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:437) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1061) at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:442) at dotty.tools.dotc.transform.MegaPhase.mapPackage$1(MegaPhase.scala:382) at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:385) at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:429) at dotty.tools.dotc.transform.MegaPhase.transformUnit(MegaPhase.scala:448) at dotty.tools.dotc.transform.MegaPhase.run(MegaPhase.scala:460) at dotty.tools.dotc.core.Phases$Phase.runOn$$anonfun$1(Phases.scala:296) at scala.collection.immutable.List.map(List.scala:246) at dotty.tools.dotc.core.Phases$Phase.runOn(Phases.scala:297) at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:185) at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15) at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10) at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323) at dotty.tools.dotc.Run.runPhases$5(Run.scala:195) at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:203) at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12) at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:67) at dotty.tools.dotc.Run.compileUnits(Run.scala:210) at dotty.tools.dotc.Run.compileUnits(Run.scala:152) at dotty.tools.repl.ReplCompiler.runCompilationUnit(ReplCompiler.scala:151) at dotty.tools.repl.ReplCompiler.compile(ReplCompiler.scala:161) at dotty.tools.repl.ReplDriver.compile(ReplDriver.scala:234) at dotty.tools.repl.ReplDriver.interpret(ReplDriver.scala:197) at dotty.tools.repl.ReplDriver.loop$1(ReplDriver.scala:130) at dotty.tools.repl.ReplDriver.runUntilQuit$$anonfun$1(ReplDriver.scala:133) at dotty.tools.repl.ReplDriver.withRedirectedOutput(ReplDriver.scala:152) at dotty.tools.repl.ReplDriver.runUntilQuit(ReplDriver.scala:133) at dotty.tools.repl.Main$.main(Main.scala:6) at dotty.tools.repl.Main.main(Main.scala) ```
abgruszecki commented 3 years ago

/cc @liufengyun

EDIT: so for clarity, I guess that this warning comes from checking pat-mat on compiler-emitted code.

I think that in pathological cases like the above, it might make sense to simply give up on detecting patmat exhaustivity, and possibly emit a warning saying as much. I know that Haskell does something like that when the GADT constraint set becomes too complicated.

liufengyun commented 3 years ago

/cc @liufengyun

EDIT: so for clarity, I guess that this warning comes from checking pat-mat on compiler-emitted code.

I think that in pathological cases like the above, it might make sense to simply give up on detecting patmat exhaustivity, and possibly emit a warning saying as much. I know that Haskell does something like that when the GADT constraint set becomes too complicated.

I think that's a good strategy to avoid hanging or crashing the compiler. For this particular case, it's also good to have a look and see if we can improve the algorithm a little bit.

smarter commented 3 years ago

scala 2 also has an analysis budget based on the formula size and recursion depth: https://github.com/scala/scala/blob/710154924085d69edda1de95bc674bbd8a89e7cd/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala#L372-L387