详解Swift的类型检查器

• 原文链接: Exponential time complexity in the Swift type checker
• 原文作者: Matt Gallagher
• 译文出自: 掘金翻译计划
• 译者: Zheaoli
• 校对者: geeeeeeeeek, Graning

这篇文章将围绕曾不断使我重写代码的一些 Swift 编译器的报错信息展开：

错误：你的表达式太过于复杂，请将其分解为一些更为简单的表达式。（译者注：原文是 error: expression was too complex to be solved in reasonable time; consider breaking up the expression into distinct sub-expressions）

我会看那个触发错误的例子，谈谈以后由相同底层问题引起以外的编译错误的负面影响。我将会带领你看看在编译过程中发生了什么，然后告诉你，怎样在短时间内去解决这些报错。

我将为编译器设计一种时间复杂度为线性算法来代替原本的指数算法来彻底的解决这个问题，而不需要采用其余更复杂的方法。

正确代码的编译错误

如果你尝试在 Swift 3 中编译这段代码，那么将会产生报错信息：

let a: Double = -(1 + 2) + -(3 + 4) + 5

这段代码无论从哪方面来讲都是合法且正确的代码，从理论上讲，在编译过程中，这段代码将会被优化成一个固定的值。

但是这段代码在编译过程中没有办法通过 Swift 的类型检查。编译器会告诉你这段代码太复杂了。但是，等等，这段代码看起来一点都不复杂不是么。里面包含 5 个变量， 4 次加法操作， 2 次取负值操作和一次强制转换为 Double 类型的操作。

但是，编译器你怎么能说这段仅包含 12 个元素的语句相当复杂呢？

这里有非常多的表达式在编译的时候会出现同样的问题。大多数表达式包含一些变量，基础的数据操作，可能还有一些重载之类的操作。接下来的表达式在编译时会面对同样的错误信息：

let b = String(1) + String(2) + String(3) + String(4)

let c = 1 * sqrt(2.0) * 3 * 4 * 5 * 6 * 7

let d = ["1" + "2"].reduce("3") { "4" + String($0) + String($1) }

let e: [(Double) -> String] = [
  { v in String(v + v) + "1" },
  { v in String(-v) } + "2",
  { v in String(Int(v)) + "3" }
]

上面的代码都是符合 Swift 语法及编程规则的，但是在编译过程中，它们都没有办法通过类型检查。

需要较长的编译时间

编译报错只是 Swift 类型检查器缺陷带来的副作用之一，比如，你可以试试下面这个例子：

let x = { String("\($0)" + "") + String("\($0)" + "") }(0)

这段代码编译时不会报错，但是在我的电脑上，使用 Swift 2.3 将花费 4s 的时间，如果是使用 Swift 3 将会花费 15s 时间。编译过程中，将会花费大量的时间在类型检查上。

现在，你可能不会遇到太多需要耗费这么多时间的问题，但是一个大型的 Swift 项目中，你将会遇到很多 expression was too complex to be solved in reasonable time 这样的报错信息。

不可预知的操作

接下来，我将讲一点 Swift 类型检查器的特性：类型检查器选择尽可能的解决非泛型重载的问题。 编译器中处理这种特定行为的路径下的代码注释对此给出了解释，这是一种避免性能问题的优化手段，用于优化造成 expression was too complex 报错的性能问题。

接下来是一些具体的例子：

let x = -(1)

这段代码将会编译失败，我们会得到一个 Ambiguous use of operator ‘-‘ 的报错信息。

这段代码并不算很模糊，编译器将会明白我们想要使用一个整数类型的变量，它将会把 1 作为一个 Int 进行处理，同时从标准库中选择如下的重载方式：

prefix public func -<T : SignedNumber>(x: T) -> T

然而，Swift 只能进行非泛型重载。在这个例子中，Float 、 Double 、 Float80 类型的实现并不完善，编译器无法根据上下文选择使用哪种实现，从而导致了这个报错信息。

某些特定的优化可以对操作符进行优化，但是可能导致如下的一些问题：

func f(_ x: Float) -> Float { return x }
func f<I: Integer>(_ x: I) -> I { return x }

let x = f(1)

prefix operator %% {}
prefix func %%(_ x: Float) -> Float { return x }
prefix func %%<I: Integer>(_ x: I) -> I { return x }

let y = %%1

在这段代码里，我们定义了两个函数（ f 和一个自定的操作 prefix %% ）。每个函数都进行了两次重载，一个参数为 (Float) -> Float ，另一个是 <I: Integer>(I) -> I。

当调用 f(1) 的时候，将会选择使用 <I: Integer>(I) -> If(1) 的实现，然后 x 将会作为 Int 类型进行处理。这应该是你所期待的方式。

当调用 %%1 时，将会使用 (Float) -> Float 的实现，同时会将 y 作为 Float 类型处理，这和我们所期望的恰恰相反。在编译过程中，编译器选择将 1 作为 Float 处理，而不是作为 Int 处理，虽然作为 Int 处理也同样能正常工作。造成这样情况的原因是，编译器在对方法的进行泛型重载之前就已经先行确定变量的类型。这不是基于前后文一致性的做法，这是编译器对于避免类似于 expression was too complex to be solved 等报错信息以及性能优化上的一种妥协。

在代码中解决上诉问题

通常来讲，Swift 里的显示代码太过复杂的缺陷并不是一个太大的问题，当然前提是你不会在单个表达式里使用两个或两个以上的下面列出的特性：

• 方法重载（包括操作符重载）
• 常量
• 不明确类型的闭包
• 会引导 Swift 进行错误类型转换的表达式

一般而言，如果你不使用如上面所述的特性，那么你一般不会遇到类似于 expression was too complex 的报错信息。然而，如果选择是用了上面所诉的特性，那么你可能会面临一些让你感到困惑的问题。通常，在编写一个足够大小的方法和其余常规代码的时候，将会很容易用到上面这些特性，这意味着有些时候我们可能要仔细考虑怎样避免大量使用上面这些特性。

你肯定是想只通过一点细微的修改来通过编译，而不是大量修改你的代码。接下来的一点小建议可能帮得上一些忙。

当上面所诉的编译报错信息出现时，编译器可能建议你将原表达式分割成不同的子表达式：

let x_1: Double = -(1 + 2)
let x_2: Double = -(3 + 4)
let x: Double = x_1 + x_2 + 5

好了，从结果上来看，这样的修改是有效的，但是却让人有点蛋疼，特别是在分解成子表达式的时候会明显破坏代码可读性的时候。

另一个建议是通过显示类型转换，减少编译器在编译过程中对方法和操作符重载的选取次数。

let x: Double = -(1 + 2) as Double + -(3 + 4) as Double + 5

上面这种做法避免了在使用 (Float) -> Float 或者是 (Float80) -> Float80 编译器需要去查找相对应的负号重载。这样的做法很有效的将编译过程中编译器的6次查找相对应的方法重载过程降至4次。

在上面的处理方式中有一个点要注意一下：不同于其余语言，在 Swift 中 Double(x) 并不等同于 x as Double。构造函数通常会如同普通方法一样，当有不同参数的重载需求时，编译器还是会将构造函数的各种重载加入到搜索空间中（尽管这些重载可能在代码中的不同的位置）。在前面所举的例子里，通过在括号前用 Double 进行显示类型转换会解决一部分问题（这种方法有利于编译器进行类型检查），同时在一些情况下，采用这种方法会导致出现一些其余的问题（请参见本文开始所举的关于 String 的例子）。最终， 使用as 操作符是在不增加复杂度的情况下解决这类的问题的最好方式。幸运的是，as 操作符的优先级比大多数二元运算符更高，这样我们可以在大多数的情况下使用它。

另一种方法是使用一个独立命名的自定义函数：

let x: Double = myCustomDoubleNegation(1 + 2) + myCustomDoubleNegation(3 + 4) + 5

这种方法可以解决之前方法重载所带来的一系列问题。然而，在一系列轻量级的代码里使用这种方式会让我们的代码显得格外的丑陋。

好了，让我们来说说最后的方法，在很多情况下，你可以根据情况自行替换方法和操作符：

let x: Double = (1 + 2).negated() + (3 + 4).negated() + 5

因为在使用对应方法时，和使用常见算数运算符相比，会有效的减少重载次数，同时使用 . 操作符时其效率相较于直接调用方法更高，因此，这种方法能有效解决我们前面所提到的问题。

Swift类型约束系统简析

编译时出现的 expression was too complex 错误是由 Swift 编译器的语义分析系统所抛出的。语义分析系统的意义在于解决整个代码里的类型问题，从而确保输入表达式的类型是正确且安全的。

最重要的是，整个报错信息是由the constraints system solver (CSSolver.cpp)里所编写的语义分析系统所定义的。类型约束系统将从 Swift 的表达式里构建一个由类型和方法组成的图，并根据节点之间的关系来对代码进行约束。约束系统将对每个节点进行推算直至每个节点都已获得明确的类型约束。

讲真，上面的东西可能太抽象了，让我们看点具体的例子吧。

let a = 1 + 2

类型约束系统将表达式解析成下面这个样子：

每个节点的名字都以 T 开头（意味着需要待确定明确的类型），然后它们用来代表需要解决的类型约束或者方法重载。在这个图里，这些节点被如下的规则所约束：

1. T1 是 ExpressibleByIntegerLiteral 类型
2. T2 是 ExpressibleByIntegerLiteral 类型
3. T0 是一个传入 (T1,T2) 返回 T3 的方法
4. T0 是 infix + ，其在 Swift 里有28种实现
5. T3 与 T4 之间可以进行交换

小贴士: 在 Swift 2.X 中，ExpressibleByIntegerLiteral 的替代者是 IntegerLiteralConvertible

在这个系统中，类型约束系统遵循着 最小分离 原则。分割出来的单元被这样一个规则所约束着，即，每个单元都是一个拥有一套独立值的个体。在上面的这个例子里，实际上只有一个最小单元：在上述的约束 4 里，T0 发生了重载。在重载之时，编译器选择了 infix + 实现列表里第一种实现：即签名是 (Int, Int) -> Int 的实现。

通过上述这个最小的单元，类型约束系统开始对元素进行类型约束：根据约束 3 T1、 T2 、 T3 被确定为 Int 类型，根据约束 4 ， T4 同样被确认为 Int 类型。

在 T1 、 T2 被确定为 Int 之后（最开始它们被认为是 ExpressibleByIntegerLiteral）， infix + 的重载方式便已经确定，这个时候编译器便不需要再考虑其余可行性，并把其当做最终的解决方案。我们在确定每个节点对应的类型后，我们便可以选择我们所需要的重载方法了。

让我们看点复杂的例子吧！

到目前为止，并没有什么超出我们意料之中的异常出现，你可能想象不到当表达式开始变得复杂之时， Swift 的编译系统将会开始不断的出现错误信息。来让我们修改下上面的例子：第一·将 2 放在括号里，第二·添加负号操作符，第三·规定返回值为 Double 类型。

let a: Double = 1 + -(2)

整个节点结构如下图所述：

节点约束如下：

1. T1 是 ExpressibleByIntegerLiteral 类型
2. T3 是 ExpressibleByIntegerLiteral 类型
3. T2 是一个传入 T3 返回 T4 的方法
4. T2 是 prefix -，其在 Swift 里有6种实现
5. T0 是一个传入 T1、T4，返回 T5 的方法
6. T0 是 infix + ，其在 Swift 里有28种实现
7. T5 是 Double 类型

相较于上面的例子，这里多了两个约束，让我们看看类型约束系统会怎样处理这个例子。

第一步：选择最小分离单元。这次是约束 4 ：“ T2 是 prefix -，在 Swift 里有6种实现”。最后系统选择了签名为 (Float) -> Float 的实现。

第二步：和第一步一样，选择最小分离单元，这次是约束 6 ：“T0 是 infix + ，其在 Swift 里有28种实现”。系统选择了签名为 (Int, Int) -> Int 的实现。

最后一步是：利用上述的类型约束确定所有节点的类型。

然而，这里出现了点问题：在第一步里我们选择的签名为 (Float) -> Float 的 prefix - 实现和第二步里我们选择的签名为 (Int, Int) -> Int 的 infix + 实现和我们的约束 5 （T0 是一个传入 T1、T4，返回 T5 的方法）发生了冲突。解决方法是放弃当前的选择，然后重新回滚至第二步，为 T0

最终，系统将遍历所有的 infix + 实现，然后发现没有一种实现同时满足约束 5 和约束 7 （T5 是 Double 类型）。

所以，类型约束系统将回滚至第一步，为 T2 选取了签名为 (Double, Double) -> Double 的实现。最后，这种实现也满足了 T0 的约束。

然而，在发现 Double 类型和 ExpressibleByIntegerLiteral 相互不匹配后，类型约束系统将继续回滚，寻找合适的重载方法。

T2 总共有6种实现，但是最后3种实现不能被优化(因为它们是通用的实现，因此优先级高于显示声明参数为 Double 的实现）。

在类型约束系统里，这种特殊优化是我曾经在Unexpected behaviors一文中提到的快速重载的一些特性。

拜这种特殊的“优化”所赐，类型约束系统需要76次查询才能找到一个合理的解决方案。如果我们添加了其余的一些新的重载，那么这个数字会变得超出我们的想象。例如，我们我们在例子里添加另外一个 infix + 操作符，比如： let a: Double = 0 + 1 + -(2) ，那么将需要1190次查询才能找到合理的解决方案。

查询解决方案的这个过程是一个典型的具有指数时间复杂度的操作。在分离单元里进行搜索的范围称为“笛卡尔积”，然后，对于图中的 $n$ 个分离单元，算法将会在 n 维笛卡尔乘积的范围内进行查找（这是一个空间复杂度同样为指数的操作）。

根据我的测试，单语句内拥有6个分离单元，便足以触发 Swift 中的 expression was too complex 的错误。

线性化的类型约束系统

针对本文所反复提到的这个问题，最好的解决方法就是在编译器中进行修复。

类型约束系统之所以采用时间复杂度为指数算法来解决方法重载的问题，是因为 Swift 需要对方法重载所生成的 n 维“笛卡尔乘积”空间里的元素进行遍历并搜索从而确定一个合适的选项（在没有更好方案之前，这应该是最好的方案）。

为了避免生成 n 维笛卡尔乘积空间，我们需要设计一个方法来实现相关逻辑实现的独立性，而不让它们彼此依赖。

在开始之前我必须给你们一个很重要的提醒：

友情提醒，这些东西仅代表我的个人观点：接下来的一些讨论，都是我从理论的角度上来分析怎样在 Swift 的类型约束系统中怎样去解决函数重载的问题。我并没有写一些东西来证明我提出的解决方案，这可能意味着我会忽略某些非常重要的东西。

前提

我们想实现如下两个目标：

1. 限制一个节点不应该与其余节点相互依赖或引用
2. 从前一个方法分析出来的分离单元应该与后一个方法分离出来的存在着交集，并进一步简化分离单元的两个约束条件。

第一个目标，可以通过限制节点的约束路径实现。在 Swift 中，每个节点的约束是双向的，每个节点的约束都从表达式的每一个分支开始，然后依照着遍历主干->线性遍历子节点的方式不断传播。在这个过程中，我们可以有选择性的简单地合并相同的约束逻辑来组合这些约束，而不是从其余节点引用相对应的类型约束。

第二个目标里，支持前面通过减少类型约束的传播复杂度来进一步简化相关约束条件。每个重载方法的分离单元之间最重要的交叉点是一个重载函数的输出，可能会作为另一个重载函数的输入。这个操作应该根据参数相互交叉的两个重载方法所产生的2维笛卡尔积来进行计算。对于其余的可能存在的交叉点来说，给出一个真正意义上的数学上的严格交叉证明是非常困难的，同时这样的证明是没有必要的，我们只需要复制 Swift 里在复杂情况下的对于类型选择的时所采用的贪婪策略即可。

让我们重新看看之前的例子

让我们看看如果我们实现了前文所讲的两个目标后，类型约束系统将会变成什么样子。首先让我们复习下之前所生成的节点图：

let a: Double = 1 + -(2)

然后让我们也复习下以下节点约束：

1. T1 是 ExpressibleByIntegerLiteral 类型
2. T3 是 ExpressibleByIntegerLiteral 类型
3. T2 是一个传入 T3 返回 T4 的方法
4. T2 是 prefix -，其在 Swift 里有6种实现
5. T0 是一个传入 T1、T4，返回 T5 的方法
6. T0 是 infix + ，其在 Swift 里有28种实现
7. T5 是 Double 类型

将节点约束从右至左传递

我们从右至左进行遍历（从叶子节点向主干遍历）。

在节点约束从 T3 向 T2 传播时，添加了这样一个新的约束：“ T2 节点的输入值必须是一个由 ExpressibleByIntegerLiteral 转化而来的值”。现在在新的约束规则和原有规则同时发生作用后，一旦我们确认所有拥有 T2 的节点都被新规则约束成功之后，或者是与“特定操作重载优先于通用操作重载（比如在 prefix - 中 Double、 Float 或者是 Float80 会被优先重载）”这条规则冲突之时，便可以丢弃我们新建立的节点约束规则。在节点约束从 T2 向 T4 中传播的过程中，添加新约束为：“ T4 必须是 prefix - 所返回的6中类型的值之一，其中 Double、Float 或 Float80 优先被考虑）。在节点约束从 T4 朝 T0 传播的过程中，添加新约束为：“ T0 的第二个参数必须是从 prefix - 返回的6种参数里的任意一种演变而来，其中 Double、 Float 或 Float80 类型优先）。在结合 T0 已有的节点约束后，T0 的节点约束变为：“ T0 是 infix + 的6种实现之一，同时从右侧传入的参数是来自 prefix - 返回参数中的任意一种，在这个过程中类型是 Double、 Float 或者 Float80 的参数优先被考虑）。在节点约束从 T1 朝 T0 传递之时，没有新的约束条件需要添加（在这里，T0 已经被我们所增加的约束条件严格约束了，同时，原本所使用的 ExpressibleByIntegerLiteral 类型已经被 Double、 Float 或者 Float80 中的任意一种类型所替代了）。在节点约束从 T0 向 T5 传播时，需新增加约束为：“ T5 是 infix + 的6种返回值中的一种，且 infix + 的第二个参数是来自 prefix - 的返回值，在这个过程中，Double、 Float 或者 Float80 类型优先被考虑）。在上述约束的共同作用下，我们可以最终确认 T5 的类型为 Double。

经过上述过程的变动之后，整个节点约束集迭代成下面这个样子：

1. T1 是 ExpressibleByIntegerLiteral 类型
2. T3 是 ExpressibleByIntegerLiteral 类型
3. T2 是一个传入 T3 返回 T4 的方法
4. T2 是 prefix - 的6种实现之一，同时为了满足在 Swift 中特殊操作重载优先级高于通用运算重载的原则，类型为 Double、 Float 或者 Float80 的 prefix - 重载优先被考虑。
5. T4 是 prefix - 的六种返回值之一，同样为了满足在 Swift 中特殊操作重载优先级高于通用运算重载的原则，类型为 Double、 Float 或者 Float80 的 prefix - 重载优先被考虑。
6. T0 是一个传入 T1、T4，返回 T5 的方法
7. T0 是 infix + 的6种实现之一，同时从右侧传入的参数是来自 prefix - 返回参数中的任意一种，在这个过程中为了满足在 Swift 中特殊操作重载优先级高于通用运算重载的原则，类型是 Double、 Float 或者 Float80 的参数优先被考虑
8. T5 是 Double 类型

将节点约束从左至右传递

现在我们开始从左至右进行遍历（先遍历主干，后遍历叶子节点）。

首先从 T5 开始遍历，约束 5 是：“ T5 是 Double 类型的节点”。这时我们为 T0 添加新的约束：“ T0 的返回值类型一定要是 Double 类型的”。在这个约束生效后，我们就可以排除除 (Double, Double) -> Double 之外的 infix + 的重载了。节点约束继续从 T0 朝 T1 传递，根据 infix + 的(Double, Double) -> Double 重载的参数要求，我们为 T1 创建一个新的约束： T1 一定是 Double 类型的。在多种约束的作用下，之前所提到的“T1 是 ExpressibleByIntegerLiteral 类型”变为“T1 是 Double 类型”。在节点约束从 T0 朝 T4 ，根据 infix + 的第二个参数的要求，我们确定 T4 的类型为 Double。节点约束从 T4 朝 T2 传播的过程中，我们新增加一个约束：“ T2 的返回值一定为 Double 类型”。在以上规则共同作用下，我们可以确定 T2 为 prefix - 的参数类型为 (Double) -> Double 重载。最后根据以上的约束，我们可以得知 ‘T3’ 的类型为 ‘Double’。

最后整个类型约束系统编程下面这个样子：

1. T1 为 Double 类型。
2. T3 为 Double 类型。`
3. T2 是 prefix - 的参数为 (Double) -> Double 类型的重载
4. T0 是 infix + 的参数为 (Double, Double) -> Double 类型的重载
5. T5 为 Double 类型。

好了，现在整个类型约束操作便已经告一段落了。

唔，我提出这算法的目的是改善方法重载的相关操作，因此，我将方法重载的次数用 n 表示。然后我将平均每个函数重载次数用 m 表示。

如我前面所述，在 Swift 中，编译器是通过在一个 n 维的笛卡尔积空间内进行搜索来确定最终的结果。它的时间复杂度是 O(m^n) 。

而我所提出的算法，是在一个2维的空间内去搜索 n-1 个分离单元来实现的。其执行时间是 m^2*n.因为 m 是和 n 相关联的，我们可以得到其最终的时间复杂度为 O(n) 。

通常来讲，在 n 为很大的时候，线性复杂度的算法比指数时间复杂度的算法更能适应当前的状况，不过我们得搞清楚什么样的情况才能被称之为 n 为很大的数。在这个例子中，3 已经是一个非常 “大” 的数了。正如我前面所提到的一样，Swift 自带的类型约束系统将进行1190次搜索来确认最后的结果。而我设计的算法只需要336次搜索。这可以说很明显的降低了最后的耗时。

我做了一个很有趣的实验：在之前所提到的 let a: Double = 1 + -(2) 这个例子里，不管是 Swift 里的类型约束系统，还是我所设计的算法，它们都是在一个2维的笛卡尔积空间内进行搜索，里面都包含了168中可能性。

Swift 里现在所采用的类型约束算法选取了在 prefix - 和 infix + 重载生成的2维笛卡尔积空间内的168种可能性的76种。但是这样做的话，整个过程里会产生567次对 ConstraintSystem::matchTypes的调用，其中546次是用于搜索相适应的重载函数。

我所设计的算法，搜索了全部168种可能性，但是根据我的分析，其最后只产生了22次对 ConstraintSystem::matchTypes 的调用。

去确定一个非公开的算法，需要进行很多次的猜测，所以知道某一种算法的的具体细节是一件非常困难的事儿。但是我想，我的算法在任意数量级的情况下，其表现优于或与现在已有的算法持平并不是一件不可能的事儿。

Swfit 很快会改进他的类型系统么？

虽然我很想说：“我一个人就把所有工作做完了，看看这些代码运行的多么完美啊”，但是这也只能是想想罢了。一个整个系统由成千上万个逻辑和单元组成，并不能单独抽出某一个节点来进行讨论。

你觉得 Swift 开发团队是不是在尝试把类型约束系统进行线性化处理呢？我对此持否定看法。

在这篇文章里“[swift-dev] A type-checking performance case study”表明官方开发者认为类型约束系统采用时间复杂度为指数的算法是一件很正常的事儿。与其将时间放在优化算法上，还不如去重构标准库，使其更为合理。

一点吐槽：

• 现在看来本文的前面两章简直就是在做无用功，我应该静静的将其删除。
• 我觉得我想法是正确的，类型约束系统应该进行大幅度改进，这样我们次啊不会被上面所提到的问题所困扰。

友情提醒: 理论上将类型约束系统并不是整个语言最主要的一部分，因此如果其进行了改进，应该是在一个小版本迭代中进行发布，而不是一个大版本更新。

结论

在我使用 Swift 的经历里, expression was too complex to be solved in reasonable time 是一个经常出线的错误，而且我并不认为这是一个简单的错误。如果你在单个例子中是用了大量的方法或者是数学操作的时候，你应该定期看看这篇文章。

Swift 里所采用的时间复杂度为指数的算法也可能导致编译时间较长的问题。 尽管我没有确切的统计整个编译里的时间分配，但是不出意外的话，系统应该将大部分时间放在了类型约束器的相关计算上。

这个问题可以再我们编写的代码的时候予以避免，但是讲真，没有必要这么做。如果编译器能采用我所提出的线性时间的算法的话，我敢肯定，这些问题都不在是问题。

在编译器做出具体的改变之前，本文所提到的问题会一直困扰着我们，与编译器的斗争还要持续下去。