base: Move Ix typeclass to GHC.Ix
authorBen Gamari <ben@smart-cactus.org>
Mon, 16 Sep 2019 14:51:08 +0000 (10:51 -0400)
committerMarge Bot <ben+marge-bot@smart-cactus.org>
Wed, 25 Sep 2019 17:55:09 +0000 (13:55 -0400)
The `Ix` class seems rather orthogonal to its original home in
`GHC.Arr`.

13 files changed:
compiler/prelude/PrelNames.hs
libraries/base/Data/Functor/Const.hs
libraries/base/Data/Functor/Identity.hs
libraries/base/Data/Ix.hs
libraries/base/Data/Ord.hs
libraries/base/GHC/Arr.hs
libraries/base/GHC/Generics.hs
libraries/base/GHC/Ix.hs [new file with mode: 0644]
libraries/base/GHC/Unicode.hs
libraries/base/GHC/Word.hs
libraries/base/base.cabal
testsuite/tests/deriving/should_compile/T14682.stderr
testsuite/tests/ghci/scripts/ghci064.stdout

index a889f70..2acb2a0 100644 (file)
@@ -504,7 +504,7 @@ gHC_PRIM, gHC_TYPES, gHC_GENERICS, gHC_MAGIC,
     gHC_LIST, gHC_TUPLE, dATA_TUPLE, dATA_EITHER, dATA_STRING,
     dATA_FOLDABLE, dATA_TRAVERSABLE,
     gHC_CONC, gHC_IO, gHC_IO_Exception,
-    gHC_ST, gHC_ARR, gHC_STABLE, gHC_PTR, gHC_ERR, gHC_REAL,
+    gHC_ST, gHC_IX, gHC_STABLE, gHC_PTR, gHC_ERR, gHC_REAL,
     gHC_FLOAT, gHC_TOP_HANDLER, sYSTEM_IO, dYNAMIC,
     tYPEABLE, tYPEABLE_INTERNAL, gENERICS,
     rEAD_PREC, lEX, gHC_INT, gHC_WORD, mONAD, mONAD_FIX, mONAD_ZIP, mONAD_FAIL,
@@ -540,7 +540,7 @@ gHC_CONC        = mkBaseModule (fsLit "GHC.Conc")
 gHC_IO          = mkBaseModule (fsLit "GHC.IO")
 gHC_IO_Exception = mkBaseModule (fsLit "GHC.IO.Exception")
 gHC_ST          = mkBaseModule (fsLit "GHC.ST")
-gHC_ARR         = mkBaseModule (fsLit "GHC.Arr")
+gHC_IX          = mkBaseModule (fsLit "GHC.Ix")
 gHC_STABLE      = mkBaseModule (fsLit "GHC.Stable")
 gHC_PTR         = mkBaseModule (fsLit "GHC.Ptr")
 gHC_ERR         = mkBaseModule (fsLit "GHC.Err")
@@ -750,11 +750,11 @@ succ_RDR                = varQual_RDR gHC_ENUM (fsLit "succ")
 pred_RDR                = varQual_RDR gHC_ENUM (fsLit "pred")
 minBound_RDR            = varQual_RDR gHC_ENUM (fsLit "minBound")
 maxBound_RDR            = varQual_RDR gHC_ENUM (fsLit "maxBound")
-range_RDR               = varQual_RDR gHC_ARR (fsLit "range")
-inRange_RDR             = varQual_RDR gHC_ARR (fsLit "inRange")
-index_RDR               = varQual_RDR gHC_ARR (fsLit "index")
-unsafeIndex_RDR         = varQual_RDR gHC_ARR (fsLit "unsafeIndex")
-unsafeRangeSize_RDR     = varQual_RDR gHC_ARR (fsLit "unsafeRangeSize")
+range_RDR               = varQual_RDR gHC_IX (fsLit "range")
+inRange_RDR             = varQual_RDR gHC_IX (fsLit "inRange")
+index_RDR               = varQual_RDR gHC_IX (fsLit "index")
+unsafeIndex_RDR         = varQual_RDR gHC_IX (fsLit "unsafeIndex")
+unsafeRangeSize_RDR     = varQual_RDR gHC_IX (fsLit "unsafeRangeSize")
 
 readList_RDR, readListDefault_RDR, readListPrec_RDR, readListPrecDefault_RDR,
     readPrec_RDR, parens_RDR, choose_RDR, lexP_RDR, expectP_RDR :: RdrName
@@ -1214,7 +1214,7 @@ rationalToDoubleName = varQual gHC_FLOAT (fsLit "rationalToDouble") rationalToDo
 
 -- Class Ix
 ixClassName :: Name
-ixClassName = clsQual gHC_ARR (fsLit "Ix") ixClassKey
+ixClassName = clsQual gHC_IX (fsLit "Ix") ixClassKey
 
 -- Typeable representation types
 trModuleTyConName
index 4e4992d..651041f 100644 (file)
@@ -25,7 +25,7 @@ import Data.Bits (Bits, FiniteBits)
 import Data.Foldable (Foldable(foldMap))
 import Foreign.Storable (Storable)
 
-import GHC.Arr (Ix)
+import GHC.Ix (Ix)
 import GHC.Base
 import GHC.Enum (Bounded, Enum)
 import GHC.Float (Floating, RealFloat)
index daaa3a4..0709393 100644 (file)
@@ -41,7 +41,7 @@ import Data.Coerce
 import Data.Foldable
 import Data.Functor.Utils ((#.))
 import Foreign.Storable (Storable)
-import GHC.Arr (Ix)
+import GHC.Ix (Ix)
 import GHC.Base ( Applicative(..), Eq(..), Functor(..), Monad(..)
                 , Semigroup, Monoid, Ord(..), ($), (.) )
 import GHC.Enum (Bounded, Enum)
index 0171431..79f0805 100644 (file)
@@ -61,4 +61,4 @@ module Data.Ix
 
     ) where
 
-import GHC.Arr
+import GHC.Ix
index 4ccfa7c..8703c7b 100644 (file)
@@ -25,7 +25,7 @@ module Data.Ord (
 
 import Data.Bits (Bits, FiniteBits)
 import Foreign.Storable (Storable)
-import GHC.Arr (Ix)
+import GHC.Ix (Ix)
 import GHC.Base
 import GHC.Enum (Bounded, Enum)
 import GHC.Float (Floating, RealFloat)
index 730f220..06951d3 100644 (file)
@@ -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
index 0492464..56fca9b 100644 (file)
@@ -736,7 +736,7 @@ import GHC.Ptr     ( Ptr )
 import GHC.Types
 
 -- Needed for instances
-import GHC.Arr     ( Ix )
+import GHC.Ix      ( Ix )
 import GHC.Base    ( Alternative(..), Applicative(..), Functor(..)
                    , Monad(..), MonadPlus(..), NonEmpty(..), String, coerce
                    , Semigroup(..), Monoid(..) )
diff --git a/libraries/base/GHC/Ix.hs b/libraries/base/GHC/Ix.hs
new file mode 100644 (file)
index 0000000..efd6467
--- /dev/null
@@ -0,0 +1,348 @@
+{-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples #-}
+{-# OPTIONS_HADDOCK not-home #-}
+
+-----------------------------------------------------------------------------
+-- |
+-- Module      :  GHC.Ix
+-- Copyright   :  (c) The University of Glasgow, 1994-2000
+-- License     :  see libraries/base/LICENSE
+--
+-- Maintainer  :  cvs-ghc@haskell.org
+-- Stability   :  internal
+-- Portability :  non-portable (GHC extensions)
+--
+-- GHC\'s Ix typeclass implementation.
+--
+-----------------------------------------------------------------------------
+
+module GHC.Ix (
+        Ix(..)
+    ) where
+
+import GHC.Enum
+import GHC.Num
+import GHC.Base
+import GHC.Real( fromIntegral )
+import GHC.Show
+
+-- | 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
index d6f3ecc..9d11b37 100644 (file)
@@ -34,7 +34,7 @@ import GHC.Base
 import GHC.Char        (chr)
 import GHC.Real
 import GHC.Enum ( Enum (..), Bounded (..) )
-import GHC.Arr ( Ix (..) )
+import GHC.Ix ( Ix (..) )
 import GHC.Num
 
 -- Data.Char.chr already imports this and we need to define a Show instance
index dcd9e16..b19e6a3 100644 (file)
@@ -57,7 +57,7 @@ import GHC.Base
 import GHC.Enum
 import GHC.Num
 import GHC.Real
-import GHC.Arr
+import GHC.Ix
 import GHC.Show
 
 ------------------------------------------------------------------------
index da018d2..d08b625 100644 (file)
@@ -258,6 +258,7 @@ Library
         GHC.IOArray
         GHC.IORef
         GHC.Int
+        GHC.Ix
         GHC.List
         GHC.Maybe
         GHC.MVar
index 7656c9c..59fc405 100644 (file)
@@ -18,7 +18,7 @@ Derived class instances:
                      <a1, Language.Haskell.TH.Syntax.lift a1>]
     Language.Haskell.TH.Syntax.liftTyped (T14682.Foo a1 a2)
       = [|| T14682.Foo a1 a2 ||]
-
+  
   instance Data.Data.Data T14682.Foo where
     Data.Data.gfoldl k z (T14682.Foo a1 a2)
       = ((z T14682.Foo `k` a1) `k` a2)
@@ -54,22 +54,22 @@ Derived class instances:
     (GHC.Classes.>) a b = (GHC.Classes.<) b a
     (GHC.Classes.>=) a b = GHC.Classes.not ((GHC.Classes.<) a b)
   
-  instance GHC.Arr.Ix T14682.Foo where
-    GHC.Arr.range (T14682.Foo a1 a2, T14682.Foo b1 b2)
+  instance GHC.Ix.Ix T14682.Foo where
+    GHC.Ix.range (T14682.Foo a1 a2, T14682.Foo b1 b2)
       = [T14682.Foo c1 c2 |
-           c1 <- GHC.Arr.range (a1, b1), c2 <- GHC.Arr.range (a2, b2)]
-    GHC.Arr.unsafeIndex
+           c1 <- GHC.Ix.range (a1, b1), c2 <- GHC.Ix.range (a2, b2)]
+    GHC.Ix.unsafeIndex
       (T14682.Foo a1 a2, T14682.Foo b1 b2)
       (T14682.Foo c1 c2)
-      = (GHC.Arr.unsafeIndex (a2, b2) c2
+      = (GHC.Ix.unsafeIndex (a2, b2) c2
            GHC.Num.+
-             (GHC.Arr.unsafeRangeSize (a2, b2)
-                GHC.Num.* GHC.Arr.unsafeIndex (a1, b1) c1))
-    GHC.Arr.inRange
+             (GHC.Ix.unsafeRangeSize (a2, b2)
+                GHC.Num.* GHC.Ix.unsafeIndex (a1, b1) c1))
+    GHC.Ix.inRange
       (T14682.Foo a1 a2, T14682.Foo b1 b2)
       (T14682.Foo c1 c2)
-      = (GHC.Arr.inRange (a1, b1) c1
-           GHC.Classes.&& GHC.Arr.inRange (a2, b2) c2)
+      = (GHC.Ix.inRange (a1, b1) c1
+           GHC.Classes.&& GHC.Ix.inRange (a2, b2) c2)
   
   T14682.$con2tag_B4iUvrAY4wB3YczpMJQUOX ::
     T14682.Foo -> GHC.Prim.Int#
@@ -175,19 +175,19 @@ GHC.Classes.Ord [T14682.Foo]
 
 
 ==================== Filling in method body ====================
-GHC.Arr.Ix [T14682.Foo]
-  GHC.Arr.index = GHC.Arr.$dmindex @(T14682.Foo)
+GHC.Ix.Ix [T14682.Foo]
+  GHC.Ix.index = GHC.Ix.$dmindex @(T14682.Foo)
 
 
 
 ==================== Filling in method body ====================
-GHC.Arr.Ix [T14682.Foo]
-  GHC.Arr.rangeSize = GHC.Arr.$dmrangeSize @(T14682.Foo)
+GHC.Ix.Ix [T14682.Foo]
+  GHC.Ix.rangeSize = GHC.Ix.$dmrangeSize @(T14682.Foo)
 
 
 
 ==================== Filling in method body ====================
-GHC.Arr.Ix [T14682.Foo]
-  GHC.Arr.unsafeRangeSize = GHC.Arr.$dmunsafeRangeSize @(T14682.Foo)
+GHC.Ix.Ix [T14682.Foo]
+  GHC.Ix.unsafeRangeSize = GHC.Ix.$dmunsafeRangeSize @(T14682.Foo)
 
 
index 9129815..e3fe5a9 100644 (file)
@@ -38,7 +38,7 @@ instance Show Bool -- Defined in ‘GHC.Show’
 instance Read Bool -- Defined in ‘GHC.Read’
 instance Bounded Bool -- Defined in ‘GHC.Enum’
 instance GHC.Generics.Generic Bool -- Defined in ‘GHC.Generics’
-instance GHC.Arr.Ix Bool -- Defined in ‘GHC.Arr
+instance GHC.Ix.Ix Bool -- Defined in ‘GHC.Ix
 instance GHC.Generics.SingKind Bool -- Defined in ‘GHC.Generics’
 instance Data.Bits.Bits Bool -- Defined in ‘Data.Bits’
 instance Data.Bits.FiniteBits Bool -- Defined in ‘Data.Bits’