Swift 的字符串为什么这么难用？

Swift 里的 String 繁琐难用的问题一直是大家频繁吐槽的点，趁着前两天 Swift 团队发了一份新的提案 SE-0265 Offset-Based Access to Indices, Elements, and Slices 来改善 String 的使用，我想跟大家分享一下自己的理解。

SE-0265 提案的内容并不难理解，主要是增加 API 去简化几个 Collection.subscript 函数的使用，但这个提案的背景故事就比较多了，看了这篇提案我思考了很多关于这个 API 相关的内容，我认为问题的核心在于 Collection.Index 的设计。

在分析 Collection.Index 之前，我们先来看一下 String 常见的使用场景：

let str = "String 的 Index 为什么这么难用？"
let targetIndex = str.index(str.startIndex, offsetBy: 4)
str[targetIndex]

上面这段代码有几个地方容易让人产生疑惑：

1. 为什么 targetIndex 要调用 String 的实例方法去生成？
2. 为什么这里需要使用 str.startIndex，而不是 0？
3. 为什么 String.Index 使用了一个自定义类型，而不是直接使用 Int？

上述的这些问题也造成了 String 的 API 变得十分繁琐，在其它语言里一行代码能解决的问题在 Swift 需要好几行，但这些其实都是 Swift 有意而为之的设计……

不等长的元素

在我们使用数组的时候，会有一个这样的假设：数组的每个元素都是等长的。例如在 C 里面，数组第 n 个元素的位置会是 数组指针 + n * 元素长度，这道公式可以让我们在 O(1) 的时间内获取到第 n 个元素。

但在 Swift 里这件事情并不一定成立，最好的例子就是 String，它的底层实现是 UTF-8 编码单位的集合，而暴露给外部的则是字符的集合，每个字符由 1 到 4 个 UTF-8 编码单位组成，换句话说，作为字符的集合时，实际上 String 的每一个元素的长度是不相等的。

这就意味着通过字符索引获取元素的时候，没办法简单地通过上面的公式计算出对应字符的位置，必须一直遍历到对应的元素才能获取到它的实际位置（UTF-8 编码单位的索引）。

那么问题就来了，如果要像 Array 那样直接使用 Int 作为索引的话，那迭代等操作就会产生更多的性能消耗，因为每次迭代都需要重新计算字符的偏移量：

// 假设 String 是以 Int 作为 Index 的话
// 下面的代码复杂度将会是 O(n^2)
// O(1) + O(2) + ... + O(n) = O(n!) ~= O(n^2)
let hello = "Hello"
for i in 0..<hello.count {
    print(hello[i])
}

那 String.Index 是怎么设计的？

思路很简单，通过自定义 Index 类型，在内部记录对应元素的偏移量，迭代过程中复用它计算下一个 index 即可：

// 下面的代码复杂度将会是 O(n)
// O(1) + O(1) + ... + O(1) = O(n)
let hello = "Hello"
var i = hello.startIndex
while i != hello.endIndex {
    print(hello[i])
    hello.formIndex(after: &i)
}

在源码里我们可以找到 String.Index 的设计说明：

String 的 Index 的内存布局如下:
 
 ┌──────────┬───────────────────╥────────────────┬──────────╥────────────────┐
 │ b63:b16  │      b15:b14      ║     b13:b8     │  b7:b1   ║       b0       │
 ├──────────┼───────────────────╫────────────────┼──────────╫────────────────┤
 │ position │ transcoded offset ║ grapheme cache │ reserved ║ scalar aligned │
 └──────────┴───────────────────╨────────────────┴──────────╨────────────────┘

- position aka `encodedOffset`: 一个 48 bit 值，用来记录码位偏移量
- transcoded offset: 一个 2 bit 的值，用来记录字符使用的码位数量
- grapheme cache: 一个 6 bit 的值，用来记录下一个字符的边界(?)
- reserved: 7 bit 的预留字段
- scalar aligned: 一个 1 bit 的值，用来记录标量是否已经对齐过(?)

但由于 Index 里记录了码位的偏移量，而每个 String 的 Index 对应的偏移量都会有差异，所以 Index 必须由 String 的实例生成：

let str = "C 语言"
let index = str.index(str.startIndex, offsetBy: 2) // 使用 String 的实例生成 index

// |   C    |        |            语            |            言            |
// | U+0043 | U+0020 |          U+8BED          |          U+8A00          |
// |   43   |   20   |   E8   |   AF   |   AD   |   E8   |   A8   |   80   |
//                   ^
//                   |
//              index 的位置
// i.encodedOffset    == 2   “语”之前的字符使用的 UTF-8 编码单位数量
//                           总共有两个，“C” 使用了一个 43，“ ” 使用了一个 20
// i.transcodedOffset == 3   “语”由 E8 AF AD 三个 UTF-8 编码单位组成
// 
// 换句话说 i 所代表的含义就是：
// 偏移 transcodedOffset 个 UTF-8 编码单位
// 取   encodedOffset    个 UTF-8 编码单位

print(str[index])  // 语

这种实现方式有趣的一点是，Index 使用过程中最消耗性能的是 Index 的生成，一旦 Index 生成了，使用它取值的操作复杂度都只会是 O(1)。

并且由于这种实现的特点，每个 String 的实例只应该使用自己生成的 Index ，使用其它实例生成的 Index 会导致意外情况的发生：

let str2 = "Clang"

// |   C    |   l    |   a    |   n    |   g    | 
// | U+0043 | U+006C | U+0061 | U+006E | U+0067 | 
// |   43   |   6C   |   61   |   6E   |   67   | 
//                   ^
//              index 的位置
// 偏移了 2 个单位，取 3 个单位，所以这里会取到三个字符
// 但作为一个索引，理论上 i 只应该指向一个字符

print(str2[index]) // ang

Index 在多个字符串间复用，就会造成这种一个索引会取到三个字符的意外情况，Swift 开发组表示过这属于一种未定义行为，在未来有可能会在运行时作为错误抛出。

大费周章支持不等长的元素？

如果不需要让 Collection 去支持不等长的元素，那一切就会变得非常简单，Collection 不再需要 Index 这一层抽象，直接使用 Int 即可，并且在标准库的类型里元素不等长的集合类型也只有 String，对它进行特殊处理也是一种可行的方案。

摆在 Swift 开发组面前的是两个选择：

• 继续完善 Collection 协议，让它更好地支持元素不等长的情况。
• 或者是专门给 String 建立一套机制，让它独立运行在 Collection 的体系之外。

开发组在这件事情上的态度其实也有过摇摆：

1. Swift 1 里 String 是遵循 Collection 的。
2. Swift 2~3 的时候移除了这个 Conformance，计划逐渐弃用掉 Index 这一层抽象直接使用 Int。
3. 但在 Swift 4 之后又重新改了回去。

这样做的好处主要还是保证 API 的正确性，提升代码的复用，之前在 Swift 2~3 里扩展一些集合相关的函数时，一模一样的代码需要在 String 和 Collection 里各写一套实现。

尽管我们确实需要 Index 这一层抽象去表达 String 这一类元素不等长的数组，但也不可否认它给 API 调用带来了一定程度负担。（Swift 更倾向于 API 的正确性，而不是易用性）

Index 不一定从 0 开始

在使用一部分切片集合的时候，例如 ArraySlice 在使用 Index 取值时，大家也许会发现一些意料之外的行为，例如说：

let a = [0, 1, 2, 3, 4]
let b = a[1...3]

print(b[1]) // 1

这里我们预想的结果应该是 2 而不是 1，原因是我们在调用 b[1] 时有一个预设：所有集合的下标都是从 0 开始的。但对于 Swift 里的集合类型来说，这件事情并不成立：

print(b.startIndex)          // 1
print((10..<100).startIndex) // 10

Collection.Index 是绝对索引

换句话说，Collection 里的 Index 其实是绝对索引，但对于我们来说，Array 和 ArraySlice 除了在生命周期处理时需要注意之外，其它 API 的调用都不会存在任何差异，也不应该存在差异，使用相对索引屏蔽掉数组和切片之间的差异应该是更好的选择，那还为什么要设计成现在的样子？

这个问题在论坛里有过很激烈的讨论，核心开发组也只是出来简单地提了两句，大意是虽然对于用户来说确实不存在区别，但对于（标准库）集合类型的算法来说，基于现有的设计可以采取更加简单高效的实现，并且实现出来的算法也不存在 Index 必须为 Int 的限制。

我个人的理解是，对于 Index == Int 的 Collection 来说，SubSequence 的 startIndex 设为 0 确实很方便，但这也是最大的问题，任何以此为前提的代码都只对于 Index == Int 的 Collection 有效，对于 Index != Int 的 Collection，缺乏类似于 0 这样的常量来作为 startIndex，很难在抽象层面去实现统一的集合算法。

我们想要的是相对索引

其实我们可以把当前的 Index 看作是 underlying collection 的绝对索引，我们想要的不是 0-based collection 而是相对索引，但相对索引最终还是要转换成绝对索引才能获取到对应的数据，但这种相对索引意味着 API 在调用时要加一层索引的映射，并且在处理 SubSequence 的 SubSequence 这种嵌套调用时，想要避免多层索引映射带来的性能消耗也是需要额外的实现复杂度。

无论 Swift 之后是否会新增相对索引，它都需要基于绝对索引去实现，现在的问题只是绝对索引作为 API 首先被呈现出来，而我们在缺乏认知的情况下使用就会显得使用起来过于繁琐。

调整一下我们对于 Collection 抽象的认知，抛弃掉数组索引必定是 0 开头的想法，换成更加抽象化的 startIndex，这件事情就可以变得自然很多。引入抽象提升性能在 Swift 并不少见，例如说 @escaping 和 weak，习惯了之后其实也没那么糟糕。

Index 之间的距离是 1，但也不是 1

前面提到了 Index == Int 的 Collection 类型一定是从 0 开始，除此之外，由于 Index 偏移的逻辑也被抽象了出来，此时的 Collection 表现出来另一个特性 —— Index 之间的距离不一定是 “1” 。

假设我们要实现一个采样函数，每隔 n 个元素取一次数组的值：

extension Array {
    func sample(interval: Int, execute: (Element) -> Void) {
        var i = 0
        while i < count {
            execute(self[i])
            i += interval
        }
    }
}

[0, 1, 2, 3, 4, 5, 6].sample(interval: 2) {
    print($0) // 0, 2, 4, 6
}

如果我们想要让它变得更加泛用，让它能够适用于大部分集合类型，那么最好将它抽象成为一个类型，就像 Swift 标准库那些集合类型：

struct SampleCollection<C: RandomAccessCollection>: RandomAccessCollection {
    let storage: C
    let sampleInterval: Int

    var startIndex: C.Index { storage.startIndex }
    var endIndex: C.Index { storage.endIndex }
    func index(before i: C.Index) -> C.Index {
        if i == endIndex {
            return storage.index(endIndex, offsetBy: -storage.count.remainderReportingOverflow(dividingBy: sampleInterval).partialValue)
        } else {
            return storage.index(i, offsetBy: -sampleInterval)
        }
    }
    func index(after i: C.Index) -> C.Index { storage.index(i, offsetBy: sampleInterval, limitedBy: endIndex) ?? endIndex }
    func distance(from start: C.Index, to end: C.Index) -> Int { storage.distance(from: start, to: end) / sampleInterval }
    subscript(position: C.Index) -> C.Element { storage[position] }

    init(sampleInterval: Int, storage: C) {
        self.sampleInterval = sampleInterval
        self.storage = storage
    }
}

封装好了类型，那么我们可以像 prefix / suffix 那样给对应的类型加上拓展方法，方便调用：

extension RandomAccessCollection {
    func sample(interval: Int) -> SampleCollection<Self> {
        SampleCollection(sampleInterval: interval, storage: self)
    }
}

let array = [0, 1, 2, 3, 4, 5, 6]
array.sample(interval: 2).forEach { print($0) } // 0, 2, 4, 6
array.sample(interval: 3).forEach { print($0) } // 0, 3, 6
array.sample(interval: 4).forEach { print($0) } // 0, 4

SampleCollection 通过实现那些 Index 相关的方法达到了采样的效果，这意味着 Index 的抽象其实是经由 Collection 诠释出来的概念，与 Index 本身并没有任何关系。

例如说两个 Index 之间的距离，0 跟 2 对于两个不同的集合类型来说，它们的 distance 其实是可以不同的：

let sampled = array.sample(interval: 2)

let firstIdx = sampled.startIndex               // 0
let secondIdx = sampled.index(after: firstIdx)  // 2

let numericDistance = secondIdx - firstIdx.     // 2
array.distance(from: firstIdx, to: secondIdx)   // 2
sampled.distance(from: firstIdx, to: secondIdx) // 1

所以我们在使用 Index == Int 的集合时，想要获取集合的第二个元素，使用 1 作为下标取值是一种错误的行为：

sampled[1]         // 1
sampled[secondIdx] // 2

Collection 会使用自己的方式去诠释两个 Index 之间的距离，所以就算我们遇上了 Index == Int 的 Collection，直接使用 Index 进行递增递减也不是一种正确的行为，最好还是正视这一层泛型抽象，减少对于具体类型的依赖。

越界时的处理

Swift 一直称自己是类型安全的语言，早期移除了 C 的 for 循环，引入了大量“函数式”的 API 去避免数组越界发生，但在使用索引或者切片 API 时越界还是会直接导致崩溃，这种行为似乎并不符合 Swift 的“安全”理念。

社区里每隔一段时间就会有人提议过改为使用 Optional 的返回值，而不是直接崩溃，但这些建议都被打回，甚至在 Commonly Rejected Changes 里有专门的一节叫大家不要再提这方面的建议（除非有特别充分的理由）。

那么类型安全意味着什么呢？Swift 所说的安全其实并非是指避免崩溃，而是避免未定义行为（Undefined Behavior），例如说数组越界时读写到了数组之外的内存区域，此时 Swift 会更倾向于终止程序的运行，而不是处于一个内存数据错误的状态继续运行下去。

Swift 开发组认为，数组越界是一种逻辑上的错误，在早期的邮件列表里比较清楚地阐述过这一点：

On Dec 14, 2015, at 6:13 PM, Brent Royal-Gordon via swift-evolution wrote:

…有一个很类似的使用场景，Dictionary 在下标取值时返回了一个 Optional 值。你也许会认为这跟 Array 的行为非常不一致。让我换一个说法来表达这件认知，对于 Dictionary来说，当你使用一个 key set 之外的 key 来下标取值时，难道这不是一个程序员的失误吗？

Array 和 Dictionary 的使用场景是存在差异的。

我认为 Array 下标取值 80% 的情况下，使用的 index 都是通过 Array 的实例间接或直接生成的，例如说 0..<array.count，或者 array.indices，亦或者是从 tableView(_:numberOfRowsInSection:) 返回的 array.count 派生出来的 array[indexPath.row]。这跟 Dictionary 的使用场景是不一样的，通常它的 key 都是别的什么数据里取出来的，或者是你想要查找与其匹配的值。例如，你很少会直接使用 array[2] 或 array[someRandomNumberFromSomewhere]，但 dictionary[“myKey”] 或 dictionary[someRandomValueFromSomewhere] 却是非常常见的。

由于这种使用场景上的差异，所以 Array 通常会使用一个非 Optional 的下标 API，并且会在使用非法 index 时直接崩溃。而 Dictionary 则拥有一个 Optional 的下标 API，并且在 index 非法时直接返回 nil。

核心开发团队先后有过两个草案改进 String 的 API，基本方向很明确，新增一种相对索引类型：

1. Collection 通用的索引类型。不需要考虑具体的 Index 类型，不需要根据数组实例去生成 Index，新的索引会在内部转换成 Collection 里的具体 Index 类型。
2. 简化 Index 的生成。
3. subscript 返回 Optional 类型。

具体的内容大家可以看提案，我是在第二份草案刚提出的时候开始写这篇文章的，删删改改终于写完了，现在草案已经变成了正式提案在 review 了，希望这篇文章可以帮助大家更好地理解这个提案的前因后果，也欢迎大家留言一起交流。

参考链接：