RnBinds.lhs 19.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
%
% (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 (
	rnTopBinds, rnTopMonoBinds,
14
	rnMethodBinds, renameSigs, renameSigsFVs,
15 16 17 18 19 20 21 22
	rnBinds,
	unknownSigErr
   ) where

#include "HsVersions.h"


import HsSyn
23
import HsBinds		( eqHsSig, sigName, hsSigDoc )
24 25 26
import RdrHsSyn
import RnHsSyn
import RnMonad
27
import RnTypes		( rnHsSigType, rnHsType )
28
import RnExpr		( rnMatch, rnGRHSs, rnPat, checkPrecMatch )
29
import RnEnv		( bindLocatedLocalsRn, lookupBndrRn, lookupInstDeclBndr,
30
			  lookupGlobalOccRn, lookupSigOccRn, bindPatSigTyVars,
31
			  warnUnusedLocalBinds, mapFvRn, extendTyVarEnvFVRn,
32
			)
33
import CmdLineOpts	( DynFlag(..) )
34
import Digraph		( stronglyConnComp, SCC(..) )
35
import Name		( Name, nameOccName, nameSrcLoc )
36
import NameSet
37
import RdrName		( RdrName, rdrNameOcc )
38
import BasicTypes	( RecFlag(..) )
39 40
import List		( partition )
import Outputable
41
import PrelNames	( isUnboundName )
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
\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).

\begin{code}
type VertexTag	= Int
\end{code}

%************************************************************************
%*									*
%* 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 @FlatMonoBindsInfo@) 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}
%*									*
%************************************************************************

@rnTopBinds@ assumes that the environment already
contains bindings for the binders of this particular binding.

\begin{code}
rnTopBinds    :: RdrNameHsBinds -> RnMS (RenamedHsBinds, FreeVars)

rnTopBinds EmptyBinds		       	  = returnRn (EmptyBinds, emptyFVs)
rnTopBinds (MonoBind bind sigs _) 	  = rnTopMonoBinds bind sigs
  -- The parser doesn't produce other forms


rnTopMonoBinds mbinds sigs
165 166
 =  mapRn lookupBndrRn binder_rdr_names			 `thenRn` \ binder_names ->
    bindPatSigTyVars (collectSigTysFromMonoBinds mbinds) $ 
167 168 169
    let
	bndr_name_set = mkNameSet binder_names
    in
170
    renameSigsFVs (okBindSig bndr_name_set) sigs 	`thenRn` \ (siglist, sig_fvs) ->
171

172 173 174 175 176 177 178 179 180
    ifOptRn Opt_WarnMissingSigs (
	let
	    type_sig_vars   = [n | Sig n _ _ <- siglist]
	    un_sigd_binders = nameSetToList (delListFromNameSet bndr_name_set type_sig_vars)
	in
        mapRn_ missingSigWarn un_sigd_binders
    )						`thenRn_`

    rn_mono_binds siglist mbinds		`thenRn` \ (final_binds, bind_fvs) ->
181 182
    returnRn (final_binds, bind_fvs `plusFV` sig_fvs)
  where
183
    binder_rdr_names = collectMonoBinders mbinds
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
\end{code}

%************************************************************************
%*									*
%* 		Nested binds
%*									*
%************************************************************************

\subsubsection{Nested binds}

@rnMonoBinds@
\begin{itemize}
\item collects up the binders for this declaration group,
\item checks that they form a set
\item extends the environment to bind them to new local names
\item calls @rnMonoBinds@ to do the real work
\end{itemize}
%
\begin{code}
rnBinds	      :: RdrNameHsBinds 
	      -> (RenamedHsBinds -> RnMS (result, FreeVars))
	      -> RnMS (result, FreeVars)

rnBinds EmptyBinds	       thing_inside = thing_inside EmptyBinds
rnBinds (MonoBind bind sigs _) thing_inside = rnMonoBinds bind sigs thing_inside
  -- the parser doesn't produce other forms


rnMonoBinds :: RdrNameMonoBinds 
            -> [RdrNameSig]
	    -> (RenamedHsBinds -> RnMS (result, FreeVars))
	    -> RnMS (result, FreeVars)

rnMonoBinds mbinds sigs	thing_inside -- Non-empty monobinds
  =	-- Extract all the binders in this group,
	-- and extend current scope, inventing new names for the new binders
	-- This also checks that the names form a set
221 222
    bindLocatedLocalsRn doc mbinders_w_srclocs			$ \ new_mbinders ->
    bindPatSigTyVars (collectSigTysFromMonoBinds mbinds)	$ 
223
    let
224
	binder_set = mkNameSet new_mbinders
225
    in
226
	-- Rename the signatures
227
    renameSigsFVs (okBindSig binder_set) sigs	`thenRn` \ (siglist, sig_fvs) ->
228 229 230 231 232

	-- Report the fixity declarations in this group that 
	-- don't refer to any of the group's binders.
	-- Then install the fixity declarations that do apply here
	-- Notice that they scope over thing_inside too
233 234 235
    let
	fixity_sigs = [(name,sig) | FixSig sig@(FixitySig name _ _) <- siglist ]
    in
236 237 238
    extendFixityEnv fixity_sigs $

    rn_mono_binds siglist mbinds	   `thenRn` \ (binds, bind_fvs) ->
239 240

    -- Now do the "thing inside", and deal with the free-variable calculations
241
    thing_inside binds 			   `thenRn` \ (result,result_fvs) ->
242 243 244 245 246 247 248
    let
	all_fvs        = result_fvs `plusFV` bind_fvs `plusFV` sig_fvs
	unused_binders = nameSetToList (binder_set `minusNameSet` all_fvs)
    in
    warnUnusedLocalBinds unused_binders	`thenRn_`
    returnRn (result, delListFromNameSet all_fvs new_mbinders)
  where
249
    mbinders_w_srclocs = collectLocatedMonoBinders mbinds
250 251 252
    doc = text "In the binding group for" <+> pp_bndrs mbinders_w_srclocs
    pp_bndrs [(b,_)] = quotes (ppr b)
    pp_bndrs bs      = fsep (punctuate comma [ppr b | (b,_) <- bs])
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
\end{code}


%************************************************************************
%*									*
\subsubsection{		MonoBinds -- the main work is done here}
%*									*
%************************************************************************

@rn_mono_binds@ 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}
rn_mono_binds :: [RenamedSig]	        -- Signatures attached to this group
	      -> RdrNameMonoBinds	
270 271
	      -> RnMS (RenamedHsBinds, 	-- Dependency analysed
		       FreeVars)	-- Free variables
272 273 274 275 276 277 278 279 280 281 282 283

rn_mono_binds siglist mbinds
  =
	 -- 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		`thenRn` \ mbinds_info ->

	 -- Do the SCC analysis
    let 
        edges	    = mkEdges (mbinds_info `zip` [(0::Int)..])
	scc_result  = stronglyConnComp edges
284
	final_binds = foldr (ThenBinds . reconstructCycle) EmptyBinds scc_result
285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

	 -- Deal with bound and free-var calculation
	rhs_fvs = plusFVs [fvs | (_,fvs,_,_) <- mbinds_info]
    in
    returnRn (final_binds, rhs_fvs)
\end{code}

@flattenMonoBinds@ is ever-so-slightly magical in that it sticks
unique ``vertex tags'' on its output; minor plumbing required.

Sigh --- need to pass along the signatures for the group of bindings,
in case any of them \fbox{\ ???\ } 

\begin{code}
flattenMonoBinds :: [RenamedSig]		-- Signatures
		 -> RdrNameMonoBinds
		 -> RnMS [FlatMonoBindsInfo]

flattenMonoBinds sigs EmptyMonoBinds = returnRn []

flattenMonoBinds sigs (AndMonoBinds bs1 bs2)
  = flattenMonoBinds sigs bs1	`thenRn` \ flat1 ->
    flattenMonoBinds sigs bs2	`thenRn` \ flat2 ->
    returnRn (flat1 ++ flat2)

flattenMonoBinds sigs (PatMonoBind pat grhss locn)
  = pushSrcLocRn locn		 	$
    rnPat pat				`thenRn` \ (pat', pat_fvs) ->

	 -- Find which things are bound in this group
    let
	names_bound_here = mkNameSet (collectPatBinders pat')
    in
318
    sigsForMe names_bound_here sigs	`thenRn` \ sigs_for_me ->
319 320 321 322 323 324 325 326 327 328 329 330
    rnGRHSs grhss			`thenRn` \ (grhss', fvs) ->
    returnRn 
	[(names_bound_here,
	  fvs `plusFV` pat_fvs,
	  PatMonoBind pat' grhss' locn,
	  sigs_for_me
	 )]

flattenMonoBinds sigs (FunMonoBind name inf matches locn)
  = pushSrcLocRn locn				 	$
    lookupBndrRn name					`thenRn` \ new_name ->
    let
331
	names_bound_here = unitNameSet new_name
332
    in
333
    sigsForMe names_bound_here sigs			`thenRn` \ sigs_for_me ->
334
    mapFvRn (rnMatch (FunRhs name)) matches		`thenRn` \ (new_matches, fvs) ->
335 336 337 338 339 340 341
    mapRn_ (checkPrecMatch inf new_name) new_matches	`thenRn_`
    returnRn
      [(unitNameSet new_name,
	fvs,
	FunMonoBind new_name inf new_matches locn,
	sigs_for_me
	)]
342 343 344 345 346 347 348 349 350


sigsForMe names_bound_here sigs
  = foldlRn check [] (filter (sigForThisGroup names_bound_here) sigs)
  where
    check sigs sig = case filter (eqHsSig sig) sigs of
			[]    -> returnRn (sig:sigs)
			other -> dupSigDeclErr sig	`thenRn_`
				 returnRn sigs
351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
\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}
370 371
rnMethodBinds :: Name			-- Class name
	      -> [Name]			-- Names for generic type variables
372 373
	      -> RdrNameMonoBinds
	      -> RnMS (RenamedMonoBinds, FreeVars)
374

375
rnMethodBinds cls gen_tyvars EmptyMonoBinds = returnRn (EmptyMonoBinds, emptyFVs)
376

377 378 379
rnMethodBinds cls gen_tyvars (AndMonoBinds mb1 mb2)
  = rnMethodBinds cls gen_tyvars mb1	`thenRn` \ (mb1', fvs1) ->
    rnMethodBinds cls gen_tyvars mb2	`thenRn` \ (mb2', fvs2) ->
380 381
    returnRn (mb1' `AndMonoBinds` mb2', fvs1 `plusFV` fvs2)

382
rnMethodBinds cls gen_tyvars (FunMonoBind name inf matches locn)
383 384
  = pushSrcLocRn locn				   	$

385
    lookupInstDeclBndr cls name				`thenRn` \ sel_name -> 
386 387
	-- We use the selector name as the binder

388
    mapFvRn rn_match matches				`thenRn` \ (new_matches, fvs) ->
389 390
    mapRn_ (checkPrecMatch inf sel_name) new_matches	`thenRn_`
    returnRn (FunMonoBind sel_name inf new_matches locn, fvs `addOneFV` sel_name)
391 392
  where
	-- Gruesome; bring into scope the correct members of the generic type variables
393
	-- See comments in RnSource.rnSourceDecl(ClassDecl)
394
    rn_match match@(Match (TypePatIn ty : _) _ _)
395
	= extendTyVarEnvFVRn gen_tvs (rnMatch (FunRhs name) match)
396 397 398 399
	where
	  tvs     = map rdrNameOcc (extractHsTyRdrNames ty)
	  gen_tvs = [tv | tv <- gen_tyvars, nameOccName tv `elem` tvs] 

400
    rn_match match = rnMatch (FunRhs name) match
401
	
402 403

-- Can't handle method pattern-bindings which bind multiple methods.
404
rnMethodBinds cls gen_tyvars mbind@(PatMonoBind other_pat _ locn)
405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483
  = pushSrcLocRn locn	$
    failWithRn (EmptyMonoBinds, emptyFVs) (methodBindErr mbind)
\end{code}


%************************************************************************
%*									*
\subsection[reconstruct-deps]{Reconstructing dependencies}
%*									*
%************************************************************************

This @MonoBinds@- and @ClassDecls@-specific code is segregated here,
as the two cases are similar.

\begin{code}
reconstructCycle :: SCC FlatMonoBindsInfo
		 -> RenamedHsBinds

reconstructCycle (AcyclicSCC (_, _, binds, sigs))
  = MonoBind binds sigs NonRecursive

reconstructCycle (CyclicSCC cycle)
  = MonoBind this_gp_binds this_gp_sigs Recursive
  where
    this_gp_binds      = foldr1 AndMonoBinds [binds | (_, _, binds, _) <- cycle]
    this_gp_sigs       = foldr1 (++)	     [sigs  | (_, _, _, sigs) <- cycle]
\end{code}

%************************************************************************
%*									*
\subsubsection{	Manipulating FlatMonoBindInfo}
%*									*
%************************************************************************

During analysis a @MonoBinds@ is flattened to a @FlatMonoBindsInfo@.
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 FlatMonoBindsInfo
  = (NameSet,			-- Set of names defined in this vertex
     NameSet,			-- Set of names used in this vertex
     RenamedMonoBinds,
     [RenamedSig])		-- Signatures, if any, for this vertex

mkEdges :: [(FlatMonoBindsInfo, VertexTag)] -> [(FlatMonoBindsInfo, VertexTag, [VertexTag])]

mkEdges flat_info
  = [ (info, tag, dest_vertices (nameSetToList names_used))
    | (info@(names_defined, names_used, mbind, sigs), tag) <- flat_info
    ]
  where
 	 -- An edge (v,v') indicates that v depends on v'
    dest_vertices src_mentions = [ target_vertex
			         | ((names_defined, _, _, _), target_vertex) <- flat_info,
				   mentioned_name <- src_mentions,
				   mentioned_name `elemNameSet` names_defined
			         ]
\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}
484 485 486 487
renameSigsFVs ok_sig sigs
  = renameSigs ok_sig sigs	`thenRn` \ sigs' ->
    returnRn (sigs', hsSigsFVs sigs')

488
renameSigs ::  (RenamedSig -> Bool)		-- OK-sig predicate
489
	    -> [RdrNameSig]
490
	    -> RnMS [RenamedSig]
491

492
renameSigs ok_sig [] = returnRn []
493

494
renameSigs ok_sig sigs
495
  =	 -- Rename the signatures
496
    mapRn renameSig sigs   	`thenRn` \ sigs' ->
497 498 499 500

	-- Check for (a) duplicate signatures
	--	     (b) signatures for things not in this group
    let
501 502 503 504
	in_scope	 = filter is_in_scope sigs'
	is_in_scope sig	 = case sigName sig of
				Just n  -> not (isUnboundName n)
				Nothing -> True
505
	(goods, bads)	 = partition ok_sig in_scope
506
    in
507
    mapRn_ unknownSigErr bads			`thenRn_`
508
    returnRn goods
509

510
-- We use lookupSigOccRn in the signatures, which is a little bit unsatisfactory
511 512 513 514 515 516 517 518
-- 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.

519
renameSig :: Sig RdrName -> RnMS (Sig Name)
520
-- ClassOpSig is renamed elsewhere.
521
renameSig (Sig v ty src_loc)
522
  = pushSrcLocRn src_loc $
523
    lookupSigOccRn v				`thenRn` \ new_v ->
524 525
    rnHsSigType (quotes (ppr v)) ty		`thenRn` \ new_ty ->
    returnRn (Sig new_v new_ty src_loc)
526

527
renameSig (SpecInstSig ty src_loc)
528
  = pushSrcLocRn src_loc $
529 530
    rnHsType (text "A SPECIALISE instance pragma") ty `thenRn` \ new_ty ->
    returnRn (SpecInstSig new_ty src_loc)
531

532
renameSig (SpecSig v ty src_loc)
533
  = pushSrcLocRn src_loc $
534
    lookupSigOccRn v			`thenRn` \ new_v ->
535 536
    rnHsSigType (quotes (ppr v)) ty	`thenRn` \ new_ty ->
    returnRn (SpecSig new_v new_ty src_loc)
537

538
renameSig (FixSig (FixitySig v fix src_loc))
539
  = pushSrcLocRn src_loc $
540
    lookupSigOccRn v		`thenRn` \ new_v ->
541
    returnRn (FixSig (FixitySig new_v fix src_loc))
542

543
renameSig (InlineSig b v p src_loc)
544
  = pushSrcLocRn src_loc $
545
    lookupSigOccRn v		`thenRn` \ new_v ->
546
    returnRn (InlineSig b new_v p src_loc)
547 548 549 550 551 552 553 554 555 556
\end{code}


%************************************************************************
%*									*
\subsection{Error messages}
%*									*
%************************************************************************

\begin{code}
557
dupSigDeclErr sig
558 559 560 561
  = pushSrcLocRn loc $
    addErrRn (sep [ptext SLIT("Duplicate") <+> ptext what_it_is <> colon,
		   ppr sig])
  where
562
    (what_it_is, loc) = hsSigDoc sig
563 564 565

unknownSigErr sig
  = pushSrcLocRn loc $
566
    addErrRn (sep [ptext SLIT("Misplaced") <+> ptext what_it_is <> colon,
567 568
		   ppr sig])
  where
569
    (what_it_is, loc) = hsSigDoc sig
570 571

missingSigWarn var
572 573
  = pushSrcLocRn (nameSrcLoc var) $
    addWarnRn (sep [ptext SLIT("Definition but no type signature for"), quotes (ppr var)])
574 575 576 577 578

methodBindErr mbind
 =  hang (ptext SLIT("Can't handle multiple methods defined by one pattern binding"))
       4 (ppr mbind)
\end{code}