2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1995
4 \section[CoreLint]{A ``lint'' pass to check for Core correctness}
7 #include "HsVersions.h"
19 import Kind ( Kind{-instance-} )
20 import Literal ( literalType, Literal{-instance-} )
21 import Id ( idType, isBottomingId,
22 dataConArgTys, GenId{-instances-}
24 import Maybes ( catMaybes )
25 import Name ( isLocallyDefined, getSrcLoc )
26 import Outputable ( Outputable(..){-instance * []-} )
28 import PprStyle ( PprStyle(..) )
29 import PprType ( GenType, GenTyVar, TyCon )
31 import PrimOp ( primOpType, PrimOp(..) )
32 import PrimRep ( PrimRep(..) )
33 import SrcLoc ( SrcLoc )
34 import Type ( mkFunTy,getFunTy_maybe,mkForAllTy,getForAllTy_maybe,
35 isPrimType,typeKind,instantiateTy,
36 mkForAllUsageTy,getForAllUsageTy,instantiateUsage,
37 maybeAppDataTyCon, eqTy
39 import TyCon ( isPrimTyCon, tyConFamilySize )
40 import TyVar ( tyVarKind, GenTyVar{-instances-} )
41 import UniqSet ( emptyUniqSet, mkUniqSet, intersectUniqSets,
42 unionUniqSets, elementOfUniqSet, UniqSet(..)
44 import Unique ( Unique )
45 import Usage ( GenUsage )
46 import Util ( zipEqual, pprTrace, pprPanic, assertPanic, panic )
48 infixr 9 `thenL`, `seqL`, `thenMaybeL`, `seqMaybeL`
51 %************************************************************************
53 \subsection[lintCoreBindings]{@lintCoreBindings@: Top-level interface}
55 %************************************************************************
57 Checks that a set of core bindings is well-formed. The PprStyle and String
58 just control what we print in the event of an error. The Bool value
59 indicates whether we have done any specialisation yet (in which case we do
64 (b) Out-of-scope type variables
65 (c) Out-of-scope local variables
68 If we have done specialisation the we check that there are
69 (a) No top-level bindings of primitive (unboxed type)
74 -- Things are *not* OK if:
76 -- * Unsaturated type app before specialisation has been done;
78 -- * Oversaturated type app after specialisation (eta reduction
79 -- may well be happening...);
81 -- Note: checkTyApp is usually followed by a call to checkSpecTyApp.
86 :: PprStyle -> String -> Bool -> [CoreBinding] -> [CoreBinding]
88 lintCoreBindings sty whoDunnit spec_done binds
89 = case (initL (lint_binds binds) spec_done) of
92 pprPanic "" (ppAboves [
93 ppStr ("*** Core Lint Errors: in " ++ whoDunnit ++ " ***"),
95 ppStr "*** Offending Program ***",
96 ppAboves (map (pprCoreBinding sty) binds),
97 ppStr "*** End of Offense ***"
100 lint_binds [] = returnL ()
101 lint_binds (bind:binds)
102 = lintCoreBinding bind `thenL` \binders ->
103 addInScopeVars binders (lint_binds binds)
106 %************************************************************************
108 \subsection[lintUnfolding]{lintUnfolding}
110 %************************************************************************
112 We use this to check all unfoldings that come in from interfaces
113 (it is very painful to catch errors otherwise):
116 lintUnfolding :: SrcLoc -> CoreExpr -> Maybe CoreExpr
118 lintUnfolding locn expr
120 (initL (addLoc (ImportedUnfolding locn) (lintCoreExpr expr))
121 True{-pretend spec done-})
125 pprTrace "WARNING: Discarded bad unfolding from interface:\n"
126 (ppAboves [msg PprForUser,
127 ppStr "*** Bad unfolding ***",
129 ppStr "*** End unfolding ***"])
133 %************************************************************************
135 \subsection[lintCoreBinding]{lintCoreBinding}
137 %************************************************************************
139 Check a core binding, returning the list of variables bound.
142 lintCoreBinding :: CoreBinding -> LintM [Id]
144 lintCoreBinding (NonRec binder rhs)
145 = lintSingleBinding (binder,rhs) `seqL` returnL [binder]
147 lintCoreBinding (Rec pairs)
148 = addInScopeVars binders (
149 mapL lintSingleBinding pairs `seqL` returnL binders
152 binders = [b | (b,_) <- pairs]
154 lintSingleBinding (binder,rhs)
155 = addLoc (RhsOf binder) (
160 -- Check match to RHS type
162 Nothing -> returnL ()
163 Just ty -> checkTys (idType binder) ty (mkRhsMsg binder ty))
166 -- Check (not isPrimType)
167 checkIfSpecDoneL (not (isPrimType (idType binder)))
168 (mkRhsPrimMsg binder rhs)
170 -- We should check the unfolding, if any, but this is tricky because
171 -- the unfolding is a SimplifiableCoreExpr. Give up for now.
175 %************************************************************************
177 \subsection[lintCoreExpr]{lintCoreExpr}
179 %************************************************************************
182 lintCoreExpr :: CoreExpr -> LintM (Maybe Type) -- Nothing if error found
184 lintCoreExpr (Var var) = checkInScope var `seqL` returnL (Just (idType var))
185 lintCoreExpr (Lit lit) = returnL (Just (literalType lit))
186 lintCoreExpr (SCC _ expr) = lintCoreExpr expr
187 lintCoreExpr (Coerce _ ty expr)
188 = _trace "lintCoreExpr:Coerce" $
189 lintCoreExpr expr `seqL` returnL (Just ty)
191 lintCoreExpr (Let binds body)
192 = lintCoreBinding binds `thenL` \binders ->
193 if (null binders) then
194 lintCoreExpr body -- Can't add a new source location
196 addLoc (BodyOfLetRec binders)
197 (addInScopeVars binders (lintCoreExpr body))
199 lintCoreExpr e@(Con con args)
200 = lintCoreArgs False e (idType con) args
201 -- Note: we don't check for primitive types in these arguments
203 lintCoreExpr e@(Prim op args)
204 = lintCoreArgs True e (primOpType op) args
205 -- Note: we do check for primitive types in these arguments
207 lintCoreExpr e@(App fun@(Var v) arg) | isBottomingId v
208 = lintCoreExpr fun `thenMaybeL` \ ty -> lintCoreArg False e ty arg
209 -- Note: we don't check for primitive types in argument to 'error'
211 lintCoreExpr e@(App fun arg)
212 = lintCoreExpr fun `thenMaybeL` \ty -> lintCoreArg True e ty arg
213 -- Note: we do check for primitive types in this argument
215 lintCoreExpr (Lam (ValBinder var) expr)
216 = addLoc (LambdaBodyOf var)
217 (addInScopeVars [var]
218 (lintCoreExpr expr `thenMaybeL` \ty ->
219 returnL (Just (mkFunTy (idType var) ty))))
221 lintCoreExpr (Lam (TyBinder tyvar) expr)
222 = lintCoreExpr expr `thenMaybeL` \ty ->
223 returnL (Just(mkForAllTy tyvar ty))
224 -- ToDo: Should add in-scope type variable at this point
226 lintCoreExpr e@(Case scrut alts)
227 = lintCoreExpr scrut `thenMaybeL` \ty ->
231 %************************************************************************
233 \subsection[lintCoreArgs]{lintCoreArgs}
235 %************************************************************************
237 The boolean argument indicates whether we should flag type
238 applications to primitive types as being errors.
241 lintCoreArgs :: Bool -> CoreExpr -> Type -> [CoreArg] -> LintM (Maybe Type)
243 lintCoreArgs _ _ ty [] = returnL (Just ty)
244 lintCoreArgs checkTyApp e ty (a : args)
245 = lintCoreArg checkTyApp e ty a `thenMaybeL` \ res ->
246 lintCoreArgs checkTyApp e res args
249 %************************************************************************
251 \subsection[lintCoreArg]{lintCoreArg}
253 %************************************************************************
256 lintCoreArg :: Bool -> CoreExpr -> Type -> CoreArg -> LintM (Maybe Type)
258 lintCoreArg _ e ty (LitArg lit)
259 = -- Make sure function type matches argument
260 case (getFunTy_maybe ty) of
261 Just (arg,res) | (literalType lit `eqTy` arg) -> returnL(Just res)
262 _ -> addErrL (mkAppMsg ty (literalType lit) e) `seqL` returnL Nothing
264 lintCoreArg _ e ty (VarArg v)
265 = -- Make sure variable is bound
266 checkInScope v `seqL`
267 -- Make sure function type matches argument
268 case (getFunTy_maybe ty) of
269 Just (arg,res) | (idType v `eqTy` arg) -> returnL(Just res)
270 _ -> addErrL (mkAppMsg ty (idType v) e) `seqL` returnL Nothing
272 lintCoreArg checkTyApp e ty a@(TyArg arg_ty)
273 = -- ToDo: Check that ty is well-kinded and has no unbound tyvars
274 checkIfSpecDoneL (not (isPrimType arg_ty)) (mkSpecTyAppMsg a)
276 case (getForAllTy_maybe ty) of
277 Nothing -> addErrL (mkTyAppMsg SLIT("Illegal") ty arg_ty e) `seqL` returnL Nothing
281 tyvar_kind = tyVarKind tyvar
282 argty_kind = typeKind arg_ty
284 if tyvar_kind == argty_kind
285 -- SUSPICIOUS! (tyvar_kind `isSubKindOf` argty_kind
286 -- || argty_kind `isSubKindOf` tyvar_kind)
288 returnL(Just(instantiateTy [(tyvar,arg_ty)] body))
290 pprTrace "lintCoreArg:kinds:" (ppCat [ppr PprDebug tyvar_kind, ppr PprDebug argty_kind]) $
291 addErrL (mkTyAppMsg SLIT("Kinds not right in") ty arg_ty e) `seqL` returnL Nothing
293 lintCoreArg _ e ty (UsageArg u)
294 = -- ToDo: Check that usage has no unbound usage variables
295 case (getForAllUsageTy ty) of
296 Just (uvar,bounds,body) ->
297 -- ToDo: Check argument satisfies bounds
298 returnL(Just(panic "lintCoreArg:instantiateUsage uvar u body"))
299 _ -> addErrL (mkUsageAppMsg ty u e) `seqL` returnL Nothing
302 %************************************************************************
304 \subsection[lintCoreAlts]{lintCoreAlts}
306 %************************************************************************
309 lintCoreAlts :: CoreCaseAlts
310 -> Type -- Type of scrutinee
311 -- -> TyCon -- TyCon pinned on the case
312 -> LintM (Maybe Type) -- Type of alternatives
314 lintCoreAlts whole_alts@(AlgAlts alts deflt) ty --tycon
315 = -- Check tycon is not a primitive tycon
316 -- addErrIfL (isPrimTyCon tycon) (mkCasePrimMsg tycon)
318 -- Check we are scrutinising a proper datatype
320 -- addErrIfL (not (tyConFamilySize tycon >= 1)) (mkCaseAbstractMsg tycon)
323 `thenL` \maybe_deflt_ty ->
324 mapL (lintAlgAlt ty {-tycon-}) alts
325 `thenL` \maybe_alt_tys ->
326 -- Check the result types
327 case catMaybes (maybe_deflt_ty : maybe_alt_tys) of
328 [] -> returnL Nothing
330 (first_ty:tys) -> mapL check tys `seqL`
331 returnL (Just first_ty)
333 check ty = checkTys first_ty ty (mkCaseAltMsg whole_alts)
335 lintCoreAlts whole_alts@(PrimAlts alts deflt) ty --tycon
336 = -- Check tycon is a primitive tycon
337 -- addErrIfL (not (isPrimTyCon tycon)) (mkCaseNotPrimMsg tycon)
339 mapL (lintPrimAlt ty) alts
340 `thenL` \maybe_alt_tys ->
342 `thenL` \maybe_deflt_ty ->
343 -- Check the result types
344 case catMaybes (maybe_deflt_ty : maybe_alt_tys) of
345 [] -> returnL Nothing
347 (first_ty:tys) -> mapL check tys `seqL`
348 returnL (Just first_ty)
350 check ty = checkTys first_ty ty (mkCaseAltMsg whole_alts)
352 lintAlgAlt scrut_ty {-tycon-ToDo: use it!-} (con,args,rhs)
353 = (case maybeAppDataTyCon scrut_ty of
355 addErrL (mkAlgAltMsg1 scrut_ty)
356 Just (tycon, tys_applied, cons) ->
358 arg_tys = dataConArgTys con tys_applied
360 checkL (con `elem` cons) (mkAlgAltMsg2 scrut_ty con) `seqL`
361 checkL (length arg_tys == length args) (mkAlgAltMsg3 con args)
363 mapL check (arg_tys `zipEqual` args) `seqL`
366 addInScopeVars args (
370 check (ty, arg) = checkTys ty (idType arg) (mkAlgAltMsg4 ty arg)
372 -- elem: yes, the elem-list here can sometimes be long-ish,
373 -- but as it's use-once, probably not worth doing anything different
374 -- We give it its own copy, so it isn't overloaded.
376 elem x (y:ys) = x==y || elem x ys
378 lintPrimAlt ty alt@(lit,rhs)
379 = checkTys (literalType lit) ty (mkPrimAltMsg alt) `seqL`
382 lintDeflt NoDefault _ = returnL Nothing
383 lintDeflt deflt@(BindDefault binder rhs) ty
384 = checkTys (idType binder) ty (mkDefltMsg deflt) `seqL`
385 addInScopeVars [binder] (lintCoreExpr rhs)
388 %************************************************************************
390 \subsection[lint-monad]{The Lint monad}
392 %************************************************************************
395 type LintM a = Bool -- True <=> specialisation has been done
396 -> [LintLocInfo] -- Locations
397 -> UniqSet Id -- Local vars in scope
398 -> Bag ErrMsg -- Error messages so far
399 -> (a, Bag ErrMsg) -- Result and error messages (if any)
401 type ErrMsg = PprStyle -> Pretty
404 = RhsOf Id -- The variable bound
405 | LambdaBodyOf Id -- The lambda-binder
406 | BodyOfLetRec [Id] -- One of the binders
407 | ImportedUnfolding SrcLoc -- Some imported unfolding (ToDo: say which)
409 instance Outputable LintLocInfo where
411 = ppBesides [ppr sty (getSrcLoc v), ppStr ": [RHS of ", pp_binders sty [v], ppStr "]"]
413 ppr sty (LambdaBodyOf b)
414 = ppBesides [ppr sty (getSrcLoc b),
415 ppStr ": [in body of lambda with binder ", pp_binder sty b, ppStr "]"]
417 ppr sty (BodyOfLetRec bs)
418 = ppBesides [ppr sty (getSrcLoc (head bs)),
419 ppStr ": [in body of letrec with binders ", pp_binders sty bs, ppStr "]"]
421 ppr sty (ImportedUnfolding locn)
422 = ppBeside (ppr sty locn) (ppStr ": [in an imported unfolding]")
424 pp_binders :: PprStyle -> [Id] -> Pretty
425 pp_binders sty bs = ppInterleave ppComma (map (pp_binder sty) bs)
427 pp_binder :: PprStyle -> Id -> Pretty
428 pp_binder sty b = ppCat [ppr sty b, ppStr "::", ppr sty (idType b)]
432 initL :: LintM a -> Bool -> Maybe ErrMsg
434 = case (m spec_done [] emptyUniqSet emptyBag) of { (_, errs) ->
435 if isEmptyBag errs then
439 ppAboves [ msg sty | msg <- bagToList errs ]
443 returnL :: a -> LintM a
444 returnL r spec loc scope errs = (r, errs)
446 thenL :: LintM a -> (a -> LintM b) -> LintM b
447 thenL m k spec loc scope errs
448 = case m spec loc scope errs of
449 (r, errs') -> k r spec loc scope errs'
451 seqL :: LintM a -> LintM b -> LintM b
452 seqL m k spec loc scope errs
453 = case m spec loc scope errs of
454 (_, errs') -> k spec loc scope errs'
456 thenMaybeL :: LintM (Maybe a) -> (a -> LintM (Maybe b)) -> LintM (Maybe b)
457 thenMaybeL m k spec loc scope errs
458 = case m spec loc scope errs of
459 (Nothing, errs2) -> (Nothing, errs2)
460 (Just r, errs2) -> k r spec loc scope errs2
462 seqMaybeL :: LintM (Maybe a) -> LintM (Maybe b) -> LintM (Maybe b)
463 seqMaybeL m k spec loc scope errs
464 = case m spec loc scope errs of
465 (Nothing, errs2) -> (Nothing, errs2)
466 (Just _, errs2) -> k spec loc scope errs2
468 mapL :: (a -> LintM b) -> [a] -> LintM [b]
469 mapL f [] = returnL []
472 mapL f xs `thenL` \ rs ->
475 mapMaybeL :: (a -> LintM (Maybe b)) -> [a] -> LintM (Maybe [b])
476 -- Returns Nothing if anything fails
477 mapMaybeL f [] = returnL (Just [])
479 = f x `thenMaybeL` \ r ->
480 mapMaybeL f xs `thenMaybeL` \ rs ->
481 returnL (Just (r:rs))
485 checkL :: Bool -> ErrMsg -> LintM ()
486 checkL True msg spec loc scope errs = ((), errs)
487 checkL False msg spec loc scope errs = ((), addErr errs msg loc)
489 checkIfSpecDoneL :: Bool -> ErrMsg -> LintM ()
490 checkIfSpecDoneL True msg spec loc scope errs = ((), errs)
491 checkIfSpecDoneL False msg True loc scope errs = ((), addErr errs msg loc)
492 checkIfSpecDoneL False msg False loc scope errs = ((), errs)
495 = if pred then addErrL spec else returnL ()
497 addErrL :: ErrMsg -> LintM ()
498 addErrL msg spec loc scope errs = ((), addErr errs msg loc)
500 addErr :: Bag ErrMsg -> ErrMsg -> [LintLocInfo] -> Bag ErrMsg
502 addErr errs_so_far msg locs
503 = ASSERT (not (null locs))
504 errs_so_far `snocBag` ( \ sty ->
505 ppHang (ppr sty (head locs)) 4 (msg sty)
508 addLoc :: LintLocInfo -> LintM a -> LintM a
509 addLoc extra_loc m spec loc scope errs
510 = m spec (extra_loc:loc) scope errs
512 addInScopeVars :: [Id] -> LintM a -> LintM a
513 addInScopeVars ids m spec loc scope errs
514 = -- We check if these "new" ids are already
515 -- in scope, i.e., we have *shadowing* going on.
516 -- For now, it's just a "trace"; we may make
517 -- a real error out of it...
519 new_set = mkUniqSet ids
521 shadowed = scope `intersectUniqSets` new_set
523 -- After adding -fliberate-case, Simon decided he likes shadowed
524 -- names after all. WDP 94/07
525 -- (if isEmptyUniqSet shadowed
527 -- else pprTrace "Shadowed vars:" (ppr PprDebug (uniqSetToList shadowed))) (
528 m spec loc (scope `unionUniqSets` new_set) errs
533 checkInScope :: Id -> LintM ()
534 checkInScope id spec loc scope errs
535 = if isLocallyDefined id && not (id `elementOfUniqSet` scope) then
536 ((),addErr errs (\sty -> ppCat [ppr sty id,ppStr "is out of scope"]) loc)
540 checkTys :: Type -> Type -> ErrMsg -> LintM ()
541 checkTys ty1 ty2 msg spec loc scope errs
542 = if ty1 `eqTy` ty2 then ((), errs) else ((), addErr errs msg loc)
546 mkCaseAltMsg :: CoreCaseAlts -> ErrMsg
547 mkCaseAltMsg alts sty
548 = ppAbove (ppStr "Type of case alternatives not the same:")
551 mkCaseDataConMsg :: CoreExpr -> ErrMsg
552 mkCaseDataConMsg expr sty
553 = ppAbove (ppStr "A case scrutinee not of data constructor type:")
556 mkCaseNotPrimMsg :: TyCon -> ErrMsg
557 mkCaseNotPrimMsg tycon sty
558 = ppAbove (ppStr "A primitive case on a non-primitive type:")
561 mkCasePrimMsg :: TyCon -> ErrMsg
562 mkCasePrimMsg tycon sty
563 = ppAbove (ppStr "An algebraic case on a primitive type:")
566 mkCaseAbstractMsg :: TyCon -> ErrMsg
567 mkCaseAbstractMsg tycon sty
568 = ppAbove (ppStr "An algebraic case on some weird type:")
571 mkDefltMsg :: CoreCaseDefault -> ErrMsg
573 = ppAbove (ppStr "Binder in case default doesn't match type of scrutinee:")
576 mkAppMsg :: Type -> Type -> CoreExpr -> ErrMsg
577 mkAppMsg fun arg expr sty
578 = ppAboves [ppStr "Argument values doesn't match argument type:",
579 ppHang (ppStr "Fun type:") 4 (ppr sty fun),
580 ppHang (ppStr "Arg type:") 4 (ppr sty arg),
581 ppHang (ppStr "Expression:") 4 (pp_expr sty expr)]
583 mkTyAppMsg :: FAST_STRING -> Type -> Type -> CoreExpr -> ErrMsg
584 mkTyAppMsg msg ty arg expr sty
585 = ppAboves [ppCat [ppPStr msg, ppStr "type application:"],
586 ppHang (ppStr "Exp type:") 4 (ppr sty ty),
587 ppHang (ppStr "Arg type:") 4 (ppr sty arg),
588 ppHang (ppStr "Expression:") 4 (pp_expr sty expr)]
590 mkUsageAppMsg :: Type -> Usage -> CoreExpr -> ErrMsg
591 mkUsageAppMsg ty u expr sty
592 = ppAboves [ppStr "Illegal usage application:",
593 ppHang (ppStr "Exp type:") 4 (ppr sty ty),
594 ppHang (ppStr "Usage exp:") 4 (ppr sty u),
595 ppHang (ppStr "Expression:") 4 (pp_expr sty expr)]
597 mkAlgAltMsg1 :: Type -> ErrMsg
599 = ppAbove (ppStr "In some case statement, type of scrutinee is not a data type:")
602 mkAlgAltMsg2 :: Type -> Id -> ErrMsg
603 mkAlgAltMsg2 ty con sty
605 ppStr "In some algebraic case alternative, constructor is not a constructor of scrutinee type:",
610 mkAlgAltMsg3 :: Id -> [Id] -> ErrMsg
611 mkAlgAltMsg3 con alts sty
613 ppStr "In some algebraic case alternative, number of arguments doesn't match constructor:",
618 mkAlgAltMsg4 :: Type -> Id -> ErrMsg
619 mkAlgAltMsg4 ty arg sty
621 ppStr "In some algebraic case alternative, type of argument doesn't match data constructor:",
626 mkPrimAltMsg :: (Literal, CoreExpr) -> ErrMsg
629 (ppStr "In a primitive case alternative, type of literal doesn't match type of scrutinee:")
632 mkRhsMsg :: Id -> Type -> ErrMsg
633 mkRhsMsg binder ty sty
635 [ppCat [ppStr "The type of this binder doesn't match the type of its RHS:",
637 ppCat [ppStr "Binder's type:", ppr sty (idType binder)],
638 ppCat [ppStr "Rhs type:", ppr sty ty]]
640 mkRhsPrimMsg :: Id -> CoreExpr -> ErrMsg
641 mkRhsPrimMsg binder rhs sty
642 = ppAboves [ppCat [ppStr "The type of this binder is primitive:",
644 ppCat [ppStr "Binder's type:", ppr sty (idType binder)]
647 mkSpecTyAppMsg :: CoreArg -> ErrMsg
648 mkSpecTyAppMsg arg sty
650 (ppStr "Unboxed types in a type application (after specialisation):")
653 pp_expr :: PprStyle -> CoreExpr -> Pretty
655 = pprCoreExpr sty (pprBigCoreBinder sty) (pprTypedCoreBinder sty) (pprTypedCoreBinder sty) expr