diff options
Diffstat (limited to 'vendor/golang.org/x/tools/go/callgraph')
8 files changed, 723 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..707a319 --- /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. + +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. +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.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..215ff17 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/cha.go @@ -0,0 +1,139 @@ +// 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" + +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) + + // 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 + + // methodsByName contains all methods, + // grouped by name for efficient lookup. + // (methodsById would be better but not every SSA method has a go/types ID.) + methodsByName := 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 methodsByName[m.Name()] { + 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 allFuncs { + 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 { + methodsByName[f.Name()] = append(methodsByName[f.Name()], f) + } + } + + 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(adonovan): opt: consider factoring the callgraph + // API so that the Callers component of each edge is a + // slice of nodes, not a singleton. + 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 { + call := site.Common() + if call.IsInvoke() { + tiface := call.Value.Type().Underlying().(*types.Interface) + addEdges(fnode, site, lookupMethods(tiface, call.Method)) + } else if g := call.StaticCallee(); g != nil { + addEdge(fnode, site, g) + } else if _, ok := call.Value.(*ssa.Builtin); !ok { + callees, _ := funcsBySig.At(call.Signature()).([]*ssa.Function) + addEdges(fnode, site, callees) + } + } + } + } + } + + return cg +} diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/cha_test.go b/vendor/golang.org/x/tools/go/callgraph/cha/cha_test.go new file mode 100644 index 0000000..cb2d585 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/cha_test.go @@ -0,0 +1,111 @@ +// 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. + +// No testdata on Android. + +// +build !android + +package cha_test + +import ( + "bytes" + "fmt" + "go/ast" + "go/parser" + "go/token" + "go/types" + "io/ioutil" + "sort" + "strings" + "testing" + + "golang.org/x/tools/go/callgraph" + "golang.org/x/tools/go/callgraph/cha" + "golang.org/x/tools/go/loader" + "golang.org/x/tools/go/ssa/ssautil" +) + +var inputs = []string{ + "testdata/func.go", + "testdata/iface.go", + "testdata/recv.go", + "testdata/issue23925.go", +} + +func expectation(f *ast.File) (string, token.Pos) { + for _, c := range f.Comments { + text := strings.TrimSpace(c.Text()) + if t := strings.TrimPrefix(text, "WANT:\n"); t != text { + return t, c.Pos() + } + } + return "", token.NoPos +} + +// TestCHA runs CHA on each file in inputs, prints the dynamic edges of +// the call graph, and compares it with the golden results embedded in +// the WANT comment at the end of the file. +// +func TestCHA(t *testing.T) { + for _, filename := range inputs { + content, err := ioutil.ReadFile(filename) + if err != nil { + t.Errorf("couldn't read file '%s': %s", filename, err) + continue + } + + conf := loader.Config{ + ParserMode: parser.ParseComments, + } + f, err := conf.ParseFile(filename, content) + if err != nil { + t.Error(err) + continue + } + + want, pos := expectation(f) + if pos == token.NoPos { + t.Errorf("No WANT: comment in %s", filename) + continue + } + + conf.CreateFromFiles("main", f) + iprog, err := conf.Load() + if err != nil { + t.Error(err) + continue + } + + prog := ssautil.CreateProgram(iprog, 0) + mainPkg := prog.Package(iprog.Created[0].Pkg) + prog.Build() + + cg := cha.CallGraph(prog) + + if got := printGraph(cg, mainPkg.Pkg); got != want { + t.Errorf("%s: got:\n%s\nwant:\n%s", + prog.Fset.Position(pos), got, want) + } + } +} + +func printGraph(cg *callgraph.Graph, from *types.Package) string { + var edges []string + callgraph.GraphVisitEdges(cg, func(e *callgraph.Edge) error { + if strings.Contains(e.Description(), "dynamic") { + edges = append(edges, fmt.Sprintf("%s --> %s", + e.Caller.Func.RelString(from), + e.Callee.Func.RelString(from))) + } + return nil + }) + sort.Strings(edges) + + var buf bytes.Buffer + buf.WriteString("Dynamic calls\n") + for _, edge := range edges { + fmt.Fprintf(&buf, " %s\n", edge) + } + return strings.TrimSpace(buf.String()) +} diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/func.go b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/func.go new file mode 100644 index 0000000..ad483f1 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/func.go @@ -0,0 +1,23 @@ +//+build ignore + +package main + +// Test of dynamic function calls; no interfaces. + +func A(int) {} + +var ( + B = func(int) {} + C = func(int) {} +) + +func f() { + pfn := B + pfn(0) // calls A, B, C, even though A is not even address-taken +} + +// WANT: +// Dynamic calls +// f --> A +// f --> init$1 +// f --> init$2 diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/iface.go b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/iface.go new file mode 100644 index 0000000..1622ec1 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/iface.go @@ -0,0 +1,65 @@ +//+build ignore + +package main + +// Test of interface calls. None of the concrete types are ever +// instantiated or converted to interfaces. + +type I interface { + f() +} + +type J interface { + f() + g() +} + +type C int // implements I + +func (*C) f() + +type D int // implements I and J + +func (*D) f() +func (*D) g() + +func one(i I, j J) { + i.f() // calls *C and *D +} + +func two(i I, j J) { + j.f() // calls *D (but not *C, even though it defines method f) +} + +func three(i I, j J) { + j.g() // calls *D +} + +func four(i I, j J) { + Jf := J.f + if unknown { + Jf = nil // suppress SSA constant propagation + } + Jf(nil) // calls *D +} + +func five(i I, j J) { + jf := j.f + if unknown { + jf = nil // suppress SSA constant propagation + } + jf() // calls *D +} + +var unknown bool + +// WANT: +// Dynamic calls +// (J).f$bound --> (*D).f +// (J).f$thunk --> (*D).f +// five --> (J).f$bound +// four --> (J).f$thunk +// one --> (*C).f +// one --> (*D).f +// three --> (*D).g +// two --> (*D).f diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/issue23925.go b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/issue23925.go new file mode 100644 index 0000000..59eaf18 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/issue23925.go @@ -0,0 +1,38 @@ +package main + +// Regression test for https://github.com/golang/go/issues/23925 + +type stringFlagImpl string + +func (*stringFlagImpl) Set(s string) error { return nil } + +type boolFlagImpl bool + +func (*boolFlagImpl) Set(s string) error { return nil } +func (*boolFlagImpl) extra() {} + +// A copy of flag.boolFlag interface, without a dependency. +// Must appear first, so that it becomes the owner of the Set methods. +type boolFlag interface { + flagValue + extra() +} + +// A copy of flag.Value, without adding a dependency. +type flagValue interface { + Set(string) error +} + +func main() { + var x flagValue = new(stringFlagImpl) + x.Set("") + + var y boolFlag = new(boolFlagImpl) + y.Set("") +} + +// WANT: +// Dynamic calls +// main --> (*boolFlagImpl).Set +// main --> (*boolFlagImpl).Set +// main --> (*stringFlagImpl).Set diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/recv.go b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/recv.go new file mode 100644 index 0000000..5ba48e9 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/testdata/recv.go @@ -0,0 +1,37 @@ +//+build ignore + +package main + +type I interface { + f() +} + +type J interface { + g() +} + +type C int // C and *C implement I; *C implements J + +func (C) f() +func (*C) g() + +type D int // *D implements I and J + +func (*D) f() +func (*D) g() + +func f(i I) { + i.f() // calls C, *C, *D +} + +func g(j J) { + j.g() // calls *C, *D +} + +// WANT: +// Dynamic calls +// f --> (*C).f +// f --> (*D).f +// f --> (C).f +// g --> (*C).g +// g --> (*D).g 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..a8f8903 --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/util.go @@ -0,0 +1,181 @@ +// 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 +// synthetic functions (except g.Root and package initializers), +// preserving the topology. In effect, calls to synthetic wrappers +// are "inlined". +// +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 || fn.Synthetic == "" || isInit(cgn.Func) { + 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()) +} |