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"
21 import {-# SOURCE #-} RnSource ( rnHsSigType, rnHsType )
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,
33 import CmdLineOpts ( DynFlag(..) )
34 import Digraph ( stronglyConnComp, SCC(..) )
35 import Name ( OccName, 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).
72 type Cycle = [VertexTag]
73 type Edge = (VertexTag, VertexTag)
76 %************************************************************************
78 %* naming conventions *
80 %************************************************************************
82 \subsection[name-conventions]{Name conventions}
84 The basic algorithm involves walking over the tree and returning a tuple
85 containing the new tree plus its free variables. Some functions, such
86 as those walking polymorphic bindings (HsBinds) and qualifier lists in
87 list comprehensions (@Quals@), return the variables bound in local
88 environments. These are then used to calculate the free variables of the
89 expression evaluated in these environments.
91 Conventions for variable names are as follows:
94 new code is given a prime to distinguish it from the old.
97 a set of variables defined in @Exp@ is written @dvExp@
100 a set of variables free in @Exp@ is written @fvExp@
103 %************************************************************************
105 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
107 %************************************************************************
109 \subsubsection[dep-HsBinds]{Polymorphic bindings}
111 Non-recursive expressions are reconstructed without any changes at top
112 level, although their component expressions may have to be altered.
113 However, non-recursive expressions are currently not expected as
114 \Haskell{} programs, and this code should not be executed.
116 Monomorphic bindings contain information that is returned in a tuple
117 (a @FlatMonoBindsInfo@) containing:
121 a unique @Int@ that serves as the ``vertex tag'' for this binding.
124 the name of a function or the names in a pattern. These are a set
125 referred to as @dvLhs@, the defined variables of the left hand side.
128 the free variables of the body. These are referred to as @fvBody@.
131 the definition's actual code. This is referred to as just @code@.
134 The function @nonRecDvFv@ returns two sets of variables. The first is
135 the set of variables defined in the set of monomorphic bindings, while the
136 second is the set of free variables in those bindings.
138 The set of variables defined in a non-recursive binding is just the
139 union of all of them, as @union@ removes duplicates. However, the
140 free variables in each successive set of cumulative bindings is the
141 union of those in the previous set plus those of the newest binding after
142 the defined variables of the previous set have been removed.
144 @rnMethodBinds@ deals only with the declarations in class and
145 instance declarations. It expects only to see @FunMonoBind@s, and
146 it expects the global environment to contain bindings for the binders
147 (which are all class operations).
149 %************************************************************************
151 \subsubsection{ Top-level bindings}
153 %************************************************************************
155 @rnTopBinds@ assumes that the environment already
156 contains bindings for the binders of this particular binding.
159 rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)
161 rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)
162 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
163 -- The parser doesn't produce other forms
166 rnTopMonoBinds mbinds sigs
167 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
169 bndr_name_set = mkNameSet binder_names
171 renameSigsFVs (okBindSig bndr_name_set) sigs `thenRn` \ (siglist, sig_fvs) ->
172 doptRn Opt_WarnMissingSigs `thenRn` \ warnMissing ->
174 type_sig_vars = [n | Sig n _ _ <- siglist]
175 un_sigd_binders | warnMissing = nameSetToList (delListFromNameSet
176 bndr_name_set type_sig_vars)
179 mapRn_ missingSigWarn un_sigd_binders `thenRn_`
181 rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->
182 returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
184 binder_rdr_names = collectMonoBinders mbinds
187 %************************************************************************
191 %************************************************************************
193 \subsubsection{Nested binds}
197 \item collects up the binders for this declaration group,
198 \item checks that they form a set
199 \item extends the environment to bind them to new local names
200 \item calls @rnMonoBinds@ to do the real work
204 rnBinds :: RdrNameHsBinds
205 -> (RenamedHsBinds -> RnMS (result, FreeVars))
206 -> RnMS (result, FreeVars)
208 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
209 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
210 -- the parser doesn't produce other forms
213 rnMonoBinds :: RdrNameMonoBinds
215 -> (RenamedHsBinds -> RnMS (result, FreeVars))
216 -> RnMS (result, FreeVars)
218 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
219 = -- Extract all the binders in this group,
220 -- and extend current scope, inventing new names for the new binders
221 -- This also checks that the names form a set
222 bindLocatedLocalsRn (text "a binding group")
223 mbinders_w_srclocs $ \ new_mbinders ->
225 binder_set = mkNameSet new_mbinders
227 -- Rename the signatures
228 renameSigsFVs (okBindSig binder_set) sigs `thenRn` \ (siglist, sig_fvs) ->
230 -- Report the fixity declarations in this group that
231 -- don't refer to any of the group's binders.
232 -- Then install the fixity declarations that do apply here
233 -- Notice that they scope over thing_inside too
235 fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
237 extendFixityEnv fixity_sigs $
239 rn_mono_binds siglist mbinds `thenRn` \ (binds, bind_fvs) ->
241 -- Now do the "thing inside", and deal with the free-variable calculations
242 thing_inside binds `thenRn` \ (result,result_fvs) ->
244 all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
245 unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
247 warnUnusedLocalBinds unused_binders `thenRn_`
248 returnRn (result, delListFromNameSet all_fvs new_mbinders)
250 mbinders_w_srclocs = collectLocatedMonoBinders mbinds
254 %************************************************************************
256 \subsubsection{ MonoBinds -- the main work is done here}
258 %************************************************************************
260 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
261 It assumes that all variables bound in this group are already in scope.
262 This is done {\em either} by pass 3 (for the top-level bindings),
263 {\em or} by @rnMonoBinds@ (for the nested ones).
266 rn_mono_binds :: [RenamedSig] -- Signatures attached to this group
268 -> RnMS (RenamedHsBinds, --
269 FreeVars) -- Free variables
271 rn_mono_binds siglist mbinds
273 -- Rename the bindings, returning a MonoBindsInfo
274 -- which is a list of indivisible vertices so far as
275 -- the strongly-connected-components (SCC) analysis is concerned
276 flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->
278 -- Do the SCC analysis
280 edges = mkEdges (mbinds_info `zip` [(0::Int)..])
281 scc_result = stronglyConnComp edges
282 final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
284 -- Deal with bound and free-var calculation
285 rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
287 returnRn (final_binds, rhs_fvs)
290 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
291 unique ``vertex tags'' on its output; minor plumbing required.
293 Sigh --- need to pass along the signatures for the group of bindings,
294 in case any of them \fbox{\ ???\ }
297 flattenMonoBinds :: [RenamedSig] -- Signatures
299 -> RnMS [FlatMonoBindsInfo]
301 flattenMonoBinds sigs EmptyMonoBinds = returnRn []
303 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
304 = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->
305 flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->
306 returnRn (flat1 ++ flat2)
308 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
309 = pushSrcLocRn locn $
310 rnPat pat `thenRn` \ (pat', pat_fvs) ->
312 -- Find which things are bound in this group
314 names_bound_here = mkNameSet (collectPatBinders pat')
316 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
317 rnGRHSs grhss `thenRn` \ (grhss', fvs) ->
320 fvs `plusFV` pat_fvs,
321 PatMonoBind pat' grhss' locn,
325 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
326 = pushSrcLocRn locn $
327 lookupBndrRn name `thenRn` \ new_name ->
329 names_bound_here = unitNameSet new_name
331 sigsForMe names_bound_here sigs `thenRn` \ sigs_for_me ->
332 mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->
333 mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`
335 [(unitNameSet new_name,
337 FunMonoBind new_name inf new_matches locn,
342 sigsForMe names_bound_here sigs
343 = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
345 check sigs sig = case filter (eqHsSig sig) sigs of
346 [] -> returnRn (sig:sigs)
347 other -> dupSigDeclErr sig `thenRn_`
352 @rnMethodBinds@ is used for the method bindings of a class and an instance
353 declaration. Like @rnMonoBinds@ but without dependency analysis.
355 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
356 That's crucial when dealing with an instance decl:
358 instance Foo (T a) where
361 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
362 and unless @op@ occurs we won't treat the type signature of @op@ in the class
363 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
364 in many ways the @op@ in an instance decl is just like an occurrence, not
368 rnMethodBinds :: [Name] -- Names for generic type variables
370 -> RnMS (RenamedMonoBinds, FreeVars)
372 rnMethodBinds gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
374 rnMethodBinds gen_tyvars (AndMonoBinds mb1 mb2)
375 = rnMethodBinds gen_tyvars mb1 `thenRn` \ (mb1', fvs1) ->
376 rnMethodBinds gen_tyvars mb2 `thenRn` \ (mb2', fvs2) ->
377 returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
379 rnMethodBinds gen_tyvars (FunMonoBind name inf matches locn)
380 = pushSrcLocRn locn $
382 lookupGlobalOccRn name `thenRn` \ sel_name ->
383 -- We use the selector name as the binder
385 mapFvRn rn_match matches `thenRn` \ (new_matches, fvs) ->
386 mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`
387 returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
389 -- Gruesome; bring into scope the correct members of the generic type variables
390 -- See comments in RnSource.rnDecl(ClassDecl)
391 rn_match match@(Match _ (TypePatIn ty : _) _ _)
392 = extendTyVarEnvFVRn gen_tvs (rnMatch match)
394 tvs = map rdrNameOcc (extractHsTyRdrNames ty)
395 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
397 rn_match match = rnMatch match
400 -- Can't handle method pattern-bindings which bind multiple methods.
401 rnMethodBinds gen_tyvars mbind@(PatMonoBind other_pat _ locn)
402 = pushSrcLocRn locn $
403 failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
407 %************************************************************************
409 \subsection[reconstruct-deps]{Reconstructing dependencies}
411 %************************************************************************
413 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
414 as the two cases are similar.
417 reconstructCycle :: SCC FlatMonoBindsInfo
420 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
421 = MonoBind binds sigs NonRecursive
423 reconstructCycle (CyclicSCC cycle)
424 = MonoBind this_gp_binds this_gp_sigs Recursive
426 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
427 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]
430 %************************************************************************
432 \subsubsection{ Manipulating FlatMonoBindInfo}
434 %************************************************************************
436 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
437 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
438 a function binding, and has itself been dependency-analysed and
442 type FlatMonoBindsInfo
443 = (NameSet, -- Set of names defined in this vertex
444 NameSet, -- Set of names used in this vertex
446 [RenamedSig]) -- Signatures, if any, for this vertex
448 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
451 = [ (info, tag, dest_vertices (nameSetToList names_used))
452 | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
455 -- An edge (v,v') indicates that v depends on v'
456 dest_vertices src_mentions = [ target_vertex
457 | ((names_defined, _, _, _), target_vertex) <- flat_info,
458 mentioned_name <- src_mentions,
459 mentioned_name `elemNameSet` names_defined
464 %************************************************************************
466 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
468 %************************************************************************
470 @renameSigs@ checks for:
472 \item more than one sig for one thing;
473 \item signatures given for things not bound here;
474 \item with suitably flaggery, that all top-level things have type signatures.
477 At the moment we don't gather free-var info from the types in
478 signatures. We'd only need this if we wanted to report unused tyvars.
481 renameSigsFVs ok_sig sigs
482 = renameSigs ok_sig sigs `thenRn` \ sigs' ->
483 returnRn (sigs', hsSigsFVs sigs')
485 renameSigs :: (RenamedSig -> Bool) -- OK-sig predicate
489 renameSigs ok_sig [] = returnRn []
491 renameSigs ok_sig sigs
492 = -- Rename the signatures
493 mapRn renameSig sigs `thenRn` \ sigs' ->
495 -- Check for (a) duplicate signatures
496 -- (b) signatures for things not in this group
498 in_scope = filter is_in_scope sigs'
499 is_in_scope sig = case sigName sig of
500 Just n -> not (isUnboundName n)
502 (goods, bads) = partition ok_sig in_scope
504 mapRn_ unknownSigErr bads `thenRn_`
507 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
508 -- because this won't work for:
509 -- instance Foo T where
512 -- We'll just rename the INLINE prag to refer to whatever other 'op'
513 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
514 -- Doesn't seem worth much trouble to sort this.
516 renameSig :: Sig RdrName -> RnMS (Sig Name)
517 -- ClassOpSig is renamed elsewhere.
518 renameSig (Sig v ty src_loc)
519 = pushSrcLocRn src_loc $
520 lookupSigOccRn v `thenRn` \ new_v ->
521 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
522 returnRn (Sig new_v new_ty src_loc)
524 renameSig (SpecInstSig ty src_loc)
525 = pushSrcLocRn src_loc $
526 rnHsType (text "A SPECIALISE instance pragma") ty `thenRn` \ new_ty ->
527 returnRn (SpecInstSig new_ty src_loc)
529 renameSig (SpecSig v ty src_loc)
530 = pushSrcLocRn src_loc $
531 lookupSigOccRn v `thenRn` \ new_v ->
532 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
533 returnRn (SpecSig new_v new_ty src_loc)
535 renameSig (FixSig (FixitySig v fix src_loc))
536 = pushSrcLocRn src_loc $
537 lookupSigOccRn v `thenRn` \ new_v ->
538 returnRn (FixSig (FixitySig new_v fix src_loc))
540 renameSig (InlineSig v p src_loc)
541 = pushSrcLocRn src_loc $
542 lookupSigOccRn v `thenRn` \ new_v ->
543 returnRn (InlineSig new_v p src_loc)
545 renameSig (NoInlineSig v p src_loc)
546 = pushSrcLocRn src_loc $
547 lookupSigOccRn v `thenRn` \ new_v ->
548 returnRn (NoInlineSig new_v p src_loc)
552 renameIE :: (RdrName -> RnMS Name) -> IE RdrName -> RnMS (IE Name, FreeVars)
553 renameIE lookup_occ_nm (IEVar v)
554 = lookup_occ_nm v `thenRn` \ new_v ->
555 returnRn (IEVar new_v, unitFV new_v)
557 renameIE lookup_occ_nm (IEThingAbs v)
558 = lookup_occ_nm v `thenRn` \ new_v ->
559 returnRn (IEThingAbs new_v, unitFV new_v)
561 renameIE lookup_occ_nm (IEThingAll v)
562 = lookup_occ_nm v `thenRn` \ new_v ->
563 returnRn (IEThingAll new_v, unitFV new_v)
565 renameIE lookup_occ_nm (IEThingWith v vs)
566 = lookup_occ_nm v `thenRn` \ new_v ->
567 mapRn lookup_occ_nm vs `thenRn` \ new_vs ->
568 returnRn (IEThingWith new_v new_vs, plusFVs [ unitFV x | x <- new_v:new_vs ])
570 renameIE lookup_occ_nm (IEModuleContents m)
571 = returnRn (IEModuleContents m, emptyFVs)
575 %************************************************************************
577 \subsection{Error messages}
579 %************************************************************************
584 addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
587 (what_it_is, loc) = hsSigDoc sig
591 addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
594 (what_it_is, loc) = hsSigDoc sig
597 = pushSrcLocRn (nameSrcLoc var) $
598 addWarnRn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
601 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))