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