[project @ 2000-09-28 13:04:14 by simonpj]
[ghc-hetmet.git] / ghc / compiler / typecheck / TcInstDcls.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 \section[TcInstDecls]{Typechecking instance declarations}
5
6 \begin{code}
7 module TcInstDcls ( tcInstDecls1, tcInstDecls2 ) where
8
9 #include "HsVersions.h"
10
11 import HsSyn            ( HsDecl(..), InstDecl(..),
12                           MonoBinds(..), HsExpr(..),  HsLit(..), Sig(..),
13                           andMonoBindList
14                         )
15 import RnHsSyn          ( RenamedHsBinds, RenamedInstDecl, RenamedHsDecl )
16 import TcHsSyn          ( TcMonoBinds, mkHsConApp )
17
18 import TcBinds          ( tcSpecSigs )
19 import TcClassDcl       ( tcMethodBind, checkFromThisClass )
20 import TcMonad
21 import RnMonad          ( RnNameSupply, FixityEnv )
22 import Inst             ( InstOrigin(..),
23                           newDicts, newClassDicts,
24                           LIE, emptyLIE, plusLIE, plusLIEs )
25 import TcDeriv          ( tcDeriving )
26 import TcEnv            ( ValueEnv, tcExtendGlobalValEnv, tcExtendTyVarEnvForMeths,
27                           tcAddImportedIdInfo, tcInstId, newDFunName
28                         )
29 import TcInstUtil       ( InstInfo(..), classDataCon )
30 import TcMonoType       ( tcHsSigType )
31 import TcSimplify       ( tcSimplifyAndCheck )
32 import TcType           ( zonkTcSigTyVars )
33
34 import Bag              ( emptyBag, unitBag, unionBags, unionManyBags,
35                           foldBag, Bag
36                         )
37 import CmdLineOpts      ( opt_GlasgowExts, opt_AllowUndecidableInstances )
38 import Class            ( classBigSig )
39 import Var              ( idName, idType )
40 import Maybes           ( maybeToBool, expectJust )
41 import MkId             ( mkDictFunId )
42 import Module           ( Module )
43 import Name             ( isLocallyDefined )
44 import NameSet          ( emptyNameSet )
45 import PrelInfo         ( eRROR_ID )
46 import PprType          ( pprConstraint )
47 import TyCon            ( isSynTyCon, tyConDerivings )
48 import Type             ( mkTyVarTys, splitSigmaTy, isTyVarTy,
49                           splitTyConApp_maybe, splitDictTy_maybe,
50                           splitAlgTyConApp_maybe,
51                           classesToPreds, classesOfPreds,
52                           unUsgTy, tyVarsOfTypes
53                         )
54 import Subst            ( mkTopTyVarSubst, substClasses )
55 import VarSet           ( mkVarSet, varSetElems )
56 import TysWiredIn       ( isFFIArgumentTy, isFFIResultTy )
57 import PrelNames        ( cCallableClassKey, cReturnableClassKey, hasKey )
58 import Outputable
59 \end{code}
60
61 Typechecking instance declarations is done in two passes. The first
62 pass, made by @tcInstDecls1@, collects information to be used in the
63 second pass.
64
65 This pre-processed info includes the as-yet-unprocessed bindings
66 inside the instance declaration.  These are type-checked in the second
67 pass, when the class-instance envs and GVE contain all the info from
68 all the instance and value decls.  Indeed that's the reason we need
69 two passes over the instance decls.
70
71
72 Here is the overall algorithm.
73 Assume that we have an instance declaration
74
75     instance c => k (t tvs) where b
76
77 \begin{enumerate}
78 \item
79 $LIE_c$ is the LIE for the context of class $c$
80 \item
81 $betas_bar$ is the free variables in the class method type, excluding the
82    class variable
83 \item
84 $LIE_cop$ is the LIE constraining a particular class method
85 \item
86 $tau_cop$ is the tau type of a class method
87 \item
88 $LIE_i$ is the LIE for the context of instance $i$
89 \item
90 $X$ is the instance constructor tycon
91 \item
92 $gammas_bar$ is the set of type variables of the instance
93 \item
94 $LIE_iop$ is the LIE for a particular class method instance
95 \item
96 $tau_iop$ is the tau type for this instance of a class method
97 \item
98 $alpha$ is the class variable
99 \item
100 $LIE_cop' = LIE_cop [X gammas_bar / alpha, fresh betas_bar]$
101 \item
102 $tau_cop' = tau_cop [X gammas_bar / alpha, fresh betas_bar]$
103 \end{enumerate}
104
105 ToDo: Update the list above with names actually in the code.
106
107 \begin{enumerate}
108 \item
109 First, make the LIEs for the class and instance contexts, which means
110 instantiate $thetaC [X inst_tyvars / alpha ]$, yielding LIElistC' and LIEC',
111 and make LIElistI and LIEI.
112 \item
113 Then process each method in turn.
114 \item
115 order the instance methods according to the ordering of the class methods
116 \item
117 express LIEC' in terms of LIEI, yielding $dbinds_super$ or an error
118 \item
119 Create final dictionary function from bindings generated already
120 \begin{pseudocode}
121 df = lambda inst_tyvars
122        lambda LIEI
123          let Bop1
124              Bop2
125              ...
126              Bopn
127          and dbinds_super
128               in <op1,op2,...,opn,sd1,...,sdm>
129 \end{pseudocode}
130 Here, Bop1 \ldots Bopn bind the methods op1 \ldots opn,
131 and $dbinds_super$ bind the superclass dictionaries sd1 \ldots sdm.
132 \end{enumerate}
133
134 \begin{code}
135 tcInstDecls1 :: ValueEnv                -- Contains IdInfo for dfun ids
136              -> [RenamedHsDecl]
137              -> Module                  -- Module for deriving
138              -> FixityEnv               -- For derivings
139              -> RnNameSupply            -- For renaming derivings
140              -> TcM s (Bag InstInfo,
141                        RenamedHsBinds)
142
143 tcInstDecls1 unf_env decls mod fixs rn_name_supply
144   =     -- Do the ordinary instance declarations
145     mapNF_Tc (tcInstDecl1 mod unf_env) 
146              [inst_decl | InstD inst_decl <- decls]     `thenNF_Tc` \ inst_info_bags ->
147     let
148         decl_inst_info = unionManyBags inst_info_bags
149     in
150         -- Handle "derived" instances; note that we only do derivings
151         -- for things in this module; we ignore deriving decls from
152         -- interfaces!
153     tcDeriving mod fixs rn_name_supply decl_inst_info
154                         `thenTc` \ (deriv_inst_info, deriv_binds) ->
155
156     let
157         full_inst_info = deriv_inst_info `unionBags` decl_inst_info
158     in
159     returnTc (full_inst_info, deriv_binds)
160
161
162 tcInstDecl1 :: Module -> ValueEnv -> RenamedInstDecl -> NF_TcM s (Bag InstInfo)
163
164 tcInstDecl1 mod unf_env (InstDecl poly_ty binds uprags maybe_dfun_name src_loc)
165   =     -- Prime error recovery, set source location
166     recoverNF_Tc (returnNF_Tc emptyBag) $
167     tcAddSrcLoc src_loc                 $
168
169         -- Type-check all the stuff before the "where"
170     tcHsSigType poly_ty                 `thenTc` \ poly_ty' ->
171     let
172         (tyvars, theta, dict_ty) = splitSigmaTy poly_ty'
173         constr                   = classesOfPreds theta
174         (clas, inst_tys)         = case splitDictTy_maybe dict_ty of
175                                      Just ct -> ct
176                                      Nothing -> pprPanic "tcInstDecl1" (ppr poly_ty)
177     in
178
179     (case maybe_dfun_name of
180         Nothing ->      -- A source-file instance declaration
181
182                 -- Check for respectable instance type, and context
183                 -- but only do this for non-imported instance decls.
184                 -- Imported ones should have been checked already, and may indeed
185                 -- contain something illegal in normal Haskell, notably
186                 --      instance CCallable [Char] 
187             scrutiniseInstanceHead clas inst_tys                `thenNF_Tc_`
188             mapNF_Tc scrutiniseInstanceConstraint constr        `thenNF_Tc_`
189
190                 -- Make the dfun id and return it
191             newDFunName mod clas inst_tys src_loc               `thenNF_Tc` \ dfun_name ->
192             returnNF_Tc (mkDictFunId dfun_name clas tyvars inst_tys constr)
193
194         Just dfun_name ->       -- An interface-file instance declaration
195                 -- Make the dfun id and add info from interface file
196             let
197                 dfun_id = mkDictFunId dfun_name clas tyvars inst_tys constr
198             in
199             returnNF_Tc (tcAddImportedIdInfo unf_env dfun_id)
200     )                                           `thenNF_Tc` \ dfun_id ->
201
202     returnTc (unitBag (InstInfo clas tyvars inst_tys constr dfun_id binds src_loc uprags))
203 \end{code}
204
205
206 %************************************************************************
207 %*                                                                      *
208 \subsection{Type-checking instance declarations, pass 2}
209 %*                                                                      *
210 %************************************************************************
211
212 \begin{code}
213 tcInstDecls2 :: Bag InstInfo
214              -> NF_TcM s (LIE, TcMonoBinds)
215
216 tcInstDecls2 inst_decls
217   = foldBag combine tcInstDecl2 (returnNF_Tc (emptyLIE, EmptyMonoBinds)) inst_decls
218   where
219     combine tc1 tc2 = tc1       `thenNF_Tc` \ (lie1, binds1) ->
220                       tc2       `thenNF_Tc` \ (lie2, binds2) ->
221                       returnNF_Tc (lie1 `plusLIE` lie2,
222                                    binds1 `AndMonoBinds` binds2)
223 \end{code}
224
225
226 ======= New documentation starts here (Sept 92)  ==============
227
228 The main purpose of @tcInstDecl2@ is to return a @HsBinds@ which defines
229 the dictionary function for this instance declaration.  For example
230 \begin{verbatim}
231         instance Foo a => Foo [a] where
232                 op1 x = ...
233                 op2 y = ...
234 \end{verbatim}
235 might generate something like
236 \begin{verbatim}
237         dfun.Foo.List dFoo_a = let op1 x = ...
238                                    op2 y = ...
239                                in
240                                    Dict [op1, op2]
241 \end{verbatim}
242
243 HOWEVER, if the instance decl has no context, then it returns a
244 bigger @HsBinds@ with declarations for each method.  For example
245 \begin{verbatim}
246         instance Foo [a] where
247                 op1 x = ...
248                 op2 y = ...
249 \end{verbatim}
250 might produce
251 \begin{verbatim}
252         dfun.Foo.List a = Dict [Foo.op1.List a, Foo.op2.List a]
253         const.Foo.op1.List a x = ...
254         const.Foo.op2.List a y = ...
255 \end{verbatim}
256 This group may be mutually recursive, because (for example) there may
257 be no method supplied for op2 in which case we'll get
258 \begin{verbatim}
259         const.Foo.op2.List a = default.Foo.op2 (dfun.Foo.List a)
260 \end{verbatim}
261 that is, the default method applied to the dictionary at this type.
262
263 What we actually produce in either case is:
264
265         AbsBinds [a] [dfun_theta_dicts]
266                  [(dfun.Foo.List, d)] ++ (maybe) [(const.Foo.op1.List, op1), ...]
267                  { d = (sd1,sd2, ..., op1, op2, ...)
268                    op1 = ...
269                    op2 = ...
270                  }
271
272 The "maybe" says that we only ask AbsBinds to make global constant methods
273 if the dfun_theta is empty.
274
275                 
276 For an instance declaration, say,
277
278         instance (C1 a, C2 b) => C (T a b) where
279                 ...
280
281 where the {\em immediate} superclasses of C are D1, D2, we build a dictionary
282 function whose type is
283
284         (C1 a, C2 b, D1 (T a b), D2 (T a b)) => C (T a b)
285
286 Notice that we pass it the superclass dictionaries at the instance type; this
287 is the ``Mark Jones optimisation''.  The stuff before the "=>" here
288 is the @dfun_theta@ below.
289
290 First comes the easy case of a non-local instance decl.
291
292 \begin{code}
293 tcInstDecl2 :: InstInfo -> NF_TcM s (LIE, TcMonoBinds)
294
295 tcInstDecl2 (InstInfo clas inst_tyvars inst_tys
296                       inst_decl_theta
297                       dfun_id monobinds
298                       locn uprags)
299   | not (isLocallyDefined dfun_id)
300   = returnNF_Tc (emptyLIE, EmptyMonoBinds)
301
302   | otherwise
303   =      -- Prime error recovery
304     recoverNF_Tc (returnNF_Tc (emptyLIE, EmptyMonoBinds))  $
305     tcAddSrcLoc locn                                       $
306
307          -- Check that all the method bindings come from this class
308     checkFromThisClass clas monobinds                   `thenNF_Tc_`
309
310         -- Instantiate the instance decl with tc-style type variables
311     tcInstId dfun_id            `thenNF_Tc` \ (inst_tyvars', dfun_theta', dict_ty') ->
312     let
313         (clas, inst_tys')       = expectJust "tcInstDecl2" (splitDictTy_maybe dict_ty')
314
315         origin                  = InstanceDeclOrigin
316
317         (class_tyvars, sc_theta, _, op_items) = classBigSig clas
318
319         dm_ids = [dm_id | (_, dm_id, _) <- op_items]
320
321         -- Instantiate the theta found in the original instance decl
322         inst_decl_theta' = substClasses (mkTopTyVarSubst inst_tyvars (mkTyVarTys inst_tyvars'))
323                                         inst_decl_theta
324
325          -- Instantiate the super-class context with inst_tys
326         sc_theta' = substClasses (mkTopTyVarSubst class_tyvars inst_tys') sc_theta
327     in
328          -- Create dictionary Ids from the specified instance contexts.
329     newClassDicts origin sc_theta'      `thenNF_Tc` \ (sc_dicts,        sc_dict_ids) ->
330     newDicts origin dfun_theta'         `thenNF_Tc` \ (dfun_arg_dicts,  dfun_arg_dicts_ids)  ->
331     newClassDicts origin inst_decl_theta' `thenNF_Tc` \ (inst_decl_dicts, _) ->
332     newClassDicts origin [(clas,inst_tys')] `thenNF_Tc` \ (this_dict,       [this_dict_id]) ->
333
334     tcExtendTyVarEnvForMeths inst_tyvars inst_tyvars' (
335         tcExtendGlobalValEnv dm_ids (
336                 -- Default-method Ids may be mentioned in synthesised RHSs 
337
338         mapAndUnzip3Tc (tcMethodBind clas origin inst_tyvars' inst_tys'
339                                      (classesToPreds inst_decl_theta')
340                                      monobinds uprags True)
341                        op_items
342     ))                  `thenTc` \ (method_binds_s, insts_needed_s, meth_lies_w_ids) ->
343
344         -- Deal with SPECIALISE instance pragmas by making them
345         -- look like SPECIALISE pragmas for the dfun
346     let
347         dfun_prags = [SpecSig (idName dfun_id) ty loc | SpecInstSig ty loc <- uprags]
348     in
349     tcExtendGlobalValEnv [dfun_id] (
350         tcSpecSigs dfun_prags
351     )                                   `thenTc` \ (prag_binds, prag_lie) ->
352
353         -- Check the overloading constraints of the methods and superclasses
354
355         -- tcMethodBind has checked that the class_tyvars havn't
356         -- been unified with each other or another type, but we must
357         -- still zonk them before passing them to tcSimplifyAndCheck
358     zonkTcSigTyVars inst_tyvars'        `thenNF_Tc` \ zonked_inst_tyvars ->
359     let
360         inst_tyvars_set = mkVarSet zonked_inst_tyvars
361
362         (meth_lies, meth_ids) = unzip meth_lies_w_ids
363
364                  -- These insts are in scope; quite a few, eh?
365         avail_insts = this_dict                 `plusLIE` 
366                       dfun_arg_dicts            `plusLIE`
367                       sc_dicts                  `plusLIE`
368                       unionManyBags meth_lies
369
370         methods_lie = plusLIEs insts_needed_s
371     in
372
373         -- Ditto method bindings
374     tcAddErrCtxt methodCtxt (
375       tcSimplifyAndCheck
376                  (ptext SLIT("instance declaration context"))
377                  inst_tyvars_set                        -- Local tyvars
378                  avail_insts
379                  methods_lie
380     )                                            `thenTc` \ (const_lie1, lie_binds1) ->
381     
382         -- Check that we *could* construct the superclass dictionaries,
383         -- even though we are *actually* going to pass the superclass dicts in;
384         -- the check ensures that the caller will never have 
385         --a problem building them.
386     tcAddErrCtxt superClassCtxt (
387       tcSimplifyAndCheck
388                  (ptext SLIT("instance declaration context"))
389                  inst_tyvars_set                -- Local tyvars
390                  inst_decl_dicts                -- The instance dictionaries available
391                  sc_dicts                       -- The superclass dicationaries reqd
392     )                                   `thenTc` \ _ -> 
393                                                 -- Ignore the result; we're only doing
394                                                 -- this to make sure it can be done.
395
396         -- Now do the simplification again, this time to get the
397         -- bindings; this time we use an enhanced "avails"
398         -- Ignore errors because they come from the *previous* tcSimplify
399     discardErrsTc (
400         tcSimplifyAndCheck
401                  (ptext SLIT("instance declaration context"))
402                  inst_tyvars_set
403                  dfun_arg_dicts         -- NB! Don't include this_dict here, else the sc_dicts
404                                         -- get bound by just selecting from this_dict!!
405                  sc_dicts
406     )                                            `thenTc` \ (const_lie2, lie_binds2) ->
407         
408
409         -- Create the result bindings
410     let
411         dict_constr   = classDataCon clas
412         scs_and_meths = sc_dict_ids ++ meth_ids
413
414         dict_rhs
415           | null scs_and_meths
416           =     -- Blatant special case for CCallable, CReturnable
417                 -- If the dictionary is empty then we should never
418                 -- select anything from it, so we make its RHS just
419                 -- emit an error message.  This in turn means that we don't
420                 -- mention the constructor, which doesn't exist for CCallable, CReturnable
421                 -- Hardly beautiful, but only three extra lines.
422             HsApp (TyApp (HsVar eRROR_ID) [(unUsgTy . idType) this_dict_id])
423                   (HsLit (HsString msg))
424
425           | otherwise   -- The common case
426           = mkHsConApp dict_constr inst_tys' (map HsVar (sc_dict_ids ++ meth_ids))
427                 -- We don't produce a binding for the dict_constr; instead we
428                 -- rely on the simplifier to unfold this saturated application
429                 -- We do this rather than generate an HsCon directly, because
430                 -- it means that the special cases (e.g. dictionary with only one
431                 -- member) are dealt with by the common MkId.mkDataConWrapId code rather
432                 -- than needing to be repeated here.
433
434           where
435             msg = _PK_ ("Compiler error: bad dictionary " ++ showSDoc (ppr clas))
436
437         dict_bind    = VarMonoBind this_dict_id dict_rhs
438         method_binds = andMonoBindList method_binds_s
439
440         main_bind
441           = AbsBinds
442                  zonked_inst_tyvars
443                  dfun_arg_dicts_ids
444                  [(inst_tyvars', dfun_id, this_dict_id)] 
445                  emptyNameSet           -- No inlines (yet)
446                  (lie_binds1    `AndMonoBinds` 
447                   lie_binds2    `AndMonoBinds`
448                   method_binds  `AndMonoBinds`
449                   dict_bind)
450     in
451     returnTc (const_lie1 `plusLIE` const_lie2 `plusLIE` prag_lie,
452               main_bind `AndMonoBinds` prag_binds)
453 \end{code}
454
455
456 %************************************************************************
457 %*                                                                      *
458 \subsection{Checking for a decent instance type}
459 %*                                                                      *
460 %************************************************************************
461
462 @scrutiniseInstanceHead@ checks the type {\em and} its syntactic constraints:
463 it must normally look like: @instance Foo (Tycon a b c ...) ...@
464
465 The exceptions to this syntactic checking: (1)~if the @GlasgowExts@
466 flag is on, or (2)~the instance is imported (they must have been
467 compiled elsewhere). In these cases, we let them go through anyway.
468
469 We can also have instances for functions: @instance Foo (a -> b) ...@.
470
471 \begin{code}
472 scrutiniseInstanceConstraint (clas, tys)
473   |  all isTyVarTy tys 
474   || opt_AllowUndecidableInstances = returnNF_Tc ()
475   | otherwise                      = addErrTc (instConstraintErr clas tys)
476
477 scrutiniseInstanceHead clas inst_taus
478   |     -- CCALL CHECK
479         -- A user declaration of a CCallable/CReturnable instance
480         -- must be for a "boxed primitive" type.
481     (clas `hasKey` cCallableClassKey   && not (ccallable_type   first_inst_tau)) ||
482     (clas `hasKey` cReturnableClassKey && not (creturnable_type first_inst_tau))
483   = addErrTc (nonBoxedPrimCCallErr clas first_inst_tau)
484
485         -- DERIVING CHECK
486         -- It is obviously illegal to have an explicit instance
487         -- for something that we are also planning to `derive'
488   | maybeToBool alg_tycon_app_maybe && clas `elem` (tyConDerivings alg_tycon)
489   = addErrTc (derivingWhenInstanceExistsErr clas first_inst_tau)
490            -- Kind check will have ensured inst_taus is of length 1
491
492         -- Allow anything for AllowUndecidableInstances
493   | opt_AllowUndecidableInstances
494   = returnNF_Tc ()
495
496         -- If GlasgowExts then check at least one isn't a type variable
497   | opt_GlasgowExts 
498   = if all isTyVarTy inst_taus then
499         addErrTc (instTypeErr clas inst_taus (text "There must be at least one non-type-variable in the instance head"))
500     else
501         returnNF_Tc ()
502
503         -- WITH HASKELL 1.4, MUST HAVE C (T a b c)
504   |  not (length inst_taus == 1 &&
505           maybeToBool maybe_tycon_app &&        -- Yes, there's a type constuctor
506           not (isSynTyCon tycon) &&             -- ...but not a synonym
507           all isTyVarTy arg_tys &&              -- Applied to type variables
508           length (varSetElems (tyVarsOfTypes arg_tys)) == length arg_tys
509                  -- This last condition checks that all the type variables are distinct
510      )
511   = addErrTc (instTypeErr clas inst_taus
512                         (text "the instance type must be of form (T a b c)" $$
513                          text "where T is not a synonym, and a,b,c are distinct type variables")
514     )
515
516   | otherwise
517   = returnNF_Tc ()
518
519   where
520     (first_inst_tau : _)       = inst_taus
521
522         -- Stuff for algebraic or -> type
523     maybe_tycon_app       = splitTyConApp_maybe first_inst_tau
524     Just (tycon, arg_tys) = maybe_tycon_app
525
526         -- Stuff for an *algebraic* data type
527     alg_tycon_app_maybe    = splitAlgTyConApp_maybe first_inst_tau
528                                 -- The "Alg" part looks through synonyms
529     Just (alg_tycon, _, _) = alg_tycon_app_maybe
530  
531 ccallable_type   ty = isFFIArgumentTy False {- Not safe call -} ty
532 creturnable_type ty = isFFIResultTy ty
533 \end{code}
534
535 \begin{code}
536 instConstraintErr clas tys
537   = hang (ptext SLIT("Illegal constraint") <+> 
538           quotes (pprConstraint clas tys) <+> 
539           ptext SLIT("in instance context"))
540          4 (ptext SLIT("(Instance contexts must constrain only type variables)"))
541         
542 instTypeErr clas tys msg
543   = sep [ptext SLIT("Illegal instance declaration for") <+> quotes (pprConstraint clas tys),
544          nest 4 (parens msg)
545     ]
546
547 derivingWhenInstanceExistsErr clas tycon
548   = hang (hsep [ptext SLIT("Deriving class"), 
549                        quotes (ppr clas), 
550                        ptext SLIT("type"), quotes (ppr tycon)])
551          4 (ptext SLIT("when an explicit instance exists"))
552
553 nonBoxedPrimCCallErr clas inst_ty
554   = hang (ptext SLIT("Unacceptable instance type for ccall-ish class"))
555          4 (hsep [ ptext SLIT("class"), ppr clas, ptext SLIT("type"),
556                         ppr inst_ty])
557
558 methodCtxt     = ptext SLIT("When checking the methods of an instance declaration")
559 superClassCtxt = ptext SLIT("When checking the superclasses of an instance declaration")
560 \end{code}