1// Copyright 2018 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 ctrlflow is an analysis that provides a syntactic
6// control-flow graph (CFG) for the body of a function.
7// It records whether a function cannot return.
8// By itself, it does not report any diagnostics.
9package ctrlflow
10
11import (
12	"go/ast"
13	"go/types"
14	"log"
15	"reflect"
16
17	"golang.org/x/tools/go/analysis"
18	"golang.org/x/tools/go/analysis/passes/inspect"
19	"golang.org/x/tools/go/ast/inspector"
20	"golang.org/x/tools/go/cfg"
21	"golang.org/x/tools/go/types/typeutil"
22)
23
24var Analyzer = &analysis.Analyzer{
25	Name:       "ctrlflow",
26	Doc:        "build a control-flow graph",
27	URL:        "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/ctrlflow",
28	Run:        run,
29	ResultType: reflect.TypeOf(new(CFGs)),
30	FactTypes:  []analysis.Fact{new(noReturn)},
31	Requires:   []*analysis.Analyzer{inspect.Analyzer},
32}
33
34// noReturn is a fact indicating that a function does not return.
35type noReturn struct{}
36
37func (*noReturn) AFact() {}
38
39func (*noReturn) String() string { return "noReturn" }
40
41// A CFGs holds the control-flow graphs
42// for all the functions of the current package.
43type CFGs struct {
44	defs      map[*ast.Ident]types.Object // from Pass.TypesInfo.Defs
45	funcDecls map[*types.Func]*declInfo
46	funcLits  map[*ast.FuncLit]*litInfo
47	pass      *analysis.Pass // transient; nil after construction
48}
49
50// CFGs has two maps: funcDecls for named functions and funcLits for
51// unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
52// syntax node, *ast.FuncDecl, because callMayReturn needs to do a
53// look-up by *types.Func, and you can get from an *ast.FuncDecl to a
54// *types.Func but not the other way.
55
56type declInfo struct {
57	decl     *ast.FuncDecl
58	cfg      *cfg.CFG // iff decl.Body != nil
59	started  bool     // to break cycles
60	noReturn bool
61}
62
63type litInfo struct {
64	cfg      *cfg.CFG
65	noReturn bool
66}
67
68// FuncDecl returns the control-flow graph for a named function.
69// It returns nil if decl.Body==nil.
70func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
71	if decl.Body == nil {
72		return nil
73	}
74	fn := c.defs[decl.Name].(*types.Func)
75	return c.funcDecls[fn].cfg
76}
77
78// FuncLit returns the control-flow graph for a literal function.
79func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
80	return c.funcLits[lit].cfg
81}
82
83func run(pass *analysis.Pass) (interface{}, error) {
84	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
85
86	// Because CFG construction consumes and produces noReturn
87	// facts, CFGs for exported FuncDecls must be built before 'run'
88	// returns; we cannot construct them lazily.
89	// (We could build CFGs for FuncLits lazily,
90	// but the benefit is marginal.)
91
92	// Pass 1. Map types.Funcs to ast.FuncDecls in this package.
93	funcDecls := make(map[*types.Func]*declInfo) // functions and methods
94	funcLits := make(map[*ast.FuncLit]*litInfo)
95
96	var decls []*types.Func // keys(funcDecls), in order
97	var lits []*ast.FuncLit // keys(funcLits), in order
98
99	nodeFilter := []ast.Node{
100		(*ast.FuncDecl)(nil),
101		(*ast.FuncLit)(nil),
102	}
103	inspect.Preorder(nodeFilter, func(n ast.Node) {
104		switch n := n.(type) {
105		case *ast.FuncDecl:
106			// Type information may be incomplete.
107			if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
108				funcDecls[fn] = &declInfo{decl: n}
109				decls = append(decls, fn)
110			}
111		case *ast.FuncLit:
112			funcLits[n] = new(litInfo)
113			lits = append(lits, n)
114		}
115	})
116
117	c := &CFGs{
118		defs:      pass.TypesInfo.Defs,
119		funcDecls: funcDecls,
120		funcLits:  funcLits,
121		pass:      pass,
122	}
123
124	// Pass 2. Build CFGs.
125
126	// Build CFGs for named functions.
127	// Cycles in the static call graph are broken
128	// arbitrarily but deterministically.
129	// We create noReturn facts as discovered.
130	for _, fn := range decls {
131		c.buildDecl(fn, funcDecls[fn])
132	}
133
134	// Build CFGs for literal functions.
135	// These aren't relevant to facts (since they aren't named)
136	// but are required for the CFGs.FuncLit API.
137	for _, lit := range lits {
138		li := funcLits[lit]
139		if li.cfg == nil {
140			li.cfg = cfg.New(lit.Body, c.callMayReturn)
141			if !hasReachableReturn(li.cfg) {
142				li.noReturn = true
143			}
144		}
145	}
146
147	// All CFGs are now built.
148	c.pass = nil
149
150	return c, nil
151}
152
153// di.cfg may be nil on return.
154func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
155	// buildDecl may call itself recursively for the same function,
156	// because cfg.New is passed the callMayReturn method, which
157	// builds the CFG of the callee, leading to recursion.
158	// The buildDecl call tree thus resembles the static call graph.
159	// We mark each node when we start working on it to break cycles.
160
161	if !di.started { // break cycle
162		di.started = true
163
164		if isIntrinsicNoReturn(fn) {
165			di.noReturn = true
166		}
167		if di.decl.Body != nil {
168			di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
169			if !hasReachableReturn(di.cfg) {
170				di.noReturn = true
171			}
172		}
173		if di.noReturn {
174			c.pass.ExportObjectFact(fn, new(noReturn))
175		}
176
177		// debugging
178		if false {
179			log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
180		}
181	}
182}
183
184// callMayReturn reports whether the called function may return.
185// It is passed to the CFG builder.
186func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
187	if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
188		return false // panic never returns
189	}
190
191	// Is this a static call? Also includes static functions
192	// parameterized by a type. Such functions may or may not
193	// return depending on the parameter type, but in some
194	// cases the answer is definite. We let ctrlflow figure
195	// that out.
196	fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
197	if fn == nil {
198		return true // callee not statically known; be conservative
199	}
200
201	// Function or method declared in this package?
202	if di, ok := c.funcDecls[fn]; ok {
203		c.buildDecl(fn, di)
204		return !di.noReturn
205	}
206
207	// Not declared in this package.
208	// Is there a fact from another package?
209	return !c.pass.ImportObjectFact(fn, new(noReturn))
210}
211
212var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
213
214func hasReachableReturn(g *cfg.CFG) bool {
215	for _, b := range g.Blocks {
216		if b.Live && b.Return() != nil {
217			return true
218		}
219	}
220	return false
221}
222
223// isIntrinsicNoReturn reports whether a function intrinsically never
224// returns because it stops execution of the calling thread.
225// It is the base case in the recursion.
226func isIntrinsicNoReturn(fn *types.Func) bool {
227	// Add functions here as the need arises, but don't allocate memory.
228	path, name := fn.Pkg().Path(), fn.Name()
229	return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
230		path == "runtime" && name == "Goexit"
231}
232