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