typeparams: a new module with a transitional API for generics in tools
Add a new module for use by tool authors that need operate on generic
code, while still building at older Go versions.
This module API proxies the Go 1.18 API for type parameters, providing
stubs at earlier Go versions. It also contains some common helpers to
supplement the go/types API.
For golang/go#50447
Change-Id: I97feb834eb2da646620f8377904520b511871915
Reviewed-on: https://go-review.googlesource.com/c/exp/+/383375
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
Trust: Dominik Honnef <dominik@honnef.co>
Reviewed-by: Ian Cottrell <iancottrell@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/typeparams/common.go b/typeparams/common.go
new file mode 100644
index 0000000..e697083
--- /dev/null
+++ b/typeparams/common.go
@@ -0,0 +1,186 @@
+// Copyright 2021 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 typeparams contains common utilities for writing tools that interact
+// with generic Go code, as introduced with Go 1.18.
+//
+// THIS PACKAGE IS CURRENTLY EXPERIMENTAL AND MAY CHANGE. While the API is
+// being tested, we may find the need for improvement. This caveat will be
+// removed shortly.
+//
+// Many of the types and functions in this package are proxies for the new APIs
+// introduced in the standard library with Go 1.18. For example, the
+// typeparams.Union type is an alias for go/types.Union, and the ForTypeSpec
+// function returns the value of the go/ast.TypeSpec.TypeParams field. At Go
+// versions older than 1.18 these helpers are implemented as stubs, allowing
+// users of this package to write code that handles generic constructs inline,
+// even if the Go version being used to compile does not support generics.
+//
+// Additionally, this package contains common utilities for working with the
+// new generic constructs, to supplement the standard library APIs. Notably,
+// the NormalTerms API computes a minimal representation of the structural
+// restrictions on a type parameter. In the future, these supplemental APIs may
+// be available in the standard library..
+package typeparams
+
+import (
+ "go/ast"
+ "go/token"
+ "go/types"
+)
+
+// Enabled reports whether type parameters are enabled in the current build
+// environment.
+func Enabled() bool {
+ return enabled
+}
+
+// UnpackIndexExpr extracts data from AST nodes that represent index
+// expressions.
+//
+// For an ast.IndexExpr, the resulting indices slice will contain exactly one
+// index expression. For an ast.IndexListExpr (go1.18+), it may have a variable
+// number of index expressions.
+//
+// For nodes that don't represent index expressions, the first return value of
+// UnpackIndexExpr will be nil.
+func UnpackIndexExpr(n ast.Node) (x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) {
+ switch e := n.(type) {
+ case *ast.IndexExpr:
+ return e.X, e.Lbrack, []ast.Expr{e.Index}, e.Rbrack
+ case *IndexListExpr:
+ return e.X, e.Lbrack, e.Indices, e.Rbrack
+ }
+ return nil, token.NoPos, nil, token.NoPos
+}
+
+// PackIndexExpr returns an *ast.IndexExpr or *ast.IndexListExpr, depending on
+// the cardinality of indices. Calling PackIndexExpr with len(indices) == 0
+// will panic.
+func PackIndexExpr(x ast.Expr, lbrack token.Pos, indices []ast.Expr, rbrack token.Pos) ast.Expr {
+ switch len(indices) {
+ case 0:
+ panic("empty indices")
+ case 1:
+ return &ast.IndexExpr{
+ X: x,
+ Lbrack: lbrack,
+ Index: indices[0],
+ Rbrack: rbrack,
+ }
+ default:
+ return &IndexListExpr{
+ X: x,
+ Lbrack: lbrack,
+ Indices: indices,
+ Rbrack: rbrack,
+ }
+ }
+}
+
+// IsTypeParam reports whether t is a type parameter.
+func IsTypeParam(t types.Type) bool {
+ _, ok := t.(*TypeParam)
+ return ok
+}
+
+// OriginMethod returns the origin method associated with the method fn. For
+// methods on a non-generic receiver base type, this is just fn. However, for
+// methods with a generic receiver, OriginMethod returns the corresponding
+// method in the method set of the origin type.
+//
+// As a special case, if fn is not a method (has no receiver), OriginMethod
+// returns fn.
+func OriginMethod(fn *types.Func) *types.Func {
+ recv := fn.Type().(*types.Signature).Recv()
+ if recv == nil {
+ return fn
+ }
+ base := recv.Type()
+ p, isPtr := base.(*types.Pointer)
+ if isPtr {
+ base = p.Elem()
+ }
+ named, isNamed := base.(*types.Named)
+ if !isNamed {
+ // Receiver is a *types.Interface.
+ return fn
+ }
+ if ForNamed(named).Len() == 0 {
+ // Receiver base has no type parameters, so we can avoid the lookup below.
+ return fn
+ }
+ orig := NamedTypeOrigin(named)
+ gfn, _, _ := types.LookupFieldOrMethod(orig, true, fn.Pkg(), fn.Name())
+ return gfn.(*types.Func)
+}
+
+// GenericAssignableTo is a generalization of types.AssignableTo that
+// implements the following rule for uninstantiated generic types:
+//
+// If V and T are generic named types, then V is considered assignable to T if,
+// for every possible instantation of V[A_1, ..., A_N], the instantiation
+// T[A_1, ..., A_N] is valid and V[A_1, ..., A_N] implements T[A_1, ..., A_N].
+//
+// If T has structural constraints, they must be satisfied by V.
+//
+// For example, consider the following type declarations:
+//
+// type Interface[T any] interface {
+// Accept(T)
+// }
+//
+// type Container[T any] struct {
+// Element T
+// }
+//
+// func (c Container[T]) Accept(t T) { c.Element = t }
+//
+// In this case, GenericAssignableTo reports that instantiations of Container
+// are assignable to the corresponding instantiation of Interface.
+func GenericAssignableTo(ctxt *Context, V, T types.Type) bool {
+ // If V and T are not both named, or do not have matching non-empty type
+ // parameter lists, fall back on types.AssignableTo.
+
+ VN, Vnamed := V.(*types.Named)
+ TN, Tnamed := T.(*types.Named)
+ if !Vnamed || !Tnamed {
+ return types.AssignableTo(V, T)
+ }
+
+ vtparams := ForNamed(VN)
+ ttparams := ForNamed(TN)
+ if vtparams.Len() == 0 || vtparams.Len() != ttparams.Len() || NamedTypeArgs(VN).Len() != 0 || NamedTypeArgs(TN).Len() != 0 {
+ return types.AssignableTo(V, T)
+ }
+
+ // V and T have the same (non-zero) number of type params. Instantiate both
+ // with the type parameters of V. This must always succeed for V, and will
+ // succeed for T if and only if the type set of each type parameter of V is a
+ // subset of the type set of the corresponding type parameter of T, meaning
+ // that every instantiation of V corresponds to a valid instantiation of T.
+
+ // Minor optimization: ensure we share a context across the two
+ // instantiations below.
+ if ctxt == nil {
+ ctxt = NewContext()
+ }
+
+ var targs []types.Type
+ for i := 0; i < vtparams.Len(); i++ {
+ targs = append(targs, vtparams.At(i))
+ }
+
+ vinst, err := Instantiate(ctxt, V, targs, true)
+ if err != nil {
+ panic("type parameters should satisfy their own constraints")
+ }
+
+ tinst, err := Instantiate(ctxt, T, targs, true)
+ if err != nil {
+ return false
+ }
+
+ return types.AssignableTo(vinst, tinst)
+}
diff --git a/typeparams/common_test.go b/typeparams/common_test.go
new file mode 100644
index 0000000..5dd5c3f
--- /dev/null
+++ b/typeparams/common_test.go
@@ -0,0 +1,238 @@
+// Copyright 2021 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 typeparams_test
+
+import (
+ "go/ast"
+ "go/parser"
+ "go/token"
+ "go/types"
+ "testing"
+
+ . "golang.org/x/exp/typeparams"
+)
+
+func TestGetIndexExprData(t *testing.T) {
+ x := &ast.Ident{}
+ i := &ast.Ident{}
+
+ want := &IndexListExpr{X: x, Lbrack: 1, Indices: []ast.Expr{i}, Rbrack: 2}
+ tests := map[ast.Node]bool{
+ &ast.IndexExpr{X: x, Lbrack: 1, Index: i, Rbrack: 2}: true,
+ want: true,
+ &ast.Ident{}: false,
+ }
+
+ for n, isIndexExpr := range tests {
+ X, lbrack, indices, rbrack := UnpackIndexExpr(n)
+ if got := X != nil; got != isIndexExpr {
+ t.Errorf("UnpackIndexExpr(%v) = %v, _, _, _; want nil: %t", n, x, !isIndexExpr)
+ }
+ if X == nil {
+ continue
+ }
+ if X != x || lbrack != 1 || indices[0] != i || rbrack != 2 {
+ t.Errorf("UnpackIndexExprData(%v) = %v, %v, %v, %v; want %+v", n, x, lbrack, indices, rbrack, want)
+ }
+ }
+}
+
+func SkipIfNotEnabled(t *testing.T) {
+ if !Enabled() {
+ t.Skip("type parameters are not enabled")
+ }
+}
+
+func TestOriginMethodRecursive(t *testing.T) {
+ SkipIfNotEnabled(t)
+
+ src := `package p
+
+type N[A any] int
+
+func (r N[B]) m() { r.m(); r.n() }
+
+func (r *N[C]) n() { }
+`
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "p.go", src, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+ info := types.Info{
+ Defs: make(map[*ast.Ident]types.Object),
+ Uses: make(map[*ast.Ident]types.Object),
+ }
+ var conf types.Config
+ if _, err := conf.Check("p", fset, []*ast.File{f}, &info); err != nil {
+ t.Fatal(err)
+ }
+
+ // Collect objects from types.Info.
+ var m, n *types.Func // the 'origin' methods in Info.Defs
+ var mm, mn *types.Func // the methods used in the body of m
+
+ for _, decl := range f.Decls {
+ fdecl, ok := decl.(*ast.FuncDecl)
+ if !ok {
+ continue
+ }
+ def := info.Defs[fdecl.Name].(*types.Func)
+ switch fdecl.Name.Name {
+ case "m":
+ m = def
+ ast.Inspect(fdecl.Body, func(n ast.Node) bool {
+ if call, ok := n.(*ast.CallExpr); ok {
+ sel := call.Fun.(*ast.SelectorExpr)
+ use := info.Uses[sel.Sel].(*types.Func)
+ switch sel.Sel.Name {
+ case "m":
+ mm = use
+ case "n":
+ mn = use
+ }
+ }
+ return true
+ })
+ case "n":
+ n = def
+ }
+ }
+
+ tests := []struct {
+ name string
+ input, want *types.Func
+ }{
+ {"declared m", m, m},
+ {"declared n", n, n},
+ {"used m", mm, m},
+ {"used n", mn, n},
+ }
+
+ for _, test := range tests {
+ if got := OriginMethod(test.input); got != test.want {
+ t.Errorf("OriginMethod(%q) = %v, want %v", test.name, test.input, test.want)
+ }
+ }
+}
+
+func TestOriginMethodUses(t *testing.T) {
+ SkipIfNotEnabled(t)
+
+ tests := []string{
+ `type T interface { m() }; func _(t T) { t.m() }`,
+ `type T[P any] interface { m() P }; func _[A any](t T[A]) { t.m() }`,
+ `type T[P any] interface { m() P }; func _(t T[int]) { t.m() }`,
+ `type T[P any] int; func (r T[A]) m() { r.m() }`,
+ `type T[P any] int; func (r *T[A]) m() { r.m() }`,
+ `type T[P any] int; func (r *T[A]) m() {}; func _(t T[int]) { t.m() }`,
+ `type T[P any] int; func (r *T[A]) m() {}; func _[A any](t T[A]) { t.m() }`,
+ }
+
+ for _, src := range tests {
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "p.go", "package p; "+src, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+ info := types.Info{
+ Uses: make(map[*ast.Ident]types.Object),
+ }
+ var conf types.Config
+ pkg, err := conf.Check("p", fset, []*ast.File{f}, &info)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ T := pkg.Scope().Lookup("T").Type()
+ obj, _, _ := types.LookupFieldOrMethod(T, true, pkg, "m")
+ m := obj.(*types.Func)
+
+ ast.Inspect(f, func(n ast.Node) bool {
+ if call, ok := n.(*ast.CallExpr); ok {
+ sel := call.Fun.(*ast.SelectorExpr)
+ use := info.Uses[sel.Sel].(*types.Func)
+ orig := OriginMethod(use)
+ if orig != m {
+ t.Errorf("%s:\nUses[%v] = %v, want %v", src, types.ExprString(sel), use, m)
+ }
+ }
+ return true
+ })
+ }
+}
+
+func TestGenericAssignableTo(t *testing.T) {
+ SkipIfNotEnabled(t)
+
+ tests := []struct {
+ src string
+ want bool
+ }{
+ // The inciting issue: golang/go#50887.
+ {`
+ type T[P any] interface {
+ Accept(P)
+ }
+
+ type V[Q any] struct {
+ Element Q
+ }
+
+ func (c V[Q]) Accept(q Q) { c.Element = q }
+ `, true},
+
+ // Various permutations on constraints and signatures.
+ {`type T[P ~int] interface{ A(P) }; type V[Q int] int; func (V[Q]) A(Q) {}`, true},
+ {`type T[P int] interface{ A(P) }; type V[Q ~int] int; func (V[Q]) A(Q) {}`, false},
+ {`type T[P int|string] interface{ A(P) }; type V[Q int] int; func (V[Q]) A(Q) {}`, true},
+ {`type T[P any] interface{ A(P) }; type V[Q any] int; func (V[Q]) A(Q, Q) {}`, false},
+ {`type T[P any] interface{ int; A(P) }; type V[Q any] int; func (V[Q]) A(Q) {}`, false},
+
+ // Various structural restrictions on T.
+ {`type T[P any] interface{ ~int; A(P) }; type V[Q any] int; func (V[Q]) A(Q) {}`, true},
+ {`type T[P any] interface{ ~int|string; A(P) }; type V[Q any] int; func (V[Q]) A(Q) {}`, true},
+ {`type T[P any] interface{ int; A(P) }; type V[Q int] int; func (V[Q]) A(Q) {}`, false},
+
+ // Various recursive constraints.
+ {`type T[P ~struct{ f *P }] interface{ A(P) }; type V[Q ~struct{ f *Q }] int; func (V[Q]) A(Q) {}`, true},
+ {`type T[P ~struct{ f *P }] interface{ A(P) }; type V[Q ~struct{ g *Q }] int; func (V[Q]) A(Q) {}`, false},
+ {`type T[P ~*X, X any] interface{ A(P) X }; type V[Q ~*Y, Y any] int; func (V[Q, Y]) A(Q) (y Y) { return }`, true},
+ {`type T[P ~*X, X any] interface{ A(P) X }; type V[Q ~**Y, Y any] int; func (V[Q, Y]) A(Q) (y Y) { return }`, false},
+ {`type T[P, X any] interface{ A(P) X }; type V[Q ~*Y, Y any] int; func (V[Q, Y]) A(Q) (y Y) { return }`, true},
+ {`type T[P ~*X, X any] interface{ A(P) X }; type V[Q, Y any] int; func (V[Q, Y]) A(Q) (y Y) { return }`, false},
+ {`type T[P, X any] interface{ A(P) X }; type V[Q, Y any] int; func (V[Q, Y]) A(Q) (y Y) { return }`, true},
+
+ // In this test case, we reverse the type parameters in the signature of V.A
+ {`type T[P, X any] interface{ A(P) X }; type V[Q, Y any] int; func (V[Q, Y]) A(Y) (y Q) { return }`, false},
+ // It would be nice to return true here: V can only be instantiated with
+ // [int, int], so the identity of the type parameters should not matter.
+ {`type T[P, X any] interface{ A(P) X }; type V[Q, Y int] int; func (V[Q, Y]) A(Y) (y Q) { return }`, false},
+ }
+
+ for _, test := range tests {
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "p.go", "package p; "+test.src, 0)
+ if err != nil {
+ t.Fatalf("%s:\n%v", test.src, err)
+ }
+ var conf types.Config
+ pkg, err := conf.Check("p", fset, []*ast.File{f}, nil)
+ if err != nil {
+ t.Fatalf("%s:\n%v", test.src, err)
+ }
+
+ V := pkg.Scope().Lookup("V").Type()
+ T := pkg.Scope().Lookup("T").Type()
+
+ if types.AssignableTo(V, T) {
+ t.Fatal("AssignableTo")
+ }
+
+ if got := GenericAssignableTo(nil, V, T); got != test.want {
+ t.Fatalf("%s:\nGenericAssignableTo(%v, %v) = %v, want %v", test.src, V, T, got, test.want)
+ }
+ }
+}
diff --git a/typeparams/copytermlist.go b/typeparams/copytermlist.go
new file mode 100644
index 0000000..ffe997a
--- /dev/null
+++ b/typeparams/copytermlist.go
@@ -0,0 +1,100 @@
+// Copyright 2021 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.
+
+//go:build ignore
+// +build ignore
+
+// copytermlist.go copies the term list algorithm from GOROOT/src/go/types.
+// Run it with:
+// GO111MODULE=off go run copytermlist.go
+
+package main
+
+import (
+ "bytes"
+ "fmt"
+ "go/ast"
+ "go/format"
+ "go/parser"
+ "go/token"
+ "os"
+ "path/filepath"
+ "reflect"
+ "runtime"
+ "strings"
+
+ "golang.org/x/tools/go/ast/astutil"
+)
+
+func main() {
+ if err := doCopy(); err != nil {
+ fmt.Fprintf(os.Stderr, "error copying from go/types: %v", err)
+ os.Exit(1)
+ }
+}
+
+func doCopy() error {
+ dir := filepath.Join(runtime.GOROOT(), "src", "go", "types")
+ for _, name := range []string{"typeterm.go", "termlist.go"} {
+ path := filepath.Join(dir, name)
+ fset := token.NewFileSet()
+ file, err := parser.ParseFile(fset, path, nil, parser.ParseComments)
+ if err != nil {
+ return err
+ }
+ file.Name.Name = "typeparams"
+ file.Doc = &ast.CommentGroup{List: []*ast.Comment{&ast.Comment{Text: "DO NOT MODIFY"}}}
+ var needImport bool
+ selectorType := reflect.TypeOf((*ast.SelectorExpr)(nil))
+ astutil.Apply(file, func(c *astutil.Cursor) bool {
+ if id, _ := c.Node().(*ast.Ident); id != nil {
+ // Check if this ident should be qualified with types. For simplicity,
+ // assume the copied files do not themselves contain any exported
+ // symbols.
+
+ // As a simple heuristic, just verify that the ident may be replaced by
+ // a selector.
+ if !token.IsExported(id.Name) {
+ return false
+ }
+ v := reflect.TypeOf(c.Parent()).Elem() // ast nodes are all pointers
+ field, ok := v.FieldByName(c.Name())
+ if !ok {
+ panic("missing field")
+ }
+ t := field.Type
+ if c.Index() > 0 { // => t is a slice
+ t = t.Elem()
+ }
+ if !selectorType.AssignableTo(t) {
+ return false
+ }
+ needImport = true
+ c.Replace(&ast.SelectorExpr{
+ X: ast.NewIdent("types"),
+ Sel: ast.NewIdent(id.Name),
+ })
+ }
+ return true
+ }, nil)
+ if needImport {
+ astutil.AddImport(fset, file, "go/types")
+ }
+
+ var b bytes.Buffer
+ if err := format.Node(&b, fset, file); err != nil {
+ return err
+ }
+
+ // Hack in the 'generated' byline.
+ content := b.String()
+ header := "// Code generated by copytermlist.go DO NOT EDIT.\n\npackage typeparams"
+ content = strings.Replace(content, "package typeparams", header, 1)
+
+ if err := os.WriteFile(name, []byte(content), 0644); err != nil {
+ return err
+ }
+ }
+ return nil
+}
diff --git a/typeparams/go.mod b/typeparams/go.mod
new file mode 100644
index 0000000..b1224b1
--- /dev/null
+++ b/typeparams/go.mod
@@ -0,0 +1,3 @@
+module golang.org/x/exp/typeparams
+
+go 1.18
diff --git a/typeparams/normalize.go b/typeparams/normalize.go
new file mode 100644
index 0000000..55c788a
--- /dev/null
+++ b/typeparams/normalize.go
@@ -0,0 +1,200 @@
+// Copyright 2021 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 typeparams
+
+import (
+ "errors"
+ "fmt"
+ "go/types"
+ "os"
+ "strings"
+)
+
+const debug = false
+
+// ErrEmptyTypeSet is returned if a type set computation results in a type set
+// with no types.
+var ErrEmptyTypeSet = errors.New("empty type set")
+
+// NormalTerms returns a slice of terms representing the normalized structural
+// type restrictions of a type, if any.
+//
+// For all types other than *types.TypeParam, *types.Interface, and
+// *types.Union, this is just a single term with Tilde() == false and
+// Type() == typ. For *types.TypeParam, *types.Interface, and *types.Union, see
+// below.
+//
+// Structural type restrictions of a type parameter are created via
+// non-interface types embedded in its constraint interface (directly, or via a
+// chain of interface embeddings). For example, in the declaration type
+// T[P interface{~int; m()}] int the structural restriction of the type
+// parameter P is ~int.
+//
+// With interface embedding and unions, the specification of structural type
+// restrictions may be arbitrarily complex. For example, consider the
+// following:
+//
+// type A interface{ ~string|~[]byte }
+//
+// type B interface{ int|string }
+//
+// type C interface { ~string|~int }
+//
+// type T[P interface{ A|B; C }] int
+//
+// In this example, the structural type restriction of P is ~string|int: A|B
+// expands to ~string|~[]byte|int|string, which reduces to ~string|~[]byte|int,
+// which when intersected with C (~string|~int) yields ~string|int.
+//
+// NormalTerms computes these expansions and reductions, producing a
+// "normalized" form of the embeddings. A structural restriction is normalized
+// if it is a single union containing no interface terms, and is minimal in the
+// sense that removing any term changes the set of types satisfying the
+// constraint. It is left as a proof for the reader that, modulo sorting, there
+// is exactly one such normalized form.
+//
+// Because the minimal representation always takes this form, NormalTerms
+// returns a slice of tilde terms corresponding to the terms of the union in
+// the normalized structural restriction. An error is returned if the type is
+// invalid, exceeds complexity bounds, or has an empty type set. In the latter
+// case, NormalTerms returns ErrEmptyTypeSet.
+//
+// NormalTerms makes no guarantees about the order of terms, except that it
+// is deterministic.
+func NormalTerms(typ types.Type) ([]*Term, error) {
+ if tparam, ok := typ.(*TypeParam); ok {
+ constraint := tparam.Constraint()
+ if constraint == nil {
+ return nil, fmt.Errorf("%s has nil constraint", tparam)
+ }
+ iface, _ := constraint.Underlying().(*types.Interface)
+ if iface == nil {
+ return nil, fmt.Errorf("constraint is %T, not *types.Interface", constraint.Underlying())
+ }
+ typ = iface
+ }
+ tset, err := computeTermSetInternal(typ, make(map[types.Type]*termSet), 0)
+ if err != nil {
+ return nil, err
+ }
+ if tset.terms.isEmpty() {
+ return nil, ErrEmptyTypeSet
+ }
+ if tset.terms.isAll() {
+ return nil, nil
+ }
+ var terms []*Term
+ for _, term := range tset.terms {
+ terms = append(terms, NewTerm(term.tilde, term.typ))
+ }
+ return terms, nil
+}
+
+// A termSet holds the normalized set of terms for a given type.
+//
+// The name termSet is intentionally distinct from 'type set': a type set is
+// all types that implement a type (and includes method restrictions), whereas
+// a term set just represents the structural restrictions on a type.
+type termSet struct {
+ complete bool
+ terms termlist
+}
+
+func indentf(depth int, format string, args ...interface{}) {
+ fmt.Fprintf(os.Stderr, strings.Repeat(".", depth)+format+"\n", args...)
+}
+
+func computeTermSetInternal(t types.Type, seen map[types.Type]*termSet, depth int) (res *termSet, err error) {
+ if t == nil {
+ panic("nil type")
+ }
+
+ if debug {
+ indentf(depth, "%s", t.String())
+ defer func() {
+ if err != nil {
+ indentf(depth, "=> %s", err)
+ } else {
+ indentf(depth, "=> %s", res.terms.String())
+ }
+ }()
+ }
+
+ const maxTermCount = 100
+ if tset, ok := seen[t]; ok {
+ if !tset.complete {
+ return nil, fmt.Errorf("cycle detected in the declaration of %s", t)
+ }
+ return tset, nil
+ }
+
+ // Mark the current type as seen to avoid infinite recursion.
+ tset := new(termSet)
+ defer func() {
+ tset.complete = true
+ }()
+ seen[t] = tset
+
+ switch u := t.Underlying().(type) {
+ case *types.Interface:
+ // The term set of an interface is the intersection of the term sets of its
+ // embedded types.
+ tset.terms = allTermlist
+ for i := 0; i < u.NumEmbeddeds(); i++ {
+ embedded := u.EmbeddedType(i)
+ if _, ok := embedded.Underlying().(*TypeParam); ok {
+ return nil, fmt.Errorf("invalid embedded type %T", embedded)
+ }
+ tset2, err := computeTermSetInternal(embedded, seen, depth+1)
+ if err != nil {
+ return nil, err
+ }
+ tset.terms = tset.terms.intersect(tset2.terms)
+ }
+ case *Union:
+ // The term set of a union is the union of term sets of its terms.
+ tset.terms = nil
+ for i := 0; i < u.Len(); i++ {
+ t := u.Term(i)
+ var terms termlist
+ switch t.Type().Underlying().(type) {
+ case *types.Interface:
+ tset2, err := computeTermSetInternal(t.Type(), seen, depth+1)
+ if err != nil {
+ return nil, err
+ }
+ terms = tset2.terms
+ case *TypeParam, *Union:
+ // A stand-alone type parameter or union is not permitted as union
+ // term.
+ return nil, fmt.Errorf("invalid union term %T", t)
+ default:
+ if t.Type() == types.Typ[types.Invalid] {
+ continue
+ }
+ terms = termlist{{t.Tilde(), t.Type()}}
+ }
+ tset.terms = tset.terms.union(terms)
+ if len(tset.terms) > maxTermCount {
+ return nil, fmt.Errorf("exceeded max term count %d", maxTermCount)
+ }
+ }
+ case *TypeParam:
+ panic("unreachable")
+ default:
+ // For all other types, the term set is just a single non-tilde term
+ // holding the type itself.
+ if u != types.Typ[types.Invalid] {
+ tset.terms = termlist{{false, t}}
+ }
+ }
+ return tset, nil
+}
+
+// under is a facade for the go/types internal function of the same name. It is
+// used by typeterm.go.
+func under(t types.Type) types.Type {
+ return t.Underlying()
+}
diff --git a/typeparams/normalize_test.go b/typeparams/normalize_test.go
new file mode 100644
index 0000000..dd47b57
--- /dev/null
+++ b/typeparams/normalize_test.go
@@ -0,0 +1,102 @@
+// Copyright 2021 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 typeparams_test
+
+import (
+ "go/ast"
+ "go/parser"
+ "go/token"
+ "go/types"
+ "strings"
+ "testing"
+
+ . "golang.org/x/exp/typeparams"
+)
+
+func TestNormalTerms(t *testing.T) {
+ if !Enabled() {
+ t.Skip("typeparams are not enabled")
+ }
+
+ // In the following tests, src must define a type T with (at least) one type
+ // parameter. We will compute the normal terms of the first type parameter.
+ tests := []struct {
+ src string
+ want string
+ wantError string
+ }{
+ {"package emptyinterface0; type T[P interface{}] int", "all", ""},
+ {"package emptyinterface1; type T[P interface{ int | interface{} }] int", "all", ""},
+ {"package singleton; type T[P interface{ int }] int", "int", ""},
+ {"package under; type T[P interface{~int}] int", "~int", ""},
+ {"package superset; type T[P interface{ ~int | int }] int", "~int", ""},
+ {"package overlap; type T[P interface{ ~int; int }] int", "int", ""},
+ {"package emptyintersection; type T[P interface{ ~int; string }] int", "", "empty type set"},
+
+ {"package embedded0; type T[P interface{ I }] int; type I interface { int }", "int", ""},
+ {"package embedded1; type T[P interface{ I | string }] int; type I interface{ int | ~string }", "int|~string", ""},
+ {"package embedded2; type T[P interface{ I; string }] int; type I interface{ int | ~string }", "string", ""},
+
+ {"package named; type T[P C] int; type C interface{ ~int|int }", "~int", ""},
+ {`// package example is taken from the docstring for StructuralTerms
+package example
+
+type A interface{ ~string|~[]byte }
+
+type B interface{ int|string }
+
+type C interface { ~string|~int }
+
+type T[P interface{ A|B; C }] int
+`, "~string|int", ""},
+ }
+
+ for _, test := range tests {
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "p.go", test.src, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+ t.Run(f.Name.Name, func(t *testing.T) {
+ conf := types.Config{
+ Error: func(error) {}, // keep going on errors
+ }
+ pkg, err := conf.Check("", fset, []*ast.File{f}, nil)
+ if err != nil {
+ t.Logf("types.Config.Check: %v", err)
+ // keep going on type checker errors: we want to assert on behavior of
+ // invalid code as well.
+ }
+ obj := pkg.Scope().Lookup("T")
+ if obj == nil {
+ t.Fatal("type T not found")
+ }
+ T := ForNamed(obj.Type().(*types.Named)).At(0)
+ terms, err := NormalTerms(T)
+ if test.wantError != "" {
+ if err == nil {
+ t.Fatalf("StructuralTerms(%s): nil error, want %q", T, test.wantError)
+ }
+ if !strings.Contains(err.Error(), test.wantError) {
+ t.Errorf("StructuralTerms(%s): err = %q, want %q", T, err, test.wantError)
+ }
+ return
+ }
+ if err != nil {
+ t.Fatal(err)
+ }
+ var got string
+ if len(terms) == 0 {
+ got = "all"
+ } else {
+ qf := types.RelativeTo(pkg)
+ got = types.TypeString(NewUnion(terms), qf)
+ }
+ if got != test.want {
+ t.Errorf("StructuralTerms(%s) = %q, want %q", T, got, test.want)
+ }
+ })
+ }
+}
diff --git a/typeparams/termlist.go b/typeparams/termlist.go
new file mode 100644
index 0000000..6f88bfa
--- /dev/null
+++ b/typeparams/termlist.go
@@ -0,0 +1,172 @@
+// Copyright 2021 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.
+
+// Code generated by copytermlist.go DO NOT EDIT.
+
+package typeparams
+
+import (
+ "bytes"
+ "go/types"
+)
+
+// A termlist represents the type set represented by the union
+// t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn.
+// A termlist is in normal form if all terms are disjoint.
+// termlist operations don't require the operands to be in
+// normal form.
+type termlist []*term
+
+// allTermlist represents the set of all types.
+// It is in normal form.
+var allTermlist = termlist{new(term)}
+
+// String prints the termlist exactly (without normalization).
+func (xl termlist) String() string {
+ if len(xl) == 0 {
+ return "∅"
+ }
+ var buf bytes.Buffer
+ for i, x := range xl {
+ if i > 0 {
+ buf.WriteString(" ∪ ")
+ }
+ buf.WriteString(x.String())
+ }
+ return buf.String()
+}
+
+// isEmpty reports whether the termlist xl represents the empty set of types.
+func (xl termlist) isEmpty() bool {
+ // If there's a non-nil term, the entire list is not empty.
+ // If the termlist is in normal form, this requires at most
+ // one iteration.
+ for _, x := range xl {
+ if x != nil {
+ return false
+ }
+ }
+ return true
+}
+
+// isAll reports whether the termlist xl represents the set of all types.
+func (xl termlist) isAll() bool {
+ // If there's a π€ term, the entire list is π€.
+ // If the termlist is in normal form, this requires at most
+ // one iteration.
+ for _, x := range xl {
+ if x != nil && x.typ == nil {
+ return true
+ }
+ }
+ return false
+}
+
+// norm returns the normal form of xl.
+func (xl termlist) norm() termlist {
+ // Quadratic algorithm, but good enough for now.
+ // TODO(gri) fix asymptotic performance
+ used := make([]bool, len(xl))
+ var rl termlist
+ for i, xi := range xl {
+ if xi == nil || used[i] {
+ continue
+ }
+ for j := i + 1; j < len(xl); j++ {
+ xj := xl[j]
+ if xj == nil || used[j] {
+ continue
+ }
+ if u1, u2 := xi.union(xj); u2 == nil {
+ // If we encounter a π€ term, the entire list is π€.
+ // Exit early.
+ // (Note that this is not just an optimization;
+ // if we continue, we may end up with a π€ term
+ // and other terms and the result would not be
+ // in normal form.)
+ if u1.typ == nil {
+ return allTermlist
+ }
+ xi = u1
+ used[j] = true // xj is now unioned into xi - ignore it in future iterations
+ }
+ }
+ rl = append(rl, xi)
+ }
+ return rl
+}
+
+// If the type set represented by xl is specified by a single (non-π€) term,
+// singleType returns that type. Otherwise it returns nil.
+func (xl termlist) singleType() types.Type {
+ if nl := xl.norm(); len(nl) == 1 {
+ return nl[0].typ // if nl.isAll() then typ is nil, which is ok
+ }
+ return nil
+}
+
+// union returns the union xl ∪ yl.
+func (xl termlist) union(yl termlist) termlist {
+ return append(xl, yl...).norm()
+}
+
+// intersect returns the intersection xl ∩ yl.
+func (xl termlist) intersect(yl termlist) termlist {
+ if xl.isEmpty() || yl.isEmpty() {
+ return nil
+ }
+
+ // Quadratic algorithm, but good enough for now.
+ // TODO(gri) fix asymptotic performance
+ var rl termlist
+ for _, x := range xl {
+ for _, y := range yl {
+ if r := x.intersect(y); r != nil {
+ rl = append(rl, r)
+ }
+ }
+ }
+ return rl.norm()
+}
+
+// equal reports whether xl and yl represent the same type set.
+func (xl termlist) equal(yl termlist) bool {
+ // TODO(gri) this should be more efficient
+ return xl.subsetOf(yl) && yl.subsetOf(xl)
+}
+
+// includes reports whether t ∈ xl.
+func (xl termlist) includes(t types.Type) bool {
+ for _, x := range xl {
+ if x.includes(t) {
+ return true
+ }
+ }
+ return false
+}
+
+// supersetOf reports whether y ⊆ xl.
+func (xl termlist) supersetOf(y *term) bool {
+ for _, x := range xl {
+ if y.subsetOf(x) {
+ return true
+ }
+ }
+ return false
+}
+
+// subsetOf reports whether xl ⊆ yl.
+func (xl termlist) subsetOf(yl termlist) bool {
+ if yl.isEmpty() {
+ return xl.isEmpty()
+ }
+
+ // each term x of xl must be a subset of yl
+ for _, x := range xl {
+ if !yl.supersetOf(x) {
+ return false // x is not a subset yl
+ }
+ }
+ return true
+}
diff --git a/typeparams/typeparams_go117.go b/typeparams/typeparams_go117.go
new file mode 100644
index 0000000..efc33f1
--- /dev/null
+++ b/typeparams/typeparams_go117.go
@@ -0,0 +1,202 @@
+// Copyright 2021 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.
+
+//go:build !go1.18
+// +build !go1.18
+
+package typeparams
+
+import (
+ "go/ast"
+ "go/token"
+ "go/types"
+)
+
+const enabled = false
+
+func unsupported() {
+ panic("type parameters are unsupported at this go version")
+}
+
+// IndexListExpr is a placeholder type, as type parameters are not supported at
+// this Go version. Its methods panic on use.
+type IndexListExpr struct {
+ ast.Expr
+ X ast.Expr // expression
+ Lbrack token.Pos // position of "["
+ Indices []ast.Expr // index expressions
+ Rbrack token.Pos // position of "]"
+}
+
+func (*IndexListExpr) Pos() token.Pos { unsupported(); return token.NoPos }
+func (*IndexListExpr) End() token.Pos { unsupported(); return token.NoPos }
+
+// ForTypeSpec returns an empty field list, as type parameters on not supported
+// at this Go version.
+func ForTypeSpec(*ast.TypeSpec) *ast.FieldList {
+ return nil
+}
+
+// ForFuncType returns an empty field list, as type parameters are not
+// supported at this Go version.
+func ForFuncType(*ast.FuncType) *ast.FieldList {
+ return nil
+}
+
+// TypeParam is a placeholder type, as type parameters are not supported at
+// this Go version. Its methods panic on use.
+type TypeParam struct{ types.Type }
+
+func (*TypeParam) String() string { unsupported(); return "" }
+func (*TypeParam) Underlying() types.Type { unsupported(); return nil }
+func (*TypeParam) Index() int { unsupported(); return 0 }
+func (*TypeParam) Constraint() types.Type { unsupported(); return nil }
+func (*TypeParam) SetConstraint(types.Type) { unsupported() }
+func (*TypeParam) Obj() *types.TypeName { unsupported(); return nil }
+
+// TypeParamList is a placeholder for an empty type parameter list.
+type TypeParamList struct{}
+
+func (*TypeParamList) Len() int { return 0 }
+func (*TypeParamList) At(int) *TypeParam { unsupported(); return nil }
+
+// TypeList is a placeholder for an empty type list.
+type TypeList struct{}
+
+func (*TypeList) Len() int { return 0 }
+func (*TypeList) At(int) types.Type { unsupported(); return nil }
+
+// NewTypeParam is unsupported at this Go version, and panics.
+func NewTypeParam(name *types.TypeName, constraint types.Type) *TypeParam {
+ unsupported()
+ return nil
+}
+
+// NewSignatureType calls types.NewSignature, panicking if recvTypeParams or
+// typeParams is non-empty.
+func NewSignatureType(recv *types.Var, recvTypeParams, typeParams []*TypeParam, params, results *types.Tuple, variadic bool) *types.Signature {
+ if len(recvTypeParams) != 0 || len(typeParams) != 0 {
+ unsupported()
+ }
+ return types.NewSignature(recv, params, results, variadic)
+}
+
+// ForSignature returns an empty slice.
+func ForSignature(*types.Signature) *TypeParamList {
+ return nil
+}
+
+// RecvTypeParams returns a nil slice.
+func RecvTypeParams(sig *types.Signature) *TypeParamList {
+ return nil
+}
+
+// IsComparable returns false, as no interfaces are type-restricted at this Go
+// version.
+func IsComparable(*types.Interface) bool {
+ return false
+}
+
+// IsMethodSet returns true, as no interfaces are type-restricted at this Go
+// version.
+func IsMethodSet(*types.Interface) bool {
+ return true
+}
+
+// IsImplicit returns false, as no interfaces are implicit at this Go version.
+func IsImplicit(*types.Interface) bool {
+ return false
+}
+
+// MarkImplicit does nothing, because this Go version does not have implicit
+// interfaces.
+func MarkImplicit(*types.Interface) {}
+
+// ForNamed returns an empty type parameter list, as type parameters are not
+// supported at this Go version.
+func ForNamed(*types.Named) *TypeParamList {
+ return nil
+}
+
+// SetForNamed panics if tparams is non-empty.
+func SetForNamed(_ *types.Named, tparams []*TypeParam) {
+ if len(tparams) > 0 {
+ unsupported()
+ }
+}
+
+// NamedTypeArgs returns nil.
+func NamedTypeArgs(*types.Named) *TypeList {
+ return nil
+}
+
+// NamedTypeOrigin is the identity method at this Go version.
+func NamedTypeOrigin(named *types.Named) types.Type {
+ return named
+}
+
+// Term holds information about a structural type restriction.
+type Term struct {
+ tilde bool
+ typ types.Type
+}
+
+func (m *Term) Tilde() bool { return m.tilde }
+func (m *Term) Type() types.Type { return m.typ }
+func (m *Term) String() string {
+ pre := ""
+ if m.tilde {
+ pre = "~"
+ }
+ return pre + m.typ.String()
+}
+
+// NewTerm creates a new placeholder term type.
+func NewTerm(tilde bool, typ types.Type) *Term {
+ return &Term{tilde, typ}
+}
+
+// Union is a placeholder type, as type parameters are not supported at this Go
+// version. Its methods panic on use.
+type Union struct{ types.Type }
+
+func (*Union) String() string { unsupported(); return "" }
+func (*Union) Underlying() types.Type { unsupported(); return nil }
+func (*Union) Len() int { return 0 }
+func (*Union) Term(i int) *Term { unsupported(); return nil }
+
+// NewUnion is unsupported at this Go version, and panics.
+func NewUnion(terms []*Term) *Union {
+ unsupported()
+ return nil
+}
+
+// InitInstances is a noop at this Go version.
+func InitInstances(*types.Info) {}
+
+// Instance is a placeholder type, as type parameters are not supported at this
+// Go version.
+type Instance struct {
+ TypeArgs *TypeList
+ Type types.Type
+}
+
+// GetInstances returns a nil map, as type parameters are not supported at this
+// Go version.
+func GetInstances(info *types.Info) map[*ast.Ident]Instance { return nil }
+
+// Context is a placeholder type, as type parameters are not supported at
+// this Go version.
+type Context struct{}
+
+// NewContext returns a placeholder Context instance.
+func NewContext() *Context {
+ return &Context{}
+}
+
+// Instantiate is unsupported on this Go version, and panics.
+func Instantiate(ctxt *Context, typ types.Type, targs []types.Type, validate bool) (types.Type, error) {
+ unsupported()
+ return nil, nil
+}
diff --git a/typeparams/typeparams_go118.go b/typeparams/typeparams_go118.go
new file mode 100644
index 0000000..1176104
--- /dev/null
+++ b/typeparams/typeparams_go118.go
@@ -0,0 +1,148 @@
+// Copyright 2021 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.
+
+//go:build go1.18
+// +build go1.18
+
+package typeparams
+
+import (
+ "go/ast"
+ "go/types"
+)
+
+const enabled = true
+
+// IndexListExpr is an alias for ast.IndexListExpr.
+type IndexListExpr = ast.IndexListExpr
+
+// ForTypeSpec returns n.TypeParams.
+func ForTypeSpec(n *ast.TypeSpec) *ast.FieldList {
+ if n == nil {
+ return nil
+ }
+ return n.TypeParams
+}
+
+// ForFuncType returns n.TypeParams.
+func ForFuncType(n *ast.FuncType) *ast.FieldList {
+ if n == nil {
+ return nil
+ }
+ return n.TypeParams
+}
+
+// TypeParam is an alias for types.TypeParam
+type TypeParam = types.TypeParam
+
+// TypeParamList is an alias for types.TypeParamList
+type TypeParamList = types.TypeParamList
+
+// TypeList is an alias for types.TypeList
+type TypeList = types.TypeList
+
+// NewTypeParam calls types.NewTypeParam.
+func NewTypeParam(name *types.TypeName, constraint types.Type) *TypeParam {
+ return types.NewTypeParam(name, constraint)
+}
+
+// NewSignatureType calls types.NewSignatureType.
+func NewSignatureType(recv *types.Var, recvTypeParams, typeParams []*TypeParam, params, results *types.Tuple, variadic bool) *types.Signature {
+ return types.NewSignatureType(recv, recvTypeParams, typeParams, params, results, variadic)
+}
+
+// ForSignature returns sig.TypeParams()
+func ForSignature(sig *types.Signature) *TypeParamList {
+ return sig.TypeParams()
+}
+
+// RecvTypeParams returns sig.RecvTypeParams().
+func RecvTypeParams(sig *types.Signature) *TypeParamList {
+ return sig.RecvTypeParams()
+}
+
+// IsComparable calls iface.IsComparable().
+func IsComparable(iface *types.Interface) bool {
+ return iface.IsComparable()
+}
+
+// IsMethodSet calls iface.IsMethodSet().
+func IsMethodSet(iface *types.Interface) bool {
+ return iface.IsMethodSet()
+}
+
+// IsImplicit calls iface.IsImplicit().
+func IsImplicit(iface *types.Interface) bool {
+ return iface.IsImplicit()
+}
+
+// MarkImplicit calls iface.MarkImplicit().
+func MarkImplicit(iface *types.Interface) {
+ iface.MarkImplicit()
+}
+
+// ForNamed extracts the (possibly empty) type parameter object list from
+// named.
+func ForNamed(named *types.Named) *TypeParamList {
+ return named.TypeParams()
+}
+
+// SetForNamed sets the type params tparams on n. Each tparam must be of
+// dynamic type *types.TypeParam.
+func SetForNamed(n *types.Named, tparams []*TypeParam) {
+ n.SetTypeParams(tparams)
+}
+
+// NamedTypeArgs returns named.TypeArgs().
+func NamedTypeArgs(named *types.Named) *TypeList {
+ return named.TypeArgs()
+}
+
+// NamedTypeOrigin returns named.Orig().
+func NamedTypeOrigin(named *types.Named) types.Type {
+ return named.Origin()
+}
+
+// Term is an alias for types.Term.
+type Term = types.Term
+
+// NewTerm calls types.NewTerm.
+func NewTerm(tilde bool, typ types.Type) *Term {
+ return types.NewTerm(tilde, typ)
+}
+
+// Union is an alias for types.Union
+type Union = types.Union
+
+// NewUnion calls types.NewUnion.
+func NewUnion(terms []*Term) *Union {
+ return types.NewUnion(terms)
+}
+
+// InitInstances initializes info to record information about type and function
+// instances.
+func InitInstances(info *types.Info) {
+ info.Instances = make(map[*ast.Ident]types.Instance)
+}
+
+// Instance is an alias for types.Instance.
+type Instance = types.Instance
+
+// GetInstances returns info.Instances.
+func GetInstances(info *types.Info) map[*ast.Ident]Instance {
+ return info.Instances
+}
+
+// Context is an alias for types.Context.
+type Context = types.Context
+
+// NewContext calls types.NewContext.
+func NewContext() *Context {
+ return types.NewContext()
+}
+
+// Instantiate calls types.Instantiate.
+func Instantiate(ctxt *Context, typ types.Type, targs []types.Type, validate bool) (types.Type, error) {
+ return types.Instantiate(ctxt, typ, targs, validate)
+}
diff --git a/typeparams/typeparams_test.go b/typeparams/typeparams_test.go
new file mode 100644
index 0000000..50d1e2e
--- /dev/null
+++ b/typeparams/typeparams_test.go
@@ -0,0 +1,138 @@
+// Copyright 2021 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.
+
+//go:build go1.18
+// +build go1.18
+
+package typeparams_test
+
+import (
+ "bytes"
+ "go/ast"
+ "go/build"
+ "go/importer"
+ "go/parser"
+ "go/token"
+ "go/types"
+ "testing"
+)
+
+// TestAPIConsistency verifies that exported APIs match at Go 1.17 and Go
+// 1.18+.
+//
+// It relies on the convention that the names of type aliases in the typeparams
+// package match the names of the types they are aliasing.
+//
+// This test could be made more precise.
+func TestAPIConsistency(t *testing.T) {
+ api118 := getAPI(buildPackage(t, true))
+ api117 := getAPI(buildPackage(t, false))
+
+ for name, api := range api117 {
+ if api != api118[name] {
+ t.Errorf("%q: got %s at 1.17, but %s at 1.18+", name, api, api118[name])
+ }
+ delete(api118, name)
+ }
+ for name, api := range api118 {
+ if api != api117[name] {
+ t.Errorf("%q: got %s at 1.18+, but %s at 1.17", name, api, api117[name])
+ }
+ }
+}
+
+func getAPI(pkg *types.Package) map[string]string {
+ api := make(map[string]string)
+ for _, name := range pkg.Scope().Names() {
+ if !token.IsExported(name) {
+ continue
+ }
+ api[name] = name
+ obj := pkg.Scope().Lookup(name)
+ if f, ok := obj.(*types.Func); ok {
+ api[name] = formatSignature(f.Type().(*types.Signature))
+ }
+ typ := pkg.Scope().Lookup(name).Type()
+ // Consider method sets of pointer and non-pointer receivers.
+ msets := map[string]*types.MethodSet{
+ name: types.NewMethodSet(typ),
+ "*" + name: types.NewMethodSet(types.NewPointer(typ)),
+ }
+ for name, mset := range msets {
+ for i := 0; i < mset.Len(); i++ {
+ f := mset.At(i).Obj().(*types.Func)
+ mname := f.Name()
+ if token.IsExported(mname) {
+ api[name+"."+mname] = formatSignature(f.Type().(*types.Signature))
+ }
+ }
+ }
+ }
+ return api
+}
+
+func formatSignature(sig *types.Signature) string {
+ var b bytes.Buffer
+ b.WriteString("func")
+ writeTuple(&b, sig.Params())
+ writeTuple(&b, sig.Results())
+ return b.String()
+}
+
+func writeTuple(buf *bytes.Buffer, t *types.Tuple) {
+ buf.WriteRune('(')
+
+ // The API at Go 1.18 uses aliases for types in go/types. These types are
+ // _actually_ in the go/types package, and therefore would be formatted as
+ // e.g. *types.TypeParam, which would not match *typeparams.TypeParam --
+ // go/types does not track aliases. As we use the same name for all aliases,
+ // we can make the formatted signatures match by dropping the package
+ // qualifier.
+ qf := func(*types.Package) string { return "" }
+
+ for i := 0; i < t.Len(); i++ {
+ if i > 0 {
+ buf.WriteString(", ")
+ }
+ buf.WriteString(types.TypeString(t.At(i).Type(), qf))
+ }
+ buf.WriteRune(')')
+}
+
+func buildPackage(t *testing.T, go118 bool) *types.Package {
+ ctxt := build.Default
+ if !go118 {
+ for i, tag := range ctxt.ReleaseTags {
+ if tag == "go1.18" {
+ ctxt.ReleaseTags = ctxt.ReleaseTags[:i]
+ break
+ }
+ }
+ }
+ bpkg, err := ctxt.ImportDir(".", 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+ return typeCheck(t, bpkg.GoFiles)
+}
+
+func typeCheck(t *testing.T, filenames []string) *types.Package {
+ fset := token.NewFileSet()
+ var files []*ast.File
+ for _, name := range filenames {
+ f, err := parser.ParseFile(fset, name, nil, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+ files = append(files, f)
+ }
+ conf := types.Config{
+ Importer: importer.Default(),
+ }
+ pkg, err := conf.Check("", fset, files, nil)
+ if err != nil {
+ t.Fatal(err)
+ }
+ return pkg
+}
diff --git a/typeparams/typeterm.go b/typeparams/typeterm.go
new file mode 100644
index 0000000..7ddee28
--- /dev/null
+++ b/typeparams/typeterm.go
@@ -0,0 +1,170 @@
+// Copyright 2021 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.
+
+// Code generated by copytermlist.go DO NOT EDIT.
+
+package typeparams
+
+import "go/types"
+
+// A term describes elementary type sets:
+//
+// ∅: (*term)(nil) == ∅ // set of no types (empty set)
+// π€: &term{} == π€ // set of all types (π€niverse)
+// T: &term{false, T} == {T} // set of type T
+// ~t: &term{true, t} == {t' | under(t') == t} // set of types with underlying type t
+//
+type term struct {
+ tilde bool // valid if typ != nil
+ typ types.Type
+}
+
+func (x *term) String() string {
+ switch {
+ case x == nil:
+ return "∅"
+ case x.typ == nil:
+ return "π€"
+ case x.tilde:
+ return "~" + x.typ.String()
+ default:
+ return x.typ.String()
+ }
+}
+
+// equal reports whether x and y represent the same type set.
+func (x *term) equal(y *term) bool {
+ // easy cases
+ switch {
+ case x == nil || y == nil:
+ return x == y
+ case x.typ == nil || y.typ == nil:
+ return x.typ == y.typ
+ }
+ // ∅ ⊂ x, y ⊂ π€
+
+ return x.tilde == y.tilde && types.Identical(x.typ, y.typ)
+}
+
+// union returns the union x ∪ y: zero, one, or two non-nil terms.
+func (x *term) union(y *term) (_, _ *term) {
+ // easy cases
+ switch {
+ case x == nil && y == nil:
+ return nil, nil // ∅ ∪ ∅ == ∅
+ case x == nil:
+ return y, nil // ∅ ∪ y == y
+ case y == nil:
+ return x, nil // x ∪ ∅ == x
+ case x.typ == nil:
+ return x, nil // π€ ∪ y == π€
+ case y.typ == nil:
+ return y, nil // x ∪ π€ == π€
+ }
+ // ∅ ⊂ x, y ⊂ π€
+
+ if x.disjoint(y) {
+ return x, y // x ∪ y == (x, y) if x ∩ y == ∅
+ }
+ // x.typ == y.typ
+
+ // ~t ∪ ~t == ~t
+ // ~t ∪ T == ~t
+ // T ∪ ~t == ~t
+ // T ∪ T == T
+ if x.tilde || !y.tilde {
+ return x, nil
+ }
+ return y, nil
+}
+
+// intersect returns the intersection x ∩ y.
+func (x *term) intersect(y *term) *term {
+ // easy cases
+ switch {
+ case x == nil || y == nil:
+ return nil // ∅ ∩ y == ∅ and ∩ ∅ == ∅
+ case x.typ == nil:
+ return y // π€ ∩ y == y
+ case y.typ == nil:
+ return x // x ∩ π€ == x
+ }
+ // ∅ ⊂ x, y ⊂ π€
+
+ if x.disjoint(y) {
+ return nil // x ∩ y == ∅ if x ∩ y == ∅
+ }
+ // x.typ == y.typ
+
+ // ~t ∩ ~t == ~t
+ // ~t ∩ T == T
+ // T ∩ ~t == T
+ // T ∩ T == T
+ if !x.tilde || y.tilde {
+ return x
+ }
+ return y
+}
+
+// includes reports whether t ∈ x.
+func (x *term) includes(t types.Type) bool {
+ // easy cases
+ switch {
+ case x == nil:
+ return false // t ∈ ∅ == false
+ case x.typ == nil:
+ return true // t ∈ π€ == true
+ }
+ // ∅ ⊂ x ⊂ π€
+
+ u := t
+ if x.tilde {
+ u = under(u)
+ }
+ return types.Identical(x.typ, u)
+}
+
+// subsetOf reports whether x ⊆ y.
+func (x *term) subsetOf(y *term) bool {
+ // easy cases
+ switch {
+ case x == nil:
+ return true // ∅ ⊆ y == true
+ case y == nil:
+ return false // x ⊆ ∅ == false since x != ∅
+ case y.typ == nil:
+ return true // x ⊆ π€ == true
+ case x.typ == nil:
+ return false // π€ ⊆ y == false since y != π€
+ }
+ // ∅ ⊂ x, y ⊂ π€
+
+ if x.disjoint(y) {
+ return false // x ⊆ y == false if x ∩ y == ∅
+ }
+ // x.typ == y.typ
+
+ // ~t ⊆ ~t == true
+ // ~t ⊆ T == false
+ // T ⊆ ~t == true
+ // T ⊆ T == true
+ return !x.tilde || y.tilde
+}
+
+// disjoint reports whether x ∩ y == ∅.
+// x.typ and y.typ must not be nil.
+func (x *term) disjoint(y *term) bool {
+ if debug && (x.typ == nil || y.typ == nil) {
+ panic("invalid argument(s)")
+ }
+ ux := x.typ
+ if y.tilde {
+ ux = under(ux)
+ }
+ uy := y.typ
+ if x.tilde {
+ uy = under(uy)
+ }
+ return !types.Identical(ux, uy)
+}
