callgraph

Documentation

Overview

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.

Index

• Variables
• func AddEdge(caller *Node, site ssa.CallInstruction, callee *Node)
• func CalleesOf(caller *Node) map[*Node]bool
• func GraphVisitEdges(g *Graph, edge func(*Edge) error) error
• type Edge
  • func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge
  • func (e Edge) Description() string
  • func (e Edge) Pos() token.Pos
  • func (e Edge) String() string
• type Graph
  • func New(root *ssa.Function) *Graph
  • func (g *Graph) CreateNode(fn *ssa.Function) *Node
  • func (g *Graph) DeleteNode(n *Node)
  • func (g *Graph) DeleteSyntheticNodes()
  • func (g *Graph) PruneInvoke(prog *ssa.Program)
  • func (g *Graph) PruneSDK()
  • func (g *Graph) PruneSoundly()
• type Node
  • func (n *Node) String() string

Variables

var SDKList = []string{"encoding", "io", "os", "sort", "errors", "path", "strconv", "expvar", "log", "plugin", "strings",
	"cmd", "flag", "sync", "fmt", "syscall", "archive", "compress", "go", "reflect", "testdata", "container", "hash",
	"math", "regexp", "testing", "bufio", "context", "html", "mime", "text", "crypto", "image", "time", "builtin",
	"database", "index", "unicode", "bytes", "debug", "internal", "net", "runtime", "unsafe"}

Functions

func AddEdge

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

func CalleesOf(caller *Node) map[*Node]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 *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

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

func (e Edge) Description() string

func (Edge) Pos

func (e Edge) Pos() token.Pos

func (Edge) String

func (e Edge) String() string

type Graph

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

func New(root *ssa.Function) *Graph

New returns a new Graph with the specified root node.

func (*Graph) CreateNode

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

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

func (*Graph) DeleteNode

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

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".

func (*Graph) PruneInvoke

func (g *Graph) PruneInvoke(prog *ssa.Program)

PruneInvoke can make the callgraph more precise regarding interface method invoking, but it makes the callgraph no longer sound. For a CallInstruction that is of "invoke" mode, try to only reserve Out edges whose callee is in the same package as the caller. If failed to find any, then reserve that in the same package as the one defines the interface. If still failed, do nothing.

func (*Graph) PruneSDK

func (g *Graph) PruneSDK()

PruneSDK removes all In and Out Edges of a Node if its package is in Go SDK or golang.org. The Node is not deleted

func (*Graph) PruneSoundly

func (g *Graph) PruneSoundly()

PruneSoundly is aimed to make the callgraph more precise, without hurting its soundness Currently we have 2 strategies to prune the callgraph: 1. When an anonymous function does not escape, delete all In edges of it except the real one. 2. ...

type Node

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

func (n *Node) String() string