2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 \section[TcInstDecls]{Typechecking instance declarations}
7 module TcInstDcls ( tcInstDecls1, tcInstDecls2 ) where
9 #include "HsVersions.h"
12 import TcBinds ( tcSpecSigs )
13 import TcClassDcl ( tcMethodBind, mkMethodBind, badMethodErr,
14 tcClassDecl2, getGenericInstances )
16 import TcMType ( tcSkolSigType, checkValidTheta, checkValidInstHead, instTypeErr,
17 checkAmbiguity, SourceTyCtxt(..) )
18 import TcType ( mkClassPred, tyVarsOfType,
19 tcSplitSigmaTy, tcSplitDFunHead, mkTyVarTys,
20 SkolemInfo(InstSkol), tcSplitDFunTy, pprClassPred )
21 import Inst ( tcInstClassOp, newDicts, instToId, showLIE,
22 getOverlapFlag, tcExtendLocalInstEnv )
23 import InstEnv ( mkLocalInstance, instanceDFunId )
24 import TcDeriv ( tcDeriving )
25 import TcEnv ( tcExtendGlobalValEnv, tcExtendTyVarEnv,
26 InstInfo(..), InstBindings(..),
27 newDFunName, tcExtendIdEnv
29 import TcHsType ( kcHsSigType, tcHsKindedType )
30 import TcUnify ( checkSigTyVars )
31 import TcSimplify ( tcSimplifyCheck, tcSimplifySuperClasses )
32 import Type ( zipOpenTvSubst, substTheta, substTys )
33 import DataCon ( classDataCon )
34 import Class ( classBigSig )
35 import Var ( Id, idName, idType )
36 import MkId ( mkDictFunId, rUNTIME_ERROR_ID )
37 import FunDeps ( checkInstFDs )
38 import Name ( Name, getSrcLoc )
39 import NameSet ( unitNameSet, emptyNameSet )
40 import UnicodeUtil ( stringToUtf8 )
41 import Maybe ( catMaybes )
42 import SrcLoc ( srcLocSpan, unLoc, noLoc, Located(..), srcSpanStart )
43 import ListSetOps ( minusList )
49 Typechecking instance declarations is done in two passes. The first
50 pass, made by @tcInstDecls1@, collects information to be used in the
53 This pre-processed info includes the as-yet-unprocessed bindings
54 inside the instance declaration. These are type-checked in the second
55 pass, when the class-instance envs and GVE contain all the info from
56 all the instance and value decls. Indeed that's the reason we need
57 two passes over the instance decls.
60 Here is the overall algorithm.
61 Assume that we have an instance declaration
63 instance c => k (t tvs) where b
67 $LIE_c$ is the LIE for the context of class $c$
69 $betas_bar$ is the free variables in the class method type, excluding the
72 $LIE_cop$ is the LIE constraining a particular class method
74 $tau_cop$ is the tau type of a class method
76 $LIE_i$ is the LIE for the context of instance $i$
78 $X$ is the instance constructor tycon
80 $gammas_bar$ is the set of type variables of the instance
82 $LIE_iop$ is the LIE for a particular class method instance
84 $tau_iop$ is the tau type for this instance of a class method
86 $alpha$ is the class variable
88 $LIE_cop' = LIE_cop [X gammas_bar / alpha, fresh betas_bar]$
90 $tau_cop' = tau_cop [X gammas_bar / alpha, fresh betas_bar]$
93 ToDo: Update the list above with names actually in the code.
97 First, make the LIEs for the class and instance contexts, which means
98 instantiate $thetaC [X inst_tyvars / alpha ]$, yielding LIElistC' and LIEC',
99 and make LIElistI and LIEI.
101 Then process each method in turn.
103 order the instance methods according to the ordering of the class methods
105 express LIEC' in terms of LIEI, yielding $dbinds_super$ or an error
107 Create final dictionary function from bindings generated already
109 df = lambda inst_tyvars
116 in <op1,op2,...,opn,sd1,...,sdm>
118 Here, Bop1 \ldots Bopn bind the methods op1 \ldots opn,
119 and $dbinds_super$ bind the superclass dictionaries sd1 \ldots sdm.
123 %************************************************************************
125 \subsection{Extracting instance decls}
127 %************************************************************************
129 Gather up the instance declarations from their various sources
132 tcInstDecls1 -- Deal with both source-code and imported instance decls
133 :: [LTyClDecl Name] -- For deriving stuff
134 -> [LInstDecl Name] -- Source code instance decls
135 -> TcM (TcGblEnv, -- The full inst env
136 [InstInfo], -- Source-code instance decls to process;
137 -- contains all dfuns for this module
138 [HsBindGroup Name]) -- Supporting bindings for derived instances
140 tcInstDecls1 tycl_decls inst_decls
142 -- Stop if addInstInfos etc discovers any errors
143 -- (they recover, so that we get more than one error each round)
145 -- (1) Do the ordinary instance declarations
146 mappM tcLocalInstDecl1 inst_decls `thenM` \ local_inst_infos ->
149 local_inst_info = catMaybes local_inst_infos
150 clas_decls = filter (isClassDecl.unLoc) tycl_decls
152 -- (2) Instances from generic class declarations
153 getGenericInstances clas_decls `thenM` \ generic_inst_info ->
155 -- Next, construct the instance environment so far, consisting of
156 -- a) local instance decls
157 -- b) generic instances
158 addInsts local_inst_info $
159 addInsts generic_inst_info $
161 -- (3) Compute instances from "deriving" clauses;
162 -- This stuff computes a context for the derived instance decl, so it
163 -- needs to know about all the instances possible; hence inst_env4
164 tcDeriving tycl_decls `thenM` \ (deriv_inst_info, deriv_binds) ->
165 addInsts deriv_inst_info $
167 getGblEnv `thenM` \ gbl_env ->
169 generic_inst_info ++ deriv_inst_info ++ local_inst_info,
172 addInsts :: [InstInfo] -> TcM a -> TcM a
173 addInsts infos thing_inside
174 = tcExtendLocalInstEnv (map iSpec infos) thing_inside
178 tcLocalInstDecl1 :: LInstDecl Name
179 -> TcM (Maybe InstInfo) -- Nothing if there was an error
180 -- A source-file instance declaration
181 -- Type-check all the stuff before the "where"
183 -- We check for respectable instance type, and context
184 -- but only do this for non-imported instance decls.
185 -- Imported ones should have been checked already, and may indeed
186 -- contain something illegal in normal Haskell, notably
187 -- instance CCallable [Char]
188 tcLocalInstDecl1 decl@(L loc (InstDecl poly_ty binds uprags))
189 = -- Prime error recovery, set source location
190 recoverM (returnM Nothing) $
192 addErrCtxt (instDeclCtxt1 poly_ty) $
194 -- Typecheck the instance type itself. We can't use
195 -- tcHsSigType, because it's not a valid user type.
196 kcHsSigType poly_ty `thenM` \ kinded_ty ->
197 tcHsKindedType kinded_ty `thenM` \ poly_ty' ->
199 (tyvars, theta, tau) = tcSplitSigmaTy poly_ty'
201 checkValidTheta InstThetaCtxt theta `thenM_`
202 checkAmbiguity tyvars theta (tyVarsOfType tau) `thenM_`
203 checkValidInstHead tau `thenM` \ (clas,inst_tys) ->
204 checkTc (checkInstFDs theta clas inst_tys)
205 (instTypeErr (pprClassPred clas inst_tys) msg) `thenM_`
206 newDFunName clas inst_tys (srcSpanStart loc) `thenM` \ dfun_name ->
207 getOverlapFlag `thenM` \ overlap_flag ->
208 let dfun = mkDictFunId dfun_name tyvars theta clas inst_tys
209 ispec = mkLocalInstance dfun overlap_flag
211 returnM (Just (InstInfo { iSpec = ispec, iBinds = VanillaInst binds uprags }))
213 msg = parens (ptext SLIT("the instance types do not agree with the functional dependencies of the class"))
217 %************************************************************************
219 \subsection{Type-checking instance declarations, pass 2}
221 %************************************************************************
224 tcInstDecls2 :: [LTyClDecl Name] -> [InstInfo]
225 -> TcM (TcLclEnv, LHsBinds Id)
226 -- (a) From each class declaration,
227 -- generate any default-method bindings
228 -- (b) From each instance decl
229 -- generate the dfun binding
231 tcInstDecls2 tycl_decls inst_decls
232 = do { -- (a) Default methods from class decls
233 (dm_binds_s, dm_ids_s) <- mapAndUnzipM tcClassDecl2 $
234 filter (isClassDecl.unLoc) tycl_decls
235 ; tcExtendIdEnv (concat dm_ids_s) $ do
237 -- (b) instance declarations
238 ; inst_binds_s <- mappM tcInstDecl2 inst_decls
241 ; tcl_env <- getLclEnv
242 ; returnM (tcl_env, unionManyBags dm_binds_s `unionBags`
243 unionManyBags inst_binds_s) }
246 ======= New documentation starts here (Sept 92) ==============
248 The main purpose of @tcInstDecl2@ is to return a @HsBinds@ which defines
249 the dictionary function for this instance declaration. For example
251 instance Foo a => Foo [a] where
255 might generate something like
257 dfun.Foo.List dFoo_a = let op1 x = ...
263 HOWEVER, if the instance decl has no context, then it returns a
264 bigger @HsBinds@ with declarations for each method. For example
266 instance Foo [a] where
272 dfun.Foo.List a = Dict [Foo.op1.List a, Foo.op2.List a]
273 const.Foo.op1.List a x = ...
274 const.Foo.op2.List a y = ...
276 This group may be mutually recursive, because (for example) there may
277 be no method supplied for op2 in which case we'll get
279 const.Foo.op2.List a = default.Foo.op2 (dfun.Foo.List a)
281 that is, the default method applied to the dictionary at this type.
283 What we actually produce in either case is:
285 AbsBinds [a] [dfun_theta_dicts]
286 [(dfun.Foo.List, d)] ++ (maybe) [(const.Foo.op1.List, op1), ...]
287 { d = (sd1,sd2, ..., op1, op2, ...)
292 The "maybe" says that we only ask AbsBinds to make global constant methods
293 if the dfun_theta is empty.
296 For an instance declaration, say,
298 instance (C1 a, C2 b) => C (T a b) where
301 where the {\em immediate} superclasses of C are D1, D2, we build a dictionary
302 function whose type is
304 (C1 a, C2 b, D1 (T a b), D2 (T a b)) => C (T a b)
306 Notice that we pass it the superclass dictionaries at the instance type; this
307 is the ``Mark Jones optimisation''. The stuff before the "=>" here
308 is the @dfun_theta@ below.
310 First comes the easy case of a non-local instance decl.
314 tcInstDecl2 :: InstInfo -> TcM (LHsBinds Id)
316 tcInstDecl2 (InstInfo { iSpec = ispec, iBinds = binds })
318 dfun_id = instanceDFunId ispec
319 rigid_info = InstSkol dfun_id
320 inst_ty = idType dfun_id
322 -- Prime error recovery
323 recoverM (returnM emptyLHsBinds) $
324 setSrcSpan (srcLocSpan (getSrcLoc dfun_id)) $
325 addErrCtxt (instDeclCtxt2 (idType dfun_id)) $
327 -- Instantiate the instance decl with skolem constants
328 tcSkolSigType rigid_info inst_ty `thenM` \ (inst_tyvars', dfun_theta', inst_head') ->
329 -- These inst_tyvars' scope over the 'where' part
330 -- Those tyvars are inside the dfun_id's type, which is a bit
331 -- bizarre, but OK so long as you realise it!
333 (clas, inst_tys') = tcSplitDFunHead inst_head'
334 (class_tyvars, sc_theta, _, op_items) = classBigSig clas
336 -- Instantiate the super-class context with inst_tys
337 sc_theta' = substTheta (zipOpenTvSubst class_tyvars inst_tys') sc_theta
338 origin = SigOrigin rigid_info
340 -- Create dictionary Ids from the specified instance contexts.
341 newDicts InstScOrigin sc_theta' `thenM` \ sc_dicts ->
342 newDicts origin dfun_theta' `thenM` \ dfun_arg_dicts ->
343 newDicts origin [mkClassPred clas inst_tys'] `thenM` \ [this_dict] ->
344 -- Default-method Ids may be mentioned in synthesised RHSs,
345 -- but they'll already be in the environment.
347 -- Typecheck the methods
348 let -- These insts are in scope; quite a few, eh?
349 avail_insts = [this_dict] ++ dfun_arg_dicts ++ sc_dicts
351 tcMethods origin clas inst_tyvars'
352 dfun_theta' inst_tys' avail_insts
353 op_items binds `thenM` \ (meth_ids, meth_binds) ->
355 -- Figure out bindings for the superclass context
356 -- Don't include this_dict in the 'givens', else
357 -- sc_dicts get bound by just selecting from this_dict!!
358 addErrCtxt superClassCtxt
359 (tcSimplifySuperClasses inst_tyvars'
361 sc_dicts) `thenM` \ sc_binds ->
363 -- It's possible that the superclass stuff might unified one
364 -- of the inst_tyavars' with something in the envt
365 checkSigTyVars inst_tyvars' `thenM_`
367 -- Deal with 'SPECIALISE instance' pragmas by making them
368 -- look like SPECIALISE pragmas for the dfun
370 uprags = case binds of
371 VanillaInst _ uprags -> uprags
373 spec_prags = [ L loc (SpecSig (L loc (idName dfun_id)) ty)
374 | L loc (SpecInstSig ty) <- uprags ]
376 tcExtendGlobalValEnv [dfun_id] (
377 tcExtendTyVarEnv inst_tyvars' $
378 tcSpecSigs spec_prags
379 ) `thenM` \ prag_binds ->
381 -- Create the result bindings
383 dict_constr = classDataCon clas
384 scs_and_meths = map instToId sc_dicts ++ meth_ids
385 this_dict_id = instToId this_dict
386 inlines | null dfun_arg_dicts = emptyNameSet
387 | otherwise = unitNameSet (idName dfun_id)
388 -- Always inline the dfun; this is an experimental decision
389 -- because it makes a big performance difference sometimes.
390 -- Often it means we can do the method selection, and then
391 -- inline the method as well. Marcin's idea; see comments below.
393 -- BUT: don't inline it if it's a constant dictionary;
394 -- we'll get all the benefit without inlining, and we get
395 -- a **lot** of code duplication if we inline it
397 -- See Note [Inline dfuns] below
401 = -- Blatant special case for CCallable, CReturnable
402 -- If the dictionary is empty then we should never
403 -- select anything from it, so we make its RHS just
404 -- emit an error message. This in turn means that we don't
405 -- mention the constructor, which doesn't exist for CCallable, CReturnable
406 -- Hardly beautiful, but only three extra lines.
407 nlHsApp (noLoc $ TyApp (nlHsVar rUNTIME_ERROR_ID)
408 [idType this_dict_id])
409 (nlHsLit (HsStringPrim (mkFastString (stringToUtf8 msg))))
411 | otherwise -- The common case
412 = mkHsConApp dict_constr inst_tys' (map HsVar scs_and_meths)
413 -- We don't produce a binding for the dict_constr; instead we
414 -- rely on the simplifier to unfold this saturated application
415 -- We do this rather than generate an HsCon directly, because
416 -- it means that the special cases (e.g. dictionary with only one
417 -- member) are dealt with by the common MkId.mkDataConWrapId code rather
418 -- than needing to be repeated here.
421 msg = "Compiler error: bad dictionary " ++ showSDoc (ppr clas)
423 dict_bind = noLoc (VarBind this_dict_id dict_rhs)
424 all_binds = dict_bind `consBag` (sc_binds `unionBags` meth_binds)
426 main_bind = noLoc $ AbsBinds
428 (map instToId dfun_arg_dicts)
429 [(inst_tyvars', dfun_id, this_dict_id)]
432 showLIE (text "instance") `thenM_`
433 returnM (unitBag main_bind `unionBags`
437 tcMethods origin clas inst_tyvars' dfun_theta' inst_tys'
438 avail_insts op_items (VanillaInst monobinds uprags)
439 = -- Check that all the method bindings come from this class
441 sel_names = [idName sel_id | (sel_id, _) <- op_items]
442 bad_bndrs = collectHsBindBinders monobinds `minusList` sel_names
444 mappM (addErrTc . badMethodErr clas) bad_bndrs `thenM_`
446 -- Make the method bindings
448 mk_method_bind = mkMethodBind origin clas inst_tys' monobinds
450 mapAndUnzipM mk_method_bind op_items `thenM` \ (meth_insts, meth_infos) ->
452 -- And type check them
453 -- It's really worth making meth_insts available to the tcMethodBind
454 -- Consider instance Monad (ST s) where
455 -- {-# INLINE (>>) #-}
456 -- (>>) = ...(>>=)...
457 -- If we don't include meth_insts, we end up with bindings like this:
458 -- rec { dict = MkD then bind ...
459 -- then = inline_me (... (GHC.Base.>>= dict) ...)
461 -- The trouble is that (a) 'then' and 'dict' are mutually recursive,
462 -- and (b) the inline_me prevents us inlining the >>= selector, which
463 -- would unravel the loop. Result: (>>) ends up as a loop breaker, and
464 -- is not inlined across modules. Rather ironic since this does not
465 -- happen without the INLINE pragma!
467 -- Solution: make meth_insts available, so that 'then' refers directly
468 -- to the local 'bind' rather than going via the dictionary.
470 -- BUT WATCH OUT! If the method type mentions the class variable, then
471 -- this optimisation is not right. Consider
475 -- instance C Int where
477 -- The occurrence of 'op' on the rhs gives rise to a constraint
479 -- The trouble is that the 'meth_inst' for op, which is 'available', also
480 -- looks like 'op at Int'. But they are not the same.
482 all_insts = avail_insts ++ catMaybes meth_insts
483 tc_method_bind = tcMethodBind inst_tyvars' dfun_theta' all_insts uprags
484 meth_ids = [meth_id | (_,meth_id,_) <- meth_infos]
487 mapM tc_method_bind meth_infos `thenM` \ meth_binds_s ->
489 returnM (meth_ids, unionManyBags meth_binds_s)
492 -- Derived newtype instances
493 tcMethods origin clas inst_tyvars' dfun_theta' inst_tys'
494 avail_insts op_items (NewTypeDerived rep_tys)
495 = getInstLoc origin `thenM` \ inst_loc ->
496 mapAndUnzip3M (do_one inst_loc) op_items `thenM` \ (meth_ids, meth_binds, rhs_insts) ->
499 (ptext SLIT("newtype derived instance"))
500 inst_tyvars' avail_insts rhs_insts `thenM` \ lie_binds ->
502 -- I don't think we have to do the checkSigTyVars thing
504 returnM (meth_ids, lie_binds `unionBags` listToBag meth_binds)
507 do_one inst_loc (sel_id, _)
508 = -- The binding is like "op @ NewTy = op @ RepTy"
509 -- Make the *binder*, like in mkMethodBind
510 tcInstClassOp inst_loc sel_id inst_tys' `thenM` \ meth_inst ->
512 -- Make the *occurrence on the rhs*
513 tcInstClassOp inst_loc sel_id rep_tys' `thenM` \ rhs_inst ->
515 meth_id = instToId meth_inst
517 return (meth_id, noLoc (VarBind meth_id (nlHsVar (instToId rhs_inst))), rhs_inst)
519 -- Instantiate rep_tys with the relevant type variables
520 -- This looks a bit odd, because inst_tyvars' are the skolemised version
521 -- of the type variables in the instance declaration; but rep_tys doesn't
522 -- have the skolemised version, so we substitute them in here
523 rep_tys' = substTys subst rep_tys
524 subst = zipOpenTvSubst inst_tyvars' (mkTyVarTys inst_tyvars')
528 ------------------------------
529 [Inline dfuns] Inlining dfuns unconditionally
530 ------------------------------
532 The code above unconditionally inlines dict funs. Here's why.
533 Consider this program:
535 test :: Int -> Int -> Bool
536 test x y = (x,y) == (y,x) || test y x
537 -- Recursive to avoid making it inline.
539 This needs the (Eq (Int,Int)) instance. If we inline that dfun
540 the code we end up with is good:
543 \r -> case ==# [ww ww1] of wild {
544 PrelBase.False -> Test.$wtest ww1 ww;
546 case ==# [ww1 ww] of wild1 {
547 PrelBase.False -> Test.$wtest ww1 ww;
548 PrelBase.True -> PrelBase.True [];
551 Test.test = \r [w w1]
554 case w1 of w3 { PrelBase.I# ww1 -> Test.$wtest ww ww1; };
557 If we don't inline the dfun, the code is not nearly as good:
559 (==) = case PrelTup.$fEq(,) PrelBase.$fEqInt PrelBase.$fEqInt of tpl {
560 PrelBase.:DEq tpl1 tpl2 -> tpl2;
565 let { y = PrelBase.I#! [ww1]; } in
566 let { x = PrelBase.I#! [ww]; } in
567 let { sat_slx = PrelTup.(,)! [y x]; } in
568 let { sat_sly = PrelTup.(,)! [x y];
570 case == sat_sly sat_slx of wild {
571 PrelBase.False -> Test.$wtest ww1 ww;
572 PrelBase.True -> PrelBase.True [];
579 case w1 of w3 { PrelBase.I# ww1 -> Test.$wtest ww ww1; };
582 Why doesn't GHC inline $fEq? Because it looks big:
584 PrelTup.zdfEqZ1T{-rcX-}
585 = \ @ a{-reT-} :: * @ b{-reS-} :: *
586 zddEq{-rf6-} _Ks :: {PrelBase.Eq{-23-} a{-reT-}}
587 zddEq1{-rf7-} _Ks :: {PrelBase.Eq{-23-} b{-reS-}} ->
589 zeze{-rf0-} _Kl :: (b{-reS-} -> b{-reS-} -> PrelBase.Bool{-3c-})
590 zeze{-rf0-} = PrelBase.zeze{-01L-}@ b{-reS-} zddEq1{-rf7-} } in
592 zeze1{-rf3-} _Kl :: (a{-reT-} -> a{-reT-} -> PrelBase.Bool{-3c-})
593 zeze1{-rf3-} = PrelBase.zeze{-01L-} @ a{-reT-} zddEq{-rf6-} } in
595 zeze2{-reN-} :: ((a{-reT-}, b{-reS-}) -> (a{-reT-}, b{-reS-})-> PrelBase.Bool{-3c-})
596 zeze2{-reN-} = \ ds{-rf5-} _Ks :: (a{-reT-}, b{-reS-})
597 ds1{-rf4-} _Ks :: (a{-reT-}, b{-reS-}) ->
599 of wild{-reW-} _Kd { (a1{-rf2-} _Ks, a2{-reZ-} _Ks) ->
601 of wild1{-reX-} _Kd { (b1{-rf1-} _Ks, b2{-reY-} _Ks) ->
603 (zeze1{-rf3-} a1{-rf2-} b1{-rf1-})
604 (zeze{-rf0-} a2{-reZ-} b2{-reY-})
608 a1{-reR-} :: ((a{-reT-}, b{-reS-})-> (a{-reT-}, b{-reS-})-> PrelBase.Bool{-3c-})
609 a1{-reR-} = \ a2{-reV-} _Ks :: (a{-reT-}, b{-reS-})
610 b1{-reU-} _Ks :: (a{-reT-}, b{-reS-}) ->
611 PrelBase.not{-r6I-} (zeze2{-reN-} a2{-reV-} b1{-reU-})
613 PrelBase.zdwZCDEq{-r8J-} @ (a{-reT-}, b{-reS-}) a1{-reR-} zeze2{-reN-})
615 and it's not as bad as it seems, because it's further dramatically
616 simplified: only zeze2 is extracted and its body is simplified.
619 %************************************************************************
621 \subsection{Error messages}
623 %************************************************************************
626 instDeclCtxt1 hs_inst_ty
627 = inst_decl_ctxt (case unLoc hs_inst_ty of
628 HsForAllTy _ _ _ (L _ (HsPredTy pred)) -> ppr pred
629 HsPredTy pred -> ppr pred
630 other -> ppr hs_inst_ty) -- Don't expect this
631 instDeclCtxt2 dfun_ty
632 = inst_decl_ctxt (ppr (mkClassPred cls tys))
634 (_,_,cls,tys) = tcSplitDFunTy dfun_ty
636 inst_decl_ctxt doc = ptext SLIT("In the instance declaration for") <+> quotes doc
638 superClassCtxt = ptext SLIT("When checking the super-classes of an instance declaration")