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.
7 // This file computes the CALLERS and CALLEES relations from the call
8 // graph. CALLERS/CALLEES information is displayed in the lower pane
9 // when a "func" token or ast.CallExpr.Lparen is clicked, respectively.
20 "golang.org/x/tools/go/callgraph"
21 "golang.org/x/tools/go/ssa"
24 // doCallgraph computes the CALLEES and CALLERS relations.
25 func (a *analysis) doCallgraph(cg *callgraph.Graph) {
26 log.Print("Deleting synthetic nodes...")
27 // TODO(adonovan): opt: DeleteSyntheticNodes is asymptotically
28 // inefficient and can be (unpredictably) slow.
29 cg.DeleteSyntheticNodes()
30 log.Print("Synthetic nodes deleted")
32 // Populate nodes of package call graphs (PCGs).
33 for _, n := range cg.Nodes {
36 // Within each PCG, sort funcs by name.
37 for _, pcg := range a.pcgs {
41 calledFuncs := make(map[ssa.CallInstruction]map[*ssa.Function]bool)
42 callingSites := make(map[*ssa.Function]map[ssa.CallInstruction]bool)
43 for _, n := range cg.Nodes {
44 for _, e := range n.Out {
46 continue // a call from a synthetic node such as <root>
49 // Add (site pos, callee) to calledFuncs.
50 // (Dynamic calls only.)
51 callee := e.Callee.Func
53 a.pcgAddEdge(n.Func, callee)
55 if callee.Synthetic != "" {
56 continue // call of a package initializer
59 if e.Site.Common().StaticCallee() == nil {
61 // (CALLEES information for static calls
62 // is computed using SSA information.)
63 lparen := e.Site.Common().Pos()
64 if lparen != token.NoPos {
65 fns := calledFuncs[e.Site]
67 fns = make(map[*ssa.Function]bool)
68 calledFuncs[e.Site] = fns
74 // Add (callee, site) to callingSites.
75 fns := callingSites[callee]
77 fns = make(map[ssa.CallInstruction]bool)
78 callingSites[callee] = fns
85 log.Print("Callees...")
86 for site, fns := range calledFuncs {
89 funcs = append(funcs, fn)
93 a.addCallees(site, funcs)
97 log.Print("Callers...")
98 for callee, sites := range callingSites {
99 pos := funcToken(callee)
100 if pos == token.NoPos {
101 log.Printf("CALLERS: skipping %s: no pos", callee)
105 var this *types.Package // for relativizing names
106 if callee.Pkg != nil {
107 this = callee.Pkg.Pkg
110 // Compute sites grouped by parent, with text and URLs.
111 sitesByParent := make(map[*ssa.Function]sitesByPos)
112 for site := range sites {
114 sitesByParent[fn] = append(sitesByParent[fn], site)
117 for fn := range sitesByParent {
118 funcs = append(funcs, fn)
123 Callee: callee.String(),
124 Callers: []callerJSON{}, // (JS wants non-nil)
126 for _, fn := range funcs {
127 caller := callerJSON{
128 Func: prettyFunc(this, fn),
129 Sites: []anchorJSON{}, // (JS wants non-nil)
131 sites := sitesByParent[fn]
133 for _, site := range sites {
134 pos := site.Common().Pos()
135 if pos != token.NoPos {
136 caller.Sites = append(caller.Sites, anchorJSON{
137 Text: fmt.Sprintf("%d", a.prog.Fset.Position(pos).Line),
138 Href: a.posURL(pos, len("(")),
142 v.Callers = append(v.Callers, caller)
145 fi, offset := a.fileAndOffset(pos)
148 end: offset + len("func"),
149 title: fmt.Sprintf("%d callers", len(sites)),
150 onclick: fmt.Sprintf("onClickCallers(%d)", fi.addData(v)),
155 log.Print("Package call graph...")
156 for pkg, pcg := range a.pcgs {
157 // Maps (*ssa.Function).RelString() to index in JSON CALLGRAPH array.
158 index := make(map[string]int)
160 // Treat exported functions (and exported methods of
161 // exported named types) as roots even if they aren't
162 // actually called from outside the package.
163 for i, n := range pcg.nodes {
164 if i == 0 || n.fn.Object() == nil || !n.fn.Object().Exported() {
167 recv := n.fn.Signature.Recv()
168 if recv == nil || deref(recv.Type()).(*types.Named).Obj().Exported() {
169 roots := &pcg.nodes[0].edges
170 roots.SetBit(roots, i, 1)
172 index[n.fn.RelString(pkg.Pkg)] = i
175 json := a.pcgJSON(pcg)
177 // TODO(adonovan): pkg.Path() is not unique!
178 // It is possible to declare a non-test package called x_test.
179 a.result.pkgInfo(pkg.Pkg.Path()).setCallGraph(json, index)
183 // addCallees adds client data and links for the facts that site calls fns.
184 func (a *analysis) addCallees(site ssa.CallInstruction, fns []*ssa.Function) {
186 Descr: site.Common().Description(),
187 Callees: []anchorJSON{}, // (JS wants non-nil)
189 var this *types.Package // for relativizing names
190 if p := site.Parent().Package(); p != nil {
194 for _, fn := range fns {
195 v.Callees = append(v.Callees, anchorJSON{
196 Text: prettyFunc(this, fn),
197 Href: a.posURL(funcToken(fn), len("func")),
201 fi, offset := a.fileAndOffset(site.Common().Pos())
204 end: offset + len("("),
205 title: fmt.Sprintf("%d callees", len(v.Callees)),
206 onclick: fmt.Sprintf("onClickCallees(%d)", fi.addData(v)),
210 // -- utilities --------------------------------------------------------
212 // stable order within packages but undefined across packages.
213 type funcsByPos []*ssa.Function
215 func (a funcsByPos) Less(i, j int) bool { return a[i].Pos() < a[j].Pos() }
216 func (a funcsByPos) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
217 func (a funcsByPos) Len() int { return len(a) }
219 type sitesByPos []ssa.CallInstruction
221 func (a sitesByPos) Less(i, j int) bool { return a[i].Common().Pos() < a[j].Common().Pos() }
222 func (a sitesByPos) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
223 func (a sitesByPos) Len() int { return len(a) }
225 func funcToken(fn *ssa.Function) token.Pos {
226 switch syntax := fn.Syntax().(type) {
228 return syntax.Type.Func
230 return syntax.Type.Func
235 // prettyFunc pretty-prints fn for the user interface.
236 // TODO(adonovan): return HTML so we have more markup freedom.
237 func prettyFunc(this *types.Package, fn *ssa.Function) string {
238 if fn.Parent() != nil {
239 return fmt.Sprintf("%s in %s",
240 types.TypeString(fn.Signature, types.RelativeTo(this)),
241 prettyFunc(this, fn.Parent()))
243 if fn.Synthetic != "" && fn.Name() == "init" {
244 // (This is the actual initializer, not a declared 'func init').
245 if fn.Pkg.Pkg == this {
246 return "package initializer"
248 return fmt.Sprintf("%q package initializer", fn.Pkg.Pkg.Path())
250 return fn.RelString(this)
253 // -- intra-package callgraph ------------------------------------------
255 // pcgNode represents a node in the package call graph (PCG).
256 type pcgNode struct {
258 pretty string // cache of prettyFunc(fn)
259 edges big.Int // set of callee func indices
262 // A packageCallGraph represents the intra-package edges of the global call graph.
263 // The zeroth node indicates "all external functions".
264 type packageCallGraph struct {
265 nodeIndex map[*ssa.Function]int // maps func to node index (a small int)
266 nodes []*pcgNode // maps node index to node
269 // sortNodes populates pcg.nodes in name order and updates the nodeIndex.
270 func (pcg *packageCallGraph) sortNodes() {
271 nodes := make([]*pcgNode, 0, len(pcg.nodeIndex))
272 nodes = append(nodes, &pcgNode{fn: nil, pretty: "<external>"})
273 for fn := range pcg.nodeIndex {
274 nodes = append(nodes, &pcgNode{
276 pretty: prettyFunc(fn.Pkg.Pkg, fn),
279 sort.Sort(pcgNodesByPretty(nodes[1:]))
280 for i, n := range nodes {
281 pcg.nodeIndex[n.fn] = i
286 func (pcg *packageCallGraph) addEdge(caller, callee *ssa.Function) {
288 if caller.Pkg == callee.Pkg {
289 // intra-package edge
290 callerIndex = pcg.nodeIndex[caller]
295 edges := &pcg.nodes[callerIndex].edges
296 edges.SetBit(edges, pcg.nodeIndex[callee], 1)
299 func (a *analysis) pcgAddNode(fn *ssa.Function) {
303 pcg, ok := a.pcgs[fn.Pkg]
305 pcg = &packageCallGraph{nodeIndex: make(map[*ssa.Function]int)}
308 pcg.nodeIndex[fn] = -1
311 func (a *analysis) pcgAddEdge(caller, callee *ssa.Function) {
312 if callee.Pkg != nil {
313 a.pcgs[callee.Pkg].addEdge(caller, callee)
317 // pcgJSON returns a new slice of callgraph JSON values.
318 func (a *analysis) pcgJSON(pcg *packageCallGraph) []*PCGNodeJSON {
319 var nodes []*PCGNodeJSON
320 for _, n := range pcg.nodes {
322 // TODO(adonovan): why is there no good way to iterate
323 // over the set bits of a big.Int?
325 nbits := n.edges.BitLen()
326 for j := 0; j < nbits; j++ {
327 if n.edges.Bit(j) == 1 {
328 callees = append(callees, j)
334 pos = funcToken(n.fn)
336 nodes = append(nodes, &PCGNodeJSON{
339 Href: a.posURL(pos, len("func")),
347 type pcgNodesByPretty []*pcgNode
349 func (a pcgNodesByPretty) Less(i, j int) bool { return a[i].pretty < a[j].pretty }
350 func (a pcgNodesByPretty) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
351 func (a pcgNodesByPretty) Len() int { return len(a) }