go/ssa: Adds datastructures for function instantiation.

Adds [unexported] fields to Function for Origin, TypeParams, and TypeArguments. Populates TypeParameters for package level functions and methods.

Adds datastructures for creating function instantiations. Tracking unique instantiations on Program.

Adds map for canonicalizing lists of types.

Updates golang/go#48525

Change-Id: I9cb01f2ed24a9cacf3a515444d0cc0474333e417
Reviewed-on: https://go-review.googlesource.com/c/tools/+/397714
Reviewed-by: Robert Findley <rfindley@google.com>
Trust: Tim King <taking@google.com>
Run-TryBot: Tim King <taking@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>

10 files changed, 520 insertions, 32 deletions

diff --git a/go/ssa/builder.go b/go/ssa/builder.go
index baf374d33..5470add22 100644
--- a/go/ssa/builder.go
+++ b/go/ssa/builder.go
@@ -2213,6 +2213,7 @@ func (b *builder) buildFunctionBody(fn *Function) {
 	var functype *ast.FuncType
 	switch n := fn.syntax.(type) {
 	case nil:
+		// TODO(taking): Temporarily this can be the body of a generic function.
 		return // not a Go source function.  (Synthetic, or from object file.)
 	case *ast.FuncDecl:
 		functype = n.Type
@@ -2351,7 +2352,7 @@ func (p *Package) build() {
 	// TODO(adonovan): ideally belongs in memberFromObject, but
 	// that would require package creation in topological order.
 	for name, mem := range p.Members {
-		if ast.IsExported(name) {
+		if ast.IsExported(name) && !isGeneric(mem) {
 			p.Prog.needMethodsOf(mem.Type(), &p.created)
 		}
 	}
diff --git a/go/ssa/builder_test.go b/go/ssa/builder_test.go
index c45f930b3..3990eff29 100644
--- a/go/ssa/builder_test.go
+++ b/go/ssa/builder_test.go
@@ -20,6 +20,7 @@ import (
 	"golang.org/x/tools/go/loader"
 	"golang.org/x/tools/go/ssa"
 	"golang.org/x/tools/go/ssa/ssautil"
+	"golang.org/x/tools/internal/typeparams"
 )
 
 func isEmpty(f *ssa.Function) bool { return f.Blocks == nil }
@@ -498,3 +499,65 @@ func h(error)
 		t.Errorf("expected a single Phi (for the range index), got %d", phis)
 	}
 }
+
+// TestGenericDecls ensures that *unused* generic types, methods and functions
+// signatures can be built.
+//
+// TODO(taking): Add calls from non-generic functions to instantiations of generic functions.
+// TODO(taking): Add globals with types that are instantiations of generic functions.
+func TestGenericDecls(t *testing.T) {
+	if !typeparams.Enabled {
+		t.Skip("TestGenericDecls only works with type parameters enabled.")
+	}
+	const input = `
+package p
+
+import "unsafe"
+
+type Pointer[T any] struct {
+	v unsafe.Pointer
+}
+
+func (x *Pointer[T]) Load() *T {
+	return (*T)(LoadPointer(&x.v))
+}
+
+func Load[T any](x *Pointer[T]) *T {
+	return x.Load()
+}
+
+func LoadPointer(addr *unsafe.Pointer) (val unsafe.Pointer)
+`
+	// The SSA members for this package should look something like this:
+	//          func  LoadPointer func(addr *unsafe.Pointer) (val unsafe.Pointer)
+	//      type  Pointer     struct{v unsafe.Pointer}
+	//        method (*Pointer[T any]) Load() *T
+	//      func  init        func()
+	//      var   init$guard  bool
+
+	// Parse
+	var conf loader.Config
+	f, err := conf.ParseFile("<input>", input)
+	if err != nil {
+		t.Fatalf("parse: %v", err)
+	}
+	conf.CreateFromFiles("p", f)
+
+	// Load
+	lprog, err := conf.Load()
+	if err != nil {
+		t.Fatalf("Load: %v", err)
+	}
+
+	// Create and build SSA
+	prog := ssautil.CreateProgram(lprog, 0)
+	p := prog.Package(lprog.Package("p").Pkg)
+	p.Build()
+
+	if load := p.Func("Load"); typeparams.ForSignature(load.Signature).Len() != 1 {
+		t.Errorf("expected a single type param T for Load got %q", load.Signature)
+	}
+	if ptr := p.Type("Pointer"); typeparams.ForNamed(ptr.Type().(*types.Named)).Len() != 1 {
+		t.Errorf("expected a single type param T for Pointer got %q", ptr.Type())
+	}
+}
diff --git a/go/ssa/create.go b/go/ssa/create.go
index 816d22e48..7ca68f130 100644
--- a/go/ssa/create.go
+++ b/go/ssa/create.go
@@ -16,6 +16,7 @@ import (
 	"sync"
 
 	"golang.org/x/tools/go/types/typeutil"
+	"golang.org/x/tools/internal/typeparams"
 )
 
 // NewProgram returns a new SSA Program.
@@ -24,12 +25,15 @@ import (
 //
 func NewProgram(fset *token.FileSet, mode BuilderMode) *Program {
 	prog := &Program{
-		Fset:     fset,
-		imported: make(map[string]*Package),
-		packages: make(map[*types.Package]*Package),
-		thunks:   make(map[selectionKey]*Function),
-		bounds:   make(map[*types.Func]*Function),
-		mode:     mode,
+		Fset:      fset,
+		imported:  make(map[string]*Package),
+		packages:  make(map[*types.Package]*Package),
+		thunks:    make(map[selectionKey]*Function),
+		bounds:    make(map[*types.Func]*Function),
+		mode:      mode,
+		canon:     newCanonizer(),
+		ctxt:      typeparams.NewContext(),
+		instances: make(map[*Function]*instanceSet),
 	}
 
 	h := typeutil.MakeHasher() // protected by methodsMu, in effect
@@ -85,20 +89,39 @@ func memberFromObject(pkg *Package, obj types.Object, syntax ast.Node) {
 			pkg.ninit++
 			name = fmt.Sprintf("init#%d", pkg.ninit)
 		}
+
+		// Collect type parameters if this is a generic function/method.
+		var tparams []*typeparams.TypeParam
+		for i, rtparams := 0, typeparams.RecvTypeParams(sig); i < rtparams.Len(); i++ {
+			tparams = append(tparams, rtparams.At(i))
+		}
+		for i, sigparams := 0, typeparams.ForSignature(sig); i < sigparams.Len(); i++ {
+			tparams = append(tparams, sigparams.At(i))
+		}
+
 		fn := &Function{
-			name:      name,
-			object:    obj,
-			Signature: sig,
-			syntax:    syntax,
-			pos:       obj.Pos(),
-			Pkg:       pkg,
-			Prog:      pkg.Prog,
-			info:      pkg.info,
+			name:        name,
+			object:      obj,
+			Signature:   sig,
+			syntax:      syntax,
+			pos:         obj.Pos(),
+			Pkg:         pkg,
+			Prog:        pkg.Prog,
+			info:        pkg.info,
+			_TypeParams: tparams,
 		}
 		pkg.created.Add(fn)
 		if syntax == nil {
 			fn.Synthetic = "loaded from gc object file"
 		}
+		if len(tparams) > 0 {
+			fn.Prog.createInstanceSet(fn)
+		}
+		if len(tparams) > 0 && syntax != nil {
+			fn.Synthetic = "generic function"
+			// TODO(taking): Allow for the function to be built once type params are supported.
+			fn.syntax = nil // Treating as an external function temporarily.
+		}
 
 		pkg.objects[obj] = fn
 		if sig.Recv() == nil {
diff --git a/go/ssa/func.go b/go/ssa/func.go
index 1aea65372..e00f50e61 100644
--- a/go/ssa/func.go
+++ b/go/ssa/func.go
@@ -263,6 +263,7 @@ func (f *Function) finishBody() {
 	// clear remaining stateful variables
 	f.namedResults = nil // (used by lifting)
 	f.info = nil
+	f.subst = nil
 
 	numberRegisters(f)
 }
diff --git a/go/ssa/instantiate.go b/go/ssa/instantiate.go
new file mode 100644
index 000000000..871d708ba
--- /dev/null
+++ b/go/ssa/instantiate.go
@@ -0,0 +1,172 @@
+// 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 ssa
+
+import (
+	"fmt"
+	"go/ast"
+	"go/types"
+
+	"golang.org/x/tools/internal/typeparams"
+)
+
+// Instances returns all of the instances generated by runtime types for this function in an unspecified order.
+//
+// Thread-safe.
+//
+// This is an experimental interface! It may change without warning.
+func (prog *Program) _Instances(fn *Function) []*Function {
+	if len(fn._TypeParams) == 0 {
+		return nil
+	}
+
+	prog.methodsMu.Lock()
+	defer prog.methodsMu.Unlock()
+	return prog.instances[fn].list()
+}
+
+// A set of instantiations of a generic function fn.
+type instanceSet struct {
+	fn        *Function               // len(fn._TypeParams) > 0 and len(fn._TypeArgs) == 0.
+	instances map[*typeList]*Function // canonical type arguments to an instance.
+	syntax    *ast.FuncDecl           // fn.syntax copy for instantiating after fn is done. nil on synthetic packages.
+	info      *types.Info             // fn.pkg.info copy for building after fn is done.. nil on synthetic packages.
+
+	// TODO(taking): Consider ways to allow for clearing syntax and info when done building.
+	// May require a public API change as MethodValue can request these be built after prog.Build() is done.
+}
+
+func (insts *instanceSet) list() []*Function {
+	if insts == nil {
+		return nil
+	}
+
+	fns := make([]*Function, 0, len(insts.instances))
+	for _, fn := range insts.instances {
+		fns = append(fns, fn)
+	}
+	return fns
+}
+
+// createInstanceSet adds a new instanceSet for a generic function fn if one does not exist.
+//
+// Precondition: fn is a package level declaration (function or method).
+//
+// EXCLUSIVE_LOCKS_ACQUIRED(prog.methodMu)
+//
+func (prog *Program) createInstanceSet(fn *Function) {
+	assert(len(fn._TypeParams) > 0 && len(fn._TypeArgs) == 0, "Can only create instance sets for generic functions")
+
+	prog.methodsMu.Lock()
+	defer prog.methodsMu.Unlock()
+
+	syntax, _ := fn.syntax.(*ast.FuncDecl)
+	assert((syntax == nil) == (fn.syntax == nil), "fn.syntax is either nil or a *ast.FuncDecl")
+
+	if _, ok := prog.instances[fn]; !ok {
+		prog.instances[fn] = &instanceSet{
+			fn:     fn,
+			syntax: syntax,
+			info:   fn.info,
+		}
+	}
+}
+
+// needsInstance returns an Function that that is the instantiation of fn with the type arguments targs.
+//
+// Any CREATEd instance is added to cr.
+//
+// EXCLUSIVE_LOCKS_ACQUIRED(prog.methodMu)
+func (prog *Program) needsInstance(fn *Function, targs []types.Type, cr *creator) *Function {
+	prog.methodsMu.Lock()
+	defer prog.methodsMu.Unlock()
+
+	return prog.instances[fn].lookupOrCreate(targs, cr)
+}
+
+// lookupOrCreate returns the instantiation of insts.fn using targs.
+// If the instantiation is reported, this is added to cr.
+//
+func (insts *instanceSet) lookupOrCreate(targs []types.Type, cr *creator) *Function {
+	if insts.instances == nil {
+		insts.instances = make(map[*typeList]*Function)
+	}
+
+	// canonicalize on a tuple of targs. Sig is not unique.
+	//
+	// func A[T any]() {
+	//   var x T
+	//   fmt.Println("%T", x)
+	// }
+	key := insts.fn.Prog.canon.List(targs)
+	if inst, ok := insts.instances[key]; ok {
+		return inst
+	}
+	instance := createInstance(insts.fn, targs, insts.info, insts.syntax, cr)
+
+	// TODO(taking): Allow for the function to be built after monomorphization is supported.
+	instance.syntax = nil // treat instance as an external function to prevent building.
+
+	insts.instances[key] = instance
+	return instance
+}
+
+// createInstance returns an CREATEd instantiation of fn using targs.
+//
+// Function is added to cr.
+//
+func createInstance(fn *Function, targs []types.Type, info *types.Info, syntax ast.Node, cr *creator) *Function {
+	prog := fn.Prog
+	var sig *types.Signature
+	var obj *types.Func
+	if recv := fn.Signature.Recv(); recv != nil {
+		// method
+		// instantiates m with targs and returns a canonical representative for this method.
+		m := fn.object.(*types.Func)
+		recv := recvType(m)
+		if p, ok := recv.(*types.Pointer); ok {
+			recv = p.Elem()
+		}
+		named := recv.(*types.Named)
+		inst, err := typeparams.Instantiate(prog.ctxt, typeparams.NamedTypeOrigin(named), targs, false)
+		if err != nil {
+			panic(err)
+		}
+		canon, _, _ := types.LookupFieldOrMethod(prog.canon.Type(inst), true, m.Pkg(), m.Name())
+		obj = canon.(*types.Func)
+		sig = obj.Type().(*types.Signature)
+	} else {
+		instSig, err := typeparams.Instantiate(prog.ctxt, fn.Signature, targs, false)
+		if err != nil {
+			panic(err)
+		}
+		instance, ok := instSig.(*types.Signature)
+		if !ok {
+			panic("Instantiate of a Signature returned a non-signature")
+		}
+		obj = fn.object.(*types.Func) // instantiation does not exist yet
+		sig = prog.canon.Type(instance).(*types.Signature)
+	}
+
+	name := fmt.Sprintf("%s[%s]", fn.Name(), targs) // may not be unique
+	synthetic := fmt.Sprintf("instantiation of %s", fn.Name())
+	instance := &Function{
+		name:        name,
+		object:      obj,
+		Signature:   sig,
+		Synthetic:   synthetic,
+		syntax:      syntax, // on synthetic packages syntax is nil.
+		_Origin:     fn,
+		pos:         obj.Pos(),
+		Pkg:         nil,
+		Prog:        fn.Prog,
+		_TypeParams: fn._TypeParams,
+		_TypeArgs:   targs,
+		info:        info, // on synthetic packages info is nil.
+		subst:       makeSubster(prog.ctxt, fn._TypeParams, targs, false),
+	}
+	cr.Add(instance)
+	return instance
+}
diff --git a/go/ssa/instantiate_test.go b/go/ssa/instantiate_test.go
new file mode 100644
index 000000000..6dbe0246c
--- /dev/null
+++ b/go/ssa/instantiate_test.go
@@ -0,0 +1,126 @@
+// 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 ssa
+
+// Note: Tests use unexported functions.
+
+import (
+	"bytes"
+	"go/types"
+	"reflect"
+	"sort"
+	"testing"
+
+	"golang.org/x/tools/go/loader"
+	"golang.org/x/tools/internal/typeparams"
+)
+
+// TestNeedsInstance ensures that new method instances can be created via needsInstance,
+// that TypeArgs are as expected, and can be accessed via _Instances.
+func TestNeedsInstance(t *testing.T) {
+	if !typeparams.Enabled {
+		return
+	}
+	const input = `
+package p
+
+import "unsafe"
+
+type Pointer[T any] struct {
+	v unsafe.Pointer
+}
+
+func (x *Pointer[T]) Load() *T {
+	return (*T)(LoadPointer(&x.v))
+}
+
+func LoadPointer(addr *unsafe.Pointer) (val unsafe.Pointer)
+`
+	// The SSA members for this package should look something like this:
+	//      func  LoadPointer func(addr *unsafe.Pointer) (val unsafe.Pointer)
+	//      type  Pointer     struct{v unsafe.Pointer}
+	//        method (*Pointer[T any]) Load() *T
+	//      func  init        func()
+	//      var   init$guard  bool
+
+	// Parse
+	var conf loader.Config
+	f, err := conf.ParseFile("<input>", input)
+	if err != nil {
+		t.Fatalf("parse: %v", err)
+	}
+	conf.CreateFromFiles("p", f)
+
+	// Load
+	lprog, err := conf.Load()
+	if err != nil {
+		t.Fatalf("Load: %v", err)
+	}
+
+	// Create and build SSA
+	prog := NewProgram(lprog.Fset, 0)
+
+	for _, info := range lprog.AllPackages {
+		prog.CreatePackage(info.Pkg, info.Files, &info.Info, info.Importable)
+	}
+
+	p := prog.Package(lprog.Package("p").Pkg)
+	p.Build()
+
+	ptr := p.Type("Pointer").Type().(*types.Named)
+	if ptr.NumMethods() != 1 {
+		t.Fatalf("Expected Pointer to have 1 method. got %d", ptr.NumMethods())
+	}
+
+	obj := ptr.Method(0)
+	if obj.Name() != "Load" {
+		t.Errorf("Expected Pointer to have method named 'Load'. got %q", obj.Name())
+	}
+
+	meth := prog.FuncValue(obj)
+
+	var cr creator
+	intSliceTyp := types.NewSlice(types.Typ[types.Int])
+	instance := prog.needsInstance(meth, []types.Type{intSliceTyp}, &cr)
+	if len(cr) != 1 {
+		t.Errorf("Expected first instance to create a function. got %d created functions", len(cr))
+	}
+	if instance._Origin != meth {
+		t.Errorf("Expected Origin of %s to be %s. got %s", instance, meth, instance._Origin)
+	}
+	if len(instance._TypeArgs) != 1 || !types.Identical(instance._TypeArgs[0], intSliceTyp) {
+		t.Errorf("Expected TypeArgs of %s to be %v. got %v", instance, []types.Type{intSliceTyp}, instance._TypeArgs)
+	}
+	instances := prog._Instances(meth)
+	if want := []*Function{instance}; !reflect.DeepEqual(instances, want) {
+		t.Errorf("Expected instances of %s to be %v. got %v", meth, want, instances)
+	}
+
+	// A second request with an identical type returns the same Function.
+	second := prog.needsInstance(meth, []types.Type{types.NewSlice(types.Typ[types.Int])}, &cr)
+	if second != instance || len(cr) != 1 {
+		t.Error("Expected second identical instantiation to not create a function")
+	}
+
+	// Add a second instance.
+	inst2 := prog.needsInstance(meth, []types.Type{types.NewSlice(types.Typ[types.Uint])}, &cr)
+	instances = prog._Instances(meth)
+
+	// Note: instance.Name() < inst2.Name()
+	sort.Slice(instances, func(i, j int) bool {
+		return instances[i].Name() < instances[j].Name()
+	})
+	if want := []*Function{instance, inst2}; !reflect.DeepEqual(instances, want) {
+		t.Errorf("Expected instances of %s to be %v. got %v", meth, want, instances)
+	}
+
+	// build and sanity check manually created instance.
+	var b builder
+	b.buildFunction(instance)
+	var buf bytes.Buffer
+	if !sanityCheck(instance, &buf) {
+		t.Errorf("sanityCheck of %s failed with: %s", instance, buf.String())
+	}
+}
diff --git a/go/ssa/methods.go b/go/ssa/methods.go
index 64453d502..8250bc0c9 100644
--- a/go/ssa/methods.go
+++ b/go/ssa/methods.go
@@ -57,13 +57,13 @@ func (prog *Program) LookupMethod(T types.Type, pkg *types.Package, name string)
 	return prog.MethodValue(sel)
 }
 
-// methodSet contains the (concrete) methods of a non-interface type.
+// methodSet contains the (concrete) methods of a concrete type (non-interface, non-parameterized).
 type methodSet struct {
 	mapping  map[string]*Function // populated lazily
 	complete bool                 // mapping contains all methods
 }
 
-// Precondition: !isInterface(T).
+// Precondition: T is a concrete type, e.g. !isInterface(T) and not parameterized.
 // EXCLUSIVE_LOCKS_REQUIRED(prog.methodsMu)
 func (prog *Program) createMethodSet(T types.Type) *methodSet {
 	mset, ok := prog.methodSets.At(T).(*methodSet)
@@ -126,7 +126,10 @@ func (prog *Program) RuntimeTypes() []types.Type {
 //
 func (prog *Program) declaredFunc(obj *types.Func) *Function {
 	if v := prog.packageLevelMember(obj); v != nil {
-		return v.(*Function)
+		fn := v.(*Function)
+		// TODO(taking): Removed restriction once generics are supported.
+		assert(len(fn._TypeParams) == len(fn._TypeArgs), "ssa does not yet support calling generic functions. See https://github.com/golang/go/issues/48525")
+		return fn
 	}
 	panic("no concrete method: " + obj.String())
 }
@@ -142,6 +145,7 @@ func (prog *Program) declaredFunc(obj *types.Func) *Function {
 // Adds any created functions to cr.
 //
 // Precondition: T is not a method signature (*Signature with Recv()!=nil).
+// Precondition: T is not parameterized.
 //
 // Thread-safe.  (Called via emitConv from multiple builder goroutines.)
 //
diff --git a/go/ssa/sanity.go b/go/ssa/sanity.go
index 6e65d760d..0cda70427 100644
--- a/go/ssa/sanity.go
+++ b/go/ssa/sanity.go
@@ -419,7 +419,8 @@ func (s *sanity) checkFunction(fn *Function) bool {
 		if strings.HasPrefix(fn.Synthetic, "wrapper ") ||
 			strings.HasPrefix(fn.Synthetic, "bound ") ||
 			strings.HasPrefix(fn.Synthetic, "thunk ") ||
-			strings.HasSuffix(fn.name, "Error") {
+			strings.HasSuffix(fn.name, "Error") ||
+			strings.HasPrefix(fn.Synthetic, "instantiation") {
 			// ok
 		} else {
 			s.errorf("nil Pkg")
diff --git a/go/ssa/ssa.go b/go/ssa/ssa.go
index ae8537a38..79da139ae 100644
--- a/go/ssa/ssa.go
+++ b/go/ssa/ssa.go
@@ -16,6 +16,7 @@ import (
 	"sync"
 
 	"golang.org/x/tools/go/types/typeutil"
+	"golang.org/x/tools/internal/typeparams"
 )
 
 // A Program is a partial or complete Go program converted to SSA form.
@@ -26,13 +27,15 @@ type Program struct {
 	mode       BuilderMode                 // set of mode bits for SSA construction
 	MethodSets typeutil.MethodSetCache     // cache of type-checker's method-sets
 
-	canon canonizer // type canonicalization map
+	canon *canonizer          // type canonicalization map
+	ctxt  *typeparams.Context // cache for type checking instantiations
 
 	methodsMu    sync.Mutex                 // guards the following maps:
 	methodSets   typeutil.Map               // maps type to its concrete methodSet
 	runtimeTypes typeutil.Map               // types for which rtypes are needed
 	bounds       map[*types.Func]*Function  // bounds for curried x.Method closures
 	thunks       map[selectionKey]*Function // thunks for T.Method expressions
+	instances    map[*Function]*instanceSet // instances of generic functions
 }
 
 // A Package is a single analyzed Go package containing Members for
@@ -316,6 +319,10 @@ type Function struct {
 	referrers []Instruction // referring instructions (iff Parent() != nil)
 	built     bool          // function has completed both CREATE and BUILD phase.
 
+	_Origin     *Function               // the origin function if this the instantiation of a generic function. nil if Parent() != nil.
+	_TypeParams []*typeparams.TypeParam // the type paramaters of this function. len(TypeParams) == len(_TypeArgs) => runtime function
+	_TypeArgs   []types.Type            // type arguments for for an instantiation. len(_TypeArgs) != 0 => instantiation
+
 	// The following fields are set transiently during building,
 	// then cleared.
 	currentBlock *BasicBlock             // where to emit code
@@ -324,6 +331,7 @@ type Function struct {
 	targets      *targets                // linked stack of branch targets
 	lblocks      map[*ast.Object]*lblock // labelled blocks
 	info         *types.Info             // *types.Info to build from. nil for wrappers.
+	subst        *subster                // type substitution cache
 }
 
 // BasicBlock represents an SSA basic block.
diff --git a/go/ssa/util.go b/go/ssa/util.go
index ef53e9f2c..ce1c3e9b6 100644
--- a/go/ssa/util.go
+++ b/go/ssa/util.go
@@ -17,6 +17,7 @@ import (
 
 	"golang.org/x/tools/go/ast/astutil"
 	"golang.org/x/tools/go/types/typeutil"
+	"golang.org/x/tools/internal/typeparams"
 )
 
 //// Sanity checking utilities
@@ -124,25 +125,48 @@ func nonbasicTypes(ts []types.Type) []types.Type {
 	return filtered
 }
 
+// isGeneric returns true if a package-level member is generic.
+func isGeneric(m Member) bool {
+	switch m := m.(type) {
+	case *NamedConst, *Global:
+		return false
+	case *Type:
+		// lifted from types.isGeneric.
+		named, _ := m.Type().(*types.Named)
+		return named != nil && named.Obj() != nil && typeparams.NamedTypeArgs(named) == nil && typeparams.ForNamed(named) != nil
+	case *Function:
+		return len(m._TypeParams) != len(m._TypeArgs)
+	default:
+		panic("unreachable")
+	}
+}
+
 // Mapping of a type T to a canonical instance C s.t. types.Indentical(T, C).
 // Thread-safe.
 type canonizer struct {
 	mu    sync.Mutex
-	canon typeutil.Map // map from type to a canonical instance
+	types typeutil.Map // map from type to a canonical instance
+	lists typeListMap  // map from a list of types to a canonical instance
+}
+
+func newCanonizer() *canonizer {
+	c := &canonizer{}
+	h := typeutil.MakeHasher()
+	c.types.SetHasher(h)
+	c.lists.hasher = h
+	return c
 }
 
-// Tuple returns a canonical representative of a Tuple of types.
-// Representative of the empty Tuple is nil.
-func (c *canonizer) Tuple(ts []types.Type) *types.Tuple {
+// List returns a canonical representative of a list of types.
+// Representative of the empty list is nil.
+func (c *canonizer) List(ts []types.Type) *typeList {
 	if len(ts) == 0 {
 		return nil
 	}
-	vars := make([]*types.Var, len(ts))
-	for i, t := range ts {
-		vars[i] = anonVar(t)
-	}
-	tuple := types.NewTuple(vars...)
-	return c.Type(tuple).(*types.Tuple)
+
+	c.mu.Lock()
+	defer c.mu.Unlock()
+	return c.lists.rep(ts)
 }
 
 // Type returns a canonical representative of type T.
@@ -150,9 +174,74 @@ func (c *canonizer) Type(T types.Type) types.Type {
 	c.mu.Lock()
 	defer c.mu.Unlock()
 
-	if r := c.canon.At(T); r != nil {
+	if r := c.types.At(T); r != nil {
 		return r.(types.Type)
 	}
-	c.canon.Set(T, T)
+	c.types.Set(T, T)
 	return T
 }
+
+// A type for representating an canonized list of types.
+type typeList []types.Type
+
+func (l *typeList) identical(ts []types.Type) bool {
+	if l == nil {
+		return len(ts) == 0
+	}
+	n := len(*l)
+	if len(ts) != n {
+		return false
+	}
+	for i, left := range *l {
+		right := ts[i]
+		if !types.Identical(left, right) {
+			return false
+		}
+	}
+	return true
+}
+
+type typeListMap struct {
+	hasher  typeutil.Hasher
+	buckets map[uint32][]*typeList
+}
+
+// rep returns a canonical representative of a slice of types.
+func (m *typeListMap) rep(ts []types.Type) *typeList {
+	if m == nil || len(ts) == 0 {
+		return nil
+	}
+
+	if m.buckets == nil {
+		m.buckets = make(map[uint32][]*typeList)
+	}
+
+	h := m.hash(ts)
+	bucket := m.buckets[h]
+	for _, l := range bucket {
+		if l.identical(ts) {
+			return l
+		}
+	}
+
+	// not present. create a representative.
+	cp := make(typeList, len(ts))
+	copy(cp, ts)
+	rep := &cp
+
+	m.buckets[h] = append(bucket, rep)
+	return rep
+}
+
+func (m *typeListMap) hash(ts []types.Type) uint32 {
+	if m == nil {
+		return 0
+	}
+	// Some smallish prime far away from typeutil.Hash.
+	n := len(ts)
+	h := uint32(13619) + 2*uint32(n)
+	for i := 0; i < n; i++ {
+		h += 3 * m.hasher.Hash(ts[i])
+	}
+	return h
+}