    {-
    (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(..),
            uNIQUE_BITS,

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

            pprUniqueAlways,

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

            newTagUnique,
            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.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 )

    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 an ASCII character.  It is typically used to make it easier
    to distinguish uniques constructed by different parts of the compiler.
    There is a (potentially incomplete) list of unique tags used given in
    GHC.Builtin.Uniques. See Note [Uniques for wired-in prelude things and known tags]

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

    -}

    -- | 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

    {-# 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 -> (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 -> 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 = Char -> Word64 -> Unique
    mkUnique Char
    'X' 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 -> Char -> Unique
    newTagUnique Unique
    u Char
    c = Char -> Word64 -> Unique
    mkUnique Char
    c Word64
    i where (Char
    _,Word64
    i) = Unique -> (Char, Word64)
    unpkUnique 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!

    mkUnique :: Char -> Word64 -> Unique       -- Builds a unique from pieces
    -- EXPORTED and used only in GHC.Builtin.Uniques
    mkUnique :: Char -> Word64 -> Unique
    mkUnique 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

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

    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

    unpkUnique :: Unique -> (Char, Word64)
    unpkUnique (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)

    -- | 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)
    unpkUnique 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
      = case Unique -> (Char, Word64)
    unpkUnique Unique
    uniq of
          (Char
    tag, Word64
    u) -> Char
    tag Char -> String -> String
    forall a. a -> [a] -> [a]
    : Word64 -> String
    w64ToBase62 Word64
    u

    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 -> String -> String
    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 -> String -> String
    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 -> String -> String
    forall a. a -> [a] -> [a]
    : String
    cs
                | Bool
    otherwise
                = Word64 -> String -> String
    go Word64
    q (Char
    c Char -> String -> String
    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"#