-%\r
-% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998\r
-%\r
-\section[RnBinds]{Renaming and dependency analysis of bindings}\r
-\r
-This module does renaming and dependency analysis on value bindings in\r
-the abstract syntax. It does {\em not} do cycle-checks on class or\r
-type-synonym declarations; those cannot be done at this stage because\r
-they may be affected by renaming (which isn't fully worked out yet).\r
-\r
-\begin{code}\r
-module RnBinds (\r
- rnTopBinds, rnTopMonoBinds,\r
- rnMethodBinds, renameSigs,\r
- rnBinds,\r
- unknownSigErr\r
- ) where\r
-\r
-#include "HsVersions.h"\r
-\r
-import {-# SOURCE #-} RnSource ( rnHsSigType )\r
-\r
-import HsSyn\r
-import HsBinds ( sigsForMe )\r
-import RdrHsSyn\r
-import RnHsSyn\r
-import RnMonad\r
-import RnExpr ( rnMatch, rnGRHSs, rnPat, checkPrecMatch )\r
-import RnEnv ( bindLocatedLocalsRn, lookupBndrRn, lookupGlobalOccRn,\r
- warnUnusedLocalBinds, mapFvRn, \r
- FreeVars, emptyFVs, plusFV, plusFVs, unitFV, addOneFV,\r
- unknownNameErr\r
- )\r
-import CmdLineOpts ( opt_WarnMissingSigs )\r
-import Digraph ( stronglyConnComp, SCC(..) )\r
-import Name ( OccName, Name, nameOccName )\r
-import NameSet\r
-import RdrName ( RdrName, rdrNameOcc )\r
-import BasicTypes ( RecFlag(..), TopLevelFlag(..) )\r
-import Util ( thenCmp, removeDups )\r
-import List ( partition )\r
-import ListSetOps ( minusList )\r
-import Bag ( bagToList )\r
-import FiniteMap ( lookupFM, listToFM )\r
-import Maybe ( isJust )\r
-import Outputable\r
-\end{code}\r
-\r
--- ToDo: Put the annotations into the monad, so that they arrive in the proper\r
--- place and can be used when complaining.\r
-\r
-The code tree received by the function @rnBinds@ contains definitions\r
-in where-clauses which are all apparently mutually recursive, but which may\r
-not really depend upon each other. For example, in the top level program\r
-\begin{verbatim}\r
-f x = y where a = x\r
- y = x\r
-\end{verbatim}\r
-the definitions of @a@ and @y@ do not depend on each other at all.\r
-Unfortunately, the typechecker cannot always check such definitions.\r
-\footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive\r
-definitions. In Proceedings of the International Symposium on Programming,\r
-Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}\r
-However, the typechecker usually can check definitions in which only the\r
-strongly connected components have been collected into recursive bindings.\r
-This is precisely what the function @rnBinds@ does.\r
-\r
-ToDo: deal with case where a single monobinds binds the same variable\r
-twice.\r
-\r
-The vertag tag is a unique @Int@; the tags only need to be unique\r
-within one @MonoBinds@, so that unique-Int plumbing is done explicitly\r
-(heavy monad machinery not needed).\r
-\r
-\begin{code}\r
-type VertexTag = Int\r
-type Cycle = [VertexTag]\r
-type Edge = (VertexTag, VertexTag)\r
-\end{code}\r
-\r
-%************************************************************************\r
-%* *\r
-%* naming conventions *\r
-%* *\r
-%************************************************************************\r
-\r
-\subsection[name-conventions]{Name conventions}\r
-\r
-The basic algorithm involves walking over the tree and returning a tuple\r
-containing the new tree plus its free variables. Some functions, such\r
-as those walking polymorphic bindings (HsBinds) and qualifier lists in\r
-list comprehensions (@Quals@), return the variables bound in local\r
-environments. These are then used to calculate the free variables of the\r
-expression evaluated in these environments.\r
-\r
-Conventions for variable names are as follows:\r
-\begin{itemize}\r
-\item\r
-new code is given a prime to distinguish it from the old.\r
-\r
-\item\r
-a set of variables defined in @Exp@ is written @dvExp@\r
-\r
-\item\r
-a set of variables free in @Exp@ is written @fvExp@\r
-\end{itemize}\r
-\r
-%************************************************************************\r
-%* *\r
-%* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *\r
-%* *\r
-%************************************************************************\r
-\r
-\subsubsection[dep-HsBinds]{Polymorphic bindings}\r
-\r
-Non-recursive expressions are reconstructed without any changes at top\r
-level, although their component expressions may have to be altered.\r
-However, non-recursive expressions are currently not expected as\r
-\Haskell{} programs, and this code should not be executed.\r
-\r
-Monomorphic bindings contain information that is returned in a tuple\r
-(a @FlatMonoBindsInfo@) containing:\r
-\r
-\begin{enumerate}\r
-\item\r
-a unique @Int@ that serves as the ``vertex tag'' for this binding.\r
-\r
-\item\r
-the name of a function or the names in a pattern. These are a set\r
-referred to as @dvLhs@, the defined variables of the left hand side.\r
-\r
-\item\r
-the free variables of the body. These are referred to as @fvBody@.\r
-\r
-\item\r
-the definition's actual code. This is referred to as just @code@.\r
-\end{enumerate}\r
-\r
-The function @nonRecDvFv@ returns two sets of variables. The first is\r
-the set of variables defined in the set of monomorphic bindings, while the\r
-second is the set of free variables in those bindings.\r
-\r
-The set of variables defined in a non-recursive binding is just the\r
-union of all of them, as @union@ removes duplicates. However, the\r
-free variables in each successive set of cumulative bindings is the\r
-union of those in the previous set plus those of the newest binding after\r
-the defined variables of the previous set have been removed.\r
-\r
-@rnMethodBinds@ deals only with the declarations in class and\r
-instance declarations. It expects only to see @FunMonoBind@s, and\r
-it expects the global environment to contain bindings for the binders\r
-(which are all class operations).\r
-\r
-%************************************************************************\r
-%* *\r
-%* Top-level bindings\r
-%* *\r
-%************************************************************************\r
-\r
-@rnTopBinds@ assumes that the environment already\r
-contains bindings for the binders of this particular binding.\r
-\r
-\begin{code}\r
-rnTopBinds :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)\r
-\r
-rnTopBinds EmptyBinds = returnRn (EmptyBinds, emptyFVs)\r
-rnTopBinds (MonoBind bind sigs _) = rnTopMonoBinds bind sigs\r
- -- The parser doesn't produce other forms\r
-\r
-\r
-rnTopMonoBinds EmptyMonoBinds sigs \r
- = returnRn (EmptyBinds, emptyFVs)\r
-\r
-rnTopMonoBinds mbinds sigs\r
- = mapRn lookupBndrRn binder_rdr_names `thenRn` \ binder_names ->\r
- let\r
- binder_set = mkNameSet binder_names\r
- binder_occ_fm = listToFM [(nameOccName x,x) | x <- binder_names]\r
- in\r
- renameSigs opt_WarnMissingSigs binder_set\r
- (lookupSigOccRn binder_occ_fm) sigs `thenRn` \ (siglist, sig_fvs) ->\r
- rn_mono_binds siglist mbinds `thenRn` \ (final_binds, bind_fvs) ->\r
- returnRn (final_binds, bind_fvs `plusFV` sig_fvs)\r
- where\r
- binder_rdr_names = map fst (bagToList (collectMonoBinders mbinds))\r
-\r
--- the names appearing in the sigs have to be bound by \r
--- this group's binders.\r
-lookupSigOccRn binder_occ_fm rdr_name\r
- = case lookupFM binder_occ_fm (rdrNameOcc rdr_name) of\r
- Nothing -> failWithRn (mkUnboundName rdr_name)\r
- (unknownNameErr rdr_name)\r
- Just x -> returnRn x\r
-\end{code}\r
-\r
-%************************************************************************\r
-%* *\r
-%* Nested binds\r
-%* *\r
-%************************************************************************\r
-\r
-@rnMonoBinds@\r
- - collects up the binders for this declaration group,\r
- - checks that they form a set\r
- - extends the environment to bind them to new local names\r
- - calls @rnMonoBinds@ to do the real work\r
-\r
-\begin{code}\r
-rnBinds :: RdrNameHsBinds \r
- -> (RenamedHsBinds -> RnMS (result, FreeVars))\r
- -> RnMS (result, FreeVars)\r
-\r
-rnBinds EmptyBinds thing_inside = thing_inside EmptyBinds\r
-rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside\r
- -- the parser doesn't produce other forms\r
-\r
-\r
-rnMonoBinds :: RdrNameMonoBinds \r
- -> [RdrNameSig]\r
- -> (RenamedHsBinds -> RnMS (result, FreeVars))\r
- -> RnMS (result, FreeVars)\r
-\r
-rnMonoBinds EmptyMonoBinds sigs thing_inside = thing_inside EmptyBinds\r
-\r
-rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds\r
- = -- Extract all the binders in this group,\r
- -- and extend current scope, inventing new names for the new binders\r
- -- This also checks that the names form a set\r
- bindLocatedLocalsRn (text "a binding group") mbinders_w_srclocs $ \ new_mbinders ->\r
- let\r
- binder_set = mkNameSet new_mbinders\r
-\r
- -- Weed out the fixity declarations that do not\r
- -- apply to any of the binders in this group.\r
- (sigs_for_me, fixes_not_for_me) = partition forLocalBind sigs\r
-\r
- forLocalBind (FixSig sig@(FixitySig name _ _ )) =\r
- isJust (lookupFM binder_occ_fm (rdrNameOcc name))\r
- forLocalBind _ = True\r
-\r
- binder_occ_fm = listToFM [(nameOccName x,x) | x <- new_mbinders]\r
-\r
- in\r
- -- Report the fixity declarations in this group that \r
- -- don't refer to any of the group's binders.\r
- --\r
- mapRn_ (unknownSigErr) fixes_not_for_me `thenRn_`\r
- renameSigs False binder_set\r
- (lookupSigOccRn binder_occ_fm) sigs_for_me `thenRn` \ (siglist, sig_fvs) ->\r
- let\r
- fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]\r
- in\r
- -- Install the fixity declarations that do apply here and go.\r
- extendFixityEnv fixity_sigs (\r
- rn_mono_binds siglist mbinds\r
- ) `thenRn` \ (binds, bind_fvs) ->\r
-\r
- -- Now do the "thing inside", and deal with the free-variable calculations\r
- thing_inside binds `thenRn` \ (result,result_fvs) ->\r
- let\r
- all_fvs = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs\r
- unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)\r
- in\r
- warnUnusedLocalBinds unused_binders `thenRn_`\r
- returnRn (result, delListFromNameSet all_fvs new_mbinders)\r
- where\r
- mbinders_w_srclocs = bagToList (collectMonoBinders mbinds)\r
-\end{code}\r
-\r
-\r
-%************************************************************************\r
-%* *\r
-%* MonoBinds -- the main work is done here\r
-%* *\r
-%************************************************************************\r
-\r
-@rn_mono_binds@ is used by *both* top-level and nested bindings. It\r
-assumes that all variables bound in this group are already in scope.\r
-This is done *either* by pass 3 (for the top-level bindings), *or* by\r
-@rnMonoBinds@ (for the nested ones).\r
-\r
-\begin{code}\r
-rn_mono_binds :: [RenamedSig] -- Signatures attached to this group\r
- -> RdrNameMonoBinds \r
- -> RnMS (RenamedHsBinds, -- \r
- FreeVars) -- Free variables\r
-\r
-rn_mono_binds siglist mbinds\r
- =\r
- -- Rename the bindings, returning a MonoBindsInfo\r
- -- which is a list of indivisible vertices so far as\r
- -- the strongly-connected-components (SCC) analysis is concerned\r
- flattenMonoBinds siglist mbinds `thenRn` \ mbinds_info ->\r
-\r
- -- Do the SCC analysis\r
- let \r
- edges = mkEdges (mbinds_info `zip` [(0::Int)..])\r
- scc_result = stronglyConnComp edges\r
- final_binds = foldr1 ThenBinds (map reconstructCycle scc_result)\r
-\r
- -- Deal with bound and free-var calculation\r
- rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]\r
- in\r
- returnRn (final_binds, rhs_fvs)\r
-\end{code}\r
-\r
-@flattenMonoBinds@ is ever-so-slightly magical in that it sticks\r
-unique ``vertex tags'' on its output; minor plumbing required.\r
-\r
-Sigh - need to pass along the signatures for the group of bindings,\r
-in case any of them \r
-\r
-\begin{code}\r
-flattenMonoBinds :: [RenamedSig] -- Signatures\r
- -> RdrNameMonoBinds\r
- -> RnMS [FlatMonoBindsInfo]\r
-\r
-flattenMonoBinds sigs EmptyMonoBinds = returnRn []\r
-\r
-flattenMonoBinds sigs (AndMonoBinds bs1 bs2)\r
- = flattenMonoBinds sigs bs1 `thenRn` \ flat1 ->\r
- flattenMonoBinds sigs bs2 `thenRn` \ flat2 ->\r
- returnRn (flat1 ++ flat2)\r
-\r
-flattenMonoBinds sigs (PatMonoBind pat grhss locn)\r
- = pushSrcLocRn locn $\r
- rnPat pat `thenRn` \ (pat', pat_fvs) ->\r
-\r
- -- Find which things are bound in this group\r
- let\r
- names_bound_here = mkNameSet (collectPatBinders pat')\r
- sigs_for_me = sigsForMe (`elemNameSet` names_bound_here) sigs\r
- in\r
- rnGRHSs grhss `thenRn` \ (grhss', fvs) ->\r
- returnRn \r
- [(names_bound_here,\r
- fvs `plusFV` pat_fvs,\r
- PatMonoBind pat' grhss' locn,\r
- sigs_for_me\r
- )]\r
-\r
-flattenMonoBinds sigs (FunMonoBind name inf matches locn)\r
- = pushSrcLocRn locn $\r
- lookupBndrRn name `thenRn` \ new_name ->\r
- let\r
- sigs_for_me = sigsForMe (new_name ==) sigs\r
- in\r
- mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->\r
- mapRn_ (checkPrecMatch inf new_name) new_matches `thenRn_`\r
- returnRn\r
- [(unitNameSet new_name,\r
- fvs,\r
- FunMonoBind new_name inf new_matches locn,\r
- sigs_for_me\r
- )]\r
-\end{code}\r
-\r
-\r
-@rnMethodBinds@ is used for the method bindings of a class and an instance\r
-declaration. like @rnMonoBinds@ but without dependency analysis.\r
-\r
-NOTA BENE: we record each *binder* of a method-bind group as a free variable.\r
-That's crucial when dealing with an instance decl:\r
- instance Foo (T a) where\r
- op x = ...\r
-This might be the *sole* occurrence of 'op' for an imported class Foo,\r
-and unless op occurs we won't treat the type signature of op in the class\r
-decl for Foo as a source of instance-decl gates. But we should! Indeed,\r
-in many ways the op in an instance decl is just like an occurrence, not\r
-a binder.\r
-\r
-\begin{code}\r
-rnMethodBinds :: RdrNameMonoBinds -> RnMS (RenamedMonoBinds, FreeVars)\r
-\r
-rnMethodBinds EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)\r
-\r
-rnMethodBinds (AndMonoBinds mb1 mb2)\r
- = rnMethodBinds mb1 `thenRn` \ (mb1', fvs1) ->\r
- rnMethodBinds mb2 `thenRn` \ (mb2', fvs2) ->\r
- returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)\r
-\r
-rnMethodBinds (FunMonoBind name inf matches locn)\r
- = pushSrcLocRn locn $\r
-\r
- lookupGlobalOccRn name `thenRn` \ sel_name -> \r
- -- We use the selector name as the binder\r
-\r
- mapFvRn rnMatch matches `thenRn` \ (new_matches, fvs) ->\r
- mapRn_ (checkPrecMatch inf sel_name) new_matches `thenRn_`\r
- returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)\r
-\r
-rnMethodBinds (PatMonoBind (VarPatIn name) grhss locn)\r
- = pushSrcLocRn locn $\r
- lookupGlobalOccRn name `thenRn` \ sel_name -> \r
- rnGRHSs grhss `thenRn` \ (grhss', fvs) ->\r
- returnRn (PatMonoBind (VarPatIn sel_name) grhss' locn, fvs `addOneFV` sel_name)\r
-\r
--- Can't handle method pattern-bindings which bind multiple methods.\r
-rnMethodBinds mbind@(PatMonoBind other_pat _ locn)\r
- = pushSrcLocRn locn $\r
- failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)\r
-\end{code}\r
-\r
-\r
-%************************************************************************\r
-%* *\r
-\subsection[reconstruct-deps]{Reconstructing dependencies}\r
-%* *\r
-%************************************************************************\r
-\r
-This @MonoBinds@- and @ClassDecls@-specific code is segregated here,\r
-as the two cases are similar.\r
-\r
-\begin{code}\r
-reconstructCycle :: SCC FlatMonoBindsInfo\r
- -> RenamedHsBinds\r
-\r
-reconstructCycle (AcyclicSCC (_, _, binds, sigs))\r
- = MonoBind binds sigs NonRecursive\r
-\r
-reconstructCycle (CyclicSCC cycle)\r
- = MonoBind this_gp_binds this_gp_sigs Recursive\r
- where\r
- this_gp_binds = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]\r
- this_gp_sigs = foldr1 (++) [sigs | (_, _, _, sigs) <- cycle]\r
-\end{code}\r
-\r
-%************************************************************************\r
-%* *\r
-%* Manipulating FlatMonoBindInfo *\r
-%* *\r
-%************************************************************************\r
-\r
-During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.\r
-The @RenamedMonoBinds@ is always an empty bind, a pattern binding or\r
-a function binding, and has itself been dependency-analysed and\r
-renamed.\r
-\r
-\begin{code}\r
-type FlatMonoBindsInfo\r
- = (NameSet, -- Set of names defined in this vertex\r
- NameSet, -- Set of names used in this vertex\r
- RenamedMonoBinds,\r
- [RenamedSig]) -- Signatures, if any, for this vertex\r
-\r
-mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]\r
-\r
-mkEdges flat_info\r
- = [ (info, tag, dest_vertices (nameSetToList names_used))\r
- | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info\r
- ]\r
- where\r
- -- An edge (v,v') indicates that v depends on v'\r
- dest_vertices src_mentions = [ target_vertex\r
- | ((names_defined, _, _, _), target_vertex) <- flat_info,\r
- mentioned_name <- src_mentions,\r
- mentioned_name `elemNameSet` names_defined\r
- ]\r
-\end{code}\r
-\r
-\r
-%************************************************************************\r
-%* *\r
-\subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}\r
-%* *\r
-%************************************************************************\r
-\r
-@renameSigs@ checks for: (a)~more than one sig for one thing;\r
-(b)~signatures given for things not bound here; (c)~with suitably\r
-flaggery, that all top-level things have type signatures.\r
-\r
-At the moment we don't gather free-var info from the types in\r
-signatures. We'd only need this if we wanted to report unused tyvars.\r
-\r
-\begin{code}\r
-renameSigs :: Bool -- True => warn if (required) type signatures are missing.\r
- -> NameSet -- Set of names bound in this group\r
- -> (RdrName -> RnMS Name)\r
- -> [RdrNameSig]\r
- -> RnMS ([RenamedSig], FreeVars) -- List of Sig constructors\r
-\r
-renameSigs sigs_required binders lookup_occ_nm sigs\r
- = -- Rename the signatures\r
- mapFvRn (renameSig lookup_occ_nm) sigs `thenRn` \ (sigs', fvs) ->\r
-\r
- -- Check for (a) duplicate signatures\r
- -- (b) signatures for things not in this group\r
- -- (c) optionally, bindings with no signature\r
- let\r
- (goodies, dups) = removeDups cmp_sig (sigsForMe (not . isUnboundName) sigs')\r
- not_this_group = sigsForMe (not . (`elemNameSet` binders)) goodies\r
- type_sig_vars = [n | Sig n _ _ <- goodies]\r
- un_sigd_binders | sigs_required = nameSetToList binders `minusList` type_sig_vars\r
- | otherwise = []\r
- in\r
- mapRn_ dupSigDeclErr dups `thenRn_`\r
- mapRn_ unknownSigErr not_this_group `thenRn_`\r
- mapRn_ (addWarnRn.missingSigWarn) un_sigd_binders `thenRn_`\r
- returnRn (sigs', fvs) \r
- -- bad ones and all:\r
- -- we need bindings of *some* sort for every name\r
-\r
--- We use lookupOccRn in the signatures, which is a little bit unsatisfactory\r
--- because this won't work for:\r
--- instance Foo T where\r
--- {-# INLINE op #-}\r
--- Baz.op = ...\r
--- We'll just rename the INLINE prag to refer to whatever other 'op'\r
--- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)\r
--- Doesn't seem worth much trouble to sort this.\r
-\r
-renameSig lookup_occ_nm (Sig v ty src_loc)\r
- = pushSrcLocRn src_loc $\r
- lookup_occ_nm v `thenRn` \ new_v ->\r
- rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->\r
- returnRn (Sig new_v new_ty src_loc, fvs `addOneFV` new_v)\r
-\r
-renameSig _ (SpecInstSig ty src_loc)\r
- = pushSrcLocRn src_loc $\r
- rnHsSigType (text "A SPECIALISE instance pragma") ty `thenRn` \ (new_ty, fvs) ->\r
- returnRn (SpecInstSig new_ty src_loc, fvs)\r
-\r
-renameSig lookup_occ_nm (SpecSig v ty src_loc)\r
- = pushSrcLocRn src_loc $\r
- lookup_occ_nm v `thenRn` \ new_v ->\r
- rnHsSigType (quotes (ppr v)) ty `thenRn` \ (new_ty,fvs) ->\r
- returnRn (SpecSig new_v new_ty src_loc, fvs `addOneFV` new_v)\r
-\r
-renameSig lookup_occ_nm (InlineSig v src_loc)\r
- = pushSrcLocRn src_loc $\r
- lookup_occ_nm v `thenRn` \ new_v ->\r
- returnRn (InlineSig new_v src_loc, unitFV new_v)\r
-\r
-renameSig lookup_occ_nm (FixSig (FixitySig v fix src_loc))\r
- = pushSrcLocRn src_loc $\r
- lookup_occ_nm v `thenRn` \ new_v ->\r
- returnRn (FixSig (FixitySig new_v fix src_loc), unitFV new_v)\r
-\r
-renameSig lookup_occ_nm (NoInlineSig v src_loc)\r
- = pushSrcLocRn src_loc $\r
- lookup_occ_nm v `thenRn` \ new_v ->\r
- returnRn (NoInlineSig new_v src_loc, unitFV new_v)\r
-\end{code}\r
-\r
-Checking for distinct signatures; oh, so boring\r
-\r
-\begin{code}\r
-cmp_sig :: RenamedSig -> RenamedSig -> Ordering\r
-cmp_sig (Sig n1 _ _) (Sig n2 _ _) = n1 `compare` n2\r
-cmp_sig (InlineSig n1 _) (InlineSig n2 _) = n1 `compare` n2\r
-cmp_sig (NoInlineSig n1 _) (NoInlineSig n2 _) = n1 `compare` n2\r
-cmp_sig (SpecInstSig ty1 _) (SpecInstSig ty2 _) = cmpHsType compare ty1 ty2\r
-cmp_sig (SpecSig n1 ty1 _) (SpecSig n2 ty2 _) \r
- = -- may have many specialisations for one value;\r
- -- but not ones that are exactly the same...\r
- thenCmp (n1 `compare` n2) (cmpHsType compare ty1 ty2)\r
-\r
-cmp_sig other_1 other_2 -- Tags *must* be different\r
- | (sig_tag other_1) _LT_ (sig_tag other_2) = LT \r
- | otherwise = GT\r
-\r
-sig_tag (Sig n1 _ _) = (ILIT(1) :: FAST_INT)\r
-sig_tag (SpecSig n1 _ _) = ILIT(2)\r
-sig_tag (InlineSig n1 _) = ILIT(3)\r
-sig_tag (NoInlineSig n1 _) = ILIT(4)\r
-sig_tag (SpecInstSig _ _) = ILIT(5)\r
-sig_tag (FixSig _) = ILIT(6)\r
-sig_tag _ = panic# "tag(RnBinds)"\r
-\end{code}\r
-\r
-%************************************************************************\r
-%* *\r
-\subsection{Error messages}\r
-%* *\r
-%************************************************************************\r
-\r
-\begin{code}\r
-dupSigDeclErr (sig:sigs)\r
- = pushSrcLocRn loc $\r
- addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,\r
- ppr sig])\r
- where\r
- (what_it_is, loc) = sig_doc sig\r
-\r
-unknownSigErr sig\r
- = pushSrcLocRn loc $\r
- addErrRn (sep [ptext SLIT("Misplaced"),\r
- ptext what_it_is <> colon,\r
- ppr sig])\r
- where\r
- (what_it_is, loc) = sig_doc sig\r
-\r
-sig_doc (Sig _ _ loc) = (SLIT("type signature"),loc)\r
-sig_doc (ClassOpSig _ _ _ loc) = (SLIT("class-method type signature"), loc)\r
-sig_doc (SpecSig _ _ loc) = (SLIT("SPECIALISE pragma"),loc)\r
-sig_doc (InlineSig _ loc) = (SLIT("INLINE pragma"),loc)\r
-sig_doc (NoInlineSig _ loc) = (SLIT("NOINLINE pragma"),loc)\r
-sig_doc (SpecInstSig _ loc) = (SLIT("SPECIALISE instance pragma"),loc)\r
-sig_doc (FixSig (FixitySig _ _ loc)) = (SLIT("fixity declaration"), loc)\r
-\r
-missingSigWarn var\r
- = sep [ptext SLIT("definition but no type signature for"), quotes (ppr var)]\r
-\r
-methodBindErr mbind\r
- = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))\r
- 4 (ppr mbind)\r
-\end{code}\r
+%
+% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
+%
+\section[RnBinds]{Renaming and dependency analysis of bindings}
+
+This module does renaming and dependency analysis on value bindings in
+the abstract syntax. It does {\em not} do cycle-checks on class or
+type-synonym declarations; those cannot be done at this stage because
+they may be affected by renaming (which isn't fully worked out yet).
+
+\begin{code}
+module RnBinds (
+ rnTopMonoBinds, rnMonoBinds, rnMonoBindsAndThen,
+ rnMethodBinds, renameSigs, checkSigs, unknownSigErr
+ ) where
+
+#include "HsVersions.h"
+
+
+import HsSyn
+import HsBinds ( eqHsSig, hsSigDoc )
+import RdrHsSyn
+import RnHsSyn
+import TcRnMonad
+import RnTypes ( rnHsSigType, rnHsType, rnPat )
+import RnExpr ( rnMatch, rnGRHSs, checkPrecMatch )
+import RnEnv ( bindLocatedLocalsRn, lookupBndrRn, lookupInstDeclBndr,
+ lookupSigOccRn, bindPatSigTyVars, bindPatSigTyVarsFV,
+ bindLocalFixities,
+ warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
+ )
+import CmdLineOpts ( DynFlag(..) )
+import Digraph ( SCC(..), stronglyConnComp )
+import Name ( Name, nameOccName, nameSrcLoc )
+import NameSet
+import RdrName ( RdrName, rdrNameOcc )
+import BasicTypes ( RecFlag(..), TopLevelFlag(..), isTopLevel )
+import List ( unzip4 )
+import Outputable
+\end{code}
+
+-- ToDo: Put the annotations into the monad, so that they arrive in the proper
+-- place and can be used when complaining.
+
+The code tree received by the function @rnBinds@ contains definitions
+in where-clauses which are all apparently mutually recursive, but which may
+not really depend upon each other. For example, in the top level program
+\begin{verbatim}
+f x = y where a = x
+ y = x
+\end{verbatim}
+the definitions of @a@ and @y@ do not depend on each other at all.
+Unfortunately, the typechecker cannot always check such definitions.
+\footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
+definitions. In Proceedings of the International Symposium on Programming,
+Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
+However, the typechecker usually can check definitions in which only the
+strongly connected components have been collected into recursive bindings.
+This is precisely what the function @rnBinds@ does.
+
+ToDo: deal with case where a single monobinds binds the same variable
+twice.
+
+The vertag tag is a unique @Int@; the tags only need to be unique
+within one @MonoBinds@, so that unique-Int plumbing is done explicitly
+(heavy monad machinery not needed).
+
+
+%************************************************************************
+%* *
+%* naming conventions *
+%* *
+%************************************************************************
+
+\subsection[name-conventions]{Name conventions}
+
+The basic algorithm involves walking over the tree and returning a tuple
+containing the new tree plus its free variables. Some functions, such
+as those walking polymorphic bindings (HsBinds) and qualifier lists in
+list comprehensions (@Quals@), return the variables bound in local
+environments. These are then used to calculate the free variables of the
+expression evaluated in these environments.
+
+Conventions for variable names are as follows:
+\begin{itemize}
+\item
+new code is given a prime to distinguish it from the old.
+
+\item
+a set of variables defined in @Exp@ is written @dvExp@
+
+\item
+a set of variables free in @Exp@ is written @fvExp@
+\end{itemize}
+
+%************************************************************************
+%* *
+%* analysing polymorphic bindings (HsBinds, Bind, MonoBinds) *
+%* *
+%************************************************************************
+
+\subsubsection[dep-HsBinds]{Polymorphic bindings}
+
+Non-recursive expressions are reconstructed without any changes at top
+level, although their component expressions may have to be altered.
+However, non-recursive expressions are currently not expected as
+\Haskell{} programs, and this code should not be executed.
+
+Monomorphic bindings contain information that is returned in a tuple
+(a @FlatMonoBinds@) containing:
+
+\begin{enumerate}
+\item
+a unique @Int@ that serves as the ``vertex tag'' for this binding.
+
+\item
+the name of a function or the names in a pattern. These are a set
+referred to as @dvLhs@, the defined variables of the left hand side.
+
+\item
+the free variables of the body. These are referred to as @fvBody@.
+
+\item
+the definition's actual code. This is referred to as just @code@.
+\end{enumerate}
+
+The function @nonRecDvFv@ returns two sets of variables. The first is
+the set of variables defined in the set of monomorphic bindings, while the
+second is the set of free variables in those bindings.
+
+The set of variables defined in a non-recursive binding is just the
+union of all of them, as @union@ removes duplicates. However, the
+free variables in each successive set of cumulative bindings is the
+union of those in the previous set plus those of the newest binding after
+the defined variables of the previous set have been removed.
+
+@rnMethodBinds@ deals only with the declarations in class and
+instance declarations. It expects only to see @FunMonoBind@s, and
+it expects the global environment to contain bindings for the binders
+(which are all class operations).
+
+%************************************************************************
+%* *
+\subsubsection{ Top-level bindings}
+%* *
+%************************************************************************
+
+@rnTopMonoBinds@ assumes that the environment already
+contains bindings for the binders of this particular binding.
+
+\begin{code}
+rnTopMonoBinds :: RdrNameMonoBinds
+ -> [RdrNameSig]
+ -> RnM (RenamedHsBinds, DefUses)
+
+-- The binders of the binding are in scope already;
+-- the top level scope resoluttion does that
+
+rnTopMonoBinds mbinds sigs
+ = bindPatSigTyVars (collectSigTysFromMonoBinds mbinds) $ \ _ ->
+ -- Hmm; by analogy with Ids, this doesn't look right
+ -- Top-level bound type vars should really scope over
+ -- everything, but we only scope them over the other bindings
+
+ rnMonoBinds TopLevel mbinds sigs
+\end{code}
+
+
+%************************************************************************
+%* *
+%* Nested binds
+%* *
+%************************************************************************
+
+\begin{code}
+rnMonoBindsAndThen :: RdrNameMonoBinds
+ -> [RdrNameSig]
+ -> (RenamedHsBinds -> RnM (result, FreeVars))
+ -> RnM (result, FreeVars)
+
+rnMonoBindsAndThen mbinds sigs thing_inside -- Non-empty monobinds
+ = -- Extract all the binders in this group, and extend the
+ -- current scope, inventing new names for the new binders
+ -- This also checks that the names form a set
+ bindLocatedLocalsRn doc mbinders_w_srclocs $ \ _ ->
+ bindPatSigTyVarsFV (collectSigTysFromMonoBinds mbinds) $
+
+ -- Then install local fixity declarations
+ -- Notice that they scope over thing_inside too
+ bindLocalFixities [sig | FixSig sig <- sigs ] $
+
+ -- Do the business
+ rnMonoBinds NotTopLevel mbinds sigs `thenM` \ (binds, bind_dus) ->
+
+ -- Now do the "thing inside"
+ thing_inside binds `thenM` \ (result,result_fvs) ->
+
+ -- Final error checking
+ let
+ all_uses = duUses bind_dus `plusFV` result_fvs
+ bndrs = duDefs bind_dus
+ real_uses = findUses bind_dus result_fvs
+ unused_bndrs = nameSetToList (bndrs `minusNameSet` all_uses)
+ in
+ warnUnusedLocalBinds unused_bndrs `thenM_`
+
+ returnM (result, all_uses `minusNameSet` bndrs)
+ -- It's important to return all the uses, not the 'real uses' used for
+ -- warning about unused bindings. Otherwise consider:
+ -- x = 3
+ -- y = let p = x in 'x'
+ -- If we don't "see" the dependency of 'y' on 'x', we may put the
+ -- bindings in the wrong order, and the type checker will complain
+ -- that x isn't in scope
+ where
+ mbinders_w_srclocs = collectLocatedMonoBinders mbinds
+ doc = text "In the binding group for:"
+ <+> pprWithCommas ppr (map fst mbinders_w_srclocs)
+\end{code}
+
+
+%************************************************************************
+%* *
+\subsubsection{ MonoBinds -- the main work is done here}
+%* *
+%************************************************************************
+
+@rnMonoBinds@ is used by {\em both} top-level and nested bindings.
+It assumes that all variables bound in this group are already in scope.
+This is done {\em either} by pass 3 (for the top-level bindings),
+{\em or} by @rnMonoBinds@ (for the nested ones).
+
+\begin{code}
+rnMonoBinds :: TopLevelFlag
+ -> RdrNameMonoBinds
+ -> [RdrNameSig]
+ -> RnM (RenamedHsBinds, DefUses)
+
+-- Assumes the binders of the binding are in scope already
+
+rnMonoBinds top_lvl mbinds sigs
+ = renameSigs sigs `thenM` \ siglist ->
+
+ -- Rename the bindings, returning a MonoBindsInfo
+ -- which is a list of indivisible vertices so far as
+ -- the strongly-connected-components (SCC) analysis is concerned
+ flattenMonoBinds siglist mbinds `thenM` \ mbinds_info ->
+
+ -- Do the SCC analysis
+ let
+ scc_result = rnSCC mbinds_info
+ (binds_s, bind_dus_s) = unzip (map reconstructCycle scc_result)
+ bind_dus = mkDUs bind_dus_s
+ final_binds = foldr ThenBinds EmptyBinds binds_s
+ binders = duDefs bind_dus
+ in
+ -- Check for duplicate or mis-placed signatures
+ checkSigs (okBindSig binders) siglist `thenM_`
+
+ -- Warn about missing signatures,
+ -- but only at top level, and not in interface mode
+ -- (The latter is important when renaming bindings from 'deriving' clauses.)
+ getModeRn `thenM` \ mode ->
+ doptM Opt_WarnMissingSigs `thenM` \ warn_missing_sigs ->
+ (if isTopLevel top_lvl &&
+ warn_missing_sigs &&
+ not (isInterfaceMode mode)
+ then let
+ type_sig_vars = [n | Sig n _ _ <- siglist]
+ un_sigd_binders = filter (not . (`elem` type_sig_vars))
+ (nameSetToList binders)
+ in
+ mappM_ missingSigWarn un_sigd_binders
+ else
+ returnM ()
+ ) `thenM_`
+
+ returnM (final_binds, bind_dus `plusDU` usesOnly (hsSigsFVs siglist))
+\end{code}
+
+@flattenMonoBinds@ is ever-so-slightly magical in that it sticks
+unique ``vertex tags'' on its output; minor plumbing required.
+
+\begin{code}
+flattenMonoBinds :: [RenamedSig] -- Signatures
+ -> RdrNameMonoBinds
+ -> RnM [FlatMonoBinds]
+
+flattenMonoBinds sigs EmptyMonoBinds = returnM []
+
+flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
+ = flattenMonoBinds sigs bs1 `thenM` \ flat1 ->
+ flattenMonoBinds sigs bs2 `thenM` \ flat2 ->
+ returnM (flat1 ++ flat2)
+
+flattenMonoBinds sigs (PatMonoBind pat grhss locn)
+ = addSrcLoc locn $
+ rnPat pat `thenM` \ (pat', pat_fvs) ->
+
+ -- Find which things are bound in this group
+ let
+ names_bound_here = mkNameSet (collectPatBinders pat')
+ in
+ sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
+ rnGRHSs PatBindRhs grhss `thenM` \ (grhss', fvs) ->
+ returnM
+ [(names_bound_here, fvs `plusFV` pat_fvs,
+ PatMonoBind pat' grhss' locn, sigs_for_me
+ )]
+
+flattenMonoBinds sigs (FunMonoBind name inf matches locn)
+ = addSrcLoc locn $
+ lookupBndrRn name `thenM` \ new_name ->
+ let
+ names_bound_here = unitNameSet new_name
+ in
+ sigsForMe names_bound_here sigs `thenM` \ sigs_for_me ->
+ mapFvRn (rnMatch (FunRhs new_name)) matches `thenM` \ (new_matches, fvs) ->
+ mappM_ (checkPrecMatch inf new_name) new_matches `thenM_`
+ returnM
+ [(unitNameSet new_name, fvs,
+ FunMonoBind new_name inf new_matches locn, sigs_for_me
+ )]
+
+
+sigsForMe names_bound_here sigs
+ = foldlM check [] (filter (sigForThisGroup names_bound_here) sigs)
+ where
+ check sigs sig = case filter (eqHsSig sig) sigs of
+ [] -> returnM (sig:sigs)
+ other -> dupSigDeclErr sig `thenM_`
+ returnM sigs
+\end{code}
+
+
+@rnMethodBinds@ is used for the method bindings of a class and an instance
+declaration. Like @rnMonoBinds@ but without dependency analysis.
+
+NOTA BENE: we record each {\em binder} of a method-bind group as a free variable.
+That's crucial when dealing with an instance decl:
+\begin{verbatim}
+ instance Foo (T a) where
+ op x = ...
+\end{verbatim}
+This might be the {\em sole} occurrence of @op@ for an imported class @Foo@,
+and unless @op@ occurs we won't treat the type signature of @op@ in the class
+decl for @Foo@ as a source of instance-decl gates. But we should! Indeed,
+in many ways the @op@ in an instance decl is just like an occurrence, not
+a binder.
+
+\begin{code}
+rnMethodBinds :: Name -- Class name
+ -> [Name] -- Names for generic type variables
+ -> RdrNameMonoBinds
+ -> RnM (RenamedMonoBinds, FreeVars)
+
+rnMethodBinds cls gen_tyvars EmptyMonoBinds = returnM (EmptyMonoBinds, emptyFVs)
+
+rnMethodBinds cls gen_tyvars (AndMonoBinds mb1 mb2)
+ = rnMethodBinds cls gen_tyvars mb1 `thenM` \ (mb1', fvs1) ->
+ rnMethodBinds cls gen_tyvars mb2 `thenM` \ (mb2', fvs2) ->
+ returnM (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
+
+rnMethodBinds cls gen_tyvars (FunMonoBind name inf matches locn)
+ = addSrcLoc locn $
+
+ lookupInstDeclBndr cls name `thenM` \ sel_name ->
+ -- We use the selector name as the binder
+
+ mapFvRn (rn_match sel_name) matches `thenM` \ (new_matches, fvs) ->
+ mappM_ (checkPrecMatch inf sel_name) new_matches `thenM_`
+ returnM (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
+ where
+ -- Gruesome; bring into scope the correct members of the generic type variables
+ -- See comments in RnSource.rnSourceDecl(ClassDecl)
+ rn_match sel_name match@(Match (TypePat ty : _) _ _)
+ = extendTyVarEnvFVRn gen_tvs $
+ rnMatch (FunRhs sel_name) match
+ where
+ tvs = map rdrNameOcc (extractHsTyRdrNames ty)
+ gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
+
+ rn_match sel_name match = rnMatch (FunRhs sel_name) match
+
+
+-- Can't handle method pattern-bindings which bind multiple methods.
+rnMethodBinds cls gen_tyvars mbind@(PatMonoBind other_pat _ locn)
+ = addSrcLoc locn (addErr (methodBindErr mbind)) `thenM_`
+ returnM (EmptyMonoBinds, emptyFVs)
+\end{code}
+
+
+%************************************************************************
+%* *
+ Strongly connected components
+
+%* *
+%************************************************************************
+
+During analysis a @MonoBinds@ is flattened to a @FlatMonoBinds@.
+The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
+a function binding, and has itself been dependency-analysed and
+renamed.
+
+\begin{code}
+type FlatMonoBinds = (Defs, Uses, RenamedMonoBinds, [RenamedSig])
+ -- Signatures, if any, for this vertex
+
+rnSCC :: [FlatMonoBinds] -> [SCC FlatMonoBinds]
+rnSCC nodes = stronglyConnComp (mkEdges nodes)
+
+type VertexTag = Int
+
+mkEdges :: [FlatMonoBinds] -> [(FlatMonoBinds, VertexTag, [VertexTag])]
+ -- We keep the uses with the binding,
+ -- so we can track unused bindings better
+mkEdges nodes
+ = [ (thing, tag, dest_vertices uses)
+ | (thing@(_, uses, _, _), tag) <- tagged_nodes
+ ]
+ where
+ tagged_nodes = nodes `zip` [0::VertexTag ..]
+
+ -- An edge (v,v') indicates that v depends on v'
+ dest_vertices uses = [ target_vertex
+ | ((defs, _, _, _), target_vertex) <- tagged_nodes,
+ defs `intersectsNameSet` uses
+ ]
+
+reconstructCycle :: SCC FlatMonoBinds -> (RenamedHsBinds, (Defs,Uses))
+reconstructCycle (AcyclicSCC (defs, uses, binds, sigs))
+ = (MonoBind binds sigs NonRecursive, (defs, uses))
+reconstructCycle (CyclicSCC cycle)
+ = (MonoBind this_gp_binds this_gp_sigs Recursive,
+ (unionManyNameSets defs_s, unionManyNameSets uses_s))
+ where
+ (defs_s, uses_s, binds_s, sigs_s) = unzip4 cycle
+ this_gp_binds = foldr1 AndMonoBinds binds_s
+ this_gp_sigs = foldr1 (++) sigs_s
+\end{code}
+
+
+%************************************************************************
+%* *
+\subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
+%* *
+%************************************************************************
+
+@renameSigs@ checks for:
+\begin{enumerate}
+\item more than one sig for one thing;
+\item signatures given for things not bound here;
+\item with suitably flaggery, that all top-level things have type signatures.
+\end{enumerate}
+%
+At the moment we don't gather free-var info from the types in
+signatures. We'd only need this if we wanted to report unused tyvars.
+
+\begin{code}
+checkSigs :: (RenamedSig -> Bool) -- OK-sig predicbate
+ -> [RenamedSig]
+ -> RnM ()
+checkSigs ok_sig sigs
+ -- Check for (a) duplicate signatures
+ -- (b) signatures for things not in this group
+ -- Well, I can't see the check for (a)... ToDo!
+ = mappM_ unknownSigErr bad_sigs
+ where
+ bad_sigs = filter (not . ok_sig) sigs
+
+-- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
+-- because this won't work for:
+-- instance Foo T where
+-- {-# INLINE op #-}
+-- Baz.op = ...
+-- We'll just rename the INLINE prag to refer to whatever other 'op'
+-- is in scope. (I'm assuming that Baz.op isn't in scope unqualified.)
+-- Doesn't seem worth much trouble to sort this.
+
+renameSigs :: [Sig RdrName] -> RnM [Sig Name]
+renameSigs sigs = mappM renameSig (filter (not . isFixitySig) sigs)
+ -- Remove fixity sigs which have been dealt with already
+
+renameSig :: Sig RdrName -> RnM (Sig Name)
+-- ClassOpSig, FixitSig is renamed elsewhere.
+renameSig (Sig v ty src_loc)
+ = addSrcLoc src_loc $
+ lookupSigOccRn v `thenM` \ new_v ->
+ rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
+ returnM (Sig new_v new_ty src_loc)
+
+renameSig (SpecInstSig ty src_loc)
+ = addSrcLoc src_loc $
+ rnHsType (text "A SPECIALISE instance pragma") ty `thenM` \ new_ty ->
+ returnM (SpecInstSig new_ty src_loc)
+
+renameSig (SpecSig v ty src_loc)
+ = addSrcLoc src_loc $
+ lookupSigOccRn v `thenM` \ new_v ->
+ rnHsSigType (quotes (ppr v)) ty `thenM` \ new_ty ->
+ returnM (SpecSig new_v new_ty src_loc)
+
+renameSig (InlineSig b v p src_loc)
+ = addSrcLoc src_loc $
+ lookupSigOccRn v `thenM` \ new_v ->
+ returnM (InlineSig b new_v p src_loc)
+\end{code}
+
+
+%************************************************************************
+%* *
+\subsection{Error messages}
+%* *
+%************************************************************************
+
+\begin{code}
+dupSigDeclErr sig
+ = addSrcLoc loc $
+ addErr (sep [ptext SLIT("Duplicate") <+> what_it_is <> colon,
+ ppr sig])
+ where
+ (what_it_is, loc) = hsSigDoc sig
+
+unknownSigErr sig
+ = addSrcLoc loc $
+ addErr (sep [ptext SLIT("Misplaced") <+> what_it_is <> colon,
+ ppr sig])
+ where
+ (what_it_is, loc) = hsSigDoc sig
+
+missingSigWarn var
+ = addSrcLoc (nameSrcLoc var) $
+ addWarn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
+
+methodBindErr mbind
+ = hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
+ 4 (ppr mbind)
+\end{code}