{- (c) The University of Glasgow 2006 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998 \section[InstEnv]{Utilities for typechecking instance declarations} The bits common to TcInstDcls and TcDeriv. -} {-# LANGUAGE CPP, DeriveDataTypeable #-} module InstEnv ( DFunId, InstMatch, ClsInstLookupResult, OverlapFlag(..), OverlapMode(..), setOverlapModeMaybe, ClsInst(..), DFunInstType, pprInstance, pprInstanceHdr, pprInstances, instanceHead, instanceSig, mkLocalInstance, mkImportedInstance, instanceDFunId, updateClsInstDFun, instanceRoughTcs, fuzzyClsInstCmp, orphNamesOfClsInst, InstEnvs(..), VisibleOrphanModules, InstEnv, emptyInstEnv, extendInstEnv, deleteFromInstEnv, deleteDFunFromInstEnv, identicalClsInstHead, extendInstEnvList, lookupUniqueInstEnv, lookupInstEnv, instEnvElts, memberInstEnv, instIsVisible, classInstances, instanceBindFun, instanceCantMatch, roughMatchTcs, isOverlappable, isOverlapping, isIncoherent ) where #include "HsVersions.h" import GhcPrelude import TcType -- InstEnv is really part of the type checker, -- and depends on TcType in many ways import CoreSyn ( IsOrphan(..), isOrphan, chooseOrphanAnchor ) import Module import Class import Var import VarSet import Name import NameSet import Unify import Outputable import ErrUtils import BasicTypes import UniqDFM import Util import Id import Data.Data ( Data ) import Data.Maybe ( isJust, isNothing ) {- ************************************************************************ * * ClsInst: the data type for type-class instances * * ************************************************************************ -} -- | A type-class instance. Note that there is some tricky laziness at work -- here. See Note [ClsInst laziness and the rough-match fields] for more -- details. data ClsInst = ClsInst { -- Used for "rough matching"; see -- Note [ClsInst laziness and the rough-match fields] -- INVARIANT: is_tcs = roughMatchTcs is_tys ClsInst -> Name is_cls_nm :: Name -- ^ Class name , ClsInst -> [Maybe Name] is_tcs :: [Maybe Name] -- ^ Top of type args -- | @is_dfun_name = idName . is_dfun@. -- -- We use 'is_dfun_name' for the visibility check, -- 'instIsVisible', which needs to know the 'Module' which the -- dictionary is defined in. However, we cannot use the 'Module' -- attached to 'is_dfun' since doing so would mean we would -- potentially pull in an entire interface file unnecessarily. -- This was the cause of #12367. , ClsInst -> Name is_dfun_name :: Name -- Used for "proper matching"; see Note [Proper-match fields] , ClsInst -> [TyVar] is_tvs :: [TyVar] -- Fresh template tyvars for full match -- See Note [Template tyvars are fresh] , ClsInst -> Class is_cls :: Class -- The real class , ClsInst -> [Type] is_tys :: [Type] -- Full arg types (mentioning is_tvs) -- INVARIANT: is_dfun Id has type -- forall is_tvs. (...) => is_cls is_tys -- (modulo alpha conversion) , ClsInst -> TyVar is_dfun :: DFunId -- See Note [Haddock assumptions] , ClsInst -> OverlapFlag is_flag :: OverlapFlag -- See detailed comments with -- the decl of BasicTypes.OverlapFlag , ClsInst -> IsOrphan is_orphan :: IsOrphan } deriving Typeable ClsInst DataType Constr Typeable ClsInst => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClsInst -> c ClsInst) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c ClsInst) -> (ClsInst -> Constr) -> (ClsInst -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c ClsInst)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c ClsInst)) -> ((forall b. Data b => b -> b) -> ClsInst -> ClsInst) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r) -> (forall u. (forall d. Data d => d -> u) -> ClsInst -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> ClsInst -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst) -> Data ClsInst ClsInst -> DataType ClsInst -> Constr (forall b. Data b => b -> b) -> ClsInst -> ClsInst (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClsInst -> c ClsInst (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c ClsInst forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> ClsInst -> u forall u. (forall d. Data d => d -> u) -> ClsInst -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c ClsInst forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClsInst -> c ClsInst forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c ClsInst) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c ClsInst) $cClsInst :: Constr $tClsInst :: DataType gmapMo :: (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst $cgmapMo :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst gmapMp :: (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst $cgmapMp :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst gmapM :: (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst $cgmapM :: forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> ClsInst -> m ClsInst gmapQi :: Int -> (forall d. Data d => d -> u) -> ClsInst -> u $cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> ClsInst -> u gmapQ :: (forall d. Data d => d -> u) -> ClsInst -> [u] $cgmapQ :: forall u. (forall d. Data d => d -> u) -> ClsInst -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r $cgmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r $cgmapQl :: forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClsInst -> r gmapT :: (forall b. Data b => b -> b) -> ClsInst -> ClsInst $cgmapT :: (forall b. Data b => b -> b) -> ClsInst -> ClsInst dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c ClsInst) $cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c ClsInst) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c ClsInst) $cdataCast1 :: forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c ClsInst) dataTypeOf :: ClsInst -> DataType $cdataTypeOf :: ClsInst -> DataType toConstr :: ClsInst -> Constr $ctoConstr :: ClsInst -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c ClsInst $cgunfold :: forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c ClsInst gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClsInst -> c ClsInst $cgfoldl :: forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClsInst -> c ClsInst $cp1Data :: Typeable ClsInst Data -- | A fuzzy comparison function for class instances, intended for sorting -- instances before displaying them to the user. fuzzyClsInstCmp :: ClsInst -> ClsInst -> Ordering fuzzyClsInstCmp :: ClsInst -> ClsInst -> Ordering fuzzyClsInstCmp x :: ClsInst x y :: ClsInst y = Name -> Name -> Ordering stableNameCmp (ClsInst -> Name is_cls_nm ClsInst x) (ClsInst -> Name is_cls_nm ClsInst y) Ordering -> Ordering -> Ordering forall a. Monoid a => a -> a -> a `mappend` [Ordering] -> Ordering forall a. Monoid a => [a] -> a mconcat (((Maybe Name, Maybe Name) -> Ordering) -> [(Maybe Name, Maybe Name)] -> [Ordering] forall a b. (a -> b) -> [a] -> [b] map (Maybe Name, Maybe Name) -> Ordering cmp ([Maybe Name] -> [Maybe Name] -> [(Maybe Name, Maybe Name)] forall a b. [a] -> [b] -> [(a, b)] zip (ClsInst -> [Maybe Name] is_tcs ClsInst x) (ClsInst -> [Maybe Name] is_tcs ClsInst y))) where cmp :: (Maybe Name, Maybe Name) -> Ordering cmp (Nothing, Nothing) = Ordering EQ cmp (Nothing, Just _) = Ordering LT cmp (Just _, Nothing) = Ordering GT cmp (Just x :: Name x, Just y :: Name y) = Name -> Name -> Ordering stableNameCmp Name x Name y isOverlappable, isOverlapping, isIncoherent :: ClsInst -> Bool isOverlappable :: ClsInst -> Bool isOverlappable i :: ClsInst i = OverlapMode -> Bool hasOverlappableFlag (OverlapFlag -> OverlapMode overlapMode (ClsInst -> OverlapFlag is_flag ClsInst i)) isOverlapping :: ClsInst -> Bool isOverlapping i :: ClsInst i = OverlapMode -> Bool hasOverlappingFlag (OverlapFlag -> OverlapMode overlapMode (ClsInst -> OverlapFlag is_flag ClsInst i)) isIncoherent :: ClsInst -> Bool isIncoherent i :: ClsInst i = OverlapMode -> Bool hasIncoherentFlag (OverlapFlag -> OverlapMode overlapMode (ClsInst -> OverlapFlag is_flag ClsInst i)) {- Note [ClsInst laziness and the rough-match fields] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose we load 'instance A.C B.T' from A.hi, but suppose that the type B.T is otherwise unused in the program. Then it's stupid to load B.hi, the data type declaration for B.T -- and perhaps further instance declarations! We avoid this as follows: * is_cls_nm, is_tcs, is_dfun_name are all Names. We can poke them to our heart's content. * Proper-match fields. is_dfun, and its related fields is_tvs, is_cls, is_tys contain TyVars, Class, Type, Class etc, and so are all lazy thunks. When we poke any of these fields we'll typecheck the DFunId declaration, and hence pull in interfaces that it refers to. See Note [Proper-match fields]. * Rough-match fields. During instance lookup, we use the is_cls_nm :: Name and is_tcs :: [Maybe Name] fields to perform a "rough match", *without* poking inside the DFunId. The rough-match fields allow us to say "definitely does not match", based only on Names. This laziness is very important; see Trac #12367. Try hard to avoid pulling on the structured fields unless you really need the instance. * Another place to watch is InstEnv.instIsVisible, which needs the module to which the ClsInst belongs. We can get this from is_dfun_name. * In is_tcs, Nothing means that this type arg is a type variable (Just n) means that this type arg is a TyConApp with a type constructor of n. This is always a real tycon, never a synonym! (Two different synonyms might match, but two different real tycons can't.) NB: newtypes are not transparent, though! -} {- Note [Template tyvars are fresh] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The is_tvs field of a ClsInst has *completely fresh* tyvars. That is, they are * distinct from any other ClsInst * distinct from any tyvars free in predicates that may be looked up in the class instance environment Reason for freshness: we use unification when checking for overlap etc, and that requires the tyvars to be distinct. The invariant is checked by the ASSERT in lookupInstEnv'. Note [Proper-match fields] ~~~~~~~~~~~~~~~~~~~~~~~~~ The is_tvs, is_cls, is_tys fields are simply cached values, pulled out (lazily) from the dfun id. They are cached here simply so that we don't need to decompose the DFunId each time we want to match it. The hope is that the rough-match fields mean that we often never poke the proper-match fields. However, note that: * is_tvs must be a superset of the free vars of is_tys * is_tvs, is_tys may be alpha-renamed compared to the ones in the dfun Id Note [Haddock assumptions] ~~~~~~~~~~~~~~~~~~~~~~~~~~ For normal user-written instances, Haddock relies on * the SrcSpan of * the Name of * the is_dfun of * an Instance being equal to * the SrcSpan of * the instance head type of * the InstDecl used to construct the Instance. -} instanceDFunId :: ClsInst -> DFunId instanceDFunId :: ClsInst -> TyVar instanceDFunId = ClsInst -> TyVar is_dfun updateClsInstDFun :: (DFunId -> DFunId) -> ClsInst -> ClsInst updateClsInstDFun :: (TyVar -> TyVar) -> ClsInst -> ClsInst updateClsInstDFun tidy_dfun :: TyVar -> TyVar tidy_dfun ispec :: ClsInst ispec = ClsInst ispec { is_dfun :: TyVar is_dfun = TyVar -> TyVar tidy_dfun (ClsInst -> TyVar is_dfun ClsInst ispec) } instanceRoughTcs :: ClsInst -> [Maybe Name] instanceRoughTcs :: ClsInst -> [Maybe Name] instanceRoughTcs = ClsInst -> [Maybe Name] is_tcs instance NamedThing ClsInst where getName :: ClsInst -> Name getName ispec :: ClsInst ispec = TyVar -> Name forall a. NamedThing a => a -> Name getName (ClsInst -> TyVar is_dfun ClsInst ispec) instance Outputable ClsInst where ppr :: ClsInst -> SDoc ppr = ClsInst -> SDoc pprInstance pprInstance :: ClsInst -> SDoc -- Prints the ClsInst as an instance declaration pprInstance :: ClsInst -> SDoc pprInstance ispec :: ClsInst ispec = SDoc -> Int -> SDoc -> SDoc hang (ClsInst -> SDoc pprInstanceHdr ClsInst ispec) 2 ([SDoc] -> SDoc vcat [ String -> SDoc text "--" SDoc -> SDoc -> SDoc <+> Name -> SDoc pprDefinedAt (ClsInst -> Name forall a. NamedThing a => a -> Name getName ClsInst ispec) , SDoc -> SDoc whenPprDebug (TyVar -> SDoc forall a. Outputable a => a -> SDoc ppr (ClsInst -> TyVar is_dfun ClsInst ispec)) ]) -- * pprInstanceHdr is used in VStudio to populate the ClassView tree pprInstanceHdr :: ClsInst -> SDoc -- Prints the ClsInst as an instance declaration pprInstanceHdr :: ClsInst -> SDoc pprInstanceHdr (ClsInst { is_flag :: ClsInst -> OverlapFlag is_flag = OverlapFlag flag, is_dfun :: ClsInst -> TyVar is_dfun = TyVar dfun }) = String -> SDoc text "instance" SDoc -> SDoc -> SDoc <+> OverlapFlag -> SDoc forall a. Outputable a => a -> SDoc ppr OverlapFlag flag SDoc -> SDoc -> SDoc <+> Type -> SDoc pprSigmaType (TyVar -> Type idType TyVar dfun) pprInstances :: [ClsInst] -> SDoc pprInstances :: [ClsInst] -> SDoc pprInstances ispecs :: [ClsInst] ispecs = [SDoc] -> SDoc vcat ((ClsInst -> SDoc) -> [ClsInst] -> [SDoc] forall a b. (a -> b) -> [a] -> [b] map ClsInst -> SDoc pprInstance [ClsInst] ispecs) instanceHead :: ClsInst -> ([TyVar], Class, [Type]) -- Returns the head, using the fresh tyavs from the ClsInst instanceHead :: ClsInst -> ([TyVar], Class, [Type]) instanceHead (ClsInst { is_tvs :: ClsInst -> [TyVar] is_tvs = [TyVar] tvs, is_tys :: ClsInst -> [Type] is_tys = [Type] tys, is_dfun :: ClsInst -> TyVar is_dfun = TyVar dfun }) = ([TyVar] tvs, Class cls, [Type] tys) where (_, _, cls :: Class cls, _) = Type -> ([TyVar], [Type], Class, [Type]) tcSplitDFunTy (TyVar -> Type idType TyVar dfun) -- | Collects the names of concrete types and type constructors that make -- up the head of a class instance. For instance, given `class Foo a b`: -- -- `instance Foo (Either (Maybe Int) a) Bool` would yield -- [Either, Maybe, Int, Bool] -- -- Used in the implementation of ":info" in GHCi. -- -- The 'tcSplitSigmaTy' is because of -- instance Foo a => Baz T where ... -- The decl is an orphan if Baz and T are both not locally defined, -- even if Foo *is* locally defined orphNamesOfClsInst :: ClsInst -> NameSet orphNamesOfClsInst :: ClsInst -> NameSet orphNamesOfClsInst (ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm, is_tys :: ClsInst -> [Type] is_tys = [Type] tys }) = [Type] -> NameSet orphNamesOfTypes [Type] tys NameSet -> NameSet -> NameSet `unionNameSet` Name -> NameSet unitNameSet Name cls_nm instanceSig :: ClsInst -> ([TyVar], [Type], Class, [Type]) -- Decomposes the DFunId instanceSig :: ClsInst -> ([TyVar], [Type], Class, [Type]) instanceSig ispec :: ClsInst ispec = Type -> ([TyVar], [Type], Class, [Type]) tcSplitDFunTy (TyVar -> Type idType (ClsInst -> TyVar is_dfun ClsInst ispec)) mkLocalInstance :: DFunId -> OverlapFlag -> [TyVar] -> Class -> [Type] -> ClsInst -- Used for local instances, where we can safely pull on the DFunId. -- Consider using newClsInst instead; this will also warn if -- the instance is an orphan. mkLocalInstance :: TyVar -> OverlapFlag -> [TyVar] -> Class -> [Type] -> ClsInst mkLocalInstance dfun :: TyVar dfun oflag :: OverlapFlag oflag tvs :: [TyVar] tvs cls :: Class cls tys :: [Type] tys = ClsInst :: Name -> [Maybe Name] -> Name -> [TyVar] -> Class -> [Type] -> TyVar -> OverlapFlag -> IsOrphan -> ClsInst ClsInst { is_flag :: OverlapFlag is_flag = OverlapFlag oflag, is_dfun :: TyVar is_dfun = TyVar dfun , is_tvs :: [TyVar] is_tvs = [TyVar] tvs , is_dfun_name :: Name is_dfun_name = Name dfun_name , is_cls :: Class is_cls = Class cls, is_cls_nm :: Name is_cls_nm = Name cls_name , is_tys :: [Type] is_tys = [Type] tys, is_tcs :: [Maybe Name] is_tcs = [Type] -> [Maybe Name] roughMatchTcs [Type] tys , is_orphan :: IsOrphan is_orphan = IsOrphan orph } where cls_name :: Name cls_name = Class -> Name className Class cls dfun_name :: Name dfun_name = TyVar -> Name idName TyVar dfun this_mod :: Module this_mod = ASSERT( isExternalName dfun_name ) nameModule dfun_name is_local :: Name -> Bool is_local name :: Name name = Module -> Name -> Bool nameIsLocalOrFrom Module this_mod Name name -- Compute orphanhood. See Note [Orphans] in InstEnv (cls_tvs :: [TyVar] cls_tvs, fds :: [FunDep TyVar] fds) = Class -> ([TyVar], [FunDep TyVar]) classTvsFds Class cls arg_names :: [NameSet] arg_names = [(Name -> Bool) -> NameSet -> NameSet filterNameSet Name -> Bool is_local (Type -> NameSet orphNamesOfType Type ty) | Type ty <- [Type] tys] -- See Note [When exactly is an instance decl an orphan?] orph :: IsOrphan orph | Name -> Bool is_local Name cls_name = OccName -> IsOrphan NotOrphan (Name -> OccName nameOccName Name cls_name) | (IsOrphan -> Bool) -> [IsOrphan] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool all IsOrphan -> Bool notOrphan [IsOrphan] mb_ns = ASSERT( not (null mb_ns) ) head mb_ns | Bool otherwise = IsOrphan IsOrphan notOrphan :: IsOrphan -> Bool notOrphan NotOrphan{} = Bool True notOrphan _ = Bool False mb_ns :: [IsOrphan] -- One for each fundep; a locally-defined name -- that is not in the "determined" arguments mb_ns :: [IsOrphan] mb_ns | [FunDep TyVar] -> Bool forall (t :: * -> *) a. Foldable t => t a -> Bool null [FunDep TyVar] fds = [[NameSet] -> IsOrphan choose_one [NameSet] arg_names] | Bool otherwise = (FunDep TyVar -> IsOrphan) -> [FunDep TyVar] -> [IsOrphan] forall a b. (a -> b) -> [a] -> [b] map FunDep TyVar -> IsOrphan forall (t :: * -> *) a. Foldable t => (a, t TyVar) -> IsOrphan do_one [FunDep TyVar] fds do_one :: (a, t TyVar) -> IsOrphan do_one (_ltvs :: a _ltvs, rtvs :: t TyVar rtvs) = [NameSet] -> IsOrphan choose_one [NameSet ns | (tv :: TyVar tv,ns :: NameSet ns) <- [TyVar] cls_tvs [TyVar] -> [NameSet] -> [(TyVar, NameSet)] forall a b. [a] -> [b] -> [(a, b)] `zip` [NameSet] arg_names , Bool -> Bool not (TyVar tv TyVar -> t TyVar -> Bool forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool `elem` t TyVar rtvs)] choose_one :: [NameSet] -> IsOrphan choose_one nss :: [NameSet] nss = NameSet -> IsOrphan chooseOrphanAnchor ([NameSet] -> NameSet unionNameSets [NameSet] nss) mkImportedInstance :: Name -- ^ the name of the class -> [Maybe Name] -- ^ the types which the class was applied to -> Name -- ^ the 'Name' of the dictionary binding -> DFunId -- ^ the 'Id' of the dictionary. -> OverlapFlag -- ^ may this instance overlap? -> IsOrphan -- ^ is this instance an orphan? -> ClsInst -- Used for imported instances, where we get the rough-match stuff -- from the interface file -- The bound tyvars of the dfun are guaranteed fresh, because -- the dfun has been typechecked out of the same interface file mkImportedInstance :: Name -> [Maybe Name] -> Name -> TyVar -> OverlapFlag -> IsOrphan -> ClsInst mkImportedInstance cls_nm :: Name cls_nm mb_tcs :: [Maybe Name] mb_tcs dfun_name :: Name dfun_name dfun :: TyVar dfun oflag :: OverlapFlag oflag orphan :: IsOrphan orphan = ClsInst :: Name -> [Maybe Name] -> Name -> [TyVar] -> Class -> [Type] -> TyVar -> OverlapFlag -> IsOrphan -> ClsInst ClsInst { is_flag :: OverlapFlag is_flag = OverlapFlag oflag, is_dfun :: TyVar is_dfun = TyVar dfun , is_tvs :: [TyVar] is_tvs = [TyVar] tvs, is_tys :: [Type] is_tys = [Type] tys , is_dfun_name :: Name is_dfun_name = Name dfun_name , is_cls_nm :: Name is_cls_nm = Name cls_nm, is_cls :: Class is_cls = Class cls, is_tcs :: [Maybe Name] is_tcs = [Maybe Name] mb_tcs , is_orphan :: IsOrphan is_orphan = IsOrphan orphan } where (tvs :: [TyVar] tvs, _, cls :: Class cls, tys :: [Type] tys) = Type -> ([TyVar], [Type], Class, [Type]) tcSplitDFunTy (TyVar -> Type idType TyVar dfun) {- Note [When exactly is an instance decl an orphan?] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (see MkIface.instanceToIfaceInst, which implements this) Roughly speaking, an instance is an orphan if its head (after the =>) mentions nothing defined in this module. Functional dependencies complicate the situation though. Consider module M where { class C a b | a -> b } and suppose we are compiling module X: module X where import M data T = ... instance C Int T where ... This instance is an orphan, because when compiling a third module Y we might get a constraint (C Int v), and we'd want to improve v to T. So we must make sure X's instances are loaded, even if we do not directly use anything from X. More precisely, an instance is an orphan iff If there are no fundeps, then at least of the names in the instance head is locally defined. If there are fundeps, then for every fundep, at least one of the names free in a *non-determined* part of the instance head is defined in this module. (Note that these conditions hold trivially if the class is locally defined.) ************************************************************************ * * InstEnv, ClsInstEnv * * ************************************************************************ A @ClsInstEnv@ all the instances of that class. The @Id@ inside a ClsInstEnv mapping is the dfun for that instance. If class C maps to a list containing the item ([a,b], [t1,t2,t3], dfun), then forall a b, C t1 t2 t3 can be constructed by dfun or, to put it another way, we have instance (...) => C t1 t2 t3, witnessed by dfun -} --------------------------------------------------- {- Note [InstEnv determinism] ~~~~~~~~~~~~~~~~~~~~~~~~~~ We turn InstEnvs into a list in some places that don't directly affect the ABI. That happens when we create output for `:info`. Unfortunately that nondeterminism is nonlocal and it's hard to tell what it affects without following a chain of functions. It's also easy to accidentally make that nondeterminism affect the ABI. Furthermore the envs should be relatively small, so it should be free to use deterministic maps here. Testing with nofib and validate detected no difference between UniqFM and UniqDFM. See also Note [Deterministic UniqFM] -} type InstEnv = UniqDFM ClsInstEnv -- Maps Class to instances for that class -- See Note [InstEnv determinism] -- | 'InstEnvs' represents the combination of the global type class instance -- environment, the local type class instance environment, and the set of -- transitively reachable orphan modules (according to what modules have been -- directly imported) used to test orphan instance visibility. data InstEnvs = InstEnvs { InstEnvs -> InstEnv ie_global :: InstEnv, -- External-package instances InstEnvs -> InstEnv ie_local :: InstEnv, -- Home-package instances InstEnvs -> VisibleOrphanModules ie_visible :: VisibleOrphanModules -- Set of all orphan modules transitively -- reachable from the module being compiled -- See Note [Instance lookup and orphan instances] } -- | Set of visible orphan modules, according to what modules have been directly -- imported. This is based off of the dep_orphs field, which records -- transitively reachable orphan modules (modules that define orphan instances). type VisibleOrphanModules = ModuleSet newtype ClsInstEnv = ClsIE [ClsInst] -- The instances for a particular class, in any order instance Outputable ClsInstEnv where ppr :: ClsInstEnv -> SDoc ppr (ClsIE is :: [ClsInst] is) = [ClsInst] -> SDoc pprInstances [ClsInst] is -- INVARIANTS: -- * The is_tvs are distinct in each ClsInst -- of a ClsInstEnv (so we can safely unify them) -- Thus, the @ClassInstEnv@ for @Eq@ might contain the following entry: -- [a] ===> dfun_Eq_List :: forall a. Eq a => Eq [a] -- The "a" in the pattern must be one of the forall'd variables in -- the dfun type. emptyInstEnv :: InstEnv emptyInstEnv :: InstEnv emptyInstEnv = InstEnv forall elt. UniqDFM elt emptyUDFM instEnvElts :: InstEnv -> [ClsInst] instEnvElts :: InstEnv -> [ClsInst] instEnvElts ie :: InstEnv ie = [ClsInst elt | ClsIE elts :: [ClsInst] elts <- InstEnv -> [ClsInstEnv] forall elt. UniqDFM elt -> [elt] eltsUDFM InstEnv ie, ClsInst elt <- [ClsInst] elts] -- See Note [InstEnv determinism] -- | Test if an instance is visible, by checking that its origin module -- is in 'VisibleOrphanModules'. -- See Note [Instance lookup and orphan instances] instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool instIsVisible vis_mods :: VisibleOrphanModules vis_mods ispec :: ClsInst ispec -- NB: Instances from the interactive package always are visible. We can't -- add interactive modules to the set since we keep creating new ones -- as a GHCi session progresses. = case Name -> Maybe Module nameModule_maybe (ClsInst -> Name is_dfun_name ClsInst ispec) of Nothing -> Bool True Just mod :: Module mod | Module -> Bool isInteractiveModule Module mod -> Bool True | IsOrphan IsOrphan <- ClsInst -> IsOrphan is_orphan ClsInst ispec -> Module mod Module -> VisibleOrphanModules -> Bool `elemModuleSet` VisibleOrphanModules vis_mods | Bool otherwise -> Bool True classInstances :: InstEnvs -> Class -> [ClsInst] classInstances :: InstEnvs -> Class -> [ClsInst] classInstances (InstEnvs { ie_global :: InstEnvs -> InstEnv ie_global = InstEnv pkg_ie, ie_local :: InstEnvs -> InstEnv ie_local = InstEnv home_ie, ie_visible :: InstEnvs -> VisibleOrphanModules ie_visible = VisibleOrphanModules vis_mods }) cls :: Class cls = InstEnv -> [ClsInst] get InstEnv home_ie [ClsInst] -> [ClsInst] -> [ClsInst] forall a. [a] -> [a] -> [a] ++ InstEnv -> [ClsInst] get InstEnv pkg_ie where get :: InstEnv -> [ClsInst] get env :: InstEnv env = case InstEnv -> Class -> Maybe ClsInstEnv forall key elt. Uniquable key => UniqDFM elt -> key -> Maybe elt lookupUDFM InstEnv env Class cls of Just (ClsIE insts :: [ClsInst] insts) -> (ClsInst -> Bool) -> [ClsInst] -> [ClsInst] forall a. (a -> Bool) -> [a] -> [a] filter (VisibleOrphanModules -> ClsInst -> Bool instIsVisible VisibleOrphanModules vis_mods) [ClsInst] insts Nothing -> [] -- | Checks for an exact match of ClsInst in the instance environment. -- We use this when we do signature checking in TcRnDriver memberInstEnv :: InstEnv -> ClsInst -> Bool memberInstEnv :: InstEnv -> ClsInst -> Bool memberInstEnv inst_env :: InstEnv inst_env ins_item :: ClsInst ins_item@(ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm } ) = Bool -> (ClsInstEnv -> Bool) -> Maybe ClsInstEnv -> Bool forall b a. b -> (a -> b) -> Maybe a -> b maybe Bool False (\(ClsIE items :: [ClsInst] items) -> (ClsInst -> Bool) -> [ClsInst] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool any (ClsInst -> ClsInst -> Bool identicalDFunType ClsInst ins_item) [ClsInst] items) (InstEnv -> Name -> Maybe ClsInstEnv forall key elt. Uniquable key => UniqDFM elt -> key -> Maybe elt lookupUDFM InstEnv inst_env Name cls_nm) where identicalDFunType :: ClsInst -> ClsInst -> Bool identicalDFunType cls1 :: ClsInst cls1 cls2 :: ClsInst cls2 = Type -> Type -> Bool eqType (TyVar -> Type varType (ClsInst -> TyVar is_dfun ClsInst cls1)) (TyVar -> Type varType (ClsInst -> TyVar is_dfun ClsInst cls2)) extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv extendInstEnvList inst_env :: InstEnv inst_env ispecs :: [ClsInst] ispecs = (InstEnv -> ClsInst -> InstEnv) -> InstEnv -> [ClsInst] -> InstEnv forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl' InstEnv -> ClsInst -> InstEnv extendInstEnv InstEnv inst_env [ClsInst] ispecs extendInstEnv :: InstEnv -> ClsInst -> InstEnv extendInstEnv :: InstEnv -> ClsInst -> InstEnv extendInstEnv inst_env :: InstEnv inst_env ins_item :: ClsInst ins_item@(ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm }) = (ClsInstEnv -> ClsInstEnv -> ClsInstEnv) -> InstEnv -> Name -> ClsInstEnv -> InstEnv forall key elt. Uniquable key => (elt -> elt -> elt) -> UniqDFM elt -> key -> elt -> UniqDFM elt addToUDFM_C ClsInstEnv -> ClsInstEnv -> ClsInstEnv forall p. ClsInstEnv -> p -> ClsInstEnv add InstEnv inst_env Name cls_nm ([ClsInst] -> ClsInstEnv ClsIE [ClsInst ins_item]) where add :: ClsInstEnv -> p -> ClsInstEnv add (ClsIE cur_insts :: [ClsInst] cur_insts) _ = [ClsInst] -> ClsInstEnv ClsIE (ClsInst ins_item ClsInst -> [ClsInst] -> [ClsInst] forall a. a -> [a] -> [a] : [ClsInst] cur_insts) deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv deleteFromInstEnv inst_env :: InstEnv inst_env ins_item :: ClsInst ins_item@(ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm }) = (ClsInstEnv -> ClsInstEnv) -> InstEnv -> Name -> InstEnv forall key elt. Uniquable key => (elt -> elt) -> UniqDFM elt -> key -> UniqDFM elt adjustUDFM ClsInstEnv -> ClsInstEnv adjust InstEnv inst_env Name cls_nm where adjust :: ClsInstEnv -> ClsInstEnv adjust (ClsIE items :: [ClsInst] items) = [ClsInst] -> ClsInstEnv ClsIE ((ClsInst -> Bool) -> [ClsInst] -> [ClsInst] forall a. (a -> Bool) -> [a] -> [a] filterOut (ClsInst -> ClsInst -> Bool identicalClsInstHead ClsInst ins_item) [ClsInst] items) deleteDFunFromInstEnv :: InstEnv -> DFunId -> InstEnv -- Delete a specific instance fron an InstEnv deleteDFunFromInstEnv :: InstEnv -> TyVar -> InstEnv deleteDFunFromInstEnv inst_env :: InstEnv inst_env dfun :: TyVar dfun = (ClsInstEnv -> ClsInstEnv) -> InstEnv -> Class -> InstEnv forall key elt. Uniquable key => (elt -> elt) -> UniqDFM elt -> key -> UniqDFM elt adjustUDFM ClsInstEnv -> ClsInstEnv adjust InstEnv inst_env Class cls where (_, _, cls :: Class cls, _) = Type -> ([TyVar], [Type], Class, [Type]) tcSplitDFunTy (TyVar -> Type idType TyVar dfun) adjust :: ClsInstEnv -> ClsInstEnv adjust (ClsIE items :: [ClsInst] items) = [ClsInst] -> ClsInstEnv ClsIE ((ClsInst -> Bool) -> [ClsInst] -> [ClsInst] forall a. (a -> Bool) -> [a] -> [a] filterOut ClsInst -> Bool same_dfun [ClsInst] items) same_dfun :: ClsInst -> Bool same_dfun (ClsInst { is_dfun :: ClsInst -> TyVar is_dfun = TyVar dfun' }) = TyVar dfun TyVar -> TyVar -> Bool forall a. Eq a => a -> a -> Bool == TyVar dfun' identicalClsInstHead :: ClsInst -> ClsInst -> Bool -- ^ True when when the instance heads are the same -- e.g. both are Eq [(a,b)] -- Used for overriding in GHCi -- Obviously should be insenstive to alpha-renaming identicalClsInstHead :: ClsInst -> ClsInst -> Bool identicalClsInstHead (ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm1, is_tcs :: ClsInst -> [Maybe Name] is_tcs = [Maybe Name] rough1, is_tys :: ClsInst -> [Type] is_tys = [Type] tys1 }) (ClsInst { is_cls_nm :: ClsInst -> Name is_cls_nm = Name cls_nm2, is_tcs :: ClsInst -> [Maybe Name] is_tcs = [Maybe Name] rough2, is_tys :: ClsInst -> [Type] is_tys = [Type] tys2 }) = Name cls_nm1 Name -> Name -> Bool forall a. Eq a => a -> a -> Bool == Name cls_nm2 Bool -> Bool -> Bool && Bool -> Bool not ([Maybe Name] -> [Maybe Name] -> Bool instanceCantMatch [Maybe Name] rough1 [Maybe Name] rough2) -- Fast check for no match, uses the "rough match" fields Bool -> Bool -> Bool && Maybe TCvSubst -> Bool forall a. Maybe a -> Bool isJust ([Type] -> [Type] -> Maybe TCvSubst tcMatchTys [Type] tys1 [Type] tys2) Bool -> Bool -> Bool && Maybe TCvSubst -> Bool forall a. Maybe a -> Bool isJust ([Type] -> [Type] -> Maybe TCvSubst tcMatchTys [Type] tys2 [Type] tys1) {- ************************************************************************ * * Looking up an instance * * ************************************************************************ @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match. Since the env is kept ordered, the first match must be the only one. The thing we are looking up can have an arbitrary "flexi" part. Note [Instance lookup and orphan instances] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose we are compiling a module M, and we have a zillion packages loaded, and we are looking up an instance for C (T W). If we find a match in module 'X' from package 'p', should be "in scope"; that is, is p:X in the transitive closure of modules imported from M? The difficulty is that the "zillion packages" might include ones loaded through earlier invocations of the GHC API, or earlier module loads in GHCi. They might not be in the dependencies of M itself; and if not, the instances in them should not be visible. Trac #2182, #8427. There are two cases: * If the instance is *not an orphan*, then module X defines C, T, or W. And in order for those types to be involved in typechecking M, it must be that X is in the transitive closure of M's imports. So we can use the instance. * If the instance *is an orphan*, the above reasoning does not apply. So we keep track of the set of orphan modules transitively below M; this is the ie_visible field of InstEnvs, of type VisibleOrphanModules. If module p:X is in this set, then we can use the instance, otherwise we can't. 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: http://www.haskell.org/ghc/docs/latest/html/users_guide/glasgow_exts.html#instance-overlap The willingness to be overlapped or incoherent is a property of the instance declaration itself, controlled as follows: * An instance is "incoherent" if it has an INCOHERENT pragma, or if it appears in a module compiled with -XIncoherentInstances. * An instance is "overlappable" 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" if it has an OVERLAPPING or OVERLAPS pragma, or if it appears in a module compiled with -XOverlappingInstances, or if the instance is incoherent. compiled with -XOverlappingInstances. 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. * Find 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*. * Eliminate any candidate `IX` for which both of the following hold: - There is another candidate `IY` that is strictly more specific; 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.) - If exactly one non-incoherent candidate remains, select it. If all remaining candidates are incoherent, select an arbitrary one. Otherwise the search fails (i.e. when more than one surviving candidate is not incoherent). - If the selected candidate (from the previous step) is incoherent, the search succeeds, returning that candidate. - If not, find all instances that *unify* with the target constraint, but do not *match* it. Such non-candidate instances might match when the target constraint is further instantiated. If all of them are incoherent, the search succeeds, returning the selected candidate; if not, the search fails. 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], -} D a) => D [a] where d = c instance C [Int] where c = [37] main = print (d :: [Int]) \end{pseudocode} What do you think `main' prints (assuming we have overlapping instances, and all that turned on)? Well, the instance for `D' at type `[a]' is defined to be `c' at the same type, and we've got an instance of `C' at `[Int]', so the answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because the `C [Int]' instance is more specific). Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That was easy ;-) Let's just consult hugs for good measure. Wait - if I use old hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it doesn't even compile! What's going on!? What hugs complains about is the `D [a]' instance decl. \begin{pseudocode} ERROR "mj.hs" (line 10): Cannot build superclass instance *** Instance : D [a] *** Context supplied : D a *** Required superclass : C [a] \end{pseudocode} You might wonder what hugs is complaining about. It's saying that you need to add `C [a]' to the context of the `D [a]' instance (as appears in comments). But there's that `C [a]' instance decl one line above that says that I can reduce the need for a `C [a]' instance to the need for a `C a' instance, and in this case, I already have the necessary `C a' instance (since we have `D a' explicitly in the context, and `C' is a superclass of `D'). Unfortunately, the above reasoning indicates a premature commitment to the generic `C [a]' instance. I.e., it prematurely rules out the more specific instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to add the context that hugs suggests (uncomment the `C [a]'), effectively deferring the decision about which instance to use. Now, interestingly enough, 4.04 has this same bug, but it's covered up in this case by a little known `optimization' that was disabled in 4.06. Ghc-4.04 silently inserts any missing superclass context into an instance declaration. In this case, it silently inserts the `C [a]', and everything happens to work out. (See `basicTypes/MkId:mkDictFunId' for the code in question. Search for `Mark Jones', although Mark claims no credit for the `optimization' in question, and would rather it stopped being called the `Mark Jones optimization' ;-) So, what's the fix? I think hugs has it right. Here's why. Let's try something else out with ghc-4.04. Let's add the following line: d' :: D a => [a] d' = c Everyone raise their hand who thinks that `d :: [Int]' should give a different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The `optimization' only applies to instance decls, not to regular bindings, giving inconsistent behavior. Old hugs had this same bug. Here's how we fixed it: like GHC, the list of instances for a given class is ordered, so that more specific instances come before more generic ones. For example, the instance list for C might contain: ..., C Int, ..., C a, ... When we go to look for a `C Int' instance we'll get that one first. But what if we go looking for a `C b' (`b' is unconstrained)? We'll pass the `C Int' instance, and keep going. But if `b' is unconstrained, then we don't know yet if the more specific instance will eventually apply. GHC keeps going, and matches on the generic `C a'. The fix is to, at each step, check to see if there's a reverse match, and if so, abort the search. This prevents hugs from prematurely chosing a generic instance when a more specific one exists. --Jeff BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in this test. Suppose the instance envt had ..., forall a b. C a a b, ..., forall a b c. C a b c, ... (still most specific first) Now suppose we are looking for (C x y Int), where x and y are unconstrained. C x y Int doesn't match the template {a,b} C a a b but neither does C a a b match the template {x,y} C x y Int But still x and y might subsequently be unified so they *do* match. Simple story: unify, don't match. -} type DFunInstType = Maybe Type -- Just ty => Instantiate with this type -- Nothing => Instantiate with any type of this tyvar's kind -- See Note [DFunInstType: instantiating types] type InstMatch = (ClsInst, [DFunInstType]) type ClsInstLookupResult = ( [InstMatch] -- Successful matches , [ClsInst] -- These don't match but do unify , [InstMatch] ) -- Unsafe overlapped instances under Safe Haskell -- (see Note [Safe Haskell Overlapping Instances] in -- TcSimplify). {- Note [DFunInstType: instantiating types] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A successful match is a ClsInst, together with the types at which the dfun_id in the ClsInst should be instantiated The instantiating types are (Either TyVar Type)s because the dfun might have some tyvars that *only* appear in arguments dfun :: forall a b. C a b, Ord b => D [a] When we match this against D [ty], we return the instantiating types [Just ty, Nothing] where the 'Nothing' indicates that 'b' can be freely instantiated. (The caller instantiates it to a flexi type variable, which will presumably later become fixed via functional dependencies.) -} -- |Look up an instance in the given instance environment. The given class application must match exactly -- one instance and the match may not contain any flexi type variables. If the lookup is unsuccessful, -- yield 'Left errorMessage'. lookupUniqueInstEnv :: InstEnvs -> Class -> [Type] -> Either MsgDoc (ClsInst, [Type]) lookupUniqueInstEnv :: InstEnvs -> Class -> [Type] -> Either SDoc (ClsInst, [Type]) lookupUniqueInstEnv instEnv :: InstEnvs instEnv cls :: Class cls tys :: [Type] tys = case Bool -> InstEnvs -> Class -> [Type] -> ClsInstLookupResult lookupInstEnv Bool False InstEnvs instEnv Class cls [Type] tys of ([(inst :: ClsInst inst, inst_tys :: [DFunInstType] inst_tys)], _, _) | Bool noFlexiVar -> (ClsInst, [Type]) -> Either SDoc (ClsInst, [Type]) forall a b. b -> Either a b Right (ClsInst inst, [Type] inst_tys') | Bool otherwise -> SDoc -> Either SDoc (ClsInst, [Type]) forall a b. a -> Either a b Left (SDoc -> Either SDoc (ClsInst, [Type])) -> SDoc -> Either SDoc (ClsInst, [Type]) forall a b. (a -> b) -> a -> b $ String -> SDoc text "flexible type variable:" SDoc -> SDoc -> SDoc <+> (Type -> SDoc forall a. Outputable a => a -> SDoc ppr (Type -> SDoc) -> Type -> SDoc forall a b. (a -> b) -> a -> b $ TyCon -> [Type] -> Type mkTyConApp (Class -> TyCon classTyCon Class cls) [Type] tys) where inst_tys' :: [Type] inst_tys' = [Type ty | Just ty :: Type ty <- [DFunInstType] inst_tys] noFlexiVar :: Bool noFlexiVar = (DFunInstType -> Bool) -> [DFunInstType] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool all DFunInstType -> Bool forall a. Maybe a -> Bool isJust [DFunInstType] inst_tys _other :: ClsInstLookupResult _other -> SDoc -> Either SDoc (ClsInst, [Type]) forall a b. a -> Either a b Left (SDoc -> Either SDoc (ClsInst, [Type])) -> SDoc -> Either SDoc (ClsInst, [Type]) forall a b. (a -> b) -> a -> b $ String -> SDoc text "instance not found" SDoc -> SDoc -> SDoc <+> (Type -> SDoc forall a. Outputable a => a -> SDoc ppr (Type -> SDoc) -> Type -> SDoc forall a b. (a -> b) -> a -> b $ TyCon -> [Type] -> Type mkTyConApp (Class -> TyCon classTyCon Class cls) [Type] tys) lookupInstEnv' :: InstEnv -- InstEnv to look in -> VisibleOrphanModules -- But filter against this -> Class -> [Type] -- What we are looking for -> ([InstMatch], -- Successful matches [ClsInst]) -- These don't match but do unify -- (no incoherent ones in here) -- The second component of the result pair happens when we look up -- Foo [a] -- in an InstEnv that has entries for -- Foo [Int] -- Foo [b] -- Then which we choose would depend on the way in which 'a' -- is instantiated. So we report that Foo [b] is a match (mapping b->a) -- but Foo [Int] is a unifier. This gives the caller a better chance of -- giving a suitable error message lookupInstEnv' :: InstEnv -> VisibleOrphanModules -> Class -> [Type] -> ([InstMatch], [ClsInst]) lookupInstEnv' ie :: InstEnv ie vis_mods :: VisibleOrphanModules vis_mods cls :: Class cls tys :: [Type] tys = InstEnv -> ([InstMatch], [ClsInst]) lookup InstEnv ie where rough_tcs :: [Maybe Name] rough_tcs = [Type] -> [Maybe Name] roughMatchTcs [Type] tys all_tvs :: Bool all_tvs = (Maybe Name -> Bool) -> [Maybe Name] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool all Maybe Name -> Bool forall a. Maybe a -> Bool isNothing [Maybe Name] rough_tcs -------------- lookup :: InstEnv -> ([InstMatch], [ClsInst]) lookup env :: InstEnv env = case InstEnv -> Class -> Maybe ClsInstEnv forall key elt. Uniquable key => UniqDFM elt -> key -> Maybe elt lookupUDFM InstEnv env Class cls of Nothing -> ([],[]) -- No instances for this class Just (ClsIE insts :: [ClsInst] insts) -> [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [] [] [ClsInst] insts -------------- find :: [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find ms :: [InstMatch] ms us :: [ClsInst] us [] = ([InstMatch] ms, [ClsInst] us) find ms :: [InstMatch] ms us :: [ClsInst] us (item :: ClsInst item@(ClsInst { is_tcs :: ClsInst -> [Maybe Name] is_tcs = [Maybe Name] mb_tcs, is_tvs :: ClsInst -> [TyVar] is_tvs = [TyVar] tpl_tvs , is_tys :: ClsInst -> [Type] is_tys = [Type] tpl_tys }) : rest :: [ClsInst] rest) | Bool -> Bool not (VisibleOrphanModules -> ClsInst -> Bool instIsVisible VisibleOrphanModules vis_mods ClsInst item) = [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [InstMatch] ms [ClsInst] us [ClsInst] rest -- See Note [Instance lookup and orphan instances] -- Fast check for no match, uses the "rough match" fields | [Maybe Name] -> [Maybe Name] -> Bool instanceCantMatch [Maybe Name] rough_tcs [Maybe Name] mb_tcs = [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [InstMatch] ms [ClsInst] us [ClsInst] rest | Just subst :: TCvSubst subst <- [Type] -> [Type] -> Maybe TCvSubst tcMatchTys [Type] tpl_tys [Type] tys = [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find ((ClsInst item, (TyVar -> DFunInstType) -> [TyVar] -> [DFunInstType] forall a b. (a -> b) -> [a] -> [b] map (TCvSubst -> TyVar -> DFunInstType lookupTyVar TCvSubst subst) [TyVar] tpl_tvs) InstMatch -> [InstMatch] -> [InstMatch] forall a. a -> [a] -> [a] : [InstMatch] ms) [ClsInst] us [ClsInst] rest -- Does not match, so next check whether the things unify -- See Note [Overlapping instances] -- Ignore ones that are incoherent: Note [Incoherent instances] | ClsInst -> Bool isIncoherent ClsInst item = [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [InstMatch] ms [ClsInst] us [ClsInst] rest | Bool otherwise = ASSERT2( tyCoVarsOfTypes tys `disjointVarSet` tpl_tv_set, (ppr cls <+> ppr tys <+> ppr all_tvs) $$ (ppr tpl_tvs <+> ppr tpl_tys) ) -- Unification will break badly if the variables overlap -- They shouldn't because we allocate separate uniques for them -- See Note [Template tyvars are fresh] case (TyVar -> BindFlag) -> [Type] -> [Type] -> Maybe TCvSubst tcUnifyTys TyVar -> BindFlag instanceBindFun [Type] tpl_tys [Type] tys of Just _ -> [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [InstMatch] ms (ClsInst itemClsInst -> [ClsInst] -> [ClsInst] forall a. a -> [a] -> [a] :[ClsInst] us) [ClsInst] rest Nothing -> [InstMatch] -> [ClsInst] -> [ClsInst] -> ([InstMatch], [ClsInst]) find [InstMatch] ms [ClsInst] us [ClsInst] rest where tpl_tv_set :: TyCoVarSet tpl_tv_set = [TyVar] -> TyCoVarSet mkVarSet [TyVar] tpl_tvs --------------- -- This is the common way to call this function. lookupInstEnv :: Bool -- Check Safe Haskell overlap restrictions -> InstEnvs -- External and home package inst-env -> Class -> [Type] -- What we are looking for -> ClsInstLookupResult -- ^ See Note [Rules for instance lookup] -- ^ See Note [Safe Haskell Overlapping Instances] in TcSimplify -- ^ See Note [Safe Haskell Overlapping Instances Implementation] in TcSimplify lookupInstEnv :: Bool -> InstEnvs -> Class -> [Type] -> ClsInstLookupResult lookupInstEnv check_overlap_safe :: Bool check_overlap_safe (InstEnvs { ie_global :: InstEnvs -> InstEnv ie_global = InstEnv pkg_ie , ie_local :: InstEnvs -> InstEnv ie_local = InstEnv home_ie , ie_visible :: InstEnvs -> VisibleOrphanModules ie_visible = VisibleOrphanModules vis_mods }) cls :: Class cls tys :: [Type] tys = -- pprTrace "lookupInstEnv" (ppr cls <+> ppr tys $$ ppr home_ie) $ ([InstMatch] final_matches, [ClsInst] final_unifs, [InstMatch] unsafe_overlapped) where (home_matches :: [InstMatch] home_matches, home_unifs :: [ClsInst] home_unifs) = InstEnv -> VisibleOrphanModules -> Class -> [Type] -> ([InstMatch], [ClsInst]) lookupInstEnv' InstEnv home_ie VisibleOrphanModules vis_mods Class cls [Type] tys (pkg_matches :: [InstMatch] pkg_matches, pkg_unifs :: [ClsInst] pkg_unifs) = InstEnv -> VisibleOrphanModules -> Class -> [Type] -> ([InstMatch], [ClsInst]) lookupInstEnv' InstEnv pkg_ie VisibleOrphanModules vis_mods Class cls [Type] tys all_matches :: [InstMatch] all_matches = [InstMatch] home_matches [InstMatch] -> [InstMatch] -> [InstMatch] forall a. [a] -> [a] -> [a] ++ [InstMatch] pkg_matches all_unifs :: [ClsInst] all_unifs = [ClsInst] home_unifs [ClsInst] -> [ClsInst] -> [ClsInst] forall a. [a] -> [a] -> [a] ++ [ClsInst] pkg_unifs final_matches :: [InstMatch] final_matches = (InstMatch -> [InstMatch] -> [InstMatch]) -> [InstMatch] -> [InstMatch] -> [InstMatch] forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr InstMatch -> [InstMatch] -> [InstMatch] insert_overlapping [] [InstMatch] all_matches -- Even if the unifs is non-empty (an error situation) -- we still prune the matches, so that the error message isn't -- misleading (complaining of multiple matches when some should be -- overlapped away) unsafe_overlapped :: [InstMatch] unsafe_overlapped = case [InstMatch] final_matches of [match :: InstMatch match] -> InstMatch -> [InstMatch] forall b. (ClsInst, b) -> [InstMatch] check_safe InstMatch match _ -> [] -- If the selected match is incoherent, discard all unifiers final_unifs :: [ClsInst] final_unifs = case [InstMatch] final_matches of (m :: InstMatch m:_) | ClsInst -> Bool isIncoherent (InstMatch -> ClsInst forall a b. (a, b) -> a fst InstMatch m) -> [] _ -> [ClsInst] all_unifs -- NOTE [Safe Haskell isSafeOverlap] -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -- We restrict code compiled in 'Safe' mode from overriding code -- compiled in any other mode. The rationale is that code compiled -- in 'Safe' mode is code that is untrusted by the ghc user. So -- we shouldn't let that code change the behaviour of code the -- user didn't compile in 'Safe' mode since that's the code they -- trust. So 'Safe' instances can only overlap instances from the -- same module. A same instance origin policy for safe compiled -- instances. check_safe :: (ClsInst, b) -> [InstMatch] check_safe (inst :: ClsInst inst,_) = case Bool check_overlap_safe Bool -> Bool -> Bool && ClsInst -> Bool unsafeTopInstance ClsInst inst of -- make sure it only overlaps instances from the same module True -> [InstMatch] -> [InstMatch] -> [InstMatch] forall b. [(ClsInst, b)] -> [(ClsInst, b)] -> [(ClsInst, b)] go [] [InstMatch] all_matches -- most specific is from a trusted location. False -> [] where go :: [(ClsInst, b)] -> [(ClsInst, b)] -> [(ClsInst, b)] go bad :: [(ClsInst, b)] bad [] = [(ClsInst, b)] bad go bad :: [(ClsInst, b)] bad (i :: (ClsInst, b) i@(x :: ClsInst x,_):unchecked :: [(ClsInst, b)] unchecked) = if ClsInst -> Bool forall a. NamedThing a => a -> Bool inSameMod ClsInst x Bool -> Bool -> Bool || ClsInst -> Bool isOverlappable ClsInst x then [(ClsInst, b)] -> [(ClsInst, b)] -> [(ClsInst, b)] go [(ClsInst, b)] bad [(ClsInst, b)] unchecked else [(ClsInst, b)] -> [(ClsInst, b)] -> [(ClsInst, b)] go ((ClsInst, b) i(ClsInst, b) -> [(ClsInst, b)] -> [(ClsInst, b)] forall a. a -> [a] -> [a] :[(ClsInst, b)] bad) [(ClsInst, b)] unchecked inSameMod :: a -> Bool inSameMod b :: a b = let na :: Name na = Name -> Name forall a. NamedThing a => a -> Name getName (Name -> Name) -> Name -> Name forall a b. (a -> b) -> a -> b $ ClsInst -> Name forall a. NamedThing a => a -> Name getName ClsInst inst la :: Bool la = Name -> Bool isInternalName Name na nb :: Name nb = Name -> Name forall a. NamedThing a => a -> Name getName (Name -> Name) -> Name -> Name forall a b. (a -> b) -> a -> b $ a -> Name forall a. NamedThing a => a -> Name getName a b lb :: Bool lb = Name -> Bool isInternalName Name nb in (Bool la Bool -> Bool -> Bool && Bool lb) Bool -> Bool -> Bool || (HasDebugCallStack => Name -> Module Name -> Module nameModule Name na Module -> Module -> Bool forall a. Eq a => a -> a -> Bool == HasDebugCallStack => Name -> Module Name -> Module nameModule Name nb) -- We consider the most specific instance unsafe when it both: -- (1) Comes from a module compiled as `Safe` -- (2) Is an orphan instance, OR, an instance for a MPTC unsafeTopInstance :: ClsInst -> Bool unsafeTopInstance inst :: ClsInst inst = OverlapFlag -> Bool isSafeOverlap (ClsInst -> OverlapFlag is_flag ClsInst inst) Bool -> Bool -> Bool && (IsOrphan -> Bool isOrphan (ClsInst -> IsOrphan is_orphan ClsInst inst) Bool -> Bool -> Bool || Class -> Int classArity (ClsInst -> Class is_cls ClsInst inst) Int -> Int -> Bool forall a. Ord a => a -> a -> Bool > 1) --------------- insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch] -- ^ Add a new solution, knocking out strictly less specific ones -- See Note [Rules for instance lookup] insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch] insert_overlapping new_item :: InstMatch new_item [] = [InstMatch new_item] insert_overlapping new_item :: InstMatch new_item@(new_inst :: ClsInst new_inst,_) (old_item :: InstMatch old_item@(old_inst :: ClsInst old_inst,_) : old_items :: [InstMatch] old_items) | Bool new_beats_old -- New strictly overrides old , Bool -> Bool not Bool old_beats_new , ClsInst new_inst ClsInst -> ClsInst -> Bool `can_override` ClsInst old_inst = InstMatch -> [InstMatch] -> [InstMatch] insert_overlapping InstMatch new_item [InstMatch] old_items | Bool old_beats_new -- Old strictly overrides new , Bool -> Bool not Bool new_beats_old , ClsInst old_inst ClsInst -> ClsInst -> Bool `can_override` ClsInst new_inst = InstMatch old_item InstMatch -> [InstMatch] -> [InstMatch] forall a. a -> [a] -> [a] : [InstMatch] old_items -- Discard incoherent instances; see Note [Incoherent instances] | ClsInst -> Bool isIncoherent ClsInst old_inst -- Old is incoherent; discard it = InstMatch -> [InstMatch] -> [InstMatch] insert_overlapping InstMatch new_item [InstMatch] old_items | ClsInst -> Bool isIncoherent ClsInst new_inst -- New is incoherent; discard it = InstMatch old_item InstMatch -> [InstMatch] -> [InstMatch] forall a. a -> [a] -> [a] : [InstMatch] old_items -- Equal or incomparable, and neither is incoherent; keep both | Bool otherwise = InstMatch old_item InstMatch -> [InstMatch] -> [InstMatch] forall a. a -> [a] -> [a] : InstMatch -> [InstMatch] -> [InstMatch] insert_overlapping InstMatch new_item [InstMatch] old_items where new_beats_old :: Bool new_beats_old = ClsInst new_inst ClsInst -> ClsInst -> Bool `more_specific_than` ClsInst old_inst old_beats_new :: Bool old_beats_new = ClsInst old_inst ClsInst -> ClsInst -> Bool `more_specific_than` ClsInst new_inst -- `instB` can be instantiated to match `instA` -- or the two are equal instA :: ClsInst instA more_specific_than :: ClsInst -> ClsInst -> Bool `more_specific_than` instB :: ClsInst instB = Maybe TCvSubst -> Bool forall a. Maybe a -> Bool isJust ([Type] -> [Type] -> Maybe TCvSubst tcMatchTys (ClsInst -> [Type] is_tys ClsInst instB) (ClsInst -> [Type] is_tys ClsInst instA)) instA :: ClsInst instA can_override :: ClsInst -> ClsInst -> Bool `can_override` instB :: ClsInst instB = ClsInst -> Bool isOverlapping ClsInst instA Bool -> Bool -> Bool || ClsInst -> Bool isOverlappable ClsInst instB -- Overlap permitted if either the more specific instance -- is marked as overlapping, or the more general one is -- marked as overlappable. -- Latest change described in: Trac #9242. -- Previous change: Trac #3877, Dec 10. {- Note [Incoherent instances] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ For some classes, the choice of a particular instance does not matter, any one is good. E.g. consider class D a b where { opD :: a -> b -> String } instance D Int b where ... instance D a Int where ... g (x::Int) = opD x x -- Wanted: D Int Int For such classes this should work (without having to add an "instance D Int Int", and using -XOverlappingInstances, which would then work). This is what -XIncoherentInstances is for: Telling GHC "I don't care which instance you use; if you can use one, use it." Should this logic only work when *all* candidates have the incoherent flag, or even when all but one have it? The right choice is the latter, which can be justified by comparing the behaviour with how -XIncoherentInstances worked when it was only about the unify-check (note [Overlapping instances]): Example: class C a b c where foo :: (a,b,c) instance C [a] b Int instance [incoherent] [Int] b c instance [incoherent] C a Int c Thanks to the incoherent flags, [Wanted] C [a] b Int works: Only instance one matches, the others just unify, but are marked incoherent. So I can write (foo :: ([a],b,Int)) :: ([Int], Int, Int). but if that works then I really want to be able to write foo :: ([Int], Int, Int) as well. Now all three instances from above match. None is more specific than another, so none is ruled out by the normal overlapping rules. One of them is not incoherent, but we still want this to compile. Hence the "all-but-one-logic". The implementation is in insert_overlapping, where we remove matching incoherent instances as long as there are others. ************************************************************************ * * Binding decisions * * ************************************************************************ -} instanceBindFun :: TyCoVar -> BindFlag instanceBindFun :: TyVar -> BindFlag instanceBindFun tv :: TyVar tv | TyVar -> Bool isOverlappableTyVar TyVar tv = BindFlag Skolem | Bool otherwise = BindFlag BindMe -- Note [Binding when looking up instances] {- Note [Binding when looking up instances] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When looking up in the instance environment, or family-instance environment, we are careful about multiple matches, as described above in Note [Overlapping instances] The key_tys can contain skolem constants, and we can guarantee that those are never going to be instantiated to anything, so we should not involve them in the unification test. Example: class Foo a where { op :: a -> Int } instance Foo a => Foo [a] -- NB overlap instance Foo [Int] -- NB overlap data T = forall a. Foo a => MkT a f :: T -> Int f (MkT x) = op [x,x] The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd complain, saying that the choice of instance depended on the instantiation of 'a'; but of course it isn't *going* to be instantiated. We do this only for isOverlappableTyVar skolems. For example we reject g :: forall a => [a] -> Int g x = op x on the grounds that the correct instance depends on the instantiation of 'a' -}