Skip to content
  • Simon Peyton Jones's avatar
    [project @ 2002-04-02 13:21:36 by simonpj] · 13878c13
    Simon Peyton Jones authored
    -----------------------------------------------------
    	Fix two nasty, subtle loops in context simplification
    	-----------------------------------------------------
    
    The context simplifier in TcSimplify was building a recursive
    dictionary, which meant the program looped when run.  The reason
    was pretty devious; in fact there are two independent causes.
    
    Cause 1
    ~~~~~~~
    Consider
     	class Eq b => Foo a b
    	instance Eq a => Foo [a] a
    If we are reducing
    	d:Foo [t] t
    we'll first deduce that it holds (via the instance decl), thus:
    	d:Foo [t] t = $fFooList deq
    	deq:Eq t = ...some rhs depending on t...
    Now we add d's superclasses.  We must not then overwrite the Eq t
    constraint with a superclass selection!!
    
    The only decent way to solve this is to track what dependencies
    a binding has; that is what the is_loop parameter to TcSimplify.addSCs
    now does.
    
    
    Cause 2
    ~~~~~~~
    This shows up when simplifying the superclass context of an
    instance declaration.  Consider
    
      class S a
    
      class S a => C a where { opc :: a -> a }
      class S b => D b where { opd :: b -> b }
    
      instance C Int where
         opc = opd
    
      instance D Int where
         opd = opc
    
    From (instance C Int) we get the constraint set {ds1:S Int, dd:D Int}
    Simplifying, we may well get:
    	$dfCInt = :C ds1 (opd dd)
    	dd  = $dfDInt
    	ds1 = $p1 dd
    Notice that we spot that we can extract ds1 from dd.
    
    Alas!  Alack! We can do the same for (instance D Int):
    
    	$dfDInt = :D ds2 (opc dc)
    	dc  = $dfCInt
    	ds2 = $p1 dc
    
    And now we've defined the superclass in terms of itself.
    
    
    Solution: treat the superclass context separately, and simplify it
    all the way down to nothing on its own.  Don't toss any 'free' parts
    out to be simplified together with other bits of context.
    
    This is done in TcInstDcls.tcSuperClasses, which is well commented.
    
    All this from a bug report from Peter White!
    13878c13