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