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, renameSigsFVs,
19 #include "HsVersions.h"
23 import HsBinds ( eqHsSig, sigName, hsSigDoc )
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,
33 import CmdLineOpts ( DynFlag(..) )
34 import Digraph ( stronglyConnComp, SCC(..) )
35 import Name ( Name, nameOccName, nameSrcLoc )
37 import RdrName ( RdrName, rdrNameOcc )
38 import BasicTypes ( RecFlag(..) )
39 import List ( partition )
41 import PrelNames ( isUnboundName )
44 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
45 -- place and can be used when complaining.
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
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.
63 ToDo: deal with case where a single monobinds binds the same variable
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).
74 %************************************************************************
76 %* naming conventions *
78 %************************************************************************
80 \subsection[name-conventions]{Name conventions}
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.
89 Conventions for variable names are as follows:
92 new code is given a prime to distinguish it from the old.
95 a set of variables defined in @Exp@ is written @dvExp@
98 a set of variables free in @Exp@ is written @fvExp@
101 %************************************************************************
103 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
105 %************************************************************************
107 \subsubsection[dep-HsBinds]{Polymorphic bindings}
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.
114 Monomorphic bindings contain information that is returned in a tuple
115 (a @FlatMonoBindsInfo@) containing:
119 a unique @Int@ that serves as the ``vertex tag'' for this binding.
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.
126 the free variables of the body. These are referred to as @fvBody@.
129 the definition's actual code. This is referred to as just @code@.
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.
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.
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).
147 %************************************************************************
149 \subsubsection{ Top-level bindings}
151 %************************************************************************
153 @rnTopBinds@ assumes that the environment already
154 contains bindings for the binders of this particular binding.
157 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
159 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
160 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
161 -- The parser doesn't produce other forms
164 rnTopMonoBinds mbinds sigs
165 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
167 bndr_name_set = mkNameSet binder_names
169 renameSigsFVs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
171 ifOptRn Opt_WarnMissingSigs (
173 type_sig_vars = [n | Sig n _ _ <- siglist]
174 un_sigd_binders = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
176 mapRn_ missingSigWarn un_sigd_binders
179 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
180 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
182 binder_rdr_names = collectMonoBinders mbinds
185 %************************************************************************
189 %************************************************************************
191 \subsubsection{Nested binds}
195 \item collects up the binders for this declaration group,
196 \item checks that they form a set
197 \item extends the environment to bind them to new local names
198 \item calls @rnMonoBinds@ to do the real work
202 rnBinds :: RdrNameHsBinds
203 -> (RenamedHsBinds -> RnMS (result, FreeVars))
204 -> RnMS (result, FreeVars)
206 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
207 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
208 -- the parser doesn't produce other forms
211 rnMonoBinds :: RdrNameMonoBinds
213 -> (RenamedHsBinds -> RnMS (result, FreeVars))
214 -> RnMS (result, FreeVars)
216 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
217 = -- Extract all the binders in this group,
218 -- and extend current scope, inventing new names for the new binders
219 -- This also checks that the names form a set
220 bindLocatedLocalsRn doc mbinders_w_srclocs $ \ new_mbinders ->
221 bindPatSigTyVars (collectSigTysFromMonoBinds mbinds) $
223 binder_set = mkNameSet new_mbinders
225 -- Rename the signatures
226 renameSigsFVs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
228 -- Report the fixity declarations in this group that
229 -- don't refer to any of the group's binders.
230 -- Then install the fixity declarations that do apply here
231 -- Notice that they scope over thing_inside too
233 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
235 extendFixityEnv fixity_sigs $
237 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
239 -- Now do the "thing inside", and deal with the free-variable calculations
240 thing_inside binds `thenRn` \ (result,result_fvs) ->
242 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
243 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
245 warnUnusedLocalBinds unused_binders `thenRn_`
246 returnRn (result, delListFromNameSet all_fvs new_mbinders)
248 mbinders_w_srclocs = collectLocatedMonoBinders mbinds
249 doc = text "In the binding group for" <+> pp_bndrs mbinders_w_srclocs
250 pp_bndrs [(b,_)] = quotes (ppr b)
251 pp_bndrs bs = fsep (punctuate comma [ppr b | (b,_) <- bs])
255 %************************************************************************
257 \subsubsection{ MonoBinds -- the main work is done here}
259 %************************************************************************
261 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
262 It assumes that all variables bound in this group are already in scope.
263 This is done {\em either} by pass 3 (for the top-level bindings),
264 {\em or} by @rnMonoBinds@ (for the nested ones).
267 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
269 -> RnMS (RenamedHsBinds, -- Dependency analysed
270 FreeVars) -- Free variables
272 rn_mono_binds siglist mbinds
274 -- Rename the bindings, returning a MonoBindsInfo
275 -- which is a list of indivisible vertices so far as
276 -- the strongly-connected-components (SCC) analysis is concerned
277 flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->
279 -- Do the SCC analysis
281 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
282 scc_result = stronglyConnComp edges
283 final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
285 -- Deal with bound and free-var calculation
286 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
288 returnRn (final_binds, rhs_fvs)
291 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
292 unique ``vertex tags'' on its output; minor plumbing required.
294 Sigh --- need to pass along the signatures for the group of bindings,
295 in case any of them \fbox{\ ???\ }
298 flattenMonoBinds :: [RenamedSig] -- Signatures
300 -> RnMS [FlatMonoBindsInfo]
302 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
304 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
305 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
306 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
307 returnRn (flat1 ++ flat2)
309 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
310 = pushSrcLocRn locn $
311 rnPat pat `thenRn` \ (pat', pat_fvs) ->
313 -- Find which things are bound in this group
315 names_bound_here = mkNameSet (collectPatBinders pat')
317 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
318 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
321 fvs `plusFV` pat_fvs,
322 PatMonoBind pat' grhss' locn,
326 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
327 = pushSrcLocRn locn $
328 lookupBndrRn name `thenRn` \ new_name ->
330 names_bound_here = unitNameSet new_name
332 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
333 mapFvRn (rnMatch (FunRhs name)) matches `thenRn` \ (new_matches, fvs) ->
334 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
336 [(unitNameSet new_name,
338 FunMonoBind new_name inf new_matches locn,
343 sigsForMe names_bound_here sigs
344 = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
346 check sigs sig = case filter (eqHsSig sig) sigs of
347 [] -> returnRn (sig:sigs)
348 other -> dupSigDeclErr sig `thenRn_`
353 @rnMethodBinds@ is used for the method bindings of a class and an instance
354 declaration. Like @rnMonoBinds@ but without dependency analysis.
356 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
357 That's crucial when dealing with an instance decl:
359 instance Foo (T a) where
362 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
363 and unless @op@ occurs we won't treat the type signature of @op@ in the class
364 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
365 in many ways the @op@ in an instance decl is just like an occurrence, not
369 rnMethodBinds :: [Name] -- Names for generic type variables
371 -> RnMS (RenamedMonoBinds, FreeVars)
373 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
375 rnMethodBinds gen_tyvars (AndMonoBinds mb1 mb2)
376 = rnMethodBinds gen_tyvars mb1 `thenRn` \ (mb1', fvs1) ->
377 rnMethodBinds gen_tyvars mb2 `thenRn` \ (mb2', fvs2) ->
378 returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
380 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
381 = pushSrcLocRn locn $
383 lookupGlobalOccRn name `thenRn` \ sel_name ->
384 -- We use the selector name as the binder
386 mapFvRn rn_match matches `thenRn` \ (new_matches, fvs) ->
387 mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`
388 returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
390 -- Gruesome; bring into scope the correct members of the generic type variables
391 -- See comments in RnSource.rnSourceDecl(ClassDecl)
392 rn_match match@(Match (TypePatIn ty : _) _ _)
393 = extendTyVarEnvFVRn gen_tvs (rnMatch (FunRhs name) match)
395 tvs = map rdrNameOcc (extractHsTyRdrNames ty)
396 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
398 rn_match match = rnMatch (FunRhs name) match
401 -- Can't handle method pattern-bindings which bind multiple methods.
402 rnMethodBinds gen_tyvars mbind@(PatMonoBind other_pat _ locn)
403 = pushSrcLocRn locn $
404 failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
408 %************************************************************************
410 \subsection[reconstruct-deps]{Reconstructing dependencies}
412 %************************************************************************
414 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
415 as the two cases are similar.
418 reconstructCycle :: SCC FlatMonoBindsInfo
421 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
422 = MonoBind binds sigs NonRecursive
424 reconstructCycle (CyclicSCC cycle)
425 = MonoBind this_gp_binds this_gp_sigs Recursive
427 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
428 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
431 %************************************************************************
433 \subsubsection{ Manipulating FlatMonoBindInfo}
435 %************************************************************************
437 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
438 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
439 a function binding, and has itself been dependency-analysed and
443 type FlatMonoBindsInfo
444 = (NameSet, -- Set of names defined in this vertex
445 NameSet, -- Set of names used in this vertex
447 [RenamedSig]) -- Signatures, if any, for this vertex
449 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
452 = [ (info, tag, dest_vertices (nameSetToList names_used))
453 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
456 -- An edge (v,v') indicates that v depends on v'
457 dest_vertices src_mentions = [ target_vertex
458 | ((names_defined, _, _, _), target_vertex) <- flat_info,
459 mentioned_name <- src_mentions,
460 mentioned_name `elemNameSet` names_defined
465 %************************************************************************
467 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
469 %************************************************************************
471 @renameSigs@ checks for:
473 \item more than one sig for one thing;
474 \item signatures given for things not bound here;
475 \item with suitably flaggery, that all top-level things have type signatures.
478 At the moment we don't gather free-var info from the types in
479 signatures. We'd only need this if we wanted to report unused tyvars.
482 renameSigsFVs ok_sig sigs
483 = renameSigs ok_sig sigs `thenRn` \ sigs' ->
484 returnRn (sigs', hsSigsFVs sigs')
486 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
490 renameSigs ok_sig [] = returnRn []
492 renameSigs ok_sig sigs
493 = -- Rename the signatures
494 mapRn renameSig sigs `thenRn` \ sigs' ->
496 -- Check for (a) duplicate signatures
497 -- (b) signatures for things not in this group
499 in_scope = filter is_in_scope sigs'
500 is_in_scope sig = case sigName sig of
501 Just n -> not (isUnboundName n)
503 (goods, bads) = partition ok_sig in_scope
505 mapRn_ unknownSigErr bads `thenRn_`
508 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
509 -- because this won't work for:
510 -- instance Foo T where
513 -- We'll just rename the INLINE prag to refer to whatever other 'op'
514 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
515 -- Doesn't seem worth much trouble to sort this.
517 renameSig :: Sig RdrName -> RnMS (Sig Name)
518 -- ClassOpSig is renamed elsewhere.
519 renameSig (Sig v ty src_loc)
520 = pushSrcLocRn src_loc $
521 lookupSigOccRn v `thenRn` \ new_v ->
522 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
523 returnRn (Sig new_v new_ty src_loc)
525 renameSig (SpecInstSig ty src_loc)
526 = pushSrcLocRn src_loc $
527 rnHsType (text "A SPECIALISE instance pragma") ty `thenRn` \ new_ty ->
528 returnRn (SpecInstSig new_ty src_loc)
530 renameSig (SpecSig v ty src_loc)
531 = pushSrcLocRn src_loc $
532 lookupSigOccRn v `thenRn` \ new_v ->
533 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
534 returnRn (SpecSig new_v new_ty src_loc)
536 renameSig (FixSig (FixitySig v fix src_loc))
537 = pushSrcLocRn src_loc $
538 lookupSigOccRn v `thenRn` \ new_v ->
539 returnRn (FixSig (FixitySig new_v fix src_loc))
541 renameSig (InlineSig b v p src_loc)
542 = pushSrcLocRn src_loc $
543 lookupSigOccRn v `thenRn` \ new_v ->
544 returnRn (InlineSig b new_v p src_loc)
548 %************************************************************************
550 \subsection{Error messages}
552 %************************************************************************
557 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
560 (what_it_is, loc) = hsSigDoc sig
564 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
567 (what_it_is, loc) = hsSigDoc sig
570 = pushSrcLocRn (nameSrcLoc var) $
571 addWarnRn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
574 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))