blob: 37d799f4bc3b4de3dce0603c4796b4fa81fb6765 [file] [log] [blame]
Alan Donovan942d5832018-09-17 09:28:16 -04001// 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
Rebecca Stambler207d3de2019-11-20 22:43:00 -05005// Package cfg constructs a simple control-flow graph (CFG) of the
Alan Donovan942d5832018-09-17 09:28:16 -04006// 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//
Russ Coxd5f48fc2022-04-11 23:03:04 -040023// 1: x := f()
24// x != nil
25// succs: 2, 3
26// 2: T()
27// succs: 4
28// 3: F()
29// succs: 4
30// 4:
Alan Donovan942d5832018-09-17 09:28:16 -040031//
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.
Alan Donovan942d5832018-09-17 09:28:16 -040039package cfg
40
41import (
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.
52type 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.
62type 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.
80func 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
112func (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.
117func (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.
125func (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
144func 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}