数组(Array)

基本概念

数组是由相同类型元素的集合组成的数据结构,计算机会为数组分配一块连续的内存来保存其中的元素,我们可以利用数组中元素的索引快速访问特定元素,常见的数组大多都是一维的线性数组,而多维数组在数值和图形计算领域却有比较常见的应用。

数组有如下特点:

  • 数组是值类型,默认情况下作为参数传递给函数时会拷贝,不影响原数组。
  • 声明时,默认值为零值(0、“”、false等)
  • 声明固定长度,不能动态变化
  • 元素的数据类型要相同
  • 占用内存连续
Go
var a [5]int         // 声明一个长度为5的int类型数组
a = [5]int{1, 2, 3}  // 将前三个元素初始化为1、2、3,后两个元素默认为0

b := [5]int{1, 2, 3, 4, 5}//直接初始化并赋值
x := a[0]    // 访问第一个元素
a[2] = 10    // 修改第三个元素
var a  = [5]int{1,2,3,4,5}

//for循环遍历
for i := 0; i < len(a); i++ {
    fmt.Println(a[i])
}

//for - range遍历
for index,value := range a{
  fmt.Println(index, value)
}
func sum(a [5]int) int {
    s := 0
    for i := 0; i < len(a); i++ {
        s += a[i]
    }
    return s
}

x := sum([5]int{1, 2, 3, 4, 5})

var a [3][3]int     // 声明一个3x3的二维数组
a[0][0] = 1         // 访问第一个元素
GoGo

数组底层编译原理

GoGo
tokenASTASTASTIRGoSSAStatic Single AssignmentIR

整个编译流程中,词法分析、语法分析、类型检查、中间代码生成和代码优化都是由编译器完成的,而生成汇编代码和链接则是由链接器完成的。

关于数组底层内容,将选取词法分析、语法分析、类型检查、生成中间代码等阶段的几个重要关键点讲解。

编译时数组类型解析

数组声明解析
Go[...]T
array1 := [5]int{1,2,3,4,5}
array2 := [...]int{1,2,3,4,5}
ArrayType[...]nil
ArrayType
// go 1.20.3   path:  src/cmd/compile/internal/syntax/nodes.go
//ArrayType 数组类型节点结构体
type (
  ......
  // [Len]Elem
  ArrayType struct {
    Len  Expr
    Elem Expr
    expr
  }
  ......
)
LenElemexpr
LenExprLennilElemExprEleminterface{}Elemnilexpr
Expr
GoExprAST1+2x+3f()Expr
ArrayTypetypeOrNil()
GoparserExprIndirectChanTypeArrayTypeMapTypeStructTypeInterfaceTypenil
typeOrNil()
// go 1.20.3   path:  src/cmd/compile/internal/syntax/parser.go
func (p *parser) typeOrNil() Expr {
	......
  // 获取当前词法标记的位置信息
	pos := p.pos()
	switch p.tok {
	......
	case _Lbrack:
    // '[' oexpr ']' ntype 或 '[' _DotDotDot ']' ntype,解析数组或切片类型
		p.next() // 向前读取一个词法标记
    // 如果下一个词法标记是右中括号,则表示是切片类型
		if p.got(_Rbrack) {
      // 解析切片类型并返回切片类型节点
			return p.sliceType(pos)
		}
    // 否则解析数组类型并返回数组类型节点
		return p.arrayType(pos, nil)
	......
	return nil
}
  
/**
	// go 1.20.3   path:  src/cmd/compile/internal/syntax/parser.go
	该函数用于解析数组类型,并返回一个Expr表示该类型
	pos表示数组类型的位置,len表示数组的长度
*/
func (p *parser) arrayType(pos Pos, len Expr) Expr {
	......
  // 如果长度为空并且没有出现省略号(_DotDotDot),则解析表达式
	if len == nil && !p.got(_DotDotDot) {
		p.xnest++
		len = p.expr()
		p.xnest--
	}
	......
	// 要求下一个标记为右方括号
	p.want(Rbrack)
	// 创建一个新的数组类型
	t := new(ArrayType)
	t.pos = pos
	t.Len = len
	t.Elem = p.type()
	return t
}
ArrayType
types2.Array
Gonil
niltypes2.Array
types2.Arraytypes2.Arraytypes.Array

这种转换发生在类型检查阶段,因为只有在这个阶段,编译器才有足够的信息来确定数组类型的长度。

type conversion
ArrayTypeLenniltypes2.Array-1check.indexedElts(e.ElemList, utyp.elem, utyp.len)nLen
types2.Array
// go 1.20.3   path:  src/cmd/compile/internal/types2/array.go
type Array struct {
	len  int64
	elem Type
}
exprInternalGo

来看看该函数对数组类型的节点表达式检查的相关源码:

func (check *Checker) exprInternal(x *operand, e syntax.Expr, hint Type) exprKind {
	......
	//通过类型断言判断表达式 e 的具体类型
	switch e := e.(type) {
	......
	//如果类型是*syntax.CompositeLit类型,即语法树节点类型
	case *syntax.CompositeLit:
		//声明了两个 Type 类型的变量 typ 和 base,用于保存表达式 e 的类型
		var typ, base Type
		switch {
		//如果 e.Type 不为空,则将其转换为Type类型,并将其赋值给变量 typ 和 base
		case e.Type != nil:
      //e.Type为 *syntax.ArrayType 类型且数组长度 Len 为 nil,则将typ设置为&types2.Array,
			if atyp, _ := e.Type.(*syntax.ArrayType); atyp != nil && atyp.Len == nil {
				typ = &Array{len: -1, elem: check.varType(atyp.Elem)}
				base = typ
				break
			}
			typ = check.typ(e.Type)
			base = typ
		......
		}
		//通过 coreType 函数获取 base 的基础类型信息
		switch utyp := coreType(base).(type) {
		......
		//如果基础类型是 *Array 类型,即数组类型
		case *Array:
			//首先检查其元素类型是否为 nil,如果是则报错,表示这是无效的递归类型
			if utyp.elem == nil {
				check.error(e, InvalidTypeCycle, "invalid recursive type")
				goto Error
			}

			//通过 indexedElts 函数计算复合字面量表达式的元素数量
			n := check.indexedElts(e.ElemList, utyp.elem, utyp.len)
			//如果数组类型的长度为负数,则设置其长度为计算得到的元素数量
			if utyp.len < 0 {
				utyp.len = n
        //如果 e.Type 不为空,则记录类型和值信息
				if e.Type != nil {
					check.recordTypeAndValue(e.Type, typexpr, utyp, nil)
				}
			}
		......
		}
		......
	}
	......
}
types.Array 与 types2.Array转换
Gogo/types
types.Arraytypes2Arraytypes
typestypes.NewArray()types2.Arraytypes.Arraytypes2types
//go1.20.3 path:src/cmd/compile/internal/types/type.go
type Array struct {
    Elem  *Type // element type
    Bound int64 // number of elements; <0 if unknown yet
}

func NewArray(elem *Type, bound int64) *Type {
	//如果bound小于0,则抛出一个致命错误。
	if bound < 0 {
		base.Fatalf("NewArray: invalid bound %v", bound)
	}
	//创建一个新的Type结构体,并将其类型设置为TARRAY,表示这是一个数组类型
	t := newType(TARRAY)

	//将t的extra字段设置为一个指向Array结构体的指针,
	//其中Elem字段指向elem所指向的Type结构体,表示该数组的元素类型;
	//Bound字段设置为bound,表示该数组的长度。
	t.extra = &Array{Elem: elem, Bound: bound}
	//如果elem所指向的Type结构体具有类型参数(即泛型类型),则将t的HasTParam字段设置为true
	if elem.HasTParam() {
		t.SetHasTParam(true)
	}
	//如果elem所指向的Type结构体具有形状信息(即元组类型),则将t的HasShape字段设置为true
	if elem.HasShape() {
		t.SetHasShape(true)
	}
	return t
}
types2.Arraytypes.NewArray()types.Array
//go1.20.3 path: src/cmd/compile/internal/noder/types.go
func (g *irgen) typ0(typ types2.Type) *types.Type {
    switch typ := typ.(type) {
    ...
    case *types2.Array:
        return types.NewArray(g.typ1(typ.Elem()), typ.Len())
    ...
}

编译时数组字面量初始化

ElemBoundtcComplit -> typecheckarraylit
tcComplitcomposite literalir.Node

该函数相关数组的源码:

// go 1.20.3   path: /src/cmd/compile/internal/typecheck/expr.go
func tcCompLit(n *ir.CompLitExpr) (res ir.Node) {
    ...
    //获取 CompLitExpr 的类型 t
    t := n.Type()
  
    //通过调用断言函数AssertfAt确保类型t不为 nil。
  	//如果为 nil,则输出错误信息 "missing type in composite literal"。
    base.AssertfAt(t != nil, n.Pos(), "missing type in composite literal")
  
    //根据类型 t 的种类,执行不同的处理
    switch t.Kind() {
    ...
    //如果 t的种类为 TARRAY,即数组
    case types.TARRAY:
        //对数组字面量的元素进行类型检查,且将数组字面量中的每个元素转换为指定类型的值,并确保所有元素都具有相同的类型
        typecheckarraylit(t.Elem(), t.NumElem(), n.List, "array literal")
        //将操作符设置为 OARRAYLIT
        n.SetOp(ir.OARRAYLIT)
    ...
    return n
}
typecheckarraylit

它接受四个参数:

elemTypeboundeltsir.Nodectx

该函数源码如下:

// go 1.20.3  path: src/cmd/compile/internal/typecheck/typecheck.go
func typecheckarraylit(elemType *types.Type, bound int64, elts []ir.Node, ctx string) int64 {
    ...
  	//遍历数组字面量 elts 中的每个元素
    for i, elt := range elts {
        //设置元素 elt 的位置信息
        ir.SetPos(elt)
        //将元素 elt 的值赋给变量r
        r := elts[i]
        ......
        //对变量r的值进行表达式转换
        r = Expr(r)
        //将变量r的值转换为指定类型 elemType 的值
        r = AssignConv(r, elemType, ctx)
        ...
}

编译时初始化字面量的优化

Type Checking

在编译期间,编译器将复合字面量转化为静态或动态的数据结构,并将其放入程序的数据段或堆中。而在运行期间,程序可以直接使用这些静态或动态的数据结构,而不需要再次计算或初始化。

cmd/compile/internal/gc.anylit
var arr [5]int
statictmp_0[0] = 1
statictmp_0[1] = 2
statictmp_0[2] = 3
statictmp_0[3] = 4
statictmp_0[4] = 5
arr = statictmp_0
var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3
anylit
func anylit(n ir.Node, var_ ir.Node, init *ir.Nodes) {
	t := n.Type()
	switch n.Op() {
	......
	case ir.OSTRUCTLIT, ir.OARRAYLIT:
		n := n.(*ir.CompLitExpr)
		if !t.IsStruct() && !t.IsArray() {
			base.Fatalf("anylit: not struct/array")
		}

		// 针对字面量表达式的静态优化
		if isSimpleName(var_) && len(n.List) > 4 {
			vstat := readonlystaticname(t)
			ctxt := inInitFunction
			if n.Op() == ir.OARRAYLIT {
				ctxt = inNonInitFunction
			}
			// 进行静态优化
			fixedlit(ctxt, initKindStatic, n, vstat, init)
			// 将静态变量赋值给目标变量
			appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, vstat))
			// 进行动态优化
			fixedlit(inInitFunction, initKindDynamic, n, var_, init)
			break
		}

		var components int64
		if n.Op() == ir.OARRAYLIT {
			components = t.NumElem()
		} else {
			components = int64(t.NumFields())
		}
		// 如果变量名是简单标识符或者字面量表达式中的元素数量小于目标结构体或数组中的元素数量,则给目标变量赋值为nil
		if isSimpleName(var_) || int64(len(n.List)) < components {
			appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, nil))
		}

		// 执行局部代码优化
		fixedlit(inInitFunction, initKindLocalCode, n, var_, init)
	......
	}
}
fixedlitGocompilerGoconstantGoliteral valueexpressionconstant resolverfixedlit
fixedlit
func fixedlit(ctxt initContext, kind initKind, n *ir.CompLitExpr, var_ ir.Node, init *ir.Nodes) {
	// 判断 var_ 是否为空标识符 _
	isBlank := var_ == ir.BlankNode
	var splitnode func(ir.Node) (a ir.Node, value ir.Node)
	switch n.Op() {
	//如果n的操作符是 OARRAYLIT 或者 OSLICELIT,则说明n表示一个数组或者一个切片
	case ir.OARRAYLIT, ir.OSLICELIT:
		var k int64
		// 定义一个匿名函数 splitnode,用于分离数组或切片中的每个元素
		splitnode = func(r ir.Node) (ir.Node, ir.Node) {
			if r.Op() == ir.OKEY {
				// 如果该元素是 key-value 形式,如 a:[2]int{0:1, 1:2},则需要解析key值
				kv := r.(*ir.KeyExpr)
				k = typecheck.IndexConst(kv.Key)
				if k < 0 {
					// key 值必须是非负整数
					base.Fatalf("fixedlit: invalid index %v", kv.Key)
				}
				r = kv.Value
			}
			// 构造IndexExpr节点,表示当前元素的索引, 如 a[0],a[1],a[2]
			a := ir.NewIndexExpr(base.Pos, var_, ir.NewInt(k))
			k++
			if isBlank {
				//如果当前元素没有对应变量,则返回 BlankNode 作为变量占位符
				return ir.BlankNode, r
			}
			// 返回变量和值
			return a, r
		}
	......
	}

	for _, r := range n.List {
		// 分割节点,提取数组/切片/键值对的下标和值
		a, value := splitnode(r)
		// 如果是匿名变量并且右值没有副作用,则继续处理下一个节点
		if a == ir.BlankNode && !staticinit.AnySideEffects(value) {
			continue
		}
		//处理不同类型的右值, 如果右值是一个复合字面量,则递归处理
		switch value.Op() {
		......
		//如果是数组/结构体字面量,递归调用 fixedlit 函数
		case ir.OARRAYLIT, ir.OSTRUCTLIT:
			value := value.(*ir.CompLitExpr)
			fixedlit(ctxt, kind, value, a, init)
			continue
		}

		// 判断右值是否为常量节点
		islit := ir.IsConstNode(value)

		// 如果当前为静态初始化且右值不是常量,则继续处理下一个节点
		// 如果当前为动态初始化且右值是常量,则继续处理下一个节点
		if (kind == initKindStatic && !islit) || (kind == initKindDynamic && islit) {
			continue
		}

		// 构造赋值语句节点
		ir.SetPos(a)
		as := ir.NewAssignStmt(base.Pos, a, value)
		as = typecheck.Stmt(as).(*ir.AssignStmt)

		// 根据不同的初始化类型,生成不同的赋值语句
		switch kind {
		// 静态初始化
		case initKindStatic:
			genAsStatic(as)  // 如果右值是常量,则直接将赋值语句添加到静态初始化列表中
		// 动态初始化
		case initKindDynamic, initKindLocalCode:
			// 如果右值是常量,则直接将赋值语句添加到动态初始化列表中
			appendWalkStmt(init, orderStmtInPlace(as, map[string][]*ir.Name{}))
		default:
			base.Fatalf("fixedlit: bad kind %d", kind)
		}
	}
}

该函数大致流程为:

ctxtkindn.Op()fixedlitfixedlitnil
fixedlitfixedlitctxtkindnvar_

编译时数组索引越界检查

Go
// go 1.20.3  path: src/cmd/compile/internal/typecheck/typecheck.go
func typecheck1(n ir.Node, top int) ir.Node {
  ......
  switch n.Op() {
  ......
  case ir.OINDEX:
        n := n.(*ir.IndexExpr)
        return tcIndex(n)
  ......
  }
}

// go 1.20.3  path: src/cmd/compile/internal/typecheck/expr.go
func tcIndex(n *ir.IndexExpr) ir.Node {
	//调用Expr 函数对被索引的对象进行语义分析
	n.X = Expr(n.X)
	//再调用 DefaultLit 函数对结果进行类型推导
	n.X = DefaultLit(n.X, nil)
	//调用 implicitstar 函数对结果进行处理
	n.X = implicitstar(n.X)
	l := n.X
	n.Index = Expr(n.Index)
	r := n.Index
	t := l.Type()
	//获取被索引的对象的类型,并判断该类型是否为 nil,或者索引值的类型是否为 nil,如果是,则返回 nil 并结束函数
	if t == nil || r.Type() == nil {
		n.SetType(nil)
		return n
	}
	// 使用 switch 语句块,检查类型 t 的种类
	switch t.Kind() {
	......
	// 如果类型是字符串类型、数组类型或切片类型
	case types.TSTRING, types.TARRAY, types.TSLICE:
		// 调用 indexlit 函数对索引表达式中的索引进行处理
		n.Index = indexlit(n.Index)
		// 如果类型是字符串类型,将索引表达式的类型设置为 ByteType,否则设置为元素类型
		if t.IsString() {
			n.SetType(types.ByteType)
		} else {
			n.SetType(t.Elem())
		}
		// 创建一个字符串变量 why,设置为 "string"
		why := "string"
		// 如果类型是数组类型,将 why 设置为 "array",如果是切片类型,将 why 设置为 "slice"
		if t.IsArray() {
			why = "array"
		} else if t.IsSlice() {
			why = "slice"
		}
		// 如果索引表达式的类型不为空且不是整数类型,输出错误信息
		if n.Index.Type() != nil && !n.Index.Type().IsInteger() {
			base.Errorf("non-integer %s index %v", why, n.Index)
			return n
		}
		// 如果索引表达式未绑定且是整数类型的常量
		if !n.Bounded() && ir.IsConst(n.Index, constant.Int) {
			x := n.Index.Val()
			// 如果索引小于 0,输出错误信息
			if constant.Sign(x) < 0 {
				base.Errorf("invalid %s index %v (index must be non-negative)", why, n.Index)
				// 如果类型是数组类型且索引大于等于数组长度,输出错误信息
			} else if t.IsArray() && constant.Compare(x, token.GEQ, constant.MakeInt64(t.NumElem())) {
				base.Errorf("invalid array index %v (out of bounds for %d-element array)", n.Index, t.NumElem())
				// 如果类型是字符串类型且索引大于等于字符串长度,输出错误信息
			} else if ir.IsConst(n.X, constant.String) && constant.Compare(x, token.GEQ, constant.MakeInt64(int64(len(ir.StringVal(n.X))))) {
				base.Errorf("invalid string index %v (out of bounds for %d-byte string)", n.Index, len(ir.StringVal(n.X)))
				// 如果索引溢出,输出错误信息
			} else if ir.ConstOverflow(x, types.Types[types.TINT]) {
				base.Errorf("invalid %s index %v (index too large)", why, n.Index)
			}
		}
		......
	}
	return n
}
TEXT runtime·panicIndex(SB),NOSPLIT,$0-8
	MOVL	AX, x+0(FP)
	MOVL	CX, y+4(FP)
	JMP	runtime·goPanicIndex(SB)

func goPanicIndex(x int, y int) {
	panicCheck1(getcallerpc(), "index out of range")
	panic(boundsError{x: int64(x), signed: true, y: y, code: boundsIndex})
}
package main

func outOfArray() int {
	arr := [3]int{1, 2, 3}
	i := 2
	elem := arr[i]
	return elem
}

func main() {}

$ GOSSAFUNC=outOfRange go build main.go
dumped SSA to ./ssa.html
start
b1:-
......
v20 (6) = LocalAddr <*[3]int> {arr} v2 v19
v21 (6) = IsInBounds <bool> v13 v10
If v21 → b2 b3 (likely) (6)
b2: ← b1-
v24 (6) = PtrIndex <*int> v20 v13
v25 (6) = Copy <mem> v19
v26 (6) = Load <int> v24 v25 (elem[int])
v27 (7) = MakeResult <int,mem> v26 v25
Ret v27 (+7)
b3: ← b1-
v22 (6) = Copy <mem> v19
v23 (6) = PanicBounds <mem> [0] v13 v10 v22
Exit v23 (6)
name i[int]: v13
name elem[int]: v26
start
b1:-
......
v20 (5) = LocalAddr <*[3]int> {arr} v2 v19
v21 (+5) = PtrIndex <*int> v20 v13
v22 (5) = Load <int> v21 v19 (elem[int])
v23 (+6) = MakeResult <int,mem> v22 v19
Ret v23 (+6)
name elem[int]: v22

总结

go[…]int{2,3,4}44go

参考资料:
Draven https://draveness.me/golang/