Self 实现 IteratorProtocol 时 Swift 如何推断出 Sequence 需求?

How does Swift infer Sequence requirements when Self implements IteratorProtocol?

我正在阅读 Sequence 文档,在他们使用的示例中(见下文)推断出对 Sequence 的要求。我的问题是它是如何推断出来的。我理解推理在更简单的情况下是如何工作的,但在这个例子中我无法理解 Swift 是如何推理的。

我看到 Sequence 的 makeIterator 方法有一个默认实现,但我不明白这里的 return 值是如何推断出来的。

例子

struct Countdown: Sequence, IteratorProtocol {

    var count: Int

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

上述类型参考

IteratorProtocol {

   func next() -> Self.Element?

   associatedtype Iterator

   associatedtype Element
}
Sequence {

   func makeIterator() -> Self.Iterator

   associatedtype Iterator

   associatedtype Element

}

让我们从IteratorProtocol.next的实现开始。编译器看到这个实现:

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

并注意到它 return 是一个 Int?。那么,IteratorProtocol.next 应该是 return 一个 Self.Element?,所以它推断出 IteratorProtocol.Element == Int。现在 Coundown 满足 IteratorProtocol.

请注意 SequenceIteratorProtocol 共享 关联类型 Element。一旦 Swift 找出 IteratorProtcol.Element 的 witness,就好像你在 Countdown 中声明了一个新的类型别名 Element,而恰好 Sequence 需要Countdown.Element 存在。

之后,编译器推断出Iterator == Self。这样 makeIterator 的默认实现就可用了。然而,编译器如何推断出这一点是一个谜,因为只有这些信息,通常无法推断出类型,这可以通过创建自己的序列和迭代器来证明协议。

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

在查看 source code 之后,我怀疑可能存在一些编译器魔法,尤其是这里:

// 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
} 

这似乎为 Iterator 设置了一个“首选”类型来推断为。好像在说“当Iterator不能被推断为任何东西时,尝试Self”。我在其他任何地方都找不到 _Default_Iterator,这就是为什么我断定它是编译器的魔法。这样做的全部目的是让您仅通过符合 IteratorProtocol 并实现 next 来符合 Sequence,正如 documentation 所说的那样。

现在Iterator == Self,我们也满足了对Element的约束:

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

因此我们证明 Countdown 符合 Sequence.