Adding upstream version 1.1.0.upstream/1.1.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 288 insertions, 0 deletions

diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/apidiff/correspondence.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/apidiff/correspondence.go
new file mode 100644
index 0000000..ee00bc0
--- /dev/null
+++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/apidiff/correspondence.go
@@ -0,0 +1,288 @@
+package apidiff
+
+import (
+	"fmt"
+	"go/types"
+	"sort"
+)
+
+// Two types are correspond if they are identical except for defined types,
+// which must correspond.
+//
+// Two defined types correspond if they can be interchanged in the old and new APIs,
+// possibly after a renaming.
+//
+// This is not a pure function. If we come across named types while traversing,
+// we establish correspondence.
+func (d *differ) correspond(old, new types.Type) bool {
+	return d.corr(old, new, nil)
+}
+
+// corr determines whether old and new correspond. The argument p is a list of
+// known interface identities, to avoid infinite recursion.
+//
+// corr calls itself recursively as much as possible, to establish more
+// correspondences and so check more of the API. E.g. if the new function has more
+// parameters than the old, compare all the old ones before returning false.
+//
+// Compare this to the implementation of go/types.Identical.
+func (d *differ) corr(old, new types.Type, p *ifacePair) bool {
+	// Structure copied from types.Identical.
+	switch old := old.(type) {
+	case *types.Basic:
+		return types.Identical(old, new)
+
+	case *types.Array:
+		if new, ok := new.(*types.Array); ok {
+			return d.corr(old.Elem(), new.Elem(), p) && old.Len() == new.Len()
+		}
+
+	case *types.Slice:
+		if new, ok := new.(*types.Slice); ok {
+			return d.corr(old.Elem(), new.Elem(), p)
+		}
+
+	case *types.Map:
+		if new, ok := new.(*types.Map); ok {
+			return d.corr(old.Key(), new.Key(), p) && d.corr(old.Elem(), new.Elem(), p)
+		}
+
+	case *types.Chan:
+		if new, ok := new.(*types.Chan); ok {
+			return d.corr(old.Elem(), new.Elem(), p) && old.Dir() == new.Dir()
+		}
+
+	case *types.Pointer:
+		if new, ok := new.(*types.Pointer); ok {
+			return d.corr(old.Elem(), new.Elem(), p)
+		}
+
+	case *types.Signature:
+		if new, ok := new.(*types.Signature); ok {
+			pe := d.corr(old.Params(), new.Params(), p)
+			re := d.corr(old.Results(), new.Results(), p)
+			return old.Variadic() == new.Variadic() && pe && re
+		}
+
+	case *types.Tuple:
+		if new, ok := new.(*types.Tuple); ok {
+			for i := 0; i < old.Len(); i++ {
+				if i >= new.Len() || !d.corr(old.At(i).Type(), new.At(i).Type(), p) {
+					return false
+				}
+			}
+			return old.Len() == new.Len()
+		}
+
+	case *types.Struct:
+		if new, ok := new.(*types.Struct); ok {
+			for i := 0; i < old.NumFields(); i++ {
+				if i >= new.NumFields() {
+					return false
+				}
+				of := old.Field(i)
+				nf := new.Field(i)
+				if of.Anonymous() != nf.Anonymous() ||
+					old.Tag(i) != new.Tag(i) ||
+					!d.corr(of.Type(), nf.Type(), p) ||
+					!d.corrFieldNames(of, nf) {
+					return false
+				}
+			}
+			return old.NumFields() == new.NumFields()
+		}
+
+	case *types.Interface:
+		if new, ok := new.(*types.Interface); ok {
+			// Deal with circularity. See the comment in types.Identical.
+			q := &ifacePair{old, new, p}
+			for p != nil {
+				if p.identical(q) {
+					return true // same pair was compared before
+				}
+				p = p.prev
+			}
+			oldms := d.sortedMethods(old)
+			newms := d.sortedMethods(new)
+			for i, om := range oldms {
+				if i >= len(newms) {
+					return false
+				}
+				nm := newms[i]
+				if d.methodID(om) != d.methodID(nm) || !d.corr(om.Type(), nm.Type(), q) {
+					return false
+				}
+			}
+			return old.NumMethods() == new.NumMethods()
+		}
+
+	case *types.Named:
+		if new, ok := new.(*types.Named); ok {
+			return d.establishCorrespondence(old, new)
+		}
+		if new, ok := new.(*types.Basic); ok {
+			// Basic types are defined types, too, so we have to support them.
+
+			return d.establishCorrespondence(old, new)
+		}
+
+	case *types.TypeParam:
+		if new, ok := new.(*types.TypeParam); ok {
+			if old.Index() == new.Index() {
+				return true
+			}
+		}
+
+	default:
+		panic(fmt.Sprintf("unknown type kind %T", old))
+	}
+	return false
+}
+
+// Compare old and new field names. We are determining correspondence across packages,
+// so just compare names, not packages. For an unexported, embedded field of named
+// type (non-named embedded fields are possible with aliases), we check that the type
+// names correspond. We check the types for correspondence before this is called, so
+// we've established correspondence.
+func (d *differ) corrFieldNames(of, nf *types.Var) bool {
+	if of.Anonymous() && nf.Anonymous() && !of.Exported() && !nf.Exported() {
+		if on, ok := of.Type().(*types.Named); ok {
+			nn := nf.Type().(*types.Named)
+			return d.establishCorrespondence(on, nn)
+		}
+	}
+	return of.Name() == nf.Name()
+}
+
+// Establish that old corresponds with new if it does not already
+// correspond to something else.
+func (d *differ) establishCorrespondence(old *types.Named, new types.Type) bool {
+	oldname := old.Obj()
+	oldc := d.correspondMap[oldname]
+	if oldc == nil {
+		// For now, assume the types don't correspond unless they are from the old
+		// and new packages, respectively.
+		//
+		// This is too conservative. For instance,
+		//    [old] type A = q.B; [new] type A q.C
+		// could be OK if in package q, B is an alias for C.
+		// Or, using p as the name of the current old/new packages:
+		//    [old] type A = q.B; [new] type A int
+		// could be OK if in q,
+		//    [old] type B int; [new] type B = p.A
+		// In this case, p.A and q.B name the same type in both old and new worlds.
+		// Note that this case doesn't imply circular package imports: it's possible
+		// that in the old world, p imports q, but in the new, q imports p.
+		//
+		// However, if we didn't do something here, then we'd incorrectly allow cases
+		// like the first one above in which q.B is not an alias for q.C
+		//
+		// What we should do is check that the old type, in the new world's package
+		// of the same path, doesn't correspond to something other than the new type.
+		// That is a bit hard, because there is no easy way to find a new package
+		// matching an old one.
+		if newn, ok := new.(*types.Named); ok {
+			if old.Obj().Pkg() != d.old || newn.Obj().Pkg() != d.new {
+				return old.Obj().Id() == newn.Obj().Id()
+			}
+			// Prior to generics, any two named types could correspond.
+			// Two named types cannot correspond if their type parameter lists don't match.
+			if !typeParamListsMatch(old.TypeParams(), newn.TypeParams()) {
+				return false
+			}
+		}
+		// If there is no correspondence, create one.
+		d.correspondMap[oldname] = new
+		// Check that the corresponding types are compatible.
+		d.checkCompatibleDefined(oldname, old, new)
+		return true
+	}
+	return typesEquivalent(oldc, new)
+}
+
+// Two list of type parameters match if they are the same length, and
+// the constraints of corresponding type parameters are identical.
+func typeParamListsMatch(tps1, tps2 *types.TypeParamList) bool {
+	if tps1.Len() != tps2.Len() {
+		return false
+	}
+	for i := 0; i < tps1.Len(); i++ {
+		if !types.Identical(tps1.At(i).Constraint(), tps2.At(i).Constraint()) {
+			return false
+		}
+	}
+	return true
+}
+
+// typesEquivalent reports whether two types are identical, or if
+// the types have identical type param lists except that one type has nil
+// constraints.
+//
+// This allows us to match a Type from a method receiver or arg to the Type from
+// the declaration.
+func typesEquivalent(old, new types.Type) bool {
+	if types.Identical(old, new) {
+		return true
+	}
+	// Handle two types with the same type params, one
+	// having constraints and one not.
+	oldn, ok := old.(*types.Named)
+	if !ok {
+		return false
+	}
+	newn, ok := new.(*types.Named)
+	if !ok {
+		return false
+	}
+	oldps := oldn.TypeParams()
+	newps := newn.TypeParams()
+	if oldps.Len() != newps.Len() {
+		return false
+	}
+	if oldps.Len() == 0 {
+		// Not generic types.
+		return false
+	}
+	for i := 0; i < oldps.Len(); i++ {
+		oldp := oldps.At(i)
+		newp := newps.At(i)
+		if oldp.Constraint() == nil || newp.Constraint() == nil {
+			return true
+		}
+		if !types.Identical(oldp.Constraint(), newp.Constraint()) {
+			return false
+		}
+	}
+	return true
+}
+
+func (d *differ) sortedMethods(iface *types.Interface) []*types.Func {
+	ms := make([]*types.Func, iface.NumMethods())
+	for i := 0; i < iface.NumMethods(); i++ {
+		ms[i] = iface.Method(i)
+	}
+	sort.Slice(ms, func(i, j int) bool { return d.methodID(ms[i]) < d.methodID(ms[j]) })
+	return ms
+}
+
+func (d *differ) methodID(m *types.Func) string {
+	// If the method belongs to one of the two packages being compared, use
+	// just its name even if it's unexported. That lets us treat unexported names
+	// from the old and new packages as equal.
+	if m.Pkg() == d.old || m.Pkg() == d.new {
+		return m.Name()
+	}
+	return m.Id()
+}
+
+// Copied from the go/types package:
+
+// An ifacePair is a node in a stack of interface type pairs compared for identity.
+type ifacePair struct {
+	x, y *types.Interface
+	prev *ifacePair
+}
+
+func (p *ifacePair) identical(q *ifacePair) bool {
+	return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x
+}