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.Reportf(stmt.Pos(), "unreachable code")
193			d.reachable = true // silence error about next statement
194		}
195	}
196
197	switch x := stmt.(type) {
198	default:
199		log.Fatalf("%s: internal error in findDead: unexpected statement %T", d.pass.Fset.Position(x.Pos()), x)
200
201	case *ast.AssignStmt,
202		*ast.BadStmt,
203		*ast.DeclStmt,
204		*ast.DeferStmt,
205		*ast.EmptyStmt,
206		*ast.GoStmt,
207		*ast.IncDecStmt,
208		*ast.SendStmt:
209		// no control flow
210
211	case *ast.BlockStmt:
212		for _, stmt := range x.List {
213			d.findDead(stmt)
214		}
215
216	case *ast.BranchStmt:
217		switch x.Tok {
218		case token.BREAK, token.GOTO, token.FALLTHROUGH:
219			d.reachable = false
220		case token.CONTINUE:
221			// NOTE: We accept "continue" statements as terminating.
222			// They are not necessary in the spec definition of terminating,
223			// because a continue statement cannot be the final statement
224			// before a return. But for the more general problem of syntactically
225			// identifying dead code, continue redirects control flow just
226			// like the other terminating statements.
227			d.reachable = false
228		}
229
230	case *ast.ExprStmt:
231		// Call to panic?
232		call, ok := x.X.(*ast.CallExpr)
233		if ok {
234			name, ok := call.Fun.(*ast.Ident)
235			if ok && name.Name == "panic" && name.Obj == nil {
236				d.reachable = false
237			}
238		}
239
240	case *ast.ForStmt:
241		d.findDead(x.Body)
242		d.reachable = x.Cond != nil || d.hasBreak[x]
243
244	case *ast.IfStmt:
245		d.findDead(x.Body)
246		if x.Else != nil {
247			r := d.reachable
248			d.reachable = true
249			d.findDead(x.Else)
250			d.reachable = d.reachable || r
251		} else {
252			// might not have executed if statement
253			d.reachable = true
254		}
255
256	case *ast.LabeledStmt:
257		d.findDead(x.Stmt)
258
259	case *ast.RangeStmt:
260		d.findDead(x.Body)
261		d.reachable = true
262
263	case *ast.ReturnStmt:
264		d.reachable = false
265
266	case *ast.SelectStmt:
267		// NOTE: Unlike switch and type switch below, we don't care
268		// whether a select has a default, because a select without a
269		// default blocks until one of the cases can run. That's different
270		// from a switch without a default, which behaves like it has
271		// a default with an empty body.
272		anyReachable := false
273		for _, comm := range x.Body.List {
274			d.reachable = true
275			for _, stmt := range comm.(*ast.CommClause).Body {
276				d.findDead(stmt)
277			}
278			anyReachable = anyReachable || d.reachable
279		}
280		d.reachable = anyReachable || d.hasBreak[x]
281
282	case *ast.SwitchStmt:
283		anyReachable := false
284		hasDefault := false
285		for _, cas := range x.Body.List {
286			cc := cas.(*ast.CaseClause)
287			if cc.List == nil {
288				hasDefault = true
289			}
290			d.reachable = true
291			for _, stmt := range cc.Body {
292				d.findDead(stmt)
293			}
294			anyReachable = anyReachable || d.reachable
295		}
296		d.reachable = anyReachable || d.hasBreak[x] || !hasDefault
297
298	case *ast.TypeSwitchStmt:
299		anyReachable := false
300		hasDefault := false
301		for _, cas := range x.Body.List {
302			cc := cas.(*ast.CaseClause)
303			if cc.List == nil {
304				hasDefault = true
305			}
306			d.reachable = true
307			for _, stmt := range cc.Body {
308				d.findDead(stmt)
309			}
310			anyReachable = anyReachable || d.reachable
311		}
312		d.reachable = anyReachable || d.hasBreak[x] || !hasDefault
313	}
314}
315