CODEWITHSUNDEEP
swifttypesprotocolssequencetype-inference
3366784
3366784

Reputation: 2485

How does Swift infer Sequence requirements when Self implements IteratorProtocol?

I'm reading the Sequence documentation and in an example that they use (see below) the requirements for Sequence are inferred. My question is how is it inferred. I understand how inferencing works in simpler cases but in this example I cannot understand how Swift infers things.

I see that Sequence's makeIterator method has a default implementation but I don't understand how the return value is inferred here.

Example

struct Countdown: Sequence, IteratorProtocol {

    var count: Int

    mutating func next() -> Int? {
        if count == 0 {
            return nil
        } else {
            defer { count -= 1 }
            return count
        }
    }
}

Reference for types mentioned above

IteratorProtocol {

   func next() -> Self.Element?

   associatedtype Iterator

   associatedtype Element
}

Sequence {

   func makeIterator() -> Self.Iterator

   associatedtype Iterator

   associatedtype Element

}

Upvotes: 1

Views: 199

Answers (1)

Sweeper
Sweeper

Reputation: 271810

Let's start with the implementation of IteratorProtocol.next. The compiler sees this implementation:

mutating func next() -> Int? {
    if count == 0 {
        return nil
    } else {
        defer { count -= 1 }
        return count
    }
}

And notices that it returns an Int?. Well, IteratorProtocol.next is supposed to return a Self.Element?, so it infers that IteratorProtocol.Element == Int. Now Coundown satisfies IteratorProtocol.

Note that Sequence and IteratorProtocol share the associated type Element. Once Swift figures out the witness for IteratorProtcol.Element, it's as if you declared a new type alias Element in Countdown, and it just so happens that Sequence requires that Countdown.Element to exist.

After that, the compiler infers Iterator == Self. This is so that the default implementation of makeIterator is available. However, it is quite a mystery how the compiler can infer this, because with only these information, the type can't normally be inferred, as can be shown by creating your own sequence and iterator protocols.

protocol MyIterator {
    associatedtype Element
    
    mutating func next() -> Element?
}

protocol MySequence {
    associatedtype Element where Element == Iterator.Element
    associatedtype Iterator : MyIterator
    
    func makeIterator() -> Iterator
}

extension MySequence where Self == Self.Iterator {
    func makeIterator() -> Iterator {
        return self
    }
}

struct Countdown: MySequence, MyIterator { // doesn't compile
    var count: Int

    mutating func next() -> Int? {
        if count == 0 {
            return nil
        } else {
            defer { count -= 1 }
            return count
        }
    }
}

After looking into the source code, I suspect there might be some compiler magic going on, especially here:

// Provides a default associated type witness for Iterator when the
// Self type is both a Sequence and an Iterator.
extension Sequence where Self: IteratorProtocol {
  // @_implements(Sequence, Iterator)
  public typealias _Default_Iterator = Self
}

This seems to set a "preferred" type for Iterator to be inferred as. It seems to be saying "When Iterator can't be inferred to be anything, try Self". I can't find _Default_Iterator anywhere else, which is why I concluded it's compiler magic. The whole purpose of this is to allow you to conform to Sequence by only conforming to IteratorProtocol and implementing next, as the documentation said you can do.

Now that Iterator == Self, we have also satisfied the constraint on Element:

associatedtype Element where Self.Element == Self.Iterator.Element

Thus we have shown that Countdown conforms to Sequence.

Upvotes: 1

Related Questions