+
+While @lookupFamInstEnv@ uses a one-way match, the next function
+@lookupFamInstEnvUnify@ uses two-way matching (ie, unification). This is
+needed to check for overlapping instances.
+
+For class instances, these two variants of lookup are combined into one
+function (cf, @InstEnv@). We don't do that for family instances as the
+results of matching and unification are used in two different contexts.
+Moreover, matching is the wildly more frequently used operation in the case of
+indexed synonyms and we don't want to slow that down by needless unification.
+
+\begin{code}
+lookupFamInstEnvUnify :: (FamInstEnv, FamInstEnv) -> TyCon -> [Type]
+ -> [(FamInstMatch)]
+lookupFamInstEnvUnify (pkg_ie, home_ie) fam tys
+ = home_matches ++ pkg_matches
+ where
+ rough_tcs = roughMatchTcs tys
+ all_tvs = all isNothing rough_tcs
+ home_matches = lookup home_ie
+ pkg_matches = lookup pkg_ie
+
+ --------------
+ lookup env = case lookupUFM env fam of
+ Nothing -> [] -- No instances for this class
+ Just (FamIE insts has_tv_insts)
+ -- Short cut for common case:
+ -- The thing we are looking up is of form (C a
+ -- b c), and the FamIE has no instances of
+ -- that form, so don't bother to search
+ | all_tvs && not has_tv_insts -> []
+ | otherwise -> find insts
+
+ --------------
+ find [] = []
+ find (item@(FamInst { fi_tcs = mb_tcs, fi_tvs = tpl_tvs,
+ fi_tys = tpl_tys, fi_tycon = tycon }) : rest)
+ -- Fast check for no match, uses the "rough match" fields
+ | instanceCantMatch rough_tcs mb_tcs
+ = find rest
+
+ | otherwise
+ = ASSERT2( tyVarsOfTypes tys `disjointVarSet` tpl_tvs,
+ (ppr fam <+> ppr tys <+> ppr all_tvs) $$
+ (ppr tycon <+> ppr tpl_tvs <+> ppr tpl_tys)
+ )
+ -- Unification will break badly if the variables overlap
+ -- They shouldn't because we allocate separate uniques for them
+ case tcUnifyTys bind_fn tpl_tys tys of
+ Just subst -> let rep_tys = substTyVars subst (tyConTyVars tycon)
+ in
+ (item, rep_tys) : find rest
+ Nothing -> find rest
+
+-- See explanation at @InstEnv.bind_fn@.
+--
+bind_fn tv | isTcTyVar tv && isExistentialTyVar tv = Skolem
+ | otherwise = BindMe
+\end{code}
+
+--------------------------------------
+-- Normalisation
+
+\begin{code}
+ -- get rid of TOPLEVEL type functions by rewriting them
+ -- i.e. treating their equations as a TRS
+toplevelNormaliseFamInst :: FamInstEnvs ->
+ Type ->
+ (CoercionI,Type)
+toplevelNormaliseFamInst env ty
+ | Just ty' <- tcView ty = normaliseFamInst env ty'
+toplevelNormaliseFamInst env ty@(TyConApp tyCon tys)
+ | isOpenTyCon tyCon
+ = normaliseFamInst env ty
+toplevelNormaliseFamInst env ty
+ = (IdCo,ty)
+
+
+ -- get rid of ALL type functions by rewriting them
+ -- i.e. treating their equations as a TRS
+normaliseFamInst :: FamInstEnvs -> -- environment with family instances
+ Type -> -- old type
+ (CoercionI,Type) -- (coercion,new type)
+normaliseFamInst env ty
+ | Just ty' <- tcView ty = normaliseFamInst env ty'
+normaliseFamInst env ty@(TyConApp tyCon tys) =
+ let (cois,ntys) = mapAndUnzip (normaliseFamInst env) tys
+ tycon_coi = mkTyConAppCoI tyCon ntys cois
+ maybe_ty_co = lookupFamInst env tyCon ntys
+ in case maybe_ty_co of
+ -- a matching family instance exists
+ Just (ty',co) ->
+ let first_coi = mkTransCoI tycon_coi (ACo co)
+ (rest_coi,nty) = normaliseFamInst env ty'
+ fix_coi = mkTransCoI first_coi rest_coi
+ in (fix_coi,nty)
+ -- no matching family instance exists
+ -- we do not do anything
+ Nothing ->
+ (tycon_coi,TyConApp tyCon ntys)
+normaliseFamInst env ty@(AppTy ty1 ty2) =
+ let (coi1,nty1) = normaliseFamInst env ty1
+ (coi2,nty2) = normaliseFamInst env ty2
+ in (mkAppTyCoI nty1 coi1 nty2 coi2, AppTy nty1 nty2)
+normaliseFamInst env ty@(FunTy ty1 ty2) =
+ let (coi1,nty1) = normaliseFamInst env ty1
+ (coi2,nty2) = normaliseFamInst env ty2
+ in (mkFunTyCoI nty1 coi1 nty2 coi2, FunTy nty1 nty2)
+normaliseFamInst env ty@(ForAllTy tyvar ty1) =
+ let (coi,nty1) = normaliseFamInst env ty1
+ in (mkForAllTyCoI tyvar coi,ForAllTy tyvar nty1)
+normaliseFamInst env ty@(NoteTy note ty1) =
+ let (coi,nty1) = normaliseFamInst env ty1
+ in (mkNoteTyCoI note coi,NoteTy note nty1)
+normaliseFamInst env ty@(TyVarTy _) =
+ (IdCo,ty)
+normaliseFamInst env (PredTy predty) =
+ normaliseFamInstPred env predty
+
+normaliseFamInstPred :: FamInstEnvs -> PredType -> (CoercionI,Type)
+normaliseFamInstPred env (ClassP cls tys) =
+ let (cois,tys') = mapAndUnzip (normaliseFamInst env) tys
+ in (mkClassPPredCoI cls tys' cois, PredTy $ ClassP cls tys')
+normaliseFamInstPred env (IParam ipn ty) =
+ let (coi,ty') = normaliseFamInst env ty
+ in (mkIParamPredCoI ipn coi, PredTy $ IParam ipn ty')
+normaliseFamInstPred env (EqPred ty1 ty2) =
+ let (coi1,ty1') = normaliseFamInst env ty1
+ (coi2,ty2') = normaliseFamInst env ty2
+ in (mkEqPredCoI ty1' coi1 ty2' coi2, PredTy $ EqPred ty1' ty2')
+
+lookupFamInst :: FamInstEnvs -> TyCon -> [Type] -> Maybe (Type,Coercion)
+
+-- (lookupFamInst F tys) looks for a top-level instance
+-- co : forall a. F tys' = G a
+-- (The rhs is always of form G a; see Note [The FamInst structure]
+-- in FamInst.)
+-- where we can instantiate 'a' with t to make tys'[t/a] = tys
+-- Hence (co t) : F tys ~ G t
+-- Then we return (Just (G t, co t))
+
+lookupFamInst env tycon tys
+ | not (isOpenTyCon tycon) -- Dead code; fix.
+ = Nothing
+ | otherwise
+ = case lookupFamInstEnv env tycon tys of
+ [(subst, fam_inst)] ->
+ Just (mkTyConApp rep_tc substituted_vars, mkTyConApp coercion_tycon substituted_vars)
+ where -- NB: invariant of lookupFamInstEnv is that (tyConTyVars rep_tc)
+ -- is in the domain of the substitution
+ rep_tc = famInstTyCon fam_inst
+ coercion_tycon = expectJust "lookupFamInst" (tyConFamilyCoercion_maybe rep_tc)
+ substituted_vars = substTyVars subst (tyConTyVars rep_tc)
+ other -> Nothing
+\end{code}
projects / ghc-hetmet.git / blobdiff