| 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 |
Members