Arrays allow out-of-bounds indexes

[amthrax]

The array changes proposed and recently implemented for ticket #1610 (Make arrays safer) strengthened the requirements on Ix instances, but weakened the requirements on array users. Specifically, array referencing now permits indexes that are not inRange.

For example,

import Data.Array.IArray

b :: Array (Int,Int) Int
b = listArray ((0,0), (3,3)) (repeat 0)

main = do
  print (b ! (0,5))              -- SHOULD fail, but doesn't
  print (index (bounds b) (0,5)) -- DOES fail

The first line in main should fail because the specified index is not inRange, but doesn't because the (!) operator (specifically Data.Array.Base.safeIndex) now uses unsafeIndex and simply checks that the resulting index is within the linearized bounds of the array. In this case, the unsafe index of (0,5) wraps aroung to the index of (1,1).

A simple fix would be to use index instead of unsafeIndex in the implementation of Data.Array.Base.safeIndex. This would both require the user to use in-bounds references and would require Ix instances to return in-bounds indexes.

[igloo]

When fixing #1046 and #1610, some people were worried about the performance overhead of checking both that the index was within the range (in terms of the Ix class), and also that we were looking for a value within the real range (i.e. offset in [0..rangeSize)).

We used to do just the first check, which meant that you could access memory that you shouldn't with a funky Ix instance. Now we do just the second check, meaning if you ask for an out-of-range index then you might successfully get a value back.

Would you like to make a  proposal for doing both checks?

[igloo]

See also:  http://www.haskell.org/pipermail/haskell-cafe/2008-March/040598.html

[guest]

This is not my Haskell! Checks must be done completely by default. It should be possible however to turn them off by a compiler switch.

[simonmar]

It's not always necessary to do both checks, for example it suffices to do the second check for ordinary one-dimensional integral indices. So perhaps the cost of doing this properly won't be so bad.

Moving this to the 6.12 milestone - it was the GHC project that broke it, so we should fix it again :-)

[igloo]

See also #2669.

[simonpj]

Triggered by this thread  http://www.haskell.org/pipermail/haskell-cafe/2009-June/063399.html, I had quick look.

There are two range tests under discussion

• One tests every index supplied by the client of the array, against the original bounds. We should never leave this test out.
• The other tests the Int offset computed by index, in case the Ix instance for this type is bogus. We can omit this check iff we trust the instance.

The only safe thing to do (and Haskell is supposed to be a safe language) is to do both checks, thus (in GHC.Arr):

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 error "Error in array index"

(Note the use of index rather than unsafeIndex.) To avoid the double test in the (wildly common) cases of indexing using the (trusted) built-in instances for Int, (Int,Int) etc, we could use a RULE to call version of safeIndex that did only one test.

Furthermore, we should improve the "Error in array index" error message. If we have the first client-oriented test in place, then this second error can read something like "The index method for an Ix instance returned offset N, but the array has size M". I don't see how to say which type, sadly. Typeable is not a superclass of Ix.

Simon

[simonpj]

I'll change this to high priority to make sure we get to it for 6.12. Simon

[igloo]

Fixed by these patches in array and base:

Sun Jul 19 16:29:31 BST 2009  Ian Lynagh <igloo@earth.li>
  * Improve the index checking for array accesses; fixes #2120 #2669
  As well as checking that offset we are reading is actually inside the
  array, we now also check that it is "in range" as defined by the Ix
  instance. This fixes confusing behaviour (#2120) and improves some error
  messages (#2669).

Sun Jul 19 16:32:28 BST 2009  Ian Lynagh <igloo@earth.li>
  * Improve the index checking for array accesses; fixes #2120 #2669
  As well as checking that offset we are reading is actually inside the
  array, we now also check that it is "in range" as defined by the Ix
  instance. This fixes confusing behaviour (#2120) and improves some error
  messages (#2669).