+++ /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