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

{-# LANGUAGE Trustworthy #-}

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

import Control.Applicative (Const(..))
import Control.Exception (assert)
import Control.DeepSeq (NFData(rnf))
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.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)
import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Map as Map
import qualified Data.Sequence as Seq
import qualified Data.Set as Set
import qualified Data.Tree as Tree

-- 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(..))
#else
import Data.Fixed (Fixed)
import Unsafe.Coerce (unsafeCoerce)
#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

import Foreign.C.Types (CInt(..))

#if !(MIN_VERSION_base(4,8,0))
import Data.Word (Word)
#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

import Data.Functor.Classes (Eq1(..),Ord1(..),Show1(..))

-- Whether we have lifted classes, in particular, Eq2
#ifndef MIN_VERSION_transformers
#define LIFTED_FUNCTOR_CLASSES 1
#else
#if !(MIN_VERSION_transformers(0,4,0) && !MIN_VERSION_transformers(0,5,0))
#define LIFTED_FUNCTOR_CLASSES 1
#endif
#endif

#ifdef LIFTED_FUNCTOR_CLASSES
import Data.Functor.Classes (Eq2)
#endif

#if MIN_VERSION_base(4,9,0)
import qualified Data.List.NonEmpty as NE
import Data.Semigroup

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

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

import Data.String (IsString(..))

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

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

#ifdef VERSION_base_orphans
import Data.Orphans ()
#endif

#ifdef VERSION_transformers_compat
import Control.Monad.Trans.Instances ()
#endif

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

#ifdef VERSION_functor_classes_compat
import Data.Map.Functor.Classes ()
import Data.Set.Functor.Classes ()
import Data.IntMap.Functor.Classes ()
import Data.Sequence.Functor.Classes ()
import Data.Tree.Functor.Classes ()
#endif

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

#if LIFTED_FUNCTOR_CLASSES
class Eq2 t => Hashable2 t where
#else
class Hashable2 t where
#endif
    -- | 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
`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 :: (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# 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. (?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
$
            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. (?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
$
            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
`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 :: (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
`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 :: (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
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

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

#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 -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (ShortByteString -> Int
BSI.length ShortByteString
sbs))
#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 -> 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 Array
arr Int
off Int
len) = Int -> Int -> SPInt
SP
            (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
s)
            (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
len)

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

-- this cannot be capi, as GHC panics.
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 '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 #-}

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)
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
#else
instance Hashable (Fixed a) where
    hashWithSalt salt x = hashWithSalt salt (unsafeCoerce x :: Integer)
#endif


#if MIN_VERSION_base(4,8,0)
-- TODO: make available on all base
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

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

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


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


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


#if !MIN_VERSION_base(4,16,0)
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

#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
#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
`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 (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
#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

-- | 'hash' has 'Eq' requirement.
--
-- @since 1.4.0.0
hashedHash :: Hashed a -> Int
hashedHash :: 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 :: (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)

#if MIN_VERSION_base(4,9,0)
#define LIFTED_FUNCTOR_CLASSES 1
#elif defined(MIN_VERSION_transformers)
#if !(MIN_VERSION_transformers(0,4,0)) || MIN_VERSION_transformers(0,5,0)
#define LIFTED_FUNCTOR_CLASSES 1
#endif
#endif

-- instances for @Data.Functor.Classes@ higher rank typeclasses
-- in base-4.9 and onward.
#if LIFTED_FUNCTOR_CLASSES
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
_) = 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
#else
instance Eq1 Hashed where eq1 = (==)
instance Ord1 Hashed where compare1 = compare
instance Show1 Hashed where showsPrec1 = showsPrec
#endif

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

-- | @since 1.3.4.0
instance Hashable2 Map.Map where
    liftHashWithSalt2 :: (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 :: (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 :: (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 :: (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 :: (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 (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.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 :: (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 Forest a
xs) = (Int -> Tree a -> Int) -> Int -> Forest 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) Forest 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 = hashWithSalt1
instance Hashable1 Solo where
    liftHashWithSalt h salt (Solo x) = h salt x
#endif