The Data.Array.* hierarchy is unsafe (or, Segfaulting for fun and profit)

[Iavor Diatchki]

Hello,

another option (perhaps too draconian?) would be to disallow
user-defined instances for Ix, and to ensure that the predefined
instances satisfy the required laws.  We can do this in one of the
following ways:
* Do not export 'Ix': not good because we cannot write type signatures
* Export 'Ix' but not its methods: ensures that programmers can define
only trivial (i.e. undefined) instances.
* Add a super class to 'Ix' (e.g., 'PrivateIx') which is not exported.
 This would disallow user-defined instances because they can never
satisfy the 'PrivateIx' constraint.

Perhaps such restrictions are not in the spirit of Haskell but this is
a valid point in the design space that we might want to consider.

-Iavor



On 12/6/06, Simon Marlow <simonmar at microsoft.com> wrote:
> Simon Peyton-Jones wrote:
> >>> To me, the wording "An implementation is entitled to assume..."
> >>> implies that there are no obligations on the implementation should
> >>> the assumption not hold - no obligation to yield _|_ or any other
> >>> behaviour.
> >>>
> >>>> If "laws not satisfied => any behaviour OK" were the correct
> >>>> interpretation, then it would be OK for the Array implementation to
> >>>> wipe all your files at the first encounter of a broken Ix law... ;)
> >>>
> >>> Yup.  That's not quite as bad as in C, where it's ok for an
> >>> implementation to wipe all your files if you overflow the int
> >>> type...
> >>>
> >>> Cheers,
> >>>         Simon
> >>
> >> Still, this is pretty bad, and raises questions about the safety of
> >> Haskell programs in general.  It seems unsatisfactory that if a
> >> programmer makes a mistake in the definition of an 'Ix' instance,
> >> then there are no guarantees about the behavior of their program at
> >> all...
> >
> > I rather agree with Iavor here.  If a program makes no use of
> > unsafeX functions, and has no foreign calls, and passes the
> > typechecker, then it should not crash.
>
> Yes, I agree too!  I'm just pointing out that the problem is already in the Haskell 98 specification, which we follow.  If possible we should fix this in Haskell'.
>
> > However, I don't see how to achieve this for array indexing,
> > without adding another test to every array access.
>
> If (!) was changed to be a method of IArray, then for certain arrays we could use unsafeIndex instead of index, and check the index against the physical array size instead.  Eg. (!) is currently defined as
>
>   arr ! i = case bounds arr of (l,u) -> unsafeAt arr (index (l,u) i)
>
> This would be the default method for (!), but for some arrays we could replace it by
>
>   arr ! i = case bounds arr of (l,u) -> safeAt (unsafeIndex (l,u) i)
>
> Where safeAt is implemented by looking at the physical array size.  One slight problem is that the size stored in GHC's byte arrays is rounded up to the nearest word.  Also we don't have a sizeOfArray# primitive, as Spencer pointed out in the original post in the thread.  Similar changes would be required in the MArray class too: readArray/writeArray would need to become methods.
>
> Cheers,
>         Simon
>