module InstEnv (
DFunId, InstEnv,
- emptyInstEnv, extendInstEnv,
- lookupInstEnv,
- classInstEnv, simpleDFunClassTyCon, checkFunDeps
+ emptyInstEnv, extendInstEnv, extendInstEnvList,
+ lookupInstEnv, instEnvElts,
+ classInstances, simpleDFunClassTyCon, checkFunDeps
) where
#include "HsVersions.h"
import Class ( Class, classTvsFds )
-import Var ( Id )
+import Var ( Id, isTcTyVar )
import VarSet
-import VarEnv
-import TcType ( Type, tcTyConAppTyCon,
- tcSplitDFunTy, tyVarsOfTypes,
- matchTys, unifyTyListsX
+import Type ( TvSubst )
+import TcType ( Type, tcTyConAppTyCon, tcIsTyVarTy,
+ tcSplitDFunTy, tyVarsOfTypes, isExistentialTyVar
)
+import Unify ( tcMatchTys, tcUnifyTys, BindFlag(..) )
import FunDeps ( checkClsFD )
import TyCon ( TyCon )
import Outputable
-import UniqFM ( UniqFM, lookupWithDefaultUFM, emptyUFM, eltsUFM, addToUFM_C )
+import UniqFM ( UniqFM, lookupUFM, emptyUFM, addToUFM_C, eltsUFM )
import Id ( idType )
import CmdLineOpts
import Util ( notNull )
%* *
%************************************************************************
+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
+
\begin{code}
type DFunId = Id
type InstEnv = UniqFM ClsInstEnv -- Maps Class to instances for that class
-type ClsInstEnv = [InstEnvElt] -- The instances for a particular class
+
+data ClsInstEnv
+ = ClsIE [InstEnvElt] -- The instances for a particular class, in any order
+ Bool -- True <=> there is an instance of form C a b c
+ -- If *not* then the common case of looking up
+ -- (C a b c) can fail immediately
+ -- NB: use tcIsTyVarTy: don't look through newtypes!!
+
type InstEnvElt = (TyVarSet, [Type], DFunId)
- -- INVARIANTs: see notes below
+
+-- INVARIANTS:
+-- * [a,b] must be a superset of the free vars of [t1,t2,t3]
+--
+-- * The dfun must itself be quantified over [a,b]
+--
+-- * The template type variables [a,b] are distinct in each item
+-- 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 = emptyUFM
-classInstEnv :: InstEnv -> Class -> ClsInstEnv
-classInstEnv env cls = lookupWithDefaultUFM env [] cls
+instEnvElts :: InstEnv -> [InstEnvElt]
+instEnvElts ie = [elt | ClsIE elts _ <- eltsUFM ie, elt <- elts]
+
+classInstances :: (InstEnv,InstEnv) -> Class -> [InstEnvElt]
+classInstances (pkg_ie, home_ie) cls
+ = get home_ie ++ get pkg_ie
+ where
+ get env = case lookupUFM env cls of
+ Just (ClsIE insts _) -> insts
+ Nothing -> []
+
+extendInstEnvList :: InstEnv -> [DFunId] -> InstEnv
+extendInstEnvList inst_env dfuns = foldl extendInstEnv inst_env dfuns
extendInstEnv :: InstEnv -> DFunId -> InstEnv
extendInstEnv inst_env dfun_id
- = addToUFM_C add inst_env clas [ins_item]
+ = addToUFM_C add inst_env clas (ClsIE [ins_item] ins_tyvar)
where
- add old _ = ins_item : old
+ add (ClsIE cur_insts cur_tyvar) _ = ClsIE (ins_item : cur_insts)
+ (ins_tyvar || cur_tyvar)
(ins_tvs, _, clas, ins_tys) = tcSplitDFunTy (idType dfun_id)
ins_tv_set = mkVarSet ins_tvs
ins_item = (ins_tv_set, ins_tys, dfun_id)
+ ins_tyvar = all tcIsTyVarTy ins_tys
#ifdef UNUSED
pprInstEnv :: InstEnv -> SDoc
pprInstEnv env
= vcat [ brackets (pprWithCommas ppr (varSetElems tyvars)) <+>
brackets (pprWithCommas ppr tys) <+> ppr dfun
- | cls_inst_env <- eltsUFM env
+ | ClsIE cls_inst_env _ <- eltsUFM env
, (tyvars, tys, dfun) <- cls_inst_env
]
#endif
%* *
%************************************************************************
-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
-
-There is an important consistency constraint in the elements of a ClsInstEnv:
-
- * [a,b] must be a superset of the free vars of [t1,t2,t3]
-
- * The dfun must itself be quantified over [a,b]
-
- * More specific instances come before less specific ones,
- where they overlap
-
-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.
-
-
Notes on overlapping instances
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lookupInstEnv :: DynFlags
-> (InstEnv -- External package inst-env
,InstEnv) -- Home-package inst-env
- -> Class -> [Type] -- What we are looking for
- -> ([(TyVarSubstEnv, InstEnvElt)], -- Successful matches
- [Id]) -- These don't match but do unify
+ -> Class -> [Type] -- What we are looking for
+ -> ([(TvSubst, InstEnvElt)], -- Successful matches
+ [Id]) -- These don't match but do unify
-- The second component of the tuple happens when we look up
-- Foo [a]
-- in an InstEnv that has entries for
-- so don't attempt to pune the matches
| otherwise = (pruned_matches, [])
where
+ all_tvs = all tcIsTyVarTy tys
incoherent_ok = dopt Opt_AllowIncoherentInstances dflags
overlap_ok = dopt Opt_AllowOverlappingInstances dflags
- (home_matches, home_unifs) = lookup_inst_env home_ie cls tys
- (pkg_matches, pkg_unifs) = lookup_inst_env pkg_ie cls tys
+ (home_matches, home_unifs) = lookup_inst_env home_ie cls tys all_tvs
+ (pkg_matches, pkg_unifs) = lookup_inst_env pkg_ie cls tys all_tvs
all_matches = home_matches ++ pkg_matches
all_unifs | incoherent_ok = [] -- Don't worry about these if incoherent is ok!
| otherwise = home_unifs ++ pkg_unifs
pruned_matches | overlap_ok = foldr insert_overlapping [] all_matches
| otherwise = all_matches
-lookup_inst_env :: InstEnv -- The envt
- -> Class -> [Type] -- What we are looking for
- -> ([(TyVarSubstEnv, InstEnvElt)], -- Successful matches
- [Id]) -- These don't match but do unify
-lookup_inst_env env key_cls key_tys
- = find (classInstEnv env key_cls) [] []
+lookup_inst_env :: InstEnv -- The envt
+ -> Class -> [Type] -- What we are looking for
+ -> Bool -- All the [Type] are tyvars
+ -> ([(TvSubst, InstEnvElt)], -- Successful matches
+ [Id]) -- These don't match but do unify
+lookup_inst_env env key_cls key_tys key_all_tvs
+ = case lookupUFM env key_cls of
+ Nothing -> ([],[]) -- No instances for this class
+ Just (ClsIE insts has_tv_insts)
+ | key_all_tvs && not has_tv_insts -> ([],[]) -- Short cut for common case
+ -- The thing we are looking up is of form (C a b c), and
+ -- the ClsIE has no instances of that form, so don't bother to search
+ | otherwise -> find insts [] []
where
- key_vars = tyVarsOfTypes key_tys
-
find [] ms us = (ms, us)
find (item@(tpl_tyvars, tpl, dfun_id) : rest) ms us
- = case matchTys tpl_tyvars tpl key_tys of
- Just (subst, leftovers) -> ASSERT( null leftovers )
- find rest ((subst,item):ms) us
+ = case tcMatchTys tpl_tyvars tpl key_tys of
+ Just subst -> find rest ((subst,item):ms) us
Nothing
-- Does not match, so next check whether the things unify
-- [see notes about overlapping instances above]
- -> case unifyTyListsX (key_vars `unionVarSet` tpl_tyvars) key_tys tpl of
+ -> ASSERT2( not (tyVarsOfTypes key_tys `intersectsVarSet` tpl_tyvars),
+ (ppr key_cls <+> ppr key_tys <+> ppr key_all_tvs) $$
+ (ppr dfun_id <+> ppr tpl_tyvars <+> ppr tpl)
+ )
+ -- Unification will break badly if the variables overlap
+ -- They shouldn't because we allocate separate uniques for them
+ case tcUnifyTys bind_fn tpl key_tys of
Just _ -> find rest ms (dfun_id:us)
Nothing -> find rest ms us
-insert_overlapping :: (TyVarSubstEnv, InstEnvElt) -> [(TyVarSubstEnv, InstEnvElt)]
- -> [(TyVarSubstEnv, InstEnvElt)]
+ bind_fn tv | isTcTyVar tv && isExistentialTyVar tv = Skolem
+ | otherwise = BindMe
+ -- 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 pattern-bound 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'
+
+insert_overlapping :: (TvSubst, InstEnvElt) -> [(TvSubst, InstEnvElt)]
+ -> [(TvSubst, InstEnvElt)]
-- Add a new solution, knocking out strictly less specific ones
insert_overlapping new_item [] = [new_item]
insert_overlapping new_item (item:items)
-- Keep new one
| old_beats_new = item : items
-- Keep old one
- | otherwise = item : insert_overlapping new_item items
+ | otherwise = item : insert_overlapping new_item items
-- Keep both
where
new_beats_old = new_item `beats` item
old_beats_new = item `beats` new_item
(_, (tvs1, tys1, _)) `beats` (_, (tvs2, tys2, _))
- = isJust (matchTys tvs2 tys2 tys1) -- A beats B if A is more specific than B
+ = isJust (tcMatchTys tvs2 tys2 tys1) -- A beats B if A is more specific than B
-- I.e. if B can be instantiated to match A
\end{code}
-> Maybe [DFunId] -- Nothing <=> ok
-- Just dfs <=> conflict with dfs
-- Check wheher adding DFunId would break functional-dependency constraints
-checkFunDeps (pkg_ie, home_ie) dfun
+checkFunDeps inst_envs dfun
| null bad_fundeps = Nothing
| otherwise = Just bad_fundeps
where
(ins_tvs, _, clas, ins_tys) = tcSplitDFunTy (idType dfun)
ins_tv_set = mkVarSet ins_tvs
- cls_inst_env = classInstEnv home_ie clas ++ classInstEnv pkg_ie clas
+ cls_inst_env = classInstances inst_envs clas
bad_fundeps = badFunDeps cls_inst_env clas ins_tv_set ins_tys
-badFunDeps :: ClsInstEnv -> Class
+badFunDeps :: [InstEnvElt] -> Class
-> TyVarSet -> [Type] -- Proposed new instance type
-> [DFunId]
badFunDeps cls_inst_env clas ins_tv_set ins_tys