| 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 |
Members