.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/internal/apidiff/correspondence.go

   1 package apidiff
   2
   3 import (
   4         "go/types"
   5         "sort"
   6 )
   7
   8 // Two types are correspond if they are identical except for defined types,
   9 // which must correspond.
  10 //
  11 // Two defined types correspond if they can be interchanged in the old and new APIs,
  12 // possibly after a renaming.
  13 //
  14 // This is not a pure function. If we come across named types while traversing,
  15 // we establish correspondence.
  16 func (d *differ) correspond(old, new types.Type) bool {
  17         return d.corr(old, new, nil)
  18 }
  19
  20 // corr determines whether old and new correspond. The argument p is a list of
  21 // known interface identities, to avoid infinite recursion.
  22 //
  23 // corr calls itself recursively as much as possible, to establish more
  24 // correspondences and so check more of the API. E.g. if the new function has more
  25 // parameters than the old, compare all the old ones before returning false.
  26 //
  27 // Compare this to the implementation of go/types.Identical.
  28 func (d *differ) corr(old, new types.Type, p *ifacePair) bool {
  29         // Structure copied from types.Identical.
  30         switch old := old.(type) {
  31         case *types.Basic:
  32                 return types.Identical(old, new)
  33
  34         case *types.Array:
  35                 if new, ok := new.(*types.Array); ok {
  36                         return d.corr(old.Elem(), new.Elem(), p) && old.Len() == new.Len()
  37                 }
  38
  39         case *types.Slice:
  40                 if new, ok := new.(*types.Slice); ok {
  41                         return d.corr(old.Elem(), new.Elem(), p)
  42                 }
  43
  44         case *types.Map:
  45                 if new, ok := new.(*types.Map); ok {
  46                         return d.corr(old.Key(), new.Key(), p) && d.corr(old.Elem(), new.Elem(), p)
  47                 }
  48
  49         case *types.Chan:
  50                 if new, ok := new.(*types.Chan); ok {
  51                         return d.corr(old.Elem(), new.Elem(), p) && old.Dir() == new.Dir()
  52                 }
  53
  54         case *types.Pointer:
  55                 if new, ok := new.(*types.Pointer); ok {
  56                         return d.corr(old.Elem(), new.Elem(), p)
  57                 }
  58
  59         case *types.Signature:
  60                 if new, ok := new.(*types.Signature); ok {
  61                         pe := d.corr(old.Params(), new.Params(), p)
  62                         re := d.corr(old.Results(), new.Results(), p)
  63                         return old.Variadic() == new.Variadic() && pe && re
  64                 }
  65
  66         case *types.Tuple:
  67                 if new, ok := new.(*types.Tuple); ok {
  68                         for i := 0; i < old.Len(); i++ {
  69                                 if i >= new.Len() || !d.corr(old.At(i).Type(), new.At(i).Type(), p) {
  70                                         return false
  71                                 }
  72                         }
  73                         return old.Len() == new.Len()
  74                 }
  75
  76         case *types.Struct:
  77                 if new, ok := new.(*types.Struct); ok {
  78                         for i := 0; i < old.NumFields(); i++ {
  79                                 if i >= new.NumFields() {
  80                                         return false
  81                                 }
  82                                 of := old.Field(i)
  83                                 nf := new.Field(i)
  84                                 if of.Anonymous() != nf.Anonymous() ||
  85                                         old.Tag(i) != new.Tag(i) ||
  86                                         !d.corr(of.Type(), nf.Type(), p) ||
  87                                         !d.corrFieldNames(of, nf) {
  88                                         return false
  89                                 }
  90                         }
  91                         return old.NumFields() == new.NumFields()
  92                 }
  93
  94         case *types.Interface:
  95                 if new, ok := new.(*types.Interface); ok {
  96                         // Deal with circularity. See the comment in types.Identical.
  97                         q := &ifacePair{old, new, p}
  98                         for p != nil {
  99                                 if p.identical(q) {
 100                                         return true // same pair was compared before
 101                                 }
 102                                 p = p.prev
 103                         }
 104                         oldms := d.sortedMethods(old)
 105                         newms := d.sortedMethods(new)
 106                         for i, om := range oldms {
 107                                 if i >= len(newms) {
 108                                         return false
 109                                 }
 110                                 nm := newms[i]
 111                                 if d.methodID(om) != d.methodID(nm) || !d.corr(om.Type(), nm.Type(), q) {
 112                                         return false
 113                                 }
 114                         }
 115                         return old.NumMethods() == new.NumMethods()
 116                 }
 117
 118         case *types.Named:
 119                 if new, ok := new.(*types.Named); ok {
 120                         return d.establishCorrespondence(old, new)
 121                 }
 122                 if new, ok := new.(*types.Basic); ok {
 123                         // Basic types are defined types, too, so we have to support them.
 124
 125                         return d.establishCorrespondence(old, new)
 126                 }
 127
 128         default:
 129                 panic("unknown type kind")
 130         }
 131         return false
 132 }
 133
 134 // Compare old and new field names. We are determining correspondence across packages,
 135 // so just compare names, not packages. For an unexported, embedded field of named
 136 // type (non-named embedded fields are possible with aliases), we check that the type
 137 // names correspond. We check the types for correspondence before this is called, so
 138 // we've established correspondence.
 139 func (d *differ) corrFieldNames(of, nf *types.Var) bool {
 140         if of.Anonymous() && nf.Anonymous() && !of.Exported() && !nf.Exported() {
 141                 if on, ok := of.Type().(*types.Named); ok {
 142                         nn := nf.Type().(*types.Named)
 143                         return d.establishCorrespondence(on, nn)
 144                 }
 145         }
 146         return of.Name() == nf.Name()
 147 }
 148
 149 // Establish that old corresponds with new if it does not already
 150 // correspond to something else.
 151 func (d *differ) establishCorrespondence(old *types.Named, new types.Type) bool {
 152         oldname := old.Obj()
 153         oldc := d.correspondMap[oldname]
 154         if oldc == nil {
 155                 // For now, assume the types don't correspond unless they are from the old
 156                 // and new packages, respectively.
 157                 //
 158                 // This is too conservative. For instance,
 159                 //    [old] type A = q.B; [new] type A q.C
 160                 // could be OK if in package q, B is an alias for C.
 161                 // Or, using p as the name of the current old/new packages:
 162                 //    [old] type A = q.B; [new] type A int
 163                 // could be OK if in q,
 164                 //    [old] type B int; [new] type B = p.A
 165                 // In this case, p.A and q.B name the same type in both old and new worlds.
 166                 // Note that this case doesn't imply circular package imports: it's possible
 167                 // that in the old world, p imports q, but in the new, q imports p.
 168                 //
 169                 // However, if we didn't do something here, then we'd incorrectly allow cases
 170                 // like the first one above in which q.B is not an alias for q.C
 171                 //
 172                 // What we should do is check that the old type, in the new world's package
 173                 // of the same path, doesn't correspond to something other than the new type.
 174                 // That is a bit hard, because there is no easy way to find a new package
 175                 // matching an old one.
 176                 if newn, ok := new.(*types.Named); ok {
 177                         if old.Obj().Pkg() != d.old || newn.Obj().Pkg() != d.new {
 178                                 return old.Obj().Id() == newn.Obj().Id()
 179                         }
 180                 }
 181                 // If there is no correspondence, create one.
 182                 d.correspondMap[oldname] = new
 183                 // Check that the corresponding types are compatible.
 184                 d.checkCompatibleDefined(oldname, old, new)
 185                 return true
 186         }
 187         return types.Identical(oldc, new)
 188 }
 189
 190 func (d *differ) sortedMethods(iface *types.Interface) []*types.Func {
 191         ms := make([]*types.Func, iface.NumMethods())
 192         for i := 0; i < iface.NumMethods(); i++ {
 193                 ms[i] = iface.Method(i)
 194         }
 195         sort.Slice(ms, func(i, j int) bool { return d.methodID(ms[i]) < d.methodID(ms[j]) })
 196         return ms
 197 }
 198
 199 func (d *differ) methodID(m *types.Func) string {
 200         // If the method belongs to one of the two packages being compared, use
 201         // just its name even if it's unexported. That lets us treat unexported names
 202         // from the old and new packages as equal.
 203         if m.Pkg() == d.old || m.Pkg() == d.new {
 204                 return m.Name()
 205         }
 206         return m.Id()
 207 }
 208
 209 // Copied from the go/types package:
 210
 211 // An ifacePair is a node in a stack of interface type pairs compared for identity.
 212 type ifacePair struct {
 213         x, y *types.Interface
 214         prev *ifacePair
 215 }
 216
 217 func (p *ifacePair) identical(q *ifacePair) bool {
 218         return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x
 219 }