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