main.go

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

     1  // Copyright 2014 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  // callgraph: a tool for reporting the call graph of a Go program.
     6  // See Usage for details, or run with -help.
     7  package main // import "golang.org/x/tools/cmd/callgraph"
     8  
     9  // TODO(adonovan):
    10  //
    11  // Features:
    12  // - restrict graph to a single package
    13  // - output
    14  //   - functions reachable from root (use digraph tool?)
    15  //   - unreachable functions (use digraph tool?)
    16  //   - dynamic (runtime) types
    17  //   - indexed output (numbered nodes)
    18  //   - JSON output
    19  //   - additional template fields:
    20  //     callee file/line/col
    21  
    22  import (
    23  	"bytes"
    24  	"flag"
    25  	"fmt"
    26  	"go/build"
    27  	"go/token"
    28  	"io"
    29  	"os"
    30  	"runtime"
    31  	"text/template"
    32  
    33  	"golang.org/x/tools/go/buildutil"
    34  	"golang.org/x/tools/go/callgraph"
    35  	"golang.org/x/tools/go/callgraph/cha"
    36  	"golang.org/x/tools/go/callgraph/rta"
    37  	"golang.org/x/tools/go/callgraph/static"
    38  	"golang.org/x/tools/go/callgraph/vta"
    39  	"golang.org/x/tools/go/packages"
    40  	"golang.org/x/tools/go/ssa"
    41  	"golang.org/x/tools/go/ssa/ssautil"
    42  )
    43  
    44  // flags
    45  var (
    46  	algoFlag = flag.String("algo", "rta",
    47  		`Call graph construction algorithm (static, cha, rta, vta)`)
    48  
    49  	testFlag = flag.Bool("test", false,
    50  		"Loads test code (*_test.go) for imported packages")
    51  
    52  	formatFlag = flag.String("format",
    53  		"{{.Caller}}\t--{{.Dynamic}}-{{.Line}}:{{.Column}}-->\t{{.Callee}}",
    54  		"A template expression specifying how to format an edge")
    55  )
    56  
    57  func init() {
    58  	flag.Var((*buildutil.TagsFlag)(&build.Default.BuildTags), "tags", buildutil.TagsFlagDoc)
    59  }
    60  
    61  const Usage = `callgraph: display the call graph of a Go program.
    62  
    63  Usage:
    64  
    65    callgraph [-algo=static|cha|rta|vta] [-test] [-format=...] package...
    66  
    67  Flags:
    68  
    69  -algo      Specifies the call-graph construction algorithm, one of:
    70  
    71              static      static calls only (unsound)
    72              cha         Class Hierarchy Analysis
    73              rta         Rapid Type Analysis
    74              vta         Variable Type Analysis
    75  
    76             The algorithms are ordered by increasing precision in their
    77             treatment of dynamic calls (and thus also computational cost).
    78             RTA requires a whole program (main or test), and
    79             include only functions reachable from main.
    80  
    81  -test      Include the package's tests in the analysis.
    82  
    83  -format    Specifies the format in which each call graph edge is displayed.
    84             One of:
    85  
    86              digraph     output suitable for input to
    87                          golang.org/x/tools/cmd/digraph.
    88              graphviz    output in AT&T GraphViz (.dot) format.
    89  
    90             All other values are interpreted using text/template syntax.
    91             The default value is:
    92  
    93              {{.Caller}}\t--{{.Dynamic}}-{{.Line}}:{{.Column}}-->\t{{.Callee}}
    94  
    95             The structure passed to the template is (effectively):
    96  
    97                     type Edge struct {
    98                             Caller      *ssa.Function // calling function
    99                             Callee      *ssa.Function // called function
   100  
   101                             // Call site:
   102                             Filename    string // containing file
   103                             Offset      int    // offset within file of '('
   104                             Line        int    // line number
   105                             Column      int    // column number of call
   106                             Dynamic     string // "static" or "dynamic"
   107                             Description string // e.g. "static method call"
   108                     }
   109  
   110             Caller and Callee are *ssa.Function values, which print as
   111             "(*sync/atomic.Mutex).Lock", but other attributes may be
   112             derived from them. For example:
   113  
   114             - {{.Caller.Pkg.Pkg.Path}} yields the import path of the
   115               enclosing package; and
   116  
   117             - {{(.Caller.Prog.Fset.Position .Caller.Pos).Filename}}
   118               yields the name of the file that declares the caller.
   119  
   120             - The 'posn' template function returns the token.Position
   121               of an ssa.Function, so the previous example can be
   122               reduced to {{(posn .Caller).Filename}}.
   123  
   124             Consult the documentation for go/token, text/template, and
   125             golang.org/x/tools/go/ssa for more detail.
   126  
   127  Examples:
   128  
   129    Show the call graph of the trivial web server application:
   130  
   131      callgraph -format digraph $GOROOT/src/net/http/triv.go
   132  
   133    Same, but show only the packages of each function:
   134  
   135      callgraph -format '{{.Caller.Pkg.Pkg.Path}} -> {{.Callee.Pkg.Pkg.Path}}' \
   136        $GOROOT/src/net/http/triv.go | sort | uniq
   137  
   138    Show functions that make dynamic calls into the 'fmt' test package,
   139    using the Rapid Type Analysis algorithm:
   140  
   141      callgraph -format='{{.Caller}} -{{.Dynamic}}-> {{.Callee}}' -test -algo=rta fmt |
   142        sed -ne 's/-dynamic-/--/p' |
   143        sed -ne 's/-->.*fmt_test.*$//p' | sort | uniq
   144  
   145    Show all functions directly called by the callgraph tool's main function:
   146  
   147      callgraph -format=digraph golang.org/x/tools/cmd/callgraph |
   148        digraph succs golang.org/x/tools/cmd/callgraph.main
   149  `
   150  
   151  func init() {
   152  	// If $GOMAXPROCS isn't set, use the full capacity of the machine.
   153  	// For small machines, use at least 4 threads.
   154  	if os.Getenv("GOMAXPROCS") == "" {
   155  		n := runtime.NumCPU()
   156  		if n < 4 {
   157  			n = 4
   158  		}
   159  		runtime.GOMAXPROCS(n)
   160  	}
   161  }
   162  
   163  func main() {
   164  	flag.Parse()
   165  	if err := doCallgraph("", "", *algoFlag, *formatFlag, *testFlag, flag.Args()); err != nil {
   166  		fmt.Fprintf(os.Stderr, "callgraph: %s\n", err)
   167  		os.Exit(1)
   168  	}
   169  }
   170  
   171  var stdout io.Writer = os.Stdout
   172  
   173  func doCallgraph(dir, gopath, algo, format string, tests bool, args []string) error {
   174  	if len(args) == 0 {
   175  		fmt.Fprint(os.Stderr, Usage)
   176  		return nil
   177  	}
   178  
   179  	cfg := &packages.Config{
   180  		Mode:  packages.LoadAllSyntax,
   181  		Tests: tests,
   182  		Dir:   dir,
   183  	}
   184  	if gopath != "" {
   185  		cfg.Env = append(os.Environ(), "GOPATH="+gopath) // to enable testing
   186  	}
   187  	initial, err := packages.Load(cfg, args...)
   188  	if err != nil {
   189  		return err
   190  	}
   191  	if packages.PrintErrors(initial) > 0 {
   192  		return fmt.Errorf("packages contain errors")
   193  	}
   194  
   195  	// Create and build SSA-form program representation.
   196  	mode := ssa.InstantiateGenerics // instantiate generics by default for soundness
   197  	prog, pkgs := ssautil.AllPackages(initial, mode)
   198  	prog.Build()
   199  
   200  	// -- call graph construction ------------------------------------------
   201  
   202  	var cg *callgraph.Graph
   203  
   204  	switch algo {
   205  	case "static":
   206  		cg = static.CallGraph(prog)
   207  
   208  	case "cha":
   209  		cg = cha.CallGraph(prog)
   210  
   211  	case "pta":
   212  		return fmt.Errorf("pointer analysis is no longer supported (see Go issue #59676)")
   213  
   214  	case "rta":
   215  		mains, err := mainPackages(pkgs)
   216  		if err != nil {
   217  			return err
   218  		}
   219  		var roots []*ssa.Function
   220  		for _, main := range mains {
   221  			roots = append(roots, main.Func("init"), main.Func("main"))
   222  		}
   223  		rtares := rta.Analyze(roots, true)
   224  		cg = rtares.CallGraph
   225  
   226  		// NB: RTA gives us Reachable and RuntimeTypes too.
   227  
   228  	case "vta":
   229  		cg = vta.CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
   230  
   231  	default:
   232  		return fmt.Errorf("unknown algorithm: %s", algo)
   233  	}
   234  
   235  	cg.DeleteSyntheticNodes()
   236  
   237  	// -- output------------------------------------------------------------
   238  
   239  	var before, after string
   240  
   241  	// Pre-canned formats.
   242  	switch format {
   243  	case "digraph":
   244  		format = `{{printf "%q %q" .Caller .Callee}}`
   245  
   246  	case "graphviz":
   247  		before = "digraph callgraph {\n"
   248  		after = "}\n"
   249  		format = `  {{printf "%q" .Caller}} -> {{printf "%q" .Callee}}`
   250  	}
   251  
   252  	funcMap := template.FuncMap{
   253  		"posn": func(f *ssa.Function) token.Position {
   254  			return f.Prog.Fset.Position(f.Pos())
   255  		},
   256  	}
   257  	tmpl, err := template.New("-format").Funcs(funcMap).Parse(format)
   258  	if err != nil {
   259  		return fmt.Errorf("invalid -format template: %v", err)
   260  	}
   261  
   262  	// Allocate these once, outside the traversal.
   263  	var buf bytes.Buffer
   264  	data := Edge{fset: prog.Fset}
   265  
   266  	fmt.Fprint(stdout, before)
   267  	if err := callgraph.GraphVisitEdges(cg, func(edge *callgraph.Edge) error {
   268  		data.position.Offset = -1
   269  		data.edge = edge
   270  		data.Caller = edge.Caller.Func
   271  		data.Callee = edge.Callee.Func
   272  
   273  		buf.Reset()
   274  		if err := tmpl.Execute(&buf, &data); err != nil {
   275  			return err
   276  		}
   277  		stdout.Write(buf.Bytes())
   278  		if len := buf.Len(); len == 0 || buf.Bytes()[len-1] != '\n' {
   279  			fmt.Fprintln(stdout)
   280  		}
   281  		return nil
   282  	}); err != nil {
   283  		return err
   284  	}
   285  	fmt.Fprint(stdout, after)
   286  	return nil
   287  }
   288  
   289  // mainPackages returns the main packages to analyze.
   290  // Each resulting package is named "main" and has a main function.
   291  func mainPackages(pkgs []*ssa.Package) ([]*ssa.Package, error) {
   292  	var mains []*ssa.Package
   293  	for _, p := range pkgs {
   294  		if p != nil && p.Pkg.Name() == "main" && p.Func("main") != nil {
   295  			mains = append(mains, p)
   296  		}
   297  	}
   298  	if len(mains) == 0 {
   299  		return nil, fmt.Errorf("no main packages")
   300  	}
   301  	return mains, nil
   302  }
   303  
   304  type Edge struct {
   305  	Caller *ssa.Function
   306  	Callee *ssa.Function
   307  
   308  	edge     *callgraph.Edge
   309  	fset     *token.FileSet
   310  	position token.Position // initialized lazily
   311  }
   312  
   313  func (e *Edge) pos() *token.Position {
   314  	if e.position.Offset == -1 {
   315  		e.position = e.fset.Position(e.edge.Pos()) // called lazily
   316  	}
   317  	return &e.position
   318  }
   319  
   320  func (e *Edge) Filename() string { return e.pos().Filename }
   321  func (e *Edge) Column() int      { return e.pos().Column }
   322  func (e *Edge) Line() int        { return e.pos().Line }
   323  func (e *Edge) Offset() int      { return e.pos().Offset }
   324  
   325  func (e *Edge) Dynamic() string {
   326  	if e.edge.Site != nil && e.edge.Site.Common().StaticCallee() == nil {
   327  		return "dynamic"
   328  	}
   329  	return "static"
   330  }
   331  
   332  func (e *Edge) Description() string { return e.edge.Description() }
   333
View as plain text