Go学习之Array

Friday, July 1, 2022

1. 概述

数组是一种数据结构，是相同类型元素的集合。计算机会为数组分配一块连续的内存来存储其元素，可以利用元素的索引快速访问元素。

作为一种基本的数据类型，一般会从两个维度来描述数组：存储的元素类型和存储的元素个数。对 Go 语言来说，只有这两个条件都相同才是同一类型，哪怕类型相同大小不同也是不同的类型。

Go 语言生成数组的函数为 src/cmd/compile/internal/types/type.go::NewArray，该函数接收元素类型 elem 和数组大小 bound，从函数源码可以看出，数组是否应该分配在堆中在编译期就确定了。

// EType describes a kind of type.
type EType uint8

const (
	Txxx EType = iota

	...
	TARRAY // 值为20
  ...
)

// NewArray returns a new fixed-length array Type.
func NewArray(elem *Type, bound int64) *Type {
	if bound < 0 {
		Fatalf("NewArray: invalid bound %v", bound)
	}
	t := New(TARRAY)
	t.Extra = &Array{Elem: elem, Bound: bound}
	t.SetNotInHeap(elem.NotInHeap())
	return t
}

// New returns a new Type of the specified kind.
func New(et EType) *Type {
	t := &Type{
		Etype: et,
		Width: BADWIDTH,
	}
	t.Orig = t
	// TODO(josharian): lazily initialize some of these?
	switch t.Etype {
	case TMAP:
		t.Extra = new(Map)
	case TFORW:
		t.Extra = new(Forward)
	case TFUNC:
		t.Extra = new(Func)
	case TSTRUCT:
		t.Extra = new(Struct)
	case TINTER:
		t.Extra = new(Interface)
	case TPTR:
		t.Extra = Ptr{}
	case TCHANARGS:
		t.Extra = ChanArgs{}
	case TFUNCARGS:
		t.Extra = FuncArgs{}
	case TCHAN:
		t.Extra = new(Chan)
	case TTUPLE:
		t.Extra = new(Tuple)
	case TRESULTS:
		t.Extra = new(Results)
	}
	return t
}

// Array contains Type fields specific to array types.
type Array struct {
	Elem  *Type // element type
	Bound int64 // number of elements; <0 if unknown yet
}

func (t *Type) NotInHeap() bool  { return t.flags&typeNotInHeap != 0 }

2.初始化

Go 语言的数组有两种初始化方式：

  1. 显示指定数组大小，如 arr1 := [3]int{1, 2, 3}

  2. 使用 […]T 声明数组，Go 语言会在编译期通过源代码推导数组大小，如 arr2 := […]int{1, 2, 3}

以上两种方式在运行期得到的结果一致，第 2 种方式在编译期就会转为第 1 种，这也就是编译器对数组大小的推导，第 2 种方式只是 Go 语言提供的一种语法糖。

在不考虑逃逸分析的情况下，如果数组元素少于或等于4个，那么所有变量会直接在栈上初始化；如果数组元素多于4个，变量就会在静态存储区初始化然后复制到栈上，这些转换后的代码才会继续进入中间代码生成和机器码生成两个阶段，最后生成可执行的二进制文件。

3. 访问和赋值

无论是在栈上还是静态存储区，数组在内存中都是一连串的内存空间，通过 ① 指向数组开头的指针、② 元素的数量、③ 元素类型占的空间大小  表示数组。

  • 如果不知道数组中元素的数量，访问时就有可能发生越界。

  • 如果不知道数组中元素类型的大小，就无法知道应该一次取出多少字节数据。

数组越界是很严重的错误，Go 语言可以通过编译期间的静态类型检查判断数组是否越界，该函数会验证访问数组的索引：src/cmd/compile/internal/gc/typecheck.go:typecheck1，从源码可以得知，对索引越界判断的错误有四种：

  1. 索引非整数，报错：non-integer array index %v
  2. 索引是负数，报错：invalid array index %v (index must be non-negative)
  3. 索引越界，报错：invalid array index %v (out of bounds for %d-element array)
  4. 索引过大，报错：invalid array index %v (index too large)
// The result of typecheck1 MUST be assigned back to n, e.g.
// 	n.Left = typecheck1(n.Left, top)
func typecheck1(n *Node, top int) (res *Node) {
	if enableTrace && trace {
		defer tracePrint("typecheck1", n)(&res)
	}

	switch n.Op {

	......

	case OINDEX:
		ok |= ctxExpr
		n.Left = typecheck(n.Left, ctxExpr)
		n.Left = defaultlit(n.Left, nil)
		n.Left = implicitstar(n.Left)
		l := n.Left
		n.Right = typecheck(n.Right, ctxExpr)
		r := n.Right
		t := l.Type
		if t == nil || r.Type == nil {
			n.Type = nil
			return n
		}
		switch t.Etype {
		
		......

		case TSTRING, TARRAY, TSLICE:
			n.Right = indexlit(n.Right)
			if t.IsString() {
				n.Type = types.Bytetype
			} else {
				n.Type = t.Elem()
			}
			why := "string"
			if t.IsArray() {
				why = "array"
			} else if t.IsSlice() {
				why = "slice"
			}

			if n.Right.Type != nil && !n.Right.Type.IsInteger() {
				yyerror("non-integer %s index %v", why, n.Right)
				break
			}

			if !n.Bounded() && Isconst(n.Right, CTINT) {
				x := n.Right.Int64Val()
				if x < 0 {
					yyerror("invalid %s index %v (index must be non-negative)", why, n.Right)
				} else if t.IsArray() && x >= t.NumElem() {
					yyerror("invalid array index %v (out of bounds for %d-element array)", n.Right, t.NumElem())
				} else if Isconst(n.Left, CTSTR) && x >= int64(len(n.Left.StringVal())) {
					yyerror("invalid string index %v (out of bounds for %d-byte string)", n.Right, len(n.Left.StringVal()))
				} else if n.Right.Val().U.(*Mpint).Cmp(maxintval[TINT]) > 0 {
					yyerror("invalid %s index %v (index too large)", why, n.Right)
				}
			}

		......
		
		}

	......

}

数组和字符串的一些简单越界错误会在编译期间发现，例如直接使用整数或常量访问数组；但是使用变量访问数组或字符串，编译期就无法提前发现错误。

Go 语言运行时发现数组、切片和字符串的越界操作时，会由运行时的 runtime.panicIndex 和 runtime.goPanicIndex 触发程序的运行时错误并导致崩溃退出。

4. 小结

数组是 Go 语言中重要的数据结构，对数组的访问和赋值需要同时依赖编译器和运行时，它的大多数操作在编译期会转换成直接读写内存。在中间代码生成期间，编译器还会插入运行时方法 runtime.panicIndex 调用防止发生越界错误。

Go Array Go

Go学习之SliceGo与Context