Hi everyone, I've encountered a problem when trying to optimize a generic algorithm and was a bit stuck when I had to adapt an implementation detail to whether my generic type conformed to more restrictive protocol or not. In python, a simple if isinstance(self, class) would solve the issue, but I didn't find any equivalent in swift.
The problem
Playing around with generic algorithms (in this case quickselect), I had to gather the last accessible index of a Collection. It is easy and cheap if the collection conforms to BidirectionalCollection by using
let lastIndex = index(before: endIndex)
(inside an extension on Collection). It is also easy in the general case (though O(n)) by doing something like
let lastIndex = indices.max()!
The problem is that I did not find a way to implement this so that it's O(n) in the general case (fair enough), but falls back to something that is O(1) when the collection happens to be bidirectional (which is often the case in practice). You can always use
let lastIndex = return index(endIndex, offsetBy: -1)
and the compiler is happy, but it crashes at runtime if you use it on a collection that is not bidirectional with:
Fatal error: Only BidirectionalCollections can be advanced by a negative amount
Defining different extensions for Collection and BidirectionalCollection such as:
extension BidirectionalCollection {
public func lastIndex() -> Index {
print("BidirectionalCollection implementation")
return index(endIndex, offsetBy: -1)
}
}
extension Collection {
public func lastIndex() -> Index {
print("Collection implementation")
return indices.max()!
}
}
may seem like it works, but as soon as you use that in a context more generic, it fails:
extension Collection {
func findLastIndex() -> Index { return lastIndex() }
}
will never use the BidirectionalCollection implementation. The only way to get this to work is if lastIndex was a protocol requirement, which would mean change the Collection protocol.
Pitch
Having some way to check at dispatch if the type on which we are writing an extension conforms to additional protocol would be very helpful to adjust the implementation to be the most efficient it can be. For instance, in this case, if we had a test like Self is BidirectionalCollection we could write something like:
var lastIndex: Index = startIndex
if Self is BidirectionalCollection {
lastIndex = return index(endIndex, offsetBy: -1)
} else {
lastIndex = indices.max()!
}
or even shorter
let lastIndex = (Self is BidirectionalCollection) ? index(endIndex, offsetBy: -1) : indices.max()!
or any other kind of syntax that would help know if Self conforms to BidirectionalCollection.
Please let me know if I missed anything and there is already something in the language to do this.