[project @ 2001-11-05 14:16:48 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, bindPatSigTyVars,
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     bindPatSigTyVars (collectSigTysFromMonoBinds mbinds) $ 
167     let
168         bndr_name_set = mkNameSet binder_names
169     in
170     renameSigsFVs (okBindSig bndr_name_set) sigs        `thenRn` \ (siglist, sig_fvs) ->
171
172     ifOptRn Opt_WarnMissingSigs (
173         let
174             type_sig_vars   = [n | Sig n _ _ <- siglist]
175             un_sigd_binders = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
176         in
177         mapRn_ missingSigWarn un_sigd_binders
178     )                                           `thenRn_`
179
180     rn_mono_binds siglist mbinds                `thenRn` \ (final_binds, bind_fvs) ->
181     returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
182   where
183     binder_rdr_names = collectMonoBinders mbinds
184 \end{code}
185
186 %************************************************************************
187 %*                                                                      *
188 %*              Nested binds
189 %*                                                                      *
190 %************************************************************************
191
192 \subsubsection{Nested binds}
193
194 @rnMonoBinds@
195 \begin{itemize}
196 \item collects up the binders for this declaration group,
197 \item checks that they form a set
198 \item extends the environment to bind them to new local names
199 \item calls @rnMonoBinds@ to do the real work
200 \end{itemize}
201 %
202 \begin{code}
203 rnBinds       :: RdrNameHsBinds 
204               -> (RenamedHsBinds -> RnMS (result, FreeVars))
205               -> RnMS (result, FreeVars)
206
207 rnBinds EmptyBinds             thing_inside = thing_inside EmptyBinds
208 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
209   -- the parser doesn't produce other forms
210
211
212 rnMonoBinds :: RdrNameMonoBinds 
213             -> [RdrNameSig]
214             -> (RenamedHsBinds -> RnMS (result, FreeVars))
215             -> RnMS (result, FreeVars)
216
217 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
218   =     -- Extract all the binders in this group,
219         -- and extend current scope, inventing new names for the new binders
220         -- This also checks that the names form a set
221     bindLocatedLocalsRn doc mbinders_w_srclocs                  $ \ new_mbinders ->
222     bindPatSigTyVars (collectSigTysFromMonoBinds mbinds)        $ 
223     let
224         binder_set = mkNameSet new_mbinders
225     in
226         -- Rename the signatures
227     renameSigsFVs (okBindSig binder_set) sigs   `thenRn` \ (siglist, sig_fvs) ->
228
229         -- Report the fixity declarations in this group that 
230         -- don't refer to any of the group's binders.
231         -- Then install the fixity declarations that do apply here
232         -- Notice that they scope over thing_inside too
233     let
234         fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
235     in
236     extendFixityEnv fixity_sigs $
237
238     rn_mono_binds siglist mbinds           `thenRn` \ (binds, bind_fvs) ->
239
240     -- Now do the "thing inside", and deal with the free-variable calculations
241     thing_inside binds                     `thenRn` \ (result,result_fvs) ->
242     let
243         all_fvs        = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
244         unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
245     in
246     warnUnusedLocalBinds unused_binders `thenRn_`
247     returnRn (result, delListFromNameSet all_fvs new_mbinders)
248   where
249     mbinders_w_srclocs = collectLocatedMonoBinders mbinds
250     doc = text "In the binding group for" <+> pp_bndrs mbinders_w_srclocs
251     pp_bndrs [(b,_)] = quotes (ppr b)
252     pp_bndrs bs      = fsep (punctuate comma [ppr b | (b,_) <- bs])
253 \end{code}
254
255
256 %************************************************************************
257 %*                                                                      *
258 \subsubsection{         MonoBinds -- the main work is done here}
259 %*                                                                      *
260 %************************************************************************
261
262 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
263 It assumes that all variables bound in this group are already in scope.
264 This is done {\em either} by pass 3 (for the top-level bindings),
265 {\em or} by @rnMonoBinds@ (for the nested ones).
266
267 \begin{code}
268 rn_mono_binds :: [RenamedSig]           -- Signatures attached to this group
269               -> RdrNameMonoBinds       
270               -> RnMS (RenamedHsBinds,  -- Dependency analysed
271                        FreeVars)        -- Free variables
272
273 rn_mono_binds siglist mbinds
274   =
275          -- Rename the bindings, returning a MonoBindsInfo
276          -- which is a list of indivisible vertices so far as
277          -- the strongly-connected-components (SCC) analysis is concerned
278     flattenMonoBinds siglist mbinds             `thenRn` \ mbinds_info ->
279
280          -- Do the SCC analysis
281     let 
282         edges       = mkEdges (mbinds_info `zip` [(0::Int)..])
283         scc_result  = stronglyConnComp edges
284         final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
285
286          -- Deal with bound and free-var calculation
287         rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
288     in
289     returnRn (final_binds, rhs_fvs)
290 \end{code}
291
292 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
293 unique ``vertex tags'' on its output; minor plumbing required.
294
295 Sigh --- need to pass along the signatures for the group of bindings,
296 in case any of them \fbox{\ ???\ } 
297
298 \begin{code}
299 flattenMonoBinds :: [RenamedSig]                -- Signatures
300                  -> RdrNameMonoBinds
301                  -> RnMS [FlatMonoBindsInfo]
302
303 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
304
305 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
306   = flattenMonoBinds sigs bs1   `thenRn` \ flat1 ->
307     flattenMonoBinds sigs bs2   `thenRn` \ flat2 ->
308     returnRn (flat1 ++ flat2)
309
310 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
311   = pushSrcLocRn locn                   $
312     rnPat pat                           `thenRn` \ (pat', pat_fvs) ->
313
314          -- Find which things are bound in this group
315     let
316         names_bound_here = mkNameSet (collectPatBinders pat')
317     in
318     sigsForMe names_bound_here sigs     `thenRn` \ sigs_for_me ->
319     rnGRHSs grhss                       `thenRn` \ (grhss', fvs) ->
320     returnRn 
321         [(names_bound_here,
322           fvs `plusFV` pat_fvs,
323           PatMonoBind pat' grhss' locn,
324           sigs_for_me
325          )]
326
327 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
328   = pushSrcLocRn locn                                   $
329     lookupBndrRn name                                   `thenRn` \ new_name ->
330     let
331         names_bound_here = unitNameSet new_name
332     in
333     sigsForMe names_bound_here sigs                     `thenRn` \ sigs_for_me ->
334     mapFvRn (rnMatch (FunRhs name)) matches             `thenRn` \ (new_matches, fvs) ->
335     mapRn_ (checkPrecMatch inf new_name) new_matches    `thenRn_`
336     returnRn
337       [(unitNameSet new_name,
338         fvs,
339         FunMonoBind new_name inf new_matches locn,
340         sigs_for_me
341         )]
342
343
344 sigsForMe names_bound_here sigs
345   = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
346   where
347     check sigs sig = case filter (eqHsSig sig) sigs of
348                         []    -> returnRn (sig:sigs)
349                         other -> dupSigDeclErr sig      `thenRn_`
350                                  returnRn sigs
351 \end{code}
352
353
354 @rnMethodBinds@ is used for the method bindings of a class and an instance
355 declaration.   Like @rnMonoBinds@ but without dependency analysis.
356
357 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
358 That's crucial when dealing with an instance decl:
359 \begin{verbatim}
360         instance Foo (T a) where
361            op x = ...
362 \end{verbatim}
363 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
364 and unless @op@ occurs we won't treat the type signature of @op@ in the class
365 decl for @Foo@ as a source of instance-decl gates.  But we should!  Indeed,
366 in many ways the @op@ in an instance decl is just like an occurrence, not
367 a binder.
368
369 \begin{code}
370 rnMethodBinds :: [Name]                 -- Names for generic type variables
371               -> RdrNameMonoBinds
372               -> RnMS (RenamedMonoBinds, FreeVars)
373
374 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
375
376 rnMethodBinds gen_tyvars (AndMonoBinds mb1 mb2)
377   = rnMethodBinds gen_tyvars mb1        `thenRn` \ (mb1', fvs1) ->
378     rnMethodBinds gen_tyvars mb2        `thenRn` \ (mb2', fvs2) ->
379     returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
380
381 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
382   = pushSrcLocRn locn                                   $
383
384     lookupGlobalOccRn name                              `thenRn` \ sel_name -> 
385         -- We use the selector name as the binder
386
387     mapFvRn rn_match matches                            `thenRn` \ (new_matches, fvs) ->
388     mapRn_ (checkPrecMatch inf sel_name) new_matches    `thenRn_`
389     returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
390   where
391         -- Gruesome; bring into scope the correct members of the generic type variables
392         -- See comments in RnSource.rnSourceDecl(ClassDecl)
393     rn_match match@(Match (TypePatIn ty : _) _ _)
394         = extendTyVarEnvFVRn gen_tvs (rnMatch (FunRhs name) match)
395         where
396           tvs     = map rdrNameOcc (extractHsTyRdrNames ty)
397           gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs] 
398
399     rn_match match = rnMatch (FunRhs name) match
400         
401
402 -- Can't handle method pattern-bindings which bind multiple methods.
403 rnMethodBinds gen_tyvars mbind@(PatMonoBind other_pat _ locn)
404   = pushSrcLocRn locn   $
405     failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
406 \end{code}
407
408
409 %************************************************************************
410 %*                                                                      *
411 \subsection[reconstruct-deps]{Reconstructing dependencies}
412 %*                                                                      *
413 %************************************************************************
414
415 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
416 as the two cases are similar.
417
418 \begin{code}
419 reconstructCycle :: SCC FlatMonoBindsInfo
420                  -> RenamedHsBinds
421
422 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
423   = MonoBind binds sigs NonRecursive
424
425 reconstructCycle (CyclicSCC cycle)
426   = MonoBind this_gp_binds this_gp_sigs Recursive
427   where
428     this_gp_binds      = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
429     this_gp_sigs       = foldr1 (++)         [sigs  | (_, _, _, sigs) <- cycle]
430 \end{code}
431
432 %************************************************************************
433 %*                                                                      *
434 \subsubsection{ Manipulating FlatMonoBindInfo}
435 %*                                                                      *
436 %************************************************************************
437
438 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
439 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
440 a function binding, and has itself been dependency-analysed and
441 renamed.
442
443 \begin{code}
444 type FlatMonoBindsInfo
445   = (NameSet,                   -- Set of names defined in this vertex
446      NameSet,                   -- Set of names used in this vertex
447      RenamedMonoBinds,
448      [RenamedSig])              -- Signatures, if any, for this vertex
449
450 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
451
452 mkEdges flat_info
453   = [ (info, tag, dest_vertices (nameSetToList names_used))
454     | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
455     ]
456   where
457          -- An edge (v,v') indicates that v depends on v'
458     dest_vertices src_mentions = [ target_vertex
459                                  | ((names_defined, _, _, _), target_vertex) <- flat_info,
460                                    mentioned_name <- src_mentions,
461                                    mentioned_name `elemNameSet` names_defined
462                                  ]
463 \end{code}
464
465
466 %************************************************************************
467 %*                                                                      *
468 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
469 %*                                                                      *
470 %************************************************************************
471
472 @renameSigs@ checks for:
473 \begin{enumerate}
474 \item more than one sig for one thing;
475 \item signatures given for things not bound here;
476 \item with suitably flaggery, that all top-level things have type signatures.
477 \end{enumerate}
478 %
479 At the moment we don't gather free-var info from the types in
480 signatures.  We'd only need this if we wanted to report unused tyvars.
481
482 \begin{code}
483 renameSigsFVs ok_sig sigs
484   = renameSigs ok_sig sigs      `thenRn` \ sigs' ->
485     returnRn (sigs', hsSigsFVs sigs')
486
487 renameSigs ::  (RenamedSig -> Bool)             -- OK-sig predicate
488             -> [RdrNameSig]
489             -> RnMS [RenamedSig]
490
491 renameSigs ok_sig [] = returnRn []
492
493 renameSigs ok_sig sigs
494   =      -- Rename the signatures
495     mapRn renameSig sigs        `thenRn` \ sigs' ->
496
497         -- Check for (a) duplicate signatures
498         --           (b) signatures for things not in this group
499     let
500         in_scope         = filter is_in_scope sigs'
501         is_in_scope sig  = case sigName sig of
502                                 Just n  -> not (isUnboundName n)
503                                 Nothing -> True
504         (goods, bads)    = partition ok_sig in_scope
505     in
506     mapRn_ unknownSigErr bads                   `thenRn_`
507     returnRn goods
508
509 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
510 -- because this won't work for:
511 --      instance Foo T where
512 --        {-# INLINE op #-}
513 --        Baz.op = ...
514 -- We'll just rename the INLINE prag to refer to whatever other 'op'
515 -- is in scope.  (I'm assuming that Baz.op isn't in scope unqualified.)
516 -- Doesn't seem worth much trouble to sort this.
517
518 renameSig :: Sig RdrName -> RnMS (Sig Name)
519 -- ClassOpSig is renamed elsewhere.
520 renameSig (Sig v ty src_loc)
521   = pushSrcLocRn src_loc $
522     lookupSigOccRn v                            `thenRn` \ new_v ->
523     rnHsSigType (quotes (ppr v)) ty             `thenRn` \ new_ty ->
524     returnRn (Sig new_v new_ty src_loc)
525
526 renameSig (SpecInstSig ty src_loc)
527   = pushSrcLocRn src_loc $
528     rnHsType (text "A SPECIALISE instance pragma") ty `thenRn` \ new_ty ->
529     returnRn (SpecInstSig new_ty src_loc)
530
531 renameSig (SpecSig v ty src_loc)
532   = pushSrcLocRn src_loc $
533     lookupSigOccRn v                    `thenRn` \ new_v ->
534     rnHsSigType (quotes (ppr v)) ty     `thenRn` \ new_ty ->
535     returnRn (SpecSig new_v new_ty src_loc)
536
537 renameSig (FixSig (FixitySig v fix src_loc))
538   = pushSrcLocRn src_loc $
539     lookupSigOccRn v            `thenRn` \ new_v ->
540     returnRn (FixSig (FixitySig new_v fix src_loc))
541
542 renameSig (InlineSig b v p src_loc)
543   = pushSrcLocRn src_loc $
544     lookupSigOccRn v            `thenRn` \ new_v ->
545     returnRn (InlineSig b new_v p src_loc)
546 \end{code}
547
548
549 %************************************************************************
550 %*                                                                      *
551 \subsection{Error messages}
552 %*                                                                      *
553 %************************************************************************
554
555 \begin{code}
556 dupSigDeclErr sig
557   = pushSrcLocRn loc $
558     addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
559                    ppr sig])
560   where
561     (what_it_is, loc) = hsSigDoc sig
562
563 unknownSigErr sig
564   = pushSrcLocRn loc $
565     addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
566                    ppr sig])
567   where
568     (what_it_is, loc) = hsSigDoc sig
569
570 missingSigWarn var
571   = pushSrcLocRn (nameSrcLoc var) $
572     addWarnRn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
573
574 methodBindErr mbind
575  =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
576        4 (ppr mbind)
577 \end{code}