containers 0.6.4.1 → 0.6.5.1

raw patch · 17 files changed

+84/−190 lines, 17 filesdep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• changelog.md +20/−1
• containers.cabal +3/−3
• src/Data/Graph.hs +2/−2
• src/Data/IntMap.hs +2/−3
• src/Data/IntMap/Internal.hs +1/−0
• src/Data/IntMap/Lazy.hs +2/−3
• src/Data/IntMap/Strict.hs +2/−3
• src/Data/IntMap/Strict/Internal.hs +4/−3
• src/Data/IntSet.hs +2/−3
• src/Data/IntSet/Internal.hs +8/−154
• src/Data/Map/Internal.hs +13/−7
• src/Data/Map/Strict/Internal.hs +2/−0
• src/Data/Sequence.hs +1/−1
• src/Data/Sequence/Internal.hs +10/−2
• src/Data/Set/Internal.hs +8/−2
• src/Data/Tree.hs +2/−1
• src/Utils/Containers/Internal/PtrEquality.hs +2/−2

@@ -1,6 +1,25 @@ # Changelog for [`containers` package](http://github.com/haskell/containers) -## [0.6.4.1]+## 0.6.5.1++### Bug fixes++* `foldr'` and `foldl'` for `Map` and `Set` are now strict everywhere they+  should be, and we have detailed tests to make sure they stay that way.+  (Thanks, coot.)++* The `Ord IntSet` instance, which was broken in the last version, has been+  repaired.++### New instance++* We now have `Ord a => Ord (Tree a)` (Thanks, Ericson2314.)++### Testing fixes++* Thanks to konsumlamm and infinity0 for various bug fixes in the test suite.++## 0.6.4.1  ### Bug fixes 

@@ -1,5 +1,5 @@ name: containers-version: 0.6.4.1+version: 0.6.5.1 license: BSD3 license-file: LICENSE maintainer: libraries@haskell.org@@ -25,7 +25,7 @@     include/containers.h     changelog.md -tested-with: GHC==8.10.1, GHC==8.8.2, 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+tested-with: GHC==9.0.1, GHC==8.10.4, GHC==8.8.4, 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  source-repository head     type:     git@@ -35,7 +35,7 @@     default-language: Haskell2010     build-depends: base >= 4.6 && < 5, array >= 0.4.0.0, deepseq >= 1.2 && < 1.5     hs-source-dirs: src-    ghc-options: -O2 -Wall+    ghc-options: -O2 -Wall -fwarn-incomplete-uni-patterns -fwarn-incomplete-record-updates      other-extensions: CPP, BangPatterns 

@@ -122,7 +122,7 @@ #else import qualified Data.Array as UA #endif-import Data.List+import qualified Data.List as L #if MIN_VERSION_base(4,9,0) import Data.Functor.Classes #endif@@ -442,7 +442,7 @@   where     max_v           = length edges0 - 1     bounds0         = (0,max_v) :: (Vertex, Vertex)-    sorted_edges    = sortBy lt edges0+    sorted_edges    = L.sortBy lt edges0     edges1          = zipWith (,) [0..] sorted_edges      graph           = array bounds0 [(,) v (mapMaybe key_vertex ks) | (,) v (_,    _, ks) <- edges1]

@@ -46,9 +46,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- -- Operation comments contain the operation time complexity in -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.

@@ -13,6 +13,7 @@ #endif  {-# OPTIONS_HADDOCK not-home #-}+{-# OPTIONS_GHC -fno-warn-incomplete-uni-patterns #-}  #include "containers.h" 

@@ -60,9 +60,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- ----------------------------------------------------------------------------- 

@@ -77,9 +77,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- ----------------------------------------------------------------------------- 

@@ -2,6 +2,8 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE PatternGuards #-} +{-# OPTIONS_GHC -fno-warn-incomplete-uni-patterns #-}+ #include "containers.h"  -----------------------------------------------------------------------------@@ -75,9 +77,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- ----------------------------------------------------------------------------- 

@@ -49,9 +49,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- -- Additionally, this implementation places bitmaps in the leaves of the tree. -- Their size is the natural size of a machine word (32 or 64 bits) and greatly

@@ -56,9 +56,8 @@ --      Workshop on ML, September 1998, pages 77-86, --      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452> -----    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve---      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),---      October 1968, pages 514-534.+--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",+--      Journal of the ACM, 15(4), October 1968, pages 514-534. -- -- Additionally, this implementation places bitmaps in the leaves of the tree. -- Their size is the natural size of a machine word (32 or 64 bits) and greatly@@ -221,7 +220,10 @@  #if __GLASGOW_HASKELL__ import qualified GHC.Exts+#if !(MIN_VERSION_base(4,8,0) && (WORD_SIZE_IN_BITS==64))+import qualified GHC.Int #endif+#endif  import qualified Data.Foldable as Foldable #if MIN_VERSION_base(4,8,0)@@ -1213,156 +1215,8 @@ --------------------------------------------------------------------}  instance Ord IntSet where-  compare Nil Nil = EQ-  compare Nil _ = LT-  compare _ Nil = GT-  compare t1@(Tip _ _) t2@(Tip _ _)-    = orderingOf $ relateTipTip t1 t2-  compare xs ys-    | (xsNeg, xsNonNeg) <- splitSign xs-    , (ysNeg, ysNonNeg) <- splitSign ys-    = case relate xsNeg ysNeg of-       Less -> LT-       Prefix -> if null xsNonNeg then LT else GT-       Equals -> orderingOf (relate xsNonNeg ysNonNeg)-       FlipPrefix -> if null ysNonNeg then GT else LT-       Greater -> GT---- | detailed outcome of lexicographic comparison of lists.--- w.r.t. Ordering, there are two extra cases,--- since (++) is not monotonic w.r.t. lex. order on lists--- (which is used by definition):--- consider comparison of  (Bin [0,3,4] [ 6] ) to  (Bin [0,3] [7] )--- where [0,3,4] > [0,3]  but [0,3,4,6] < [0,3,7].--data Relation-  = Less  -- ^ holds for [0,3,4] [0,3,5,1]-  | Prefix -- ^ holds for [0,3,4] [0,3,4,5]-  | Equals -- ^  holds for [0,3,4] [0,3,4]-  | FlipPrefix -- ^ holds for [0,3,4] [0,3]-  | Greater -- ^ holds for [0,3,4] [0,2,5]-  deriving (Show, Eq)-   -orderingOf :: Relation -> Ordering-{-# INLINE orderingOf #-}-orderingOf r = case r of-  Less -> LT-  Prefix -> LT-  Equals -> EQ-  FlipPrefix -> GT-  Greater -> GT---- | precondition: each argument is non-mixed-relate :: IntSet -> IntSet -> Relation-relate Nil Nil = Equals-relate Nil _t2 = Prefix-relate _t1 Nil = FlipPrefix-relate t1@Tip{} t2@Tip{} = relateTipTip t1 t2-relate t1@(Bin _p1 m1 l1 r1) t2@(Bin _p2 m2 l2 r2)-  | succUpperbound t1 <= lowerbound t2 = Less-  | lowerbound t1 >= succUpperbound t2 = Greater-  | otherwise = case compare (natFromInt m1) (natFromInt m2) of-      GT -> combine_left (relate l1 t2)-      EQ -> combine (relate l1 l2) (relate r1 r2)-      LT -> combine_right (relate t1 l2)-relate t1@(Bin _p1 m1 l1 _r1) t2@(Tip p2 _bm2)-  | succUpperbound t1 <= lowerbound t2 = Less-  | lowerbound t1 >= succUpperbound t2 = Greater-  | 0 == (m1 .&. p2) = combine_left (relate l1 t2)-  | otherwise = Less-relate t1@(Tip p1 _bm1) t2@(Bin _p2 m2 l2 _r2)-  | succUpperbound t1 <= lowerbound t2 = Less-  | lowerbound t1 >= succUpperbound t2 = Greater-  | 0 == (p1 .&. m2) = combine_right (relate t1 l2)-  | otherwise = Greater--relateTipTip :: IntSet -> IntSet -> Relation-{-# INLINE relateTipTip #-}-relateTipTip (Tip p1 bm1) (Tip p2 bm2) = case compare p1 p2 of-  LT -> Less-  EQ -> relateBM bm1 bm2-  GT -> Greater-relateTipTip _ _ = error "relateTipTip"--relateBM :: BitMap -> BitMap -> Relation-{-# inline relateBM #-}-relateBM w1 w2 | w1 == w2 = Equals-relateBM w1 w2 =-  let delta = xor w1 w2-      lowest_diff_mask = delta .&. complement (delta-1)-      prefix = (complement lowest_diff_mask + 1)-            .&. (complement lowest_diff_mask)-  in  if 0 == lowest_diff_mask .&. w1-      then if 0 == w1 .&. prefix-           then Prefix else Greater-      else if 0 == w2 .&. prefix-           then FlipPrefix else Less---- | This function has the property--- relate t1@(Bin p m l1 r1) t2@(Bin p m l2 r2) = combine (relate l1 l2) (relate r1 r2)--- It is important that `combine` is lazy in the second argument (achieved by inlining)-combine :: Relation -> Relation -> Relation-{-# inline combine #-}-combine r eq = case r of-      Less -> Less-      Prefix -> Greater-      Equals -> eq-      FlipPrefix -> Less-      Greater -> Greater---- | This function has the property--- relate t1@(Bin p1 m1 l1 r1) t2 = combine_left (relate l1 t2)--- under the precondition that the range of l1 contains the range of t2,--- and r1 is non-empty-combine_left :: Relation -> Relation-{-# inline combine_left #-}-combine_left r = case r of-      Less -> Less-      Prefix -> Greater-      Equals -> FlipPrefix-      FlipPrefix -> FlipPrefix-      Greater -> Greater---- | This function has the property--- relate t1 t2@(Bin p2 m2 l2 r2) = combine_right (relate t1 l2)--- under the precondition that the range of t1 is included in the range of l2,--- and r2 is non-empty-combine_right :: Relation -> Relation-{-# inline combine_right #-}-combine_right r = case r of-      Less -> Less-      Prefix -> Prefix-      Equals -> Prefix-      FlipPrefix -> Less-      Greater -> Greater---- | shall only be applied to non-mixed non-Nil trees-lowerbound :: IntSet -> Int-{-# INLINE lowerbound #-}-lowerbound Nil = error "lowerbound: Nil"-lowerbound (Tip p _) = p-lowerbound (Bin p _ _ _) = p---- | this is one more than the actual upper bound (to save one operation)--- shall only be applied to non-mixed non-Nil trees-succUpperbound :: IntSet -> Int-{-# INLINE succUpperbound #-}-succUpperbound Nil = error "succUpperbound: Nil"-succUpperbound (Tip p _) = p + wordSize -succUpperbound (Bin p m _ _) = p + shiftR m 1---- | split a set into subsets of negative and non-negative elements-splitSign :: IntSet -> (IntSet,IntSet)-{-# INLINE splitSign #-}-splitSign t@(Tip kx _)-  | kx >= 0 = (Nil, t)-  | otherwise = (t, Nil)-splitSign t@(Bin p m l r)-  -- m < 0 is the usual way to find out if we have positives and negatives (see findMax)-  | m < 0 = (r, l)-  | p < 0 = (t, Nil)-  | otherwise = (Nil, t)-splitSign Nil = (Nil, Nil)+    compare s1 s2 = compare (toAscList s1) (toAscList s2)+    -- tentative implementation. See if more efficient exists.  {--------------------------------------------------------------------   Show@@ -1642,7 +1496,7 @@ ----------------------------------------------------------------------}  indexOfTheOnlyBit bitmask =-  GHC.Exts.I# (lsbArray `GHC.Exts.indexInt8OffAddr#` unboxInt (intFromNat ((bitmask * magic) `shiftRL` offset)))+  fromIntegral (GHC.Int.I8# (lsbArray `GHC.Exts.indexInt8OffAddr#` unboxInt (intFromNat ((bitmask * magic) `shiftRL` offset))))   where unboxInt (GHC.Exts.I# i) = i #if WORD_SIZE_IN_BITS==32         magic = 0x077CB531

@@ -1155,6 +1155,8 @@ -- > let f _ = Just "c" -- > alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")] -- > alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]+--+-- Note that @'adjust' = alter . fmap@.  -- See Note: Type of local 'go' function alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a@@ -3272,8 +3274,8 @@ foldr' :: (a -> b -> b) -> b -> Map k a -> b foldr' f z = go z   where-    go !z' Tip             = z'-    go z' (Bin _ _ x l r) = go (f x (go z' r)) l+    go !z' Tip            = z'+    go z' (Bin _ _ x l r) = go (f x $! go z' r) l {-# INLINE foldr' #-}  -- | /O(n)/. Fold the values in the map using the given left-associative@@ -3298,8 +3300,10 @@ foldl' :: (a -> b -> a) -> a -> Map k b -> a foldl' f z = go z   where-    go !z' Tip             = z'-    go z' (Bin _ _ x l r) = go (f (go z' l) x) r+    go !z' Tip            = z'+    go z' (Bin _ _ x l r) =+      let !z'' = go z' l+      in go (f z'' x) r {-# INLINE foldl' #-}  -- | /O(n)/. Fold the keys and values in the map using the given right-associative@@ -3326,7 +3330,7 @@ foldrWithKey' f z = go z   where     go !z' Tip              = z'-    go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l+    go z' (Bin _ kx x l r) = go (f kx x $! go z' r) l {-# INLINE foldrWithKey' #-}  -- | /O(n)/. Fold the keys and values in the map using the given left-associative@@ -3352,8 +3356,10 @@ foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a foldlWithKey' f z = go z   where-    go !z' Tip              = z'-    go z' (Bin _ kx x l r) = go (f (go z' l) kx x) r+    go !z' Tip             = z'+    go z' (Bin _ kx x l r) =+      let !z'' = go z' l+      in go (f z'' kx x) r {-# INLINE foldlWithKey' #-}  -- | /O(n)/. Fold the keys and values in the map using the given monoid, such that

@@ -795,6 +795,8 @@ -- > let f _ = Just "c" -- > alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")] -- > alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]+--+-- Note that @'adjust' = alter . fmap@.  -- See Map.Internal.Note: Type of local 'go' function alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a

@@ -297,7 +297,7 @@ shift2Right :: Seq a -> Seq a -> (Seq a, Seq a) shift2Right Empty ys = (Empty, ys) shift2Right (Empty :|> x) ys = (Empty, x :<| ys)-shift2Right (xs :|> x1 :|> x2) = (xs, x1 :<| x2 :<| ys)+shift2Right (xs :|> x1 :|> x2) ys = (xs, x1 :<| x2 :<| ys) @  @

@@ -17,6 +17,7 @@ {-# LANGUAGE PatternGuards #-}  {-# OPTIONS_HADDOCK not-home #-}+{-# OPTIONS_GHC -fno-warn-incomplete-uni-patterns #-}  ----------------------------------------------------------------------------- -- |@@ -201,7 +202,6 @@     null, length, lookup, take, drop, splitAt, foldl, foldl1, foldr, foldr1,     scanl, scanl1, scanr, scanr1, replicate, zip, zipWith, zip3, zipWith3,     unzip, takeWhile, dropWhile, iterate, reverse, filter, mapM, sum, all)-import qualified Data.List import Control.Applicative (Applicative(..), (<$>), (<**>),  Alternative,                             liftA2, liftA3) import qualified Control.Applicative as Applicative@@ -211,7 +211,12 @@ import Data.Functor (Functor(..)) import Utils.Containers.Internal.State (State(..), execState) import Data.Foldable (Foldable(foldl, foldl1, foldr, foldr1, foldMap, foldl', foldr'), toList)+import qualified Data.Foldable as F +#if !(__GLASGOW_HASKELL__ >= 708)+import qualified Data.List+#endif+ #if MIN_VERSION_base(4,9,0) import qualified Data.Semigroup as Semigroup import Data.Functor.Classes@@ -523,7 +528,7 @@     EmptyR -> fmap firstf xs     Seq fs''FT :> lastf -> case rigidify xsFT of          RigidEmpty -> empty-         RigidOne (Elem x) -> fmap ($x) fs+         RigidOne (Elem x) -> fmap ($ x) fs          RigidTwo (Elem x1) (Elem x2) ->             Seq $ ap2FT firstf fs''FT lastf (x1, x2)          RigidThree (Elem x1) (Elem x2) (Elem x3) ->@@ -2191,6 +2196,9 @@     fmap f (x :< xs)    = f x :< fmap f xs  instance Foldable ViewL where+    foldMap _ EmptyL = mempty+    foldMap f (x :< xs) = f x <> foldMap f xs+     foldr _ z EmptyL = z     foldr f z (x :< xs) = f x (foldr f z xs) 

@@ -850,6 +850,10 @@   Difference --------------------------------------------------------------------} -- | /O(m*log(n\/m + 1)), m <= n/. Difference of two sets.+--+-- Return elements of the first set not existing in the second set.+--+-- > difference (fromList [5, 3]) (fromList [5, 7]) == singleton 3 difference :: Ord a => Set a -> Set a -> Set a difference Tip _   = Tip difference t1 Tip  = t1@@ -987,7 +991,7 @@ foldr' f z = go z   where     go !z' Tip           = z'-    go z' (Bin _ x l r) = go (f x (go z' r)) l+    go z' (Bin _ x l r) = go (f x $! go z' r) l {-# INLINE foldr' #-}  -- | /O(n)/. Fold the elements in the set using the given left-associative@@ -1010,7 +1014,9 @@ foldl' f z = go z   where     go !z' Tip           = z'-    go z' (Bin _ x l r) = go (f (go z' l) x) r+    go z' (Bin _ x l r) =+      let !z'' = go z' l+      in go (f z'' x) r {-# INLINE foldl' #-}  {--------------------------------------------------------------------

@@ -97,6 +97,7 @@     } #ifdef __GLASGOW_HASKELL__   deriving ( Eq+           , Ord -- ^ @since 0.6.5            , Read            , Show            , Data@@ -104,7 +105,7 @@            , Generic1 -- ^ @since 0.5.8            ) #else-  deriving (Eq, Read, Show)+  deriving (Eq, Ord, Read, Show) #endif  -- | This type synonym exists primarily for historical

@@ -14,7 +14,7 @@ #if __GLASGOW_HASKELL__ < 707 import GHC.Exts ( (==#) ) #else-import GHC.Exts ( isTrue# )+import GHC.Exts ( Int#, isTrue# ) #endif #endif @@ -35,7 +35,7 @@ hetPtrEq x y = unsafeCoerce reallyUnsafePtrEquality# x y ==# 1# #else ptrEq x y = isTrue# (reallyUnsafePtrEquality# x y)-hetPtrEq x y = isTrue# (unsafeCoerce reallyUnsafePtrEquality# x y)+hetPtrEq x y = isTrue# (unsafeCoerce (reallyUnsafePtrEquality# :: x -> x -> Int#) x y) #endif  #else