.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/godoc/analysis/callgraph.go

   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 analysis
   6
   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.
  10
  11 import (
  12         "fmt"
  13         "go/ast"
  14         "go/token"
  15         "go/types"
  16         "log"
  17         "math/big"
  18         "sort"
  19
  20         "golang.org/x/tools/go/callgraph"
  21         "golang.org/x/tools/go/ssa"
  22 )
  23
  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")
  31
  32         // Populate nodes of package call graphs (PCGs).
  33         for _, n := range cg.Nodes {
  34                 a.pcgAddNode(n.Func)
  35         }
  36         // Within each PCG, sort funcs by name.
  37         for _, pcg := range a.pcgs {
  38                 pcg.sortNodes()
  39         }
  40
  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 {
  45                         if e.Site == nil {
  46                                 continue // a call from a synthetic node such as <root>
  47                         }
  48
  49                         // Add (site pos, callee) to calledFuncs.
  50                         // (Dynamic calls only.)
  51                         callee := e.Callee.Func
  52
  53                         a.pcgAddEdge(n.Func, callee)
  54
  55                         if callee.Synthetic != "" {
  56                                 continue // call of a package initializer
  57                         }
  58
  59                         if e.Site.Common().StaticCallee() == nil {
  60                                 // dynamic call
  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]
  66                                         if fns == nil {
  67                                                 fns = make(map[*ssa.Function]bool)
  68                                                 calledFuncs[e.Site] = fns
  69                                         }
  70                                         fns[callee] = true
  71                                 }
  72                         }
  73
  74                         // Add (callee, site) to callingSites.
  75                         fns := callingSites[callee]
  76                         if fns == nil {
  77                                 fns = make(map[ssa.CallInstruction]bool)
  78                                 callingSites[callee] = fns
  79                         }
  80                         fns[e.Site] = true
  81                 }
  82         }
  83
  84         // CALLEES.
  85         log.Print("Callees...")
  86         for site, fns := range calledFuncs {
  87                 var funcs funcsByPos
  88                 for fn := range fns {
  89                         funcs = append(funcs, fn)
  90                 }
  91                 sort.Sort(funcs)
  92
  93                 a.addCallees(site, funcs)
  94         }
  95
  96         // CALLERS
  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)
 102                         continue
 103                 }
 104
 105                 var this *types.Package // for relativizing names
 106                 if callee.Pkg != nil {
 107                         this = callee.Pkg.Pkg
 108                 }
 109
 110                 // Compute sites grouped by parent, with text and URLs.
 111                 sitesByParent := make(map[*ssa.Function]sitesByPos)
 112                 for site := range sites {
 113                         fn := site.Parent()
 114                         sitesByParent[fn] = append(sitesByParent[fn], site)
 115                 }
 116                 var funcs funcsByPos
 117                 for fn := range sitesByParent {
 118                         funcs = append(funcs, fn)
 119                 }
 120                 sort.Sort(funcs)
 121
 122                 v := callersJSON{
 123                         Callee:  callee.String(),
 124                         Callers: []callerJSON{}, // (JS wants non-nil)
 125                 }
 126                 for _, fn := range funcs {
 127                         caller := callerJSON{
 128                                 Func:  prettyFunc(this, fn),
 129                                 Sites: []anchorJSON{}, // (JS wants non-nil)
 130                         }
 131                         sites := sitesByParent[fn]
 132                         sort.Sort(sites)
 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("(")),
 139                                         })
 140                                 }
 141                         }
 142                         v.Callers = append(v.Callers, caller)
 143                 }
 144
 145                 fi, offset := a.fileAndOffset(pos)
 146                 fi.addLink(aLink{
 147                         start:   offset,
 148                         end:     offset + len("func"),
 149                         title:   fmt.Sprintf("%d callers", len(sites)),
 150                         onclick: fmt.Sprintf("onClickCallers(%d)", fi.addData(v)),
 151                 })
 152         }
 153
 154         // PACKAGE CALLGRAPH
 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)
 159
 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() {
 165                                 continue
 166                         }
 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)
 171                         }
 172                         index[n.fn.RelString(pkg.Pkg)] = i
 173                 }
 174
 175                 json := a.pcgJSON(pcg)
 176
 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)
 180         }
 181 }
 182
 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) {
 185         v := calleesJSON{
 186                 Descr:   site.Common().Description(),
 187                 Callees: []anchorJSON{}, // (JS wants non-nil)
 188         }
 189         var this *types.Package // for relativizing names
 190         if p := site.Parent().Package(); p != nil {
 191                 this = p.Pkg
 192         }
 193
 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")),
 198                 })
 199         }
 200
 201         fi, offset := a.fileAndOffset(site.Common().Pos())
 202         fi.addLink(aLink{
 203                 start:   offset,
 204                 end:     offset + len("("),
 205                 title:   fmt.Sprintf("%d callees", len(v.Callees)),
 206                 onclick: fmt.Sprintf("onClickCallees(%d)", fi.addData(v)),
 207         })
 208 }
 209
 210 // -- utilities --------------------------------------------------------
 211
 212 // stable order within packages but undefined across packages.
 213 type funcsByPos []*ssa.Function
 214
 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) }
 218
 219 type sitesByPos []ssa.CallInstruction
 220
 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) }
 224
 225 func funcToken(fn *ssa.Function) token.Pos {
 226         switch syntax := fn.Syntax().(type) {
 227         case *ast.FuncLit:
 228                 return syntax.Type.Func
 229         case *ast.FuncDecl:
 230                 return syntax.Type.Func
 231         }
 232         return token.NoPos
 233 }
 234
 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()))
 242         }
 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"
 247                 }
 248                 return fmt.Sprintf("%q package initializer", fn.Pkg.Pkg.Path())
 249         }
 250         return fn.RelString(this)
 251 }
 252
 253 // -- intra-package callgraph ------------------------------------------
 254
 255 // pcgNode represents a node in the package call graph (PCG).
 256 type pcgNode struct {
 257         fn     *ssa.Function
 258         pretty string  // cache of prettyFunc(fn)
 259         edges  big.Int // set of callee func indices
 260 }
 261
 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
 267 }
 268
 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{
 275                         fn:     fn,
 276                         pretty: prettyFunc(fn.Pkg.Pkg, fn),
 277                 })
 278         }
 279         sort.Sort(pcgNodesByPretty(nodes[1:]))
 280         for i, n := range nodes {
 281                 pcg.nodeIndex[n.fn] = i
 282         }
 283         pcg.nodes = nodes
 284 }
 285
 286 func (pcg *packageCallGraph) addEdge(caller, callee *ssa.Function) {
 287         var callerIndex int
 288         if caller.Pkg == callee.Pkg {
 289                 // intra-package edge
 290                 callerIndex = pcg.nodeIndex[caller]
 291                 if callerIndex < 1 {
 292                         panic(caller)
 293                 }
 294         }
 295         edges := &pcg.nodes[callerIndex].edges
 296         edges.SetBit(edges, pcg.nodeIndex[callee], 1)
 297 }
 298
 299 func (a *analysis) pcgAddNode(fn *ssa.Function) {
 300         if fn.Pkg == nil {
 301                 return
 302         }
 303         pcg, ok := a.pcgs[fn.Pkg]
 304         if !ok {
 305                 pcg = &packageCallGraph{nodeIndex: make(map[*ssa.Function]int)}
 306                 a.pcgs[fn.Pkg] = pcg
 307         }
 308         pcg.nodeIndex[fn] = -1
 309 }
 310
 311 func (a *analysis) pcgAddEdge(caller, callee *ssa.Function) {
 312         if callee.Pkg != nil {
 313                 a.pcgs[callee.Pkg].addEdge(caller, callee)
 314         }
 315 }
 316
 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 {
 321
 322                 // TODO(adonovan): why is there no good way to iterate
 323                 // over the set bits of a big.Int?
 324                 var callees []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)
 329                         }
 330                 }
 331
 332                 var pos token.Pos
 333                 if n.fn != nil {
 334                         pos = funcToken(n.fn)
 335                 }
 336                 nodes = append(nodes, &PCGNodeJSON{
 337                         Func: anchorJSON{
 338                                 Text: n.pretty,
 339                                 Href: a.posURL(pos, len("func")),
 340                         },
 341                         Callees: callees,
 342                 })
 343         }
 344         return nodes
 345 }
 346
 347 type pcgNodesByPretty []*pcgNode
 348
 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) }