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
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,
128 return2GMPsDataConKey,
130 returnIntAndGMPDataConKey,
131 returnIntAndGMPTyConKey,
137 stablePtrPrimTyConKey,
139 stateAndAddrPrimDataConKey,
140 stateAndAddrPrimTyConKey,
141 stateAndArrayPrimDataConKey,
142 stateAndArrayPrimTyConKey,
143 stateAndByteArrayPrimDataConKey,
144 stateAndByteArrayPrimTyConKey,
145 stateAndCharPrimDataConKey,
146 stateAndCharPrimTyConKey,
147 stateAndDoublePrimDataConKey,
148 stateAndDoublePrimTyConKey,
149 stateAndFloatPrimDataConKey,
150 stateAndFloatPrimTyConKey,
151 stateAndIntPrimDataConKey,
152 stateAndIntPrimTyConKey,
153 stateAndMallocPtrPrimDataConKey,
154 stateAndMallocPtrPrimTyConKey,
155 stateAndMutableArrayPrimDataConKey,
156 stateAndMutableArrayPrimTyConKey,
157 stateAndMutableByteArrayPrimDataConKey,
158 stateAndMutableByteArrayPrimTyConKey,
159 stateAndPtrPrimDataConKey,
160 stateAndPtrPrimTyConKey,
161 stateAndStablePtrPrimDataConKey,
162 stateAndStablePtrPrimTyConKey,
163 stateAndSynchVarPrimDataConKey,
164 stateAndSynchVarPrimTyConKey,
165 stateAndWordPrimDataConKey,
166 stateAndWordPrimTyConKey,
171 synchVarPrimTyConKey,
175 unpackCStringAppendIdKey,
176 unpackCStringFoldrIdKey,
189 -- to make interface self-sufficient
194 import Ubiq{-uitous-}
200 %************************************************************************
202 \subsection[Unique-type]{@Unique@ type and operations}
204 %************************************************************************
206 The @Chars@ are ``tag letters'' that identify the @UniqueSupply@.
207 Fast comparison is everything on @Uniques@:
210 u2i :: Unique -> FAST_INT
212 data Unique = MkUnique Int#
216 Now come the functions which construct uniques from their pieces, and vice versa.
217 The stuff about unique *supplies* is handled further down this module.
220 mkUnique :: Char -> Int -> Unique -- Builds a unique from pieces
221 unpkUnique :: Unique -> (Char, Int) -- The reverse
223 mkUnifiableTyVarUnique :: Int -> Unique -- Injects a subst-array index into the Unique type
224 unpkUnifiableTyVarUnique :: Unique -> Int -- The reverse process
226 mkUniqueGrimily :: Int# -> Unique -- A trap-door for UniqSupply
231 mkUniqueGrimily x = MkUnique x
233 mkUnifiableTyVarUnique i = mkUnique '_'{-MAGIC CHAR-} i
235 unpkUnifiableTyVarUnique uniq
236 = case (unpkUnique uniq) of { (tag, i) ->
237 ASSERT(tag == '_'{-MAGIC CHAR-})
240 -- pop the Char in the top 8 bits of the Unique(Supply)
242 -- No 64-bit bugs here, as long as we have at least 32 bits. --JSM
248 mkUnique (MkChar c#) (MkInt i#)
249 = MkUnique (w2i (((i2w (ord# c#)) `shiftL#` (i2w_s 24#)) `or#` (i2w i#)))
251 unpkUnique (MkUnique u)
253 tag = MkChar (chr# (w2i ((i2w u) `shiftr` (i2w_s 24#))))
254 i = MkInt (w2i ((i2w u) `and#` (i2w 16777215#){-``0x00ffffff''-}))
258 shiftr x y = shiftRA# x y
261 %************************************************************************
263 \subsection[Unique-instances]{Instance declarations for @Unique@}
265 %************************************************************************
267 And the whole point (besides uniqueness) is fast equality. We don't
268 use `deriving' because we want {\em precise} control of ordering
269 (equality on @Uniques@ is v common).
272 eqUnique (MkUnique u1) (MkUnique u2) = u1 ==# u2
273 ltUnique (MkUnique u1) (MkUnique u2) = u1 <# u2
274 leUnique (MkUnique u1) (MkUnique u2) = u1 <=# u2
276 cmpUnique (MkUnique u1) (MkUnique u2)
277 = if u1 ==# u2 then EQ_ else if u1 <# u2 then LT_ else GT_
279 instance Eq Unique where
280 a == b = eqUnique a b
281 a /= b = not (eqUnique a b)
283 instance Ord Unique where
285 a <= b = leUnique a b
286 a > b = not (leUnique a b)
287 a >= b = not (ltUnique a b)
288 _tagCmp a b = case cmpUnique a b of { LT_ -> _LT; EQ_ -> _EQ; GT__ -> _GT }
290 instance Ord3 Unique where
295 We do sometimes make strings with @Uniques@ in them:
297 pprUnique, pprUnique10 :: Unique -> Pretty
300 = case unpkUnique uniq of
301 (tag, u) -> ppBeside (ppChar tag) (iToBase62 u)
303 pprUnique10 uniq -- in base-10, dudes
304 = case unpkUnique uniq of
305 (tag, u) -> ppBeside (ppChar tag) (ppInt u)
307 showUnique :: Unique -> FAST_STRING
308 showUnique uniq = _PK_ (ppShow 80 (pprUnique uniq))
310 instance Outputable Unique where
311 ppr sty u = pprUnique u
313 instance Text Unique where
314 showsPrec p uniq rest = _UNPK_ (showUnique uniq)
315 readsPrec p = panic "no readsPrec for Unique"
317 instance NamedThing Unique where
321 %************************************************************************
323 \subsection[Utils-base62]{Base-62 numbers}
325 %************************************************************************
327 A character-stingy way to read/write numbers (notably Uniques).
328 The ``62-its'' are \tr{[0-9a-zA-Z]}. We don't handle negative Ints.
329 Code stolen from Lennart.
331 iToBase62 :: Int -> Pretty
336 bytes = case chars62 of { _ByteArray bounds_who_needs_'em bytes -> bytes }
339 case (indexCharArray# bytes n#) of { c ->
342 case (quotRem n 62) of { (q, I# r#) ->
343 case (indexCharArray# bytes r#) of { c ->
344 ppBeside (iToBase62 q) (ppChar (C# c)) }}
346 -- keep this at top level! (bug on 94/10/24 WDP)
347 chars62 :: _ByteArray Int
350 newCharArray (0, 61) `thenStrictlyST` \ ch_array ->
351 fill_in ch_array 0 62 "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
353 unsafeFreezeByteArray ch_array
356 fill_in ch_array i lim str
358 = returnStrictlyST ()
360 = writeCharArray ch_array i (str !! i) `seqStrictlyST`
361 fill_in ch_array (i+1) lim str
364 %************************************************************************
366 \subsection[Uniques-prelude]{@Uniques@ for wired-in Prelude things}
368 %************************************************************************
370 Allocation of unique supply characters:
371 a-z: lower case chars for unique supplies (see Main.lhs)
372 B: builtin (see UniqSupply.lhs)
373 C-E: pseudo uniques (see UniqSupply.lhs)
374 _: unifiable tyvars (above)
375 1-8: prelude things below
378 mkAlphaTyVarUnique i = mkUnique '1' i
380 mkPreludeClassUnique i = mkUnique '2' i
381 mkPreludeTyConUnique i = mkUnique '3' i
382 mkTupleTyConUnique a = mkUnique '4' a
384 mkPreludeDataConUnique i = mkUnique '5' i -- must be alphabetic
385 mkTupleDataConUnique a = mkUnique '6' a -- ditto (*may* be used in C labels)
387 mkPrimOpIdUnique op = mkUnique '7' op
388 mkPreludeMiscIdUnique i = mkUnique '8' i
391 %************************************************************************
393 \subsubsection[Uniques-prelude-Classes]{@Uniques@ for wired-in @Classes@}
395 %************************************************************************
398 eqClassKey = mkPreludeClassUnique 1
399 ordClassKey = mkPreludeClassUnique 2
400 numClassKey = mkPreludeClassUnique 3
401 integralClassKey = mkPreludeClassUnique 4
402 fractionalClassKey = mkPreludeClassUnique 5
403 floatingClassKey = mkPreludeClassUnique 6
404 realClassKey = mkPreludeClassUnique 7
405 realFracClassKey = mkPreludeClassUnique 8
406 realFloatClassKey = mkPreludeClassUnique 9
407 ixClassKey = mkPreludeClassUnique 10
408 enumClassKey = mkPreludeClassUnique 11
409 showClassKey = mkPreludeClassUnique 12
410 readClassKey = mkPreludeClassUnique 13
411 monadClassKey = mkPreludeClassUnique 14
412 monadZeroClassKey = mkPreludeClassUnique 15
413 binaryClassKey = mkPreludeClassUnique 16
414 cCallableClassKey = mkPreludeClassUnique 17
415 cReturnableClassKey = mkPreludeClassUnique 18
418 %************************************************************************
420 \subsubsection[Uniques-prelude-TyCons]{@Uniques@ for wired-in @TyCons@}
422 %************************************************************************
425 addrPrimTyConKey = mkPreludeTyConUnique 1
426 addrTyConKey = mkPreludeTyConUnique 2
427 arrayPrimTyConKey = mkPreludeTyConUnique 3
428 boolTyConKey = mkPreludeTyConUnique 4
429 byteArrayPrimTyConKey = mkPreludeTyConUnique 5
430 charPrimTyConKey = mkPreludeTyConUnique 7
431 charTyConKey = mkPreludeTyConUnique 8
432 doublePrimTyConKey = mkPreludeTyConUnique 9
433 doubleTyConKey = mkPreludeTyConUnique 10
434 floatPrimTyConKey = mkPreludeTyConUnique 11
435 floatTyConKey = mkPreludeTyConUnique 12
436 funTyConKey = mkPreludeTyConUnique 13
437 iOTyConKey = mkPreludeTyConUnique 14
438 intPrimTyConKey = mkPreludeTyConUnique 15
439 intTyConKey = mkPreludeTyConUnique 16
440 integerTyConKey = mkPreludeTyConUnique 17
441 liftTyConKey = mkPreludeTyConUnique 18
442 listTyConKey = mkPreludeTyConUnique 19
443 mallocPtrPrimTyConKey = mkPreludeTyConUnique 20
444 mallocPtrTyConKey = mkPreludeTyConUnique 21
445 mutableArrayPrimTyConKey = mkPreludeTyConUnique 22
446 mutableByteArrayPrimTyConKey = mkPreludeTyConUnique 23
447 orderingTyConKey = mkPreludeTyConUnique 24
448 synchVarPrimTyConKey = mkPreludeTyConUnique 25
449 ratioTyConKey = mkPreludeTyConUnique 26
450 rationalTyConKey = mkPreludeTyConUnique 27
451 realWorldTyConKey = mkPreludeTyConUnique 28
452 return2GMPsTyConKey = mkPreludeTyConUnique 29
453 returnIntAndGMPTyConKey = mkPreludeTyConUnique 30
454 stablePtrPrimTyConKey = mkPreludeTyConUnique 31
455 stablePtrTyConKey = mkPreludeTyConUnique 32
456 stateAndAddrPrimTyConKey = mkPreludeTyConUnique 33
457 stateAndArrayPrimTyConKey = mkPreludeTyConUnique 34
458 stateAndByteArrayPrimTyConKey = mkPreludeTyConUnique 35
459 stateAndCharPrimTyConKey = mkPreludeTyConUnique 36
460 stateAndDoublePrimTyConKey = mkPreludeTyConUnique 37
461 stateAndFloatPrimTyConKey = mkPreludeTyConUnique 38
462 stateAndIntPrimTyConKey = mkPreludeTyConUnique 39
463 stateAndMallocPtrPrimTyConKey = mkPreludeTyConUnique 40
464 stateAndMutableArrayPrimTyConKey = mkPreludeTyConUnique 41
465 stateAndMutableByteArrayPrimTyConKey = mkPreludeTyConUnique 42
466 stateAndSynchVarPrimTyConKey = mkPreludeTyConUnique 43
467 stateAndPtrPrimTyConKey = mkPreludeTyConUnique 44
468 stateAndStablePtrPrimTyConKey = mkPreludeTyConUnique 45
469 stateAndWordPrimTyConKey = mkPreludeTyConUnique 46
470 statePrimTyConKey = mkPreludeTyConUnique 47
471 stateTyConKey = mkPreludeTyConUnique 48
472 stringTyConKey = mkPreludeTyConUnique 49
473 stTyConKey = mkPreludeTyConUnique 50
474 primIoTyConKey = mkPreludeTyConUnique 51
475 voidPrimTyConKey = mkPreludeTyConUnique 52
476 wordPrimTyConKey = mkPreludeTyConUnique 53
477 wordTyConKey = mkPreludeTyConUnique 54
480 %************************************************************************
482 \subsubsection[Uniques-prelude-DataCons]{@Uniques@ for wired-in @DataCons@}
484 %************************************************************************
487 addrDataConKey = mkPreludeDataConUnique 1
488 buildDataConKey = mkPreludeDataConUnique 2
489 charDataConKey = mkPreludeDataConUnique 4
490 consDataConKey = mkPreludeDataConUnique 5
491 doubleDataConKey = mkPreludeDataConUnique 6
492 eqDataConKey = mkPreludeDataConUnique 7
493 falseDataConKey = mkPreludeDataConUnique 8
494 floatDataConKey = mkPreludeDataConUnique 9
495 gtDataConKey = mkPreludeDataConUnique 10
496 intDataConKey = mkPreludeDataConUnique 11
497 integerDataConKey = mkPreludeDataConUnique 12
498 liftDataConKey = mkPreludeDataConUnique 13
499 ltDataConKey = mkPreludeDataConUnique 14
500 mallocPtrDataConKey = mkPreludeDataConUnique 15
501 nilDataConKey = mkPreludeDataConUnique 18
502 ratioDataConKey = mkPreludeDataConUnique 21
503 return2GMPsDataConKey = mkPreludeDataConUnique 22
504 returnIntAndGMPDataConKey = mkPreludeDataConUnique 23
505 stablePtrDataConKey = mkPreludeDataConUnique 24
506 stateAndAddrPrimDataConKey = mkPreludeDataConUnique 25
507 stateAndArrayPrimDataConKey = mkPreludeDataConUnique 26
508 stateAndByteArrayPrimDataConKey = mkPreludeDataConUnique 27
509 stateAndCharPrimDataConKey = mkPreludeDataConUnique 28
510 stateAndDoublePrimDataConKey = mkPreludeDataConUnique 29
511 stateAndFloatPrimDataConKey = mkPreludeDataConUnique 30
512 stateAndIntPrimDataConKey = mkPreludeDataConUnique 31
513 stateAndMallocPtrPrimDataConKey = mkPreludeDataConUnique 32
514 stateAndMutableArrayPrimDataConKey = mkPreludeDataConUnique 33
515 stateAndMutableByteArrayPrimDataConKey = mkPreludeDataConUnique 34
516 stateAndSynchVarPrimDataConKey = mkPreludeDataConUnique 35
517 stateAndPtrPrimDataConKey = mkPreludeDataConUnique 36
518 stateAndStablePtrPrimDataConKey = mkPreludeDataConUnique 37
519 stateAndWordPrimDataConKey = mkPreludeDataConUnique 38
520 stateDataConKey = mkPreludeDataConUnique 39
521 trueDataConKey = mkPreludeDataConUnique 40
522 wordDataConKey = mkPreludeDataConUnique 41
525 %************************************************************************
527 \subsubsection[Uniques-prelude-Ids]{@Uniques@ for wired-in @Ids@ (except @DataCons@)}
529 %************************************************************************
532 absentErrorIdKey = mkPreludeMiscIdUnique 1
533 appendIdKey = mkPreludeMiscIdUnique 2
534 augmentIdKey = mkPreludeMiscIdUnique 3
535 buildIdKey = mkPreludeMiscIdUnique 4
536 errorIdKey = mkPreludeMiscIdUnique 5
537 foldlIdKey = mkPreludeMiscIdUnique 6
538 foldrIdKey = mkPreludeMiscIdUnique 7
539 forkIdKey = mkPreludeMiscIdUnique 8
540 int2IntegerIdKey = mkPreludeMiscIdUnique 9
541 integerMinusOneIdKey = mkPreludeMiscIdUnique 10
542 integerPlusOneIdKey = mkPreludeMiscIdUnique 11
543 integerPlusTwoIdKey = mkPreludeMiscIdUnique 12
544 integerZeroIdKey = mkPreludeMiscIdUnique 13
545 packCStringIdKey = mkPreludeMiscIdUnique 14
546 parErrorIdKey = mkPreludeMiscIdUnique 15
547 parIdKey = mkPreludeMiscIdUnique 16
548 patErrorIdKey = mkPreludeMiscIdUnique 17
549 realWorldPrimIdKey = mkPreludeMiscIdUnique 18
550 runSTIdKey = mkPreludeMiscIdUnique 19
551 seqIdKey = mkPreludeMiscIdUnique 20
552 traceIdKey = mkPreludeMiscIdUnique 21
553 unpackCString2IdKey = mkPreludeMiscIdUnique 22
554 unpackCStringAppendIdKey= mkPreludeMiscIdUnique 23
555 unpackCStringFoldrIdKey = mkPreludeMiscIdUnique 24
556 unpackCStringIdKey = mkPreludeMiscIdUnique 25
557 voidPrimIdKey = mkPreludeMiscIdUnique 26
558 mainIdKey = mkPreludeMiscIdUnique 27
559 mainPrimIOIdKey = mkPreludeMiscIdUnique 28
562 parLocalIdKey = mkPreludeMiscIdUnique 29
563 parGlobalIdKey = mkPreludeMiscIdUnique 30
564 noFollowIdKey = mkPreludeMiscIdUnique 31
565 copyableIdKey = mkPreludeMiscIdUnique 32
569 Certain class operations from Prelude classes. They get
570 their own uniques so we can look them up easily when we want
571 to conjure them up during type checking.
573 fromIntClassOpKey = mkPreludeMiscIdUnique 33
574 fromIntegerClassOpKey = mkPreludeMiscIdUnique 34
575 fromRationalClassOpKey = mkPreludeMiscIdUnique 35
576 enumFromClassOpKey = mkPreludeMiscIdUnique 36
577 enumFromThenClassOpKey = mkPreludeMiscIdUnique 37
578 enumFromToClassOpKey = mkPreludeMiscIdUnique 38
579 enumFromThenToClassOpKey= mkPreludeMiscIdUnique 39
580 eqClassOpKey = mkPreludeMiscIdUnique 40
581 geClassOpKey = mkPreludeMiscIdUnique 41
582 negateClassOpKey = mkPreludeMiscIdUnique 42