Custom `Typeable` solver, that keeps track of kinds.

Summary:
This implements the new `Typeable` solver: when GHC sees `Typeable` constraints
it solves them on the spot.

The current implementation creates `TyCon` representations on the spot.

Pro: No overhead at all in code that does not use `Typeable`
Cons: Code that uses `Typeable` may create multipe `TyCon` represntations.

We have discussed an implementation where representations of `TyCons` are
computed once, in the module, where a datatype is declared.  This would
lead to more code being generated:  for a promotable datatype we need to
generate `2 + number_of_data_cons` type-constructro representations,
and we have to do that for all programs, even ones that do not intend to
use typeable.

I added code to emit warning whenevar `deriving Typeable` is encountered---
the idea being that this is not needed anymore, and shold be fixed.

Also, we allow `instance Typeable T` in .hs-boot files, but they result
in a warning, and are ignored.  This last one was to avoid breaking exisitng
code, and should become an error, eventually.

Test Plan:
1. GHC can compile itself.
2. I compiled a number of large libraries, including `lens`.
    - I had to make some small changes:
      `unordered-containers` uses internals of `TypeReps`, so I had to do a 1 line fix
    - `lens` needed one instance changed, due to a poly-kinded `Typeble` instance

3. I also run some code that uses `syb` to traverse a largish datastrucutre.
I didn't notice any signifiant performance difference between the 7.8.3 version,
and this implementation.

Reviewers: simonpj, simonmar, austin, hvr

Reviewed By: austin, hvr

Subscribers: thomie

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

GHC Trac Issues: #9858

2 files changed, 46 insertions, 26 deletions

diff --git a/docs/users_guide/flags.xml b/docs/users_guide/flags.xml
index 4bf78b6fc0..bdb783d0a6 100644
--- a/docs/users_guide/flags.xml
+++ b/docs/users_guide/flags.xml
@@ -752,7 +752,8 @@
           </row>
           <row>
             <entry><option>-XAutoDeriveTypeable</option></entry>
-            <entry>Automatically <link linkend="deriving-typeable">derive Typeable instances for every datatype and type class declaration</link>.
+            <entry>As of GHC 7.10, this option is not needed, and should
+                   not be used.  Automatically <link linkend="deriving-typeable">derive Typeable instances for every datatype and type class declaration</link>.
             Implies <option>-XDeriveDataTypeable</option>.</entry>
             <entry>dynamic</entry>
             <entry><option>-XNoAutoDeriveTypeable</option></entry>
@@ -814,7 +815,7 @@
           </row>
           <row>
             <entry><option>-XDeriveDataTypeable</option></entry>
-            <entry>Enable <link linkend="deriving-typeable">deriving for the Data and Typeable classes</link>.
+            <entry>Enable <link linkend="deriving-typeable">deriving for the Data class</link>.
               Implied by <option>-XAutoDeriveTypeable</option>.</entry>
             <entry>dynamic</entry>
             <entry><option>-XNoDeriveDataTypeable</option></entry>
@@ -1708,6 +1709,20 @@
             <entry><option>-fno-warn-partial-type-signatures</option></entry>
           </row>
 
+          <row>
+            <entry><option>-fwarn-deriving-typeable</option></entry>
+            <entry>
+              warn when encountering a request to derive an instance of
+              class <literal>Typeable</literal>. As of GHC 7.10, such
+              declarations are unnecessary and are ignored by the compiler
+              because GHC has a custom solver for discharging this type of
+              constraint.
+            </entry>
+            <entry>dynamic</entry>
+            <entry><option>-fno-warn-deriving-typeable</option></entry>
+          </row>
+
+
         </tbody>
       </tgroup>
     </informaltable>
diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml
index d98445eb5d..e8337dd559 100644
--- a/docs/users_guide/glasgow_exts.xml
+++ b/docs/users_guide/glasgow_exts.xml
@@ -4062,44 +4062,49 @@ can be mentioned in the <literal>deriving</literal> clause.
 </para></listitem>
 
 <listitem><para>
-Only derived instances of <literal>Typeable</literal> are allowed;
-i.e. handwritten instances are forbidden.  This ensures that the
-programmer cannot subert the type system by writing bogus instances.
+GHC has a custom solver for discharging constraints that involve
+class <literal>Typeable</literal>, and handwritten instances are forbidden.
+This ensures that the programmer cannot subert the type system by
+writing bogus instances.
 </para></listitem>
 
 <listitem><para>
-With <option>-XDeriveDataTypeable</option>
-GHC allows you to derive instances of <literal>Typeable</literal> for data types or newtypes,
-using a <literal>deriving</literal> clause, or using
-a standalone deriving declaration (<xref linkend="stand-alone-deriving"/>).
+Derived instances of <literal>Typeable</literal> are ignored,
+and may be reported as an error in a later version of the compiler.
 </para></listitem>
 
 <listitem><para>
-With <option>-XDataKinds</option>, deriving <literal>Typeable</literal> for a data
-type (whether via a deriving clause or standalone deriving)
-also derives <literal>Typeable</literal> for the promoted data constructors (<xref linkend="promotion"/>).
+The rules for solving `Typeable` constraints are as follows:
+<itemizedlist>
+<listitem><para>A concrete type constructor applied to some types.
+<programlisting>
+instance (Typeable t1, .., Typeable t_n) =>
+  Typeable (T t1 .. t_n)
+</programlisting>
+This rule works for any concrete type constructor, including type
+constructors with polymorhic kinds.   The only restriction is that
+if the type constructor has a polymorhic kind, then it has to be applied
+to all of its kinds parameters, and these kinds need to be concrete
+(i.e., they cannot mention kind variables).
 </para></listitem>
 
 <listitem><para>
-However, using standalone deriving, you can <emphasis>also</emphasis> derive
-a <literal>Typeable</literal> instance for a data family.
-You may not add a <literal>deriving(Typeable)</literal> clause to a
-<literal>data instance</literal> declaration; instead you must use a
-standalone deriving declaration for the data family.
+<programlisting>A type variable applied to some types.
+instance (Typeable f, Typeable t1, .., Typeable t_n) =>
+  Typeable (f t1 .. t_n)
+</programlisting>
 </para></listitem>
 
 <listitem><para>
-Using standalone deriving, you can <emphasis>also</emphasis> derive
-a <literal>Typeable</literal> instance for a type class.
+<programlisting>A concrete type literal.
+instance Typeable 0       -- Type natural literals
+instance Typeable "Hello" -- Type-level symbols
+</programlisting>
 </para></listitem>
-
-<listitem><para>
-The flag <option>-XAutoDeriveTypeable</option> triggers the generation
-of derived <literal>Typeable</literal> instances for every datatype, data family,
-and type class declaration in the module it is used, unless a manually-specified one is
-already provided.
-This flag implies <option>-XDeriveDataTypeable</option>.
+</itemizedlist>
 </para></listitem>
+
+
 </itemizedlist>
 
 </para>