Refactor DeriveAnyClass's instance context inference

Summary:
Currently, `DeriveAnyClass` has two glaring flaws:

* It only works on classes whose argument is of kind `*` or `* -> *` (#9821).
* The way it infers constraints makes no sense. It basically co-opts the
  algorithms used to infer contexts for `Eq` (for `*`-kinded arguments) or
  `Functor` (for `(* -> *)`-kinded arguments). This tends to produce overly
  constrained instances, which in extreme cases can lead to legitimate things
  failing to typecheck (#12594). Or even worse, it can trigger GHC panics
  (#12144 and #12423).

This completely reworks the way `DeriveAnyClass` infers constraints to fix
these two issues. It now uses the type signatures of the derived class's
methods to infer constraints (and to simplify them). A high-level description
of how this works is included in the GHC users' guide, and more technical notes
on what is going on can be found as comments (and a Note) in `TcDerivInfer`.

Fixes #9821, #12144, #12423, #12594.

Test Plan: ./validate

Reviewers: dfeuer, goldfire, simonpj, austin, bgamari

Subscribers: dfeuer, thomie

Differential Revision: https://phabricator.haskell.org/D2961

2 files changed, 68 insertions, 15 deletions

diff --git a/docs/users_guide/8.2.1-notes.rst b/docs/users_guide/8.2.1-notes.rst
index a01ad1a9d5..45ed5896f5 100644
--- a/docs/users_guide/8.2.1-notes.rst
+++ b/docs/users_guide/8.2.1-notes.rst
@@ -55,6 +55,17 @@ Compiler
   class instance using the :ghc-flag:`-XDerivingStrategies` language extension
   (see :ref:`deriving-strategies`).
 
+- :ghc-flag:`-XDeriveAnyClass` is no longer limited to type classes whose
+  argument is of kind ``*`` or ``* -> *``.
+
+- The means by which :ghc-flag:`-XDeriveAnyClass` infers instance contexts has
+  been completely overhauled. The instance context is now inferred using the
+  type signatures (and default type signatures) of the derived class's methods
+  instead of using the datatype's definition, which often led to
+  overconstrained instances or instances that didn't typecheck (or worse,
+  triggered GHC panics). See the section on
+  :ref:`DeriveAnyClass <derive-any-class>` for more details.
+
 - GHC now allows standalone deriving using :ghc-flag:`-XDeriveAnyClass` on
   any data type, even if its data constructors are not in scope. This is
   consistent with the fact that this code (in the presence of
diff --git a/docs/users_guide/glasgow_exts.rst b/docs/users_guide/glasgow_exts.rst
index 50744f3e11..550bca8949 100644
--- a/docs/users_guide/glasgow_exts.rst
+++ b/docs/users_guide/glasgow_exts.rst
@@ -4185,29 +4185,71 @@ Note the following details
   class on a newtype, and :ghc-flag:`-XGeneralizedNewtypeDeriving` is also on,
   :ghc-flag:`-XDeriveAnyClass` takes precedence.
 
-- :ghc-flag:`-XDeriveAnyClass` is allowed only when the last argument of the class
-  has kind ``*`` or ``(* -> *)``.  So this is not allowed: ::
+- The instance context is determined by the type signatures of the derived
+  class's methods. For instance, if the class is: ::
 
-    data T a b = MkT a b deriving( Bifunctor )
+    class Foo a where
+      bar :: a -> String
+      default bar :: Show a => a -> String
+      bar = show
+
+      baz :: a -> a -> Bool
+      default baz :: Ord a => a -> a -> Bool
+      baz x y = compare x y == EQ
+
+  And you attempt to derive it using :ghc-flag:`-XDeriveAnyClass`: ::
+
+    instance Eq   a => Eq   (Option a) where ...
+    instance Ord  a => Ord  (Option a) where ...
+    instance Show a => Show (Option a) where ...
+
+    data Option a = None | Some a deriving Foo
+
+  Then the derived ``Foo`` instance will be: ::
+
+    instance (Show a, Ord a) => Foo (Option a)
+
+  Since the default type signatures for ``bar`` and ``baz`` require ``Show a``
+  and ``Ord a`` constraints, respectively.
+
+  Constraints on the non-default type signatures can play a role in inferring
+  the instance context as well. For example, if you have this class: ::
+
+    class HigherEq f where
+      (==#) :: f a -> f a -> Bool
+      default (==#) :: Eq (f a) => f a -> f a -> Bool
+      x ==# y = (x == y)
+
+  And you tried to derive an instance for it: ::
 
-  because the last argument of ``Bifunctor :: (* -> * -> *) -> Constraint``
-  has the wrong kind.
+    instance Eq a => Eq (Option a) where ...
+    data Option a = None | Some a deriving HigherEq
 
-- The instance context will be generated according to the same rules
-  used when deriving ``Eq`` (if the kind of the type is ``*``), or
-  the rules for ``Functor`` (if the kind of the type is ``(* -> *)``).
-  For example ::
+  Then it will fail with an error to the effect of: ::
 
-    instance C a => C (a,b) where ...
+    No instance for (Eq a)
+        arising from the 'deriving' clause of a data type declaration
 
-    data T a b = MkT a (a,b) deriving( C )
+  That is because we require an ``Eq (Option a)`` instance from the default
+  type signature for ``(==#)``, which in turn requires an ``Eq a`` instance,
+  which we don't have in scope. But if you tweak the definition of
+  ``HigherEq`` slightly: ::
 
-  The ``deriving`` clause will generate ::
+    class HigherEq f where
+      (==#) :: Eq a => f a -> f a -> Bool
+      default (==#) :: Eq (f a) => f a -> f a -> Bool
+      x ==# y = (x == y)
 
-    instance C a => C (T a b) where {}
+  Then it becomes possible to derive a ``HigherEq Option`` instance. Note that
+  the only difference is that now the non-default type signature for ``(==#)``
+  brings in an ``Eq a`` constraint. Constraints from non-default type
+  signatures never appear in the derived instance context itself, but they can
+  be used to discharge obligations that are demanded by the default type
+  signatures. In the example above, the default type signature demanded an
+  ``Eq a`` instance, and the non-default signature was able to satisfy that
+  request, so the derived instance is simply: ::
 
-  The constraints `C a` and `C (a,b)` are generated from the data
-  constructor arguments, but the latter simplifies to `C a`.
+    instance HigherEq Option
 
 - :ghc-flag:`-XDeriveAnyClass` can be used with partially applied classes,
   such as ::