Opened 2 years ago

Closed 2 years ago

#14163 closed bug (fixed)

Stack Overflow with ApplicativeDo

Reported by: lippling Owned by: simonmar
Priority: high Milestone: 8.2.2
Component: Compiler Version: 8.2.1
Keywords: ApplicativeDo Cc: dfeuer
Operating System: MacOS X Architecture: x86_64 (amd64)
Type of failure: Compile-time crash or panic Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D3900
Wiki Page:

Description (last modified by bgamari)

I tried to compile one of our server applications with 8.2.1 (which compiles fine with 8.0.2).

The compilation runs smoothly, but when it reaches a specific file, the RAM usage goes up to > 20GB pretty fast on my 16GB machine and the GHC process gets terminated with a stack overflow error.

I tried to find a minimal example that causes this behavior:

#!/usr/bin/env stack
-- stack --resolver nightly-2017-08-25 script

{-# LANGUAGE ApplicativeDo #-}

x = do
    (a, _) <- undefined
    (b, _) <- undefined
    (c, _) <- undefined

main = undefined

It only happens with at least 3 of these pattern matches.

Change History (16)

comment:1 Changed 2 years ago by lippling

Description: modified (diff)

comment:2 Changed 2 years ago by simonpj

Keywords: ApplicativeDo added
Owner: set to simonmar

OK Simon M is the expert here. But I did find that if I add the following traceRn in rearrangeForApplicativeDo:

rearrangeForApplicativeDo ctxt stmts0 = do
  optimal_ado <- goptM Opt_OptimalApplicativeDo
  let stmt_tree | optimal_ado = mkStmtTreeOptimal stmts
                | otherwise = mkStmtTreeHeuristic stmts
  traceRn "rearrangeForADo" (ppr stmt_tree)    <------------------- NEW
  return_name <- lookupSyntaxName' returnMName
  pure_name   <- lookupSyntaxName' pureAName

then I get this output


That is, it seems that mkStmtTreeHeuristicgoes into a loop.

If you use -foptimal-applicative-do it works fine!

Over to you, Simon

comment:3 Changed 2 years ago by lippling

So the workarounds are:

  • Disable ApplicativeDo -OR-
  • Enable the -foptimal-applicative-do flag and have longer compile times (O(n2) vs. O(n3)) -OR-
  • Rearrange the code so that ApplicativeDo doesn't "trigger"

Am I right?

comment:4 Changed 2 years ago by bgamari

Description: modified (diff)
Milestone: 8.2.2
Priority: normalhigh

comment:5 Changed 2 years ago by simonpj

I think your summary of the workarounds is right.

comment:6 Changed 2 years ago by dfeuer

I have a pretty decent guess about the problem. We have

mkStmtTreeHeuristic :: [(ExprLStmt GhcRn, FreeVars)] -> ExprStmtTree
mkStmtTreeHeuristic [one] = StmtTreeOne one
mkStmtTreeHeuristic stmts =
  case segments stmts of
    [one] -> split one
    segs -> StmtTreeApplicative (map split segs)
  split [one] = StmtTreeOne one
  split stmts =
    StmtTreeBind (mkStmtTreeHeuristic before) (mkStmtTreeHeuristic after)
    where (before, after) = splitSegment stmts

The do block in question can't actually be split at all (all the pattern matches are strict). So I think the trick is probably to make sure before is non-empty before producing StmtTreeBind. I'll give this a whirl.

comment:7 Changed 2 years ago by dfeuer

Cc: dfeuer added

comment:8 Changed 2 years ago by dfeuer

Differential Rev(s): Phab:D3900

I have a workaround: if the splitter doesn't actually split, just pull off the first statement and the rest and form a StmtTreeBind. But I don't yet understand enough to see why we have this problem with strict patterns and not with other dependencies.

comment:9 Changed 2 years ago by Simon Peyton Jones <simonpj@…>

In 567dca6e/ghc:

Add some traceRn and (Outputable StmtTree)

I added these when investigating Trac #14163, but they'll be
useful anyway.

comment:10 Changed 2 years ago by simonmar

@lippling: there's one other workaround, which is to add a ~ to your patterns, like so:

x = do
    ~(a, _) <- undefined
    ~(b, _) <- undefined
    ~(c, _) <- undefined

comment:11 Changed 2 years ago by lippling

@simonmar: Thanks! Good to know.

comment:12 Changed 2 years ago by George

Is this a duplicate of #14034 ?

comment:13 Changed 2 years ago by simonmar

Yes, thanks! I've closed #14034 as a dup.

comment:14 Changed 2 years ago by David Feuer <David.Feuer@…>

In 011e15aa/ghc:

Deal with unbreakable blocks in Applicative Do

The renamer wasn't able to deal with more than a couple strict
patterns in a row with `ApplicativeDo` when using the heuristic
splitter. Update it to work with them properly.

Reviewers: simonmar, austin, bgamari, hvr

Reviewed By: simonmar

Subscribers: RyanGlScott, lippling, rwbarton, thomie

GHC Trac Issues: #14163

Differential Revision:

comment:15 Changed 2 years ago by dfeuer

Status: newmerge

comment:16 Changed 2 years ago by bgamari

Resolution: fixed
Status: mergeclosed
Note: See TracTickets for help on using tickets.