Rewrite `Coercible` solver

Summary:
This is a rewrite of the algorithm to solve for Coercible "instances".

A preliminary form of these ideas is at
https://ghc.haskell.org/trac/ghc/wiki/Design/NewCoercibleSolver

The basic idea here is that the `EqPred` constructor of `PredTree`
now is parameterised by a new type `EqRel` (where
`data EqRel = NomEq | ReprEq`). Thus, every equality constraint can
now talk about nominal equality (the usual case) or representational
equality (the `Coercible` case).

This is a change from the previous
behavior where `Coercible` was just considered a regular class with
a special case in `matchClassInst`.

Because of this change, representational equalities are now
canonicalized just like nominal ones, allowing more equalities
to be solved -- in particular, the case at the top of #9117.

A knock-on effect is that the flattener must be aware of the
choice of equality relation, because the inert set now stores
both representational inert equalities alongside the nominal
inert equalities. Of course, we can use representational equalities
to rewrite only within another representational equality --
thus the parameterization of the flattener.

A nice side effect of this change is that I've introduced a new
type `CtFlavour`, which tracks G vs. W vs. D, removing some ugliness
in the flattener.

This commit includes some refactoring as discussed on D546.
It also removes the ability of Deriveds to rewrite Deriveds.

This fixes bugs #9117 and #8984.

Reviewers: simonpj, austin, nomeata

Subscribers: carter, thomie

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

GHC Trac Issues: #9117, #8984

2 files changed, 76 insertions, 86 deletions

diff --git a/testsuite/tests/roles/should_fail/Roles10.stderr b/testsuite/tests/roles/should_fail/Roles10.stderr
index 2102298269..4275385081 100644
--- a/testsuite/tests/roles/should_fail/Roles10.stderr
+++ b/testsuite/tests/roles/should_fail/Roles10.stderr
@@ -1,10 +1,7 @@
 
 Roles10.hs:16:12:
-    Could not coerce from ‘Bool’ to ‘Char’
-      because ‘Bool’ and ‘Char’ are different types.
-      arising from the coercion of the method ‘meth’ from type
-                   ‘Int -> F Int’ to type ‘Age -> F Age’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match representation of type ‘Char’ with that of ‘Bool’
+    arising from the coercion of the method ‘meth’
+      from type ‘Int -> F Int’ to type ‘Age -> F Age’
+    Relevant role signatures: type role F nominal
     When deriving the instance for (C Age)
diff --git a/testsuite/tests/roles/should_fail/RolesIArray.stderr b/testsuite/tests/roles/should_fail/RolesIArray.stderr
index aad2f2b18a..fa9e8fe57f 100644
--- a/testsuite/tests/roles/should_fail/RolesIArray.stderr
+++ b/testsuite/tests/roles/should_fail/RolesIArray.stderr
@@ -1,100 +1,93 @@
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.unsafeAccumArray’
-        from type ‘forall e' i.
-                   Ix i =>
-                   (Word64 -> e' -> Word64)
-                   -> Word64 -> (i, i) -> [(Int, e')] -> UArray i Word64’
-          to type ‘forall e' i.
-                   Ix i =>
-                   (N -> e' -> N) -> N -> (i, i) -> [(Int, e')] -> UArray i N’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.unsafeAccumArray’
+      from type ‘forall e' i.
+                 Ix i =>
+                 (Word64 -> e' -> Word64)
+                 -> Word64 -> (i, i) -> [(Int, e')] -> UArray i Word64’
+        to type ‘forall e' i.
+                 Ix i =>
+                 (N -> e' -> N) -> N -> (i, i) -> [(Int, e')] -> UArray i N’
+    Relevant role signatures:
+      type role Ix nominal
+      type role [] representational
+      type role (,) representational representational
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.unsafeAccum’
-        from type ‘forall e' i.
-                   Ix i =>
-                   (Word64 -> e' -> Word64)
-                   -> UArray i Word64 -> [(Int, e')] -> UArray i Word64’
-          to type ‘forall e' i.
-                   Ix i =>
-                   (N -> e' -> N) -> UArray i N -> [(Int, e')] -> UArray i N’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.unsafeAccum’
+      from type ‘forall e' i.
+                 Ix i =>
+                 (Word64 -> e' -> Word64)
+                 -> UArray i Word64 -> [(Int, e')] -> UArray i Word64’
+        to type ‘forall e' i.
+                 Ix i =>
+                 (N -> e' -> N) -> UArray i N -> [(Int, e')] -> UArray i N’
+    Relevant role signatures:
+      type role Ix nominal
+      type role [] representational
+      type role (,) representational representational
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.unsafeReplace’
-        from type ‘forall i.
-                   Ix i =>
-                   UArray i Word64 -> [(Int, Word64)] -> UArray i Word64’
-          to type ‘forall i.
-                   Ix i =>
-                   UArray i N -> [(Int, N)] -> UArray i N’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.unsafeReplace’
+      from type ‘forall i.
+                 Ix i =>
+                 UArray i Word64 -> [(Int, Word64)] -> UArray i Word64’
+        to type ‘forall i. Ix i => UArray i N -> [(Int, N)] -> UArray i N’
+    Relevant role signatures:
+      type role Ix nominal
+      type role [] representational
+      type role (,) representational representational
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.unsafeAt’
-        from type ‘forall i. Ix i => UArray i Word64 -> Int -> Word64’
-          to type ‘forall i. Ix i => UArray i N -> Int -> N’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.unsafeAt’
+      from type ‘forall i. Ix i => UArray i Word64 -> Int -> Word64’
+        to type ‘forall i. Ix i => UArray i N -> Int -> N’
+    Relevant role signatures:
+      type role Ix nominal
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.unsafeArray’
-        from type ‘forall i.
-                   Ix i =>
-                   (i, i) -> [(Int, Word64)] -> UArray i Word64’
-          to type ‘forall i. Ix i => (i, i) -> [(Int, N)] -> UArray i N’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.unsafeArray’
+      from type ‘forall i.
+                 Ix i =>
+                 (i, i) -> [(Int, Word64)] -> UArray i Word64’
+        to type ‘forall i. Ix i => (i, i) -> [(Int, N)] -> UArray i N’
+    Relevant role signatures:
+      type role Ix nominal
+      type role [] representational
+      type role (,) representational representational
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘Data.Array.Base.numElements’
-        from type ‘forall i. Ix i => UArray i Word64 -> Int’
-          to type ‘forall i. Ix i => UArray i N -> Int’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘Data.Array.Base.numElements’
+      from type ‘forall i. Ix i => UArray i Word64 -> Int’
+        to type ‘forall i. Ix i => UArray i N -> Int’
+    Relevant role signatures:
+      type role Ix nominal
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)
 
 RolesIArray.hs:10:13:
-    Could not coerce from ‘UArray i Word64’ to ‘UArray i N’
-      because the second type argument of ‘UArray’ has role Nominal,
-      but the arguments ‘Word64’ and ‘N’ differ
-      arising from the coercion of the method ‘bounds’
-        from type ‘forall i. Ix i => UArray i Word64 -> (i, i)’
-          to type ‘forall i. Ix i => UArray i N -> (i, i)’
-    Possible fix:
-      use a standalone 'deriving instance' declaration,
-        so you can specify the instance context yourself
+    Couldn't match type ‘Word64’ with ‘N’
+    arising from the coercion of the method ‘bounds’
+      from type ‘forall i. Ix i => UArray i Word64 -> (i, i)’
+        to type ‘forall i. Ix i => UArray i N -> (i, i)’
+    Relevant role signatures:
+      type role Ix nominal
+      type role (,) representational representational
+      type role UArray nominal nominal
     When deriving the instance for (IArray UArray N)