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