cmd/deadcode/deadcode.go - tools - Git at Google

 // Copyright 2023 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 //go:build go1.20

 package main

 import (
 	"bytes"
 	_ "embed"
 	"encoding/json"
 	"flag"
 	"fmt"
 	"go/ast"
 	"go/token"
 	"go/types"
 	"io"
 	"log"
 	"os"
 	"path/filepath"
 	"regexp"
 	"runtime"
 	"runtime/pprof"
 	"sort"
 	"strings"
 	"text/template"

 	"golang.org/x/telemetry"
 	"golang.org/x/tools/go/callgraph"
 	"golang.org/x/tools/go/callgraph/rta"
 	"golang.org/x/tools/go/packages"
 	"golang.org/x/tools/go/ssa"
 	"golang.org/x/tools/go/ssa/ssautil"
 	"golang.org/x/tools/internal/typesinternal"
 )

 //go:embed doc.go
 var doc string

 // flags
 var (
 	testFlag = flag.Bool("test", false, "include implicit test packages and executables")
 	tagsFlag = flag.String("tags", "", "comma-separated list of extra build tags (see: go help buildconstraint)")

 	filterFlag    = flag.String("filter", "<module>", "report only packages matching this regular expression (default: module of first package)")
 	generatedFlag = flag.Bool("generated", false, "include dead functions in generated Go files")
 	whyLiveFlag   = flag.String("whylive", "", "show a path from main to the named function")
 	formatFlag    = flag.String("f", "", "format output records using template")
 	jsonFlag      = flag.Bool("json", false, "output JSON records")
 	cpuProfile    = flag.String("cpuprofile", "", "write CPU profile to this file")
 	memProfile    = flag.String("memprofile", "", "write memory profile to this file")
 )

 func usage() {
 	// Extract the content of the /* ... */ comment in doc.go.
 	_, after, _ := strings.Cut(doc, "/*\n")
 	doc, _, _ := strings.Cut(after, "*/")
 	io.WriteString(flag.CommandLine.Output(), doc+`
 Flags:

 `)
 	flag.PrintDefaults()
 }

 func main() {
 	telemetry.Start(telemetry.Config{ReportCrashes: true})

 	log.SetPrefix("deadcode: ")
 	log.SetFlags(0) // no time prefix

 	flag.Usage = usage
 	flag.Parse()
 	if len(flag.Args()) == 0 {
 		usage()
 		os.Exit(2)
 	}

 	if *cpuProfile != "" {
 		f, err := os.Create(*cpuProfile)
 		if err != nil {
 			log.Fatal(err)
 		}
 		if err := pprof.StartCPUProfile(f); err != nil {
 			log.Fatal(err)
 		}
 		// NB: profile won't be written in case of error.
 		defer pprof.StopCPUProfile()
 	}

 	if *memProfile != "" {
 		f, err := os.Create(*memProfile)
 		if err != nil {
 			log.Fatal(err)
 		}
 		// NB: profile won't be written in case of error.
 		defer func() {
 			runtime.GC() // get up-to-date statistics
 			if err := pprof.WriteHeapProfile(f); err != nil {
 				log.Fatalf("Writing memory profile: %v", err)
 			}
 			f.Close()
 		}()
 	}

 	// Reject bad output options early.
 	if *formatFlag != "" {
 		if *jsonFlag {
 			log.Fatalf("you cannot specify both -f=template and -json")
 		}
 		if _, err := template.New("deadcode").Parse(*formatFlag); err != nil {
 			log.Fatalf("invalid -f: %v", err)
 		}
 	}

 	// Load, parse, and type-check the complete program(s).
 	cfg := &packages.Config{
 		BuildFlags: []string{"-tags=" + *tagsFlag},
 		Mode:       packages.LoadAllSyntax | packages.NeedModule,
 		Tests:      *testFlag,
 	}
 	initial, err := packages.Load(cfg, flag.Args()...)
 	if err != nil {
 		log.Fatalf("Load: %v", err)
 	}
 	if len(initial) == 0 {
 		log.Fatalf("no packages")
 	}
 	if packages.PrintErrors(initial) > 0 {
 		log.Fatalf("packages contain errors")
 	}

 	// If -filter is unset, use first module (if available).
 	if *filterFlag == "<module>" {
 		if mod := initial[0].Module; mod != nil && mod.Path != "" {
 			*filterFlag = "^" + regexp.QuoteMeta(mod.Path) + "\\b"
 		} else {
 			*filterFlag = "" // match any
 		}
 	}
 	filter, err := regexp.Compile(*filterFlag)
 	if err != nil {
 		log.Fatalf("-filter: %v", err)
 	}

 	// Create SSA-form program representation
 	// and find main packages.
 	prog, pkgs := ssautil.AllPackages(initial, ssa.InstantiateGenerics)
 	prog.Build()

 	mains := ssautil.MainPackages(pkgs)
 	if len(mains) == 0 {
 		log.Fatalf("no main packages")
 	}
 	var roots []*ssa.Function
 	for _, main := range mains {
 		roots = append(roots, main.Func("init"), main.Func("main"))
 	}

 	// Gather all source-level functions,
 	// as the user interface is expressed in terms of them.
 	//
 	// We ignore synthetic wrappers, and nested functions. Literal
 	// functions passed as arguments to other functions are of
 	// course address-taken and there exists a dynamic call of
 	// that signature, so when they are unreachable, it is
 	// invariably because the parent is unreachable.
 	var sourceFuncs []*ssa.Function
 	generated := make(map[string]bool)
 	packages.Visit(initial, nil, func(p *packages.Package) {
 		for _, file := range p.Syntax {
 			for _, decl := range file.Decls {
 				if decl, ok := decl.(*ast.FuncDecl); ok {
 					obj := p.TypesInfo.Defs[decl.Name].(*types.Func)
 					fn := prog.FuncValue(obj)
 					sourceFuncs = append(sourceFuncs, fn)
 				}
 			}

 			if isGenerated(file) {
 				generated[p.Fset.File(file.Pos()).Name()] = true
 			}
 		}
 	})

 	// Compute the reachabilty from main.
 	// (Build a call graph only for -whylive.)
 	res := rta.Analyze(roots, *whyLiveFlag != "")

 	// Subtle: the -test flag causes us to analyze test variants
 	// such as "package p as compiled for p.test" or even "for q.test".
 	// This leads to multiple distinct ssa.Function instances that
 	// represent the same source declaration, and it is essentially
 	// impossible to discover this from the SSA representation
 	// (since it has lost the connection to go/packages.Package.ID).
 	//
 	// So, we de-duplicate such variants by position:
 	// if any one of them is live, we consider all of them live.
 	// (We use Position not Pos to avoid assuming that files common
 	// to packages "p" and "p [p.test]" were parsed only once.)
 	reachablePosn := make(map[token.Position]bool)
 	for fn := range res.Reachable {
 		if fn.Pos().IsValid() || fn.Name() == "init" {
 			reachablePosn[prog.Fset.Position(fn.Pos())] = true
 		}
 	}

 	// The -whylive=fn flag causes deadcode to explain why a function
 	// is not dead, by showing a path to it from some root.
 	if *whyLiveFlag != "" {
 		targets := make(map[*ssa.Function]bool)
 		for _, fn := range sourceFuncs {
 			if prettyName(fn, true) == *whyLiveFlag {
 				targets[fn] = true
 			}
 		}
 		if len(targets) == 0 {
 			// Function is not part of the program.
 			//
 			// TODO(adonovan): improve the UX here in case
 			// of spelling or syntax mistakes. Some ideas:
 			// - a cmd/callgraph command to enumerate
 			//   available functions.
 			// - a deadcode -live flag to compute the complement.
 			// - a syntax hint: example.com/pkg.Func or (example.com/pkg.Type).Method
 			// - report the element of AllFunctions with the smallest
 			//   Levenshtein distance from *whyLiveFlag.
 			// - permit -whylive=regexp. But beware of spurious
 			//   matches (e.g. fmt.Print matches fmt.Println)
 			//   and the annoyance of having to quote parens (*T).f.
 			log.Fatalf("function %q not found in program", *whyLiveFlag)
 		}

 		// Opt: remove the unreachable ones.
 		for fn := range targets {
 			if !reachablePosn[prog.Fset.Position(fn.Pos())] {
 				delete(targets, fn)
 			}
 		}
 		if len(targets) == 0 {
 			log.Fatalf("function %s is dead code", *whyLiveFlag)
 		}

 		res.CallGraph.DeleteSyntheticNodes() // inline synthetic wrappers (except inits)
 		root, path := pathSearch(roots, res, targets)
 		if root == nil {
 			// RTA doesn't add callgraph edges for reflective calls.
 			log.Fatalf("%s is reachable only through reflection", *whyLiveFlag)
 		}
 		if len(path) == 0 {
 			// No edges => one of the targets is a root.
 			// Rather than (confusingly) print nothing, make this an error.
 			log.Fatalf("%s is a root", root.Func)
 		}

 		// Build a list of jsonEdge records
 		// to print as -json or -f=template.
 		var edges []any
 		for _, edge := range path {
 			edges = append(edges, jsonEdge{
 				Initial:  cond(len(edges) == 0, prettyName(edge.Caller.Func, true), ""),
 				Kind:     cond(isStaticCall(edge), "static", "dynamic"),
 				Position: toJSONPosition(prog.Fset.Position(edge.Site.Pos())),
 				Callee:   prettyName(edge.Callee.Func, true),
 			})
 		}
 		format := `{{if .Initial}}{{printf "%19s%s\n" "" .Initial}}{{end}}{{printf "%8s@L%.4d --> %s" .Kind .Position.Line .Callee}}`
 		if *formatFlag != "" {
 			format = *formatFlag
 		}
 		printObjects(format, edges)
 		return
 	}

 	// Group unreachable functions by package path.
 	byPkgPath := make(map[string]map[*ssa.Function]bool)
 	for _, fn := range sourceFuncs {
 		posn := prog.Fset.Position(fn.Pos())

 		if !reachablePosn[posn] {
 			reachablePosn[posn] = true // suppress dups with same pos

 			pkgpath := fn.Pkg.Pkg.Path()
 			m, ok := byPkgPath[pkgpath]
 			if !ok {
 				m = make(map[*ssa.Function]bool)
 				byPkgPath[pkgpath] = m
 			}
 			m[fn] = true
 		}
 	}

 	// Build array of jsonPackage objects.
 	var packages []any
 	pkgpaths := keys(byPkgPath)
 	sort.Strings(pkgpaths)
 	for _, pkgpath := range pkgpaths {
 		if !filter.MatchString(pkgpath) {
 			continue
 		}

 		m := byPkgPath[pkgpath]

 		// Print functions that appear within the same file in
 		// declaration order. This tends to keep related
 		// methods such as (T).Marshal and (*T).Unmarshal
 		// together better than sorting.
 		fns := keys(m)
 		sort.Slice(fns, func(i, j int) bool {
 			xposn := prog.Fset.Position(fns[i].Pos())
 			yposn := prog.Fset.Position(fns[j].Pos())
 			if xposn.Filename != yposn.Filename {
 				return xposn.Filename < yposn.Filename
 			}
 			return xposn.Line < yposn.Line
 		})

 		var functions []jsonFunction
 		for _, fn := range fns {
 			posn := prog.Fset.Position(fn.Pos())

 			// Without -generated, skip functions declared in
 			// generated Go files.
 			// (Functions called by them may still be reported.)
 			gen := generated[posn.Filename]
 			if gen && !*generatedFlag {
 				continue
 			}

 			functions = append(functions, jsonFunction{
 				Name:      prettyName(fn, false),
 				Position:  toJSONPosition(posn),
 				Generated: gen,
 			})
 		}
 		if len(functions) > 0 {
 			packages = append(packages, jsonPackage{
 				Name:  fns[0].Pkg.Pkg.Name(),
 				Path:  pkgpath,
 				Funcs: functions,
 			})
 		}
 	}

 	// Default line-oriented format: "a/b/c.go:1:2: unreachable func: T.f"
 	format := `{{range .Funcs}}{{printf "%s: unreachable func: %s\n" .Position .Name}}{{end}}`
 	if *formatFlag != "" {
 		format = *formatFlag
 	}
 	printObjects(format, packages)
 }

 // prettyName is a fork of Function.String designed to reduce
 // go/ssa's fussy punctuation symbols, e.g. "(*pkg.T).F" -> "pkg.T.F".
 //
 // It only works for functions that remain after
 // callgraph.Graph.DeleteSyntheticNodes: source-level named functions
 // and methods, their anonymous functions, and synthetic package
 // initializers.
 func prettyName(fn *ssa.Function, qualified bool) string {
 	var buf strings.Builder

 	// optional package qualifier
 	if qualified && fn.Pkg != nil {
 		fmt.Fprintf(&buf, "%s.", fn.Pkg.Pkg.Path())
 	}

 	var format func(*ssa.Function)
 	format = func(fn *ssa.Function) {
 		// anonymous?
 		if fn.Parent() != nil {
 			format(fn.Parent())
 			i := index(fn.Parent().AnonFuncs, fn)
 			fmt.Fprintf(&buf, "$%d", i+1)
 			return
 		}

 		// method receiver?
 		if recv := fn.Signature.Recv(); recv != nil {
 			_, named := typesinternal.ReceiverNamed(recv)
 			buf.WriteString(named.Obj().Name())
 			buf.WriteByte('.')
 		}

 		// function/method name
 		buf.WriteString(fn.Name())
 	}
 	format(fn)

 	return buf.String()
 }

 // printObjects formats an array of objects, either as JSON or using a
 // template, following the manner of 'go list (-json|-f=template)'.
 func printObjects(format string, objects []any) {
 	if *jsonFlag {
 		out, err := json.MarshalIndent(objects, "", "\t")
 		if err != nil {
 			log.Fatalf("internal error: %v", err)
 		}
 		os.Stdout.Write(out)
 		return
 	}

 	// -f=template. Parse can't fail: we checked it earlier.
 	tmpl := template.Must(template.New("deadcode").Parse(format))
 	for _, object := range objects {
 		var buf bytes.Buffer
 		if err := tmpl.Execute(&buf, object); err != nil {
 			log.Fatal(err)
 		}
 		if n := buf.Len(); n == 0 || buf.Bytes()[n-1] != '\n' {
 			buf.WriteByte('\n')
 		}
 		os.Stdout.Write(buf.Bytes())
 	}
 }

 // TODO(adonovan): use go1.21's ast.IsGenerated.

 // isGenerated reports whether the file was generated by a program,
 // not handwritten, by detecting the special comment described
 // at https://go.dev/s/generatedcode.
 //
 // The syntax tree must have been parsed with the ParseComments flag.
 // Example:
 //
 //	f, err := parser.ParseFile(fset, filename, src, parser.ParseComments|parser.PackageClauseOnly)
 //	if err != nil { ... }
 //	gen := ast.IsGenerated(f)
 func isGenerated(file *ast.File) bool {
 	_, ok := generator(file)
 	return ok
 }

 func generator(file *ast.File) (string, bool) {
 	for _, group := range file.Comments {
 		for _, comment := range group.List {
 			if comment.Pos() > file.Package {
 				break // after package declaration
 			}
 			// opt: check Contains first to avoid unnecessary array allocation in Split.
 			const prefix = "// Code generated "
 			if strings.Contains(comment.Text, prefix) {
 				for _, line := range strings.Split(comment.Text, "\n") {
 					if rest, ok := strings.CutPrefix(line, prefix); ok {
 						if gen, ok := strings.CutSuffix(rest, " DO NOT EDIT."); ok {
 							return gen, true
 						}
 					}
 				}
 			}
 		}
 	}
 	return "", false
 }

 // pathSearch returns the shortest path from one of the roots to one
 // of the targets (along with the root itself), or zero if no path was found.
 func pathSearch(roots []*ssa.Function, res *rta.Result, targets map[*ssa.Function]bool) (*callgraph.Node, []*callgraph.Edge) {
 	// Search breadth-first (for shortest path) from the root.
 	//
 	// We don't use the virtual CallGraph.Root node as we wish to
 	// choose the order in which we search entrypoints:
 	// non-test packages before test packages,
 	// main functions before init functions.

 	// Sort roots into preferred order.
 	importsTesting := func(fn *ssa.Function) bool {
 		isTesting := func(p *types.Package) bool { return p.Path() == "testing" }
 		return containsFunc(fn.Pkg.Pkg.Imports(), isTesting)
 	}
 	sort.Slice(roots, func(i, j int) bool {
 		x, y := roots[i], roots[j]
 		xtest := importsTesting(x)
 		ytest := importsTesting(y)
 		if xtest != ytest {
 			return !xtest // non-tests before tests
 		}
 		xinit := x.Name() == "init"
 		yinit := y.Name() == "init"
 		if xinit != yinit {
 			return !xinit // mains before inits
 		}
 		return false
 	})

 	search := func(allowDynamic bool) (*callgraph.Node, []*callgraph.Edge) {
 		// seen maps each encountered node to its predecessor on the
 		// path to a root node, or to nil for root itself.
 		seen := make(map[*callgraph.Node]*callgraph.Edge)
 		bfs := func(root *callgraph.Node) []*callgraph.Edge {
 			queue := []*callgraph.Node{root}
 			seen[root] = nil
 			for len(queue) > 0 {
 				node := queue[0]
 				queue = queue[1:]

 				// found a path?
 				if targets[node.Func] {
 					path := []*callgraph.Edge{} // non-nil in case len(path)=0
 					for {
 						edge := seen[node]
 						if edge == nil {
 							reverse(path)
 							return path
 						}
 						path = append(path, edge)
 						node = edge.Caller
 					}
 				}

 				for _, edge := range node.Out {
 					if allowDynamic || isStaticCall(edge) {
 						if _, ok := seen[edge.Callee]; !ok {
 							seen[edge.Callee] = edge
 							queue = append(queue, edge.Callee)
 						}
 					}
 				}
 			}
 			return nil
 		}
 		for _, rootFn := range roots {
 			root := res.CallGraph.Nodes[rootFn]
 			if root == nil {
 				// Missing call graph node for root.
 				// TODO(adonovan): seems like a bug in rta.
 				continue
 			}
 			if path := bfs(root); path != nil {
 				return root, path
 			}
 		}
 		return nil, nil
 	}

 	for _, allowDynamic := range []bool{false, true} {
 		if root, path := search(allowDynamic); path != nil {
 			return root, path
 		}
 	}

 	return nil, nil
 }

 // -- utilities --

 func isStaticCall(edge *callgraph.Edge) bool {
 	return edge.Site != nil && edge.Site.Common().StaticCallee() != nil
 }

 var cwd, _ = os.Getwd()

 func toJSONPosition(posn token.Position) jsonPosition {
 	// Use cwd-relative filename if possible.
 	filename := posn.Filename
 	if rel, err := filepath.Rel(cwd, filename); err == nil && !strings.HasPrefix(rel, "..") {
 		filename = rel
 	}

 	return jsonPosition{filename, posn.Line, posn.Column}
 }

 func cond[T any](cond bool, t, f T) T {
 	if cond {
 		return t
 	} else {
 		return f
 	}
 }

 // -- output protocol (for JSON or text/template) --

 // Keep in sync with doc comment!

 type jsonFunction struct {
 	Name      string       // name (sans package qualifier)
 	Position  jsonPosition // file/line/column of declaration
 	Generated bool         // function is declared in a generated .go file
 }

 func (f jsonFunction) String() string { return f.Name }

 type jsonPackage struct {
 	Name  string         // declared name
 	Path  string         // full import path
 	Funcs []jsonFunction // non-empty list of package's dead functions
 }

 func (p jsonPackage) String() string { return p.Path }

 // The Initial and Callee names are package-qualified.
 type jsonEdge struct {
 	Initial  string `json:",omitempty"` // initial entrypoint (main or init); first edge only
 	Kind     string // = static | dynamic
 	Position jsonPosition
 	Callee   string
 }

 type jsonPosition struct {
 	File      string
 	Line, Col int
 }

 func (p jsonPosition) String() string {
 	return fmt.Sprintf("%s:%d:%d", p.File, p.Line, p.Col)
 }

 // -- from the future --

 // TODO(adonovan): use go1.22's slices and maps packages.

 func containsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
 	return indexFunc(s, f) >= 0
 }

 func indexFunc[S ~[]E, E any](s S, f func(E) bool) int {
 	for i := range s {
 		if f(s[i]) {
 			return i
 		}
 	}
 	return -1
 }

 func index[S ~[]E, E comparable](s S, v E) int {
 	for i := range s {
 		if v == s[i] {
 			return i
 		}
 	}
 	return -1
 }

 func reverse[S ~[]E, E any](s S) {
 	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
 		s[i], s[j] = s[j], s[i]
 	}
 }

 func keys[M ~map[K]V, K comparable, V any](m M) []K {
 	r := make([]K, 0, len(m))
 	for k := range m {
 		r = append(r, k)
 	}
 	return r
 }
	// Copyright 2023 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	//go:build go1.20

	package main

	import (
	"bytes"
	_ "embed"
	"encoding/json"
	"flag"
	"fmt"
	"go/ast"
	"go/token"
	"go/types"
	"io"
	"log"
	"os"
	"path/filepath"
	"regexp"
	"runtime"
	"runtime/pprof"
	"sort"
	"strings"
	"text/template"

	"golang.org/x/telemetry"
	"golang.org/x/tools/go/callgraph"
	"golang.org/x/tools/go/callgraph/rta"
	"golang.org/x/tools/go/packages"
	"golang.org/x/tools/go/ssa"
	"golang.org/x/tools/go/ssa/ssautil"
	"golang.org/x/tools/internal/typesinternal"
	)

	//go:embed doc.go
	var doc string

	// flags
	var (
	testFlag = flag.Bool("test", false, "include implicit test packages and executables")
	tagsFlag = flag.String("tags", "", "comma-separated list of extra build tags (see: go help buildconstraint)")

	filterFlag = flag.String("filter", "<module>", "report only packages matching this regular expression (default: module of first package)")
	generatedFlag = flag.Bool("generated", false, "include dead functions in generated Go files")
	whyLiveFlag = flag.String("whylive", "", "show a path from main to the named function")
	formatFlag = flag.String("f", "", "format output records using template")
	jsonFlag = flag.Bool("json", false, "output JSON records")
	cpuProfile = flag.String("cpuprofile", "", "write CPU profile to this file")
	memProfile = flag.String("memprofile", "", "write memory profile to this file")
	)

	func usage() {
	// Extract the content of the /* ... */ comment in doc.go.
	_, after, _ := strings.Cut(doc, "/*\n")
	doc, _, _ := strings.Cut(after, "*/")
	io.WriteString(flag.CommandLine.Output(), doc+`
	Flags:

	`)
	flag.PrintDefaults()
	}

	func main() {
	telemetry.Start(telemetry.Config{ReportCrashes: true})

	log.SetPrefix("deadcode: ")
	log.SetFlags(0) // no time prefix

	flag.Usage = usage
	flag.Parse()
	if len(flag.Args()) == 0 {
	usage()
	os.Exit(2)
	}

	if *cpuProfile != "" {
	f, err := os.Create(*cpuProfile)
	if err != nil {
	log.Fatal(err)
	}
	if err := pprof.StartCPUProfile(f); err != nil {
	log.Fatal(err)
	}
	// NB: profile won't be written in case of error.
	defer pprof.StopCPUProfile()
	}

	if *memProfile != "" {
	f, err := os.Create(*memProfile)
	if err != nil {
	log.Fatal(err)
	}
	// NB: profile won't be written in case of error.
	defer func() {
	runtime.GC() // get up-to-date statistics
	if err := pprof.WriteHeapProfile(f); err != nil {
	log.Fatalf("Writing memory profile: %v", err)
	}
	f.Close()
	}()
	}

	// Reject bad output options early.
	if *formatFlag != "" {
	if *jsonFlag {
	log.Fatalf("you cannot specify both -f=template and -json")
	}
	if _, err := template.New("deadcode").Parse(*formatFlag); err != nil {
	log.Fatalf("invalid -f: %v", err)
	}
	}

	// Load, parse, and type-check the complete program(s).
	cfg := &packages.Config{
	BuildFlags: []string{"-tags=" + *tagsFlag},
	Mode: packages.LoadAllSyntax \| packages.NeedModule,
	Tests: *testFlag,
	}
	initial, err := packages.Load(cfg, flag.Args()...)
	if err != nil {
	log.Fatalf("Load: %v", err)
	}
	if len(initial) == 0 {
	log.Fatalf("no packages")
	}
	if packages.PrintErrors(initial) > 0 {
	log.Fatalf("packages contain errors")
	}

	// If -filter is unset, use first module (if available).
	if *filterFlag == "<module>" {
	if mod := initial[0].Module; mod != nil && mod.Path != "" {
	*filterFlag = "^" + regexp.QuoteMeta(mod.Path) + "\\b"
	} else {
	*filterFlag = "" // match any
	}
	}
	filter, err := regexp.Compile(*filterFlag)
	if err != nil {
	log.Fatalf("-filter: %v", err)
	}

	// Create SSA-form program representation
	// and find main packages.
	prog, pkgs := ssautil.AllPackages(initial, ssa.InstantiateGenerics)
	prog.Build()

	mains := ssautil.MainPackages(pkgs)
	if len(mains) == 0 {
	log.Fatalf("no main packages")
	}
	var roots []*ssa.Function
	for _, main := range mains {
	roots = append(roots, main.Func("init"), main.Func("main"))
	}

	// Gather all source-level functions,
	// as the user interface is expressed in terms of them.
	//
	// We ignore synthetic wrappers, and nested functions. Literal
	// functions passed as arguments to other functions are of
	// course address-taken and there exists a dynamic call of
	// that signature, so when they are unreachable, it is
	// invariably because the parent is unreachable.
	var sourceFuncs []*ssa.Function
	generated := make(map[string]bool)
	packages.Visit(initial, nil, func(p *packages.Package) {
	for _, file := range p.Syntax {
	for _, decl := range file.Decls {
	if decl, ok := decl.(*ast.FuncDecl); ok {
	obj := p.TypesInfo.Defs[decl.Name].(*types.Func)
	fn := prog.FuncValue(obj)
	sourceFuncs = append(sourceFuncs, fn)
	}
	}

	if isGenerated(file) {
	generated[p.Fset.File(file.Pos()).Name()] = true
	}
	}
	})

	// Compute the reachabilty from main.
	// (Build a call graph only for -whylive.)
	res := rta.Analyze(roots, *whyLiveFlag != "")

	// Subtle: the -test flag causes us to analyze test variants
	// such as "package p as compiled for p.test" or even "for q.test".
	// This leads to multiple distinct ssa.Function instances that
	// represent the same source declaration, and it is essentially
	// impossible to discover this from the SSA representation
	// (since it has lost the connection to go/packages.Package.ID).
	//
	// So, we de-duplicate such variants by position:
	// if any one of them is live, we consider all of them live.
	// (We use Position not Pos to avoid assuming that files common
	// to packages "p" and "p [p.test]" were parsed only once.)
	reachablePosn := make(map[token.Position]bool)
	for fn := range res.Reachable {
	if fn.Pos().IsValid() \|\| fn.Name() == "init" {
	reachablePosn[prog.Fset.Position(fn.Pos())] = true
	}
	}

	// The -whylive=fn flag causes deadcode to explain why a function
	// is not dead, by showing a path to it from some root.
	if *whyLiveFlag != "" {
	targets := make(map[*ssa.Function]bool)
	for _, fn := range sourceFuncs {
	if prettyName(fn, true) == *whyLiveFlag {
	targets[fn] = true
	}
	}
	if len(targets) == 0 {
	// Function is not part of the program.
	//
	// TODO(adonovan): improve the UX here in case
	// of spelling or syntax mistakes. Some ideas:
	// - a cmd/callgraph command to enumerate
	// available functions.
	// - a deadcode -live flag to compute the complement.
	// - a syntax hint: example.com/pkg.Func or (example.com/pkg.Type).Method
	// - report the element of AllFunctions with the smallest
	// Levenshtein distance from *whyLiveFlag.
	// - permit -whylive=regexp. But beware of spurious
	// matches (e.g. fmt.Print matches fmt.Println)
	// and the annoyance of having to quote parens (*T).f.
	log.Fatalf("function %q not found in program", *whyLiveFlag)
	}

	// Opt: remove the unreachable ones.
	for fn := range targets {
	if !reachablePosn[prog.Fset.Position(fn.Pos())] {
	delete(targets, fn)
	}
	}
	if len(targets) == 0 {
	log.Fatalf("function %s is dead code", *whyLiveFlag)
	}

	res.CallGraph.DeleteSyntheticNodes() // inline synthetic wrappers (except inits)
	root, path := pathSearch(roots, res, targets)
	if root == nil {
	// RTA doesn't add callgraph edges for reflective calls.
	log.Fatalf("%s is reachable only through reflection", *whyLiveFlag)
	}
	if len(path) == 0 {
	// No edges => one of the targets is a root.
	// Rather than (confusingly) print nothing, make this an error.
	log.Fatalf("%s is a root", root.Func)
	}

	// Build a list of jsonEdge records
	// to print as -json or -f=template.
	var edges []any
	for _, edge := range path {
	edges = append(edges, jsonEdge{
	Initial: cond(len(edges) == 0, prettyName(edge.Caller.Func, true), ""),
	Kind: cond(isStaticCall(edge), "static", "dynamic"),
	Position: toJSONPosition(prog.Fset.Position(edge.Site.Pos())),
	Callee: prettyName(edge.Callee.Func, true),
	})
	}
	format := `{{if .Initial}}{{printf "%19s%s\n" "" .Initial}}{{end}}{{printf "%8s@L%.4d --> %s" .Kind .Position.Line .Callee}}`
	if *formatFlag != "" {
	format = *formatFlag
	}
	printObjects(format, edges)
	return
	}

	// Group unreachable functions by package path.
	byPkgPath := make(map[string]map[*ssa.Function]bool)
	for _, fn := range sourceFuncs {
	posn := prog.Fset.Position(fn.Pos())

	if !reachablePosn[posn] {
	reachablePosn[posn] = true // suppress dups with same pos

	pkgpath := fn.Pkg.Pkg.Path()
	m, ok := byPkgPath[pkgpath]
	if !ok {
	m = make(map[*ssa.Function]bool)
	byPkgPath[pkgpath] = m
	}
	m[fn] = true
	}
	}

	// Build array of jsonPackage objects.
	var packages []any
	pkgpaths := keys(byPkgPath)
	sort.Strings(pkgpaths)
	for _, pkgpath := range pkgpaths {
	if !filter.MatchString(pkgpath) {
	continue
	}

	m := byPkgPath[pkgpath]

	// Print functions that appear within the same file in
	// declaration order. This tends to keep related
	// methods such as (T).Marshal and (*T).Unmarshal
	// together better than sorting.
	fns := keys(m)
	sort.Slice(fns, func(i, j int) bool {
	xposn := prog.Fset.Position(fns[i].Pos())
	yposn := prog.Fset.Position(fns[j].Pos())
	if xposn.Filename != yposn.Filename {
	return xposn.Filename < yposn.Filename
	}
	return xposn.Line < yposn.Line
	})

	var functions []jsonFunction
	for _, fn := range fns {
	posn := prog.Fset.Position(fn.Pos())

	// Without -generated, skip functions declared in
	// generated Go files.
	// (Functions called by them may still be reported.)
	gen := generated[posn.Filename]
	if gen && !*generatedFlag {
	continue
	}

	functions = append(functions, jsonFunction{
	Name: prettyName(fn, false),
	Position: toJSONPosition(posn),
	Generated: gen,
	})
	}
	if len(functions) > 0 {
	packages = append(packages, jsonPackage{
	Name: fns[0].Pkg.Pkg.Name(),
	Path: pkgpath,
	Funcs: functions,
	})
	}
	}

	// Default line-oriented format: "a/b/c.go:1:2: unreachable func: T.f"
	format := `{{range .Funcs}}{{printf "%s: unreachable func: %s\n" .Position .Name}}{{end}}`
	if *formatFlag != "" {
	format = *formatFlag
	}
	printObjects(format, packages)
	}

	// prettyName is a fork of Function.String designed to reduce
	// go/ssa's fussy punctuation symbols, e.g. "(*pkg.T).F" -> "pkg.T.F".
	//
	// It only works for functions that remain after
	// callgraph.Graph.DeleteSyntheticNodes: source-level named functions
	// and methods, their anonymous functions, and synthetic package
	// initializers.
	func prettyName(fn *ssa.Function, qualified bool) string {
	var buf strings.Builder

	// optional package qualifier
	if qualified && fn.Pkg != nil {
	fmt.Fprintf(&buf, "%s.", fn.Pkg.Pkg.Path())
	}

	var format func(*ssa.Function)
	format = func(fn *ssa.Function) {
	// anonymous?
	if fn.Parent() != nil {
	format(fn.Parent())
	i := index(fn.Parent().AnonFuncs, fn)
	fmt.Fprintf(&buf, "$%d", i+1)
	return
	}

	// method receiver?
	if recv := fn.Signature.Recv(); recv != nil {
	_, named := typesinternal.ReceiverNamed(recv)
	buf.WriteString(named.Obj().Name())
	buf.WriteByte('.')
	}

	// function/method name
	buf.WriteString(fn.Name())
	}
	format(fn)

	return buf.String()
	}

	// printObjects formats an array of objects, either as JSON or using a
	// template, following the manner of 'go list (-json\|-f=template)'.
	func printObjects(format string, objects []any) {
	if *jsonFlag {
	out, err := json.MarshalIndent(objects, "", "\t")
	if err != nil {
	log.Fatalf("internal error: %v", err)
	}
	os.Stdout.Write(out)
	return
	}

	// -f=template. Parse can't fail: we checked it earlier.
	tmpl := template.Must(template.New("deadcode").Parse(format))
	for _, object := range objects {
	var buf bytes.Buffer
	if err := tmpl.Execute(&buf, object); err != nil {
	log.Fatal(err)
	}
	if n := buf.Len(); n == 0 \|\| buf.Bytes()[n-1] != '\n' {
	buf.WriteByte('\n')
	}
	os.Stdout.Write(buf.Bytes())
	}
	}

	// TODO(adonovan): use go1.21's ast.IsGenerated.

	// isGenerated reports whether the file was generated by a program,
	// not handwritten, by detecting the special comment described
	// at https://go.dev/s/generatedcode.
	//
	// The syntax tree must have been parsed with the ParseComments flag.
	// Example:
	//
	// f, err := parser.ParseFile(fset, filename, src, parser.ParseComments\|parser.PackageClauseOnly)
	// if err != nil { ... }
	// gen := ast.IsGenerated(f)
	func isGenerated(file *ast.File) bool {
	_, ok := generator(file)
	return ok
	}

	func generator(file *ast.File) (string, bool) {
	for _, group := range file.Comments {
	for _, comment := range group.List {
	if comment.Pos() > file.Package {
	break // after package declaration
	}
	// opt: check Contains first to avoid unnecessary array allocation in Split.
	const prefix = "// Code generated "
	if strings.Contains(comment.Text, prefix) {
	for _, line := range strings.Split(comment.Text, "\n") {
	if rest, ok := strings.CutPrefix(line, prefix); ok {
	if gen, ok := strings.CutSuffix(rest, " DO NOT EDIT."); ok {
	return gen, true
	}
	}
	}
	}
	}
	}
	return "", false
	}

	// pathSearch returns the shortest path from one of the roots to one
	// of the targets (along with the root itself), or zero if no path was found.
	func pathSearch(roots []ssa.Function, res rta.Result, targets map[ssa.Function]bool) (callgraph.Node, []*callgraph.Edge) {
	// Search breadth-first (for shortest path) from the root.
	//
	// We don't use the virtual CallGraph.Root node as we wish to
	// choose the order in which we search entrypoints:
	// non-test packages before test packages,
	// main functions before init functions.

	// Sort roots into preferred order.
	importsTesting := func(fn *ssa.Function) bool {
	isTesting := func(p *types.Package) bool { return p.Path() == "testing" }
	return containsFunc(fn.Pkg.Pkg.Imports(), isTesting)
	}
	sort.Slice(roots, func(i, j int) bool {
	x, y := roots[i], roots[j]
	xtest := importsTesting(x)
	ytest := importsTesting(y)
	if xtest != ytest {
	return !xtest // non-tests before tests
	}
	xinit := x.Name() == "init"
	yinit := y.Name() == "init"
	if xinit != yinit {
	return !xinit // mains before inits
	}
	return false
	})

	search := func(allowDynamic bool) (callgraph.Node, []callgraph.Edge) {
	// seen maps each encountered node to its predecessor on the
	// path to a root node, or to nil for root itself.
	seen := make(map[callgraph.Node]callgraph.Edge)
	bfs := func(root callgraph.Node) []callgraph.Edge {
	queue := []*callgraph.Node{root}
	seen[root] = nil
	for len(queue) > 0 {
	node := queue[0]
	queue = queue[1:]

	// found a path?
	if targets[node.Func] {
	path := []*callgraph.Edge{} // non-nil in case len(path)=0
	for {
	edge := seen[node]
	if edge == nil {
	reverse(path)
	return path
	}
	path = append(path, edge)
	node = edge.Caller
	}
	}

	for _, edge := range node.Out {
	if allowDynamic \|\| isStaticCall(edge) {
	if _, ok := seen[edge.Callee]; !ok {
	seen[edge.Callee] = edge
	queue = append(queue, edge.Callee)
	}
	}
	}
	}
	return nil
	}
	for _, rootFn := range roots {
	root := res.CallGraph.Nodes[rootFn]
	if root == nil {
	// Missing call graph node for root.
	// TODO(adonovan): seems like a bug in rta.
	continue
	}
	if path := bfs(root); path != nil {
	return root, path
	}
	}
	return nil, nil
	}

	for _, allowDynamic := range []bool{false, true} {
	if root, path := search(allowDynamic); path != nil {
	return root, path
	}
	}

	return nil, nil
	}

	// -- utilities --

	func isStaticCall(edge *callgraph.Edge) bool {
	return edge.Site != nil && edge.Site.Common().StaticCallee() != nil
	}

	var cwd, _ = os.Getwd()

	func toJSONPosition(posn token.Position) jsonPosition {
	// Use cwd-relative filename if possible.
	filename := posn.Filename
	if rel, err := filepath.Rel(cwd, filename); err == nil && !strings.HasPrefix(rel, "..") {
	filename = rel
	}

	return jsonPosition{filename, posn.Line, posn.Column}
	}

	func cond[T any](cond bool, t, f T) T {
	if cond {
	return t
	} else {
	return f
	}
	}

	// -- output protocol (for JSON or text/template) --

	// Keep in sync with doc comment!

	type jsonFunction struct {
	Name string // name (sans package qualifier)
	Position jsonPosition // file/line/column of declaration
	Generated bool // function is declared in a generated .go file
	}

	func (f jsonFunction) String() string { return f.Name }

	type jsonPackage struct {
	Name string // declared name
	Path string // full import path
	Funcs []jsonFunction // non-empty list of package's dead functions
	}

	func (p jsonPackage) String() string { return p.Path }

	// The Initial and Callee names are package-qualified.
	type jsonEdge struct {
	Initial string `json:",omitempty"` // initial entrypoint (main or init); first edge only
	Kind string // = static \| dynamic
	Position jsonPosition
	Callee string
	}

	type jsonPosition struct {
	File string
	Line, Col int
	}

	func (p jsonPosition) String() string {
	return fmt.Sprintf("%s:%d:%d", p.File, p.Line, p.Col)
	}

	// -- from the future --

	// TODO(adonovan): use go1.22's slices and maps packages.

	func containsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
	return indexFunc(s, f) >= 0
	}

	func indexFunc[S ~[]E, E any](s S, f func(E) bool) int {
	for i := range s {
	if f(s[i]) {
	return i
	}
	}
	return -1
	}

	func index[S ~[]E, E comparable](s S, v E) int {
	for i := range s {
	if v == s[i] {
	return i
	}
	}
	return -1
	}

	func reverse[S ~[]E, E any](s S) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
	s[i], s[j] = s[j], s[i]
	}
	}

	func keys[M ~map[K]V, K comparable, V any](m M) []K {
	r := make([]K, 0, len(m))
	for k := range m {
	r = append(r, k)
	}
	return r
	}