| 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 | } |
| 224 |
Members