[GHC] #12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop

[GHC]

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into
an infinite loop
-------------------------------------+-------------------------------------
        Reporter:  RyanGlScott       |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler (Type    |              Version:  8.0.1
  checker)                           |
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Yikes that is really bad. At ''least'' we should get a context-stack
 overflow.

 But there is more, as I found when investigating:

 * At the moment if we have
 {{{
 inert:     [D] a ~ ty
 work item  [D] a ~ ty
 }}}
   we rewrite the work item with the inert to get `[D] ty ~ ty` and then
 take a series steps to decompose it.  It'd be fast to use `unifyDerived`
 for this case.

 * The reason we generate two duplicate Derived constraints is also a bit
 stupid.  Suppose we have `[W] C T a`, where class C has some fundeps, and
 `a` is a skolem of some kind.  From this we might generate a derived `[D]
 a ~ ty`.  This kicks out a derived shadow `[D] C T a` from the inerts.  We
 rewrite it to `[D] C T ty`.  ''But then we interact it with the `[W] C T
 a` in the inert set, to make another derived `[D] a ~ ty`.  What a waste
 of effort.

 But underlying all this is the question of what ''should'' happen here.
 The problem is:
 {{{
 [W] C a b
 --> [D] b ~ Foo beta1    (by fundeps, beta1 fresh unification variable)
 --> [D] C a (Foo beta1)  (rewrite)
 --> [D] C a beta1        (use instance C a b => C a (Foo b))
 }}}
 and now the cycle repeats.  With a hand-written instance decl
 {{{
 instance C a b => C a (Foo b)
 }}}
 you rightly need `UndecidableInstances`, but it's less clear what to do
 when trying to guess the instance context; fail in some way I guess.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/12860#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler