2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
4 \section[Unique]{The @Unique@ data type}
6 @Uniques@ are used to distinguish entities in the compiler (@Ids@,
7 @Classes@, etc.) from each other. Thus, @Uniques@ are the basic
8 comparison key in the compiler.
10 If there is any single operation that needs to be fast, it is @Unique@
11 comparison. Unsurprisingly, there is quite a bit of huff-and-puff
14 Some of the other hair in this code is to be able to use a
15 ``splittable @UniqueSupply@'' if requested/possible (not standard
19 #include "HsVersions.h"
21 --<mkdependHS:friends> UniqSupply
24 Unique, Uniquable(..),
25 u2i, -- hack: used in UniqFM
27 pprUnique, pprUnique10, showUnique,
29 mkUnique, -- Used in UniqSupply
30 mkUniqueGrimily, -- Used in UniqSupply only!
32 -- now all the built-in Uniques (and functions to make them)
33 -- [the Oh-So-Wonderful Haskell module system wins again...]
39 absentErrorIdKey, -- alphabetical...
50 byteArrayPrimTyConKey,
62 enumFromThenClassOpKey,
63 enumFromThenToClassOpKey,
79 fromIntegerClassOpKey,
80 fromRationalClassOpKey,
103 mallocPtrPrimTyConKey,
107 mutableArrayPrimTyConKey,
108 mutableByteArrayPrimTyConKey,
127 return2GMPsDataConKey,
129 returnIntAndGMPDataConKey,
130 returnIntAndGMPTyConKey,
136 stablePtrPrimTyConKey,
138 stateAndAddrPrimDataConKey,
139 stateAndAddrPrimTyConKey,
140 stateAndArrayPrimDataConKey,
141 stateAndArrayPrimTyConKey,
142 stateAndByteArrayPrimDataConKey,
143 stateAndByteArrayPrimTyConKey,
144 stateAndCharPrimDataConKey,
145 stateAndCharPrimTyConKey,
146 stateAndDoublePrimDataConKey,
147 stateAndDoublePrimTyConKey,
148 stateAndFloatPrimDataConKey,
149 stateAndFloatPrimTyConKey,
150 stateAndIntPrimDataConKey,
151 stateAndIntPrimTyConKey,
152 stateAndMallocPtrPrimDataConKey,
153 stateAndMallocPtrPrimTyConKey,
154 stateAndMutableArrayPrimDataConKey,
155 stateAndMutableArrayPrimTyConKey,
156 stateAndMutableByteArrayPrimDataConKey,
157 stateAndMutableByteArrayPrimTyConKey,
158 stateAndPtrPrimDataConKey,
159 stateAndPtrPrimTyConKey,
160 stateAndStablePtrPrimDataConKey,
161 stateAndStablePtrPrimTyConKey,
162 stateAndSynchVarPrimDataConKey,
163 stateAndSynchVarPrimTyConKey,
164 stateAndWordPrimDataConKey,
165 stateAndWordPrimTyConKey,
170 synchVarPrimTyConKey,
174 unpackCStringAppendIdKey,
175 unpackCStringFoldrIdKey,
188 -- to make interface self-sufficient
193 import Ubiq{-uitous-}
199 %************************************************************************
201 \subsection[Unique-type]{@Unique@ type and operations}
203 %************************************************************************
205 The @Chars@ are ``tag letters'' that identify the @UniqueSupply@.
206 Fast comparison is everything on @Uniques@:
209 u2i :: Unique -> FAST_INT
211 data Unique = MkUnique Int#
215 Now come the functions which construct uniques from their pieces, and vice versa.
216 The stuff about unique *supplies* is handled further down this module.
219 mkUnique :: Char -> Int -> Unique -- Builds a unique from pieces
220 unpkUnique :: Unique -> (Char, Int) -- The reverse
222 mkUnifiableTyVarUnique :: Int -> Unique -- Injects a subst-array index into the Unique type
223 unpkUnifiableTyVarUnique :: Unique -> Int -- The reverse process
225 mkUniqueGrimily :: Int# -> Unique -- A trap-door for UniqSupply
230 mkUniqueGrimily x = MkUnique x
232 mkUnifiableTyVarUnique i = mkUnique '_'{-MAGIC CHAR-} i
234 unpkUnifiableTyVarUnique uniq
235 = case (unpkUnique uniq) of { (tag, i) ->
236 ASSERT(tag == '_'{-MAGIC CHAR-})
239 -- pop the Char in the top 8 bits of the Unique(Supply)
241 -- No 64-bit bugs here, as long as we have at least 32 bits. --JSM
247 mkUnique (MkChar c#) (MkInt i#)
248 = MkUnique (w2i (((i2w (ord# c#)) `shiftL#` (i2w_s 24#)) `or#` (i2w i#)))
250 unpkUnique (MkUnique u)
252 tag = MkChar (chr# (w2i ((i2w u) `shiftr` (i2w_s 24#))))
253 i = MkInt (w2i ((i2w u) `and#` (i2w 16777215#){-``0x00ffffff''-}))
257 shiftr x y = shiftRA# x y
260 %************************************************************************
262 \subsection[Unique-instances]{Instance declarations for @Unique@}
264 %************************************************************************
266 And the whole point (besides uniqueness) is fast equality. We don't
267 use `deriving' because we want {\em precise} control of ordering
268 (equality on @Uniques@ is v common).
271 eqUnique (MkUnique u1) (MkUnique u2) = u1 ==# u2
272 ltUnique (MkUnique u1) (MkUnique u2) = u1 <# u2
273 leUnique (MkUnique u1) (MkUnique u2) = u1 <=# u2
275 cmpUnique (MkUnique u1) (MkUnique u2)
276 = if u1 ==# u2 then EQ_ else if u1 <# u2 then LT_ else GT_
278 instance Eq Unique where
279 a == b = eqUnique a b
280 a /= b = not (eqUnique a b)
282 instance Ord Unique where
284 a <= b = leUnique a b
285 a > b = not (leUnique a b)
286 a >= b = not (ltUnique a b)
287 _tagCmp a b = case cmpUnique a b of { LT_ -> _LT; EQ_ -> _EQ; GT__ -> _GT }
289 instance Ord3 Unique where
293 class Uniquable a where
294 uniqueOf :: a -> Unique
296 instance Uniquable Unique where
300 We do sometimes make strings with @Uniques@ in them:
302 pprUnique, pprUnique10 :: Unique -> Pretty
305 = case unpkUnique uniq of
306 (tag, u) -> ppBeside (ppChar tag) (iToBase62 u)
308 pprUnique10 uniq -- in base-10, dudes
309 = case unpkUnique uniq of
310 (tag, u) -> ppBeside (ppChar tag) (ppInt u)
312 showUnique :: Unique -> FAST_STRING
313 showUnique uniq = _PK_ (ppShow 80 (pprUnique uniq))
315 instance Outputable Unique where
316 ppr sty u = pprUnique u
318 instance Text Unique where
319 showsPrec p uniq rest = _UNPK_ (showUnique uniq)
320 readsPrec p = panic "no readsPrec for Unique"
323 %************************************************************************
325 \subsection[Utils-base62]{Base-62 numbers}
327 %************************************************************************
329 A character-stingy way to read/write numbers (notably Uniques).
330 The ``62-its'' are \tr{[0-9a-zA-Z]}. We don't handle negative Ints.
331 Code stolen from Lennart.
333 iToBase62 :: Int -> Pretty
338 bytes = case chars62 of { _ByteArray bounds_who_needs_'em bytes -> bytes }
341 case (indexCharArray# bytes n#) of { c ->
344 case (quotRem n 62) of { (q, I# r#) ->
345 case (indexCharArray# bytes r#) of { c ->
346 ppBeside (iToBase62 q) (ppChar (C# c)) }}
348 -- keep this at top level! (bug on 94/10/24 WDP)
349 chars62 :: _ByteArray Int
352 newCharArray (0, 61) `thenStrictlyST` \ ch_array ->
353 fill_in ch_array 0 62 "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
355 unsafeFreezeByteArray ch_array
358 fill_in ch_array i lim str
360 = returnStrictlyST ()
362 = writeCharArray ch_array i (str !! i) `seqStrictlyST`
363 fill_in ch_array (i+1) lim str
366 %************************************************************************
368 \subsection[Uniques-prelude]{@Uniques@ for wired-in Prelude things}
370 %************************************************************************
372 Allocation of unique supply characters:
373 a-z: lower case chars for unique supplies (see Main.lhs)
374 B: builtin (see UniqSupply.lhs)
375 C-E: pseudo uniques (see UniqSupply.lhs)
376 _: unifiable tyvars (above)
377 1-8: prelude things below
380 mkAlphaTyVarUnique i = mkUnique '1' i
382 mkPreludeClassUnique i = mkUnique '2' i
383 mkPreludeTyConUnique i = mkUnique '3' i
384 mkTupleTyConUnique a = mkUnique '4' a
386 mkPreludeDataConUnique i = mkUnique '5' i -- must be alphabetic
387 mkTupleDataConUnique a = mkUnique '6' a -- ditto (*may* be used in C labels)
389 mkPrimOpIdUnique op = mkUnique '7' op
390 mkPreludeMiscIdUnique i = mkUnique '8' i
393 %************************************************************************
395 \subsubsection[Uniques-prelude-Classes]{@Uniques@ for wired-in @Classes@}
397 %************************************************************************
400 eqClassKey = mkPreludeClassUnique 1
401 ordClassKey = mkPreludeClassUnique 2
402 numClassKey = mkPreludeClassUnique 3
403 integralClassKey = mkPreludeClassUnique 4
404 fractionalClassKey = mkPreludeClassUnique 5
405 floatingClassKey = mkPreludeClassUnique 6
406 realClassKey = mkPreludeClassUnique 7
407 realFracClassKey = mkPreludeClassUnique 8
408 realFloatClassKey = mkPreludeClassUnique 9
409 ixClassKey = mkPreludeClassUnique 10
410 enumClassKey = mkPreludeClassUnique 11
411 showClassKey = mkPreludeClassUnique 12
412 readClassKey = mkPreludeClassUnique 13
413 monadClassKey = mkPreludeClassUnique 14
414 monadZeroClassKey = mkPreludeClassUnique 15
415 binaryClassKey = mkPreludeClassUnique 16
416 cCallableClassKey = mkPreludeClassUnique 17
417 cReturnableClassKey = mkPreludeClassUnique 18
420 %************************************************************************
422 \subsubsection[Uniques-prelude-TyCons]{@Uniques@ for wired-in @TyCons@}
424 %************************************************************************
427 addrPrimTyConKey = mkPreludeTyConUnique 1
428 addrTyConKey = mkPreludeTyConUnique 2
429 arrayPrimTyConKey = mkPreludeTyConUnique 3
430 boolTyConKey = mkPreludeTyConUnique 4
431 byteArrayPrimTyConKey = mkPreludeTyConUnique 5
432 charPrimTyConKey = mkPreludeTyConUnique 7
433 charTyConKey = mkPreludeTyConUnique 8
434 doublePrimTyConKey = mkPreludeTyConUnique 9
435 doubleTyConKey = mkPreludeTyConUnique 10
436 floatPrimTyConKey = mkPreludeTyConUnique 11
437 floatTyConKey = mkPreludeTyConUnique 12
438 funTyConKey = mkPreludeTyConUnique 13
439 iOTyConKey = mkPreludeTyConUnique 14
440 intPrimTyConKey = mkPreludeTyConUnique 15
441 intTyConKey = mkPreludeTyConUnique 16
442 integerTyConKey = mkPreludeTyConUnique 17
443 liftTyConKey = mkPreludeTyConUnique 18
444 listTyConKey = mkPreludeTyConUnique 19
445 mallocPtrPrimTyConKey = mkPreludeTyConUnique 20
446 mallocPtrTyConKey = mkPreludeTyConUnique 21
447 mutableArrayPrimTyConKey = mkPreludeTyConUnique 22
448 mutableByteArrayPrimTyConKey = mkPreludeTyConUnique 23
449 orderingTyConKey = mkPreludeTyConUnique 24
450 synchVarPrimTyConKey = mkPreludeTyConUnique 25
451 ratioTyConKey = mkPreludeTyConUnique 26
452 rationalTyConKey = mkPreludeTyConUnique 27
453 realWorldTyConKey = mkPreludeTyConUnique 28
454 return2GMPsTyConKey = mkPreludeTyConUnique 29
455 returnIntAndGMPTyConKey = mkPreludeTyConUnique 30
456 stablePtrPrimTyConKey = mkPreludeTyConUnique 31
457 stablePtrTyConKey = mkPreludeTyConUnique 32
458 stateAndAddrPrimTyConKey = mkPreludeTyConUnique 33
459 stateAndArrayPrimTyConKey = mkPreludeTyConUnique 34
460 stateAndByteArrayPrimTyConKey = mkPreludeTyConUnique 35
461 stateAndCharPrimTyConKey = mkPreludeTyConUnique 36
462 stateAndDoublePrimTyConKey = mkPreludeTyConUnique 37
463 stateAndFloatPrimTyConKey = mkPreludeTyConUnique 38
464 stateAndIntPrimTyConKey = mkPreludeTyConUnique 39
465 stateAndMallocPtrPrimTyConKey = mkPreludeTyConUnique 40
466 stateAndMutableArrayPrimTyConKey = mkPreludeTyConUnique 41
467 stateAndMutableByteArrayPrimTyConKey = mkPreludeTyConUnique 42
468 stateAndSynchVarPrimTyConKey = mkPreludeTyConUnique 43
469 stateAndPtrPrimTyConKey = mkPreludeTyConUnique 44
470 stateAndStablePtrPrimTyConKey = mkPreludeTyConUnique 45
471 stateAndWordPrimTyConKey = mkPreludeTyConUnique 46
472 statePrimTyConKey = mkPreludeTyConUnique 47
473 stateTyConKey = mkPreludeTyConUnique 48
474 stringTyConKey = mkPreludeTyConUnique 49
475 stTyConKey = mkPreludeTyConUnique 50
476 primIoTyConKey = mkPreludeTyConUnique 51
477 voidPrimTyConKey = mkPreludeTyConUnique 52
478 wordPrimTyConKey = mkPreludeTyConUnique 53
479 wordTyConKey = mkPreludeTyConUnique 54
482 %************************************************************************
484 \subsubsection[Uniques-prelude-DataCons]{@Uniques@ for wired-in @DataCons@}
486 %************************************************************************
489 addrDataConKey = mkPreludeDataConUnique 1
490 buildDataConKey = mkPreludeDataConUnique 2
491 charDataConKey = mkPreludeDataConUnique 4
492 consDataConKey = mkPreludeDataConUnique 5
493 doubleDataConKey = mkPreludeDataConUnique 6
494 eqDataConKey = mkPreludeDataConUnique 7
495 falseDataConKey = mkPreludeDataConUnique 8
496 floatDataConKey = mkPreludeDataConUnique 9
497 gtDataConKey = mkPreludeDataConUnique 10
498 intDataConKey = mkPreludeDataConUnique 11
499 integerDataConKey = mkPreludeDataConUnique 12
500 liftDataConKey = mkPreludeDataConUnique 13
501 ltDataConKey = mkPreludeDataConUnique 14
502 mallocPtrDataConKey = mkPreludeDataConUnique 15
503 nilDataConKey = mkPreludeDataConUnique 18
504 ratioDataConKey = mkPreludeDataConUnique 21
505 return2GMPsDataConKey = mkPreludeDataConUnique 22
506 returnIntAndGMPDataConKey = mkPreludeDataConUnique 23
507 stablePtrDataConKey = mkPreludeDataConUnique 24
508 stateAndAddrPrimDataConKey = mkPreludeDataConUnique 25
509 stateAndArrayPrimDataConKey = mkPreludeDataConUnique 26
510 stateAndByteArrayPrimDataConKey = mkPreludeDataConUnique 27
511 stateAndCharPrimDataConKey = mkPreludeDataConUnique 28
512 stateAndDoublePrimDataConKey = mkPreludeDataConUnique 29
513 stateAndFloatPrimDataConKey = mkPreludeDataConUnique 30
514 stateAndIntPrimDataConKey = mkPreludeDataConUnique 31
515 stateAndMallocPtrPrimDataConKey = mkPreludeDataConUnique 32
516 stateAndMutableArrayPrimDataConKey = mkPreludeDataConUnique 33
517 stateAndMutableByteArrayPrimDataConKey = mkPreludeDataConUnique 34
518 stateAndSynchVarPrimDataConKey = mkPreludeDataConUnique 35
519 stateAndPtrPrimDataConKey = mkPreludeDataConUnique 36
520 stateAndStablePtrPrimDataConKey = mkPreludeDataConUnique 37
521 stateAndWordPrimDataConKey = mkPreludeDataConUnique 38
522 stateDataConKey = mkPreludeDataConUnique 39
523 trueDataConKey = mkPreludeDataConUnique 40
524 wordDataConKey = mkPreludeDataConUnique 41
527 %************************************************************************
529 \subsubsection[Uniques-prelude-Ids]{@Uniques@ for wired-in @Ids@ (except @DataCons@)}
531 %************************************************************************
534 absentErrorIdKey = mkPreludeMiscIdUnique 1
535 appendIdKey = mkPreludeMiscIdUnique 2
536 augmentIdKey = mkPreludeMiscIdUnique 3
537 buildIdKey = mkPreludeMiscIdUnique 4
538 errorIdKey = mkPreludeMiscIdUnique 5
539 foldlIdKey = mkPreludeMiscIdUnique 6
540 foldrIdKey = mkPreludeMiscIdUnique 7
541 forkIdKey = mkPreludeMiscIdUnique 8
542 int2IntegerIdKey = mkPreludeMiscIdUnique 9
543 integerMinusOneIdKey = mkPreludeMiscIdUnique 10
544 integerPlusOneIdKey = mkPreludeMiscIdUnique 11
545 integerPlusTwoIdKey = mkPreludeMiscIdUnique 12
546 integerZeroIdKey = mkPreludeMiscIdUnique 13
547 packCStringIdKey = mkPreludeMiscIdUnique 14
548 parErrorIdKey = mkPreludeMiscIdUnique 15
549 parIdKey = mkPreludeMiscIdUnique 16
550 patErrorIdKey = mkPreludeMiscIdUnique 17
551 realWorldPrimIdKey = mkPreludeMiscIdUnique 18
552 runSTIdKey = mkPreludeMiscIdUnique 19
553 seqIdKey = mkPreludeMiscIdUnique 20
554 traceIdKey = mkPreludeMiscIdUnique 21
555 unpackCString2IdKey = mkPreludeMiscIdUnique 22
556 unpackCStringAppendIdKey= mkPreludeMiscIdUnique 23
557 unpackCStringFoldrIdKey = mkPreludeMiscIdUnique 24
558 unpackCStringIdKey = mkPreludeMiscIdUnique 25
559 voidPrimIdKey = mkPreludeMiscIdUnique 26
560 mainIdKey = mkPreludeMiscIdUnique 27
561 mainPrimIOIdKey = mkPreludeMiscIdUnique 28
564 parLocalIdKey = mkPreludeMiscIdUnique 29
565 parGlobalIdKey = mkPreludeMiscIdUnique 30
566 noFollowIdKey = mkPreludeMiscIdUnique 31
567 copyableIdKey = mkPreludeMiscIdUnique 32
571 Certain class operations from Prelude classes. They get
572 their own uniques so we can look them up easily when we want
573 to conjure them up during type checking.
575 fromIntClassOpKey = mkPreludeMiscIdUnique 33
576 fromIntegerClassOpKey = mkPreludeMiscIdUnique 34
577 fromRationalClassOpKey = mkPreludeMiscIdUnique 35
578 enumFromClassOpKey = mkPreludeMiscIdUnique 36
579 enumFromThenClassOpKey = mkPreludeMiscIdUnique 37
580 enumFromToClassOpKey = mkPreludeMiscIdUnique 38
581 enumFromThenToClassOpKey= mkPreludeMiscIdUnique 39
582 eqClassOpKey = mkPreludeMiscIdUnique 40
583 geClassOpKey = mkPreludeMiscIdUnique 41