mirror of
https://github.com/burrowers/garble.git
synced 2025-09-26 20:01:16 +08:00
cb83c50b13
Except on reflect_abi_code.go, as that needs to be compatible with older versions of Go given that we inject its code.
355 lines
9.4 KiB
Go
355 lines
9.4 KiB
Go
// Originally bundled from golang.org/x/tools/internal/typeparams@v0.29.0,
|
||
// as it is used by x/tools/go/types/typeutil and is an internal package.
|
||
|
||
package main
|
||
|
||
import (
|
||
"bytes"
|
||
"errors"
|
||
"fmt"
|
||
"go/types"
|
||
)
|
||
|
||
var errEmptyTypeSet = errors.New("empty type set")
|
||
|
||
// InterfaceTermSet computes the normalized terms for a constraint interface,
|
||
// returning an error if the term set cannot be computed or is empty. In the
|
||
// latter case, the error will be ErrEmptyTypeSet.
|
||
//
|
||
// See the documentation of StructuralTerms for more information on
|
||
// normalization.
|
||
func typeparams_InterfaceTermSet(iface *types.Interface) ([]*types.Term, error) {
|
||
return typeparams_computeTermSet(iface)
|
||
}
|
||
|
||
// UnionTermSet computes the normalized terms for a union, returning an error
|
||
// if the term set cannot be computed or is empty. In the latter case, the
|
||
// error will be ErrEmptyTypeSet.
|
||
//
|
||
// See the documentation of StructuralTerms for more information on
|
||
// normalization.
|
||
func typeparams_UnionTermSet(union *types.Union) ([]*types.Term, error) {
|
||
return typeparams_computeTermSet(union)
|
||
}
|
||
|
||
func typeparams_computeTermSet(typ types.Type) ([]*types.Term, error) {
|
||
tset, err := typeparams_computeTermSetInternal(typ, make(map[types.Type]*typeparams_termSet), 0)
|
||
if err != nil {
|
||
return nil, err
|
||
}
|
||
if tset.terms.isEmpty() {
|
||
return nil, errEmptyTypeSet
|
||
}
|
||
if tset.terms.isAll() {
|
||
return nil, nil
|
||
}
|
||
var terms []*types.Term
|
||
for _, term := range tset.terms {
|
||
terms = append(terms, types.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 typeparams_termSet struct {
|
||
complete bool
|
||
terms typeparams_termlist
|
||
}
|
||
|
||
func typeparams_computeTermSetInternal(t types.Type, seen map[types.Type]*typeparams_termSet, depth int) (res *typeparams_termSet, err error) {
|
||
if t == nil {
|
||
panic("nil type")
|
||
}
|
||
|
||
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(typeparams_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 = typeparams_allTermlist
|
||
for i := range u.NumEmbeddeds() {
|
||
embedded := u.EmbeddedType(i)
|
||
if _, ok := embedded.Underlying().(*types.TypeParam); ok {
|
||
return nil, fmt.Errorf("invalid embedded type %T", embedded)
|
||
}
|
||
tset2, err := typeparams_computeTermSetInternal(embedded, seen, depth+1)
|
||
if err != nil {
|
||
return nil, err
|
||
}
|
||
tset.terms = tset.terms.intersect(tset2.terms)
|
||
}
|
||
case *types.Union:
|
||
// The term set of a union is the union of term sets of its terms.
|
||
tset.terms = nil
|
||
for i := range u.Len() {
|
||
t := u.Term(i)
|
||
var terms typeparams_termlist
|
||
switch t.Type().Underlying().(type) {
|
||
case *types.Interface:
|
||
tset2, err := typeparams_computeTermSetInternal(t.Type(), seen, depth+1)
|
||
if err != nil {
|
||
return nil, err
|
||
}
|
||
terms = tset2.terms
|
||
case *types.TypeParam, *types.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 = typeparams_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 *types.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 = typeparams_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 typeparams_under(t types.Type) types.Type {
|
||
return t.Underlying()
|
||
}
|
||
|
||
// 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 typeparams_termlist []*typeparams_term
|
||
|
||
// allTermlist represents the set of all types.
|
||
// It is in normal form.
|
||
|
||
// allTermlist represents the set of all types.
|
||
// It is in normal form.
|
||
var typeparams_allTermlist = typeparams_termlist{new(typeparams_term)}
|
||
|
||
// String prints the termlist exactly (without normalization).
|
||
func (xl typeparams_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 typeparams_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 typeparams_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 typeparams_termlist) norm() typeparams_termlist {
|
||
// Quadratic algorithm, but good enough for now.
|
||
// TODO(gri) fix asymptotic performance
|
||
used := make([]bool, len(xl))
|
||
var rl typeparams_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 typeparams_allTermlist
|
||
}
|
||
xi = u1
|
||
used[j] = true // xj is now unioned into xi - ignore it in future iterations
|
||
}
|
||
}
|
||
rl = append(rl, xi)
|
||
}
|
||
return rl
|
||
}
|
||
|
||
// union returns the union xl ∪ yl.
|
||
func (xl typeparams_termlist) union(yl typeparams_termlist) typeparams_termlist {
|
||
return append(xl, yl...).norm()
|
||
}
|
||
|
||
// intersect returns the intersection xl ∩ yl.
|
||
func (xl typeparams_termlist) intersect(yl typeparams_termlist) typeparams_termlist {
|
||
if xl.isEmpty() || yl.isEmpty() {
|
||
return nil
|
||
}
|
||
|
||
// Quadratic algorithm, but good enough for now.
|
||
// TODO(gri) fix asymptotic performance
|
||
var rl typeparams_termlist
|
||
for _, x := range xl {
|
||
for _, y := range yl {
|
||
if r := x.intersect(y); r != nil {
|
||
rl = append(rl, r)
|
||
}
|
||
}
|
||
}
|
||
return rl.norm()
|
||
}
|
||
|
||
// 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 typeparams_term struct {
|
||
tilde bool // valid if typ != nil
|
||
typ types.Type
|
||
}
|
||
|
||
func (x *typeparams_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()
|
||
}
|
||
}
|
||
|
||
// union returns the union x ∪ y: zero, one, or two non-nil terms.
|
||
func (x *typeparams_term) union(y *typeparams_term) (_, _ *typeparams_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 *typeparams_term) intersect(y *typeparams_term) *typeparams_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
|
||
}
|
||
|
||
// disjoint reports whether x ∩ y == ∅.
|
||
// x.typ and y.typ must not be nil.
|
||
func (x *typeparams_term) disjoint(y *typeparams_term) bool {
|
||
ux := x.typ
|
||
if y.tilde {
|
||
ux = typeparams_under(ux)
|
||
}
|
||
uy := y.typ
|
||
if x.tilde {
|
||
uy = typeparams_under(uy)
|
||
}
|
||
return !types.Identical(ux, uy)
|
||
}
|