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 ( opt_WarnMissingSigs )
35 import Digraph ( stronglyConnComp, SCC(..) )
36 import Name ( OccName, Name, nameOccName, mkUnboundName, isUnboundName )
38 import RdrName ( RdrName, rdrNameOcc )
39 import BasicTypes ( RecFlag(..) )
40 import List ( partition )
41 import Bag ( bagToList )
45 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
46 -- place and can be used when complaining.
48 The code tree received by the function @rnBinds@ contains definitions
49 in where-clauses which are all apparently mutually recursive, but which may
50 not really depend upon each other. For example, in the top level program
55 the definitions of @a@ and @y@ do not depend on each other at all.
56 Unfortunately, the typechecker cannot always check such definitions.
57 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
58 definitions. In Proceedings of the International Symposium on Programming,
59 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
60 However, the typechecker usually can check definitions in which only the
61 strongly connected components have been collected into recursive bindings.
62 This is precisely what the function @rnBinds@ does.
64 ToDo: deal with case where a single monobinds binds the same variable
67 The vertag tag is a unique @Int@; the tags only need to be unique
68 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
69 (heavy monad machinery not needed).
73 type Cycle = [VertexTag]
74 type Edge = (VertexTag, VertexTag)
77 %************************************************************************
79 %* naming conventions *
81 %************************************************************************
83 \subsection[name-conventions]{Name conventions}
85 The basic algorithm involves walking over the tree and returning a tuple
86 containing the new tree plus its free variables. Some functions, such
87 as those walking polymorphic bindings (HsBinds) and qualifier lists in
88 list comprehensions (@Quals@), return the variables bound in local
89 environments. These are then used to calculate the free variables of the
90 expression evaluated in these environments.
92 Conventions for variable names are as follows:
95 new code is given a prime to distinguish it from the old.
98 a set of variables defined in @Exp@ is written @dvExp@
101 a set of variables free in @Exp@ is written @fvExp@
104 %************************************************************************
106 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
108 %************************************************************************
110 \subsubsection[dep-HsBinds]{Polymorphic bindings}
112 Non-recursive expressions are reconstructed without any changes at top
113 level, although their component expressions may have to be altered.
114 However, non-recursive expressions are currently not expected as
115 \Haskell{} programs, and this code should not be executed.
117 Monomorphic bindings contain information that is returned in a tuple
118 (a @FlatMonoBindsInfo@) containing:
122 a unique @Int@ that serves as the ``vertex tag'' for this binding.
125 the name of a function or the names in a pattern. These are a set
126 referred to as @dvLhs@, the defined variables of the left hand side.
129 the free variables of the body. These are referred to as @fvBody@.
132 the definition's actual code. This is referred to as just @code@.
135 The function @nonRecDvFv@ returns two sets of variables. The first is
136 the set of variables defined in the set of monomorphic bindings, while the
137 second is the set of free variables in those bindings.
139 The set of variables defined in a non-recursive binding is just the
140 union of all of them, as @union@ removes duplicates. However, the
141 free variables in each successive set of cumulative bindings is the
142 union of those in the previous set plus those of the newest binding after
143 the defined variables of the previous set have been removed.
145 @rnMethodBinds@ deals only with the declarations in class and
146 instance declarations. It expects only to see @FunMonoBind@s, and
147 it expects the global environment to contain bindings for the binders
148 (which are all class operations).
150 %************************************************************************
152 \subsubsection{ Top-level bindings}
154 %************************************************************************
156 @rnTopBinds@ assumes that the environment already
157 contains bindings for the binders of this particular binding.
160 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
162 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
163 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
164 -- The parser doesn't produce other forms
167 rnTopMonoBinds mbinds sigs
168 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
170 bndr_name_set = mkNameSet binder_names
172 renameSigs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
174 type_sig_vars = [n | Sig n _ _ <- siglist]
175 un_sigd_binders | opt_WarnMissingSigs = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
178 mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders `thenRn_`
180 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
181 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
183 binder_rdr_names = collectMonoBinders mbinds
186 %************************************************************************
190 %************************************************************************
192 \subsubsection{Nested binds}
196 \item collects up the binders for this declaration group,
197 \item checks that they form a set
198 \item extends the environment to bind them to new local names
199 \item calls @rnMonoBinds@ to do the real work
203 rnBinds :: RdrNameHsBinds
204 -> (RenamedHsBinds -> RnMS (result, FreeVars))
205 -> RnMS (result, FreeVars)
207 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
208 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
209 -- the parser doesn't produce other forms
212 rnMonoBinds :: RdrNameMonoBinds
214 -> (RenamedHsBinds -> RnMS (result, FreeVars))
215 -> RnMS (result, FreeVars)
217 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
218 = -- Extract all the binders in this group,
219 -- and extend current scope, inventing new names for the new binders
220 -- This also checks that the names form a set
221 bindLocatedLocalsRn (text "a binding group")
222 mbinders_w_srclocs $ \ new_mbinders ->
224 binder_set = mkNameSet new_mbinders
226 -- Rename the signatures
227 renameSigs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
229 -- Report the fixity declarations in this group that
230 -- don't refer to any of the group's binders.
231 -- Then install the fixity declarations that do apply here
232 -- Notice that they scope over thing_inside too
234 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
236 extendFixityEnv fixity_sigs $
238 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
240 -- Now do the "thing inside", and deal with the free-variable calculations
241 thing_inside binds `thenRn` \ (result,result_fvs) ->
243 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
244 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
246 warnUnusedLocalBinds unused_binders `thenRn_`
247 returnRn (result, delListFromNameSet all_fvs new_mbinders)
249 mbinders_w_srclocs = collectLocatedMonoBinders mbinds
253 %************************************************************************
255 \subsubsection{ MonoBinds -- the main work is done here}
257 %************************************************************************
259 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
260 It assumes that all variables bound in this group are already in scope.
261 This is done {\em either} by pass 3 (for the top-level bindings),
262 {\em or} by @rnMonoBinds@ (for the nested ones).
265 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
267 -> RnMS (RenamedHsBinds, --
268 FreeVars) -- Free variables
270 rn_mono_binds siglist mbinds
272 -- Rename the bindings, returning a MonoBindsInfo
273 -- which is a list of indivisible vertices so far as
274 -- the strongly-connected-components (SCC) analysis is concerned
275 flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->
277 -- Do the SCC analysis
279 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
280 scc_result = stronglyConnComp edges
281 final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
283 -- Deal with bound and free-var calculation
284 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
286 returnRn (final_binds, rhs_fvs)
289 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
290 unique ``vertex tags'' on its output; minor plumbing required.
292 Sigh --- need to pass along the signatures for the group of bindings,
293 in case any of them \fbox{\ ???\ }
296 flattenMonoBinds :: [RenamedSig] -- Signatures
298 -> RnMS [FlatMonoBindsInfo]
300 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
302 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
303 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
304 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
305 returnRn (flat1 ++ flat2)
307 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
308 = pushSrcLocRn locn $
309 rnPat pat `thenRn` \ (pat', pat_fvs) ->
311 -- Find which things are bound in this group
313 names_bound_here = mkNameSet (collectPatBinders pat')
315 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
316 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
319 fvs `plusFV` pat_fvs,
320 PatMonoBind pat' grhss' locn,
324 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
325 = pushSrcLocRn locn $
326 lookupBndrRn name `thenRn` \ new_name ->
328 names_bound_here = unitNameSet new_name
330 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
331 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
332 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
334 [(unitNameSet new_name,
336 FunMonoBind new_name inf new_matches locn,
341 sigsForMe names_bound_here sigs
342 = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
344 check sigs sig = case filter (eqHsSig sig) sigs of
345 [] -> returnRn (sig:sigs)
346 other -> dupSigDeclErr sig `thenRn_`
351 @rnMethodBinds@ is used for the method bindings of a class and an instance
352 declaration. Like @rnMonoBinds@ but without dependency analysis.
354 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
355 That's crucial when dealing with an instance decl:
357 instance Foo (T a) where
360 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
361 and unless @op@ occurs we won't treat the type signature of @op@ in the class
362 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
363 in many ways the @op@ in an instance decl is just like an occurrence, not
367 rnMethodBinds :: [Name] -- Names for generic type variables
369 -> RnMS (RenamedMonoBinds, FreeVars)
371 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
373 rnMethodBinds gen_tyvars (AndMonoBinds mb1 mb2)
374 = rnMethodBinds gen_tyvars mb1 `thenRn` \ (mb1', fvs1) ->
375 rnMethodBinds gen_tyvars mb2 `thenRn` \ (mb2', fvs2) ->
376 returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
378 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
379 = pushSrcLocRn locn $
381 lookupGlobalOccRn name `thenRn` \ sel_name ->
382 -- We use the selector name as the binder
384 mapFvRn rn_match matches `thenRn` \ (new_matches, fvs) ->
385 mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`
386 returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
388 -- Gruesome; bring into scope the correct members of the generic type variables
389 -- See comments in RnSource.rnDecl(ClassDecl)
390 rn_match match@(Match _ (TypePatIn ty : _) _ _)
391 = extendTyVarEnvFVRn gen_tvs (rnMatch match)
393 tvs = map rdrNameOcc (extractHsTyRdrNames ty)
394 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
396 rn_match match = rnMatch match
399 -- Can't handle method pattern-bindings which bind multiple methods.
400 rnMethodBinds gen_tyvars mbind@(PatMonoBind other_pat _ locn)
401 = pushSrcLocRn locn $
402 failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
406 %************************************************************************
408 \subsection[reconstruct-deps]{Reconstructing dependencies}
410 %************************************************************************
412 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
413 as the two cases are similar.
416 reconstructCycle :: SCC FlatMonoBindsInfo
419 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
420 = MonoBind binds sigs NonRecursive
422 reconstructCycle (CyclicSCC cycle)
423 = MonoBind this_gp_binds this_gp_sigs Recursive
425 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
426 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
429 %************************************************************************
431 \subsubsection{ Manipulating FlatMonoBindInfo}
433 %************************************************************************
435 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
436 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
437 a function binding, and has itself been dependency-analysed and
441 type FlatMonoBindsInfo
442 = (NameSet, -- Set of names defined in this vertex
443 NameSet, -- Set of names used in this vertex
445 [RenamedSig]) -- Signatures, if any, for this vertex
447 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
450 = [ (info, tag, dest_vertices (nameSetToList names_used))
451 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
454 -- An edge (v,v') indicates that v depends on v'
455 dest_vertices src_mentions = [ target_vertex
456 | ((names_defined, _, _, _), target_vertex) <- flat_info,
457 mentioned_name <- src_mentions,
458 mentioned_name `elemNameSet` names_defined
463 %************************************************************************
465 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
467 %************************************************************************
469 @renameSigs@ checks for:
471 \item more than one sig for one thing;
472 \item signatures given for things not bound here;
473 \item with suitably flaggery, that all top-level things have type signatures.
476 At the moment we don't gather free-var info from the types in
477 signatures. We'd only need this if we wanted to report unused tyvars.
480 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
482 -> RnMS ([RenamedSig], FreeVars)
484 renameSigs ok_sig [] = returnRn ([], emptyFVs) -- Common shortcut
486 renameSigs ok_sig sigs
487 = -- Rename the signatures
488 mapFvRn renameSig sigs `thenRn` \ (sigs', fvs) ->
490 -- Check for (a) duplicate signatures
491 -- (b) signatures for things not in this group
493 in_scope = filter is_in_scope sigs'
494 is_in_scope sig = case sigName sig of
495 Just n -> not (isUnboundName n)
497 (goods, bads) = partition ok_sig in_scope
499 mapRn_ unknownSigErr bads `thenRn_`
500 returnRn (goods, fvs)
502 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
503 -- because this won't work for:
504 -- instance Foo T where
507 -- We'll just rename the INLINE prag to refer to whatever other 'op'
508 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
509 -- Doesn't seem worth much trouble to sort this.
511 renameSig :: Sig RdrName -> RnMS (Sig Name, FreeVars)
512 -- ClassOpSig is renamed elsewhere.
513 renameSig (Sig v ty src_loc)
514 = pushSrcLocRn src_loc $
515 lookupSigOccRn v `thenRn` \ new_v ->
516 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
517 returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)
519 renameSig (SpecInstSig ty src_loc)
520 = pushSrcLocRn src_loc $
521 rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->
522 returnRn (SpecInstSig new_ty src_loc, fvs)
524 renameSig (SpecSig v ty src_loc)
525 = pushSrcLocRn src_loc $
526 lookupSigOccRn v `thenRn` \ new_v ->
527 rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->
528 returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)
530 renameSig (FixSig (FixitySig v fix src_loc))
531 = pushSrcLocRn src_loc $
532 lookupSigOccRn v `thenRn` \ new_v ->
533 returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)
535 renameSig (InlineSig v p src_loc)
536 = pushSrcLocRn src_loc $
537 lookupSigOccRn v `thenRn` \ new_v ->
538 returnRn (InlineSig new_v p src_loc, unitFV new_v)
540 renameSig (NoInlineSig v p src_loc)
541 = pushSrcLocRn src_loc $
542 lookupSigOccRn v `thenRn` \ new_v ->
543 returnRn (NoInlineSig new_v p src_loc, unitFV new_v)
547 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
548 renameIE lookup_occ_nm (IEVar v)
549 = lookup_occ_nm v `thenRn` \ new_v ->
550 returnRn (IEVar new_v, unitFV new_v)
552 renameIE lookup_occ_nm (IEThingAbs v)
553 = lookup_occ_nm v `thenRn` \ new_v ->
554 returnRn (IEThingAbs new_v, unitFV new_v)
556 renameIE lookup_occ_nm (IEThingAll v)
557 = lookup_occ_nm v `thenRn` \ new_v ->
558 returnRn (IEThingAll new_v, unitFV new_v)
560 renameIE lookup_occ_nm (IEThingWith v vs)
561 = lookup_occ_nm v `thenRn` \ new_v ->
562 mapRn lookup_occ_nm vs `thenRn` \ new_vs ->
563 returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
565 renameIE lookup_occ_nm (IEModuleContents m)
566 = returnRn (IEModuleContents m, emptyFVs)
570 %************************************************************************
572 \subsection{Error messages}
574 %************************************************************************
579 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
582 (what_it_is, loc) = hsSigDoc sig
586 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
589 (what_it_is, loc) = hsSigDoc sig
592 = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]
595 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))