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