Swift源码阅读 - 集合类型的核心设计思想

如果让你设计Sequence类型，你会为它添加那些约束呢？如果你没有特别丰富的经验，最好的办法，还是去看看Swift官方的Sequence实现吧。还是那句话，源码之前，了无秘密。

Sequence是一个值类型

当我们走近源代码之前，先来思考一个问题。一个最纯粹的“序列”，究竟意味着什么呢？通过前面两节内容我们知道，序列本身可以是有限的，也可以是无限的；可以是支持多次遍历的，也可以是只能遍历一次的。把这些约束摆在眼前，其实答案就很明显了：

• 序列的遍历只能单步向前；
• 序列表现的语义，是某种形式的值，它支持的各种访问操作应该是只读的；

如何以标准库的视角设计一个类型

接下来，我们思考第二个问题。把序列作为一个标准库的组件进行设计的时候，我们应该从哪些方面来考虑呢？其实，这个问题可以进一步放大成：设计一个容器类型应该从哪些方面进行考虑呢？实际上，得益于编程语言自身的发展，关于标准库中容器类的设计，已经被人们总结出了一些规律。围绕着容器类，一共有三个大的概念，分别是：

• Container - 容器类型本身，它提供了元素的存储，并为各种不同容器（数组、链表、字典、树等等）的访问提供了一致的接口；
• Iterator - 与容器搭配工作的Iterator，它为用各种不同的形式遍历容器（向前、向后、随机访问）提供了一致的接口。通常，每一个Container都有它“御用”的Iterator，因为Iterator的各种实现需要对Container的内部构造了如指掌；
• Algorithm - 当Container和Iterator有了一致的接口之后，也就意味着对各种不同形式数据结构的访问都有了一致的访问方法，于是，我们就可以基于这些接口，来开发出重用度极高的通用算法，这些算法只基于通用接口描述的核心语义，而不与任何具体的数据结构相关；

基于上面这三个大的概念，我们可以进一步细化它们各自应该考虑的约束，也就是应该提供哪些接口：

对于Container而言，我们应该回答下面几个“它应该”的问题：

• 暴露哪些和容器自身有关的类型；
• 如何初始化；
• 支持哪些赋值方式；
• 提供哪些和尺寸有关的接口；
• 有哪些直接访问元素的方法；
• 可以获取哪些形式的Iterator；
• 支持哪些形式的比较；
• 提供哪些以只读方式访问元素的接口；
• 提供哪些增、删、改元素的接口；

对于Iterator而言，我们应该回答下面几个“它应该”的问题：

• 暴露哪些和Iterator自身有关的类型；
• 提供哪些在Container中移动位置的接口；
• 提供哪些访问Container数据成员的接口；

而对于算法，有了Container和Interator之后，这就变成了一个容器无关的独立话题，我们就先不在这里展开了。

实际上，几乎任何一种编程语言中和容器有关的标准库设计，都遵从了上面的设计逻辑。

Protocols

有了上面这个大的框架之后，接下来的问题自然就变成了：应该如何实践呢？当然，不同的编程语言，践行这些标准的方式不尽相同。对Swift而言，我们可以利用protocol，把上面诸多的约束划分成很多个不同的protocol，然后，把这些protocol组合起来，就变成了多种不同的Containers和Iterators。这样做最大的好处，就是可以通过编译器，对这些约束在编译期就提供了保障。

有了这个思路之后，为了定义Sequence，我们的问题就又可以细化成：上面提出的关于Container设计的问题中，哪些适用于Sequence呢？由于我们已经明确遵从Sequence的类型是某种形式的值，它提供的接口是只读的，因此，下面这些问题，都是我们要考虑的：

• 暴露哪些和容器自身有关的类型；
• 提供哪些和尺寸有关的接口；
• 有哪些直接访问元素的方法；
• 可以获取哪些形式的Iterator；
• 支持哪些形式的比较；
• 提供哪些以只读方式访问元素的接口；

而对于遍历序列类型的Iterator，我们要考虑的问题，和之前是一样的。至此，我们装备的理论知识就差不多了，带着这些问题，我们在Swift的源代码中来找一找答案。

IteratorProtocol

我们可以在这里找到Sequence的一部分定义。在文件的一开始，我们会看到一大段关于Sequence的注释。在这段注释的开始，比较重要的是关于Iterator和Sequence的一个概述：

/// The `IteratorProtocol` protocol is tightly linked with the `Sequence`
/// protocol. Sequences provide access to their elements by creating an
/// iterator, which keeps track of its iteration process and returns one
/// element at a time as it advances through the sequence.
/// ...

可以看到，这和刚才我们描述的Container和Iterator的关系，是一样的。

接下来，我们直接跳转到第一行代码的位置，这里，是Swift对Sequence Iterator这个概念的定义：

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

这个定义我们并不陌生，在上一节中，我们已经用过了。现在，站在标准库设计的立场，我们再来看一下。实际上，它回答了之前我们对Iterator类型约束提出的三个问题：

Q: 暴露哪些和Iterator自身有关的类型？

A：作为遍历序列类型的Iterator，只暴露了一个类型，就是迭代器指向位置的元素的类型。实际上，关于Iterator，还有一种应该暴露的类型，就是Iterator自身的种类，它决定了我们可以如何在Container中移动位置，以及Iterator可以对容器进行的操作。不过现在大家知道就好了，我们遇到的时候再说。

Q: 提供哪些在Container中移动位置的接口？

A：之前我们说过，序列类型的Iterator只能单步向前移动，因此它只约束了一个next方法，每次在序列中向前移动一个位置。而没有类似：++ / -- / [] / prev这类移动位置的接口。

Q: 提供哪些访问Container数据成员的接口；

A：由于我们无法随机在序列中访问元素，也不一定可以反复访问同一个位置，因此唯一通过Iterator访问到序列元素的机会，就是调用了next时的返回值。我们不应该约束可以反复访问同一个位置的接口，也不应该提供可以通过Iterator修改元素的功能。

在Sequence的注释中，我们可以找到这样一段：

/// Whenever you use multiple iterators (or `for`-`in` loops) over a single
/// sequence, be sure you know that the specific sequence supports repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.

简单来说，反复访问序列中的同一个位置，要么，你明确知道这样可行，要么，这个类型遵从了protocol Collection。总之，这种行为不是Sequence的一部分。

Sequence

了解了与之搭配的Iterator之后，我们就可以来看Sequence自身的定义了。同样，我们顺着之前对Container提出的各种问题为线索，来理解源代码。

暴露哪些和容器自身有关的类型

我们的第一个问题：应该暴露哪些和容器自身有关的类型。一个比较直接的想法，它至少应该对外提供两种类型，分别是容器内元素的类型和与容器搭配工作的Iteraor的类型。有了它们，我们才可以正常使用容器。为此，Sequence是这样定义的：

public protocol Sequence {
  /// A type representing the sequence's elements.
  associatedtype Element

  /// A type that provides the sequence's iteration interface and
  /// encapsulates its iteration state.
  associatedtype Iterator : IteratorProtocol
    where Iterator.Element == Element
}

其中：

• Element表示序列中的元素类型；
• Iterator表示和特定序列一起搭配工作的Iterator；

至此，尽管才刚刚开始，但有了这些内容，我们就已经可以编写自己的第一个“通用算法了”。之前，我们使用reduce的时候，总要传递一个初始值：

var array = [0, 1, 2, 3, 4]
var sum = array.reduce(0, +)

很多时候这样做都很麻烦，因为我们就是要用容器中的第一个元素作为reduce的初始值。为此，假设我们要定义一个全局函数来改进这个问题。当然，也可以把它写成extension Sequence，这里选择全局函数，是为了更好的理解我们之前说过的Container / Iterator / Algorithm三元素的关系：

func reduce1<U, V>(of sequence: U,
                  _ partial: (V, V) -> V) -> V?
    where U: Sequence, V == U.Element {
        var iter: U.Iterator = sequence.makeIterator()

        guard var accumulated = iter.next() else {
            return nil
        }

        while let element = iter.next() {
            accumulated = partial(accumulated, element)
        }

        return accumulated
}

在这个全局函数的实现里，有两点是值得注意的。

第一点，正因为Sequence对外暴露了Element和Iterator，诸如V == U.Element和var iter: U.Iterator = sequence.makeIterator()这样的代码才可以正常通过编译。你可能会觉得，对于iter的定义，可以依靠type inference啊，并不一定要写出来。而实际上，这其实和是否要明确写出来U.Iterator关系并不大。当我们使用sequence.makeIterator()的时候，“用于遍历sequence的类型”就已经暴露在开发者的眼前了。

于是，我们就可以这样来使用这个全局版的reduce1：

let sum1 = reduce1(of: array, +) // 10

第二点，纵览reduce1的实现，你就会发现，无论是遍历sequence，还是对sequence的成员进行操作，这其中没有一处是和sequence的具体实现细节相关的，reduce1并不关心应该访问哪个对象的哪个属性，也完全不关心容器对象的具体内存布局。iter作为一种粘合剂，很好的组合了sequence和reduce1。基于这种思路，我们还可以开发出很多通用的算法。而这，就是Container / Iterator / Algorithm三者关系的一个具体的体现。

除了Element和Iterator之外，Sequence还暴露了一个表示其区间的类型：

public protocol Sequence {
  /// A type that represents a subsequence of some of the sequence's elements.
  associatedtype SubSequence : Sequence = AnySequence<Element>
    where Element == SubSequence.Element,
          SubSequence.SubSequence == SubSequence
}

从这个定义中，我们可以了解到不少信息：

• 首先，对于一个遵从了Sequence的类型，它的区间类型也是一个Sequence，这样，当我们访问一个区间的时候，才能有和访问原始序列有同样的行为。并且，区间中元素的类型和与其对应的原始Sequence应该是一样的（where Element == SubSequence.Element）；
• 其次，“区间的区间”应该和原始Sequence的区间类型相同（SubSequence.SubSequence == SubSequence），这确保了我们可以一直把一个原始的序列分割下去。这里使用了一个Swift 4.1中引入的特性，帮助我们可以通过递归的形式，约束类型的定义；
• 第三，如果一个序列没有专门定义自己的SubSequence，那么Swift将使用AnySequence<Element>作为它的区间类型，这是因为，在下一节我们会看到，Swift为Sequence约束的一些方法提供了默认实现，这些实现要求我们得有一个具体的SubSequence类型；