{-# LANGUAGE BangPatterns, CPP, MagicHash,
             ScopedTypeVariables, UnliftedFFITypes, DeriveDataTypeable,
             DefaultSignatures, FlexibleContexts, TypeFamilies,
             MultiParamTypeClasses #-}

#if __GLASGOW_HASKELL__ >= 801
{-# LANGUAGE PolyKinds #-} -- For TypeRep instances
#endif

{-# OPTIONS_GHC -fno-warn-deprecations #-}

------------------------------------------------------------------------
-- |
-- Module      :  Data.Hashable.Class
-- Copyright   :  (c) Milan Straka 2010
--                (c) Johan Tibell 2011
--                (c) Bryan O'Sullivan 2011, 2012
-- SPDX-License-Identifier : BSD-3-Clause
-- Maintainer  :  johan.tibell@gmail.com
-- Stability   :  provisional
-- Portability :  portable
--
-- This module defines a class, 'Hashable', for types that can be
-- converted to a hash value.  This class exists for the benefit of
-- hashing-based data structures.  The module provides instances for
-- most standard types.

module Data.Hashable.Class
    (
      -- * Computing hash values
      Hashable(..)
    , Hashable1(..)
    , Hashable2(..)

      -- ** Support for generics
    , genericHashWithSalt
    , genericLiftHashWithSalt
    , GHashable(..)
    , HashArgs(..)
    , Zero
    , One

      -- * Creating new instances
    , hashUsing
    , hashPtr
    , hashPtrWithSalt
    , hashByteArray
    , hashByteArrayWithSalt
    , defaultHashWithSalt
      -- * Higher Rank Functions
    , hashWithSalt1
    , hashWithSalt2
    , defaultLiftHashWithSalt
    -- * Caching hashes
    , Hashed
    , hashed
    , unhashed
    , mapHashed
    , traverseHashed
    ) where

import Control.Applicative (Const(..))
import Control.Exception (assert)
import Control.DeepSeq (NFData(rnf))
import Data.Bits (shiftL, shiftR, xor)
import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as BL
import qualified Data.ByteString.Unsafe as B
import Data.Complex (Complex(..))
import Data.Int (Int8, Int16, Int32, Int64)
import Data.List (foldl')
import Data.Ratio (Ratio, denominator, numerator)
import qualified Data.Text as T
import qualified Data.Text.Array as TA
import qualified Data.Text.Internal as T
import qualified Data.Text.Lazy as TL
import Data.Version (Version(..))
import Data.Word (Word8, Word16, Word32, Word64)
import Foreign.C (CString)
import Foreign.Marshal.Utils (with)
import Foreign.Ptr (Ptr, FunPtr, IntPtr, WordPtr, castPtr, castFunPtrToPtr, ptrToIntPtr)
import Foreign.Storable (alignment, peek, sizeOf)
import GHC.Base (ByteArray#)
import GHC.Conc (ThreadId(..))
import GHC.Prim (ThreadId#)
import System.IO.Unsafe (unsafeDupablePerformIO)
import System.Mem.StableName
import Data.Unique (Unique, hashUnique)

-- As we use qualified F.Foldable, we don't get warnings with newer base
import qualified Data.Foldable as F

#if MIN_VERSION_base(4,7,0)
import Data.Proxy (Proxy)
#endif

#if MIN_VERSION_base(4,7,0)
import Data.Fixed (Fixed(..))
#endif

#if MIN_VERSION_base(4,8,0)
import Data.Functor.Identity (Identity(..))
#endif

import GHC.Generics

#if   MIN_VERSION_base(4,10,0)
import Type.Reflection (Typeable, TypeRep, SomeTypeRep(..))
import Type.Reflection.Unsafe (typeRepFingerprint)
import GHC.Fingerprint.Type(Fingerprint(..))
#elif MIN_VERSION_base(4,8,0)
import Data.Typeable (typeRepFingerprint, Typeable, TypeRep)
import GHC.Fingerprint.Type(Fingerprint(..))
#else
import Data.Typeable.Internal (Typeable, TypeRep (..))
import GHC.Fingerprint.Type(Fingerprint(..))
#endif

#if MIN_VERSION_base(4,5,0)
import Foreign.C (CLong(..))
import Foreign.C.Types (CInt(..))
#else
import Foreign.C (CLong)
import Foreign.C.Types (CInt)
#endif

#if !(MIN_VERSION_base(4,8,0))
import Data.Word (Word)
#endif

#if MIN_VERSION_base(4,7,0)
import Data.Bits (finiteBitSize)
#else
import Data.Bits (bitSize)
#endif

#if !(MIN_VERSION_bytestring(0,10,0))
import qualified Data.ByteString.Lazy.Internal as BL  -- foldlChunks
#endif

#if MIN_VERSION_bytestring(0,10,4)
import qualified Data.ByteString.Short.Internal as BSI
#endif

#ifdef VERSION_ghc_bignum
import GHC.Num.BigNat (BigNat (..))
import GHC.Num.Integer (Integer (..))
import GHC.Num.Natural (Natural (..))
import GHC.Exts (Int (..), sizeofByteArray#)
#endif

#ifdef VERSION_integer_gmp

# if MIN_VERSION_integer_gmp(1,0,0)
#  define MIN_VERSION_integer_gmp_1_0_0
# endif

import GHC.Exts (Int(..))
import GHC.Integer.GMP.Internals (Integer(..))
# if defined(MIN_VERSION_integer_gmp_1_0_0)
import GHC.Exts (sizeofByteArray#)
import GHC.Integer.GMP.Internals (BigNat(BN#))
# endif
#endif

#if MIN_VERSION_base(4,8,0)
import Data.Void (Void, absurd)
import GHC.Exts (Word(..))
#ifndef VERSION_ghc_bignum
import GHC.Natural (Natural(..))
#endif
#endif

#if MIN_VERSION_base(4,9,0)
import qualified Data.List.NonEmpty as NE
import Data.Semigroup
import Data.Functor.Classes (Eq1(..),Ord1(..),Show1(..),showsUnaryWith)

import Data.Functor.Compose (Compose(..))
import qualified Data.Functor.Product as FP
import qualified Data.Functor.Sum as FS
#endif

import Data.String (IsString(..))

#if MIN_VERSION_base(4,9,0)
import Data.Kind (Type)
#else
#define Type *
#endif

#include "MachDeps.h"

infixl 0 `hashWithSalt`

------------------------------------------------------------------------
-- * Computing hash values

-- | A default salt used in the implementation of 'hash'.
defaultSalt :: Int
#if WORD_SIZE_IN_BITS == 64
defaultSalt :: Int
defaultSalt = -Int
3750763034362895579 -- 14695981039346656037 :: Int64
#else
defaultSalt = -2128831035 -- 2166136261 :: Int32
#endif
{-# INLINE defaultSalt #-}

-- | The class of types that can be converted to a hash value.
--
-- Minimal implementation: 'hashWithSalt'.
class Hashable a where
    -- | Return a hash value for the argument, using the given salt.
    --
    -- The general contract of 'hashWithSalt' is:
    --
    --  * If two values are equal according to the '==' method, then
    --    applying the 'hashWithSalt' method on each of the two values
    --    /must/ produce the same integer result if the same salt is
    --    used in each case.
    --
    --  * It is /not/ required that if two values are unequal
    --    according to the '==' method, then applying the
    --    'hashWithSalt' method on each of the two values must produce
    --    distinct integer results. However, the programmer should be
    --    aware that producing distinct integer results for unequal
    --    values may improve the performance of hashing-based data
    --    structures.
    --
    --  * This method can be used to compute different hash values for
    --    the same input by providing a different salt in each
    --    application of the method. This implies that any instance
    --    that defines 'hashWithSalt' /must/ make use of the salt in
    --    its implementation.
    hashWithSalt :: Int -> a -> Int

    -- | Like 'hashWithSalt', but no salt is used. The default
    -- implementation uses 'hashWithSalt' with some default salt.
    -- Instances might want to implement this method to provide a more
    -- efficient implementation than the default implementation.
    hash :: a -> Int
    hash = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
defaultSalt

    default hashWithSalt :: (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int
    hashWithSalt = Int -> a -> Int
forall a. (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int
genericHashWithSalt
    {-# INLINE hashWithSalt #-}

-- | Generic 'hashWithSalt'.
--
-- @since 1.3.0.0
genericHashWithSalt :: (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int
genericHashWithSalt :: Int -> a -> Int
genericHashWithSalt = \Int
salt -> HashArgs Zero Any -> Int -> Rep a Any -> Int
forall arity (f :: * -> *) a.
GHashable arity f =>
HashArgs arity a -> Int -> f a -> Int
ghashWithSalt HashArgs Zero Any
forall a. HashArgs Zero a
HashArgs0 Int
salt (Rep a Any -> Int) -> (a -> Rep a Any) -> a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Rep a Any
forall a x. Generic a => a -> Rep a x
from
{-# INLINE genericHashWithSalt #-}

data Zero
data One

data family HashArgs arity a :: Type
data instance HashArgs Zero a = HashArgs0
newtype instance HashArgs One  a = HashArgs1 (Int -> a -> Int)

-- | The class of types that can be generically hashed.
class GHashable arity f where
    ghashWithSalt :: HashArgs arity a -> Int -> f a -> Int

class Hashable1 t where
    -- | Lift a hashing function through the type constructor.
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> t a -> Int

    default liftHashWithSalt :: (Generic1 t, GHashable One (Rep1 t)) => (Int -> a -> Int) -> Int -> t a -> Int
    liftHashWithSalt = (Int -> a -> Int) -> Int -> t a -> Int
forall (t :: * -> *) a.
(Generic1 t, GHashable One (Rep1 t)) =>
(Int -> a -> Int) -> Int -> t a -> Int
genericLiftHashWithSalt
    {-# INLINE liftHashWithSalt #-}

-- | Generic 'liftHashWithSalt'.
--
-- @since 1.3.0.0
genericLiftHashWithSalt :: (Generic1 t, GHashable One (Rep1 t)) => (Int -> a -> Int) -> Int -> t a -> Int
genericLiftHashWithSalt :: (Int -> a -> Int) -> Int -> t a -> Int
genericLiftHashWithSalt = \Int -> a -> Int
h Int
salt -> HashArgs One a -> Int -> Rep1 t a -> Int
forall arity (f :: * -> *) a.
GHashable arity f =>
HashArgs arity a -> Int -> f a -> Int
ghashWithSalt ((Int -> a -> Int) -> HashArgs One a
forall a. (Int -> a -> Int) -> HashArgs One a
HashArgs1 Int -> a -> Int
h) Int
salt (Rep1 t a -> Int) -> (t a -> Rep1 t a) -> t a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t a -> Rep1 t a
forall k (f :: k -> *) (a :: k). Generic1 f => f a -> Rep1 f a
from1
{-# INLINE genericLiftHashWithSalt #-}

class Hashable2 t where
    -- | Lift a hashing function through the binary type constructor.
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int

-- | Lift the 'hashWithSalt' function through the type constructor.
--
-- > hashWithSalt1 = liftHashWithSalt hashWithSalt
hashWithSalt1 :: (Hashable1 f, Hashable a) => Int -> f a -> Int
hashWithSalt1 :: Int -> f a -> Int
hashWithSalt1 = (Int -> a -> Int) -> Int -> f a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt

-- | Lift the 'hashWithSalt' function through the type constructor.
--
-- > hashWithSalt2 = liftHashWithSalt2 hashWithSalt hashWithSalt
hashWithSalt2 :: (Hashable2 f, Hashable a, Hashable b) => Int -> f a b -> Int
hashWithSalt2 :: Int -> f a b -> Int
hashWithSalt2 = (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> f a b -> Int
forall (t :: * -> * -> *) a b.
Hashable2 t =>
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
liftHashWithSalt2 Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int -> b -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt

-- | Lift the 'hashWithSalt' function halfway through the type constructor.
-- This function makes a suitable default implementation of 'liftHashWithSalt',
-- given that the type constructor @t@ in question can unify with @f a@.
defaultLiftHashWithSalt :: (Hashable2 f, Hashable a) => (Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt :: (Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt Int -> b -> Int
h = (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> f a b -> Int
forall (t :: * -> * -> *) a b.
Hashable2 t =>
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
liftHashWithSalt2 Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int -> b -> Int
h

-- | Since we support a generic implementation of 'hashWithSalt' we
-- cannot also provide a default implementation for that method for
-- the non-generic instance use case. Instead we provide
-- 'defaultHashWith'.
defaultHashWithSalt :: Hashable a => Int -> a -> Int
defaultHashWithSalt :: Int -> a -> Int
defaultHashWithSalt Int
salt a
x = Int
salt Int -> Int -> Int
`combine` a -> Int
forall a. Hashable a => a -> Int
hash a
x

-- | Transform a value into a 'Hashable' value, then hash the
-- transformed value using the given salt.
--
-- This is a useful shorthand in cases where a type can easily be
-- mapped to another type that is already an instance of 'Hashable'.
-- Example:
--
-- > data Foo = Foo | Bar
-- >          deriving (Enum)
-- >
-- > instance Hashable Foo where
-- >     hashWithSalt = hashUsing fromEnum
hashUsing :: (Hashable b) =>
             (a -> b)           -- ^ Transformation function.
          -> Int                -- ^ Salt.
          -> a                  -- ^ Value to transform.
          -> Int
hashUsing :: (a -> b) -> Int -> a -> Int
hashUsing a -> b
f Int
salt a
x = Int -> b -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (a -> b
f a
x)
{-# INLINE hashUsing #-}

instance Hashable Int where
    hash :: Int -> Int
hash = Int -> Int
forall a. a -> a
id
    hashWithSalt :: Int -> Int -> Int
hashWithSalt = Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Int8 where
    hash :: Int8 -> Int
hash = Int8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Int8 -> Int
hashWithSalt = Int -> Int8 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Int16 where
    hash :: Int16 -> Int
hash = Int16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Int16 -> Int
hashWithSalt = Int -> Int16 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Int32 where
    hash :: Int32 -> Int
hash = Int32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Int32 -> Int
hashWithSalt = Int -> Int32 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Int64 where
    hash :: Int64 -> Int
hash Int64
n
#if MIN_VERSION_base(4,7,0)
        | Int -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Int
forall a. HasCallStack => a
undefined :: Int) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
64 = Int64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int64
n
#else
        | bitSize (undefined :: Int) == 64 = fromIntegral n
#endif
        | Bool
otherwise = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int64
n Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor`
                                   (Int64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int64
n Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
32 :: Word64))
    hashWithSalt :: Int -> Int64 -> Int
hashWithSalt = Int -> Int64 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Word where
    hash :: Word -> Int
hash = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Word -> Int
hashWithSalt = Int -> Word -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Word8 where
    hash :: Word8 -> Int
hash = Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Word8 -> Int
hashWithSalt = Int -> Word8 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Word16 where
    hash :: Word16 -> Int
hash = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Word16 -> Int
hashWithSalt = Int -> Word16 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Word32 where
    hash :: Word32 -> Int
hash = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Word32 -> Int
hashWithSalt = Int -> Word32 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Word64 where
    hash :: Word64 -> Int
hash Word64
n
#if MIN_VERSION_base(4,7,0)
        | Int -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Int
forall a. HasCallStack => a
undefined :: Int) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
64 = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
n
#else
        | bitSize (undefined :: Int) == 64 = fromIntegral n
#endif
        | Bool
otherwise = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
n Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
n Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
32))
    hashWithSalt :: Int -> Word64 -> Int
hashWithSalt = Int -> Word64 -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable () where
    hash :: () -> Int
hash = () -> Int
forall a. Enum a => a -> Int
fromEnum
    hashWithSalt :: Int -> () -> Int
hashWithSalt = Int -> () -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Bool where
    hash :: Bool -> Int
hash = Bool -> Int
forall a. Enum a => a -> Int
fromEnum
    hashWithSalt :: Int -> Bool -> Int
hashWithSalt = Int -> Bool -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Ordering where
    hash :: Ordering -> Int
hash = Ordering -> Int
forall a. Enum a => a -> Int
fromEnum
    hashWithSalt :: Int -> Ordering -> Int
hashWithSalt = Int -> Ordering -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Char where
    hash :: Char -> Int
hash = Char -> Int
forall a. Enum a => a -> Int
fromEnum
    hashWithSalt :: Int -> Char -> Int
hashWithSalt = Int -> Char -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

#if defined(MIN_VERSION_integer_gmp_1_0_0) || defined(VERSION_ghc_bignum)
instance Hashable BigNat where
    hashWithSalt :: Int -> BigNat -> Int
hashWithSalt Int
salt (BN# ByteArray#
ba) = ByteArray# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt ByteArray#
ba Int
0 Int
numBytes Int
salt
                                 Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` Int
size
      where
        size :: Int
size     = Int
numBytes Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` SIZEOF_HSWORD
        numBytes :: Int
numBytes = Int# -> Int
I# (ByteArray# -> Int#
sizeofByteArray# ByteArray#
ba)
#endif

#if MIN_VERSION_base(4,8,0)
instance Hashable Natural where
# if defined(VERSION_ghc_bignum)
    hash (NS n)   = hash (W# n)
    hash (NB bn)  = hash (BN# bn)

    hashWithSalt salt (NS n)  = hashWithSalt salt (W# n)
    hashWithSalt salt (NB bn) = hashWithSalt salt (BN# bn)
# else
# if defined(MIN_VERSION_integer_gmp_1_0_0)
    hash :: Natural -> Int
hash (NatS# GmpLimb#
n)   = Word -> Int
forall a. Hashable a => a -> Int
hash (GmpLimb# -> Word
W# GmpLimb#
n)
    hash (NatJ# BigNat
bn)  = BigNat -> Int
forall a. Hashable a => a -> Int
hash BigNat
bn

    hashWithSalt :: Int -> Natural -> Int
hashWithSalt Int
salt (NatS# GmpLimb#
n)   = Int -> Word -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (GmpLimb# -> Word
W# GmpLimb#
n)
    hashWithSalt Int
salt (NatJ# BigNat
bn)  = Int -> BigNat -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt BigNat
bn
# else
    hash (Natural n) = hash n

    hashWithSalt salt (Natural n) = hashWithSalt salt n
# endif
# endif
#endif

instance Hashable Integer where
#if defined(VERSION_ghc_bignum)
    hash (IS n)  = I# n
    hash (IP bn) = hash (BN# bn)
    hash (IN bn) = negate (hash (BN# bn))

    hashWithSalt salt (IS n)  = hashWithSalt salt (I# n)
    hashWithSalt salt (IP bn) = hashWithSalt salt (BN# bn)
    hashWithSalt salt (IN bn) = negate (hashWithSalt salt (BN# bn))
#else
#if defined(VERSION_integer_gmp)
# if defined(MIN_VERSION_integer_gmp_1_0_0)
    hash :: Integer -> Int
hash (S# Int#
n)   = (Int# -> Int
I# Int#
n)
    hash (Jp# BigNat
bn) = BigNat -> Int
forall a. Hashable a => a -> Int
hash BigNat
bn
    hash (Jn# BigNat
bn) = Int -> Int
forall a. Num a => a -> a
negate (BigNat -> Int
forall a. Hashable a => a -> Int
hash BigNat
bn)

    hashWithSalt :: Int -> Integer -> Int
hashWithSalt Int
salt (S# Int#
n)   = Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (Int# -> Int
I# Int#
n)
    hashWithSalt Int
salt (Jp# BigNat
bn) = Int -> BigNat -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt BigNat
bn
    hashWithSalt Int
salt (Jn# BigNat
bn) = Int -> Int
forall a. Num a => a -> a
negate (Int -> BigNat -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt BigNat
bn)
# else
    hash (S# int) = I# int
    hash n@(J# size# byteArray)
        | n >= minInt && n <= maxInt = fromInteger n :: Int
        | otherwise = let size = I# size#
                          numBytes = SIZEOF_HSWORD * abs size
                      in hashByteArrayWithSalt byteArray 0 numBytes defaultSalt
                         `hashWithSalt` size
      where minInt = fromIntegral (minBound :: Int)
            maxInt = fromIntegral (maxBound :: Int)

    hashWithSalt salt (S# n) = hashWithSalt salt (I# n)
    hashWithSalt salt n@(J# size# byteArray)
        | n >= minInt && n <= maxInt = hashWithSalt salt (fromInteger n :: Int)
        | otherwise = let size = I# size#
                          numBytes = SIZEOF_HSWORD * abs size
                      in hashByteArrayWithSalt byteArray 0 numBytes salt
                         `hashWithSalt` size
      where minInt = fromIntegral (minBound :: Int)
            maxInt = fromIntegral (maxBound :: Int)
# endif
#else
    hashWithSalt salt = foldl' hashWithSalt salt . go
      where
        go n | inBounds n = [fromIntegral n :: Int]
             | otherwise   = fromIntegral n : go (n `shiftR` WORD_SIZE_IN_BITS)
        maxInt = fromIntegral (maxBound :: Int)
        inBounds x = x >= fromIntegral (minBound :: Int) && x <= maxInt
#endif
#endif

instance Hashable a => Hashable (Complex a) where
    {-# SPECIALIZE instance Hashable (Complex Double) #-}
    {-# SPECIALIZE instance Hashable (Complex Float)  #-}
    hash :: Complex a -> Int
hash (a
r :+ a
i) = a -> Int
forall a. Hashable a => a -> Int
hash a
r Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a
i
    hashWithSalt :: Int -> Complex a -> Int
hashWithSalt = Int -> Complex a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1
instance Hashable1 Complex where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Complex a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s (a
r :+ a
i) = Int
s Int -> a -> Int
`h` a
r Int -> a -> Int
`h` a
i

#if MIN_VERSION_base(4,9,0)
-- Starting with base-4.9, numerator/denominator don't need 'Integral' anymore
instance Hashable a => Hashable (Ratio a) where
#else
instance (Integral a, Hashable a) => Hashable (Ratio a) where
#endif
    {-# SPECIALIZE instance Hashable (Ratio Integer) #-}
    hash :: Ratio a -> Int
hash Ratio a
a = a -> Int
forall a. Hashable a => a -> Int
hash (Ratio a -> a
forall a. Ratio a -> a
numerator Ratio a
a) Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` Ratio a -> a
forall a. Ratio a -> a
denominator Ratio a
a
    hashWithSalt :: Int -> Ratio a -> Int
hashWithSalt Int
s Ratio a
a = Int
s Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` Ratio a -> a
forall a. Ratio a -> a
numerator Ratio a
a Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` Ratio a -> a
forall a. Ratio a -> a
denominator Ratio a
a

-- | __Note__: prior to @hashable-1.3.0.0@, @hash 0.0 /= hash (-0.0)@
--
-- The 'hash' of NaN is not well defined.
--
-- @since 1.3.0.0
instance Hashable Float where
    hash :: Float -> Int
hash Float
x
        | Float
x Float -> Float -> Bool
forall a. Eq a => a -> a -> Bool
== -Float
0.0 Bool -> Bool -> Bool
|| Float
x Float -> Float -> Bool
forall a. Eq a => a -> a -> Bool
== Float
0.0 = Int
0 -- see note in 'Hashable Double'
        | Float -> Bool
forall a. RealFloat a => a -> Bool
isIEEE Float
x =
            Bool -> Int -> Int
forall a. HasCallStack => Bool -> a -> a
assert (Float -> Int
forall a. Storable a => a -> Int
sizeOf Float
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Word32 -> Int
forall a. Storable a => a -> Int
sizeOf (Word32
0::Word32) Bool -> Bool -> Bool
&&
                    Float -> Int
forall a. Storable a => a -> Int
alignment Float
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Word32 -> Int
forall a. Storable a => a -> Int
alignment (Word32
0::Word32)) (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$
            Word32 -> Int
forall a. Hashable a => a -> Int
hash ((IO Word32 -> Word32
forall a. IO a -> a
unsafeDupablePerformIO (IO Word32 -> Word32) -> IO Word32 -> Word32
forall a b. (a -> b) -> a -> b
$ Float -> (Ptr Float -> IO Word32) -> IO Word32
forall a b. Storable a => a -> (Ptr a -> IO b) -> IO b
with Float
x ((Ptr Float -> IO Word32) -> IO Word32)
-> (Ptr Float -> IO Word32) -> IO Word32
forall a b. (a -> b) -> a -> b
$ Ptr Word32 -> IO Word32
forall a. Storable a => Ptr a -> IO a
peek (Ptr Word32 -> IO Word32)
-> (Ptr Float -> Ptr Word32) -> Ptr Float -> IO Word32
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ptr Float -> Ptr Word32
forall a b. Ptr a -> Ptr b
castPtr) :: Word32)
        | Bool
otherwise = String -> Int
forall a. Hashable a => a -> Int
hash (Float -> String
forall a. Show a => a -> String
show Float
x)
    hashWithSalt :: Int -> Float -> Int
hashWithSalt = Int -> Float -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

-- | __Note__: prior to @hashable-1.3.0.0@, @hash 0.0 /= hash (-0.0)@
--
-- The 'hash' of NaN is not well defined.
--
-- @since 1.3.0.0
instance Hashable Double where
    hash :: Double -> Int
hash Double
x
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== -Double
0.0 Bool -> Bool -> Bool
|| Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
0.0 = Int
0 -- s.t. @hash -0.0 == hash 0.0@ ; see #173
        | Double -> Bool
forall a. RealFloat a => a -> Bool
isIEEE Double
x =
            Bool -> Int -> Int
forall a. HasCallStack => Bool -> a -> a
assert (Double -> Int
forall a. Storable a => a -> Int
sizeOf Double
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64 -> Int
forall a. Storable a => a -> Int
sizeOf (Word64
0::Word64) Bool -> Bool -> Bool
&&
                    Double -> Int
forall a. Storable a => a -> Int
alignment Double
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64 -> Int
forall a. Storable a => a -> Int
alignment (Word64
0::Word64)) (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$
            Word64 -> Int
forall a. Hashable a => a -> Int
hash ((IO Word64 -> Word64
forall a. IO a -> a
unsafeDupablePerformIO (IO Word64 -> Word64) -> IO Word64 -> Word64
forall a b. (a -> b) -> a -> b
$ Double -> (Ptr Double -> IO Word64) -> IO Word64
forall a b. Storable a => a -> (Ptr a -> IO b) -> IO b
with Double
x ((Ptr Double -> IO Word64) -> IO Word64)
-> (Ptr Double -> IO Word64) -> IO Word64
forall a b. (a -> b) -> a -> b
$ Ptr Word64 -> IO Word64
forall a. Storable a => Ptr a -> IO a
peek (Ptr Word64 -> IO Word64)
-> (Ptr Double -> Ptr Word64) -> Ptr Double -> IO Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ptr Double -> Ptr Word64
forall a b. Ptr a -> Ptr b
castPtr) :: Word64)
        | Bool
otherwise = String -> Int
forall a. Hashable a => a -> Int
hash (Double -> String
forall a. Show a => a -> String
show Double
x)
    hashWithSalt :: Int -> Double -> Int
hashWithSalt = Int -> Double -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

-- | A value with bit pattern (01)* (or 5* in hexa), for any size of Int.
-- It is used as data constructor distinguisher. GHC computes its value during
-- compilation.
distinguisher :: Int
distinguisher :: Int
distinguisher = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word -> Int) -> Word -> Int
forall a b. (a -> b) -> a -> b
$ (Word
forall a. Bounded a => a
maxBound :: Word) Word -> Word -> Word
forall a. Integral a => a -> a -> a
`quot` Word
3
{-# INLINE distinguisher #-}

instance Hashable a => Hashable (Maybe a) where
    hash :: Maybe a -> Int
hash Maybe a
Nothing = Int
0
    hash (Just a
a) = Int
distinguisher Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a
a
    hashWithSalt :: Int -> Maybe a -> Int
hashWithSalt = Int -> Maybe a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance Hashable1 Maybe where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Maybe a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
s Maybe a
Nothing = Int
s Int -> Int -> Int
`combine` Int
0
    liftHashWithSalt Int -> a -> Int
h Int
s (Just a
a) = Int
s Int -> Int -> Int
`combine` Int
distinguisher Int -> a -> Int
`h` a
a

instance (Hashable a, Hashable b) => Hashable (Either a b) where
    hash :: Either a b -> Int
hash (Left a
a)  = Int
0 Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a
a
    hash (Right b
b) = Int
distinguisher Int -> b -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` b
b
    hashWithSalt :: Int -> Either a b -> Int
hashWithSalt = Int -> Either a b -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance Hashable a => Hashable1 (Either a) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Either a a -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> Either a a -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance Hashable2 Either where
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> Either a b -> Int
liftHashWithSalt2 Int -> a -> Int
h Int -> b -> Int
_ Int
s (Left a
a) = Int
s Int -> Int -> Int
`combine` Int
0 Int -> a -> Int
`h` a
a
    liftHashWithSalt2 Int -> a -> Int
_ Int -> b -> Int
h Int
s (Right b
b) = Int
s Int -> Int -> Int
`combine` Int
distinguisher Int -> b -> Int
`h` b
b

instance (Hashable a1, Hashable a2) => Hashable (a1, a2) where
    hash :: (a1, a2) -> Int
hash (a1
a1, a2
a2) = a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2
    hashWithSalt :: Int -> (a1, a2) -> Int
hashWithSalt = Int -> (a1, a2) -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance Hashable a1 => Hashable1 ((,) a1) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance Hashable2 (,) where
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> (a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a
a1, b
a2) = Int
s Int -> a -> Int
`h1` a
a1 Int -> b -> Int
`h2` b
a2

instance (Hashable a1, Hashable a2, Hashable a3) => Hashable (a1, a2, a3) where
    hash :: (a1, a2, a3) -> Int
hash (a1
a1, a2
a2, a3
a3) = a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
    hashWithSalt :: Int -> (a1, a2, a3) -> Int
hashWithSalt = Int -> (a1, a2, a3) -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable a1, Hashable a2) => Hashable1 ((,,) a1 a2) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a2, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a2, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance Hashable a1 => Hashable2 ((,,) a1) where
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> (a1, a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a1
a1, a
a2, b
a3) =
      (Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1) Int -> a -> Int
`h1` a
a2 Int -> b -> Int
`h2` b
a3

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4) =>
         Hashable (a1, a2, a3, a4) where
    hash :: (a1, a2, a3, a4) -> Int
hash (a1
a1, a2
a2, a3
a3, a4
a4) = a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2
                            Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3 Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4
    hashWithSalt :: Int -> (a1, a2, a3, a4) -> Int
hashWithSalt = Int -> (a1, a2, a3, a4) -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable a1, Hashable a2, Hashable a3) => Hashable1 ((,,,) a1 a2 a3) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a2, a3, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a2, a3, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2) => Hashable2 ((,,,) a1 a2) where
    liftHashWithSalt2 :: (Int -> a -> Int)
-> (Int -> b -> Int) -> Int -> (a1, a2, a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a1
a1, a2
a2, a
a3, b
a4) =
      (Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2) Int -> a -> Int
`h1` a
a3 Int -> b -> Int
`h2` b
a4

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5)
      => Hashable (a1, a2, a3, a4, a5) where
    hash :: (a1, a2, a3, a4, a5) -> Int
hash (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5) =
        a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
        Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4 Int -> a5 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a5
a5
    hashWithSalt :: Int -> (a1, a2, a3, a4, a5) -> Int
hashWithSalt = Int -> (a1, a2, a3, a4, a5) -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable a1, Hashable a2, Hashable a3,
          Hashable a4) => Hashable1 ((,,,,) a1 a2 a3 a4) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3)
      => Hashable2 ((,,,,) a1 a2 a3) where
    liftHashWithSalt2 :: (Int -> a -> Int)
-> (Int -> b -> Int) -> Int -> (a1, a2, a3, a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a1
a1, a2
a2, a3
a3, a
a4, b
a5) =
      (Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2
         Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3) Int -> a -> Int
`h1` a
a4 Int -> b -> Int
`h2` b
a5


instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5,
          Hashable a6) => Hashable (a1, a2, a3, a4, a5, a6) where
    hash :: (a1, a2, a3, a4, a5, a6) -> Int
hash (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5, a6
a6) =
        a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
        Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4 Int -> a5 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a5
a5 Int -> a6 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a6
a6
    hashWithSalt :: Int -> (a1, a2, a3, a4, a5, a6) -> Int
hashWithSalt = Int -> (a1, a2, a3, a4, a5, a6) -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4,
          Hashable a5) => Hashable1 ((,,,,,) a1 a2 a3 a4 a5) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a5, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a5, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3,
          Hashable a4) => Hashable2 ((,,,,,) a1 a2 a3 a4) where
    liftHashWithSalt2 :: (Int -> a -> Int)
-> (Int -> b -> Int) -> Int -> (a1, a2, a3, a4, a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a1
a1, a2
a2, a3
a3, a4
a4, a
a5, b
a6) =
      (Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
         Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4) Int -> a -> Int
`h1` a
a5 Int -> b -> Int
`h2` b
a6


instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5,
          Hashable a6, Hashable a7) =>
         Hashable (a1, a2, a3, a4, a5, a6, a7) where
    hash :: (a1, a2, a3, a4, a5, a6, a7) -> Int
hash (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5, a6
a6, a7
a7) =
        a1 -> Int
forall a. Hashable a => a -> Int
hash a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
        Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4 Int -> a5 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a5
a5 Int -> a6 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a6
a6 Int -> a7 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a7
a7
    hashWithSalt :: Int -> (a1, a2, a3, a4, a5, a6, a7) -> Int
hashWithSalt Int
s (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5, a6
a6, a7
a7) =
        Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
        Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4 Int -> a5 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a5
a5 Int -> a6 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a6
a6 Int -> a7 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a7
a7

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6) => Hashable1 ((,,,,,,) a1 a2 a3 a4 a5 a6) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a5, a6, a) -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> (a1, a2, a3, a4, a5, a6, a) -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4,
          Hashable a5) => Hashable2 ((,,,,,,) a1 a2 a3 a4 a5) where
    liftHashWithSalt2 :: (Int -> a -> Int)
-> (Int -> b -> Int) -> Int -> (a1, a2, a3, a4, a5, a, b) -> Int
liftHashWithSalt2 Int -> a -> Int
h1 Int -> b -> Int
h2 Int
s (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5, a
a6, b
a7) =
      (Int
s Int -> a1 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a1
a1 Int -> a2 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a2
a2 Int -> a3 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a3
a3
         Int -> a4 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a4
a4 Int -> a5 -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a5
a5) Int -> a -> Int
`h1` a
a6 Int -> b -> Int
`h2` b
a7

instance Hashable (StableName a) where
    hash :: StableName a -> Int
hash = StableName a -> Int
forall a. StableName a -> Int
hashStableName
    hashWithSalt :: Int -> StableName a -> Int
hashWithSalt = Int -> StableName a -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

-- Auxillary type for Hashable [a] definition
data SPInt = SP !Int !Int

instance Hashable a => Hashable [a] where
    {-# SPECIALIZE instance Hashable [Char] #-}
    hashWithSalt :: Int -> [a] -> Int
hashWithSalt = Int -> [a] -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance Hashable1 [] where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> [a] -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt [a]
arr = SPInt -> Int
finalise ((SPInt -> a -> SPInt) -> SPInt -> [a] -> SPInt
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' SPInt -> a -> SPInt
step (Int -> Int -> SPInt
SP Int
salt Int
0) [a]
arr)
      where
        finalise :: SPInt -> Int
finalise (SP Int
s Int
l) = Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s Int
l
        step :: SPInt -> a -> SPInt
step (SP Int
s Int
l) a
x   = Int -> Int -> SPInt
SP (Int -> a -> Int
h Int
s a
x) (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

instance Hashable B.ByteString where
    hashWithSalt :: Int -> ByteString -> Int
hashWithSalt Int
salt ByteString
bs = IO Int -> Int
forall a. IO a -> a
unsafeDupablePerformIO (IO Int -> Int) -> IO Int -> Int
forall a b. (a -> b) -> a -> b
$
                           ByteString -> (CStringLen -> IO Int) -> IO Int
forall a. ByteString -> (CStringLen -> IO a) -> IO a
B.unsafeUseAsCStringLen ByteString
bs ((CStringLen -> IO Int) -> IO Int)
-> (CStringLen -> IO Int) -> IO Int
forall a b. (a -> b) -> a -> b
$ \(Ptr CChar
p, Int
len) ->
                           Ptr CChar -> Int -> Int -> IO Int
forall a. Ptr a -> Int -> Int -> IO Int
hashPtrWithSalt Ptr CChar
p (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len) Int
salt

instance Hashable BL.ByteString where
    hashWithSalt :: Int -> ByteString -> Int
hashWithSalt = (Int -> ByteString -> Int) -> Int -> ByteString -> Int
forall a. (a -> ByteString -> a) -> a -> ByteString -> a
BL.foldlChunks Int -> ByteString -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt

#if MIN_VERSION_bytestring(0,10,4)
instance Hashable BSI.ShortByteString where
    hashWithSalt :: Int -> ShortByteString -> Int
hashWithSalt Int
salt sbs :: ShortByteString
sbs@(BSI.SBS ByteArray#
ba) =
        ByteArray# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt ByteArray#
ba Int
0 (ShortByteString -> Int
BSI.length ShortByteString
sbs) Int
salt
#endif

instance Hashable T.Text where
    hashWithSalt :: Int -> Text -> Int
hashWithSalt Int
salt (T.Text Array
arr Int
off Int
len) =
        ByteArray# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt (Array -> ByteArray#
TA.aBA Array
arr) (Int
off Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) (Int
len Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1)
        Int
salt

instance Hashable TL.Text where
    hashWithSalt :: Int -> Text -> Int
hashWithSalt = (Int -> Text -> Int) -> Int -> Text -> Int
forall a. (a -> Text -> a) -> a -> Text -> a
TL.foldlChunks Int -> Text -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt

-- | Compute the hash of a ThreadId.
hashThreadId :: ThreadId -> Int
hashThreadId :: ThreadId -> Int
hashThreadId (ThreadId ThreadId#
t) = Int -> Int
forall a. Hashable a => a -> Int
hash (CInt -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ThreadId# -> CInt
getThreadId ThreadId#
t) :: Int)

foreign import ccall unsafe "rts_getThreadId" getThreadId
    :: ThreadId# -> CInt

instance Hashable ThreadId where
    hash :: ThreadId -> Int
hash = ThreadId -> Int
hashThreadId
    hashWithSalt :: Int -> ThreadId -> Int
hashWithSalt = Int -> ThreadId -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable (Ptr a) where
    hashWithSalt :: Int -> Ptr a -> Int
hashWithSalt Int
salt Ptr a
p = Int -> IntPtr -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (IntPtr -> Int) -> IntPtr -> Int
forall a b. (a -> b) -> a -> b
$ Ptr a -> IntPtr
forall a. Ptr a -> IntPtr
ptrToIntPtr Ptr a
p

instance Hashable (FunPtr a) where
    hashWithSalt :: Int -> FunPtr a -> Int
hashWithSalt Int
salt FunPtr a
p = Int -> Ptr Any -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (Ptr Any -> Int) -> Ptr Any -> Int
forall a b. (a -> b) -> a -> b
$ FunPtr a -> Ptr Any
forall a b. FunPtr a -> Ptr b
castFunPtrToPtr FunPtr a
p

instance Hashable IntPtr where
    hash :: IntPtr -> Int
hash IntPtr
n = IntPtr -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral IntPtr
n
    hashWithSalt :: Int -> IntPtr -> Int
hashWithSalt = Int -> IntPtr -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable WordPtr where
    hash :: WordPtr -> Int
hash WordPtr
n = WordPtr -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral WordPtr
n
    hashWithSalt :: Int -> WordPtr -> Int
hashWithSalt = Int -> WordPtr -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

----------------------------------------------------------------------------
-- Fingerprint & TypeRep instances

-- | @since 1.3.0.0
instance Hashable Fingerprint where
    hash :: Fingerprint -> Int
hash (Fingerprint Word64
x Word64
_) = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
x
    hashWithSalt :: Int -> Fingerprint -> Int
hashWithSalt = Int -> Fingerprint -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt
    {-# INLINE hash #-}

#if MIN_VERSION_base(4,10,0)

hashTypeRep :: Type.Reflection.TypeRep a -> Int
hashTypeRep :: TypeRep a -> Int
hashTypeRep TypeRep a
tr =
    let Fingerprint Word64
x Word64
_ = TypeRep a -> Fingerprint
forall k (a :: k). TypeRep a -> Fingerprint
typeRepFingerprint TypeRep a
tr in Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
x

instance Hashable Type.Reflection.SomeTypeRep where
    hash :: SomeTypeRep -> Int
hash (Type.Reflection.SomeTypeRep TypeRep a
r) = TypeRep a -> Int
forall k (a :: k). TypeRep a -> Int
hashTypeRep TypeRep a
r
    hashWithSalt :: Int -> SomeTypeRep -> Int
hashWithSalt = Int -> SomeTypeRep -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt
    {-# INLINE hash #-}

instance Hashable (Type.Reflection.TypeRep a) where
    hash :: TypeRep a -> Int
hash = TypeRep a -> Int
forall k (a :: k). TypeRep a -> Int
hashTypeRep
    hashWithSalt :: Int -> TypeRep a -> Int
hashWithSalt = Int -> TypeRep a -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt
    {-# INLINE hash #-}

#else

-- | Compute the hash of a TypeRep, in various GHC versions we can do this quickly.
hashTypeRep :: TypeRep -> Int
{-# INLINE hashTypeRep #-}
#if   MIN_VERSION_base(4,8,0)
-- Fingerprint is just the MD5, so taking any Int from it is fine
hashTypeRep tr = let Fingerprint x _ = typeRepFingerprint tr in fromIntegral x
#else
-- Fingerprint is just the MD5, so taking any Int from it is fine
hashTypeRep (TypeRep (Fingerprint x _) _ _) = fromIntegral x
#endif

instance Hashable TypeRep where
    hash = hashTypeRep
    hashWithSalt = defaultHashWithSalt
    {-# INLINE hash #-}

#endif

----------------------------------------------------------------------------

#if MIN_VERSION_base(4,8,0)
instance Hashable Void where
    hashWithSalt :: Int -> Void -> Int
hashWithSalt Int
_ = Void -> Int
forall a. Void -> a
absurd
#endif

-- | Compute a hash value for the content of this pointer.
hashPtr :: Ptr a      -- ^ pointer to the data to hash
        -> Int        -- ^ length, in bytes
        -> IO Int     -- ^ hash value
hashPtr :: Ptr a -> Int -> IO Int
hashPtr Ptr a
p Int
len = Ptr a -> Int -> Int -> IO Int
forall a. Ptr a -> Int -> Int -> IO Int
hashPtrWithSalt Ptr a
p Int
len Int
defaultSalt

-- | Compute a hash value for the content of this pointer, using an
-- initial salt.
--
-- This function can for example be used to hash non-contiguous
-- segments of memory as if they were one contiguous segment, by using
-- the output of one hash as the salt for the next.
hashPtrWithSalt :: Ptr a   -- ^ pointer to the data to hash
                -> Int     -- ^ length, in bytes
                -> Int     -- ^ salt
                -> IO Int  -- ^ hash value
hashPtrWithSalt :: Ptr a -> Int -> Int -> IO Int
hashPtrWithSalt Ptr a
p Int
len Int
salt =
    CLong -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (CLong -> Int) -> IO CLong -> IO Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` Ptr CChar -> CLong -> CLong -> IO CLong
c_hashCString (Ptr a -> Ptr CChar
forall a b. Ptr a -> Ptr b
castPtr Ptr a
p) (Int -> CLong
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len)
    (Int -> CLong
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
salt)

foreign import ccall unsafe "hashable_fnv_hash" c_hashCString
    :: CString -> CLong -> CLong -> IO CLong

-- | Compute a hash value for the content of this 'ByteArray#',
-- beginning at the specified offset, using specified number of bytes.
hashByteArray :: ByteArray#  -- ^ data to hash
              -> Int         -- ^ offset, in bytes
              -> Int         -- ^ length, in bytes
              -> Int         -- ^ hash value
hashByteArray :: ByteArray# -> Int -> Int -> Int
hashByteArray ByteArray#
ba0 Int
off Int
len = ByteArray# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt ByteArray#
ba0 Int
off Int
len Int
defaultSalt
{-# INLINE hashByteArray #-}

-- | Compute a hash value for the content of this 'ByteArray#', using
-- an initial salt.
--
-- This function can for example be used to hash non-contiguous
-- segments of memory as if they were one contiguous segment, by using
-- the output of one hash as the salt for the next.
hashByteArrayWithSalt
    :: ByteArray#  -- ^ data to hash
    -> Int         -- ^ offset, in bytes
    -> Int         -- ^ length, in bytes
    -> Int         -- ^ salt
    -> Int         -- ^ hash value
hashByteArrayWithSalt :: ByteArray# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt ByteArray#
ba !Int
off !Int
len !Int
h =
    CLong -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (CLong -> Int) -> CLong -> Int
forall a b. (a -> b) -> a -> b
$ ByteArray# -> CLong -> CLong -> CLong -> CLong
c_hashByteArray ByteArray#
ba (Int -> CLong
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
off) (Int -> CLong
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len)
    (Int -> CLong
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
h)

foreign import ccall unsafe "hashable_fnv_hash_offset" c_hashByteArray
    :: ByteArray# -> CLong -> CLong -> CLong -> CLong

-- | Combine two given hash values.  'combine' has zero as a left
-- identity.
combine :: Int -> Int -> Int
combine :: Int -> Int -> Int
combine Int
h1 Int
h2 = (Int
h1 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
16777619) Int -> Int -> Int
forall a. Bits a => a -> a -> a
`xor` Int
h2

instance Hashable Unique where
    hash :: Unique -> Int
hash = Unique -> Int
hashUnique
    hashWithSalt :: Int -> Unique -> Int
hashWithSalt = Int -> Unique -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt

instance Hashable Version where
    hashWithSalt :: Int -> Version -> Int
hashWithSalt Int
salt (Version [Int]
branch [String]
tags) =
        Int
salt Int -> [Int] -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` [Int]
branch Int -> [String] -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` [String]
tags

#if MIN_VERSION_base(4,7,0)
-- Using hashWithSalt1 would cause needless constraint
instance Hashable (Fixed a) where
    hashWithSalt :: Int -> Fixed a -> Int
hashWithSalt Int
salt (MkFixed Integer
i) = Int -> Integer -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Integer
i
instance Hashable1 Fixed where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Fixed a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
salt (MkFixed Integer
i) = Int -> Integer -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Integer
i
#endif

#if MIN_VERSION_base(4,8,0)
instance Hashable a => Hashable (Identity a) where
    hashWithSalt :: Int -> Identity a -> Int
hashWithSalt = Int -> Identity a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1
instance Hashable1 Identity where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Identity a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (Identity a
x) = Int -> a -> Int
h Int
salt a
x
#endif

-- Using hashWithSalt1 would cause needless constraint
instance Hashable a => Hashable (Const a b) where
    hashWithSalt :: Int -> Const a b -> Int
hashWithSalt Int
salt (Const a
x) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt a
x

instance Hashable a => Hashable1 (Const a) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Const a a -> Int
liftHashWithSalt = (Int -> a -> Int) -> Int -> Const a a -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(Int -> b -> Int) -> Int -> f a b -> Int
defaultLiftHashWithSalt

instance Hashable2 Const where
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> Const a b -> Int
liftHashWithSalt2 Int -> a -> Int
f Int -> b -> Int
_ Int
salt (Const a
x) = Int -> a -> Int
f Int
salt a
x

#if MIN_VERSION_base(4,7,0)
instance Hashable (Proxy a) where
    hash :: Proxy a -> Int
hash Proxy a
_ = Int
0
    hashWithSalt :: Int -> Proxy a -> Int
hashWithSalt Int
s Proxy a
_ = Int
s

instance Hashable1 Proxy where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Proxy a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
s Proxy a
_ = Int
s
#endif

-- instances formerly provided by 'semigroups' package
#if MIN_VERSION_base(4,9,0)
instance Hashable a => Hashable (NE.NonEmpty a) where
    hashWithSalt :: Int -> NonEmpty a -> Int
hashWithSalt Int
p (a
a NE.:| [a]
as) = Int
p Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` a
a Int -> [a] -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` [a]
as

-- | @since 1.3.1.0
instance Hashable1 NE.NonEmpty where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> NonEmpty a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (a
a NE.:| [a]
as) = (Int -> a -> Int) -> Int -> [a] -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h (Int -> a -> Int
h Int
salt a
a) [a]
as

instance Hashable a => Hashable (Min a) where
    hashWithSalt :: Int -> Min a -> Int
hashWithSalt Int
p (Min a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

-- | @since 1.3.1.0
instance Hashable1 Min where liftHashWithSalt :: (Int -> a -> Int) -> Int -> Min a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (Min a
a) = Int -> a -> Int
h Int
salt a
a

instance Hashable a => Hashable (Max a) where
    hashWithSalt :: Int -> Max a -> Int
hashWithSalt Int
p (Max a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

-- | @since 1.3.1.0
instance Hashable1 Max where liftHashWithSalt :: (Int -> a -> Int) -> Int -> Max a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (Max a
a) = Int -> a -> Int
h Int
salt a
a

-- | __Note__: Prior to @hashable-1.3.0.0@ the hash computation included the second argument of 'Arg' which wasn't consistent with its 'Eq' instance.
--
-- @since 1.3.0.0
instance Hashable a => Hashable (Arg a b) where
    hashWithSalt :: Int -> Arg a b -> Int
hashWithSalt Int
p (Arg a
a b
_) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

instance Hashable a => Hashable (First a) where
    hashWithSalt :: Int -> First a -> Int
hashWithSalt Int
p (First a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

-- | @since 1.3.1.0
instance Hashable1 First where liftHashWithSalt :: (Int -> a -> Int) -> Int -> First a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (First a
a) = Int -> a -> Int
h Int
salt a
a

instance Hashable a => Hashable (Last a) where
    hashWithSalt :: Int -> Last a -> Int
hashWithSalt Int
p (Last a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

-- | @since 1.3.1.0
instance Hashable1 Last where liftHashWithSalt :: (Int -> a -> Int) -> Int -> Last a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (Last a
a) = Int -> a -> Int
h Int
salt a
a

instance Hashable a => Hashable (WrappedMonoid a) where
    hashWithSalt :: Int -> WrappedMonoid a -> Int
hashWithSalt Int
p (WrapMonoid a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

-- | @since 1.3.1.0
instance Hashable1 WrappedMonoid where liftHashWithSalt :: (Int -> a -> Int) -> Int -> WrappedMonoid a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (WrapMonoid a
a) = Int -> a -> Int
h Int
salt a
a

instance Hashable a => Hashable (Option a) where
    hashWithSalt :: Int -> Option a -> Int
hashWithSalt Int
p (Option Maybe a
a) = Int -> Maybe a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p Maybe a
a

-- | @since 1.3.1.0
instance Hashable1 Option where liftHashWithSalt :: (Int -> a -> Int) -> Int -> Option a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt (Option Maybe a
a) = (Int -> a -> Int) -> Int -> Maybe a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h Int
salt Maybe a
a
#endif

-- instances for @Data.Functor.{Product,Sum,Compose}@, present
-- in base-4.9 and onward.
#if MIN_VERSION_base(4,9,0)
-- | In general, @hash (Compose x) ≠ hash x@. However, @hashWithSalt@ satisfies
-- its variant of this equivalence.
instance (Hashable1 f, Hashable1 g, Hashable a) => Hashable (Compose f g a) where
    hashWithSalt :: Int -> Compose f g a -> Int
hashWithSalt = Int -> Compose f g a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable1 f, Hashable1 g) => Hashable1 (Compose f g) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Compose f g a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s = (Int -> g a -> Int) -> Int -> f (g a) -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt ((Int -> a -> Int) -> Int -> g a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h) Int
s (f (g a) -> Int)
-> (Compose f g a -> f (g a)) -> Compose f g a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compose f g a -> f (g a)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose

instance (Hashable1 f, Hashable1 g) => Hashable1 (FP.Product f g) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Product f g a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s (FP.Pair f a
a g a
b) = (Int -> a -> Int) -> Int -> g a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h ((Int -> a -> Int) -> Int -> f a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s f a
a) g a
b

instance (Hashable1 f, Hashable1 g, Hashable a) => Hashable (FP.Product f g a) where
    hashWithSalt :: Int -> Product f g a -> Int
hashWithSalt = Int -> Product f g a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

instance (Hashable1 f, Hashable1 g) => Hashable1 (FS.Sum f g) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> Sum f g a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s (FS.InL f a
a) = (Int -> a -> Int) -> Int -> f a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h (Int
s Int -> Int -> Int
`combine` Int
0) f a
a
    liftHashWithSalt Int -> a -> Int
h Int
s (FS.InR g a
a) = (Int -> a -> Int) -> Int -> g a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> a -> Int
h (Int
s Int -> Int -> Int
`combine` Int
distinguisher) g a
a

instance (Hashable1 f, Hashable1 g, Hashable a) => Hashable (FS.Sum f g a) where
    hashWithSalt :: Int -> Sum f g a -> Int
hashWithSalt = Int -> Sum f g a -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1
#endif

-- | A hashable value along with the result of the 'hash' function.
data Hashed a = Hashed a {-# UNPACK #-} !Int
  deriving (Typeable)

-- | Wrap a hashable value, caching the 'hash' function result.
hashed :: Hashable a => a -> Hashed a
hashed :: a -> Hashed a
hashed a
a = a -> Int -> Hashed a
forall a. a -> Int -> Hashed a
Hashed a
a (a -> Int
forall a. Hashable a => a -> Int
hash a
a)

-- | Unwrap hashed value.
unhashed :: Hashed a -> a
unhashed :: Hashed a -> a
unhashed (Hashed a
a Int
_) = a
a

-- | Uses precomputed hash to detect inequality faster
instance Eq a => Eq (Hashed a) where
  Hashed a
a Int
ha == :: Hashed a -> Hashed a -> Bool
== Hashed a
b Int
hb = Int
ha Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hb Bool -> Bool -> Bool
&& a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b

instance Ord a => Ord (Hashed a) where
  Hashed a
a Int
_ compare :: Hashed a -> Hashed a -> Ordering
`compare` Hashed a
b Int
_ = a
a a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` a
b

instance Show a => Show (Hashed a) where
  showsPrec :: Int -> Hashed a -> ShowS
showsPrec Int
d (Hashed a
a Int
_) = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"hashed" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' ' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 a
a

instance Hashable (Hashed a) where
  hashWithSalt :: Int -> Hashed a -> Int
hashWithSalt = Int -> Hashed a -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt
  hash :: Hashed a -> Int
hash (Hashed a
_ Int
h) = Int
h

-- This instance is a little unsettling. It is unusal for
-- 'liftHashWithSalt' to ignore its first argument when a
-- value is actually available for it to work on.
instance Hashable1 Hashed where
  liftHashWithSalt :: (Int -> a -> Int) -> Int -> Hashed a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
s (Hashed a
_ Int
h) = Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt Int
s Int
h

instance (IsString a, Hashable a) => IsString (Hashed a) where
  fromString :: String -> Hashed a
fromString String
s = let r :: a
r = String -> a
forall a. IsString a => String -> a
fromString String
s in a -> Int -> Hashed a
forall a. a -> Int -> Hashed a
Hashed a
r (a -> Int
forall a. Hashable a => a -> Int
hash a
r)

instance F.Foldable Hashed where
  foldr :: (a -> b -> b) -> b -> Hashed a -> b
foldr a -> b -> b
f b
acc (Hashed a
a Int
_) = a -> b -> b
f a
a b
acc

instance NFData a => NFData (Hashed a) where
  rnf :: Hashed a -> ()
rnf = a -> ()
forall a. NFData a => a -> ()
rnf (a -> ()) -> (Hashed a -> a) -> Hashed a -> ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Hashed a -> a
forall a. Hashed a -> a
unhashed

-- | 'Hashed' cannot be 'Functor'
mapHashed :: Hashable b => (a -> b) -> Hashed a -> Hashed b
mapHashed :: (a -> b) -> Hashed a -> Hashed b
mapHashed a -> b
f (Hashed a
a Int
_) = b -> Hashed b
forall a. Hashable a => a -> Hashed a
hashed (a -> b
f a
a)

-- | 'Hashed' cannot be 'Traversable'
traverseHashed :: (Hashable b, Functor f) => (a -> f b) -> Hashed a -> f (Hashed b)
traverseHashed :: (a -> f b) -> Hashed a -> f (Hashed b)
traverseHashed a -> f b
f (Hashed a
a Int
_) = (b -> Hashed b) -> f b -> f (Hashed b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap b -> Hashed b
forall a. Hashable a => a -> Hashed a
hashed (a -> f b
f a
a)

-- instances for @Data.Functor.Classes@ higher rank typeclasses
-- in base-4.9 and onward.
#if MIN_VERSION_base(4,9,0)
instance Eq1 Hashed where
  liftEq :: (a -> b -> Bool) -> Hashed a -> Hashed b -> Bool
liftEq a -> b -> Bool
f (Hashed a
a Int
ha) (Hashed b
b Int
hb) = Int
ha Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hb Bool -> Bool -> Bool
&& a -> b -> Bool
f a
a b
b

instance Ord1 Hashed where
  liftCompare :: (a -> b -> Ordering) -> Hashed a -> Hashed b -> Ordering
liftCompare a -> b -> Ordering
f (Hashed a
a Int
_) (Hashed b
b Int
_) = a -> b -> Ordering
f a
a b
b

instance Show1 Hashed where
  liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Hashed a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
_ Int
d (Hashed a
a Int
_) = (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith Int -> a -> ShowS
sp String
"hashed" Int
d a
a
#endif