blob: 6cf71f04588ea53c2bad7719db4a10c92386fdc6 [file] [log] [blame]
// 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 (
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 whose underlying type is not *types.TypeParam,
// *types.Interface, or *types.Union, this is just a single term with Tilde()
// == false and Type() == typ. For types whose underlying type is
// *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 is 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)
if t.Type() == types.Typ[types.Invalid] {
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:
// 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()