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 incrUnique, -- Used for renumbering
33 initRenumberingUniques,
35 -- now all the built-in Uniques (and functions to make them)
36 -- [the Oh-So-Wonderful Haskell module system wins again...]
42 getBuiltinUniques, mkBuiltinUnique,
43 mkPseudoUnique1, mkPseudoUnique2, mkPseudoUnique3,
45 absentErrorIdKey, -- alphabetical...
57 byteArrayPrimTyConKey,
70 enumFromThenClassOpKey,
71 enumFromThenToClassOpKey,
86 foreignObjPrimTyConKey,
92 fromIntegerClassOpKey,
93 fromRationalClassOpKey,
103 integerMinusOneIdKey,
109 irrefutPatErrorIdKey,
116 mainKey, mainPrimIoKey,
121 mutableArrayPrimTyConKey,
122 mutableByteArrayPrimTyConKey,
124 noDefaultMethodErrorIdKey,
125 nonExhaustiveGuardsErrorIdKey,
126 nonExplicitMethodErrorIdKey,
149 return2GMPsDataConKey,
151 returnIntAndGMPDataConKey,
152 returnIntAndGMPTyConKey,
163 stablePtrPrimTyConKey,
165 stateAndAddrPrimDataConKey,
166 stateAndAddrPrimTyConKey,
167 stateAndArrayPrimDataConKey,
168 stateAndArrayPrimTyConKey,
169 stateAndByteArrayPrimDataConKey,
170 stateAndByteArrayPrimTyConKey,
171 stateAndCharPrimDataConKey,
172 stateAndCharPrimTyConKey,
173 stateAndDoublePrimDataConKey,
174 stateAndDoublePrimTyConKey,
175 stateAndFloatPrimDataConKey,
176 stateAndFloatPrimTyConKey,
177 stateAndForeignObjPrimDataConKey,
178 stateAndForeignObjPrimTyConKey,
179 stateAndIntPrimDataConKey,
180 stateAndIntPrimTyConKey,
181 stateAndMutableArrayPrimDataConKey,
182 stateAndMutableArrayPrimTyConKey,
183 stateAndMutableByteArrayPrimDataConKey,
184 stateAndMutableByteArrayPrimTyConKey,
185 stateAndPtrPrimDataConKey,
186 stateAndPtrPrimTyConKey,
187 stateAndStablePtrPrimDataConKey,
188 stateAndStablePtrPrimTyConKey,
189 stateAndSynchVarPrimDataConKey,
190 stateAndSynchVarPrimTyConKey,
191 stateAndWordPrimDataConKey,
192 stateAndWordPrimTyConKey,
196 synchVarPrimTyConKey,
201 unpackCStringAppendIdKey,
202 unpackCStringFoldrIdKey,
231 %************************************************************************
233 \subsection[Unique-type]{@Unique@ type and operations}
235 %************************************************************************
237 The @Chars@ are ``tag letters'' that identify the @UniqueSupply@.
238 Fast comparison is everything on @Uniques@:
241 u2i :: Unique -> FAST_INT
243 data Unique = MkUnique Int#
247 Now come the functions which construct uniques from their pieces, and vice versa.
248 The stuff about unique *supplies* is handled further down this module.
251 mkUnique :: Char -> Int -> Unique -- Builds a unique from pieces
252 unpkUnique :: Unique -> (Char, Int) -- The reverse
254 mkUniqueGrimily :: Int# -> Unique -- A trap-door for UniqSupply
256 incrUnique :: Unique -> Unique
261 mkUniqueGrimily x = MkUnique x
263 incrUnique (MkUnique i) = MkUnique (i +# 1#)
265 -- pop the Char in the top 8 bits of the Unique(Supply)
267 -- No 64-bit bugs here, as long as we have at least 32 bits. --JSM
273 mkUnique (C# c) (I# i)
274 = MkUnique (w2i (((i2w (ord# c)) `shiftL#` (i2w_s 24#)) `or#` (i2w i)))
276 unpkUnique (MkUnique u)
278 tag = C# (chr# (w2i ((i2w u) `shiftr` (i2w_s 24#))))
279 i = I# (w2i ((i2w u) `and#` (i2w 16777215#){-``0x00ffffff''-}))
283 shiftr x y = shiftRA# x y
286 %************************************************************************
288 \subsection[Unique-instances]{Instance declarations for @Unique@}
290 %************************************************************************
292 And the whole point (besides uniqueness) is fast equality. We don't
293 use `deriving' because we want {\em precise} control of ordering
294 (equality on @Uniques@ is v common).
297 eqUnique (MkUnique u1) (MkUnique u2) = u1 ==# u2
298 ltUnique (MkUnique u1) (MkUnique u2) = u1 <# u2
299 leUnique (MkUnique u1) (MkUnique u2) = u1 <=# u2
301 cmpUnique (MkUnique u1) (MkUnique u2)
302 = if u1 ==# u2 then EQ_ else if u1 <# u2 then LT_ else GT_
304 instance Eq Unique where
305 a == b = eqUnique a b
306 a /= b = not (eqUnique a b)
308 instance Ord Unique where
310 a <= b = leUnique a b
311 a > b = not (leUnique a b)
312 a >= b = not (ltUnique a b)
313 _tagCmp a b = case cmpUnique a b of { LT_ -> _LT; EQ_ -> _EQ; GT__ -> _GT }
315 instance Ord3 Unique where
319 instance Uniquable Unique where
323 We do sometimes make strings with @Uniques@ in them:
325 pprUnique, pprUnique10 :: Unique -> Pretty
328 = case unpkUnique uniq of
329 (tag, u) -> finish_ppr tag u (iToBase62 u)
331 pprUnique10 uniq -- in base-10, dudes
332 = case unpkUnique uniq of
333 (tag, u) -> finish_ppr tag u (ppInt u)
335 finish_ppr tag u pp_u
336 = if tag /= 't' -- this is just to make v common tyvars, t1, t2, ...
337 -- come out as a, b, ... (shorter, easier to read)
347 pp_all = ppBeside (ppChar tag) pp_u
349 showUnique :: Unique -> FAST_STRING
350 showUnique uniq = _PK_ (ppShow 80 (pprUnique uniq))
352 instance Outputable Unique where
353 ppr sty u = pprUnique u
355 instance Text Unique where
356 showsPrec p uniq rest = _UNPK_ (showUnique uniq)
359 %************************************************************************
361 \subsection[Utils-base62]{Base-62 numbers}
363 %************************************************************************
365 A character-stingy way to read/write numbers (notably Uniques).
366 The ``62-its'' are \tr{[0-9a-zA-Z]}. We don't handle negative Ints.
367 Code stolen from Lennart.
369 #if __GLASGOW_HASKELL__ >= 200
370 # define BYTE_ARRAY GHCbase.ByteArray
371 # define RUN_ST GHCbase.runST
372 # define AND_THEN >>=
373 # define AND_THEN_ >>
374 # define RETURN return
376 # define BYTE_ARRAY _ByteArray
377 # define RUN_ST _runST
378 # define AND_THEN `thenStrictlyST`
379 # define AND_THEN_ `seqStrictlyST`
380 # define RETURN returnStrictlyST
383 iToBase62 :: Int -> Pretty
388 bytes = case chars62 of { BYTE_ARRAY bounds_who_needs_'em bytes -> bytes }
391 case (indexCharArray# bytes n#) of { c ->
394 case (quotRem n 62) of { (q, I# r#) ->
395 case (indexCharArray# bytes r#) of { c ->
396 ppBeside (iToBase62 q) (ppChar (C# c)) }}
398 -- keep this at top level! (bug on 94/10/24 WDP)
399 chars62 :: BYTE_ARRAY Int
402 newCharArray (0, 61) AND_THEN \ ch_array ->
403 fill_in ch_array 0 62 "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
405 unsafeFreezeByteArray ch_array
408 fill_in ch_array i lim str
412 = writeCharArray ch_array i (str !! i) AND_THEN_
413 fill_in ch_array (i+1) lim str
416 %************************************************************************
418 \subsection[Uniques-prelude]{@Uniques@ for wired-in Prelude things}
420 %************************************************************************
422 Allocation of unique supply characters:
423 v,t,u : for renumbering value-, type- and usage- vars.
424 other a-z: lower case chars for unique supplies (see Main.lhs)
426 C-E: pseudo uniques (used in native-code generator)
427 _: unifiable tyvars (above)
428 1-8: prelude things below
431 mkAlphaTyVarUnique i = mkUnique '1' i
433 mkPreludeClassUnique i = mkUnique '2' i
434 mkPreludeTyConUnique i = mkUnique '3' i
435 mkTupleTyConUnique a = mkUnique '4' a
437 mkPreludeDataConUnique i = mkUnique '5' i -- must be alphabetic
438 mkTupleDataConUnique a = mkUnique '6' a -- ditto (*may* be used in C labels)
440 mkPrimOpIdUnique op = mkUnique '7' op
441 mkPreludeMiscIdUnique i = mkUnique '8' i
443 initRenumberingUniques = (mkUnique 'v' 1, mkUnique 't' 1, mkUnique 'u' 1)
445 mkPseudoUnique1, mkPseudoUnique2, mkPseudoUnique3,
446 mkBuiltinUnique :: Int -> Unique
448 mkBuiltinUnique i = mkUnique 'B' i
449 mkPseudoUnique1 i = mkUnique 'C' i -- used for uniqueOf on Regs
450 mkPseudoUnique2 i = mkUnique 'D' i -- ditto
451 mkPseudoUnique3 i = mkUnique 'E' i -- ditto
453 getBuiltinUniques :: Int -> [Unique]
454 getBuiltinUniques n = map (mkUnique 'B') [1 .. n]
457 %************************************************************************
459 \subsubsection[Uniques-prelude-Classes]{@Uniques@ for wired-in @Classes@}
461 %************************************************************************
464 boundedClassKey = mkPreludeClassUnique 1
465 enumClassKey = mkPreludeClassUnique 2
466 eqClassKey = mkPreludeClassUnique 3
467 evalClassKey = mkPreludeClassUnique 4
468 floatingClassKey = mkPreludeClassUnique 5
469 fractionalClassKey = mkPreludeClassUnique 6
470 integralClassKey = mkPreludeClassUnique 7
471 monadClassKey = mkPreludeClassUnique 8
472 monadZeroClassKey = mkPreludeClassUnique 9
473 monadPlusClassKey = mkPreludeClassUnique 10
474 functorClassKey = mkPreludeClassUnique 11
475 numClassKey = mkPreludeClassUnique 12
476 ordClassKey = mkPreludeClassUnique 13
477 readClassKey = mkPreludeClassUnique 14
478 realClassKey = mkPreludeClassUnique 15
479 realFloatClassKey = mkPreludeClassUnique 16
480 realFracClassKey = mkPreludeClassUnique 17
481 showClassKey = mkPreludeClassUnique 18
483 cCallableClassKey = mkPreludeClassUnique 19
484 cReturnableClassKey = mkPreludeClassUnique 20
486 ixClassKey = mkPreludeClassUnique 21
489 %************************************************************************
491 \subsubsection[Uniques-prelude-TyCons]{@Uniques@ for wired-in @TyCons@}
493 %************************************************************************
496 addrPrimTyConKey = mkPreludeTyConUnique 1
497 addrTyConKey = mkPreludeTyConUnique 2
498 arrayPrimTyConKey = mkPreludeTyConUnique 3
499 boolTyConKey = mkPreludeTyConUnique 4
500 byteArrayPrimTyConKey = mkPreludeTyConUnique 5
501 charPrimTyConKey = mkPreludeTyConUnique 7
502 charTyConKey = mkPreludeTyConUnique 8
503 doublePrimTyConKey = mkPreludeTyConUnique 9
504 doubleTyConKey = mkPreludeTyConUnique 10
505 floatPrimTyConKey = mkPreludeTyConUnique 11
506 floatTyConKey = mkPreludeTyConUnique 12
507 funTyConKey = mkPreludeTyConUnique 13
508 iOTyConKey = mkPreludeTyConUnique 14
509 intPrimTyConKey = mkPreludeTyConUnique 15
510 intTyConKey = mkPreludeTyConUnique 16
511 integerTyConKey = mkPreludeTyConUnique 17
512 liftTyConKey = mkPreludeTyConUnique 18
513 listTyConKey = mkPreludeTyConUnique 19
514 foreignObjPrimTyConKey = mkPreludeTyConUnique 20
515 foreignObjTyConKey = mkPreludeTyConUnique 21
516 mutableArrayPrimTyConKey = mkPreludeTyConUnique 22
517 mutableByteArrayPrimTyConKey = mkPreludeTyConUnique 23
518 orderingTyConKey = mkPreludeTyConUnique 24
519 synchVarPrimTyConKey = mkPreludeTyConUnique 25
520 ratioTyConKey = mkPreludeTyConUnique 26
521 rationalTyConKey = mkPreludeTyConUnique 27
522 realWorldTyConKey = mkPreludeTyConUnique 28
523 return2GMPsTyConKey = mkPreludeTyConUnique 29
524 returnIntAndGMPTyConKey = mkPreludeTyConUnique 30
525 stablePtrPrimTyConKey = mkPreludeTyConUnique 31
526 stablePtrTyConKey = mkPreludeTyConUnique 32
527 stateAndAddrPrimTyConKey = mkPreludeTyConUnique 33
528 stateAndArrayPrimTyConKey = mkPreludeTyConUnique 34
529 stateAndByteArrayPrimTyConKey = mkPreludeTyConUnique 35
530 stateAndCharPrimTyConKey = mkPreludeTyConUnique 36
531 stateAndDoublePrimTyConKey = mkPreludeTyConUnique 37
532 stateAndFloatPrimTyConKey = mkPreludeTyConUnique 38
533 stateAndIntPrimTyConKey = mkPreludeTyConUnique 39
534 stateAndForeignObjPrimTyConKey = mkPreludeTyConUnique 40
535 stateAndMutableArrayPrimTyConKey = mkPreludeTyConUnique 41
536 stateAndMutableByteArrayPrimTyConKey = mkPreludeTyConUnique 42
537 stateAndSynchVarPrimTyConKey = mkPreludeTyConUnique 43
538 stateAndPtrPrimTyConKey = mkPreludeTyConUnique 44
539 stateAndStablePtrPrimTyConKey = mkPreludeTyConUnique 45
540 stateAndWordPrimTyConKey = mkPreludeTyConUnique 46
541 statePrimTyConKey = mkPreludeTyConUnique 47
542 stateTyConKey = mkPreludeTyConUnique 48
544 stTyConKey = mkPreludeTyConUnique 50
545 primIoTyConKey = mkPreludeTyConUnique 51
547 wordPrimTyConKey = mkPreludeTyConUnique 53
548 wordTyConKey = mkPreludeTyConUnique 54
549 voidTyConKey = mkPreludeTyConUnique 55
552 %************************************************************************
554 \subsubsection[Uniques-prelude-DataCons]{@Uniques@ for wired-in @DataCons@}
556 %************************************************************************
559 addrDataConKey = mkPreludeDataConUnique 1
560 buildDataConKey = mkPreludeDataConUnique 2
561 charDataConKey = mkPreludeDataConUnique 4
562 consDataConKey = mkPreludeDataConUnique 5
563 doubleDataConKey = mkPreludeDataConUnique 6
564 eqDataConKey = mkPreludeDataConUnique 7
565 falseDataConKey = mkPreludeDataConUnique 8
566 floatDataConKey = mkPreludeDataConUnique 9
567 gtDataConKey = mkPreludeDataConUnique 10
568 intDataConKey = mkPreludeDataConUnique 11
569 integerDataConKey = mkPreludeDataConUnique 12
570 liftDataConKey = mkPreludeDataConUnique 13
571 ltDataConKey = mkPreludeDataConUnique 14
572 foreignObjDataConKey = mkPreludeDataConUnique 15
573 nilDataConKey = mkPreludeDataConUnique 18
574 ratioDataConKey = mkPreludeDataConUnique 21
575 return2GMPsDataConKey = mkPreludeDataConUnique 22
576 returnIntAndGMPDataConKey = mkPreludeDataConUnique 23
577 stablePtrDataConKey = mkPreludeDataConUnique 24
578 stateAndAddrPrimDataConKey = mkPreludeDataConUnique 25
579 stateAndArrayPrimDataConKey = mkPreludeDataConUnique 26
580 stateAndByteArrayPrimDataConKey = mkPreludeDataConUnique 27
581 stateAndCharPrimDataConKey = mkPreludeDataConUnique 28
582 stateAndDoublePrimDataConKey = mkPreludeDataConUnique 29
583 stateAndFloatPrimDataConKey = mkPreludeDataConUnique 30
584 stateAndIntPrimDataConKey = mkPreludeDataConUnique 31
585 stateAndForeignObjPrimDataConKey = mkPreludeDataConUnique 32
586 stateAndMutableArrayPrimDataConKey = mkPreludeDataConUnique 33
587 stateAndMutableByteArrayPrimDataConKey = mkPreludeDataConUnique 34
588 stateAndSynchVarPrimDataConKey = mkPreludeDataConUnique 35
589 stateAndPtrPrimDataConKey = mkPreludeDataConUnique 36
590 stateAndStablePtrPrimDataConKey = mkPreludeDataConUnique 37
591 stateAndWordPrimDataConKey = mkPreludeDataConUnique 38
592 stateDataConKey = mkPreludeDataConUnique 39
593 trueDataConKey = mkPreludeDataConUnique 40
594 wordDataConKey = mkPreludeDataConUnique 41
595 stDataConKey = mkPreludeDataConUnique 42
598 %************************************************************************
600 \subsubsection[Uniques-prelude-Ids]{@Uniques@ for wired-in @Ids@ (except @DataCons@)}
602 %************************************************************************
605 absentErrorIdKey = mkPreludeMiscIdUnique 1
606 andandIdKey = mkPreludeMiscIdUnique 2
607 appendIdKey = mkPreludeMiscIdUnique 3
608 augmentIdKey = mkPreludeMiscIdUnique 4
609 buildIdKey = mkPreludeMiscIdUnique 5
610 composeIdKey = mkPreludeMiscIdUnique 6
611 errorIdKey = mkPreludeMiscIdUnique 7
612 foldlIdKey = mkPreludeMiscIdUnique 8
613 foldrIdKey = mkPreludeMiscIdUnique 9
614 forkIdKey = mkPreludeMiscIdUnique 10
615 int2IntegerIdKey = mkPreludeMiscIdUnique 11
616 integerMinusOneIdKey = mkPreludeMiscIdUnique 12
617 integerPlusOneIdKey = mkPreludeMiscIdUnique 13
618 integerPlusTwoIdKey = mkPreludeMiscIdUnique 14
619 integerZeroIdKey = mkPreludeMiscIdUnique 15
620 irrefutPatErrorIdKey = mkPreludeMiscIdUnique 16
621 lexIdKey = mkPreludeMiscIdUnique 17
622 noDefaultMethodErrorIdKey = mkPreludeMiscIdUnique 20
623 nonExhaustiveGuardsErrorIdKey = mkPreludeMiscIdUnique 21
624 nonExplicitMethodErrorIdKey = mkPreludeMiscIdUnique 22
625 notIdKey = mkPreludeMiscIdUnique 23
626 packCStringIdKey = mkPreludeMiscIdUnique 24
627 parErrorIdKey = mkPreludeMiscIdUnique 25
628 parIdKey = mkPreludeMiscIdUnique 26
629 patErrorIdKey = mkPreludeMiscIdUnique 27
630 readParenIdKey = mkPreludeMiscIdUnique 28
631 realWorldPrimIdKey = mkPreludeMiscIdUnique 29
632 recConErrorIdKey = mkPreludeMiscIdUnique 30
633 recUpdErrorIdKey = mkPreludeMiscIdUnique 31
634 runSTIdKey = mkPreludeMiscIdUnique 32
635 seqIdKey = mkPreludeMiscIdUnique 33
636 showParenIdKey = mkPreludeMiscIdUnique 34
637 showSpaceIdKey = mkPreludeMiscIdUnique 35
638 showStringIdKey = mkPreludeMiscIdUnique 36
639 traceIdKey = mkPreludeMiscIdUnique 37
640 unpackCString2IdKey = mkPreludeMiscIdUnique 38
641 unpackCStringAppendIdKey = mkPreludeMiscIdUnique 39
642 unpackCStringFoldrIdKey = mkPreludeMiscIdUnique 40
643 unpackCStringIdKey = mkPreludeMiscIdUnique 41
644 voidIdKey = mkPreludeMiscIdUnique 42
645 ushowListIdKey = mkPreludeMiscIdUnique 43
646 ureadListIdKey = mkPreludeMiscIdUnique 44
648 copyableIdKey = mkPreludeMiscIdUnique 45
649 noFollowIdKey = mkPreludeMiscIdUnique 46
650 parAtAbsIdKey = mkPreludeMiscIdUnique 47
651 parAtForNowIdKey = mkPreludeMiscIdUnique 48
652 parAtIdKey = mkPreludeMiscIdUnique 49
653 parAtRelIdKey = mkPreludeMiscIdUnique 50
654 parGlobalIdKey = mkPreludeMiscIdUnique 51
655 parLocalIdKey = mkPreludeMiscIdUnique 52
658 Certain class operations from Prelude classes. They get
659 their own uniques so we can look them up easily when we want
660 to conjure them up during type checking.
662 fromIntClassOpKey = mkPreludeMiscIdUnique 53
663 fromIntegerClassOpKey = mkPreludeMiscIdUnique 54
664 minusClassOpKey = mkPreludeMiscIdUnique 69
665 fromRationalClassOpKey = mkPreludeMiscIdUnique 55
666 enumFromClassOpKey = mkPreludeMiscIdUnique 56
667 enumFromThenClassOpKey = mkPreludeMiscIdUnique 57
668 enumFromToClassOpKey = mkPreludeMiscIdUnique 58
669 enumFromThenToClassOpKey= mkPreludeMiscIdUnique 59
670 eqClassOpKey = mkPreludeMiscIdUnique 60
671 geClassOpKey = mkPreludeMiscIdUnique 61
672 zeroClassOpKey = mkPreludeMiscIdUnique 62
673 thenMClassOpKey = mkPreludeMiscIdUnique 63 -- (>>=)
674 unboundKey = mkPreludeMiscIdUnique 64 -- Just a place holder for unbound
675 -- variables produced by the renamer
676 fromEnumClassOpKey = mkPreludeMiscIdUnique 65
678 mainKey = mkPreludeMiscIdUnique 66
679 mainPrimIoKey = mkPreludeMiscIdUnique 67
680 returnMClassOpKey = mkPreludeMiscIdUnique 68
681 -- Used for minusClassOp 69
682 otherwiseIdKey = mkPreludeMiscIdUnique 70