1 // Copyright 2018 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Package ctrlflow is an analysis that provides a syntactic
6 // control-flow graph (CFG) for the body of a function.
7 // It records whether a function cannot return.
8 // By itself, it does not report any diagnostics.
17 "golang.org/x/tools/go/analysis"
18 "golang.org/x/tools/go/analysis/passes/inspect"
19 "golang.org/x/tools/go/ast/inspector"
20 "golang.org/x/tools/go/cfg"
21 "golang.org/x/tools/go/types/typeutil"
24 var Analyzer = &analysis.Analyzer{
26 Doc: "build a control-flow graph",
28 ResultType: reflect.TypeOf(new(CFGs)),
29 FactTypes: []analysis.Fact{new(noReturn)},
30 Requires: []*analysis.Analyzer{inspect.Analyzer},
33 // noReturn is a fact indicating that a function does not return.
34 type noReturn struct{}
36 func (*noReturn) AFact() {}
38 func (*noReturn) String() string { return "noReturn" }
40 // A CFGs holds the control-flow graphs
41 // for all the functions of the current package.
43 defs map[*ast.Ident]types.Object // from Pass.TypesInfo.Defs
44 funcDecls map[*types.Func]*declInfo
45 funcLits map[*ast.FuncLit]*litInfo
46 pass *analysis.Pass // transient; nil after construction
49 // CFGs has two maps: funcDecls for named functions and funcLits for
50 // unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
51 // syntax node, *ast.FuncDecl, because callMayReturn needs to do a
52 // look-up by *types.Func, and you can get from an *ast.FuncDecl to a
53 // *types.Func but not the other way.
55 type declInfo struct {
57 cfg *cfg.CFG // iff decl.Body != nil
58 started bool // to break cycles
67 // FuncDecl returns the control-flow graph for a named function.
68 // It returns nil if decl.Body==nil.
69 func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
73 fn := c.defs[decl.Name].(*types.Func)
74 return c.funcDecls[fn].cfg
77 // FuncLit returns the control-flow graph for a literal function.
78 func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
79 return c.funcLits[lit].cfg
82 func run(pass *analysis.Pass) (interface{}, error) {
83 inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
85 // Because CFG construction consumes and produces noReturn
86 // facts, CFGs for exported FuncDecls must be built before 'run'
87 // returns; we cannot construct them lazily.
88 // (We could build CFGs for FuncLits lazily,
89 // but the benefit is marginal.)
91 // Pass 1. Map types.Funcs to ast.FuncDecls in this package.
92 funcDecls := make(map[*types.Func]*declInfo) // functions and methods
93 funcLits := make(map[*ast.FuncLit]*litInfo)
95 var decls []*types.Func // keys(funcDecls), in order
96 var lits []*ast.FuncLit // keys(funcLits), in order
98 nodeFilter := []ast.Node{
102 inspect.Preorder(nodeFilter, func(n ast.Node) {
103 switch n := n.(type) {
105 // Type information may be incomplete.
106 if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
107 funcDecls[fn] = &declInfo{decl: n}
108 decls = append(decls, fn)
111 funcLits[n] = new(litInfo)
112 lits = append(lits, n)
117 defs: pass.TypesInfo.Defs,
118 funcDecls: funcDecls,
123 // Pass 2. Build CFGs.
125 // Build CFGs for named functions.
126 // Cycles in the static call graph are broken
127 // arbitrarily but deterministically.
128 // We create noReturn facts as discovered.
129 for _, fn := range decls {
130 c.buildDecl(fn, funcDecls[fn])
133 // Build CFGs for literal functions.
134 // These aren't relevant to facts (since they aren't named)
135 // but are required for the CFGs.FuncLit API.
136 for _, lit := range lits {
139 li.cfg = cfg.New(lit.Body, c.callMayReturn)
140 if !hasReachableReturn(li.cfg) {
146 // All CFGs are now built.
152 // di.cfg may be nil on return.
153 func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
154 // buildDecl may call itself recursively for the same function,
155 // because cfg.New is passed the callMayReturn method, which
156 // builds the CFG of the callee, leading to recursion.
157 // The buildDecl call tree thus resembles the static call graph.
158 // We mark each node when we start working on it to break cycles.
160 if !di.started { // break cycle
163 if isIntrinsicNoReturn(fn) {
166 if di.decl.Body != nil {
167 di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
168 if !hasReachableReturn(di.cfg) {
173 c.pass.ExportObjectFact(fn, new(noReturn))
178 log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
183 // callMayReturn reports whether the called function may return.
184 // It is passed to the CFG builder.
185 func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
186 if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
187 return false // panic never returns
190 // Is this a static call?
191 fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
193 return true // callee not statically known; be conservative
196 // Function or method declared in this package?
197 if di, ok := c.funcDecls[fn]; ok {
202 // Not declared in this package.
203 // Is there a fact from another package?
204 return !c.pass.ImportObjectFact(fn, new(noReturn))
207 var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
209 func hasReachableReturn(g *cfg.CFG) bool {
210 for _, b := range g.Blocks {
211 if b.Live && b.Return() != nil {
218 // isIntrinsicNoReturn reports whether a function intrinsically never
219 // returns because it stops execution of the calling thread.
220 // It is the base case in the recursion.
221 func isIntrinsicNoReturn(fn *types.Func) bool {
222 // Add functions here as the need arises, but don't allocate memory.
223 path, name := fn.Pkg().Path(), fn.Name()
224 return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
225 path == "runtime" && name == "Goexit"