[譯]Go 如何計算 len()..？#私藏項目實操分享#

Go 如何計算 len()..？

這篇文章的動機是不久前關于 Gophers Slack 的一個問題。一位開發(fā)人員想知道在哪里可以找到有關 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 是編譯器魔術，而不是實際的函數(shù)調用。

… 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 處理的所有類型都具有相同的頭格式，編譯器只是將對象視為頭并返回表示元素長度的整數(shù)

雖然這些答案在技術上是正確的，但我認為用一個簡明的解釋來展開構成這個 "魔法 "的層次是很好的 這也是一個很好的小練習，可以讓我們更深入地了解 Go 編譯器的內部工作原理。 順便說一下，本帖中的所有鏈接都指向即將發(fā)布的 Go 1.17 分支 。

一個小插曲

一些可能有助于理解本文其余部分的背景信息。 Go 編譯器由四個主要階段組成。你可以從 這里 開始閱讀它們。前兩者一般稱為編譯器“前端”，后兩者也稱為編譯器“后端”。

Parsing：源文件被標記、解析，并為每個源文件構建一個語法樹。

AST transformations and type-checking：語法樹被轉換為編譯器的 AST 表示，并且 AST 樹被類型檢查。

Generic SSA：AST 樹被轉換為靜態(tài)單分配 (SSA) 形式，這是一種可以實現(xiàn)優(yōu)化的低級中間表示。

Generating machine code：SSA 經(jīng)歷另一個特定于機器的優(yōu)化過程，然后傳遞給匯編程序以轉換為機器代碼并寫出最終的二進制文件。

讓我們重新開始吧！

入口點

Go 編譯器的入口點(不出所料)是 compile/internal/gc 包中的 main() 函數(shù)。正如文檔字符串所暗示的那樣，該函數(shù)負責解析 Go 源文件、對解析的 Go 包進行類型檢查、將所有內容編譯為機器代碼并編寫已編譯的包定義。 早期發(fā)生的事情之一是 typecheck.InitUniverse() ，它定義了基本類型、內置函數(shù)和操作數(shù)。在那里，我們看到所有內置函數(shù)如何與“操作”匹配，我們可以使用 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 數(shù)組的初始化，它定義了各種操作數(shù)的有效類型；例如， + 運算符應該允許哪些類型:

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

編譯器‘前端’

繼續(xù)編譯過程中的下一個主要步驟，我們到達了從 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，因為它實際上最終不會成為函數(shù)調用。 編譯器隱式地獲取參數(shù)的地址并使用 okforlen 數(shù)組來驗證參數(shù)的合法性或發(fā)出相關的錯誤消息。

// 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}

回到主編譯器流程，在對所有內容進行類型檢查后，所有函數(shù)都將 排隊等待編譯 。 在 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()) } ... } ...}

數(shù)組

對于數(shù)組，我們僅根據(jù)輸入數(shù)組的 NumElem() 方法返回一個常量整數(shù)，該方法僅訪問輸入數(shù)組的 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 參數(shù)的地址，并以零偏移量引用其結構布局，就像 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，即分別是實時地圖單元和通道隊列數(shù)據(jù)。

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 編譯器的內部工作沒有什么經(jīng)驗，所以有些東西可能是不對的。另外，很多東西在不久的將來都會發(fā)生變化，特別是泛型和新的類型系統(tǒng)會在接下來的幾個 Go 版本中出現(xiàn)，但至少我希望我提供了一種方法，你可以用它來開始自己的挖掘工作。 在任何情況下，請不要猶豫，就新帖子發(fā)表評論、建議、想法或簡單地談論 Go！ 下次再見，再見！ 寫于 2021 年 7 月 31 日

Go 數(shù)據(jù)結構

版權聲明：本文內容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內刪除侵權內容。

版權聲明：本文內容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內刪除侵權內容。