[译]Go 如何计算 len()..？#私藏项目实操分享#

Go 如何计算 len()..？

这篇文章的动机是不久前关于 Gophers Slack 的一个问题。一位开发人员想知道在哪里可以找到有关 len 的更多信息。

I want to know how the len func gets called.

我想知道如何调用 len() 。

人们很快就给出了正确的答案：

It doesn’t. Len is compiler magic, not an actual function call.

它没有。 Len 是编译器魔术，而不是实际的函数调用。

… all the types len works on have the same header format, the compiler just treats the object like a header and returns the integer representing the length of elements

.. len 处理的所有类型都具有相同的头格式，编译器只是将对象视为头并返回表示元素长度的整数

虽然这些答案在技术上是正确的，但我认为用一个简明的解释来展开构成这个 "魔法 "的层次是很好的 这也是一个很好的小练习，可以让我们更深入地了解 Go 编译器的内部工作原理。 顺便说一下，本帖中的所有链接都指向即将发布的 Go 1.17 分支 。

一个小插曲

一些可能有助于理解本文其余部分的背景信息。 Go 编译器由四个主要阶段组成。你可以从 这里 开始阅读它们。前两者一般称为编译器“前端”，后两者也称为编译器“后端”。

Parsing：源文件被标记、解析，并为每个源文件构建一个语法树。

AST transformations and type-checking：语法树被转换为编译器的 AST 表示，并且 AST 树被类型检查。

Generic SSA：AST 树被转换为静态单分配 (SSA) 形式，这是一种可以实现优化的低级中间表示。

Generating machine code：SSA 经历另一个特定于机器的优化过程，然后传递给汇编程序以转换为机器代码并写出最终的二进制文件。

让我们重新开始吧！

入口点

Go 编译器的入口点(不出所料)是 compile/internal/gc 包中的 main() 函数。正如文档字符串所暗示的那样，该函数负责解析 Go 源文件、对解析的 Go 包进行类型检查、将所有内容编译为机器代码并编写已编译的包定义。 早期发生的事情之一是 typecheck.InitUniverse() ，它定义了基本类型、内置函数和操作数。在那里，我们看到所有内置函数如何与“操作”匹配，我们可以使用 ir.OLEN 来跟踪调用 len 的步骤。

var builtinFuncs = [...]struct { name string op ir.Op}{ {"append", ir.OAPPEND}, {"cap", ir.OCAP}, {"close", ir.OCLOSE}, {"complex", ir.OCOMPLEX}, {"copy", ir.OCOPY}, {"delete", ir.ODELETE}, {"imag", ir.OIMAG}, {"len", ir.OLEN}, {"make", ir.OMAKE}, {"new", ir.ONEW}, {"panic", ir.OPANIC}, {"print", ir.OPRINT}, {"println", ir.OPRINTN}, {"real", ir.OREAL}, {"recover", ir.ORECOVER},}

稍后在 InitUniverse 中，可以看到 okfor 数组的初始化，它定义了各种操作数的有效类型；例如， + 运算符应该允许哪些类型:

if types.IsInt[et] || et == types.TIDEAL { ... okforadd[et] = true ... } if types.IsFloat[et] { ... okforadd[et] = true ... } if types.IsComplex[et] { ... okforadd[et] = true ... }

以同样的方式，我们可以看到所有类型都是 len() 的有效输入:

okforlen[types.TARRAY] = true okforlen[types.TCHAN] = true okforlen[types.TMAP] = true okforlen[types.TSLICE] = true okforlen[types.TSTRING] = true

编译器‘前端’

继续编译过程中的下一个主要步骤，我们到达了从 noder.LoadPackage(flag.Args()) 开始解析和检查输入的点。在更深的几个层次上，我们可以看到每个文件都被单独 解析 ，然后在五个不同的阶段进行类型检查。

Phase 1: const, type, and names and types of funcs.Phase 2: Variable assignments, interface assignments, alias declarations.Phase 3: Type check function bodies.Phase 4: Check external declarations.Phase 5: Verify map keys, unused dot imports.

一旦在最后一个类型检查阶段遇到 len 语句，它就会转换为 UnaryExpr，因为它实际上最终不会成为函数调用。 编译器隐式地获取参数的地址并使用 okforlen 数组来验证参数的合法性或发出相关的错误消息。

// typecheck1 should ONLY be called from typecheck.func typecheck1(n ir.Node, top int) ir.Node { if n, ok := n.(*ir.Name); ok { typecheckdef(n) } switch n.Op() { ... case ir.OCAP, ir.OLEN: n := n.(*ir.UnaryExpr) return tcLenCap(n) }}// tcLenCap typechecks an OLEN or OCAP node.func tcLenCap(n *ir.UnaryExpr) ir.Node { n.X = Expr(n.X) n.X = DefaultLit(n.X, nil) n.X = implicitstar(n.X) ... var ok bool if n.Op() == ir.OLEN { ok = okforlen[t.Kind()] } else { ok = okforcap[t.Kind()] } if !ok { base.Errorf("invalid argument %L for %v", l, n.Op()) n.SetType(nil) return n } n.SetType(types.Types[types.TINT]) return n}

回到主编译器流程，在对所有内容进行类型检查后，所有函数都将 排队等待编译 。 在 compileFunctions() 中，队列中的每个元素都通过 ssagen.Compile

compile = func(fns []*ir.Func) { wg.Add(len(fns)) for _, fn := range fns { fn := fn queue(func(worker int) { ssagen.Compile(fn, worker) compile(fn.Closures) wg.Done() }) } } ... compile(compilequeue)

在几层深的地方，在 buildssa 和 genssa 之后，我们终于可以将 AST 树中的 len 表达式转换为 SSA。 在这一点上很容易看到每个可用类型是如何处理的！

// expr converts the expression n to ssa, adds it to s and returns the ssa result.func (s *state) expr(n ir.Node) *ssa.Value { ... switch n.Op() { case ir.OLEN, ir.OCAP: n := n.(*ir.UnaryExpr) switch { case n.X.Type().IsSlice(): op := ssa.OpSliceLen if n.Op() == ir.OCAP { op = ssa.OpSliceCap } return s.newValue1(op, types.Types[types.TINT], s.expr(n.X)) case n.X.Type().IsString(): // string; not reachable for OCAP return s.newValue1(ssa.OpStringLen, types.Types[types.TINT], s.expr(n.X)) case n.X.Type().IsMap(), n.X.Type().IsChan(): return s.referenceTypeBuiltin(n, s.expr(n.X)) default: // array return s.constInt(types.Types[types.TINT], n.X.Type().NumElem()) } ... } ...}

数组

对于数组，我们仅根据输入数组的 NumElem() 方法返回一个常量整数，该方法仅访问输入数组的 Bound 字段。

// 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) NumElem() int64 { t.wantEtype(TARRAY) return t.Extra.(*Array).Bound}

切片，字符串

对于切片和字符串，我们必须看看 ssa.OpSliceLen 和 ssa.OpStringLen 是如何处理的。 当这些调用中的任何一个在后期扩展阶段和 rewriteSelect 方法中被降低时，切片和字符串将被递归遍历以使用诸如 offset+x.ptrSize 之类的指针算法来找出它们的大小

func (x *expandState) rewriteSelect(leaf *Value, selector *Value, offset int64, regOffset Abi1RO) []*LocalSlot { switch selector.Op { ... case OpStringLen, OpSliceLen: ls := x.rewriteSelect(leaf, selector.Args[0], offset+x.ptrSize, regOffset+RO_slice_len) locs = x.splitSlots(ls, ".len", x.ptrSize, leafType) ... } return locs

映射、通道

最后，对于映射和通道，我们使用 referenceTypeBuiltin 辅助工具。它的内部工作原理有点神奇，但它最终做的是获取 map/chan 参数的地址，并以零偏移量引用其结构布局，就像 unsafe.Pointer(uintptr(unsafe.Pointer(s)) 一样，最终返回第一个结构体的值。

// referenceTypeBuiltin generates code for the len/cap builtins for maps and channels.func (s *state) referenceTypeBuiltin(n *ir.UnaryExpr, x *ssa.Value) *ssa.Value { if !n.X.Type().IsMap() && !n.X.Type().IsChan() { s.Fatalf("node must be a map or a channel") } // if n == nil { // return 0 // } else { // // len // return *((*int)n) // // cap // return *(((*int)n)+1) // } lenType := n.Type() nilValue := s.constNil(types.Types[types.TUINTPTR]) cmp := s.newValue2(ssa.OpEqPtr, types.Types[types.TBOOL], x, nilValue) b := s.endBlock() b.Kind = ssa.BlockIf b.SetControl(cmp) b.Likely = ssa.BranchUnlikely bThen := s.f.NewBlock(ssa.BlockPlain) bElse := s.f.NewBlock(ssa.BlockPlain) bAfter := s.f.NewBlock(ssa.BlockPlain) ... switch n.Op() { case ir.OLEN: // length is stored in the first word for map/chan s.vars[n] = s.load(lenType, x) ... return s.variable(n, lenType)}

hmap 和 hchan 结构的定义表明，它们的第一个字段确实包含我们需要的 len，即分别是实时地图单元和通道队列数据。

type hmap struct { count int // # live cells == size of map. Must be first (used by len() builtin) flags uint8 B uint8 noverflow uint16 hash0 uint32 buckets unsafe.Pointer oldbuckets unsafe.Pointer nevacuate uintptr extra *mapextra}type hchan struct { qcount uint // total data in the queue dataqsiz uint buf unsafe.Pointer elemsize uint16 closed uint32 elemtype *_type sendx uint recvx uint recvq waitq sendq waitq lock mutex}

最后的话

Aaaand 就是这样！这篇文章没有我想象的那么长；我只是希望它对你也很有趣。 我对 Go 编译器的内部工作没有什么经验，所以有些东西可能是不对的。另外，很多东西在不久的将来都会发生变化，特别是泛型和新的类型系统会在接下来的几个 Go 版本中出现，但至少我希望我提供了一种方法，你可以用它来开始自己的挖掘工作。 在任何情况下，请不要犹豫，就新帖子发表评论、建议、想法或简单地谈论 Go！ 下次再见，再见！ 写于 2021 年 7 月 31 日

Go 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。