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 ( eqHsSig, sigName, hsSigDoc )
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,
35 import CmdLineOpts ( opt_WarnMissingSigs )
36 import Digraph ( stronglyConnComp, SCC(..) )
37 import Name ( OccName, Name, nameOccName, mkUnboundName, isUnboundName )
39 import RdrName ( RdrName, rdrNameOcc )
40 import BasicTypes ( RecFlag(..), TopLevelFlag(..) )
41 import Util ( thenCmp, removeDups )
42 import List ( partition )
43 import ListSetOps ( minusList )
44 import Bag ( bagToList )
45 import FiniteMap ( lookupFM, listToFM )
46 import Maybe ( isJust )
50 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
51 -- place and can be used when complaining.
53 The code tree received by the function @rnBinds@ contains definitions
54 in where-clauses which are all apparently mutually recursive, but which may
55 not really depend upon each other. For example, in the top level program
60 the definitions of @a@ and @y@ do not depend on each other at all.
61 Unfortunately, the typechecker cannot always check such definitions.
62 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
63 definitions. In Proceedings of the International Symposium on Programming,
64 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
65 However, the typechecker usually can check definitions in which only the
66 strongly connected components have been collected into recursive bindings.
67 This is precisely what the function @rnBinds@ does.
69 ToDo: deal with case where a single monobinds binds the same variable
72 The vertag tag is a unique @Int@; the tags only need to be unique
73 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
74 (heavy monad machinery not needed).
78 type Cycle = [VertexTag]
79 type Edge = (VertexTag, VertexTag)
82 %************************************************************************
84 %* naming conventions *
86 %************************************************************************
88 \subsection[name-conventions]{Name conventions}
90 The basic algorithm involves walking over the tree and returning a tuple
91 containing the new tree plus its free variables. Some functions, such
92 as those walking polymorphic bindings (HsBinds) and qualifier lists in
93 list comprehensions (@Quals@), return the variables bound in local
94 environments. These are then used to calculate the free variables of the
95 expression evaluated in these environments.
97 Conventions for variable names are as follows:
100 new code is given a prime to distinguish it from the old.
103 a set of variables defined in @Exp@ is written @dvExp@
106 a set of variables free in @Exp@ is written @fvExp@
109 %************************************************************************
111 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
113 %************************************************************************
115 \subsubsection[dep-HsBinds]{Polymorphic bindings}
117 Non-recursive expressions are reconstructed without any changes at top
118 level, although their component expressions may have to be altered.
119 However, non-recursive expressions are currently not expected as
120 \Haskell{} programs, and this code should not be executed.
122 Monomorphic bindings contain information that is returned in a tuple
123 (a @FlatMonoBindsInfo@) containing:
127 a unique @Int@ that serves as the ``vertex tag'' for this binding.
130 the name of a function or the names in a pattern. These are a set
131 referred to as @dvLhs@, the defined variables of the left hand side.
134 the free variables of the body. These are referred to as @fvBody@.
137 the definition's actual code. This is referred to as just @code@.
140 The function @nonRecDvFv@ returns two sets of variables. The first is
141 the set of variables defined in the set of monomorphic bindings, while the
142 second is the set of free variables in those bindings.
144 The set of variables defined in a non-recursive binding is just the
145 union of all of them, as @union@ removes duplicates. However, the
146 free variables in each successive set of cumulative bindings is the
147 union of those in the previous set plus those of the newest binding after
148 the defined variables of the previous set have been removed.
150 @rnMethodBinds@ deals only with the declarations in class and
151 instance declarations. It expects only to see @FunMonoBind@s, and
152 it expects the global environment to contain bindings for the binders
153 (which are all class operations).
155 %************************************************************************
157 \subsubsection{ Top-level bindings}
159 %************************************************************************
161 @rnTopBinds@ assumes that the environment already
162 contains bindings for the binders of this particular binding.
165 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
167 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
168 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
169 -- The parser doesn't produce other forms
172 rnTopMonoBinds EmptyMonoBinds sigs
173 = returnRn (EmptyBinds, emptyFVs)
175 rnTopMonoBinds mbinds sigs
176 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
178 bndr_name_set = mkNameSet binder_names
180 renameSigs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
182 type_sig_vars = [n | Sig n _ _ <- siglist]
183 un_sigd_binders | opt_WarnMissingSigs = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
186 mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders `thenRn_`
188 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
189 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
191 binder_rdr_names = map fst (bagToList (collectMonoBinders mbinds))
194 %************************************************************************
198 %************************************************************************
200 \subsubsection{Nested binds}
204 \item collects up the binders for this declaration group,
205 \item checks that they form a set
206 \item extends the environment to bind them to new local names
207 \item calls @rnMonoBinds@ to do the real work
211 rnBinds :: RdrNameHsBinds
212 -> (RenamedHsBinds -> RnMS (result, FreeVars))
213 -> RnMS (result, FreeVars)
215 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
216 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
217 -- the parser doesn't produce other forms
220 rnMonoBinds :: RdrNameMonoBinds
222 -> (RenamedHsBinds -> RnMS (result, FreeVars))
223 -> RnMS (result, FreeVars)
225 rnMonoBinds EmptyMonoBinds sigs thing_inside = thing_inside EmptyBinds
227 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
228 = -- Extract all the binders in this group,
229 -- and extend current scope, inventing new names for the new binders
230 -- This also checks that the names form a set
231 bindLocatedLocalsRn (text "a binding group") mbinders_w_srclocs
234 binder_set = mkNameSet new_mbinders
236 -- Rename the signatures
237 renameSigs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
239 -- Report the fixity declarations in this group that
240 -- don't refer to any of the group's binders.
241 -- Then install the fixity declarations that do apply here
242 -- Notice that they scope over thing_inside too
244 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
246 extendFixityEnv fixity_sigs $
248 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
250 -- Now do the "thing inside", and deal with the free-variable calculations
251 thing_inside binds `thenRn` \ (result,result_fvs) ->
253 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
254 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
256 warnUnusedLocalBinds unused_binders `thenRn_`
257 returnRn (result, delListFromNameSet all_fvs new_mbinders)
259 mbinders_w_srclocs = bagToList (collectMonoBinders mbinds)
263 %************************************************************************
265 \subsubsection{ MonoBinds -- the main work is done here}
267 %************************************************************************
269 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
270 It assumes that all variables bound in this group are already in scope.
271 This is done {\em either} by pass 3 (for the top-level bindings),
272 {\em or} by @rnMonoBinds@ (for the nested ones).
275 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
277 -> RnMS (RenamedHsBinds, --
278 FreeVars) -- Free variables
280 rn_mono_binds siglist mbinds
282 -- Rename the bindings, returning a MonoBindsInfo
283 -- which is a list of indivisible vertices so far as
284 -- the strongly-connected-components (SCC) analysis is concerned
285 flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->
287 -- Do the SCC analysis
289 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
290 scc_result = stronglyConnComp edges
291 final_binds = foldr1 ThenBinds (map reconstructCycle scc_result)
293 -- Deal with bound and free-var calculation
294 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
296 returnRn (final_binds, rhs_fvs)
299 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
300 unique ``vertex tags'' on its output; minor plumbing required.
302 Sigh --- need to pass along the signatures for the group of bindings,
303 in case any of them \fbox{\ ???\ }
306 flattenMonoBinds :: [RenamedSig] -- Signatures
308 -> RnMS [FlatMonoBindsInfo]
310 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
312 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
313 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
314 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
315 returnRn (flat1 ++ flat2)
317 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
318 = pushSrcLocRn locn $
319 rnPat pat `thenRn` \ (pat', pat_fvs) ->
321 -- Find which things are bound in this group
323 names_bound_here = mkNameSet (collectPatBinders pat')
325 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
326 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
329 fvs `plusFV` pat_fvs,
330 PatMonoBind pat' grhss' locn,
334 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
335 = pushSrcLocRn locn $
336 lookupBndrRn name `thenRn` \ new_name ->
338 names_bound_here = unitNameSet new_name
340 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
341 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
342 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
344 [(unitNameSet new_name,
346 FunMonoBind new_name inf new_matches locn,
351 sigsForMe names_bound_here sigs
352 = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
354 check sigs sig = case filter (eqHsSig sig) sigs of
355 [] -> returnRn (sig:sigs)
356 other -> dupSigDeclErr sig `thenRn_`
361 @rnMethodBinds@ is used for the method bindings of a class and an instance
362 declaration. Like @rnMonoBinds@ but without dependency analysis.
364 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
365 That's crucial when dealing with an instance decl:
367 instance Foo (T a) where
370 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
371 and unless @op@ occurs we won't treat the type signature of @op@ in the class
372 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
373 in many ways the @op@ in an instance decl is just like an occurrence, not
377 rnMethodBinds :: RdrNameMonoBinds -> RnMS (RenamedMonoBinds, FreeVars)
379 rnMethodBinds EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
381 rnMethodBinds (AndMonoBinds mb1 mb2)
382 = rnMethodBinds mb1 `thenRn` \ (mb1', fvs1) ->
383 rnMethodBinds mb2 `thenRn` \ (mb2', fvs2) ->
384 returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
386 rnMethodBinds (FunMonoBind name inf matches locn)
387 = pushSrcLocRn locn $
389 lookupGlobalOccRn name `thenRn` \ sel_name ->
390 -- We use the selector name as the binder
392 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
393 mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`
394 returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
396 -- Can't handle method pattern-bindings which bind multiple methods.
397 rnMethodBinds mbind@(PatMonoBind other_pat _ locn)
398 = pushSrcLocRn locn $
399 failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
403 %************************************************************************
405 \subsection[reconstruct-deps]{Reconstructing dependencies}
407 %************************************************************************
409 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
410 as the two cases are similar.
413 reconstructCycle :: SCC FlatMonoBindsInfo
416 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
417 = MonoBind binds sigs NonRecursive
419 reconstructCycle (CyclicSCC cycle)
420 = MonoBind this_gp_binds this_gp_sigs Recursive
422 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
423 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
426 %************************************************************************
428 \subsubsection{ Manipulating FlatMonoBindInfo}
430 %************************************************************************
432 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
433 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
434 a function binding, and has itself been dependency-analysed and
438 type FlatMonoBindsInfo
439 = (NameSet, -- Set of names defined in this vertex
440 NameSet, -- Set of names used in this vertex
442 [RenamedSig]) -- Signatures, if any, for this vertex
444 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
447 = [ (info, tag, dest_vertices (nameSetToList names_used))
448 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
451 -- An edge (v,v') indicates that v depends on v'
452 dest_vertices src_mentions = [ target_vertex
453 | ((names_defined, _, _, _), target_vertex) <- flat_info,
454 mentioned_name <- src_mentions,
455 mentioned_name `elemNameSet` names_defined
460 %************************************************************************
462 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
464 %************************************************************************
466 @renameSigs@ checks for:
468 \item more than one sig for one thing;
469 \item signatures given for things not bound here;
470 \item with suitably flaggery, that all top-level things have type signatures.
473 At the moment we don't gather free-var info from the types in
474 signatures. We'd only need this if we wanted to report unused tyvars.
477 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
479 -> RnMS ([RenamedSig], FreeVars)
481 renameSigs ok_sig [] = returnRn ([], emptyFVs) -- Common shortcut
483 renameSigs ok_sig sigs
484 = -- Rename the signatures
485 mapFvRn renameSig sigs `thenRn` \ (sigs', fvs) ->
487 -- Check for (a) duplicate signatures
488 -- (b) signatures for things not in this group
490 in_scope = filter is_in_scope sigs'
491 is_in_scope sig = case sigName sig of
492 Just n -> not (isUnboundName n)
494 (goods, bads) = partition ok_sig in_scope
496 mapRn_ unknownSigErr bads `thenRn_`
497 returnRn (goods, fvs)
499 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
500 -- because this won't work for:
501 -- instance Foo T where
504 -- We'll just rename the INLINE prag to refer to whatever other 'op'
505 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
506 -- Doesn't seem worth much trouble to sort this.
508 renameSig :: Sig RdrName -> RnMS (Sig Name, FreeVars)
510 renameSig (Sig v ty src_loc)
511 = pushSrcLocRn src_loc $
512 lookupSigOccRn v `thenRn` \ new_v ->
513 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
514 returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)
516 renameSig (SpecInstSig ty src_loc)
517 = pushSrcLocRn src_loc $
518 rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->
519 returnRn (SpecInstSig new_ty src_loc, fvs)
521 renameSig (SpecSig v ty src_loc)
522 = pushSrcLocRn src_loc $
523 lookupSigOccRn v `thenRn` \ new_v ->
524 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
525 returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)
527 renameSig (FixSig (FixitySig v fix src_loc))
528 = pushSrcLocRn src_loc $
529 lookupSigOccRn v `thenRn` \ new_v ->
530 returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)
532 renameSig (InlineSig v p src_loc)
533 = pushSrcLocRn src_loc $
534 lookupSigOccRn v `thenRn` \ new_v ->
535 returnRn (InlineSig new_v p src_loc, unitFV new_v)
537 renameSig (NoInlineSig v p src_loc)
538 = pushSrcLocRn src_loc $
539 lookupSigOccRn v `thenRn` \ new_v ->
540 returnRn (NoInlineSig new_v p src_loc, unitFV new_v)
544 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
545 renameIE lookup_occ_nm (IEVar v)
546 = lookup_occ_nm v `thenRn` \ new_v ->
547 returnRn (IEVar new_v, unitFV new_v)
549 renameIE lookup_occ_nm (IEThingAbs v)
550 = lookup_occ_nm v `thenRn` \ new_v ->
551 returnRn (IEThingAbs new_v, unitFV new_v)
553 renameIE lookup_occ_nm (IEThingAll v)
554 = lookup_occ_nm v `thenRn` \ new_v ->
555 returnRn (IEThingAll new_v, unitFV new_v)
557 renameIE lookup_occ_nm (IEThingWith v vs)
558 = lookup_occ_nm v `thenRn` \ new_v ->
559 mapRn lookup_occ_nm vs `thenRn` \ new_vs ->
560 returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
562 renameIE lookup_occ_nm (IEModuleContents m)
563 = returnRn (IEModuleContents m, emptyFVs)
567 %************************************************************************
569 \subsection{Error messages}
571 %************************************************************************
576 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
579 (what_it_is, loc) = hsSigDoc sig
583 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
586 (what_it_is, loc) = hsSigDoc sig
589 = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]
592 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))