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