diff options
Diffstat (limited to 'vendor/golang.org/x/tools/go/callgraph/cha')
6 files changed, 0 insertions, 413 deletions
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 |