Go 博客

所有可比较类型

Robert Griesemer
2023 年 2 月 17 日

我们在 2 月 1 日发布了最新的 Go 版本 1.20,其中包括一些语言上的改动。在这里,我们将讨论其中一个改动:预声明的 comparable 类型约束现在会被所有 可比较类型 满足。令人惊讶的是,在 Go 1.20 之前,一些可比较类型并不能满足 comparable

如果您感到困惑,那么您来对地方了。考虑以下有效的 map 声明

var lookupTable map[any]string

其中 map 的键类型是 any (这是一个 可比较类型)。这在 Go 中完美运行。另一方面,在 Go 1.20 之前,看起来等效的泛型 map 类型

type genericLookupTable[K comparable, V any] map[K]V

可以像普通 map 类型一样使用,但当使用 any 作为键类型时会产生编译时错误

var lookupTable genericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19)

从 Go 1.20 开始,这段代码将正常编译。

Go 1.20 之前 comparable 的行为特别令人恼火,因为它阻止了我们编写原本希望使用泛型编写的那种泛型库。提议的 maps.Clone 函数

func Clone[M ~map[K]V, K comparable, V any](m M) M { … }

可以编写,但无法用于像 lookupTable 这样的 map,原因与我们的 genericLookupTable 无法使用 any 作为键类型的原因相同。

在这篇博文中,我们希望阐明这一切背后的语言机制。为此,我们首先提供一些背景信息。

类型参数和约束

Go 1.18 引入了泛型,随之而来的是 类型参数 作为一种新的语言构造。

在普通函数中,参数的取值范围受到其类型的限制。类似地,在泛型函数(或类型)中,类型参数的类型范围受到其 类型约束 的限制。因此,类型约束定义了允许用作类型实参的类型集合

Go 1.18 也改变了我们看待接口的方式:过去接口定义了一组方法,现在接口定义了一组类型。这种新观点完全向后兼容:对于接口定义的任何一组方法,我们可以想象实现这些方法的所有类型的(无限)集合。例如,给定一个 io.Writer 接口,我们可以想象所有具有适当签名的 Write 方法的类型的无限集合。所有这些类型都实现了该接口,因为它们都具有必需的 Write 方法。

但是新的类型集合观点比旧的方法集合观点更强大:我们可以显式地描述一组类型,而不仅仅是通过方法间接地描述。这为我们提供了控制类型集合的新方法。从 Go 1.18 开始,接口不仅可以嵌入其他接口,还可以嵌入任何类型、类型联合,或者共享相同 底层类型 的无限类型集合。然后将这些类型包含在 类型集合计算 中:联合表示法 A|B 表示“类型 A 或类型 B”,而 ~T 表示“所有具有底层类型 T 的类型”。例如,以下接口

interface {
    ~int | ~string
    io.Writer
}

定义了所有底层类型为 intstring,并且还实现了 io.WriterWrite 方法的类型集合。

这种泛化接口不能用作变量类型。但由于它们描述的是类型集合,因此它们被用作类型约束,而类型约束就是类型的集合。例如,我们可以编写一个泛型 min 函数

func min[P interface{ ~int64 | ~float64 }](x, y P) P

它接受任何 int64float64 参数。(当然,更实际的实现会使用一个约束来枚举所有支持 < 运算符的基本类型。)

顺便说一句,由于枚举没有方法的显式类型很常见,一点点 语法糖 允许我们 省略外部的 interface{},从而形成更紧凑、更地道的写法

func min[P ~int64 | ~float64](x, y P) P { … }

有了新的类型集合观点,我们还需要一种新的方式来解释 实现 接口意味着什么。我们说(非接口)类型 T 实现了接口 I,当且仅当 T 是接口类型集合中的一个元素。如果 T 本身是一个接口,它描述了一个类型集合。该集合中的每一个类型也必须在 I 的类型集合中,否则 T 将包含未实现 I 的类型。因此,如果 T 是一个接口,当且仅当 T 的类型集合是 I 的类型集合的子集时,它才实现了接口 I

现在我们已经具备了理解约束满足的所有要素。正如我们之前所见,类型约束描述了类型参数可接受的类型实参集合。当类型实参位于约束接口描述的集合中时,该类型实参满足相应的类型参数约束。这是另一种说法,即类型实参实现了约束。在 Go 1.18 和 Go 1.19 中,约束满足意味着约束实现。正如我们稍后将看到的那样,在 Go 1.20 中,约束满足不再完全等同于约束实现。

类型参数值的操作

类型约束不仅指定了类型参数可接受的类型实参,它还决定了对类型参数值可以进行的操作。正如我们所期望的,如果一个约束定义了一个方法,例如 Write,那么可以在相应类型参数的值上调用 Write 方法。更一般地说,如果约束定义的类型集合中的所有类型都支持某个操作,例如 +*,那么相应的类型参数值也可以使用该操作。

例如,以上面的 min 函数为例,在函数体中,任何 int64float64 类型支持的操作都可以在类型参数 P 的值上执行。这包括所有基本算术运算,以及 < 等比较操作。但不包括 &| 等位运算,因为这些操作未定义在 float64 值上。

可比较类型

与其他一元和二元操作不同,== 不仅定义在有限的一组 预声明类型 上,还定义在无限多样的类型上,包括数组、结构体和接口。不可能在约束中枚举所有这些类型。如果我们关注的类型不仅仅是预声明类型,我们需要一种不同的机制来表达类型参数必须支持 ==(当然还有 !=)。

我们通过 Go 1.18 引入的预声明类型 comparable 解决了这个问题。comparable 是一个接口类型,其类型集合是可比较类型的无限集合,并且可以在我们需要类型实参支持 == 时用作约束。

然而,comparable 包含的类型集合与 Go 规范定义的全部 可比较类型 集合并不相同。根据定义,接口(包括 comparable)指定的类型集合不包含接口本身(或任何其他接口)。因此,像 any 这样的接口不包含在 comparable 中,即使所有接口都支持 ==。这是怎么回事?

接口(以及包含它们的复合类型)的比较可能会在运行时发生 panic:当动态类型(存储在接口变量中的实际值的类型)不可比较时,就会发生这种情况。考虑我们最初的 lookupTable 示例:它接受任意值作为键。但是如果我们尝试使用不支持 == 的键(例如切片值)输入值,就会发生运行时 panic

lookupTable[[]int{}] = "slice"  // PANIC: runtime error: hash of unhashable type []int

相比之下,comparable 只包含编译器保证在使用 == 时不会发生 panic 的类型。我们将这些类型称为严格可比较类型

大多数时候,这正是我们想要的:令人欣慰的是,如果操作数受 comparable 约束,泛型函数中的 == 不会发生 panic,这符合我们的直觉。

不幸的是,comparable 的这个定义以及约束满足的规则阻止了我们编写有用的泛型代码,例如前面展示的 genericLookupTable 类型:要使 any 成为可接受的类型实参,any 必须满足(并因此实现)comparable。但是 any 的类型集合比 comparable 的类型集合更大(不是子集),因此 any 未实现 comparable

var lookupTable GenericLookupTable[any, string] // ERROR: any does not implement comparable (Go 1.18 and Go 1.19)

用户很早就认识到这个问题,并迅速提交了大量问题和提案(#51338#52474#52531#52614#52624#53734 等)。显然,这是一个我们需要解决的问题。

“显而易见”的解决方案是简单地将甚至非严格可比较的类型也包含在 comparable 类型集合中。但这会导致与类型集合模型不一致。考虑以下示例

func f[Q comparable]() { … }

func g[P any]() {
        _ = f[int] // (1) ok: int implements comparable
        _ = f[P]   // (2) error: type parameter P does not implement comparable
        _ = f[any] // (3) error: any does not implement comparable (Go 1.18, Go.19)
}

函数 f 需要一个严格可比较的类型实参。显然,使用 int 实例化 f 是可以的:int 值在使用 == 时永远不会 panic,因此 int 实现了 comparable(情况 1)。另一方面,使用 P 实例化 f 是不允许的:P 的类型集合由其约束 any 定义,而 any 代表所有可能类型的集合。该集合包含根本不可比较的类型。因此,P 未实现 comparable,因此不能用于实例化 f(情况 2)。最后,使用类型 any(而不是受 any 约束的类型参数)也不起作用,原因完全相同(情况 3)。

然而,我们确实希望在这种情况下能够使用类型 any 作为类型实参。摆脱这种困境的唯一方法是改变语言。但如何改变呢?

接口实现 vs 约束满足

如前所述,约束满足即接口实现:类型实参 T 满足约束 C,当且仅当 T 实现了 C。这是有道理的:T 必须在 C 期望的类型集合中,这正是接口实现的定义。

但这同时也是问题所在,因为它阻止我们将非严格可比较类型用作 comparable 的类型实参。

因此,对于 Go 1.20,在公开讨论了近一年的众多替代方案(参见上面提到的问题)之后,我们决定仅针对这种情况引入一个例外。为了避免不一致,我们没有改变 comparable 的含义,而是区分了与将值传递给变量相关的接口实现,以及与将类型实参传递给类型参数相关的约束满足。一旦分离,我们可以为这些概念分别赋予(略微)不同的规则,这正是我们在提案 #56548 中所做的。

好消息是,这个例外在 规范 中的范围相当有限。约束满足与接口实现几乎相同,只是有一个例外

类型 T 满足约束 C,当且仅当

  • T 实现了 C;或
  • C 可以写成 interface{ comparable; E } 的形式,其中 E 是一个基本接口,并且 T可比较的 并实现了 E

第二个要点就是这个例外。撇开规范的繁琐形式不谈,这个例外是这样说的:期望严格可比较类型(可能还有方法 E 等其他要求)的约束 C,会被任何支持 == 的类型实参 T 满足(并且 T 也实现了 E 中的方法,如果存在的话)。或者更简短地说:支持 == 的类型也满足 comparable(即使它可能并未实现它)。

我们可以立即看到这个改动是向后兼容的:在 Go 1.20 之前,约束满足与接口实现相同,我们仍然保留该规则(第 1 个要点)。所有依赖该规则的代码继续按以前的方式工作。只有当该规则失败时,我们才需要考虑例外情况。

让我们重新审视之前的示例

func f[Q comparable]() { … }

func g[P any]() {
        _ = f[int] // (1) ok: int satisfies comparable
        _ = f[P]   // (2) error: type parameter P does not satisfy comparable
        _ = f[any] // (3) ok: satisfies comparable (Go 1.20)
}

现在,any 确实满足(但没有实现!)comparable。为什么?因为 Go 允许将 == 用于 any 类型的值(这对应于规范规则中的类型 T),并且因为约束 comparable(对应于规则中的约束 C)可以写成 interface{ comparable; E } 的形式,其中 E 在此示例中只是空接口(情况 3)。

有趣的是,P 仍然不满足 comparable(情况 2)。原因是 P 是一个受 any 约束的类型参数(它不是 any)。操作 ==P 的类型集合中的所有类型上都不可用,因此在 P 上也不可用;它不是一个 可比较类型。因此,此例外不适用。但这没关系:我们确实希望知道,comparable 这个严格可比较的要求在大多数情况下得到了强制执行。我们只是需要对支持 == 的 Go 类型做个例外,这基本上是出于历史原因:我们一直都能够比较非严格可比较的类型。

后果和补救措施

我们 gopher 们感到自豪的是,特定语言的行为可以通过语言规范中阐述的一套相当紧凑的规则来解释和归纳。多年来,我们一直在完善这些规则,尽可能地使其更简单、更通用。我们也一直在小心地保持规则的正交性,时刻警惕意外和不幸的后果。争议通过查阅规范解决,而不是通过规定。这是我们自 Go 诞生以来一直追求的目标。

精心设计的类型系统,添加例外绝非易事,必然伴随后果!

那么问题出在哪里?有一个明显的(尽管是轻微的)缺点,还有一个不太明显(但更严重)的缺点。显然,现在我们的约束满足规则更复杂了,可以说不如以前优雅。这不太可能对我们的日常工作产生重大影响。

但我们确实为这个例外付出了代价:在 Go 1.20 中,依赖 comparable 的泛型函数不再是静态类型安全的。如果对 comparable 类型参数的操作数应用 ==!=,它们可能会发生 panic,即使声明表明它们是严格可比较的。一个不可比较的值可能通过一个非严格可比较的类型实参偷偷溜过多个泛型函数或类型,并导致 panic。在 Go 1.20 中,我们现在可以声明

var lookupTable genericLookupTable[any, string]

而不会出现编译时错误,但如果我们在此例中使用了非严格可比较的键类型,就会发生运行时 panic,就像使用内置的 map 类型一样。我们为了运行时检查而放弃了静态类型安全。

在某些情况下,这可能还不够,我们希望强制执行严格可比较性。以下观察使我们能够做到这一点,至少是有限的形式:类型参数不会从我们添加到约束满足规则中的例外中受益。例如,在我们之前的示例中,函数 g 中的类型参数 Pany 约束(any 本身是可比较的,但不是严格可比较的),因此 P 不满足 comparable。我们可以利用这一知识,为给定类型 T 构建某种编译时断言

type T struct { … }

我们想断言 T 是严格可比较的。很容易想到写这样的代码

// isComparable may be instantiated with any type that supports ==
// including types that are not strictly comparable because of the
// exception for constraint satisfaction.
func isComparable[_ comparable]() {}

// Tempting but not quite what we want: this declaration is also
// valid for types T that are not strictly comparable.
var _ = isComparable[T] // compile-time error if T does not support ==

这个空的(空白)变量声明充当了我们的“断言”。但是由于约束满足规则中的例外,isComparable[T] 只有当 T 完全不可比较时才会失败;如果 T 支持 ==,它就会成功。我们可以通过将 T 用作类型约束而不是类型实参来解决这个问题

func _[P T]() {
    _ = isComparable[P] // P supports == only if T is strictly comparable
}

这里有一个 通过失败 的 Playground 示例,演示了此机制。

最后的观察

有趣的是,直到 Go 1.18 发布前两个月,编译器实现的约束满足规则与我们现在在 Go 1.20 中的实现完全相同。但由于当时约束满足意味着接口实现,我们的实现与语言规范不一致。我们通过 问题 #50646 得知了这一事实。当时距离发布非常近,我们必须迅速做出决定。在缺乏令人信服的解决方案的情况下,将实现与规范保持一致似乎是最安全的。一年后,有了充足的时间考虑不同的方法,看起来我们最初的实现正是我们想要的实现。我们兜了一圈又回到了原点。

一如既往,如果有什么未能按预期工作,请通过 https://golang.ac.cn/issue/new 提交问题告知我们。

谢谢!

下一篇文章:Go 集成测试的代码覆盖率
上一篇文章:性能分析引导优化预览
博客索引