[swift-evolution] Add ability to validate collection indices

Haravikk swift-evolution at haravikk.me
Sun Dec 18 03:12:52 CST 2016

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161218/0e43c932/attachment.html>

More information about the swift-evolution mailing list