Opened 22 months ago
Closed 21 months ago
#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 22 months ago by
Priority: | high → highest |
---|
comment:2 Changed 22 months ago by
Cc: | snoyberg added |
---|
comment:3 Changed 22 months ago by
Owner: | set to gkaracha |
---|
comment:4 Changed 22 months ago by
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 22 months ago by
Milestone: | → 8.0.1 |
---|
comment:7 Changed 22 months ago by
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 22 months ago by
Cc: | RyanGlScott added |
---|
comment:9 Changed 22 months ago by
Ha, finally! It took more than I expected but I found the source: I do not understand why but
GHC wraps all patterns in CoPat
s:
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 CoPat
s 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.
comment:11 Changed 22 months ago by
Replying to Ben Gamari <ben@…>:
In 0acdcf24/ghc
Merged to ghc-8.0 via c1acc2a92947f512b1a6a20019524af09266a2aa
comment:12 Changed 22 months ago by
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 22 months ago by
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 CoPat
s 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 22 months ago by
Keywords: | pattern checker added |
---|
comment:15 Changed 22 months ago by
Keywords: | PatternMatchWarnings added |
---|
comment:17 Changed 21 months ago by
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 21 months ago by
Differential Rev(s): | → Phab:D1795 |
---|---|
Status: | new → patch |
comment:20 Changed 21 months ago by
Resolution: | → fixed |
---|---|
Status: | patch → closed |
Merged to ghc-8.0
as 6e23b68047a2c995562eba173fe9485cae18bff2.
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