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 ( rnMatchGroup, rnMatch, rnGRHSs, checkPrecMatch )
27 import RnEnv ( bindLocatedLocalsRn, lookupLocatedBndrRn,
28 lookupLocatedInstDeclBndr,
29 lookupLocatedSigOccRn, bindPatSigTyVars, bindPatSigTyVarsFV,
30 bindLocalFixities, bindSigTyVarsFV,
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 )
44 import Monad ( foldM )
47 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
48 -- place and can be used when complaining.
50 The code tree received by the function @rnBinds@ contains definitions
51 in where-clauses which are all apparently mutually recursive, but which may
52 not really depend upon each other. For example, in the top level program
57 the definitions of @a@ and @y@ do not depend on each other at all.
58 Unfortunately, the typechecker cannot always check such definitions.
59 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
60 definitions. In Proceedings of the International Symposium on Programming,
61 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
62 However, the typechecker usually can check definitions in which only the
63 strongly connected components have been collected into recursive bindings.
64 This is precisely what the function @rnBinds@ does.
66 ToDo: deal with case where a single monobinds binds the same variable
69 The vertag tag is a unique @Int@; the tags only need to be unique
70 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
71 (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 (HsBindGroup, HsBind)
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 @FlatMonoBinds@) 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 @rnTopMonoBinds@ assumes that the environment already
154 contains bindings for the binders of this particular binding.
157 rnTopBinds :: LHsBinds RdrName
159 -> RnM ([HsBindGroup Name], DefUses)
161 -- The binders of the binding are in scope already;
162 -- the top level scope resolution does that
164 rnTopBinds mbinds sigs
165 = bindPatSigTyVars (collectSigTysFromHsBinds (bagToList mbinds)) $ \ _ ->
166 -- Hmm; by analogy with Ids, this doesn't look right
167 -- Top-level bound type vars should really scope over
168 -- everything, but we only scope them over the other bindings
170 rnBinds TopLevel mbinds sigs
174 %************************************************************************
178 %************************************************************************
181 rnBindsAndThen :: Bag (LHsBind RdrName)
183 -> ([HsBindGroup Name] -> RnM (result, FreeVars))
184 -> RnM (result, FreeVars)
186 rnBindsAndThen mbinds sigs thing_inside
187 = -- Extract all the binders in this group, and extend the
188 -- current scope, inventing new names for the new binders
189 -- This also checks that the names form a set
190 bindLocatedLocalsRn doc mbinders_w_srclocs $ \ _ ->
191 bindPatSigTyVarsFV (collectSigTysFromHsBinds (bagToList mbinds)) $
193 -- Then install local fixity declarations
194 -- Notice that they scope over thing_inside too
195 bindLocalFixities [sig | L _ (FixSig sig) <- sigs ] $
198 rnBinds NotTopLevel mbinds sigs `thenM` \ (binds, bind_dus) ->
200 -- Now do the "thing inside"
201 thing_inside binds `thenM` \ (result,result_fvs) ->
203 -- Final error checking
205 all_uses = duUses bind_dus `plusFV` result_fvs
206 bndrs = duDefs bind_dus
207 unused_bndrs = nameSetToList (bndrs `minusNameSet` all_uses)
209 warnUnusedLocalBinds unused_bndrs `thenM_`
211 returnM (result, all_uses `minusNameSet` bndrs)
212 -- duUses: It's important to return all the uses, not the 'real uses' used for
213 -- warning about unused bindings. Otherwise consider:
215 -- y = let p = x in 'x' -- NB: p not used
216 -- If we don't "see" the dependency of 'y' on 'x', we may put the
217 -- bindings in the wrong order, and the type checker will complain
218 -- that x isn't in scope
220 mbinders_w_srclocs = collectHsBindLocatedBinders mbinds
221 doc = text "In the binding group for:"
222 <+> pprWithCommas ppr (map unLoc mbinders_w_srclocs)
226 %************************************************************************
228 \subsubsection{rnBinds -- the main work is done here}
230 %************************************************************************
232 @rnMonoBinds@ is used by {\em both} top-level and nested bindings.
233 It assumes that all variables bound in this group are already in scope.
234 This is done {\em either} by pass 3 (for the top-level bindings),
235 {\em or} by @rnMonoBinds@ (for the nested ones).
238 rnBinds :: TopLevelFlag
241 -> RnM ([HsBindGroup Name], DefUses)
243 -- Assumes the binders of the binding are in scope already
245 rnBinds top_lvl mbinds sigs
246 = renameSigs sigs `thenM` \ siglist ->
248 -- Rename the bindings, returning a [HsBindVertex]
249 -- which is a list of indivisible vertices so far as
250 -- the strongly-connected-components (SCC) analysis is concerned
251 mkBindVertices siglist mbinds `thenM` \ mbinds_info ->
253 -- Do the SCC analysis
255 scc_result = rnSCC mbinds_info
256 (groups, bind_dus_s) = unzip (map reconstructCycle scc_result)
257 bind_dus = mkDUs bind_dus_s
258 binders = duDefs bind_dus
260 -- Check for duplicate or mis-placed signatures
261 checkSigs (okBindSig binders) siglist `thenM_`
263 -- Warn about missing signatures,
264 -- but only at top level, and not in interface mode
265 -- (The latter is important when renaming bindings from 'deriving' clauses.)
266 doptM Opt_WarnMissingSigs `thenM` \ warn_missing_sigs ->
267 (if isTopLevel top_lvl &&
270 type_sig_vars = [ unLoc n | L _ (Sig n _) <- siglist]
271 un_sigd_binders = filter (not . (`elem` type_sig_vars))
272 (nameSetToList binders)
274 mappM_ missingSigWarn un_sigd_binders
279 returnM (groups, bind_dus `plusDU` usesOnly (hsSigsFVs siglist))
282 @mkBindVertices@ is ever-so-slightly magical in that it sticks
283 unique ``vertex tags'' on its output; minor plumbing required.
286 mkBindVertices :: [LSig Name] -- Signatures
289 mkBindVertices sigs = mapM (mkBindVertex sigs) . bagToList
291 mkBindVertex :: [LSig Name] -> LHsBind RdrName -> RnM BindVertex
292 mkBindVertex sigs (L loc (PatBind pat grhss ty))
294 rnLPat pat `thenM` \ (pat', pat_fvs) ->
296 -- Find which things are bound in this group
298 names_bound_here = mkNameSet (collectPatBinders pat')
300 sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
301 bindSigTyVarsFV sigs_for_me (
302 rnGRHSs PatBindRhs grhss
303 ) `thenM` \ (grhss', fvs) ->
305 (names_bound_here, fvs `plusFV` pat_fvs,
306 L loc (PatBind pat' grhss' ty), sigs_for_me
309 mkBindVertex sigs (L loc (FunBind name inf matches))
311 lookupLocatedBndrRn name `thenM` \ new_name ->
313 plain_name = unLoc new_name
314 names_bound_here = unitNameSet plain_name
316 sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
317 bindSigTyVarsFV sigs_for_me (
318 rnMatchGroup (FunRhs plain_name) matches
319 ) `thenM` \ (new_matches, fvs) ->
320 checkPrecMatch inf plain_name new_matches `thenM_`
322 (unitNameSet plain_name, fvs,
323 L loc (FunBind new_name inf new_matches), sigs_for_me
326 sigsForMe names_bound_here sigs
327 = foldlM check [] (filter (sigForThisGroup names_bound_here) sigs)
329 -- sigForThisGroup only returns signatures for
330 -- which sigName returns a Just
331 eq sig1 sig2 = eqHsSig (unLoc sig1) (unLoc sig2)
333 check sigs sig = case filter (eq sig) sigs of
334 [] -> returnM (sig:sigs)
335 other -> dupSigDeclErr sig other `thenM_`
340 @rnMethodBinds@ is used for the method bindings of a class and an instance
341 declaration. Like @rnBinds@ but without dependency analysis.
343 NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
344 That's crucial when dealing with an instance decl:
346 instance Foo (T a) where
349 This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
350 and unless @op@ occurs we won't treat the type signature of @op@ in the class
351 decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
352 in many ways the @op@ in an instance decl is just like an occurrence, not
356 rnMethodBinds :: Name -- Class name
357 -> [Name] -- Names for generic type variables
359 -> RnM (LHsBinds Name, FreeVars)
361 rnMethodBinds cls gen_tyvars binds
362 = foldM do_one (emptyBag,emptyFVs) (bagToList binds)
363 where do_one (binds,fvs) bind = do
364 (bind', fvs_bind) <- rnMethodBind cls gen_tyvars bind
365 return (bind' `unionBags` binds, fvs_bind `plusFV` fvs)
367 rnMethodBind cls gen_tyvars (L loc (FunBind name inf (MatchGroup 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) ->
375 new_group = MatchGroup new_matches placeHolderType
377 checkPrecMatch inf plain_name new_group `thenM_`
378 returnM (unitBag (L loc (FunBind sel_name inf new_group)), fvs `addOneFV` plain_name)
380 -- Truly gruesome; bring into scope the correct members of the generic
381 -- type variables. See comments in RnSource.rnSourceDecl(ClassDecl)
382 rn_match sel_name match@(L _ (Match (L _ (TypePat ty) : _) _ _))
383 = extendTyVarEnvFVRn gen_tvs $
384 rnMatch (FunRhs sel_name) match
386 tvs = map (rdrNameOcc.unLoc) (extractHsTyRdrTyVars ty)
387 gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
389 rn_match sel_name match = rnMatch (FunRhs sel_name) match
392 -- Can't handle method pattern-bindings which bind multiple methods.
393 rnMethodBind cls gen_tyvars mbind@(L loc (PatBind other_pat _ _))
394 = addLocErr mbind methodBindErr `thenM_`
395 returnM (emptyBag, emptyFVs)
399 %************************************************************************
401 Strongly connected components
403 %************************************************************************
406 type BindVertex = (Defs, Uses, LHsBind Name, [LSig Name])
407 -- Signatures, if any, for this vertex
409 rnSCC :: [BindVertex] -> [SCC BindVertex]
410 rnSCC nodes = stronglyConnComp (mkEdges nodes)
414 mkEdges :: [BindVertex] -> [(BindVertex, VertexTag, [VertexTag])]
415 -- We keep the uses with the binding,
416 -- so we can track unused bindings better
418 = [ (thing, tag, dest_vertices uses)
419 | (thing@(_, uses, _, _), tag) <- tagged_nodes
422 tagged_nodes = nodes `zip` [0::VertexTag ..]
424 -- An edge (v,v') indicates that v depends on v'
425 dest_vertices uses = [ target_vertex
426 | ((defs, _, _, _), target_vertex) <- tagged_nodes,
427 defs `intersectsNameSet` uses
430 reconstructCycle :: SCC BindVertex -> (HsBindGroup Name, (Defs,Uses))
431 reconstructCycle (AcyclicSCC (defs, uses, bind, sigs))
432 = (HsBindGroup (unitBag bind) sigs NonRecursive, (defs, uses))
433 reconstructCycle (CyclicSCC cycle)
434 = (HsBindGroup this_gp_binds this_gp_sigs Recursive,
435 (unionManyNameSets defs_s, unionManyNameSets uses_s))
437 (defs_s, uses_s, binds_s, sigs_s) = unzip4 cycle
438 this_gp_binds = listToBag binds_s
439 this_gp_sigs = foldr1 (++) sigs_s
443 %************************************************************************
445 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
447 %************************************************************************
449 @renameSigs@ checks for:
451 \item more than one sig for one thing;
452 \item signatures given for things not bound here;
453 \item with suitably flaggery, that all top-level things have type signatures.
456 At the moment we don't gather free-var info from the types in
457 signatures. We'd only need this if we wanted to report unused tyvars.
460 checkSigs :: (LSig Name -> Bool) -- OK-sig predicbate
463 checkSigs ok_sig sigs
464 -- Check for (a) duplicate signatures
465 -- (b) signatures for things not in this group
466 -- Well, I can't see the check for (a)... ToDo!
467 = mappM_ unknownSigErr (filter bad sigs)
469 bad sig = not (ok_sig sig) &&
471 Just n | isUnboundName n -> False
472 -- Don't complain about an unbound name again
475 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
476 -- because this won't work for:
477 -- instance Foo T where
480 -- We'll just rename the INLINE prag to refer to whatever other 'op'
481 -- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
482 -- Doesn't seem worth much trouble to sort this.
484 renameSigs :: [LSig RdrName] -> RnM [LSig Name]
485 renameSigs sigs = mappM (wrapLocM renameSig) (filter (not . isFixitySig . unLoc) sigs)
486 -- Remove fixity sigs which have been dealt with already
488 renameSig :: Sig RdrName -> RnM (Sig Name)
489 -- FixitSig is renamed elsewhere.
491 = lookupLocatedSigOccRn v `thenM` \ new_v ->
492 rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
493 returnM (Sig new_v new_ty)
495 renameSig (SpecInstSig ty)
496 = rnLHsType (text "A SPECIALISE instance pragma") ty `thenM` \ new_ty ->
497 returnM (SpecInstSig new_ty)
499 renameSig (SpecSig v ty)
500 = lookupLocatedSigOccRn v `thenM` \ new_v ->
501 rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
502 returnM (SpecSig new_v new_ty)
504 renameSig (InlineSig b v p)
505 = lookupLocatedSigOccRn v `thenM` \ new_v ->
506 returnM (InlineSig b new_v p)
510 %************************************************************************
512 \subsection{Error messages}
514 %************************************************************************
517 dupSigDeclErr (L loc sig) sigs
519 vcat [ptext SLIT("Duplicate") <+> what_it_is <> colon,
520 nest 2 (vcat (map ppr_sig (L loc sig:sigs)))]
522 what_it_is = hsSigDoc sig
523 ppr_sig (L loc sig) = ppr loc <> colon <+> ppr sig
525 unknownSigErr (L loc sig)
527 sep [ptext SLIT("Misplaced") <+> what_it_is <> colon, ppr sig]
529 what_it_is = hsSigDoc sig
532 = addWarnAt (mkSrcSpan loc loc) $
533 sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)]
535 loc = nameSrcLoc var -- TODO: make a proper span
538 = hang (ptext SLIT("Pattern bindings (except simple variables) not allowed in instance declarations"))