{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE CApiFFI                    #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DefaultSignatures          #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE PackageImports             #-}
{-# LANGUAGE PolyKinds                  #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# 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
    , defaultHash
      -- * 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 Control.Monad.ST       (runST)
import Data.Array.Byte        (ByteArray (..))
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.Word               (Word (..))
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.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 MIN_VERSION_base(4,19,0)
import GHC.Conc.Sync (fromThreadId)
#else
import GHC.Prim (ThreadId#)
#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
#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
import GHC.Exts                  (Int (..))
import GHC.Integer.GMP.Internals (Integer (..))
import GHC.Exts                  (sizeofByteArray#)
import GHC.Integer.GMP.Internals (BigNat (BN#))
#endif

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

import GHC.Float (castDoubleToWord64, castFloatToWord32)

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

-- filepath >=1.4.100 && <1.5 has System.OsString.Internal.Types module
#if MIN_VERSION_filepath(1,4,100) && !(MIN_VERSION_filepath(1,5,0))
#define HAS_OS_STRING_filepath 1
#else
#define HAS_OS_STRING_filepath 0
#endif

-- if we depend on os_string module, then it has System.OsString.Internal.Types
-- module as well
#ifdef MIN_VERSION_os_string
#define HAS_OS_STRING_os_string 1
#else
#define HAS_OS_STRING_os_string 0
#endif

#if HAS_OS_STRING_filepath && HAS_OS_STRING_os_string
import "os-string" System.OsString.Internal.Types (OsString (..), PosixString (..), WindowsString (..))
import qualified "filepath" System.OsString.Internal.Types as FP (OsString (..), PosixString (..), WindowsString (..))
#elif HAS_OS_STRING_filepath || HAS_OS_STRING_os_string
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
import Data.Hashable.XXH3

#include "MachDeps.h"

infixl 0 `hashWithSalt`

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

-- | The class of types that can be converted to a hash value.
--
-- Minimal implementation: 'hashWithSalt'.
--
-- 'Hashable' is intended exclusively for use in in-memory data structures.
-- .
-- 'Hashable' does /not/ have a fixed standard.
-- This allows it to improve over time.
-- .
-- Because it does not have a fixed standard, different computers or computers on different versions of the code will observe different hash values.
-- As such, 'Hashable' is not recommended for use other than in-memory datastructures.
-- Specifically, 'Hashable' is not intended for network use or in applications which persist hashed values.
-- For stable hashing use named hashes: sha256, crc32, xxhash 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 = a -> Int
forall a. Hashable a => a -> Int
defaultHash

    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'.
--
-- @since 1.4.3.0
--
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

-- | Default implementation of 'hash' based on 'hashWithSalt'.
--
-- @since 1.4.3.0
--
defaultHash :: Hashable a => a -> Int
defaultHash :: forall a. Hashable a => a -> Int
defaultHash = Int -> a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
defaultSalt

-- | 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
    hash :: Word64 -> Int
hash = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
    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(VERSION_integer_gmp) || defined(VERSION_ghc_bignum)
instance Hashable BigNat where
    hashWithSalt :: Int -> BigNat -> Int
hashWithSalt Int
salt (BN# BigNat#
ba) = Int -> ByteArray -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (BigNat# -> ByteArray
ByteArray 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)
#elif defined(VERSION_integer_gmp)
    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

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))
#elif defined(VERSION_integer_gmp)
    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
    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

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
$
            Word32 -> Int
forall a. Hashable a => a -> Int
hash (Float -> Word32
castFloatToWord32 Float
x)
        | 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 (Double -> Word64
castDoubleToWord64 Double
x)
        | 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
    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
    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
    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
    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
    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
    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
    hash :: ByteString -> Int
hash ByteString
bs = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteString -> Word64 -> Word64
xxh3_64bit_withSeed_bs ByteString
bs Word64
0)

    hashWithSalt :: Int -> ByteString -> Int
hashWithSalt Int
salt ByteString
bs =
        Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteString -> Word64 -> Word64
xxh3_64bit_withSeed_bs ByteString
bs (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Int
len)))
      where
        len :: Int
len = ByteString -> Int
B.length ByteString
bs

instance Hashable BL.ByteString where
    hashWithSalt :: Int -> ByteString -> Int
hashWithSalt Int
salt ByteString
lbs = (forall s. ST s Int) -> Int
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s Int) -> Int) -> (forall s. ST s Int) -> Int
forall a b. (a -> b) -> a -> b
$ do
        XXH3_State s
s <- ST s (XXH3_State s)
forall s. ST s (XXH3_State s)
xxh3_64bit_createState
        XXH3_State s -> Word64 -> ST s ()
forall s. XXH3_State s -> Word64 -> ST s ()
xxh3_64bit_reset_withSeed XXH3_State s
s (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
salt)
        Word64
len <- (ByteString -> (Word64 -> ST s Word64) -> Word64 -> ST s Word64)
-> (Word64 -> ST s Word64) -> ByteString -> Word64 -> ST s Word64
forall a. (ByteString -> a -> a) -> a -> ByteString -> a
BL.foldrChunks (XXH3_State s
-> ByteString -> (Word64 -> ST s Word64) -> Word64 -> ST s Word64
forall {t} {s} {b}.
Num t =>
XXH3_State s -> ByteString -> (t -> ST s b) -> t -> ST s b
step XXH3_State s
s) Word64 -> ST s Word64
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ByteString
lbs Word64
0
        XXH3_State s -> Word64 -> ST s ()
forall s. XXH3_State s -> Word64 -> ST s ()
xxh3_64bit_update_w64 XXH3_State s
s Word64
len
        Word64
digest <- XXH3_State s -> ST s Word64
forall s. XXH3_State s -> ST s Word64
xxh3_64bit_digest XXH3_State s
s
        Int -> ST s Int
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
digest)
      where
        step :: XXH3_State s -> ByteString -> (t -> ST s b) -> t -> ST s b
step XXH3_State s
s ByteString
bs t -> ST s b
next !t
acc = do
            XXH3_State s -> ByteString -> ST s ()
forall s. XXH3_State s -> ByteString -> ST s ()
xxh3_64bit_update_bs XXH3_State s
s ByteString
bs
            t -> ST s b
next (t
acc t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteString -> Int
B.length ByteString
bs))

instance Hashable BSI.ShortByteString where
    hash :: ShortByteString -> Int
hash (BSI.SBS BigNat#
ba) = ByteArray -> Int
forall a. Hashable a => a -> Int
hash (BigNat# -> ByteArray
ByteArray BigNat#
ba)
    hashWithSalt :: Int -> ShortByteString -> Int
hashWithSalt Int
salt (BSI.SBS BigNat#
ba) = Int -> ByteArray -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (BigNat# -> ByteArray
ByteArray BigNat#
ba)

#if HAS_OS_STRING_filepath || HAS_OS_STRING_os_string
-- | @since 1.4.2.0
deriving newtype instance Hashable PosixString

-- | @since 1.4.2.0
deriving newtype instance Hashable WindowsString

-- | @since 1.4.2.0
deriving newtype instance Hashable OsString
#endif

#if HAS_OS_STRING_filepath && HAS_OS_STRING_os_string
deriving newtype instance Hashable FP.PosixString
deriving newtype instance Hashable FP.WindowsString
deriving newtype instance Hashable FP.OsString
#endif

#if MIN_VERSION_text(2,0,0)

instance Hashable T.Text where
    hash :: Text -> Int
hash (T.Text (TA.ByteArray BigNat#
arr) Int
off Int
len) =
        Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteArray -> Int -> Int -> Word64 -> Word64
xxh3_64bit_withSeed_ba (BigNat# -> ByteArray
ByteArray BigNat#
arr) Int
off Int
len Word64
0)
    hashWithSalt :: Int -> Text -> Int
hashWithSalt Int
salt (T.Text (TA.ByteArray BigNat#
arr) Int
off Int
len) =
        Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteArray -> Int -> Int -> Word64 -> Word64
xxh3_64bit_withSeed_ba (BigNat# -> ByteArray
ByteArray BigNat#
arr) Int
off Int
len (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (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 Text
lt = (forall s. ST s Int) -> Int
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s Int) -> Int) -> (forall s. ST s Int) -> Int
forall a b. (a -> b) -> a -> b
$ do
        XXH3_State s
s <- ST s (XXH3_State s)
forall s. ST s (XXH3_State s)
xxh3_64bit_createState
        XXH3_State s -> Word64 -> ST s ()
forall s. XXH3_State s -> Word64 -> ST s ()
xxh3_64bit_reset_withSeed XXH3_State s
s (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
salt)
        Word64
len <- (Text -> (Word64 -> ST s Word64) -> Word64 -> ST s Word64)
-> (Word64 -> ST s Word64) -> Text -> Word64 -> ST s Word64
forall a. (Text -> a -> a) -> a -> Text -> a
TL.foldrChunks (XXH3_State s
-> Text -> (Word64 -> ST s Word64) -> Word64 -> ST s Word64
forall {t} {s} {b}.
Num t =>
XXH3_State s -> Text -> (t -> ST s b) -> t -> ST s b
step XXH3_State s
s) Word64 -> ST s Word64
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Text
lt Word64
0
        XXH3_State s -> Word64 -> ST s ()
forall s. XXH3_State s -> Word64 -> ST s ()
xxh3_64bit_update_w64 XXH3_State s
s Word64
len
        Word64
digest <- XXH3_State s -> ST s Word64
forall s. XXH3_State s -> ST s Word64
xxh3_64bit_digest XXH3_State s
s
        Int -> ST s Int
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
digest)
      where
        step :: XXH3_State s -> Text -> (t -> ST s b) -> t -> ST s b
step XXH3_State s
s (T.Text (TA.ByteArray BigNat#
arr) Int
off Int
len) t -> ST s b
next !t
acc = do
            XXH3_State s -> ByteArray -> Int -> Int -> ST s ()
forall s. XXH3_State s -> ByteArray -> Int -> Int -> ST s ()
xxh3_64bit_update_ba XXH3_State s
s (BigNat# -> ByteArray
ByteArray BigNat#
arr) Int
off Int
len
            t -> ST s b
next (t
acc t -> t -> t
forall a. Num a => a -> a -> a
+ Int -> t
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len)

#else

instance Hashable T.Text where
    hash (T.Text arr off len) =
        fromIntegral (xxh3_64bit_withSeed_ba (ByteArray (TA.aBA arr)) (unsafeShiftL off 1) (unsafeShiftL len 1) 0)
    hashWithSalt salt (T.Text arr off len) =
        fromIntegral (xxh3_64bit_withSeed_ba (ByteArray (TA.aBA arr)) (unsafeShiftL off 1) (unsafeShiftL len 1) (fromIntegral (hashWithSalt salt len)))

instance Hashable TL.Text where
    hashWithSalt salt lt = runST $ do
        s <- xxh3_64bit_createState
        xxh3_64bit_reset_withSeed s (fromIntegral salt)
        len <- TL.foldrChunks (step s) return lt 0
        xxh3_64bit_update_w64 s len
        digest <- xxh3_64bit_digest s
        return (fromIntegral digest)
      where
        step s (T.Text arr off len) next !acc = do
            xxh3_64bit_update_ba s (ByteArray (TA.aBA arr)) (unsafeShiftL off 1) (unsafeShiftL len 1)
            next (acc + fromIntegral len)

#endif

#if !MIN_VERSION_base(4,19,0)
fromThreadId :: ThreadId -> Word64
fromThreadId :: ThreadId -> Word64
fromThreadId (ThreadId ThreadId#
t) = CULLong -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ThreadId# -> CULLong
getThreadId ThreadId#
t)

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

instance Hashable ThreadId where
    hash :: ThreadId -> Int
hash = Word64 -> Int
forall a. Hashable a => a -> Int
hash (Word64 -> Int) -> (ThreadId -> Word64) -> ThreadId -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ThreadId -> Word64
fromThreadId
    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

deriving newtype instance Hashable (Fixed a)

deriving newtype instance Hashable a => Hashable (Identity a)
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
deriving newtype instance Hashable a => Hashable (Const a b)

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

deriving newtype instance Hashable a => Hashable (Semi.Min a)
deriving newtype instance Hashable a => Hashable (Semi.Max 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

deriving newtype instance Hashable a => Hashable (Semi.First a)
deriving newtype instance Hashable a => Hashable (Semi.Last a)
deriving newtype instance Hashable a => Hashable (Semi.WrappedMonoid a)

#if !MIN_VERSION_base(4,16,0)
deriving newtype instance Hashable a => Hashable (Semi.Option 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
    hash :: ByteArray -> Int
hash ba :: ByteArray
ba@(AB.ByteArray BigNat#
ba') =
        Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteArray -> Int -> Int -> Word64 -> Word64
xxh3_64bit_withSeed_ba ByteArray
ba Int
0 Int
len Word64
0)
      where
        !len :: Int
len = Int# -> Int
I# (BigNat# -> Int#
sizeofByteArray# BigNat#
ba')

    hashWithSalt :: Int -> ByteArray -> Int
hashWithSalt Int
salt ba :: ByteArray
ba@(AB.ByteArray BigNat#
ba') =
        Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ByteArray -> Int -> Int -> Word64 -> Word64
xxh3_64bit_withSeed_ba ByteArray
ba Int
0 Int
len (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt Int
len)))
      where
        !len :: Int
len = 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