1package ineffassign
2
3import (
4	"fmt"
5	"go/ast"
6	"go/token"
7	"sort"
8	"strings"
9
10	"golang.org/x/tools/go/analysis"
11)
12
13// Analyzer is the ineffassign analysis.Analyzer instance.
14var Analyzer = &analysis.Analyzer{
15	Name: "ineffassign",
16	Doc:  "detect ineffectual assignments in Go code",
17	Run:  checkPath,
18}
19
20func checkPath(pass *analysis.Pass) (interface{}, error) {
21	for _, file := range pass.Files {
22		if isGenerated(file) {
23			continue
24		}
25
26		bld := &builder{vars: map[*ast.Object]*variable{}}
27		bld.walk(file)
28
29		chk := &checker{vars: bld.vars, seen: map[*block]bool{}}
30		for _, b := range bld.roots {
31			chk.check(b)
32		}
33		sort.Sort(chk.ineff)
34
35		for _, id := range chk.ineff {
36			pass.Report(analysis.Diagnostic{
37				Pos:     id.Pos(),
38				Message: fmt.Sprintf("ineffectual assignment to %s", id.Name),
39			})
40		}
41	}
42
43	return nil, nil
44}
45
46func isGenerated(file *ast.File) bool {
47	for _, cg := range file.Comments {
48		for _, c := range cg.List {
49			if strings.HasPrefix(c.Text, "// Code generated ") && strings.HasSuffix(c.Text, " DO NOT EDIT.") {
50				return true
51			}
52		}
53	}
54
55	return false
56}
57
58type builder struct {
59	roots     []*block
60	block     *block
61	vars      map[*ast.Object]*variable
62	results   []*ast.FieldList
63	breaks    branchStack
64	continues branchStack
65	gotos     branchStack
66	labelStmt *ast.LabeledStmt
67}
68
69type block struct {
70	children []*block
71	ops      map[*ast.Object][]operation
72}
73
74func (b *block) addChild(c *block) {
75	b.children = append(b.children, c)
76}
77
78type operation struct {
79	id     *ast.Ident
80	assign bool
81}
82
83type variable struct {
84	fundept int
85	escapes bool
86}
87
88func (bld *builder) walk(n ast.Node) {
89	if n != nil {
90		ast.Walk(bld, n)
91	}
92}
93
94func (bld *builder) Visit(n ast.Node) ast.Visitor {
95	switch n := n.(type) {
96	case *ast.FuncDecl:
97		if n.Body != nil {
98			bld.fun(n.Type, n.Body)
99		}
100	case *ast.FuncLit:
101		bld.fun(n.Type, n.Body)
102	case *ast.IfStmt:
103		bld.walk(n.Init)
104		bld.walk(n.Cond)
105		b0 := bld.block
106		bld.newBlock(b0)
107		bld.walk(n.Body)
108		b1 := bld.block
109		if n.Else != nil {
110			bld.newBlock(b0)
111			bld.walk(n.Else)
112			b0 = bld.block
113		}
114		bld.newBlock(b0, b1)
115	case *ast.ForStmt:
116		lbl := bld.stmtLabel(n)
117		brek := bld.breaks.push(lbl)
118		continu := bld.continues.push(lbl)
119		bld.walk(n.Init)
120		start := bld.newBlock(bld.block)
121		bld.walk(n.Cond)
122		cond := bld.block
123		bld.newBlock(cond)
124		bld.walk(n.Body)
125		continu.setDestination(bld.newBlock(bld.block))
126		bld.walk(n.Post)
127		bld.block.addChild(start)
128		brek.setDestination(bld.newBlock(cond))
129		bld.breaks.pop()
130		bld.continues.pop()
131	case *ast.RangeStmt:
132		lbl := bld.stmtLabel(n)
133		brek := bld.breaks.push(lbl)
134		continu := bld.continues.push(lbl)
135		bld.walk(n.X)
136		pre := bld.newBlock(bld.block)
137		start := bld.newBlock(pre)
138		if n.Key != nil {
139			lhs := []ast.Expr{n.Key}
140			if n.Value != nil {
141				lhs = append(lhs, n.Value)
142			}
143			bld.walk(&ast.AssignStmt{Lhs: lhs, Tok: n.Tok, TokPos: n.TokPos, Rhs: []ast.Expr{&ast.Ident{NamePos: n.X.End()}}})
144		}
145		bld.walk(n.Body)
146		bld.block.addChild(start)
147		continu.setDestination(pre)
148		brek.setDestination(bld.newBlock(pre, bld.block))
149		bld.breaks.pop()
150		bld.continues.pop()
151	case *ast.SwitchStmt:
152		bld.walk(n.Init)
153		bld.walk(n.Tag)
154		bld.swtch(n, n.Body.List)
155	case *ast.TypeSwitchStmt:
156		bld.walk(n.Init)
157		bld.walk(n.Assign)
158		bld.swtch(n, n.Body.List)
159	case *ast.SelectStmt:
160		brek := bld.breaks.push(bld.stmtLabel(n))
161		for _, c := range n.Body.List {
162			c := c.(*ast.CommClause).Comm
163			if s, ok := c.(*ast.AssignStmt); ok {
164				bld.walk(s.Rhs[0])
165			} else {
166				bld.walk(c)
167			}
168		}
169		b0 := bld.block
170		exits := make([]*block, len(n.Body.List))
171		dfault := false
172		for i, c := range n.Body.List {
173			c := c.(*ast.CommClause)
174			bld.newBlock(b0)
175			bld.walk(c)
176			exits[i] = bld.block
177			dfault = dfault || c.Comm == nil
178		}
179		if !dfault {
180			exits = append(exits, b0)
181		}
182		brek.setDestination(bld.newBlock(exits...))
183		bld.breaks.pop()
184	case *ast.LabeledStmt:
185		bld.gotos.get(n.Label).setDestination(bld.newBlock(bld.block))
186		bld.labelStmt = n
187		bld.walk(n.Stmt)
188	case *ast.BranchStmt:
189		switch n.Tok {
190		case token.BREAK:
191			bld.breaks.get(n.Label).addSource(bld.block)
192			bld.newBlock()
193		case token.CONTINUE:
194			bld.continues.get(n.Label).addSource(bld.block)
195			bld.newBlock()
196		case token.GOTO:
197			bld.gotos.get(n.Label).addSource(bld.block)
198			bld.newBlock()
199		}
200
201	case *ast.AssignStmt:
202		if n.Tok == token.QUO_ASSIGN || n.Tok == token.REM_ASSIGN {
203			bld.maybePanic()
204		}
205
206		for _, x := range n.Rhs {
207			bld.walk(x)
208		}
209		for i, x := range n.Lhs {
210			if id, ok := ident(x); ok {
211				if n.Tok >= token.ADD_ASSIGN && n.Tok <= token.AND_NOT_ASSIGN {
212					bld.use(id)
213				}
214				// Don't treat explicit initialization to zero as assignment; it is often used as shorthand for a bare declaration.
215				if n.Tok == token.DEFINE && i < len(n.Rhs) && isZeroInitializer(n.Rhs[i]) {
216					bld.use(id)
217				} else {
218					bld.assign(id)
219				}
220			} else {
221				bld.walk(x)
222			}
223		}
224	case *ast.GenDecl:
225		if n.Tok == token.VAR {
226			for _, s := range n.Specs {
227				s := s.(*ast.ValueSpec)
228				for _, x := range s.Values {
229					bld.walk(x)
230				}
231				for _, id := range s.Names {
232					if len(s.Values) > 0 {
233						bld.assign(id)
234					} else {
235						bld.use(id)
236					}
237				}
238			}
239		}
240	case *ast.IncDecStmt:
241		if id, ok := ident(n.X); ok {
242			bld.use(id)
243			bld.assign(id)
244		} else {
245			bld.walk(n.X)
246		}
247	case *ast.Ident:
248		bld.use(n)
249	case *ast.ReturnStmt:
250		for _, x := range n.Results {
251			bld.walk(x)
252		}
253		if res := bld.results[len(bld.results)-1]; res != nil {
254			for _, f := range res.List {
255				for _, id := range f.Names {
256					if n.Results != nil {
257						bld.assign(id)
258					}
259					bld.use(id)
260				}
261			}
262		}
263		bld.newBlock()
264	case *ast.SendStmt:
265		bld.maybePanic()
266		return bld
267
268	case *ast.BinaryExpr:
269		if n.Op == token.EQL || n.Op == token.QUO || n.Op == token.REM {
270			bld.maybePanic()
271		}
272		return bld
273	case *ast.CallExpr:
274		bld.maybePanic()
275		return bld
276	case *ast.IndexExpr:
277		bld.maybePanic()
278		return bld
279	case *ast.UnaryExpr:
280		id, ok := ident(n.X)
281		if ix, isIx := n.X.(*ast.IndexExpr); isIx {
282			// We don't care about indexing into slices, but without type information we can do no better.
283			id, ok = ident(ix.X)
284		}
285		if ok && n.Op == token.AND {
286			if v, ok := bld.vars[id.Obj]; ok {
287				v.escapes = true
288			}
289		}
290		return bld
291	case *ast.SelectorExpr:
292		bld.maybePanic()
293		// A method call (possibly delayed via a method value) might implicitly take
294		// the address of its receiver, causing it to escape.
295		// We can't do any better here without knowing the variable's type.
296		if id, ok := ident(n.X); ok {
297			if v, ok := bld.vars[id.Obj]; ok {
298				v.escapes = true
299			}
300		}
301		return bld
302	case *ast.SliceExpr:
303		bld.maybePanic()
304		// We don't care about slicing into slices, but without type information we can do no better.
305		if id, ok := ident(n.X); ok {
306			if v, ok := bld.vars[id.Obj]; ok {
307				v.escapes = true
308			}
309		}
310		return bld
311	case *ast.StarExpr:
312		bld.maybePanic()
313		return bld
314	case *ast.TypeAssertExpr:
315		bld.maybePanic()
316		return bld
317
318	default:
319		return bld
320	}
321	return nil
322}
323
324func isZeroInitializer(x ast.Expr) bool {
325	// Assume that a call expression of a single argument is a conversion expression.  We can't do better without type information.
326	if c, ok := x.(*ast.CallExpr); ok {
327		switch c.Fun.(type) {
328		case *ast.Ident, *ast.SelectorExpr:
329		default:
330			return false
331		}
332		if len(c.Args) != 1 {
333			return false
334		}
335		x = c.Args[0]
336	}
337
338	switch x := x.(type) {
339	case *ast.BasicLit:
340		switch x.Value {
341		case "0", "0.0", "0.", ".0", `""`:
342			return true
343		}
344	case *ast.Ident:
345		return x.Name == "false" && x.Obj == nil
346	}
347
348	return false
349}
350
351func (bld *builder) fun(typ *ast.FuncType, body *ast.BlockStmt) {
352	for _, v := range bld.vars {
353		v.fundept++
354	}
355	bld.results = append(bld.results, typ.Results)
356
357	b := bld.block
358	bld.newBlock()
359	bld.roots = append(bld.roots, bld.block)
360	bld.walk(typ)
361	bld.walk(body)
362	bld.block = b
363
364	bld.results = bld.results[:len(bld.results)-1]
365	for _, v := range bld.vars {
366		v.fundept--
367	}
368}
369
370func (bld *builder) swtch(stmt ast.Stmt, cases []ast.Stmt) {
371	brek := bld.breaks.push(bld.stmtLabel(stmt))
372	b0 := bld.block
373	list := b0
374	exits := make([]*block, 0, len(cases)+1)
375	var dfault, fallthru *block
376	for _, c := range cases {
377		c := c.(*ast.CaseClause)
378
379		if c.List != nil {
380			list = bld.newBlock(list)
381			for _, x := range c.List {
382				bld.walk(x)
383			}
384		}
385
386		parents := []*block{}
387		if c.List != nil {
388			parents = append(parents, list)
389		}
390		if fallthru != nil {
391			parents = append(parents, fallthru)
392			fallthru = nil
393		}
394		bld.newBlock(parents...)
395		if c.List == nil {
396			dfault = bld.block
397		}
398		for _, s := range c.Body {
399			bld.walk(s)
400			if s, ok := s.(*ast.BranchStmt); ok && s.Tok == token.FALLTHROUGH {
401				fallthru = bld.block
402			}
403		}
404
405		if fallthru == nil {
406			exits = append(exits, bld.block)
407		}
408	}
409	if dfault != nil {
410		list.addChild(dfault)
411	} else {
412		exits = append(exits, b0)
413	}
414	brek.setDestination(bld.newBlock(exits...))
415	bld.breaks.pop()
416}
417
418// An operation that might panic marks named function results as used.
419func (bld *builder) maybePanic() {
420	if len(bld.results) == 0 {
421		return
422	}
423	res := bld.results[len(bld.results)-1]
424	if res == nil {
425		return
426	}
427	for _, f := range res.List {
428		for _, id := range f.Names {
429			bld.use(id)
430		}
431	}
432}
433
434func (bld *builder) newBlock(parents ...*block) *block {
435	bld.block = &block{ops: map[*ast.Object][]operation{}}
436	for _, b := range parents {
437		b.addChild(bld.block)
438	}
439	return bld.block
440}
441
442func (bld *builder) stmtLabel(s ast.Stmt) *ast.Object {
443	if ls := bld.labelStmt; ls != nil && ls.Stmt == s {
444		return ls.Label.Obj
445	}
446	return nil
447}
448
449func (bld *builder) assign(id *ast.Ident) {
450	bld.newOp(id, true)
451}
452
453func (bld *builder) use(id *ast.Ident) {
454	bld.newOp(id, false)
455}
456
457func (bld *builder) newOp(id *ast.Ident, assign bool) {
458	if id.Name == "_" || id.Obj == nil {
459		return
460	}
461
462	v, ok := bld.vars[id.Obj]
463	if !ok {
464		v = &variable{}
465		bld.vars[id.Obj] = v
466	}
467	v.escapes = v.escapes || v.fundept > 0 || bld.block == nil
468
469	if b := bld.block; b != nil && !v.escapes {
470		b.ops[id.Obj] = append(b.ops[id.Obj], operation{id, assign})
471	}
472}
473
474type branchStack []*branch
475
476type branch struct {
477	label *ast.Object
478	srcs  []*block
479	dst   *block
480}
481
482func (s *branchStack) push(lbl *ast.Object) *branch {
483	br := &branch{label: lbl}
484	*s = append(*s, br)
485	return br
486}
487
488func (s *branchStack) get(lbl *ast.Ident) *branch {
489	for i := len(*s) - 1; i >= 0; i-- {
490		if br := (*s)[i]; lbl == nil || br.label == lbl.Obj {
491			return br
492		}
493	}
494
495	// Guard against invalid code (break/continue outside of loop).
496	if lbl == nil {
497		return &branch{}
498	}
499
500	return s.push(lbl.Obj)
501}
502
503func (br *branch) addSource(src *block) {
504	br.srcs = append(br.srcs, src)
505	if br.dst != nil {
506		src.addChild(br.dst)
507	}
508}
509
510func (br *branch) setDestination(dst *block) {
511	br.dst = dst
512	for _, src := range br.srcs {
513		src.addChild(dst)
514	}
515}
516
517func (s *branchStack) pop() {
518	*s = (*s)[:len(*s)-1]
519}
520
521func ident(x ast.Expr) (*ast.Ident, bool) {
522	if p, ok := x.(*ast.ParenExpr); ok {
523		return ident(p.X)
524	}
525	id, ok := x.(*ast.Ident)
526	return id, ok
527}
528
529type checker struct {
530	vars  map[*ast.Object]*variable
531	seen  map[*block]bool
532	ineff idents
533}
534
535func (chk *checker) check(b *block) {
536	if chk.seen[b] {
537		return
538	}
539	chk.seen[b] = true
540
541	for obj, ops := range b.ops {
542	ops:
543		for i, op := range ops {
544			if !op.assign {
545				continue
546			}
547			if i+1 < len(ops) {
548				if ops[i+1].assign {
549					chk.ineff = append(chk.ineff, op.id)
550				}
551				continue
552			}
553			seen := map[*block]bool{}
554			for _, b := range b.children {
555				if used(obj, b, seen) {
556					continue ops
557				}
558			}
559			if !chk.vars[obj].escapes {
560				chk.ineff = append(chk.ineff, op.id)
561			}
562		}
563	}
564
565	for _, b := range b.children {
566		chk.check(b)
567	}
568}
569
570func used(obj *ast.Object, b *block, seen map[*block]bool) bool {
571	if seen[b] {
572		return false
573	}
574	seen[b] = true
575
576	if ops := b.ops[obj]; len(ops) > 0 {
577		return !ops[0].assign
578	}
579	for _, b := range b.children {
580		if used(obj, b, seen) {
581			return true
582		}
583	}
584	return false
585}
586
587type idents []*ast.Ident
588
589func (ids idents) Len() int           { return len(ids) }
590func (ids idents) Less(i, j int) bool { return ids[i].Pos() < ids[j].Pos() }
591func (ids idents) Swap(i, j int)      { ids[i], ids[j] = ids[j], ids[i] }
592