.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/go/callgraph/callgraph.go

   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
   7 Package callgraph defines the call graph and various algorithms
   8 and utilities to operate on it.
   9
  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.
  14
  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
  20 polymorphic call.
  21
  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
  25 the dynamic behavior.
  26
  27 All call graphs have a synthetic root node which is responsible for
  28 calling main() and init().
  29
  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
  32 language.
  33
  34 */
  35 package 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
  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 //
  55 type 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.
  61 func 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.
  68 func (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.
  78 type 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
  85 func (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.
  93 type Edge struct {
  94         Caller *Node
  95         Site   ssa.CallInstruction
  96         Callee *Node
  97 }
  98
  99 func (e Edge) String() string {
 100         return fmt.Sprintf("%s --> %s", e.Caller, e.Callee)
 101 }
 102
 103 func (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
 116 func (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.
 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)
 129 }