[swift-evolution] Add ability to validate collection indices

[Haravikk]

> On 18 Dec 2016, at 10:04, Rien <Rien at balancingrock.nl> wrote:
> 
> Solutions that work only part of the time will raise expectations of the user only to crush hem later when they fail.
> It will likely generate a number of “bug” reports that must then be explained.
> 
> I would suggest that functionality like this should only be applied to custom types, never on the build-in types.
> 
> Regards,
> Rien

It's not so much that it only works part of the time, but more that in situations where the "link" would be broken we would need to issue a warning, which could get annoying given that currently we have no way to suppress these.

This is why I stopped working on it as there's a lot of details to hammer out; I do think it's feasible, but there's a lot to consider. For example, indices could be treated in a manner similar to non-escaping closures, in that you can't store or pass them in any way that would break this link to the parent, unless you use a keyword or attribute to explicitly handle them in an "unsafe" way.

So it's not so much that it only works "part of the time", but rather that it relies on a type of inference, and needs some way to correctly (and usefully) handle situations where that inference can't be performed, which is why I put it to one side as it was taking up too much time.

If I ever do have more time I might put up a more formal thread to discuss it properly; I do think it's feasible, and possible to make it work well in most common cases, the question mark is just how best to handle those cases where either more data is needed, or the warning needs to be overridden somehow.

>> On 18 Dec 2016, at 10:12, Haravikk via swift-evolution <swift-evolution at swift.org> wrote:
>>> On 16 Dec 2016, at 14:51, Anton Zhilin via swift-evolution <swift-evolution at swift.org> wrote:
>>> It will be impossible without huge additional overhead.
>>> I assume that "invalidated" means "no more points to that element".
>>> 
>>> Consider that an element is inserted in the middle of an Array.
>>> Assuming enough capacity, all iterators after that one will be invalidated.
>>> But all new iterators pointing to the same spots will be valid.
>>> How do you differentiate between the "old" ones and the "new" ones?
>>> 
>>> I see only one general approach to this:
>>> 1. Make iterator type a class
>>> 2. Add to the collection, an array of all iterators, which have been created (and are being used)
>>> 3. Add a "valid" flag to iterator
>>> 4. On most operations on the collection, it will walk through its iterators, marking some as "invalid".
>>> 
>>> It's a safe way to eliminate some "out of bounds" errors, but it's just utterly rediculous.
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> There was one idea I was exploring but never quite came up with a final design for, which would be the ability for types to "tag" and invalidate values that they return.
>> 
>> In essence, a collection might return an index and tag it as "indices", and a later call to remove, add etc. might invalidate all values tagged as "indices", and provide some guidance on what to do about it. The Swift compiler will make a best effort to track these tags to provide warnings.
>> 
>> I was thinking something like this (heavily cut down):
>> 
>> 	struct Foo : Collection {
>> 		func index(_ i:Index, offsetBy n:IndexDistance) -> Index @tag("indices") { return i + n }
>> 		@invalidates("indices") func remove(at:Index) { /* Remove an element */ }
>> 	}
>> 
>> 	var foo = Foo()
>> 	let index = foo.index(foo.startIndex, offsetBy: 5)
>> 	foo.remove(at: index) // This is fine
>> 	foo.remove(at: index) // Warning: indices of foo have been invalidated
>> 
>> In other words, the variable index is linked (in the compiler, not at run-time) to the type instance that created it by the specified tag "indices". Now, when that type invalidates "indices" that variable is effectively marked as invalid, thus any attempt to use it will produce a warning that it may no longer be valid. Of course in the case of simple indices it should be fine, though technically speaking you're still doing something that could still fail at runtime.
>> 
>> The idea here is that, in the simpler cases at least, the compiler gains some awareness of index invalidation, allowing us to potentially avoid run-time errors entirely; naturally it gets more complex if the indices are passed around, but as long as it is still possible to track where they came from (e.g- if it's a collection held by a class reference) then it can still work. This feature could also be used to detect use of an index for the wrong type or instance; i.e- if two instances have the same index type, indices may not be compatible between the two, currently mixing and matching them isn't a compiler error, but can fail unexpectedly at runtime, though there's probably a simpler solution to that specific case (e.g- some way to make the type checker to treat their indices as if they were different types).