阅读 978

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

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

SE-0265 提案的内容并不难理解,主要是增加 API 去简化几个 Collection.subscript 函数的使用,但这个提案的背景故事就比较多了,所以这次我想聊的是 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,每一个元素都可能会是由 1~4 个 UTF8 码位组成。这就意味着通过索引获取元素的时候,没办法简单地通过上面的公式计算出元素的位置,必须一直遍历到索引对应的元素才能获取到它的实际位置(偏移量)。

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 是怎么设计的?

那 Swift 的 String 是怎么解决这个问题的呢?思路很简单,通过自定义 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 的设计说明:

StringIndex 的内存布局如下:
 
 ┌──────────┬───────────────────╥────────────────┬──────────╥────────────────┐
 │ 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 里记录了码位的偏移量,而每个 StringIndex 对应的偏移量都会有差异,所以我们在生成 Index 时必须使用 String 的实例来进行计算:

let str = "String 的切片为什么这么难用?"
let k = 1
let targetIndex = str.index(str.startIndex, offsetBy: k) // 这里必须使用 str 去生成 Index
print(str[targetIndex])
复制代码

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

并且由于这种实现的特点,不同的 String 实例生成的 Index 也不应该被混用的:

// |   C    |        |            语            |            言            |
// | U+0043 | U+0020 |          U+8BED          |          U+8A00          |
// |   43   |   20   |   E8   |   AF   |   AD   |   E8   |   A8   |   80   |
let str = "C 语言"

// |   C    |   l    |   a    |   n    |   g    |
// | U+0043 | U+006C | U+0061 | U+006E | U+0067 |
// |   43   |   6C   |   61   |   6E   |   67   |
let str2 = "Clang"

// i.encodedOffset    == 2 (偏移量)
// i.transcodedOffset == 3 (长度)
let i = str.index(str.startIndex, offsetBy: 2) 

print(str[i])  // 语
print(str2[i]) // ang
复制代码

Swift 开发组表示过 Index 的混用属于一种未定义行为,在未来有可能会在运行时作为错误抛出。

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

如果不需要让 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 里扩展一些集合相关的函数时,一模一样的代码需要在 StringCollection 里各写一套实现。

尽管我们确实需要 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 其实是绝对索引,但对于我们来说,ArrayArraySlice 除了在生命周期处理时需要注意之外,其它 API 的调用都不会存在任何差异,也不应该存在差异,使用相对索引屏蔽掉数组和切片之间的差异应该是更好的选择,那还为什么要设计成现在的样子?

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

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

我们想要的是相对索引

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

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

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

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

前面提到了 Index == IntCollection 类型一定是从 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 == IntCollection,直接使用 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 来下标取值时,难道这不是一个程序员的失误吗?

ArrayDictionary 的使用场景是存在差异的。

我认为 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] 却是非常常见的。

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

总结

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

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

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

参考链接:

关注下面的标签,发现更多相似文章
评论