GHC inlines class method forever

[benmachine]

irene-knapp showed me this over IRC, I refined the test case a bit:

{-# LANGUAGE FlexibleContexts, MultiParamTypeClasses #-}
module Bug () where

class C a b where
  discord :: C a b => a b () -- Remove the constraint and it works
  rhyme :: a b ()

instance C (,) b => C (,) [b] where
  discord = discord
  rhyme = discord

GHC 7.2.2 compiling this with -O loops forever. I've worked out:

• The C a b context in the class is completely superfluous but the bug isn't triggered without it.
• The pattern of recursion in the two method signatures is fragile: rhyme = rhyme doesn't trigger the bug, for example.
• Adding a NOINLINE discord stops the bug from triggering. Similarly, compiling without optimisations doesn't trigger the bug.
• While it's looping, GHC slowly but steadily chews through all of your memory.

[hvr]

Jfyi, GHC 7.4.0.20111219 (= RC 1) shows the same misbehaviour...

[simonpj]

Thanks. This is almost identical to #5448, but even simpler. For the record, here's an even simpler example

class C a b where
   discord :: C a b => a b () -- Remove the constraint and it works

instance C (,) b => C (,) [b] where
   discord = discord

foo :: C (,) b => (,) [b] ()
foo = discord

Here is how it plays out. We get this code (in reality the MkC stuff is a newtype, but that's irrelevant):

$cd d1 d2 = discord d2 d2
discord d = case d of MkC x -> x
$fC d = MkC ($cd d)

foo d = discord ($fC d) ($fC d)

None of these definitions are recursive. So when we simplify foo we get

discord ($fC d) ($fC d)
--> (case ($fC d) of MkC x -> x) ($fC d)
--> (case (MkC ($cd d)) of MkC x -> x) ($fC d)
--> $cd d ($fC d)
--> discord ($fC d) ($fC d)

and there is the loop.

The culprit is, as usual, the data type for the dictionary, which has itself appearing contravariantly:

data C a b = MkC (C a b => a b ())

The tick-count thing means that with 5.4 we get Simplifier ticks exhausted, and adding -ddump-simpl-stats points fairly clearly to the culprit. It's fixable by adding {-# NOINLINE discord #-} on the instance declaration.

None of this is satisfactory. The difficulty is that I do not know how to solve the problem in general -- at least not without hobbling the optimiser. I suppose that we could spot the special case of a class that mentions itself in the context of a class method, but that is a very special case.