2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
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,
18 #include "HsVersions.h"
20 import {-# SOURCE #-} RnSource ( rnHsSigType )
26 import RnExpr ( rnMatch, rnGRHSsAndBinds, rnPat, checkPrecMatch )
27 import RnEnv ( bindLocatedLocalsRn, lookupBndrRn, lookupOccRn,
28 newLocalNames, isUnboundName, warnUnusedBinds
30 import CmdLineOpts ( opt_SigsRequired )
31 import Digraph ( stronglyConnComp, SCC(..) )
32 import Name ( OccName(..), Provenance,
34 NameSet(..), emptyNameSet, mkNameSet, unionNameSets,
35 minusNameSet, unionManyNameSets, elemNameSet, unitNameSet, nameSetToList
37 import BasicTypes ( RecFlag(..), TopLevelFlag(..) )
38 import Util ( thenCmp, removeDups, panic, panic#, assertPanic )
39 import UniqSet ( UniqSet )
40 import ListSetOps ( minusList )
41 import Bag ( bagToList )
42 import UniqFM ( UniqFM )
46 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
47 -- place and can be used when complaining.
49 The code tree received by the function @rnBinds@ contains definitions
50 in where-clauses which are all apparently mutually recursive, but which may
51 not really depend upon each other. For example, in the top level program
56 the definitions of @a@ and @y@ do not depend on each other at all.
57 Unfortunately, the typechecker cannot always check such definitions.
58 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
59 definitions. In Proceedings of the International Symposium on Programming,
60 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
61 However, the typechecker usually can check definitions in which only the
62 strongly connected components have been collected into recursive bindings.
63 This is precisely what the function @rnBinds@ does.
65 ToDo: deal with case where a single monobinds binds the same variable
68 The vertag tag is a unique @Int@; the tags only need to be unique
69 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
70 (heavy monad machinery not needed).
74 type Cycle = [VertexTag]
75 type Edge = (VertexTag, VertexTag)
78 %************************************************************************
80 %* naming conventions *
82 %************************************************************************
84 \subsection[name-conventions]{Name conventions}
86 The basic algorithm involves walking over the tree and returning a tuple
87 containing the new tree plus its free variables. Some functions, such
88 as those walking polymorphic bindings (HsBinds) and qualifier lists in
89 list comprehensions (@Quals@), return the variables bound in local
90 environments. These are then used to calculate the free variables of the
91 expression evaluated in these environments.
93 Conventions for variable names are as follows:
96 new code is given a prime to distinguish it from the old.
99 a set of variables defined in @Exp@ is written @dvExp@
102 a set of variables free in @Exp@ is written @fvExp@
105 %************************************************************************
107 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
109 %************************************************************************
111 \subsubsection[dep-HsBinds]{Polymorphic bindings}
113 Non-recursive expressions are reconstructed without any changes at top
114 level, although their component expressions may have to be altered.
115 However, non-recursive expressions are currently not expected as
116 \Haskell{} programs, and this code should not be executed.
118 Monomorphic bindings contain information that is returned in a tuple
119 (a @FlatMonoBindsInfo@) containing:
123 a unique @Int@ that serves as the ``vertex tag'' for this binding.
126 the name of a function or the names in a pattern. These are a set
127 referred to as @dvLhs@, the defined variables of the left hand side.
130 the free variables of the body. These are referred to as @fvBody@.
133 the definition's actual code. This is referred to as just @code@.
136 The function @nonRecDvFv@ returns two sets of variables. The first is
137 the set of variables defined in the set of monomorphic bindings, while the
138 second is the set of free variables in those bindings.
140 The set of variables defined in a non-recursive binding is just the
141 union of all of them, as @union@ removes duplicates. However, the
142 free variables in each successive set of cumulative bindings is the
143 union of those in the previous set plus those of the newest binding after
144 the defined variables of the previous set have been removed.
146 @rnMethodBinds@ deals only with the declarations in class and
147 instance declarations. It expects only to see @FunMonoBind@s, and
148 it expects the global environment to contain bindings for the binders
149 (which are all class operations).
151 %************************************************************************
153 %* Top-level bindings
155 %************************************************************************
157 @rnTopBinds@ assumes that the environment already
158 contains bindings for the binders of this particular binding.
161 rnTopBinds :: RdrNameHsBinds -> RnMS s RenamedHsBinds
163 rnTopBinds EmptyBinds = returnRn EmptyBinds
164 rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs
165 -- The parser doesn't produce other forms
168 rnTopMonoBinds EmptyMonoBinds sigs
169 = returnRn EmptyBinds
171 rnTopMonoBinds mbinds sigs
172 = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->
174 binder_set = mkNameSet binder_names
175 exported_binders = mkNameSet (filter isExportedName binder_names)
177 rn_mono_binds TopLevel
178 binder_set mbinds sigs `thenRn` \ (new_binds, fv_set) ->
180 unused_binders = binder_set `minusNameSet` (fv_set `unionNameSets` exported_binders)
182 warnUnusedBinds unused_binders `thenRn_`
185 binder_rdr_names = map fst (bagToList (collectMonoBinders mbinds))
188 %************************************************************************
192 %************************************************************************
195 - collects up the binders for this declaration group,
196 - checks that they form a set
197 - extends the environment to bind them to new local names
198 - calls @rnMonoBinds@ to do the real work
201 rnBinds :: RdrNameHsBinds
202 -> (RenamedHsBinds -> RnMS s (result, FreeVars))
203 -> RnMS s (result, FreeVars)
205 rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds
206 rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
207 -- the parser doesn't produce other forms
210 rnMonoBinds :: RdrNameMonoBinds -> [RdrNameSig]
211 -> (RenamedHsBinds -> RnMS s (result, FreeVars))
212 -> RnMS s (result, FreeVars)
214 rnMonoBinds EmptyMonoBinds sigs thing_inside = thing_inside EmptyBinds
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 (text "binding group") mbinders_w_srclocs $ \ new_mbinders ->
222 binder_set = mkNameSet new_mbinders
224 rn_mono_binds NotTopLevel
225 binder_set mbinds sigs `thenRn` \ (binds,bind_fvs) ->
227 -- Now do the "thing inside", and deal with the free-variable calculations
228 thing_inside binds `thenRn` \ (result,result_fvs) ->
230 all_fvs = result_fvs `unionNameSets` bind_fvs
231 net_fvs = all_fvs `minusNameSet` binder_set
232 unused_binders = binder_set `minusNameSet` all_fvs
234 warnUnusedBinds unused_binders `thenRn_`
235 returnRn (result, net_fvs)
237 mbinders_w_srclocs = bagToList (collectMonoBinders mbinds)
241 %************************************************************************
243 %* MonoBinds -- the main work is done here
245 %************************************************************************
247 @rnMonoBinds@ is used by *both* top-level and nested bindings. It
248 assumes that all variables bound in this group are already in scope.
249 This is done *either* by pass 3 (for the top-level bindings), *or* by
250 @rnNestedMonoBinds@ (for the nested ones).
253 rn_mono_binds :: TopLevelFlag
254 -> NameSet -- Binders of this group
256 -> [RdrNameSig] -- Signatures attached to this group
257 -> RnMS s (RenamedHsBinds, --
258 FreeVars) -- Free variables
260 rn_mono_binds top_lev binders mbinds sigs
262 -- Rename the bindings, returning a MonoBindsInfo
263 -- which is a list of indivisible vertices so far as
264 -- the strongly-connected-components (SCC) analysis is concerned
265 rnBindSigs top_lev binders sigs `thenRn` \ siglist ->
266 flattenMonoBinds 0 siglist mbinds `thenRn` \ (_, mbinds_info) ->
268 -- Do the SCC analysis
269 let edges = mkEdges mbinds_info
270 scc_result = stronglyConnComp edges
271 final_binds = foldr1 ThenBinds (map reconstructCycle scc_result)
273 -- Deal with bound and free-var calculation
274 rhs_fvs = unionManyNameSets [fvs | (_,_,fvs,_,_) <- mbinds_info]
276 returnRn (final_binds, rhs_fvs)
279 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
280 unique ``vertex tags'' on its output; minor plumbing required.
283 flattenMonoBinds :: Int -- Next free vertex tag
284 -> [RenamedSig] -- Signatures
286 -> RnMS s (Int, [FlatMonoBindsInfo])
288 flattenMonoBinds uniq sigs EmptyMonoBinds = returnRn (uniq, [])
290 flattenMonoBinds uniq sigs (AndMonoBinds bs1 bs2)
291 = flattenMonoBinds uniq sigs bs1 `thenRn` \ (uniq1, flat1) ->
292 flattenMonoBinds uniq1 sigs bs2 `thenRn` \ (uniq2, flat2) ->
293 returnRn (uniq2, flat1 ++ flat2)
295 flattenMonoBinds uniq sigs (PatMonoBind pat grhss_and_binds locn)
296 = pushSrcLocRn locn $
297 rnPat pat `thenRn` \ pat' ->
298 rnGRHSsAndBinds grhss_and_binds `thenRn` \ (grhss_and_binds', fvs) ->
300 -- Find which things are bound in this group
302 names_bound_here = mkNameSet (collectPatBinders pat')
303 sigs_for_me = filter ((`elemNameSet` names_bound_here) . sig_name) sigs
304 sigs_fvs = foldr sig_fv emptyNameSet sigs_for_me
310 fvs `unionNameSets` sigs_fvs,
311 PatMonoBind pat' grhss_and_binds' locn,
316 flattenMonoBinds uniq sigs (FunMonoBind name inf matches locn)
317 = pushSrcLocRn locn $
318 mapRn (checkPrecMatch inf name) matches `thenRn_`
319 lookupBndrRn name `thenRn` \ name' ->
320 mapAndUnzipRn rnMatch matches `thenRn` \ (new_matches, fv_lists) ->
322 fvs = unionManyNameSets fv_lists
323 sigs_for_me = filter ((name' ==) . sig_name) sigs
324 sigs_fvs = foldr sig_fv emptyNameSet sigs_for_me
330 fvs `unionNameSets` sigs_fvs,
331 FunMonoBind name' inf new_matches locn,
338 @rnMethodBinds@ is used for the method bindings of an instance
339 declaration. like @rnMonoBinds@ but without dependency analysis.
342 rnMethodBinds :: RdrNameMonoBinds -> RnMS s RenamedMonoBinds
344 rnMethodBinds EmptyMonoBinds = returnRn EmptyMonoBinds
346 rnMethodBinds (AndMonoBinds mb1 mb2)
347 = andRn AndMonoBinds (rnMethodBinds mb1)
350 rnMethodBinds (FunMonoBind occname inf matches locn)
351 = pushSrcLocRn locn $
352 mapRn (checkPrecMatch inf occname) matches `thenRn_`
354 newLocalNames [(occname, locn)] `thenRn` \ [op_name] ->
355 -- Make a fresh local for the bound variable; it must be different
356 -- to occurrences of the same thing on the LHS, which refer to the global
359 mapAndUnzipRn rnMatch matches `thenRn` \ (new_matches, _) ->
360 returnRn (FunMonoBind op_name inf new_matches locn)
362 rnMethodBinds (PatMonoBind (VarPatIn occname) grhss_and_binds locn)
363 = pushSrcLocRn locn $
364 newLocalNames [(occname, locn)] `thenRn` \ [op_name] ->
365 rnGRHSsAndBinds grhss_and_binds `thenRn` \ (grhss_and_binds', _) ->
366 returnRn (PatMonoBind (VarPatIn op_name) grhss_and_binds' locn)
368 -- Can't handle method pattern-bindings which bind multiple methods.
369 rnMethodBinds mbind@(PatMonoBind other_pat _ locn)
370 = pushSrcLocRn locn $
371 failWithRn EmptyMonoBinds (methodBindErr mbind)
375 -- If a SPECIALIZE pragma is of the "... = blah" form,
376 -- then we'd better make sure "blah" is taken into
377 -- acct in the dependency analysis (or we get an
378 -- unexpected out-of-scope error)! WDP 95/07
380 sig_fv (SpecSig _ _ (Just blah) _) acc = acc `unionNameSets` (unitNameSet blah)
384 %************************************************************************
386 \subsection[reconstruct-deps]{Reconstructing dependencies}
388 %************************************************************************
390 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
391 as the two cases are similar.
394 reconstructCycle :: SCC FlatMonoBindsInfo
397 reconstructCycle (AcyclicSCC (_, _, _, binds, sigs))
398 = MonoBind binds sigs NonRecursive
400 reconstructCycle (CyclicSCC cycle)
401 = MonoBind this_gp_binds this_gp_sigs Recursive
403 this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, _, binds, _) <- cycle]
404 this_gp_sigs = foldr1 (++) [sigs | (_, _, _, _, sigs) <- cycle]
407 %************************************************************************
409 %* Manipulating FlatMonoBindInfo *
411 %************************************************************************
413 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
414 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
415 a function binding, and has itself been dependency-analysed and
419 type FlatMonoBindsInfo
420 = (VertexTag, -- Identifies the vertex
421 NameSet, -- Set of names defined in this vertex
422 NameSet, -- Set of names used in this vertex
423 RenamedMonoBinds, -- Binding for this vertex (always just one binding, either fun or pat)
424 [RenamedSig]) -- Signatures, if any, for this vertex
427 mkEdges :: [FlatMonoBindsInfo] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
430 = [ (info, tag, dest_vertices (nameSetToList names_used))
431 | info@(tag, names_defined, names_used, mbind, sigs) <- flat_info
434 -- An edge (v,v') indicates that v depends on v'
435 dest_vertices src_mentions = [ target_vertex
436 | (target_vertex, names_defined, _, _, _) <- flat_info,
437 mentioned_name <- src_mentions,
438 mentioned_name `elemNameSet` names_defined
443 %************************************************************************
445 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
447 %************************************************************************
449 @rnBindSigs@ checks for: (a)~more than one sig for one thing;
450 (b)~signatures given for things not bound here; (c)~with suitably
451 flaggery, that all top-level things have type signatures.
454 rnBindSigs :: TopLevelFlag
455 -> NameSet -- Set of names bound in this group
457 -> RnMS s [RenamedSig] -- List of Sig constructors
459 rnBindSigs top_lev binders sigs
460 = -- Rename the signatures
461 mapRn renameSig sigs `thenRn` \ sigs' ->
463 -- Check for (a) duplicate signatures
464 -- (b) signatures for things not in this group
465 -- (c) optionally, bindings with no signature
467 (goodies, dups) = removeDups cmp_sig (filter (not.isUnboundName.sig_name) sigs')
468 not_this_group = filter (\sig -> not (sig_name sig `elemNameSet` binders)) goodies
469 type_sig_vars = [n | Sig n _ _ <- goodies]
470 sigs_required = case top_lev of {TopLevel -> opt_SigsRequired; NotTopLevel -> False}
471 un_sigd_binders | sigs_required = nameSetToList binders `minusList` type_sig_vars
474 mapRn dupSigDeclErr dups `thenRn_`
475 mapRn unknownSigErr not_this_group `thenRn_`
476 mapRn (addErrRn.missingSigErr) un_sigd_binders `thenRn_`
478 returnRn sigs' -- bad ones and all:
479 -- we need bindings of *some* sort for every name
482 renameSig (Sig v ty src_loc)
483 = pushSrcLocRn src_loc $
484 lookupBndrRn v `thenRn` \ new_v ->
485 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
486 returnRn (Sig new_v new_ty src_loc)
488 renameSig (SpecSig v ty using src_loc)
489 = pushSrcLocRn src_loc $
490 lookupBndrRn v `thenRn` \ new_v ->
491 rnHsSigType (quotes (ppr v)) ty `thenRn` \ new_ty ->
492 rn_using using `thenRn` \ new_using ->
493 returnRn (SpecSig new_v new_ty new_using src_loc)
495 rn_using Nothing = returnRn Nothing
496 rn_using (Just x) = lookupOccRn x `thenRn` \ new_x ->
497 returnRn (Just new_x)
499 renameSig (InlineSig v src_loc)
500 = pushSrcLocRn src_loc $
501 lookupBndrRn v `thenRn` \ new_v ->
502 returnRn (InlineSig new_v src_loc)
504 renameSig (MagicUnfoldingSig v str src_loc)
505 = pushSrcLocRn src_loc $
506 lookupBndrRn v `thenRn` \ new_v ->
507 returnRn (MagicUnfoldingSig new_v str src_loc)
510 Checking for distinct signatures; oh, so boring
513 cmp_sig :: RenamedSig -> RenamedSig -> Ordering
514 cmp_sig (Sig n1 _ _) (Sig n2 _ _) = n1 `compare` n2
515 cmp_sig (InlineSig n1 _) (InlineSig n2 _) = n1 `compare` n2
516 cmp_sig (MagicUnfoldingSig n1 _ _) (MagicUnfoldingSig n2 _ _) = n1 `compare` n2
517 cmp_sig (SpecSig n1 ty1 _ _) (SpecSig n2 ty2 _ _)
518 = -- may have many specialisations for one value;
519 -- but not ones that are exactly the same...
520 thenCmp (n1 `compare` n2) (cmpHsType compare ty1 ty2)
522 cmp_sig other_1 other_2 -- Tags *must* be different
523 | (sig_tag other_1) _LT_ (sig_tag other_2) = LT
526 sig_tag (Sig n1 _ _) = (ILIT(1) :: FAST_INT)
527 sig_tag (SpecSig n1 _ _ _) = ILIT(2)
528 sig_tag (InlineSig n1 _) = ILIT(3)
529 sig_tag (MagicUnfoldingSig n1 _ _) = ILIT(4)
530 sig_tag _ = panic# "tag(RnBinds)"
532 sig_name (Sig n _ _) = n
533 sig_name (ClassOpSig n _ _ _) = n
534 sig_name (SpecSig n _ _ _) = n
535 sig_name (InlineSig n _) = n
536 sig_name (MagicUnfoldingSig n _ _) = n
539 %************************************************************************
541 \subsection{Error messages}
543 %************************************************************************
546 dupSigDeclErr (sig:sigs)
548 addErrRn (sep [ptext SLIT("more than one"),
549 ptext what_it_is, ptext SLIT("given for"),
550 quotes (ppr (sig_name sig))])
552 (what_it_is, loc) = sig_doc sig
556 addErrRn (sep [ptext flavour, ptext SLIT("but no definition for"),
557 quotes (ppr (sig_name sig))])
559 (flavour, loc) = sig_doc sig
561 sig_doc (Sig _ _ loc) = (SLIT("type signature"),loc)
562 sig_doc (ClassOpSig _ _ _ loc) = (SLIT("class-method type signature"), loc)
563 sig_doc (SpecSig _ _ _ loc) = (SLIT("SPECIALIZE pragma"),loc)
564 sig_doc (InlineSig _ loc) = (SLIT("INLINE pragma"),loc)
565 sig_doc (MagicUnfoldingSig _ _ loc) = (SLIT("MAGIC_UNFOLDING pragma"),loc)
568 = sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)]
571 = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))