deadcode.go

Documentation: golang.org/x/tools/cmd/deadcode

     1  // Copyright 2023 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  //go:build go1.20
     6  
     7  package main
     8  
     9  import (
    10  	"bytes"
    11  	_ "embed"
    12  	"encoding/json"
    13  	"flag"
    14  	"fmt"
    15  	"go/ast"
    16  	"go/token"
    17  	"go/types"
    18  	"io"
    19  	"log"
    20  	"os"
    21  	"path/filepath"
    22  	"regexp"
    23  	"runtime"
    24  	"runtime/pprof"
    25  	"sort"
    26  	"strings"
    27  	"text/template"
    28  
    29  	"golang.org/x/telemetry"
    30  	"golang.org/x/tools/go/callgraph"
    31  	"golang.org/x/tools/go/callgraph/rta"
    32  	"golang.org/x/tools/go/packages"
    33  	"golang.org/x/tools/go/ssa"
    34  	"golang.org/x/tools/go/ssa/ssautil"
    35  	"golang.org/x/tools/internal/typesinternal"
    36  )
    37  
    38  //go:embed doc.go
    39  var doc string
    40  
    41  // flags
    42  var (
    43  	testFlag = flag.Bool("test", false, "include implicit test packages and executables")
    44  	tagsFlag = flag.String("tags", "", "comma-separated list of extra build tags (see: go help buildconstraint)")
    45  
    46  	filterFlag    = flag.String("filter", "<module>", "report only packages matching this regular expression (default: module of first package)")
    47  	generatedFlag = flag.Bool("generated", false, "include dead functions in generated Go files")
    48  	whyLiveFlag   = flag.String("whylive", "", "show a path from main to the named function")
    49  	formatFlag    = flag.String("f", "", "format output records using template")
    50  	jsonFlag      = flag.Bool("json", false, "output JSON records")
    51  	cpuProfile    = flag.String("cpuprofile", "", "write CPU profile to this file")
    52  	memProfile    = flag.String("memprofile", "", "write memory profile to this file")
    53  )
    54  
    55  func usage() {
    56  	// Extract the content of the /* ... */ comment in doc.go.
    57  	_, after, _ := strings.Cut(doc, "/*\n")
    58  	doc, _, _ := strings.Cut(after, "*/")
    59  	io.WriteString(flag.CommandLine.Output(), doc+`
    60  Flags:
    61  
    62  `)
    63  	flag.PrintDefaults()
    64  }
    65  
    66  func main() {
    67  	telemetry.Start(telemetry.Config{ReportCrashes: true})
    68  
    69  	log.SetPrefix("deadcode: ")
    70  	log.SetFlags(0) // no time prefix
    71  
    72  	flag.Usage = usage
    73  	flag.Parse()
    74  	if len(flag.Args()) == 0 {
    75  		usage()
    76  		os.Exit(2)
    77  	}
    78  
    79  	if *cpuProfile != "" {
    80  		f, err := os.Create(*cpuProfile)
    81  		if err != nil {
    82  			log.Fatal(err)
    83  		}
    84  		if err := pprof.StartCPUProfile(f); err != nil {
    85  			log.Fatal(err)
    86  		}
    87  		// NB: profile won't be written in case of error.
    88  		defer pprof.StopCPUProfile()
    89  	}
    90  
    91  	if *memProfile != "" {
    92  		f, err := os.Create(*memProfile)
    93  		if err != nil {
    94  			log.Fatal(err)
    95  		}
    96  		// NB: profile won't be written in case of error.
    97  		defer func() {
    98  			runtime.GC() // get up-to-date statistics
    99  			if err := pprof.WriteHeapProfile(f); err != nil {
   100  				log.Fatalf("Writing memory profile: %v", err)
   101  			}
   102  			f.Close()
   103  		}()
   104  	}
   105  
   106  	// Reject bad output options early.
   107  	if *formatFlag != "" {
   108  		if *jsonFlag {
   109  			log.Fatalf("you cannot specify both -f=template and -json")
   110  		}
   111  		if _, err := template.New("deadcode").Parse(*formatFlag); err != nil {
   112  			log.Fatalf("invalid -f: %v", err)
   113  		}
   114  	}
   115  
   116  	// Load, parse, and type-check the complete program(s).
   117  	cfg := &packages.Config{
   118  		BuildFlags: []string{"-tags=" + *tagsFlag},
   119  		Mode:       packages.LoadAllSyntax | packages.NeedModule,
   120  		Tests:      *testFlag,
   121  	}
   122  	initial, err := packages.Load(cfg, flag.Args()...)
   123  	if err != nil {
   124  		log.Fatalf("Load: %v", err)
   125  	}
   126  	if len(initial) == 0 {
   127  		log.Fatalf("no packages")
   128  	}
   129  	if packages.PrintErrors(initial) > 0 {
   130  		log.Fatalf("packages contain errors")
   131  	}
   132  
   133  	// If -filter is unset, use first module (if available).
   134  	if *filterFlag == "<module>" {
   135  		if mod := initial[0].Module; mod != nil && mod.Path != "" {
   136  			*filterFlag = "^" + regexp.QuoteMeta(mod.Path) + "\\b"
   137  		} else {
   138  			*filterFlag = "" // match any
   139  		}
   140  	}
   141  	filter, err := regexp.Compile(*filterFlag)
   142  	if err != nil {
   143  		log.Fatalf("-filter: %v", err)
   144  	}
   145  
   146  	// Create SSA-form program representation
   147  	// and find main packages.
   148  	prog, pkgs := ssautil.AllPackages(initial, ssa.InstantiateGenerics)
   149  	prog.Build()
   150  
   151  	mains := ssautil.MainPackages(pkgs)
   152  	if len(mains) == 0 {
   153  		log.Fatalf("no main packages")
   154  	}
   155  	var roots []*ssa.Function
   156  	for _, main := range mains {
   157  		roots = append(roots, main.Func("init"), main.Func("main"))
   158  	}
   159  
   160  	// Gather all source-level functions,
   161  	// as the user interface is expressed in terms of them.
   162  	//
   163  	// We ignore synthetic wrappers, and nested functions. Literal
   164  	// functions passed as arguments to other functions are of
   165  	// course address-taken and there exists a dynamic call of
   166  	// that signature, so when they are unreachable, it is
   167  	// invariably because the parent is unreachable.
   168  	var sourceFuncs []*ssa.Function
   169  	generated := make(map[string]bool)
   170  	packages.Visit(initial, nil, func(p *packages.Package) {
   171  		for _, file := range p.Syntax {
   172  			for _, decl := range file.Decls {
   173  				if decl, ok := decl.(*ast.FuncDecl); ok {
   174  					obj := p.TypesInfo.Defs[decl.Name].(*types.Func)
   175  					fn := prog.FuncValue(obj)
   176  					sourceFuncs = append(sourceFuncs, fn)
   177  				}
   178  			}
   179  
   180  			if isGenerated(file) {
   181  				generated[p.Fset.File(file.Pos()).Name()] = true
   182  			}
   183  		}
   184  	})
   185  
   186  	// Compute the reachabilty from main.
   187  	// (Build a call graph only for -whylive.)
   188  	res := rta.Analyze(roots, *whyLiveFlag != "")
   189  
   190  	// Subtle: the -test flag causes us to analyze test variants
   191  	// such as "package p as compiled for p.test" or even "for q.test".
   192  	// This leads to multiple distinct ssa.Function instances that
   193  	// represent the same source declaration, and it is essentially
   194  	// impossible to discover this from the SSA representation
   195  	// (since it has lost the connection to go/packages.Package.ID).
   196  	//
   197  	// So, we de-duplicate such variants by position:
   198  	// if any one of them is live, we consider all of them live.
   199  	// (We use Position not Pos to avoid assuming that files common
   200  	// to packages "p" and "p [p.test]" were parsed only once.)
   201  	reachablePosn := make(map[token.Position]bool)
   202  	for fn := range res.Reachable {
   203  		if fn.Pos().IsValid() || fn.Name() == "init" {
   204  			reachablePosn[prog.Fset.Position(fn.Pos())] = true
   205  		}
   206  	}
   207  
   208  	// The -whylive=fn flag causes deadcode to explain why a function
   209  	// is not dead, by showing a path to it from some root.
   210  	if *whyLiveFlag != "" {
   211  		targets := make(map[*ssa.Function]bool)
   212  		for _, fn := range sourceFuncs {
   213  			if prettyName(fn, true) == *whyLiveFlag {
   214  				targets[fn] = true
   215  			}
   216  		}
   217  		if len(targets) == 0 {
   218  			// Function is not part of the program.
   219  			//
   220  			// TODO(adonovan): improve the UX here in case
   221  			// of spelling or syntax mistakes. Some ideas:
   222  			// - a cmd/callgraph command to enumerate
   223  			//   available functions.
   224  			// - a deadcode -live flag to compute the complement.
   225  			// - a syntax hint: example.com/pkg.Func or (example.com/pkg.Type).Method
   226  			// - report the element of AllFunctions with the smallest
   227  			//   Levenshtein distance from *whyLiveFlag.
   228  			// - permit -whylive=regexp. But beware of spurious
   229  			//   matches (e.g. fmt.Print matches fmt.Println)
   230  			//   and the annoyance of having to quote parens (*T).f.
   231  			log.Fatalf("function %q not found in program", *whyLiveFlag)
   232  		}
   233  
   234  		// Opt: remove the unreachable ones.
   235  		for fn := range targets {
   236  			if !reachablePosn[prog.Fset.Position(fn.Pos())] {
   237  				delete(targets, fn)
   238  			}
   239  		}
   240  		if len(targets) == 0 {
   241  			log.Fatalf("function %s is dead code", *whyLiveFlag)
   242  		}
   243  
   244  		res.CallGraph.DeleteSyntheticNodes() // inline synthetic wrappers (except inits)
   245  		root, path := pathSearch(roots, res, targets)
   246  		if root == nil {
   247  			// RTA doesn't add callgraph edges for reflective calls.
   248  			log.Fatalf("%s is reachable only through reflection", *whyLiveFlag)
   249  		}
   250  		if len(path) == 0 {
   251  			// No edges => one of the targets is a root.
   252  			// Rather than (confusingly) print nothing, make this an error.
   253  			log.Fatalf("%s is a root", root.Func)
   254  		}
   255  
   256  		// Build a list of jsonEdge records
   257  		// to print as -json or -f=template.
   258  		var edges []any
   259  		for _, edge := range path {
   260  			edges = append(edges, jsonEdge{
   261  				Initial:  cond(len(edges) == 0, prettyName(edge.Caller.Func, true), ""),
   262  				Kind:     cond(isStaticCall(edge), "static", "dynamic"),
   263  				Position: toJSONPosition(prog.Fset.Position(edge.Site.Pos())),
   264  				Callee:   prettyName(edge.Callee.Func, true),
   265  			})
   266  		}
   267  		format := `{{if .Initial}}{{printf "%19s%s\n" "" .Initial}}{{end}}{{printf "%8s@L%.4d --> %s" .Kind .Position.Line .Callee}}`
   268  		if *formatFlag != "" {
   269  			format = *formatFlag
   270  		}
   271  		printObjects(format, edges)
   272  		return
   273  	}
   274  
   275  	// Group unreachable functions by package path.
   276  	byPkgPath := make(map[string]map[*ssa.Function]bool)
   277  	for _, fn := range sourceFuncs {
   278  		posn := prog.Fset.Position(fn.Pos())
   279  
   280  		if !reachablePosn[posn] {
   281  			reachablePosn[posn] = true // suppress dups with same pos
   282  
   283  			pkgpath := fn.Pkg.Pkg.Path()
   284  			m, ok := byPkgPath[pkgpath]
   285  			if !ok {
   286  				m = make(map[*ssa.Function]bool)
   287  				byPkgPath[pkgpath] = m
   288  			}
   289  			m[fn] = true
   290  		}
   291  	}
   292  
   293  	// Build array of jsonPackage objects.
   294  	var packages []any
   295  	pkgpaths := keys(byPkgPath)
   296  	sort.Strings(pkgpaths)
   297  	for _, pkgpath := range pkgpaths {
   298  		if !filter.MatchString(pkgpath) {
   299  			continue
   300  		}
   301  
   302  		m := byPkgPath[pkgpath]
   303  
   304  		// Print functions that appear within the same file in
   305  		// declaration order. This tends to keep related
   306  		// methods such as (T).Marshal and (*T).Unmarshal
   307  		// together better than sorting.
   308  		fns := keys(m)
   309  		sort.Slice(fns, func(i, j int) bool {
   310  			xposn := prog.Fset.Position(fns[i].Pos())
   311  			yposn := prog.Fset.Position(fns[j].Pos())
   312  			if xposn.Filename != yposn.Filename {
   313  				return xposn.Filename < yposn.Filename
   314  			}
   315  			return xposn.Line < yposn.Line
   316  		})
   317  
   318  		var functions []jsonFunction
   319  		for _, fn := range fns {
   320  			posn := prog.Fset.Position(fn.Pos())
   321  
   322  			// Without -generated, skip functions declared in
   323  			// generated Go files.
   324  			// (Functions called by them may still be reported.)
   325  			gen := generated[posn.Filename]
   326  			if gen && !*generatedFlag {
   327  				continue
   328  			}
   329  
   330  			functions = append(functions, jsonFunction{
   331  				Name:      prettyName(fn, false),
   332  				Position:  toJSONPosition(posn),
   333  				Generated: gen,
   334  			})
   335  		}
   336  		if len(functions) > 0 {
   337  			packages = append(packages, jsonPackage{
   338  				Name:  fns[0].Pkg.Pkg.Name(),
   339  				Path:  pkgpath,
   340  				Funcs: functions,
   341  			})
   342  		}
   343  	}
   344  
   345  	// Default line-oriented format: "a/b/c.go:1:2: unreachable func: T.f"
   346  	format := `{{range .Funcs}}{{printf "%s: unreachable func: %s\n" .Position .Name}}{{end}}`
   347  	if *formatFlag != "" {
   348  		format = *formatFlag
   349  	}
   350  	printObjects(format, packages)
   351  }
   352  
   353  // prettyName is a fork of Function.String designed to reduce
   354  // go/ssa's fussy punctuation symbols, e.g. "(*pkg.T).F" -> "pkg.T.F".
   355  //
   356  // It only works for functions that remain after
   357  // callgraph.Graph.DeleteSyntheticNodes: source-level named functions
   358  // and methods, their anonymous functions, and synthetic package
   359  // initializers.
   360  func prettyName(fn *ssa.Function, qualified bool) string {
   361  	var buf strings.Builder
   362  
   363  	// optional package qualifier
   364  	if qualified && fn.Pkg != nil {
   365  		fmt.Fprintf(&buf, "%s.", fn.Pkg.Pkg.Path())
   366  	}
   367  
   368  	var format func(*ssa.Function)
   369  	format = func(fn *ssa.Function) {
   370  		// anonymous?
   371  		if fn.Parent() != nil {
   372  			format(fn.Parent())
   373  			i := index(fn.Parent().AnonFuncs, fn)
   374  			fmt.Fprintf(&buf, "$%d", i+1)
   375  			return
   376  		}
   377  
   378  		// method receiver?
   379  		if recv := fn.Signature.Recv(); recv != nil {
   380  			_, named := typesinternal.ReceiverNamed(recv)
   381  			buf.WriteString(named.Obj().Name())
   382  			buf.WriteByte('.')
   383  		}
   384  
   385  		// function/method name
   386  		buf.WriteString(fn.Name())
   387  	}
   388  	format(fn)
   389  
   390  	return buf.String()
   391  }
   392  
   393  // printObjects formats an array of objects, either as JSON or using a
   394  // template, following the manner of 'go list (-json|-f=template)'.
   395  func printObjects(format string, objects []any) {
   396  	if *jsonFlag {
   397  		out, err := json.MarshalIndent(objects, "", "\t")
   398  		if err != nil {
   399  			log.Fatalf("internal error: %v", err)
   400  		}
   401  		os.Stdout.Write(out)
   402  		return
   403  	}
   404  
   405  	// -f=template. Parse can't fail: we checked it earlier.
   406  	tmpl := template.Must(template.New("deadcode").Parse(format))
   407  	for _, object := range objects {
   408  		var buf bytes.Buffer
   409  		if err := tmpl.Execute(&buf, object); err != nil {
   410  			log.Fatal(err)
   411  		}
   412  		if n := buf.Len(); n == 0 || buf.Bytes()[n-1] != '\n' {
   413  			buf.WriteByte('\n')
   414  		}
   415  		os.Stdout.Write(buf.Bytes())
   416  	}
   417  }
   418  
   419  // TODO(adonovan): use go1.21's ast.IsGenerated.
   420  
   421  // isGenerated reports whether the file was generated by a program,
   422  // not handwritten, by detecting the special comment described
   423  // at https://go.dev/s/generatedcode.
   424  //
   425  // The syntax tree must have been parsed with the ParseComments flag.
   426  // Example:
   427  //
   428  //	f, err := parser.ParseFile(fset, filename, src, parser.ParseComments|parser.PackageClauseOnly)
   429  //	if err != nil { ... }
   430  //	gen := ast.IsGenerated(f)
   431  func isGenerated(file *ast.File) bool {
   432  	_, ok := generator(file)
   433  	return ok
   434  }
   435  
   436  func generator(file *ast.File) (string, bool) {
   437  	for _, group := range file.Comments {
   438  		for _, comment := range group.List {
   439  			if comment.Pos() > file.Package {
   440  				break // after package declaration
   441  			}
   442  			// opt: check Contains first to avoid unnecessary array allocation in Split.
   443  			const prefix = "// Code generated "
   444  			if strings.Contains(comment.Text, prefix) {
   445  				for _, line := range strings.Split(comment.Text, "\n") {
   446  					if rest, ok := strings.CutPrefix(line, prefix); ok {
   447  						if gen, ok := strings.CutSuffix(rest, " DO NOT EDIT."); ok {
   448  							return gen, true
   449  						}
   450  					}
   451  				}
   452  			}
   453  		}
   454  	}
   455  	return "", false
   456  }
   457  
   458  // pathSearch returns the shortest path from one of the roots to one
   459  // of the targets (along with the root itself), or zero if no path was found.
   460  func pathSearch(roots []*ssa.Function, res *rta.Result, targets map[*ssa.Function]bool) (*callgraph.Node, []*callgraph.Edge) {
   461  	// Search breadth-first (for shortest path) from the root.
   462  	//
   463  	// We don't use the virtual CallGraph.Root node as we wish to
   464  	// choose the order in which we search entrypoints:
   465  	// non-test packages before test packages,
   466  	// main functions before init functions.
   467  
   468  	// Sort roots into preferred order.
   469  	importsTesting := func(fn *ssa.Function) bool {
   470  		isTesting := func(p *types.Package) bool { return p.Path() == "testing" }
   471  		return containsFunc(fn.Pkg.Pkg.Imports(), isTesting)
   472  	}
   473  	sort.Slice(roots, func(i, j int) bool {
   474  		x, y := roots[i], roots[j]
   475  		xtest := importsTesting(x)
   476  		ytest := importsTesting(y)
   477  		if xtest != ytest {
   478  			return !xtest // non-tests before tests
   479  		}
   480  		xinit := x.Name() == "init"
   481  		yinit := y.Name() == "init"
   482  		if xinit != yinit {
   483  			return !xinit // mains before inits
   484  		}
   485  		return false
   486  	})
   487  
   488  	search := func(allowDynamic bool) (*callgraph.Node, []*callgraph.Edge) {
   489  		// seen maps each encountered node to its predecessor on the
   490  		// path to a root node, or to nil for root itself.
   491  		seen := make(map[*callgraph.Node]*callgraph.Edge)
   492  		bfs := func(root *callgraph.Node) []*callgraph.Edge {
   493  			queue := []*callgraph.Node{root}
   494  			seen[root] = nil
   495  			for len(queue) > 0 {
   496  				node := queue[0]
   497  				queue = queue[1:]
   498  
   499  				// found a path?
   500  				if targets[node.Func] {
   501  					path := []*callgraph.Edge{} // non-nil in case len(path)=0
   502  					for {
   503  						edge := seen[node]
   504  						if edge == nil {
   505  							reverse(path)
   506  							return path
   507  						}
   508  						path = append(path, edge)
   509  						node = edge.Caller
   510  					}
   511  				}
   512  
   513  				for _, edge := range node.Out {
   514  					if allowDynamic || isStaticCall(edge) {
   515  						if _, ok := seen[edge.Callee]; !ok {
   516  							seen[edge.Callee] = edge
   517  							queue = append(queue, edge.Callee)
   518  						}
   519  					}
   520  				}
   521  			}
   522  			return nil
   523  		}
   524  		for _, rootFn := range roots {
   525  			root := res.CallGraph.Nodes[rootFn]
   526  			if root == nil {
   527  				// Missing call graph node for root.
   528  				// TODO(adonovan): seems like a bug in rta.
   529  				continue
   530  			}
   531  			if path := bfs(root); path != nil {
   532  				return root, path
   533  			}
   534  		}
   535  		return nil, nil
   536  	}
   537  
   538  	for _, allowDynamic := range []bool{false, true} {
   539  		if root, path := search(allowDynamic); path != nil {
   540  			return root, path
   541  		}
   542  	}
   543  
   544  	return nil, nil
   545  }
   546  
   547  // -- utilities --
   548  
   549  func isStaticCall(edge *callgraph.Edge) bool {
   550  	return edge.Site != nil && edge.Site.Common().StaticCallee() != nil
   551  }
   552  
   553  var cwd, _ = os.Getwd()
   554  
   555  func toJSONPosition(posn token.Position) jsonPosition {
   556  	// Use cwd-relative filename if possible.
   557  	filename := posn.Filename
   558  	if rel, err := filepath.Rel(cwd, filename); err == nil && !strings.HasPrefix(rel, "..") {
   559  		filename = rel
   560  	}
   561  
   562  	return jsonPosition{filename, posn.Line, posn.Column}
   563  }
   564  
   565  func cond[T any](cond bool, t, f T) T {
   566  	if cond {
   567  		return t
   568  	} else {
   569  		return f
   570  	}
   571  }
   572  
   573  // -- output protocol (for JSON or text/template) --
   574  
   575  // Keep in sync with doc comment!
   576  
   577  type jsonFunction struct {
   578  	Name      string       // name (sans package qualifier)
   579  	Position  jsonPosition // file/line/column of declaration
   580  	Generated bool         // function is declared in a generated .go file
   581  }
   582  
   583  func (f jsonFunction) String() string { return f.Name }
   584  
   585  type jsonPackage struct {
   586  	Name  string         // declared name
   587  	Path  string         // full import path
   588  	Funcs []jsonFunction // non-empty list of package's dead functions
   589  }
   590  
   591  func (p jsonPackage) String() string { return p.Path }
   592  
   593  // The Initial and Callee names are package-qualified.
   594  type jsonEdge struct {
   595  	Initial  string `json:",omitempty"` // initial entrypoint (main or init); first edge only
   596  	Kind     string // = static | dynamic
   597  	Position jsonPosition
   598  	Callee   string
   599  }
   600  
   601  type jsonPosition struct {
   602  	File      string
   603  	Line, Col int
   604  }
   605  
   606  func (p jsonPosition) String() string {
   607  	return fmt.Sprintf("%s:%d:%d", p.File, p.Line, p.Col)
   608  }
   609  
   610  // -- from the future --
   611  
   612  // TODO(adonovan): use go1.22's slices and maps packages.
   613  
   614  func containsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
   615  	return indexFunc(s, f) >= 0
   616  }
   617  
   618  func indexFunc[S ~[]E, E any](s S, f func(E) bool) int {
   619  	for i := range s {
   620  		if f(s[i]) {
   621  			return i
   622  		}
   623  	}
   624  	return -1
   625  }
   626  
   627  func index[S ~[]E, E comparable](s S, v E) int {
   628  	for i := range s {
   629  		if v == s[i] {
   630  			return i
   631  		}
   632  	}
   633  	return -1
   634  }
   635  
   636  func reverse[S ~[]E, E any](s S) {
   637  	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
   638  		s[i], s[j] = s[j], s[i]
   639  	}
   640  }
   641  
   642  func keys[M ~map[K]V, K comparable, V any](m M) []K {
   643  	r := make([]K, 0, len(m))
   644  	for k := range m {
   645  		r = append(r, k)
   646  	}
   647  	return r
   648  }
   649
View as plain text