Swift5 为什么SubSequence不适用于序列类型

改动的初衷

为了搞清楚这个问题，我们得从在Swift 5之前需要这个类型的下面几个方法说起：

func dropFirst(_:) -> SubSequence
func dropLast(_:) -> SubSequence
func drop(while:) -> SubSequence
func prefix(_:) -> SubSequence
func prefix(while:) -> SubSequence
func suffix(_:) -> SubSequence
func split(separator:) -> [SubSequence]

可以看到，它们都返回一个SubSequence对象以表示从原始Sequence中提取出来的子序列。但是，我们必须要再强调一下，序列不是集合，这种用一个统一的类型来表示上面这些方法返回的子序列，在某些时候，并不那么方便。

是什么时候呢？一个最明显的例子，就是对那些不能反复遍历的序列。例如之前我们实现过的InputStream，这是一个不可重复遍历的无限序列。对于dropFirst来说，它返回的类型应该忽略掉前n次输入，并把后面的输入作为一个新的无限序列。而对于prefix来说，返回的类型应该只接受前n次输入，并忽略后续的输入，这是一个有限序列。

所以你看，显然，这两个方法的返回值不应该用同一个类型来表达。但在Swift 5以前，Sequence要求它们的返回类型相同。为此，Swift的标准库就采用了一种折衷的方式。

首先，在Sequence的定义里，把SubSequence定义成了AnySequence：

/// In Swift 4
public protocol Sequence {
  associatedtype SubSequence : Sequence = AnySequence<Element>
}

其次，让上面列出的方法返回它们自己对应的类型。例如，dropFirst就返回一个_DropFirstSequence对象。然后，用AnySequence抹掉这些类型的区别：

/// In Swift 4
internal func dropFirst(_ k: Int) -> AnySequence<Base.Element> {
  return AnySequence(
    _DropFirstSequence(
      _iterator: _iterator, limit: _limit + k, dropped: _dropped))
}

如此一来，这些方法的返回值，就可以用同一个类型表示了。然而这样做的代价，则是牺牲了性能和类型的可扩展性。关于对这个问题详细的评估和影响，大家有空可以去阅读这份提议中的描述。对于我们来说，现在只要理解为什么统一用SubSequence对Sequence来说不合适就行了。

具体的做法

为了解决这个问题，Swift开发团队把SubSequence的首次登场，放到了Collection里。在后面的内容中我们会提到，Collection意味着一个可以反复遍历的有限集合。如果是这样，用同一个类型表达之前那些方法的返回值，就没问题了。

而Sequence索性就让那些方法直接返回原来藏在AnySequence背后的类型就好了：

extension Sequence {
  public func dropFirst(_ k: Int = 1) -> DropFirstSequence<Self>
  public func dropLast(_ k: Int = 1) -> [Element]

  public func suffix(_ maxLength: Int) -> [Element]
  public func prefix(_ maxLength: Int) -> PrefixSequence<Self>

  public func drop(
    while predicate: (Element) throws -> Bool
  ) rethrows -> DropWhileSequence<Self>

  public func prefix(
    while predicate: (Element) throws -> Bool
  ) rethrows -> [Element]

  public func split(
    maxSplits: Int = Int.max,
    omittingEmptySubsequences: Bool = true,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [ArraySlice<Element>]
}

在这些接口的定义里：

• 表达的语义仍旧是一个序列的，返回值使用了自定义类型；
• 表达的语义侧重于一个有限范围内的结果集合，都返回了数组；

还是用之前实现的InputStream举例：

• 对于dropFirst来说，丢弃了序列中的前k个输入之后，由接下来的用户输入构成的仍旧是一个无限序列，因此，得使用一个专门的DropFirstSequence表示；
• 对于dropLast来说，这是一个当输入结束后（例如，按Ctrl + D）才能获取的值，我们得用一个缓冲区记录之前用户的所有输入，才能从中丢弃掉末尾的k个元素。这个方法表达的，就是一个有限范围的结果集合，因此它返回了[Element]；

当然，这是从道理上分析出来的。接下来，我们还是来看看两个方法的具体实现。

dropLast

首先，是dropLast，它的定义在这里：

public __consuming func dropLast(_ k: Int = 1) -> [Element] {
  _precondition(k >= 0,
    "Can't drop a negative number of elements from a sequence")
  guard k != 0 else { return Array(self) }

  var result = ContiguousArray<Element>()
  var ringBuffer = ContiguousArray<Element>()
  var i = ringBuffer.startIndex

  for element in self {
    if ringBuffer.count < k {
      ringBuffer.append(element)
    } else {
      result.append(ringBuffer[I])
      ringBuffer[i] = element
      i = (i + 1) % k
    }
  }

  return Array(result)
}

如果k小于0，执行的时候会触发运行时错误。如果k等于0，就用序列中所有的值生成一个数组返回。否则，就要从序列中忽略最后k个元素，用剩余的元素生成一个数组返回，这个过程是通过两个buffer完成的。其中，result中缓存的是用于生成结果数组的所有元素，ringBuffer是一个环状缓冲区，它缓存的是所有要从原始Sequence中丢弃的元素。

一开始遍历序列的时候，只要读到的元素个数小于等于k，就直接在ringBuffer中追加元素。此时，dropLast返回的，一直是一个空数组。直到ringBuffer被填满之后，再有新元素追加，每追加一个，ringBuffer中从头开始的元素就有一个要被加到result里。于是，每加入k个元素，ringBuffer的值就被轮换一次。而这也就是ringBuffer这个名字的含义了。

了解了dropLast的实现方式之后，你可能会想：为什么要采用这种缓冲区的方式呢？直接把遍历到的所有元素放到一个数组里，然后找到“最后k个元素之外”的索引位置，用这个位置创建新数组返回不是更简单么？顺着这个想法，我们可以自己创建一个：

extension Sequence {
  func dropLast1(_ k: Int) -> [Element] {
    var buffer = Array<Element>()

    for elem in self {
      buffer.append(elem)
    }

    if (k < buffer.count) {
      return Array(buffer[0..<(buffer.count - k)])
    }

    return []
  }
}

当然，我们只是为了讨论不同的缓存实现方式，因此dropLast1里没有处理各种不合法的k值。那么为什么Swift标准库中没有使用这样的方式呢？

在dropLast的代码里，我们能找到这样一段注释。它解释了为什么要采用这种环状缓冲区的方式实现：

// Put incoming elements from this sequence in a holding tank, a ring buffer
// of size <= k. If more elements keep coming in, pull them out of the
// holding tank into the result, an `Array`. This saves
// `k` * sizeof(Element) of memory, because slices keep the entire
// memory of an `Array` alive.

大体的意思是说，相比我们刚才自建的那种用数组的方式。Swift现有的方案节约了k * sizeof(Element)字节的内存。为什么会这样呢？

从大的方面说，这和数组的实现机制有关。当我们用buffer[0..<(buffer.count - k)]获取子数组时，出于效能方面的考虑，得到的并不是一个新的Array，而是一个ArraySlice。它和原始数组是共享内存的，只是标记了子数组的位置。这也就意味着，只要我们截取数组，无论截取的多短，只要这个片段在，整个数组都会因为截取的区间保持在内存里。

接下来，当我们用这个ArraySlice创建新数组的时候，同样出于效能方面的考虑，这时并不会拷贝数组的内容，Array使用了Copy On Write的方式。

最后，把这个创建的数组返回，这一步同样是使用Copy On Write方式完成的。因此，尽管返回的数组中并不包括被丢弃的k个元素，但是此时这个数组底层的存储中，这k个元素会被Array的实现机制保持在内存里。而Swift标准库中的实现则不存在这个问题，result中保存的就是返回结果中的元素。这就是为什么注释中说可以节约k * sizeof(Element)字节的原因了。