# 1.循环

## 1. 经典循环

下面是一段经典的三段式循环的代码，我们将它编译成汇编指令：

```go
package main

func main() {
	for i := 0; i < 10; i++ {
		println(i)
	}
}

"".main STEXT size=98 args=0x0 locals=0x18
	00000 (main.go:3)	TEXT	"".main(SB), $24-0
	...
	00029 (main.go:3)	XORL	AX, AX                   ;; i := 0
	00031 (main.go:4)	JMP	75                         
	00033 (main.go:4)	MOVQ	AX, "".i+8(SP)
	00038 (main.go:5)	CALL	runtime.printlock(SB)
	00043 (main.go:5)	MOVQ	"".i+8(SP), AX
	00048 (main.go:5)	MOVQ	AX, (SP)
	00052 (main.go:5)	CALL	runtime.printint(SB)
	00057 (main.go:5)	CALL	runtime.printnl(SB)
	00062 (main.go:5)	CALL	runtime.printunlock(SB)
	00067 (main.go:4)	MOVQ	"".i+8(SP), AX
	00072 (main.go:4)	INCQ	AX                       ;; i++
	00075 (main.go:4)	CMPQ	AX, $10                  ;; 比较变量 i 和 10
	00079 (main.go:4)	JLT	33                         ;; 最关键的一行：跳转到 33 行如果 i < 10
	...
```

1. 0029 \~ 0031 行负责循环的初始化；
   1. 对寄存器 `AX` 中的变量 `i` 进行初始化并执行 `JMP 75` 指令跳转到 0075 行；
2. 0075 \~ 0079 行负责检查循环的终止条件，将寄存器中存储的数据 `i` 与 10 比较；
   1. `JLT 33` 命令会在变量的值小于 10 时跳转到 0033 行执行循环主体；
   2. 大于 10 时跳出循环体执行下面的代码；
3. 0033 \~ 0072 行是循环内部的语句；
   1. 通过多个汇编指令打印变量中的内容；
   2. `INCQ AX` 指令会将变量加一，然后再与 10 进行比较，回到第二步；

在汇编语言中，无论是经典的 `for` 循环还是 `for-range` 循环都会使用 `JMP` 等命令跳回循环体的开始位置复用代码。

`for-range` 这种写法经过编译器优化最终也会转换成普通的 `for` 循环。

Go 语言中的经典循环在编译器看来是一个 `OFOR` 类型的节点，这个节点由以下四个部分组成：

1. 初始化循环的 `Ninit`；
2. 循环的继续条件 `Left`；
3. 循环体结束时执行的 `Right`；
4. 循环体 `NBody`：

```go
for Ninit; Left; Right {
    NBody
}
```

## 2. 范围循环

范围循环同时使用 `for` 和 `range` 两个关键字，编译器会在编译期间将所有 for-range 循环变成经典循环。从编译器的视角来看，就是将 `ORANGE` 类型的节点转换成 `OFOR` 节点。

节点类型的转换过程都发生在中间代码生成阶段，所有的 for-range 循环都会被 [`cmd/compile/internal/gc.walkrange`](https://draveness.me/golang/tree/cmd/compile/internal/gc.walkrange) 转换成不包含复杂结构、只包含基本表达式的语句。接下来，我们按照循环遍历的元素类型依次介绍遍历数组和切片、哈希表、字符串以及管道时的过程。

### 2.1 数组和切片

对于数组和切片来说，Go 语言有三种不同的遍历方式，这三种不同的遍历方式分别对应着代码中的不同条件，它们会在 [`cmd/compile/internal/gc.walkrange`](https://draveness.me/golang/tree/cmd/compile/internal/gc.walkrange) 函数中转换成不同的控制逻辑，我们会分成几种情况分析该函数的逻辑：

1. 分析遍历数组和切片清空元素的情况；
2. 分析使用 `for range a {}` 遍历数组和切片，不关心索引和数据的情况；
3. 分析使用 `for i := range a {}` 遍历数组和切片，只关心索引的情况；
4. 分析使用 `for i, elem := range a {}` 遍历数组和切片，关心索引和数据的情况；

#### 2.1.1 切片清空元素

当我们想要在 Go 语言中清空一个切片或者哈希时，一般都会使用以下的方法将切片中的元素置零：

```go
func main() {
	arr := []int{1, 2, 3}
	for i, _ := range arr {
		arr[i] = 0
	}
}
```

依次遍历切片和哈希看起来是非常耗费性能的，因为数组、切片和哈希占用的内存空间都是连续的，所以最快的方法是直接清空这片内存中的内容。Go 语言在遍历时会做如下优化：

```go
func walkrange(n *Node) *Node {
	switch t.Etype {
	case TARRAY, TSLICE:
		if arrayClear(n, v1, v2, a) {
			return n
		}
```

在 `arrayClear` 函数中，Go 语言会直接使用 [`runtime.memclrNoHeapPointers`](https://draveness.me/golang/tree/runtime.memclrNoHeapPointers) 或者 [`runtime.memclrHasPointers`](https://draveness.me/golang/tree/runtime.memclrHasPointers) 清除目标数组内存空间中的全部数据，并在执行完成后更新遍历数组的索引。

#### 2.1.2 `for range a`

处理了上面的特殊情况之后，我们可以回到 `ORANGE` 节点的处理过程了。这里会设置 for 循环的 `Left` 和 `Right` 字段，也就是终止条件和循环体每次执行结束后运行的代码：

```go
		ha := a

		hv1 := temp(types.Types[TINT])
		hn := temp(types.Types[TINT])

		init = append(init, nod(OAS, hv1, nil))
		init = append(init, nod(OAS, hn, nod(OLEN, ha, nil)))

		n.Left = nod(OLT, hv1, hn)
		n.Right = nod(OAS, hv1, nod(OADD, hv1, nodintconst(1)))

		if v1 == nil {
			break
		}
```

如果循环是 `for range a {}`，那么就满足了上述代码中的条件 `v1 == nil`，即循环不关心数组的索引和数据，这种循环会被编译器转换成如下形式：

```go
ha := a
hv1 := 0
hn := len(ha)
v1 := hv1
for ; hv1 < hn; hv1++ {
    ...
}
```

这是 `ORANGE` 结构在编译期间被转换的最简单形式，由于原代码不需要获取数组的索引和元素，只需要使用数组或者切片的数量执行对应次数的循环，所以会生成一个最简单的 for 循环。

#### 2.1.3 `for i := range a`

如果我们在遍历数组时需要使用索引 `for i := range a {}`，那么编译器会继续会执行下面的代码：

```go
		if v2 == nil {
			body = []*Node{nod(OAS, v1, hv1)}
			break
		}
```

`v2 == nil` 意味着调用方不关心数组的元素，只关心遍历数组使用的索引。它会将 `for i := range a {}` 转换成下面的逻辑，与第一种循环相比，这种循环在循环体中添加了 `v1 := hv1` 语句，传递遍历数组时的索引：

```go
ha := a
hv1 := 0
hn := len(ha)
v1 := hv1
for ; hv1 < hn; hv1++ {
    v1 = hv1 // 多了一步这个，v1 用于返回索引
    ...
}
```

#### 2.1.4 `for i, elem := range a`

处理这种情况会使用下面这段的代码：

```go
		tmp := nod(OINDEX, ha, hv1)
		tmp.SetBounded(true)
		a := nod(OAS2, nil, nil)
		a.List.Set2(v1, v2)
		a.Rlist.Set2(hv1, tmp)
		body = []*Node{a}
	}
	n.Ninit.Append(init...)
	n.Nbody.Prepend(body...)

	return n
}
```

这段代码处理的使用者同时关心索引和切片的情况。它不仅会在循环体中插入更新索引的语句，还会插入赋值操作让循环体内部的代码能够访问数组中的元素：

```go
ha := a
hv1 := 0
hn := len(ha) // 这个遍历条件在遍历前就拷贝不变了
v1 := hv1     // 要返回的索引
v2 := nil     // 要返回的值
for ; hv1 < hn; hv1++ {
    tmp := ha[hv1]
    v1, v2 = hv1, tmp // 拷贝要返回的索引和值
    ...
}
```

因此可以解释以下现象：

1. 循环期间向原切片追加元素，循环次数并不会变：因为要循环切片的长度一开始就拷贝走了，这个变量不会变
2. 在循环中如果对变量进行取址，该地址也不会变：因为取的一直是同一个变量 `v2` 的地址，它的地址一直没变，只是在循环期间会修改值

### 2.2 哈希表

在遍历哈希表时，编译器会使用 [`runtime.mapiterinit`](https://draveness.me/golang/tree/runtime.mapiterinit) 和 [`runtime.mapiternext`](https://draveness.me/golang/tree/runtime.mapiternext) 两个运行时函数重写原始的 for-range 循环：

```go
// for key, val := range hash {} 这种写法的展开：
ha := a
hit := hiter(n.Type)
th := hit.Type
mapiterinit(typename(t), ha, &hit) // 遍历开始
for ; hit.key != nil; mapiternext(&hit) {
    key := *hit.key
    val := *hit.val
}
```

遍历前会通过 `mapiterinit` 函数初始化 [`runtime.hiter`](https://draveness.me/golang/tree/runtime.hiter) 结构体中的字段，并通过 [`runtime.fastrand`](https://draveness.me/golang/tree/runtime.fastrand) 生成一个随机数帮助我们随机选择一个遍历桶的起始位置。Go 团队在设计哈希表的遍历时就不想让使用者依赖固定的遍历顺序，所以引入了随机数保证遍历的随机性。

```go
func mapiterinit(t *maptype, h *hmap, it *hiter) {
	it.t = t
	it.h = h
	it.B = h.B
	it.buckets = h.buckets

	r := uintptr(fastrand())             // 随机数
	it.startBucket = r & bucketMask(h.B) // 随机数 % 2^B 作为起点桶下标
	it.offset = uint8(r >> h.B & (bucketCnt - 1))
	it.bucket = it.startBucket
	mapiternext(it) // 遍历
}
```

遍历哈希会使用 [`runtime.mapiternext`](https://draveness.me/golang/tree/runtime.mapiternext) 方法，该方法主要做两件事：桶的选择，以及桶内元素的遍历。

#### 2.2.1 桶的选择

这步主要做两件事：

1. 在待遍历的桶为空时，定位到下一个要遍历的桶；
2. 遍历一轮，回到起始位置后，中止遍历

```go
func mapiternext(it *hiter) {
	h := it.h
	t := it.t
	bucket := it.bucket
	b := it.bptr
	i := it.i
	alg := t.key.alg

next:
	if b == nil {
		if bucket == it.startBucket && it.wrapped { // 遍历一轮，回到起始位置后，中止遍历
			it.key = nil
			it.value = nil
			return
		}
		b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) // 下一个要遍历的桶地址
		bucket++                                                   // 下一个要遍历的桶下标
		if bucket == bucketShift(it.B) {                           // 下标到边界时，重置为0，从头开始遍历
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}
```

#### 2.2.2 桶内元素遍历

这个主要是遍历桶内的8个kv，以及溢出桶。如果哈希表处于扩容期间就会调用 [`runtime.mapaccessK`](https://draveness.me/golang/tree/runtime.mapaccessK) 获取键值对。

```go
	for ; i < bucketCnt; i++ {                   // bucketCnt=8
		offi := (i + it.offset) & (bucketCnt - 1)
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) // 遍历8个kv
		v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
			!(t.reflexivekey() || alg.equal(k, k)) {
			it.key = k
			it.value = v
		} else { // 如果处于扩容期间，调用 mapaccessK 遍历旧桶
			rk, rv := mapaccessK(t, h, k)
			it.key = rk
			it.value = rv
		}
		it.bucket = bucket
		it.i = i + 1
		return
	}
	b = b.overflow(t) // 遍历溢出桶
	i = 0
	goto next
}
```

### 2.3 字符串

遍历字符串的过程与数组、切片和哈希表非常相似，只是在遍历时会获取字符串中索引对应的字节并将字节转换成 `rune`。我们在遍历字符串时拿到的值都是 `rune` 类型的变量，`for i, r := range s {}` 的结构都会被转换成如下所示的形式：

```go
ha := s
for hv1 := 0; hv1 < len(ha); {
    hv1t := hv1
    hv2 := rune(ha[hv1])
    if hv2 < utf8.RuneSelf { // ASCII 编码，只占用一个字节长，直接+1 即可
        hv1++
    } else {
        hv2, hv1 = decoderune(ha, hv1) // 占用多个字节，需要解码，索引也不是只+1了
    }
    v1, v2 = hv1t, hv2
}
```

字符串是一个只读的字节数组切片，所以范围循环在编译期间生成的框架与切片非常类似，只是细节有一些不同。

使用下标访问字符串中的元素时得到的就是字节，但是这段代码会将当前的字节转换成 `rune` 类型。如果当前的 `rune` 是 ASCII 的，那么只会占用一个字节长度，每次循环体运行之后只需要将索引加一，但是如果当前 `rune` 占用了多个字节就会使用 [`runtime.decoderune`](https://draveness.me/golang/tree/runtime.decoderune) 函数解码

### 2.4 通道

使用 range 遍历 Channel 也是比较常见的做法，一个形如 `for v := range ch {}` 的语句最终会被转换成如下的格式：

```go
ha := a
hv1, hb := <-ha
for ; hb != false; hv1, hb = <-ha {
    v1 := hv1
    hv1 = nil
    ...
}
```

循环会使用 `<-ch` 从管道中取出等待处理的值，这个操作会调用 [`runtime.chanrecv2`](https://draveness.me/golang/tree/runtime.chanrecv2) 并阻塞当前的协程，当 [`runtime.chanrecv2`](https://draveness.me/golang/tree/runtime.chanrecv2) 返回时会根据布尔值 `hb` 判断当前的值是否存在：

* 如果不存在当前值，意味着当前的管道已经被关闭；
* 如果存在当前值，会为 `v1` 赋值并清除 `hv1` 变量中的数据，然后重新陷入阻塞等待新数据

#### 原文链接

<https://draveness.me/golang/docs/part2-foundation/ch05-keyword/golang-for-range>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wtifs.gitbook.io/diva-notes/go/4.-chang-yong-guan-jian-zi/1.-xun-huan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.