packages feed

hashable 1.2.7.0 → 1.3.0.0

raw patch · 10 files changed

+318/−324 lines, 10 filesdep +integer-simpledep ~basedep ~bytestringdep ~integer-gmpPVP ok

version bump matches the API change (PVP)

Dependencies added: integer-simple

Dependency ranges changed: base, bytestring, integer-gmp, text

API changes (from Hackage documentation)

+ Data.Hashable: infixl 0 `hashWithSalt`
+ Data.Hashable.Generic: class GHashable arity f
+ Data.Hashable.Generic: data One
+ Data.Hashable.Generic: data Zero
+ Data.Hashable.Generic: data family HashArgs arity a :: *
+ Data.Hashable.Generic: genericHashWithSalt :: (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int
+ Data.Hashable.Generic: genericLiftHashWithSalt :: (Generic1 t, GHashable One (Rep1 t)) => (Int -> a -> Int) -> Int -> t a -> Int
+ Data.Hashable.Generic: ghashWithSalt :: GHashable arity f => HashArgs arity a -> Int -> f a -> Int
- Data.Hashable: hashUsing :: (Hashable b) => (a -> b) -> Int -> a -> Int
+ Data.Hashable: hashUsing :: Hashable b => (a -> b) -> Int -> a -> Int

Files

CHANGES.md view
@@ -1,3 +1,23 @@+See also https://pvp.haskell.org/faq++## Version 1.3.0.0++ * Semantic change of `Hashable Arg` instance to *not* hash the second+   argument of `Arg` in order to be consistent with `Eq Arg` (#171)++ * Semantic change of `Hashable Float` and `Hashable Double` instances+   to hash `-0.0` and `0.0` to the same value (#173)++ * Add `Hashable` instance for `Fingerprint` (#156)++ * Add new `Data.Hashable.Generic` module providing the default+   implementations `genericHashWithSalt` and `genericLiftHashWithSalt`+   together with other Generics support helpers (#148, #178)++ * Bump minimum version requirement of `base` to `base-4.5` (i.e. GHC >= 7.4)++----+ ## Version 1.2.7.0   * Add `Hashable` and `Hashable1` instances for `Complex`@@ -111,14 +131,14 @@   * Fix bug where code relied on rewrite rules firing for correctness. -## Version1.2.0.4+## Version 1.2.0.4   * Update docs to match code.   * Work around bug in GHCi runtime linker, which never call static    initializers. -## Version1.2.0.3+## Version 1.2.0.3   * Make building of SSE 4.1 code conditional, as it doesn't work on all    platforms.@@ -126,17 +146,17 @@  * Use a fixed salt, but allow random salting. Random salting by    default broke people's code. -## Version1.2.0.2+## Version 1.2.0.2   * Work around ghci linker bug on Windows. -## Version1.2.0.1+## Version 1.2.0.1   * Fix performance bug in SSE implementation of SipHash.   * Fix segfault due to incorrect stack alignment on Windows. -## Version1.2.0.0+## Version 1.2.0.0   * Switch string hashing from FNV-1 to SipHash, in an effort to    prevent collision attacks.@@ -152,11 +172,13 @@   * Add instance for Ordering. -## Version1.1.2.5+---- +## Version 1.1.2.5+  * Bug fix for bytestring < 0.10.0. -## Version1.1.2.4+## Version 1.1.2.4   * Switch string hashing from Bernstein to FNV-1 @@ -166,48 +188,44 @@   * Now works with GHC 7.6. -## Version1.1.2.3+## Version 1.1.2.3   * Add instance for TypeRep.   * Update dependency on test-framework. -## Version1.1.2.2+## Version 1.1.2.2   * Bug fix for GHC 7.4 -## Version1.1.2.1+## Version 1.1.2.1   * Update dependency on test-framework.   * Improve documentation of combine. -## Version1.1.2.0-- * Add instances for Interger, Ratio, Float, Double, and StableName.+## Version 1.1.2.0   * Fix hash collision issues for lists and tuples when using a    user-specified salt. -## Version1.1.1.0+ * Add instances for `Integer`, `Ratio`, `Float`, `Double`, and `StableName`.   * Improved instances for tuples and lists. - * Add instances for StableName, Float, Double, Integer, and Ratio.--## Version1.1.1.0+## Version 1.1.1.0 - * Add hashWithSalt, which allows the user to create different hash+ * Add `hashWithSalt`, which allows the user to create different hash    values for the same input by providing different seeds. This is    useful for application like Cuckoo hashing which need a family of    hash functions. - * Fix a bug in the Hashable instance for Int64/Word64 on 32-bit+ * Fix a bug in the `Hashable` instance for `Int64`/`Word64` on 32-bit    platforms.   * Improved resilience to leading zero in the input being hashed. -## Version1.1.0.0+## Version 1.1.0.0   * Add instance for: strict and lazy Texts, ThreadId @@ -220,17 +238,19 @@  * Fix ByteString hashing to work correctly on both 32 and 64-bit    platforms. -## Version1.0.1.1+## Version 1.0.1.1   * Fix bug in Hashable instance for lazy ByteStrings where differences    in the internal structure of the ByteString could cause different    hash values for ByteStrings that are equal according to ==. -## Version1.0.1.0+## Version 1.0.1.0   * Add two helpers for creating Hashable instances: hashPtr and    hashByteArray. -## Version1.0.0+----++## Version 1.0.0   * Separate Hashable class to its own package from hashmap 1.0.0.3.
Data/Hashable.hs view
@@ -1,8 +1,5 @@-{-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-}-#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Trustworthy #-}-#endif  ------------------------------------------------------------------------ -- |@@ -10,7 +7,7 @@ -- Copyright   :  (c) Milan Straka 2010 --                (c) Johan Tibell 2011 --                (c) Bryan O'Sullivan 2011, 2012--- License     :  BSD-style+-- SPDX-License-Identifier : BSD-3-Clause -- Maintainer  :  johan.tibell@gmail.com -- Stability   :  provisional -- Portability :  portable@@ -20,7 +17,7 @@ -- hashing-based data structures.  The module provides instances for -- most standard types.  Efficient instances for other types can be -- generated automatically and effortlessly using the generics support--- in GHC 7.2 and above.+-- in GHC 7.4 and above. -- -- The easiest way to get started is to use the 'hash' function. Here -- is an example session with @ghci@.@@ -60,10 +57,9 @@     , hashUsing     , hashPtr     , hashPtrWithSalt-#if defined(__GLASGOW_HASKELL__)     , hashByteArray     , hashByteArrayWithSalt-#endif+     -- * Caching hashes     , Hashed     , hashed@@ -73,10 +69,7 @@     ) where  import Data.Hashable.Class--#ifdef GENERICS import Data.Hashable.Generic ()-#endif  -- $security -- #security#@@ -95,9 +88,9 @@  -- $generics ----- Beginning with GHC 7.2, the recommended way to make instances of+-- The recommended way to make instances of -- 'Hashable' for most types is to use the compiler's support for--- automatically generating default instances.+-- automatically generating default instances using "GHC.Generics". -- -- > {-# LANGUAGE DeriveGeneric #-} -- >@@ -117,6 +110,11 @@ -- If you omit a body for the instance declaration, GHC will generate -- a default instance that correctly and efficiently hashes every -- constructor and parameter.+--+-- The default implementations are provided by+-- 'genericHashWithSalt' and 'genericLiftHashWithSalt'; those together with+-- the generic type class 'GHashable' and auxiliary functions are exported+-- from the "Data.Hashable.Generic" module.  -- $generic_err --
Data/Hashable/Class.hs view
@@ -1,26 +1,19 @@-{-# LANGUAGE BangPatterns, CPP, ForeignFunctionInterface, MagicHash,-             ScopedTypeVariables, UnliftedFFITypes #-}--#if __GLASGOW_HASKELL__ < 710-{-# LANGUAGE DeriveDataTypeable #-}-#endif+{-# LANGUAGE BangPatterns, CPP, MagicHash,+             ScopedTypeVariables, UnliftedFFITypes, DeriveDataTypeable,+             DefaultSignatures, FlexibleContexts, TypeFamilies,+             MultiParamTypeClasses #-}  #if __GLASGOW_HASKELL__ >= 801 {-# LANGUAGE PolyKinds #-} -- For TypeRep instances #endif -#ifdef GENERICS-{-# LANGUAGE DefaultSignatures, FlexibleContexts, GADTs,-    MultiParamTypeClasses, EmptyDataDecls #-}-#endif- ------------------------------------------------------------------------ -- | -- Module      :  Data.Hashable.Class -- Copyright   :  (c) Milan Straka 2010 --                (c) Johan Tibell 2011 --                (c) Bryan O'Sullivan 2011, 2012--- License     :  BSD-style+-- SPDX-License-Identifier : BSD-3-Clause -- Maintainer  :  johan.tibell@gmail.com -- Stability   :  provisional -- Portability :  portable@@ -36,13 +29,14 @@       Hashable(..)     , Hashable1(..)     , Hashable2(..)-#ifdef GENERICS+       -- ** Support for generics+    , genericHashWithSalt+    , genericLiftHashWithSalt     , GHashable(..)     , HashArgs(..)     , Zero     , One-#endif        -- * Creating new instances     , hashUsing@@ -106,25 +100,21 @@ import Data.Functor.Identity (Identity(..)) #endif -#ifdef GENERICS import GHC.Generics-#endif -#if   __GLASGOW_HASKELL__ >= 801+#if   MIN_VERSION_base(4,10,0) import Type.Reflection (Typeable, TypeRep, SomeTypeRep(..)) import Type.Reflection.Unsafe (typeRepFingerprint) import GHC.Fingerprint.Type(Fingerprint(..))-#elif __GLASGOW_HASKELL__ >= 710+#elif MIN_VERSION_base(4,8,0) import Data.Typeable (typeRepFingerprint, Typeable, TypeRep) import GHC.Fingerprint.Type(Fingerprint(..))-#elif __GLASGOW_HASKELL__ >= 702+#else import Data.Typeable.Internal (Typeable, TypeRep (..)) import GHC.Fingerprint.Type(Fingerprint(..))-#elif __GLASGOW_HASKELL__ >= 606-import Data.Typeable (typeRepKey, Typeable, TypeRep) #endif -#if __GLASGOW_HASKELL__ >= 703+#if MIN_VERSION_base(4,5,0) import Foreign.C (CLong(..)) import Foreign.C.Types (CInt(..)) #else@@ -233,31 +223,43 @@     hash :: a -> Int     hash = hashWithSalt defaultSalt -#ifdef GENERICS     default hashWithSalt :: (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int-    hashWithSalt salt = ghashWithSalt HashArgs0 salt . from+    hashWithSalt = genericHashWithSalt+    {-# INLINE hashWithSalt #-} +-- | Generic 'hashWithSalt'.+--+-- @since 1.3.0.0+genericHashWithSalt :: (Generic a, GHashable Zero (Rep a)) => Int -> a -> Int+genericHashWithSalt = \salt -> ghashWithSalt HashArgs0 salt . from+{-# INLINE genericHashWithSalt #-}+ data Zero data One -data HashArgs arity a where-    HashArgs0 :: HashArgs Zero a-    HashArgs1 :: (Int -> a -> Int) -> HashArgs One a+data family HashArgs arity a :: *+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 -#endif- class Hashable1 t where     -- | Lift a hashing function through the type constructor.     liftHashWithSalt :: (Int -> a -> Int) -> Int -> t a -> Int-#ifdef GENERICS+     default liftHashWithSalt :: (Generic1 t, GHashable One (Rep1 t)) => (Int -> a -> Int) -> Int -> t a -> Int-    liftHashWithSalt h salt = ghashWithSalt (HashArgs1 h) salt . from1-#endif+    liftHashWithSalt = 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 = \h salt -> ghashWithSalt (HashArgs1 h) salt . from1+{-# INLINE genericLiftHashWithSalt #-}+ class Hashable2 t where     -- | Lift a hashing function through the binary type constructor.     liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int@@ -458,8 +460,14 @@     hash a = hash (numerator a) `hashWithSalt` denominator a     hashWithSalt s a = s `hashWithSalt` numerator a `hashWithSalt` denominator 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 x+        | x == -0.0 || x == 0.0 = 0 -- see note in 'Hashable Double'         | isIEEE x =             assert (sizeOf x >= sizeOf (0::Word32) &&                     alignment x >= alignment (0::Word32)) $@@ -467,8 +475,14 @@         | otherwise = hash (show x)     hashWithSalt = 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 x+        | x == -0.0 || x == 0.0 = 0 -- s.t. @hash -0.0 == hash 0.0@ ; see #173         | isIEEE x =             assert (sizeOf x >= sizeOf (0::Word64) &&                     alignment x >= alignment (0::Word64)) $@@ -620,11 +634,7 @@  #if MIN_VERSION_bytestring(0,10,4) instance Hashable BSI.ShortByteString where-#if MIN_VERSION_base(4,3,0)     hashWithSalt salt sbs@(BSI.SBS ba) =-#else-    hashWithSalt salt sbs@(BSI.SBS ba _) =-#endif         hashByteArrayWithSalt ba 0 (BSI.length sbs) salt #endif @@ -661,28 +671,16 @@     hash n = fromIntegral n     hashWithSalt = defaultHashWithSalt -#if __GLASGOW_HASKELL__ < 801--- | Compute the hash of a TypeRep, in various GHC versions we can do this quickly.-hashTypeRep :: TypeRep -> Int-{-# INLINE hashTypeRep #-}-#if __GLASGOW_HASKELL__ >= 710--- Fingerprint is just the MD5, so taking any Int from it is fine-hashTypeRep tr = let Fingerprint x _ = typeRepFingerprint tr in fromIntegral x-#elif __GLASGOW_HASKELL__ >= 702--- Fingerprint is just the MD5, so taking any Int from it is fine-hashTypeRep (TypeRep (Fingerprint x _) _ _) = fromIntegral x-#elif __GLASGOW_HASKELL__ >= 606-hashTypeRep = unsafeDupablePerformIO . typeRepKey-#else-hashTypeRep = hash . show-#endif+----------------------------------------------------------------------------+-- Fingerprint & TypeRep instances -instance Hashable TypeRep where-    hash = hashTypeRep+-- | @since 1.3.0.0+instance Hashable Fingerprint where+    hash (Fingerprint x _) = fromIntegral x     hashWithSalt = defaultHashWithSalt     {-# INLINE hash #-} -#else+#if MIN_VERSION_base(4,10,0)  hashTypeRep :: Type.Reflection.TypeRep a -> Int hashTypeRep tr =@@ -697,8 +695,29 @@     hash = hashTypeRep     hashWithSalt = defaultHashWithSalt     {-# INLINE hash #-}++#else++-- | Compute the hash of a TypeRep, in various GHC versions we can do this quickly.+hashTypeRep :: TypeRep -> Int+{-# INLINE hashTypeRep #-}+#if   MIN_VERSION_base(4,8,0)+-- Fingerprint is just the MD5, so taking any Int from it is fine+hashTypeRep tr = let Fingerprint x _ = typeRepFingerprint tr in fromIntegral x+#else+-- Fingerprint is just the MD5, so taking any Int from it is fine+hashTypeRep (TypeRep (Fingerprint x _) _ _) = fromIntegral x #endif +instance Hashable TypeRep where+    hash = hashTypeRep+    hashWithSalt = defaultHashWithSalt+    {-# INLINE hash #-}++#endif++----------------------------------------------------------------------------+ #if MIN_VERSION_base(4,8,0) instance Hashable Void where     hashWithSalt _ = absurd@@ -813,8 +832,11 @@ instance Hashable a => Hashable (Max a) where     hashWithSalt p (Max a) = hashWithSalt p a -instance (Hashable a, Hashable b) => Hashable (Arg a b) where-    hashWithSalt p (Arg a b) = hashWithSalt p a `hashWithSalt` b+-- | __Note__: Prior to @hashable-1.3.0.0@ the hash computation included the second argument of 'Arg' which wasn't consistent with its 'Eq' instance.+--+-- @since 1.3.0.0+instance Hashable a => Hashable (Arg a b) where+    hashWithSalt p (Arg a _) = hashWithSalt p a  instance Hashable a => Hashable (First a) where     hashWithSalt p (First a) = hashWithSalt p a@@ -916,5 +938,3 @@ instance Show1 Hashed where   liftShowsPrec sp _ d (Hashed a _) = showsUnaryWith sp "hashed" d a #endif--
Data/Hashable/Generic.hs view
@@ -1,124 +1,25 @@-{-# LANGUAGE BangPatterns, FlexibleInstances, KindSignatures,-             ScopedTypeVariables, TypeOperators,-             MultiParamTypeClasses, GADTs, FlexibleContexts #-}-{-# OPTIONS_GHC -fno-warn-orphans #-}+{-# LANGUAGE Trustworthy #-} ------------------------------------------------------------------------- -- | -- Module      :  Data.Hashable.Generic--- Copyright   :  (c) Bryan O'Sullivan 2012--- License     :  BSD-style--- Maintainer  :  bos@serpentine.com+-- SPDX-License-Identifier : BSD-3-Clause -- Stability   :  provisional--- Portability :  GHC >= 7.2+-- Portability :  GHC >= 7.4 -- -- Hashable support for GHC generics.-+--+-- @since 1.3.0.0 module Data.Hashable.Generic     (+    -- * Implementation using Generics.+      genericHashWithSalt+    , genericLiftHashWithSalt+    -- * Constraints+    , GHashable (..)+    , One+    , Zero+    , HashArgs (..)     ) where +import Data.Hashable.Generic.Instances () import Data.Hashable.Class-import GHC.Generics---- Type without constructors-instance GHashable arity V1 where-    ghashWithSalt _ salt _ = hashWithSalt salt ()---- Constructor without arguments-instance GHashable arity U1 where-    ghashWithSalt _ salt U1 = hashWithSalt salt ()--instance (GHashable arity a, GHashable arity b) => GHashable arity (a :*: b) where-    ghashWithSalt toHash salt (x :*: y) =-      (ghashWithSalt toHash (ghashWithSalt toHash salt x) y)---- Metadata (constructor name, etc)-instance GHashable arity a => GHashable arity (M1 i c a) where-    ghashWithSalt targs salt = ghashWithSalt targs salt . unM1---- Constants, additional parameters, and rank-1 recursion-instance Hashable a => GHashable arity (K1 i a) where-    ghashWithSalt _ = hashUsing unK1--instance GHashable One Par1 where-    ghashWithSalt (HashArgs1 h) salt = h salt . unPar1--instance Hashable1 f => GHashable One (Rec1 f) where-    ghashWithSalt (HashArgs1 h) salt = liftHashWithSalt h salt . unRec1--instance (Hashable1 f, GHashable One g) => GHashable One (f :.: g) where-    ghashWithSalt targs salt = liftHashWithSalt (ghashWithSalt targs) salt . unComp1--class SumSize f => GSum arity f where-    hashSum :: HashArgs arity a -> Int -> Int -> f a -> Int-    -- hashSum args salt index value = ...---- [Note: Hashing a sum type]------ The tree structure is used in GHC.Generics to represent the sum (and--- product) part of the generic represention of the type, e.g.:------   (C0 ... :+: C1 ...) :+: (C2 ... :+: (C3 ... :+: C4 ...))------ The value constructed with C2 constructor is represented as (R1 (L1 ...)).--- Yet, if we think that this tree is a flat (heterogenous) list:------   [C0 ..., C1 ..., C2 ..., C3 ..., C4... ]------ then the value constructed with C2 is a (dependent) pair (2, ...), and--- hashing it is simple:------   salt `hashWithSalt` (2 :: Int) `hashWithSalt` ...------ This is what we do below. When drilling down the tree, we count how many--- leafs are to the left (`index` variable). At the leaf case C1, we'll have an--- actual index into the sum.------ This works well for balanced data. However for recursive types like:------   data Nat = Z | S Nat------ the `hashWithSalt salt (S (S (S Z)))` is------   salt `hashWithSalt` (1 :: Int) -- first S---        `hashWithSalt` (1 :: Int) -- second S---        `hashWithSalt` (1 :: Int) -- third S---        `hashWithSalt` (0 :: Int) -- Z---        `hashWithSalt` ()         -- U1------ For that type the manual implementation:------    instance Hashable Nat where---        hashWithSalt salt n = hashWithSalt salt (natToInteger n)------ would be better performing CPU and hash-quality wise (assuming that--- Integer's Hashable is of high quality).----instance (GSum arity a, GSum arity b) => GHashable arity (a :+: b) where-    ghashWithSalt toHash salt = hashSum toHash salt 0--instance (GSum arity a, GSum arity b) => GSum arity (a :+: b) where-    hashSum toHash !salt !index s = case s of-        L1 x -> hashSum toHash salt index x-        R1 x -> hashSum toHash salt (index + sizeL) x-      where-        sizeL = unTagged (sumSize :: Tagged a)-    {-# INLINE hashSum #-}--instance GHashable arity a => GSum arity (C1 c a) where-    hashSum toHash !salt !index (M1 x) = ghashWithSalt toHash (hashWithSalt salt index) x-    {-# INLINE hashSum #-}--class SumSize f where-    sumSize :: Tagged f--newtype Tagged (s :: * -> *) = Tagged {unTagged :: Int}--instance (SumSize a, SumSize b) => SumSize (a :+: b) where-    sumSize = Tagged $ unTagged (sumSize :: Tagged a) +-                       unTagged (sumSize :: Tagged b)--instance SumSize (C1 c a) where-    sumSize = Tagged 1-
+ Data/Hashable/Generic/Instances.hs view
@@ -0,0 +1,121 @@+{-# LANGUAGE BangPatterns, FlexibleInstances, KindSignatures,+             ScopedTypeVariables, TypeOperators,+             MultiParamTypeClasses, GADTs, FlexibleContexts #-}+{-# OPTIONS_GHC -fno-warn-orphans #-}++------------------------------------------------------------------------+-- |+-- Module      :  Data.Hashable.Generic.Instances+-- Copyright   :  (c) Bryan O'Sullivan 2012+-- SPDX-License-Identifier : BSD-3-Clause+-- Maintainer  :  bos@serpentine.com+-- Stability   :  provisional+-- Portability :  GHC >= 7.4+--+-- Internal module defining orphan instances for "GHC.Generics"+--+module Data.Hashable.Generic.Instances () where++import Data.Hashable.Class+import GHC.Generics++-- Type without constructors+instance GHashable arity V1 where+    ghashWithSalt _ salt _ = hashWithSalt salt ()++-- Constructor without arguments+instance GHashable arity U1 where+    ghashWithSalt _ salt U1 = hashWithSalt salt ()++instance (GHashable arity a, GHashable arity b) => GHashable arity (a :*: b) where+    ghashWithSalt toHash salt (x :*: y) =+      (ghashWithSalt toHash (ghashWithSalt toHash salt x) y)++-- Metadata (constructor name, etc)+instance GHashable arity a => GHashable arity (M1 i c a) where+    ghashWithSalt targs salt = ghashWithSalt targs salt . unM1++-- Constants, additional parameters, and rank-1 recursion+instance Hashable a => GHashable arity (K1 i a) where+    ghashWithSalt _ = hashUsing unK1++instance GHashable One Par1 where+    ghashWithSalt (HashArgs1 h) salt = h salt . unPar1++instance Hashable1 f => GHashable One (Rec1 f) where+    ghashWithSalt (HashArgs1 h) salt = liftHashWithSalt h salt . unRec1++instance (Hashable1 f, GHashable One g) => GHashable One (f :.: g) where+    ghashWithSalt targs salt = liftHashWithSalt (ghashWithSalt targs) salt . unComp1++class SumSize f => GSum arity f where+    hashSum :: HashArgs arity a -> Int -> Int -> f a -> Int+    -- hashSum args salt index value = ...++-- [Note: Hashing a sum type]+--+-- The tree structure is used in GHC.Generics to represent the sum (and+-- product) part of the generic represention of the type, e.g.:+--+--   (C0 ... :+: C1 ...) :+: (C2 ... :+: (C3 ... :+: C4 ...))+--+-- The value constructed with C2 constructor is represented as (R1 (L1 ...)).+-- Yet, if we think that this tree is a flat (heterogenous) list:+--+--   [C0 ..., C1 ..., C2 ..., C3 ..., C4... ]+--+-- then the value constructed with C2 is a (dependent) pair (2, ...), and+-- hashing it is simple:+--+--   salt `hashWithSalt` (2 :: Int) `hashWithSalt` ...+--+-- This is what we do below. When drilling down the tree, we count how many+-- leafs are to the left (`index` variable). At the leaf case C1, we'll have an+-- actual index into the sum.+--+-- This works well for balanced data. However for recursive types like:+--+--   data Nat = Z | S Nat+--+-- the `hashWithSalt salt (S (S (S Z)))` is+--+--   salt `hashWithSalt` (1 :: Int) -- first S+--        `hashWithSalt` (1 :: Int) -- second S+--        `hashWithSalt` (1 :: Int) -- third S+--        `hashWithSalt` (0 :: Int) -- Z+--        `hashWithSalt` ()         -- U1+--+-- For that type the manual implementation:+--+--    instance Hashable Nat where+--        hashWithSalt salt n = hashWithSalt salt (natToInteger n)+--+-- would be better performing CPU and hash-quality wise (assuming that+-- Integer's Hashable is of high quality).+--+instance (GSum arity a, GSum arity b) => GHashable arity (a :+: b) where+    ghashWithSalt toHash salt = hashSum toHash salt 0++instance (GSum arity a, GSum arity b) => GSum arity (a :+: b) where+    hashSum toHash !salt !index s = case s of+        L1 x -> hashSum toHash salt index x+        R1 x -> hashSum toHash salt (index + sizeL) x+      where+        sizeL = unTagged (sumSize :: Tagged a)+    {-# INLINE hashSum #-}++instance GHashable arity a => GSum arity (C1 c a) where+    hashSum toHash !salt !index (M1 x) = ghashWithSalt toHash (hashWithSalt salt index) x+    {-# INLINE hashSum #-}++class SumSize f where+    sumSize :: Tagged f++newtype Tagged (s :: * -> *) = Tagged {unTagged :: Int}++instance (SumSize a, SumSize b) => SumSize (a :+: b) where+    sumSize = Tagged $ unTagged (sumSize :: Tagged a) ++                       unTagged (sumSize :: Tagged b)++instance SumSize (C1 c a) where+    sumSize = Tagged 1
Data/Hashable/Lifted.hs view
@@ -1,7 +1,4 @@-{-# LANGUAGE CPP #-}-#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Trustworthy #-}-#endif  ------------------------------------------------------------------------ -- |@@ -9,7 +6,7 @@ -- Copyright   :  (c) Milan Straka 2010 --                (c) Johan Tibell 2011 --                (c) Bryan O'Sullivan 2011, 2012--- License     :  BSD-style+-- SPDX-License-Identifier : BSD-3-Clause -- Maintainer  :  johan.tibell@gmail.com -- Stability   :  provisional -- Portability :  portable@@ -77,7 +74,7 @@ -- given a 'liftHash' method: -- -- > class Hashable1 t where--- >     liftHash :: (Int -> a) -> t a -> Int+-- >     liftHash :: (a -> Int) -> t a -> Int -- >     liftHashWithSalt :: (Int -> a -> Int) -> Int -> t a -> Int -- -- Even for a type as simple as 'Maybe', the problem manifests itself. The
− benchmarks/cbits/siphash.h 
@@ -1,68 +0,0 @@-#ifndef _hashable_siphash_h-#define _hashable_siphash_h--#include <stdint.h>-#include <stdlib.h>--typedef uint64_t u64;-typedef uint32_t u32;-typedef uint16_t u16;-typedef uint8_t u8;--#define SIPHASH_ROUNDS 2-#define SIPHASH_FINALROUNDS 4--u64 hashable_siphash(int, int, u64, u64, const u8 *, size_t);-u64 hashable_siphash24(u64, u64, const u8 *, size_t);--#if defined(__i386)--/* To use SSE instructions, we have to adjust the stack from its-   default of 4-byte alignment to use 16-byte alignment. */--# define ALIGNED_STACK __attribute__((force_align_arg_pointer))--u64 hashable_siphash24_sse2(u64, u64, const u8 *, size_t) ALIGNED_STACK;-u64 hashable_siphash24_sse41(u64, u64, const u8 *, size_t) ALIGNED_STACK;-#endif--#if defined(_WIN32)-# define __LITTLE_ENDIAN 1234-# define __BIG_ENDIAN 4321-# define __BYTE_ORDER __LITTLE_ENDIAN--#elif (defined(__FreeBSD__) && __FreeBSD_version >= 470000) || defined(__OpenBSD__) || defined(__NetBSD__)-# include <sys/endian.h>-# define __BIG_ENDIAN BIG_ENDIAN-# define __LITTLE_ENDIAN LITTLE_ENDIAN-# define __BYTE_ORDER BYTE_ORDER--#elif (defined(BSD) && (BSD >= 199103)) || defined(__APPLE__)-# include <machine/endian.h>-# define __BIG_ENDIAN BIG_ENDIAN-# define __LITTLE_ENDIAN LITTLE_ENDIAN-# define __BYTE_ORDER BYTE_ORDER--#elif defined(__linux__)-# include <endian.h>-#endif--static inline u64 peek_u64le(const u64 *p)-{-    u64 x = *p;--#if __BYTE_ORDER == __BIG_ENDIAN-    x = ((x & 0xff00000000000000ull) >> 56) |-	((x & 0x00ff000000000000ull) >> 40) |-	((x & 0x0000ff0000000000ull) >> 24) |-	((x & 0x000000ff00000000ull) >> 8) |-	((x & 0x00000000ff000000ull) << 8) |-	((x & 0x0000000000ff0000ull) << 24) |-	((x & 0x000000000000ff00ull) << 40) |-	((x & 0x00000000000000ffull) << 56);-#endif--    return x;-}--#endif /* _hashable_siphash_h */
hashable.cabal view
@@ -1,6 +1,6 @@ Cabal-version:       1.12 Name:                hashable-Version:             1.2.7.0+Version:             1.3.0.0 Synopsis:            A class for types that can be converted to a hash value Description:         This package defines a class, 'Hashable', for types that                      can be converted to a hash value.  This class@@ -8,6 +8,7 @@                      structures.  The package provides instances for                      basic types and a way to combine hash values. Homepage:            http://github.com/tibbe/hashable+-- SPDX-License-Identifier : BSD-3-Clause License:             BSD3 License-file:        LICENSE Author:              Milan Straka <fox@ucw.cz>@@ -17,16 +18,13 @@ Stability:           Provisional Category:            Data Build-type:          Simple--- tests/Properties.hs shouldn't have to go here, but the source files--- for the test-suite stanzas don't get picked up by `cabal sdist`.-tested-with:         GHC==8.4.1, GHC==8.2.2, GHC==8.0.2, GHC==7.10.3, GHC==7.8.4, GHC==7.6.3, GHC==7.4.2, GHC==7.2.2+tested-with:         GHC==8.8.1, GHC==8.6.5, GHC==8.4.4, GHC==8.2.2, GHC==8.0.2, GHC==7.10.3, GHC==7.8.4, GHC==7.6.3, GHC==7.4.2  Extra-source-files:-  CHANGES.md, README.md, tests/Properties.hs,-  benchmarks/Benchmarks.hs, benchmarks/cbits/*.c, benchmarks/cbits/*.h+  CHANGES.md, README.md  Flag integer-gmp-  Description: Are we using integer-gmp to provide fast Integer instances?+  Description: Are we using @integer-gmp@ to provide fast Integer instances?   Default: True  Flag sse2@@ -47,40 +45,47 @@ Library   Exposed-modules:   Data.Hashable                      Data.Hashable.Lifted+                     Data.Hashable.Generic   Other-modules:     Data.Hashable.Class-  Build-depends:     base >= 4.4 && < 4.12,-                     bytestring >= 0.9 && < 0.11,-                     deepseq >= 1.3 && < 1.5-  if impl(ghc)-    Build-depends:   ghc-prim,-                     text >= 0.11.0.5-  if impl(ghc) && flag(integer-gmp)-    Build-depends:   integer-gmp >= 0.2+                     Data.Hashable.Generic.Instances -  if impl(ghc >= 7.2.1)-    CPP-Options:     -DGENERICS-    Other-modules:   Data.Hashable.Generic+  C-sources:         cbits/fnv.c -  C-sources:-                     cbits/fnv.c+  Build-depends:     base       >= 4.5      && < 4.14+                   , bytestring >= 0.9      && < 0.11+                   , deepseq    >= 1.3      && < 1.5+                   , text       >= 0.12     && < 1.3+                   , ghc-prim -  Ghc-options:       -Wall-  if impl(ghc >= 6.8)-    Ghc-options: -fwarn-tabs+  if flag(integer-gmp)+    Build-depends:   integer-gmp >= 0.4 && < 1.1   else-    c-sources:         cbits/getRandomBytes.c-    other-modules:     Data.Hashable.RandomSource-    if os(windows)-      extra-libraries: advapi32+    -- this is needed for the automatic flag to be well-balanced+    Build-depends:   integer-simple    Default-Language:  Haskell2010+  Other-Extensions:  BangPatterns+                     CPP+                     DeriveDataTypeable+                     FlexibleContexts+                     FlexibleInstances+                     GADTs+                     KindSignatures+                     MagicHash+                     MultiParamTypeClasses+                     ScopedTypeVariables+                     Trustworthy+                     TypeOperators+                     UnliftedFFITypes +  Ghc-options:       -Wall -fwarn-tabs+ Test-suite tests   Type:              exitcode-stdio-1.0   Hs-source-dirs:    tests   Main-is:           Main.hs   Other-modules:     Properties Regress-  Build-depends:     base >= 4.0 && < 5.0,+  Build-depends:     base,                      bytestring,                      ghc-prim,                      hashable,@@ -95,11 +100,9 @@     Build-depends:   unix     CPP-options:     -DHAVE_MMAP     Other-modules:   Regress.Mmap+    Other-Extensions: CApiFFI    Ghc-options:       -Wall -fno-warn-orphans-  if impl(ghc >= 7.2.1)-    CPP-Options:     -DGENERICS-   Default-Language:  Haskell2010  benchmark benchmarks
tests/Properties.hs view
@@ -1,8 +1,6 @@ {-# LANGUAGE BangPatterns, CPP, GeneralizedNewtypeDeriving, MagicHash,     Rank2Types, UnboxedTuples #-}-#ifdef GENERICS {-# LANGUAGE DeriveGeneric, ScopedTypeVariables #-}-#endif  -- | QuickCheck tests for the 'Data.Hashable' module.  We test -- functions by comparing the C and Haskell implementations.@@ -11,6 +9,7 @@  import Data.Hashable (Hashable, hash, hashByteArray, hashPtr,          Hashed, hashed, unhashed, hashWithSalt)+import Data.Hashable.Generic (genericHashWithSalt) import Data.Hashable.Lifted (hashWithSalt1) import qualified Data.ByteString as B import qualified Data.ByteString.Lazy as BL@@ -27,9 +26,7 @@ import Test.QuickCheck hiding ((.&.)) import Test.Framework (Test, testGroup) import Test.Framework.Providers.QuickCheck2 (testProperty)-#ifdef GENERICS import GHC.Generics-#endif  #if MIN_VERSION_bytestring(0,10,4) import qualified Data.ByteString.Short as BS@@ -156,8 +153,6 @@  -- Generics -#ifdef GENERICS- data Product2 a b = Product2 a b                     deriving (Generic) @@ -191,6 +186,13 @@ data Sum3 a b c = S3a a | S3b b | S3c c                   deriving (Eq, Ord, Show, Generic) +instance (Arbitrary a, Arbitrary b, Arbitrary c) => Arbitrary (Sum3 a b c) where+  arbitrary = oneof+    [ fmap S3a arbitrary+    , fmap S3b arbitrary+    , fmap S3c arbitrary+    ]+ instance (Hashable a, Hashable b, Hashable c) => Hashable (Sum3 a b c)  -- Hashes of the same parameter, but with different sum constructors,@@ -208,7 +210,8 @@              , hash (S3b x :: Sum3 Int Int Int)              , hash (S3c x :: Sum3 Int Int Int) ] -#endif+pGeneric :: Sum3 Int Bool String -> Int -> Bool+pGeneric x salt = hashWithSalt salt x == genericHashWithSalt salt x  instance (Arbitrary a, Hashable a) => Arbitrary (Hashed a) where   arbitrary = fmap hashed arbitrary@@ -235,7 +238,6 @@       , testProperty "bytestring/rechunk" pBSRechunk       , testProperty "bytestring/rechunked" pBSLazyRechunked       ]-#ifdef GENERICS     , testGroup "generics"       [       -- Note: "product2" and "product3" have been temporarily@@ -246,8 +248,8 @@       -- "product3" pProduct3         testProperty "sum2_differ" pSum2_differ       , testProperty "sum3_differ" pSum3_differ+      , testProperty "genericHashWithSalt" pGeneric       ]-#endif     , testGroup "lifted law"       [ testProperty "Hashed" pLiftedHashed       ]
tests/Regress/Mmap.hsc view
@@ -1,4 +1,4 @@-{-# LANGUAGE ForeignFunctionInterface #-}+{-# LANGUAGE CApiFFI #-}  module Regress.Mmap (regressions) where @@ -60,14 +60,14 @@ mprotect addr len prot =     throwErrnoIfMinus1_ "mprotect" $ c_mprotect addr len prot -foreign import ccall unsafe "sys/mman.h mmap"+foreign import capi unsafe "sys/mman.h mmap"     c_mmap :: Ptr a -> CSize -> CInt -> CInt -> CInt -> COff -> IO (Ptr a) -foreign import ccall unsafe "sys/mman.h munmap"+foreign import capi unsafe "sys/mman.h munmap"     c_munmap :: Ptr a -> CSize -> IO CInt -foreign import ccall unsafe "sys/mman.h mprotect"+foreign import capi unsafe "sys/mman.h mprotect"     c_mprotect :: Ptr a -> CSize -> CInt -> IO CInt -foreign import ccall unsafe "unistd.h getpagesize"+foreign import capi unsafe "unistd.h getpagesize"     getPageSize :: IO CInt