Note [Rules for instance lookup]

These functions implement the carefully-written rules in the user
manual section on "overlapping instances". At risk of duplication,
here are the rules.  If the rules change, change this text and the
user manual simultaneously.  The link may be this:
https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/instances.html#instance-overlap

The willingness to be overlapped or incoherent is a property of the
instance declaration itself, controlled by its `OverlapMode`, as follows

 * An instance is "incoherent" (OverlapMode = `Incoherent` or `NonCanonical`)
   if it has an `INCOHERENT` pragma, or
   if it appears in a module compiled with `-XIncoherentInstances`.
   In those cases:
      -fspecialise-incoherents on  => Incoherent
      -fspecialise-incoherents off => NonCanonical
   NB: it is on by default

 * An instance is "overlappable" (OverlapMode = `Overlappable` or `Overlaps`)
   if it has an `OVERLAPPABLE` or `OVERLAPS` pragma, or
   if it appears in a module compiled with `-XOverlappingInstances`, or
   if the instance is incoherent.

 * An instance is "overlapping" (OverlapMode = `Overlapping` or `Overlaps`)
   if it has an `OVERLAPPING` or `OVERLAPS` pragma, or
   if it appears in a module compiled with `-XOverlappingInstances`, or
   if the instance is incoherent.

Now suppose that, in some client module, we are searching for an instance
of the target constraint (C ty1 .. tyn). The search works like this.

(IL0) If there are any local Givens that match (potentially unifying
      any metavariables, even untouchable ones) the target constraint,
      the search fails unless -XIncoherentInstances is enabled. See
      Note [Instance and Given overlap] in GHC.Tc.Solver.Dict.  This is
      implemented by the first guard in matchClassInst.

(IL1) Find `all_matches` and `all_unifs` in `lookupInstEnv`:
      - all_matches: all instances `I` that *match* the target constraint (that
        is, the target constraint is a substitution instance of `I`). These
        instance declarations are the /candidates/.
      - all_unifs: all non-incoherent instances that *unify with but do not match*
        the target constraint. These are not candidates, but might match later if
        the target constraint is furhter instantiated. See
        `data PotentialUnifiers` for more precise details.

(IL2) If there are no candidates, the search fails
      (lookupInstEnv returns no final_matches). The PotentialUnifiers are returned
      by lookupInstEnv for use in error message generation (mkDictErr).

(IL3) Eliminate any candidate `IX` for which there is another candidate `IY` such
      that both of the following hold:
      - `IY` is strictly more specific than `IX`. That is, `IY` is a
        substitution instance of `IX` but not vice versa.
      - Either `IX` is *overlappable*, or `IY` is *overlapping*. (This
        "either/or" design, rather than a "both/and" design, allow a
        client to deliberately override an instance from a library,
        without requiring a change to the library.)

      In addition, provided there is at least one candidate, eliminate any other
      candidates that are *incoherent*. (In particular, if all remaining candidates
      are incoherent, all except an arbitrarily chosen one will be eliminated.)

      This is implemented by `pruneOverlappedMatches`, producing final_matches in
      lookupInstEnv.  See Note [Instance overlap and guards] and
      Note [Incoherent instances].

(IL4) If exactly one *incoherent* candidate remains, the search succeeds.
      (By the previous step, there cannot be more than one incoherent candidate
      remaining.)

      In this case, lookupInstEnv returns the successful match, and it returns
      NoUnifiers as the final_unifs, which amounts to skipping the following
      steps.

(IL5) If more than one candidate remains, the search fails. (We have already
      eliminated the incoherent candidates, and we have no way to select
      between non-incoherent candidates.)

(IL6) Otherwise there is exactly one candidate remaining. The all_unifs
      computed at step (IL1) are returned from lookupInstEnv as final_unifs.

      If there are no potential unifiers, the search succeeds (in matchInstEnv).
      If there is at least one (non-incoherent) potential unifier, matchInstEnv
      returns a NotSure result and refrains from committing to the instance.

      Incoherent instances are not returned as part of the potential unifiers. This
      affects error messages: they will not be listed as "potentially matching instances"
      in an "Overlapping instances" or "Ambiguous type variable" error.
      See also Note [Recording coherence information in `PotentialUnifiers`].


Notice that these rules are not influenced by flag settings in the
client module, where the instances are *used*. These rules make it
possible for a library author to design a library that relies on
overlapping instances without the client having to know.

Note [Overlapping instances]   (NB: these notes are quite old)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Overlap is permitted, but only in such a way that one can make
a unique choice when looking up.  That is, overlap is only permitted if
one template matches the other, or vice versa.  So this is ok:

  [a]  [Int]

but this is not

  (Int,a)  (b,Int)

If overlap is permitted, the list is kept most specific first, so that
the first lookup is the right choice.


For now we just use association lists.

\subsection{Avoiding a problem with overlapping}

Consider this little program:

\begin{pseudocode}
     class C a        where c :: a
     class C a => D a where d :: a

     instance C Int where c = 17
     instance D Int where d = 13

     instance C a => C [a] where c = [c]
     instance ({- C [a],