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