blob: 948ce9a3241ec218782022ee3f72c28e9579fafe [file] [log] [blame]
// Copyright 2014 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.
// Package static computes the call graph of a Go program containing
// only static call edges.
package static
import (
"go/types"
"golang.org/x/tools/go/callgraph"
"golang.org/x/tools/go/ssa"
)
// CallGraph computes the static call graph of the specified program.
//
// The resulting graph includes:
// - all package-level functions;
// - all methods of package-level non-parameterized non-interface types;
// - pointer wrappers (*C).F for source-level methods C.F;
// - and all functions reachable from them following only static calls.
//
// It does not consider exportedness, nor treat main packages specially.
func CallGraph(prog *ssa.Program) *callgraph.Graph {
cg := callgraph.New(nil)
// Recursively follow all static calls.
seen := make(map[int]bool) // node IDs already seen
var visit func(fnode *callgraph.Node)
visit = func(fnode *callgraph.Node) {
if !seen[fnode.ID] {
seen[fnode.ID] = true
for _, b := range fnode.Func.Blocks {
for _, instr := range b.Instrs {
if site, ok := instr.(ssa.CallInstruction); ok {
if g := site.Common().StaticCallee(); g != nil {
gnode := cg.CreateNode(g)
callgraph.AddEdge(fnode, site, gnode)
visit(gnode)
}
}
}
}
}
}
// If we were ever to redesign this function, we should allow
// the caller to provide the set of root functions and just
// perform the reachability step. This would allow them to
// work forwards from main entry points:
//
// rootNames := []string{"init", "main"}
// for _, main := range ssautil.MainPackages(prog.AllPackages()) {
// for _, rootName := range rootNames {
// visit(cg.CreateNode(main.Func(rootName)))
// }
// }
//
// or to control whether to include non-exported
// functions/methods, wrapper methods, and so on.
// Unfortunately that's not consistent with its historical
// behavior and existing tests.
//
// The logic below is a slight simplification and
// rationalization of ssautil.AllFunctions. (Having to include
// (*T).F wrapper methods is unfortunate--they are not source
// functions, and if they're reachable, they'll be in the
// graph--but the existing tests will break without it.)
methodsOf := func(T types.Type) {
if !types.IsInterface(T) {
mset := prog.MethodSets.MethodSet(T)
for i := 0; i < mset.Len(); i++ {
visit(cg.CreateNode(prog.MethodValue(mset.At(i))))
}
}
}
// Start from package-level symbols.
for _, pkg := range prog.AllPackages() {
for _, mem := range pkg.Members {
switch mem := mem.(type) {
case *ssa.Function:
// package-level function
visit(cg.CreateNode(mem))
case *ssa.Type:
// methods of package-level non-interface non-parameterized types
if !types.IsInterface(mem.Type()) {
if named, ok := mem.Type().(*types.Named); ok &&
named.TypeParams() == nil {
methodsOf(named) // T
methodsOf(types.NewPointer(named)) // *T
}
}
}
}
}
return cg
}