[SR-1922] Associated type inference issue with BidirectionalCollection

[natecook1000]

Previous ID	SR-1922
Radar	None
Original Reporter	@natecook1000
Type	Bug
Status	Resolved
Resolution	Done

Environment

swift/master @ 6acb0fd

Additional Detail from JIRA

Votes	1
Component/s	Standard Library
Labels	Bug
Assignee	@natecook1000
Priority	Medium

md5: 708c3a7818a570deefa755fbbdd5ed8d

relates to:

• SR-2458 Requires Unit test for all of Collections and Slices

Issue Description:

There's an issue with associated type inference in bidirectional collections—seems like there's a conflict that is preventing resolution.

I can create an index and forward and random-access collections that use that index solely by implementing the required methods:

struct FatalIndex { }
func <(lhs: FatalIndex, rhs: FatalIndex) -> Bool { fatalError() }
func ==(lhs: FatalIndex, rhs: FatalIndex) -> Bool { fatalError() }
extension FatalIndex : Comparable { }

struct FatalCollection<T> : Collection {
    var startIndex: FatalIndex { fatalError() }
    var endIndex: FatalIndex { fatalError() }
    subscript(i: FatalIndex) -> T { fatalError() }
    func index(after i: FatalIndex) -> FatalIndex { fatalError() }
    func index(before i: FatalIndex) -> FatalIndex { fatalError() }
}

struct FatalRandomAccessCollection<T> : RandomAccessCollection {
    var startIndex: FatalIndex { fatalError() }
    var endIndex: FatalIndex { fatalError() }
    subscript(i: FatalIndex) -> T { fatalError() }
    func index(after i: FatalIndex) -> FatalIndex { fatalError() }
    func index(before i: FatalIndex) -> FatalIndex { fatalError() }
}

However, using the same code for a bidirectional collection gives me a litany of errors:

struct FatalBidirectionalCollection<T> : BidirectionalCollection {
    var startIndex: FatalIndex { fatalError() }
    var endIndex: FatalIndex { fatalError() }
    subscript(i: FatalIndex) -> T { fatalError() }
    func index(after i: FatalIndex) -> FatalIndex { fatalError() }
    func index(before i: FatalIndex) -> FatalIndex { fatalError() }
}

Lots of errors:

<REPL Input>:1:8: error: type 'FatalBidirectionalCollection<T>' does not conform to protocol 'BidirectionalCollection'
struct FatalBidirectionalCollection<T> : BidirectionalCollection {
       ^
Swift.BidirectionalCollection:40:20: note: protocol requires nested type 'SubSequence'
    associatedtype SubSequence : BidirectionalIndexable, Collection = BidirectionalSlice<Self>
                   ^
Swift.BidirectionalCollection:43:20: note: default type 'DefaultBidirectionalIndices<FatalBidirectionalCollection<T>>' for associated type 'Indices' (from protocol 'BidirectionalCollection') does not conform to 'BidirectionalIndexable'
    associatedtype Indices : BidirectionalIndexable, Collection = DefaultBidirectionalIndices<Self>
                   ^
<REPL Input>:1:8: error: type 'FatalBidirectionalCollection<T>' does not conform to protocol 'Collection'
struct FatalBidirectionalCollection<T> : BidirectionalCollection {
       ^
Swift.Collection:147:20: note: protocol requires nested type 'SubSequence'
    associatedtype SubSequence : IndexableBase, Sequence = Slice<Self>
                   ^
Swift.Collection:190:20: note: protocol requires nested type 'Indices'
    associatedtype Indices : IndexableBase, Sequence = DefaultIndices<Self>
                   ^
Swift.Collection:138:20: note: protocol requires nested type 'Iterator'
    associatedtype Iterator : IteratorProtocol = IndexingIterator<Self>
                   ^
<REPL Input>:1:8: error: type 'FatalBidirectionalCollection<T>' does not conform to protocol 'Sequence'
struct FatalBidirectionalCollection<T> : BidirectionalCollection {
       ^
Swift.Sequence:120:20: note: unable to infer associated type 'Iterator' for protocol 'Sequence'
    associatedtype Iterator : IteratorProtocol
                   ^
Swift.Sequence:5:17: note: inferred type 'FatalBidirectionalCollection<T>' (by matching requirement 'makeIterator()') is invalid: does not conform to 'IteratorProtocol'
    public func makeIterator() -> Self
                ^
Swift.Collection:6:17: note: inferred type 'IndexingIterator<FatalBidirectionalCollection<T>>' (by matching requirement 'makeIterator()') is invalid: does not conform to 'IteratorProtocol'
    public func makeIterator() -> IndexingIterator<Self>
                ^
Swift.Collection:19:17: note: inferred type 'FatalBidirectionalCollection<T>.Iterator' (by matching requirement 'map') is invalid: does not conform to 'IteratorProtocol'
    public func map<T>(_ transform: @noescape (Self.Iterator.Element) throws -> T) rethrows -> [T]
                ^
Swift.Collection:214:17: note: inferred type 'FatalBidirectionalCollection<T>.Iterator' (by matching requirement 'split(maxSplits:omittingEmptySubsequences:isSeparator:)') is invalid: does not conform to 'IteratorProtocol'
    public func split(maxSplits: Int = default, omittingEmptySubsequences: Bool = default, isSeparator: @noescape (Self.Iterator.Element) throws -> Bool) rethrows -> [Self.SubSequence]
                ^
Swift.Collection:2:17: note: inferred type 'FatalBidirectionalCollection<T>.Iterator' (by matching requirement '_copyToNativeArrayBuffer()') is invalid: does not conform to 'IteratorProtocol'
    public func _copyToNativeArrayBuffer() -> _ContiguousArrayBuffer<Self.Iterator.Element>
                ^
Swift.Sequence:3:17: note: inferred type 'FatalBidirectionalCollection<T>.Iterator' (by matching requirement '_copyContents(initializing:)') is invalid: does not conform to 'IteratorProtocol'
    public func _copyContents(initializing ptr: UnsafeMutablePointer<Self.Element>) -> UnsafeMutablePointer<Self.Element>
                ^
<REPL Input>:1:8: error: type 'FatalBidirectionalCollection<T>' does not conform to protocol 'IndexableBase'
struct FatalBidirectionalCollection<T> : BidirectionalCollection {
       ^
Swift.IndexableBase:56:20: note: ambiguous inference of associated type 'SubSequence': 'Slice<FatalBidirectionalCollection<T>>' vs. 'BidirectionalSlice<FatalBidirectionalCollection<T>>'
    associatedtype SubSequence
                   ^
Swift.Collection:25:12: note: matching requirement 'subscript' to this declaration inferred associated type to 'Slice<FatalBidirectionalCollection<T>>'
    public subscript(bounds: Range<Self.Index>) -> Slice<Self> { get }
           ^
Swift.BidirectionalIndexable:5:12: note: matching requirement 'subscript' to this declaration inferred associated type to 'BidirectionalSlice<FatalBidirectionalCollection<T>>'
    public subscript(bounds: Range<Self.Index>) -> BidirectionalSlice<Self> { get }
           ^

[nsalmoria]

I ran into the exact same problem today.

Note that if you try to work around the 'ambiguous inference' errors by explicitly declaring

typealias SubSequence = BidirectionalSlice<FatalBidirectionalCollection<T>>

you get the puzzling error

Type alias 'SubSequence' circularly references itself

[natecook1000]

I found a workaround for this—inference is falling down on both Index and SubSequence. The FatalBidirectionalCollection collection compiles if you add two things: an explicit type alias for Index and an implementation of subscript(bounds: Range<Index>) -> SubSequence.

struct FatalBidirectionalCollection<T> : BidirectionalCollection {
    var startIndex: FatalIndex { fatalError() }
    var endIndex: FatalIndex { fatalError() }
    subscript(i: FatalIndex) -> T { fatalError() }
    func index(after i: FatalIndex) -> FatalIndex { fatalError() }
    func index(before i: FatalIndex) -> FatalIndex { fatalError() }

    typealias Index = FatalIndex
    subscript(bounds: Range<FatalIndex>) -> BidirectionalSlice<FatalBidirectionalCollection> { fatalError() }
}

[natecook1000]

Fixed in #3510