ghc/compiler/rename/RnBinds.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   3 %
   4 \section[RnBinds]{Renaming and dependency analysis of bindings}
   5
   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).
  10
  11 \begin{code}
  12 module RnBinds (
  13         rnTopBinds, rnBinds, rnBindsAndThen,
  14         rnMethodBinds, renameSigs, checkSigs
  15    ) where
  16
  17 #include "HsVersions.h"
  18
  19
  20 import HsSyn
  21 import HsBinds          ( hsSigDoc, eqHsSig )
  22 import RdrHsSyn
  23 import RnHsSyn
  24 import TcRnMonad
  25 import RnTypes          ( rnHsSigType, rnLHsType, rnLPat )
  26 import RnExpr           ( rnMatch, rnGRHSs, checkPrecMatch )
  27 import RnEnv            ( bindLocatedLocalsRn, lookupLocatedBndrRn,
  28                           lookupLocatedInstDeclBndr,
  29                           lookupLocatedSigOccRn, bindPatSigTyVars, bindPatSigTyVarsFV,
  30                           bindLocalFixities,
  31                           warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
  32                         )
  33 import CmdLineOpts      ( DynFlag(..) )
  34 import Digraph          ( SCC(..), stronglyConnComp )
  35 import Name             ( Name, nameOccName, nameSrcLoc )
  36 import NameSet
  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 )
  42 import Bag
  43 import Outputable
  44
  45 import Monad            ( foldM )
  46
  47 import SrcLoc (getLoc) -- tmp
  48 \end{code}
  49
  50 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
  51 -- place and can be used when complaining.
  52
  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
  56 \begin{verbatim}
  57 f x = y where a = x
  58               y = x
  59 \end{verbatim}
  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.
  68
  69 ToDo: deal with case where a single monobinds binds the same variable
  70 twice.
  71
  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).
  75
  76
  77 %************************************************************************
  78 %*                                                                      *
  79 %* naming conventions                                                   *
  80 %*                                                                      *
  81 %************************************************************************
  82
  83 \subsection[name-conventions]{Name conventions}
  84
  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.
  91
  92 Conventions for variable names are as follows:
  93 \begin{itemize}
  94 \item
  95 new code is given a prime to distinguish it from the old.
  96
  97 \item
  98 a set of variables defined in @Exp@ is written @dvExp@
  99
 100 \item
 101 a set of variables free in @Exp@ is written @fvExp@
 102 \end{itemize}
 103
 104 %************************************************************************
 105 %*                                                                      *
 106 %* analysing polymorphic bindings (HsBindGroup, HsBind)
 107 %*                                                                      *
 108 %************************************************************************
 109
 110 \subsubsection[dep-HsBinds]{Polymorphic bindings}
 111
 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.
 116
 117 Monomorphic bindings contain information that is returned in a tuple
 118 (a @FlatMonoBinds@) containing:
 119
 120 \begin{enumerate}
 121 \item
 122 a unique @Int@ that serves as the ``vertex tag'' for this binding.
 123
 124 \item
 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.
 127
 128 \item
 129 the free variables of the body. These are referred to as @fvBody@.
 130
 131 \item
 132 the definition's actual code. This is referred to as just @code@.
 133 \end{enumerate}
 134
 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.
 138
 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.
 144
 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).
 149
 150 %************************************************************************
 151 %*                                                                      *
 152 \subsubsection{ Top-level bindings}
 153 %*                                                                      *
 154 %************************************************************************
 155
 156 @rnTopMonoBinds@ assumes that the environment already
 157 contains bindings for the binders of this particular binding.
 158
 159 \begin{code}
 160 rnTopBinds :: Bag (LHsBind RdrName)
 161            -> [LSig RdrName]
 162            -> RnM ([HsBindGroup Name], DefUses)
 163
 164 -- The binders of the binding are in scope already;
 165 -- the top level scope resolution does that
 166
 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
 172
 173     rnBinds TopLevel mbinds sigs
 174 \end{code}
 175
 176
 177 %************************************************************************
 178 %*                                                                      *
 179 %*              Nested binds
 180 %*                                                                      *
 181 %************************************************************************
 182
 183 \begin{code}
 184 rnBindsAndThen :: Bag (LHsBind RdrName)
 185                -> [LSig RdrName]
 186                -> ([HsBindGroup Name] -> RnM (result, FreeVars))
 187                -> RnM (result, FreeVars)
 188
 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))    $
 195
 196         -- Then install local fixity declarations
 197         -- Notice that they scope over thing_inside too
 198     bindLocalFixities [sig | L _ (FixSig sig) <- sigs ]         $
 199
 200         -- Do the business
 201     rnBinds NotTopLevel mbinds sigs     `thenM` \ (binds, bind_dus) ->
 202
 203         -- Now do the "thing inside"
 204     thing_inside binds                  `thenM` \ (result,result_fvs) ->
 205
 206         -- Final error checking
 207     let
 208         all_uses     = duUses bind_dus `plusFV` result_fvs
 209         bndrs        = duDefs bind_dus
 210         unused_bndrs = nameSetToList (bndrs `minusNameSet` all_uses)
 211     in
 212     warnUnusedLocalBinds unused_bndrs   `thenM_`
 213
 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:
 217         --      x = 3
 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
 222   where
 223     mbinders_w_srclocs = collectHsBindLocatedBinders mbinds
 224     doc = text "In the binding group for:"
 225           <+> pprWithCommas ppr (map unLoc mbinders_w_srclocs)
 226 \end{code}
 227
 228
 229 %************************************************************************
 230 %*                                                                      *
 231 \subsubsection{rnBinds -- the main work is done here}
 232 %*                                                                      *
 233 %************************************************************************
 234
 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).
 239
 240 \begin{code}
 241 rnBinds :: TopLevelFlag
 242         -> Bag (LHsBind RdrName)
 243         -> [LSig RdrName]
 244         -> RnM ([HsBindGroup Name], DefUses)
 245
 246 -- Assumes the binders of the binding are in scope already
 247
 248 rnBinds top_lvl mbinds sigs
 249  =  renameSigs sigs                     `thenM` \ siglist ->
 250
 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 ->
 255
 256          -- Do the SCC analysis
 257     let
 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
 262     in
 263         -- Check for duplicate or mis-placed signatures
 264     checkSigs (okBindSig binders) siglist       `thenM_`
 265
 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 &&
 271          warn_missing_sigs
 272      then let
 273             type_sig_vars   = [ unLoc n | L _ (Sig n _) <- siglist]
 274             un_sigd_binders = filter (not . (`elem` type_sig_vars))
 275                                      (nameSetToList binders)
 276           in
 277           mappM_ missingSigWarn un_sigd_binders
 278      else
 279         returnM ()
 280     )                                           `thenM_`
 281
 282     returnM (groups, bind_dus `plusDU` usesOnly (hsSigsFVs siglist))
 283 \end{code}
 284
 285 @mkBindVertices@ is ever-so-slightly magical in that it sticks
 286 unique ``vertex tags'' on its output; minor plumbing required.
 287
 288 \begin{code}
 289 mkBindVertices :: [LSig Name]           -- Signatures
 290                -> Bag (LHsBind RdrName)
 291                -> RnM [BindVertex]
 292 mkBindVertices sigs = mapM (mkBindVertex sigs) . bagToList
 293
 294 mkBindVertex :: [LSig Name] -> LHsBind RdrName -> RnM BindVertex
 295 mkBindVertex sigs (L loc (PatBind pat grhss))
 296   = addSrcSpan loc $
 297     rnLPat pat                          `thenM` \ (pat', pat_fvs) ->
 298
 299          -- Find which things are bound in this group
 300     let
 301         names_bound_here = mkNameSet (collectPatBinders pat')
 302     in
 303     sigsForMe names_bound_here sigs     `thenM` \ sigs_for_me ->
 304     rnGRHSs PatBindRhs grhss            `thenM` \ (grhss', fvs) ->
 305     returnM
 306         (names_bound_here, fvs `plusFV` pat_fvs,
 307           L loc (PatBind pat' grhss'), sigs_for_me
 308         )
 309
 310 mkBindVertex sigs (L loc (FunBind name inf matches))
 311   = addSrcSpan loc $
 312     lookupLocatedBndrRn name                            `thenM` \ new_name ->
 313     let
 314         plain_name = unLoc new_name
 315         names_bound_here = unitNameSet plain_name
 316     in
 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_`
 320     returnM
 321       (unitNameSet plain_name, fvs,
 322         L loc (FunBind new_name inf new_matches), sigs_for_me
 323       )
 324
 325 sigsForMe names_bound_here sigs
 326   = foldlM check [] (filter (sigForThisGroup names_bound_here) sigs)
 327   where
 328         -- sigForThisGroup only returns signatures for
 329         -- which sigName returns a Just
 330     eq sig1 sig2 = eqHsSig (unLoc sig1) (unLoc sig2)
 331
 332     check sigs sig = case filter (eq sig) sigs of
 333                         []    -> returnM (sig:sigs)
 334                         other -> dupSigDeclErr sig other        `thenM_`
 335                                  returnM sigs
 336 \end{code}
 337
 338
 339 @rnMethodBinds@ is used for the method bindings of a class and an instance
 340 declaration.   Like @rnBinds@ but without dependency analysis.
 341
 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:
 344 \begin{verbatim}
 345         instance Foo (T a) where
 346            op x = ...
 347 \end{verbatim}
 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
 352 a binder.
 353
 354 \begin{code}
 355 rnMethodBinds :: Name                   -- Class name
 356               -> [Name]                 -- Names for generic type variables
 357               -> (LHsBinds RdrName)
 358               -> RnM (LHsBinds Name, FreeVars)
 359
 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)
 365
 366
 367 rnMethodBind cls gen_tyvars (L loc (FunBind name inf matches))
 368   =  addSrcSpan loc $
 369      lookupLocatedInstDeclBndr cls name                 `thenM` \ sel_name ->
 370      let plain_name = unLoc sel_name in
 371         -- We use the selector name as the binder
 372
 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)
 376   where
 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
 382         where
 383           tvs     = map (rdrNameOcc.unLoc) (extractHsTyRdrTyVars ty)
 384           gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
 385
 386     rn_match sel_name match = rnMatch (FunRhs sel_name) match
 387
 388
 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)
 393 \end{code}
 394
 395
 396 %************************************************************************
 397 %*                                                                      *
 398         Strongly connected components
 399 %*                                                                      *
 400 %************************************************************************
 401
 402 \begin{code}
 403 type BindVertex = (Defs, Uses, LHsBind Name, [LSig Name])
 404                         -- Signatures, if any, for this vertex
 405
 406 rnSCC :: [BindVertex] -> [SCC BindVertex]
 407 rnSCC nodes = stronglyConnComp (mkEdges nodes)
 408
 409 type VertexTag  = Int
 410
 411 mkEdges :: [BindVertex] -> [(BindVertex, VertexTag, [VertexTag])]
 412         -- We keep the uses with the binding,
 413         -- so we can track unused bindings better
 414 mkEdges nodes
 415   = [ (thing, tag, dest_vertices uses)
 416     | (thing@(_, uses, _, _), tag) <- tagged_nodes
 417     ]
 418   where
 419     tagged_nodes = nodes `zip` [0::VertexTag ..]
 420
 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
 425                          ]
 426
 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))
 433   where
 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
 437 \end{code}
 438
 439
 440 %************************************************************************
 441 %*                                                                      *
 442 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
 443 %*                                                                      *
 444 %************************************************************************
 445
 446 @renameSigs@ checks for:
 447 \begin{enumerate}
 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.
 451 \end{enumerate}
 452 %
 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.
 455
 456 \begin{code}
 457 checkSigs :: (LSig Name -> Bool)        -- OK-sig predicbate
 458           -> [LSig Name]
 459           -> RnM ()
 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)
 465   where
 466     bad sig = not (ok_sig sig) &&
 467               case sigName sig of
 468                 Just n | isUnboundName n -> False
 469                                 -- Don't complain about an unbound name again
 470                 other                    -> True
 471
 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
 475 --        {-# INLINE op #-}
 476 --        Baz.op = ...
 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.
 480
 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
 484
 485 renameSig :: Sig RdrName -> RnM (Sig Name)
 486 -- FixitSig is renamed elsewhere.
 487 renameSig (Sig v ty)
 488   = lookupLocatedSigOccRn v                     `thenM` \ new_v ->
 489     rnHsSigType (quotes (ppr v)) ty             `thenM` \ new_ty ->
 490     returnM (Sig new_v new_ty)
 491
 492 renameSig (SpecInstSig ty)
 493   = rnLHsType (text "A SPECIALISE instance pragma") ty `thenM` \ new_ty ->
 494     returnM (SpecInstSig new_ty)
 495
 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)
 500
 501 renameSig (InlineSig b v p)
 502   = lookupLocatedSigOccRn v             `thenM` \ new_v ->
 503     returnM (InlineSig b new_v p)
 504 \end{code}
 505
 506
 507 %************************************************************************
 508 %*                                                                      *
 509 \subsection{Error messages}
 510 %*                                                                      *
 511 %************************************************************************
 512
 513 \begin{code}
 514 dupSigDeclErr (L loc sig) sigs
 515   = addErrAt loc $
 516         vcat [ptext SLIT("Duplicate") <+> what_it_is <> colon,
 517               nest 2 (vcat (map ppr_sig (L loc sig:sigs)))]
 518   where
 519     what_it_is = hsSigDoc sig
 520     ppr_sig (L loc sig) = ppr loc <> colon <+> ppr sig
 521
 522 unknownSigErr (L loc sig)
 523   = addErrAt loc $
 524         sep [ptext SLIT("Misplaced") <+> what_it_is <> colon, ppr sig]
 525   where
 526     what_it_is = hsSigDoc sig
 527
 528 missingSigWarn var
 529   = addWarnAt (mkSrcSpan loc loc) $
 530       sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)]
 531   where
 532     loc = nameSrcLoc var  -- TODO: make a proper span
 533
 534 methodBindErr mbind
 535  =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
 536        4 (ppr mbind)
 537 \end{code}