[Pre-proposal] Enforcing Correct use of Array Indices


(Haravikk) #1

So the issue of Array index safety came up on the discussion for the .indexed() proposal. Now of course there's nothing wrong with arrays using integers as indices as such, but it does mean that indices can be manipulated outside of the array, which somewhat defeats the idea of the indexing model requiring them to be passed back to the parent collection for manipulation.

In a few types of my own I've avoided this problem by doing the following:

public struct MyMaskedIndex : Comparable { fileprivate var raw:Int }
// Comparable conformance omitted

public struct MyType : Collection {
    // Lots of stuff omitted
    public func distance(from start:MyMaskedIndex, to end:MyMaskedIndex) -> Int {
        return end.raw - start.raw;
    }
}

In essence MaskedIndex is still just an Int, and should optimise as such, but in development the use of a type like this ensures that indices from my collection can't be manipulated externally, which enables the type-checker to conveniently prevent any mistakes I might make. It's a handy pattern for other things like hashed values, ensuring I can't use unhashed values of the same type by accident and so-on.

I just wanted to raise the topic to see what other people thought about the idea of doing something similar for Array and any other types that use integer types directly as indices? For convenience it is still possible to have a public initialiser on the masking type(s), so that custom values can be used, but by using MaskedIndex(raw:) it should be much more obvious what's happening.

Feedback welcome!


(Dave Abrahams) #2

So the issue of Array index safety came up on the discussion for the
.indexed() proposal. Now of course there's nothing wrong with arrays
using integers as indices as such, but it does mean that indices can
be manipulated outside of the array, which somewhat defeats the idea
of the indexing model requiring them to be passed back to the parent
collection for manipulation.

In a few types of my own I've avoided this problem by doing the
following:

public struct MyMaskedIndex : Comparable { fileprivate var raw:Int }
// Comparable conformance omitted

public struct MyType : Collection {
    // Lots of stuff omitted
    public func distance(from start:MyMaskedIndex, to
end:MyMaskedIndex) -> Int {
        return end.raw - start.raw;
    }
}

In essence MaskedIndex is still just an Int, and should optimise as
such, but in development the use of a type like this ensures that
indices from my collection can't be manipulated externally, which
enables the type-checker to conveniently prevent any mistakes I might
make. It's a handy pattern for other things like hashed values,
ensuring I can't use unhashed values of the same type by accident and
so-on.

Yeah, but it doesn't really ensure you won't use an invalid index.
Among many other things, you can always reset the collection to an empty
state and all the old indices become invalid with respect to it.

I just wanted to raise the topic to see what other people thought
about the idea of doing something similar for Array and any other
types that use integer types directly as indices? For convenience it
is still possible to have a public initialiser on the masking type(s),
so that custom values can be used, but by using MaskedIndex(raw:) it
should be much more obvious what's happening.

Believe me, we considered this when doing the Array design. Being able
to index an Array with Ints is pretty fundamental to its usability and
adoptability, and wrapping the index doesn't buy any real safety.

···

on Thu Sep 29 2016, Haravikk <swift-evolution@swift.org> wrote:

--
-Dave


(Haravikk) #3

It certainly doesn't solve all the problems, but then it really is just intended to avoid the simple mistake of manipulating the index externally; like I say, the wrapped value should optimise away (since all it is is an Int in reality), and if it's given a public constructor then a person can still do external manipulation if they must, they just have to be explicit about it.

The idea is literally just to let the type-checker catch some simple, but easy to make, errors that purpose-made index types like DictionaryIndex aren't vulnerable to.

···

On 30 Sep 2016, at 13:10, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Thu Sep 29 2016, Haravikk <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

So the issue of Array index safety came up on the discussion for the
.indexed() proposal. Now of course there's nothing wrong with arrays
using integers as indices as such, but it does mean that indices can
be manipulated outside of the array, which somewhat defeats the idea
of the indexing model requiring them to be passed back to the parent
collection for manipulation.

In a few types of my own I've avoided this problem by doing the
following:

public struct MyMaskedIndex : Comparable { fileprivate var raw:Int }
// Comparable conformance omitted

public struct MyType : Collection {
   // Lots of stuff omitted
   public func distance(from start:MyMaskedIndex, to
end:MyMaskedIndex) -> Int {
       return end.raw - start.raw;
   }
}

In essence MaskedIndex is still just an Int, and should optimise as
such, but in development the use of a type like this ensures that
indices from my collection can't be manipulated externally, which
enables the type-checker to conveniently prevent any mistakes I might
make. It's a handy pattern for other things like hashed values,
ensuring I can't use unhashed values of the same type by accident and
so-on.

Yeah, but it doesn't really ensure you won't use an invalid index.
Among many other things, you can always reset the collection to an empty
state and all the old indices become invalid with respect to it.

I just wanted to raise the topic to see what other people thought
about the idea of doing something similar for Array and any other
types that use integer types directly as indices? For convenience it
is still possible to have a public initialiser on the masking type(s),
so that custom values can be used, but by using MaskedIndex(raw:) it
should be much more obvious what's happening.

Believe me, we considered this when doing the Array design. Being able
to index an Array with Ints is pretty fundamental to its usability and
adoptability, and wrapping the index doesn't buy any real safety.


(Dave Abrahams) #4

Yes, I understand. You asked what “people thought;” I was saying we
thought about it and explaining the rationale for our choice. The
benefits don't seem to outweigh the costs.

···

on Mon Oct 03 2016, Haravikk <swift-evolution@swift.org> wrote:

On 30 Sep 2016, at 13:10, Dave Abrahams via swift-evolution >> <swift-evolution@swift.org> wrote:
on Thu Sep 29 2016, Haravikk >> <swift-evolution@swift.org >> <mailto:swift-evolution@swift.org>> > >> wrote:

So the issue of Array index safety came up on the discussion for the
.indexed() proposal. Now of course there's nothing wrong with arrays
using integers as indices as such, but it does mean that indices can
be manipulated outside of the array, which somewhat defeats the idea
of the indexing model requiring them to be passed back to the parent
collection for manipulation.

In a few types of my own I've avoided this problem by doing the
following:

public struct MyMaskedIndex : Comparable { fileprivate var raw:Int }
// Comparable conformance omitted

public struct MyType : Collection {
   // Lots of stuff omitted
   public func distance(from start:MyMaskedIndex, to
end:MyMaskedIndex) -> Int {
       return end.raw - start.raw;
   }
}

In essence MaskedIndex is still just an Int, and should optimise as
such, but in development the use of a type like this ensures that
indices from my collection can't be manipulated externally, which
enables the type-checker to conveniently prevent any mistakes I might
make. It's a handy pattern for other things like hashed values,
ensuring I can't use unhashed values of the same type by accident and
so-on.

Yeah, but it doesn't really ensure you won't use an invalid index.
Among many other things, you can always reset the collection to an empty
state and all the old indices become invalid with respect to it.

I just wanted to raise the topic to see what other people thought
about the idea of doing something similar for Array and any other
types that use integer types directly as indices? For convenience it
is still possible to have a public initialiser on the masking type(s),
so that custom values can be used, but by using MaskedIndex(raw:) it
should be much more obvious what's happening.

Believe me, we considered this when doing the Array design. Being able
to index an Array with Ints is pretty fundamental to its usability and
adoptability, and wrapping the index doesn't buy any real safety.

It certainly doesn't solve all the problems, but then it really is
just intended to avoid the simple mistake of manipulating the index
externally; like I say, the wrapped value should optimise away (since
all it is is an Int in reality), and if it's given a public
constructor then a person can still do external manipulation if they
must, they just have to be explicit about it.

The idea is literally just to let the type-checker catch some simple,
but easy to make, errors that purpose-made index types like
DictionaryIndex aren't vulnerable to.

--
-Dave