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