Source file src/cmd/vendor/golang.org/x/tools/go/cfg/cfg.go
1 // Copyright 2016 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 cfg constructs a simple control-flow graph (CFG) of the 6 // statements and expressions within a single function. 7 // 8 // Use cfg.New to construct the CFG for a function body. 9 // 10 // The blocks of the CFG contain all the function's non-control 11 // statements. The CFG does not contain control statements such as If, 12 // Switch, Select, and Branch, but does contain their subexpressions; 13 // also, each block records the control statement (Block.Stmt) that 14 // gave rise to it and its relationship (Block.Kind) to that statement. 15 // 16 // For example, this source code: 17 // 18 // if x := f(); x != nil { 19 // T() 20 // } else { 21 // F() 22 // } 23 // 24 // produces this CFG: 25 // 26 // 1: x := f() Body 27 // x != nil 28 // succs: 2, 3 29 // 2: T() IfThen 30 // succs: 4 31 // 3: F() IfElse 32 // succs: 4 33 // 4: IfDone 34 // 35 // The CFG does contain Return statements; even implicit returns are 36 // materialized (at the position of the function's closing brace). 37 // 38 // The CFG does not record conditions associated with conditional branch 39 // edges, nor the short-circuit semantics of the && and || operators, 40 // nor abnormal control flow caused by panic. If you need this 41 // information, use golang.org/x/tools/go/ssa instead. 42 package cfg 43 44 import ( 45 "bytes" 46 "fmt" 47 "go/ast" 48 "go/format" 49 "go/token" 50 51 "golang.org/x/tools/internal/cfginternal" 52 ) 53 54 // A CFG represents the control-flow graph of a single function. 55 // 56 // The entry point is Blocks[0]; there may be multiple return blocks. 57 type CFG struct { 58 Blocks []*Block // block[0] is entry; order otherwise undefined 59 noreturn bool // function body lacks a reachable return statement 60 } 61 62 // A Block represents a basic block: a list of statements and 63 // expressions that are always evaluated sequentially. 64 // 65 // A block may have 0-2 successors: zero for a return block or a block 66 // that calls a function such as panic that never returns; one for a 67 // normal (jump) block; and two for a conditional (if) block. 68 // 69 // In a conditional block, the last entry in Nodes is the condition and always 70 // an [ast.Expr], Succs[0] is the successor if the condition is true, and 71 // Succs[1] is the successor if the condition is false. 72 type Block struct { 73 Nodes []ast.Node // statements, expressions, and ValueSpecs 74 Succs []*Block // successor nodes in the graph 75 Index int32 // index within CFG.Blocks 76 Live bool // block is reachable from entry 77 returns bool // block contains return or defer (which may recover and return) 78 Kind BlockKind // block kind 79 Stmt ast.Stmt // statement that gave rise to this block (see BlockKind for details) 80 81 succs2 [2]*Block // underlying array for Succs 82 } 83 84 // A BlockKind identifies the purpose of a block. 85 // It also determines the possible types of its Stmt field. 86 type BlockKind uint8 87 88 const ( 89 KindInvalid BlockKind = iota // Stmt=nil 90 91 KindUnreachable // unreachable block after {Branch,Return}Stmt / no-return call ExprStmt 92 KindBody // function body BlockStmt 93 KindForBody // body of ForStmt 94 KindForDone // block after ForStmt 95 KindForLoop // head of ForStmt 96 KindForPost // post condition of ForStmt 97 KindIfDone // block after IfStmt 98 KindIfElse // else block of IfStmt 99 KindIfThen // then block of IfStmt 100 KindLabel // labeled block of BranchStmt (Stmt may be nil for dangling label) 101 KindRangeBody // body of RangeStmt 102 KindRangeDone // block after RangeStmt 103 KindRangeLoop // head of RangeStmt 104 KindSelectCaseBody // body of SelectStmt 105 KindSelectDone // block after SelectStmt 106 KindSelectAfterCase // block after a CommClause 107 KindSwitchCaseBody // body of CaseClause 108 KindSwitchDone // block after {Type.}SwitchStmt 109 KindSwitchNextCase // secondary expression of a multi-expression CaseClause 110 ) 111 112 func (kind BlockKind) String() string { 113 return [...]string{ 114 KindInvalid: "Invalid", 115 KindUnreachable: "Unreachable", 116 KindBody: "Body", 117 KindForBody: "ForBody", 118 KindForDone: "ForDone", 119 KindForLoop: "ForLoop", 120 KindForPost: "ForPost", 121 KindIfDone: "IfDone", 122 KindIfElse: "IfElse", 123 KindIfThen: "IfThen", 124 KindLabel: "Label", 125 KindRangeBody: "RangeBody", 126 KindRangeDone: "RangeDone", 127 KindRangeLoop: "RangeLoop", 128 KindSelectCaseBody: "SelectCaseBody", 129 KindSelectDone: "SelectDone", 130 KindSelectAfterCase: "SelectAfterCase", 131 KindSwitchCaseBody: "SwitchCaseBody", 132 KindSwitchDone: "SwitchDone", 133 KindSwitchNextCase: "SwitchNextCase", 134 }[kind] 135 } 136 137 // New returns a new control-flow graph for the specified function body, 138 // which must be non-nil. 139 // 140 // The CFG builder calls mayReturn to determine whether a given function 141 // call may return. For example, calls to panic, os.Exit, and log.Fatal 142 // do not return, so the builder can remove infeasible graph edges 143 // following such calls. The builder calls mayReturn only for a 144 // CallExpr beneath an ExprStmt. 145 func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG { 146 b := builder{ 147 mayReturn: mayReturn, 148 } 149 b.current = b.newBlock(KindBody, body) 150 b.stmt(body) 151 152 // Compute liveness (reachability from entry point), 153 // breadth-first, marking Block.Live flags. 154 q := make([]*Block, 0, len(b.blocks)) 155 q = append(q, b.blocks[0]) // entry point 156 for len(q) > 0 { 157 b := q[len(q)-1] 158 q = q[:len(q)-1] 159 160 if !b.Live { 161 b.Live = true 162 q = append(q, b.Succs...) 163 } 164 } 165 166 // Does control fall off the end of the function's body? 167 // Make implicit return explicit. 168 if b.current != nil && b.current.Live { 169 b.current.returns = true 170 b.add(&ast.ReturnStmt{ 171 Return: body.End() - 1, 172 }) 173 } 174 175 // Is any return (or defer+recover) block reachable? 176 noreturn := true 177 for _, bl := range b.blocks { 178 if bl.Live && bl.returns { 179 noreturn = false 180 break 181 } 182 } 183 184 return &CFG{Blocks: b.blocks, noreturn: noreturn} 185 } 186 187 // isNoReturn reports whether the function has no reachable return. 188 // TODO(adonovan): add (*CFG).NoReturn to public API. 189 func isNoReturn(_cfg any) bool { return _cfg.(*CFG).noreturn } 190 191 func init() { 192 cfginternal.IsNoReturn = isNoReturn // expose to ctrlflow analyzer 193 } 194 195 func (b *Block) String() string { 196 return fmt.Sprintf("block %d (%s)", b.Index, b.comment(nil)) 197 } 198 199 func (b *Block) comment(fset *token.FileSet) string { 200 s := b.Kind.String() 201 if fset != nil && b.Stmt != nil { 202 s = fmt.Sprintf("%s@L%d", s, fset.Position(b.Stmt.Pos()).Line) 203 } 204 return s 205 } 206 207 // Return returns the return statement at the end of this block if present, nil 208 // otherwise. 209 // 210 // When control falls off the end of the function, the ReturnStmt is synthetic 211 // and its [ast.Node.End] position may be beyond the end of the file. 212 // 213 // A function that contains no return statement (explicit or implied) 214 // may yet return normally, and may even return a nonzero value. For example: 215 // 216 // func() (res any) { 217 // defer func() { res = recover() }() 218 // panic(123) 219 // } 220 func (b *Block) Return() (ret *ast.ReturnStmt) { 221 if len(b.Nodes) > 0 { 222 ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt) 223 } 224 return 225 } 226 227 // Format formats the control-flow graph for ease of debugging. 228 func (g *CFG) Format(fset *token.FileSet) string { 229 var buf bytes.Buffer 230 for _, b := range g.Blocks { 231 fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment(fset)) 232 for _, n := range b.Nodes { 233 fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n)) 234 } 235 if len(b.Succs) > 0 { 236 fmt.Fprintf(&buf, "\tsuccs:") 237 for _, succ := range b.Succs { 238 fmt.Fprintf(&buf, " %d", succ.Index) 239 } 240 buf.WriteByte('\n') 241 } 242 buf.WriteByte('\n') 243 } 244 return buf.String() 245 } 246 247 // Dot returns the control-flow graph in the [Dot graph description language]. 248 // Use a command such as 'dot -Tsvg' to render it in a form viewable in a browser. 249 // This method is provided as a debugging aid; the details of the 250 // output are unspecified and may change. 251 // 252 // [Dot graph description language]: https://en.wikipedia.org/wiki/DOT_(graph_description_language) 253 func (g *CFG) Dot(fset *token.FileSet) string { 254 var buf bytes.Buffer 255 buf.WriteString("digraph CFG {\n") 256 buf.WriteString(" node [shape=box];\n") 257 for _, b := range g.Blocks { 258 // node label 259 var text bytes.Buffer 260 text.WriteString(b.comment(fset)) 261 for _, n := range b.Nodes { 262 fmt.Fprintf(&text, "\n%s", formatNode(fset, n)) 263 } 264 265 // node and edges 266 fmt.Fprintf(&buf, " n%d [label=%q];\n", b.Index, &text) 267 for _, succ := range b.Succs { 268 fmt.Fprintf(&buf, " n%d -> n%d;\n", b.Index, succ.Index) 269 } 270 } 271 buf.WriteString("}\n") 272 return buf.String() 273 } 274 275 func formatNode(fset *token.FileSet, n ast.Node) string { 276 var buf bytes.Buffer 277 format.Node(&buf, fset, n) 278 // Indent secondary lines by a tab. 279 return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1)) 280 } 281