summaryrefslogtreecommitdiffhomepage
path: root/vendor/golang.org/x/tools/go/callgraph
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/golang.org/x/tools/go/callgraph')
-rw-r--r--vendor/golang.org/x/tools/go/callgraph/callgraph.go129
-rw-r--r--vendor/golang.org/x/tools/go/callgraph/cha/cha.go164
-rw-r--r--vendor/golang.org/x/tools/go/callgraph/util.go180
3 files changed, 473 insertions, 0 deletions
diff --git a/vendor/golang.org/x/tools/go/callgraph/callgraph.go b/vendor/golang.org/x/tools/go/callgraph/callgraph.go
new file mode 100644
index 0000000..a1b0ca5
--- /dev/null
+++ b/vendor/golang.org/x/tools/go/callgraph/callgraph.go
@@ -0,0 +1,129 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+/*
+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 callgraph // import "golang.org/x/tools/go/callgraph"
+
+// TODO(adonovan): add a function to eliminate wrappers from the
+// callgraph, preserving topology.
+// More generally, we could eliminate "uninteresting" nodes such as
+// nodes from packages we don't care about.
+
+// TODO(zpavlinovic): decide how callgraphs handle calls to and from generic function bodies.
+
+import (
+ "fmt"
+ "go/token"
+
+ "golang.org/x/tools/go/ssa"
+)
+
+// 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 Graph struct {
+ Root *Node // the distinguished root node
+ Nodes map[*ssa.Function]*Node // all nodes by function
+}
+
+// New returns a new Graph with the specified root node.
+func New(root *ssa.Function) *Graph {
+ g := &Graph{Nodes: make(map[*ssa.Function]*Node)}
+ g.Root = g.CreateNode(root)
+ return g
+}
+
+// CreateNode returns the Node for fn, creating it if not present.
+// The root node may have fn=nil.
+func (g *Graph) CreateNode(fn *ssa.Function) *Node {
+ n, ok := g.Nodes[fn]
+ if !ok {
+ n = &Node{Func: fn, ID: len(g.Nodes)}
+ g.Nodes[fn] = n
+ }
+ return n
+}
+
+// A Node represents a node in a call graph.
+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)
+}
+
+func (n *Node) String() string {
+ return fmt.Sprintf("n%d:%s", n.ID, n.Func)
+}
+
+// A Edge represents an edge in the call graph.
+//
+// Site is nil for edges originating in synthetic or intrinsic
+// functions, e.g. reflect.Value.Call or the root of the call graph.
+type Edge struct {
+ Caller *Node
+ Site ssa.CallInstruction
+ Callee *Node
+}
+
+func (e Edge) String() string {
+ return fmt.Sprintf("%s --> %s", e.Caller, e.Callee)
+}
+
+func (e Edge) Description() string {
+ var prefix string
+ switch e.Site.(type) {
+ case nil:
+ return "synthetic call"
+ case *ssa.Go:
+ prefix = "concurrent "
+ case *ssa.Defer:
+ prefix = "deferred "
+ }
+ return prefix + e.Site.Common().Description()
+}
+
+func (e Edge) Pos() token.Pos {
+ if e.Site == nil {
+ return token.NoPos
+ }
+ return e.Site.Pos()
+}
+
+// AddEdge adds the edge (caller, site, callee) to the call graph.
+// Elimination of duplicate edges is the caller's responsibility.
+func AddEdge(caller *Node, site ssa.CallInstruction, callee *Node) {
+ e := &Edge{caller, site, callee}
+ callee.In = append(callee.In, e)
+ caller.Out = append(caller.Out, e)
+}
diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/cha.go b/vendor/golang.org/x/tools/go/callgraph/cha/cha.go
new file mode 100644
index 0000000..3040f3d
--- /dev/null
+++ b/vendor/golang.org/x/tools/go/callgraph/cha/cha.go
@@ -0,0 +1,164 @@
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package cha computes the call graph of a Go program using the Class
+// Hierarchy Analysis (CHA) algorithm.
+//
+// CHA was first described in "Optimization of Object-Oriented Programs
+// Using Static Class Hierarchy Analysis", Jeffrey Dean, David Grove,
+// and Craig Chambers, ECOOP'95.
+//
+// CHA is related to RTA (see go/callgraph/rta); the difference is that
+// CHA conservatively computes the entire "implements" relation between
+// interfaces and concrete types ahead of time, whereas RTA uses dynamic
+// programming to construct it on the fly as it encounters new functions
+// reachable from main. CHA may thus include spurious call edges for
+// types that haven't been instantiated yet, or types that are never
+// instantiated.
+//
+// Since CHA conservatively assumes that all functions are address-taken
+// and all concrete types are put into interfaces, it is sound to run on
+// partial programs, such as libraries without a main or test function.
+package cha // import "golang.org/x/tools/go/callgraph/cha"
+
+// TODO(zpavlinovic): update CHA for how it handles generic function bodies.
+
+import (
+ "go/types"
+
+ "golang.org/x/tools/go/callgraph"
+ "golang.org/x/tools/go/ssa"
+ "golang.org/x/tools/go/ssa/ssautil"
+ "golang.org/x/tools/go/types/typeutil"
+)
+
+// CallGraph computes the call graph of the specified program using the
+// Class Hierarchy Analysis algorithm.
+func CallGraph(prog *ssa.Program) *callgraph.Graph {
+ cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
+
+ allFuncs := ssautil.AllFunctions(prog)
+
+ calleesOf := lazyCallees(allFuncs)
+
+ addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) {
+ gnode := cg.CreateNode(g)
+ callgraph.AddEdge(fnode, site, gnode)
+ }
+
+ addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) {
+ // Because every call to a highly polymorphic and
+ // frequently used abstract method such as
+ // (io.Writer).Write is assumed to call every concrete
+ // Write method in the program, the call graph can
+ // contain a lot of duplication.
+ //
+ // TODO(taking): opt: consider making lazyCallees public.
+ // Using the same benchmarks as callgraph_test.go, removing just
+ // the explicit callgraph.Graph construction is 4x less memory
+ // and is 37% faster.
+ // CHA 86 ms/op 16 MB/op
+ // lazyCallees 63 ms/op 4 MB/op
+ for _, g := range callees {
+ addEdge(fnode, site, g)
+ }
+ }
+
+ for f := range allFuncs {
+ fnode := cg.CreateNode(f)
+ for _, b := range f.Blocks {
+ for _, instr := range b.Instrs {
+ if site, ok := instr.(ssa.CallInstruction); ok {
+ if g := site.Common().StaticCallee(); g != nil {
+ addEdge(fnode, site, g)
+ } else {
+ addEdges(fnode, site, calleesOf(site))
+ }
+ }
+ }
+ }
+ }
+
+ return cg
+}
+
+// lazyCallees returns a function that maps a call site (in a function in fns)
+// to its callees within fns.
+//
+// The resulting function is not concurrency safe.
+func lazyCallees(fns map[*ssa.Function]bool) func(site ssa.CallInstruction) []*ssa.Function {
+ // funcsBySig contains all functions, keyed by signature. It is
+ // the effective set of address-taken functions used to resolve
+ // a dynamic call of a particular signature.
+ var funcsBySig typeutil.Map // value is []*ssa.Function
+
+ // methodsByID contains all methods, grouped by ID for efficient
+ // lookup.
+ //
+ // We must key by ID, not name, for correct resolution of interface
+ // calls to a type with two (unexported) methods spelled the same but
+ // from different packages. The fact that the concrete type implements
+ // the interface does not mean the call dispatches to both methods.
+ methodsByID := make(map[string][]*ssa.Function)
+
+ // An imethod represents an interface method I.m.
+ // (There's no go/types object for it;
+ // a *types.Func may be shared by many interfaces due to interface embedding.)
+ type imethod struct {
+ I *types.Interface
+ id string
+ }
+ // methodsMemo records, for every abstract method call I.m on
+ // interface type I, the set of concrete methods C.m of all
+ // types C that satisfy interface I.
+ //
+ // Abstract methods may be shared by several interfaces,
+ // hence we must pass I explicitly, not guess from m.
+ //
+ // methodsMemo is just a cache, so it needn't be a typeutil.Map.
+ methodsMemo := make(map[imethod][]*ssa.Function)
+ lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function {
+ id := m.Id()
+ methods, ok := methodsMemo[imethod{I, id}]
+ if !ok {
+ for _, f := range methodsByID[id] {
+ C := f.Signature.Recv().Type() // named or *named
+ if types.Implements(C, I) {
+ methods = append(methods, f)
+ }
+ }
+ methodsMemo[imethod{I, id}] = methods
+ }
+ return methods
+ }
+
+ for f := range fns {
+ if f.Signature.Recv() == nil {
+ // Package initializers can never be address-taken.
+ if f.Name() == "init" && f.Synthetic == "package initializer" {
+ continue
+ }
+ funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function)
+ funcs = append(funcs, f)
+ funcsBySig.Set(f.Signature, funcs)
+ } else if obj := f.Object(); obj != nil {
+ id := obj.(*types.Func).Id()
+ methodsByID[id] = append(methodsByID[id], f)
+ }
+ }
+
+ return func(site ssa.CallInstruction) []*ssa.Function {
+ call := site.Common()
+ if call.IsInvoke() {
+ tiface := call.Value.Type().Underlying().(*types.Interface)
+ return lookupMethods(tiface, call.Method)
+ } else if g := call.StaticCallee(); g != nil {
+ return []*ssa.Function{g}
+ } else if _, ok := call.Value.(*ssa.Builtin); !ok {
+ fns, _ := funcsBySig.At(call.Signature()).([]*ssa.Function)
+ return fns
+ }
+ return nil
+ }
+}
diff --git a/vendor/golang.org/x/tools/go/callgraph/util.go b/vendor/golang.org/x/tools/go/callgraph/util.go
new file mode 100644
index 0000000..5499320
--- /dev/null
+++ b/vendor/golang.org/x/tools/go/callgraph/util.go
@@ -0,0 +1,180 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package callgraph
+
+import "golang.org/x/tools/go/ssa"
+
+// This file provides various utilities over call graphs, such as
+// visitation and path search.
+
+// CalleesOf returns a new set containing all direct callees of the
+// caller node.
+func CalleesOf(caller *Node) map[*Node]bool {
+ callees := make(map[*Node]bool)
+ for _, e := range caller.Out {
+ callees[e.Callee] = true
+ }
+ return callees
+}
+
+// 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.
+func GraphVisitEdges(g *Graph, edge func(*Edge) error) error {
+ seen := make(map[*Node]bool)
+ var visit func(n *Node) error
+ visit = func(n *Node) error {
+ if !seen[n] {
+ seen[n] = true
+ for _, e := range n.Out {
+ if err := visit(e.Callee); err != nil {
+ return err
+ }
+ if err := edge(e); err != nil {
+ return err
+ }
+ }
+ }
+ return nil
+ }
+ for _, n := range g.Nodes {
+ if err := visit(n); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// 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 PathSearch(start *Node, isEnd func(*Node) bool) []*Edge {
+ stack := make([]*Edge, 0, 32)
+ seen := make(map[*Node]bool)
+ var search func(n *Node) []*Edge
+ search = func(n *Node) []*Edge {
+ if !seen[n] {
+ seen[n] = true
+ if isEnd(n) {
+ return stack
+ }
+ for _, e := range n.Out {
+ stack = append(stack, e) // push
+ if found := search(e.Callee); found != nil {
+ return found
+ }
+ stack = stack[:len(stack)-1] // pop
+ }
+ }
+ return nil
+ }
+ return search(start)
+}
+
+// DeleteSyntheticNodes removes from call graph g all nodes for
+// functions that do not correspond to source syntax. For historical
+// reasons, nodes for g.Root and package initializers are always
+// kept.
+//
+// As nodes are removed, edges are created to preserve the
+// reachability relation of the remaining nodes.
+func (g *Graph) DeleteSyntheticNodes() {
+ // Measurements on the standard library and go.tools show that
+ // resulting graph has ~15% fewer nodes and 4-8% fewer edges
+ // than the input.
+ //
+ // Inlining a wrapper of in-degree m, out-degree n adds m*n
+ // and removes m+n edges. Since most wrappers are monomorphic
+ // (n=1) this results in a slight reduction. Polymorphic
+ // wrappers (n>1), e.g. from embedding an interface value
+ // inside a struct to satisfy some interface, cause an
+ // increase in the graph, but they seem to be uncommon.
+
+ // Hash all existing edges to avoid creating duplicates.
+ edges := make(map[Edge]bool)
+ for _, cgn := range g.Nodes {
+ for _, e := range cgn.Out {
+ edges[*e] = true
+ }
+ }
+ for fn, cgn := range g.Nodes {
+ if cgn == g.Root || isInit(cgn.Func) || fn.Syntax() != nil {
+ continue // keep
+ }
+ for _, eIn := range cgn.In {
+ for _, eOut := range cgn.Out {
+ newEdge := Edge{eIn.Caller, eIn.Site, eOut.Callee}
+ if edges[newEdge] {
+ continue // don't add duplicate
+ }
+ AddEdge(eIn.Caller, eIn.Site, eOut.Callee)
+ edges[newEdge] = true
+ }
+ }
+ g.DeleteNode(cgn)
+ }
+}
+
+func isInit(fn *ssa.Function) bool {
+ return fn.Pkg != nil && fn.Pkg.Func("init") == fn
+}
+
+// DeleteNode removes node n and its edges from the graph g.
+// (NB: not efficient for batch deletion.)
+func (g *Graph) DeleteNode(n *Node) {
+ n.deleteIns()
+ n.deleteOuts()
+ delete(g.Nodes, n.Func)
+}
+
+// deleteIns deletes all incoming edges to n.
+func (n *Node) deleteIns() {
+ for _, e := range n.In {
+ removeOutEdge(e)
+ }
+ n.In = nil
+}
+
+// deleteOuts deletes all outgoing edges from n.
+func (n *Node) deleteOuts() {
+ for _, e := range n.Out {
+ removeInEdge(e)
+ }
+ n.Out = nil
+}
+
+// removeOutEdge removes edge.Caller's outgoing edge 'edge'.
+func removeOutEdge(edge *Edge) {
+ caller := edge.Caller
+ n := len(caller.Out)
+ for i, e := range caller.Out {
+ if e == edge {
+ // Replace it with the final element and shrink the slice.
+ caller.Out[i] = caller.Out[n-1]
+ caller.Out[n-1] = nil // aid GC
+ caller.Out = caller.Out[:n-1]
+ return
+ }
+ }
+ panic("edge not found: " + edge.String())
+}
+
+// removeInEdge removes edge.Callee's incoming edge 'edge'.
+func removeInEdge(edge *Edge) {
+ caller := edge.Callee
+ n := len(caller.In)
+ for i, e := range caller.In {
+ if e == edge {
+ // Replace it with the final element and shrink the slice.
+ caller.In[i] = caller.In[n-1]
+ caller.In[n-1] = nil // aid GC
+ caller.In = caller.In[:n-1]
+ return
+ }
+ }
+ panic("edge not found: " + edge.String())
+}