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