Opened 8 years ago

Last modified 18 months ago

#5400 new bug

GHC loops on compiling with optimizations

Reported by: noschinl Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.0.4
Keywords: Cc:
Operating System: Linux Architecture: x86_64 (amd64)
Type of failure: Compile-time crash Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


When compiling the snippet below with optimizations enabled (i.e. ghc -O test.hs), GHC does not seem to terminate. This happens with at least 7.0.3 and 7.0.4. Without optimizations, it builds fine.

data A = A Int

class C a where 
    fromHsk :: C a => a -> Int

instance C Int where 
    fromHsk = fromHsk

instance C A where 
    fromHsk (A s) = fromHsk s

main = undefined

When building this example with GHC 6.12.4, it fails with a complaint about the bogus type constraints in the declaration of fromHsk:

    All of the type variables in the constraint `C a'
    are already in scope (at least one must be universally quantified here)
        (Use -XFlexibleContexts to lift this restriction)
    When checking the class method: fromHsk :: (C a) => a -> Int
    In the class declaration for `C'

After removing these unneeded constraint (i.e. changing the declaration of fromHsk to fromHsk :: a -> Int, the snippet above builds even with GHC 7.0.4 and optimizations.

Attachments (1)

ghc-v.log (2.7 KB) - added by noschinl 8 years ago.
ghc -v -dcore-lint -O test.hs

Download all attachments as: .zip

Change History (4)

Changed 8 years ago by noschinl

Attachment: ghc-v.log added

ghc -v -dcore-lint -O test.hs

comment:1 Changed 8 years ago by simonpj

Milestone: _|_

Interesting example! This program should diverge, of course, but it should not do so at runtime. Yet it turns out to be a disguised case of GHC's well-known compile-time divergence bug (User manual 12.2.1, bullet 3).

Here is the desugaring of the program after dictionaries have become explicit:

data C a = MkC (C a -> Int)

fH :: C Int -> Int
fH x = case x of { MkC g -> g x }

fCInt :: C Int   -- The instance decl for (C Int) gives this
fCInt = MkC fH

Notice that

  • None of these definitions is recursive
  • But the data type C a has a (C a) on the left of an arrow.

Now consider evaluating

     fH fCInt

--> (inline fH)
    case fCInt of MkC g -> g fCInt

--> (inline fCInt and eliminate the case)
    fH fCInt

and so on forever...

It's a classic example of the Russell-paradox loop. The manual claims this "never happens in practice" and I guess this bug report is a counter-example! However, it's not easy to fix this particular loop; and as you found, it's not a program you want to write anyway.

See also #3872

comment:2 Changed 8 years ago by simonpj

See also #5448

comment:3 Changed 18 months ago by sgraf

Note that the reproduction lacks a {-# LANGUAGE ConstrainedClassMethods #-} to compile with GHC 8.2.1 and then compiles flawlessly with -O2.

The typical Russel's paradox example from the user's guide just crashes with a panic (similar to #5448):

ghc.exe: panic! (the 'impossible' happened)
  (GHC version 8.2.1 for x86_64-unknown-mingw32):
        Simplifier ticks exhausted
  When trying UnfoldingDone russel
  To increase the limit, use -fsimpl-tick-factor=N (default 100)
  If you need to do this, let GHC HQ know, and what factor you needed
  To see detailed counts use -ddump-simpl-stats
  Total ticks: 6361
  Call stack:
      CallStack (from HasCallStack):
        prettyCurrentCallStack, called at compiler\utils\Outputable.hs:1133:58 in ghc:Outputable
        callStackDoc, called at compiler\utils\Outputable.hs:1137:37 in ghc:Outputable
        pprPanic, called at compiler\simplCore\SimplMonad.hs:199:31 in ghc:SimplMonad

I'd advocate this to be a warning rather than a panic, but otherwise consider the whole issue fixed.

Note: See TracTickets for help on using tickets.