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 calleesOf := lazyCallees(allFuncs) 44 45 addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) { 46 gnode := cg.CreateNode(g) 47 callgraph.AddEdge(fnode, site, gnode) 48 } 49 50 addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) { 51 // Because every call to a highly polymorphic and 52 // frequently used abstract method such as 53 // (io.Writer).Write is assumed to call every concrete 54 // Write method in the program, the call graph can 55 // contain a lot of duplication. 56 // 57 // TODO(taking): opt: consider making lazyCallees public. 58 // Using the same benchmarks as callgraph_test.go, removing just 59 // the explicit callgraph.Graph construction is 4x less memory 60 // and is 37% faster. 61 // CHA 86 ms/op 16 MB/op 62 // lazyCallees 63 ms/op 4 MB/op 63 for _, g := range callees { 64 addEdge(fnode, site, g) 65 } 66 } 67 68 for f := range allFuncs { 69 fnode := cg.CreateNode(f) 70 for _, b := range f.Blocks { 71 for _, instr := range b.Instrs { 72 if site, ok := instr.(ssa.CallInstruction); ok { 73 if g := site.Common().StaticCallee(); g != nil { 74 addEdge(fnode, site, g) 75 } else { 76 addEdges(fnode, site, calleesOf(site)) 77 } 78 } 79 } 80 } 81 } 82 83 return cg 84 } 85 86 // lazyCallees returns a function that maps a call site (in a function in fns) 87 // to its callees within fns. 88 // 89 // The resulting function is not concurrency safe. 90 func lazyCallees(fns map[*ssa.Function]bool) func(site ssa.CallInstruction) []*ssa.Function { 91 // funcsBySig contains all functions, keyed by signature. It is 92 // the effective set of address-taken functions used to resolve 93 // a dynamic call of a particular signature. 94 var funcsBySig typeutil.Map // value is []*ssa.Function 95 96 // methodsByID contains all methods, grouped by ID for efficient 97 // lookup. 98 // 99 // We must key by ID, not name, for correct resolution of interface 100 // calls to a type with two (unexported) methods spelled the same but 101 // from different packages. The fact that the concrete type implements 102 // the interface does not mean the call dispatches to both methods. 103 methodsByID := make(map[string][]*ssa.Function) 104 105 // An imethod represents an interface method I.m. 106 // (There's no go/types object for it; 107 // a *types.Func may be shared by many interfaces due to interface embedding.) 108 type imethod struct { 109 I *types.Interface 110 id string 111 } 112 // methodsMemo records, for every abstract method call I.m on 113 // interface type I, the set of concrete methods C.m of all 114 // types C that satisfy interface I. 115 // 116 // Abstract methods may be shared by several interfaces, 117 // hence we must pass I explicitly, not guess from m. 118 // 119 // methodsMemo is just a cache, so it needn't be a typeutil.Map. 120 methodsMemo := make(map[imethod][]*ssa.Function) 121 lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function { 122 id := m.Id() 123 methods, ok := methodsMemo[imethod{I, id}] 124 if !ok { 125 for _, f := range methodsByID[id] { 126 C := f.Signature.Recv().Type() // named or *named 127 if types.Implements(C, I) { 128 methods = append(methods, f) 129 } 130 } 131 methodsMemo[imethod{I, id}] = methods 132 } 133 return methods 134 } 135 136 for f := range fns { 137 if f.Signature.Recv() == nil { 138 // Package initializers can never be address-taken. 139 if f.Name() == "init" && f.Synthetic == "package initializer" { 140 continue 141 } 142 funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function) 143 funcs = append(funcs, f) 144 funcsBySig.Set(f.Signature, funcs) 145 } else if obj := f.Object(); obj != nil { 146 id := obj.(*types.Func).Id() 147 methodsByID[id] = append(methodsByID[id], f) 148 } 149 } 150 151 return func(site ssa.CallInstruction) []*ssa.Function { 152 call := site.Common() 153 if call.IsInvoke() { 154 tiface := call.Value.Type().Underlying().(*types.Interface) 155 return lookupMethods(tiface, call.Method) 156 } else if g := call.StaticCallee(); g != nil { 157 return []*ssa.Function{g} 158 } else if _, ok := call.Value.(*ssa.Builtin); !ok { 159 fns, _ := funcsBySig.At(call.Signature()).([]*ssa.Function) 160 return fns 161 } 162 return nil 163 } 164 } 165