X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FArr.lhs;h=ade0b984d9d79efdfc0c4ad338f96c5ff627910f;hb=8073392a94dc5ab198e4758d6738a0c7f5ed68cf;hp=9e52c71097aad0e104c768266294b9797c631e78;hpb=297d7e3e4ce4950125fd4b6e3bff9d7f6afbfbc6;p=ghc-base.git

diff --git a/GHC/Arr.lhs b/GHC/Arr.lhs
index 9e52c71..ade0b98 100644
--- a/GHC/Arr.lhs
+++ b/GHC/Arr.lhs
@@ -1,5 +1,8 @@
 \begin{code}
-{-# OPTIONS_GHC -fno-implicit-prelude #-}
+{-# LANGUAGE NoImplicitPrelude, NoBangPatterns, MagicHash, UnboxedTuples #-}
+{-# OPTIONS_GHC -funbox-strict-fields #-}
+{-# OPTIONS_HADDOCK hide #-}
+
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  GHC.Arr
@@ -17,7 +20,6 @@
 -- #hide
 module GHC.Arr where
 
-import {-# SOURCE #-} GHC.Err ( error )
 import GHC.Enum
 import GHC.Num
 import GHC.ST
@@ -32,15 +34,15 @@ default ()
 
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{The @Ix@ class}
-%*							*
+%*                                                      *
 %*********************************************************
 
 \begin{code}
 -- | 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 "Data.Array", "Data.Array.IArray" and "Data.Array.MArray").
+-- (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.
@@ -48,66 +50,116 @@ default ()
 -- An implementation is entitled to assume the following laws about these
 -- operations:
 --
--- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@
+-- * @'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]@
+-- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@ @ @
 --
--- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@
+-- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@ @ @
 --
 -- Minimal complete instance: 'range', 'index' and 'inRange'.
 --
 class (Ord a) => Ix a where
     -- | The list of values in the subrange defined by a bounding pair.
-    range		:: (a,a) -> [a]
+    range               :: (a,a) -> [a]
     -- | The position of a subscript in the subrange.
-    index		:: (a,a) -> a -> Int
+    index               :: (a,a) -> a -> Int
     -- | Like 'index', but without checking that the value is in range.
-    unsafeIndex		:: (a,a) -> a -> Int
+    unsafeIndex         :: (a,a) -> a -> Int
     -- | Returns 'True' the given subscript lies in the range defined
     -- the bounding pair.
-    inRange		:: (a,a) -> a -> Bool
+    inRange             :: (a,a) -> a -> Bool
     -- | The size of the subrange defined by a bounding pair.
-    rangeSize		:: (a,a) -> Int
+    rangeSize           :: (a,a) -> Int
     -- | like 'rangeSize', but without checking that the upper bound is
     -- in range.
-    --
-    -- As long as you don't override the default 'rangeSize', you can
-    -- specify 'unsafeRangeSize' as follows, to speed up some operations:
-    --
-    -- >  unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-    --
     unsafeRangeSize     :: (a,a) -> Int
 
-	-- Must specify one of index, unsafeIndex
-    index b i | inRange b i = unsafeIndex b i
-	      | otherwise   = error "Error in array index"
+        -- 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
+                       | 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
 \end{code}
 
 Note that the following is NOT right
-	rangeSize (l,h) | l <= h    = index b h + 1
-			| otherwise = 0
+        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))
+        ((1,2),(2,1))
 Here l<h, but the second index ranges from 2..1 and
 hence is empty
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{Instances of @Ix@}
-%*							*
+%*                                                      *
 %*********************************************************
 
+Note [Inlining index]
+~~~~~~~~~~~~~~~~~~~~~
+We inline the 'index' operation, 
+
+ * Partly because it generates much faster code 
+   (although bigger); see Trac #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.  Trac #1610
+
+ * If you do (B) but not (A), you may get no complaint when you index
+   an array out of its semantic bounds.  Trac #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 (Trac #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.
+
 \begin{code}
--- abstract these errors from the relevant index functions so that
+-- Abstract these errors from the relevant index functions so that
 -- the guts of the function will be small enough to inline.
 
 {-# NOINLINE indexError #-}
@@ -115,8 +167,11 @@ indexError :: Show a => (a,a) -> a -> String -> b
 indexError rng i tp
   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
            showParen True (showsPrec 0 i) .
-	   showString " out of range " $
-	   showParen True (showsPrec 0 rng) "")
+           showString " out of range " $
+           showParen True (showsPrec 0 rng) "")
+
+hopelessIndexError :: Int -- Try to use 'indexError' instead!
+hopelessIndexError = error "Error in array index"
 
 ----------------------------------------------------------------------
 instance  Ix Char  where
@@ -126,31 +181,31 @@ instance  Ix Char  where
     {-# 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"
+              | otherwise   =  indexError b i "Char"
 
-    inRange (m,n) i	=  m <= i && i <= n
-
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
+    inRange (m,n) i     =  m <= i && i <= n
 
 ----------------------------------------------------------------------
 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
+        -- 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"
+              | otherwise   =  indexError b i "Int"
 
     {-# INLINE inRange #-}
     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
 ----------------------------------------------------------------------
 instance  Ix Integer  where
     {-# INLINE range #-}
@@ -159,12 +214,12 @@ instance  Ix Integer  where
     {-# 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
+              | otherwise   =  indexError b i "Integer"
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
+    inRange (m,n) i     =  m <= i && i <= n
 
 ----------------------------------------------------------------------
 instance Ix Bool where -- as derived
@@ -174,13 +229,13 @@ instance Ix Bool where -- as derived
     {-# 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"
+              | otherwise   =  indexError b i "Bool"
 
     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
 ----------------------------------------------------------------------
 instance Ix Ordering where -- as derived
     {-# INLINE range #-}
@@ -189,13 +244,13 @@ instance Ix Ordering where -- as derived
     {-# 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"
+              | otherwise   =  indexError b i "Ordering"
 
     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
 ----------------------------------------------------------------------
 instance Ix () where
     {-# INLINE range #-}
@@ -204,29 +259,26 @@ instance Ix () where
     unsafeIndex   ((), ()) () = 0
     {-# INLINE inRange #-}
     inRange ((), ()) () = True
-    {-# INLINE index #-}
-    index b i = unsafeIndex b i
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
+    {-# INLINE index #-}  -- See Note [Inlining index]
+    index b i = unsafeIndex b i
 
 ----------------------------------------------------------------------
 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
     {-# SPECIALISE instance Ix (Int,Int) #-}
 
-    {- INLINE range #-}
+    {-# INLINE range #-}
     range ((l1,l2),(u1,u2)) =
       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 
-    {- INLINE unsafeIndex #-}
+    {-# INLINE unsafeIndex #-}
     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 
-    {- INLINE inRange #-}
+    {-# INLINE inRange #-}
     inRange ((l1,l2),(u1,u2)) (i1,i2) =
       inRange (l1,u1) i1 && inRange (l2,u2) i2
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
     -- Default method for index
 
 ----------------------------------------------------------------------
@@ -247,8 +299,6 @@ instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
       inRange (l3,u3) i3
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
     -- Default method for index
 
 ----------------------------------------------------------------------
@@ -269,8 +319,6 @@ instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
       inRange (l3,u3) i3 && inRange (l4,u4) i4
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
     -- Default method for index
 
 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
@@ -293,15 +341,13 @@ instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
       inRange (l3,u3) i3 && inRange (l4,u4) i4 && 
       inRange (l5,u5) i5
 
-    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
     -- Default method for index
 \end{code}
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{The @Array@ types}
-%*							*
+%*                                                      *
 %*********************************************************
 
 \begin{code}
@@ -309,7 +355,13 @@ type IPr = (Int, Int)
 
 -- | The type of immutable non-strict (boxed) arrays
 -- with indices in @i@ and elements in @e@.
-data Ix i => Array     i e = Array   !i !i (Array# e)
+data Array i e
+         = Array !i         -- the lower bound, l
+                 !i         -- the upper bound, u
+                 !Int       -- a cache of (rangeSize (l,u))
+                            -- used to make sure an index is
+                            -- really in range
+                 (Array# e) -- The actual elements
 
 -- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type
 -- arguments are as follows:
@@ -320,21 +372,27 @@ data Ix i => Array     i e = Array   !i !i (Array# e)
 --
 --  * @e@: the element type of the array.
 --
-data         STArray s i e = STArray !i !i (MutableArray# s e)
-	-- No Ix context for STArray.  They are stupid,
-	-- and force an Ix context on the equality instance.
+data STArray s i e
+         = STArray !i                  -- the lower bound, l
+                   !i                  -- the upper bound, u
+                   !Int                -- a cache of (rangeSize (l,u))
+                                       -- used to make sure an index is
+                                       -- really in range
+                   (MutableArray# s e) -- The actual elements
+        -- No Ix context for STArray.  They are stupid,
+        -- and force an Ix context on the equality instance.
 
 -- Just pointer equality on mutable arrays:
 instance Eq (STArray s i e) where
-    STArray _ _ arr1# == STArray _ _ arr2# =
+    STArray _ _ _ arr1# == STArray _ _ _ arr2# =
         sameMutableArray# arr1# arr2#
 \end{code}
 
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{Operations on immutable arrays}
-%*							*
+%*                                                      *
 %*********************************************************
 
 \begin{code}
@@ -354,7 +412,7 @@ arrEleBottom = error "(Array.!): undefined array element"
 --
 -- Because the indices must be checked for these errors, 'array' is
 -- strict in the bounds argument and in the indices of the association
--- list, but nonstrict in the values.  Thus, recurrences such as the
+-- list, but non-strict in the values.  Thus, recurrences such as the
 -- following are possible:
 --
 -- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
@@ -369,38 +427,48 @@ arrEleBottom = error "(Array.!): undefined array element"
 -- with which the array was constructed.
 {-# INLINE array #-}
 array :: Ix i
-	=> (i,i)	-- ^ a pair of /bounds/, each of the index type
-			-- of the array.  These bounds are the lowest and
-			-- highest indices in the array, in that order.
-			-- For example, a one-origin vector of length
-			-- '10' has bounds '(1,10)', and a one-origin '10'
-			-- by '10' matrix has bounds '((1,1),(10,10))'.
-	-> [(i, e)]	-- ^ a list of /associations/ of the form
-			-- (/index/, /value/).  Typically, this list will
-			-- be expressed as a comprehension.  An
-			-- association '(i, x)' defines the value of
-			-- the array at index 'i' to be 'x'.
-	-> Array i e
-array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
+        => (i,i)        -- ^ a pair of /bounds/, each of the index type
+                        -- of the array.  These bounds are the lowest and
+                        -- highest indices in the array, in that order.
+                        -- For example, a one-origin vector of length
+                        -- '10' has bounds '(1,10)', and a one-origin '10'
+                        -- by '10' matrix has bounds '((1,1),(10,10))'.
+        -> [(i, e)]     -- ^ a list of /associations/ of the form
+                        -- (/index/, /value/).  Typically, this list will
+                        -- be expressed as a comprehension.  An
+                        -- association '(i, x)' defines the value of
+                        -- the array at index 'i' to be 'x'.
+        -> Array i e
+array (l,u) ies
+    = let n = safeRangeSize (l,u)
+      in unsafeArray' (l,u) n
+                      [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 
 {-# INLINE unsafeArray #-}
 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
-unsafeArray (l,u) ies = runST (ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
-    case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
-    foldr (fill marr#) (done l u marr#) ies s2# }})
+unsafeArray b ies = unsafeArray' b (rangeSize b) ies
+
+{-# INLINE unsafeArray' #-}
+unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
+unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
+    case newArray# n# arrEleBottom s1# of
+        (# s2#, marr# #) ->
+            foldr (fill marr#) (done l u n marr#) ies s2#)
 
 {-# INLINE fill #-}
 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
-fill marr# (I# i#, e) next s1# =
-    case writeArray# marr# i# e s1#     of { s2# ->
-    next s2# }
+-- NB: put the \s after the "=" so that 'fill' 
+--     inlines when applied to three args 
+fill marr# (I# i#, e) next 
+ = \s1# -> case writeArray# marr# i# e s1# of 
+             s2# -> next s2# 
 
 {-# INLINE done #-}
-done :: Ix i => i -> i -> MutableArray# s e -> STRep s (Array i e)
-done l u marr# s1# =
-    case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
-    (# s2#, Array l u arr# #) }
+done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
+-- See NB on 'fill'
+done l u n marr# 
+  = \s1# -> case unsafeFreezeArray# marr# s1# of
+              (# s2#, arr# #) -> (# s2#, Array l u n arr# #)
 
 -- This is inefficient and I'm not sure why:
 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
@@ -413,7 +481,7 @@ done l u marr# s1# =
 {-# INLINE listArray #-}
 listArray :: Ix i => (i,i) -> [e] -> Array i e
 listArray (l,u) es = runST (ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
+    case safeRangeSize (l,u)            of { n@(I# n#) ->
     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
     let fillFromList i# xs s3# | i# ==# n# = s3#
                                | otherwise = case xs of
@@ -421,41 +489,82 @@ listArray (l,u) es = runST (ST $ \s1# ->
             y:ys -> case writeArray# marr# i# y s3# of { s4# ->
                     fillFromList (i# +# 1#) ys s4# } in
     case fillFromList 0# es s2#         of { s3# ->
-    done l u marr# s3# }}})
+    done l u n marr# s3# }}})
 
 -- | The value at the given index in an array.
 {-# INLINE (!) #-}
 (!) :: Ix i => Array i e -> i -> e
-arr@(Array l u _) ! i = unsafeAt arr (index (l,u) i)
+arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
+
+{-# INLINE safeRangeSize #-}
+safeRangeSize :: Ix i => (i, i) -> Int
+safeRangeSize (l,u) = let r = rangeSize (l, u)
+                      in if r < 0 then negRange
+                                  else r
+
+-- Don't inline this error message everywhere!!
+negRange :: Int	  -- Uninformative, but Ix does not provide Show
+negRange = error "Negative range size"
+
+{-# INLINE[1] safeIndex #-}
+-- See Note [Double bounds-checking of index values]
+-- Inline *after* (!) so the rules can fire
+safeIndex :: Ix i => (i, i) -> Int -> i -> Int
+safeIndex (l,u) n i = let i' = index (l,u) i
+                      in if (0 <= i') && (i' < n)
+                         then i'
+                         else badSafeIndex i' n
+
+-- See Note [Double bounds-checking of index values]
+{-# RULES
+"safeIndex/I"       safeIndex = lessSafeIndex :: (Int,Int) -> Int -> Int -> Int
+"safeIndex/(I,I)"   safeIndex = lessSafeIndex :: ((Int,Int),(Int,Int)) -> Int -> (Int,Int) -> Int
+"safeIndex/(I,I,I)" safeIndex = lessSafeIndex :: ((Int,Int,Int),(Int,Int,Int)) -> Int -> (Int,Int,Int) -> Int
+  #-}
+
+lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int
+-- See Note [Double bounds-checking of index values]
+-- Do only (A), the semantic check
+lessSafeIndex (l,u) _ i = index (l,u) i  
+
+-- Don't inline this long error message everywhere!!
+badSafeIndex :: Int -> Int -> Int
+badSafeIndex i' n = error ("Error in array index; " ++ show i' ++
+                        " not in range [0.." ++ show n ++ ")")
 
 {-# INLINE unsafeAt #-}
 unsafeAt :: Ix i => Array i e -> Int -> e
-unsafeAt (Array _ _ arr#) (I# i#) =
+unsafeAt (Array _ _ _ arr#) (I# i#) =
     case indexArray# arr# i# of (# e #) -> e
 
 -- | The bounds with which an array was constructed.
 {-# INLINE bounds #-}
 bounds :: Ix i => Array i e -> (i,i)
-bounds (Array l u _) = (l,u)
+bounds (Array l u _ _) = (l,u)
+
+-- | The number of elements in the array.
+{-# INLINE numElements #-}
+numElements :: Ix i => Array i e -> Int
+numElements (Array _ _ n _) = n
 
 -- | The list of indices of an array in ascending order.
 {-# INLINE indices #-}
 indices :: Ix i => Array i e -> [i]
-indices (Array l u _) = range (l,u)
+indices (Array l u _ _) = range (l,u)
 
 -- | The list of elements of an array in index order.
 {-# INLINE elems #-}
 elems :: Ix i => Array i e -> [e]
-elems arr@(Array l u _) =
-    [unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
+elems arr@(Array _ _ n _) =
+    [unsafeAt arr i | i <- [0 .. n - 1]]
 
 -- | The list of associations of an array in index order.
 {-# INLINE assocs #-}
 assocs :: Ix i => Array i e -> [(i, e)]
-assocs arr@(Array l u _) =
-    [(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
+assocs arr@(Array l u _ _) =
+    [(i, arr ! i) | i <- range (l,u)]
 
--- | The 'accumArray' deals with repeated indices in the association
+-- | The 'accumArray' function deals with repeated indices in the association
 -- list using an /accumulating function/ which combines the values of
 -- associations with the same index.
 -- For example, given a list of values of some index type, @hist@
@@ -471,27 +580,34 @@ assocs arr@(Array l u _) =
 -- not in general be recursive.
 {-# INLINE accumArray #-}
 accumArray :: Ix i
-	=> (e -> a -> e)	-- ^ accumulating function
-	-> e			-- ^ initial value
-	-> (i,i)		-- ^ bounds of the array
-	-> [(i, a)]		-- ^ association list
-	-> Array i e
-accumArray f init (l,u) ies =
-    unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
+        => (e -> a -> e)        -- ^ accumulating function
+        -> e                    -- ^ initial value
+        -> (i,i)                -- ^ bounds of the array
+        -> [(i, a)]             -- ^ association list
+        -> Array i e
+accumArray f initial (l,u) ies =
+    let n = safeRangeSize (l,u)
+    in unsafeAccumArray' f initial (l,u) n
+                         [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 
 {-# INLINE unsafeAccumArray #-}
 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
-unsafeAccumArray f init (l,u) ies = runST (ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
-    case newArray# n# init s1#          of { (# s2#, marr# #) ->
-    foldr (adjust f marr#) (done l u marr#) ies s2# }})
+unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
+
+{-# INLINE unsafeAccumArray' #-}
+unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
+unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
+    case newArray# n# initial s1#          of { (# s2#, marr# #) ->
+    foldr (adjust f marr#) (done l u n marr#) ies s2# })
 
 {-# INLINE adjust #-}
 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
-adjust f marr# (I# i#, new) next s1# =
-    case readArray# marr# i# s1#        of { (# s2#, old #) ->
-    case writeArray# marr# i# (f old new) s2# of { s3# ->
-    next s3# }}
+-- See NB on 'fill'
+adjust f marr# (I# i#, new) next
+  = \s1# -> case readArray# marr# i# s1# of
+        	(# s2#, old #) ->
+        	    case writeArray# marr# i# (f old new) s2# of
+        	        s3# -> next s3#
 
 -- | Constructs an array identical to the first argument except that it has
 -- been updated by the associations in the right argument.
@@ -506,14 +622,14 @@ adjust f marr# (I# i#, new) next s1# =
 -- but GHC's implementation uses the last association for each index.
 {-# INLINE (//) #-}
 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
-arr@(Array l u _) // ies =
-    unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies]
+arr@(Array l u n _) // ies =
+    unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 
 {-# INLINE unsafeReplace #-}
 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
-unsafeReplace arr@(Array l u _) ies = runST (do
-    STArray _ _ marr# <- thawSTArray arr
-    ST (foldr (fill marr#) (done l u marr#) ies))
+unsafeReplace arr ies = runST (do
+    STArray l u n marr# <- thawSTArray arr
+    ST (foldr (fill marr#) (done l u n marr#) ies))
 
 -- | @'accum' f@ takes an array and an association list and accumulates
 -- pairs from the list into the array with the accumulating function @f@.
@@ -523,19 +639,19 @@ unsafeReplace arr@(Array l u _) ies = runST (do
 --
 {-# INLINE accum #-}
 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
-accum f arr@(Array l u _) ies =
-    unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies]
+accum f arr@(Array l u n _) ies =
+    unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 
 {-# INLINE unsafeAccum #-}
 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
-unsafeAccum f arr@(Array l u _) ies = runST (do
-    STArray _ _ marr# <- thawSTArray arr
-    ST (foldr (adjust f marr#) (done l u marr#) ies))
+unsafeAccum f arr ies = runST (do
+    STArray l u n marr# <- thawSTArray arr
+    ST (foldr (adjust f marr#) (done l u n marr#) ies))
 
 {-# INLINE amap #-}
 amap :: Ix i => (a -> b) -> Array i a -> Array i b
-amap f arr@(Array l u _) =
-    unsafeArray (l,u) [(i, f (unsafeAt arr i)) | i <- [0 .. rangeSize (l,u) - 1]]
+amap f arr@(Array l u n _) =
+    unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]
 
 -- | 'ixmap' allows for transformations on array indices.
 -- It may be thought of as providing function composition on the right
@@ -546,14 +662,14 @@ amap f arr@(Array l u _) =
 {-# INLINE ixmap #-}
 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
 ixmap (l,u) f arr =
-    unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
+    array (l,u) [(i, arr ! f i) | i <- range (l,u)]
 
 {-# INLINE eqArray #-}
 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
-eqArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
-    if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else
+eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
+    if n1 == 0 then n2 == 0 else
     l1 == l2 && u1 == u2 &&
-    and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]]
+    and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
 
 {-# INLINE cmpArray #-}
 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
@@ -561,13 +677,14 @@ cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 
 {-# INLINE cmpIntArray #-}
 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
-cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
-    if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else
-    if rangeSize (l2,u2) == 0 then GT else
-    case compare l1 l2 of
-        EQ    -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1]
-        other -> other
-    where
+cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
+    if n1 == 0 then
+        if n2 == 0 then EQ else LT
+    else if n2 == 0 then GT
+    else case compare l1 l2 of
+             EQ    -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
+             other -> other
+  where
     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
         EQ    -> rest
         other -> other
@@ -577,9 +694,9 @@ cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
 
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{Array instances}
-%*							*
+%*                                                      *
 %*********************************************************
 
 \begin{code}
@@ -599,16 +716,16 @@ instance (Ix a, Show a, Show b) => Show (Array a b) where
         showsPrec appPrec1 (bounds a) .
         showChar ' ' .
         showsPrec appPrec1 (assocs a)
-	-- Precedence of 'array' is the precedence of application
+        -- Precedence of 'array' is the precedence of application
 
 -- The Read instance is in GHC.Read
 \end{code}
 
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{Operations on mutable arrays}
-%*							*
+%*                                                      *
 %*********************************************************
 
 Idle ADR question: What's the tradeoff here between flattening these
@@ -627,48 +744,51 @@ might be different, though.
 \begin{code}
 {-# INLINE newSTArray #-}
 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
-newSTArray (l,u) init = ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
-    case newArray# n# init s1#          of { (# s2#, marr# #) ->
-    (# s2#, STArray l u marr# #) }}
+newSTArray (l,u) initial = ST $ \s1# ->
+    case safeRangeSize (l,u)            of { n@(I# n#) ->
+    case newArray# n# initial s1#       of { (# s2#, marr# #) ->
+    (# s2#, STArray l u n marr# #) }}
 
 {-# INLINE boundsSTArray #-}
 boundsSTArray :: STArray s i e -> (i,i)  
-boundsSTArray (STArray l u _) = (l,u)
+boundsSTArray (STArray l u _ _) = (l,u)
+
+{-# INLINE numElementsSTArray #-}
+numElementsSTArray :: STArray s i e -> Int
+numElementsSTArray (STArray _ _ n _) = n
 
 {-# INLINE readSTArray #-}
 readSTArray :: Ix i => STArray s i e -> i -> ST s e
-readSTArray marr@(STArray l u _) i =
-    unsafeReadSTArray marr (index (l,u) i)
+readSTArray marr@(STArray l u n _) i =
+    unsafeReadSTArray marr (safeIndex (l,u) n i)
 
 {-# INLINE unsafeReadSTArray #-}
 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
-unsafeReadSTArray (STArray _ _ marr#) (I# i#) = ST $ \s1# ->
-    readArray# marr# i# s1#
+unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
+    = ST $ \s1# -> readArray# marr# i# s1#
 
 {-# INLINE writeSTArray #-}
 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s () 
-writeSTArray marr@(STArray l u _) i e =
-    unsafeWriteSTArray marr (index (l,u) i) e
+writeSTArray marr@(STArray l u n _) i e =
+    unsafeWriteSTArray marr (safeIndex (l,u) n i) e
 
 {-# INLINE unsafeWriteSTArray #-}
 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s () 
-unsafeWriteSTArray (STArray _ _ marr#) (I# i#) e = ST $ \s1# ->
-    case writeArray# marr# i# e s1#     of { s2# ->
-    (# s2#, () #) }
+unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
+    case writeArray# marr# i# e s1# of
+        s2# -> (# s2#, () #)
 \end{code}
 
 
 %*********************************************************
-%*							*
+%*                                                      *
 \subsection{Moving between mutable and immutable}
-%*							*
+%*                                                      *
 %*********************************************************
 
 \begin{code}
 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
-freezeSTArray (STArray l u marr#) = ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
+freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
     let copy i# s3# | i# ==# n# = s3#
                     | otherwise =
@@ -677,17 +797,16 @@ freezeSTArray (STArray l u marr#) = ST $ \s1# ->
             copy (i# +# 1#) s5# }} in
     case copy 0# s2#                    of { s3# ->
     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
-    (# s4#, Array l u arr# #) }}}}
+    (# s4#, Array l u n arr# #) }}}
 
 {-# INLINE unsafeFreezeSTArray #-}
 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
-unsafeFreezeSTArray (STArray l u marr#) = ST $ \s1# ->
+unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
-    (# s2#, Array l u arr# #) }
+    (# s2#, Array l u n arr# #) }
 
 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
-thawSTArray (Array l u arr#) = ST $ \s1# ->
-    case rangeSize (l,u)                of { I# n# ->
+thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
     let copy i# s3# | i# ==# n# = s3#
                     | otherwise =
@@ -695,11 +814,11 @@ thawSTArray (Array l u arr#) = ST $ \s1# ->
             case writeArray# marr# i# e s3# of { s4# ->
             copy (i# +# 1#) s4# }} in
     case copy 0# s2#                    of { s3# ->
-    (# s3#, STArray l u marr# #) }}}
+    (# s3#, STArray l u n marr# #) }}
 
 {-# INLINE unsafeThawSTArray #-}
 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
-unsafeThawSTArray (Array l u arr#) = ST $ \s1# ->
+unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
-    (# s2#, STArray l u marr# #) }
+    (# s2#, STArray l u n marr# #) }
 \end{code}