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.
7 Package callgraph defines the call graph and various algorithms
8 and utilities to operate on it.
10 A call graph is a labelled directed graph whose nodes represent
11 functions and whose edge labels represent syntactic function call
12 sites. The presence of a labelled edge (caller, site, callee)
13 indicates that caller may call callee at the specified call site.
15 A call graph is a multigraph: it may contain multiple edges (caller,
16 *, callee) connecting the same pair of nodes, so long as the edges
17 differ by label; this occurs when one function calls another function
18 from multiple call sites. Also, it may contain multiple edges
19 (caller, site, *) that differ only by callee; this indicates a
22 A SOUND call graph is one that overapproximates the dynamic calling
23 behaviors of the program in all possible executions. One call graph
24 is more PRECISE than another if it is a smaller overapproximation of
27 All call graphs have a synthetic root node which is responsible for
28 calling main() and init().
30 Calls to built-in functions (e.g. panic, println) are not represented
31 in the call graph; they are treated like built-in operators of the
35 package callgraph // import "golang.org/x/tools/go/callgraph"
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.
46 "golang.org/x/tools/go/ssa"
49 // A Graph represents a call graph.
51 // A graph may contain nodes that are not reachable from the root.
52 // If the call graph is sound, such nodes indicate unreachable
56 Root *Node // the distinguished root node
57 Nodes map[*ssa.Function]*Node // all nodes by function
60 // New returns a new Graph with the specified root node.
61 func New(root *ssa.Function) *Graph {
62 g := &Graph{Nodes: make(map[*ssa.Function]*Node)}
63 g.Root = g.CreateNode(root)
67 // CreateNode returns the Node for fn, creating it if not present.
68 func (g *Graph) CreateNode(fn *ssa.Function) *Node {
71 n = &Node{Func: fn, ID: len(g.Nodes)}
77 // A Node represents a node in a call graph.
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)
85 func (n *Node) String() string {
86 return fmt.Sprintf("n%d:%s", n.ID, n.Func)
89 // A Edge represents an edge in the call graph.
91 // Site is nil for edges originating in synthetic or intrinsic
92 // functions, e.g. reflect.Call or the root of the call graph.
95 Site ssa.CallInstruction
99 func (e Edge) String() string {
100 return fmt.Sprintf("%s --> %s", e.Caller, e.Callee)
103 func (e Edge) Description() string {
105 switch e.Site.(type) {
107 return "synthetic call"
109 prefix = "concurrent "
113 return prefix + e.Site.Common().Description()
116 func (e Edge) Pos() token.Pos {
123 // AddEdge adds the edge (caller, site, callee) to the call graph.
124 // Elimination of duplicate edges is the caller's responsibility.
125 func 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)