diff options
Diffstat (limited to 'libraries/base/GHC/Arr.hs')
| -rw-r--r-- | libraries/base/GHC/Arr.hs | 326 |
1 files changed, 1 insertions, 325 deletions
diff --git a/libraries/base/GHC/Arr.hs b/libraries/base/GHC/Arr.hs index 730f2205b5..06951d3851 100644 --- a/libraries/base/GHC/Arr.hs +++ b/libraries/base/GHC/Arr.hs @@ -20,7 +20,6 @@ module GHC.Arr ( Ix(..), Array(..), STArray(..), - indexError, hopelessIndexError, arrEleBottom, array, listArray, (!), safeRangeSize, negRange, safeIndex, badSafeIndex, bounds, numElements, numElementsSTArray, indices, elems, @@ -42,340 +41,17 @@ module GHC.Arr ( unsafeFreezeSTArray, unsafeThawSTArray, ) where -import GHC.Enum import GHC.Num import GHC.ST import GHC.Base import GHC.List -import GHC.Real( fromIntegral ) +import GHC.Ix import GHC.Show infixl 9 !, // default () --- | The 'Ix' class is used to map a contiguous subrange of values in --- a type onto integers. It is used primarily for array indexing --- (see the array package). --- --- The first argument @(l,u)@ of each of these operations is a pair --- specifying the lower and upper bounds of a contiguous subrange of values. --- --- An implementation is entitled to assume the following laws about these --- operations: --- --- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@ @ @ --- --- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@ --- --- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@ @ @ --- --- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@ @ @ --- -class (Ord a) => Ix a where - {-# MINIMAL range, (index | unsafeIndex), inRange #-} - - -- | The list of values in the subrange defined by a bounding pair. - range :: (a,a) -> [a] - -- | The position of a subscript in the subrange. - index :: (a,a) -> a -> Int - -- | Like 'index', but without checking that the value is in range. - unsafeIndex :: (a,a) -> a -> Int - -- | Returns 'True' the given subscript lies in the range defined - -- the bounding pair. - inRange :: (a,a) -> a -> Bool - -- | The size of the subrange defined by a bounding pair. - rangeSize :: (a,a) -> Int - -- | like 'rangeSize', but without checking that the upper bound is - -- in range. - unsafeRangeSize :: (a,a) -> Int - - -- Must specify one of index, unsafeIndex - - -- 'index' is typically over-ridden in instances, with essentially - -- the same code, but using indexError instead of hopelessIndexError - -- Reason: we have 'Show' at the instances - {-# INLINE index #-} -- See Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = hopelessIndexError - - unsafeIndex b i = index b i - - rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1 - | otherwise = 0 -- This case is only here to - -- check for an empty range - -- NB: replacing (inRange b h) by (l <= h) fails for - -- tuples. E.g. (1,2) <= (2,1) but the range is empty - - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 - -{- -Note that the following is NOT right - rangeSize (l,h) | l <= h = index b h + 1 - | otherwise = 0 - -Because it might be the case that l<h, but the range -is nevertheless empty. Consider - ((1,2),(2,1)) -Here l<h, but the second index ranges from 2..1 and -hence is empty - - -Note [Inlining index] -~~~~~~~~~~~~~~~~~~~~~ -We inline the 'index' operation, - - * Partly because it generates much faster code - (although bigger); see #1216 - - * Partly because it exposes the bounds checks to the simplifier which - might help a big. - -If you make a per-instance index method, you may consider inlining it. - -Note [Double bounds-checking of index values] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -When you index an array, a!x, there are two possible bounds checks we might make: - - (A) Check that (inRange (bounds a) x) holds. - - (A) is checked in the method for 'index' - - (B) Check that (index (bounds a) x) lies in the range 0..n, - where n is the size of the underlying array - - (B) is checked in the top-level function (!), in safeIndex. - -Of course it *should* be the case that (A) holds iff (B) holds, but that -is a property of the particular instances of index, bounds, and inRange, -so GHC cannot guarantee it. - - * If you do (A) and not (B), then you might get a seg-fault, - by indexing at some bizarre location. #1610 - - * If you do (B) but not (A), you may get no complaint when you index - an array out of its semantic bounds. #2120 - -At various times we have had (A) and not (B), or (B) and not (A); both -led to complaints. So now we implement *both* checks (#2669). - -For 1-d, 2-d, and 3-d arrays of Int we have specialised instances to avoid this. - -Note [Out-of-bounds error messages] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -The default method for 'index' generates hoplelessIndexError, because -Ix doesn't have Show as a superclass. For particular base types we -can do better, so we override the default method for index. --} - --- Abstract these errors from the relevant index functions so that --- the guts of the function will be small enough to inline. - -{-# NOINLINE indexError #-} -indexError :: Show a => (a,a) -> a -> String -> b -indexError rng i tp - = errorWithoutStackTrace (showString "Ix{" . showString tp . showString "}.index: Index " . - showParen True (showsPrec 0 i) . - showString " out of range " $ - showParen True (showsPrec 0 rng) "") - -hopelessIndexError :: Int -- Try to use 'indexError' instead! -hopelessIndexError = errorWithoutStackTrace "Error in array index" - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix Char where - {-# INLINE range #-} - range (m,n) = [m..n] - - {-# INLINE unsafeIndex #-} - unsafeIndex (m,_n) i = fromEnum i - fromEnum m - - {-# INLINE index #-} -- See Note [Out-of-bounds error messages] - -- and Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Char" - - inRange (m,n) i = m <= i && i <= n - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix Int where - {-# INLINE range #-} - -- The INLINE stops the build in the RHS from getting inlined, - -- so that callers can fuse with the result of range - range (m,n) = [m..n] - - {-# INLINE unsafeIndex #-} - unsafeIndex (m,_n) i = i - m - - {-# INLINE index #-} -- See Note [Out-of-bounds error messages] - -- and Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Int" - - {-# INLINE inRange #-} - inRange (I# m,I# n) (I# i) = isTrue# (m <=# i) && isTrue# (i <=# n) - --- | @since 4.6.0.0 -instance Ix Word where - range (m,n) = [m..n] - unsafeIndex (m,_) i = fromIntegral (i - m) - inRange (m,n) i = m <= i && i <= n - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix Integer where - {-# INLINE range #-} - range (m,n) = [m..n] - - {-# INLINE unsafeIndex #-} - unsafeIndex (m,_n) i = fromInteger (i - m) - - {-# INLINE index #-} -- See Note [Out-of-bounds error messages] - -- and Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Integer" - - inRange (m,n) i = m <= i && i <= n - ----------------------------------------------------------------------- --- | @since 4.8.0.0 -instance Ix Natural where - range (m,n) = [m..n] - inRange (m,n) i = m <= i && i <= n - unsafeIndex (m,_) i = fromIntegral (i-m) - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Natural" - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix Bool where -- as derived - {-# INLINE range #-} - range (m,n) = [m..n] - - {-# INLINE unsafeIndex #-} - unsafeIndex (l,_) i = fromEnum i - fromEnum l - - {-# INLINE index #-} -- See Note [Out-of-bounds error messages] - -- and Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Bool" - - inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix Ordering where -- as derived - {-# INLINE range #-} - range (m,n) = [m..n] - - {-# INLINE unsafeIndex #-} - unsafeIndex (l,_) i = fromEnum i - fromEnum l - - {-# INLINE index #-} -- See Note [Out-of-bounds error messages] - -- and Note [Inlining index] - index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Ordering" - - inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u - ----------------------------------------------------------------------- --- | @since 2.01 -instance Ix () where - {-# INLINE range #-} - range ((), ()) = [()] - {-# INLINE unsafeIndex #-} - unsafeIndex ((), ()) () = 0 - {-# INLINE inRange #-} - inRange ((), ()) () = True - - {-# INLINE index #-} -- See Note [Inlining index] - index b i = unsafeIndex b i - ----------------------------------------------------------------------- --- | @since 2.01 -instance (Ix a, Ix b) => Ix (a, b) where -- as derived - {-# SPECIALISE instance Ix (Int,Int) #-} - - {-# INLINE range #-} - range ((l1,l2),(u1,u2)) = - [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] - - {-# INLINE unsafeIndex #-} - unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) = - unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2 - - {-# INLINE inRange #-} - inRange ((l1,l2),(u1,u2)) (i1,i2) = - inRange (l1,u1) i1 && inRange (l2,u2) i2 - - -- Default method for index - ----------------------------------------------------------------------- --- | @since 2.01 -instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where - {-# SPECIALISE instance Ix (Int,Int,Int) #-} - - range ((l1,l2,l3),(u1,u2,u3)) = - [(i1,i2,i3) | i1 <- range (l1,u1), - i2 <- range (l2,u2), - i3 <- range (l3,u3)] - - unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) = - unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * ( - unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * ( - unsafeIndex (l1,u1) i1)) - - inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) = - inRange (l1,u1) i1 && inRange (l2,u2) i2 && - inRange (l3,u3) i3 - - -- Default method for index - ----------------------------------------------------------------------- --- | @since 2.01 -instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where - range ((l1,l2,l3,l4),(u1,u2,u3,u4)) = - [(i1,i2,i3,i4) | i1 <- range (l1,u1), - i2 <- range (l2,u2), - i3 <- range (l3,u3), - i4 <- range (l4,u4)] - - unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) = - unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * ( - unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * ( - unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * ( - unsafeIndex (l1,u1) i1))) - - inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) = - inRange (l1,u1) i1 && inRange (l2,u2) i2 && - inRange (l3,u3) i3 && inRange (l4,u4) i4 - - -- Default method for index --- | @since 2.01 -instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where - range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) = - [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1), - i2 <- range (l2,u2), - i3 <- range (l3,u3), - i4 <- range (l4,u4), - i5 <- range (l5,u5)] - - unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) = - unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * ( - unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * ( - unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * ( - unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * ( - unsafeIndex (l1,u1) i1)))) - - inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) = - inRange (l1,u1) i1 && inRange (l2,u2) i2 && - inRange (l3,u3) i3 && inRange (l4,u4) i4 && - inRange (l5,u5) i5 - - -- Default method for index - -- | The type of immutable non-strict (boxed) arrays -- with indices in @i@ and elements in @e@. data Array i e |