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, rnBinds, rnBindsAndThen,
14 rnMethodBinds, renameSigs, checkSigs
17 #include "HsVersions.h"
21 import HsBinds ( hsSigDoc, eqHsSig )
25 import RnTypes ( rnHsSigType, rnLHsType, rnLPat )
26 import RnExpr ( rnMatch, rnGRHSs, checkPrecMatch )
27 import RnEnv ( bindLocatedLocalsRn, lookupLocatedBndrRn,
28 lookupLocatedInstDeclBndr,
29 lookupLocatedSigOccRn, bindPatSigTyVars, bindPatSigTyVarsFV,
31 warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
33 import CmdLineOpts ( DynFlag(..) )
34 import Digraph ( SCC(..), stronglyConnComp )
35 import Name ( Name, nameOccName, nameSrcLoc )
37 import PrelNames ( isUnboundName )
38 import RdrName ( RdrName, rdrNameOcc )
39 import BasicTypes ( RecFlag(..), TopLevelFlag(..), isTopLevel )
40 import List ( unzip4 )
41 import SrcLoc ( mkSrcSpan, Located(..), unLoc )
45 import Monad ( foldM )
47 import SrcLoc (getLoc) -- tmp
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).
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 (HsBindGroup, HsBind)
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 @FlatMonoBinds@) 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 @rnTopMonoBinds@ assumes that the environment already
157 contains bindings for the binders of this particular binding.
160 rnTopBinds :: Bag (LHsBind RdrName)
162 -> RnM ([HsBindGroup Name], DefUses)
164 -- The binders of the binding are in scope already;
165 -- the top level scope resolution does that
167 rnTopBinds mbinds sigs
168 = bindPatSigTyVars (collectSigTysFromHsBinds (bagToList mbinds)) $ \ _ ->
169 -- Hmm; by analogy with Ids, this doesn't look right
170 -- Top-level bound type vars should really scope over
171 -- everything, but we only scope them over the other bindings
173 rnBinds TopLevel mbinds sigs
177 %************************************************************************
181 %************************************************************************
184 rnBindsAndThen :: Bag (LHsBind RdrName)
186 -> ([HsBindGroup Name] -> RnM (result, FreeVars))
187 -> RnM (result, FreeVars)
189 rnBindsAndThen mbinds sigs thing_inside
190 = -- Extract all the binders in this group, and extend the
191 -- current scope, inventing new names for the new binders
192 -- This also checks that the names form a set
193 bindLocatedLocalsRn doc mbinders_w_srclocs $ \ _ ->
194 bindPatSigTyVarsFV (collectSigTysFromHsBinds (bagToList mbinds)) $
196 -- Then install local fixity declarations
197 -- Notice that they scope over thing_inside too
198 bindLocalFixities [sig | L _ (FixSig sig) <- sigs ] $
201 rnBinds NotTopLevel mbinds sigs `thenM` \ (binds, bind_dus) ->
203 -- Now do the "thing inside"
204 thing_inside binds `thenM` \ (result,result_fvs) ->
206 -- Final error checking
208 all_uses = duUses bind_dus `plusFV` result_fvs
209 bndrs = duDefs bind_dus
210 unused_bndrs = nameSetToList (bndrs `minusNameSet` all_uses)
212 warnUnusedLocalBinds unused_bndrs `thenM_`
214 returnM (result, all_uses `minusNameSet` bndrs)
215 -- duUses: It's important to return all the uses, not the 'real uses' used for
216 -- warning about unused bindings. Otherwise consider:
218 -- y = let p = x in 'x' -- NB: p not used
219 -- If we don't "see" the dependency of 'y' on 'x', we may put the
220 -- bindings in the wrong order, and the type checker will complain
221 -- that x isn't in scope
223 mbinders_w_srclocs = collectHsBindLocatedBinders mbinds
224 doc = text "In the binding group for:"
225 <+> pprWithCommas ppr (map unLoc mbinders_w_srclocs)
229 %************************************************************************
231 \subsubsection{rnBinds -- the main work is done here}
233 %************************************************************************
235 @rnMonoBinds@ is used by {\em both} top-level and nested bindings.
236 It assumes that all variables bound in this group are already in scope.
237 This is done {\em either} by pass 3 (for the top-level bindings),
238 {\em or} by @rnMonoBinds@ (for the nested ones).
241 rnBinds :: TopLevelFlag
242 -> Bag (LHsBind RdrName)
244 -> RnM ([HsBindGroup Name], DefUses)
246 -- Assumes the binders of the binding are in scope already
248 rnBinds top_lvl mbinds sigs
249 = renameSigs sigs `thenM` \ siglist ->
251 -- Rename the bindings, returning a [HsBindVertex]
252 -- which is a list of indivisible vertices so far as
253 -- the strongly-connected-components (SCC) analysis is concerned
254 mkBindVertices siglist mbinds `thenM` \ mbinds_info ->
256 -- Do the SCC analysis
258 scc_result = rnSCC mbinds_info
259 (groups, bind_dus_s) = unzip (map reconstructCycle scc_result)
260 bind_dus = mkDUs bind_dus_s
261 binders = duDefs bind_dus
263 -- Check for duplicate or mis-placed signatures
264 checkSigs (okBindSig binders) siglist `thenM_`
266 -- Warn about missing signatures,
267 -- but only at top level, and not in interface mode
268 -- (The latter is important when renaming bindings from 'deriving' clauses.)
269 doptM Opt_WarnMissingSigs `thenM` \ warn_missing_sigs ->
270 (if isTopLevel top_lvl &&
273 type_sig_vars = [ unLoc n | L _ (Sig n _) <- siglist]
274 un_sigd_binders = filter (not . (`elem` type_sig_vars))
275 (nameSetToList binders)
277 mappM_ missingSigWarn un_sigd_binders
282 returnM (groups, bind_dus `plusDU` usesOnly (hsSigsFVs siglist))
285 @mkBindVertices@ is ever-so-slightly magical in that it sticks
286 unique ``vertex tags'' on its output; minor plumbing required.
289 mkBindVertices :: [LSig Name] -- Signatures
290 -> Bag (LHsBind RdrName)
292 mkBindVertices sigs = mapM (mkBindVertex sigs) . bagToList
294 mkBindVertex :: [LSig Name] -> LHsBind RdrName -> RnM BindVertex
295 mkBindVertex sigs (L loc (PatBind pat grhss))
297 rnLPat pat `thenM` \ (pat', pat_fvs) ->
299 -- Find which things are bound in this group
301 names_bound_here = mkNameSet (collectPatBinders pat')
303 sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
304 rnGRHSs PatBindRhs grhss `thenM` \ (grhss', fvs) ->
306 (names_bound_here, fvs `plusFV` pat_fvs,
307 L loc (PatBind pat' grhss'), sigs_for_me
310 mkBindVertex sigs (L loc (FunBind name inf matches))
312 lookupLocatedBndrRn name `thenM` \ new_name ->
314 plain_name = unLoc new_name
315 names_bound_here = unitNameSet plain_name
317 sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
318 mapFvRn (rnMatch (FunRhs plain_name)) matches `thenM` \ (new_matches, fvs) ->
319 mappM_ (checkPrecMatch inf plain_name) new_matches `thenM_`
321 (unitNameSet plain_name, fvs,
322 L loc (FunBind new_name inf new_matches), sigs_for_me
325 sigsForMe names_bound_here sigs
326 = foldlM check [] (filter (sigForThisGroup names_bound_here) sigs)
328 -- sigForThisGroup only returns signatures for
329 -- which sigName returns a Just
330 eq sig1 sig2 = eqHsSig (unLoc sig1) (unLoc sig2)
332 check sigs sig = case filter (eq sig) sigs of
333 [] -> returnM (sig:sigs)
334 other -> dupSigDeclErr sig other `thenM_`
339 @rnMethodBinds@ is used for the method bindings of a class and an instance
340 declaration. Like @rnBinds@ but without dependency analysis.
342 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
343 That's crucial when dealing with an instance decl:
345 instance Foo (T a) where
348 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
349 and unless @op@ occurs we won't treat the type signature of @op@ in the class
350 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
351 in many ways the @op@ in an instance decl is just like an occurrence, not
355 rnMethodBinds :: Name -- Class name
356 -> [Name] -- Names for generic type variables
357 -> (LHsBinds RdrName)
358 -> RnM (LHsBinds Name, FreeVars)
360 rnMethodBinds cls gen_tyvars binds
361 = foldM do_one (emptyBag,emptyFVs) (bagToList binds)
362 where do_one (binds,fvs) bind = do
363 (bind', fvs_bind) <- rnMethodBind cls gen_tyvars bind
364 return (bind' `unionBags` binds, fvs_bind `plusFV` fvs)
367 rnMethodBind cls gen_tyvars (L loc (FunBind name inf matches))
369 lookupLocatedInstDeclBndr cls name `thenM` \ sel_name ->
370 let plain_name = unLoc sel_name in
371 -- We use the selector name as the binder
373 mapFvRn (rn_match plain_name) matches `thenM` \ (new_matches, fvs) ->
374 mappM_ (checkPrecMatch inf plain_name) new_matches `thenM_`
375 returnM (unitBag (L loc (FunBind sel_name inf new_matches)), fvs `addOneFV` plain_name)
377 -- Gruesome; bring into scope the correct members of the generic type variables
378 -- See comments in RnSource.rnSourceDecl(ClassDecl)
379 rn_match sel_name match@(L _ (Match (L _ (TypePat ty) : _) _ _))
380 = extendTyVarEnvFVRn gen_tvs $
381 rnMatch (FunRhs sel_name) match
383 tvs = map (rdrNameOcc.unLoc) (extractHsTyRdrTyVars ty)
384 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
386 rn_match sel_name match = rnMatch (FunRhs sel_name) match
389 -- Can't handle method pattern-bindings which bind multiple methods.
390 rnMethodBind cls gen_tyvars mbind@(L loc (PatBind other_pat _))
391 = addLocErr mbind methodBindErr `thenM_`
392 returnM (emptyBag, emptyFVs)
396 %************************************************************************
398 Strongly connected components
400 %************************************************************************
403 type BindVertex = (Defs, Uses, LHsBind Name, [LSig Name])
404 -- Signatures, if any, for this vertex
406 rnSCC :: [BindVertex] -> [SCC BindVertex]
407 rnSCC nodes = stronglyConnComp (mkEdges nodes)
411 mkEdges :: [BindVertex] -> [(BindVertex, VertexTag, [VertexTag])]
412 -- We keep the uses with the binding,
413 -- so we can track unused bindings better
415 = [ (thing, tag, dest_vertices uses)
416 | (thing@(_, uses, _, _), tag) <- tagged_nodes
419 tagged_nodes = nodes `zip` [0::VertexTag ..]
421 -- An edge (v,v') indicates that v depends on v'
422 dest_vertices uses = [ target_vertex
423 | ((defs, _, _, _), target_vertex) <- tagged_nodes,
424 defs `intersectsNameSet` uses
427 reconstructCycle :: SCC BindVertex -> (HsBindGroup Name, (Defs,Uses))
428 reconstructCycle (AcyclicSCC (defs, uses, bind, sigs))
429 = (HsBindGroup (unitBag bind) sigs NonRecursive, (defs, uses))
430 reconstructCycle (CyclicSCC cycle)
431 = (HsBindGroup this_gp_binds this_gp_sigs Recursive,
432 (unionManyNameSets defs_s, unionManyNameSets uses_s))
434 (defs_s, uses_s, binds_s, sigs_s) = unzip4 cycle
435 this_gp_binds = listToBag binds_s
436 this_gp_sigs = foldr1 (++) sigs_s
440 %************************************************************************
442 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
444 %************************************************************************
446 @renameSigs@ checks for:
448 \item more than one sig for one thing;
449 \item signatures given for things not bound here;
450 \item with suitably flaggery, that all top-level things have type signatures.
453 At the moment we don't gather free-var info from the types in
454 signatures. We'd only need this if we wanted to report unused tyvars.
457 checkSigs :: (LSig Name -> Bool) -- OK-sig predicbate
460 checkSigs ok_sig sigs
461 -- Check for (a) duplicate signatures
462 -- (b) signatures for things not in this group
463 -- Well, I can't see the check for (a)... ToDo!
464 = mappM_ unknownSigErr (filter bad sigs)
466 bad sig = not (ok_sig sig) &&
468 Just n | isUnboundName n -> False
469 -- Don't complain about an unbound name again
472 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
473 -- because this won't work for:
474 -- instance Foo T where
477 -- We'll just rename the INLINE prag to refer to whatever other 'op'
478 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
479 -- Doesn't seem worth much trouble to sort this.
481 renameSigs :: [LSig RdrName] -> RnM [LSig Name]
482 renameSigs sigs = mappM (wrapLocM renameSig) (filter (not . isFixitySig . unLoc) sigs)
483 -- Remove fixity sigs which have been dealt with already
485 renameSig :: Sig RdrName -> RnM (Sig Name)
486 -- FixitSig is renamed elsewhere.
488 = lookupLocatedSigOccRn v `thenM` \ new_v ->
489 rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
490 returnM (Sig new_v new_ty)
492 renameSig (SpecInstSig ty)
493 = rnLHsType (text "A SPECIALISE instance pragma") ty `thenM` \ new_ty ->
494 returnM (SpecInstSig new_ty)
496 renameSig (SpecSig v ty)
497 = lookupLocatedSigOccRn v `thenM` \ new_v ->
498 rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
499 returnM (SpecSig new_v new_ty)
501 renameSig (InlineSig b v p)
502 = lookupLocatedSigOccRn v `thenM` \ new_v ->
503 returnM (InlineSig b new_v p)
507 %************************************************************************
509 \subsection{Error messages}
511 %************************************************************************
514 dupSigDeclErr (L loc sig) sigs
516 vcat [ptext SLIT("Duplicate") <+> what_it_is <> colon,
517 nest 2 (vcat (map ppr_sig (L loc sig:sigs)))]
519 what_it_is = hsSigDoc sig
520 ppr_sig (L loc sig) = ppr loc <> colon <+> ppr sig
522 unknownSigErr (L loc sig)
524 sep [ptext SLIT("Misplaced") <+> what_it_is <> colon, ppr sig]
526 what_it_is = hsSigDoc sig
529 = addWarnAt (mkSrcSpan loc loc) $
530 sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)]
532 loc = nameSrcLoc var -- TODO: make a proper span
535 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))