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.
5 // Package cha computes the call graph of a Go program using the Class
6 // Hierarchy Analysis (CHA) algorithm.
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.
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
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.
24 package cha // import "honnef.co/go/tools/callgraph/cha"
29 "golang.org/x/tools/go/types/typeutil"
30 "honnef.co/go/tools/callgraph"
31 "honnef.co/go/tools/ir"
32 "honnef.co/go/tools/ir/irutil"
35 // CallGraph computes the call graph of the specified program using the
36 // Class Hierarchy Analysis algorithm.
38 func CallGraph(prog *ir.Program) *callgraph.Graph {
39 cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
41 allFuncs := irutil.AllFunctions(prog)
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 []*ir.Function
48 // methodsByName contains all methods,
49 // grouped by name for efficient lookup.
50 methodsByName := make(map[string][]*ir.Function)
52 // methodsMemo records, for every abstract method call call I.f on
53 // interface type I, the set of concrete methods C.f of all
54 // types C that satisfy interface I.
55 methodsMemo := make(map[*types.Func][]*ir.Function)
56 lookupMethods := func(m *types.Func) []*ir.Function {
57 methods, ok := methodsMemo[m]
59 I := m.Type().(*types.Signature).Recv().Type().Underlying().(*types.Interface)
60 for _, f := range methodsByName[m.Name()] {
61 C := f.Signature.Recv().Type() // named or *named
62 if types.Implements(C, I) {
63 methods = append(methods, f)
66 methodsMemo[m] = methods
71 for f := range allFuncs {
72 if f.Signature.Recv() == nil {
73 // Package initializers can never be address-taken.
74 if f.Name() == "init" && f.Synthetic == "package initializer" {
77 funcs, _ := funcsBySig.At(f.Signature).([]*ir.Function)
78 funcs = append(funcs, f)
79 funcsBySig.Set(f.Signature, funcs)
81 methodsByName[f.Name()] = append(methodsByName[f.Name()], f)
85 addEdge := func(fnode *callgraph.Node, site ir.CallInstruction, g *ir.Function) {
86 gnode := cg.CreateNode(g)
87 callgraph.AddEdge(fnode, site, gnode)
90 addEdges := func(fnode *callgraph.Node, site ir.CallInstruction, callees []*ir.Function) {
91 // Because every call to a highly polymorphic and
92 // frequently used abstract method such as
93 // (io.Writer).Write is assumed to call every concrete
94 // Write method in the program, the call graph can
95 // contain a lot of duplication.
97 // TODO(adonovan): opt: consider factoring the callgraph
98 // API so that the Callers component of each edge is a
99 // slice of nodes, not a singleton.
100 for _, g := range callees {
101 addEdge(fnode, site, g)
105 for f := range allFuncs {
106 fnode := cg.CreateNode(f)
107 for _, b := range f.Blocks {
108 for _, instr := range b.Instrs {
109 if site, ok := instr.(ir.CallInstruction); ok {
110 call := site.Common()
112 addEdges(fnode, site, lookupMethods(call.Method))
113 } else if g := call.StaticCallee(); g != nil {
114 addEdge(fnode, site, g)
115 } else if _, ok := call.Value.(*ir.Builtin); !ok {
116 callees, _ := funcsBySig.At(call.Signature()).([]*ir.Function)
117 addEdges(fnode, site, callees)