| 1 | // Copyright 2014 The Go Authors. All rights reserved. |
|---|---|
| 2 | // Use of this source code is governed by a BSD-style |
| 3 | // license that can be found in the LICENSE file. |
| 4 | |
| 5 | // Package cha computes the call graph of a Go program using the Class |
| 6 | // Hierarchy Analysis (CHA) algorithm. |
| 7 | // |
| 8 | // CHA was first described in "Optimization of Object-Oriented Programs |
| 9 | // Using Static Class Hierarchy Analysis", Jeffrey Dean, David Grove, |
| 10 | // and Craig Chambers, ECOOP'95. |
| 11 | // |
| 12 | // CHA is related to RTA (see go/callgraph/rta); the difference is that |
| 13 | // CHA conservatively computes the entire "implements" relation between |
| 14 | // interfaces and concrete types ahead of time, whereas RTA uses dynamic |
| 15 | // programming to construct it on the fly as it encounters new functions |
| 16 | // reachable from main. CHA may thus include spurious call edges for |
| 17 | // types that haven't been instantiated yet, or types that are never |
| 18 | // instantiated. |
| 19 | // |
| 20 | // Since CHA conservatively assumes that all functions are address-taken |
| 21 | // and all concrete types are put into interfaces, it is sound to run on |
| 22 | // partial programs, such as libraries without a main or test function. |
| 23 | package cha // import "golang.org/x/tools/go/callgraph/cha" |
| 24 | |
| 25 | // TODO(zpavlinovic): update CHA for how it handles generic function bodies. |
| 26 | |
| 27 | import ( |
| 28 | "go/types" |
| 29 | |
| 30 | "golang.org/x/tools/go/callgraph" |
| 31 | "golang.org/x/tools/go/ssa" |
| 32 | "golang.org/x/tools/go/ssa/ssautil" |
| 33 | "golang.org/x/tools/go/types/typeutil" |
| 34 | ) |
| 35 | |
| 36 | // CallGraph computes the call graph of the specified program using the |
| 37 | // Class Hierarchy Analysis algorithm. |
| 38 | func CallGraph(prog *ssa.Program) *callgraph.Graph { |
| 39 | cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph |
| 40 | |
| 41 | allFuncs := ssautil.AllFunctions(prog) |
| 42 | |
| 43 | // funcsBySig contains all functions, keyed by signature. It is |
| 44 | // the effective set of address-taken functions used to resolve |
| 45 | // a dynamic call of a particular signature. |
| 46 | var funcsBySig typeutil.Map // value is []*ssa.Function |
| 47 | |
| 48 | // methodsByName contains all methods, |
| 49 | // grouped by name for efficient lookup. |
| 50 | // (methodsById would be better but not every SSA method has a go/types ID.) |
| 51 | methodsByName := make(map[string][]*ssa.Function) |
| 52 | |
| 53 | // An imethod represents an interface method I.m. |
| 54 | // (There's no go/types object for it; |
| 55 | // a *types.Func may be shared by many interfaces due to interface embedding.) |
| 56 | type imethod struct { |
| 57 | I *types.Interface |
| 58 | id string |
| 59 | } |
| 60 | // methodsMemo records, for every abstract method call I.m on |
| 61 | // interface type I, the set of concrete methods C.m of all |
| 62 | // types C that satisfy interface I. |
| 63 | // |
| 64 | // Abstract methods may be shared by several interfaces, |
| 65 | // hence we must pass I explicitly, not guess from m. |
| 66 | // |
| 67 | // methodsMemo is just a cache, so it needn't be a typeutil.Map. |
| 68 | methodsMemo := make(map[imethod][]*ssa.Function) |
| 69 | lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function { |
| 70 | id := m.Id() |
| 71 | methods, ok := methodsMemo[imethod{I, id}] |
| 72 | if !ok { |
| 73 | for _, f := range methodsByName[m.Name()] { |
| 74 | C := f.Signature.Recv().Type() // named or *named |
| 75 | if types.Implements(C, I) { |
| 76 | methods = append(methods, f) |
| 77 | } |
| 78 | } |
| 79 | methodsMemo[imethod{I, id}] = methods |
| 80 | } |
| 81 | return methods |
| 82 | } |
| 83 | |
| 84 | for f := range allFuncs { |
| 85 | if f.Signature.Recv() == nil { |
| 86 | // Package initializers can never be address-taken. |
| 87 | if f.Name() == "init" && f.Synthetic == "package initializer" { |
| 88 | continue |
| 89 | } |
| 90 | funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function) |
| 91 | funcs = append(funcs, f) |
| 92 | funcsBySig.Set(f.Signature, funcs) |
| 93 | } else { |
| 94 | methodsByName[f.Name()] = append(methodsByName[f.Name()], f) |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) { |
| 99 | gnode := cg.CreateNode(g) |
| 100 | callgraph.AddEdge(fnode, site, gnode) |
| 101 | } |
| 102 | |
| 103 | addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) { |
| 104 | // Because every call to a highly polymorphic and |
| 105 | // frequently used abstract method such as |
| 106 | // (io.Writer).Write is assumed to call every concrete |
| 107 | // Write method in the program, the call graph can |
| 108 | // contain a lot of duplication. |
| 109 | // |
| 110 | // TODO(adonovan): opt: consider factoring the callgraph |
| 111 | // API so that the Callers component of each edge is a |
| 112 | // slice of nodes, not a singleton. |
| 113 | for _, g := range callees { |
| 114 | addEdge(fnode, site, g) |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | for f := range allFuncs { |
| 119 | fnode := cg.CreateNode(f) |
| 120 | for _, b := range f.Blocks { |
| 121 | for _, instr := range b.Instrs { |
| 122 | if site, ok := instr.(ssa.CallInstruction); ok { |
| 123 | call := site.Common() |
| 124 | if call.IsInvoke() { |
| 125 | tiface := call.Value.Type().Underlying().(*types.Interface) |
| 126 | addEdges(fnode, site, lookupMethods(tiface, call.Method)) |
| 127 | } else if g := call.StaticCallee(); g != nil { |
| 128 | addEdge(fnode, site, g) |
| 129 | } else if _, ok := call.Value.(*ssa.Builtin); !ok { |
| 130 | callees, _ := funcsBySig.At(call.Signature()).([]*ssa.Function) |
| 131 | addEdges(fnode, site, callees) |
| 132 | } |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | return cg |
| 139 | } |
| 140 |
Members