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
    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

rearrangeForADo
  (StmtTreeBind
     (StmtTreeBind
        (StmtTreeBind
           (StmtTreeBind
              (StmtTreeBind
                 (StmtTreeBind
                    (StmtTreeBind
                       (StmtTreeBind
                          (StmtTreeBind
                             (StmtTreeBind
                                (StmtTreeBind
                                   (StmtTreeBind
                                      (StmtTreeBind
                                         (StmtTreeBind
                                            (StmtTreeBind
                                               (StmtTreeBind
                                                  (StmtTreeBind
                                                     (StmtTreeBind
                                                        (StmtTreeBind
                                                           (StmtTreeBind

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)
 where
  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
    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: https://phabricator.haskell.org/D3900

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.