.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.1.0/internal/apidiff/correspondence.go

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