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 // For example, this source code: 14 // 15 // if x := f(); x != nil { 16 // T() 17 // } else { 18 // F() 19 // } 20 // 21 // produces this CFG: 22 // 23 // 1: x := f() 24 // x != nil 25 // succs: 2, 3 26 // 2: T() 27 // succs: 4 28 // 3: F() 29 // succs: 4 30 // 4: 31 // 32 // The CFG does contain Return statements; even implicit returns are 33 // materialized (at the position of the function's closing brace). 34 // 35 // The CFG does not record conditions associated with conditional branch 36 // edges, nor the short-circuit semantics of the && and || operators, 37 // nor abnormal control flow caused by panic. If you need this 38 // information, use golang.org/x/tools/go/ssa instead. 39 package cfg 40 41 import ( 42 "bytes" 43 "fmt" 44 "go/ast" 45 "go/format" 46 "go/token" 47 ) 48 49 // A CFG represents the control-flow graph of a single function. 50 // 51 // The entry point is Blocks[0]; there may be multiple return blocks. 52 type CFG struct { 53 Blocks []*Block // block[0] is entry; order otherwise undefined 54 } 55 56 // A Block represents a basic block: a list of statements and 57 // expressions that are always evaluated sequentially. 58 // 59 // A block may have 0-2 successors: zero for a return block or a block 60 // that calls a function such as panic that never returns; one for a 61 // normal (jump) block; and two for a conditional (if) block. 62 type Block struct { 63 Nodes []ast.Node // statements, expressions, and ValueSpecs 64 Succs []*Block // successor nodes in the graph 65 Index int32 // index within CFG.Blocks 66 Live bool // block is reachable from entry 67 68 comment string // for debugging 69 succs2 [2]*Block // underlying array for Succs 70 } 71 72 // New returns a new control-flow graph for the specified function body, 73 // which must be non-nil. 74 // 75 // The CFG builder calls mayReturn to determine whether a given function 76 // call may return. For example, calls to panic, os.Exit, and log.Fatal 77 // do not return, so the builder can remove infeasible graph edges 78 // following such calls. The builder calls mayReturn only for a 79 // CallExpr beneath an ExprStmt. 80 func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG { 81 b := builder{ 82 mayReturn: mayReturn, 83 cfg: new(CFG), 84 } 85 b.current = b.newBlock("entry") 86 b.stmt(body) 87 88 // Compute liveness (reachability from entry point), breadth-first. 89 q := make([]*Block, 0, len(b.cfg.Blocks)) 90 q = append(q, b.cfg.Blocks[0]) // entry point 91 for len(q) > 0 { 92 b := q[len(q)-1] 93 q = q[:len(q)-1] 94 95 if !b.Live { 96 b.Live = true 97 q = append(q, b.Succs...) 98 } 99 } 100 101 // Does control fall off the end of the function's body? 102 // Make implicit return explicit. 103 if b.current != nil && b.current.Live { 104 b.add(&ast.ReturnStmt{ 105 Return: body.End() - 1, 106 }) 107 } 108 109 return b.cfg 110 } 111 112 func (b *Block) String() string { 113 return fmt.Sprintf("block %d (%s)", b.Index, b.comment) 114 } 115 116 // Return returns the return statement at the end of this block if present, nil otherwise. 117 func (b *Block) Return() (ret *ast.ReturnStmt) { 118 if len(b.Nodes) > 0 { 119 ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt) 120 } 121 return 122 } 123 124 // Format formats the control-flow graph for ease of debugging. 125 func (g *CFG) Format(fset *token.FileSet) string { 126 var buf bytes.Buffer 127 for _, b := range g.Blocks { 128 fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment) 129 for _, n := range b.Nodes { 130 fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n)) 131 } 132 if len(b.Succs) > 0 { 133 fmt.Fprintf(&buf, "\tsuccs:") 134 for _, succ := range b.Succs { 135 fmt.Fprintf(&buf, " %d", succ.Index) 136 } 137 buf.WriteByte('\n') 138 } 139 buf.WriteByte('\n') 140 } 141 return buf.String() 142 } 143 144 func formatNode(fset *token.FileSet, n ast.Node) string { 145 var buf bytes.Buffer 146 format.Node(&buf, fset, n) 147 // Indent secondary lines by a tab. 148 return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1)) 149 } 150