{-# LANGUAGE CApiFFI               #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DefaultSignatures     #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE MagicHash             #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE PolyKinds             #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE Trustworthy           #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE UnliftedFFITypes      #-}

{-# 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
    , hashedHash
    , unhashed
    , mapHashed
    , traverseHashed
    ) where

import Control.Applicative    (Const (..))
import Control.DeepSeq        (NFData (rnf))
import Control.Exception      (assert)
import Data.Complex           (Complex (..))
import Data.Fixed             (Fixed (..))
import Data.Functor.Classes   (Eq1 (..), Eq2 (..), Ord1 (..), Show1 (..))
import Data.Functor.Compose   (Compose (..))
import Data.Functor.Identity  (Identity (..))
import Data.Int               (Int16, Int8)
import Data.Kind              (Type)
import Data.List              (foldl')
import Data.Proxy             (Proxy)
import Data.Ratio             (Ratio, denominator, numerator)
import Data.String            (IsString (..))
import Data.Unique            (Unique, hashUnique)
import Data.Version           (Version (..))
import Data.Void              (Void, absurd)
import Data.Word              (Word16, Word8)
import Foreign.Ptr            (FunPtr, IntPtr, Ptr, WordPtr, castFunPtrToPtr, ptrToIntPtr)
import Foreign.Storable       (alignment, sizeOf)
import GHC.Base               (ByteArray#)
import GHC.Conc               (ThreadId (..))
import GHC.Fingerprint.Type   (Fingerprint (..))
import GHC.Prim               (ThreadId#)
import GHC.Word               (Word (..))
import System.IO.Unsafe       (unsafeDupablePerformIO)
import System.Mem.StableName  (StableName, hashStableName)
import Type.Reflection        (SomeTypeRep (..), TypeRep)
import Type.Reflection.Unsafe (typeRepFingerprint)

import qualified Data.Array.Byte                as AB
import qualified Data.ByteString                as B
import qualified Data.ByteString.Lazy           as BL
import qualified Data.ByteString.Short.Internal as BSI
import qualified Data.ByteString.Unsafe         as B
import qualified Data.Functor.Product           as FP
import qualified Data.Functor.Sum               as FS
import qualified Data.IntMap                    as IntMap
import qualified Data.IntSet                    as IntSet
import qualified Data.List.NonEmpty             as NE
import qualified Data.Map                       as Map
import qualified Data.Semigroup                 as Semi
import qualified Data.Sequence                  as Seq
import qualified Data.Set                       as Set
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 qualified Data.Tree                      as Tree

import GHC.Generics

#if __GLASGOW_HASKELL__ >= 904
import Foreign.C.Types (CULLong (..))
#elif __GLASGOW_HASKELL__ >= 900
import Foreign.C.Types (CLong (..))
#else
import Foreign.C.Types (CInt (..))
#endif

#ifdef VERSION_ghc_bignum
import GHC.Exts        (Int (..), sizeofByteArray#)
import GHC.Num.BigNat  (BigNat (..))
import GHC.Num.Integer (Integer (..))
import GHC.Num.Natural (Natural (..))
#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

#ifndef VERSION_ghc_bignum
import GHC.Natural (Natural (..))
#endif

#if MIN_VERSION_base(4,11,0)
import GHC.Float (castDoubleToWord64, castFloatToWord32)
#else
import Foreign.Marshal.Utils (with)
import Foreign.Ptr           (castPtr)
import Foreign.Storable      (peek)
#endif

#if MIN_VERSION_base(4,16,0)
import Data.Tuple (Solo (..))
#elif MIN_VERSION_base(4,15,0)
import GHC.Tuple (Solo (..))
#endif

#if MIN_VERSION_filepath(1,4,100)
import System.OsString.Internal.Types (OsString (..), PosixString (..), WindowsString (..))
#endif

#ifdef VERSION_base_orphans
import Data.Orphans ()
#endif

#ifdef VERSION_ghc_bignum_orphans
import GHC.Num.Orphans ()
#endif

import Data.Hashable.Imports
import Data.Hashable.LowLevel

#include "MachDeps.h"

infixl 0 `hashWithSalt`

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

-- | The class of types that can be converted to a hash value.
--
-- Minimal implementation: 'hashWithSalt'.
--
-- /Note:/ the hash is not guaranteed to be stable across
-- library versions, operating systems or architectures.
-- For stable hashing use named hashes: SHA256, CRC32 etc.
--
-- If you are looking for 'Hashable' instance in @time@ package,
-- check [time-compat](https://hackage.haskell.org/package/time-compat)
--
class Eq a => 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' may return negative 'Int' values.
    --
    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 :: forall a. (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int
genericHashWithSalt = \Int
salt -> HashArgs Zero Any -> Int -> Rep a Any -> Int
forall a. HashArgs Zero a -> Int -> Rep a a -> 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 x. a -> Rep a x
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 Eq1 t => 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 :: forall (t :: * -> *) a.
(Generic1 t, GHashable One (Rep1 t)) =>
(Int -> a -> Int) -> Int -> t a -> Int
genericLiftHashWithSalt = \Int -> a -> Int
h Int
salt -> HashArgs One a -> Int -> Rep1 t a -> Int
forall a. 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 a. t a -> Rep1 t a
forall k (f :: k -> *) (a :: k). Generic1 f => f a -> Rep1 f a
from1
{-# INLINE genericLiftHashWithSalt #-}

class Eq2 t => 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 :: forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1 = (Int -> a -> Int) -> Int -> f a -> Int
forall a. (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 :: forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a, Hashable b) =>
Int -> f a b -> Int
hashWithSalt2 = (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> f a b -> Int
forall a b.
(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 :: forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a) =>
(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 a b.
(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 :: forall a. Hashable a => Int -> a -> Int
defaultHashWithSalt Int
salt a
x = Int
salt Int -> Int -> Int
`hashInt` 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
--
-- @since 1.2.0.0
hashUsing :: (Hashable b) =>
             (a -> b)           -- ^ Transformation function.
          -> Int                -- ^ Salt.
          -> a                  -- ^ Value to transform.
          -> Int
hashUsing :: forall b a. Hashable b => (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
hashInt

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 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    hashWithSalt :: Int -> Int64 -> Int
hashWithSalt = Int -> Int64 -> Int
hashInt64

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
    hashWithSalt :: Int -> Word64 -> Int
hashWithSalt = Int -> Word64 -> Int
hashWord64

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# BigNat#
ba) = BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
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# (BigNat# -> Int#
sizeofByteArray# BigNat#
ba)
#endif

instance Hashable Natural where
#if defined(VERSION_ghc_bignum)
    hash :: Natural -> Int
hash (NS Word#
n)   = Word -> Int
forall a. Hashable a => a -> Int
hash (Word# -> Word
W# Word#
n)
    hash (NB BigNat#
bn)  = BigNat -> Int
forall a. Hashable a => a -> Int
hash (BigNat# -> BigNat
BN# BigNat#
bn)

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

    hashWithSalt salt (NatS# n)   = hashWithSalt salt (W# n)
    hashWithSalt salt (NatJ# bn)  = hashWithSalt salt bn
#else
    hash (Natural n) = hash n

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

instance Hashable Integer where
#if defined(VERSION_ghc_bignum)
    hash :: Integer -> Int
hash (IS Int#
n)  = Int# -> Int
I# Int#
n
    hash (IP BigNat#
bn) = BigNat -> Int
forall a. Hashable a => a -> Int
hash (BigNat# -> BigNat
BN# BigNat#
bn)
    hash (IN BigNat#
bn) = Int -> Int
forall a. Num a => a -> a
negate (BigNat -> Int
forall a. Hashable a => a -> Int
hash (BigNat# -> BigNat
BN# BigNat#
bn))

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

    hashWithSalt salt (S# n)   = hashWithSalt salt (I# n)
    hashWithSalt salt (Jp# bn) = hashWithSalt salt bn
    hashWithSalt salt (Jn# bn) = negate (hashWithSalt salt 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 :: forall a. (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

instance Hashable a => Hashable (Ratio a) where
    {-# 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. (?callStack::CallStack) => 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
$
#if MIN_VERSION_base(4,11,0)
            Word32 -> Int
forall a. Hashable a => a -> Int
hash (Float -> Word32
castFloatToWord32 Float
x)
#else
            hash ((unsafeDupablePerformIO $ with x $ peek . castPtr) :: Word32)
#endif
        | 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. (?callStack::CallStack) => 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
$
#if MIN_VERSION_base(4,11,0)
            Word64 -> Int
forall a. Hashable a => a -> Int
hash (Double -> Word64
castDoubleToWord64 Double
x)
#else
            hash ((unsafeDupablePerformIO $ with x $ peek . castPtr) :: Word64)
#endif
        | 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 :: forall a. (Int -> a -> Int) -> Int -> Maybe a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
s Maybe a
Nothing = Int
s Int -> Int -> Int
`hashInt` Int
0
    liftHashWithSalt Int -> a -> Int
h Int
s (Just a
a) = Int
s Int -> Int -> Int
`hashInt` 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 :: forall a. (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 :: forall a b.
(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
`hashInt` 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
`hashInt` 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 :: forall a. (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 :: forall a b.
(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 :: forall a. (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 :: forall a b.
(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 :: forall a. (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 :: forall a b.
(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
s (a1
a1, a2
a2, a3
a3, a4
a4, a5
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 -> 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

{-
instance (Hashable a1, Hashable a2, Hashable a3,
          Hashable a4) => Hashable1 ((,,,,) a1 a2 a3 a4) where
    liftHashWithSalt = defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3)
      => Hashable2 ((,,,,) a1 a2 a3) where
    liftHashWithSalt2 h1 h2 s (a1, a2, a3, a4, a5) =
      (s `hashWithSalt` a1 `hashWithSalt` a2
         `hashWithSalt` a3) `h1` a4 `h2` 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
s (a1
a1, a2
a2, a3
a3, a4
a4, a5
a5, a6
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 -> 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

{-
instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4,
          Hashable a5) => Hashable1 ((,,,,,) a1 a2 a3 a4 a5) where
    liftHashWithSalt = defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3,
          Hashable a4) => Hashable2 ((,,,,,) a1 a2 a3 a4) where
    liftHashWithSalt2 h1 h2 s (a1, a2, a3, a4, a5, a6) =
      (s `hashWithSalt` a1 `hashWithSalt` a2 `hashWithSalt` a3
         `hashWithSalt` a4) `h1` a5 `h2` 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 = defaultLiftHashWithSalt

instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4,
          Hashable a5) => Hashable2 ((,,,,,,) a1 a2 a3 a4 a5) where
    liftHashWithSalt2 h1 h2 s (a1, a2, a3, a4, a5, a6, a7) =
      (s `hashWithSalt` a1 `hashWithSalt` a2 `hashWithSalt` a3
         `hashWithSalt` a4 `hashWithSalt` a5) `h1` a6 `h2` 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

-- Auxiliary 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 :: forall a. (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 b a. (b -> a -> b) -> b -> [a] -> b
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 -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Int
len)

instance Hashable BL.ByteString where
    hashWithSalt :: Int -> ByteString -> Int
hashWithSalt Int
salt = SPInt -> Int
finalise (SPInt -> Int) -> (ByteString -> SPInt) -> ByteString -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (SPInt -> ByteString -> SPInt) -> SPInt -> ByteString -> SPInt
forall a. (a -> ByteString -> a) -> a -> ByteString -> a
BL.foldlChunks SPInt -> ByteString -> SPInt
step (Int -> Int -> SPInt
SP Int
salt Int
0)
      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 -> ByteString -> SPInt
step (SP Int
s Int
l) ByteString
bs  = IO SPInt -> SPInt
forall a. IO a -> a
unsafeDupablePerformIO (IO SPInt -> SPInt) -> IO SPInt -> SPInt
forall a b. (a -> b) -> a -> b
$
                            ByteString -> (CStringLen -> IO SPInt) -> IO SPInt
forall a. ByteString -> (CStringLen -> IO a) -> IO a
B.unsafeUseAsCStringLen ByteString
bs ((CStringLen -> IO SPInt) -> IO SPInt)
-> (CStringLen -> IO SPInt) -> IO SPInt
forall a b. (a -> b) -> a -> b
$ \(Ptr CChar
p, Int
len) -> do
                                Int
s' <- 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
s
                                SPInt -> IO SPInt
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> SPInt
SP Int
s' (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
len))

instance Hashable BSI.ShortByteString where
    hashWithSalt :: Int -> ShortByteString -> Int
hashWithSalt Int
salt sbs :: ShortByteString
sbs@(BSI.SBS BigNat#
ba) =
        BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
ba Int
0 (ShortByteString -> Int
BSI.length ShortByteString
sbs) (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (ShortByteString -> Int
BSI.length ShortByteString
sbs))

#if MIN_VERSION_filepath(1,4,100)
-- | @since 1.4.2.0
instance Hashable PosixString where
    hashWithSalt :: Int -> PosixString -> Int
hashWithSalt Int
salt (PosixString ShortByteString
s) = Int -> ShortByteString -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt ShortByteString
s

-- | @since 1.4.2.0
instance Hashable WindowsString where
    hashWithSalt :: Int -> WindowsString -> Int
hashWithSalt Int
salt (WindowsString ShortByteString
s) = Int -> ShortByteString -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt ShortByteString
s

-- | @since 1.4.2.0
instance Hashable OsString where
    hashWithSalt :: Int -> OsString -> Int
hashWithSalt Int
salt (OsString PosixString
s) = Int -> PosixString -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt PosixString
s
#endif

#if MIN_VERSION_text(2,0,0)

instance Hashable T.Text where
    hashWithSalt :: Int -> Text -> Int
hashWithSalt Int
salt (T.Text (TA.ByteArray BigNat#
arr) Int
off Int
len) =
        BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
arr Int
off Int
len (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Int
len)

instance Hashable TL.Text where
    hashWithSalt :: Int -> Text -> Int
hashWithSalt Int
salt = SPInt -> Int
finalise (SPInt -> Int) -> (Text -> SPInt) -> Text -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (SPInt -> Text -> SPInt) -> SPInt -> Text -> SPInt
forall a. (a -> Text -> a) -> a -> Text -> a
TL.foldlChunks SPInt -> Text -> SPInt
step (Int -> Int -> SPInt
SP Int
salt Int
0)
      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 -> Text -> SPInt
step (SP Int
s Int
l) (T.Text (TA.ByteArray BigNat#
arr) Int
off Int
len) = Int -> Int -> SPInt
SP
            (BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
arr Int
off Int
len Int
s)
            (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
len)

#else

instance Hashable T.Text where
    hashWithSalt salt (T.Text arr off len) =
        hashByteArrayWithSalt (TA.aBA arr) (off `shiftL` 1) (len `shiftL` 1)
        (hashWithSalt salt len)

instance Hashable TL.Text where
    hashWithSalt salt = finalise . TL.foldlChunks step (SP salt 0)
      where
        finalise (SP s l) = hashWithSalt s l
        step (SP s l) (T.Text arr off len) = SP
            (hashByteArrayWithSalt (TA.aBA arr) (off `shiftL` 1) (len `shiftL` 1) s)
            (l + len)

#endif

-- | 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 (CULLong -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ThreadId# -> CULLong
getThreadId ThreadId#
t) :: Int)

-- this cannot be capi, as GHC panics.
foreign import ccall unsafe "rts_getThreadId" getThreadId
#if __GLASGOW_HASKELL__ >= 904
    -- https://gitlab.haskell.org/ghc/ghc/-/merge_requests/6163
    :: ThreadId# -> CULLong
#elif __GLASGOW_HASKELL__ >= 900
    -- https://gitlab.haskell.org/ghc/ghc/-/merge_requests/1254
    :: ThreadId# -> CLong
#else
    :: ThreadId# -> CInt
#endif

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

hashTypeRep :: Type.Reflection.TypeRep a -> Int
hashTypeRep :: forall {k} (a :: k). 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 #-}

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

instance Hashable Void where
    hashWithSalt :: Int -> Void -> Int
hashWithSalt Int
_ = Void -> Int
forall a. Void -> a
absurd

-- | 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 :: forall a. 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 '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 :: BigNat# -> Int -> Int -> Int
hashByteArray BigNat#
ba0 Int
off Int
len = BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
ba0 Int
off Int
len Int
defaultSalt
{-# INLINE hashByteArray #-}

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

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 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 :: forall a. (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

-- 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 :: forall a. (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 :: forall a b.
(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

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 :: forall a. (Int -> a -> Int) -> Int -> Proxy a -> Int
liftHashWithSalt Int -> a -> Int
_ Int
s Proxy a
_ = Int
s

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 :: forall a. (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 a. (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 (Semi.Min a) where
    hashWithSalt :: Int -> Min a -> Int
hashWithSalt Int
p (Semi.Min a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

instance Hashable a => Hashable (Semi.Max a) where
    hashWithSalt :: Int -> Max a -> Int
hashWithSalt Int
p (Semi.Max a
a) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p 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 (Semi.Arg a b) where
    hashWithSalt :: Int -> Arg a b -> Int
hashWithSalt Int
p (Semi.Arg a
a b
_) = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
p a
a

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


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


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


#if !MIN_VERSION_base(4,16,0)
instance Hashable a => Hashable (Semi.Option a) where
    hashWithSalt p (Semi.Option a) = hashWithSalt p a

#endif

-- TODO: this instance is removed as there isn't Eq1 Min/Max, ...

#if 0
-- | @since 1.3.1.0
-- instance Hashable1 Min where liftHashWithSalt h salt (Min a) = h salt a

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

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

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


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

-- | @since 1.3.1.0
-- instance Hashable1 Option where liftHashWithSalt h salt (Option a) = liftHashWithSalt h salt a
#endif

-- | 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 :: forall a. (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 a. (Int -> a -> Int) -> Int -> f a -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt ((Int -> a -> Int) -> Int -> g a -> Int
forall 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 (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} {k2} (f :: k1 -> *) (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 :: forall a. (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 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 -> a -> Int) -> Int -> f a -> Int
forall 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 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 :: forall a. (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 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
`hashInt` 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 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
`hashInt` 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

-- | This instance was available since 1.4.1.0 only for GHC-9.4+
--
-- @since 1.4.2.0
--
instance Hashable AB.ByteArray where
    hashWithSalt :: Int -> ByteArray -> Int
hashWithSalt Int
salt (AB.ByteArray BigNat#
ba) =
        BigNat# -> Int -> Int -> Int -> Int
hashByteArrayWithSalt BigNat#
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# (BigNat# -> Int#
sizeofByteArray# BigNat#
ba)

-------------------------------------------------------------------------------
-- Hashed
-------------------------------------------------------------------------------

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

-- | Wrap a hashable value, caching the 'hash' function result.
hashed :: Hashable a => a -> Hashed a
hashed :: forall a. Hashable a => 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 :: forall a. Hashed a -> a
unhashed (Hashed a
a Int
_) = a
a

-- | 'hash' has 'Eq' requirement.
--
-- @since 1.4.0.0
hashedHash :: Hashed a -> Int
hashedHash :: forall a. Hashed a -> Int
hashedHash (Hashed a
_ Int
h) = Int
h

-- | 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 Eq a => 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
forall a. Hashed a -> Int
hashedHash


-- 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 :: forall a. (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 Foldable Hashed where
  foldMap :: forall m a. Monoid m => (a -> m) -> Hashed a -> m
foldMap a -> m
f (Hashed a
a Int
_) = a -> m
f a
a
  foldr :: forall a b. (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 :: forall b a. Hashable b => (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 :: forall b (f :: * -> *) a.
(Hashable b, Functor f) =>
(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 a b. (a -> b) -> f a -> f 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.
instance Eq1 Hashed where
  liftEq :: forall a b. (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 :: forall a b.
(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 :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Hashed a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
_ 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
. Int -> a -> ShowS
sp Int
11 a
a

-------------------------------------------------------------------------------
-- containers
-------------------------------------------------------------------------------

-- | @since 1.3.4.0
instance Hashable2 Map.Map where
    liftHashWithSalt2 :: forall a b.
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> Map a b -> Int
liftHashWithSalt2 Int -> a -> Int
hk Int -> b -> Int
hv Int
s Map a b
m = (Int -> a -> b -> Int) -> Int -> Map a b -> Int
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey'
        (\Int
s' a
k b
v -> Int -> b -> Int
hv (Int -> a -> Int
hk Int
s' a
k) b
v)
        (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (Map a b -> Int
forall k a. Map k a -> Int
Map.size Map a b
m))
        Map a b
m

-- | @since 1.3.4.0
instance Hashable k => Hashable1 (Map.Map k) where
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> Map k a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s Map k a
m = (Int -> k -> a -> Int) -> Int -> Map k a -> Int
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey'
        (\Int
s' k
k a
v -> Int -> a -> Int
h (Int -> k -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s' k
k) a
v)
        (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (Map k a -> Int
forall k a. Map k a -> Int
Map.size Map k a
m))
        Map k a
m

-- | @since 1.3.4.0
instance (Hashable k, Hashable v) => Hashable (Map.Map k v) where
    hashWithSalt :: Int -> Map k v -> Int
hashWithSalt = Int -> Map k v -> Int
forall (f :: * -> * -> *) a b.
(Hashable2 f, Hashable a, Hashable b) =>
Int -> f a b -> Int
hashWithSalt2

-- | @since 1.3.4.0
instance Hashable1 IntMap.IntMap where
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> IntMap a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s IntMap a
m = (Int -> Int -> a -> Int) -> Int -> IntMap a -> Int
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey'
        (\Int
s' Int
k a
v -> Int -> a -> Int
h (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s' Int
k) a
v)
        (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (IntMap a -> Int
forall a. IntMap a -> Int
IntMap.size IntMap a
m))
        IntMap a
m

-- | @since 1.3.4.0
instance Hashable v => Hashable (IntMap.IntMap v) where
    hashWithSalt :: Int -> IntMap v -> Int
hashWithSalt = Int -> IntMap v -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

-- | @since 1.3.4.0
instance Hashable1 Set.Set where
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> Set a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s Set a
x = (Int -> a -> Int) -> Int -> Set a -> Int
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl' Int -> a -> Int
h (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (Set a -> Int
forall a. Set a -> Int
Set.size Set a
x)) Set a
x

-- | @since 1.3.4.0
instance Hashable v => Hashable (Set.Set v) where
    hashWithSalt :: Int -> Set v -> Int
hashWithSalt = Int -> Set v -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

-- | @since 1.3.4.0
instance Hashable IntSet.IntSet where
    hashWithSalt :: Int -> IntSet -> Int
hashWithSalt Int
salt IntSet
x = (Int -> Int -> Int) -> Int -> IntSet -> Int
forall a. (a -> Int -> a) -> a -> IntSet -> a
IntSet.foldl' Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt
        (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (IntSet -> Int
IntSet.size IntSet
x))
        IntSet
x

-- | @since 1.3.4.0
instance Hashable1 Seq.Seq where
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> Seq a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s Seq a
x = (Int -> a -> Int) -> Int -> Seq a -> Int
forall b a. (b -> a -> b) -> b -> Seq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Int -> a -> Int
h (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (Seq a -> Int
forall a. Seq a -> Int
Seq.length Seq a
x)) Seq a
x

-- | @since 1.3.4.0
instance Hashable v => Hashable (Seq.Seq v) where
    hashWithSalt :: Int -> Seq v -> Int
hashWithSalt = Int -> Seq v -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

-- | @since 1.3.4.0
instance Hashable1 Tree.Tree where
    liftHashWithSalt :: forall a. (Int -> a -> Int) -> Int -> Tree a -> Int
liftHashWithSalt Int -> a -> Int
h = Int -> Tree a -> Int
go where
        go :: Int -> Tree a -> Int
go Int
s (Tree.Node a
x [Tree a]
xs) = (Int -> Tree a -> Int) -> Int -> [Tree a] -> Int
forall a. (Int -> a -> Int) -> Int -> [a] -> Int
forall (t :: * -> *) a.
Hashable1 t =>
(Int -> a -> Int) -> Int -> t a -> Int
liftHashWithSalt Int -> Tree a -> Int
go (Int -> a -> Int
h Int
s a
x) [Tree a]
xs

-- | @since 1.3.4.0
instance Hashable v => Hashable (Tree.Tree v) where
    hashWithSalt :: Int -> Tree v -> Int
hashWithSalt = Int -> Tree v -> Int
forall (f :: * -> *) a.
(Hashable1 f, Hashable a) =>
Int -> f a -> Int
hashWithSalt1

-------------------------------------------------------------------------------
-- Solo
-------------------------------------------------------------------------------

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