From b1247d2d0d51108c910a73891ff3116e5f032ab1 Mon Sep 17 00:00:00 2001 From: "Kali Kaneko (leap communications)" Date: Sat, 12 Jan 2019 18:39:45 +0100 Subject: [pkg] all your deps are vendored to us --- vendor/golang.org/x/tools/go/callgraph/cha/cha.go | 139 ++++++++++++++++++++++ 1 file changed, 139 insertions(+) create mode 100644 vendor/golang.org/x/tools/go/callgraph/cha/cha.go (limited to 'vendor/golang.org/x/tools/go/callgraph/cha/cha.go') 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 +} -- cgit v1.2.3