## Summary Nested cases, even cases that don't scrutinise their input at all, have exponential time complexity in the desugaring step. Here's a minimal example, which takes around 4 seconds to compile on my machine: ``` zero :: Int zero = case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case 0 of x20 -> x20) of x19 -> x19) of x18 -> x18) of x17 -> x17) of x16 -> x16) of x15 -> x15) of x14 -> x14) of x13 -> x13) of x12 -> x12) of x11 -> x11) of x10 -> x10) of x9 -> x9) of x8 -> x8) of x7 -> x7) of x6 -> x6) of x5 -> x5) of x4 -> x4) of x3 -> x3) of x2 -> x2) of x1 -> x1 main :: IO () main = print zero ``` Adding more nested cases makes this even worse, and timing GHC indicates exponential growth: - 21 `case` expressions (this example) took 4.4 seconds to run `ghc -fno-code Test.hs` - 22 took 7.9 seconds - 23 took 15.6 seconds - 24 took 32.0 seconds - 25 took 65.0 seconds - 26 took 127.2 seconds Running `ghc -v` shows that almost all of this time was taken in the desugaring step, but I don't know enough about GHC's internals to narrow it down more than that. Also, it seems to use a constant amount of memory: GHC never crashes on these programs, it just takes a long time. My very uneducated guess is that the case-of-case transformation is causing massive code duplication, even though all of these case expressions have only one branch. This came up when trying to use Haskell as a target language in another compiler, where I was hoping to avoid writing optimisation passes by having GHC's simplifier do them for me. ## Steps to reproduce Run `ghc` on a file with this input. Testing on the Haskell Playground, GHC 8.8.4 seems to handle programs like this (even with more nested cases), but 8.10.7 and up all time out on this example. ## Expected behavior Something better than exponential complexity. ## Environment * GHC version used: 9.6.7 * Operating System: Ubuntu 24.04.4 LTS * System Architecture: Intel i5-1335U ## Related issues #25381 seems related, but that issue involves exponentially-larger types. In this issue, all of the types in question are just `Int` so that shouldn't be an issue here.