correspondence.go

Documentation: golang.org/x/tools/internal/apidiff

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