[swift-dev] Associated type inference fun with RandomAccessCollection

[Douglas Gregor]

Sent from my iPhone

> On Nov 7, 2016, at 7:07 PM, Mark Lacey <mark.lacey at apple.com> wrote:
> 
> 
>> On Nov 7, 2016, at 6:16 PM, Douglas Gregor via swift-dev <swift-dev at swift.org> wrote:
>> 
>> Hi all,
>> 
>> While working on the type checker, I came across an interesting case for associated type inference with the ‘Indices’ type of RandomAccessCollection. At issue is a simple model of RandomAccessCollection where the Index type is Int:
>> 
>> class ReferenceCollection : RandomAccessCollection {
>>   typealias Index = Int
>>   
>>   var startIndex: Int {
>>     return 0
>>   }
>> 
>>   var endIndex: Int {
>>     return 1
>>   }
>> 
>>   subscript(index: Int) -> String {
>>     return ""
>>   }
>> 
>>   func index(after i: Int) -> Int {
>>     return 1
>>   }
>> 
>>   func index(before i: Int) -> Int {
>>     return 0
>>   }
>> }
>> 
>> What’s the inferred associated Indices? The RandomAccessIterator protocol has a default:
>> 
>> protocol RandomAccessCollection {
>>     associatedtype Indices : _RandomAccessIndexable, BidirectionalCollection
>>       = DefaultRandomAccessIndices<Self>
>>     var indices: Indices { get }
>> }
>> 
>> which will kick in if nothing else can be inferred. There is also an implementation for this defaulted case in a protocol extension from which we can infer Indices:
>> 
>> extension RandomAccessCollection where Indices == DefaultRandomAccessIndices<Self> {
>>    public var indices: DefaultRandomAccessIndices<Self> { }
>> }
>> 
>> Those line up, which is easy, but there is *another* protocol extension of RandomAccessIterator from which we can infer Indices:
>> 
>> extension RandomAccessCollection
>> where Index : Strideable, 
>>       Index.Stride == IndexDistance,
>>       Indices == CountableRange<Index> {
>> 
>>   public var indices: CountableRange<Index> {
>>     return startIndex..<endIndex
>>   }
>> }
>> 
>> Note that both DefaultRandomAccessIndices<ReferenceCollection> and CountableRange<Int> would be valid inferences for Indices. We have three options:
>> 
>> 1) Consider type inference to be ambiguous, because there is no natural ordering between the two protocol extensions (they have incompatible same-type constraints on the associated type Indices).
>> 2) Consider the first protocol extension to “win” because… we prefer the extension which corresponds to the associated type default (?). This would be consistent with a world where we don’t have associated type inference at all. (It also matches Swift 3.0.1’s behavior).
>> 3) Consider the second protocol extension to “win” because…the other protocol extension corresponds to the associated type default, and could therefore be considered to be a lowest-common-denominator implementation only there to provide the most basic defaults.
> 
> I can see the appeal of option 3, but IMO anything other than option 1 seems pretty brittle. Presumably with that option, and with the class providing a typealias for Indices, you would no longer have an ambiguity and the code would compile, correct?

Yes, adding an explicit typealias (to either of them) fixes the issue. 

  - Doug

> Mark
> 
>> 
>> For reference, Swift 3.0.1 picked DefaultRandomAccessIndices<ReferenceCollection>, current Swift master picks CountableRange<Int>, and my work-in-progress to improve the type checker calls it ambiguous, hence the question :)
>> 
>> 	- Doug
>> 
>> _______________________________________________
>> swift-dev mailing list
>> swift-dev at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161107/b8c8fdd1/attachment.html>