| // 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", |
| URL: "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/ctrlflow", |
| 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" |
| } |