2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 \section[RnBinds]{Renaming and dependency analysis of bindings}
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).
13 rnTopBinds, rnTopMonoBinds,
14 rnMethodBinds, renameSigs,
19 #include "HsVersions.h"
21 import {-# SOURCE #-} RnSource ( rnHsSigType )
24 import HsBinds ( sigsForMe, cmpHsSig, sigName, hsSigDoc )
28 import RnExpr ( rnMatch, rnGRHSs, rnPat, checkPrecMatch )
29 import RnEnv ( bindLocatedLocalsRn, lookupBndrRn, lookupGlobalOccRn, lookupOccRn,
30 warnUnusedLocalBinds, mapFvRn,
31 FreeVars, emptyFVs, plusFV, plusFVs, unitFV, addOneFV,
34 import CmdLineOpts ( opt_WarnMissingSigs )
35 import Digraph ( stronglyConnComp, SCC(..) )
36 import Name ( OccName, Name, nameOccName, mkUnboundName, isUnboundName )
38 import RdrName ( RdrName, rdrNameOcc )
39 import BasicTypes ( RecFlag(..), TopLevelFlag(..) )
40 import Util ( thenCmp, removeDups )
41 import List ( partition )
42 import ListSetOps ( minusList )
43 import Bag ( bagToList )
44 import FiniteMap ( lookupFM, listToFM )
45 import Maybe ( isJust )
49 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
50 -- place and can be used when complaining.
52 The code tree received by the function @rnBinds@ contains definitions
53 in where-clauses which are all apparently mutually recursive, but which may
54 not really depend upon each other. For example, in the top level program
59 the definitions of @a@ and @y@ do not depend on each other at all.
60 Unfortunately, the typechecker cannot always check such definitions.
61 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
62 definitions. In Proceedings of the International Symposium on Programming,
63 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
64 However, the typechecker usually can check definitions in which only the
65 strongly connected components have been collected into recursive bindings.
66 This is precisely what the function @rnBinds@ does.
68 ToDo: deal with case where a single monobinds binds the same variable
71 The vertag tag is a unique @Int@; the tags only need to be unique
72 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
73 (heavy monad machinery not needed).
77 type Cycle = [VertexTag]
78 type Edge = (VertexTag, VertexTag)
81 %************************************************************************
83 %* naming conventions *
85 %************************************************************************
87 \subsection[name-conventions]{Name conventions}
89 The basic algorithm involves walking over the tree and returning a tuple
90 containing the new tree plus its free variables. Some functions, such
91 as those walking polymorphic bindings (HsBinds) and qualifier lists in
92 list comprehensions (@Quals@), return the variables bound in local
93 environments. These are then used to calculate the free variables of the
94 expression evaluated in these environments.
96 Conventions for variable names are as follows:
99 new code is given a prime to distinguish it from the old.
102 a set of variables defined in @Exp@ is written @dvExp@
105 a set of variables free in @Exp@ is written @fvExp@
108 %************************************************************************
110 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
112 %************************************************************************
114 \subsubsection[dep-HsBinds]{Polymorphic bindings}
116 Non-recursive expressions are reconstructed without any changes at top
117 level, although their component expressions may have to be altered.
118 However, non-recursive expressions are currently not expected as
119 \Haskell{} programs, and this code should not be executed.
121 Monomorphic bindings contain information that is returned in a tuple
122 (a @FlatMonoBindsInfo@) containing:
126 a unique @Int@ that serves as the ``vertex tag'' for this binding.
129 the name of a function or the names in a pattern. These are a set
130 referred to as @dvLhs@, the defined variables of the left hand side.
133 the free variables of the body. These are referred to as @fvBody@.
136 the definition's actual code. This is referred to as just @code@.
139 The function @nonRecDvFv@ returns two sets of variables. The first is
140 the set of variables defined in the set of monomorphic bindings, while the
141 second is the set of free variables in those bindings.
143 The set of variables defined in a non-recursive binding is just the
144 union of all of them, as @union@ removes duplicates. However, the
145 free variables in each successive set of cumulative bindings is the
146 union of those in the previous set plus those of the newest binding after
147 the defined variables of the previous set have been removed.
149 @rnMethodBinds@ deals only with the declarations in class and
150 instance declarations. It expects only to see @FunMonoBind@s, and
151 it expects the global environment to contain bindings for the binders
152 (which are all class operations).
154 %************************************************************************
156 \subsubsection{ Top-level bindings}
158 %************************************************************************
160 @rnTopBinds@ assumes that the environment already
161 contains bindings for the binders of this particular binding.
164 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
166 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
167 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
168 -- The parser doesn't produce other forms
171 rnTopMonoBinds EmptyMonoBinds sigs
172 = returnRn (EmptyBinds, emptyFVs)
174 rnTopMonoBinds mbinds sigs
175 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
176 renameSigs (okBindSig (mkNameSet binder_names)) sigs `thenRn` \ (siglist, sig_fvs) ->
178 type_sig_vars = [n | Sig n _ _ <- siglist]
179 un_sigd_binders | opt_WarnMissingSigs = binder_names `minusList` type_sig_vars
182 mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders `thenRn_`
184 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
185 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
187 binder_rdr_names = map fst (bagToList (collectMonoBinders mbinds))
190 %************************************************************************
194 %************************************************************************
196 \subsubsection{Nested binds}
200 \item collects up the binders for this declaration group,
201 \item checks that they form a set
202 \item extends the environment to bind them to new local names
203 \item calls @rnMonoBinds@ to do the real work
207 rnBinds :: RdrNameHsBinds
208 -> (RenamedHsBinds -> RnMS (result, FreeVars))
209 -> RnMS (result, FreeVars)
211 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
212 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
213 -- the parser doesn't produce other forms
216 rnMonoBinds :: RdrNameMonoBinds
218 -> (RenamedHsBinds -> RnMS (result, FreeVars))
219 -> RnMS (result, FreeVars)
221 rnMonoBinds EmptyMonoBinds sigs thing_inside = thing_inside EmptyBinds
223 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
224 = -- Extract all the binders in this group,
225 -- and extend current scope, inventing new names for the new binders
226 -- This also checks that the names form a set
227 bindLocatedLocalsRn (text "a binding group") mbinders_w_srclocs
230 binder_set = mkNameSet new_mbinders
232 -- Rename the signatures
233 renameSigs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
235 -- Report the fixity declarations in this group that
236 -- don't refer to any of the group's binders.
237 -- Then install the fixity declarations that do apply here
238 -- Notice that they scope over thing_inside too
240 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
242 extendFixityEnv fixity_sigs $
244 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
246 -- Now do the "thing inside", and deal with the free-variable calculations
247 thing_inside binds `thenRn` \ (result,result_fvs) ->
249 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
250 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
252 warnUnusedLocalBinds unused_binders `thenRn_`
253 returnRn (result, delListFromNameSet all_fvs new_mbinders)
255 mbinders_w_srclocs = bagToList (collectMonoBinders mbinds)
259 %************************************************************************
261 \subsubsection{ MonoBinds -- the main work is done here}
263 %************************************************************************
265 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
266 It assumes that all variables bound in this group are already in scope.
267 This is done {\em either} by pass 3 (for the top-level bindings),
268 {\em or} by @rnMonoBinds@ (for the nested ones).
271 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
273 -> RnMS (RenamedHsBinds, --
274 FreeVars) -- Free variables
276 rn_mono_binds siglist mbinds
278 -- Rename the bindings, returning a MonoBindsInfo
279 -- which is a list of indivisible vertices so far as
280 -- the strongly-connected-components (SCC) analysis is concerned
281 flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->
283 -- Do the SCC analysis
285 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
286 scc_result = stronglyConnComp edges
287 final_binds = foldr1 ThenBinds (map reconstructCycle scc_result)
289 -- Deal with bound and free-var calculation
290 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
292 returnRn (final_binds, rhs_fvs)
295 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
296 unique ``vertex tags'' on its output; minor plumbing required.
298 Sigh --- need to pass along the signatures for the group of bindings,
299 in case any of them \fbox{\ ???\ }
302 flattenMonoBinds :: [RenamedSig] -- Signatures
304 -> RnMS [FlatMonoBindsInfo]
306 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
308 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
309 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
310 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
311 returnRn (flat1 ++ flat2)
313 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
314 = pushSrcLocRn locn $
315 rnPat pat `thenRn` \ (pat', pat_fvs) ->
317 -- Find which things are bound in this group
319 names_bound_here = mkNameSet (collectPatBinders pat')
320 sigs_for_me = sigsForMe (`elemNameSet` names_bound_here) sigs
322 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
325 fvs `plusFV` pat_fvs,
326 PatMonoBind pat' grhss' locn,
330 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
331 = pushSrcLocRn locn $
332 lookupBndrRn name `thenRn` \ new_name ->
334 sigs_for_me = sigsForMe (new_name ==) sigs
336 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
337 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
339 [(unitNameSet new_name,
341 FunMonoBind new_name inf new_matches locn,
347 @rnMethodBinds@ is used for the method bindings of a class and an instance
348 declaration. Like @rnMonoBinds@ but without dependency analysis.
350 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
351 That's crucial when dealing with an instance decl:
353 instance Foo (T a) where
356 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
357 and unless @op@ occurs we won't treat the type signature of @op@ in the class
358 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
359 in many ways the @op@ in an instance decl is just like an occurrence, not
363 rnMethodBinds :: RdrNameMonoBinds -> RnMS (RenamedMonoBinds, FreeVars)
365 rnMethodBinds EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
367 rnMethodBinds (AndMonoBinds mb1 mb2)
368 = rnMethodBinds mb1 `thenRn` \ (mb1', fvs1) ->
369 rnMethodBinds mb2 `thenRn` \ (mb2', fvs2) ->
370 returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
372 rnMethodBinds (FunMonoBind name inf matches locn)
373 = pushSrcLocRn locn $
375 lookupGlobalOccRn name `thenRn` \ sel_name ->
376 -- We use the selector name as the binder
378 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
379 mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`
380 returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
382 -- Can't handle method pattern-bindings which bind multiple methods.
383 rnMethodBinds mbind@(PatMonoBind other_pat _ locn)
384 = pushSrcLocRn locn $
385 failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
389 %************************************************************************
391 \subsection[reconstruct-deps]{Reconstructing dependencies}
393 %************************************************************************
395 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
396 as the two cases are similar.
399 reconstructCycle :: SCC FlatMonoBindsInfo
402 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
403 = MonoBind binds sigs NonRecursive
405 reconstructCycle (CyclicSCC cycle)
406 = MonoBind this_gp_binds this_gp_sigs Recursive
408 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
409 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
412 %************************************************************************
414 \subsubsection{ Manipulating FlatMonoBindInfo}
416 %************************************************************************
418 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
419 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
420 a function binding, and has itself been dependency-analysed and
424 type FlatMonoBindsInfo
425 = (NameSet, -- Set of names defined in this vertex
426 NameSet, -- Set of names used in this vertex
428 [RenamedSig]) -- Signatures, if any, for this vertex
430 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
433 = [ (info, tag, dest_vertices (nameSetToList names_used))
434 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
437 -- An edge (v,v') indicates that v depends on v'
438 dest_vertices src_mentions = [ target_vertex
439 | ((names_defined, _, _, _), target_vertex) <- flat_info,
440 mentioned_name <- src_mentions,
441 mentioned_name `elemNameSet` names_defined
446 %************************************************************************
448 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
450 %************************************************************************
452 @renameSigs@ checks for:
454 \item more than one sig for one thing;
455 \item signatures given for things not bound here;
456 \item with suitably flaggery, that all top-level things have type signatures.
459 At the moment we don't gather free-var info from the types in
460 signatures. We'd only need this if we wanted to report unused tyvars.
463 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
465 -> RnMS ([RenamedSig], FreeVars)
467 renameSigs ok_sig [] = returnRn ([], emptyFVs) -- Common shortcut
469 renameSigs ok_sig sigs
470 = -- Rename the signatures
471 mapFvRn renameSig sigs `thenRn` \ (sigs', fvs) ->
473 -- Check for (a) duplicate signatures
474 -- (b) signatures for things not in this group
476 in_scope = filter is_in_scope sigs'
477 is_in_scope sig = case sigName sig of
478 Just n -> not (isUnboundName n)
480 (not_dups, dups) = removeDups cmpHsSig in_scope
481 (goods, bads) = partition ok_sig not_dups
483 mapRn_ unknownSigErr bads `thenRn_`
484 mapRn_ dupSigDeclErr dups `thenRn_`
485 returnRn (goods, fvs)
487 -- We use lookupOccRn in the signatures, which is a little bit unsatisfactory
488 -- because this won't work for:
489 -- instance Foo T where
492 -- We'll just rename the INLINE prag to refer to whatever other 'op'
493 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
494 -- Doesn't seem worth much trouble to sort this.
496 renameSig :: Sig RdrName -> RnMS (Sig Name, FreeVars)
498 renameSig (Sig v ty src_loc)
499 = pushSrcLocRn src_loc $
500 lookupOccRn v `thenRn` \ new_v ->
501 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
502 returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)
504 renameSig (SpecInstSig ty src_loc)
505 = pushSrcLocRn src_loc $
506 rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->
507 returnRn (SpecInstSig new_ty src_loc, fvs)
509 renameSig (SpecSig v ty src_loc)
510 = pushSrcLocRn src_loc $
511 lookupOccRn v `thenRn` \ new_v ->
512 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
513 returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)
515 renameSig (FixSig (FixitySig v fix src_loc))
516 = pushSrcLocRn src_loc $
517 lookupOccRn v `thenRn` \ new_v ->
518 returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)
520 renameSig (DeprecSig (Deprecation ie txt) src_loc)
521 = pushSrcLocRn src_loc $
522 renameIE lookupOccRn ie `thenRn` \ (new_ie, fvs) ->
523 returnRn (DeprecSig (Deprecation new_ie txt) src_loc, fvs)
525 renameSig (InlineSig v p src_loc)
526 = pushSrcLocRn src_loc $
527 lookupOccRn v `thenRn` \ new_v ->
528 returnRn (InlineSig new_v p src_loc, unitFV new_v)
530 renameSig (NoInlineSig v p src_loc)
531 = pushSrcLocRn src_loc $
532 lookupOccRn v `thenRn` \ new_v ->
533 returnRn (NoInlineSig new_v p src_loc, unitFV new_v)
537 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
538 renameIE lookup_occ_nm (IEVar v)
539 = lookup_occ_nm v `thenRn` \ new_v ->
540 returnRn (IEVar new_v, unitFV new_v)
542 renameIE lookup_occ_nm (IEThingAbs v)
543 = lookup_occ_nm v `thenRn` \ new_v ->
544 returnRn (IEThingAbs new_v, unitFV new_v)
546 renameIE lookup_occ_nm (IEThingAll v)
547 = lookup_occ_nm v `thenRn` \ new_v ->
548 returnRn (IEThingAll new_v, unitFV new_v)
550 renameIE lookup_occ_nm (IEThingWith v vs)
551 = lookup_occ_nm v `thenRn` \ new_v ->
552 mapRn lookup_occ_nm vs `thenRn` \ new_vs ->
553 returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
555 renameIE lookup_occ_nm (IEModuleContents m)
556 = returnRn (IEModuleContents m, emptyFVs)
560 %************************************************************************
562 \subsection{Error messages}
564 %************************************************************************
567 dupSigDeclErr (sig:sigs)
569 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
572 (what_it_is, loc) = hsSigDoc sig
576 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
579 (what_it_is, loc) = hsSigDoc sig
582 = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]
585 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))