{- (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, BangPatterns, MagicHash #-} module GHC.Types.Unique ( -- * Main data types Unique, Uniquable(..), uNIQUE_BITS, -- ** Constructors, destructors and operations on 'Unique's hasKey, pprUniqueAlways, mkUniqueGrimily, getKey, mkUnique, unpkUnique, 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 "HsVersions.h" #include "Unique.h" import GHC.Prelude import GHC.Data.FastString import GHC.Utils.Outputable import GHC.Utils.Misc import GHC.Utils.Panic -- just for implementing a fast [0,61) -> Char function import GHC.Exts (indexCharOffAddr#, Char(..), Int(..)) import Data.Char ( chr, ord ) {- ************************************************************************ * * \subsection[Unique-type]{@Unique@ type and operations} * * ************************************************************************ Note [Uniques and masks] ~~~~~~~~~~~~~~~~~~~~~~~~ A `Unique` in GHC is a Word-sized value composed of two pieces: * A "mask", of width `UNIQUE_TAG_BITS`, in the high order bits * A number, of width `uNIQUE_BITS`, which fills up the remainder of the Word The mask 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 masks used given in GHC.Builtin.Uniques. See Note [Uniques-prelude - Uniques for wired-in Prelude things] `mkUnique` constructs a `Unique` from its pieces mkUnique :: Char -> Int -> 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 Int {-# INLINE uNIQUE_BITS #-} uNIQUE_BITS :: Int uNIQUE_BITS :: Int uNIQUE_BITS = forall b. FiniteBits b => b -> Int finiteBitSize (Int 0 :: 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, Int) -- The reverse mkUniqueGrimily :: Int -> Unique -- A trap-door for UniqSupply getKey :: Unique -> Int -- for Var incrUnique :: Unique -> Unique stepUnique :: Unique -> Int -> Unique newTagUnique :: Unique -> Char -> Unique mkUniqueGrimily :: Int -> Unique mkUniqueGrimily = Int -> Unique MkUnique {-# INLINE getKey #-} getKey :: Unique -> Int getKey (MkUnique Int x) = Int x incrUnique :: Unique -> Unique incrUnique (MkUnique Int i) = Int -> Unique MkUnique (Int i forall a. Num a => a -> a -> a + Int 1) stepUnique :: Unique -> Int -> Unique stepUnique (MkUnique Int i) Int n = Int -> Unique MkUnique (Int i forall a. Num a => a -> a -> a + Int n) mkLocalUnique :: Int -> Unique mkLocalUnique :: Int -> Unique mkLocalUnique Int i = Char -> Int -> Unique mkUnique Char 'X' Int i minLocalUnique :: Unique minLocalUnique :: Unique minLocalUnique = Int -> Unique mkLocalUnique Int 0 maxLocalUnique :: Unique maxLocalUnique :: Unique maxLocalUnique = Int -> Unique mkLocalUnique Int uniqueMask -- newTagUnique changes the "domain" of a unique to a different char newTagUnique :: Unique -> Char -> Unique newTagUnique Unique u Char c = Char -> Int -> Unique mkUnique Char c Int i where (Char _,Int i) = Unique -> (Char, Int) unpkUnique Unique u -- | How many bits are devoted to the unique index (as opposed to the class -- character). uniqueMask :: Int uniqueMask :: Int uniqueMask = (Int 1 forall a. Bits a => a -> Int -> a `shiftL` Int uNIQUE_BITS) forall a. Num a => a -> a -> a - Int 1 -- 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 -> Int -> Unique -- Builds a unique from pieces -- EXPORTED and used only in GHC.Builtin.Uniques mkUnique :: Char -> Int -> Unique mkUnique Char c Int i = Int -> Unique MkUnique (Int tag forall a. Bits a => a -> a -> a .|. Int bits) where tag :: Int tag = Char -> Int ord Char c forall a. Bits a => a -> Int -> a `shiftL` Int uNIQUE_BITS bits :: Int bits = Int i forall a. Bits a => a -> a -> a .&. Int uniqueMask unpkUnique :: Unique -> (Char, Int) unpkUnique (MkUnique Int u) = let -- as long as the Char may have its eighth bit set, we -- really do need the logical right-shift here! tag :: Char tag = Int -> Char chr (Int u forall a. Bits a => a -> Int -> a `shiftR` Int uNIQUE_BITS) i :: Int i = Int u forall a. Bits a => a -> a -> a .&. Int uniqueMask in (Char tag, Int 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, Int) unpkUnique Unique u of (Char c, Int x) -> Char -> Int ord Char c forall a. Ord a => a -> a -> Bool < Int 0xff Bool -> Bool -> Bool && Int x forall a. Ord a => a -> a -> Bool <= (Int 1 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 = forall a. Uniquable a => a -> Unique getUnique a x forall a. Eq a => a -> a -> Bool == Unique k instance Uniquable FastString where getUnique :: FastString -> Unique getUnique FastString fs = Int -> Unique mkUniqueGrimily (FastString -> Int uniqueOfFS FastString fs) instance Uniquable Int where getUnique :: Int -> Unique getUnique Int i = Int -> Unique mkUniqueGrimily Int i {- ************************************************************************ * * \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. -- Note that this is weaker than bit-for-bit identical binaries and getting -- bit-for-bit identical binaries is not a goal for now. -- This means that we don't care about nondeterminism that happens after -- the interface files are created, in particular we don't care about -- register allocation and code generation. -- To track progress on bit-for-bit determinism see #12262. eqUnique :: Unique -> Unique -> Bool eqUnique :: Unique -> Unique -> Bool eqUnique (MkUnique Int u1) (MkUnique Int u2) = Int u1 forall a. Eq a => a -> a -> Bool == Int u2 ltUnique :: Unique -> Unique -> Bool ltUnique :: Unique -> Unique -> Bool ltUnique (MkUnique Int u1) (MkUnique Int u2) = Int u1 forall a. Ord a => a -> a -> Bool < Int 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 Int u1) (MkUnique Int u2) = if Int u1 forall a. Eq a => a -> a -> Bool == Int u2 then Ordering EQ else if Int u1 forall a. Ord a => a -> a -> Bool < Int 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 Module.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, Int) unpkUnique Unique uniq of (Char tag, Int u) -> Char -> Int -> String -> String finish_show Char tag Int u (Int -> String iToBase62 Int u) finish_show :: Char -> Int -> String -> String finish_show :: Char -> Int -> String -> String finish_show Char 't' Int u String _pp_u | Int u forall a. Ord a => a -> a -> Bool < Int 26 = -- Special case to make v common tyvars, t1, t2, ... -- come out as a, b, ... (shorter, easier to read) [Int -> Char chr (Char -> Int ord Char 'a' forall a. Num a => a -> a -> a + Int u)] finish_show Char tag Int _ String pp_u = Char tag forall a. a -> [a] -> [a] : String pp_u pprUniqueAlways :: Unique -> SDoc -- 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 :: Unique -> SDoc pprUniqueAlways Unique u = String -> SDoc text (Unique -> String showUnique Unique u) instance Outputable Unique where ppr :: Unique -> SDoc ppr = Unique -> SDoc 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]}. We don't handle negative Ints. Code stolen from Lennart. -} iToBase62 :: Int -> String iToBase62 :: Int -> String iToBase62 Int n_ = ASSERT(n_ >= 0) go n_ "" where go :: Int -> String -> String go Int n String cs | Int n forall a. Ord a => a -> a -> Bool < Int 62 = let !c :: Char c = Int -> Char chooseChar62 Int n in Char c forall a. a -> [a] -> [a] : String cs | Bool otherwise = Int -> String -> String go Int q (Char c forall a. a -> [a] -> [a] : String cs) where (!Int q, Int r) = forall a. Integral a => a -> a -> (a, a) quotRem Int n Int 62 !c :: Char c = Int -> Char chooseChar62 Int 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"#