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, lookupSigOccRn,
31 warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
32 FreeVars, emptyFVs, plusFV, plusFVs, unitFV, addOneFV
34 import CmdLineOpts ( DynFlag(..) )
35 import Digraph ( stronglyConnComp, SCC(..) )
36 import Name ( OccName, Name, nameOccName )
38 import RdrName ( RdrName, rdrNameOcc )
39 import BasicTypes ( RecFlag(..) )
40 import List ( partition )
41 import Bag ( bagToList )
43 import PrelNames ( mkUnboundName, isUnboundName )
46 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
47 -- place and can be used when complaining.
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
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.
65 ToDo: deal with case where a single monobinds binds the same variable
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).
74 type Cycle = [VertexTag]
75 type Edge = (VertexTag, VertexTag)
78 %************************************************************************
80 %* naming conventions *
82 %************************************************************************
84 \subsection[name-conventions]{Name conventions}
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.
93 Conventions for variable names are as follows:
96 new code is given a prime to distinguish it from the old.
99 a set of variables defined in @Exp@ is written @dvExp@
102 a set of variables free in @Exp@ is written @fvExp@
105 %************************************************************************
107 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
109 %************************************************************************
111 \subsubsection[dep-HsBinds]{Polymorphic bindings}
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.
118 Monomorphic bindings contain information that is returned in a tuple
119 (a @FlatMonoBindsInfo@) containing:
123 a unique @Int@ that serves as the ``vertex tag'' for this binding.
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.
130 the free variables of the body. These are referred to as @fvBody@.
133 the definition's actual code. This is referred to as just @code@.
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.
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.
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).
151 %************************************************************************
153 \subsubsection{ Top-level bindings}
155 %************************************************************************
157 @rnTopBinds@ assumes that the environment already
158 contains bindings for the binders of this particular binding.
161 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
163 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
164 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
165 -- The parser doesn't produce other forms
168 rnTopMonoBinds mbinds sigs
169 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
171 bndr_name_set = mkNameSet binder_names
173 renameSigs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
174 doptRn Opt_WarnMissingSigs `thenRn` \ warnMissing ->
176 type_sig_vars = [n | Sig n _ _ <- siglist]
177 un_sigd_binders | warnMissing = nameSetToList (delListFromNameSet
178 bndr_name_set type_sig_vars)
181 mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders `thenRn_`
183 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
184 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
186 binder_rdr_names = collectMonoBinders mbinds
189 %************************************************************************
193 %************************************************************************
195 \subsubsection{Nested binds}
199 \item collects up the binders for this declaration group,
200 \item checks that they form a set
201 \item extends the environment to bind them to new local names
202 \item calls @rnMonoBinds@ to do the real work
206 rnBinds :: RdrNameHsBinds
207 -> (RenamedHsBinds -> RnMS (result, FreeVars))
208 -> RnMS (result, FreeVars)
210 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
211 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
212 -- the parser doesn't produce other forms
215 rnMonoBinds :: RdrNameMonoBinds
217 -> (RenamedHsBinds -> RnMS (result, FreeVars))
218 -> RnMS (result, FreeVars)
220 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
221 = -- Extract all the binders in this group,
222 -- and extend current scope, inventing new names for the new binders
223 -- This also checks that the names form a set
224 bindLocatedLocalsRn (text "a binding group")
225 mbinders_w_srclocs $ \ new_mbinders ->
227 binder_set = mkNameSet new_mbinders
229 -- Rename the signatures
230 renameSigs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
232 -- Report the fixity declarations in this group that
233 -- don't refer to any of the group's binders.
234 -- Then install the fixity declarations that do apply here
235 -- Notice that they scope over thing_inside too
237 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
239 extendFixityEnv fixity_sigs $
241 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
243 -- Now do the "thing inside", and deal with the free-variable calculations
244 thing_inside binds `thenRn` \ (result,result_fvs) ->
246 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
247 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
249 warnUnusedLocalBinds unused_binders `thenRn_`
250 returnRn (result, delListFromNameSet all_fvs new_mbinders)
252 mbinders_w_srclocs = collectLocatedMonoBinders mbinds
256 %************************************************************************
258 \subsubsection{ MonoBinds -- the main work is done here}
260 %************************************************************************
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).
268 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
270 -> RnMS (RenamedHsBinds, --
271 FreeVars) -- Free variables
273 rn_mono_binds siglist mbinds
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 ->
280 -- Do the SCC analysis
282 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
283 scc_result = stronglyConnComp edges
284 final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
286 -- Deal with bound and free-var calculation
287 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
289 returnRn (final_binds, rhs_fvs)
292 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
293 unique ``vertex tags'' on its output; minor plumbing required.
295 Sigh --- need to pass along the signatures for the group of bindings,
296 in case any of them \fbox{\ ???\ }
299 flattenMonoBinds :: [RenamedSig] -- Signatures
301 -> RnMS [FlatMonoBindsInfo]
303 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
305 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
306 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
307 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
308 returnRn (flat1 ++ flat2)
310 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
311 = pushSrcLocRn locn $
312 rnPat pat `thenRn` \ (pat', pat_fvs) ->
314 -- Find which things are bound in this group
316 names_bound_here = mkNameSet (collectPatBinders pat')
318 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
319 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
322 fvs `plusFV` pat_fvs,
323 PatMonoBind pat' grhss' locn,
327 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
328 = pushSrcLocRn locn $
329 lookupBndrRn name `thenRn` \ new_name ->
331 names_bound_here = unitNameSet new_name
333 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
334 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
335 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
337 [(unitNameSet new_name,
339 FunMonoBind new_name inf new_matches locn,
344 sigsForMe names_bound_here sigs
345 = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
347 check sigs sig = case filter (eqHsSig sig) sigs of
348 [] -> returnRn (sig:sigs)
349 other -> dupSigDeclErr sig `thenRn_`
354 @rnMethodBinds@ is used for the method bindings of a class and an instance
355 declaration. Like @rnMonoBinds@ but without dependency analysis.
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:
360 instance Foo (T a) where
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
370 rnMethodBinds :: [Name] -- Names for generic type variables
372 -> RnMS (RenamedMonoBinds, FreeVars)
374 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
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)
381 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
382 = pushSrcLocRn locn $
384 lookupGlobalOccRn name `thenRn` \ sel_name ->
385 -- We use the selector name as the binder
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)
391 -- Gruesome; bring into scope the correct members of the generic type variables
392 -- See comments in RnSource.rnDecl(ClassDecl)
393 rn_match match@(Match _ (TypePatIn ty : _) _ _)
394 = extendTyVarEnvFVRn gen_tvs (rnMatch match)
396 tvs = map rdrNameOcc (extractHsTyRdrNames ty)
397 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
399 rn_match match = rnMatch match
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)
409 %************************************************************************
411 \subsection[reconstruct-deps]{Reconstructing dependencies}
413 %************************************************************************
415 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
416 as the two cases are similar.
419 reconstructCycle :: SCC FlatMonoBindsInfo
422 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
423 = MonoBind binds sigs NonRecursive
425 reconstructCycle (CyclicSCC cycle)
426 = MonoBind this_gp_binds this_gp_sigs Recursive
428 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
429 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
432 %************************************************************************
434 \subsubsection{ Manipulating FlatMonoBindInfo}
436 %************************************************************************
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
444 type FlatMonoBindsInfo
445 = (NameSet, -- Set of names defined in this vertex
446 NameSet, -- Set of names used in this vertex
448 [RenamedSig]) -- Signatures, if any, for this vertex
450 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
453 = [ (info, tag, dest_vertices (nameSetToList names_used))
454 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
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
466 %************************************************************************
468 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
470 %************************************************************************
472 @renameSigs@ checks for:
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.
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.
483 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
485 -> RnMS ([RenamedSig], FreeVars)
487 renameSigs ok_sig [] = returnRn ([], emptyFVs) -- Common shortcut
489 renameSigs ok_sig sigs
490 = -- Rename the signatures
491 mapFvRn renameSig sigs `thenRn` \ (sigs', fvs) ->
493 -- Check for (a) duplicate signatures
494 -- (b) signatures for things not in this group
496 in_scope = filter is_in_scope sigs'
497 is_in_scope sig = case sigName sig of
498 Just n -> not (isUnboundName n)
500 (goods, bads) = partition ok_sig in_scope
502 mapRn_ unknownSigErr bads `thenRn_`
503 returnRn (goods, fvs)
505 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
506 -- because this won't work for:
507 -- instance Foo T where
510 -- We'll just rename the INLINE prag to refer to whatever other 'op'
511 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
512 -- Doesn't seem worth much trouble to sort this.
514 renameSig :: Sig RdrName -> RnMS (Sig Name, FreeVars)
515 -- ClassOpSig is renamed elsewhere.
516 renameSig (Sig v ty src_loc)
517 = pushSrcLocRn src_loc $
518 lookupSigOccRn v `thenRn` \ new_v ->
519 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
520 returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)
522 renameSig (SpecInstSig ty src_loc)
523 = pushSrcLocRn src_loc $
524 rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->
525 returnRn (SpecInstSig new_ty src_loc, fvs)
527 renameSig (SpecSig v ty src_loc)
528 = pushSrcLocRn src_loc $
529 lookupSigOccRn v `thenRn` \ new_v ->
530 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
531 returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)
533 renameSig (FixSig (FixitySig v fix src_loc))
534 = pushSrcLocRn src_loc $
535 lookupSigOccRn v `thenRn` \ new_v ->
536 returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)
538 renameSig (InlineSig v p src_loc)
539 = pushSrcLocRn src_loc $
540 lookupSigOccRn v `thenRn` \ new_v ->
541 returnRn (InlineSig new_v p src_loc, unitFV new_v)
543 renameSig (NoInlineSig v p src_loc)
544 = pushSrcLocRn src_loc $
545 lookupSigOccRn v `thenRn` \ new_v ->
546 returnRn (NoInlineSig new_v p src_loc, unitFV new_v)
550 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
551 renameIE lookup_occ_nm (IEVar v)
552 = lookup_occ_nm v `thenRn` \ new_v ->
553 returnRn (IEVar new_v, unitFV new_v)
555 renameIE lookup_occ_nm (IEThingAbs v)
556 = lookup_occ_nm v `thenRn` \ new_v ->
557 returnRn (IEThingAbs new_v, unitFV new_v)
559 renameIE lookup_occ_nm (IEThingAll v)
560 = lookup_occ_nm v `thenRn` \ new_v ->
561 returnRn (IEThingAll new_v, unitFV new_v)
563 renameIE lookup_occ_nm (IEThingWith v vs)
564 = lookup_occ_nm v `thenRn` \ new_v ->
565 mapRn lookup_occ_nm vs `thenRn` \ new_vs ->
566 returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
568 renameIE lookup_occ_nm (IEModuleContents m)
569 = returnRn (IEModuleContents m, emptyFVs)
573 %************************************************************************
575 \subsection{Error messages}
577 %************************************************************************
582 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
585 (what_it_is, loc) = hsSigDoc sig
589 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
592 (what_it_is, loc) = hsSigDoc sig
595 = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]
598 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))