{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998


@Uniques@ are used to distinguish entities in the compiler (@Ids@,
@Classes@, etc.) from each other.  Thus, @Uniques@ are the basic
comparison key in the compiler.

If there is any single operation that needs to be fast, it is @Unique@

comparison.  Unsurprisingly, there is quite a bit of huff-and-puff
directed to that end.

Some of the other hair in this code is to be able to use a
``splittable @UniqueSupply@'' if requested/possible (not standard
Haskell).
-}

{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}

module GHC.Types.Unique (
        -- * Main data types
        Unique, Uniquable(..),
        UniqueTag(..), uniqueTag, charToUniqueTag,
        uNIQUE_BITS,

        -- ** Constructors, destructors and operations on 'Unique's
        hasKey,

        showUnique,
        pprUniqueAlways,

        mkTag,
        mkUniqueGrimily,
        mkUniqueGrimilyWithTag,
        mkUniqueIntGrimily,
        getKey,
        mkUnique, unpkUnique,
        unpkUniqueGrimly,
        mkUniqueInt,
        eqUnique, ltUnique,
        incrUnique, stepUnique,

        newTagUnique, newTagUniqueGrimly,
        nonDetCmpUnique,
        isValidKnownKeyUnique,

        -- ** Local uniques
        -- | These are exposed exclusively for use by 'GHC.Types.Var.Env.uniqAway', which
        -- has rather peculiar needs. See Note [Local uniques].
        mkLocalUnique, minLocalUnique, maxLocalUnique,
    ) where

#include "Unique.h"

import GHC.Prelude

import GHC.Data.FastString
import GHC.Utils.Outputable
import GHC.Utils.Panic.Plain (panic)
import GHC.Utils.Word64 (intToWord64, word64ToInt)

-- just for implementing a fast [0,61) -> Char function
import GHC.Exts (indexCharOffAddr#, Char(..), Int(..))

import GHC.Word         ( Word64 )
import Data.Char        ( chr, ord, isPrint )

import Language.Haskell.Syntax.Module.Name

{-
************************************************************************
*                                                                      *
\subsection[Unique-type]{@Unique@ type and operations}
*                                                                      *
************************************************************************

Note [Uniques and tags]
~~~~~~~~~~~~~~~~~~~~~~~~
A `Unique` in GHC is a 64 bit value composed of two pieces:
* A "tag", of width `UNIQUE_TAG_BITS`, in the high order bits
* A number, of width `uNIQUE_BITS`, which fills up the remainder of the Word64

The tag is typically stored as an ASCII character.  It is typically used to make it easier
to distinguish uniques constructed by different parts of the compiler.
To ensure that we assign distinct tags for each purpose, we represent tags in the compiler
via the UniqueTag ADT.

The bidirectional mapping from the UniqueTag ADT to the corresponding character is witnessed
by the uniqueTag and charToUniqueTag functions.
See Note [Uniques for wired-in prelude things and known tags]

`mkUnique` constructs a `Unique` from its pieces
  mkUnique :: UniqueTag -> Word64 -> Unique

Note [Performance implications of UniqueTag]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The UniqueTag ADT is meant to be ephemeral and eliminated by the simplifier,
so for long term storage (i.e. in monadic environments or data structures) we
want to store the raw 'Char's. Working with the raw tags is done via the *Grimly
class of functions

For instance, if we are generating a unique for a concrete tag, we should use
functions like `mkUniqueInt` which take a `UniqueTag` which will be eliminated by inlining.

However, if the unique is unknown and comes from a stored location, we should prefer using
the 'Char' directly. This avoids multiple conversions using `uniqueTag` at runtime.

For instance, instead of `env_ut :: UniqueTag` and

newUnique
  = do { env <- getEnv
       ; let tag = env_ut env
       ; liftIO $! uniqFromTag tag }

Prefer `env_ut :: Char` and
       ; liftIO $! uniqFromTagGrimly tag }

-}

-- | Unique identifier.
--
-- The type of unique identifiers that are used in many places in GHC
-- for fast ordering and equality tests. You should generate these with
-- the functions from the 'UniqSupply' module
--
-- These are sometimes also referred to as \"keys\" in comments in GHC.
newtype Unique = MkUnique Word64

data UniqueTag
  = AlphaTyVarTag
  | BcoTag
  | BlockIdTag
  | BoxedTupleDataTag
  | BoxedTupleTyConTag
  | BoxingTyConTag
  | BuiltinTag
  | CmmTag
  | CodeGenTag
  | CostCentreTag
  | CTupleDataTag
  | CTupleSelTag
  | CTupleTag
  | DataNSTag
  | DsTag
  | FldNSTag
  | HscTag
  | IfaceTag
  | JsTag
  | LocalTag
  | PluginTag
  | PreludeClassTag
  | PreludeDataConTag
  | PreludeMiscIdTag
  | PreludeTyConTag
  | PrimOpTag
  | PseudoTag
  | RegClassTag
  | RegPairTag
  | RegSingleTag
  | RegSubTag
  | RnIfaceTag
  | SimplTag
  | SkolemTag
  | SrtTag
  | StgPTag
  | StgTag
  | SumTag
  | TcNSTag
  | TcTag
  | TsanTag
  | TvNSTag
  | UnboxedTupleDataTag
  | UnboxedTupleTyConTag
  | UniqueRenamerTag
  | VarNSTag
  | VirtualRegTag
  | NullTag
  deriving (UniqueTag -> UniqueTag -> Bool
(UniqueTag -> UniqueTag -> Bool)
-> (UniqueTag -> UniqueTag -> Bool) -> Eq UniqueTag
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: UniqueTag -> UniqueTag -> Bool
== :: UniqueTag -> UniqueTag -> Bool
$c/= :: UniqueTag -> UniqueTag -> Bool
/= :: UniqueTag -> UniqueTag -> Bool
Eq, Int -> UniqueTag -> ShowS
[UniqueTag] -> ShowS
UniqueTag -> String
(Int -> UniqueTag -> ShowS)
-> (UniqueTag -> String)
-> ([UniqueTag] -> ShowS)
-> Show UniqueTag
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> UniqueTag -> ShowS
showsPrec :: Int -> UniqueTag -> ShowS
$cshow :: UniqueTag -> String
show :: UniqueTag -> String
$cshowList :: [UniqueTag] -> ShowS
showList :: [UniqueTag] -> ShowS
Show, Int -> UniqueTag
UniqueTag -> Int
UniqueTag -> [UniqueTag]
UniqueTag -> UniqueTag
UniqueTag -> UniqueTag -> [UniqueTag]
UniqueTag -> UniqueTag -> UniqueTag -> [UniqueTag]
(UniqueTag -> UniqueTag)
-> (UniqueTag -> UniqueTag)
-> (Int -> UniqueTag)
-> (UniqueTag -> Int)
-> (UniqueTag -> [UniqueTag])
-> (UniqueTag -> UniqueTag -> [UniqueTag])
-> (UniqueTag -> UniqueTag -> [UniqueTag])
-> (UniqueTag -> UniqueTag -> UniqueTag -> [UniqueTag])
-> Enum UniqueTag
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
$csucc :: UniqueTag -> UniqueTag
succ :: UniqueTag -> UniqueTag
$cpred :: UniqueTag -> UniqueTag
pred :: UniqueTag -> UniqueTag
$ctoEnum :: Int -> UniqueTag
toEnum :: Int -> UniqueTag
$cfromEnum :: UniqueTag -> Int
fromEnum :: UniqueTag -> Int
$cenumFrom :: UniqueTag -> [UniqueTag]
enumFrom :: UniqueTag -> [UniqueTag]
$cenumFromThen :: UniqueTag -> UniqueTag -> [UniqueTag]
enumFromThen :: UniqueTag -> UniqueTag -> [UniqueTag]
$cenumFromTo :: UniqueTag -> UniqueTag -> [UniqueTag]
enumFromTo :: UniqueTag -> UniqueTag -> [UniqueTag]
$cenumFromThenTo :: UniqueTag -> UniqueTag -> UniqueTag -> [UniqueTag]
enumFromThenTo :: UniqueTag -> UniqueTag -> UniqueTag -> [UniqueTag]
Enum, UniqueTag
UniqueTag -> UniqueTag -> Bounded UniqueTag
forall a. a -> a -> Bounded a
$cminBound :: UniqueTag
minBound :: UniqueTag
$cmaxBound :: UniqueTag
maxBound :: UniqueTag
Bounded)

uniqueTag :: UniqueTag -> Char
uniqueTag :: UniqueTag -> Char
uniqueTag UniqueTag
AlphaTyVarTag        = Char
'1'
uniqueTag UniqueTag
BcoTag               = Char
'I'
uniqueTag UniqueTag
BlockIdTag           = Char
'L'
uniqueTag UniqueTag
BoxedTupleDataTag    = Char
'7'
uniqueTag UniqueTag
BoxedTupleTyConTag   = Char
'4'
uniqueTag UniqueTag
BoxingTyConTag       = Char
'b'
uniqueTag UniqueTag
BuiltinTag           = Char
'B'
uniqueTag UniqueTag
CmmTag               = Char
'c'
uniqueTag UniqueTag
CodeGenTag           = Char
'n'
uniqueTag UniqueTag
CostCentreTag        = Char
'C'
uniqueTag UniqueTag
CTupleDataTag        = Char
'm'
uniqueTag UniqueTag
CTupleSelTag         = Char
'j'
uniqueTag UniqueTag
CTupleTag            = Char
'k'
uniqueTag UniqueTag
DataNSTag            = Char
'd'
uniqueTag UniqueTag
DsTag                = Char
'D'
uniqueTag UniqueTag
FldNSTag             = Char
'f'
uniqueTag UniqueTag
HscTag               = Char
'r'
uniqueTag UniqueTag
IfaceTag             = Char
'i'
uniqueTag UniqueTag
JsTag                = Char
'J'
uniqueTag UniqueTag
LocalTag             = Char
'X'
uniqueTag UniqueTag
PluginTag            = Char
'p'
uniqueTag UniqueTag
PreludeClassTag      = Char
'2'
uniqueTag UniqueTag
PreludeDataConTag    = Char
'6'
uniqueTag UniqueTag
PreludeMiscIdTag     = Char
'0'
uniqueTag UniqueTag
PreludeTyConTag      = Char
'3'
uniqueTag UniqueTag
PrimOpTag            = Char
'9'
uniqueTag UniqueTag
PseudoTag            = Char
'E'
uniqueTag UniqueTag
RegClassTag          = Char
'A'
uniqueTag UniqueTag
RegPairTag           = Char
'P'
uniqueTag UniqueTag
RegSingleTag         = Char
'R'
uniqueTag UniqueTag
RegSubTag            = Char
'S'
uniqueTag UniqueTag
RnIfaceTag           = Char
'M'
uniqueTag UniqueTag
SimplTag             = Char
's'
uniqueTag UniqueTag
SkolemTag            = Char
'K'
uniqueTag UniqueTag
SrtTag               = Char
'u'
uniqueTag UniqueTag
StgPTag              = Char
'g'
uniqueTag UniqueTag
StgTag               = Char
't'
uniqueTag UniqueTag
SumTag               = Char
'z'
uniqueTag UniqueTag
TcNSTag              = Char
'N'
uniqueTag UniqueTag
TcTag                = Char
'a'
uniqueTag UniqueTag
TsanTag              = Char
'T'
uniqueTag UniqueTag
TvNSTag              = Char
'v'
uniqueTag UniqueTag
UnboxedTupleDataTag  = Char
'8'
uniqueTag UniqueTag
UnboxedTupleTyConTag = Char
'5'
uniqueTag UniqueTag
UniqueRenamerTag     = Char
'Q'
uniqueTag UniqueTag
VarNSTag             = Char
'V'
uniqueTag UniqueTag
VirtualRegTag        = Char
'H'
uniqueTag UniqueTag
NullTag              = Int -> Char
chr Int
0
{-# INLINE uniqueTag #-}

charToUniqueTag :: Char -> UniqueTag
charToUniqueTag :: Char -> UniqueTag
charToUniqueTag Char
'0' = UniqueTag
PreludeMiscIdTag
charToUniqueTag Char
'1' = UniqueTag
AlphaTyVarTag
charToUniqueTag Char
'2' = UniqueTag
PreludeClassTag
charToUniqueTag Char
'3' = UniqueTag
PreludeTyConTag
charToUniqueTag Char
'4' = UniqueTag
BoxedTupleTyConTag
charToUniqueTag Char
'5' = UniqueTag
UnboxedTupleTyConTag
charToUniqueTag Char
'6' = UniqueTag
PreludeDataConTag
charToUniqueTag Char
'7' = UniqueTag
BoxedTupleDataTag
charToUniqueTag Char
'8' = UniqueTag
UnboxedTupleDataTag
charToUniqueTag Char
'9' = UniqueTag
PrimOpTag
charToUniqueTag Char
'a' = UniqueTag
TcTag
charToUniqueTag Char
'A' = UniqueTag
RegClassTag
charToUniqueTag Char
'b' = UniqueTag
BoxingTyConTag
charToUniqueTag Char
'B' = UniqueTag
BuiltinTag
charToUniqueTag Char
'c' = UniqueTag
CmmTag
charToUniqueTag Char
'C' = UniqueTag
CostCentreTag
charToUniqueTag Char
'd' = UniqueTag
DataNSTag
charToUniqueTag Char
'D' = UniqueTag
DsTag
charToUniqueTag Char
'E' = UniqueTag
PseudoTag
charToUniqueTag Char
'f' = UniqueTag
FldNSTag
charToUniqueTag Char
'g' = UniqueTag
StgPTag
charToUniqueTag Char
'H' = UniqueTag
VirtualRegTag
charToUniqueTag Char
'i' = UniqueTag
IfaceTag
charToUniqueTag Char
'I' = UniqueTag
BcoTag
charToUniqueTag Char
'j' = UniqueTag
CTupleSelTag
charToUniqueTag Char
'J' = UniqueTag
JsTag
charToUniqueTag Char
'k' = UniqueTag
CTupleTag
charToUniqueTag Char
'K' = UniqueTag
SkolemTag
charToUniqueTag Char
'L' = UniqueTag
BlockIdTag
charToUniqueTag Char
'm' = UniqueTag
CTupleDataTag
charToUniqueTag Char
'M' = UniqueTag
RnIfaceTag
charToUniqueTag Char
'n' = UniqueTag
CodeGenTag
charToUniqueTag Char
'N' = UniqueTag
TcNSTag
charToUniqueTag Char
'p' = UniqueTag
PluginTag
charToUniqueTag Char
'P' = UniqueTag
RegPairTag
charToUniqueTag Char
'Q' = UniqueTag
UniqueRenamerTag
charToUniqueTag Char
'r' = UniqueTag
HscTag
charToUniqueTag Char
'R' = UniqueTag
RegSingleTag
charToUniqueTag Char
's' = UniqueTag
SimplTag
charToUniqueTag Char
'S' = UniqueTag
RegSubTag
charToUniqueTag Char
't' = UniqueTag
StgTag
charToUniqueTag Char
'T' = UniqueTag
TsanTag
charToUniqueTag Char
'u' = UniqueTag
SrtTag
charToUniqueTag Char
'v' = UniqueTag
TvNSTag
charToUniqueTag Char
'V' = UniqueTag
VarNSTag
charToUniqueTag Char
'X' = UniqueTag
LocalTag
charToUniqueTag Char
'z' = UniqueTag
SumTag
charToUniqueTag Char
c
  | Char -> Int
ord Char
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = UniqueTag
NullTag
  | Bool
otherwise = String -> UniqueTag
forall a. HasCallStack => String -> a
panic (String -> UniqueTag) -> String -> UniqueTag
forall a b. (a -> b) -> a -> b
$ String
"charToUniqueTag: unknown tag for char " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Char -> String
forall a. Show a => a -> String
show Char
c
{-# INLINE charToUniqueTag #-}


{-# INLINE uNIQUE_BITS #-}
uNIQUE_BITS :: Int
uNIQUE_BITS :: Int
uNIQUE_BITS = Int
64 Int -> Int -> Int
forall a. Num a => a -> a -> a
- UNIQUE_TAG_BITS

{-
Now come the functions which construct uniques from their pieces, and vice versa.
The stuff about unique *supplies* is handled further down this module.
-}

unpkUnique :: Unique -> (UniqueTag, Word64)        -- The reverse
unpkUniqueGrimly :: Unique -> (Char, Word64)        -- The reverse

mkUniqueGrimily :: Word64 -> Unique                -- A trap-door for UniqSupply
getKey          :: Unique -> Word64                -- for Var

incrUnique   :: Unique -> Unique
stepUnique   :: Unique -> Word64 -> Unique
newTagUnique :: Unique -> UniqueTag -> Unique
newTagUniqueGrimly :: Unique -> Char -> Unique

mkUniqueGrimily :: Word64 -> Unique
mkUniqueGrimily = Word64 -> Unique
MkUnique

{-# INLINE getKey #-}
getKey :: Unique -> Word64
getKey (MkUnique Word64
x) = Word64
x

incrUnique :: Unique -> Unique
incrUnique (MkUnique Word64
i) = Word64 -> Unique
MkUnique (Word64
i Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1)
stepUnique :: Unique -> Word64 -> Unique
stepUnique (MkUnique Word64
i) Word64
n = Word64 -> Unique
MkUnique (Word64
i Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
n)

mkLocalUnique :: Word64 -> Unique
mkLocalUnique :: Word64 -> Unique
mkLocalUnique Word64
i = UniqueTag -> Word64 -> Unique
mkUnique UniqueTag
LocalTag Word64
i

minLocalUnique :: Unique
minLocalUnique :: Unique
minLocalUnique = Word64 -> Unique
mkLocalUnique Word64
0

maxLocalUnique :: Unique
maxLocalUnique :: Unique
maxLocalUnique = Word64 -> Unique
mkLocalUnique Word64
uniqueMask

-- newTagUnique changes the "domain" of a unique to a different char
newTagUnique :: Unique -> UniqueTag -> Unique
newTagUnique Unique
u UniqueTag
c = Unique -> Char -> Unique
newTagUniqueGrimly Unique
u (UniqueTag -> Char
uniqueTag UniqueTag
c)

newTagUniqueGrimly :: Unique -> Char -> Unique
newTagUniqueGrimly Unique
u Char
c = Char -> Word64 -> Unique
mkUniqueGrimilyWithTag Char
c Word64
i where (Char
_,Word64
i) = Unique -> (Char, Word64)
unpkUniqueGrimly Unique
u

-- | Bitmask that has zeros for the tag bits and ones for the rest.
uniqueMask :: Word64
uniqueMask :: Word64
uniqueMask = (Word64
1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
uNIQUE_BITS) Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1

-- | Put the character in the highest bits of the Word64.
-- This may truncate the character to UNIQUE_TAG_BITS.
-- This function is used in @`mkSplitUniqSupply`@ so that it can
-- precompute and share the tag part of the uniques it generates.
mkTag :: Char -> Word64
mkTag :: Char -> Word64
mkTag Char
c = Int -> Word64
HasDebugCallStack => Int -> Word64
intToWord64 (Char -> Int
ord Char
c) Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
uNIQUE_BITS

-- pop the Char in the top 8 bits of the Unique(Supply)

-- No 64-bit bugs here, as long as we have at least 32 bits. --JSM

-- and as long as the Char fits in 8 bits, which we assume anyway!

mkUniqueGrimilyWithTag :: Char -> Word64 -> Unique       -- Builds a unique from pieces
mkUniqueGrimilyWithTag :: Char -> Word64 -> Unique
mkUniqueGrimilyWithTag Char
c Word64
i
  = Word64 -> Unique
MkUnique (Word64
tag Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.|. Word64
bits)
  where
    tag :: Word64
tag  = Char -> Word64
mkTag Char
c
    bits :: Word64
bits = Word64
i Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
uniqueMask

{-# INLINE mkUniqueGrimilyWithTag #-}

mkUnique :: UniqueTag -> Word64 -> Unique       -- Builds a unique from pieces
mkUnique :: UniqueTag -> Word64 -> Unique
mkUnique UniqueTag
c Word64
i = Char -> Word64 -> Unique
mkUniqueGrimilyWithTag (UniqueTag -> Char
uniqueTag UniqueTag
c) Word64
i

{-# INLINE mkUnique #-}

mkUniqueInt :: UniqueTag -> Int -> Unique
mkUniqueInt :: UniqueTag -> Int -> Unique
mkUniqueInt UniqueTag
c Int
i = UniqueTag -> Word64 -> Unique
mkUnique UniqueTag
c (Int -> Word64
HasDebugCallStack => Int -> Word64
intToWord64 Int
i)

{-# INLINE mkUniqueInt #-}

mkUniqueIntGrimily :: Int -> Unique
mkUniqueIntGrimily :: Int -> Unique
mkUniqueIntGrimily = Word64 -> Unique
MkUnique (Word64 -> Unique) -> (Int -> Word64) -> Int -> Unique
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word64
HasDebugCallStack => Int -> Word64
intToWord64

{-# INLINE mkUniqueIntGrimily #-}

unpkUniqueGrimly :: Unique -> (Char, Word64)
unpkUniqueGrimly (MkUnique Word64
u)
  = let
        -- The potentially truncating use of fromIntegral here is safe
        -- because the argument is just the tag bits after shifting.
        tag :: Char
tag = Int -> Char
chr (Word64 -> Int
HasDebugCallStack => Word64 -> Int
word64ToInt (Word64
u Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
uNIQUE_BITS))
        i :: Word64
i   = Word64
u Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
uniqueMask
    in
    (Char
tag, Word64
i)
{-# INLINE unpkUniqueGrimly #-}


unpkUnique :: Unique -> (UniqueTag, Word64)
unpkUnique Unique
u = case Unique -> (Char, Word64)
unpkUniqueGrimly Unique
u of
  (Char
c, Word64
i) -> ( Char -> UniqueTag
charToUniqueTag Char
c, Word64
i)
{-# INLINE unpkUnique #-}

-- | The interface file symbol-table encoding assumes that known-key uniques fit
-- in 30-bits; verify this.
--
-- See Note [Symbol table representation of names] in "GHC.Iface.Binary" for details.
isValidKnownKeyUnique :: Unique -> Bool
isValidKnownKeyUnique :: Unique -> Bool
isValidKnownKeyUnique Unique
u =
    case Unique -> (Char, Word64)
unpkUniqueGrimly Unique
u of
      (Char
c, Word64
x) -> Char -> Int
ord Char
c Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0xff Bool -> Bool -> Bool
&& Word64
x Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= (Word64
1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
22)

{-
************************************************************************
*                                                                      *
\subsection[Uniquable-class]{The @Uniquable@ class}
*                                                                      *
************************************************************************
-}

-- | Class of things that we can obtain a 'Unique' from
class Uniquable a where
    getUnique :: a -> Unique

hasKey          :: Uniquable a => a -> Unique -> Bool
a
x hasKey :: forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
k    = a -> Unique
forall a. Uniquable a => a -> Unique
getUnique a
x Unique -> Unique -> Bool
forall a. Eq a => a -> a -> Bool
== Unique
k

instance Uniquable FastString where
 getUnique :: FastString -> Unique
getUnique FastString
fs = Int -> Unique
mkUniqueIntGrimily (FastString -> Int
uniqueOfFS FastString
fs)

instance Uniquable Int where
  getUnique :: Int -> Unique
getUnique Int
i = Int -> Unique
mkUniqueIntGrimily Int
i

instance Uniquable Word64 where
  getUnique :: Word64 -> Unique
getUnique Word64
i = Word64 -> Unique
mkUniqueGrimily Word64
i

instance Uniquable ModuleName where
  getUnique :: ModuleName -> Unique
getUnique (ModuleName FastString
nm) = FastString -> Unique
forall a. Uniquable a => a -> Unique
getUnique FastString
nm


{-
************************************************************************
*                                                                      *
\subsection[Unique-instances]{Instance declarations for @Unique@}
*                                                                      *
************************************************************************

And the whole point (besides uniqueness) is fast equality.  We don't
use `deriving' because we want {\em precise} control of ordering
(equality on @Uniques@ is v common).
-}

-- Note [Unique Determinism]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~
-- The order of allocated @Uniques@ is not stable across rebuilds.
-- The main reason for that is that typechecking interface files pulls
-- @Uniques@ from @UniqSupply@ and the interface file for the module being
-- currently compiled can, but doesn't have to exist.
--
-- It gets more complicated if you take into account that the interface
-- files are loaded lazily and that building multiple files at once has to
-- work for any subset of interface files present. When you add parallelism
-- this makes @Uniques@ hopelessly random.
--
-- As such, to get deterministic builds, the order of the allocated
-- @Uniques@ should not affect the final result.
-- see also wiki/deterministic-builds
--
-- Note [Unique Determinism and code generation]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- The goal of the deterministic builds (wiki/deterministic-builds, #4012)
-- is to get ABI compatible binaries given the same inputs and environment.
-- The motivation behind that is that if the ABI doesn't change the
-- binaries can be safely reused.
--
-- Besides ABI/interface determinism, we also guarantee bit-for-bit identical
-- binaries (when -fobject-determinism is given), also known as object
-- determinism (#12935)
--
-- To achieve this, we must take care to non-determinism in the code
-- generation, and, in particular, guarantee that the existing uniques are
-- renamed deterministically and new ones are produced deterministically too.
-- The overview of object determinism is given by Note [Object determinism].
-- References to this note identify code where the unique determinism may
-- impact object determinism more specifically.

eqUnique :: Unique -> Unique -> Bool
eqUnique :: Unique -> Unique -> Bool
eqUnique (MkUnique Word64
u1) (MkUnique Word64
u2) = Word64
u1 Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
u2

ltUnique :: Unique -> Unique -> Bool
ltUnique :: Unique -> Unique -> Bool
ltUnique (MkUnique Word64
u1) (MkUnique Word64
u2) = Word64
u1 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Word64
u2

-- Provided here to make it explicit at the call-site that it can
-- introduce non-determinism.
-- See Note [Unique Determinism]
-- See Note [No Ord for Unique]
nonDetCmpUnique :: Unique -> Unique -> Ordering
nonDetCmpUnique :: Unique -> Unique -> Ordering
nonDetCmpUnique (MkUnique Word64
u1) (MkUnique Word64
u2)
  = if Word64
u1 Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
u2 then Ordering
EQ else if Word64
u1 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Word64
u2 then Ordering
LT else Ordering
GT

{-
Note [No Ord for Unique]
~~~~~~~~~~~~~~~~~~~~~~~~~~
As explained in Note [Unique Determinism] the relative order of Uniques
is nondeterministic. To prevent from accidental use the Ord Unique
instance has been removed.
This makes it easier to maintain deterministic builds, but comes with some
drawbacks.
The biggest drawback is that Maps keyed by Uniques can't directly be used.
The alternatives are:

  1) Use UniqFM or UniqDFM, see Note [Deterministic UniqFM] to decide which
  2) Create a newtype wrapper based on Unique ordering where nondeterminism
     is controlled. See GHC.Unit.Module.Env.ModuleEnv
  3) Change the algorithm to use nonDetCmpUnique and document why it's still
     deterministic
  4) Use TrieMap as done in GHC.Cmm.CommonBlockElim.groupByLabel
-}

instance Eq Unique where
    Unique
a == :: Unique -> Unique -> Bool
== Unique
b = Unique -> Unique -> Bool
eqUnique Unique
a Unique
b
    Unique
a /= :: Unique -> Unique -> Bool
/= Unique
b = Bool -> Bool
not (Unique -> Unique -> Bool
eqUnique Unique
a Unique
b)

instance Uniquable Unique where
    getUnique :: Unique -> Unique
getUnique Unique
u = Unique
u

-- We do sometimes make strings with @Uniques@ in them:

showUnique :: Unique -> String
showUnique :: Unique -> String
showUnique Unique
uniq
  = String
tagStr String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word64 -> String
w64ToBase62 Word64
u
  where
    (Char
tag, Word64
u) = Unique -> (Char, Word64)
unpkUniqueGrimly Unique
uniq
    -- Avoid emitting non-printable characters in pretty uniques.
    -- See #25989.
    tagStr :: String
tagStr
      | Bool -> Bool
not (Char -> Bool
isPrint Char
tag)  = Int -> String
forall a. Show a => a -> String
show (Char -> Int
ord Char
tag) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"_"
      | Bool
otherwise          = [Char
tag]

pprUniqueAlways :: IsLine doc => Unique -> doc
-- The "always" means regardless of -dsuppress-uniques
-- It replaces the old pprUnique to remind callers that
-- they should consider whether they want to consult
-- Opt_SuppressUniques
pprUniqueAlways :: forall doc. IsLine doc => Unique -> doc
pprUniqueAlways Unique
u
  = String -> doc
forall doc. IsLine doc => String -> doc
text (Unique -> String
showUnique Unique
u)
{-# SPECIALIZE pprUniqueAlways :: Unique -> SDoc #-}
{-# SPECIALIZE pprUniqueAlways :: Unique -> HLine #-} -- see Note [SPECIALIZE to HDoc] in GHC.Utils.Outputable

instance Outputable Unique where
    ppr :: Unique -> SDoc
ppr = Unique -> SDoc
forall doc. IsLine doc => Unique -> doc
pprUniqueAlways

instance Show Unique where
    show :: Unique -> String
show Unique
uniq = Unique -> String
showUnique Unique
uniq

{-
************************************************************************
*                                                                      *
\subsection[Utils-base62]{Base-62 numbers}
*                                                                      *
************************************************************************

A character-stingy way to read/write numbers (notably Uniques).
The ``62-its'' are \tr{[0-9a-zA-Z]}.
Code stolen from Lennart.
-}

w64ToBase62 :: Word64 -> String
w64ToBase62 :: Word64 -> String
w64ToBase62 Word64
n_ = Word64 -> ShowS
go Word64
n_ String
""
  where
    -- The potentially truncating uses of fromIntegral here are safe
    -- because the argument is guaranteed to be less than 62 in both cases.
    go :: Word64 -> ShowS
go Word64
n String
cs | Word64
n Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Word64
62
            = let !c :: Char
c = Int -> Char
chooseChar62 (Word64 -> Int
HasDebugCallStack => Word64 -> Int
word64ToInt Word64
n) in Char
c Char -> ShowS
forall a. a -> [a] -> [a]
: String
cs
            | Bool
otherwise
            = Word64 -> ShowS
go Word64
q (Char
c Char -> ShowS
forall a. a -> [a] -> [a]
: String
cs) where (!Word64
q, Word64
r) = Word64 -> Word64 -> (Word64, Word64)
forall a. Integral a => a -> a -> (a, a)
quotRem Word64
n Word64
62
                                  !c :: Char
c = Int -> Char
chooseChar62 (Word64 -> Int
HasDebugCallStack => Word64 -> Int
word64ToInt Word64
r)

    chooseChar62 :: Int -> Char
    {-# INLINE chooseChar62 #-}
    chooseChar62 :: Int -> Char
chooseChar62 (I# Int#
n) = Char# -> Char
C# (Addr# -> Int# -> Char#
indexCharOffAddr# Addr#
chars62 Int#
n)
    chars62 :: Addr#
chars62 = Addr#
"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"#