X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2Ftypecheck%2FTcGenDeriv.lhs;h=3fb18485670d879486a38cb1de236ebf0241e1e1;hp=a7956e4fcc7fb4e4cc9aeeb88bf9381ef9a4c990;hb=836b1e90821aacc9d1e09fe78085f911597274c8;hpb=8c2fd74094dc533bf3256158325e3f091e57e5d2 diff --git a/compiler/typecheck/TcGenDeriv.lhs b/compiler/typecheck/TcGenDeriv.lhs index a7956e4..3fb1848 100644 --- a/compiler/typecheck/TcGenDeriv.lhs +++ b/compiler/typecheck/TcGenDeriv.lhs @@ -12,7 +12,7 @@ This is where we do all the grimy bindings' generation. \begin{code} module TcGenDeriv ( - DerivAuxBind(..), DerivAuxBinds, isDupAux, + DerivAuxBinds, isDupAux, gen_Bounded_binds, gen_Enum_binds, @@ -23,6 +23,11 @@ module TcGenDeriv ( gen_Show_binds, gen_Data_binds, gen_Typeable_binds, + gen_Functor_binds, + FFoldType(..), functorLikeTraverse, + deepSubtypesContaining, foldDataConArgs, + gen_Foldable_binds, + gen_Traversable_binds, genAuxBind ) where @@ -37,19 +42,22 @@ import Name import HscTypes import PrelInfo import PrelNames -import MkId import PrimOp import SrcLoc import TyCon import TcType import TysPrim import TysWiredIn +import Type +import Var( TyVar ) +import TypeRep +import VarSet +import State import Util +import MonadUtils import Outputable import FastString -import OccName import Bag - import Data.List ( partition, intersperse ) \end{code} @@ -57,15 +65,21 @@ import Data.List ( partition, intersperse ) type DerivAuxBinds = [DerivAuxBind] data DerivAuxBind -- Please add these auxiliary top-level bindings - = DerivAuxBind (LHsBind RdrName) - | GenCon2Tag TyCon -- The con2Tag for given TyCon + = GenCon2Tag TyCon -- The con2Tag for given TyCon | GenTag2Con TyCon -- ...ditto tag2Con | GenMaxTag TyCon -- ...and maxTag + -- Scrap your boilerplate + | MkDataCon DataCon -- For constructor C we get $cC :: Constr + | MkTyCon TyCon -- For tycon T we get $tT :: DataType + + isDupAux :: DerivAuxBind -> DerivAuxBind -> Bool isDupAux (GenCon2Tag tc1) (GenCon2Tag tc2) = tc1 == tc2 isDupAux (GenTag2Con tc1) (GenTag2Con tc2) = tc1 == tc2 isDupAux (GenMaxTag tc1) (GenMaxTag tc2) = tc1 == tc2 +isDupAux (MkDataCon dc1) (MkDataCon dc2) = dc1 == dc2 +isDupAux (MkTyCon tc1) (MkTyCon tc2) = tc1 == tc2 isDupAux _ _ = False \end{code} @@ -297,75 +311,80 @@ gen_Ord_binds loc tycon | Just (con, prim_tc) <- primWrapperType_maybe tycon = gen_PrimOrd_binds con prim_tc - | otherwise + | otherwise = (unitBag compare, aux_binds) - -- `AndMonoBinds` compare - -- The default declaration in PrelBase handles this + -- `AndMonoBinds` compare + -- The default declaration in PrelBase handles this where aux_binds | single_con_type = [] - | otherwise = [GenCon2Tag tycon] + | otherwise = [GenCon2Tag tycon] compare = L loc (mkFunBind (L loc compare_RDR) compare_matches) compare_matches = [mkMatch [a_Pat, b_Pat] compare_rhs cmp_eq_binds] cmp_eq_binds = HsValBinds (ValBindsIn (unitBag cmp_eq) []) compare_rhs - | single_con_type = cmp_eq_Expr a_Expr b_Expr - | otherwise - = untag_Expr tycon [(a_RDR, ah_RDR), (b_RDR, bh_RDR)] - (cmp_tags_Expr eqInt_RDR ah_RDR bh_RDR - (cmp_eq_Expr a_Expr b_Expr) -- True case - -- False case; they aren't equal - -- So we need to do a less-than comparison on the tags - (cmp_tags_Expr ltInt_RDR ah_RDR bh_RDR ltTag_Expr gtTag_Expr)) + | single_con_type = cmp_eq_Expr a_Expr b_Expr + | otherwise + = untag_Expr tycon [(a_RDR, ah_RDR), (b_RDR, bh_RDR)] + (cmp_tags_Expr eqInt_RDR ah_RDR bh_RDR + (cmp_eq_Expr a_Expr b_Expr) -- True case + -- False case; they aren't equal + -- So we need to do a less-than comparison on the tags + (cmp_tags_Expr ltInt_RDR ah_RDR bh_RDR + ltTag_Expr gtTag_Expr)) tycon_data_cons = tyConDataCons tycon single_con_type = isSingleton tycon_data_cons (nullary_cons, nonnullary_cons) | isNewTyCon tycon = ([], tyConDataCons tycon) - | otherwise = partition isNullarySrcDataCon tycon_data_cons + | otherwise = partition isNullarySrcDataCon tycon_data_cons cmp_eq = mk_FunBind loc cmp_eq_RDR cmp_eq_match cmp_eq_match | isEnumerationTyCon tycon - -- We know the tags are equal, so if it's an enumeration TyCon, - -- then there is nothing left to do - -- Catch this specially to avoid warnings - -- about overlapping patterns from the desugarer, - -- and to avoid unnecessary pattern-matching + -- We know the tags are equal, so if it's an + -- enumeration TyCon, + -- then there is nothing left to do + -- Catch this specially to avoid warnings + -- about overlapping patterns from the desugarer, + -- and to avoid unnecessary pattern-matching = [([nlWildPat,nlWildPat], eqTag_Expr)] | otherwise = map pats_etc nonnullary_cons ++ - (if single_con_type then -- Omit wildcards when there's just one - [] -- constructor, to silence desugarer - else + (if single_con_type then -- Omit wildcards when there's just one + [] -- constructor, to silence desugarer + else [([nlWildPat, nlWildPat], default_rhs)]) - default_rhs | null nullary_cons = impossible_Expr -- Keep desugarer from complaining about - -- inexhaustive patterns - | otherwise = eqTag_Expr -- Some nullary constructors; - -- Tags are equal, no args => return EQ + default_rhs | null nullary_cons = -- Keep desugarer from complaining about + -- inexhaustive patterns + impossible_Expr + | otherwise = -- Some nullary constructors; + -- Tags are equal, no args => return EQ + eqTag_Expr pats_etc data_con - = ([con1_pat, con2_pat], - nested_compare_expr tys_needed as_needed bs_needed) - where - con1_pat = nlConVarPat data_con_RDR as_needed - con2_pat = nlConVarPat data_con_RDR bs_needed - - data_con_RDR = getRdrName data_con - con_arity = length tys_needed - as_needed = take con_arity as_RDRs - bs_needed = take con_arity bs_RDRs - tys_needed = dataConOrigArgTys data_con - - nested_compare_expr [ty] [a] [b] - = careful_compare_Case tycon ty eqTag_Expr (nlHsVar a) (nlHsVar b) - - nested_compare_expr (ty:tys) (a:as) (b:bs) - = let eq_expr = nested_compare_expr tys as bs - in careful_compare_Case tycon ty eq_expr (nlHsVar a) (nlHsVar b) - - nested_compare_expr _ _ _ = panic "nested_compare_expr" -- Args always equal length + = ([con1_pat, con2_pat], + nested_compare_expr tys_needed as_needed bs_needed) + where + con1_pat = nlConVarPat data_con_RDR as_needed + con2_pat = nlConVarPat data_con_RDR bs_needed + + data_con_RDR = getRdrName data_con + con_arity = length tys_needed + as_needed = take con_arity as_RDRs + bs_needed = take con_arity bs_RDRs + tys_needed = dataConOrigArgTys data_con + + nested_compare_expr [ty] [a] [b] + = careful_compare_Case tycon ty eqTag_Expr (nlHsVar a) (nlHsVar b) + + nested_compare_expr (ty:tys) (a:as) (b:bs) + = let eq_expr = nested_compare_expr tys as bs + in careful_compare_Case tycon ty eq_expr (nlHsVar a) (nlHsVar b) + + -- Args always equal length + nested_compare_expr _ _ _ = panic "nested_compare_expr" \end{code} Note [Comparision of primitive types] @@ -552,8 +571,8 @@ gen_Bounded_binds loc tycon data_cons = tyConDataCons tycon ----- enum-flavored: --------------------------- - min_bound_enum = mkVarBind loc minBound_RDR (nlHsVar data_con_1_RDR) - max_bound_enum = mkVarBind loc maxBound_RDR (nlHsVar data_con_N_RDR) + min_bound_enum = mkHsVarBind loc minBound_RDR (nlHsVar data_con_1_RDR) + max_bound_enum = mkHsVarBind loc maxBound_RDR (nlHsVar data_con_N_RDR) data_con_1 = head data_cons data_con_N = last data_cons @@ -563,9 +582,9 @@ gen_Bounded_binds loc tycon ----- single-constructor-flavored: ------------- arity = dataConSourceArity data_con_1 - min_bound_1con = mkVarBind loc minBound_RDR $ + min_bound_1con = mkHsVarBind loc minBound_RDR $ nlHsVarApps data_con_1_RDR (nOfThem arity minBound_RDR) - max_bound_1con = mkVarBind loc maxBound_RDR $ + max_bound_1con = mkHsVarBind loc maxBound_RDR $ nlHsVarApps data_con_1_RDR (nOfThem arity maxBound_RDR) \end{code} @@ -682,9 +701,7 @@ gen_Ix_binds loc tycon data_con = case tyConSingleDataCon_maybe tycon of -- just checking... Nothing -> panic "get_Ix_binds" - Just dc | any isUnLiftedType (dataConOrigArgTys dc) - -> pprPanic "Can't derive Ix for a single-constructor type with primitive argument types:" (ppr tycon) - | otherwise -> dc + Just dc -> dc con_arity = dataConSourceArity data_con data_con_RDR = getRdrName data_con @@ -706,7 +723,7 @@ gen_Ix_binds loc tycon mk_qual a b c = noLoc $ mkBindStmt (nlVarPat c) (nlHsApp (nlHsVar range_RDR) - (nlTuple [nlHsVar a, nlHsVar b] Boxed)) + (mkLHsVarTuple [a,b])) ---------------- single_con_index @@ -728,11 +745,11 @@ gen_Ix_binds loc tycon ) plus_RDR ( genOpApp ( (nlHsApp (nlHsVar unsafeRangeSize_RDR) - (nlTuple [nlHsVar l, nlHsVar u] Boxed)) + (mkLHsVarTuple [l,u])) ) times_RDR (mk_index rest) ) mk_one l u i - = nlHsApps unsafeIndex_RDR [nlTuple [nlHsVar l, nlHsVar u] Boxed, nlHsVar i] + = nlHsApps unsafeIndex_RDR [mkLHsVarTuple [l,u], nlHsVar i] ------------------ single_con_inRange @@ -741,8 +758,7 @@ gen_Ix_binds loc tycon con_pat cs_needed] $ foldl1 and_Expr (zipWith3Equal "single_con_inRange" in_range as_needed bs_needed cs_needed) where - in_range a b c = nlHsApps inRange_RDR [nlTuple [nlHsVar a, nlHsVar b] Boxed, - nlHsVar c] + in_range a b c = nlHsApps inRange_RDR [mkLHsVarTuple [a,b], nlHsVar c] \end{code} %************************************************************************ @@ -797,16 +813,16 @@ gen_Read_binds get_fixity loc tycon where ----------------------------------------------------------------------- default_readlist - = mkVarBind loc readList_RDR (nlHsVar readListDefault_RDR) + = mkHsVarBind loc readList_RDR (nlHsVar readListDefault_RDR) default_readlistprec - = mkVarBind loc readListPrec_RDR (nlHsVar readListPrecDefault_RDR) + = mkHsVarBind loc readListPrec_RDR (nlHsVar readListPrecDefault_RDR) ----------------------------------------------------------------------- data_cons = tyConDataCons tycon (nullary_cons, non_nullary_cons) = partition isNullarySrcDataCon data_cons - read_prec = mkVarBind loc readPrec_RDR + read_prec = mkHsVarBind loc readPrec_RDR (nlHsApp (nlHsVar parens_RDR) read_cons) read_cons = foldr1 mk_alt (read_nullary_cons ++ read_non_nullary_cons) @@ -820,9 +836,8 @@ gen_Read_binds get_fixity loc tycon _ -> [nlHsApp (nlHsVar choose_RDR) (nlList (map mk_pair nullary_cons))] - mk_pair con = nlTuple [nlHsLit (mkHsString (data_con_str con)), - result_expr con []] - Boxed + mk_pair con = mkLHsTupleExpr [nlHsLit (mkHsString (data_con_str con)), + result_expr con []] read_non_nullary_con data_con | is_infix = mk_parser infix_prec infix_stmts body @@ -837,22 +852,26 @@ gen_Read_binds get_fixity loc tycon con_str = data_con_str data_con prefix_parser = mk_parser prefix_prec prefix_stmts body - prefix_stmts -- T a b c - = (if not (isSym con_str) then - [bindLex (ident_pat con_str)] - else [read_punc "(", bindLex (symbol_pat con_str), read_punc ")"]) - ++ read_args + + read_prefix_con + | isSym con_str = [read_punc "(", bindLex (symbol_pat con_str), read_punc ")"] + | otherwise = [bindLex (ident_pat con_str)] + read_infix_con + | isSym con_str = [bindLex (symbol_pat con_str)] + | otherwise = [read_punc "`", bindLex (ident_pat con_str), read_punc "`"] + + prefix_stmts -- T a b c + = read_prefix_con ++ read_args + infix_stmts -- a %% b, or a `T` b = [read_a1] - ++ (if isSym con_str - then [bindLex (symbol_pat con_str)] - else [read_punc "`", bindLex (ident_pat con_str), read_punc "`"]) + ++ read_infix_con ++ [read_a2] record_stmts -- T { f1 = a, f2 = b } - = [bindLex (ident_pat (wrapOpParens con_str)), - read_punc "{"] + = read_prefix_con + ++ [read_punc "{"] ++ concat (intersperse [read_punc ","] field_stmts) ++ [read_punc "}"] @@ -888,9 +907,8 @@ gen_Read_binds get_fixity loc tycon data_con_str con = occNameString (getOccName con) read_punc c = bindLex (punc_pat c) - read_arg a ty - | isUnLiftedType ty = pprPanic "Error in deriving:" (text "Can't read unlifted types yet:" <+> ppr ty) - | otherwise = noLoc (mkBindStmt (nlVarPat a) (nlHsVarApps step_RDR [readPrec_RDR])) + read_arg a ty = ASSERT( not (isUnLiftedType ty) ) + noLoc (mkBindStmt (nlVarPat a) (nlHsVarApps step_RDR [readPrec_RDR])) read_field lbl a = read_lbl lbl ++ [read_punc "=", @@ -948,7 +966,7 @@ gen_Show_binds get_fixity loc tycon = (listToBag [shows_prec, show_list], []) where ----------------------------------------------------------------------- - show_list = mkVarBind loc showList_RDR + show_list = mkHsVarBind loc showList_RDR (nlHsApp (nlHsVar showList___RDR) (nlHsPar (nlHsApp (nlHsVar showsPrec_RDR) (nlHsIntLit 0)))) ----------------------------------------------------------------------- shows_prec = mk_FunBind loc showsPrec_RDR (map pats_etc (tyConDataCons tycon)) @@ -1080,7 +1098,7 @@ gen_Typeable_binds loc tycon [nlWildPat] (nlHsApps mkTypeRep_RDR [tycon_rep, nlList []]) where - tycon_rep = nlHsVar mkTyConRep_RDR `nlHsApp` nlHsLit (mkHsString (showSDoc (ppr tycon))) + tycon_rep = nlHsVar mkTyConRep_RDR `nlHsApp` nlHsLit (mkHsString (showSDocOneLine (ppr tycon))) mk_typeOf_RDR :: TyCon -> RdrName -- Use the arity of the TyCon to make the right typeOfn function @@ -1124,17 +1142,21 @@ we generate dataTypeOf _ = $dT + dataCast1 = gcast1 -- If T :: * -> * + dataCast2 = gcast2 -- if T :: * -> * -> * + + \begin{code} gen_Data_binds :: SrcSpan -> TyCon -> (LHsBinds RdrName, -- The method bindings DerivAuxBinds) -- Auxiliary bindings gen_Data_binds loc tycon - = (listToBag [gfoldl_bind, gunfold_bind, toCon_bind, dataTypeOf_bind], + = (listToBag [gfoldl_bind, gunfold_bind, toCon_bind, dataTypeOf_bind] + `unionBags` gcast_binds, -- Auxiliary definitions: the data type and constructors - DerivAuxBind datatype_bind : map mk_con_bind data_cons) + MkTyCon tycon : map MkDataCon data_cons) where - tycon_name = tyConName tycon data_cons = tyConDataCons tycon n_cons = length data_cons one_constr = n_cons == 1 @@ -1181,47 +1203,33 @@ gen_Data_binds loc tycon loc dataTypeOf_RDR [nlWildPat] - (nlHsVar data_type_name) - - ------------ $dT - data_type_name = mkAuxBinderName tycon_name mkDataTOcc - datatype_bind = mkVarBind - loc - data_type_name - ( nlHsVar mkDataType_RDR - `nlHsApp` nlHsLit (mkHsString (showSDoc (ppr tycon))) - `nlHsApp` nlList constrs - ) - constrs = [nlHsVar (mk_constr_name con) | con <- data_cons] - - - ------------ $cT1 etc - mk_constr_name con = mkAuxBinderName (dataConName con) mkDataCOcc - mk_con_bind dc = DerivAuxBind $ - mkVarBind - loc - (mk_constr_name dc) - (nlHsApps mkConstr_RDR (constr_args dc)) - constr_args dc = - [ -- nlHsIntLit (toInteger (dataConTag dc)), -- Tag - nlHsVar data_type_name, -- DataType - nlHsLit (mkHsString (occNameString dc_occ)), -- String name - nlList labels, -- Field labels - nlHsVar fixity] -- Fixity - where - labels = map (nlHsLit . mkHsString . getOccString) - (dataConFieldLabels dc) - dc_occ = getOccName dc - is_infix = isDataSymOcc dc_occ - fixity | is_infix = infix_RDR - | otherwise = prefix_RDR + (nlHsVar (mk_data_type_name tycon)) + + ------------ gcast1/2 + tycon_kind = tyConKind tycon + gcast_binds | tycon_kind `eqKind` kind1 = mk_gcast dataCast1_RDR gcast1_RDR + | tycon_kind `eqKind` kind2 = mk_gcast dataCast2_RDR gcast2_RDR + | otherwise = emptyBag + mk_gcast dataCast_RDR gcast_RDR + = unitBag (mk_easy_FunBind loc dataCast_RDR [nlVarPat f_RDR] + (nlHsVar gcast_RDR `nlHsApp` nlHsVar f_RDR)) + + +kind1, kind2 :: Kind +kind1 = liftedTypeKind `mkArrowKind` liftedTypeKind +kind2 = liftedTypeKind `mkArrowKind` kind1 gfoldl_RDR, gunfold_RDR, toConstr_RDR, dataTypeOf_RDR, mkConstr_RDR, - mkDataType_RDR, conIndex_RDR, prefix_RDR, infix_RDR :: RdrName + mkDataType_RDR, conIndex_RDR, prefix_RDR, infix_RDR, + dataCast1_RDR, dataCast2_RDR, gcast1_RDR, gcast2_RDR :: RdrName gfoldl_RDR = varQual_RDR gENERICS (fsLit "gfoldl") gunfold_RDR = varQual_RDR gENERICS (fsLit "gunfold") toConstr_RDR = varQual_RDR gENERICS (fsLit "toConstr") dataTypeOf_RDR = varQual_RDR gENERICS (fsLit "dataTypeOf") +dataCast1_RDR = varQual_RDR gENERICS (fsLit "dataCast1") +dataCast2_RDR = varQual_RDR gENERICS (fsLit "dataCast2") +gcast1_RDR = varQual_RDR tYPEABLE (fsLit "gcast1") +gcast2_RDR = varQual_RDR tYPEABLE (fsLit "gcast2") mkConstr_RDR = varQual_RDR gENERICS (fsLit "mkConstr") mkDataType_RDR = varQual_RDR gENERICS (fsLit "mkDataType") conIndex_RDR = varQual_RDR gENERICS (fsLit "constrIndex") @@ -1229,6 +1237,328 @@ prefix_RDR = dataQual_RDR gENERICS (fsLit "Prefix") infix_RDR = dataQual_RDR gENERICS (fsLit "Infix") \end{code} + + +%************************************************************************ +%* * + Functor instances + + see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html + +%* * +%************************************************************************ + +For the data type: + + data T a = T1 Int a | T2 (T a) + +We generate the instance: + + instance Functor T where + fmap f (T1 b1 a) = T1 b1 (f a) + fmap f (T2 ta) = T2 (fmap f ta) + +Notice that we don't simply apply 'fmap' to the constructor arguments. +Rather + - Do nothing to an argument whose type doesn't mention 'a' + - Apply 'f' to an argument of type 'a' + - Apply 'fmap f' to other arguments +That's why we have to recurse deeply into the constructor argument types, +rather than just one level, as we typically do. + +What about types with more than one type parameter? In general, we only +derive Functor for the last position: + + data S a b = S1 [b] | S2 (a, T a b) + instance Functor (S a) where + fmap f (S1 bs) = S1 (fmap f bs) + fmap f (S2 (p,q)) = S2 (a, fmap f q) + +However, we have special cases for + - tuples + - functions + +More formally, we write the derivation of fmap code over type variable +'a for type 'b as ($fmap 'a 'b). In this general notation the derived +instance for T is: + + instance Functor T where + fmap f (T1 x1 x2) = T1 ($(fmap 'a 'b1) x1) ($(fmap 'a 'a) x2) + fmap f (T2 x1) = T2 ($(fmap 'a '(T a)) x1) + + $(fmap 'a 'b) x = x -- when b does not contain a + $(fmap 'a 'a) x = f x + $(fmap 'a '(b1,b2)) x = case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2) + $(fmap 'a '(T b1 b2)) x = fmap $(fmap 'a 'b2) x -- when a only occurs in the last parameter, b2 + $(fmap 'a '(b -> c)) x = \b -> $(fmap 'a' 'c) (x ($(cofmap 'a 'b) b)) + +For functions, the type parameter 'a can occur in a contravariant position, +which means we need to derive a function like: + + cofmap :: (a -> b) -> (f b -> f a) + +This is pretty much the same as $fmap, only without the $(cofmap 'a 'a) case: + + $(cofmap 'a 'b) x = x -- when b does not contain a + $(cofmap 'a 'a) x = error "type variable in contravariant position" + $(cofmap 'a '(b1,b2)) x = case x of (x1,x2) -> ($(cofmap 'a 'b1) x1, $(cofmap 'a 'b2) x2) + $(cofmap 'a '[b]) x = map $(cofmap 'a 'b) x + $(cofmap 'a '(T b1 b2)) x = fmap $(cofmap 'a 'b2) x -- when a only occurs in the last parameter, b2 + $(cofmap 'a '(b -> c)) x = \b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b)) + +\begin{code} +gen_Functor_binds :: SrcSpan -> TyCon -> (LHsBinds RdrName, DerivAuxBinds) +gen_Functor_binds loc tycon + = (unitBag fmap_bind, []) + where + data_cons = tyConDataCons tycon + + fmap_bind = L loc $ mkFunBind (L loc fmap_RDR) (map fmap_eqn data_cons) + fmap_eqn con = evalState (match_for_con [f_Pat] con parts) bs_RDRs + where + parts = foldDataConArgs ft_fmap con + + ft_fmap :: FFoldType (LHsExpr RdrName -> State [RdrName] (LHsExpr RdrName)) + -- Tricky higher order type; I can't say I fully understand this code :-( + ft_fmap = FT { ft_triv = \x -> return x -- fmap f x = x + , ft_var = \x -> return (nlHsApp f_Expr x) -- fmap f x = f x + , ft_fun = \g h x -> mkSimpleLam (\b -> h =<< (nlHsApp x `fmap` g b)) + -- fmap f x = \b -> h (x (g b)) + , ft_tup = mkSimpleTupleCase match_for_con -- fmap f x = case x of (a1,a2,..) -> (g1 a1,g2 a2,..) + , ft_ty_app = \_ g x -> do gg <- mkSimpleLam g -- fmap f x = fmap g x + return $ nlHsApps fmap_RDR [gg,x] + , ft_forall = \_ g x -> g x + , ft_bad_app = panic "in other argument" + , ft_co_var = panic "contravariant" } + + match_for_con = mkSimpleConMatch $ + \con_name xsM -> do xs <- sequence xsM + return (nlHsApps con_name xs) -- Con (g1 v1) (g2 v2) .. +\end{code} + +Utility functions related to Functor deriving. + +Since several things use the same pattern of traversal, this is abstracted into functorLikeTraverse. +This function works like a fold: it makes a value of type 'a' in a bottom up way. + +\begin{code} +-- Generic traversal for Functor deriving +data FFoldType a -- Describes how to fold over a Type in a functor like way + = FT { ft_triv :: a -- Does not contain variable + , ft_var :: a -- The variable itself + , ft_co_var :: a -- The variable itself, contravariantly + , ft_fun :: a -> a -> a -- Function type + , ft_tup :: Boxity -> [a] -> a -- Tuple type + , ft_ty_app :: Type -> a -> a -- Type app, variable only in last argument + , ft_bad_app :: a -- Type app, variable other than in last argument + , ft_forall :: TcTyVar -> a -> a -- Forall type + } + +functorLikeTraverse :: TyVar -- ^ Variable to look for + -> FFoldType a -- ^ How to fold + -> Type -- ^ Type to process + -> a +functorLikeTraverse var (FT { ft_triv = caseTrivial, ft_var = caseVar + , ft_co_var = caseCoVar, ft_fun = caseFun + , ft_tup = caseTuple, ft_ty_app = caseTyApp + , ft_bad_app = caseWrongArg, ft_forall = caseForAll }) + ty + = fst (go False ty) + where -- go returns (result of type a, does type contain var) + go co ty | Just ty' <- coreView ty = go co ty' + go co (TyVarTy v) | v == var = (if co then caseCoVar else caseVar,True) + go co (FunTy (PredTy _) b) = go co b + go co (FunTy x y) | xc || yc = (caseFun xr yr,True) + where (xr,xc) = go (not co) x + (yr,yc) = go co y + go co (AppTy x y) | xc = (caseWrongArg, True) + | yc = (caseTyApp x yr, True) + where (_, xc) = go co x + (yr,yc) = go co y + go co ty@(TyConApp con args) + | isTupleTyCon con = (caseTuple (tupleTyConBoxity con) xrs,True) + | null args = (caseTrivial,False) -- T + | or (init xcs) = (caseWrongArg,True) -- T (..var..) ty + | last xcs = -- T (..no var..) ty + (caseTyApp (fst (splitAppTy ty)) (last xrs),True) + where (xrs,xcs) = unzip (map (go co) args) + go co (ForAllTy v x) | v /= var && xc = (caseForAll v xr,True) + where (xr,xc) = go co x + go _ _ = (caseTrivial,False) + +-- Return all syntactic subterms of ty that contain var somewhere +-- These are the things that should appear in instance constraints +deepSubtypesContaining :: TyVar -> Type -> [TcType] +deepSubtypesContaining tv + = functorLikeTraverse tv + (FT { ft_triv = [] + , ft_var = [] + , ft_fun = (++), ft_tup = \_ xs -> concat xs + , ft_ty_app = (:) + , ft_bad_app = panic "in other argument" + , ft_co_var = panic "contravariant" + , ft_forall = \v xs -> filterOut ((v `elemVarSet`) . tyVarsOfType) xs }) + + +foldDataConArgs :: FFoldType a -> DataCon -> [a] +-- Fold over the arguments of the datacon +foldDataConArgs ft con + = map (functorLikeTraverse tv ft) (dataConOrigArgTys con) + where + tv = last (dataConUnivTyVars con) + -- Argument to derive for, 'a in the above description + -- The validity checks have ensured that con is + -- a vanilla data constructor + +-- Make a HsLam using a fresh variable from a State monad +mkSimpleLam :: (LHsExpr id -> State [id] (LHsExpr id)) -> State [id] (LHsExpr id) +-- (mkSimpleLam fn) returns (\x. fn(x)) +mkSimpleLam lam = do + (n:names) <- get + put names + body <- lam (nlHsVar n) + return (mkHsLam [nlVarPat n] body) + +mkSimpleLam2 :: (LHsExpr id -> LHsExpr id -> State [id] (LHsExpr id)) -> State [id] (LHsExpr id) +mkSimpleLam2 lam = do + (n1:n2:names) <- get + put names + body <- lam (nlHsVar n1) (nlHsVar n2) + return (mkHsLam [nlVarPat n1,nlVarPat n2] body) + +-- "Con a1 a2 a3 -> fold [x1 a1, x2 a2, x3 a3]" +mkSimpleConMatch :: Monad m => (RdrName -> [a] -> m (LHsExpr RdrName)) -> [LPat RdrName] -> DataCon -> [LHsExpr RdrName -> a] -> m (LMatch RdrName) +mkSimpleConMatch fold extra_pats con insides = do + let con_name = getRdrName con + let vars_needed = takeList insides as_RDRs + let pat = nlConVarPat con_name vars_needed + rhs <- fold con_name (zipWith ($) insides (map nlHsVar vars_needed)) + return $ mkMatch (extra_pats ++ [pat]) rhs emptyLocalBinds + +-- "case x of (a1,a2,a3) -> fold [x1 a1, x2 a2, x3 a3]" +mkSimpleTupleCase :: Monad m => ([LPat RdrName] -> DataCon -> [LHsExpr RdrName -> a] -> m (LMatch RdrName)) + -> Boxity -> [LHsExpr RdrName -> a] -> LHsExpr RdrName -> m (LHsExpr RdrName) +mkSimpleTupleCase match_for_con boxity insides x = do + let con = tupleCon boxity (length insides) + match <- match_for_con [] con insides + return $ nlHsCase x [match] +\end{code} + + +%************************************************************************ +%* * + Foldable instances + + see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html + +%* * +%************************************************************************ + +Deriving Foldable instances works the same way as Functor instances, +only Foldable instances are not possible for function types at all. +Here the derived instance for the type T above is: + + instance Foldable T where + foldr f z (T1 x1 x2 x3) = $(foldr 'a 'b1) x1 ( $(foldr 'a 'a) x2 ( $(foldr 'a 'b2) x3 z ) ) + +The cases are: + + $(foldr 'a 'b) x z = z -- when b does not contain a + $(foldr 'a 'a) x z = f x z + $(foldr 'a '(b1,b2)) x z = case x of (x1,x2) -> $(foldr 'a 'b1) x1 ( $(foldr 'a 'b2) x2 z ) + $(foldr 'a '(T b1 b2)) x z = foldr $(foldr 'a 'b2) x z -- when a only occurs in the last parameter, b2 + +Note that the arguments to the real foldr function are the wrong way around, +since (f :: a -> b -> b), while (foldr f :: b -> t a -> b). + +\begin{code} +gen_Foldable_binds :: SrcSpan -> TyCon -> (LHsBinds RdrName, DerivAuxBinds) +gen_Foldable_binds loc tycon + = (unitBag foldr_bind, []) + where + data_cons = tyConDataCons tycon + + foldr_bind = L loc $ mkFunBind (L loc foldable_foldr_RDR) (map foldr_eqn data_cons) + foldr_eqn con = evalState (match_for_con z_Expr [f_Pat,z_Pat] con parts) bs_RDRs + where + parts = foldDataConArgs ft_foldr con + + ft_foldr :: FFoldType (LHsExpr RdrName -> LHsExpr RdrName -> State [RdrName] (LHsExpr RdrName)) + ft_foldr = FT { ft_triv = \_ z -> return z -- foldr f z x = z + , ft_var = \x z -> return (nlHsApps f_RDR [x,z]) -- foldr f z x = f x z + , ft_tup = \b gs x z -> mkSimpleTupleCase (match_for_con z) b gs x + , ft_ty_app = \_ g x z -> do gg <- mkSimpleLam2 g -- foldr f z x = foldr (\xx zz -> g xx zz) z x + return $ nlHsApps foldable_foldr_RDR [gg,z,x] + , ft_forall = \_ g x z -> g x z + , ft_co_var = panic "covariant" + , ft_fun = panic "function" + , ft_bad_app = panic "in other argument" } + + match_for_con z = mkSimpleConMatch (\_con_name -> foldrM ($) z) -- g1 v1 (g2 v2 (.. z)) +\end{code} + + +%************************************************************************ +%* * + Traversable instances + + see http://www.mail-archive.com/haskell-prime@haskell.org/msg02116.html +%* * +%************************************************************************ + +Again, Traversable is much like Functor and Foldable. + +The cases are: + + $(traverse 'a 'b) x = pure x -- when b does not contain a + $(traverse 'a 'a) x = f x + $(traverse 'a '(b1,b2)) x = case x of (x1,x2) -> (,) <$> $(traverse 'a 'b1) x1 <*> $(traverse 'a 'b2) x2 + $(traverse 'a '(T b1 b2)) x = traverse $(traverse 'a 'b2) x -- when a only occurs in the last parameter, b2 + +Note that the generated code is not as efficient as it could be. For instance: + + data T a = T Int a deriving Traversable + +gives the function: traverse f (T x y) = T <$> pure x <*> f y +instead of: traverse f (T x y) = T x <$> f y + +\begin{code} +gen_Traversable_binds :: SrcSpan -> TyCon -> (LHsBinds RdrName, DerivAuxBinds) +gen_Traversable_binds loc tycon + = (unitBag traverse_bind, []) + where + data_cons = tyConDataCons tycon + + traverse_bind = L loc $ mkFunBind (L loc traverse_RDR) (map traverse_eqn data_cons) + traverse_eqn con = evalState (match_for_con [f_Pat] con parts) bs_RDRs + where + parts = foldDataConArgs ft_trav con + + + ft_trav :: FFoldType (LHsExpr RdrName -> State [RdrName] (LHsExpr RdrName)) + ft_trav = FT { ft_triv = \x -> return (nlHsApps pure_RDR [x]) -- traverse f x = pure x + , ft_var = \x -> return (nlHsApps f_RDR [x]) -- travese f x = f x + , ft_tup = mkSimpleTupleCase match_for_con -- travese f x z = case x of (a1,a2,..) -> + -- (,,) <$> g1 a1 <*> g2 a2 <*> .. + , ft_ty_app = \_ g x -> do gg <- mkSimpleLam g -- travese f x = travese (\xx -> g xx) x + return $ nlHsApps traverse_RDR [gg,x] + , ft_forall = \_ g x -> g x + , ft_co_var = panic "covariant" + , ft_fun = panic "function" + , ft_bad_app = panic "in other argument" } + + match_for_con = mkSimpleConMatch $ + \con_name xsM -> do xs <- sequence xsM + return (mkApCon (nlHsVar con_name) xs) + + -- ((Con <$> x1) <*> x2) <*> .. + mkApCon con [] = nlHsApps pure_RDR [con] + mkApCon con (x:xs) = foldl appAp (nlHsApps fmap_RDR [con,x]) xs + where appAp x y = nlHsApps ap_RDR [x,y] +\end{code} + + + %************************************************************************ %* * \subsection{Generating extra binds (@con2tag@ and @tag2con@)} @@ -1248,10 +1578,6 @@ fiddling around. \begin{code} genAuxBind :: SrcSpan -> DerivAuxBind -> LHsBind RdrName - -genAuxBind _loc (DerivAuxBind bind) - = bind - genAuxBind loc (GenCon2Tag tycon) | lots_of_constructors = mk_FunBind loc rdr_name [([], get_tag_rhs)] @@ -1272,7 +1598,8 @@ genAuxBind loc (GenCon2Tag tycon) get_tag_rhs = L loc $ ExprWithTySig (nlHsLam (mkSimpleHsAlt (nlVarPat a_RDR) (nlHsApp (nlHsVar getTag_RDR) a_Expr))) - (noLoc (mkExplicitHsForAllTy (map (noLoc.UserTyVar) tvs) (noLoc []) con2tag_ty)) + (noLoc (mkExplicitHsForAllTy (userHsTyVarBndrs (map noLoc tvs)) + (noLoc []) con2tag_ty)) con2tag_ty = nlHsTyConApp (getRdrName tycon) (map nlHsTyVar tvs) `nlHsFunTy` @@ -1295,12 +1622,44 @@ genAuxBind loc (GenTag2Con tycon) rdr_name = tag2con_RDR tycon genAuxBind loc (GenMaxTag tycon) - = mkVarBind loc rdr_name + = mkHsVarBind loc rdr_name (nlHsApp (nlHsVar intDataCon_RDR) (nlHsLit (HsIntPrim max_tag))) where rdr_name = maxtag_RDR tycon max_tag = case (tyConDataCons tycon) of data_cons -> toInteger ((length data_cons) - fIRST_TAG) + +genAuxBind loc (MkTyCon tycon) -- $dT + = mkHsVarBind loc (mk_data_type_name tycon) + ( nlHsVar mkDataType_RDR + `nlHsApp` nlHsLit (mkHsString (showSDocOneLine (ppr tycon))) + `nlHsApp` nlList constrs ) + where + constrs = [nlHsVar (mk_constr_name con) | con <- tyConDataCons tycon] + +genAuxBind loc (MkDataCon dc) -- $cT1 etc + = mkHsVarBind loc (mk_constr_name dc) + (nlHsApps mkConstr_RDR constr_args) + where + constr_args + = [ -- nlHsIntLit (toInteger (dataConTag dc)), -- Tag + nlHsVar (mk_data_type_name (dataConTyCon dc)), -- DataType + nlHsLit (mkHsString (occNameString dc_occ)), -- String name + nlList labels, -- Field labels + nlHsVar fixity] -- Fixity + + labels = map (nlHsLit . mkHsString . getOccString) + (dataConFieldLabels dc) + dc_occ = getOccName dc + is_infix = isDataSymOcc dc_occ + fixity | is_infix = infix_RDR + | otherwise = prefix_RDR + +mk_data_type_name :: TyCon -> RdrName -- "$tT" +mk_data_type_name tycon = mkAuxBinderName (tyConName tycon) mkDataTOcc + +mk_constr_name :: DataCon -> RdrName -- "$cC" +mk_constr_name con = mkAuxBinderName (dataConName con) mkDataCOcc \end{code} %************************************************************************ @@ -1498,12 +1857,13 @@ genOpApp e1 op e2 = nlHsPar (nlHsOpApp e1 op e2) \end{code} \begin{code} -a_RDR, b_RDR, c_RDR, d_RDR, k_RDR, z_RDR, ah_RDR, bh_RDR, ch_RDR, dh_RDR, +a_RDR, b_RDR, c_RDR, d_RDR, f_RDR, k_RDR, z_RDR, ah_RDR, bh_RDR, ch_RDR, dh_RDR, cmp_eq_RDR :: RdrName a_RDR = mkVarUnqual (fsLit "a") b_RDR = mkVarUnqual (fsLit "b") c_RDR = mkVarUnqual (fsLit "c") d_RDR = mkVarUnqual (fsLit "d") +f_RDR = mkVarUnqual (fsLit "f") k_RDR = mkVarUnqual (fsLit "k") z_RDR = mkVarUnqual (fsLit "z") ah_RDR = mkVarUnqual (fsLit "a#") @@ -1517,22 +1877,25 @@ as_RDRs = [ mkVarUnqual (mkFastString ("a"++show i)) | i <- [(1::Int) .. ] ] bs_RDRs = [ mkVarUnqual (mkFastString ("b"++show i)) | i <- [(1::Int) .. ] ] cs_RDRs = [ mkVarUnqual (mkFastString ("c"++show i)) | i <- [(1::Int) .. ] ] -a_Expr, b_Expr, c_Expr, ltTag_Expr, eqTag_Expr, gtTag_Expr, +a_Expr, b_Expr, c_Expr, f_Expr, z_Expr, ltTag_Expr, eqTag_Expr, gtTag_Expr, false_Expr, true_Expr :: LHsExpr RdrName a_Expr = nlHsVar a_RDR b_Expr = nlHsVar b_RDR c_Expr = nlHsVar c_RDR +f_Expr = nlHsVar f_RDR +z_Expr = nlHsVar z_RDR ltTag_Expr = nlHsVar ltTag_RDR eqTag_Expr = nlHsVar eqTag_RDR gtTag_Expr = nlHsVar gtTag_RDR false_Expr = nlHsVar false_RDR true_Expr = nlHsVar true_RDR -a_Pat, b_Pat, c_Pat, d_Pat, k_Pat, z_Pat :: LPat RdrName +a_Pat, b_Pat, c_Pat, d_Pat, f_Pat, k_Pat, z_Pat :: LPat RdrName a_Pat = nlVarPat a_RDR b_Pat = nlVarPat b_RDR c_Pat = nlVarPat c_RDR d_Pat = nlVarPat d_RDR +f_Pat = nlVarPat f_RDR k_Pat = nlVarPat k_RDR z_Pat = nlVarPat z_RDR