1// Copyright 2013 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/* 6 7Package callgraph defines the call graph and various algorithms 8and utilities to operate on it. 9 10A call graph is a labelled directed graph whose nodes represent 11functions and whose edge labels represent syntactic function call 12sites. The presence of a labelled edge (caller, site, callee) 13indicates that caller may call callee at the specified call site. 14 15A call graph is a multigraph: it may contain multiple edges (caller, 16*, callee) connecting the same pair of nodes, so long as the edges 17differ by label; this occurs when one function calls another function 18from multiple call sites. Also, it may contain multiple edges 19(caller, site, *) that differ only by callee; this indicates a 20polymorphic call. 21 22A SOUND call graph is one that overapproximates the dynamic calling 23behaviors of the program in all possible executions. One call graph 24is more PRECISE than another if it is a smaller overapproximation of 25the dynamic behavior. 26 27All call graphs have a synthetic root node which is responsible for 28calling main() and init(). 29 30Calls to built-in functions (e.g. panic, println) are not represented 31in the call graph; they are treated like built-in operators of the 32language. 33 34*/ 35package callgraph // import "golang.org/x/tools/go/callgraph" 36 37// TODO(adonovan): add a function to eliminate wrappers from the 38// callgraph, preserving topology. 39// More generally, we could eliminate "uninteresting" nodes such as 40// nodes from packages we don't care about. 41 42import ( 43 "fmt" 44 "go/token" 45 46 "golang.org/x/tools/go/ssa" 47) 48 49// A Graph represents a call graph. 50// 51// A graph may contain nodes that are not reachable from the root. 52// If the call graph is sound, such nodes indicate unreachable 53// functions. 54// 55type Graph struct { 56 Root *Node // the distinguished root node 57 Nodes map[*ssa.Function]*Node // all nodes by function 58} 59 60// New returns a new Graph with the specified root node. 61func New(root *ssa.Function) *Graph { 62 g := &Graph{Nodes: make(map[*ssa.Function]*Node)} 63 g.Root = g.CreateNode(root) 64 return g 65} 66 67// CreateNode returns the Node for fn, creating it if not present. 68func (g *Graph) CreateNode(fn *ssa.Function) *Node { 69 n, ok := g.Nodes[fn] 70 if !ok { 71 n = &Node{Func: fn, ID: len(g.Nodes)} 72 g.Nodes[fn] = n 73 } 74 return n 75} 76 77// A Node represents a node in a call graph. 78type Node struct { 79 Func *ssa.Function // the function this node represents 80 ID int // 0-based sequence number 81 In []*Edge // unordered set of incoming call edges (n.In[*].Callee == n) 82 Out []*Edge // unordered set of outgoing call edges (n.Out[*].Caller == n) 83} 84 85func (n *Node) String() string { 86 return fmt.Sprintf("n%d:%s", n.ID, n.Func) 87} 88 89// A Edge represents an edge in the call graph. 90// 91// Site is nil for edges originating in synthetic or intrinsic 92// functions, e.g. reflect.Call or the root of the call graph. 93type Edge struct { 94 Caller *Node 95 Site ssa.CallInstruction 96 Callee *Node 97} 98 99func (e Edge) String() string { 100 return fmt.Sprintf("%s --> %s", e.Caller, e.Callee) 101} 102 103func (e Edge) Description() string { 104 var prefix string 105 switch e.Site.(type) { 106 case nil: 107 return "synthetic call" 108 case *ssa.Go: 109 prefix = "concurrent " 110 case *ssa.Defer: 111 prefix = "deferred " 112 } 113 return prefix + e.Site.Common().Description() 114} 115 116func (e Edge) Pos() token.Pos { 117 if e.Site == nil { 118 return token.NoPos 119 } 120 return e.Site.Pos() 121} 122 123// AddEdge adds the edge (caller, site, callee) to the call graph. 124// Elimination of duplicate edges is the caller's responsibility. 125func AddEdge(caller *Node, site ssa.CallInstruction, callee *Node) { 126 e := &Edge{caller, site, callee} 127 callee.In = append(callee.In, e) 128 caller.Out = append(caller.Out, e) 129} 130