unordered-containers 0.2.20 → 0.2.20.1
raw patch · 12 files changed
+106/−52 lines, 12 files
Files
- CHANGES.md +19/−0
- Data/HashMap/Internal.hs +39/−26
- Data/HashMap/Internal/Strict.hs +5/−5
- Data/HashMap/Lazy.hs +1/−1
- Data/HashMap/Strict.hs +1/−1
- Data/HashSet.hs +1/−1
- Data/HashSet/Internal.hs +3/−2
- tests/Main.hs +8/−5
- tests/Properties/HashMapLazy.hs +0/−2
- tests/Regressions.hs +14/−0
- tests/Util/Key.hs +7/−3
- unordered-containers.cabal +8/−6
CHANGES.md view
@@ -1,3 +1,22 @@+## [0.2.20.1] - October 2025++* [Fix infinite loop in `isSubmapOf[By]` / `isSubsetOf` on 32-bit platforms](https://github.com/haskell-unordered-containers/unordered-containers/pull/501).+ To fix this bug and potentially other similar bugs, we return to a branching factor of 16 on 32-bit platforms.++* [Relax bounds for GHC 9.12](https://github.com/haskell-unordered-containers/unordered-containers/pull/499)++* [Require `hashable >= 1.4`](https://github.com/haskell-unordered-containers/unordered-containers/pull/506)++* Documentation changes:+ * [Fix documentation about branching factor in `Data.HashMap.Strict`](https://github.com/haskell-unordered-containers/unordered-containers/pull/494)+ * [Improve documentation for `Data.HashMap.compose`](https://github.com/haskell-unordered-containers/unordered-containers/pull/500)+ * [Fixes docs of `Data.HashMap.Lazy.fromList`: it takes O(n * log(n))](https://github.com/haskell-unordered-containers/unordered-containers/pull/498)+ * [Add disclaimer to `Data.HashSet.toList`](https://github.com/haskell-unordered-containers/unordered-containers/pull/507)++* [Remove bad `isSubmapOf` testcase](https://github.com/haskell-unordered-containers/unordered-containers/pull/504)+++ ## [0.2.20] - January 2024 * [Allow `template-haskell-2.21`](https://github.com/haskell-unordered-containers/unordered-containers/pull/484)
Data/HashMap/Internal.hs view
@@ -15,6 +15,8 @@ {-# OPTIONS_GHC -fno-full-laziness -funbox-strict-fields #-} {-# OPTIONS_HADDOCK not-home #-} +#include "MachDeps.h"+ -- | = WARNING -- -- This module is considered __internal__.@@ -125,9 +127,9 @@ , sparseIndex , two , unionArrayBy- , update32- , update32M- , update32With'+ , updateFullArray+ , updateFullArrayM+ , updateFullArrayWith' , updateOrConcatWithKey , filterMapAux , equalKeys@@ -464,7 +466,7 @@ -- | The ordering is total and consistent with the `Eq` instance. However, -- nothing else about the ordering is specified, and it may change from--- version to version of either this package or of hashable.+-- version to version of either this package or of @hashable@. instance (Ord k, Ord v) => Ord (HashMap k v) where compare = cmp compare compare @@ -830,7 +832,7 @@ !st' = go h k x (nextShift s) st in if st' `ptrEq` st then t- else Full (update32 ary i st')+ else Full (updateFullArray ary i st') where i = index h s go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith (\a _ -> (# a #)) k x v)@@ -864,7 +866,7 @@ go h k x s (Full ary) = let !st = A.index ary i !st' = go h k x (nextShift s) st- in Full (update32 ary i st')+ in Full (updateFullArray ary i st') where i = index h s go h k x s t@(Collision hy v) | h == hy = Collision h (A.snoc v (L k x))@@ -893,7 +895,7 @@ go collPos shiftedHash k x (Full ary) = let !st = A.index ary i !st' = go collPos (shiftHash shiftedHash) k x st- in Full (update32 ary i st')+ in Full (updateFullArray ary i st') where i = index' shiftedHash go collPos _shiftedHash k x (Collision h v) | collPos >= 0 = Collision h (setAtPosition collPos k x v)@@ -1041,7 +1043,7 @@ go h k s t@(Full ary) = let !st = A.index ary i !st' = go h k (nextShift s) st- ary' = update32 ary i $! st'+ ary' = updateFullArray ary i $! st' in if ptrEq st st' then t else Full ary'@@ -1270,7 +1272,7 @@ let i = index h s !st = A.index ary i !st' = go h k (nextShift s) st- ary' = update32 ary i $! st'+ ary' = updateFullArray ary i $! st' in if ptrEq st st' then t else Full ary'@@ -1554,6 +1556,9 @@ where go :: Int -> Int -> Bitmap -> Bool go !i !j !m++ -- Note: m can overflow to 0 when maxChildren == WORD_SIZE_IN_BITS. See+ -- #491. In that case there needs to be a check '| m == 0 = True' | m > b1Orb2 = True -- In case a key is both in ary1 and ary2, check ary1[i] <= ary2[j] and@@ -1660,12 +1665,12 @@ go s (Full ary1) t2 = let h2 = leafHashCode t2 i = index h2 s- ary' = update32With' ary1 i $ \st1 -> go (nextShift s) st1 t2+ ary' = updateFullArrayWith' ary1 i $ \st1 -> go (nextShift s) st1 t2 in Full ary' go s t1 (Full ary2) = let h1 = leafHashCode t1 i = index h1 s- ary' = update32With' ary2 i $ \st2 -> go (nextShift s) t1 st2+ ary' = updateFullArrayWith' ary2 i $ \st2 -> go (nextShift s) t1 st2 in Full ary' leafHashCode (Leaf h _) = h@@ -1726,9 +1731,8 @@ ------------------------------------------------------------------------ -- * Compose --- | Relate the keys of one map to the values of--- the other, by using the values of the former as keys for lookups--- in the latter.+-- | Given maps @bc@ and @ab@, relate the keys of @ab@ to the values of @bc@,+-- by using the values of @ab@ as keys for lookups in @bc@. -- -- Complexity: \( O (n * \log(m)) \), where \(m\) is the size of the first argument --@@ -2224,12 +2228,13 @@ -- ** Lists -- | \(O(n)\) Return a list of this map's elements. The list is--- produced lazily. The order of its elements is unspecified.+-- produced lazily. The order of its elements is unspecified, and it may+-- change from version to version of either this package or of @hashable@. toList :: HashMap k v -> [(k, v)] toList t = Exts.build (\ c z -> foldrWithKey (curry c) z t) {-# INLINE toList #-} --- | \(O(n)\) Construct a map with the supplied mappings. If the list+-- | \(O(n \log n)\) Construct a map with the supplied mappings. If the list -- contains duplicate mappings, the later mappings take precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = List.foldl' (\ m (k, v) -> unsafeInsert k v m) empty@@ -2406,24 +2411,24 @@ -- Manually unrolled loops -- | \(O(n)\) Update the element at the given position in this array.-update32 :: A.Array e -> Int -> e -> A.Array e-update32 ary idx b = runST (update32M ary idx b)-{-# INLINE update32 #-}+updateFullArray :: A.Array e -> Int -> e -> A.Array e+updateFullArray ary idx b = runST (updateFullArrayM ary idx b)+{-# INLINE updateFullArray #-} -- | \(O(n)\) Update the element at the given position in this array.-update32M :: A.Array e -> Int -> e -> ST s (A.Array e)-update32M ary idx b = do+updateFullArrayM :: A.Array e -> Int -> e -> ST s (A.Array e)+updateFullArrayM ary idx b = do mary <- clone ary A.write mary idx b A.unsafeFreeze mary-{-# INLINE update32M #-}+{-# INLINE updateFullArrayM #-} -- | \(O(n)\) Update the element at the given position in this array, by applying a function to it.-update32With' :: A.Array e -> Int -> (e -> e) -> A.Array e-update32With' ary idx f+updateFullArrayWith' :: A.Array e -> Int -> (e -> e) -> A.Array e+updateFullArrayWith' ary idx f | (# x #) <- A.index# ary idx- = update32 ary idx $! f x-{-# INLINE update32With' #-}+ = updateFullArray ary idx $! f x+{-# INLINE updateFullArrayWith' #-} -- | Unsafely clone an array of (2^bitsPerSubkey) elements. The length of the input -- array is not checked.@@ -2440,8 +2445,16 @@ -- | Number of bits that are inspected at each level of the hash tree. -- -- This constant is named /t/ in the original /Ideal Hash Trees/ paper.+--+-- Note that this constant is platform-dependent. On 32-bit platforms we use+-- '4', because bitmaps using '2^5' bits turned out to be prone to integer+-- overflow bugs. See #491 for instance. bitsPerSubkey :: Int+#if WORD_SIZE_IN_BITS < 64+bitsPerSubkey = 4+#else bitsPerSubkey = 5+#endif -- | The size of a 'Full' node, i.e. @2 ^ 'bitsPerSubkey'@. maxChildren :: Int
Data/HashMap/Internal/Strict.hs view
@@ -39,7 +39,7 @@ -- strings. -- -- Many operations have a average-case complexity of \(O(\log n)\). The--- implementation uses a large base (i.e. 32) so in practice these+-- implementation uses a large base (i.e. 16 or 32) so in practice these -- operations are constant time. module Data.HashMap.Internal.Strict (@@ -211,7 +211,7 @@ go h k x s (Full ary) = let st = A.index ary i st' = go h k x (nextShift s) st- ary' = HM.update32 ary i $! st'+ ary' = HM.updateFullArray ary i $! st' in Full ary' where i = index h s go h k x s t@(Collision hy v)@@ -282,7 +282,7 @@ let i = index h s st = A.index ary i st' = go h k (nextShift s) st- ary' = HM.update32 ary i $! st'+ ary' = HM.updateFullArray ary i $! st' in Full ary' go h k _ t@(Collision hy v) | h == hy = Collision h (updateWith f k v)@@ -516,12 +516,12 @@ go s (Full ary1) t2 = let h2 = leafHashCode t2 i = index h2 s- ary' = HM.update32With' ary1 i $ \st1 -> go (nextShift s) st1 t2+ ary' = HM.updateFullArrayWith' ary1 i $ \st1 -> go (nextShift s) st1 t2 in Full ary' go s t1 (Full ary2) = let h1 = leafHashCode t1 i = index h1 s- ary' = HM.update32With' ary2 i $ \st2 -> go (nextShift s) t1 st2+ ary' = HM.updateFullArrayWith' ary2 i $ \st2 -> go (nextShift s) t1 st2 in Full ary' leafHashCode (Leaf h _) = h
Data/HashMap/Lazy.hs view
@@ -20,7 +20,7 @@ -- strings. -- -- Many operations have a average-case complexity of \(O(\log n)\). The--- implementation uses a large base (i.e. 32) so in practice these+-- implementation uses a large base (i.e. 16 or 32) so in practice these -- operations are constant time. module Data.HashMap.Lazy (
Data/HashMap/Strict.hs view
@@ -19,7 +19,7 @@ -- strings. -- -- Many operations have a average-case complexity of \(O(\log n)\). The--- implementation uses a large base (i.e. 16) so in practice these+-- implementation uses a large base (i.e. 16 or 32) so in practice these -- operations are constant time. module Data.HashMap.Strict (
Data/HashSet.hs view
@@ -87,7 +87,7 @@ strings. Many operations have a average-case complexity of \(O(\log n)\). The-implementation uses a large base (i.e. 16) so in practice these+implementation uses a large base (i.e. 16 or 32) so in practice these operations are constant time. -}
Data/HashSet/Internal.hs view
@@ -37,7 +37,7 @@ -- strings. -- -- Many operations have a average-case complexity of \(O(\log n)\). The--- implementation uses a large base (i.e. 32) so in practice these+-- implementation uses a large base (i.e. 16 or 32) so in practice these -- operations are constant time. module Data.HashSet.Internal@@ -439,7 +439,8 @@ {-# INLINE filter #-} -- | \(O(n)\) Return a list of this set's elements. The list is--- produced lazily.+-- produced lazily. The order of its elements is unspecified, and it may+-- change from version to version of either this package or of @hashable@. toList :: HashSet a -> [a] toList t = Exts.build (\ c z -> foldrWithKey (const . c) z (asMap t)) {-# INLINE toList #-}
tests/Main.hs view
@@ -1,5 +1,6 @@ module Main (main) where +import GHC.IO.Encoding (setLocaleEncoding, utf8) import Test.Tasty (defaultMain, testGroup) import qualified Properties@@ -7,8 +8,10 @@ import qualified Strictness main :: IO ()-main = defaultMain $ testGroup "All"- [ Properties.tests- , Regressions.tests- , Strictness.tests- ]+main = do+ setLocaleEncoding utf8+ defaultMain $ testGroup "All"+ [ Properties.tests+ , Regressions.tests+ , Strictness.tests+ ]
tests/Properties/HashMapLazy.hs view
@@ -258,8 +258,6 @@ \(x :: HMKI) -> HM.isSubmapOf x x , testProperty "m1 ⊆ m1 ∪ m2" $ \(x :: HMKI) y -> HM.isSubmapOf x (HM.union x y)- , testProperty "m1 ⊈ m2 ⇒ m1 ∪ m2 ⊈ m1" $- \(m1 :: HMKI) m2 -> not (HM.isSubmapOf m1 m2) ==> HM.isSubmapOf m1 (HM.union m1 m2) , testProperty "m1\\m2 ⊆ m1" $ \(m1 :: HMKI) (m2 :: HMKI) -> HM.isSubmapOf (HM.difference m1 m2) m1 , testProperty "m1 ∩ m2 ≠ ∅ ⇒ m1 ⊈ m1\\m2 " $
tests/Regressions.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE BinaryLiterals #-} {-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE ScopedTypeVariables #-}@@ -26,6 +27,7 @@ import qualified Data.HashMap.Lazy as HML import qualified Data.HashMap.Strict as HMS import qualified Data.HashSet as HS+import qualified Test.Tasty as Tasty #if MIN_VERSION_base(4,12,0) -- nothunks requires base >= 4.12@@ -263,6 +265,17 @@ assert $ k2 `HS.member` s1 ------------------------------------------------------------------------+-- Issue 491++issue491 :: TestTree+issue491 = Tasty.localOption (Tasty.mkTimeout 1000000) $ testGroup "issue491" $+ [ testCase "1" $ assert $ m [0, -1] `HML.isSubmapOf` m [0, -1]+ , testCase "2" $ assert $ m [1, 0b11111] `HML.isSubmapOf` m [1, 0b11111]+ , testCase "3" $ assert $ m [0, 1] `HML.isSubmapOf` m [0, 1, 0b11111]+ ]+ where m = HS.toMap . HS.fromList @Int++------------------------------------------------------------------------ -- * Test list tests :: TestTree@@ -292,4 +305,5 @@ , testCase "issue383" issue383 #endif , testCase "issue420" issue420+ , issue491 ]
tests/Util/Key.hs view
@@ -46,6 +46,9 @@ [ (2, fromIntegral . QC.getLarge <$> arbitrary @(Large Word16)) , (1, QC.getSmall <$> arbitrary) , (1, QC.getLarge <$> arbitrary)+ -- Hashes where the lowest `maxChildren` bits are set are interesting+ -- edge cases. See #491.+ , (1, QC.elements [-1, 0xFF, 0xFFF]) ] i <- QC.frequency gens moreCollisions' <- QC.elements [moreCollisions, id]@@ -53,10 +56,11 @@ -- | Mask out most bits to produce more collisions moreCollisions :: Int -> Int-moreCollisions w = fromIntegral (w .&. mask)+moreCollisions w = fromIntegral (w .&. moreCollisionsMask) -mask :: Int-mask = sum [bit n | n <- [0, 3, 8, 14, 61]]+-- | Bitmask for @moreCollisions@+moreCollisionsMask :: Int+moreCollisionsMask = sum [bit n | n <- [0, 3, 8, 14, 61]] keyToInt :: Key -> Int keyToInt (K h x) = h * fromEnum x
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.2.20+version: 0.2.20.1 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been@@ -29,9 +29,11 @@ extra-source-files: CHANGES.md tested-with:- GHC ==9.8.1- || ==9.6.3- || ==9.4.7+ GHC ==9.12.2+ || ==9.10.2+ || ==9.8.4+ || ==9.6.7+ || ==9.4.8 || ==9.2.8 || ==9.0.2 || ==8.10.7@@ -59,8 +61,8 @@ build-depends: base >= 4.10 && < 5, deepseq >= 1.4.3,- hashable >= 1.2.5 && < 1.5,- template-haskell < 2.22+ hashable >= 1.4 && < 1.6,+ template-haskell < 2.24 default-language: Haskell2010