%
-% (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
+% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
-\section{Class Instance environments}
+\section[InstEnv]{Utilities for typechecking instance declarations}
+
+The bits common to TcInstDcls and TcDeriv.
\begin{code}
module InstEnv (
- InstEnv, emptyInstEnv, addToInstEnv, lookupInstEnv
+ DFunId, ClsInstEnv, InstEnv,
+
+ emptyInstEnv, extendInstEnv, pprInstEnv,
+ lookupInstEnv, InstLookupResult(..),
+ classInstEnv, simpleDFunClassTyCon
) where
#include "HsVersions.h"
-import Var ( TyVar, Id )
-import VarSet
+import Class ( Class )
+import Var ( Id )
+import VarSet ( TyVarSet, unionVarSet, mkVarSet, varSetElems )
import VarEnv ( TyVarSubstEnv )
-import Type ( Type, tyVarsOfTypes )
-import Unify ( unifyTyListsX, matchTys )
+import Maybes ( MaybeErr(..), returnMaB, failMaB, thenMaB, maybeToBool )
+import Name ( getSrcLoc )
+import Type ( Type, tyConAppTyCon,
+ splitSigmaTy, splitDFunTy, tyVarsOfTypes
+ )
+import PprType ( )
+import TyCon ( TyCon )
import Outputable
-import Maybes
+import Unify ( matchTys, unifyTyListsX )
+import UniqFM ( UniqFM, lookupWithDefaultUFM, addToUFM, emptyUFM, eltsUFM )
+import Id ( idType )
+import ErrUtils ( Message )
+import CmdLineOpts
\end{code}
%************************************************************************
%* *
-\section{InstEnv}
+\subsection{The key types}
%* *
%************************************************************************
\begin{code}
-type InstEnv = [(TyVarSet, [Type], Id)]
+type DFunId = Id
+
+type InstEnv = UniqFM ClsInstEnv -- Maps Class to instances for that class
+
+type ClsInstEnv = [(TyVarSet, [Type], DFunId)] -- The instances for a particular class
+
+simpleDFunClassTyCon :: DFunId -> (Class, TyCon)
+simpleDFunClassTyCon dfun
+ = (clas, tycon)
+ where
+ (_,_,clas,[ty]) = splitDFunTy (idType dfun)
+ tycon = tyConAppTyCon ty
+
+pprInstEnv :: InstEnv -> SDoc
+pprInstEnv env
+ = vcat [ brackets (pprWithCommas ppr (varSetElems tyvars)) <+>
+ brackets (pprWithCommas ppr tys) <+> ppr dfun
+ | cls_inst_env <- eltsUFM env
+ , (tyvars, tys, dfun) <- cls_inst_env
+ ]
+\end{code}
+
+%************************************************************************
+%* *
+\subsection{Instance environments: InstEnv and ClsInstEnv}
+%* *
+%************************************************************************
+
+The actual type declarations are in HscTypes.
+
+\begin{code}
+emptyInstEnv :: InstEnv
+emptyInstEnv = emptyUFM
+
+classInstEnv :: InstEnv -> Class -> ClsInstEnv
+classInstEnv env cls = lookupWithDefaultUFM env [] cls
\end{code}
-In some InstEnvs overlap is prohibited; that is, no pair of templates unify.
+A @ClsInstEnv@ lives inside a class, and identifies 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]
+
+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
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+In some ClsInstEnvs, overlap is prohibited; that is, no pair of templates unify.
In others, 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
--Jeff
-\begin{code}
-emptyInstEnv :: InstEnv
-emptyInstEnv = []
-isEmptyInstEnv env = null env
-\end{code}
-
-@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.
+@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.
\begin{code}
-lookupInstEnv :: SDoc -- For error report
- -> InstEnv -- The envt
- -> [Type] -- Key
- -> Maybe (TyVarSubstEnv, Id)
-
-lookupInstEnv doc env key
- = find env
+lookupInstEnv :: InstEnv -- The envt
+ -> Class -> [Type] -- Key
+ -> InstLookupResult
+
+data InstLookupResult
+ = FoundInst -- There is a (template,substitution) pair
+ -- that makes the template match the key,
+ -- and no template is an instance of the key
+ TyVarSubstEnv Id
+
+ | NoMatch Bool -- Boolean is true iff there is at least one
+ -- template that matches the key.
+ -- (but there are other template(s) that are
+ -- instances of the key, so we don't report
+ -- FoundInst)
+ -- The NoMatch True case 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 say there is no match, but identify
+ -- it as ambiguous case in the hope of giving a better error msg.
+ -- See the notes above from Jeff Lewis
+
+lookupInstEnv env key_cls key_tys
+ = find (classInstEnv env key_cls)
where
- key_vars = tyVarsOfTypes key
- find [] = Nothing
+ key_vars = tyVarsOfTypes key_tys
+
+ find [] = NoMatch False
find ((tpl_tyvars, tpl, val) : rest)
- = case matchTys tpl_tyvars tpl key of
+ = case matchTys tpl_tyvars tpl key_tys of
Nothing ->
- case matchTys key_vars key tpl of
+ case matchTys key_vars key_tys tpl of
Nothing -> find rest
- Just (_, _) -> Nothing
+ Just (_, _) -> NoMatch (any_match rest)
Just (subst, leftovers) -> ASSERT( null leftovers )
- Just (subst, val)
+ FoundInst subst val
+
+ any_match rest = or [ maybeToBool (matchTys tvs tpl key_tys)
+ | (tvs,tpl,_) <- rest
+ ]
\end{code}
-@addToInstEnv@ extends a @InstEnv@, checking for overlaps.
+@addToClsInstEnv@ extends a @ClsInstEnv@, checking for overlaps.
A boolean flag controls overlap reporting.
not if they unify but neither is
\begin{code}
-addToInstEnv :: Bool -- True <=> overlap permitted
- -> InstEnv -- Envt
- -> [TyVar] -> [Type] -> Id -- New item
- -> MaybeErr InstEnv -- Success...
- ([Type], Id) -- Failure: Offending overlap
-
-addToInstEnv overlap_ok env ins_tvs ins_tys value
- = insert env
+extendInstEnv :: DynFlags -> InstEnv -> [DFunId] -> (InstEnv, [Message])
+ -- Similar, but all we have is the DFuns
+extendInstEnv dflags env infos
+ = go env [] infos
where
+ go env msgs [] = (env, msgs)
+ go env msgs (dfun:dfuns) = case addToInstEnv dflags env dfun of
+ Succeeded new_env -> go new_env msgs dfuns
+ Failed dfun' -> go env (msg:msgs) dfuns
+ where
+ msg = dupInstErr dfun dfun'
+
+
+dupInstErr dfun1 dfun2
+ -- Overlapping/duplicate instances for given class; msg could be more glamourous
+ = hang (ptext SLIT("Duplicate or overlapping instance declarations:"))
+ 2 (ppr_dfun dfun1 $$ ppr_dfun dfun2)
+ where
+ ppr_dfun dfun = ppr (getSrcLoc dfun) <> colon <+> ppr tau
+ where
+ (_,_,tau) = splitSigmaTy (idType dfun)
+
+addToInstEnv :: DynFlags
+ -> InstEnv -> DFunId
+ -> MaybeErr InstEnv -- Success...
+ DFunId -- Failure: Offending overlap
+
+addToInstEnv dflags inst_env dfun_id
+ = case insert_into (classInstEnv inst_env clas) of
+ Failed stuff -> Failed stuff
+ Succeeded new_env -> Succeeded (addToUFM inst_env clas new_env)
+
+ where
+ (ins_tvs, _, clas, ins_tys) = splitDFunTy (idType dfun_id)
+
ins_tv_set = mkVarSet ins_tvs
- ins_item = (ins_tv_set, ins_tys, value)
+ ins_item = (ins_tv_set, ins_tys, dfun_id)
- insert [] = returnMaB [ins_item]
- insert env@(cur_item@(tpl_tvs, tpl_tys, val) : rest)
+ insert_into [] = returnMaB [ins_item]
+ insert_into env@(cur_item@(tpl_tvs, tpl_tys, val) : rest)
-- FAIL if:
-- (a) they are the same, or
-- (b) they unify, and any sort of overlap is prohibited,
-- (c) they unify but neither is more specific than t'other
| identical
- || (unifiable && not overlap_ok)
+ || (unifiable && not (dopt Opt_AllowOverlappingInstances dflags))
|| (unifiable && not (ins_item_more_specific || cur_item_more_specific))
- = failMaB (tpl_tys, val)
+ = failMaB val
-- New item is an instance of current item, so drop it here
| ins_item_more_specific = returnMaB (ins_item : env)
-- Otherwise carry on
- | otherwise = insert rest `thenMaB` \ rest' ->
+ | otherwise = insert_into rest `thenMaB` \ rest' ->
returnMaB (cur_item : rest')
where
unifiable = maybeToBool (unifyTyListsX (ins_tv_set `unionVarSet` tpl_tvs) tpl_tys ins_tys)
identical = ins_item_more_specific && cur_item_more_specific
\end{code}
+
projects / ghc-hetmet.git / blobdiff