cmd/compile: deal with constructed types that have shapes in them

We convert type args to shape types inside instantiations. If an
instantiation constructs a compound type based on that shape type and
uses that as a type arg to another generic function being called, then
we have a type arg with a shape type embedded inside of it. In that
case, we need to substitute out those embedded shape types with their
underlying type.

If we don't do this, we may create extra unneeded shape types that
have these other shape types embedded in them. This may lead to
generating extra shape instantiations, and a mismatch between the
instantiations that we used in generating dictionaries and the
instantations that are actually called.

Updates #51303

Change-Id: Ieef894a5fac176cfd1415f95926086277ad09759
Reviewed-on: https://go-review.googlesource.com/c/go/+/387674
Reviewed-by: Keith Randall <khr@golang.org>
Trust: Dan Scales <danscales@google.com>
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>

2 files changed, 69 insertions, 0 deletions

diff --git a/test/typeparam/issue51303.go b/test/typeparam/issue51303.go
new file mode 100644
index 0000000000..5f4bdc0634
--- /dev/null
+++ b/test/typeparam/issue51303.go
@@ -0,0 +1,65 @@
+// run -gcflags=-G=3
+
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"fmt"
+)
+
+func main() {
+	x := [][]int{{1}}
+	y := [][]int{{2, 3}}
+	IntersectSS(x, y)
+}
+
+type list[E any] interface {
+	~[]E
+	Equal(x, y E) bool
+}
+
+// ss is a set of sets
+type ss[E comparable, T []E] []T
+
+func (ss[E, T]) Equal(a, b T) bool {
+	return SetEq(a, b)
+}
+
+func IntersectSS[E comparable](x, y [][]E) [][]E {
+	return IntersectT[[]E, ss[E, []E]](ss[E, []E](x), ss[E, []E](y))
+}
+
+func IntersectT[E any, L list[E]](x, y L) L {
+	var z L
+outer:
+	for _, xe := range x {
+		fmt.Println("xe", xe)
+		for _, ye := range y {
+			fmt.Println("ye", ye)
+			fmt.Println("x", x)
+			if x.Equal(xe, ye) {
+				fmt.Println("appending")
+				z = append(z, xe)
+				continue outer
+			}
+		}
+	}
+	return z
+}
+
+func SetEq[S []E, E comparable](x, y S) bool {
+	fmt.Println("SetEq", x, y)
+outer:
+	for _, xe := range x {
+		for _, ye := range y {
+			if xe == ye {
+				continue outer
+			}
+		}
+		return false // xs wasn't found in y
+	}
+	return true
+}
diff --git a/test/typeparam/issue51303.out b/test/typeparam/issue51303.out
new file mode 100644
index 0000000000..34b3be32dd
--- /dev/null
+++ b/test/typeparam/issue51303.out
@@ -0,0 +1,4 @@
+xe [1]
+ye [2 3]
+x [[1]]
+SetEq [1] [2 3]