Note [Recursive superclasses]

See #3731, #4809, #5751, #5913, #6117, #6161, which all
describe somewhat more complicated situations, but ones
encountered in practice.

See also tests tcrun020, tcrun021, tcrun033, and #11427.

THE PROBLEM --------
The problem is that it is all too easy to create a class whose
superclass is bottom when it should not be.

Consider the following (extreme) situation:
        class C a => D a where ...
        instance D [a] => D [a] where ...   (dfunD)
        instance C [a] => C [a] where ...   (dfunC)
Although this looks wrong (assume D [a] to prove D [a]), it is only a
more extreme case of what happens with recursive dictionaries, and it
can, just about, make sense because the methods do some work before
recursing.

To implement the dfunD we must generate code for the superclass C [a],
which we had better not get by superclass selection from the supplied
argument:
       dfunD :: forall a. D [a] -> D [a]
       dfunD = \d::D [a] -> MkD (scsel d) ..

Otherwise if we later encounter a situation where
we have a [Wanted] dw::D [a] we might solve it thus:
     dw := dfunD dw
Which is all fine except that now ** the superclass C is bottom **!

The instance we want is:
       dfunD :: forall a. D [a] -> D [a]
       dfunD = \d::D [a] -> MkD (dfunC (scsel d)) ...

THE SOLUTION --------
The basic solution is simple: be very careful about using superclass
selection to generate a superclass witness in a dictionary function
definition.  More precisely:

  Superclass Invariant: in every class dictionary,
                        every superclass dictionary field
                        is non-bottom

To achieve the Superclass Invariant, in a dfun definition we can
generate a guaranteed-non-bottom superclass witness from:
  (sc1) one of the dictionary arguments itself (all non-bottom)
  (sc2) an immediate superclass of a non-bottom dictionary that is
        /Paterson-smaller/ than the instance head
        See Note [The PatersonSize of a type] in GHC.Tc.Utils.TcType
  (sc3) a call of a dfun (always returns a dictionary constructor)

The tricky case is (sc2).  We proceed by induction on the size of the
(type of) the dictionary, defined by GHC.Tc.Utils.TcType.pSizeType.  Let's
suppose we are building a dictionary of size 3 (the "head"), and suppose
the Superclass Invariant holds of smaller dictionaries.  Then if we have a
smaller dictionary, its immediate superclasses will be non-bottom by
induction.

Why "Paterson-smaller"? See Note [Paterson conditions] in GHC.Tc.Validity.
We want to be sure that the superclass dictionary is smaller /for any
ground instatiation/ of the instance, so we need to account for type
variables that occur more than once, and for type families (#20666).  And
that's exactly what the Paterson conditions check!

Here is an example, taken from CmmExpr:
       class Ord r => UserOfRegs r a where ...
(i1)   instance UserOfRegs r a => UserOfRegs r (Maybe a) where
(i2)   instance (Ord r, UserOfRegs r CmmReg) => UserOfRegs r CmmExpr where

For (i1) we can get the (Ord r) superclass by selection from
(UserOfRegs r a), since it (i.e. UserOfRegs r a) is smaller than the
thing we are building, namely (UserOfRegs r (Maybe a)).

But for (i2) that isn't the case: (UserOfRegs r CmmReg) is not smaller
than the thing we are building (UserOfRegs r CmmExpr), so we can't use
the superclasses of the former.  Hence we must instead add an explicit,
and perhaps surprising, (Ord r) argument to the instance declaration.

Here's another example from #6161:

       class         Super a => Duper a  where ...
       class Duper (Maybe a) => Foo a    where ...
(i3)   instance Foo a => Duper (Maybe a) where ...
(i4)   instance                Foo Float where ...

It would be horribly wrong to define
   dfDuperMaybe :: Foo a -> Duper (Maybe a)  -- from (i3)
   dfDuperMaybe d = MkDuper (sc_sel1 (sc_sel2 d)) ...

   dfFooFloat :: Foo Float               -- from (i4)
   dfFooFloat = MkFoo (dfDuperMaybe dfFooFloat) ...

Let's expand the RHS of dfFooFloat:
   dfFooFloat = MkFoo (MkDuper (sc_sel1 (sc_sel2 dfFooFloat)) ...) ...
That superclass argument to MkDuper is bottom!

This program gets rejected because:
* When processing (i3) we need to construct a dictionary for Super
  (Maybe a), to put in the superclass field of (Duper (Maybe a)).
* We /can/ use the superclasses of (Foo a), because the latter is
  smaller than the head of the instance, namely Duper (Maybe a).
* So we know (by (sc2)) that this Duper (Maybe a) dictionary is
  non-bottom.  But because (Duper (Maybe a)) is not smaller than the
  instance head (Duper (Maybe a)), we can't take *its* superclasses.
As a result the program is rightly rejected, unless you add
(Super (Maybe a)) to the context of (i3).

Wrinkle (W1):
    (sc2) says we only get a non-bottom dict if the dict we are
    selecting from is itself non-bottom.  So in a superclass chain,
    all the dictionaries in the chain must be non-bottom.
        class C a => D3 a
        class D2 a [[Maybe b]] => D1 a b
        class D3 a             => D2 a b
        class C a => E a b
        instance D1 a b => E a [b]
    The instance needs the wanted superclass (C a).  We can get it
    by superclass selection from
       D1 a b --> D2 a [[Maybe b]] --> D3 a --> C a
    But on the way we go through the too-big (D2 a [[Maybe b]]), and
    we don't know that is non-bottom.