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,
87 fromIntegerClassOpKey,
88 fromRationalClassOpKey,
111 mallocPtrPrimTyConKey,
115 mutableArrayPrimTyConKey,
116 mutableByteArrayPrimTyConKey,
127 irrefutPatErrorIdKey,
128 nonExhaustiveGuardsErrorIdKey,
129 noDefaultMethodErrorIdKey,
130 nonExplicitMethodErrorIdKey,
141 return2GMPsDataConKey,
143 returnIntAndGMPDataConKey,
144 returnIntAndGMPTyConKey,
150 stablePtrPrimTyConKey,
152 stateAndAddrPrimDataConKey,
153 stateAndAddrPrimTyConKey,
154 stateAndArrayPrimDataConKey,
155 stateAndArrayPrimTyConKey,
156 stateAndByteArrayPrimDataConKey,
157 stateAndByteArrayPrimTyConKey,
158 stateAndCharPrimDataConKey,
159 stateAndCharPrimTyConKey,
160 stateAndDoublePrimDataConKey,
161 stateAndDoublePrimTyConKey,
162 stateAndFloatPrimDataConKey,
163 stateAndFloatPrimTyConKey,
164 stateAndIntPrimDataConKey,
165 stateAndIntPrimTyConKey,
166 stateAndMallocPtrPrimDataConKey,
167 stateAndMallocPtrPrimTyConKey,
168 stateAndMutableArrayPrimDataConKey,
169 stateAndMutableArrayPrimTyConKey,
170 stateAndMutableByteArrayPrimDataConKey,
171 stateAndMutableByteArrayPrimTyConKey,
172 stateAndPtrPrimDataConKey,
173 stateAndPtrPrimTyConKey,
174 stateAndStablePtrPrimDataConKey,
175 stateAndStablePtrPrimTyConKey,
176 stateAndSynchVarPrimDataConKey,
177 stateAndSynchVarPrimTyConKey,
178 stateAndWordPrimDataConKey,
179 stateAndWordPrimTyConKey,
184 synchVarPrimTyConKey,
188 unpackCStringAppendIdKey,
189 unpackCStringFoldrIdKey,
202 -- to make interface self-sufficient
207 import Ubiq{-uitous-}
213 %************************************************************************
215 \subsection[Unique-type]{@Unique@ type and operations}
217 %************************************************************************
219 The @Chars@ are ``tag letters'' that identify the @UniqueSupply@.
220 Fast comparison is everything on @Uniques@:
223 u2i :: Unique -> FAST_INT
225 data Unique = MkUnique Int#
229 Now come the functions which construct uniques from their pieces, and vice versa.
230 The stuff about unique *supplies* is handled further down this module.
233 mkUnique :: Char -> Int -> Unique -- Builds a unique from pieces
234 unpkUnique :: Unique -> (Char, Int) -- The reverse
236 mkUniqueGrimily :: Int# -> Unique -- A trap-door for UniqSupply
238 incrUnique :: Unique -> Unique
243 mkUniqueGrimily x = MkUnique x
245 incrUnique (MkUnique i) = MkUnique (i +# 1#)
247 -- pop the Char in the top 8 bits of the Unique(Supply)
249 -- No 64-bit bugs here, as long as we have at least 32 bits. --JSM
255 mkUnique (MkChar c#) (MkInt i#)
256 = MkUnique (w2i (((i2w (ord# c#)) `shiftL#` (i2w_s 24#)) `or#` (i2w i#)))
258 unpkUnique (MkUnique u)
260 tag = MkChar (chr# (w2i ((i2w u) `shiftr` (i2w_s 24#))))
261 i = MkInt (w2i ((i2w u) `and#` (i2w 16777215#){-``0x00ffffff''-}))
265 shiftr x y = shiftRA# x y
268 %************************************************************************
270 \subsection[Unique-instances]{Instance declarations for @Unique@}
272 %************************************************************************
274 And the whole point (besides uniqueness) is fast equality. We don't
275 use `deriving' because we want {\em precise} control of ordering
276 (equality on @Uniques@ is v common).
279 eqUnique (MkUnique u1) (MkUnique u2) = u1 ==# u2
280 ltUnique (MkUnique u1) (MkUnique u2) = u1 <# u2
281 leUnique (MkUnique u1) (MkUnique u2) = u1 <=# u2
283 cmpUnique (MkUnique u1) (MkUnique u2)
284 = if u1 ==# u2 then EQ_ else if u1 <# u2 then LT_ else GT_
286 instance Eq Unique where
287 a == b = eqUnique a b
288 a /= b = not (eqUnique a b)
290 instance Ord Unique where
292 a <= b = leUnique a b
293 a > b = not (leUnique a b)
294 a >= b = not (ltUnique a b)
295 _tagCmp a b = case cmpUnique a b of { LT_ -> _LT; EQ_ -> _EQ; GT__ -> _GT }
297 instance Ord3 Unique where
301 instance Uniquable Unique where
305 We do sometimes make strings with @Uniques@ in them:
307 pprUnique, pprUnique10 :: Unique -> Pretty
310 = case unpkUnique uniq of
311 (tag, u) -> ppBeside (ppChar tag) (iToBase62 u)
313 pprUnique10 uniq -- in base-10, dudes
314 = case unpkUnique uniq of
315 (tag, u) -> ppBeside (ppChar tag) (ppInt u)
317 showUnique :: Unique -> FAST_STRING
318 showUnique uniq = _PK_ (ppShow 80 (pprUnique uniq))
320 instance Outputable Unique where
321 ppr sty u = pprUnique u
323 instance Text Unique where
324 showsPrec p uniq rest = _UNPK_ (showUnique uniq)
325 readsPrec p = panic "no readsPrec for Unique"
328 %************************************************************************
330 \subsection[Utils-base62]{Base-62 numbers}
332 %************************************************************************
334 A character-stingy way to read/write numbers (notably Uniques).
335 The ``62-its'' are \tr{[0-9a-zA-Z]}. We don't handle negative Ints.
336 Code stolen from Lennart.
338 iToBase62 :: Int -> Pretty
343 bytes = case chars62 of { _ByteArray bounds_who_needs_'em bytes -> bytes }
346 case (indexCharArray# bytes n#) of { c ->
349 case (quotRem n 62) of { (q, I# r#) ->
350 case (indexCharArray# bytes r#) of { c ->
351 ppBeside (iToBase62 q) (ppChar (C# c)) }}
353 -- keep this at top level! (bug on 94/10/24 WDP)
354 chars62 :: _ByteArray Int
357 newCharArray (0, 61) `thenStrictlyST` \ ch_array ->
358 fill_in ch_array 0 62 "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
360 unsafeFreezeByteArray ch_array
363 fill_in ch_array i lim str
365 = returnStrictlyST ()
367 = writeCharArray ch_array i (str !! i) `seqStrictlyST`
368 fill_in ch_array (i+1) lim str
371 %************************************************************************
373 \subsection[Uniques-prelude]{@Uniques@ for wired-in Prelude things}
375 %************************************************************************
377 Allocation of unique supply characters:
378 v,t,u : for renumbering value-, type- and usage- vars.
379 other a-z: lower case chars for unique supplies (see Main.lhs)
381 C-E: pseudo uniques (used in native-code generator)
382 _: unifiable tyvars (above)
383 1-8: prelude things below
386 mkAlphaTyVarUnique i = mkUnique '1' i
388 mkPreludeClassUnique i = mkUnique '2' i
389 mkPreludeTyConUnique i = mkUnique '3' i
390 mkTupleTyConUnique a = mkUnique '4' a
392 mkPreludeDataConUnique i = mkUnique '5' i -- must be alphabetic
393 mkTupleDataConUnique a = mkUnique '6' a -- ditto (*may* be used in C labels)
395 mkPrimOpIdUnique op = mkUnique '7' op
396 mkPreludeMiscIdUnique i = mkUnique '8' i
398 initRenumberingUniques = (mkUnique 'v' 1, mkUnique 't' 1, mkUnique 'u' 1)
400 mkPseudoUnique1, mkPseudoUnique2, mkPseudoUnique3,
401 mkBuiltinUnique :: Int -> Unique
403 mkBuiltinUnique i = mkUnique 'B' i
404 mkPseudoUnique1 i = mkUnique 'C' i -- used for uniqueOf on Regs
405 mkPseudoUnique2 i = mkUnique 'D' i -- ditto
406 mkPseudoUnique3 i = mkUnique 'E' i -- ditto
408 getBuiltinUniques :: Int -> [Unique]
409 getBuiltinUniques n = map (mkUnique 'B') [1 .. n]
412 %************************************************************************
414 \subsubsection[Uniques-prelude-Classes]{@Uniques@ for wired-in @Classes@}
416 %************************************************************************
419 eqClassKey = mkPreludeClassUnique 1
420 ordClassKey = mkPreludeClassUnique 2
421 numClassKey = mkPreludeClassUnique 3
422 integralClassKey = mkPreludeClassUnique 4
423 fractionalClassKey = mkPreludeClassUnique 5
424 floatingClassKey = mkPreludeClassUnique 6
425 realClassKey = mkPreludeClassUnique 7
426 realFracClassKey = mkPreludeClassUnique 8
427 realFloatClassKey = mkPreludeClassUnique 9
428 ixClassKey = mkPreludeClassUnique 10
429 enumClassKey = mkPreludeClassUnique 11
430 showClassKey = mkPreludeClassUnique 12
431 readClassKey = mkPreludeClassUnique 13
432 monadClassKey = mkPreludeClassUnique 14
433 monadZeroClassKey = mkPreludeClassUnique 15
434 binaryClassKey = mkPreludeClassUnique 16
435 cCallableClassKey = mkPreludeClassUnique 17
436 cReturnableClassKey = mkPreludeClassUnique 18
437 evalClassKey = mkPreludeClassUnique 19
438 boundedClassKey = mkPreludeClassUnique 20
441 %************************************************************************
443 \subsubsection[Uniques-prelude-TyCons]{@Uniques@ for wired-in @TyCons@}
445 %************************************************************************
448 addrPrimTyConKey = mkPreludeTyConUnique 1
449 addrTyConKey = mkPreludeTyConUnique 2
450 arrayPrimTyConKey = mkPreludeTyConUnique 3
451 boolTyConKey = mkPreludeTyConUnique 4
452 byteArrayPrimTyConKey = mkPreludeTyConUnique 5
453 charPrimTyConKey = mkPreludeTyConUnique 7
454 charTyConKey = mkPreludeTyConUnique 8
455 doublePrimTyConKey = mkPreludeTyConUnique 9
456 doubleTyConKey = mkPreludeTyConUnique 10
457 floatPrimTyConKey = mkPreludeTyConUnique 11
458 floatTyConKey = mkPreludeTyConUnique 12
459 funTyConKey = mkPreludeTyConUnique 13
460 iOTyConKey = mkPreludeTyConUnique 14
461 intPrimTyConKey = mkPreludeTyConUnique 15
462 intTyConKey = mkPreludeTyConUnique 16
463 integerTyConKey = mkPreludeTyConUnique 17
464 liftTyConKey = mkPreludeTyConUnique 18
465 listTyConKey = mkPreludeTyConUnique 19
466 mallocPtrPrimTyConKey = mkPreludeTyConUnique 20
467 mallocPtrTyConKey = mkPreludeTyConUnique 21
468 mutableArrayPrimTyConKey = mkPreludeTyConUnique 22
469 mutableByteArrayPrimTyConKey = mkPreludeTyConUnique 23
470 orderingTyConKey = mkPreludeTyConUnique 24
471 synchVarPrimTyConKey = mkPreludeTyConUnique 25
472 ratioTyConKey = mkPreludeTyConUnique 26
473 rationalTyConKey = mkPreludeTyConUnique 27
474 realWorldTyConKey = mkPreludeTyConUnique 28
475 return2GMPsTyConKey = mkPreludeTyConUnique 29
476 returnIntAndGMPTyConKey = mkPreludeTyConUnique 30
477 stablePtrPrimTyConKey = mkPreludeTyConUnique 31
478 stablePtrTyConKey = mkPreludeTyConUnique 32
479 stateAndAddrPrimTyConKey = mkPreludeTyConUnique 33
480 stateAndArrayPrimTyConKey = mkPreludeTyConUnique 34
481 stateAndByteArrayPrimTyConKey = mkPreludeTyConUnique 35
482 stateAndCharPrimTyConKey = mkPreludeTyConUnique 36
483 stateAndDoublePrimTyConKey = mkPreludeTyConUnique 37
484 stateAndFloatPrimTyConKey = mkPreludeTyConUnique 38
485 stateAndIntPrimTyConKey = mkPreludeTyConUnique 39
486 stateAndMallocPtrPrimTyConKey = mkPreludeTyConUnique 40
487 stateAndMutableArrayPrimTyConKey = mkPreludeTyConUnique 41
488 stateAndMutableByteArrayPrimTyConKey = mkPreludeTyConUnique 42
489 stateAndSynchVarPrimTyConKey = mkPreludeTyConUnique 43
490 stateAndPtrPrimTyConKey = mkPreludeTyConUnique 44
491 stateAndStablePtrPrimTyConKey = mkPreludeTyConUnique 45
492 stateAndWordPrimTyConKey = mkPreludeTyConUnique 46
493 statePrimTyConKey = mkPreludeTyConUnique 47
494 stateTyConKey = mkPreludeTyConUnique 48
495 stringTyConKey = mkPreludeTyConUnique 49
496 stTyConKey = mkPreludeTyConUnique 50
497 primIoTyConKey = mkPreludeTyConUnique 51
498 voidPrimTyConKey = mkPreludeTyConUnique 52
499 wordPrimTyConKey = mkPreludeTyConUnique 53
500 wordTyConKey = mkPreludeTyConUnique 54
503 %************************************************************************
505 \subsubsection[Uniques-prelude-DataCons]{@Uniques@ for wired-in @DataCons@}
507 %************************************************************************
510 addrDataConKey = mkPreludeDataConUnique 1
511 buildDataConKey = mkPreludeDataConUnique 2
512 charDataConKey = mkPreludeDataConUnique 4
513 consDataConKey = mkPreludeDataConUnique 5
514 doubleDataConKey = mkPreludeDataConUnique 6
515 eqDataConKey = mkPreludeDataConUnique 7
516 falseDataConKey = mkPreludeDataConUnique 8
517 floatDataConKey = mkPreludeDataConUnique 9
518 gtDataConKey = mkPreludeDataConUnique 10
519 intDataConKey = mkPreludeDataConUnique 11
520 integerDataConKey = mkPreludeDataConUnique 12
521 liftDataConKey = mkPreludeDataConUnique 13
522 ltDataConKey = mkPreludeDataConUnique 14
523 mallocPtrDataConKey = mkPreludeDataConUnique 15
524 nilDataConKey = mkPreludeDataConUnique 18
525 ratioDataConKey = mkPreludeDataConUnique 21
526 return2GMPsDataConKey = mkPreludeDataConUnique 22
527 returnIntAndGMPDataConKey = mkPreludeDataConUnique 23
528 stablePtrDataConKey = mkPreludeDataConUnique 24
529 stateAndAddrPrimDataConKey = mkPreludeDataConUnique 25
530 stateAndArrayPrimDataConKey = mkPreludeDataConUnique 26
531 stateAndByteArrayPrimDataConKey = mkPreludeDataConUnique 27
532 stateAndCharPrimDataConKey = mkPreludeDataConUnique 28
533 stateAndDoublePrimDataConKey = mkPreludeDataConUnique 29
534 stateAndFloatPrimDataConKey = mkPreludeDataConUnique 30
535 stateAndIntPrimDataConKey = mkPreludeDataConUnique 31
536 stateAndMallocPtrPrimDataConKey = mkPreludeDataConUnique 32
537 stateAndMutableArrayPrimDataConKey = mkPreludeDataConUnique 33
538 stateAndMutableByteArrayPrimDataConKey = mkPreludeDataConUnique 34
539 stateAndSynchVarPrimDataConKey = mkPreludeDataConUnique 35
540 stateAndPtrPrimDataConKey = mkPreludeDataConUnique 36
541 stateAndStablePtrPrimDataConKey = mkPreludeDataConUnique 37
542 stateAndWordPrimDataConKey = mkPreludeDataConUnique 38
543 stateDataConKey = mkPreludeDataConUnique 39
544 trueDataConKey = mkPreludeDataConUnique 40
545 wordDataConKey = mkPreludeDataConUnique 41
548 %************************************************************************
550 \subsubsection[Uniques-prelude-Ids]{@Uniques@ for wired-in @Ids@ (except @DataCons@)}
552 %************************************************************************
555 absentErrorIdKey = mkPreludeMiscIdUnique 1
556 appendIdKey = mkPreludeMiscIdUnique 2
557 augmentIdKey = mkPreludeMiscIdUnique 3
558 buildIdKey = mkPreludeMiscIdUnique 4
559 errorIdKey = mkPreludeMiscIdUnique 5
560 foldlIdKey = mkPreludeMiscIdUnique 6
561 foldrIdKey = mkPreludeMiscIdUnique 7
562 forkIdKey = mkPreludeMiscIdUnique 8
563 int2IntegerIdKey = mkPreludeMiscIdUnique 9
564 integerMinusOneIdKey = mkPreludeMiscIdUnique 10
565 integerPlusOneIdKey = mkPreludeMiscIdUnique 11
566 integerPlusTwoIdKey = mkPreludeMiscIdUnique 12
567 integerZeroIdKey = mkPreludeMiscIdUnique 13
568 packCStringIdKey = mkPreludeMiscIdUnique 14
569 parErrorIdKey = mkPreludeMiscIdUnique 15
570 parIdKey = mkPreludeMiscIdUnique 16
571 patErrorIdKey = mkPreludeMiscIdUnique 17
572 realWorldPrimIdKey = mkPreludeMiscIdUnique 18
573 runSTIdKey = mkPreludeMiscIdUnique 19
574 seqIdKey = mkPreludeMiscIdUnique 20
575 traceIdKey = mkPreludeMiscIdUnique 21
576 unpackCString2IdKey = mkPreludeMiscIdUnique 22
577 unpackCStringAppendIdKey = mkPreludeMiscIdUnique 23
578 unpackCStringFoldrIdKey = mkPreludeMiscIdUnique 24
579 unpackCStringIdKey = mkPreludeMiscIdUnique 25
580 voidPrimIdKey = mkPreludeMiscIdUnique 26
581 mainIdKey = mkPreludeMiscIdUnique 27
582 mainPrimIOIdKey = mkPreludeMiscIdUnique 28
583 recConErrorIdKey = mkPreludeMiscIdUnique 29
584 recUpdErrorIdKey = mkPreludeMiscIdUnique 30
585 irrefutPatErrorIdKey = mkPreludeMiscIdUnique 31
586 nonExhaustiveGuardsErrorIdKey = mkPreludeMiscIdUnique 32
587 noDefaultMethodErrorIdKey = mkPreludeMiscIdUnique 33
588 nonExplicitMethodErrorIdKey = mkPreludeMiscIdUnique 34
591 parLocalIdKey = mkPreludeMiscIdUnique 35
592 parGlobalIdKey = mkPreludeMiscIdUnique 36
593 noFollowIdKey = mkPreludeMiscIdUnique 37
594 copyableIdKey = mkPreludeMiscIdUnique 38
598 Certain class operations from Prelude classes. They get
599 their own uniques so we can look them up easily when we want
600 to conjure them up during type checking.
602 fromIntClassOpKey = mkPreludeMiscIdUnique 37
603 fromIntegerClassOpKey = mkPreludeMiscIdUnique 38
604 fromRationalClassOpKey = mkPreludeMiscIdUnique 39
605 enumFromClassOpKey = mkPreludeMiscIdUnique 40
606 enumFromThenClassOpKey = mkPreludeMiscIdUnique 41
607 enumFromToClassOpKey = mkPreludeMiscIdUnique 42
608 enumFromThenToClassOpKey= mkPreludeMiscIdUnique 43
609 eqClassOpKey = mkPreludeMiscIdUnique 44
610 geClassOpKey = mkPreludeMiscIdUnique 45