src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

callgraph.go (3795B)

      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(zpavlinovic): decide how callgraphs handle calls to and from generic function bodies.
     36 
     37 import (
     38 	"fmt"
     39 	"go/token"
     40 
     41 	"golang.org/x/tools/go/ssa"
     42 )
     43 
     44 // A Graph represents a call graph.
     45 //
     46 // A graph may contain nodes that are not reachable from the root.
     47 // If the call graph is sound, such nodes indicate unreachable
     48 // functions.
     49 type Graph struct {
     50 	Root  *Node                   // the distinguished root node (Root.Func may be nil)
     51 	Nodes map[*ssa.Function]*Node // all nodes by function
     52 }
     53 
     54 // New returns a new Graph with the specified (optional) root node.
     55 func New(root *ssa.Function) *Graph {
     56 	g := &Graph{Nodes: make(map[*ssa.Function]*Node)}
     57 	g.Root = g.CreateNode(root)
     58 	return g
     59 }
     60 
     61 // CreateNode returns the Node for fn, creating it if not present.
     62 // The root node may have fn=nil.
     63 func (g *Graph) CreateNode(fn *ssa.Function) *Node {
     64 	n, ok := g.Nodes[fn]
     65 	if !ok {
     66 		n = &Node{Func: fn, ID: len(g.Nodes)}
     67 		g.Nodes[fn] = n
     68 	}
     69 	return n
     70 }
     71 
     72 // A Node represents a node in a call graph.
     73 type Node struct {
     74 	Func *ssa.Function // the function this node represents
     75 	ID   int           // 0-based sequence number
     76 	In   []*Edge       // unordered set of incoming call edges (n.In[*].Callee == n)
     77 	Out  []*Edge       // unordered set of outgoing call edges (n.Out[*].Caller == n)
     78 }
     79 
     80 func (n *Node) String() string {
     81 	return fmt.Sprintf("n%d:%s", n.ID, n.Func)
     82 }
     83 
     84 // A Edge represents an edge in the call graph.
     85 //
     86 // Site is nil for edges originating in synthetic or intrinsic
     87 // functions, e.g. reflect.Value.Call or the root of the call graph.
     88 type Edge struct {
     89 	Caller *Node
     90 	Site   ssa.CallInstruction
     91 	Callee *Node
     92 }
     93 
     94 func (e Edge) String() string {
     95 	return fmt.Sprintf("%s --> %s", e.Caller, e.Callee)
     96 }
     97 
     98 func (e Edge) Description() string {
     99 	var prefix string
    100 	switch e.Site.(type) {
    101 	case nil:
    102 		return "synthetic call"
    103 	case *ssa.Go:
    104 		prefix = "concurrent "
    105 	case *ssa.Defer:
    106 		prefix = "deferred "
    107 	}
    108 	return prefix + e.Site.Common().Description()
    109 }
    110 
    111 func (e Edge) Pos() token.Pos {
    112 	if e.Site == nil {
    113 		return token.NoPos
    114 	}
    115 	return e.Site.Pos()
    116 }
    117 
    118 // AddEdge adds the edge (caller, site, callee) to the call graph.
    119 // Elimination of duplicate edges is the caller's responsibility.
    120 func AddEdge(caller *Node, site ssa.CallInstruction, callee *Node) {
    121 	e := &Edge{caller, site, callee}
    122 	callee.In = append(callee.In, e)
    123 	caller.Out = append(caller.Out, e)
    124 }