Kill derived constraints

Co-authored by: Sam Derbyshire

Previously, GHC had three flavours of constraint:
Wanted, Given, and Derived. This removes Derived constraints.

Though serving a number of purposes, the most important role
of Derived constraints was to enable better error messages.
This job has been taken over by the new RewriterSets, as explained
in Note [Wanteds rewrite wanteds] in GHC.Tc.Types.Constraint.

Other knock-on effects:
 - Various new Notes as I learned about under-described bits of GHC

 - A reshuffling around the AST for implicit-parameter bindings,
   with better integration with TTG.

 - Various improvements around fundeps. These were caused by the
   fact that, previously, fundep constraints were all Derived,
   and Derived constraints would get dropped. Thus, an unsolved
   Derived didn't stop compilation. Without Derived, this is no
   longer possible, and so we have to be considerably more careful
   around fundeps.

 - A nice little refactoring in GHC.Tc.Errors to center the work
   on a new datatype called ErrorItem. Constraints are converted
   into ErrorItems at the start of processing, and this allows for
   a little preprocessing before the main classification.

 - This commit also cleans up the behavior in generalisation around
   functional dependencies. Now, if a variable is determined by
   functional dependencies, it will not be quantified. This change
   is user facing, but it should trim down GHC's strange behavior
   around fundeps.

 - Previously, reportWanteds did quite a bit of work, even on an empty
   WantedConstraints. This commit adds a fast path.

 - Now, GHC will unconditionally re-simplify constraints during
   quantification. See Note [Unconditionally resimplify constraints when
   quantifying], in GHC.Tc.Solver.

Close #18398.
Close #18406.
Solve the fundep-related non-confluence in #18851.
Close #19131.
Close #19137.
Close #20922.
Close #20668.
Close #19665.

-------------------------
Metric Decrease:
    LargeRecord
    T9872b
    T9872b_defer
    T9872d
    TcPlugin_RewritePerf
-------------------------

7 files changed, 46 insertions, 44 deletions

diff --git a/testsuite/tests/partial-sigs/should_compile/InstanceGivenOverlap3.hs b/testsuite/tests/partial-sigs/should_compile/InstanceGivenOverlap3.hs
new file mode 100644
index 0000000000..be4cd92ed9
--- /dev/null
+++ b/testsuite/tests/partial-sigs/should_compile/InstanceGivenOverlap3.hs
@@ -0,0 +1,6 @@
+{-# LANGUAGE PartialTypeSignatures, FlexibleContexts #-}
+
+module InstanceGivenOverlap3 where
+
+f :: Eq [a] => a -> _
+f x = x
diff --git a/testsuite/tests/partial-sigs/should_compile/T10403.stderr b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
index fd38a126c2..38f562a516 100644
--- a/testsuite/tests/partial-sigs/should_compile/T10403.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
@@ -15,17 +15,34 @@ T10403.hs:16:12: warning: [-Wpartial-type-signatures (in -Wdefault)]
 
 T10403.hs:20:7: warning: [-Wpartial-type-signatures (in -Wdefault)]
     • Found type wildcard ‘_’
-        standing for ‘(a1 -> a2) -> B t0 a1 -> H (B t0)’
-      Where: ‘t0’ is an ambiguous type variable
+        standing for ‘(a1 -> a2) -> f0 a1 -> H f0’
+      Where: ‘f0’ is an ambiguous type variable
              ‘a2’, ‘a1’ are rigid type variables bound by
-               the inferred type of h2 :: (a1 -> a2) -> B t0 a1 -> H (B t0)
+               the inferred type of h2 :: (a1 -> a2) -> f0 a1 -> H f0
                at T10403.hs:23:1-41
     • In the type signature: h2 :: _
 
+T10403.hs:23:15: warning: [-Wdeferred-type-errors (in -Wdefault)]
+    • Ambiguous type variable ‘f0’ arising from a use of ‘fmap’
+      prevents the constraint ‘(Functor f0)’ from being solved.
+      Relevant bindings include
+        b :: f0 a1 (bound at T10403.hs:23:6)
+        h2 :: (a1 -> a2) -> f0 a1 -> H f0 (bound at T10403.hs:23:1)
+      Probable fix: use a type annotation to specify what ‘f0’ should be.
+      Potentially matching instances:
+        instance Functor IO -- Defined in ‘GHC.Base’
+        instance Functor (B t) -- Defined at T10403.hs:11:10
+        ...plus 8 others
+        ...plus one instance involving out-of-scope types
+        (use -fprint-potential-instances to see them all)
+    • In the second argument of ‘(.)’, namely ‘fmap (const ())’
+      In the expression: (H . fmap (const ())) (fmap f b)
+      In an equation for ‘h2’: h2 f b = (H . fmap (const ())) (fmap f b)
+
 T10403.hs:29:8: warning: [-Wdeferred-type-errors (in -Wdefault)]
-    • Couldn't match type ‘t0’ with ‘t’
+    • Couldn't match type ‘f0’ with ‘B t’
       Expected: H (B t)
-        Actual: H (B t0)
+        Actual: H f0
     • because type variable ‘t’ would escape its scope
     This (rigid, skolem) type variable is bound by
       the type signature for:
diff --git a/testsuite/tests/partial-sigs/should_compile/all.T b/testsuite/tests/partial-sigs/should_compile/all.T
index e38358f88a..bb7c58a576 100644
--- a/testsuite/tests/partial-sigs/should_compile/all.T
+++ b/testsuite/tests/partial-sigs/should_compile/all.T
@@ -102,3 +102,4 @@ test('T16762d', normal, compile, [''])
 test('T14658', normal, compile, [''])
 test('T18646', normal, compile, [''])
 test('T20921', normal, compile, [''])
+test('InstanceGivenOverlap3', expect_broken(20076), compile, [''])
diff --git a/testsuite/tests/partial-sigs/should_fail/NamedWildcardsNotInMonotype.stderr b/testsuite/tests/partial-sigs/should_fail/NamedWildcardsNotInMonotype.stderr
index 423fe1b040..69128accaf 100644
--- a/testsuite/tests/partial-sigs/should_fail/NamedWildcardsNotInMonotype.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/NamedWildcardsNotInMonotype.stderr
@@ -6,6 +6,12 @@ NamedWildcardsNotInMonotype.hs:5:1: error:
                    forall {a} {w}. (Show a, Eq w, Eq a) => a -> a -> String
         at NamedWildcardsNotInMonotype.hs:5:1-33
       The type variable ‘w0’ is ambiguous
+      Potentially matching instances:
+        instance Eq Ordering -- Defined in ‘GHC.Classes’
+        instance Eq () -- Defined in ‘GHC.Classes’
+        ...plus 22 others
+        ...plus four instances involving out-of-scope types
+        (use -fprint-potential-instances to see them all)
     • In the ambiguity check for the inferred type for ‘foo’
       To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
       When checking the inferred type
diff --git a/testsuite/tests/partial-sigs/should_fail/T10999.stderr b/testsuite/tests/partial-sigs/should_fail/T10999.stderr
index d6fe29c811..4942fb9f8a 100644
--- a/testsuite/tests/partial-sigs/should_fail/T10999.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/T10999.stderr
@@ -17,10 +17,10 @@ T10999.hs:5:17: error:
       In the type signature: f :: _ => () -> _
 
 T10999.hs:8:28: error:
-    • Ambiguous type variable ‘b0’ arising from a use of ‘f’
-      prevents the constraint ‘(Ord b0)’ from being solved.
-      Relevant bindings include g :: [b0] (bound at T10999.hs:8:1)
-      Probable fix: use a type annotation to specify what ‘b0’ should be.
+    • Ambiguous type variable ‘b1’ arising from a use of ‘f’
+      prevents the constraint ‘(Ord b1)’ from being solved.
+      Relevant bindings include g :: [b1] (bound at T10999.hs:8:1)
+      Probable fix: use a type annotation to specify what ‘b1’ should be.
       Potentially matching instances:
         instance Ord a => Ord (Set.Set a) -- Defined in ‘Data.Set.Internal’
         instance Ord Ordering -- Defined in ‘GHC.Classes’
diff --git a/testsuite/tests/partial-sigs/should_fail/T14584.stderr b/testsuite/tests/partial-sigs/should_fail/T14584.stderr
index 9d0247f22b..7a47f25967 100644
--- a/testsuite/tests/partial-sigs/should_fail/T14584.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/T14584.stderr
@@ -1,20 +1,9 @@
 
-T14584.hs:56:41: warning: [-Wdeferred-type-errors (in -Wdefault)]
-    • Could not deduce (SingI a) arising from a use of ‘sing’
-      from the context: (Action act, Monoid a, Good m)
-        bound by the instance declaration at T14584.hs:54:10-89
-    • In the second argument of ‘fromSing’, namely
-        ‘(sing @m @a :: Sing _)’
-      In the fourth argument of ‘act’, namely
-        ‘(fromSing @m (sing @m @a :: Sing _))’
-      In the expression:
-        act @_ @_ @act (fromSing @m (sing @m @a :: Sing _))
-
 T14584.hs:56:50: warning: [-Wdeferred-type-errors (in -Wdefault)]
-    • Could not deduce (m ~ *)
-      from the context: (Action act, Monoid a, Good m)
+    • Could not deduce (m1 ~ *)
+      from the context: (Action act, Monoid a, Good m1)
         bound by the instance declaration at T14584.hs:54:10-89
-      ‘m’ is a rigid type variable bound by
+      ‘m1’ is a rigid type variable bound by
         the instance declaration
         at T14584.hs:54:10-89
     • In the type ‘a’
@@ -24,8 +13,9 @@ T14584.hs:56:50: warning: [-Wdeferred-type-errors (in -Wdefault)]
         ‘(fromSing @m (sing @m @a :: Sing _))’
 
 T14584.hs:56:60: warning: [-Wpartial-type-signatures (in -Wdefault)]
-    • Found type wildcard ‘_’ standing for ‘a :: m’
-      Where: ‘a’, ‘m’ are rigid type variables bound by
+    • Found type wildcard ‘_’ standing for ‘a0 :: m’
+      Where: ‘a0’ is an ambiguous type variable
+             ‘m’ is a rigid type variable bound by
                the instance declaration
                at T14584.hs:54:10-89
     • In the first argument of ‘Sing’, namely ‘_’
diff --git a/testsuite/tests/partial-sigs/should_fail/T14584a.stderr b/testsuite/tests/partial-sigs/should_fail/T14584a.stderr
index c3e957b9dd..febc57797d 100644
--- a/testsuite/tests/partial-sigs/should_fail/T14584a.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/T14584a.stderr
@@ -1,10 +1,4 @@
 
-T14584a.hs:12:5: warning: [-Wdeferred-type-errors (in -Wdefault)]
-    • Couldn't match expected type ‘()’ with actual type ‘m -> m’
-    • Probable cause: ‘id @m :: _’ is applied to too few arguments
-      In the expression: id @m :: _
-      In an equation for ‘f’: f = id @m :: _
-
 T14584a.hs:12:9: warning: [-Wdeferred-type-errors (in -Wdefault)]
     • Expected a type, but ‘m’ has kind ‘k’
       ‘k’ is a rigid type variable bound by
@@ -16,11 +10,7 @@ T14584a.hs:12:9: warning: [-Wdeferred-type-errors (in -Wdefault)]
       In an equation for ‘f’: f = id @m :: _
 
 T14584a.hs:12:14: warning: [-Wpartial-type-signatures (in -Wdefault)]
-    • Found type wildcard ‘_’ standing for ‘m -> m’
-      Where: ‘m’, ‘k’ are rigid type variables bound by
-               the type signature for:
-                 f :: forall {k} (m :: k). ()
-               at T14584a.hs:11:1-17
+    • Found type wildcard ‘_’ standing for ‘()’
     • In an expression type signature: _
       In the expression: id @m :: _
       In an equation for ‘f’: f = id @m :: _
@@ -36,11 +26,3 @@ T14584a.hs:15:17: warning: [-Wdeferred-type-errors (in -Wdefault)]
       In the expression: id @m
       In an equation for ‘h’: h = id @m
     • Relevant bindings include h :: m -> m (bound at T14584a.hs:15:9)
-
-T14584a.hs:16:8: warning: [-Wdeferred-type-errors (in -Wdefault)]
-    • Couldn't match expected type ‘()’ with actual type ‘m -> m’
-    • Probable cause: ‘h’ is applied to too few arguments
-      In the expression: h
-      In the expression: let h = id @m in h
-      In an equation for ‘g’: g = let h = id @m in h
-    • Relevant bindings include h :: m -> m (bound at T14584a.hs:15:9)