unordered-containers 0.2.14.0 → 0.2.15.0
raw patch · 13 files changed
+32/−189 lines, 13 filesdep ~basedep ~bytestringdep ~containers
Dependency ranges changed: base, bytestring, containers, hashable
Files
- CHANGES.md +10/−0
- Data/HashMap/Internal.hs +2/−33
- Data/HashMap/Internal/Array.hs +1/−20
- Data/HashMap/Internal/Strict.hs +1/−8
- Data/HashMap/Internal/Unsafe.hs +0/−55
- Data/HashSet.hs +0/−2
- Data/HashSet/Internal.hs +3/−35
- benchmarks/Benchmarks.hs +0/−4
- tests/HashMapProperties.hs +0/−8
- tests/HashSetProperties.hs +0/−8
- tests/Regressions.hs +0/−1
- tests/Strictness.hs +0/−5
- unordered-containers.cabal +15/−10
CHANGES.md view
@@ -1,3 +1,13 @@+## [0.2.15.0]++* [Add security advisory regarding hash collision attacks](https://github.com/haskell-unordered-containers/unordered-containers/pull/320)++* [Add support for hashable 1.4](https://github.com/haskell-unordered-containers/unordered-containers/pull/324)++* [Drop support for GHC < 8](https://github.com/haskell-unordered-containers/unordered-containers/pull/323)++[0.2.15.0]: https://github.com/haskell-unordered-containers/unordered-containers/compare/v0.2.14.0...v0.2.15.0+ ## [0.2.14.0] * [Add `HashMap.mapKeys`.](https://github.com/haskell-unordered-containers/unordered-containers/pull/308) Thanks, Marco Perone!
Data/HashMap/Internal.hs view
@@ -137,17 +137,11 @@ , adjust# ) where -#if __GLASGOW_HASKELL__ < 710-import Control.Applicative ((<$>), Applicative(pure))-import Data.Monoid (Monoid(mempty, mappend))-import Data.Traversable (Traversable(..))-import Data.Word (Word)-#endif-#if __GLASGOW_HASKELL__ >= 711+#if !MIN_VERSION_base(4,11,0) import Data.Semigroup (Semigroup((<>))) #endif import Control.DeepSeq (NFData(rnf))-import Control.Monad.ST (ST)+import Control.Monad.ST (ST, runST) import Data.Bits ((.&.), (.|.), complement, popCount, unsafeShiftL, unsafeShiftR) import Data.Data hiding (Typeable) import qualified Data.Foldable as Foldable@@ -162,17 +156,14 @@ import qualified Data.HashMap.Internal.Array as A import qualified Data.Hashable as H import Data.Hashable (Hashable)-import Data.HashMap.Internal.Unsafe (runST) import Data.HashMap.Internal.List (isPermutationBy, unorderedCompare) import Data.Typeable (Typeable) import GHC.Exts (isTrue#) import qualified GHC.Exts as Exts -#if MIN_VERSION_base(4,9,0) import Data.Functor.Classes import GHC.Stack-#endif #if MIN_VERSION_hashable(1,2,5) import qualified Data.Hashable.Lifted as H@@ -186,9 +177,7 @@ import GHC.Exts (TYPE, Int (..), Int#) #endif -#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity (..))-#endif import Control.Applicative (Const (..)) import Data.Coerce (coerce) @@ -265,12 +254,10 @@ {-# INLINE foldr' #-} foldl' = foldl' {-# INLINE foldl' #-}-#if MIN_VERSION_base(4,8,0) null = null {-# INLINE null #-} length = size {-# INLINE length #-}-#endif #if MIN_VERSION_base(4,10,0) -- | @since 0.2.11@@ -283,7 +270,6 @@ {-# INLINE bifoldl #-} #endif -#if __GLASGOW_HASKELL__ >= 711 -- | '<>' = 'union' -- -- If a key occurs in both maps, the mapping from the first will be the mapping in the result.@@ -295,7 +281,6 @@ instance (Eq k, Hashable k) => Semigroup (HashMap k v) where (<>) = union {-# INLINE (<>) #-}-#endif -- | 'mempty' = 'empty' --@@ -310,11 +295,7 @@ instance (Eq k, Hashable k) => Monoid (HashMap k v) where mempty = empty {-# INLINE mempty #-}-#if __GLASGOW_HASKELL__ >= 711 mappend = (<>)-#else- mappend = union-#endif {-# INLINE mappend #-} instance (Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) where@@ -336,7 +317,6 @@ type Bitmap = Word type Shift = Int -#if MIN_VERSION_base(4,9,0) instance Show2 HashMap where liftShowsPrec2 spk slk spv slv d m = showsUnaryWith (liftShowsPrec sp sl) "fromList" d (toList m)@@ -353,7 +333,6 @@ where rp' = liftReadsPrec rp rl rl' = liftReadList rp rl-#endif instance (Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) where readPrec = parens $ prec 10 $ do@@ -371,13 +350,11 @@ traverse f = traverseWithKey (const f) {-# INLINABLE traverse #-} -#if MIN_VERSION_base(4,9,0) instance Eq2 HashMap where liftEq2 = equal2 instance Eq k => Eq1 (HashMap k) where liftEq = equal1-#endif -- | Note that, in the presence of hash collisions, equal @HashMap@s may -- behave differently, i.e. substitutivity may be violated:@@ -441,13 +418,11 @@ leafEq (L k v) (L k' v') = eqk k k' && eqv v v' -#if MIN_VERSION_base(4,9,0) instance Ord2 HashMap where liftCompare2 = cmp instance Ord k => Ord1 (HashMap k) where liftCompare = cmp compare-#endif -- | The ordering is total and consistent with the `Eq` instance. However, -- nothing else about the ordering is specified, and it may change from@@ -775,11 +750,7 @@ -- | /O(log n)/ Return the value to which the specified key is mapped. -- Calls 'error' if this map contains no mapping for the key.-#if MIN_VERSION_base(4,9,0) (!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v-#else-(!) :: (Eq k, Hashable k) => HashMap k v -> k -> v-#endif (!) m k = case lookup k m of Just v -> v Nothing -> error "Data.HashMap.Internal.(!): key not found"@@ -1331,7 +1302,6 @@ -- rule from firing. {-# INLINABLE [0] alterF #-} -#if MIN_VERSION_base(4,8,0) -- This is just a bottom value. See the comment on the "alterFWeird" -- rule. test_bottom :: a@@ -1448,7 +1418,6 @@ Absent -> Nothing Present v _ -> Just v {-# INLINABLE alterFEager #-}-#endif -- | /O(n*log m)/ Inclusion of maps. A map is included in another map if the keys -- are subsets and the corresponding values are equal:
Data/HashMap/Internal/Array.hs view
@@ -71,35 +71,19 @@ , fromList ) where -#if !MIN_VERSION_base(4,8,0)-import Control.Applicative (Applicative (..), (<$>))-#endif import Control.Applicative (liftA2) import Control.DeepSeq (NFData (..)) import GHC.Exts(Int(..), Int#, reallyUnsafePtrEquality#, tagToEnum#, unsafeCoerce#, State#) import GHC.ST (ST(..))-import Control.Monad.ST (stToIO)+import Control.Monad.ST (runST, stToIO) -#if __GLASGOW_HASKELL__ >= 709 import Prelude hiding (filter, foldMap, foldr, foldl, length, map, read, traverse, all)-#else-import Prelude hiding (filter, foldr, foldl, length, map, read, all)-#endif -#if __GLASGOW_HASKELL__ >= 710 import GHC.Exts (SmallArray#, newSmallArray#, readSmallArray#, writeSmallArray#, indexSmallArray#, unsafeFreezeSmallArray#, unsafeThawSmallArray#, SmallMutableArray#, sizeofSmallArray#, copySmallArray#, thawSmallArray#, sizeofSmallMutableArray#, copySmallMutableArray#, cloneSmallMutableArray#) -#else-import GHC.Exts (Array#, newArray#, readArray#, writeArray#,- indexArray#, unsafeFreezeArray#, unsafeThawArray#,- MutableArray#, sizeofArray#, copyArray#, thawArray#,- sizeofMutableArray#, copyMutableArray#, cloneMutableArray#)-import Data.Monoid (Monoid (..))-#endif- #if defined(ASSERTS) import qualified Prelude #endif@@ -108,11 +92,9 @@ import qualified Control.DeepSeq as NF #endif -import Data.HashMap.Internal.Unsafe (runST) import Control.Monad ((>=>)) -#if __GLASGOW_HASKELL__ >= 710 type Array# a = SmallArray# a type MutableArray# a = SmallMutableArray# a @@ -175,7 +157,6 @@ -> State# d -> State# d copyMutableArray# = copySmallMutableArray#-#endif ------------------------------------------------------------------------
Data/HashMap/Internal/Strict.hs view
@@ -118,11 +118,9 @@ , fromListWithKey ) where +import Control.Monad.ST (runST) import Data.Bits ((.&.), (.|.)) -#if !MIN_VERSION_base(4,8,0)-import Control.Applicative (Applicative (..), (<$>))-#endif import qualified Data.List as L import Data.Hashable (Hashable) import Prelude hiding (map, lookup)@@ -135,10 +133,7 @@ differenceWith, intersectionWith, intersectionWithKey, map, mapWithKey, mapMaybe, mapMaybeWithKey, singleton, update, unionWith, unionWithKey, traverseWithKey)-import Data.HashMap.Internal.Unsafe (runST)-#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity-#endif import Control.Applicative (Const (..)) import Data.Coerce @@ -329,7 +324,6 @@ -- don't fire. {-# INLINABLE [0] alterF #-} -#if MIN_VERSION_base(4,8,0) -- See notes in Data.HashMap.Internal test_bottom :: a test_bottom = error "Data.HashMap.alterF internal error: hit test_bottom"@@ -424,7 +418,6 @@ Absent -> Nothing Present v _ -> Just v {-# INLINABLE alterFEager #-}-#endif ------------------------------------------------------------------------ -- * Combine
− Data/HashMap/Internal/Unsafe.hs
@@ -1,55 +0,0 @@-{-# LANGUAGE CPP #-}--#if !MIN_VERSION_base(4,9,0)-{-# LANGUAGE MagicHash, Rank2Types, UnboxedTuples #-}-#endif--{-# OPTIONS_HADDOCK not-home #-}---- | = WARNING------ This module is considered __internal__.------ The Package Versioning Policy __does not apply__.------ The contents of this module may change __in any way whatsoever__--- and __without any warning__ between minor versions of this package.------ Authors importing this module are expected to track development--- closely.------ = Description------ This module exports a workaround for this bug:------ http://hackage.haskell.org/trac/ghc/ticket/5916------ Please read the comments in ghc/libraries/base/GHC/ST.lhs to--- understand what's going on here.------ Code that uses this module should be compiled with -fno-full-laziness-module Data.HashMap.Internal.Unsafe- ( runST- ) where--#if MIN_VERSION_base(4,9,0)--- The GHC issue was fixed in GHC 8.0/base 4.9-import Control.Monad.ST--#else--import GHC.Base (realWorld#)-import qualified GHC.ST as ST---- | Return the value computed by a state transformer computation.--- The @forall@ ensures that the internal state used by the 'ST'--- computation is inaccessible to the rest of the program.-runST :: (forall s. ST.ST s a) -> a-runST st = runSTRep (case st of { ST.ST st_rep -> st_rep })-{-# INLINE runST #-}--runSTRep :: (forall s. ST.STRep s a) -> a-runSTRep st_rep = case st_rep realWorld# of- (# _, r #) -> r-{-# INLINE [0] runSTRep #-}-#endif
Data/HashSet.hs view
@@ -1,7 +1,5 @@ {-# LANGUAGE CPP #-}-#if __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Safe #-}-#endif ------------------------------------------------------------------------ {-|
Data/HashSet/Internal.hs view
@@ -1,11 +1,7 @@ {-# LANGUAGE CPP, DeriveDataTypeable #-}-#if __GLASGOW_HASKELL__ >= 708 {-# LANGUAGE RoleAnnotations #-} {-# LANGUAGE TypeFamilies #-}-#endif-#if __GLASGOW_HASKELL__ >= 702 {-# LANGUAGE Trustworthy #-}-#endif {-# OPTIONS_HADDOCK not-home #-} ------------------------------------------------------------------------@@ -94,16 +90,16 @@ import Control.DeepSeq (NFData(..)) import Data.Data hiding (Typeable)+import Data.Functor.Classes import Data.HashMap.Internal ( HashMap, foldMapWithKey, foldlWithKey, foldrWithKey , equalKeys, equalKeys1) import Data.Hashable (Hashable(hashWithSalt))-#if __GLASGOW_HASKELL__ >= 711+#if !MIN_VERSION_base(4,11,0) import Data.Semigroup (Semigroup(..))-#elif __GLASGOW_HASKELL__ < 709-import Data.Monoid (Monoid(..)) #endif import GHC.Exts (build)+import qualified GHC.Exts as Exts import Prelude hiding (filter, foldr, foldl, map, null) import qualified Data.Foldable as Foldable import qualified Data.HashMap.Internal as H@@ -111,14 +107,6 @@ import Data.Typeable (Typeable) import Text.Read -#if __GLASGOW_HASKELL__ >= 708-import qualified GHC.Exts as Exts-#endif--#if MIN_VERSION_base(4,9,0)-import Data.Functor.Classes-#endif- #if MIN_VERSION_hashable(1,2,5) import qualified Data.Hashable.Lifted as H #endif@@ -127,16 +115,12 @@ import qualified Control.DeepSeq as NF #endif -import Data.Functor ((<$))- -- | A set of values. A set cannot contain duplicate values. newtype HashSet a = HashSet { asMap :: HashMap a () } deriving (Typeable) -#if __GLASGOW_HASKELL__ >= 708 type role HashSet nominal-#endif instance (NFData a) => NFData (HashSet a) where rnf = rnf . asMap@@ -170,19 +154,15 @@ HashSet a == HashSet b = equalKeys a b {-# INLINE (==) #-} -#if MIN_VERSION_base(4,9,0) instance Eq1 HashSet where liftEq eq (HashSet a) (HashSet b) = equalKeys1 eq a b-#endif instance (Ord a) => Ord (HashSet a) where compare (HashSet a) (HashSet b) = compare a b {-# INLINE compare #-} -#if MIN_VERSION_base(4,9,0) instance Ord1 HashSet where liftCompare c (HashSet a) (HashSet b) = liftCompare2 c compare a b-#endif instance Foldable.Foldable HashSet where foldMap f = foldMapWithKey (\a _ -> f a) . asMap@@ -194,16 +174,13 @@ {-# INLINE foldl' #-} foldr' = foldr' {-# INLINE foldr' #-}-#if MIN_VERSION_base(4,8,0) toList = toList {-# INLINE toList #-} null = null {-# INLINE null #-} length = size {-# INLINE length #-}-#endif -#if __GLASGOW_HASKELL__ >= 711 -- | '<>' = 'union' -- -- /O(n+m)/@@ -218,7 +195,6 @@ instance (Hashable a, Eq a) => Semigroup (HashSet a) where (<>) = union {-# INLINE (<>) #-}-#endif -- | 'mempty' = 'empty' --@@ -236,11 +212,7 @@ instance (Hashable a, Eq a) => Monoid (HashSet a) where mempty = empty {-# INLINE mempty #-}-#if __GLASGOW_HASKELL__ >= 711 mappend = (<>)-#else- mappend = union-#endif {-# INLINE mappend #-} instance (Eq a, Hashable a, Read a) => Read (HashSet a) where@@ -251,11 +223,9 @@ readListPrec = readListPrecDefault -#if MIN_VERSION_base(4,9,0) instance Show1 HashSet where liftShowsPrec sp sl d m = showsUnaryWith (liftShowsPrec sp sl) "fromList" d (toList m)-#endif instance (Show a) => Show (HashSet a) where showsPrec d m = showParen (d > 10) $@@ -486,9 +456,7 @@ fromList = HashSet . List.foldl' (\ m k -> H.insert k () m) H.empty {-# INLINE fromList #-} -#if __GLASGOW_HASKELL__ >= 708 instance (Eq a, Hashable a) => Exts.IsList (HashSet a) where type Item (HashSet a) = a fromList = fromList toList = toList-#endif
benchmarks/Benchmarks.hs view
@@ -21,10 +21,6 @@ import qualified Util.Int as UI import qualified Util.String as US -#if !MIN_VERSION_bytestring(0,10,0)-instance NFData BS.ByteString-#endif- data B where B :: NFData a => a -> B
tests/HashMapProperties.hs view
@@ -27,9 +27,7 @@ import Test.QuickCheck (Arbitrary(..), Property, (==>), (===), forAll, elements) import Test.Framework (Test, defaultMain, testGroup) import Test.Framework.Providers.QuickCheck2 (testProperty)-#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity (..))-#endif import Control.Applicative (Const (..)) import Test.QuickCheck.Function (Fun, apply) import Test.QuickCheck.Poly (A, B)@@ -196,12 +194,6 @@ fmap M.toAscList (M.alterF (apply f) k (M.fromList xs)) === fmap toAscList (HM.alterF (apply f) k (HM.fromList xs))--#if !MIN_VERSION_base(4,8,0)-newtype Identity a = Identity {runIdentity :: a}-instance Functor Identity where- fmap f (Identity x) = Identity (f x)-#endif pAlterFAdjust :: Key -> [(Key, Int)] -> Bool pAlterFAdjust k =
tests/HashSetProperties.hs view
@@ -136,21 +136,13 @@ (L.sort . S.foldr (:) []) foldrSet :: (a -> b -> b) -> b -> Set.Set a -> b-#if MIN_VERSION_containers(0,4,2) foldrSet = Set.foldr-#else-foldrSet = Foldable.foldr-#endif pFoldl' :: Int -> [Int] -> Bool pFoldl' z0 = foldl'Set (+) z0 `eq` S.foldl' (+) z0 foldl'Set :: (a -> b -> a) -> a -> Set.Set b -> a-#if MIN_VERSION_containers(0,4,2) foldl'Set = Set.foldl'-#else-foldl'Set = Foldable.foldl'-#endif ------------------------------------------------------------------------ -- ** Filter
tests/Regressions.hs view
@@ -3,7 +3,6 @@ {-# LANGUAGE UnboxedTuples #-} module Main where -import Control.Applicative ((<$>)) import Control.Exception (evaluate) import Control.Monad (replicateM) import Data.Hashable (Hashable(..))
tests/Strictness.hs view
@@ -14,11 +14,6 @@ import Control.Arrow (second) import Control.Monad (guard) import Data.Foldable (foldl')-#if !MIN_VERSION_base(4,8,0)-import Data.Functor ((<$))-import Data.Foldable (all)-import Prelude hiding (all)-#endif import Data.HashMap.Strict (HashMap) import qualified Data.HashMap.Strict as HM
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.2.14.0+version: 0.2.15.0 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been@@ -8,6 +8,13 @@ . The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared.+ .+ /Security/+ .+ This package currently provides no defenses against hash collision attacks+ such as HashDoS.+ Users who need to store input from untrusted sources are advised to use+ @Data.Map@ or @Data.Set@ from the @containers@ package instead. license: BSD3 license-file: LICENSE author: Johan Tibell@@ -22,15 +29,14 @@ extra-source-files: CHANGES.md tested-with:- GHC ==9.0.1- || ==8.10.4+ GHC ==9.2.1+ || ==9.0.1+ || ==8.10.7 || ==8.8.4 || ==8.6.5 || ==8.4.4 || ==8.2.2 || ==8.0.2- || ==7.10.3- || ==7.8.4 flag debug description: Enable debug support@@ -42,16 +48,15 @@ Data.HashMap.Internal.Array Data.HashMap.Internal.List Data.HashMap.Internal.Strict- Data.HashMap.Internal.Unsafe Data.HashMap.Lazy Data.HashMap.Strict Data.HashSet Data.HashSet.Internal build-depends:- base >= 4.7 && < 5,+ base >= 4.9 && < 5, deepseq >= 1.1,- hashable >= 1.0.1.1 && < 1.4+ hashable >= 1.0.1.1 && < 1.5 default-language: Haskell2010 @@ -115,7 +120,7 @@ build-depends: base,- containers >= 0.4,+ containers >= 0.4.2.0, hashable >= 1.0.1.1, QuickCheck >= 2.4.0.1, test-framework >= 0.3.3,@@ -195,7 +200,7 @@ build-depends: base >= 4.8.0,- bytestring,+ bytestring >= 0.10.0.0, containers, gauge >= 0.2.5 && < 0.3, deepseq >= 1.4,