[swift-dev] Associated type inference fun with RandomAccessCollection

[Douglas Gregor]

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.

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20161107/e7175f09/attachment.html>