apidiff: handle generic types

Two changes were required to handle generic types.

First, the code that tries to establish a correspondence between two
types could see one types.Type value that came from the type
declaration, looking like this:

    type Foo[T any]

and another types.Type value that came from a method argument or
return value, looking like this, with no constraint:

    func (Foo[T]) ...

We were using types.Identical in this case, but that function
(rightly, according to its narrow definition) returns false
when given `Foo[T any]` and `Foo[T]`.

So I defined typesEquivalent, which is like types.Identical
but succeeds in the above case.

The second change was also to the establishCorrespondence method.
Previously, any two named types could correspond. With generics, that
isn't true if the types have different type parameters.  Here we will
always have the full types, so we check that there are the same number
of type params and they have identical constraints. The type param
names don't matter.

Also, use cmp.Diff for TestChanges to make it easier to fix broken
tests.

Also, update the config for go/packages in the apidiff
command. Apparently there were breaking changes to that package that
made `apidiff -w` fail.

Also, fix a gorelease test because the output of apidiff has changed
for incompatible generic types.

Change-Id: I0a75eb43f3ce4b55748f86a2c33a1cea6d52b35d
Reviewed-on: https://go-review.googlesource.com/c/exp/+/411076
Run-TryBot: Jonathan Amsterdam <jba@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Jean de Klerk <deklerk@google.com>
diff --git a/apidiff/apidiff_test.go b/apidiff/apidiff_test.go
index 5f23542..9d55e14 100644
--- a/apidiff/apidiff_test.go
+++ b/apidiff/apidiff_test.go
@@ -8,12 +8,12 @@
 	"os"
 	"os/exec"
 	"path/filepath"
-	"reflect"
 	"runtime"
 	"sort"
 	"strings"
 	"testing"
 
+	"github.com/google/go-cmp/cmp"
 	"golang.org/x/tools/go/packages"
 )
 
@@ -40,12 +40,12 @@
 	report := Changes(oldpkg.Types, newpkg.Types)
 
 	got := report.messages(false)
-	if !reflect.DeepEqual(got, wanti) {
-		t.Errorf("incompatibles: got %v\nwant %v\n", got, wanti)
+	if diff := cmp.Diff(wanti, got); diff != "" {
+		t.Errorf("incompatibles: mismatch (-want, +got)\n%s", diff)
 	}
 	got = report.messages(true)
-	if !reflect.DeepEqual(got, wantc) {
-		t.Errorf("compatibles: got %v\nwant %v\n", got, wantc)
+	if diff := cmp.Diff(wantc, got); diff != "" {
+		t.Errorf("compatibles: mismatch (-want, +got)\n%s", diff)
 	}
 }
 
diff --git a/apidiff/correspondence.go b/apidiff/correspondence.go
index 34ce797..ee00bc0 100644
--- a/apidiff/correspondence.go
+++ b/apidiff/correspondence.go
@@ -185,6 +185,11 @@
 			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
@@ -192,7 +197,63 @@
 		d.checkCompatibleDefined(oldname, old, new)
 		return true
 	}
-	return types.Identical(oldc, new)
+	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 {
diff --git a/apidiff/testdata/tests.go b/apidiff/testdata/tests.go
index 61e9026..92823b2 100644
--- a/apidiff/testdata/tests.go
+++ b/apidiff/testdata/tests.go
@@ -672,7 +672,7 @@
 	E string
 }
 
-//////////////// Method sets
+//// Method sets
 
 // old
 type SM struct {
@@ -925,3 +925,45 @@
 // i Vj4: changed from k4 to j4
 // e.g. p.Vj4 = p.Vk4
 type j4 k4
+
+//// Generics
+
+// old
+type G[T any] []T
+
+// new
+// OK: param name change
+type G[A any] []A
+
+// old
+type GM[A, B comparable] map[A]B
+
+// new
+// i GM: changed from map[A]B to map[B]A
+type GM[A, B comparable] map[B]A
+
+// old
+type GT[V any] struct {
+}
+
+func (GT[V]) M(*GT[V]) {}
+
+// new
+// OK
+type GT[V any] struct {
+}
+
+func (GT[V]) M(*GT[V]) {}
+
+// old
+type GT2[V any] struct {
+}
+
+func (GT2[V]) M(*GT2[V]) {}
+
+// new
+// i GT2: changed from GT2[V any] to GT2[V comparable]
+type GT2[V comparable] struct {
+}
+
+func (GT2[V]) M(*GT2[V]) {}
diff --git a/cmd/apidiff/main.go b/cmd/apidiff/main.go
index 61677fc..92b763c 100644
--- a/cmd/apidiff/main.go
+++ b/cmd/apidiff/main.go
@@ -97,7 +97,9 @@
 }
 
 func loadPackage(importPath string) (*packages.Package, error) {
-	cfg := &packages.Config{Mode: packages.LoadTypes}
+	cfg := &packages.Config{Mode: packages.LoadTypes |
+		packages.NeedName | packages.NeedTypes | packages.NeedImports | packages.NeedDeps,
+	}
 	pkgs, err := packages.Load(cfg, importPath)
 	if err != nil {
 		return nil, err
diff --git a/cmd/gorelease/testdata/generics/changed_param.test b/cmd/gorelease/testdata/generics/changed_param.test
index e989e5a..8415e48 100644
--- a/cmd/gorelease/testdata/generics/changed_param.test
+++ b/cmd/gorelease/testdata/generics/changed_param.test
@@ -3,7 +3,7 @@
 -- want --
 # example.com/generics/a
 ## incompatible changes
-Foo[V any].Value: changed from func() V to func() any
+Foo: changed from Foo[V any] to Foo[V Number]
 ## compatible changes
 Number: added
 
diff --git a/go.mod b/go.mod
index a554448..c64f300 100644
--- a/go.mod
+++ b/go.mod
@@ -8,6 +8,7 @@
 )
 
 require (
+	github.com/google/go-cmp v0.5.8 // indirect
 	golang.org/x/sys v0.0.0-20211019181941-9d821ace8654 // indirect
 	golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 // indirect
 )
diff --git a/go.sum b/go.sum
index c48025d..d6c4d58 100644
--- a/go.sum
+++ b/go.sum
@@ -1,3 +1,5 @@
+github.com/google/go-cmp v0.5.8 h1:e6P7q2lk1O+qJJb4BtCQXlK8vWEO8V1ZeuEdJNOqZyg=
+github.com/google/go-cmp v0.5.8/go.mod h1:17dUlkBOakJ0+DkrSSNjCkIjxS6bF9zb3elmeNGIjoY=
 golang.org/x/mod v0.6.0-dev.0.20211013180041-c96bc1413d57 h1:LQmS1nU0twXLA96Kt7U9qtHJEbBk3z6Q0V4UXjZkpr4=
 golang.org/x/mod v0.6.0-dev.0.20211013180041-c96bc1413d57/go.mod h1:3p9vT2HGsQu2K1YbXdKPJLVgG5VJdoTa1poYQBtP1AY=
 golang.org/x/mod v0.6.0-dev.0.20220106191415-9b9b3d81d5e3 h1:kQgndtyPBW/JIYERgdxfwMYh3AVStj88WQTlNDi2a+o=