[swift-dev] Associated type inference fun with RandomAccessCollection

[Dave Abrahams]

on Mon Nov 07 2016, Robert Widmann <swift-dev-AT-swift.org> wrote:

> Voting for 1.  This is an ambiguity in stdlib through and through IMO.

No, this is the standard library doing the best it can with a type
checker that has mostly-unspecified semantics.  It can only be
considered an ambiguity in the standard library if you presume the
semantics of choice 1, which was never specified... hence Doug's
question.

> ~Robert Widmann
>
> 2016/11/07 22:07、Mark Lacey via swift-dev <swift-dev at swift.org> のメッセージ:
>
>> 
>>> 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?
>> 
>> 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
>> 
>> _______________________________________________
>> swift-dev mailing list
>> swift-dev at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-dev
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev
>

-- 
-Dave