#11276 closed bug (fixed)

GHC hangs/takes an exponential amount of time with simple program

Reported by: mpickering Owned by: gkaracha
Priority: highest Milestone: 8.0.1
Component: Compiler Version: 7.10.3
Keywords: pattern checker, PatternMatchWarnings Cc: snoyberg, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1795
Wiki Page:

Description

This was discovered when trying to compile xml-conduit. Here is the standalone test case with a few comments indicating how to make it compile.

The program compiles with ghc-7.10.2 but fails with HEAD.

{-# LANGUAGE RankNTypes #-}
module Hang where
import Control.Monad
import Data.Char

data Event
  = EventBeginDocument
  | EventEndDocument
  | EventBeginDoctype
  | EventEndDoctype
  | EventInstruction
  | EventBeginElement
  | EventEndElement
  | EventContent Content
  | EventComment
  | EventCDATA

data Content
  = ContentText String
  | ContentEntity String


peek :: Monad m => Consumer a m (Maybe a)
peek = undefined

type Consumer i m r = forall o. ConduitM i o m r

tag :: forall m a b c o . Monad m =>
    ConduitM Event o m (Maybe c)
tag = do
    _ <- dropWS
    return undefined
  where
-- Add this and it works
--    dropWS :: Monad m => ConduitM Event o m (Maybe Event)
    dropWS = do
-- Swap these two lines and it works
--        let x = undefined
        x <- peek
        let isWS =
                case x of
                    -- Remove some of these and it works
                    Just EventBeginDocument -> True
                    Just EventEndDocument -> True
                    Just EventBeginDoctype{} -> True
                    Just EventEndDoctype -> True
                    Just EventInstruction{} -> True
                    Just EventBeginElement{} -> False
                    Just EventEndElement{} -> False
                    Just (EventContent (ContentText t))
                        | all isSpace t -> True
                        | otherwise -> False
                    Just (EventContent ContentEntity{}) -> False
                    Just EventComment{} -> True
                    Just EventCDATA{} -> False
                    Nothing -> False
        if isWS then dropWS else return x

-- Inlined Instances

instance Functor (ConduitM i o m) where
    fmap f (ConduitM c) = ConduitM $ \rest -> c (rest . f)

instance Applicative (ConduitM i o m) where
    pure x = ConduitM ($ x)
    {-# INLINE pure #-}
    (<*>) = ap
    {-# INLINE (<*>) #-}

instance Monad (ConduitM i o m) where
    return = pure
    ConduitM f >>= g = ConduitM $ \h -> f $ \a -> unConduitM (g a) h

instance Monad m => Functor (Pipe l i o u m) where
    fmap = liftM
    {-# INLINE fmap #-}

instance Monad m => Applicative (Pipe l i o u m) where
    pure = Done
    {-# INLINE pure #-}
    (<*>) = ap
    {-# INLINE (<*>) #-}

instance Monad m => Monad (Pipe l i o u m) where
    return = pure
    {-# INLINE return #-}

    HaveOutput p c o >>= fp = HaveOutput (p >>= fp)            c          o
    NeedInput p c    >>= fp = NeedInput  (p >=> fp)            (c >=> fp)
    Done x           >>= fp = fp x
    PipeM mp         >>= fp = PipeM      ((>>= fp) `liftM` mp)
    Leftover p i     >>= fp = Leftover   (p >>= fp)            i

newtype ConduitM i o m r = ConduitM
    { unConduitM :: forall b.
                    (r -> Pipe i i o () m b) -> Pipe i i o () m b
    }

data Pipe l i o u m r =
    HaveOutput (Pipe l i o u m r) (m ()) o
  | NeedInput (i -> Pipe l i o u m r) (u -> Pipe l i o u m r)
  | Done r
  | PipeM (m (Pipe l i o u m r))
  | Leftover (Pipe l i o u m r) l

Change History (20)

comment:1 Changed 15 months ago by mpickering

Priority: highhighest

comment:2 Changed 15 months ago by snoyberg

Cc: snoyberg added

comment:3 Changed 15 months ago by simonpj

Owner: set to gkaracha

Eek. This is another example of the new pattern-match checker falling into exponential behaviour.

Workaround: -fno-warn-overlapping-patterns -fno-warn-incomplete-patterns

We probably won't solve this for the 8.0 release candidate but one way or another we must do so for the 8.0 release.

George: here is another for your list.

Simon

Last edited 15 months ago by simonpj (previous) (diff)

comment:4 in reply to:  description Changed 15 months ago by gkaracha

Replying to mpickering:

This was discovered when trying to compile xml-conduit. Here is the standalone test case with a few comments indicating how to make it compile.

The program compiles with ghc-7.10.2 but fails with HEAD.

-- Add this and it works
--    dropWS :: Monad m => ConduitM Event o m (Maybe Event)

Thanks for the comments! If you just add the signature it really does compile? This is a bit strange, since the check runs post-typechecking so I would expect to have the same signature inferred at this point so I would not expect it to make a difference. I'll have to take a closer look, thanks :)

George

comment:5 Changed 15 months ago by mpickering

Milestone: 8.0.1

comment:6 Changed 15 months ago by mpickering

George, do you have any idea what is going on here?

comment:7 in reply to:  6 Changed 15 months ago by gkaracha

Replying to mpickering:

George, do you have any idea what is going on here?

I have been busy these days with #11195, #11303 and #11245 so I did not have enough time to look into it. Fortunately they are all done now so #11276 is my main priority now, I hope to have some feedback to give tomorrow.

comment:8 Changed 15 months ago by RyanGlScott

Cc: RyanGlScott added

comment:9 Changed 15 months ago by gkaracha

Ha, finally! It took more than I expected but I found the source: I do not understand why but GHC wraps all patterns in CoPats:

Just (EventBeginDocument |> <Event>_R)
Just (EventEndDocument   |> <Event>_R)
...

Hence, the following match of translatePat (in deSugar/Check.hs) is triggered:

  CoPat wrapper p ty -> do
    ps      <- translatePat p
    (xp,xe) <- mkPmId2FormsSM ty
    let g = mkGuard ps (HsWrap wrapper (unLoc xe))
    return [xp,g]

This means that, e.g. for the first clause, instead of the *expected*:

Just EventBeginDocument

The following is generated:

Just (d2JK (EventBeginDocument <- d2JK))

And like this, we end up with a bunch of guards which make the checker explode.

The reason I had it translated like this is that CoPats are used for data families, where we have the original and a representation type constructor. Dropping the wrapper would give a type error (while it shouldn't) because the two constructors are different so the guard translation allowed me to match against d2JK using the source type (original tyCon) and then match the guard (EventBeginDocument <- d2JK) using the internal type (representation tyCon) and avoid the mix-up.

It will need some tinkering but I think I can find a workaround.

Last edited 15 months ago by gkaracha (previous) (diff)

comment:10 Changed 15 months ago by Ben Gamari <ben@…>

In 0acdcf24/ghc:

Avoid generating guards for CoPats if possible (Addresses #11276)

When translating a `CoPat` to `PmPat` check whether the wrapper
is just a hole or a cast with refl. In these cases we can safely
drop the wrapper and generate less guard patterns. Fixes T11276.

Test Plan: validate

Reviewers: bgamari, austin

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1729

GHC Trac Issues: #11276

comment:11 in reply to:  10 Changed 15 months ago by hvr

comment:12 Changed 15 months ago by simonpj

George: short term, can we just degrade gracefully for now, and do something that doesn't blow up, at the expense of maybe reporting fewer warnings?

comment:13 Changed 15 months ago by gkaracha

Hmmm, the problem appears only with data families right now I think. Dropping the wrapper in the general case does not help because we end up with non-satisfiable constraints. We could deactivate pm checking for matches that contain CoPats but this goes beyond data families (as the original test case without the signature has shown). I am still trying some ideas but I do not know exactly how much time will I need or if they are going to work after all. What is the time frame?

comment:14 Changed 15 months ago by bgamari

Keywords: pattern checker added

comment:15 Changed 15 months ago by simonpj

Keywords: PatternMatchWarnings added

comment:16 Changed 14 months ago by simonpj

Does Phab:D1795 fix this?

comment:17 in reply to:  16 Changed 14 months ago by gkaracha

Replying to simonpj:

Does Phab:D1795 fix this?

Yes, it does. The current limits are:

test('T11276', compile_timeout_multiplier(0.01), compile, ['-fwarn-incomplete-patterns -fwarn-overlapping-patterns +RTS -M1G -RTS'])

and it passes.

comment:18 Changed 14 months ago by bgamari

Differential Rev(s): Phab:D1795
Status: newpatch

comment:19 Changed 14 months ago by Ben Gamari <ben@…>

In 28f951e/ghc:

Overhaul the Overhauled Pattern Match Checker

Overhaul the Overhauled Pattern Match Checker

* Changed the representation of Value Set Abstractions. Instead of
using a prefix tree, we now use a list of Value Vector Abstractions.
The set of constraints Delta for every Value Vector Abstraction is the
oracle state so that we solve everything only once.

* Instead of doing everything lazily, we prune at once (and in general
everything is much stricter). Hence, an example written with pattern
guards is checked in almost the same time as the equivalent with
pattern matching.

* Do not store the covered and the divergent sets at all. Since what we
only need is a yes/no (does this clause cover anything? Does it force
any thunk?) We just keep a boolean for each.

* Removed flags `-Wtoo-many-guards` and `-ffull-guard-reasoning`.
Replaced with `fmax-pmcheck-iterations=n`. Still debatable what should
the default `n` be.

* When a guard is for sure not going to contribute anything, we treat
it as such: The oracle is not called and cases `CGuard`, `UGuard` and
`DGuard` from the paper are not happening at all (the generation of a
fresh variable, the unfolding of the pattern list etc.). his combined
with the above seems to be enough to drop the memory increase for test
T783 down to 18.7%.

* Do not export function `dsPmWarn` (it is now called directly from
within `checkSingle` and `checkMatches`).

* Make `PmExprVar` hold a `Name` instead of an `Id`. The term oracle
does not handle type information so using `Id` was a waste of
time/space.

* Added testcases T11195, T11303b (data families) and T11374

The patch addresses at least the following:
Trac #11195, #11276, #11303, #11374, #11162

Test Plan: validate

Reviewers: goldfire, bgamari, hvr, austin

Subscribers: simonpj, thomie

Differential Revision: https://phabricator.haskell.org/D1795

comment:20 Changed 14 months ago by bgamari

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