[swift-dev] Associated type inference fun with RandomAccessCollection

[Dave Abrahams]

on Tue Nov 08 2016, Douglas Gregor <dgregor-AT-apple.com> wrote:

>> On Nov 8, 2016, at 1:58 PM, Dave Abrahams via swift-dev <swift-dev at swift.org> wrote:
>> 
>> 
>> on Mon Nov 07 2016, Douglas Gregor <swift-dev-AT-swift.org <http://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).
>> 
>> That seems reasonable, but I would like to have a way to *create* such a
>> natural ordering.
>
> One such way is to drop the same-type requirement (Indices ==
> DefaultRandomAccessIndices<Self>) from the first extension, making it
> an unconstrained extension and, therefore, more general than the
> second (constrained) extension. I think that’s the best solution
> here. The downside is that a concrete type like ‘ReferenceCollection’
> will have the subscript operators from both RandomAccessCollection
> extensions. That’s a problem I think we should solve more generally,
> perhaps with some name-shadowing rule or keyword to say “only use this
> declaration to satisfy a requirement and for nothing else”.

I like the latter very much, and it is a good use-case for an explicit
"override" on protocol methods.


> I’ll go ahead with this solution for now.
>
>> 
>>> 2) Consider the first protocol extension to “win” because… we prefer
>>> the extension which corresponds to the associated type default
>>> (?). 
>> 
>> Up until now, specific extensions have never behaved like (or at least,
>> have never been intended to behave like) distinguishable entities in the
>> user model; I'm wary of entering that world, though I know it has been
>> discussed w.r.t. conditional conformances.
>> 
>>> 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).
>> 
>> ?? This statement makes no sense to me.  If there's no associated type
>> inference, what would it mean for this extension to "win?"
>
> If there’s no associated type inference, one would get the associated type default,
> DefaultRandomAccessIndices<Self>.

To me that just sounds like more-limited inference, but OK.

-- 
-Dave