call

Documentation

Overview

Package call defines the call graph abstraction and various algorithms and utilities to operate on it. It does not provide a concrete implementation but permits other analyses (such as pointer analyses or Rapid Type Analysis) to expose their own call graphs in a representation-independent manner.

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 call graph is called CONTEXT INSENSITIVE if no two nodes in N represent the same syntactic function declaration, i.e. the set of nodes and the set of syntactic functions are in one-to-one correspondence.

A context-sensitive call graph may have multiple nodes corresponding to the same function; this may yield a more precise approximation to the calling behavior of the program. Consider this program:

func Apply(fn func(V), value V) { fn(value) }
Apply(F, v1)
...
Apply(G, v2)

A context-insensitive call graph would represent all calls to Apply by the same node, so that node would have successors F and G. A context-sensitive call graph might represent the first and second calls to Apply by distinct nodes, so that the first would have successor F and the second would have successor G. This is a more precise representation of the possible behaviors of the program.

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.

Index

• func CalleesOf(caller GraphNode) map[GraphNode]bool
• func GraphVisitEdges(g Graph, edge func(Edge) error) error
• type Edge
  • func PathSearch(start GraphNode, isEnd func(GraphNode) bool) []Edge
• type Graph
• type GraphNode

Functions

func CalleesOf

func CalleesOf(caller GraphNode) map[GraphNode]bool

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

func GraphVisitEdges

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.

Types

type Edge

type Edge struct {
	Caller GraphNode
	Site   ssa.CallInstruction
	Callee GraphNode
}

A Edge represents an edge in the call graph.

func PathSearch

func PathSearch(start GraphNode, isEnd func(GraphNode) 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.

type Graph

type Graph interface {
	Root() GraphNode    // the distinguished root node
	Nodes() []GraphNode // new unordered set of all nodes
}

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.

type GraphNode

type GraphNode interface {
	Func() *ssa.Function          // the function this node represents
	Sites() []ssa.CallInstruction // new unordered set of call sites within this function
	Edges() []Edge                // new unordered set of outgoing edges
}

A GraphNode represents a node in a call graph.

If the call graph is context sensitive, there may be multiple GraphNodes with the same Func(); the identity of the graph node indicates the context.

Sites returns the set of syntactic call sites within this function.

For nodes representing synthetic or intrinsic functions (e.g. reflect.Call, or the root of the call graph), Sites() returns a slice containing a single nil value to indicate the synthetic call site, and each edge in Edges() has a nil Site.

All nodes "belong" to a single graph and must not be mixed with nodes belonging to another graph.

A site may appear in Sites() but not in {e.Site | e ∈ Edges()}. This indicates that that caller node was unreachable, or that the call was dynamic yet no func or interface values flow to the call site.

Clients should not mutate the node via the results of its methods.