tools: Index | Files | Directories

package callgraph

import ""

Package callgraph defines the call graph and various algorithms and utilities to operate on it.

A call graph is a labelled directed graph whose nodes represent functions and whose edge labels represent syntactic function call sites. The presence of a labelled edge (caller, site, callee) indicates that caller may call callee at the specified call site.

A call graph is a multigraph: it may contain multiple edges (caller, *, callee) connecting the same pair of nodes, so long as the edges differ by label; this occurs when one function calls another function from multiple call sites. Also, it may contain multiple edges (caller, site, *) that differ only by callee; this indicates a polymorphic call.

A SOUND call graph is one that overapproximates the dynamic calling behaviors of the program in all possible executions. One call graph is more PRECISE than another if it is a smaller overapproximation of the dynamic behavior.

All call graphs have a synthetic root node which is responsible for calling main() and init().

Calls to built-in functions (e.g. panic, println) are not represented in the call graph; they are treated like built-in operators of the language.


Package Files

callgraph.go util.go

func AddEdge Uses

func AddEdge(caller *Node, site ssa.CallInstruction, callee *Node)

AddEdge adds the edge (caller, site, callee) to the call graph. Elimination of duplicate edges is the caller's responsibility.

func CalleesOf Uses

func CalleesOf(caller *Node) map[*Node]bool

CalleesOf returns a new set containing all direct callees of the caller node.

func GraphVisitEdges Uses

func GraphVisitEdges(g *Graph, edge func(*Edge) error) error

GraphVisitEdges visits all the edges in graph g in depth-first order. The edge function is called for each edge in postorder. If it returns non-nil, visitation stops and GraphVisitEdges returns that value.

type Edge Uses

type Edge struct {
    Caller *Node
    Site   ssa.CallInstruction
    Callee *Node

A Edge represents an edge in the call graph.

Site is nil for edges originating in synthetic or intrinsic functions, e.g. reflect.Call or the root of the call graph.

func PathSearch Uses

func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge

PathSearch finds an arbitrary path starting at node start and ending at some node for which isEnd() returns true. On success, PathSearch returns the path as an ordered list of edges; on failure, it returns nil.

func (Edge) Description Uses

func (e Edge) Description() string

func (Edge) Pos Uses

func (e Edge) Pos() token.Pos

func (Edge) String Uses

func (e Edge) String() string

type Graph Uses

type Graph struct {
    Root  *Node                   // the distinguished root node
    Nodes map[*ssa.Function]*Node // all nodes by function

A Graph represents a call graph.

A graph may contain nodes that are not reachable from the root. If the call graph is sound, such nodes indicate unreachable functions.

func New Uses

func New(root *ssa.Function) *Graph

New returns a new Graph with the specified root node.

func (*Graph) CreateNode Uses

func (g *Graph) CreateNode(fn *ssa.Function) *Node

CreateNode returns the Node for fn, creating it if not present.

func (*Graph) DeleteNode Uses

func (g *Graph) DeleteNode(n *Node)

DeleteNode removes node n and its edges from the graph g. (NB: not efficient for batch deletion.)

func (*Graph) DeleteSyntheticNodes Uses

func (g *Graph) DeleteSyntheticNodes()

DeleteSyntheticNodes removes from call graph g all nodes for synthetic functions (except g.Root and package initializers), preserving the topology. In effect, calls to synthetic wrappers are "inlined".

type Node Uses

type Node struct {
    Func *ssa.Function // the function this node represents
    ID   int           // 0-based sequence number
    In   []*Edge       // unordered set of incoming call edges (n.In[*].Callee == n)
    Out  []*Edge       // unordered set of outgoing call edges (n.Out[*].Caller == n)

A Node represents a node in a call graph.

func (*Node) String Uses

func (n *Node) String() string


chaPackage cha computes the call graph of a Go program using the Class Hierarchy Analysis (CHA) algorithm.
rtaThis package provides Rapid Type Analysis (RTA) for Go, a fast algorithm for call graph construction and discovery of reachable code (and hence dead code) and runtime types.
staticPackage static computes the call graph of a Go program containing only static call edges.

Package callgraph imports 3 packages (graph) and is imported by 45 packages. Updated 2020-10-20. Refresh now. Tools for package owners.