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