[project @ 2001-09-07 13:38:55 by simonpj]
[ghc-hetmet.git] / ghc / compiler / rename / RnBinds.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 \section[RnBinds]{Renaming and dependency analysis of bindings}
5
6 This module does renaming and dependency analysis on value bindings in
7 the abstract syntax.  It does {\em not} do cycle-checks on class or
8 type-synonym declarations; those cannot be done at this stage because
9 they may be affected by renaming (which isn't fully worked out yet).
10
11 \begin{code}
12 module RnBinds (
13         rnTopBinds, rnTopMonoBinds,
14         rnMethodBinds, renameSigs, renameSigsFVs,
15         rnBinds,
16         unknownSigErr
17    ) where
18
19 #include "HsVersions.h"
20
21
22 import HsSyn
23 import HsBinds          ( eqHsSig, sigName, hsSigDoc )
24 import RdrHsSyn
25 import RnHsSyn
26 import RnMonad
27 import RnTypes          ( rnHsSigType, rnHsType )
28 import RnExpr           ( rnMatch, rnGRHSs, rnPat, checkPrecMatch )
29 import RnEnv            ( bindLocatedLocalsRn, lookupBndrRn, 
30                           lookupGlobalOccRn, lookupSigOccRn,
31                           warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
32                         )
33 import CmdLineOpts      ( DynFlag(..) )
34 import Digraph          ( stronglyConnComp, SCC(..) )
35 import Name             ( Name, nameOccName, nameSrcLoc )
36 import NameSet
37 import RdrName          ( RdrName, rdrNameOcc )
38 import BasicTypes       ( RecFlag(..) )
39 import List             ( partition )
40 import Outputable
41 import PrelNames        ( isUnboundName )
42 \end{code}
43
44 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
45 -- place and can be used when complaining.
46
47 The code tree received by the function @rnBinds@ contains definitions
48 in where-clauses which are all apparently mutually recursive, but which may
49 not really depend upon each other. For example, in the top level program
50 \begin{verbatim}
51 f x = y where a = x
52               y = x
53 \end{verbatim}
54 the definitions of @a@ and @y@ do not depend on each other at all.
55 Unfortunately, the typechecker cannot always check such definitions.
56 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
57 definitions. In Proceedings of the International Symposium on Programming,
58 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
59 However, the typechecker usually can check definitions in which only the
60 strongly connected components have been collected into recursive bindings.
61 This is precisely what the function @rnBinds@ does.
62
63 ToDo: deal with case where a single monobinds binds the same variable
64 twice.
65
66 The vertag tag is a unique @Int@; the tags only need to be unique
67 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
68 (heavy monad machinery not needed).
69
70 \begin{code}
71 type VertexTag  = Int
72 \end{code}
73
74 %************************************************************************
75 %*                                                                      *
76 %* naming conventions                                                   *
77 %*                                                                      *
78 %************************************************************************
79
80 \subsection[name-conventions]{Name conventions}
81
82 The basic algorithm involves walking over the tree and returning a tuple
83 containing the new tree plus its free variables. Some functions, such
84 as those walking polymorphic bindings (HsBinds) and qualifier lists in
85 list comprehensions (@Quals@), return the variables bound in local
86 environments. These are then used to calculate the free variables of the
87 expression evaluated in these environments.
88
89 Conventions for variable names are as follows:
90 \begin{itemize}
91 \item
92 new code is given a prime to distinguish it from the old.
93
94 \item
95 a set of variables defined in @Exp@ is written @dvExp@
96
97 \item
98 a set of variables free in @Exp@ is written @fvExp@
99 \end{itemize}
100
101 %************************************************************************
102 %*                                                                      *
103 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds)            *
104 %*                                                                      *
105 %************************************************************************
106
107 \subsubsection[dep-HsBinds]{Polymorphic bindings}
108
109 Non-recursive expressions are reconstructed without any changes at top
110 level, although their component expressions may have to be altered.
111 However, non-recursive expressions are currently not expected as
112 \Haskell{} programs, and this code should not be executed.
113
114 Monomorphic bindings contain information that is returned in a tuple
115 (a @FlatMonoBindsInfo@) containing:
116
117 \begin{enumerate}
118 \item
119 a unique @Int@ that serves as the ``vertex tag'' for this binding.
120
121 \item
122 the name of a function or the names in a pattern. These are a set
123 referred to as @dvLhs@, the defined variables of the left hand side.
124
125 \item
126 the free variables of the body. These are referred to as @fvBody@.
127
128 \item
129 the definition's actual code. This is referred to as just @code@.
130 \end{enumerate}
131
132 The function @nonRecDvFv@ returns two sets of variables. The first is
133 the set of variables defined in the set of monomorphic bindings, while the
134 second is the set of free variables in those bindings.
135
136 The set of variables defined in a non-recursive binding is just the
137 union of all of them, as @union@ removes duplicates. However, the
138 free variables in each successive set of cumulative bindings is the
139 union of those in the previous set plus those of the newest binding after
140 the defined variables of the previous set have been removed.
141
142 @rnMethodBinds@ deals only with the declarations in class and
143 instance declarations.  It expects only to see @FunMonoBind@s, and
144 it expects the global environment to contain bindings for the binders
145 (which are all class operations).
146
147 %************************************************************************
148 %*                                                                      *
149 \subsubsection{ Top-level bindings}
150 %*                                                                      *
151 %************************************************************************
152
153 @rnTopBinds@ assumes that the environment already
154 contains bindings for the binders of this particular binding.
155
156 \begin{code}
157 rnTopBinds    :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
158
159 rnTopBinds EmptyBinds                     = returnRn (EmptyBinds, emptyFVs)
160 rnTopBinds (MonoBind bind sigs _)         = rnTopMonoBinds bind sigs
161   -- The parser doesn't produce other forms
162
163
164 rnTopMonoBinds mbinds sigs
165  =  mapRn lookupBndrRn binder_rdr_names         `thenRn` \ binder_names ->
166     let
167         bndr_name_set = mkNameSet binder_names
168     in
169     renameSigsFVs (okBindSig bndr_name_set) sigs        `thenRn` \ (siglist, sig_fvs) ->
170
171     ifOptRn Opt_WarnMissingSigs (
172         let
173             type_sig_vars   = [n | Sig n _ _ <- siglist]
174             un_sigd_binders = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
175         in
176         mapRn_ missingSigWarn un_sigd_binders
177     )                                           `thenRn_`
178
179     rn_mono_binds siglist mbinds                `thenRn` \ (final_binds, bind_fvs) ->
180     returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
181   where
182     binder_rdr_names = collectMonoBinders mbinds
183 \end{code}
184
185 %************************************************************************
186 %*                                                                      *
187 %*              Nested binds
188 %*                                                                      *
189 %************************************************************************
190
191 \subsubsection{Nested binds}
192
193 @rnMonoBinds@
194 \begin{itemize}
195 \item collects up the binders for this declaration group,
196 \item checks that they form a set
197 \item extends the environment to bind them to new local names
198 \item calls @rnMonoBinds@ to do the real work
199 \end{itemize}
200 %
201 \begin{code}
202 rnBinds       :: RdrNameHsBinds 
203               -> (RenamedHsBinds -> RnMS (result, FreeVars))
204               -> RnMS (result, FreeVars)
205
206 rnBinds EmptyBinds             thing_inside = thing_inside EmptyBinds
207 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
208   -- the parser doesn't produce other forms
209
210
211 rnMonoBinds :: RdrNameMonoBinds 
212             -> [RdrNameSig]
213             -> (RenamedHsBinds -> RnMS (result, FreeVars))
214             -> RnMS (result, FreeVars)
215
216 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
217   =     -- Extract all the binders in this group,
218         -- and extend current scope, inventing new names for the new binders
219         -- This also checks that the names form a set
220     bindLocatedLocalsRn doc mbinders_w_srclocs  $ \ new_mbinders ->
221     let
222         binder_set = mkNameSet new_mbinders
223     in
224         -- Rename the signatures
225     renameSigsFVs (okBindSig binder_set) sigs   `thenRn` \ (siglist, sig_fvs) ->
226
227         -- Report the fixity declarations in this group that 
228         -- don't refer to any of the group's binders.
229         -- Then install the fixity declarations that do apply here
230         -- Notice that they scope over thing_inside too
231     let
232         fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
233     in
234     extendFixityEnv fixity_sigs $
235
236     rn_mono_binds siglist mbinds           `thenRn` \ (binds, bind_fvs) ->
237
238     -- Now do the "thing inside", and deal with the free-variable calculations
239     thing_inside binds                     `thenRn` \ (result,result_fvs) ->
240     let
241         all_fvs        = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
242         unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
243     in
244     warnUnusedLocalBinds unused_binders `thenRn_`
245     returnRn (result, delListFromNameSet all_fvs new_mbinders)
246   where
247     mbinders_w_srclocs = collectLocatedMonoBinders mbinds
248     doc = text "In the binding group for" <+> pp_bndrs mbinders_w_srclocs
249     pp_bndrs [(b,_)] = quotes (ppr b)
250     pp_bndrs bs      = fsep (punctuate comma [ppr b | (b,_) <- bs])
251 \end{code}
252
253
254 %************************************************************************
255 %*                                                                      *
256 \subsubsection{         MonoBinds -- the main work is done here}
257 %*                                                                      *
258 %************************************************************************
259
260 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
261 It assumes that all variables bound in this group are already in scope.
262 This is done {\em either} by pass 3 (for the top-level bindings),
263 {\em or} by @rnMonoBinds@ (for the nested ones).
264
265 \begin{code}
266 rn_mono_binds :: [RenamedSig]           -- Signatures attached to this group
267               -> RdrNameMonoBinds       
268               -> RnMS (RenamedHsBinds,  -- Dependency analysed
269                        FreeVars)        -- Free variables
270
271 rn_mono_binds siglist mbinds
272   =
273          -- Rename the bindings, returning a MonoBindsInfo
274          -- which is a list of indivisible vertices so far as
275          -- the strongly-connected-components (SCC) analysis is concerned
276     flattenMonoBinds siglist mbinds             `thenRn` \ mbinds_info ->
277
278          -- Do the SCC analysis
279     let 
280         edges       = mkEdges (mbinds_info `zip` [(0::Int)..])
281         scc_result  = stronglyConnComp edges
282         final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
283
284          -- Deal with bound and free-var calculation
285         rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
286     in
287     returnRn (final_binds, rhs_fvs)
288 \end{code}
289
290 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
291 unique ``vertex tags'' on its output; minor plumbing required.
292
293 Sigh --- need to pass along the signatures for the group of bindings,
294 in case any of them \fbox{\ ???\ } 
295
296 \begin{code}
297 flattenMonoBinds :: [RenamedSig]                -- Signatures
298                  -> RdrNameMonoBinds
299                  -> RnMS [FlatMonoBindsInfo]
300
301 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
302
303 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
304   = flattenMonoBinds sigs bs1   `thenRn` \ flat1 ->
305     flattenMonoBinds sigs bs2   `thenRn` \ flat2 ->
306     returnRn (flat1 ++ flat2)
307
308 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
309   = pushSrcLocRn locn                   $
310     rnPat pat                           `thenRn` \ (pat', pat_fvs) ->
311
312          -- Find which things are bound in this group
313     let
314         names_bound_here = mkNameSet (collectPatBinders pat')
315     in
316     sigsForMe names_bound_here sigs     `thenRn` \ sigs_for_me ->
317     rnGRHSs grhss                       `thenRn` \ (grhss', fvs) ->
318     returnRn 
319         [(names_bound_here,
320           fvs `plusFV` pat_fvs,
321           PatMonoBind pat' grhss' locn,
322           sigs_for_me
323          )]
324
325 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
326   = pushSrcLocRn locn                                   $
327     lookupBndrRn name                                   `thenRn` \ new_name ->
328     let
329         names_bound_here = unitNameSet new_name
330     in
331     sigsForMe names_bound_here sigs                     `thenRn` \ sigs_for_me ->
332     mapFvRn (rnMatch (FunRhs name)) matches             `thenRn` \ (new_matches, fvs) ->
333     mapRn_ (checkPrecMatch inf new_name) new_matches    `thenRn_`
334     returnRn
335       [(unitNameSet new_name,
336         fvs,
337         FunMonoBind new_name inf new_matches locn,
338         sigs_for_me
339         )]
340
341
342 sigsForMe names_bound_here sigs
343   = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
344   where
345     check sigs sig = case filter (eqHsSig sig) sigs of
346                         []    -> returnRn (sig:sigs)
347                         other -> dupSigDeclErr sig      `thenRn_`
348                                  returnRn sigs
349 \end{code}
350
351
352 @rnMethodBinds@ is used for the method bindings of a class and an instance
353 declaration.   Like @rnMonoBinds@ but without dependency analysis.
354
355 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
356 That's crucial when dealing with an instance decl:
357 \begin{verbatim}
358         instance Foo (T a) where
359            op x = ...
360 \end{verbatim}
361 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
362 and unless @op@ occurs we won't treat the type signature of @op@ in the class
363 decl for @Foo@ as a source of instance-decl gates.  But we should!  Indeed,
364 in many ways the @op@ in an instance decl is just like an occurrence, not
365 a binder.
366
367 \begin{code}
368 rnMethodBinds :: [Name]                 -- Names for generic type variables
369               -> RdrNameMonoBinds
370               -> RnMS (RenamedMonoBinds, FreeVars)
371
372 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
373
374 rnMethodBinds gen_tyvars (AndMonoBinds mb1 mb2)
375   = rnMethodBinds gen_tyvars mb1        `thenRn` \ (mb1', fvs1) ->
376     rnMethodBinds gen_tyvars mb2        `thenRn` \ (mb2', fvs2) ->
377     returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
378
379 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
380   = pushSrcLocRn locn                                   $
381
382     lookupGlobalOccRn name                              `thenRn` \ sel_name -> 
383         -- We use the selector name as the binder
384
385     mapFvRn rn_match matches                            `thenRn` \ (new_matches, fvs) ->
386     mapRn_ (checkPrecMatch inf sel_name) new_matches    `thenRn_`
387     returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
388   where
389         -- Gruesome; bring into scope the correct members of the generic type variables
390         -- See comments in RnSource.rnSourceDecl(ClassDecl)
391     rn_match match@(Match _ (TypePatIn ty : _) _ _)
392         = extendTyVarEnvFVRn gen_tvs (rnMatch (FunRhs name) match)
393         where
394           tvs     = map rdrNameOcc (extractHsTyRdrNames ty)
395           gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs] 
396
397     rn_match match = rnMatch (FunRhs name) match
398         
399
400 -- Can't handle method pattern-bindings which bind multiple methods.
401 rnMethodBinds gen_tyvars mbind@(PatMonoBind other_pat _ locn)
402   = pushSrcLocRn locn   $
403     failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
404 \end{code}
405
406
407 %************************************************************************
408 %*                                                                      *
409 \subsection[reconstruct-deps]{Reconstructing dependencies}
410 %*                                                                      *
411 %************************************************************************
412
413 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
414 as the two cases are similar.
415
416 \begin{code}
417 reconstructCycle :: SCC FlatMonoBindsInfo
418                  -> RenamedHsBinds
419
420 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
421   = MonoBind binds sigs NonRecursive
422
423 reconstructCycle (CyclicSCC cycle)
424   = MonoBind this_gp_binds this_gp_sigs Recursive
425   where
426     this_gp_binds      = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
427     this_gp_sigs       = foldr1 (++)         [sigs  | (_, _, _, sigs) <- cycle]
428 \end{code}
429
430 %************************************************************************
431 %*                                                                      *
432 \subsubsection{ Manipulating FlatMonoBindInfo}
433 %*                                                                      *
434 %************************************************************************
435
436 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
437 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
438 a function binding, and has itself been dependency-analysed and
439 renamed.
440
441 \begin{code}
442 type FlatMonoBindsInfo
443   = (NameSet,                   -- Set of names defined in this vertex
444      NameSet,                   -- Set of names used in this vertex
445      RenamedMonoBinds,
446      [RenamedSig])              -- Signatures, if any, for this vertex
447
448 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
449
450 mkEdges flat_info
451   = [ (info, tag, dest_vertices (nameSetToList names_used))
452     | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
453     ]
454   where
455          -- An edge (v,v') indicates that v depends on v'
456     dest_vertices src_mentions = [ target_vertex
457                                  | ((names_defined, _, _, _), target_vertex) <- flat_info,
458                                    mentioned_name <- src_mentions,
459                                    mentioned_name `elemNameSet` names_defined
460                                  ]
461 \end{code}
462
463
464 %************************************************************************
465 %*                                                                      *
466 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
467 %*                                                                      *
468 %************************************************************************
469
470 @renameSigs@ checks for:
471 \begin{enumerate}
472 \item more than one sig for one thing;
473 \item signatures given for things not bound here;
474 \item with suitably flaggery, that all top-level things have type signatures.
475 \end{enumerate}
476 %
477 At the moment we don't gather free-var info from the types in
478 signatures.  We'd only need this if we wanted to report unused tyvars.
479
480 \begin{code}
481 renameSigsFVs ok_sig sigs
482   = renameSigs ok_sig sigs      `thenRn` \ sigs' ->
483     returnRn (sigs', hsSigsFVs sigs')
484
485 renameSigs ::  (RenamedSig -> Bool)             -- OK-sig predicate
486             -> [RdrNameSig]
487             -> RnMS [RenamedSig]
488
489 renameSigs ok_sig [] = returnRn []
490
491 renameSigs ok_sig sigs
492   =      -- Rename the signatures
493     mapRn renameSig sigs        `thenRn` \ sigs' ->
494
495         -- Check for (a) duplicate signatures
496         --           (b) signatures for things not in this group
497     let
498         in_scope         = filter is_in_scope sigs'
499         is_in_scope sig  = case sigName sig of
500                                 Just n  -> not (isUnboundName n)
501                                 Nothing -> True
502         (goods, bads)    = partition ok_sig in_scope
503     in
504     mapRn_ unknownSigErr bads                   `thenRn_`
505     returnRn goods
506
507 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
508 -- because this won't work for:
509 --      instance Foo T where
510 --        {-# INLINE op #-}
511 --        Baz.op = ...
512 -- We'll just rename the INLINE prag to refer to whatever other 'op'
513 -- is in scope.  (I'm assuming that Baz.op isn't in scope unqualified.)
514 -- Doesn't seem worth much trouble to sort this.
515
516 renameSig :: Sig RdrName -> RnMS (Sig Name)
517 -- ClassOpSig is renamed elsewhere.
518 renameSig (Sig v ty src_loc)
519   = pushSrcLocRn src_loc $
520     lookupSigOccRn v                            `thenRn` \ new_v ->
521     rnHsSigType (quotes (ppr v)) ty             `thenRn` \ new_ty ->
522     returnRn (Sig new_v new_ty src_loc)
523
524 renameSig (SpecInstSig ty src_loc)
525   = pushSrcLocRn src_loc $
526     rnHsType (text "A SPECIALISE instance pragma") ty `thenRn` \ new_ty ->
527     returnRn (SpecInstSig new_ty src_loc)
528
529 renameSig (SpecSig v ty src_loc)
530   = pushSrcLocRn src_loc $
531     lookupSigOccRn v                    `thenRn` \ new_v ->
532     rnHsSigType (quotes (ppr v)) ty     `thenRn` \ new_ty ->
533     returnRn (SpecSig new_v new_ty src_loc)
534
535 renameSig (FixSig (FixitySig v fix src_loc))
536   = pushSrcLocRn src_loc $
537     lookupSigOccRn v            `thenRn` \ new_v ->
538     returnRn (FixSig (FixitySig new_v fix src_loc))
539
540 renameSig (InlineSig v p src_loc)
541   = pushSrcLocRn src_loc $
542     lookupSigOccRn v            `thenRn` \ new_v ->
543     returnRn (InlineSig new_v p src_loc)
544
545 renameSig (NoInlineSig v p src_loc)
546   = pushSrcLocRn src_loc $
547     lookupSigOccRn v            `thenRn` \ new_v ->
548     returnRn (NoInlineSig new_v p src_loc)
549 \end{code}
550
551
552 %************************************************************************
553 %*                                                                      *
554 \subsection{Error messages}
555 %*                                                                      *
556 %************************************************************************
557
558 \begin{code}
559 dupSigDeclErr sig
560   = pushSrcLocRn loc $
561     addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
562                    ppr sig])
563   where
564     (what_it_is, loc) = hsSigDoc sig
565
566 unknownSigErr sig
567   = pushSrcLocRn loc $
568     addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
569                    ppr sig])
570   where
571     (what_it_is, loc) = hsSigDoc sig
572
573 missingSigWarn var
574   = pushSrcLocRn (nameSrcLoc var) $
575     addWarnRn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
576
577 methodBindErr mbind
578  =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
579        4 (ppr mbind)
580 \end{code}