Home | History | Annotate | Download | only in cfg 
      1 // Copyright 2016 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 cfg
      6 
      7 import (
      8 	"bytes"
      9 	"fmt"
     10 	"go/ast"
     11 	"go/parser"
     12 	"go/token"
     13 	"testing"
     14 )
     15 
     16 const src = `package main
     17 
     18 import "log"
     19 
     20 func f1() {
     21 	live()
     22 	return
     23 	dead()
     24 }
     25 
     26 func f2() {
     27 	for {
     28 		live()
     29 	}
     30 	dead()
     31 }
     32 
     33 func f3() {
     34 	if true { // even known values are ignored
     35 		return
     36 	}
     37 	for true { // even known values are ignored
     38 		live()
     39 	}
     40 	for {
     41 		live()
     42 	}
     43 	dead()
     44 }
     45 
     46 func f4(x int) {
     47 	switch x {
     48 	case 1:
     49 		live()
     50 		fallthrough
     51 	case 2:
     52 		live()
     53 		log.Fatal()
     54 	default:
     55 		panic("oops")
     56 	}
     57 	dead()
     58 }
     59 
     60 func f4(ch chan int) {
     61 	select {
     62 	case <-ch:
     63 		live()
     64 		return
     65 	default:
     66 		live()
     67 		panic("oops")
     68 	}
     69 	dead()
     70 }
     71 
     72 func f5(unknown bool) {
     73 	for {
     74 		if unknown {
     75 			break
     76 		}
     77 		continue
     78 		dead()
     79 	}
     80 	live()
     81 }
     82 
     83 func f6(unknown bool) {
     84 outer:
     85 	for {
     86 		for {
     87 			break outer
     88 			dead()
     89 		}
     90 		dead()
     91 	}
     92 	live()
     93 }
     94 
     95 func f7() {
     96 	for {
     97 		break nosuchlabel
     98 		dead()
     99 	}
    100 	dead()
    101 }
    102 
    103 func f8() {
    104 	select{}
    105 	dead()
    106 }
    107 
    108 func f9(ch chan int) {
    109 	select {
    110 	case <-ch:
    111 		return
    112 	}
    113 	dead()
    114 }
    115 
    116 func f10(ch chan int) {
    117 	select {
    118 	case <-ch:
    119 		return
    120 		dead()
    121 	default:
    122 	}
    123 	live()
    124 }
    125 
    126 func f11() {
    127 	goto; // mustn't crash
    128 	dead()
    129 }
    130 
    131 `
    132 
    133 func TestDeadCode(t *testing.T) {
    134 	// We'll use dead code detection to verify the CFG.
    135 
    136 	fset := token.NewFileSet()
    137 	f, err := parser.ParseFile(fset, "dummy.go", src, parser.Mode(0))
    138 	if err != nil {
    139 		t.Fatal(err)
    140 	}
    141 	for _, decl := range f.Decls {
    142 		if decl, ok := decl.(*ast.FuncDecl); ok {
    143 			g := New(decl.Body, mayReturn)
    144 
    145 			// Mark blocks reachable from entry.
    146 			live := make(map[*Block]bool)
    147 			var visit func(*Block)
    148 			visit = func(b *Block) {
    149 				if !live[b] {
    150 					live[b] = true
    151 					for _, succ := range b.Succs {
    152 						visit(succ)
    153 					}
    154 				}
    155 			}
    156 			visit(g.Blocks[0])
    157 
    158 			// Print statements in unreachable blocks
    159 			// (in order determined by builder).
    160 			var buf bytes.Buffer
    161 			for _, b := range g.Blocks {
    162 				if !live[b] {
    163 					for _, n := range b.Nodes {
    164 						fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n))
    165 					}
    166 				}
    167 			}
    168 
    169 			// Check that the result contains "dead" at least once but not "live".
    170 			if !bytes.Contains(buf.Bytes(), []byte("dead")) ||
    171 				bytes.Contains(buf.Bytes(), []byte("live")) {
    172 				t.Errorf("unexpected dead statements in function %s:\n%s",
    173 					decl.Name.Name,
    174 					&buf)
    175 				t.Logf("control flow graph:\n%s", g.Format(fset))
    176 			}
    177 		}
    178 	}
    179 }
    180 
    181 // A trivial mayReturn predicate that looks only at syntax, not types.
    182 func mayReturn(call *ast.CallExpr) bool {
    183 	switch fun := call.Fun.(type) {
    184 	case *ast.Ident:
    185 		return fun.Name != "panic"
    186 	case *ast.SelectorExpr:
    187 		return fun.Sel.Name != "Fatal"
    188 	}
    189 	return true
    190 }
    191