类型构造与循环检测

Go 的静态类型是其能够很好地适应需要健壮可靠的生产系统的重要原因之一。编译 Go 包时，首先进行解析——即将包中的 Go 源代码转换为抽象语法树（AST）。随后，该 AST 被传递给 Go 类型检查器。

在这篇博文中，我们将深入探讨在 Go 1.26 中我们显著改进的类型检查器的一部分。这对 Go 用户来说意味着什么变化呢？除非您热衷于晦涩的类型定义，否则这里没有明显的变化。这次改进旨在减少边界情况，为 Go 未来的改进奠定基础。同时，这也是一个有趣的机会，来看看对 Go 程序员来说看似普通、实则隐藏着真正微妙之处的东西。

但首先，什么是类型检查？它是 Go 编译器中的一个步骤，在编译时消除整类错误。具体来说，Go 类型检查器验证：

• AST 中出现的类型是否有效（例如，map 的键类型必须是可比较的）。
• 涉及这些类型（或其值）的操作是否有效（例如，不能将 int 和 string 相加）。

为了实现这一点，类型检查器在遍历 AST 时为遇到的每个类型构建一个内部表示——这个过程非正式地称为类型构造。我们很快就会看到，尽管 Go 以其简单的类型系统闻名，但在语言的某些角落，类型构造可能出乎意料地复杂。

类型构造

让我们从一个简单的类型声明对开始：

type T []U
type U *int

当类型检查器被调用时，它首先遇到类型声明 T。这里，AST 记录了一个类型名 T 和一个类型表达式 []U 的类型定义。T 是一个定义类型；为了表示类型检查器在构造定义类型时使用的实际数据结构，我们将使用一个 Defined 结构体。

Defined 结构体包含一个指针，指向类型名右侧的类型表达式的类型。这个 underlying 字段与获取类型的底层类型相关。为了帮助说明类型检查器的状态，让我们看看遍历 AST 如何填充数据结构，从以下开始：

此时，T 处于正在构造中，以黄色表示。由于我们尚未计算类型表达式 []U——它仍然是黑色——underlying 指向 nil，以空心箭头表示。

当我们计算 []U 时，类型检查器构建了一个 Slice 结构体，这是用于表示切片类型的内部数据结构。与 Defined 类似，它包含一个指向切片元素类型的指针。我们还不知道名称 U 指的是什么，尽管我们期望它指向一个类型。所以，这个指针也是 nil。

现在你可能已经明白大意了，所以我们将加快节奏。将类型名 U 转换为类型的第一步是查找它指向的类型声明。这会给我们另一个 Defined 结构体，其中包含 *int 类型。*int 是一个指针类型，其元素类型是 int——一个基本类型，因此是完整的。

当 U 完成构造后，我们返回栈顶：

现在，U 的 Defined 结构体已填充完成，因此切片的结构体现在可以完成构造：

最后，T 现在可以完成构造了：

上面的编号显示了类型完成的顺序（在指针之后）。注意底部的类型先完成。类型构造天然是一个深度优先的过程，因为完成一个类型需要其依赖项先完成。

递归类型

有了这个简单的例子，让我们增加一点复杂性。Go 的类型系统也允许我们表达递归类型。一个典型的例子是：

type Node struct {
    next *Node
}

如果我们重新考虑上面的例子，可以通过将 *int 改为 *T 来加入一点递归：

type T []U
type U *T

现在进行一次跟踪：让我们再次从 T 开始，但跳过一些步骤来说明这一变化的效果。正如人们从我们之前的例子中可能推测的那样，类型检查器将在以下状态下处理 *T 的计算：

问题是 *T 的基类型该怎么办。我们知道 T 是什么（一个 Defined），但它目前正在构造中（其 underlying 仍然是 nil）。

我们简单地将 *T 的基类型指向 T，即使 T 是不完整的：

我们这样做是假设 T 将在未来完成构造时指向一个完整的类型。当这种情况发生时，base 将指向一个完整的类型，从而使 *T 完成。

与此同时，我们开始返回栈顶：

当我们回到顶部并完成构造 T 时，类型的"循环"将闭合，同时完成循环中的每个类型：

在考虑递归类型之前，计算类型表达式总是返回一个完整的类型。这是一个方便的特性，因为这意味着类型检查器总是可以解构（查看内部）从计算返回的类型。

但在上面的例子中，T 的计算返回了一个不完整的类型，这意味着在 T 完成之前解构 T 是不安全的。一般来说，递归类型意味着类型检查器不能再假设从计算返回的类型是完整的。

然而，类型检查涉及许多需要解构类型的检查。一个典型的例子是确认 map 键是可比较的，这需要检查 underlying 字段。我们如何安全地与像 T 这样的不完整类型交互？

回想一下，类型完整性是解构类型的前提条件。在这种情况下，类型构造从不在构造期间解构不完整的类型。完成一个类型后，它保证包含指向其他已完成类型的指针，使其本身完整——因此可以安全解构。

但等等！如果我们在类型完成之前试图解构它会发生什么？这如何发生？如果我们不小心，类型检查器可能被诱导去做类似以下的事情：

type T [unsafe.Sizeof(T{})]int

这源于在类型 T 的数组长度表达式中使用了类型 T 的复合字面量。这里，T 既是数组元素类型，也出现在数组长度中。这创建了一个循环定义：数组的长度依赖于 T{}（一个复合字面量）的大小，但 T 本身正在被定义。

类型检查器面临一个困境：

• unsafe.Sizeof 需要 T 的大小，这需要 T 的底层类型完成。
• 数组的长度会影响 T 的结构（因为是数组类型），这又需要 T 完成。
• 它们不能同时完成（不像之前）。

显然，这是不可能满足的。类型检查器该怎么办？

循环检测

从根本上说，这样的代码是无效的，因为 T 的大小无法在不了解 T 大小的情况下确定，无论类型检查器如何运作。这个特定实例——循环大小定义——属于一类称为循环错误的错误，通常涉及 Go 构造的循环定义。另一个例子是 type T T，它也属于这一类，但原因不同。在类型检查过程中查找和报告循环错误的过程称为循环检测。

那么，循环检测如何处理 type T [unsafe.Sizeof(T{})]int？为了回答这个问题，让我们看看内部的 T{}。因为 T{} 是一个复合字面量表达式，类型检查器知道其结果值是 T 类型。由于 T 不完整，我们称值 T{} 为一个不完整值。

我们必须谨慎——操作不完整值只有在不解构该值的类型时才是安全的。例如，type T [unsafe.Sizeof(new(T))]int 是安全的，因为值 new(T)（类型为 *T）从未被解构——所有指针都有相同的大小。重申一下，对类型 *T 的不完整值计算大小是安全的，但对类型 T 则不安全。

这是因为 *T 的"指针性"为 unsafe.Sizeof 提供了足够的类型信息，而仅 T 则不能。事实上，操作类型为定义类型的不完整值从来都是不安全的，因为仅一个类型名不传达任何（底层）类型信息。

在哪里进行

到目前为止，我们专注于 unsafe.Sizeof 直接操作可能不完整的值。在 type T [unsafe.Sizeof(T{})]int 中，对 unsafe.Sizeof 的调用只是数组长度表达式的"根"。我们可以很容易地想象不完整值 T{} 作为某个其他值表达式中的操作数。我们将这些可能产生不完整值的表达式称为上游：

例如，它可以被传递给一个函数（即 type T [unsafe.Sizeof(f(T{}))]int）、切片（type T [unsafe.Sizeof(T{}[:])]int）、索引（type T [unsafe.Sizeof(T{}[0])]int）等等。所有这些都是无效的，因为它们需要对 T 进行解构。例如，对 T 进行索引需要知道 T 的底层类型（以确定索引操作的含义）。

转换

另一个有趣的例子是类型转换。如果我们写：

type T [unsafe.Sizeof(T(42))]int

这里，T(42) 是一个类型转换。类型检查器需要能够解构 T 来执行转换检查——但 T 不完整。

函数调用

func f() T
type T [unsafe.Sizeof(f())]int

这里，f() 的返回值类型是 T，它不完整。类型检查器需要知道 T 来检查函数调用的结果——但做不到。

更多例子

还有更多情况：

type T [unsafe.Sizeof(i.(T))]int                // 类型断言
type T [unsafe.Sizeof(<-(make(<-chan T)))]int   // 通道接收
type T [unsafe.Sizeof(make(map[int]T)[42])]int  // map 访问
type T [unsafe.Sizeof(*new(T))]int              // 解引用

实现

我们通过在所有可能产生不完整值的位置添加完整性检查来实现循环检测。关键位置之一是 callExpr 函数，它处理函数调用和类型转换：

func callExpr(call *syntax.CallExpr) operand {
    x := typeOrValue(call.Fun)

    switch x.mode() {
    // ... 其他情况
    case typeExpr:
        // T()，意味着是类型转换
        T := x.typ()
        +   if !isComplete(T) {
        +     reportCycleErr(T)
        +     return invalid
        +   }
        // ... 处理转换，T *可以*安全解构
    }
}

我们不返回不完整的值，而是返回一个特殊的无效操作数，表示该调用表达式无法被计算。类型检查器的其余部分对无效操作数有特殊处理。通过添加这个，我们阻止了不完整值"逃逸"到下游——既进入类型转换逻辑的其余部分，也进入下游操作符——而是报告一个描述 T 问题的循环错误。

类似代码模式被用于所有其他情况，实现了对不完整值的循环检测。

结论

系统性地检测涉及不完整值的循环是类型检查器的新增功能。在 Go 1.26 之前，我们使用更复杂的类型构造算法，该算法涉及更特殊的循环检测，且并不总是有效。我们的新方法更简单，解决了一些（诚然是深奥的）编译器 panic（issue #75918、#76383、#76384、#76478 等），从而使编译器更加稳定。

作为程序员，我们已经习惯于递归类型定义和定长数组类型等特性，以至于可能会忽略其底层复杂性的微妙之处。虽然这篇文章跳过了某些细节，但希望我们已经让你对隐藏在明显事物背后的细微之处有了一些认识。