normalize.go

Documentation: golang.org/x/tools/internal/typeparams

     1  // Copyright 2021 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package typeparams
     6  
     7  import (
     8  	"errors"
     9  	"fmt"
    10  	"go/types"
    11  	"os"
    12  	"strings"
    13  )
    14  
    15  //go:generate go run copytermlist.go
    16  
    17  const debug = false
    18  
    19  var ErrEmptyTypeSet = errors.New("empty type set")
    20  
    21  // StructuralTerms returns a slice of terms representing the normalized
    22  // structural type restrictions of a type parameter, if any.
    23  //
    24  // Structural type restrictions of a type parameter are created via
    25  // non-interface types embedded in its constraint interface (directly, or via a
    26  // chain of interface embeddings). For example, in the declaration
    27  //
    28  //	type T[P interface{~int; m()}] int
    29  //
    30  // the structural restriction of the type parameter P is ~int.
    31  //
    32  // With interface embedding and unions, the specification of structural type
    33  // restrictions may be arbitrarily complex. For example, consider the
    34  // following:
    35  //
    36  //	type A interface{ ~string|~[]byte }
    37  //
    38  //	type B interface{ int|string }
    39  //
    40  //	type C interface { ~string|~int }
    41  //
    42  //	type T[P interface{ A|B; C }] int
    43  //
    44  // In this example, the structural type restriction of P is ~string|int: A|B
    45  // expands to ~string|~[]byte|int|string, which reduces to ~string|~[]byte|int,
    46  // which when intersected with C (~string|~int) yields ~string|int.
    47  //
    48  // StructuralTerms computes these expansions and reductions, producing a
    49  // "normalized" form of the embeddings. A structural restriction is normalized
    50  // if it is a single union containing no interface terms, and is minimal in the
    51  // sense that removing any term changes the set of types satisfying the
    52  // constraint. It is left as a proof for the reader that, modulo sorting, there
    53  // is exactly one such normalized form.
    54  //
    55  // Because the minimal representation always takes this form, StructuralTerms
    56  // returns a slice of tilde terms corresponding to the terms of the union in
    57  // the normalized structural restriction. An error is returned if the
    58  // constraint interface is invalid, exceeds complexity bounds, or has an empty
    59  // type set. In the latter case, StructuralTerms returns ErrEmptyTypeSet.
    60  //
    61  // StructuralTerms makes no guarantees about the order of terms, except that it
    62  // is deterministic.
    63  func StructuralTerms(tparam *TypeParam) ([]*Term, error) {
    64  	constraint := tparam.Constraint()
    65  	if constraint == nil {
    66  		return nil, fmt.Errorf("%s has nil constraint", tparam)
    67  	}
    68  	iface, _ := constraint.Underlying().(*types.Interface)
    69  	if iface == nil {
    70  		return nil, fmt.Errorf("constraint is %T, not *types.Interface", constraint.Underlying())
    71  	}
    72  	return InterfaceTermSet(iface)
    73  }
    74  
    75  // InterfaceTermSet computes the normalized terms for a constraint interface,
    76  // returning an error if the term set cannot be computed or is empty. In the
    77  // latter case, the error will be ErrEmptyTypeSet.
    78  //
    79  // See the documentation of StructuralTerms for more information on
    80  // normalization.
    81  func InterfaceTermSet(iface *types.Interface) ([]*Term, error) {
    82  	return computeTermSet(iface)
    83  }
    84  
    85  // UnionTermSet computes the normalized terms for a union, returning an error
    86  // if the term set cannot be computed or is empty. In the latter case, the
    87  // error will be ErrEmptyTypeSet.
    88  //
    89  // See the documentation of StructuralTerms for more information on
    90  // normalization.
    91  func UnionTermSet(union *Union) ([]*Term, error) {
    92  	return computeTermSet(union)
    93  }
    94  
    95  func computeTermSet(typ types.Type) ([]*Term, error) {
    96  	tset, err := computeTermSetInternal(typ, make(map[types.Type]*termSet), 0)
    97  	if err != nil {
    98  		return nil, err
    99  	}
   100  	if tset.terms.isEmpty() {
   101  		return nil, ErrEmptyTypeSet
   102  	}
   103  	if tset.terms.isAll() {
   104  		return nil, nil
   105  	}
   106  	var terms []*Term
   107  	for _, term := range tset.terms {
   108  		terms = append(terms, NewTerm(term.tilde, term.typ))
   109  	}
   110  	return terms, nil
   111  }
   112  
   113  // A termSet holds the normalized set of terms for a given type.
   114  //
   115  // The name termSet is intentionally distinct from 'type set': a type set is
   116  // all types that implement a type (and includes method restrictions), whereas
   117  // a term set just represents the structural restrictions on a type.
   118  type termSet struct {
   119  	complete bool
   120  	terms    termlist
   121  }
   122  
   123  func indentf(depth int, format string, args ...interface{}) {
   124  	fmt.Fprintf(os.Stderr, strings.Repeat(".", depth)+format+"\n", args...)
   125  }
   126  
   127  func computeTermSetInternal(t types.Type, seen map[types.Type]*termSet, depth int) (res *termSet, err error) {
   128  	if t == nil {
   129  		panic("nil type")
   130  	}
   131  
   132  	if debug {
   133  		indentf(depth, "%s", t.String())
   134  		defer func() {
   135  			if err != nil {
   136  				indentf(depth, "=> %s", err)
   137  			} else {
   138  				indentf(depth, "=> %s", res.terms.String())
   139  			}
   140  		}()
   141  	}
   142  
   143  	const maxTermCount = 100
   144  	if tset, ok := seen[t]; ok {
   145  		if !tset.complete {
   146  			return nil, fmt.Errorf("cycle detected in the declaration of %s", t)
   147  		}
   148  		return tset, nil
   149  	}
   150  
   151  	// Mark the current type as seen to avoid infinite recursion.
   152  	tset := new(termSet)
   153  	defer func() {
   154  		tset.complete = true
   155  	}()
   156  	seen[t] = tset
   157  
   158  	switch u := t.Underlying().(type) {
   159  	case *types.Interface:
   160  		// The term set of an interface is the intersection of the term sets of its
   161  		// embedded types.
   162  		tset.terms = allTermlist
   163  		for i := 0; i < u.NumEmbeddeds(); i++ {
   164  			embedded := u.EmbeddedType(i)
   165  			if _, ok := embedded.Underlying().(*TypeParam); ok {
   166  				return nil, fmt.Errorf("invalid embedded type %T", embedded)
   167  			}
   168  			tset2, err := computeTermSetInternal(embedded, seen, depth+1)
   169  			if err != nil {
   170  				return nil, err
   171  			}
   172  			tset.terms = tset.terms.intersect(tset2.terms)
   173  		}
   174  	case *Union:
   175  		// The term set of a union is the union of term sets of its terms.
   176  		tset.terms = nil
   177  		for i := 0; i < u.Len(); i++ {
   178  			t := u.Term(i)
   179  			var terms termlist
   180  			switch t.Type().Underlying().(type) {
   181  			case *types.Interface:
   182  				tset2, err := computeTermSetInternal(t.Type(), seen, depth+1)
   183  				if err != nil {
   184  					return nil, err
   185  				}
   186  				terms = tset2.terms
   187  			case *TypeParam, *Union:
   188  				// A stand-alone type parameter or union is not permitted as union
   189  				// term.
   190  				return nil, fmt.Errorf("invalid union term %T", t)
   191  			default:
   192  				if t.Type() == types.Typ[types.Invalid] {
   193  					continue
   194  				}
   195  				terms = termlist{{t.Tilde(), t.Type()}}
   196  			}
   197  			tset.terms = tset.terms.union(terms)
   198  			if len(tset.terms) > maxTermCount {
   199  				return nil, fmt.Errorf("exceeded max term count %d", maxTermCount)
   200  			}
   201  		}
   202  	case *TypeParam:
   203  		panic("unreachable")
   204  	default:
   205  		// For all other types, the term set is just a single non-tilde term
   206  		// holding the type itself.
   207  		if u != types.Typ[types.Invalid] {
   208  			tset.terms = termlist{{false, t}}
   209  		}
   210  	}
   211  	return tset, nil
   212  }
   213  
   214  // under is a facade for the go/types internal function of the same name. It is
   215  // used by typeterm.go.
   216  func under(t types.Type) types.Type {
   217  	return t.Underlying()
   218  }
   219
View as plain text