| 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. |
| 4 | |
| 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. |
| 9 | package ctrlflow |
| 10 | |
| 11 | import ( |
| 12 | "go/ast" |
| 13 | "go/types" |
| 14 | "log" |
| 15 | "reflect" |
| 16 | |
| 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" |
| 22 | ) |
| 23 | |
| 24 | var Analyzer = &analysis.Analyzer{ |
| 25 | Name: "ctrlflow", |
| 26 | Doc: "build a control-flow graph", |
| 27 | Run: run, |
| 28 | ResultType: reflect.TypeOf(new(CFGs)), |
| 29 | FactTypes: []analysis.Fact{new(noReturn)}, |
| 30 | Requires: []*analysis.Analyzer{inspect.Analyzer}, |
| 31 | } |
| 32 | |
| 33 | // noReturn is a fact indicating that a function does not return. |
| 34 | type noReturn struct{} |
| 35 | |
| 36 | func (*noReturn) AFact() {} |
| 37 | |
| 38 | func (*noReturn) String() string { return "noReturn" } |
| 39 | |
| 40 | // A CFGs holds the control-flow graphs |
| 41 | // for all the functions of the current package. |
| 42 | type CFGs struct { |
| 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 |
| 47 | } |
| 48 | |
| 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. |
| 54 | |
| 55 | type declInfo struct { |
| 56 | decl *ast.FuncDecl |
| 57 | cfg *cfg.CFG // iff decl.Body != nil |
| 58 | started bool // to break cycles |
| 59 | noReturn bool |
| 60 | } |
| 61 | |
| 62 | type litInfo struct { |
| 63 | cfg *cfg.CFG |
| 64 | noReturn bool |
| 65 | } |
| 66 | |
| 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 { |
| 70 | if decl.Body == nil { |
| 71 | return nil |
| 72 | } |
| 73 | fn := c.defs[decl.Name].(*types.Func) |
| 74 | return c.funcDecls[fn].cfg |
| 75 | } |
| 76 | |
| 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 |
| 80 | } |
| 81 | |
| 82 | func run(pass *analysis.Pass) (interface{}, error) { |
| 83 | inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector) |
| 84 | |
| 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.) |
| 90 | |
| 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) |
| 94 | |
| 95 | var decls []*types.Func // keys(funcDecls), in order |
| 96 | var lits []*ast.FuncLit // keys(funcLits), in order |
| 97 | |
| 98 | nodeFilter := []ast.Node{ |
| 99 | (*ast.FuncDecl)(nil), |
| 100 | (*ast.FuncLit)(nil), |
| 101 | } |
| 102 | inspect.Preorder(nodeFilter, func(n ast.Node) { |
| 103 | switch n := n.(type) { |
| 104 | case *ast.FuncDecl: |
| 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) |
| 109 | } |
| 110 | case *ast.FuncLit: |
| 111 | funcLits[n] = new(litInfo) |
| 112 | lits = append(lits, n) |
| 113 | } |
| 114 | }) |
| 115 | |
| 116 | c := &CFGs{ |
| 117 | defs: pass.TypesInfo.Defs, |
| 118 | funcDecls: funcDecls, |
| 119 | funcLits: funcLits, |
| 120 | pass: pass, |
| 121 | } |
| 122 | |
| 123 | // Pass 2. Build CFGs. |
| 124 | |
| 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]) |
| 131 | } |
| 132 | |
| 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 { |
| 137 | li := funcLits[lit] |
| 138 | if li.cfg == nil { |
| 139 | li.cfg = cfg.New(lit.Body, c.callMayReturn) |
| 140 | if !hasReachableReturn(li.cfg) { |
| 141 | li.noReturn = true |
| 142 | } |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | // All CFGs are now built. |
| 147 | c.pass = nil |
| 148 | |
| 149 | return c, nil |
| 150 | } |
| 151 | |
| 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. |
| 159 | |
| 160 | if !di.started { // break cycle |
| 161 | di.started = true |
| 162 | |
| 163 | if isIntrinsicNoReturn(fn) { |
| 164 | di.noReturn = true |
| 165 | } |
| 166 | if di.decl.Body != nil { |
| 167 | di.cfg = cfg.New(di.decl.Body, c.callMayReturn) |
| 168 | if !hasReachableReturn(di.cfg) { |
| 169 | di.noReturn = true |
| 170 | } |
| 171 | } |
| 172 | if di.noReturn { |
| 173 | c.pass.ExportObjectFact(fn, new(noReturn)) |
| 174 | } |
| 175 | |
| 176 | // debugging |
| 177 | if false { |
| 178 | log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn) |
| 179 | } |
| 180 | } |
| 181 | } |
| 182 | |
| 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 |
| 188 | } |
| 189 | |
| 190 | // Is this a static call? Also includes static functions |
| 191 | // parameterized by a type. Such functions may or may not |
| 192 | // return depending on the parameter type, but in some |
| 193 | // cases the answer is definite. We let ctrlflow figure |
| 194 | // that out. |
| 195 | fn := typeutil.StaticCallee(c.pass.TypesInfo, call) |
| 196 | if fn == nil { |
| 197 | return true // callee not statically known; be conservative |
| 198 | } |
| 199 | |
| 200 | // Function or method declared in this package? |
| 201 | if di, ok := c.funcDecls[fn]; ok { |
| 202 | c.buildDecl(fn, di) |
| 203 | return !di.noReturn |
| 204 | } |
| 205 | |
| 206 | // Not declared in this package. |
| 207 | // Is there a fact from another package? |
| 208 | return !c.pass.ImportObjectFact(fn, new(noReturn)) |
| 209 | } |
| 210 | |
| 211 | var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin) |
| 212 | |
| 213 | func hasReachableReturn(g *cfg.CFG) bool { |
| 214 | for _, b := range g.Blocks { |
| 215 | if b.Live && b.Return() != nil { |
| 216 | return true |
| 217 | } |
| 218 | } |
| 219 | return false |
| 220 | } |
| 221 | |
| 222 | // isIntrinsicNoReturn reports whether a function intrinsically never |
| 223 | // returns because it stops execution of the calling thread. |
| 224 | // It is the base case in the recursion. |
| 225 | func isIntrinsicNoReturn(fn *types.Func) bool { |
| 226 | // Add functions here as the need arises, but don't allocate memory. |
| 227 | path, name := fn.Pkg().Path(), fn.Name() |
| 228 | return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") || |
| 229 | path == "runtime" && name == "Goexit" |
| 230 | } |
| 231 |
Members