[swift-dev] Associated type inference fun with RandomAccessCollection

[Dave Abrahams]

on Mon Nov 07 2016, Douglas Gregor <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.

> 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?"

> 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.
>
> 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
>

-- 
-Dave