internal/typeparams: adds core type implementation
Adds a function for computing the core type of a type for use within x/tools.
Updates golang/go#52940
Change-Id: I91645c0b27031506be51a5f9d53b3e125e6fd1c2
Reviewed-on: https://go-review.googlesource.com/c/tools/+/406838
Run-TryBot: Tim King <taking@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/internal/typeparams/coretype.go b/internal/typeparams/coretype.go
new file mode 100644
index 0000000..993135e
--- /dev/null
+++ b/internal/typeparams/coretype.go
@@ -0,0 +1,122 @@
+// 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 typeparams
+
+import (
+ "go/types"
+)
+
+// CoreType returns the core type of T or nil if T does not have a core type.
+//
+// See https://go.dev/ref/spec#Core_types for the definition of a core type.
+func CoreType(T types.Type) types.Type {
+ U := T.Underlying()
+ if _, ok := U.(*types.Interface); !ok {
+ return U // for non-interface types,
+ }
+
+ terms, err := _NormalTerms(U)
+ if len(terms) == 0 || err != nil {
+ // len(terms) -> empty type set of interface.
+ // err != nil => U is invalid, exceeds complexity bounds, or has an empty type set.
+ return nil // no core type.
+ }
+
+ U = terms[0].Type().Underlying()
+ var identical int // i in [0,identical) => Identical(U, terms[i].Type().Underlying())
+ for identical = 1; identical < len(terms); identical++ {
+ if !types.Identical(U, terms[identical].Type().Underlying()) {
+ break
+ }
+ }
+
+ if identical == len(terms) {
+ // https://go.dev/ref/spec#Core_types
+ // "There is a single type U which is the underlying type of all types in the type set of T"
+ return U
+ }
+ ch, ok := U.(*types.Chan)
+ if !ok {
+ return nil // no core type as identical < len(terms) and U is not a channel.
+ }
+ // https://go.dev/ref/spec#Core_types
+ // "the type chan E if T contains only bidirectional channels, or the type chan<- E or
+ // <-chan E depending on the direction of the directional channels present."
+ for chans := identical; chans < len(terms); chans++ {
+ curr, ok := terms[chans].Type().Underlying().(*types.Chan)
+ if !ok {
+ return nil
+ }
+ if !types.Identical(ch.Elem(), curr.Elem()) {
+ return nil // channel elements are not identical.
+ }
+ if ch.Dir() == types.SendRecv {
+ // ch is bidirectional. We can safely always use curr's direction.
+ ch = curr
+ } else if curr.Dir() != types.SendRecv && ch.Dir() != curr.Dir() {
+ // ch and curr are not bidirectional and not the same direction.
+ return nil
+ }
+ }
+ return ch
+}
+
+// _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) {
+ switch typ := typ.(type) {
+ case *TypeParam:
+ return StructuralTerms(typ)
+ case *Union:
+ return UnionTermSet(typ)
+ case *types.Interface:
+ return InterfaceTermSet(typ)
+ default:
+ return []*Term{NewTerm(false, typ)}, nil
+ }
+}
diff --git a/internal/typeparams/coretype_test.go b/internal/typeparams/coretype_test.go
new file mode 100644
index 0000000..2884399
--- /dev/null
+++ b/internal/typeparams/coretype_test.go
@@ -0,0 +1,105 @@
+// 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 typeparams_test
+
+import (
+ "go/ast"
+ "go/parser"
+ "go/token"
+ "go/types"
+ "testing"
+
+ "golang.org/x/tools/internal/typeparams"
+)
+
+func TestCoreType(t *testing.T) {
+ if !typeparams.Enabled {
+ t.Skip("TestCoreType requires type parameters.")
+ }
+
+ const source = `
+ package P
+
+ type Named int
+
+ type A any
+ type B interface{~int}
+ type C interface{int}
+ type D interface{Named}
+ type E interface{~int|interface{Named}}
+ type F interface{~int|~float32}
+ type G interface{chan int|interface{chan int}}
+ type H interface{chan int|chan float32}
+ type I interface{chan<- int|chan int}
+ type J interface{chan int|chan<- int}
+ type K interface{<-chan int|chan int}
+ type L interface{chan int|<-chan int}
+ type M interface{chan int|chan Named}
+ type N interface{<-chan int|chan<- int}
+ type O interface{chan int|bool}
+ type P struct{ Named }
+ type Q interface{ Foo() }
+ type R interface{ Foo() ; Named }
+ type S interface{ Foo() ; ~int }
+
+ type T interface{chan int|interface{chan int}|<-chan int}
+`
+
+ fset := token.NewFileSet()
+ f, err := parser.ParseFile(fset, "hello.go", source, 0)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ var conf types.Config
+ pkg, err := conf.Check("P", fset, []*ast.File{f}, nil)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ for _, test := range []struct {
+ expr string // type expression of Named type
+ want string // expected core type (or "<nil>" if none)
+ }{
+ {"Named", "int"}, // Underlying type is not interface.
+ {"A", "<nil>"}, // Interface has no terms.
+ {"B", "int"}, // Tilde term.
+ {"C", "int"}, // Non-tilde term.
+ {"D", "int"}, // Named term.
+ {"E", "int"}, // Identical underlying types.
+ {"F", "<nil>"}, // Differing underlying types.
+ {"G", "chan int"}, // Identical Element types.
+ {"H", "<nil>"}, // Element type int has differing underlying type to float32.
+ {"I", "chan<- int"}, // SendRecv followed by SendOnly
+ {"J", "chan<- int"}, // SendOnly followed by SendRecv
+ {"K", "<-chan int"}, // RecvOnly followed by SendRecv
+ {"L", "<-chan int"}, // SendRecv followed by RecvOnly
+ {"M", "<nil>"}, // Element type int is not *identical* to Named.
+ {"N", "<nil>"}, // Differing channel directions
+ {"O", "<nil>"}, // A channel followed by a non-channel.
+ {"P", "struct{P.Named}"}, // Embedded type.
+ {"Q", "<nil>"}, // interface type with no terms and functions
+ {"R", "int"}, // interface type with both terms and functions.
+ {"S", "int"}, // interface type with a tilde term
+ {"T", "<-chan int"}, // Prefix of 2 terms that are identical before switching to channel.
+ } {
+ // Eval() expr for its type.
+ tv, err := types.Eval(fset, pkg, 0, test.expr)
+ if err != nil {
+ t.Fatalf("Eval(%s) failed: %v", test.expr, err)
+ }
+
+ ct := typeparams.CoreType(tv.Type)
+ var got string
+ if ct == nil {
+ got = "<nil>"
+ } else {
+ got = ct.String()
+ }
+ if got != test.want {
+ t.Errorf("coreType(%s) = %v, want %v", test.expr, got, test.want)
+ }
+ }
+}
