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//
24package cha // import "golang.org/x/tools/go/callgraph/cha"
25
26import (
27	"go/types"
28
29	"golang.org/x/tools/go/callgraph"
30	"golang.org/x/tools/go/ssa"
31	"golang.org/x/tools/go/ssa/ssautil"
32	"golang.org/x/tools/go/types/typeutil"
33)
34
35// CallGraph computes the call graph of the specified program using the
36// Class Hierarchy Analysis algorithm.
37//
38func 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