diff options
Diffstat (limited to 'vendor/golang.org/x/tools/go/callgraph')
8 files changed, 0 insertions, 723 deletions
diff --git a/vendor/golang.org/x/tools/go/callgraph/callgraph.go b/vendor/golang.org/x/tools/go/callgraph/callgraph.go deleted file mode 100644 index 707a319..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/callgraph.go +++ /dev/null @@ -1,129 +0,0 @@ -// 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 deleted file mode 100644 index 215ff17..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/cha.go +++ /dev/null @@ -1,139 +0,0 @@ -// 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 deleted file mode 100644 index cb2d585..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/cha_test.go +++ /dev/null @@ -1,111 +0,0 @@ -// 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 deleted file mode 100644 index ad483f1..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/func.go +++ /dev/null @@ -1,23 +0,0 @@ -//+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 deleted file mode 100644 index 1622ec1..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/iface.go +++ /dev/null @@ -1,65 +0,0 @@ -//+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 deleted file mode 100644 index 59eaf18..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/issue23925.go +++ /dev/null @@ -1,38 +0,0 @@ -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 deleted file mode 100644 index 5ba48e9..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/cha/testdata/recv.go +++ /dev/null @@ -1,37 +0,0 @@ -//+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 deleted file mode 100644 index a8f8903..0000000 --- a/vendor/golang.org/x/tools/go/callgraph/util.go +++ /dev/null @@ -1,181 +0,0 @@ -// 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()) -} |