golang ctrlflow 代码
文件路径：/src/cmd/vendor/golang.org/x/tools/go/analysis/passes/ctrlflow/ctrlflow.go
/ Copyright 2018 The Go Authors. All rights reserved.
/ Use of this source code is governed by a BSD-style
/ license that can be found in the LICENSE file.
/ Package ctrlflow is an analysis that provides a syntactic
/ control-flow graph (CFG) for the body of a function.
/ It records whether a function cannot return.
/ By itself, it does not report any diagnostics.
package ctrlflow
import (
"go/ast"
"go/types"
"log"
"reflect"
"golang.org/x/tools/go/analysis"
"golang.org/x/tools/go/analysis/passes/inspect"
"golang.org/x/tools/go/ast/inspector"
"golang.org/x/tools/go/cfg"
"golang.org/x/tools/go/types/typeutil"
)
var Analyzer = &analysis.Analyzer{
Name: "ctrlflow",
Doc: "build a control-flow graph",
Run: run,
ResultType: reflect.TypeOf(new(CFGs)),
FactTypes: []analysis.Fact{new(noReturn)},
Requires: []*analysis.Analyzer{inspect.Analyzer},
}
/ noReturn is a fact indicating that a function does not return.
type noReturn struct{}
func (*noReturn) AFact() {}
func (*noReturn) String() string { return "noReturn" }
/ A CFGs holds the control-flow graphs
/ for all the functions of the current package.
type CFGs struct {
defs map[*ast.Ident]types.Object / from Pass.TypesInfo.Defs
funcDecls map[*types.Func]*declInfo
funcLits map[*ast.FuncLit]*litInfo
pass *analysis.Pass / transient; nil after construction
}
/ CFGs has two maps: funcDecls for named functions and funcLits for
/ unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
/ syntax node, *ast.FuncDecl, because callMayReturn needs to do a
/ look-up by *types.Func, and you can get from an *ast.FuncDecl to a
/ *types.Func but not the other way.
type declInfo struct {
decl *ast.FuncDecl
cfg *cfg.CFG / iff decl.Body != nil
started bool / to break cycles
noReturn bool
}
type litInfo struct {
cfg *cfg.CFG
noReturn bool
}
/ FuncDecl returns the control-flow graph for a named function.
/ It returns nil if decl.Body==nil.
func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
if decl.Body == nil {
return nil
}
fn := c.defs[decl.Name].(*types.Func)
return c.funcDecls[fn].cfg
}
/ FuncLit returns the control-flow graph for a literal function.
func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
return c.funcLits[lit].cfg
}
func run(pass *analysis.Pass) (interface{}, error) {
inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
/ Because CFG construction consumes and produces noReturn
/ facts, CFGs for exported FuncDecls must be built before 'run'
/ returns; we cannot construct them lazily.
/ (We could build CFGs for FuncLits lazily,
/ but the benefit is marginal.)
/ Pass 1. Map types.Funcs to ast.FuncDecls in this package.
funcDecls := make(map[*types.Func]*declInfo) / functions and methods
funcLits := make(map[*ast.FuncLit]*litInfo)
var decls []*types.Func / keys(funcDecls), in order
var lits []*ast.FuncLit / keys(funcLits), in order
nodeFilter := []ast.Node{
(*ast.FuncDecl)(nil),
(*ast.FuncLit)(nil),
}
inspect.Preorder(nodeFilter, func(n ast.Node) {
switch n := n.(type) {
case *ast.FuncDecl:
/ Type information may be incomplete.
if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
funcDecls[fn] = &declInfo{decl: n}
decls = append(decls, fn)
}
case *ast.FuncLit:
funcLits[n] = new(litInfo)
lits = append(lits, n)
}
})
c := &CFGs{
defs: pass.TypesInfo.Defs,
funcDecls: funcDecls,
funcLits: funcLits,
pass: pass,
}
/ Pass 2. Build CFGs.
/ Build CFGs for named functions.
/ Cycles in the static call graph are broken
/ arbitrarily but deterministically.
/ We create noReturn facts as discovered.
for _, fn := range decls {
c.buildDecl(fn, funcDecls[fn])
}
/ Build CFGs for literal functions.
/ These aren't relevant to facts (since they aren't named)
/ but are required for the CFGs.FuncLit API.
for _, lit := range lits {
li := funcLits[lit]
if li.cfg == nil {
li.cfg = cfg.New(lit.Body, c.callMayReturn)
if !hasReachableReturn(li.cfg) {
li.noReturn = true
}
}
}
/ All CFGs are now built.
c.pass = nil
return c, nil
}
/ di.cfg may be nil on return.
func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
/ buildDecl may call itself recursively for the same function,
/ because cfg.New is passed the callMayReturn method, which
/ builds the CFG of the callee, leading to recursion.
/ The buildDecl call tree thus resembles the static call graph.
/ We mark each node when we start working on it to break cycles.
if !di.started { / break cycle
di.started = true
if isIntrinsicNoReturn(fn) {
di.noReturn = true
}
if di.decl.Body != nil {
di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
if !hasReachableReturn(di.cfg) {
di.noReturn = true
}
}
if di.noReturn {
c.pass.ExportObjectFact(fn, new(noReturn))
}
/ debugging
if false {
log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
}
}
}
/ callMayReturn reports whether the called function may return.
/ It is passed to the CFG builder.
func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
return false / panic never returns
}
/ Is this a static call? Also includes static functions
/ parameterized by a type. Such functions may or may not
/ return depending on the parameter type, but in some
/ cases the answer is definite. We let ctrlflow figure
/ that out.
fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
if fn == nil {
return true / callee not statically known; be conservative
}
/ Function or method declared in this package?
if di, ok := c.funcDecls[fn]; ok {
c.buildDecl(fn, di)
return !di.noReturn
}
/ Not declared in this package.
/ Is there a fact from another package?
return !c.pass.ImportObjectFact(fn, new(noReturn))
}
var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
func hasReachableReturn(g *cfg.CFG) bool {
for _, b := range g.Blocks {
if b.Live && b.Return() != nil {
return true
}
}
return false
}
/ isIntrinsicNoReturn reports whether a function intrinsically never
/ returns because it stops execution of the calling thread.
/ It is the base case in the recursion.
func isIntrinsicNoReturn(fn *types.Func) bool {
/ Add functions here as the need arises, but don't allocate memory.
path, name := fn.Pkg().Path(), fn.Name()
return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
path == "runtime" && name == "Goexit"
}