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