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