Go compilation principle series 6 (type checking)

6. Go编译过程-类型检查

前言

In the previous article, the construction of the abstract syntax tree was shared,The next stage is type checking,It traverses every node of the abstract syntax tree,Different types of nodes are type checked as follows（静态类型检查）：

• 常量、Type and function names and type validation

• 变量的赋值和初始化

• Computes compile-time constants、Bind declarations to identifiers

• Some built-in functions will be rewritten（It will be mentioned when the source code is introduced below）

• 哈希键值对的类型

• Do special syntactic or semantic checks（引用的结构体字段是否是大写可导出的？数组字面量的访问是否超过了其长度？数组的索引是不是正整数？）

通过类型检查,It can guarantee that each node of the abstract syntax tree will not have type errors（注意,The compilation phase is static type checking）,Static type error in source code,will be discovered during type checking.并且,If a type implements an interface,are also checked out at this stage

通过本文你可以了解到GoWhat does the type checking phase do,and when checking some special types of nodes,What special rewrites are made to the node（比如：map、make）

Overall overview of type checking

The type checking phase traverses every node of the abstract syntax tree,Determine the type of node.For example the following two forms

var test int
test := 1


The first is to specify the type directly,The second is that the compiler needs to get the type of the variable through type inference

mentioned in the previous articles,GoThe compiled entry file is in：

GoCompile entry file：src/cmd/compile/main.go -> gc.Main(archInit)


进入到gc.Main(archInit)方法,你会看到,Perform lexical analysis、语法分析、After the construction of the abstract syntax tree,There is a piece of code below：

func Main(archInit func(*Arch)) {
 ......
 lines := parseFiles(flag.Args())//词法分析、语法分析、The abstract syntax tree construction is all here
 ......
 //Start traversing the abstract syntax tree,Type checking for each node
 for i := 0; i < len(xtop); i++ {
 n := xtop[i]
 if op := n.Op; op != ODCL && op != OAS && op != OAS2 && (op != ODCLTYPE || !n.Left.Name.Param.Alias()) {
 xtop[i] = typecheck(n, ctxStmt)
 }
 }
 for i := 0; i < len(xtop); i++ {
 n := xtop[i]
 if op := n.Op; op == ODCL || op == OAS || op == OAS2 || op == ODCLTYPE && n.Left.Name.Param.Alias() {
 xtop[i] = typecheck(n, ctxStmt)
 }
 }
 ......
 checkMapKeys()//Check the type of the keys in the hash
 ......
}


这里的xtop是一个数组,Inside it is the root node of each abstract syntax tree（Mentioned in this article on Abstract Syntax Tree Construction,It builds each declarative statement into an abstract syntax tree,比如var、const、type、func等）.So it traverses from the root of each tree,Type checking one by one

As we can see from the code above,Type checking is mostly called：/usr/local/go/src/cmd/compile/internal/gc/typecheck.go→

typecheck

方法,This method works on constants、类型、函数声明、Assignment statements, etc. are type checked.Also called latercheckMapKeys()method to type check the keys of the hash（The implementation of these two methods will be described in detail below）

其实在

typecheck

方法中,The core logic is called in it

typecheck1

方法中.This method consists of a large oneswitch构成,根据每个节点的Op,to select different processing logic.There are many branches here,I only select a few more special ones for in-depth understanding

func typecheck1(n *Node, top int) (res *Node) {
 ......
 switch n.Op {
 // until typecheck is complete, do nothing.
 default:
 Dump("typecheck", n)
 
 Fatalf("typecheck %v", n.Op)
 
 // names
 case OLITERAL:
 ok |= ctxExpr
 
 if n.Type == nil && n.Val().Ctype() == CTSTR {
 n.Type = types.UntypedString
 }
 
 case ONONAME:
 ok |= ctxExpr
 
 case ONAME:
 ......
 case OTARRAY:
 ......
 case OTMAP:
 ......
 }
 ......
}


Learn more about type checking

OAS：赋值语句

// Left = Right or (if Colas=true) Left := Right
// If Colas, then Ninit includes a DCL node for Left.
OAS


The core of the assignment statement is the call：/usr/local/go/src/cmd/compile/internal/gc/typecheck.go→

typecheckas

case OAS:
 ok |= ctxStmt

 typecheckas(n)

 // Code that creates temps does not bother to set defn, so do it here.
 if n.Left.Op == ONAME && n.Left.IsAutoTmp() {
 n.Left.Name.Defn = n
 }


在

typecheckas

方法中,可以看到如下这段代码,It is the type of the constant on the right,The type assigned to the variable on the left

func typecheckas(n *Node) {
 ......
 if n.Left.Name != nil && n.Left.Name.Defn == n && n.Left.Name.Param.Ntype == nil {
 n.Right = defaultlit(n.Right, nil)
 n.Left.Type = n.Right.Type
 }
 ......
}


比如：var a = 666

OTARRAY：切片

OTARRAY // []int, [8]int, [N]int or [...]int


对于节点类型是OTARRAY的情况,It first checks the type of the slice value（The right node of this node）

case OTARRAY:
 ok |= ctxType
 r := typecheck(n.Right, ctxType)
 if r.Type == nil {
 n.Type = nil
 return n
 }


Then according to the difference of the left node,分三种情况,即[]int、[...]int、[6]int

• []int
  ：直接调用
  t = types.NewSlice(r.Type)
  ,返回了一个 
  TSLICE
   类型的结构体,The element's type information is also stored in the structure

• [...]int
  ：交由
  typecheckcomplit
  方法处理,

func typecheckcomplit(n *Node) (res *Node) {
 ......
 // Need to handle [...]T arrays specially.
 if n.Right.Op == OTARRAY && n.Right.Left != nil && n.Right.Left.Op == ODDD {
 n.Right.Right = typecheck(n.Right.Right, ctxType)
 if n.Right.Right.Type == nil {
 n.Type = nil
 return n
 }
 elemType := n.Right.Right.Type
 
 length := typecheckarraylit(elemType, -1, n.List.Slice(), "array literal")
 
 n.Op = OARRAYLIT
 n.Type = types.NewArray(elemType, length)
 n.Right = nil
 return n
 }
 ......
}


This method will get the number of elements in the array,然后调用

[types.NewArray](https://draveness.me/golang/tree/cmd/compile/internal/types.NewArray)

 Initializes a structure that stores the type of elements in the array and the size of the array

• [6]int
  ：If when declaring slice,with the size of the array,则直接调用
  [types.NewArray](https://draveness.me/golang/tree/cmd/compile/internal/types.NewArray)
   Initializes a structure that stores the type of elements in the array and the size of the array

It can be found that the length of the array is determined during type checking

在最后,It will update the node'sType等信息

setTypeNode(n, t)
n.Left = nil
n.Right = nil
checkwidth(t)


OTMAP：map(哈希)

OTMAP // map[string]int


对于OTMAP类型的结点,It will type-check the left and right parts separately,然后创建一个*

TMAP

结构体,将MAPThe key value type is stored in this structure*

case OTMAP:
 ok |= ctxType
 n.Left = typecheck(n.Left, ctxType)
 n.Right = typecheck(n.Right, ctxType)
 l := n.Left
 r := n.Right
 if l.Type == nil || r.Type == nil {
 n.Type = nil
 return n
 }
 if l.Type.NotInHeap() {
 yyerror("incomplete (or unallocatable) map key not allowed")
 }
 if r.Type.NotInHeap() {
 yyerror("incomplete (or unallocatable) map value not allowed")
 }

 setTypeNode(n, types.NewMap(l.Type, r.Type))
 mapqueue = append(mapqueue, n) // check map keys when all types are settled
 n.Left = nil
 n.Right = nil

......
func NewMap(k, v *Type) *Type {
 t := New(TMAP)
 mt := t.MapType()
 mt.Key = k
 mt.Elem = v
 return t
}


We can find out from the code,It doesn't just modify the nodes,And put the node into onemapqueue队列.mentioned in the previous overview sectioncheckMapKeys()The type of the hash key is checked again

func checkMapKeys() {
 for _, n := range mapqueue {
 k := n.Type.MapType().Key
 if !k.Broke() && !IsComparable(k) {
 yyerrorl(n.Pos, "invalid map key type %v", k)
 }
 }
 mapqueue = nil
}


In fact, it is traversing the queue,Verify that these types work as map的key

OMAKE：make

OMAKE // make(List) (before type checking converts to one of the following)
OMAKECHAN // make(Type, Left) (type is chan)
OMAKEMAP // make(Type, Left) (type is map)
OMAKESLICE // make(Type, Left, Right) (type is slice)


在编写go代码时,我们经常会用到make关键字来创建slice、map、channel等,在GoThe type checking phase of compilation,it will subdivideOMAKE的结点,比如：

make slice：OMAKESLICE
make map：OMAKEMAP
make chan：OMAKECHAN


具体实现就是,它会先获取到make的第一个参数,也就是类型.according to this type,进行不同的处理

case OMAKE:
 ok |= ctxExpr
 args := n.List.Slice()
 ......
 l := args[0]
 l = typecheck(l, ctxType)
 t := l.Type
 ......
 i := 1
 switch t.Etype {
 default:
 yyerror("cannot make type %v", t)
 n.Type = nil
 return n

 case TSLICE:
 ......
 n.Left = l
 n.Right = r
 n.Op = OMAKESLICE

 case TMAP:
 ......
 n.Op = OMAKEMAP
 case TCHAN:
 ......
 n.Op = OMAKECHAN
 }

 n.Type = t


• 如果第一个参数是
  切片类型
  ：获取切片的长度(len)和容量(cap),然后对len和cap进行合法性校验.And rewrite the node type

• 如果第一个参数是
  map类型
  ：获取make的第二个参数,如果没有,则默认设置为0（map的大小）.And rewrite the node type

• 如果第一个参数是chan
  类型
  ：获取make的第二个参数,如果没有,则默认设置为0（chan的缓冲区大小）.And rewrite the node type

I'm not pasting the code here,大家可以自行去看

总结

This article mainly shares several special node types in type checking.There are many other types of node type checking,You can look at the source code by yourself

It was not shared in the previous articlesGo的源码调试,So the next article plans to shareGosource code debugging method.And take the construction of an abstract syntax tree as an example,对它进行调试

参考

• go-ast-book

• 《Go语言底层原理剖析》

• 面向信仰编程-类型检查