Skip to content

Large enum (1000 cases) causes StackOverflowError #10174

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
bishabosha opened this issue Nov 4, 2020 · 3 comments · Fixed by #11058
Closed

Large enum (1000 cases) causes StackOverflowError #10174

bishabosha opened this issue Nov 4, 2020 · 3 comments · Fixed by #11058
Assignees
@liufengyun
Labels
area:pattern-matching itype:bug itype:crash
Milestone
3.0.0

Comments

@bishabosha
Copy link
Member

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
Copy link
Contributor

abgruszecki commented Nov 4, 2020 •
edited
Loading

/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 liufengyun self-assigned this Nov 4, 2020
@liufengyun
Copy link
Contributor

/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
Copy link
Member

smarter commented Nov 4, 2020

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

liufengyun added a commit to dotty-staging/dotty that referenced this issue Jan 11, 2021
@liufengyun
Fix scala#10174: avoid creating deep nesting union space
bbb790f
@liufengyun liufengyun mentioned this issue Jan 11, 2021
Merged
bishabosha added a commit that referenced this issue Jan 13, 2021
@bishabosha
Merge pull request #11058 from dotty-staging/fix-10174
a5ff84a 
Fix #10174: avoid creating deep nesting union space
@bishabosha bishabosha mentioned this issue Jan 20, 2021
Merged
@Kordyjan Kordyjan added this to the 3.0.0 milestone Aug 2, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@liufengyun liufengyun

Labels
area:pattern-matching itype:bug itype:crash
Projects
None yet
Milestone
3.0.0
Development

Successfully merging a pull request may close this issue.

Fix #10174: avoid creating deep nesting union space dotty-staging/dotty
5 participants
@smarter @liufengyun @abgruszecki @Kordyjan @bishabosha