.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/godoc/analysis/implements.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 "implements" relation over all pairs of
   8 // named types in the program.  (The mark-up is done by typeinfo.go.)
   9
  10 // TODO(adonovan): do we want to report implements(C, I) where C and I
  11 // belong to different packages and at least one is not exported?
  12
  13 import (
  14         "go/types"
  15         "sort"
  16
  17         "golang.org/x/tools/go/types/typeutil"
  18 )
  19
  20 // computeImplements computes the "implements" relation over all pairs
  21 // of named types in allNamed.
  22 func computeImplements(cache *typeutil.MethodSetCache, allNamed []*types.Named) map[*types.Named]implementsFacts {
  23         // Information about a single type's method set.
  24         type msetInfo struct {
  25                 typ          types.Type
  26                 mset         *types.MethodSet
  27                 mask1, mask2 uint64
  28         }
  29
  30         initMsetInfo := func(info *msetInfo, typ types.Type) {
  31                 info.typ = typ
  32                 info.mset = cache.MethodSet(typ)
  33                 for i := 0; i < info.mset.Len(); i++ {
  34                         name := info.mset.At(i).Obj().Name()
  35                         info.mask1 |= 1 << methodBit(name[0])
  36                         info.mask2 |= 1 << methodBit(name[len(name)-1])
  37                 }
  38         }
  39
  40         // satisfies(T, U) reports whether type T satisfies type U.
  41         // U must be an interface.
  42         //
  43         // Since there are thousands of types (and thus millions of
  44         // pairs of types) and types.Assignable(T, U) is relatively
  45         // expensive, we compute assignability directly from the
  46         // method sets.  (At least one of T and U must be an
  47         // interface.)
  48         //
  49         // We use a trick (thanks gri!) related to a Bloom filter to
  50         // quickly reject most tests, which are false.  For each
  51         // method set, we precompute a mask, a set of bits, one per
  52         // distinct initial byte of each method name.  Thus the mask
  53         // for io.ReadWriter would be {'R','W'}.  AssignableTo(T, U)
  54         // cannot be true unless mask(T)&mask(U)==mask(U).
  55         //
  56         // As with a Bloom filter, we can improve precision by testing
  57         // additional hashes, e.g. using the last letter of each
  58         // method name, so long as the subset mask property holds.
  59         //
  60         // When analyzing the standard library, there are about 1e6
  61         // calls to satisfies(), of which 0.6% return true.  With a
  62         // 1-hash filter, 95% of calls avoid the expensive check; with
  63         // a 2-hash filter, this grows to 98.2%.
  64         satisfies := func(T, U *msetInfo) bool {
  65                 return T.mask1&U.mask1 == U.mask1 &&
  66                         T.mask2&U.mask2 == U.mask2 &&
  67                         containsAllIdsOf(T.mset, U.mset)
  68         }
  69
  70         // Information about a named type N, and perhaps also *N.
  71         type namedInfo struct {
  72                 isInterface bool
  73                 base        msetInfo // N
  74                 ptr         msetInfo // *N, iff N !isInterface
  75         }
  76
  77         var infos []namedInfo
  78
  79         // Precompute the method sets and their masks.
  80         for _, N := range allNamed {
  81                 var info namedInfo
  82                 initMsetInfo(&info.base, N)
  83                 _, info.isInterface = N.Underlying().(*types.Interface)
  84                 if !info.isInterface {
  85                         initMsetInfo(&info.ptr, types.NewPointer(N))
  86                 }
  87
  88                 if info.base.mask1|info.ptr.mask1 == 0 {
  89                         continue // neither N nor *N has methods
  90                 }
  91
  92                 infos = append(infos, info)
  93         }
  94
  95         facts := make(map[*types.Named]implementsFacts)
  96
  97         // Test all pairs of distinct named types (T, U).
  98         // TODO(adonovan): opt: compute (U, T) at the same time.
  99         for t := range infos {
 100                 T := &infos[t]
 101                 var to, from, fromPtr []types.Type
 102                 for u := range infos {
 103                         if t == u {
 104                                 continue
 105                         }
 106                         U := &infos[u]
 107                         switch {
 108                         case T.isInterface && U.isInterface:
 109                                 if satisfies(&U.base, &T.base) {
 110                                         to = append(to, U.base.typ)
 111                                 }
 112                                 if satisfies(&T.base, &U.base) {
 113                                         from = append(from, U.base.typ)
 114                                 }
 115                         case T.isInterface: // U concrete
 116                                 if satisfies(&U.base, &T.base) {
 117                                         to = append(to, U.base.typ)
 118                                 } else if satisfies(&U.ptr, &T.base) {
 119                                         to = append(to, U.ptr.typ)
 120                                 }
 121                         case U.isInterface: // T concrete
 122                                 if satisfies(&T.base, &U.base) {
 123                                         from = append(from, U.base.typ)
 124                                 } else if satisfies(&T.ptr, &U.base) {
 125                                         fromPtr = append(fromPtr, U.base.typ)
 126                                 }
 127                         }
 128                 }
 129
 130                 // Sort types (arbitrarily) to avoid nondeterminism.
 131                 sort.Sort(typesByString(to))
 132                 sort.Sort(typesByString(from))
 133                 sort.Sort(typesByString(fromPtr))
 134
 135                 facts[T.base.typ.(*types.Named)] = implementsFacts{to, from, fromPtr}
 136         }
 137
 138         return facts
 139 }
 140
 141 type implementsFacts struct {
 142         to      []types.Type // named or ptr-to-named types assignable to interface T
 143         from    []types.Type // named interfaces assignable from T
 144         fromPtr []types.Type // named interfaces assignable only from *T
 145 }
 146
 147 type typesByString []types.Type
 148
 149 func (p typesByString) Len() int           { return len(p) }
 150 func (p typesByString) Less(i, j int) bool { return p[i].String() < p[j].String() }
 151 func (p typesByString) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 152
 153 // methodBit returns the index of x in [a-zA-Z], or 52 if not found.
 154 func methodBit(x byte) uint64 {
 155         switch {
 156         case 'a' <= x && x <= 'z':
 157                 return uint64(x - 'a')
 158         case 'A' <= x && x <= 'Z':
 159                 return uint64(26 + x - 'A')
 160         }
 161         return 52 // all other bytes
 162 }
 163
 164 // containsAllIdsOf reports whether the method identifiers of T are a
 165 // superset of those in U.  If U belongs to an interface type, the
 166 // result is equal to types.Assignable(T, U), but is cheaper to compute.
 167 //
 168 // TODO(gri): make this a method of *types.MethodSet.
 169 //
 170 func containsAllIdsOf(T, U *types.MethodSet) bool {
 171         t, tlen := 0, T.Len()
 172         u, ulen := 0, U.Len()
 173         for t < tlen && u < ulen {
 174                 tMeth := T.At(t).Obj()
 175                 uMeth := U.At(u).Obj()
 176                 tId := tMeth.Id()
 177                 uId := uMeth.Id()
 178                 if tId > uId {
 179                         // U has a method T lacks: fail.
 180                         return false
 181                 }
 182                 if tId < uId {
 183                         // T has a method U lacks: ignore it.
 184                         t++
 185                         continue
 186                 }
 187                 // U and T both have a method of this Id.  Check types.
 188                 if !types.Identical(tMeth.Type(), uMeth.Type()) {
 189                         return false // type mismatch
 190                 }
 191                 u++
 192                 t++
 193         }
 194         return u == ulen
 195 }