package types
+import (
+ "fmt"
+ "go/token"
+)
+
// A Type represents a type of Go.
// All types implement the Type interface.
type Type interface {
- // Underlying returns the underlying type of a type.
+ // Underlying returns the underlying type of a type
+ // w/o following forwarding chains. Only used by
+ // client packages (here for backward-compatibility).
Underlying() Type
// String returns a string representation of a type.
// NewArray returns a new array type for the given element type and length.
// A negative length indicates an unknown length.
-func NewArray(elem Type, len int64) *Array { return &Array{len, elem} }
+func NewArray(elem Type, len int64) *Array { return &Array{len: len, elem: elem} }
// Len returns the length of array a.
// A negative result indicates an unknown length.
}
// NewSlice returns a new slice type for the given element type.
-func NewSlice(elem Type) *Slice { return &Slice{elem} }
+func NewSlice(elem Type) *Slice { return &Slice{elem: elem} }
// Elem returns the element type of slice s.
func (s *Slice) Elem() Type { return s.elem }
// NewTuple returns a new tuple for the given variables.
func NewTuple(x ...*Var) *Tuple {
if len(x) > 0 {
- return &Tuple{x}
+ return &Tuple{vars: x}
}
+ // TODO(gri) Don't represent empty tuples with a (*Tuple)(nil) pointer;
+ // it's too subtle and causes problems.
return nil
}
// and store it in the Func Object) because when type-checking a function
// literal we call the general type checker which returns a general Type.
// We then unpack the *Signature and use the scope for the literal body.
- scope *Scope // function scope, present for package-local signatures
- recv *Var // nil if not a method
- params *Tuple // (incoming) parameters from left to right; or nil
- results *Tuple // (outgoing) results from left to right; or nil
- variadic bool // true if the last parameter's type is of the form ...T (or string, for append built-in only)
+ rparams []*TypeName // receiver type parameters from left to right, or nil
+ tparams []*TypeName // type parameters from left to right, or nil
+ scope *Scope // function scope, present for package-local signatures
+ recv *Var // nil if not a method
+ params *Tuple // (incoming) parameters from left to right; or nil
+ results *Tuple // (outgoing) results from left to right; or nil
+ variadic bool // true if the last parameter's type is of the form ...T (or string, for append built-in only)
}
// NewSignature returns a new function type for the given receiver, parameters,
panic("types.NewSignature: variadic parameter must be of unnamed slice type")
}
}
- return &Signature{nil, recv, params, results, variadic}
+ return &Signature{recv: recv, params: params, results: results, variadic: variadic}
}
// Recv returns the receiver of signature s (if a method), or nil if a
// contain methods whose receiver type is a different interface.
func (s *Signature) Recv() *Var { return s.recv }
+// TParams returns the type parameters of signature s, or nil.
+func (s *Signature) TParams() []*TypeName { return s.tparams }
+
+// SetTParams sets the type parameters of signature s.
+func (s *Signature) SetTParams(tparams []*TypeName) { s.tparams = tparams }
+
// Params returns the parameters of signature s, or nil.
func (s *Signature) Params() *Tuple { return s.params }
// Variadic reports whether the signature s is variadic.
func (s *Signature) Variadic() bool { return s.variadic }
+// A Sum represents a set of possible types.
+// Sums are currently used to represent type lists of interfaces
+// and thus the underlying types of type parameters; they are not
+// first class types of Go.
+type Sum struct {
+ types []Type // types are unique
+}
+
+// NewSum returns a new Sum type consisting of the provided
+// types if there are more than one. If there is exactly one
+// type, it returns that type. If the list of types is empty
+// the result is nil.
+func NewSum(types []Type) Type {
+ if len(types) == 0 {
+ return nil
+ }
+
+ // What should happen if types contains a sum type?
+ // Do we flatten the types list? For now we check
+ // and panic. This should not be possible for the
+ // current use case of type lists.
+ // TODO(gri) Come up with the rules for sum types.
+ for _, t := range types {
+ if _, ok := t.(*Sum); ok {
+ panic("sum type contains sum type - unimplemented")
+ }
+ }
+
+ if len(types) == 1 {
+ return types[0]
+ }
+ return &Sum{types: types}
+}
+
+// is reports whether all types in t satisfy pred.
+func (s *Sum) is(pred func(Type) bool) bool {
+ if s == nil {
+ return false
+ }
+ for _, t := range s.types {
+ if !pred(t) {
+ return false
+ }
+ }
+ return true
+}
+
// An Interface represents an interface type.
type Interface struct {
methods []*Func // ordered list of explicitly declared methods
+ types Type // (possibly a Sum) type declared with a type list (TODO(gri) need better field name)
embeddeds []Type // ordered list of explicitly embedded types
allMethods []*Func // ordered list of methods declared with or embedded in this interface (TODO(gri): replace with mset)
+ allTypes Type // intersection of all embedded and locally declared types (TODO(gri) need better field name)
+
+ obj Object // type declaration defining this interface; or nil (for better error messages)
+}
+
+// unpack unpacks a type into a list of types.
+// TODO(gri) Try to eliminate the need for this function.
+func unpackType(typ Type) []Type {
+ if typ == nil {
+ return nil
+ }
+ if sum := asSum(typ); sum != nil {
+ return sum.types
+ }
+ return []Type{typ}
+}
+
+// is reports whether interface t represents types that all satisfy pred.
+func (t *Interface) is(pred func(Type) bool) bool {
+ if t.allTypes == nil {
+ return false // we must have at least one type! (was bug)
+ }
+ for _, t := range unpackType(t.allTypes) {
+ if !pred(t) {
+ return false
+ }
+ }
+ return true
}
// emptyInterface represents the empty (completed) interface
func (t *Interface) Method(i int) *Func { t.assertCompleteness(); return t.allMethods[i] }
// Empty reports whether t is the empty interface.
-// The interface must have been completed.
-func (t *Interface) Empty() bool { t.assertCompleteness(); return len(t.allMethods) == 0 }
+func (t *Interface) Empty() bool {
+ if t.allMethods != nil {
+ // interface is complete - quick test
+ // A non-nil allTypes may still be empty and represents the bottom type.
+ return len(t.allMethods) == 0 && t.allTypes == nil
+ }
+ return !t.iterate(func(t *Interface) bool {
+ return len(t.methods) > 0 || t.types != nil
+ }, nil)
+}
+
+// HasTypeList reports whether interface t has a type list, possibly from an embedded type.
+func (t *Interface) HasTypeList() bool {
+ if t.allMethods != nil {
+ // interface is complete - quick test
+ return t.allTypes != nil
+ }
+
+ return t.iterate(func(t *Interface) bool {
+ return t.types != nil
+ }, nil)
+}
+
+// IsComparable reports whether interface t is or embeds the predeclared interface "comparable".
+func (t *Interface) IsComparable() bool {
+ if t.allMethods != nil {
+ // interface is complete - quick test
+ _, m := lookupMethod(t.allMethods, nil, "==")
+ return m != nil
+ }
+
+ return t.iterate(func(t *Interface) bool {
+ _, m := lookupMethod(t.methods, nil, "==")
+ return m != nil
+ }, nil)
+}
+
+// IsConstraint reports t.HasTypeList() || t.IsComparable().
+func (t *Interface) IsConstraint() bool {
+ if t.allMethods != nil {
+ // interface is complete - quick test
+ if t.allTypes != nil {
+ return true
+ }
+ _, m := lookupMethod(t.allMethods, nil, "==")
+ return m != nil
+ }
+
+ return t.iterate(func(t *Interface) bool {
+ if t.types != nil {
+ return true
+ }
+ _, m := lookupMethod(t.methods, nil, "==")
+ return m != nil
+ }, nil)
+}
+
+// iterate calls f with t and then with any embedded interface of t, recursively, until f returns true.
+// iterate reports whether any call to f returned true.
+func (t *Interface) iterate(f func(*Interface) bool, seen map[*Interface]bool) bool {
+ if f(t) {
+ return true
+ }
+ for _, e := range t.embeddeds {
+ // e should be an interface but be careful (it may be invalid)
+ if e := asInterface(e); e != nil {
+ // Cyclic interfaces such as "type E interface { E }" are not permitted
+ // but they are still constructed and we need to detect such cycles.
+ if seen[e] {
+ continue
+ }
+ if seen == nil {
+ seen = make(map[*Interface]bool)
+ }
+ seen[e] = true
+ if e.iterate(f, seen) {
+ return true
+ }
+ }
+ }
+ return false
+}
+
+// isSatisfiedBy reports whether interface t's type list is satisfied by the type typ.
+// If the the type list is empty (absent), typ trivially satisfies the interface.
+// TODO(gri) This is not a great name. Eventually, we should have a more comprehensive
+// "implements" predicate.
+func (t *Interface) isSatisfiedBy(typ Type) bool {
+ t.Complete()
+ if t.allTypes == nil {
+ return true
+ }
+ types := unpackType(t.allTypes)
+ return includes(types, typ) || includes(types, under(typ))
+}
// Complete computes the interface's method set. It must be called by users of
// NewInterfaceType and NewInterface after the interface's embedded types are
addMethod(m, true)
}
+ allTypes := t.types
+
for _, typ := range t.embeddeds {
- typ := typ.Underlying().(*Interface)
- typ.Complete()
- for _, m := range typ.allMethods {
+ utyp := under(typ)
+ etyp := asInterface(utyp)
+ if etyp == nil {
+ if utyp != Typ[Invalid] {
+ panic(fmt.Sprintf("%s is not an interface", typ))
+ }
+ continue
+ }
+ etyp.Complete()
+ for _, m := range etyp.allMethods {
addMethod(m, false)
}
+ allTypes = intersect(allTypes, etyp.allTypes)
}
for i := 0; i < len(todo); i += 2 {
sortMethods(methods)
t.allMethods = methods
}
+ t.allTypes = allTypes
return t
}
// NewMap returns a new map for the given key and element types.
func NewMap(key, elem Type) *Map {
- return &Map{key, elem}
+ return &Map{key: key, elem: elem}
}
// Key returns the key type of map m.
// NewChan returns a new channel type for the given direction and element type.
func NewChan(dir ChanDir, elem Type) *Chan {
- return &Chan{dir, elem}
+ return &Chan{dir: dir, elem: elem}
}
// Dir returns the direction of channel c.
// Elem returns the element type of channel c.
func (c *Chan) Elem() Type { return c.elem }
-// A Named represents a named type.
+// A Named represents a named (defined) type.
type Named struct {
- info typeInfo // for cycle detection
- obj *TypeName // corresponding declared object
- orig Type // type (on RHS of declaration) this *Named type is derived of (for cycle reporting)
- underlying Type // possibly a *Named during setup; never a *Named once set up completely
- methods []*Func // methods declared for this type (not the method set of this type); signatures are type-checked lazily
+ check *Checker // for Named.under implementation
+ info typeInfo // for cycle detection
+ obj *TypeName // corresponding declared object
+ orig Type // type (on RHS of declaration) this *Named type is derived of (for cycle reporting)
+ underlying Type // possibly a *Named during setup; never a *Named once set up completely
+ tparams []*TypeName // type parameters, or nil
+ targs []Type // type arguments (after instantiation), or nil
+ methods []*Func // methods declared for this type (not the method set of this type); signatures are type-checked lazily
}
// NewNamed returns a new named type for the given type name, underlying type, and associated methods.
return typ
}
+func (check *Checker) NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
+ typ := &Named{check: check, obj: obj, orig: underlying, underlying: underlying, methods: methods}
+ if obj.typ == nil {
+ obj.typ = typ
+ }
+ return typ
+}
+
// Obj returns the type name for the named type t.
func (t *Named) Obj() *TypeName { return t.obj }
+// TODO(gri) Come up with a better representation and API to distinguish
+// between parameterized instantiated and non-instantiated types.
+
+// TParams returns the type parameters of the named type t, or nil.
+// The result is non-nil for an (originally) parameterized type even if it is instantiated.
+func (t *Named) TParams() []*TypeName { return t.tparams }
+
+// TArgs returns the type arguments after instantiation of the named type t, or nil if not instantiated.
+func (t *Named) TArgs() []Type { return t.targs }
+
+// SetTArgs sets the type arguments of Named.
+func (t *Named) SetTArgs(args []Type) { t.targs = args }
+
// NumMethods returns the number of explicit methods whose receiver is named type t.
func (t *Named) NumMethods() int { return len(t.methods) }
}
}
-// Implementations for Type methods.
+// A TypeParam represents a type parameter type.
+type TypeParam struct {
+ check *Checker // for lazy type bound completion
+ id uint64 // unique id
+ obj *TypeName // corresponding type name
+ index int // parameter index
+ bound Type // *Named or *Interface; underlying type is always *Interface
+}
-func (b *Basic) Underlying() Type { return b }
-func (a *Array) Underlying() Type { return a }
-func (s *Slice) Underlying() Type { return s }
-func (s *Struct) Underlying() Type { return s }
-func (p *Pointer) Underlying() Type { return p }
+// NewTypeParam returns a new TypeParam.
+func (check *Checker) NewTypeParam(obj *TypeName, index int, bound Type) *TypeParam {
+ assert(bound != nil)
+ typ := &TypeParam{check: check, id: check.nextId, obj: obj, index: index, bound: bound}
+ check.nextId++
+ if obj.typ == nil {
+ obj.typ = typ
+ }
+ return typ
+}
+
+func (t *TypeParam) Bound() *Interface {
+ iface := asInterface(t.bound)
+ // use the type bound position if we have one
+ pos := token.NoPos
+ if n, _ := t.bound.(*Named); n != nil {
+ pos = n.obj.pos
+ }
+ // TODO(rFindley) switch this to an unexported method on Checker.
+ t.check.completeInterface(pos, iface)
+ return iface
+}
+
+// optype returns a type's operational type. Except for
+// type parameters, the operational type is the same
+// as the underlying type (as returned by under). For
+// Type parameters, the operational type is determined
+// by the corresponding type bound's type list. The
+// result may be the bottom or top type, but it is never
+// the incoming type parameter.
+func optype(typ Type) Type {
+ if t := asTypeParam(typ); t != nil {
+ // If the optype is typ, return the top type as we have
+ // no information. It also prevents infinite recursion
+ // via the asTypeParam converter function. This can happen
+ // for a type parameter list of the form:
+ // (type T interface { type T }).
+ // See also issue #39680.
+ if u := t.Bound().allTypes; u != nil && u != typ {
+ // u != typ and u is a type parameter => under(u) != typ, so this is ok
+ return under(u)
+ }
+ return theTop
+ }
+ return under(typ)
+}
+
+// An instance represents an instantiated generic type syntactically
+// (without expanding the instantiation). Type instances appear only
+// during type-checking and are replaced by their fully instantiated
+// (expanded) types before the end of type-checking.
+type instance struct {
+ check *Checker // for lazy instantiation
+ pos token.Pos // position of type instantiation; for error reporting only
+ base *Named // parameterized type to be instantiated
+ targs []Type // type arguments
+ poslist []token.Pos // position of each targ; for error reporting only
+ value Type // base(targs...) after instantiation or Typ[Invalid]; nil if not yet set
+}
+
+// expand returns the instantiated (= expanded) type of t.
+// The result is either an instantiated *Named type, or
+// Typ[Invalid] if there was an error.
+func (t *instance) expand() Type {
+ v := t.value
+ if v == nil {
+ v = t.check.instantiate(t.pos, t.base, t.targs, t.poslist)
+ if v == nil {
+ v = Typ[Invalid]
+ }
+ t.value = v
+ }
+ // After instantiation we must have an invalid or a *Named type.
+ if debug && v != Typ[Invalid] {
+ _ = v.(*Named)
+ }
+ return v
+}
+
+// expand expands a type instance into its instantiated
+// type and leaves all other types alone. expand does
+// not recurse.
+func expand(typ Type) Type {
+ if t, _ := typ.(*instance); t != nil {
+ return t.expand()
+ }
+ return typ
+}
+
+// expandf is set to expand.
+// Call expandf when calling expand causes compile-time cycle error.
+var expandf func(Type) Type
+
+func init() { expandf = expand }
+
+// bottom represents the bottom of the type lattice.
+// It is the underlying type of a type parameter that
+// cannot be satisfied by any type, usually because
+// the intersection of type constraints left nothing).
+type bottom struct{}
+
+// theBottom is the singleton bottom type.
+var theBottom = &bottom{}
+
+// top represents the top of the type lattice.
+// It is the underlying type of a type parameter that
+// can be satisfied by any type (ignoring methods),
+// usually because the type constraint has no type
+// list.
+type top struct{}
+
+// theTop is the singleton top type.
+var theTop = &top{}
+
+// Type-specific implementations of Underlying.
+func (t *Basic) Underlying() Type { return t }
+func (t *Array) Underlying() Type { return t }
+func (t *Slice) Underlying() Type { return t }
+func (t *Struct) Underlying() Type { return t }
+func (t *Pointer) Underlying() Type { return t }
func (t *Tuple) Underlying() Type { return t }
-func (s *Signature) Underlying() Type { return s }
+func (t *Signature) Underlying() Type { return t }
+func (t *Sum) Underlying() Type { return t }
func (t *Interface) Underlying() Type { return t }
-func (m *Map) Underlying() Type { return m }
-func (c *Chan) Underlying() Type { return c }
+func (t *Map) Underlying() Type { return t }
+func (t *Chan) Underlying() Type { return t }
func (t *Named) Underlying() Type { return t.underlying }
-
-func (b *Basic) String() string { return TypeString(b, nil) }
-func (a *Array) String() string { return TypeString(a, nil) }
-func (s *Slice) String() string { return TypeString(s, nil) }
-func (s *Struct) String() string { return TypeString(s, nil) }
-func (p *Pointer) String() string { return TypeString(p, nil) }
+func (t *TypeParam) Underlying() Type { return t }
+func (t *instance) Underlying() Type { return t }
+func (t *bottom) Underlying() Type { return t }
+func (t *top) Underlying() Type { return t }
+
+// Type-specific implementations of String.
+func (t *Basic) String() string { return TypeString(t, nil) }
+func (t *Array) String() string { return TypeString(t, nil) }
+func (t *Slice) String() string { return TypeString(t, nil) }
+func (t *Struct) String() string { return TypeString(t, nil) }
+func (t *Pointer) String() string { return TypeString(t, nil) }
func (t *Tuple) String() string { return TypeString(t, nil) }
-func (s *Signature) String() string { return TypeString(s, nil) }
+func (t *Signature) String() string { return TypeString(t, nil) }
+func (t *Sum) String() string { return TypeString(t, nil) }
func (t *Interface) String() string { return TypeString(t, nil) }
-func (m *Map) String() string { return TypeString(m, nil) }
-func (c *Chan) String() string { return TypeString(c, nil) }
+func (t *Map) String() string { return TypeString(t, nil) }
+func (t *Chan) String() string { return TypeString(t, nil) }
func (t *Named) String() string { return TypeString(t, nil) }
+func (t *TypeParam) String() string { return TypeString(t, nil) }
+func (t *instance) String() string { return TypeString(t, nil) }
+func (t *bottom) String() string { return TypeString(t, nil) }
+func (t *top) String() string { return TypeString(t, nil) }
+
+// under returns the true expanded underlying type.
+// If it doesn't exist, the result is Typ[Invalid].
+// under must only be called when a type is known
+// to be fully set up.
+func under(t Type) Type {
+ // TODO(gri) is this correct for *Sum?
+ if n := asNamed(t); n != nil {
+ return n.under()
+ }
+ return t
+}
+
+// Converters
+//
+// A converter must only be called when a type is
+// known to be fully set up. A converter returns
+// a type's operational type (see comment for optype)
+// or nil if the type argument is not of the
+// respective type.
+
+func asBasic(t Type) *Basic {
+ op, _ := optype(t).(*Basic)
+ return op
+}
+
+func asArray(t Type) *Array {
+ op, _ := optype(t).(*Array)
+ return op
+}
+
+func asSlice(t Type) *Slice {
+ op, _ := optype(t).(*Slice)
+ return op
+}
+
+// TODO (rFindley) delete this on the dev.typeparams branch. This is only
+// exported in the prototype for legacy compatibility.
+func AsStruct(t Type) *Struct {
+ return asStruct(t)
+}
+
+func asStruct(t Type) *Struct {
+ op, _ := optype(t).(*Struct)
+ return op
+}
+
+// TODO(rFindley) delete this on the dev.typeparams branch (see ToStruct).
+func AsPointer(t Type) *Pointer {
+ return asPointer(t)
+}
+
+func asPointer(t Type) *Pointer {
+ op, _ := optype(t).(*Pointer)
+ return op
+}
+
+func asTuple(t Type) *Tuple {
+ op, _ := optype(t).(*Tuple)
+ return op
+}
+
+func asSignature(t Type) *Signature {
+ op, _ := optype(t).(*Signature)
+ return op
+}
+
+func asSum(t Type) *Sum {
+ op, _ := optype(t).(*Sum)
+ return op
+}
+
+func asInterface(t Type) *Interface {
+ op, _ := optype(t).(*Interface)
+ return op
+}
+
+func asMap(t Type) *Map {
+ op, _ := optype(t).(*Map)
+ return op
+}
+
+func asChan(t Type) *Chan {
+ op, _ := optype(t).(*Chan)
+ return op
+}
+
+// If the argument to asNamed and asTypeParam is of the respective types
+// (possibly after expanding an instance type), these methods return that type.
+// Otherwise the result is nil.
+
+func asNamed(t Type) *Named {
+ e, _ := expand(t).(*Named)
+ return e
+}
+
+func asTypeParam(t Type) *TypeParam {
+ u, _ := under(t).(*TypeParam)
+ return u
+}