[project @ 2000-07-18 14:50:32 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,
15         rnBinds,
16         unknownSigErr
17    ) where
18
19 #include "HsVersions.h"
20
21 import {-# SOURCE #-} RnSource ( rnHsSigType )
22
23 import HsSyn
24 import HsBinds          ( eqHsSig, sigName, hsSigDoc )
25 import RdrHsSyn
26 import RnHsSyn
27 import RnMonad
28 import RnExpr           ( rnMatch, rnGRHSs, rnPat, checkPrecMatch )
29 import RnEnv            ( bindLocatedLocalsRn, lookupBndrRn, 
30                           lookupGlobalOccRn, lookupOccRn, lookupSigOccRn,
31                           warnUnusedLocalBinds, mapFvRn, 
32                           FreeVars, emptyFVs, plusFV, plusFVs, unitFV, addOneFV,
33                           unknownNameErr
34                         )
35 import CmdLineOpts      ( opt_WarnMissingSigs )
36 import Digraph          ( stronglyConnComp, SCC(..) )
37 import Name             ( OccName, Name, nameOccName, mkUnboundName, isUnboundName )
38 import NameSet
39 import RdrName          ( RdrName, rdrNameOcc  )
40 import BasicTypes       ( RecFlag(..), TopLevelFlag(..) )
41 import List             ( partition )
42 import Bag              ( bagToList )
43 import Outputable
44 \end{code}
45
46 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
47 -- place and can be used when complaining.
48
49 The code tree received by the function @rnBinds@ contains definitions
50 in where-clauses which are all apparently mutually recursive, but which may
51 not really depend upon each other. For example, in the top level program
52 \begin{verbatim}
53 f x = y where a = x
54               y = x
55 \end{verbatim}
56 the definitions of @a@ and @y@ do not depend on each other at all.
57 Unfortunately, the typechecker cannot always check such definitions.
58 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
59 definitions. In Proceedings of the International Symposium on Programming,
60 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
61 However, the typechecker usually can check definitions in which only the
62 strongly connected components have been collected into recursive bindings.
63 This is precisely what the function @rnBinds@ does.
64
65 ToDo: deal with case where a single monobinds binds the same variable
66 twice.
67
68 The vertag tag is a unique @Int@; the tags only need to be unique
69 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
70 (heavy monad machinery not needed).
71
72 \begin{code}
73 type VertexTag  = Int
74 type Cycle      = [VertexTag]
75 type Edge       = (VertexTag, VertexTag)
76 \end{code}
77
78 %************************************************************************
79 %*                                                                      *
80 %* naming conventions                                                   *
81 %*                                                                      *
82 %************************************************************************
83
84 \subsection[name-conventions]{Name conventions}
85
86 The basic algorithm involves walking over the tree and returning a tuple
87 containing the new tree plus its free variables. Some functions, such
88 as those walking polymorphic bindings (HsBinds) and qualifier lists in
89 list comprehensions (@Quals@), return the variables bound in local
90 environments. These are then used to calculate the free variables of the
91 expression evaluated in these environments.
92
93 Conventions for variable names are as follows:
94 \begin{itemize}
95 \item
96 new code is given a prime to distinguish it from the old.
97
98 \item
99 a set of variables defined in @Exp@ is written @dvExp@
100
101 \item
102 a set of variables free in @Exp@ is written @fvExp@
103 \end{itemize}
104
105 %************************************************************************
106 %*                                                                      *
107 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds)            *
108 %*                                                                      *
109 %************************************************************************
110
111 \subsubsection[dep-HsBinds]{Polymorphic bindings}
112
113 Non-recursive expressions are reconstructed without any changes at top
114 level, although their component expressions may have to be altered.
115 However, non-recursive expressions are currently not expected as
116 \Haskell{} programs, and this code should not be executed.
117
118 Monomorphic bindings contain information that is returned in a tuple
119 (a @FlatMonoBindsInfo@) containing:
120
121 \begin{enumerate}
122 \item
123 a unique @Int@ that serves as the ``vertex tag'' for this binding.
124
125 \item
126 the name of a function or the names in a pattern. These are a set
127 referred to as @dvLhs@, the defined variables of the left hand side.
128
129 \item
130 the free variables of the body. These are referred to as @fvBody@.
131
132 \item
133 the definition's actual code. This is referred to as just @code@.
134 \end{enumerate}
135
136 The function @nonRecDvFv@ returns two sets of variables. The first is
137 the set of variables defined in the set of monomorphic bindings, while the
138 second is the set of free variables in those bindings.
139
140 The set of variables defined in a non-recursive binding is just the
141 union of all of them, as @union@ removes duplicates. However, the
142 free variables in each successive set of cumulative bindings is the
143 union of those in the previous set plus those of the newest binding after
144 the defined variables of the previous set have been removed.
145
146 @rnMethodBinds@ deals only with the declarations in class and
147 instance declarations.  It expects only to see @FunMonoBind@s, and
148 it expects the global environment to contain bindings for the binders
149 (which are all class operations).
150
151 %************************************************************************
152 %*                                                                      *
153 \subsubsection{ Top-level bindings}
154 %*                                                                      *
155 %************************************************************************
156
157 @rnTopBinds@ assumes that the environment already
158 contains bindings for the binders of this particular binding.
159
160 \begin{code}
161 rnTopBinds    :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
162
163 rnTopBinds EmptyBinds                     = returnRn (EmptyBinds, emptyFVs)
164 rnTopBinds (MonoBind bind sigs _)         = rnTopMonoBinds bind sigs
165   -- The parser doesn't produce other forms
166
167
168 rnTopMonoBinds mbinds sigs
169  =  mapRn lookupBndrRn binder_rdr_names         `thenRn` \ binder_names ->
170     let
171         bndr_name_set = mkNameSet binder_names
172     in
173     renameSigs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
174     let
175         type_sig_vars   = [n | Sig n _ _ <- siglist]
176         un_sigd_binders | opt_WarnMissingSigs = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
177                         | otherwise           = []
178     in
179     mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders   `thenRn_`
180
181     rn_mono_binds siglist mbinds                   `thenRn` \ (final_binds, bind_fvs) ->
182     returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
183   where
184     binder_rdr_names = map fst (bagToList (collectMonoBinders mbinds))
185 \end{code}
186
187 %************************************************************************
188 %*                                                                      *
189 %*              Nested binds
190 %*                                                                      *
191 %************************************************************************
192
193 \subsubsection{Nested binds}
194
195 @rnMonoBinds@
196 \begin{itemize}
197 \item collects up the binders for this declaration group,
198 \item checks that they form a set
199 \item extends the environment to bind them to new local names
200 \item calls @rnMonoBinds@ to do the real work
201 \end{itemize}
202 %
203 \begin{code}
204 rnBinds       :: RdrNameHsBinds 
205               -> (RenamedHsBinds -> RnMS (result, FreeVars))
206               -> RnMS (result, FreeVars)
207
208 rnBinds EmptyBinds             thing_inside = thing_inside EmptyBinds
209 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
210   -- the parser doesn't produce other forms
211
212
213 rnMonoBinds :: RdrNameMonoBinds 
214             -> [RdrNameSig]
215             -> (RenamedHsBinds -> RnMS (result, FreeVars))
216             -> RnMS (result, FreeVars)
217
218 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
219   =     -- Extract all the binders in this group,
220         -- and extend current scope, inventing new names for the new binders
221         -- This also checks that the names form a set
222     bindLocatedLocalsRn (text "a binding group") 
223                         mbinders_w_srclocs      $ \ new_mbinders ->
224     let
225         binder_set = mkNameSet new_mbinders
226     in
227         -- Rename the signatures
228     renameSigs (okBindSig binder_set) sigs      `thenRn` \ (siglist, sig_fvs) ->
229
230         -- Report the fixity declarations in this group that 
231         -- don't refer to any of the group's binders.
232         -- Then install the fixity declarations that do apply here
233         -- Notice that they scope over thing_inside too
234     let
235         fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
236     in
237     extendFixityEnv fixity_sigs $
238
239     rn_mono_binds siglist mbinds           `thenRn` \ (binds, bind_fvs) ->
240
241     -- Now do the "thing inside", and deal with the free-variable calculations
242     thing_inside binds                     `thenRn` \ (result,result_fvs) ->
243     let
244         all_fvs        = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
245         unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
246     in
247     warnUnusedLocalBinds unused_binders `thenRn_`
248     returnRn (result, delListFromNameSet all_fvs new_mbinders)
249   where
250     mbinders_w_srclocs = bagToList (collectMonoBinders mbinds)
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,  -- 
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 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 :: RdrNameMonoBinds -> RnMS (RenamedMonoBinds, FreeVars)
369
370 rnMethodBinds EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
371
372 rnMethodBinds (AndMonoBinds mb1 mb2)
373   = rnMethodBinds mb1   `thenRn` \ (mb1', fvs1) ->
374     rnMethodBinds mb2   `thenRn` \ (mb2', fvs2) ->
375     returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
376
377 rnMethodBinds (FunMonoBind name inf matches locn)
378   = pushSrcLocRn locn                                   $
379
380     lookupGlobalOccRn name                              `thenRn` \ sel_name -> 
381         -- We use the selector name as the binder
382
383     mapFvRn rnMatch matches                             `thenRn` \ (new_matches, fvs) ->
384     mapRn_ (checkPrecMatch inf sel_name) new_matches    `thenRn_`
385     returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
386
387 -- Can't handle method pattern-bindings which bind multiple methods.
388 rnMethodBinds mbind@(PatMonoBind other_pat _ locn)
389   = pushSrcLocRn locn   $
390     failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
391 \end{code}
392
393
394 %************************************************************************
395 %*                                                                      *
396 \subsection[reconstruct-deps]{Reconstructing dependencies}
397 %*                                                                      *
398 %************************************************************************
399
400 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
401 as the two cases are similar.
402
403 \begin{code}
404 reconstructCycle :: SCC FlatMonoBindsInfo
405                  -> RenamedHsBinds
406
407 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
408   = MonoBind binds sigs NonRecursive
409
410 reconstructCycle (CyclicSCC cycle)
411   = MonoBind this_gp_binds this_gp_sigs Recursive
412   where
413     this_gp_binds      = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
414     this_gp_sigs       = foldr1 (++)         [sigs  | (_, _, _, sigs) <- cycle]
415 \end{code}
416
417 %************************************************************************
418 %*                                                                      *
419 \subsubsection{ Manipulating FlatMonoBindInfo}
420 %*                                                                      *
421 %************************************************************************
422
423 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
424 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
425 a function binding, and has itself been dependency-analysed and
426 renamed.
427
428 \begin{code}
429 type FlatMonoBindsInfo
430   = (NameSet,                   -- Set of names defined in this vertex
431      NameSet,                   -- Set of names used in this vertex
432      RenamedMonoBinds,
433      [RenamedSig])              -- Signatures, if any, for this vertex
434
435 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
436
437 mkEdges flat_info
438   = [ (info, tag, dest_vertices (nameSetToList names_used))
439     | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
440     ]
441   where
442          -- An edge (v,v') indicates that v depends on v'
443     dest_vertices src_mentions = [ target_vertex
444                                  | ((names_defined, _, _, _), target_vertex) <- flat_info,
445                                    mentioned_name <- src_mentions,
446                                    mentioned_name `elemNameSet` names_defined
447                                  ]
448 \end{code}
449
450
451 %************************************************************************
452 %*                                                                      *
453 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
454 %*                                                                      *
455 %************************************************************************
456
457 @renameSigs@ checks for:
458 \begin{enumerate}
459 \item more than one sig for one thing;
460 \item signatures given for things not bound here;
461 \item with suitably flaggery, that all top-level things have type signatures.
462 \end{enumerate}
463 %
464 At the moment we don't gather free-var info from the types in
465 signatures.  We'd only need this if we wanted to report unused tyvars.
466
467 \begin{code}
468 renameSigs ::  (RenamedSig -> Bool)             -- OK-sig predicate
469             -> [RdrNameSig]
470             -> RnMS ([RenamedSig], FreeVars)
471
472 renameSigs ok_sig [] = returnRn ([], emptyFVs)  -- Common shortcut
473
474 renameSigs ok_sig sigs
475   =      -- Rename the signatures
476     mapFvRn renameSig sigs      `thenRn` \ (sigs', fvs) ->
477
478         -- Check for (a) duplicate signatures
479         --           (b) signatures for things not in this group
480     let
481         in_scope         = filter is_in_scope sigs'
482         is_in_scope sig  = case sigName sig of
483                                 Just n  -> not (isUnboundName n)
484                                 Nothing -> True
485         (goods, bads)    = partition ok_sig in_scope
486     in
487     mapRn_ unknownSigErr bads                   `thenRn_`
488     returnRn (goods, fvs)
489
490 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
491 -- because this won't work for:
492 --      instance Foo T where
493 --        {-# INLINE op #-}
494 --        Baz.op = ...
495 -- We'll just rename the INLINE prag to refer to whatever other 'op'
496 -- is in scope.  (I'm assuming that Baz.op isn't in scope unqualified.)
497 -- Doesn't seem worth much trouble to sort this.
498
499 renameSig :: Sig RdrName -> RnMS (Sig Name, FreeVars)
500
501 renameSig (Sig v ty src_loc)
502   = pushSrcLocRn src_loc $
503     lookupSigOccRn v                            `thenRn` \ new_v ->
504     rnHsSigType (quotes (ppr v)) ty             `thenRn` \ (new_ty,fvs) ->
505     returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)
506
507 renameSig (SpecInstSig ty src_loc)
508   = pushSrcLocRn src_loc $
509     rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->
510     returnRn (SpecInstSig new_ty src_loc, fvs)
511
512 renameSig (SpecSig v ty src_loc)
513   = pushSrcLocRn src_loc $
514     lookupSigOccRn v                    `thenRn` \ new_v ->
515     rnHsSigType (quotes (ppr v)) ty     `thenRn` \ (new_ty,fvs) ->
516     returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)
517
518 renameSig (FixSig (FixitySig v fix src_loc))
519   = pushSrcLocRn src_loc $
520     lookupSigOccRn v            `thenRn` \ new_v ->
521     returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)
522
523 renameSig (InlineSig v p src_loc)
524   = pushSrcLocRn src_loc $
525     lookupSigOccRn v            `thenRn` \ new_v ->
526     returnRn (InlineSig new_v p src_loc, unitFV new_v)
527
528 renameSig (NoInlineSig v p src_loc)
529   = pushSrcLocRn src_loc $
530     lookupSigOccRn v            `thenRn` \ new_v ->
531     returnRn (NoInlineSig new_v p src_loc, unitFV new_v)
532 \end{code}
533
534 \begin{code}
535 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
536 renameIE lookup_occ_nm (IEVar v)
537   = lookup_occ_nm v             `thenRn` \ new_v ->
538     returnRn (IEVar new_v, unitFV new_v)
539
540 renameIE lookup_occ_nm (IEThingAbs v)
541   = lookup_occ_nm v             `thenRn` \ new_v ->
542     returnRn (IEThingAbs new_v, unitFV new_v)
543
544 renameIE lookup_occ_nm (IEThingAll v)
545   = lookup_occ_nm v             `thenRn` \ new_v ->
546     returnRn (IEThingAll new_v, unitFV new_v)
547
548 renameIE lookup_occ_nm (IEThingWith v vs)
549   = lookup_occ_nm v             `thenRn` \ new_v ->
550     mapRn lookup_occ_nm vs      `thenRn` \ new_vs ->
551     returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
552
553 renameIE lookup_occ_nm (IEModuleContents m)
554   = returnRn (IEModuleContents m, emptyFVs)
555 \end{code}
556
557
558 %************************************************************************
559 %*                                                                      *
560 \subsection{Error messages}
561 %*                                                                      *
562 %************************************************************************
563
564 \begin{code}
565 dupSigDeclErr sig
566   = pushSrcLocRn loc $
567     addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
568                    ppr sig])
569   where
570     (what_it_is, loc) = hsSigDoc sig
571
572 unknownSigErr sig
573   = pushSrcLocRn loc $
574     addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
575                    ppr sig])
576   where
577     (what_it_is, loc) = hsSigDoc sig
578
579 missingSigWarn var
580   = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]
581
582 methodBindErr mbind
583  =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
584        4 (ppr mbind)
585 \end{code}