never executed always true always false
    1 {-
    2 (c) The University of Glasgow 2006
    3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
    4 
    5 \section[InstEnv]{Utilities for typechecking instance declarations}
    6 
    7 The bits common to GHC.Tc.TyCl.Instance and GHC.Tc.Deriv.
    8 -}
    9 
   10 {-# LANGUAGE DeriveDataTypeable #-}
   11 
   12 module GHC.Core.InstEnv (
   13         DFunId, InstMatch, ClsInstLookupResult,
   14         OverlapFlag(..), OverlapMode(..), setOverlapModeMaybe,
   15         ClsInst(..), DFunInstType, pprInstance, pprInstanceHdr, pprInstances,
   16         instanceHead, instanceSig, mkLocalInstance, mkImportedInstance,
   17         instanceDFunId, updateClsInstDFun, instanceRoughTcs,
   18         fuzzyClsInstCmp, orphNamesOfClsInst,
   19 
   20         InstEnvs(..), VisibleOrphanModules, InstEnv,
   21         emptyInstEnv, extendInstEnv,
   22         deleteFromInstEnv, deleteDFunFromInstEnv,
   23         identicalClsInstHead,
   24         extendInstEnvList, lookupUniqueInstEnv, lookupInstEnv, instEnvElts, instEnvClasses,
   25         memberInstEnv,
   26         instIsVisible,
   27         classInstances, instanceBindFun,
   28         instanceCantMatch, roughMatchTcs,
   29         isOverlappable, isOverlapping, isIncoherent
   30     ) where
   31 
   32 import GHC.Prelude
   33 
   34 import GHC.Tc.Utils.TcType -- InstEnv is really part of the type checker,
   35               -- and depends on TcType in many ways
   36 import GHC.Core ( IsOrphan(..), isOrphan, chooseOrphanAnchor )
   37 import GHC.Unit.Module.Env
   38 import GHC.Unit.Types
   39 import GHC.Core.Class
   40 import GHC.Types.Var
   41 import GHC.Types.Var.Set
   42 import GHC.Types.Name
   43 import GHC.Types.Name.Set
   44 import GHC.Types.Unique (getUnique)
   45 import GHC.Core.Unify
   46 import GHC.Types.Basic
   47 import GHC.Types.Unique.DFM
   48 import GHC.Types.Id
   49 import Data.Data        ( Data )
   50 import Data.Maybe       ( isJust )
   51 
   52 import GHC.Utils.Misc
   53 import GHC.Utils.Outputable
   54 import GHC.Utils.Panic
   55 import GHC.Utils.Panic.Plain
   56 
   57 {-
   58 ************************************************************************
   59 *                                                                      *
   60            ClsInst: the data type for type-class instances
   61 *                                                                      *
   62 ************************************************************************
   63 -}
   64 
   65 -- | A type-class instance. Note that there is some tricky laziness at work
   66 -- here. See Note [ClsInst laziness and the rough-match fields] for more
   67 -- details.
   68 data ClsInst
   69   = ClsInst {   -- Used for "rough matching"; see
   70                 -- Note [ClsInst laziness and the rough-match fields]
   71                 -- INVARIANT: is_tcs = roughMatchTcs is_tys
   72                is_cls_nm :: Name          -- ^ Class name
   73              , is_tcs  :: [RoughMatchTc]  -- ^ Top of type args
   74 
   75                -- | @is_dfun_name = idName . is_dfun@.
   76                --
   77                -- We use 'is_dfun_name' for the visibility check,
   78                -- 'instIsVisible', which needs to know the 'Module' which the
   79                -- dictionary is defined in. However, we cannot use the 'Module'
   80                -- attached to 'is_dfun' since doing so would mean we would
   81                -- potentially pull in an entire interface file unnecessarily.
   82                -- This was the cause of #12367.
   83              , is_dfun_name :: Name
   84 
   85                 -- Used for "proper matching"; see Note [Proper-match fields]
   86              , is_tvs  :: [TyVar]       -- Fresh template tyvars for full match
   87                                         -- See Note [Template tyvars are fresh]
   88              , is_cls  :: Class         -- The real class
   89              , is_tys  :: [Type]        -- Full arg types (mentioning is_tvs)
   90                 -- INVARIANT: is_dfun Id has type
   91                 --      forall is_tvs. (...) => is_cls is_tys
   92                 -- (modulo alpha conversion)
   93 
   94              , is_dfun :: DFunId -- See Note [Haddock assumptions]
   95 
   96              , is_flag :: OverlapFlag   -- See detailed comments with
   97                                         -- the decl of BasicTypes.OverlapFlag
   98              , is_orphan :: IsOrphan
   99     }
  100   deriving Data
  101 
  102 -- | A fuzzy comparison function for class instances, intended for sorting
  103 -- instances before displaying them to the user.
  104 fuzzyClsInstCmp :: ClsInst -> ClsInst -> Ordering
  105 fuzzyClsInstCmp x y =
  106     stableNameCmp (is_cls_nm x) (is_cls_nm y) `mappend`
  107     mconcat (map cmp (zip (is_tcs x) (is_tcs y)))
  108   where
  109     cmp (OtherTc,   OtherTc)   = EQ
  110     cmp (OtherTc,   KnownTc _) = LT
  111     cmp (KnownTc _, OtherTc)   = GT
  112     cmp (KnownTc x, KnownTc y) = stableNameCmp x y
  113 
  114 isOverlappable, isOverlapping, isIncoherent :: ClsInst -> Bool
  115 isOverlappable i = hasOverlappableFlag (overlapMode (is_flag i))
  116 isOverlapping  i = hasOverlappingFlag  (overlapMode (is_flag i))
  117 isIncoherent   i = hasIncoherentFlag   (overlapMode (is_flag i))
  118 
  119 {-
  120 Note [ClsInst laziness and the rough-match fields]
  121 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  122 Suppose we load 'instance A.C B.T' from A.hi, but suppose that the type B.T is
  123 otherwise unused in the program. Then it's stupid to load B.hi, the data type
  124 declaration for B.T -- and perhaps further instance declarations!
  125 
  126 We avoid this as follows:
  127 
  128 * is_cls_nm, is_tcs, is_dfun_name are all Names. We can poke them to our heart's
  129   content.
  130 
  131 * Proper-match fields. is_dfun, and its related fields is_tvs, is_cls, is_tys
  132   contain TyVars, Class, Type, Class etc, and so are all lazy thunks. When we
  133   poke any of these fields we'll typecheck the DFunId declaration, and hence
  134   pull in interfaces that it refers to. See Note [Proper-match fields].
  135 
  136 * Rough-match fields. During instance lookup, we use the is_cls_nm :: Name and
  137   is_tcs :: [RoughMatchTc] fields to perform a "rough match", *without* poking
  138   inside the DFunId. The rough-match fields allow us to say "definitely does not
  139   match", based only on Names.  See GHC.Core.Unify
  140   Note [Rough matching in class and family instances]
  141 
  142   This laziness is very important; see #12367. Try hard to avoid pulling on
  143   the structured fields unless you really need the instance.
  144 
  145 * Another place to watch is InstEnv.instIsVisible, which needs the module to
  146   which the ClsInst belongs. We can get this from is_dfun_name.
  147 -}
  148 
  149 {-
  150 Note [Template tyvars are fresh]
  151 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  152 The is_tvs field of a ClsInst has *completely fresh* tyvars.
  153 That is, they are
  154   * distinct from any other ClsInst
  155   * distinct from any tyvars free in predicates that may
  156     be looked up in the class instance environment
  157 Reason for freshness: we use unification when checking for overlap
  158 etc, and that requires the tyvars to be distinct.
  159 
  160 The invariant is checked by the ASSERT in lookupInstEnv'.
  161 
  162 Note [Proper-match fields]
  163 ~~~~~~~~~~~~~~~~~~~~~~~~~
  164 The is_tvs, is_cls, is_tys fields are simply cached values, pulled
  165 out (lazily) from the dfun id. They are cached here simply so
  166 that we don't need to decompose the DFunId each time we want
  167 to match it.  The hope is that the rough-match fields mean
  168 that we often never poke the proper-match fields.
  169 
  170 However, note that:
  171  * is_tvs must be a superset of the free vars of is_tys
  172 
  173  * is_tvs, is_tys may be alpha-renamed compared to the ones in
  174    the dfun Id
  175 
  176 Note [Haddock assumptions]
  177 ~~~~~~~~~~~~~~~~~~~~~~~~~~
  178 For normal user-written instances, Haddock relies on
  179 
  180  * the SrcSpan of
  181  * the Name of
  182  * the is_dfun of
  183  * an Instance
  184 
  185 being equal to
  186 
  187   * the SrcSpan of
  188   * the instance head type of
  189   * the InstDecl used to construct the Instance.
  190 -}
  191 
  192 instanceDFunId :: ClsInst -> DFunId
  193 instanceDFunId = is_dfun
  194 
  195 updateClsInstDFun :: (DFunId -> DFunId) -> ClsInst -> ClsInst
  196 updateClsInstDFun tidy_dfun ispec
  197   = ispec { is_dfun = tidy_dfun (is_dfun ispec) }
  198 
  199 instanceRoughTcs :: ClsInst -> [RoughMatchTc]
  200 instanceRoughTcs = is_tcs
  201 
  202 instance NamedThing ClsInst where
  203    getName ispec = getName (is_dfun ispec)
  204 
  205 instance Outputable ClsInst where
  206    ppr = pprInstance
  207 
  208 pprInstance :: ClsInst -> SDoc
  209 -- Prints the ClsInst as an instance declaration
  210 pprInstance ispec
  211   = hang (pprInstanceHdr ispec)
  212        2 (vcat [ text "--" <+> pprDefinedAt (getName ispec)
  213                , whenPprDebug (ppr (is_dfun ispec)) ])
  214 
  215 -- * pprInstanceHdr is used in VStudio to populate the ClassView tree
  216 pprInstanceHdr :: ClsInst -> SDoc
  217 -- Prints the ClsInst as an instance declaration
  218 pprInstanceHdr (ClsInst { is_flag = flag, is_dfun = dfun })
  219   = text "instance" <+> ppr flag <+> pprSigmaType (idType dfun)
  220 
  221 pprInstances :: [ClsInst] -> SDoc
  222 pprInstances ispecs = vcat (map pprInstance ispecs)
  223 
  224 instanceHead :: ClsInst -> ([TyVar], Class, [Type])
  225 -- Returns the head, using the fresh tyvars from the ClsInst
  226 instanceHead (ClsInst { is_tvs = tvs, is_tys = tys, is_dfun = dfun })
  227    = (tvs, cls, tys)
  228    where
  229      (_, _, cls, _) = tcSplitDFunTy (idType dfun)
  230 
  231 -- | Collects the names of concrete types and type constructors that make
  232 -- up the head of a class instance. For instance, given `class Foo a b`:
  233 --
  234 -- `instance Foo (Either (Maybe Int) a) Bool` would yield
  235 --      [Either, Maybe, Int, Bool]
  236 --
  237 -- Used in the implementation of ":info" in GHCi.
  238 --
  239 -- The 'tcSplitSigmaTy' is because of
  240 --      instance Foo a => Baz T where ...
  241 -- The decl is an orphan if Baz and T are both not locally defined,
  242 --      even if Foo *is* locally defined
  243 orphNamesOfClsInst :: ClsInst -> NameSet
  244 orphNamesOfClsInst (ClsInst { is_cls_nm = cls_nm, is_tys = tys })
  245   = orphNamesOfTypes tys `unionNameSet` unitNameSet cls_nm
  246 
  247 instanceSig :: ClsInst -> ([TyVar], [Type], Class, [Type])
  248 -- Decomposes the DFunId
  249 instanceSig ispec = tcSplitDFunTy (idType (is_dfun ispec))
  250 
  251 mkLocalInstance :: DFunId -> OverlapFlag
  252                 -> [TyVar] -> Class -> [Type]
  253                 -> ClsInst
  254 -- Used for local instances, where we can safely pull on the DFunId.
  255 -- Consider using newClsInst instead; this will also warn if
  256 -- the instance is an orphan.
  257 mkLocalInstance dfun oflag tvs cls tys
  258   = ClsInst { is_flag = oflag, is_dfun = dfun
  259             , is_tvs = tvs
  260             , is_dfun_name = dfun_name
  261             , is_cls = cls, is_cls_nm = cls_name
  262             , is_tys = tys, is_tcs = roughMatchTcs tys
  263             , is_orphan = orph
  264             }
  265   where
  266     cls_name = className cls
  267     dfun_name = idName dfun
  268     this_mod = assert (isExternalName dfun_name) $ nameModule dfun_name
  269     is_local name = nameIsLocalOrFrom this_mod name
  270 
  271         -- Compute orphanhood.  See Note [Orphans] in GHC.Core.InstEnv
  272     (cls_tvs, fds) = classTvsFds cls
  273     arg_names = [filterNameSet is_local (orphNamesOfType ty) | ty <- tys]
  274 
  275     -- See Note [When exactly is an instance decl an orphan?]
  276     orph | is_local cls_name   = NotOrphan (nameOccName cls_name)
  277          | all notOrphan mb_ns = assert (not (null mb_ns)) $ head mb_ns
  278          | otherwise           = IsOrphan
  279 
  280     notOrphan NotOrphan{} = True
  281     notOrphan _ = False
  282 
  283     mb_ns :: [IsOrphan]    -- One for each fundep; a locally-defined name
  284                            -- that is not in the "determined" arguments
  285     mb_ns | null fds   = [choose_one arg_names]
  286           | otherwise  = map do_one fds
  287     do_one (_ltvs, rtvs) = choose_one [ns | (tv,ns) <- cls_tvs `zip` arg_names
  288                                             , not (tv `elem` rtvs)]
  289 
  290     choose_one nss = chooseOrphanAnchor (unionNameSets nss)
  291 
  292 mkImportedInstance :: Name           -- ^ the name of the class
  293                    -> [RoughMatchTc] -- ^ the types which the class was applied to
  294                    -> Name           -- ^ the 'Name' of the dictionary binding
  295                    -> DFunId         -- ^ the 'Id' of the dictionary.
  296                    -> OverlapFlag    -- ^ may this instance overlap?
  297                    -> IsOrphan       -- ^ is this instance an orphan?
  298                    -> ClsInst
  299 -- Used for imported instances, where we get the rough-match stuff
  300 -- from the interface file
  301 -- The bound tyvars of the dfun are guaranteed fresh, because
  302 -- the dfun has been typechecked out of the same interface file
  303 mkImportedInstance cls_nm mb_tcs dfun_name dfun oflag orphan
  304   = ClsInst { is_flag = oflag, is_dfun = dfun
  305             , is_tvs = tvs, is_tys = tys
  306             , is_dfun_name = dfun_name
  307             , is_cls_nm = cls_nm, is_cls = cls, is_tcs = mb_tcs
  308             , is_orphan = orphan }
  309   where
  310     (tvs, _, cls, tys) = tcSplitDFunTy (idType dfun)
  311 
  312 {-
  313 Note [When exactly is an instance decl an orphan?]
  314 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  315   (see GHC.Iface.Make.instanceToIfaceInst, which implements this)
  316 Roughly speaking, an instance is an orphan if its head (after the =>)
  317 mentions nothing defined in this module.
  318 
  319 Functional dependencies complicate the situation though. Consider
  320 
  321   module M where { class C a b | a -> b }
  322 
  323 and suppose we are compiling module X:
  324 
  325   module X where
  326         import M
  327         data T = ...
  328         instance C Int T where ...
  329 
  330 This instance is an orphan, because when compiling a third module Y we
  331 might get a constraint (C Int v), and we'd want to improve v to T.  So
  332 we must make sure X's instances are loaded, even if we do not directly
  333 use anything from X.
  334 
  335 More precisely, an instance is an orphan iff
  336 
  337   If there are no fundeps, then at least of the names in
  338   the instance head is locally defined.
  339 
  340   If there are fundeps, then for every fundep, at least one of the
  341   names free in a *non-determined* part of the instance head is
  342   defined in this module.
  343 
  344 (Note that these conditions hold trivially if the class is locally
  345 defined.)
  346 
  347 
  348 ************************************************************************
  349 *                                                                      *
  350                 InstEnv, ClsInstEnv
  351 *                                                                      *
  352 ************************************************************************
  353 
  354 A @ClsInstEnv@ all the instances of that class.  The @Id@ inside a
  355 ClsInstEnv mapping is the dfun for that instance.
  356 
  357 If class C maps to a list containing the item ([a,b], [t1,t2,t3], dfun), then
  358 
  359         forall a b, C t1 t2 t3  can be constructed by dfun
  360 
  361 or, to put it another way, we have
  362 
  363         instance (...) => C t1 t2 t3,  witnessed by dfun
  364 -}
  365 
  366 ---------------------------------------------------
  367 {-
  368 Note [InstEnv determinism]
  369 ~~~~~~~~~~~~~~~~~~~~~~~~~~
  370 We turn InstEnvs into a list in some places that don't directly affect
  371 the ABI. That happens when we create output for `:info`.
  372 Unfortunately that nondeterminism is nonlocal and it's hard to tell what it
  373 affects without following a chain of functions. It's also easy to accidentally
  374 make that nondeterminism affect the ABI. Furthermore the envs should be
  375 relatively small, so it should be free to use deterministic maps here.
  376 Testing with nofib and validate detected no difference between UniqFM and
  377 UniqDFM. See also Note [Deterministic UniqFM]
  378 -}
  379 
  380 -- Internally it's safe to indexable this map by
  381 -- by @Class@, the classes @Name@, the classes @TyCon@
  382 -- or it's @Unique@.
  383 -- This is since:
  384 -- getUnique cls == getUnique (className cls) == getUnique (classTyCon cls)
  385 --
  386 -- We still use Class as key type as it's both the common case
  387 -- and conveys the meaning better. But the implementation of
  388 --InstEnv is a bit more lax internally.
  389 type InstEnv = UniqDFM Class ClsInstEnv      -- Maps Class to instances for that class
  390   -- See Note [InstEnv determinism]
  391 
  392 -- | 'InstEnvs' represents the combination of the global type class instance
  393 -- environment, the local type class instance environment, and the set of
  394 -- transitively reachable orphan modules (according to what modules have been
  395 -- directly imported) used to test orphan instance visibility.
  396 data InstEnvs = InstEnvs {
  397         ie_global  :: InstEnv,               -- External-package instances
  398         ie_local   :: InstEnv,               -- Home-package instances
  399         ie_visible :: VisibleOrphanModules   -- Set of all orphan modules transitively
  400                                              -- reachable from the module being compiled
  401                                              -- See Note [Instance lookup and orphan instances]
  402     }
  403 
  404 -- | Set of visible orphan modules, according to what modules have been directly
  405 -- imported.  This is based off of the dep_orphs field, which records
  406 -- transitively reachable orphan modules (modules that define orphan instances).
  407 type VisibleOrphanModules = ModuleSet
  408 
  409 newtype ClsInstEnv
  410   = ClsIE [ClsInst]    -- The instances for a particular class, in any order
  411 
  412 instance Outputable ClsInstEnv where
  413   ppr (ClsIE is) = pprInstances is
  414 
  415 -- INVARIANTS:
  416 --  * The is_tvs are distinct in each ClsInst
  417 --      of a ClsInstEnv (so we can safely unify them)
  418 
  419 -- Thus, the @ClassInstEnv@ for @Eq@ might contain the following entry:
  420 --      [a] ===> dfun_Eq_List :: forall a. Eq a => Eq [a]
  421 -- The "a" in the pattern must be one of the forall'd variables in
  422 -- the dfun type.
  423 
  424 emptyInstEnv :: InstEnv
  425 emptyInstEnv = emptyUDFM
  426 
  427 instEnvElts :: InstEnv -> [ClsInst]
  428 instEnvElts ie = [elt | ClsIE elts <- eltsUDFM ie, elt <- elts]
  429   -- See Note [InstEnv determinism]
  430 
  431 instEnvClasses :: InstEnv -> [Class]
  432 instEnvClasses ie = [is_cls e | ClsIE (e : _) <- eltsUDFM ie]
  433 
  434 -- | Test if an instance is visible, by checking that its origin module
  435 -- is in 'VisibleOrphanModules'.
  436 -- See Note [Instance lookup and orphan instances]
  437 instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool
  438 instIsVisible vis_mods ispec
  439   -- NB: Instances from the interactive package always are visible. We can't
  440   -- add interactive modules to the set since we keep creating new ones
  441   -- as a GHCi session progresses.
  442   = case nameModule_maybe (is_dfun_name ispec) of
  443       Nothing -> True
  444       Just mod | isInteractiveModule mod     -> True
  445                | IsOrphan <- is_orphan ispec -> mod `elemModuleSet` vis_mods
  446                | otherwise                   -> True
  447 
  448 classInstances :: InstEnvs -> Class -> [ClsInst]
  449 classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls
  450   = get home_ie ++ get pkg_ie
  451   where
  452     get env = case lookupUDFM env cls of
  453                 Just (ClsIE insts) -> filter (instIsVisible vis_mods) insts
  454                 Nothing            -> []
  455 
  456 -- | Checks for an exact match of ClsInst in the instance environment.
  457 -- We use this when we do signature checking in "GHC.Tc.Module"
  458 memberInstEnv :: InstEnv -> ClsInst -> Bool
  459 memberInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm } ) =
  460     maybe False (\(ClsIE items) -> any (identicalDFunType ins_item) items)
  461           (lookupUDFM_Directly inst_env (getUnique cls_nm))
  462  where
  463   identicalDFunType cls1 cls2 =
  464     eqType (varType (is_dfun cls1)) (varType (is_dfun cls2))
  465 
  466 extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv
  467 extendInstEnvList inst_env ispecs = foldl' extendInstEnv inst_env ispecs
  468 
  469 extendInstEnv :: InstEnv -> ClsInst -> InstEnv
  470 extendInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
  471   = addToUDFM_C_Directly add inst_env (getUnique cls_nm) (ClsIE [ins_item])
  472   where
  473     add (ClsIE cur_insts) _ = ClsIE (ins_item : cur_insts)
  474 
  475 deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv
  476 deleteFromInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
  477   = adjustUDFM_Directly adjust inst_env (getUnique cls_nm)
  478   where
  479     adjust (ClsIE items) = ClsIE (filterOut (identicalClsInstHead ins_item) items)
  480 
  481 deleteDFunFromInstEnv :: InstEnv -> DFunId -> InstEnv
  482 -- Delete a specific instance fron an InstEnv
  483 deleteDFunFromInstEnv inst_env dfun
  484   = adjustUDFM adjust inst_env cls
  485   where
  486     (_, _, cls, _) = tcSplitDFunTy (idType dfun)
  487     adjust (ClsIE items) = ClsIE (filterOut same_dfun items)
  488     same_dfun (ClsInst { is_dfun = dfun' }) = dfun == dfun'
  489 
  490 identicalClsInstHead :: ClsInst -> ClsInst -> Bool
  491 -- ^ True when when the instance heads are the same
  492 -- e.g.  both are   Eq [(a,b)]
  493 -- Used for overriding in GHCi
  494 -- Obviously should be insensitive to alpha-renaming
  495 identicalClsInstHead (ClsInst { is_cls_nm = cls_nm1, is_tcs = rough1, is_tys = tys1 })
  496                      (ClsInst { is_cls_nm = cls_nm2, is_tcs = rough2, is_tys = tys2 })
  497   =  cls_nm1 == cls_nm2
  498   && not (instanceCantMatch rough1 rough2)  -- Fast check for no match, uses the "rough match" fields
  499   && isJust (tcMatchTys tys1 tys2)
  500   && isJust (tcMatchTys tys2 tys1)
  501 
  502 {-
  503 ************************************************************************
  504 *                                                                      *
  505         Looking up an instance
  506 *                                                                      *
  507 ************************************************************************
  508 
  509 @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match.  Since
  510 the env is kept ordered, the first match must be the only one.  The
  511 thing we are looking up can have an arbitrary "flexi" part.
  512 
  513 Note [Instance lookup and orphan instances]
  514 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  515 Suppose we are compiling a module M, and we have a zillion packages
  516 loaded, and we are looking up an instance for C (T W).  If we find a
  517 match in module 'X' from package 'p', should be "in scope"; that is,
  518 
  519   is p:X in the transitive closure of modules imported from M?
  520 
  521 The difficulty is that the "zillion packages" might include ones loaded
  522 through earlier invocations of the GHC API, or earlier module loads in GHCi.
  523 They might not be in the dependencies of M itself; and if not, the instances
  524 in them should not be visible.  #2182, #8427.
  525 
  526 There are two cases:
  527   * If the instance is *not an orphan*, then module X defines C, T, or W.
  528     And in order for those types to be involved in typechecking M, it
  529     must be that X is in the transitive closure of M's imports.  So we
  530     can use the instance.
  531 
  532   * If the instance *is an orphan*, the above reasoning does not apply.
  533     So we keep track of the set of orphan modules transitively below M;
  534     this is the ie_visible field of InstEnvs, of type VisibleOrphanModules.
  535 
  536     If module p:X is in this set, then we can use the instance, otherwise
  537     we can't.
  538 
  539 Note [Rules for instance lookup]
  540 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  541 These functions implement the carefully-written rules in the user
  542 manual section on "overlapping instances". At risk of duplication,
  543 here are the rules.  If the rules change, change this text and the
  544 user manual simultaneously.  The link may be this:
  545 http://www.haskell.org/ghc/docs/latest/html/users_guide/glasgow_exts.html#instance-overlap
  546 
  547 The willingness to be overlapped or incoherent is a property of the
  548 instance declaration itself, controlled as follows:
  549 
  550  * An instance is "incoherent"
  551    if it has an INCOHERENT pragma, or
  552    if it appears in a module compiled with -XIncoherentInstances.
  553 
  554  * An instance is "overlappable"
  555    if it has an OVERLAPPABLE or OVERLAPS pragma, or
  556    if it appears in a module compiled with -XOverlappingInstances, or
  557    if the instance is incoherent.
  558 
  559  * An instance is "overlapping"
  560    if it has an OVERLAPPING or OVERLAPS pragma, or
  561    if it appears in a module compiled with -XOverlappingInstances, or
  562    if the instance is incoherent.
  563      compiled with -XOverlappingInstances.
  564 
  565 Now suppose that, in some client module, we are searching for an instance
  566 of the target constraint (C ty1 .. tyn). The search works like this.
  567 
  568 *  Find all instances `I` that *match* the target constraint; that is, the
  569    target constraint is a substitution instance of `I`. These instance
  570    declarations are the *candidates*.
  571 
  572 *  Eliminate any candidate `IX` for which both of the following hold:
  573 
  574    -  There is another candidate `IY` that is strictly more specific; that
  575       is, `IY` is a substitution instance of `IX` but not vice versa.
  576 
  577    -  Either `IX` is *overlappable*, or `IY` is *overlapping*. (This
  578       "either/or" design, rather than a "both/and" design, allow a
  579       client to deliberately override an instance from a library,
  580       without requiring a change to the library.)
  581 
  582 -  If exactly one non-incoherent candidate remains, select it. If all
  583    remaining candidates are incoherent, select an arbitrary one.
  584    Otherwise the search fails (i.e. when more than one surviving
  585    candidate is not incoherent).
  586 
  587 -  If the selected candidate (from the previous step) is incoherent, the
  588    search succeeds, returning that candidate.
  589 
  590 -  If not, find all instances that *unify* with the target constraint,
  591    but do not *match* it. Such non-candidate instances might match when
  592    the target constraint is further instantiated. If all of them are
  593    incoherent, the search succeeds, returning the selected candidate; if
  594    not, the search fails.
  595 
  596 Notice that these rules are not influenced by flag settings in the
  597 client module, where the instances are *used*. These rules make it
  598 possible for a library author to design a library that relies on
  599 overlapping instances without the client having to know.
  600 
  601 Note [Overlapping instances]   (NB: these notes are quite old)
  602 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  603 Overlap is permitted, but only in such a way that one can make
  604 a unique choice when looking up.  That is, overlap is only permitted if
  605 one template matches the other, or vice versa.  So this is ok:
  606 
  607   [a]  [Int]
  608 
  609 but this is not
  610 
  611   (Int,a)  (b,Int)
  612 
  613 If overlap is permitted, the list is kept most specific first, so that
  614 the first lookup is the right choice.
  615 
  616 
  617 For now we just use association lists.
  618 
  619 \subsection{Avoiding a problem with overlapping}
  620 
  621 Consider this little program:
  622 
  623 \begin{pseudocode}
  624      class C a        where c :: a
  625      class C a => D a where d :: a
  626 
  627      instance C Int where c = 17
  628      instance D Int where d = 13
  629 
  630      instance C a => C [a] where c = [c]
  631      instance ({- C [a], -} D a) => D [a] where d = c
  632 
  633      instance C [Int] where c = [37]
  634 
  635      main = print (d :: [Int])
  636 \end{pseudocode}
  637 
  638 What do you think `main' prints  (assuming we have overlapping instances, and
  639 all that turned on)?  Well, the instance for `D' at type `[a]' is defined to
  640 be `c' at the same type, and we've got an instance of `C' at `[Int]', so the
  641 answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because
  642 the `C [Int]' instance is more specific).
  643 
  644 Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong.  That
  645 was easy ;-)  Let's just consult hugs for good measure.  Wait - if I use old
  646 hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it
  647 doesn't even compile!  What's going on!?
  648 
  649 What hugs complains about is the `D [a]' instance decl.
  650 
  651 \begin{pseudocode}
  652      ERROR "mj.hs" (line 10): Cannot build superclass instance
  653      *** Instance            : D [a]
  654      *** Context supplied    : D a
  655      *** Required superclass : C [a]
  656 \end{pseudocode}
  657 
  658 You might wonder what hugs is complaining about.  It's saying that you
  659 need to add `C [a]' to the context of the `D [a]' instance (as appears
  660 in comments).  But there's that `C [a]' instance decl one line above
  661 that says that I can reduce the need for a `C [a]' instance to the
  662 need for a `C a' instance, and in this case, I already have the
  663 necessary `C a' instance (since we have `D a' explicitly in the
  664 context, and `C' is a superclass of `D').
  665 
  666 Unfortunately, the above reasoning indicates a premature commitment to the
  667 generic `C [a]' instance.  I.e., it prematurely rules out the more specific
  668 instance `C [Int]'.  This is the mistake that ghc-4.06 makes.  The fix is to
  669 add the context that hugs suggests (uncomment the `C [a]'), effectively
  670 deferring the decision about which instance to use.
  671 
  672 Now, interestingly enough, 4.04 has this same bug, but it's covered up
  673 in this case by a little known `optimization' that was disabled in
  674 4.06.  Ghc-4.04 silently inserts any missing superclass context into
  675 an instance declaration.  In this case, it silently inserts the `C
  676 [a]', and everything happens to work out.
  677 
  678 (See `GHC.Types.Id.Make.mkDictFunId' for the code in question.  Search for
  679 `Mark Jones', although Mark claims no credit for the `optimization' in
  680 question, and would rather it stopped being called the `Mark Jones
  681 optimization' ;-)
  682 
  683 So, what's the fix?  I think hugs has it right.  Here's why.  Let's try
  684 something else out with ghc-4.04.  Let's add the following line:
  685 
  686     d' :: D a => [a]
  687     d' = c
  688 
  689 Everyone raise their hand who thinks that `d :: [Int]' should give a
  690 different answer from `d' :: [Int]'.  Well, in ghc-4.04, it does.  The
  691 `optimization' only applies to instance decls, not to regular
  692 bindings, giving inconsistent behavior.
  693 
  694 Old hugs had this same bug.  Here's how we fixed it: like GHC, the
  695 list of instances for a given class is ordered, so that more specific
  696 instances come before more generic ones.  For example, the instance
  697 list for C might contain:
  698     ..., C Int, ..., C a, ...
  699 When we go to look for a `C Int' instance we'll get that one first.
  700 But what if we go looking for a `C b' (`b' is unconstrained)?  We'll
  701 pass the `C Int' instance, and keep going.  But if `b' is
  702 unconstrained, then we don't know yet if the more specific instance
  703 will eventually apply.  GHC keeps going, and matches on the generic `C
  704 a'.  The fix is to, at each step, check to see if there's a reverse
  705 match, and if so, abort the search.  This prevents hugs from
  706 prematurely choosing a generic instance when a more specific one
  707 exists.
  708 
  709 --Jeff
  710 
  711 BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in
  712 this test.  Suppose the instance envt had
  713     ..., forall a b. C a a b, ..., forall a b c. C a b c, ...
  714 (still most specific first)
  715 Now suppose we are looking for (C x y Int), where x and y are unconstrained.
  716         C x y Int  doesn't match the template {a,b} C a a b
  717 but neither does
  718         C a a b  match the template {x,y} C x y Int
  719 But still x and y might subsequently be unified so they *do* match.
  720 
  721 Simple story: unify, don't match.
  722 -}
  723 
  724 type DFunInstType = Maybe Type
  725         -- Just ty   => Instantiate with this type
  726         -- Nothing   => Instantiate with any type of this tyvar's kind
  727         -- See Note [DFunInstType: instantiating types]
  728 
  729 type InstMatch = (ClsInst, [DFunInstType])
  730 
  731 type ClsInstLookupResult
  732      = ( [InstMatch]     -- Successful matches
  733        , [ClsInst]       -- These don't match but do unify
  734        , [InstMatch] )   -- Unsafe overlapped instances under Safe Haskell
  735                          -- (see Note [Safe Haskell Overlapping Instances] in
  736                          -- GHC.Tc.Solver).
  737 
  738 {-
  739 Note [DFunInstType: instantiating types]
  740 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  741 A successful match is a ClsInst, together with the types at which
  742         the dfun_id in the ClsInst should be instantiated
  743 The instantiating types are (Either TyVar Type)s because the dfun
  744 might have some tyvars that *only* appear in arguments
  745         dfun :: forall a b. C a b, Ord b => D [a]
  746 When we match this against D [ty], we return the instantiating types
  747         [Just ty, Nothing]
  748 where the 'Nothing' indicates that 'b' can be freely instantiated.
  749 (The caller instantiates it to a flexi type variable, which will
  750  presumably later become fixed via functional dependencies.)
  751 
  752 Note [Infinitary substitution in lookup]
  753 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  754 Consider
  755 
  756   class C a b
  757   instance C c c
  758   instance C d (Maybe d)
  759   [W] C e (Maybe e)
  760 
  761 You would think we could just use the second instance, because the first doesn't
  762 unify. But that's just ever so slightly wrong. The reason we check for unifiers
  763 along with matchers is that we don't want the possibility that a type variable
  764 instantiation could cause an instance choice to change. Yet if we have
  765   type family M = Maybe M
  766 and choose (e |-> M), then both instances match. This is absurd, but we cannot
  767 rule it out. Yet, worrying about this case is awfully inconvenient to users,
  768 and so we pretend the problem doesn't exist, by considering a lookup that runs into
  769 this occurs-check issue to indicate that an instance surely does not apply (i.e.
  770 is like the SurelyApart case). In the brief time that we didn't treat infinitary
  771 substitutions specially, two tickets were filed: #19044 and #19052, both trying
  772 to do Real Work.
  773 
  774 Why don't we just exclude any instances that are MaybeApart? Because we might
  775 have a [W] C e (F e), where F is a type family. The second instance above does
  776 not match, but it should be included as a future possibility. Unification will
  777 return MaybeApart MARTypeFamily in this case.
  778 
  779 What can go wrong with this design choice? We might get incoherence -- but not
  780 loss of type safety. In particular, if we have [W] C M M (for the M type family
  781 above), then GHC might arbitrarily choose either instance, depending on how
  782 M reduces (or doesn't).
  783 
  784 For type families, we can't just ignore the problem (as we essentially do here),
  785 because doing so would give us a hole in the type safety proof (as explored in
  786 Section 6 of "Closed Type Families with Overlapping Equations", POPL'14). This
  787 possibility of an infinitary substitution manifests as closed type families that
  788 look like they should reduce, but don't. Users complain: #9082 and #17311. For
  789 open type families, we actually can have unsoundness if we don't take infinitary
  790 substitutions into account: #8162. But, luckily, for class instances, we just
  791 risk coherence -- not great, but it seems better to give users what they likely
  792 want. (Also, note that this problem existed for the entire decade of 201x without
  793 anyone noticing, so it's manifestly not ruining anyone's day.)
  794 -}
  795 
  796 -- |Look up an instance in the given instance environment. The given class application must match exactly
  797 -- one instance and the match may not contain any flexi type variables.  If the lookup is unsuccessful,
  798 -- yield 'Left errorMessage'.
  799 lookupUniqueInstEnv :: InstEnvs
  800                     -> Class -> [Type]
  801                     -> Either SDoc (ClsInst, [Type])
  802 lookupUniqueInstEnv instEnv cls tys
  803   = case lookupInstEnv False instEnv cls tys of
  804       ([(inst, inst_tys)], _, _)
  805              | noFlexiVar -> Right (inst, inst_tys')
  806              | otherwise  -> Left $ text "flexible type variable:" <+>
  807                                     (ppr $ mkTyConApp (classTyCon cls) tys)
  808              where
  809                inst_tys'  = [ty | Just ty <- inst_tys]
  810                noFlexiVar = all isJust inst_tys
  811       _other -> Left $ text "instance not found" <+>
  812                        (ppr $ mkTyConApp (classTyCon cls) tys)
  813 
  814 lookupInstEnv' :: InstEnv          -- InstEnv to look in
  815                -> VisibleOrphanModules   -- But filter against this
  816                -> Class -> [Type]  -- What we are looking for
  817                -> ([InstMatch],    -- Successful matches
  818                    [ClsInst])      -- These don't match but do unify
  819                                    -- (no incoherent ones in here)
  820 -- The second component of the result pair happens when we look up
  821 --      Foo [a]
  822 -- in an InstEnv that has entries for
  823 --      Foo [Int]
  824 --      Foo [b]
  825 -- Then which we choose would depend on the way in which 'a'
  826 -- is instantiated.  So we report that Foo [b] is a match (mapping b->a)
  827 -- but Foo [Int] is a unifier.  This gives the caller a better chance of
  828 -- giving a suitable error message
  829 
  830 lookupInstEnv' ie vis_mods cls tys
  831   = lookup ie
  832   where
  833     rough_tcs  = roughMatchTcs tys
  834 
  835     --------------
  836     lookup env = case lookupUDFM env cls of
  837                    Nothing -> ([],[])   -- No instances for this class
  838                    Just (ClsIE insts) -> find [] [] insts
  839 
  840     --------------
  841     find ms us [] = (ms, us)
  842     find ms us (item@(ClsInst { is_tcs = mb_tcs, is_tvs = tpl_tvs
  843                               , is_tys = tpl_tys }) : rest)
  844       | not (instIsVisible vis_mods item)
  845       = find ms us rest  -- See Note [Instance lookup and orphan instances]
  846 
  847         -- Fast check for no match, uses the "rough match" fields
  848       | instanceCantMatch rough_tcs mb_tcs
  849       = find ms us rest
  850 
  851       | Just subst <- tcMatchTys tpl_tys tys
  852       = find ((item, map (lookupTyVar subst) tpl_tvs) : ms) us rest
  853 
  854         -- Does not match, so next check whether the things unify
  855         -- See Note [Overlapping instances]
  856         -- Ignore ones that are incoherent: Note [Incoherent instances]
  857       | isIncoherent item
  858       = find ms us rest
  859 
  860       | otherwise
  861       = assertPpr (tys_tv_set `disjointVarSet` tpl_tv_set)
  862                   ((ppr cls <+> ppr tys) $$
  863                    (ppr tpl_tvs <+> ppr tpl_tys)) $
  864                 -- Unification will break badly if the variables overlap
  865                 -- They shouldn't because we allocate separate uniques for them
  866                 -- See Note [Template tyvars are fresh]
  867         case tcUnifyTysFG instanceBindFun tpl_tys tys of
  868           -- We consider MaybeApart to be a case where the instance might
  869           -- apply in the future. This covers an instance like C Int and
  870           -- a target like [W] C (F a), where F is a type family.
  871             SurelyApart              -> find ms us        rest
  872               -- Note [Infinitary substitution in lookup]
  873             MaybeApart MARInfinite _ -> find ms us        rest
  874             _                        -> find ms (item:us) rest
  875       where
  876         tpl_tv_set = mkVarSet tpl_tvs
  877         tys_tv_set = tyCoVarsOfTypes tys
  878 
  879 ---------------
  880 -- This is the common way to call this function.
  881 lookupInstEnv :: Bool              -- Check Safe Haskell overlap restrictions
  882               -> InstEnvs          -- External and home package inst-env
  883               -> Class -> [Type]   -- What we are looking for
  884               -> ClsInstLookupResult
  885 -- ^ See Note [Rules for instance lookup]
  886 -- ^ See Note [Safe Haskell Overlapping Instances] in "GHC.Tc.Solver"
  887 -- ^ See Note [Safe Haskell Overlapping Instances Implementation] in "GHC.Tc.Solver"
  888 lookupInstEnv check_overlap_safe
  889               (InstEnvs { ie_global = pkg_ie
  890                         , ie_local = home_ie
  891                         , ie_visible = vis_mods })
  892               cls
  893               tys
  894   = -- pprTrace "lookupInstEnv" (ppr cls <+> ppr tys $$ ppr home_ie) $
  895     (final_matches, final_unifs, unsafe_overlapped)
  896   where
  897     (home_matches, home_unifs) = lookupInstEnv' home_ie vis_mods cls tys
  898     (pkg_matches,  pkg_unifs)  = lookupInstEnv' pkg_ie  vis_mods cls tys
  899     all_matches = home_matches ++ pkg_matches
  900     all_unifs   = home_unifs   ++ pkg_unifs
  901     final_matches = foldr insert_overlapping [] all_matches
  902         -- Even if the unifs is non-empty (an error situation)
  903         -- we still prune the matches, so that the error message isn't
  904         -- misleading (complaining of multiple matches when some should be
  905         -- overlapped away)
  906 
  907     unsafe_overlapped
  908        = case final_matches of
  909            [match] -> check_safe match
  910            _       -> []
  911 
  912     -- If the selected match is incoherent, discard all unifiers
  913     final_unifs = case final_matches of
  914                     (m:_) | isIncoherent (fst m) -> []
  915                     _                            -> all_unifs
  916 
  917     -- NOTE [Safe Haskell isSafeOverlap]
  918     -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  919     -- We restrict code compiled in 'Safe' mode from overriding code
  920     -- compiled in any other mode. The rationale is that code compiled
  921     -- in 'Safe' mode is code that is untrusted by the ghc user. So
  922     -- we shouldn't let that code change the behaviour of code the
  923     -- user didn't compile in 'Safe' mode since that's the code they
  924     -- trust. So 'Safe' instances can only overlap instances from the
  925     -- same module. A same instance origin policy for safe compiled
  926     -- instances.
  927     check_safe (inst,_)
  928         = case check_overlap_safe && unsafeTopInstance inst of
  929                 -- make sure it only overlaps instances from the same module
  930                 True -> go [] all_matches
  931                 -- most specific is from a trusted location.
  932                 False -> []
  933         where
  934             go bad [] = bad
  935             go bad (i@(x,_):unchecked) =
  936                 if inSameMod x || isOverlappable x
  937                     then go bad unchecked
  938                     else go (i:bad) unchecked
  939 
  940             inSameMod b =
  941                 let na = getName $ getName inst
  942                     la = isInternalName na
  943                     nb = getName $ getName b
  944                     lb = isInternalName nb
  945                 in (la && lb) || (nameModule na == nameModule nb)
  946 
  947     -- We consider the most specific instance unsafe when it both:
  948     --   (1) Comes from a module compiled as `Safe`
  949     --   (2) Is an orphan instance, OR, an instance for a MPTC
  950     unsafeTopInstance inst = isSafeOverlap (is_flag inst) &&
  951         (isOrphan (is_orphan inst) || classArity (is_cls inst) > 1)
  952 
  953 ---------------
  954 insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch]
  955 -- ^ Add a new solution, knocking out strictly less specific ones
  956 -- See Note [Rules for instance lookup]
  957 insert_overlapping new_item [] = [new_item]
  958 insert_overlapping new_item@(new_inst,_) (old_item@(old_inst,_) : old_items)
  959   | new_beats_old        -- New strictly overrides old
  960   , not old_beats_new
  961   , new_inst `can_override` old_inst
  962   = insert_overlapping new_item old_items
  963 
  964   | old_beats_new        -- Old strictly overrides new
  965   , not new_beats_old
  966   , old_inst `can_override` new_inst
  967   = old_item : old_items
  968 
  969   -- Discard incoherent instances; see Note [Incoherent instances]
  970   | isIncoherent old_inst      -- Old is incoherent; discard it
  971   = insert_overlapping new_item old_items
  972   | isIncoherent new_inst      -- New is incoherent; discard it
  973   = old_item : old_items
  974 
  975   -- Equal or incomparable, and neither is incoherent; keep both
  976   | otherwise
  977   = old_item : insert_overlapping new_item old_items
  978   where
  979 
  980     new_beats_old = new_inst `more_specific_than` old_inst
  981     old_beats_new = old_inst `more_specific_than` new_inst
  982 
  983     -- `instB` can be instantiated to match `instA`
  984     -- or the two are equal
  985     instA `more_specific_than` instB
  986       = isJust (tcMatchTys (is_tys instB) (is_tys instA))
  987 
  988     instA `can_override` instB
  989        = isOverlapping instA || isOverlappable instB
  990        -- Overlap permitted if either the more specific instance
  991        -- is marked as overlapping, or the more general one is
  992        -- marked as overlappable.
  993        -- Latest change described in: #9242.
  994        -- Previous change: #3877, Dec 10.
  995 
  996 {-
  997 Note [Incoherent instances]
  998 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  999 For some classes, the choice of a particular instance does not matter, any one
 1000 is good. E.g. consider
 1001 
 1002         class D a b where { opD :: a -> b -> String }
 1003         instance D Int b where ...
 1004         instance D a Int where ...
 1005 
 1006         g (x::Int) = opD x x  -- Wanted: D Int Int
 1007 
 1008 For such classes this should work (without having to add an "instance D Int
 1009 Int", and using -XOverlappingInstances, which would then work). This is what
 1010 -XIncoherentInstances is for: Telling GHC "I don't care which instance you use;
 1011 if you can use one, use it."
 1012 
 1013 Should this logic only work when *all* candidates have the incoherent flag, or
 1014 even when all but one have it? The right choice is the latter, which can be
 1015 justified by comparing the behaviour with how -XIncoherentInstances worked when
 1016 it was only about the unify-check (note [Overlapping instances]):
 1017 
 1018 Example:
 1019         class C a b c where foo :: (a,b,c)
 1020         instance C [a] b Int
 1021         instance [incoherent] [Int] b c
 1022         instance [incoherent] C a Int c
 1023 Thanks to the incoherent flags,
 1024         [Wanted]  C [a] b Int
 1025 works: Only instance one matches, the others just unify, but are marked
 1026 incoherent.
 1027 
 1028 So I can write
 1029         (foo :: ([a],b,Int)) :: ([Int], Int, Int).
 1030 but if that works then I really want to be able to write
 1031         foo :: ([Int], Int, Int)
 1032 as well. Now all three instances from above match. None is more specific than
 1033 another, so none is ruled out by the normal overlapping rules. One of them is
 1034 not incoherent, but we still want this to compile. Hence the
 1035 "all-but-one-logic".
 1036 
 1037 The implementation is in insert_overlapping, where we remove matching
 1038 incoherent instances as long as there are others.
 1039 
 1040 
 1041 
 1042 ************************************************************************
 1043 *                                                                      *
 1044         Binding decisions
 1045 *                                                                      *
 1046 ************************************************************************
 1047 -}
 1048 
 1049 instanceBindFun :: BindFun
 1050 instanceBindFun tv _rhs_ty | isOverlappableTyVar tv = Apart
 1051                            | otherwise              = BindMe
 1052    -- Note [Binding when looking up instances]
 1053 
 1054 {-
 1055 Note [Binding when looking up instances]
 1056 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1057 When looking up in the instance environment, or family-instance environment,
 1058 we are careful about multiple matches, as described above in
 1059 Note [Overlapping instances]
 1060 
 1061 The target tys can contain skolem constants. For existentials and instance variables,
 1062 we can guarantee that those
 1063 are never going to be instantiated to anything, so we should not involve
 1064 them in the unification test. These are called "super skolems". Example:
 1065         class Foo a where { op :: a -> Int }
 1066         instance Foo a => Foo [a]       -- NB overlap
 1067         instance Foo [Int]              -- NB overlap
 1068         data T = forall a. Foo a => MkT a
 1069         f :: T -> Int
 1070         f (MkT x) = op [x,x]
 1071 The op [x,x] means we need (Foo [a]). This `a` will never be instantiated, and
 1072 so it is a super skolem. (See the use of tcInstSuperSkolTyVarsX in
 1073 GHC.Tc.Gen.Pat.tcDataConPat.) Super skolems respond True to
 1074 isOverlappableTyVar, and the use of Apart in instanceBindFun, above, means
 1075 that these will be treated as fresh constants in the unification algorithm
 1076 during instance lookup. Without this treatment, GHC would complain, saying
 1077 that the choice of instance depended on the instantiation of 'a'; but of
 1078 course it isn't *going* to be instantiated. Note that it is necessary that
 1079 the unification algorithm returns SurelyApart for these super-skolems
 1080 for GHC to be able to commit to another instance.
 1081 
 1082 We do this only for super skolems.  For example we reject
 1083         g :: forall a => [a] -> Int
 1084         g x = op x
 1085 on the grounds that the correct instance depends on the instantiation of 'a'
 1086 -}