+section: compiler

+synopsis: Fix exponential-time desugaring of nested ``case`` expressions.

+  The scrutinee is no longer desugared a second time when recording

+  long-distance information for the pattern-match checker.

+issues: #27383 #20251

+mrs: !16203

+        <- matchWrapper (ArrowMatchCtxt match_ctxt) (Just (map Var arg_ids)) match'

+       ; ([discrim_var], matching_code) <- matchWrapper ctxt (Just [core_discrim]) matches

+  -> Maybe [CoreExpr]                  -- ^ Already-desugared scrutinee(s)

+            then addCoreScrutTmCs (concat scrs) new_vars $

+        -> Maybe [CoreExpr]

+        addTyCs, addCoreScrutTmCs, getLdiNablas,

+To achieve similar reasoning in the coverage checker:

+

+* We keep track of the set of values that can reach a particular program point

+  (often loosely refer red to as "Covered set") in 'GHC.HsToCore.Monad.dsl_nablas

+  :: LdiNablas'.

+

+* We fill that set with Covered Nablas returned by the exported checking functions,

+  which the call sites put into place with 'GHC.HsToCore.Monad.updPmNablas'.

+

+* Call sites also extend this set with facts from type-constraint dictionaries,

+  case scrutinees, etc. with the exported functions 'addTyCs' and

+  'addCoreScrutTmCs'.

+-- Regression test for #27383 (and #20251): deeply nested cases whose

+-- scrutinees are themselves cases must desugar in polynomial (not

+-- exponential) time.  With the bug the scrutinee is desugared twice at

+-- every level, so compiler allocation (tracked by this performance test)

+-- grows as O(2^n) in the nesting depth.

+module T27383 where

+

+zero :: Int

+zero = (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case (case 0 of x500 -> x500) of x499 -> x499) of x498 -> x498) of x497 -> x497) of x496 -> x496) of x495 -> x495) of x494 -> x494) of x493 -> x493) of x492 -> x492) of x491 -> x491) of x490 -> x490) of x489 -> x489) of x488 -> x488) of x487 -> x487) of x486 -> x486) of x485 -> x485) of x484 -> x484) of x483 -> x483) of x482 -> x482) of x481 -> x481) of x480 -> x480) of x479 -> x479) of x478 -> x478) of x477 -> x477) of x476 -> x476) of x475 -> x475) of x474 -> x474) of x473 -> x473) of x472 -> x472) of x471 -> x471) of x470 -> x470) of x469 -> x469) of x468 -> x468) of x467 -> x467) of x466 -> x466) of x465 -> x465) of x464 -> x464) of x463 -> x463) of x462 -> x462) of x461 -> x461) of x460 -> x460) of x459 -> x459) of x458 -> x458) of x457 -> x457) of x456 -> x456) of x455 -> x455) of x454 -> x454) of x453 -> x453) of x452 -> x452) of x451 -> x451) of x450 -> x450) of x449 -> x449) of x448 -> x448) of x447 -> x447) of x446 -> x446) of x445 -> x445) of x444 -> x444) of x443 -> x443) of x442 -> x442) of x441 -> x441) of x440 -> x440) of x439 -> x439) of x438 -> x438) of x437 -> x437) of x436 -> x436) of x435 -> x435) of x434 -> x434) of x433 -> x433) of x432 -> x432) of x431 -> x431) of x430 -> x430) of x429 -> x429) of x428 -> x428) of x427 -> x427) of x426 -> x426) of x425 -> x425) of x424 -> x424) of x423 -> x423) of x422 -> x422) of x421 -> x421) of x420 -> x420) of x419 -> x419) of x418 -> x418) of x417 -> x417) of x416 -> x416) of x415 -> x415) of x414 -> x414) of x413 -> x413) of x412 -> x412) of x411 -> x411) of x410 -> x410) of x409 -> x409) of x408 -> x408) of x407 -> x407) of x406 -> x406) of x405 -> x405) of x404 -> x404) of x403 -> x403) of x402 -> x402) of x401 -> x401) of x400 -> x400) of x399 -> x399) of x398 -> x398) of x397 -> x397) of x396 -> x396) of x395 -> x395) of x394 -> x394) of x393 -> x393) of x392 -> x392) of x391 -> x391) of x390 -> x390) of x389 -> x389) of x388 -> x388) of x387 -> x387) of x386 -> x386) of x385 -> x385) of x384 -> x384) of x383 -> x383) of x382 -> x382) of x381 -> x381) of x380 -> x380) of x379 -> x379) of x378 -> x378) of x377 -> x377) of x376 -> x376) of x375 -> x375) of x374 -> x374) of x373 -> x373) of x372 -> x372) of x371 -> x371) of x370 -> x370) of x369 -> x369) of x368 -> x368) of x367 -> x367) of x366 -> x366) of x365 -> x365) of x364 -> x364) of x363 -> x363) of x362 -> x362) of x361 -> x361) of x360 -> x360) of x359 -> x359) of x358 -> x358) of x357 -> x357) of x356 -> x356) of x355 -> x355) of x354 -> x354) of x353 -> x353) of x352 -> x352) of x351 -> x351) of x350 -> x350) of x349 -> x349) of x348 -> x348) of x347 -> x347) of x346 -> x346) of x345 -> x345) of x344 -> x344) of x343 -> x343) of x342 -> x342) of x341 -> x341) of x340 -> x340) of x339 -> x339) of x338 -> x338) of x337 -> x337) of x336 -> x336) of x335 -> x335) of x334 -> x334) of x333 -> x333) of x332 -> x332) of x331 -> x331) of x330 -> x330) of x329 -> x329) of x328 -> x328) of x327 -> x327) of x326 -> x326) of x325 -> x325) of x324 -> x324) of x323 -> x323) of x322 -> x322) of x321 -> x321) of x320 -> x320) of x319 -> x319) of x318 -> x318) of x317 -> x317) of x316 -> x316) of x315 -> x315) of x314 -> x314) of x313 -> x313) of x312 -> x312) of x311 -> x311) of x310 -> x310) of x309 -> x309) of x308 -> x308) of x307 -> x307) of x306 -> x306) of x305 -> x305) of x304 -> x304) of x303 -> x303) of x302 -> x302) of x301 -> x301) of x300 -> x300) of x299 -> x299) of x298 -> x298) of x297 -> x297) of x296 -> x296) of x295 -> x295) of x294 -> x294) of x293 -> x293) of x292 -> x292) of x291 -> x291) of x290 -> x290) of x289 -> x289) of x288 -> x288) of x287 -> x287) of x286 -> x286) of x285 -> x285) of x284 -> x284) of x283 -> x283) of x282 -> x282) of x281 -> x281) of x280 -> x280) of x279 -> x279) of x278 -> x278) of x277 -> x277) of x276 -> x276) of x275 -> x275) of x274 -> x274) of x273 -> x273) of x272 -> x272) of x271 -> x271) of x270 -> x270) of x269 -> x269) of x268 -> x268) of x267 -> x267) of x266 -> x266) of x265 -> x265) of x264 -> x264) of x263 -> x263) of x262 -> x262) of x261 -> x261) of x260 -> x260) of x259 -> x259) of x258 -> x258) of x257 -> x257) of x256 -> x256) of x255 -> x255) of x254 -> x254) of x253 -> x253) of x252 -> x252) of x251 -> x251) of x250 -> x250) of x249 -> x249) of x248 -> x248) of x247 -> x247) of x246 -> x246) of x245 -> x245) of x244 -> x244) of x243 -> x243) of x242 -> x242) of x241 -> x241) of x240 -> x240) of x239 -> x239) of x238 -> x238) of x237 -> x237) of x236 -> x236) of x235 -> x235) of x234 -> x234) of x233 -> x233) of x232 -> x232) of x231 -> x231) of x230 -> x230) of x229 -> x229) of x228 -> x228) of x227 -> x227) of x226 -> x226) of x225 -> x225) of x224 -> x224) of x223 -> x223) of x222 -> x222) of x221 -> x221) of x220 -> x220) of x219 -> x219) of x218 -> x218) of x217 -> x217) of x216 -> x216) of x215 -> x215) of x214 -> x214) of x213 -> x213) of x212 -> x212) of x211 -> x211) of x210 -> x210) of x209 -> x209) of x208 -> x208) of x207 -> x207) of x206 -> x206) of x205 -> x205) of x204 -> x204) of x203 -> x203) of x202 -> x202) of x201 -> x201) of x200 -> x200) of x199 -> x199) of x198 -> x198) of x197 -> x197) of x196 -> x196) of x195 -> x195) of x194 -> x194) of x193 -> x193) of x192 -> x192) of x191 -> x191) of x190 -> x190) of x189 -> x189) of x188 -> x188) of x187 -> x187) of x186 -> x186) of x185 -> x185) of x184 -> x184) of x183 -> x183) of x182 -> x182) of x181 -> x181) of x180 -> x180) of x179 -> x179) of x178 -> x178) of x177 -> x177) of x176 -> x176) of x175 -> x175) of x174 -> x174) of x173 -> x173) of x172 -> x172) of x171 -> x171) of x170 -> x170) of x169 -> x169) of x168 -> x168) of x167 -> x167) of x166 -> x166) of x165 -> x165) of x164 -> x164) of x163 -> x163) of x162 -> x162) of x161 -> x161) of x160 -> x160) of x159 -> x159) of x158 -> x158) of x157 -> x157) of x156 -> x156) of x155 -> x155) of x154 -> x154) of x153 -> x153) of x152 -> x152) of x151 -> x151) of x150 -> x150) of x149 -> x149) of x148 -> x148) of x147 -> x147) of x146 -> x146) of x145 -> x145) of x144 -> x144) of x143 -> x143) of x142 -> x142) of x141 -> x141) of x140 -> x140) of x139 -> x139) of x138 -> x138) of x137 -> x137) of x136 -> x136) of x135 -> x135) of x134 -> x134) of x133 -> x133) of x132 -> x132) of x131 -> x131) of x130 -> x130) of x129 -> x129) of x128 -> x128) of x127 -> x127) of x126 -> x126) of x125 -> x125) of x124 -> x124) of x123 -> x123) of x122 -> x122) of x121 -> x121) of x120 -> x120) of x119 -> x119) of x118 -> x118) of x117 -> x117) of x116 -> x116) of x115 -> x115) of x114 -> x114) of x113 -> x113) of x112 -> x112) of x111 -> x111) of x110 -> x110) of x109 -> x109) of x108 -> x108) of x107 -> x107) of x106 -> x106) of x105 -> x105) of x104 -> x104) of x103 -> x103) of x102 -> x102) of x101 -> x101) of x100 -> x100) of x99 -> x99) of x98 -> x98) of x97 -> x97) of x96 -> x96) of x95 -> x95) of x94 -> x94) of x93 -> x93) of x92 -> x92) of x91 -> x91) of x90 -> x90) of x89 -> x89) of x88 -> x88) of x87 -> x87) of x86 -> x86) of x85 -> x85) of x84 -> x84) of x83 -> x83) of x82 -> x82) of x81 -> x81) of x80 -> x80) of x79 -> x79) of x78 -> x78) of x77 -> x77) of x76 -> x76) of x75 -> x75) of x74 -> x74) of x73 -> x73) of x72 -> x72) of x71 -> x71) of x70 -> x70) of x69 -> x69) of x68 -> x68) of x67 -> x67) of x66 -> x66) of x65 -> x65) of x64 -> x64) of x63 -> x63) of x62 -> x62) of x61 -> x61) of x60 -> x60) of x59 -> x59) of x58 -> x58) of x57 -> x57) of x56 -> x56) of x55 -> x55) of x54 -> x54) of x53 -> x53) of x52 -> x52) of x51 -> x51) of x50 -> x50) of x49 -> x49) of x48 -> x48) of x47 -> x47) of x46 -> x46) of x45 -> x45) of x44 -> x44) of x43 -> x43) of x42 -> x42) of x41 -> x41) of x40 -> x40) of x39 -> x39) of x38 -> x38) of x37 -> x37) of x36 -> x36) of x35 -> x35) of x34 -> x34) of x33 -> x33) of x32 -> x32) of x31 -> x31) of x30 -> x30) of x29 -> x29) of x28 -> x28) of x27 -> x27) of x26 -> x26) of x25 -> x25) of x24 -> x24) of x23 -> x23) of x22 -> x22) of x21 -> x21) 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)

+test('T27383',

+     [collect_compiler_stats('bytes allocated', 10)],

+     compile,

+     ['-Wincomplete-patterns'])