DefaultIndices should conform to RangeExpression

The DefaultIndices type should conform to RangeExpression (and we should encourage other implementations of indices to do so as well). This would simplify some usages. For example, you could get an NSRange for a String with NSRange(s.indices, in: s) instead of having to write NSRange(s.startIndex..<s.endIndex, in: s).


I agree, this would be really handy.

Unfortunately there's a problem as uncovered here. RangeExpression.contains should be O(1), but Collection.indices can't be: because not every value in the range is necessarily a valid index. So it has to do a full search taking worst-case O(n).

1 Like

There's also ..., which through awful syntax hackery was made to work in s[...]. If it were made into a real property that was a proper RangeExpression then you could use it in other APIs that expect a RangeExpression as well.

The problem (as @Douglas_Gregor pointed out to me recently) is that this would need to be a generic property to work with any arbitrary Bound. Not sure if there's a way to do this (assuming we overcame the problem with naming it ...).

Even then, it would still be handy to have a slice's indices be a RangeExpression for use with the outer collection. But that's a bit more niche.

1 Like

To be clear: I don't know if the complexity problem with contains rules this idea out. I'd be tempted to gloss over it. But others might feel differently.

The documentation on RangeExpression.contains(_:) doesn't indicate a complexity. I agree that it's reasonable for people to assume O(1) but it doesn't appear that we're actually guaranteeing it.

1 Like

I think RangeExpression.contains(_:) being non-O(1) is unacceptable. It'd be better to drop it from the protocol (which in practice means deprecation) than to make it possibly take linear time.

contains is there mainly to implement ~=, which was the more interesting feature (so you could use one-sided ranges in a switch – which I don't think anyone would use with indices). Maybe that should have been the requirement.

Would it make a difference if we used @_implements magic to implement RangeExpressions.contains as (startIndex...endIndex).contains to get the O(1) implementation?

Would I be correct in assuming that the only reason this would even need contains is so a default implementation of ~= can be provided?

Unfortunately, while the obvious answer here is to remove contains and simply implement ~= for each of the concrete range types, that would be a backwards-incompatible change for any third parties that have provided their own types that conform to RangeExpression.