.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/go/callgraph/cha/cha.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 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 //
  24 package cha // import "golang.org/x/tools/go/callgraph/cha"
  25
  26 import (
  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 //
  38 func 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 }