Go Range 内部实现

原文：Go Range Loop Internals

Go 里的 range 循环用起来非常方便，但我总觉得它在不同情况下的表现有点神秘。现在看来我并不孤单：

#golang pop quiz: does this program terminate?
func main() {
v := []int{1, 2, 3}
for i := range v {
v = append(v, i)
}
}

— Dαve Cheney (@davecheney) January 13, 2017

Today's #golang gotcha: the two-value range over an array does a copy. Avoid by ranging over the pointer instead.https://t.co/SbK667osvA

— Damian Gryski (@dgryski) January 3, 2017

在亲自测试了两位大神的例子后，现在我应该接受并记住这些事实，但死记硬背的东西总是容易忘。搞清楚背后的原理是什么，才更有利于加深理解和记忆，让我们开始吧。

第一步：读读该死的手册（Read The Fxxking Manual）

先来读一下关于 range 的文档。在 Go 规范文档 "For statements with range clause" 一节可以找到关于 for...range 语法相关的说明。我不会把整个文档都拷贝过来，但会汇总一些有对我们有用的部分。

首先，提醒一下自己我们要重点注意的是什么：

for i := range a {
    fmt.Println(i)
}

range 变量

我们应该都知道，对于 range 左边的循环变量（上面这个例子里的 i）可以用以下方式来赋值：

• 等号直接赋值 (=)
• 短变量申明赋值 (:=)

当然也可以什么都不写来完全忽略迭代遍历到的值。

如果使用短变量申明（:=），Go 会在每次循环的迭代中重用申明的变量（只在循环内的作用域里有效）

range 表达式

range 右边（上述例子里的 a）表达式的结果，可以是以下这些数据类型：

• 数组
• 指向数组的指针
• 切片
• 字符串
• map
• 可以接收传输的 channel, 比如：chan int or chan<- int

range 表达式会在开始循环前被 evaluated 一次。但有一个例外情况：

<div class="tip">
如果对一个数组或者指向数组的指针做 range 并且只用到了数组索引：此时只有 len(a) 被 evaluated。
</div>

仅仅只 evaluating len(a) 意味着表达式 a 可能在编译时被 evaluated 然后被编译器替换成了常量。规范文档里对 len 的解释：

如果变量 s 是数组、指向数组的指针并且表达式里没有可以接收输入的 channel 或者函数调用（非常量），这些情况下 s 不会被 evaluated，len(s) 和 cap(s) 都是常量；除此之外 len 和 cap 的调用都不是常量并且 s 会被 evaluated。

所以这里的 evaluated 到底是什么意思？很不幸文档里没有找到相关的说明。当然我猜其实就是完全的执行表达式直到其不能再被拆解。无论如何，最重要的是 range 表达式 在整个迭代开始前会被完全的执行一次。那么你会怎么让一个表达式只执行一次？把执行结果放在一个变量里！ range 表达式的处理会不会也是这么做的？

有趣的是规范文档里提到了一些对 maps (没有提到 slices) 做添加或删除操作的情况。

如果 map 中的元素在还没有被遍历到时就被移除了，后续的迭代中这个元素就不会再出现。而如果 map 中的元素是在迭代过程中被添加的，那么在后续的迭代这个元素可能出现也可能被跳过。

稍等一会我们再回来聊 maps。

第二步: range 支持的数据类型

如果我们假设在循环开始之前会先把 range 表达式复制给一个变量，那我们需要关注什么？答案是表达式结果的数据类型，让我们更近一步的看看 range 支持的数据类型。

在我们开始前，先记住：在 Go 里，无论我们对什么赋值，都会被复制。如果赋值了一个指针，那我们就复制了一个指针副本。如果赋值了一个结构体，那我们就复制了一个结构体副本。往函数里传参也是同样的情况。好了，开始吧：

类型	谁的语法糖？
array	数组
string	一个结构体：拥有一个变量 len 和一个指针指向背后的数组
slice	一个结构体：拥有一个变量 len 、一个变量 cap 和一个指针指向背后的数组
map	指向一个结构体的指针
channel	指向一个结构体的指针

本文的末尾列出了一些参考，可以进一步了解这些数据类型的内部结构。

所以这些到底有什么 luǎn 用？下面的例子着重标记出了一些不同点：

// 复制整个数组
var a [10]int
acopy := a 

// 只复制了 slice 的结构体，并没有复制成员指针指向的数组
s := make([]int, 10)
scopy := s

// 只复制了 map 的指针
m := make(map[string]int)
mcopy := m

所以，如果要在 range 循环开始前把一个数组表达式赋值给一个变量（保证表达式只 evaluate 一次），就会复制整个数组。

第三步: Go 编译器源码

偷懒如我直接 google 了一下 Go 的编译器源码。首先发现的是 GCC 版本的编译器。我们关心的和 range 有关的部分出现在 statements.cc，就像注释里写的：

// Arrange to do a loop appropriate for the type.  We will produce
//   for INIT ; COND ; POST {
//           ITER_INIT
//           INDEX = INDEX_TEMP
//           VALUE = VALUE_TEMP // If there is a value
//           original statements
//   }

现在终于有点眉目了。range 循环在内部实现上实际就是 C 风格循环的语法糖，意料之外而又在情理之中。编译器会对每一种 range 支持的类型做专门的 “语法糖还原”。比如，

数组：

// The loop we generate:
//   len_temp := len(range)
//   range_temp := range
//   for index_temp = 0; index_temp < len_temp; index_temp++ {
//           value_temp = range_temp[index_temp]
//           index = index_temp
//           value = value_temp
//           original body
//   }

切片：

//   for_temp := range
//   len_temp := len(for_temp)
//   for index_temp = 0; index_temp < len_temp; index_temp++ {
//           value_temp = for_temp[index_temp]
//           index = index_temp
//           value = value_temp
//           original body
//   }

他们的共同点是：

• 所有类型的 range 本质上都是 C 风格的循环
• 遍历到的值会被赋值给一个临时变量

这是 gofrontend里的情况，据我所知大多数人使用的是 Go 发行版自带的 gc 编译器，看上去他们在这一点的处理上有着完全相同的行为。

我们所知道的

1. 循环变量在每一次迭代中都被赋值并会复用。
2. 可以在迭代过程中移除一个 map 里的元素或者向 map 里添加元素。添加的元素并不一定会在后续迭代中被遍历到。
3. 明确了这些之后，我们再回到开篇列出的例子上。

Dave 的推文

#golang pop quiz: does this program terminate?
func main() {
v := []int{1, 2, 3}
for i := range v {
v = append(v, i)
}
}

— Dαve Cheney (@davecheney) January 13, 2017

这段代码之所以会终止是因为它其实可以粗略的翻译成类似下面的这段：

for_temp := v
len_temp := len(for_temp)
for index_temp = 0; index_temp < len_temp; index_temp++ {
        value_temp = for_temp[index_temp]
        index = index_temp
        value = value_temp
        v = append(v, index)
}

我们知道切片实际上是一个结构体的语法糖，这个结构体有着一个指向数组的指针成员。在循环开始前对这个结构体生成副本然后赋值给 for_temp，后面的循环实际上是在对 for_temp 进行迭代。任何对于原始变量 v 本身（而非对其背后指向的数组）的更改都和生成的副本 for_temp 没有关系。但其背后指向的数组还是以指针的形式共享给 v 和 for_temp，所以 v[i] = 1 这样的语句仍然可以工作。

Damian 的推文

Today's #golang gotcha: the two-value range over an array does a copy. Avoid by ranging over the pointer instead.https://t.co/SbK667osvA

— Damian Gryski (@dgryski) January 3, 2017

和上面的例子类似，在循环开始前数组被赋值给了一个临时变量，在对数组做 range 循环时临时变量里存放的是整个数组的副本，对原数组的操作不会反映在副本上。而在对数组指针做 range 循环时临时变量存放的是指针的副本，操作的也是同一块内存空间。

附: maps

在规范文档里我们读到：

• 在 range 循环里对 maps 做添加或删除元素的操作是安全的。
• 如果在循环中对 maps 添加了一个元素，那么这个元素并不一定会出现在后续的迭代中。

对于第一点，我们知道 maps 实际上是结构体的指针。循环开始前，只会复制指针而不是内部的数据结构，因此在循环中添加或删除元素所操作的内存空间和原变量一致，合情合理。

那为什么在后续的迭代中不一定能遍历到当前添加的元素？如果你知道哈希表是如何工作的（map 本质上就是哈希表），就会明白哈希表内部数组里的元素并不是以特定顺序存放。最后一个添加的元素有可能经过哈希后被放到了内部数组里的第一个索引位，我们确实没有办法预测当前添加的元素是否会出现在后续的迭代中，毕竟在添加元素的时候很可能已经遍历过了第一个索引位。因此，当前添加的元素是否能在后续迭代中遍历到，还是看编译器的心情吧 :D

参考

• The Go Programming Language Specification
• Go slices: usage and internals
• Go Data Structures
• Inside the map implementation: slides | video
• Understanding nil: slides | video
• string source code
• slice source code
• map source code
• channel source code

原文：Go Range 内部实现

---