--- /dev/null
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package analysis
+
+// This file computes the CALLERS and CALLEES relations from the call
+// graph. CALLERS/CALLEES information is displayed in the lower pane
+// when a "func" token or ast.CallExpr.Lparen is clicked, respectively.
+
+import (
+ "fmt"
+ "go/ast"
+ "go/token"
+ "go/types"
+ "log"
+ "math/big"
+ "sort"
+
+ "golang.org/x/tools/go/callgraph"
+ "golang.org/x/tools/go/ssa"
+)
+
+// doCallgraph computes the CALLEES and CALLERS relations.
+func (a *analysis) doCallgraph(cg *callgraph.Graph) {
+ log.Print("Deleting synthetic nodes...")
+ // TODO(adonovan): opt: DeleteSyntheticNodes is asymptotically
+ // inefficient and can be (unpredictably) slow.
+ cg.DeleteSyntheticNodes()
+ log.Print("Synthetic nodes deleted")
+
+ // Populate nodes of package call graphs (PCGs).
+ for _, n := range cg.Nodes {
+ a.pcgAddNode(n.Func)
+ }
+ // Within each PCG, sort funcs by name.
+ for _, pcg := range a.pcgs {
+ pcg.sortNodes()
+ }
+
+ calledFuncs := make(map[ssa.CallInstruction]map[*ssa.Function]bool)
+ callingSites := make(map[*ssa.Function]map[ssa.CallInstruction]bool)
+ for _, n := range cg.Nodes {
+ for _, e := range n.Out {
+ if e.Site == nil {
+ continue // a call from a synthetic node such as <root>
+ }
+
+ // Add (site pos, callee) to calledFuncs.
+ // (Dynamic calls only.)
+ callee := e.Callee.Func
+
+ a.pcgAddEdge(n.Func, callee)
+
+ if callee.Synthetic != "" {
+ continue // call of a package initializer
+ }
+
+ if e.Site.Common().StaticCallee() == nil {
+ // dynamic call
+ // (CALLEES information for static calls
+ // is computed using SSA information.)
+ lparen := e.Site.Common().Pos()
+ if lparen != token.NoPos {
+ fns := calledFuncs[e.Site]
+ if fns == nil {
+ fns = make(map[*ssa.Function]bool)
+ calledFuncs[e.Site] = fns
+ }
+ fns[callee] = true
+ }
+ }
+
+ // Add (callee, site) to callingSites.
+ fns := callingSites[callee]
+ if fns == nil {
+ fns = make(map[ssa.CallInstruction]bool)
+ callingSites[callee] = fns
+ }
+ fns[e.Site] = true
+ }
+ }
+
+ // CALLEES.
+ log.Print("Callees...")
+ for site, fns := range calledFuncs {
+ var funcs funcsByPos
+ for fn := range fns {
+ funcs = append(funcs, fn)
+ }
+ sort.Sort(funcs)
+
+ a.addCallees(site, funcs)
+ }
+
+ // CALLERS
+ log.Print("Callers...")
+ for callee, sites := range callingSites {
+ pos := funcToken(callee)
+ if pos == token.NoPos {
+ log.Printf("CALLERS: skipping %s: no pos", callee)
+ continue
+ }
+
+ var this *types.Package // for relativizing names
+ if callee.Pkg != nil {
+ this = callee.Pkg.Pkg
+ }
+
+ // Compute sites grouped by parent, with text and URLs.
+ sitesByParent := make(map[*ssa.Function]sitesByPos)
+ for site := range sites {
+ fn := site.Parent()
+ sitesByParent[fn] = append(sitesByParent[fn], site)
+ }
+ var funcs funcsByPos
+ for fn := range sitesByParent {
+ funcs = append(funcs, fn)
+ }
+ sort.Sort(funcs)
+
+ v := callersJSON{
+ Callee: callee.String(),
+ Callers: []callerJSON{}, // (JS wants non-nil)
+ }
+ for _, fn := range funcs {
+ caller := callerJSON{
+ Func: prettyFunc(this, fn),
+ Sites: []anchorJSON{}, // (JS wants non-nil)
+ }
+ sites := sitesByParent[fn]
+ sort.Sort(sites)
+ for _, site := range sites {
+ pos := site.Common().Pos()
+ if pos != token.NoPos {
+ caller.Sites = append(caller.Sites, anchorJSON{
+ Text: fmt.Sprintf("%d", a.prog.Fset.Position(pos).Line),
+ Href: a.posURL(pos, len("(")),
+ })
+ }
+ }
+ v.Callers = append(v.Callers, caller)
+ }
+
+ fi, offset := a.fileAndOffset(pos)
+ fi.addLink(aLink{
+ start: offset,
+ end: offset + len("func"),
+ title: fmt.Sprintf("%d callers", len(sites)),
+ onclick: fmt.Sprintf("onClickCallers(%d)", fi.addData(v)),
+ })
+ }
+
+ // PACKAGE CALLGRAPH
+ log.Print("Package call graph...")
+ for pkg, pcg := range a.pcgs {
+ // Maps (*ssa.Function).RelString() to index in JSON CALLGRAPH array.
+ index := make(map[string]int)
+
+ // Treat exported functions (and exported methods of
+ // exported named types) as roots even if they aren't
+ // actually called from outside the package.
+ for i, n := range pcg.nodes {
+ if i == 0 || n.fn.Object() == nil || !n.fn.Object().Exported() {
+ continue
+ }
+ recv := n.fn.Signature.Recv()
+ if recv == nil || deref(recv.Type()).(*types.Named).Obj().Exported() {
+ roots := &pcg.nodes[0].edges
+ roots.SetBit(roots, i, 1)
+ }
+ index[n.fn.RelString(pkg.Pkg)] = i
+ }
+
+ json := a.pcgJSON(pcg)
+
+ // TODO(adonovan): pkg.Path() is not unique!
+ // It is possible to declare a non-test package called x_test.
+ a.result.pkgInfo(pkg.Pkg.Path()).setCallGraph(json, index)
+ }
+}
+
+// addCallees adds client data and links for the facts that site calls fns.
+func (a *analysis) addCallees(site ssa.CallInstruction, fns []*ssa.Function) {
+ v := calleesJSON{
+ Descr: site.Common().Description(),
+ Callees: []anchorJSON{}, // (JS wants non-nil)
+ }
+ var this *types.Package // for relativizing names
+ if p := site.Parent().Package(); p != nil {
+ this = p.Pkg
+ }
+
+ for _, fn := range fns {
+ v.Callees = append(v.Callees, anchorJSON{
+ Text: prettyFunc(this, fn),
+ Href: a.posURL(funcToken(fn), len("func")),
+ })
+ }
+
+ fi, offset := a.fileAndOffset(site.Common().Pos())
+ fi.addLink(aLink{
+ start: offset,
+ end: offset + len("("),
+ title: fmt.Sprintf("%d callees", len(v.Callees)),
+ onclick: fmt.Sprintf("onClickCallees(%d)", fi.addData(v)),
+ })
+}
+
+// -- utilities --------------------------------------------------------
+
+// stable order within packages but undefined across packages.
+type funcsByPos []*ssa.Function
+
+func (a funcsByPos) Less(i, j int) bool { return a[i].Pos() < a[j].Pos() }
+func (a funcsByPos) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a funcsByPos) Len() int { return len(a) }
+
+type sitesByPos []ssa.CallInstruction
+
+func (a sitesByPos) Less(i, j int) bool { return a[i].Common().Pos() < a[j].Common().Pos() }
+func (a sitesByPos) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a sitesByPos) Len() int { return len(a) }
+
+func funcToken(fn *ssa.Function) token.Pos {
+ switch syntax := fn.Syntax().(type) {
+ case *ast.FuncLit:
+ return syntax.Type.Func
+ case *ast.FuncDecl:
+ return syntax.Type.Func
+ }
+ return token.NoPos
+}
+
+// prettyFunc pretty-prints fn for the user interface.
+// TODO(adonovan): return HTML so we have more markup freedom.
+func prettyFunc(this *types.Package, fn *ssa.Function) string {
+ if fn.Parent() != nil {
+ return fmt.Sprintf("%s in %s",
+ types.TypeString(fn.Signature, types.RelativeTo(this)),
+ prettyFunc(this, fn.Parent()))
+ }
+ if fn.Synthetic != "" && fn.Name() == "init" {
+ // (This is the actual initializer, not a declared 'func init').
+ if fn.Pkg.Pkg == this {
+ return "package initializer"
+ }
+ return fmt.Sprintf("%q package initializer", fn.Pkg.Pkg.Path())
+ }
+ return fn.RelString(this)
+}
+
+// -- intra-package callgraph ------------------------------------------
+
+// pcgNode represents a node in the package call graph (PCG).
+type pcgNode struct {
+ fn *ssa.Function
+ pretty string // cache of prettyFunc(fn)
+ edges big.Int // set of callee func indices
+}
+
+// A packageCallGraph represents the intra-package edges of the global call graph.
+// The zeroth node indicates "all external functions".
+type packageCallGraph struct {
+ nodeIndex map[*ssa.Function]int // maps func to node index (a small int)
+ nodes []*pcgNode // maps node index to node
+}
+
+// sortNodes populates pcg.nodes in name order and updates the nodeIndex.
+func (pcg *packageCallGraph) sortNodes() {
+ nodes := make([]*pcgNode, 0, len(pcg.nodeIndex))
+ nodes = append(nodes, &pcgNode{fn: nil, pretty: "<external>"})
+ for fn := range pcg.nodeIndex {
+ nodes = append(nodes, &pcgNode{
+ fn: fn,
+ pretty: prettyFunc(fn.Pkg.Pkg, fn),
+ })
+ }
+ sort.Sort(pcgNodesByPretty(nodes[1:]))
+ for i, n := range nodes {
+ pcg.nodeIndex[n.fn] = i
+ }
+ pcg.nodes = nodes
+}
+
+func (pcg *packageCallGraph) addEdge(caller, callee *ssa.Function) {
+ var callerIndex int
+ if caller.Pkg == callee.Pkg {
+ // intra-package edge
+ callerIndex = pcg.nodeIndex[caller]
+ if callerIndex < 1 {
+ panic(caller)
+ }
+ }
+ edges := &pcg.nodes[callerIndex].edges
+ edges.SetBit(edges, pcg.nodeIndex[callee], 1)
+}
+
+func (a *analysis) pcgAddNode(fn *ssa.Function) {
+ if fn.Pkg == nil {
+ return
+ }
+ pcg, ok := a.pcgs[fn.Pkg]
+ if !ok {
+ pcg = &packageCallGraph{nodeIndex: make(map[*ssa.Function]int)}
+ a.pcgs[fn.Pkg] = pcg
+ }
+ pcg.nodeIndex[fn] = -1
+}
+
+func (a *analysis) pcgAddEdge(caller, callee *ssa.Function) {
+ if callee.Pkg != nil {
+ a.pcgs[callee.Pkg].addEdge(caller, callee)
+ }
+}
+
+// pcgJSON returns a new slice of callgraph JSON values.
+func (a *analysis) pcgJSON(pcg *packageCallGraph) []*PCGNodeJSON {
+ var nodes []*PCGNodeJSON
+ for _, n := range pcg.nodes {
+
+ // TODO(adonovan): why is there no good way to iterate
+ // over the set bits of a big.Int?
+ var callees []int
+ nbits := n.edges.BitLen()
+ for j := 0; j < nbits; j++ {
+ if n.edges.Bit(j) == 1 {
+ callees = append(callees, j)
+ }
+ }
+
+ var pos token.Pos
+ if n.fn != nil {
+ pos = funcToken(n.fn)
+ }
+ nodes = append(nodes, &PCGNodeJSON{
+ Func: anchorJSON{
+ Text: n.pretty,
+ Href: a.posURL(pos, len("func")),
+ },
+ Callees: callees,
+ })
+ }
+ return nodes
+}
+
+type pcgNodesByPretty []*pcgNode
+
+func (a pcgNodesByPretty) Less(i, j int) bool { return a[i].pretty < a[j].pretty }
+func (a pcgNodesByPretty) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a pcgNodesByPretty) Len() int { return len(a) }
projects / dotfiles / .git / blobdiff