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