Comments about -Wredundant-constraints
[ghc.git] / compiler / basicTypes / Var.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5 \section{@Vars@: Variables}
6 -}
7
8 {-# LANGUAGE CPP, MultiWayIf, FlexibleInstances, DeriveDataTypeable #-}
9
10 -- |
11 -- #name_types#
12 -- GHC uses several kinds of name internally:
13 --
14 -- * 'OccName.OccName': see "OccName#name_types"
15 --
16 -- * 'RdrName.RdrName': see "RdrName#name_types"
17 --
18 -- * 'Name.Name': see "Name#name_types"
19 --
20 -- * 'Id.Id': see "Id#name_types"
21 --
22 -- * 'Var.Var' is a synonym for the 'Id.Id' type but it may additionally
23 -- potentially contain type variables, which have a 'TyCoRep.Kind'
24 -- rather than a 'TyCoRep.Type' and only contain some extra
25 -- details during typechecking.
26 --
27 -- These 'Var.Var' names may either be global or local, see "Var#globalvslocal"
28 --
29 -- #globalvslocal#
30 -- Global 'Id's and 'Var's are those that are imported or correspond
31 -- to a data constructor, primitive operation, or record selectors.
32 -- Local 'Id's and 'Var's are those bound within an expression
33 -- (e.g. by a lambda) or at the top level of the module being compiled.
34
35 module Var (
36 -- * The main data type and synonyms
37 Var, CoVar, Id, NcId, DictId, DFunId, EvVar, EqVar, EvId, IpId,
38 TyVar, TypeVar, KindVar, TKVar, TyCoVar,
39
40 -- ** Taking 'Var's apart
41 varName, varUnique, varType,
42
43 -- ** Modifying 'Var's
44 setVarName, setVarUnique, setVarType, updateVarType,
45 updateVarTypeM,
46
47 -- ** Constructing, taking apart, modifying 'Id's
48 mkGlobalVar, mkLocalVar, mkExportedLocalVar, mkCoVar,
49 idInfo, idDetails,
50 lazySetIdInfo, setIdDetails, globaliseId,
51 setIdExported, setIdNotExported,
52
53 -- ** Predicates
54 isId, isTKVar, isTyVar, isTcTyVar,
55 isLocalVar, isLocalId, isCoVar, isNonCoVarId, isTyCoVar,
56 isGlobalId, isExportedId,
57 mustHaveLocalBinding,
58
59 -- * TyVar's
60 TyVarBndr(..), ArgFlag(..), TyVarBinder,
61 binderVar, binderVars, binderArgFlag, binderKind,
62 isVisibleArgFlag, isInvisibleArgFlag, sameVis,
63
64 -- ** Constructing TyVar's
65 mkTyVar, mkTcTyVar,
66
67 -- ** Taking 'TyVar's apart
68 tyVarName, tyVarKind, tcTyVarDetails, setTcTyVarDetails,
69
70 -- ** Modifying 'TyVar's
71 setTyVarName, setTyVarUnique, setTyVarKind, updateTyVarKind,
72 updateTyVarKindM,
73
74 nonDetCmpVar
75
76 ) where
77
78 #include "HsVersions.h"
79
80 import {-# SOURCE #-} TyCoRep( Type, Kind, pprKind )
81 import {-# SOURCE #-} TcType( TcTyVarDetails, pprTcTyVarDetails, vanillaSkolemTv )
82 import {-# SOURCE #-} IdInfo( IdDetails, IdInfo, coVarDetails, isCoVarDetails, vanillaIdInfo, pprIdDetails )
83
84 import Name hiding (varName)
85 import Unique ( Uniquable, Unique, getKey, getUnique
86 , mkUniqueGrimily, nonDetCmpUnique )
87 import Util
88 import Binary
89 import DynFlags
90 import Outputable
91
92 import Data.Data
93
94 {-
95 ************************************************************************
96 * *
97 Synonyms
98 * *
99 ************************************************************************
100 -- These synonyms are here and not in Id because otherwise we need a very
101 -- large number of SOURCE imports of Id.hs :-(
102 -}
103
104 -- | Identifier
105 type Id = Var -- A term-level identifier
106 -- predicate: isId
107
108 -- | Coercion Variable
109 type CoVar = Id -- See Note [Evidence: EvIds and CoVars]
110 -- predicate: isCoVar
111
112 -- |
113 type NcId = Id -- A term-level (value) variable that is
114 -- /not/ an (unlifted) coercion
115 -- predicate: isNonCoVarId
116
117 -- | Type or kind Variable
118 type TyVar = Var -- Type *or* kind variable (historical)
119
120 -- | Type or Kind Variable
121 type TKVar = Var -- Type *or* kind variable (historical)
122
123 -- | Type Variable
124 type TypeVar = Var -- Definitely a type variable
125
126 -- | Kind Variable
127 type KindVar = Var -- Definitely a kind variable
128 -- See Note [Kind and type variables]
129
130 -- See Note [Evidence: EvIds and CoVars]
131 -- | Evidence Identifier
132 type EvId = Id -- Term-level evidence: DictId, IpId, or EqVar
133
134 -- | Evidence Variable
135 type EvVar = EvId -- ...historical name for EvId
136
137 -- | Dictionary Function Identifier
138 type DFunId = Id -- A dictionary function
139
140 -- | Dictionary Identifier
141 type DictId = EvId -- A dictionary variable
142
143 -- | Implicit parameter Identifier
144 type IpId = EvId -- A term-level implicit parameter
145
146 -- | Equality Variable
147 type EqVar = EvId -- Boxed equality evidence
148
149 -- | Type or Coercion Variable
150 type TyCoVar = Id -- Type, *or* coercion variable
151 -- predicate: isTyCoVar
152
153 {- Note [Evidence: EvIds and CoVars]
154 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
155 * An EvId (evidence Id) is a term-level evidence variable
156 (dictionary, implicit parameter, or equality). Could be boxed or unboxed.
157
158 * DictId, IpId, and EqVar are synonyms when we know what kind of
159 evidence we are talking about. For example, an EqVar has type (t1 ~ t2).
160
161 * A CoVar is always an un-lifted coercion, of type (t1 ~# t2) or (t1 ~R# t2)
162
163 Note [Kind and type variables]
164 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
165 Before kind polymorphism, TyVar were used to mean type variables. Now
166 they are use to mean kind *or* type variables. KindVar is used when we
167 know for sure that it is a kind variable. In future, we might want to
168 go over the whole compiler code to use:
169 - TKVar to mean kind or type variables
170 - TypeVar to mean type variables only
171 - KindVar to mean kind variables
172
173
174 ************************************************************************
175 * *
176 \subsection{The main data type declarations}
177 * *
178 ************************************************************************
179
180
181 Every @Var@ has a @Unique@, to uniquify it and for fast comparison, a
182 @Type@, and an @IdInfo@ (non-essential info about it, e.g.,
183 strictness). The essential info about different kinds of @Vars@ is
184 in its @VarDetails@.
185 -}
186
187 -- | Variable
188 --
189 -- Essentially a typed 'Name', that may also contain some additional information
190 -- about the 'Var' and it's use sites.
191 data Var
192 = TyVar { -- Type and kind variables
193 -- see Note [Kind and type variables]
194 varName :: !Name,
195 realUnique :: {-# UNPACK #-} !Int,
196 -- ^ Key for fast comparison
197 -- Identical to the Unique in the name,
198 -- cached here for speed
199 varType :: Kind -- ^ The type or kind of the 'Var' in question
200 }
201
202 | TcTyVar { -- Used only during type inference
203 -- Used for kind variables during
204 -- inference, as well
205 varName :: !Name,
206 realUnique :: {-# UNPACK #-} !Int,
207 varType :: Kind,
208 tc_tv_details :: TcTyVarDetails
209 }
210
211 | Id {
212 varName :: !Name,
213 realUnique :: {-# UNPACK #-} !Int,
214 varType :: Type,
215 idScope :: IdScope,
216 id_details :: IdDetails, -- Stable, doesn't change
217 id_info :: IdInfo } -- Unstable, updated by simplifier
218
219 -- | Identifier Scope
220 data IdScope -- See Note [GlobalId/LocalId]
221 = GlobalId
222 | LocalId ExportFlag
223
224 data ExportFlag -- See Note [ExportFlag on binders]
225 = NotExported -- ^ Not exported: may be discarded as dead code.
226 | Exported -- ^ Exported: kept alive
227
228 {- Note [ExportFlag on binders]
229 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
230 An ExportFlag of "Exported" on a top-level binder says "keep this
231 binding alive; do not drop it as dead code". This transitively
232 keeps alive all the other top-level bindings that this binding refers
233 to. This property is persisted all the way down the pipeline, so that
234 the binding will be compiled all the way to object code, and its
235 symbols will appear in the linker symbol table.
236
237 However, note that this use of "exported" is quite different to the
238 export list on a Haskell module. Setting the ExportFlag on an Id does
239 /not/ mean that if you import the module (in Haskell source code) you
240 will see this Id. Of course, things that appear in the export list
241 of the source Haskell module do indeed have their ExportFlag set.
242 But many other things, such as dictionary functions, are kept alive
243 by having their ExportFlag set, even though they are not exported
244 in the source-code sense.
245
246 We should probably use a different term for ExportFlag, like
247 KeepAlive.
248
249 Note [GlobalId/LocalId]
250 ~~~~~~~~~~~~~~~~~~~~~~~
251 A GlobalId is
252 * always a constant (top-level)
253 * imported, or data constructor, or primop, or record selector
254 * has a Unique that is globally unique across the whole
255 GHC invocation (a single invocation may compile multiple modules)
256 * never treated as a candidate by the free-variable finder;
257 it's a constant!
258
259 A LocalId is
260 * bound within an expression (lambda, case, local let(rec))
261 * or defined at top level in the module being compiled
262 * always treated as a candidate by the free-variable finder
263
264 After CoreTidy, top-level LocalIds are turned into GlobalIds
265 -}
266
267 instance Outputable Var where
268 ppr var = sdocWithDynFlags $ \dflags ->
269 getPprStyle $ \ppr_style ->
270 if | debugStyle ppr_style && (not (gopt Opt_SuppressVarKinds dflags))
271 -> parens (ppr (varName var) <+> ppr_debug var ppr_style <+>
272 dcolon <+> pprKind (tyVarKind var))
273 | otherwise
274 -> ppr (varName var) <> ppr_debug var ppr_style
275
276 ppr_debug :: Var -> PprStyle -> SDoc
277 ppr_debug (TyVar {}) sty
278 | debugStyle sty = brackets (text "tv")
279 ppr_debug (TcTyVar {tc_tv_details = d}) sty
280 | dumpStyle sty || debugStyle sty = brackets (pprTcTyVarDetails d)
281 ppr_debug (Id { idScope = s, id_details = d }) sty
282 | debugStyle sty = brackets (ppr_id_scope s <> pprIdDetails d)
283 ppr_debug _ _ = empty
284
285 ppr_id_scope :: IdScope -> SDoc
286 ppr_id_scope GlobalId = text "gid"
287 ppr_id_scope (LocalId Exported) = text "lidx"
288 ppr_id_scope (LocalId NotExported) = text "lid"
289
290 instance NamedThing Var where
291 getName = varName
292
293 instance Uniquable Var where
294 getUnique = varUnique
295
296 instance Eq Var where
297 a == b = realUnique a == realUnique b
298
299 instance Ord Var where
300 a <= b = realUnique a <= realUnique b
301 a < b = realUnique a < realUnique b
302 a >= b = realUnique a >= realUnique b
303 a > b = realUnique a > realUnique b
304 a `compare` b = a `nonDetCmpVar` b
305
306 -- | Compare Vars by their Uniques.
307 -- This is what Ord Var does, provided here to make it explicit at the
308 -- call-site that it can introduce non-determinism.
309 -- See Note [Unique Determinism]
310 nonDetCmpVar :: Var -> Var -> Ordering
311 nonDetCmpVar a b = varUnique a `nonDetCmpUnique` varUnique b
312
313 instance Data Var where
314 -- don't traverse?
315 toConstr _ = abstractConstr "Var"
316 gunfold _ _ = error "gunfold"
317 dataTypeOf _ = mkNoRepType "Var"
318
319 varUnique :: Var -> Unique
320 varUnique var = mkUniqueGrimily (realUnique var)
321
322 setVarUnique :: Var -> Unique -> Var
323 setVarUnique var uniq
324 = var { realUnique = getKey uniq,
325 varName = setNameUnique (varName var) uniq }
326
327 setVarName :: Var -> Name -> Var
328 setVarName var new_name
329 = var { realUnique = getKey (getUnique new_name),
330 varName = new_name }
331
332 setVarType :: Id -> Type -> Id
333 setVarType id ty = id { varType = ty }
334
335 updateVarType :: (Type -> Type) -> Id -> Id
336 updateVarType f id = id { varType = f (varType id) }
337
338 updateVarTypeM :: Monad m => (Type -> m Type) -> Id -> m Id
339 updateVarTypeM f id = do { ty' <- f (varType id)
340 ; return (id { varType = ty' }) }
341
342 {- *********************************************************************
343 * *
344 * ArgFlag
345 * *
346 ********************************************************************* -}
347
348 -- | Argument Flag
349 --
350 -- Is something required to appear in source Haskell ('Required'),
351 -- permitted by request ('Specified') (visible type application), or
352 -- prohibited entirely from appearing in source Haskell ('Inferred')?
353 -- See Note [TyBinders and ArgFlags] in TyCoRep
354 data ArgFlag = Required | Specified | Inferred
355 deriving (Eq, Data)
356
357 -- | Does this 'ArgFlag' classify an argument that is written in Haskell?
358 isVisibleArgFlag :: ArgFlag -> Bool
359 isVisibleArgFlag Required = True
360 isVisibleArgFlag _ = False
361
362 -- | Does this 'ArgFlag' classify an argument that is not written in Haskell?
363 isInvisibleArgFlag :: ArgFlag -> Bool
364 isInvisibleArgFlag = not . isVisibleArgFlag
365
366 -- | Do these denote the same level of visibility? 'Required'
367 -- arguments are visible, others are not. So this function
368 -- equates 'Specified' and 'Inferred'. Used for printing.
369 sameVis :: ArgFlag -> ArgFlag -> Bool
370 sameVis Required Required = True
371 sameVis Required _ = False
372 sameVis _ Required = False
373 sameVis _ _ = True
374
375 {- *********************************************************************
376 * *
377 * TyVarBndr, TyVarBinder
378 * *
379 ********************************************************************* -}
380
381 -- Type Variable Binder
382 --
383 -- TyVarBndr is polymorphic in both tyvar and visiblity fields:
384 -- * tyvar can be TyVar or IfaceTv
385 -- * argf can be ArgFlag or TyConBndrVis
386 data TyVarBndr tyvar argf = TvBndr tyvar argf
387 deriving( Data )
388
389 -- | Type Variable Binder
390 --
391 -- A 'TyVarBinder' is the binder of a ForAllTy
392 -- It's convenient to define this synonym here rather its natural
393 -- home in TyCoRep, because it's used in DataCon.hs-boot
394 type TyVarBinder = TyVarBndr TyVar ArgFlag
395
396 binderVar :: TyVarBndr tv argf -> tv
397 binderVar (TvBndr v _) = v
398
399 binderVars :: [TyVarBndr tv argf] -> [tv]
400 binderVars tvbs = map binderVar tvbs
401
402 binderArgFlag :: TyVarBndr tv argf -> argf
403 binderArgFlag (TvBndr _ argf) = argf
404
405 binderKind :: TyVarBndr TyVar argf -> Kind
406 binderKind (TvBndr tv _) = tyVarKind tv
407
408 {-
409 ************************************************************************
410 * *
411 * Type and kind variables *
412 * *
413 ************************************************************************
414 -}
415
416 tyVarName :: TyVar -> Name
417 tyVarName = varName
418
419 tyVarKind :: TyVar -> Kind
420 tyVarKind = varType
421
422 setTyVarUnique :: TyVar -> Unique -> TyVar
423 setTyVarUnique = setVarUnique
424
425 setTyVarName :: TyVar -> Name -> TyVar
426 setTyVarName = setVarName
427
428 setTyVarKind :: TyVar -> Kind -> TyVar
429 setTyVarKind tv k = tv {varType = k}
430
431 updateTyVarKind :: (Kind -> Kind) -> TyVar -> TyVar
432 updateTyVarKind update tv = tv {varType = update (tyVarKind tv)}
433
434 updateTyVarKindM :: (Monad m) => (Kind -> m Kind) -> TyVar -> m TyVar
435 updateTyVarKindM update tv
436 = do { k' <- update (tyVarKind tv)
437 ; return $ tv {varType = k'} }
438
439 mkTyVar :: Name -> Kind -> TyVar
440 mkTyVar name kind = TyVar { varName = name
441 , realUnique = getKey (nameUnique name)
442 , varType = kind
443 }
444
445 mkTcTyVar :: Name -> Kind -> TcTyVarDetails -> TyVar
446 mkTcTyVar name kind details
447 = -- NB: 'kind' may be a coercion kind; cf, 'TcMType.newMetaCoVar'
448 TcTyVar { varName = name,
449 realUnique = getKey (nameUnique name),
450 varType = kind,
451 tc_tv_details = details
452 }
453
454 tcTyVarDetails :: TyVar -> TcTyVarDetails
455 tcTyVarDetails (TcTyVar { tc_tv_details = details }) = details
456 tcTyVarDetails (TyVar {}) = vanillaSkolemTv
457 tcTyVarDetails var = pprPanic "tcTyVarDetails" (ppr var <+> dcolon <+> pprKind (tyVarKind var))
458
459 setTcTyVarDetails :: TyVar -> TcTyVarDetails -> TyVar
460 setTcTyVarDetails tv details = tv { tc_tv_details = details }
461
462 -------------------------------------
463 instance Outputable tv => Outputable (TyVarBndr tv ArgFlag) where
464 ppr (TvBndr v Required) = ppr v
465 ppr (TvBndr v Specified) = char '@' <> ppr v
466 ppr (TvBndr v Inferred) = braces (ppr v)
467
468 instance Outputable ArgFlag where
469 ppr Required = text "[req]"
470 ppr Specified = text "[spec]"
471 ppr Inferred = text "[infrd]"
472
473 instance (Binary tv, Binary vis) => Binary (TyVarBndr tv vis) where
474 put_ bh (TvBndr tv vis) = do { put_ bh tv; put_ bh vis }
475
476 get bh = do { tv <- get bh; vis <- get bh; return (TvBndr tv vis) }
477
478
479 instance Binary ArgFlag where
480 put_ bh Required = putByte bh 0
481 put_ bh Specified = putByte bh 1
482 put_ bh Inferred = putByte bh 2
483
484 get bh = do
485 h <- getByte bh
486 case h of
487 0 -> return Required
488 1 -> return Specified
489 _ -> return Inferred
490
491 {-
492 %************************************************************************
493 %* *
494 \subsection{Ids}
495 * *
496 ************************************************************************
497 -}
498
499 idInfo :: Id -> IdInfo
500 idInfo (Id { id_info = info }) = info
501 idInfo other = pprPanic "idInfo" (ppr other)
502
503 idDetails :: Id -> IdDetails
504 idDetails (Id { id_details = details }) = details
505 idDetails other = pprPanic "idDetails" (ppr other)
506
507 -- The next three have a 'Var' suffix even though they always build
508 -- Ids, because Id.hs uses 'mkGlobalId' etc with different types
509 mkGlobalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
510 mkGlobalVar details name ty info
511 = mk_id name ty GlobalId details info
512
513 mkLocalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
514 mkLocalVar details name ty info
515 = mk_id name ty (LocalId NotExported) details info
516
517 mkCoVar :: Name -> Type -> CoVar
518 -- Coercion variables have no IdInfo
519 mkCoVar name ty = mk_id name ty (LocalId NotExported) coVarDetails vanillaIdInfo
520
521 -- | Exported 'Var's will not be removed as dead code
522 mkExportedLocalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
523 mkExportedLocalVar details name ty info
524 = mk_id name ty (LocalId Exported) details info
525
526 mk_id :: Name -> Type -> IdScope -> IdDetails -> IdInfo -> Id
527 mk_id name ty scope details info
528 = Id { varName = name,
529 realUnique = getKey (nameUnique name),
530 varType = ty,
531 idScope = scope,
532 id_details = details,
533 id_info = info }
534
535 -------------------
536 lazySetIdInfo :: Id -> IdInfo -> Var
537 lazySetIdInfo id info = id { id_info = info }
538
539 setIdDetails :: Id -> IdDetails -> Id
540 setIdDetails id details = id { id_details = details }
541
542 globaliseId :: Id -> Id
543 -- ^ If it's a local, make it global
544 globaliseId id = id { idScope = GlobalId }
545
546 setIdExported :: Id -> Id
547 -- ^ Exports the given local 'Id'. Can also be called on global 'Id's, such as data constructors
548 -- and class operations, which are born as global 'Id's and automatically exported
549 setIdExported id@(Id { idScope = LocalId {} }) = id { idScope = LocalId Exported }
550 setIdExported id@(Id { idScope = GlobalId }) = id
551 setIdExported tv = pprPanic "setIdExported" (ppr tv)
552
553 setIdNotExported :: Id -> Id
554 -- ^ We can only do this to LocalIds
555 setIdNotExported id = ASSERT( isLocalId id )
556 id { idScope = LocalId NotExported }
557
558 {-
559 ************************************************************************
560 * *
561 \subsection{Predicates over variables}
562 * *
563 ************************************************************************
564 -}
565
566 isTyVar :: Var -> Bool
567 isTyVar = isTKVar -- Historical
568
569 isTKVar :: Var -> Bool -- True of both type and kind variables
570 isTKVar (TyVar {}) = True
571 isTKVar (TcTyVar {}) = True
572 isTKVar _ = False
573
574 isTcTyVar :: Var -> Bool
575 isTcTyVar (TcTyVar {}) = True
576 isTcTyVar _ = False
577
578 isTyCoVar :: Var -> Bool
579 isTyCoVar v = isTyVar v || isCoVar v
580
581 isId :: Var -> Bool
582 isId (Id {}) = True
583 isId _ = False
584
585 isCoVar :: Var -> Bool
586 -- A coercion variable
587 isCoVar (Id { id_details = details }) = isCoVarDetails details
588 isCoVar _ = False
589
590 isNonCoVarId :: Var -> Bool
591 -- A term variable (Id) that is /not/ a coercion variable
592 isNonCoVarId (Id { id_details = details }) = not (isCoVarDetails details)
593 isNonCoVarId _ = False
594
595 isLocalId :: Var -> Bool
596 isLocalId (Id { idScope = LocalId _ }) = True
597 isLocalId _ = False
598
599 -- | 'isLocalVar' returns @True@ for type variables as well as local 'Id's
600 -- These are the variables that we need to pay attention to when finding free
601 -- variables, or doing dependency analysis.
602 isLocalVar :: Var -> Bool
603 isLocalVar v = not (isGlobalId v)
604
605 isGlobalId :: Var -> Bool
606 isGlobalId (Id { idScope = GlobalId }) = True
607 isGlobalId _ = False
608
609 -- | 'mustHaveLocalBinding' returns @True@ of 'Id's and 'TyVar's
610 -- that must have a binding in this module. The converse
611 -- is not quite right: there are some global 'Id's that must have
612 -- bindings, such as record selectors. But that doesn't matter,
613 -- because it's only used for assertions
614 mustHaveLocalBinding :: Var -> Bool
615 mustHaveLocalBinding var = isLocalVar var
616
617 -- | 'isExportedIdVar' means \"don't throw this away\"
618 isExportedId :: Var -> Bool
619 isExportedId (Id { idScope = GlobalId }) = True
620 isExportedId (Id { idScope = LocalId Exported}) = True
621 isExportedId _ = False