    {-# LANGUAGE BangPatterns               #-}
    {-# LANGUAGE CApiFFI                    #-}
    {-# LANGUAGE CPP                        #-}
    {-# LANGUAGE DefaultSignatures          #-}
    {-# LANGUAGE DerivingStrategies         #-}
    {-# LANGUAGE FlexibleContexts           #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    {-# LANGUAGE MagicHash                  #-}
    {-# LANGUAGE MultiParamTypeClasses      #-}
    {-# LANGUAGE PackageImports             #-}
    {-# LANGUAGE PolyKinds                  #-}
    {-# LANGUAGE QuantifiedConstraints      #-}
    {-# LANGUAGE ScopedTypeVariables        #-}
    {-# 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.Tuple             (Solo (..))
    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

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

    import GHC.Float (castDoubleToWord64, castFloatToWord32)

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

    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 (ZonkAny 0) -> Int -> Rep a (ZonkAny 0) -> 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 (ZonkAny 0)
    forall a. HashArgs Zero a
    HashArgs0 Int
    salt (Rep a (ZonkAny 0) -> Int) -> (a -> Rep a (ZonkAny 0)) -> a -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Rep a (ZonkAny 0)
    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, forall a. Hashable a => Hashable (t a)) => 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, forall a. Hashable a => Hashable1 (t a)) => 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

    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)

    instance Hashable Natural where
        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)

    instance Hashable Integer where
        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))

    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
            s <- ST s (XXH3_State s)
    forall s. ST s (XXH3_State s)
    xxh3_64bit_createState
            xxh3_64bit_reset_withSeed s (fromIntegral salt)
            len <- BL.foldrChunks (step s) return lbs 0
            xxh3_64bit_update_w64 s len
            digest <- xxh3_64bit_digest s
            return (fromIntegral 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
            s <- ST s (XXH3_State s)
    forall s. ST s (XXH3_State 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 :: 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 t) = fromIntegral (getThreadId 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 (ZonkAny 1) -> Int
    forall a. Hashable a => Int -> a -> Int
    hashWithSalt Int
    salt (Ptr (ZonkAny 1) -> Int) -> Ptr (ZonkAny 1) -> Int
    forall a b. (a -> b) -> a -> b
    $ FunPtr a -> Ptr (ZonkAny 1)
    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 @hashable-1.5.0.0@, @hash (Semi.arg a _) = hash a@
    --
    -- @since 1.3.0.0
    instance Hashable a => Hashable (Semi.Arg a b) where
        hash :: Arg a b -> Int
    hash (Semi.Arg a
    a b
    _) = a -> Int
    forall a. Hashable a => a -> Int
    hash a
    a
        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

    instance (Hashable (f (g a))) => Hashable (Compose f g a) where
        hash :: Compose f g a -> Int
    hash (Compose f (g a)
    x) = f (g a) -> Int
    forall a. Hashable a => a -> Int
    hash f (g a)
    x
        hashWithSalt :: Int -> Compose f g a -> Int
    hashWithSalt Int
    p (Compose f (g a)
    x) = Int -> f (g a) -> Int
    forall a. Hashable a => Int -> a -> Int
    hashWithSalt Int
    p f (g a)
    x

    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 (Hashable (f a), Hashable (g a)) => Hashable (FP.Product f g a) where
        hashWithSalt :: Int -> Product f g a -> Int
    hashWithSalt Int
    s (FP.Pair f a
    a g a
    b) = Int
    s Int -> f a -> Int
    forall a. Hashable a => Int -> a -> Int
    `hashWithSalt` f a
    a Int -> g a -> Int
    forall a. Hashable a => Int -> a -> Int
    `hashWithSalt` g a
    b

    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 (Hashable (f a), Hashable (g a)) => Hashable (FS.Sum f g a) where
        hashWithSalt :: Int -> Sum f g a -> Int
    hashWithSalt Int
    s (FS.InL f a
    a) = Int -> f a -> Int
    forall a. Hashable a => Int -> a -> Int
    hashWithSalt (Int
    s Int -> Int -> Int
    `hashInt` Int
    0) f a
    a
        hashWithSalt Int
    s (FS.InR g a
    a) = Int -> g a -> Int
    forall a. Hashable a => Int -> a -> Int
    hashWithSalt (Int
    s Int -> Int -> Int
    `hashInt` Int
    distinguisher) g a
    a

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

    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