Large enum (1000 cases) causes StackOverflowError

[bishabosha]

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)

Exception in thread "main" java.lang.StackOverflowError
	at dotty.tools.dotc.transform.patmat.SpaceLogic$$Lambda$1123/0x0000000840ca8040.<init>(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]

/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]

/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]

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