| // 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 ( |
| "fmt" |
| "go/types" |
| "os" |
| "strings" |
| ) |
| |
| //go:generate go run copytermlist.go |
| |
| const debug = false |
| |
| // NormalizeInterface returns the normal form of the interface iface, or nil if iface |
| // has an empty type set (i.e. there are no types that satisfy iface). If the |
| // resulting interface is non-nil, it will be identical to iface. |
| // |
| // An error is returned if the interface type is invalid, or too complicated to |
| // reasonably normalize (for example, contains unions with more than a hundred |
| // terms). |
| // |
| // An interface is in normal form if and only if: |
| // - it has 0 or 1 embedded types. |
| // - its embedded type is either a types.Union or has a concrete |
| // (non-interface) underlying type |
| // - if the embedded type is a union, each term of the union has a concrete |
| // underlying type, and no terms may be removed without changing the type set |
| // of the interface |
| func NormalizeInterface(iface *types.Interface) (*types.Interface, error) { |
| var methods []*types.Func |
| for i := 0; i < iface.NumMethods(); i++ { |
| methods = append(methods, iface.Method(i)) |
| } |
| var embeddeds []types.Type |
| tset, err := computeTermSet(iface, make(map[types.Type]*termSet), 0) |
| if err != nil { |
| return nil, err |
| } |
| switch { |
| case tset.terms.isEmpty(): |
| // Special case: as documented |
| return nil, nil |
| |
| case tset.terms.isAll(): |
| // No embeddeds. |
| |
| case len(tset.terms) == 1: |
| if !tset.terms[0].tilde { |
| embeddeds = append(embeddeds, tset.terms[0].typ) |
| break |
| } |
| fallthrough |
| default: |
| var terms []*Term |
| for _, term := range tset.terms { |
| terms = append(terms, NewTerm(term.tilde, term.typ)) |
| } |
| embeddeds = append(embeddeds, NewUnion(terms)) |
| } |
| |
| return types.NewInterfaceType(methods, embeddeds), 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 computeTermSet(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 := computeTermSet(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 := computeTermSet(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() |
| } |