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         rnTopMonoBinds, rnMonoBinds, rnMethodBinds,
  14         renameSigs, renameSigsFVs, unknownSigErr
  15    ) where
  16
  17 #include "HsVersions.h"
  18
  19
  20 import HsSyn
  21 import HsBinds          ( eqHsSig, sigName, hsSigDoc )
  22 import RdrHsSyn
  23 import RnHsSyn
  24 import TcRnMonad
  25 import RnTypes          ( rnHsSigType, rnHsType )
  26 import RnExpr           ( rnMatch, rnGRHSs, rnPat, checkPrecMatch )
  27 import RnEnv            ( bindLocatedLocalsRn, lookupBndrRn, lookupInstDeclBndr,
  28                           lookupSigOccRn, bindPatSigTyVars, bindLocalFixities,
  29                           warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
  30                         )
  31 import CmdLineOpts      ( DynFlag(..) )
  32 import Digraph          ( stronglyConnComp, SCC(..) )
  33 import Name             ( Name, nameOccName, nameSrcLoc )
  34 import NameSet
  35 import RdrName          ( RdrName, rdrNameOcc )
  36 import BasicTypes       ( RecFlag(..), FixitySig(..) )
  37 import List             ( partition )
  38 import Outputable
  39 import PrelNames        ( isUnboundName )
  40 \end{code}
  41
  42 -- ToDo: Put the annotations into the monad, so that they arrive in the proper
  43 -- place and can be used when complaining.
  44
  45 The code tree received by the function @rnBinds@ contains definitions
  46 in where-clauses which are all apparently mutually recursive, but which may
  47 not really depend upon each other. For example, in the top level program
  48 \begin{verbatim}
  49 f x = y where a = x
  50               y = x
  51 \end{verbatim}
  52 the definitions of @a@ and @y@ do not depend on each other at all.
  53 Unfortunately, the typechecker cannot always check such definitions.
  54 \footnote{Mycroft, A. 1984. Polymorphic type schemes and recursive
  55 definitions. In Proceedings of the International Symposium on Programming,
  56 Toulouse, pp. 217-39. LNCS 167. Springer Verlag.}
  57 However, the typechecker usually can check definitions in which only the
  58 strongly connected components have been collected into recursive bindings.
  59 This is precisely what the function @rnBinds@ does.
  60
  61 ToDo: deal with case where a single monobinds binds the same variable
  62 twice.
  63
  64 The vertag tag is a unique @Int@; the tags only need to be unique
  65 within one @MonoBinds@, so that unique-Int plumbing is done explicitly
  66 (heavy monad machinery not needed).
  67
  68 \begin{code}
  69 type VertexTag  = Int
  70 \end{code}
  71
  72 %************************************************************************
  73 %*                                                                      *
  74 %* naming conventions                                                   *
  75 %*                                                                      *
  76 %************************************************************************
  77
  78 \subsection[name-conventions]{Name conventions}
  79
  80 The basic algorithm involves walking over the tree and returning a tuple
  81 containing the new tree plus its free variables. Some functions, such
  82 as those walking polymorphic bindings (HsBinds) and qualifier lists in
  83 list comprehensions (@Quals@), return the variables bound in local
  84 environments. These are then used to calculate the free variables of the
  85 expression evaluated in these environments.
  86
  87 Conventions for variable names are as follows:
  88 \begin{itemize}
  89 \item
  90 new code is given a prime to distinguish it from the old.
  91
  92 \item
  93 a set of variables defined in @Exp@ is written @dvExp@
  94
  95 \item
  96 a set of variables free in @Exp@ is written @fvExp@
  97 \end{itemize}
  98
  99 %************************************************************************
 100 %*                                                                      *
 101 %* analysing polymorphic bindings (HsBinds, Bind, MonoBinds)            *
 102 %*                                                                      *
 103 %************************************************************************
 104
 105 \subsubsection[dep-HsBinds]{Polymorphic bindings}
 106
 107 Non-recursive expressions are reconstructed without any changes at top
 108 level, although their component expressions may have to be altered.
 109 However, non-recursive expressions are currently not expected as
 110 \Haskell{} programs, and this code should not be executed.
 111
 112 Monomorphic bindings contain information that is returned in a tuple
 113 (a @FlatMonoBindsInfo@) containing:
 114
 115 \begin{enumerate}
 116 \item
 117 a unique @Int@ that serves as the ``vertex tag'' for this binding.
 118
 119 \item
 120 the name of a function or the names in a pattern. These are a set
 121 referred to as @dvLhs@, the defined variables of the left hand side.
 122
 123 \item
 124 the free variables of the body. These are referred to as @fvBody@.
 125
 126 \item
 127 the definition's actual code. This is referred to as just @code@.
 128 \end{enumerate}
 129
 130 The function @nonRecDvFv@ returns two sets of variables. The first is
 131 the set of variables defined in the set of monomorphic bindings, while the
 132 second is the set of free variables in those bindings.
 133
 134 The set of variables defined in a non-recursive binding is just the
 135 union of all of them, as @union@ removes duplicates. However, the
 136 free variables in each successive set of cumulative bindings is the
 137 union of those in the previous set plus those of the newest binding after
 138 the defined variables of the previous set have been removed.
 139
 140 @rnMethodBinds@ deals only with the declarations in class and
 141 instance declarations.  It expects only to see @FunMonoBind@s, and
 142 it expects the global environment to contain bindings for the binders
 143 (which are all class operations).
 144
 145 %************************************************************************
 146 %*                                                                      *
 147 \subsubsection{ Top-level bindings}
 148 %*                                                                      *
 149 %************************************************************************
 150
 151 @rnTopMonoBinds@ assumes that the environment already
 152 contains bindings for the binders of this particular binding.
 153
 154 \begin{code}
 155 rnTopMonoBinds mbinds sigs
 156  =  mappM lookupBndrRn binder_rdr_names                  `thenM` \ binder_names ->
 157     bindPatSigTyVars (collectSigTysFromMonoBinds mbinds) $
 158     let
 159         bndr_name_set = mkNameSet binder_names
 160     in
 161     renameSigsFVs (okBindSig bndr_name_set) sigs        `thenM` \ (siglist, sig_fvs) ->
 162
 163         -- Warn about missing signatures, but not in interface mode
 164         -- (This is important when renaming bindings from 'deriving' clauses.)
 165     getModeRn                                           `thenM` \ mode ->
 166     doptM Opt_WarnMissingSigs                           `thenM` \ warn_missing_sigs ->
 167     (if warn_missing_sigs && not (isInterfaceMode mode) then
 168         let
 169             type_sig_vars   = [n | Sig n _ _ <- siglist]
 170             un_sigd_binders = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
 171         in
 172         mappM_ missingSigWarn un_sigd_binders
 173      else
 174         returnM ()
 175     )                                           `thenM_`
 176
 177     rn_mono_binds siglist mbinds                `thenM` \ (final_binds, bind_fvs) ->
 178     returnM (final_binds, bind_fvs `plusFV` sig_fvs)
 179   where
 180     binder_rdr_names = collectMonoBinders mbinds
 181 \end{code}
 182
 183 %************************************************************************
 184 %*                                                                      *
 185 %*              Nested binds
 186 %*                                                                      *
 187 %************************************************************************
 188
 189 \subsubsection{Nested binds}
 190
 191 @rnMonoBinds@
 192 \begin{itemize}
 193 \item collects up the binders for this declaration group,
 194 \item checks that they form a set
 195 \item extends the environment to bind them to new local names
 196 \item calls @rnMonoBinds@ to do the real work
 197 \end{itemize}
 198 %
 199 \begin{code}
 200 rnMonoBinds :: RdrNameMonoBinds
 201             -> [RdrNameSig]
 202             -> (RenamedHsBinds -> RnM (result, FreeVars))
 203             -> RnM (result, FreeVars)
 204
 205 rnMonoBinds mbinds sigs thing_inside -- Non-empty monobinds
 206   =     -- Extract all the binders in this group,
 207         -- and extend current scope, inventing new names for the new binders
 208         -- This also checks that the names form a set
 209     bindLocatedLocalsRn doc mbinders_w_srclocs                  $ \ new_mbinders ->
 210     bindPatSigTyVars (collectSigTysFromMonoBinds mbinds)        $
 211     let
 212         binder_set = mkNameSet new_mbinders
 213     in
 214         -- Rename the signatures
 215     renameSigsFVs (okBindSig binder_set) sigs   `thenM` \ (siglist, sig_fvs) ->
 216
 217         -- Report the fixity declarations in this group that
 218         -- don't refer to any of the group's binders.
 219         -- Then install the fixity declarations that do apply here
 220         -- Notice that they scope over thing_inside too
 221     bindLocalFixities [sig | FixSig sig <- siglist ]    $
 222
 223     rn_mono_binds siglist mbinds           `thenM` \ (binds, bind_fvs) ->
 224
 225     -- Now do the "thing inside", and deal with the free-variable calculations
 226     thing_inside binds                     `thenM` \ (result,result_fvs) ->
 227     let
 228         all_fvs        = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
 229         unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
 230     in
 231     warnUnusedLocalBinds unused_binders `thenM_`
 232     returnM (result, delListFromNameSet all_fvs new_mbinders)
 233   where
 234     mbinders_w_srclocs = collectLocatedMonoBinders mbinds
 235     doc = text "In the binding group for" <+> pp_bndrs mbinders_w_srclocs
 236     pp_bndrs [(b,_)] = quotes (ppr b)
 237     pp_bndrs bs      = fsep (punctuate comma [ppr b | (b,_) <- bs])
 238 \end{code}
 239
 240
 241 %************************************************************************
 242 %*                                                                      *
 243 \subsubsection{         MonoBinds -- the main work is done here}
 244 %*                                                                      *
 245 %************************************************************************
 246
 247 @rn_mono_binds@ is used by {\em both} top-level and nested bindings.
 248 It assumes that all variables bound in this group are already in scope.
 249 This is done {\em either} by pass 3 (for the top-level bindings),
 250 {\em or} by @rnMonoBinds@ (for the nested ones).
 251
 252 \begin{code}
 253 rn_mono_binds :: [RenamedSig]           -- Signatures attached to this group
 254               -> RdrNameMonoBinds
 255               -> RnM (RenamedHsBinds,   -- Dependency analysed
 256                        FreeVars)        -- Free variables
 257
 258 rn_mono_binds siglist mbinds
 259   =
 260          -- Rename the bindings, returning a MonoBindsInfo
 261          -- which is a list of indivisible vertices so far as
 262          -- the strongly-connected-components (SCC) analysis is concerned
 263     flattenMonoBinds siglist mbinds             `thenM` \ mbinds_info ->
 264
 265          -- Do the SCC analysis
 266     let
 267         edges       = mkEdges (mbinds_info `zip` [(0::Int)..])
 268         scc_result  = stronglyConnComp edges
 269         final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
 270
 271          -- Deal with bound and free-var calculation
 272         rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
 273     in
 274     returnM (final_binds, rhs_fvs)
 275 \end{code}
 276
 277 @flattenMonoBinds@ is ever-so-slightly magical in that it sticks
 278 unique ``vertex tags'' on its output; minor plumbing required.
 279
 280 Sigh --- need to pass along the signatures for the group of bindings,
 281 in case any of them \fbox{\ ???\ }
 282
 283 \begin{code}
 284 flattenMonoBinds :: [RenamedSig]                -- Signatures
 285                  -> RdrNameMonoBinds
 286                  -> RnM [FlatMonoBindsInfo]
 287
 288 flattenMonoBinds sigs EmptyMonoBinds = returnM []
 289
 290 flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
 291   = flattenMonoBinds sigs bs1   `thenM` \ flat1 ->
 292     flattenMonoBinds sigs bs2   `thenM` \ flat2 ->
 293     returnM (flat1 ++ flat2)
 294
 295 flattenMonoBinds sigs (PatMonoBind pat grhss locn)
 296   = addSrcLoc locn                      $
 297     rnPat 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 grhss                       `thenM` \ (grhss', fvs) ->
 305     returnM
 306         [(names_bound_here,
 307           fvs `plusFV` pat_fvs,
 308           PatMonoBind pat' grhss' locn,
 309           sigs_for_me
 310          )]
 311
 312 flattenMonoBinds sigs (FunMonoBind name inf matches locn)
 313   = addSrcLoc locn                                      $
 314     lookupBndrRn name                                   `thenM` \ new_name ->
 315     let
 316         names_bound_here = unitNameSet new_name
 317     in
 318     sigsForMe names_bound_here sigs                     `thenM` \ sigs_for_me ->
 319     mapFvRn (rnMatch (FunRhs name)) matches             `thenM` \ (new_matches, fvs) ->
 320     mappM_ (checkPrecMatch inf new_name) new_matches    `thenM_`
 321     returnM
 322       [(unitNameSet new_name,
 323         fvs,
 324         FunMonoBind new_name inf new_matches locn,
 325         sigs_for_me
 326         )]
 327
 328
 329 sigsForMe names_bound_here sigs
 330   = foldlM check [] (filter (sigForThisGroup names_bound_here) sigs)
 331   where
 332     check sigs sig = case filter (eqHsSig sig) sigs of
 333                         []    -> returnM (sig:sigs)
 334                         other -> dupSigDeclErr sig      `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 @rnMonoBinds@ 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               -> RdrNameMonoBinds
 358               -> RnM (RenamedMonoBinds, FreeVars)
 359
 360 rnMethodBinds cls gen_tyvars EmptyMonoBinds = returnM (EmptyMonoBinds, emptyFVs)
 361
 362 rnMethodBinds cls gen_tyvars (AndMonoBinds mb1 mb2)
 363   = rnMethodBinds cls gen_tyvars mb1    `thenM` \ (mb1', fvs1) ->
 364     rnMethodBinds cls gen_tyvars mb2    `thenM` \ (mb2', fvs2) ->
 365     returnM (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)
 366
 367 rnMethodBinds cls gen_tyvars (FunMonoBind name inf matches locn)
 368   = addSrcLoc locn                                      $
 369
 370     lookupInstDeclBndr cls name                         `thenM` \ sel_name ->
 371         -- We use the selector name as the binder
 372
 373     mapFvRn rn_match matches                            `thenM` \ (new_matches, fvs) ->
 374     mappM_ (checkPrecMatch inf sel_name) new_matches    `thenM_`
 375     returnM (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_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 match@(Match (TypePat ty : _) _ _)
 380         = extendTyVarEnvFVRn gen_tvs (rnMatch (FunRhs name) match)
 381         where
 382           tvs     = map rdrNameOcc (extractHsTyRdrNames ty)
 383           gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs]
 384
 385     rn_match match = rnMatch (FunRhs name) match
 386
 387
 388 -- Can't handle method pattern-bindings which bind multiple methods.
 389 rnMethodBinds cls gen_tyvars mbind@(PatMonoBind other_pat _ locn)
 390   = addSrcLoc locn (addErr (methodBindErr mbind))       `thenM_`
 391     returnM (EmptyMonoBinds, emptyFVs)
 392 \end{code}
 393
 394
 395 %************************************************************************
 396 %*                                                                      *
 397 \subsection[reconstruct-deps]{Reconstructing dependencies}
 398 %*                                                                      *
 399 %************************************************************************
 400
 401 This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
 402 as the two cases are similar.
 403
 404 \begin{code}
 405 reconstructCycle :: SCC FlatMonoBindsInfo
 406                  -> RenamedHsBinds
 407
 408 reconstructCycle (AcyclicSCC (_, _, binds, sigs))
 409   = MonoBind binds sigs NonRecursive
 410
 411 reconstructCycle (CyclicSCC cycle)
 412   = MonoBind this_gp_binds this_gp_sigs Recursive
 413   where
 414     this_gp_binds      = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
 415     this_gp_sigs       = foldr1 (++)         [sigs  | (_, _, _, sigs) <- cycle]
 416 \end{code}
 417
 418 %************************************************************************
 419 %*                                                                      *
 420 \subsubsection{ Manipulating FlatMonoBindInfo}
 421 %*                                                                      *
 422 %************************************************************************
 423
 424 During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
 425 The @RenamedMonoBinds@ is always an empty bind, a pattern binding or
 426 a function binding, and has itself been dependency-analysed and
 427 renamed.
 428
 429 \begin{code}
 430 type FlatMonoBindsInfo
 431   = (NameSet,                   -- Set of names defined in this vertex
 432      NameSet,                   -- Set of names used in this vertex
 433      RenamedMonoBinds,
 434      [RenamedSig])              -- Signatures, if any, for this vertex
 435
 436 mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]
 437
 438 mkEdges flat_info
 439   = [ (info, tag, dest_vertices (nameSetToList names_used))
 440     | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
 441     ]
 442   where
 443          -- An edge (v,v') indicates that v depends on v'
 444     dest_vertices src_mentions = [ target_vertex
 445                                  | ((names_defined, _, _, _), target_vertex) <- flat_info,
 446                                    mentioned_name <- src_mentions,
 447                                    mentioned_name `elemNameSet` names_defined
 448                                  ]
 449 \end{code}
 450
 451
 452 %************************************************************************
 453 %*                                                                      *
 454 \subsubsection[dep-Sigs]{Signatures (and user-pragmas for values)}
 455 %*                                                                      *
 456 %************************************************************************
 457
 458 @renameSigs@ checks for:
 459 \begin{enumerate}
 460 \item more than one sig for one thing;
 461 \item signatures given for things not bound here;
 462 \item with suitably flaggery, that all top-level things have type signatures.
 463 \end{enumerate}
 464 %
 465 At the moment we don't gather free-var info from the types in
 466 signatures.  We'd only need this if we wanted to report unused tyvars.
 467
 468 \begin{code}
 469 renameSigsFVs ok_sig sigs
 470   = renameSigs ok_sig sigs      `thenM` \ sigs' ->
 471     returnM (sigs', hsSigsFVs sigs')
 472
 473 renameSigs ::  (RenamedSig -> Bool)             -- OK-sig predicate
 474             -> [RdrNameSig]
 475             -> RnM [RenamedSig]
 476
 477 renameSigs ok_sig [] = returnM []
 478
 479 renameSigs ok_sig sigs
 480   =      -- Rename the signatures
 481     mappM renameSig sigs        `thenM` \ sigs' ->
 482
 483         -- Check for (a) duplicate signatures
 484         --           (b) signatures for things not in this group
 485     let
 486         in_scope         = filter is_in_scope sigs'
 487         is_in_scope sig  = case sigName sig of
 488                                 Just n  -> not (isUnboundName n)
 489                                 Nothing -> True
 490         (goods, bads)    = partition ok_sig in_scope
 491     in
 492     mappM_ unknownSigErr bads                   `thenM_`
 493     returnM goods
 494
 495 -- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
 496 -- because this won't work for:
 497 --      instance Foo T where
 498 --        {-# INLINE op #-}
 499 --        Baz.op = ...
 500 -- We'll just rename the INLINE prag to refer to whatever other 'op'
 501 -- is in scope.  (I'm assuming that Baz.op isn't in scope unqualified.)
 502 -- Doesn't seem worth much trouble to sort this.
 503
 504 renameSig :: Sig RdrName -> RnM (Sig Name)
 505 -- ClassOpSig is renamed elsewhere.
 506 renameSig (Sig v ty src_loc)
 507   = addSrcLoc src_loc $
 508     lookupSigOccRn v                            `thenM` \ new_v ->
 509     rnHsSigType (quotes (ppr v)) ty             `thenM` \ new_ty ->
 510     returnM (Sig new_v new_ty src_loc)
 511
 512 renameSig (SpecInstSig ty src_loc)
 513   = addSrcLoc src_loc $
 514     rnHsType (text "A SPECIALISE instance pragma") ty `thenM` \ new_ty ->
 515     returnM (SpecInstSig new_ty src_loc)
 516
 517 renameSig (SpecSig v ty src_loc)
 518   = addSrcLoc src_loc $
 519     lookupSigOccRn v                    `thenM` \ new_v ->
 520     rnHsSigType (quotes (ppr v)) ty     `thenM` \ new_ty ->
 521     returnM (SpecSig new_v new_ty src_loc)
 522
 523 renameSig (FixSig (FixitySig v fix src_loc))
 524   = addSrcLoc src_loc $
 525     lookupSigOccRn v            `thenM` \ new_v ->
 526     returnM (FixSig (FixitySig new_v fix src_loc))
 527
 528 renameSig (InlineSig b v p src_loc)
 529   = addSrcLoc src_loc $
 530     lookupSigOccRn v            `thenM` \ new_v ->
 531     returnM (InlineSig b new_v p src_loc)
 532 \end{code}
 533
 534
 535 %************************************************************************
 536 %*                                                                      *
 537 \subsection{Error messages}
 538 %*                                                                      *
 539 %************************************************************************
 540
 541 \begin{code}
 542 dupSigDeclErr sig
 543   = addSrcLoc loc $
 544     addErr (sep [ptext SLIT("Duplicate") <+> what_it_is <> colon,
 545                    ppr sig])
 546   where
 547     (what_it_is, loc) = hsSigDoc sig
 548
 549 unknownSigErr sig
 550   = addSrcLoc loc $
 551     addErr (sep [ptext SLIT("Misplaced") <+> what_it_is <> colon,
 552                    ppr sig])
 553   where
 554     (what_it_is, loc) = hsSigDoc sig
 555
 556 missingSigWarn var
 557   = addSrcLoc (nameSrcLoc var) $
 558     addWarn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
 559
 560 methodBindErr mbind
 561  =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
 562        4 (ppr mbind)
 563 \end{code}