Imported From: https://issues.scala-lang.org/browse/SI-9181?orig=1
Reporter: @propensive
Affected Versions: 2.11.5
Attachments:

• graph.png (created on Feb 24, 2015 10:01:48 PM UTC, 23614 bytes)

@retronym said:
/cc @gbasler

@retronym said (edited on Feb 24, 2015 11:45:35 PM UTC):
Regressed in scala/scala@b64a5ec

@retronym said:
Related mailing list thread, including workarounds: https://groups.google.com/d/msg/scala-debate/tm3heyNHydw/0RB1oIX1D1cJ

@gbasler said:
I have prepared a fix: scala/scala#4370. It avoids the quadratic (!) runtime behavior by just giving up quicker...

The problem did not appear in 2.11.4 because it would just blow up in memory (there's a check that stops before this happens). Since this was improved recently, not the CNF translation but the solver became the bottleneck - there was no check to prevent the latter from blow up...

At the beginning I thought the translation is just quadratic but after some research I've figured out that there's one with linear space complexity - I'll give it a try...

Btw: how did you find this one? Is this produced by a code generator that produces hundreds of case classes? Is there a Scala compiler performance benchmark?

Too bad that I just missed the deadline for 2.11.6 ...

@retronym said:
The original report was on scala-debate. It was already minimized, so not sure what the motivating use case was: https://groups.google.com/d/msg/scala-debate/_udt06by3j0/TmpTLzNddCEJ

Rado Buransky (radoburansky) said:
We are generating Scala source code and that's how we ran into this problem. We have used a workaround using a Map, which is not as good as a type-checked patmat, but it's ok for us.

@gbasler said:
I'm working on some changes that will make even really big pattern matches tractable to the exhaustivity analysis, it can already check your problem (for example if I remove 2 cases, it will now complain):
gbasler/scala@65a6b0b

@gbasler said:
Here's an even better fix that can handle such big pattern matches without any problems:
scala/scala#4379