Add kind equalities to GHC.
[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, DeriveDataTypeable, MultiWayIf #-}
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, 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, isTyCoVar,
56 isGlobalId, isExportedId,
57 mustHaveLocalBinding,
58
59 -- ** Constructing 'TyVar's
60 mkTyVar, mkTcTyVar,
61
62 -- ** Taking 'TyVar's apart
63 tyVarName, tyVarKind, tcTyVarDetails, setTcTyVarDetails,
64
65 -- ** Modifying 'TyVar's
66 setTyVarName, setTyVarUnique, setTyVarKind, updateTyVarKind,
67 updateTyVarKindM
68
69 ) where
70
71 #include "HsVersions.h"
72
73 import {-# SOURCE #-} TyCoRep( Type, Kind )
74 import {-# SOURCE #-} TcType( TcTyVarDetails, pprTcTyVarDetails, vanillaSkolemTv )
75 import {-# SOURCE #-} IdInfo( IdDetails, IdInfo, coVarDetails, isCoVarDetails, vanillaIdInfo, pprIdDetails )
76
77 import Name hiding (varName)
78 import Unique
79 import Util
80 import DynFlags
81 import FastString
82 import Outputable
83
84 import Data.Data
85
86 {-
87 ************************************************************************
88 * *
89 Synonyms
90 * *
91 ************************************************************************
92 -- These synonyms are here and not in Id because otherwise we need a very
93 -- large number of SOURCE imports of Id.hs :-(
94 -}
95
96 type Id = Var -- A term-level identifier
97
98 type TyVar = Var -- Type *or* kind variable (historical)
99
100 type TKVar = Var -- Type *or* kind variable (historical)
101 type TypeVar = Var -- Definitely a type variable
102 type KindVar = Var -- Definitely a kind variable
103 -- See Note [Kind and type variables]
104
105 -- See Note [Evidence: EvIds and CoVars]
106 type EvId = Id -- Term-level evidence: DictId, IpId, or EqVar
107 type EvVar = EvId -- ...historical name for EvId
108 type DFunId = Id -- A dictionary function
109 type DictId = EvId -- A dictionary variable
110 type IpId = EvId -- A term-level implicit parameter
111 type EqVar = EvId -- Boxed equality evidence
112
113 type CoVar = Id -- See Note [Evidence: EvIds and CoVars]
114
115 type TyCoVar = Id -- Type, kind, *or* coercion variable
116
117 {-
118 Note [Evidence: EvIds and CoVars]
119 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
120 * An EvId (evidence Id) is a term-level evidence variable
121 (dictionary, implicit parameter, or equality). Could be boxed or unboxed.
122
123 * DictId, IpId, and EqVar are synonyms when we know what kind of
124 evidence we are talking about. For example, an EqVar has type (t1 ~ t2).
125
126 Note [Kind and type variables]
127 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
128 Before kind polymorphism, TyVar were used to mean type variables. Now
129 they are use to mean kind *or* type variables. KindVar is used when we
130 know for sure that it is a kind variable. In future, we might want to
131 go over the whole compiler code to use:
132 - TKVar to mean kind or type variables
133 - TypeVar to mean type variables only
134 - KindVar to mean kind variables
135
136
137 ************************************************************************
138 * *
139 \subsection{The main data type declarations}
140 * *
141 ************************************************************************
142
143
144 Every @Var@ has a @Unique@, to uniquify it and for fast comparison, a
145 @Type@, and an @IdInfo@ (non-essential info about it, e.g.,
146 strictness). The essential info about different kinds of @Vars@ is
147 in its @VarDetails@.
148 -}
149
150 -- | Essentially a typed 'Name', that may also contain some additional information
151 -- about the 'Var' and it's use sites.
152 data Var
153 = TyVar { -- Type and kind variables
154 -- see Note [Kind and type variables]
155 varName :: !Name,
156 realUnique :: {-# UNPACK #-} !Int,
157 -- ^ Key for fast comparison
158 -- Identical to the Unique in the name,
159 -- cached here for speed
160 varType :: Kind -- ^ The type or kind of the 'Var' in question
161 }
162
163 | TcTyVar { -- Used only during type inference
164 -- Used for kind variables during
165 -- inference, as well
166 varName :: !Name,
167 realUnique :: {-# UNPACK #-} !Int,
168 varType :: Kind,
169 tc_tv_details :: TcTyVarDetails
170 }
171
172 | Id {
173 varName :: !Name,
174 realUnique :: {-# UNPACK #-} !Int,
175 varType :: Type,
176 idScope :: IdScope,
177 id_details :: IdDetails, -- Stable, doesn't change
178 id_info :: IdInfo } -- Unstable, updated by simplifier
179 deriving Typeable
180
181 data IdScope -- See Note [GlobalId/LocalId]
182 = GlobalId
183 | LocalId ExportFlag
184
185 data ExportFlag -- See Note [ExportFlag on binders]
186 = NotExported -- ^ Not exported: may be discarded as dead code.
187 | Exported -- ^ Exported: kept alive
188
189 {- Note [ExportFlag on binders]
190 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
191 An ExportFlag of "Exported" on a top-level binder says "keep this
192 binding alive; do not drop it as dead code". This transitively
193 keeps alive all the other top-level bindings that this binding refers
194 to. This property is persisted all the way down the pipeline, so that
195 the binding will be compiled all the way to object code, and its
196 symbols will appear in the linker symbol table.
197
198 However, note that this use of "exported" is quite different to the
199 export list on a Haskell module. Setting the ExportFlag on an Id does
200 /not/ mean that if you import the module (in Haskell source code) you
201 will see this Id. Of course, things that appear in the export list
202 of the source Haskell module do indeed have their ExportFlag set.
203 But many other things, such as dictionary functions, are kept alive
204 by having their ExportFlag set, even though they are not exported
205 in the source-code sense.
206
207 We should probably use a different term for ExportFlag, like
208 KeepAlive.
209
210 Note [GlobalId/LocalId]
211 ~~~~~~~~~~~~~~~~~~~~~~~
212 A GlobalId is
213 * always a constant (top-level)
214 * imported, or data constructor, or primop, or record selector
215 * has a Unique that is globally unique across the whole
216 GHC invocation (a single invocation may compile multiple modules)
217 * never treated as a candidate by the free-variable finder;
218 it's a constant!
219
220 A LocalId is
221 * bound within an expression (lambda, case, local let(rec))
222 * or defined at top level in the module being compiled
223 * always treated as a candidate by the free-variable finder
224
225 After CoreTidy, top-level LocalIds are turned into GlobalIds
226 -}
227
228 instance Outputable Var where
229 ppr var = sdocWithDynFlags $ \dflags ->
230 getPprStyle $ \ppr_style ->
231 if | debugStyle ppr_style && (not (gopt Opt_SuppressVarKinds dflags))
232 -> parens (ppr (varName var) <+> ppr_debug var ppr_style <+>
233 dcolon <+> ppr (tyVarKind var))
234 | otherwise
235 -> ppr (varName var) <> ppr_debug var ppr_style
236
237 ppr_debug :: Var -> PprStyle -> SDoc
238 ppr_debug (TyVar {}) sty
239 | debugStyle sty = brackets (ptext (sLit "tv"))
240 ppr_debug (TcTyVar {tc_tv_details = d}) sty
241 | dumpStyle sty || debugStyle sty = brackets (pprTcTyVarDetails d)
242 ppr_debug (Id { idScope = s, id_details = d }) sty
243 | debugStyle sty = brackets (ppr_id_scope s <> pprIdDetails d)
244 ppr_debug _ _ = empty
245
246 ppr_id_scope :: IdScope -> SDoc
247 ppr_id_scope GlobalId = ptext (sLit "gid")
248 ppr_id_scope (LocalId Exported) = ptext (sLit "lidx")
249 ppr_id_scope (LocalId NotExported) = ptext (sLit "lid")
250
251 instance NamedThing Var where
252 getName = varName
253
254 instance Uniquable Var where
255 getUnique = varUnique
256
257 instance Eq Var where
258 a == b = realUnique a == realUnique b
259
260 instance Ord Var where
261 a <= b = realUnique a <= realUnique b
262 a < b = realUnique a < realUnique b
263 a >= b = realUnique a >= realUnique b
264 a > b = realUnique a > realUnique b
265 a `compare` b = varUnique a `compare` varUnique b
266
267 instance Data Var where
268 -- don't traverse?
269 toConstr _ = abstractConstr "Var"
270 gunfold _ _ = error "gunfold"
271 dataTypeOf _ = mkNoRepType "Var"
272
273 varUnique :: Var -> Unique
274 varUnique var = mkUniqueGrimily (realUnique var)
275
276 setVarUnique :: Var -> Unique -> Var
277 setVarUnique var uniq
278 = var { realUnique = getKey uniq,
279 varName = setNameUnique (varName var) uniq }
280
281 setVarName :: Var -> Name -> Var
282 setVarName var new_name
283 = var { realUnique = getKey (getUnique new_name),
284 varName = new_name }
285
286 setVarType :: Id -> Type -> Id
287 setVarType id ty = id { varType = ty }
288
289 updateVarType :: (Type -> Type) -> Id -> Id
290 updateVarType f id = id { varType = f (varType id) }
291
292 updateVarTypeM :: Monad m => (Type -> m Type) -> Id -> m Id
293 updateVarTypeM f id = do { ty' <- f (varType id)
294 ; return (id { varType = ty' }) }
295
296 {-
297 ************************************************************************
298 * *
299 \subsection{Type and kind variables}
300 * *
301 ************************************************************************
302 -}
303
304 tyVarName :: TyVar -> Name
305 tyVarName = varName
306
307 tyVarKind :: TyVar -> Kind
308 tyVarKind = varType
309
310 setTyVarUnique :: TyVar -> Unique -> TyVar
311 setTyVarUnique = setVarUnique
312
313 setTyVarName :: TyVar -> Name -> TyVar
314 setTyVarName = setVarName
315
316 setTyVarKind :: TyVar -> Kind -> TyVar
317 setTyVarKind tv k = tv {varType = k}
318
319 updateTyVarKind :: (Kind -> Kind) -> TyVar -> TyVar
320 updateTyVarKind update tv = tv {varType = update (tyVarKind tv)}
321
322 updateTyVarKindM :: (Monad m) => (Kind -> m Kind) -> TyVar -> m TyVar
323 updateTyVarKindM update tv
324 = do { k' <- update (tyVarKind tv)
325 ; return $ tv {varType = k'} }
326
327 mkTyVar :: Name -> Kind -> TyVar
328 mkTyVar name kind = TyVar { varName = name
329 , realUnique = getKey (nameUnique name)
330 , varType = kind
331 }
332
333 mkTcTyVar :: Name -> Kind -> TcTyVarDetails -> TyVar
334 mkTcTyVar name kind details
335 = -- NB: 'kind' may be a coercion kind; cf, 'TcMType.newMetaCoVar'
336 TcTyVar { varName = name,
337 realUnique = getKey (nameUnique name),
338 varType = kind,
339 tc_tv_details = details
340 }
341
342 tcTyVarDetails :: TyVar -> TcTyVarDetails
343 tcTyVarDetails (TcTyVar { tc_tv_details = details }) = details
344 tcTyVarDetails (TyVar {}) = vanillaSkolemTv
345 tcTyVarDetails var = pprPanic "tcTyVarDetails" (ppr var <+> dcolon <+> ppr (tyVarKind var))
346
347 setTcTyVarDetails :: TyVar -> TcTyVarDetails -> TyVar
348 setTcTyVarDetails tv details = tv { tc_tv_details = details }
349
350 {-
351 %************************************************************************
352 %* *
353 \subsection{Ids}
354 * *
355 ************************************************************************
356 -}
357
358 idInfo :: Id -> IdInfo
359 idInfo (Id { id_info = info }) = info
360 idInfo other = pprPanic "idInfo" (ppr other)
361
362 idDetails :: Id -> IdDetails
363 idDetails (Id { id_details = details }) = details
364 idDetails other = pprPanic "idDetails" (ppr other)
365
366 -- The next three have a 'Var' suffix even though they always build
367 -- Ids, because Id.hs uses 'mkGlobalId' etc with different types
368 mkGlobalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
369 mkGlobalVar details name ty info
370 = mk_id name ty GlobalId details info
371
372 mkLocalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
373 mkLocalVar details name ty info
374 = mk_id name ty (LocalId NotExported) details info
375
376 mkCoVar :: Name -> Type -> CoVar
377 -- Coercion variables have no IdInfo
378 mkCoVar name ty = mk_id name ty (LocalId NotExported) coVarDetails vanillaIdInfo
379
380 -- | Exported 'Var's will not be removed as dead code
381 mkExportedLocalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
382 mkExportedLocalVar details name ty info
383 = mk_id name ty (LocalId Exported) details info
384
385 mk_id :: Name -> Type -> IdScope -> IdDetails -> IdInfo -> Id
386 mk_id name ty scope details info
387 = Id { varName = name,
388 realUnique = getKey (nameUnique name),
389 varType = ty,
390 idScope = scope,
391 id_details = details,
392 id_info = info }
393
394 -------------------
395 lazySetIdInfo :: Id -> IdInfo -> Var
396 lazySetIdInfo id info = id { id_info = info }
397
398 setIdDetails :: Id -> IdDetails -> Id
399 setIdDetails id details = id { id_details = details }
400
401 globaliseId :: Id -> Id
402 -- ^ If it's a local, make it global
403 globaliseId id = id { idScope = GlobalId }
404
405 setIdExported :: Id -> Id
406 -- ^ Exports the given local 'Id'. Can also be called on global 'Id's, such as data constructors
407 -- and class operations, which are born as global 'Id's and automatically exported
408 setIdExported id@(Id { idScope = LocalId {} }) = id { idScope = LocalId Exported }
409 setIdExported id@(Id { idScope = GlobalId }) = id
410 setIdExported tv = pprPanic "setIdExported" (ppr tv)
411
412 setIdNotExported :: Id -> Id
413 -- ^ We can only do this to LocalIds
414 setIdNotExported id = ASSERT( isLocalId id )
415 id { idScope = LocalId NotExported }
416
417 {-
418 ************************************************************************
419 * *
420 \subsection{Predicates over variables}
421 * *
422 ************************************************************************
423 -}
424
425 isTyVar :: Var -> Bool
426 isTyVar = isTKVar -- Historical
427
428 isTKVar :: Var -> Bool -- True of both type and kind variables
429 isTKVar (TyVar {}) = True
430 isTKVar (TcTyVar {}) = True
431 isTKVar _ = False
432
433 isTcTyVar :: Var -> Bool
434 isTcTyVar (TcTyVar {}) = True
435 isTcTyVar _ = False
436
437 isId :: Var -> Bool
438 isId (Id {}) = True
439 isId _ = False
440
441 isTyCoVar :: Var -> Bool
442 isTyCoVar v = isTyVar v || isCoVar v
443
444 isCoVar :: Var -> Bool
445 isCoVar v = isId v && isCoVarDetails (id_details v)
446
447 isLocalId :: Var -> Bool
448 isLocalId (Id { idScope = LocalId _ }) = True
449 isLocalId _ = False
450
451 -- | 'isLocalVar' returns @True@ for type variables as well as local 'Id's
452 -- These are the variables that we need to pay attention to when finding free
453 -- variables, or doing dependency analysis.
454 isLocalVar :: Var -> Bool
455 isLocalVar v = not (isGlobalId v)
456
457 isGlobalId :: Var -> Bool
458 isGlobalId (Id { idScope = GlobalId }) = True
459 isGlobalId _ = False
460
461 -- | 'mustHaveLocalBinding' returns @True@ of 'Id's and 'TyVar's
462 -- that must have a binding in this module. The converse
463 -- is not quite right: there are some global 'Id's that must have
464 -- bindings, such as record selectors. But that doesn't matter,
465 -- because it's only used for assertions
466 mustHaveLocalBinding :: Var -> Bool
467 mustHaveLocalBinding var = isLocalVar var
468
469 -- | 'isExportedIdVar' means \"don't throw this away\"
470 isExportedId :: Var -> Bool
471 isExportedId (Id { idScope = GlobalId }) = True
472 isExportedId (Id { idScope = LocalId Exported}) = True
473 isExportedId _ = False