1// Copyright 2013 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 unreachable defines an Analyzer that checks for unreachable code.
6package unreachable
7
8// TODO(adonovan): use the new cfg package, which is more precise.
9
10import (
11	"go/ast"
12	"go/token"
13	"log"
14
15	"golang.org/x/tools/go/analysis"
16	"golang.org/x/tools/go/analysis/passes/inspect"
17	"golang.org/x/tools/go/ast/inspector"
18)
19
20const Doc = `check for unreachable code
21
22The unreachable analyzer finds statements that execution can never reach
23because they are preceded by an return statement, a call to panic, an
24infinite loop, or similar constructs.`
25
26var Analyzer = &analysis.Analyzer{
27	Name:             "unreachable",
28	Doc:              Doc,
29	Requires:         []*analysis.Analyzer{inspect.Analyzer},
30	RunDespiteErrors: true,
31	Run:              run,
32}
33
34func run(pass *analysis.Pass) (interface{}, error) {
35	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
36
37	nodeFilter := []ast.Node{
38		(*ast.FuncDecl)(nil),
39		(*ast.FuncLit)(nil),
40	}
41	inspect.Preorder(nodeFilter, func(n ast.Node) {
42		var body *ast.BlockStmt
43		switch n := n.(type) {
44		case *ast.FuncDecl:
45			body = n.Body
46		case *ast.FuncLit:
47			body = n.Body
48		}
49		if body == nil {
50			return
51		}
52		d := &deadState{
53			pass:     pass,
54			hasBreak: make(map[ast.Stmt]bool),
55			hasGoto:  make(map[string]bool),
56			labels:   make(map[string]ast.Stmt),
57		}
58		d.findLabels(body)
59		d.reachable = true
60		d.findDead(body)
61	})
62	return nil, nil
63}
64
65type deadState struct {
66	pass        *analysis.Pass
67	hasBreak    map[ast.Stmt]bool
68	hasGoto     map[string]bool
69	labels      map[string]ast.Stmt
70	breakTarget ast.Stmt
71
72	reachable bool
73}
74
75// findLabels gathers information about the labels defined and used by stmt
76// and about which statements break, whether a label is involved or not.
77func (d *deadState) findLabels(stmt ast.Stmt) {
78	switch x := stmt.(type) {
79	default:
80		log.Fatalf("%s: internal error in findLabels: unexpected statement %T", d.pass.Fset.Position(x.Pos()), x)
81
82	case *ast.AssignStmt,
83		*ast.BadStmt,
84		*ast.DeclStmt,
85		*ast.DeferStmt,
86		*ast.EmptyStmt,
87		*ast.ExprStmt,
88		*ast.GoStmt,
89		*ast.IncDecStmt,
90		*ast.ReturnStmt,
91		*ast.SendStmt:
92		// no statements inside
93
94	case *ast.BlockStmt:
95		for _, stmt := range x.List {
96			d.findLabels(stmt)
97		}
98
99	case *ast.BranchStmt:
100		switch x.Tok {
101		case token.GOTO:
102			if x.Label != nil {
103				d.hasGoto[x.Label.Name] = true
104			}
105
106		case token.BREAK:
107			stmt := d.breakTarget
108			if x.Label != nil {
109				stmt = d.labels[x.Label.Name]
110			}
111			if stmt != nil {
112				d.hasBreak[stmt] = true
113			}
114		}
115
116	case *ast.IfStmt:
117		d.findLabels(x.Body)
118		if x.Else != nil {
119			d.findLabels(x.Else)
120		}
121
122	case *ast.LabeledStmt:
123		d.labels[x.Label.Name] = x.Stmt
124		d.findLabels(x.Stmt)
125
126	// These cases are all the same, but the x.Body only works
127	// when the specific type of x is known, so the cases cannot
128	// be merged.
129	case *ast.ForStmt:
130		outer := d.breakTarget
131		d.breakTarget = x
132		d.findLabels(x.Body)
133		d.breakTarget = outer
134
135	case *ast.RangeStmt:
136		outer := d.breakTarget
137		d.breakTarget = x
138		d.findLabels(x.Body)
139		d.breakTarget = outer
140
141	case *ast.SelectStmt:
142		outer := d.breakTarget
143		d.breakTarget = x
144		d.findLabels(x.Body)
145		d.breakTarget = outer
146
147	case *ast.SwitchStmt:
148		outer := d.breakTarget
149		d.breakTarget = x
150		d.findLabels(x.Body)
151		d.breakTarget = outer
152
153	case *ast.TypeSwitchStmt:
154		outer := d.breakTarget
155		d.breakTarget = x
156		d.findLabels(x.Body)
157		d.breakTarget = outer
158
159	case *ast.CommClause:
160		for _, stmt := range x.Body {
161			d.findLabels(stmt)
162		}
163
164	case *ast.CaseClause:
165		for _, stmt := range x.Body {
166			d.findLabels(stmt)
167		}
168	}
169}
170
171// findDead walks the statement looking for dead code.
172// If d.reachable is false on entry, stmt itself is dead.
173// When findDead returns, d.reachable tells whether the
174// statement following stmt is reachable.
175func (d *deadState) findDead(stmt ast.Stmt) {
176	// Is this a labeled goto target?
177	// If so, assume it is reachable due to the goto.
178	// This is slightly conservative, in that we don't
179	// check that the goto is reachable, so
180	//	L: goto L
181	// will not provoke a warning.
182	// But it's good enough.
183	if x, isLabel := stmt.(*ast.LabeledStmt); isLabel && d.hasGoto[x.Label.Name] {
184		d.reachable = true
185	}
186
187	if !d.reachable {
188		switch stmt.(type) {
189		case *ast.EmptyStmt:
190			// do not warn about unreachable empty statements
191		default:
192			d.pass.Report(analysis.Diagnostic{
193				Pos:     stmt.Pos(),
194				End:     stmt.End(),
195				Message: "unreachable code",
196				SuggestedFixes: []analysis.SuggestedFix{{
197					Message: "Remove",
198					TextEdits: []analysis.TextEdit{{
199						Pos: stmt.Pos(),
200						End: stmt.End(),
201					}},
202				}},
203			})
204			d.reachable = true // silence error about next statement
205		}
206	}
207
208	switch x := stmt.(type) {
209	default:
210		log.Fatalf("%s: internal error in findDead: unexpected statement %T", d.pass.Fset.Position(x.Pos()), x)
211
212	case *ast.AssignStmt,
213		*ast.BadStmt,
214		*ast.DeclStmt,
215		*ast.DeferStmt,
216		*ast.EmptyStmt,
217		*ast.GoStmt,
218		*ast.IncDecStmt,
219		*ast.SendStmt:
220		// no control flow
221
222	case *ast.BlockStmt:
223		for _, stmt := range x.List {
224			d.findDead(stmt)
225		}
226
227	case *ast.BranchStmt:
228		switch x.Tok {
229		case token.BREAK, token.GOTO, token.FALLTHROUGH:
230			d.reachable = false
231		case token.CONTINUE:
232			// NOTE: We accept "continue" statements as terminating.
233			// They are not necessary in the spec definition of terminating,
234			// because a continue statement cannot be the final statement
235			// before a return. But for the more general problem of syntactically
236			// identifying dead code, continue redirects control flow just
237			// like the other terminating statements.
238			d.reachable = false
239		}
240
241	case *ast.ExprStmt:
242		// Call to panic?
243		call, ok := x.X.(*ast.CallExpr)
244		if ok {
245			name, ok := call.Fun.(*ast.Ident)
246			if ok && name.Name == "panic" && name.Obj == nil {
247				d.reachable = false
248			}
249		}
250
251	case *ast.ForStmt:
252		d.findDead(x.Body)
253		d.reachable = x.Cond != nil || d.hasBreak[x]
254
255	case *ast.IfStmt:
256		d.findDead(x.Body)
257		if x.Else != nil {
258			r := d.reachable
259			d.reachable = true
260			d.findDead(x.Else)
261			d.reachable = d.reachable || r
262		} else {
263			// might not have executed if statement
264			d.reachable = true
265		}
266
267	case *ast.LabeledStmt:
268		d.findDead(x.Stmt)
269
270	case *ast.RangeStmt:
271		d.findDead(x.Body)
272		d.reachable = true
273
274	case *ast.ReturnStmt:
275		d.reachable = false
276
277	case *ast.SelectStmt:
278		// NOTE: Unlike switch and type switch below, we don't care
279		// whether a select has a default, because a select without a
280		// default blocks until one of the cases can run. That's different
281		// from a switch without a default, which behaves like it has
282		// a default with an empty body.
283		anyReachable := false
284		for _, comm := range x.Body.List {
285			d.reachable = true
286			for _, stmt := range comm.(*ast.CommClause).Body {
287				d.findDead(stmt)
288			}
289			anyReachable = anyReachable || d.reachable
290		}
291		d.reachable = anyReachable || d.hasBreak[x]
292
293	case *ast.SwitchStmt:
294		anyReachable := false
295		hasDefault := false
296		for _, cas := range x.Body.List {
297			cc := cas.(*ast.CaseClause)
298			if cc.List == nil {
299				hasDefault = true
300			}
301			d.reachable = true
302			for _, stmt := range cc.Body {
303				d.findDead(stmt)
304			}
305			anyReachable = anyReachable || d.reachable
306		}
307		d.reachable = anyReachable || d.hasBreak[x] || !hasDefault
308
309	case *ast.TypeSwitchStmt:
310		anyReachable := false
311		hasDefault := false
312		for _, cas := range x.Body.List {
313			cc := cas.(*ast.CaseClause)
314			if cc.List == nil {
315				hasDefault = true
316			}
317			d.reachable = true
318			for _, stmt := range cc.Body {
319				d.findDead(stmt)
320			}
321			anyReachable = anyReachable || d.reachable
322		}
323		d.reachable = anyReachable || d.hasBreak[x] || !hasDefault
324	}
325}
326