Source file src/cmd/compile/internal/types/type.go

     1  // Copyright 2017 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 types
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/internal/objabi"
    10  	"cmd/internal/src"
    11  	"fmt"
    12  	"go/constant"
    13  	"internal/types/errors"
    14  	"sync"
    15  )
    16  
    17  // Object represents an ir.Node, but without needing to import cmd/compile/internal/ir,
    18  // which would cause an import cycle. The uses in other packages must type assert
    19  // values of type Object to ir.Node or a more specific type.
    20  type Object interface {
    21  	Pos() src.XPos
    22  	Sym() *Sym
    23  	Type() *Type
    24  }
    25  
    26  //go:generate stringer -type Kind -trimprefix T type.go
    27  
    28  // Kind describes a kind of type.
    29  type Kind uint8
    30  
    31  const (
    32  	Txxx Kind = iota
    33  
    34  	TINT8
    35  	TUINT8
    36  	TINT16
    37  	TUINT16
    38  	TINT32
    39  	TUINT32
    40  	TINT64
    41  	TUINT64
    42  	TINT
    43  	TUINT
    44  	TUINTPTR
    45  
    46  	TCOMPLEX64
    47  	TCOMPLEX128
    48  
    49  	TFLOAT32
    50  	TFLOAT64
    51  
    52  	TBOOL
    53  
    54  	TPTR
    55  	TFUNC
    56  	TSLICE
    57  	TARRAY
    58  	TSTRUCT
    59  	TCHAN
    60  	TMAP
    61  	TINTER
    62  	TFORW
    63  	TANY
    64  	TSTRING
    65  	TUNSAFEPTR
    66  
    67  	// pseudo-types for literals
    68  	TIDEAL // untyped numeric constants
    69  	TNIL
    70  	TBLANK
    71  
    72  	// pseudo-types used temporarily only during frame layout (CalcSize())
    73  	TFUNCARGS
    74  	TCHANARGS
    75  
    76  	// SSA backend types
    77  	TSSA     // internal types used by SSA backend (flags, memory, etc.)
    78  	TTUPLE   // a pair of types, used by SSA backend
    79  	TRESULTS // multiple types; the result of calling a function or method, with a memory at the end.
    80  
    81  	NTYPE
    82  )
    83  
    84  // ChanDir is whether a channel can send, receive, or both.
    85  type ChanDir uint8
    86  
    87  func (c ChanDir) CanRecv() bool { return c&Crecv != 0 }
    88  func (c ChanDir) CanSend() bool { return c&Csend != 0 }
    89  
    90  const (
    91  	// types of channel
    92  	// must match ../../../../reflect/type.go:/ChanDir
    93  	Crecv ChanDir = 1 << 0
    94  	Csend ChanDir = 1 << 1
    95  	Cboth ChanDir = Crecv | Csend
    96  )
    97  
    98  // Types stores pointers to predeclared named types.
    99  //
   100  // It also stores pointers to several special types:
   101  //   - Types[TANY] is the placeholder "any" type recognized by SubstArgTypes.
   102  //   - Types[TBLANK] represents the blank variable's type.
   103  //   - Types[TINTER] is the canonical "interface{}" type.
   104  //   - Types[TNIL] represents the predeclared "nil" value's type.
   105  //   - Types[TUNSAFEPTR] is package unsafe's Pointer type.
   106  var Types [NTYPE]*Type
   107  
   108  var (
   109  	// Predeclared alias types. These are actually created as distinct
   110  	// defined types for better error messages, but are then specially
   111  	// treated as identical to their respective underlying types.
   112  	AnyType  *Type
   113  	ByteType *Type
   114  	RuneType *Type
   115  
   116  	// Predeclared error interface type.
   117  	ErrorType *Type
   118  	// Predeclared comparable interface type.
   119  	ComparableType *Type
   120  
   121  	// Types to represent untyped string and boolean constants.
   122  	UntypedString = newType(TSTRING)
   123  	UntypedBool   = newType(TBOOL)
   124  
   125  	// Types to represent untyped numeric constants.
   126  	UntypedInt     = newType(TIDEAL)
   127  	UntypedRune    = newType(TIDEAL)
   128  	UntypedFloat   = newType(TIDEAL)
   129  	UntypedComplex = newType(TIDEAL)
   130  )
   131  
   132  // UntypedTypes maps from a constant.Kind to its untyped Type
   133  // representation.
   134  var UntypedTypes = [...]*Type{
   135  	constant.Bool:    UntypedBool,
   136  	constant.String:  UntypedString,
   137  	constant.Int:     UntypedInt,
   138  	constant.Float:   UntypedFloat,
   139  	constant.Complex: UntypedComplex,
   140  }
   141  
   142  // DefaultKinds maps from a constant.Kind to its default Kind.
   143  var DefaultKinds = [...]Kind{
   144  	constant.Bool:    TBOOL,
   145  	constant.String:  TSTRING,
   146  	constant.Int:     TINT,
   147  	constant.Float:   TFLOAT64,
   148  	constant.Complex: TCOMPLEX128,
   149  }
   150  
   151  // A Type represents a Go type.
   152  //
   153  // There may be multiple unnamed types with identical structure. However, there must
   154  // be a unique Type object for each unique named (defined) type. After noding, a
   155  // package-level type can be looked up by building its unique symbol sym (sym =
   156  // package.Lookup(name)) and checking sym.Def. If sym.Def is non-nil, the type
   157  // already exists at package scope and is available at sym.Def.(*ir.Name).Type().
   158  // Local types (which may have the same name as a package-level type) are
   159  // distinguished by their vargen, which is embedded in their symbol name.
   160  type Type struct {
   161  	// extra contains extra etype-specific fields.
   162  	// As an optimization, those etype-specific structs which contain exactly
   163  	// one pointer-shaped field are stored as values rather than pointers when possible.
   164  	//
   165  	// TMAP: *Map
   166  	// TFORW: *Forward
   167  	// TFUNC: *Func
   168  	// TSTRUCT: *Struct
   169  	// TINTER: *Interface
   170  	// TFUNCARGS: FuncArgs
   171  	// TCHANARGS: ChanArgs
   172  	// TCHAN: *Chan
   173  	// TPTR: Ptr
   174  	// TARRAY: *Array
   175  	// TSLICE: Slice
   176  	// TSSA: string
   177  	extra interface{}
   178  
   179  	// width is the width of this Type in bytes.
   180  	width int64 // valid if Align > 0
   181  
   182  	// list of base methods (excluding embedding)
   183  	methods fields
   184  	// list of all methods (including embedding)
   185  	allMethods fields
   186  
   187  	// canonical OTYPE node for a named type (should be an ir.Name node with same sym)
   188  	obj Object
   189  	// the underlying type (type literal or predeclared type) for a defined type
   190  	underlying *Type
   191  
   192  	// Cache of composite types, with this type being the element type.
   193  	cache struct {
   194  		ptr   *Type // *T, or nil
   195  		slice *Type // []T, or nil
   196  	}
   197  
   198  	kind  Kind  // kind of type
   199  	align uint8 // the required alignment of this type, in bytes (0 means Width and Align have not yet been computed)
   200  
   201  	intRegs, floatRegs uint8 // registers needed for ABIInternal
   202  
   203  	flags bitset8
   204  
   205  	// For defined (named) generic types, a pointer to the list of type params
   206  	// (in order) of this type that need to be instantiated. For instantiated
   207  	// generic types, this is the targs used to instantiate them. These targs
   208  	// may be typeparams (for re-instantiated types such as Value[T2]) or
   209  	// concrete types (for fully instantiated types such as Value[int]).
   210  	// rparams is only set for named types that are generic or are fully
   211  	// instantiated from a generic type, and is otherwise set to nil.
   212  	// TODO(danscales): choose a better name.
   213  	rparams *[]*Type
   214  }
   215  
   216  // Registers returns the number of integer and floating-point
   217  // registers required to represent a parameter of this type under the
   218  // ABIInternal calling conventions.
   219  //
   220  // If t must be passed by memory, Registers returns (math.MaxUint8,
   221  // math.MaxUint8).
   222  func (t *Type) Registers() (uint8, uint8) {
   223  	CalcSize(t)
   224  	return t.intRegs, t.floatRegs
   225  }
   226  
   227  func (*Type) CanBeAnSSAAux() {}
   228  
   229  const (
   230  	typeNotInHeap  = 1 << iota // type cannot be heap allocated
   231  	typeNoalg                  // suppress hash and eq algorithm generation
   232  	typeDeferwidth             // width computation has been deferred and type is on deferredTypeStack
   233  	typeRecur
   234  	typeIsShape  // represents a set of closely related types, for generics
   235  	typeHasShape // there is a shape somewhere in the type
   236  )
   237  
   238  func (t *Type) NotInHeap() bool  { return t.flags&typeNotInHeap != 0 }
   239  func (t *Type) Noalg() bool      { return t.flags&typeNoalg != 0 }
   240  func (t *Type) Deferwidth() bool { return t.flags&typeDeferwidth != 0 }
   241  func (t *Type) Recur() bool      { return t.flags&typeRecur != 0 }
   242  func (t *Type) IsShape() bool    { return t.flags&typeIsShape != 0 }
   243  func (t *Type) HasShape() bool   { return t.flags&typeHasShape != 0 }
   244  
   245  func (t *Type) SetNotInHeap(b bool)  { t.flags.set(typeNotInHeap, b) }
   246  func (t *Type) SetNoalg(b bool)      { t.flags.set(typeNoalg, b) }
   247  func (t *Type) SetDeferwidth(b bool) { t.flags.set(typeDeferwidth, b) }
   248  func (t *Type) SetRecur(b bool)      { t.flags.set(typeRecur, b) }
   249  
   250  // Should always do SetHasShape(true) when doing SetIsShape(true).
   251  func (t *Type) SetIsShape(b bool)  { t.flags.set(typeIsShape, b) }
   252  func (t *Type) SetHasShape(b bool) { t.flags.set(typeHasShape, b) }
   253  
   254  // Kind returns the kind of type t.
   255  func (t *Type) Kind() Kind { return t.kind }
   256  
   257  // Sym returns the name of type t.
   258  func (t *Type) Sym() *Sym {
   259  	if t.obj != nil {
   260  		return t.obj.Sym()
   261  	}
   262  	return nil
   263  }
   264  
   265  // Underlying returns the underlying type of type t.
   266  func (t *Type) Underlying() *Type { return t.underlying }
   267  
   268  // Pos returns a position associated with t, if any.
   269  // This should only be used for diagnostics.
   270  func (t *Type) Pos() src.XPos {
   271  	if t.obj != nil {
   272  		return t.obj.Pos()
   273  	}
   274  	return src.NoXPos
   275  }
   276  
   277  func (t *Type) RParams() []*Type {
   278  	if t.rparams == nil {
   279  		return nil
   280  	}
   281  	return *t.rparams
   282  }
   283  
   284  func (t *Type) SetRParams(rparams []*Type) {
   285  	if len(rparams) == 0 {
   286  		base.Fatalf("Setting nil or zero-length rparams")
   287  	}
   288  	t.rparams = &rparams
   289  	// HasShape should be set if any type argument is or has a shape type.
   290  	for _, rparam := range rparams {
   291  		if rparam.HasShape() {
   292  			t.SetHasShape(true)
   293  			break
   294  		}
   295  	}
   296  }
   297  
   298  // IsFullyInstantiated reports whether t is a fully instantiated generic type; i.e. an
   299  // instantiated generic type where all type arguments are non-generic or fully
   300  // instantiated generic types.
   301  func (t *Type) IsFullyInstantiated() bool {
   302  	return len(t.RParams()) > 0
   303  }
   304  
   305  // Map contains Type fields specific to maps.
   306  type Map struct {
   307  	Key  *Type // Key type
   308  	Elem *Type // Val (elem) type
   309  
   310  	Bucket *Type // internal struct type representing a hash bucket
   311  }
   312  
   313  // MapType returns t's extra map-specific fields.
   314  func (t *Type) MapType() *Map {
   315  	t.wantEtype(TMAP)
   316  	return t.extra.(*Map)
   317  }
   318  
   319  // Forward contains Type fields specific to forward types.
   320  type Forward struct {
   321  	Copyto      []*Type  // where to copy the eventual value to
   322  	Embedlineno src.XPos // first use of this type as an embedded type
   323  }
   324  
   325  // forwardType returns t's extra forward-type-specific fields.
   326  func (t *Type) forwardType() *Forward {
   327  	t.wantEtype(TFORW)
   328  	return t.extra.(*Forward)
   329  }
   330  
   331  // Func contains Type fields specific to func types.
   332  type Func struct {
   333  	allParams []*Field // slice of all parameters, in receiver/params/results order
   334  
   335  	startParams  int // index of the start of the (regular) parameters section
   336  	startResults int // index of the start of the results section
   337  
   338  	resultsTuple *Type // struct-like type representing multi-value results
   339  
   340  	// Argwid is the total width of the function receiver, params, and results.
   341  	// It gets calculated via a temporary TFUNCARGS type.
   342  	// Note that TFUNC's Width is Widthptr.
   343  	Argwid int64
   344  }
   345  
   346  func (ft *Func) recvs() []*Field         { return ft.allParams[:ft.startParams] }
   347  func (ft *Func) params() []*Field        { return ft.allParams[ft.startParams:ft.startResults] }
   348  func (ft *Func) results() []*Field       { return ft.allParams[ft.startResults:] }
   349  func (ft *Func) recvParams() []*Field    { return ft.allParams[:ft.startResults] }
   350  func (ft *Func) paramsResults() []*Field { return ft.allParams[ft.startParams:] }
   351  
   352  // funcType returns t's extra func-specific fields.
   353  func (t *Type) funcType() *Func {
   354  	t.wantEtype(TFUNC)
   355  	return t.extra.(*Func)
   356  }
   357  
   358  // StructType contains Type fields specific to struct types.
   359  type Struct struct {
   360  	fields fields
   361  
   362  	// Maps have three associated internal structs (see struct MapType).
   363  	// Map links such structs back to their map type.
   364  	Map *Type
   365  
   366  	ParamTuple bool // whether this struct is actually a tuple of signature parameters
   367  }
   368  
   369  // StructType returns t's extra struct-specific fields.
   370  func (t *Type) StructType() *Struct {
   371  	t.wantEtype(TSTRUCT)
   372  	return t.extra.(*Struct)
   373  }
   374  
   375  // Interface contains Type fields specific to interface types.
   376  type Interface struct {
   377  }
   378  
   379  // Ptr contains Type fields specific to pointer types.
   380  type Ptr struct {
   381  	Elem *Type // element type
   382  }
   383  
   384  // ChanArgs contains Type fields specific to TCHANARGS types.
   385  type ChanArgs struct {
   386  	T *Type // reference to a chan type whose elements need a width check
   387  }
   388  
   389  // // FuncArgs contains Type fields specific to TFUNCARGS types.
   390  type FuncArgs struct {
   391  	T *Type // reference to a func type whose elements need a width check
   392  }
   393  
   394  // Chan contains Type fields specific to channel types.
   395  type Chan struct {
   396  	Elem *Type   // element type
   397  	Dir  ChanDir // channel direction
   398  }
   399  
   400  // chanType returns t's extra channel-specific fields.
   401  func (t *Type) chanType() *Chan {
   402  	t.wantEtype(TCHAN)
   403  	return t.extra.(*Chan)
   404  }
   405  
   406  type Tuple struct {
   407  	first  *Type
   408  	second *Type
   409  	// Any tuple with a memory type must put that memory type second.
   410  }
   411  
   412  // Results are the output from calls that will be late-expanded.
   413  type Results struct {
   414  	Types []*Type // Last element is memory output from call.
   415  }
   416  
   417  // Array contains Type fields specific to array types.
   418  type Array struct {
   419  	Elem  *Type // element type
   420  	Bound int64 // number of elements; <0 if unknown yet
   421  }
   422  
   423  // Slice contains Type fields specific to slice types.
   424  type Slice struct {
   425  	Elem *Type // element type
   426  }
   427  
   428  // A Field is a (Sym, Type) pairing along with some other information, and,
   429  // depending on the context, is used to represent:
   430  //   - a field in a struct
   431  //   - a method in an interface or associated with a named type
   432  //   - a function parameter
   433  type Field struct {
   434  	flags bitset8
   435  
   436  	Embedded uint8 // embedded field
   437  
   438  	Pos src.XPos
   439  
   440  	// Name of field/method/parameter. Can be nil for interface fields embedded
   441  	// in interfaces and unnamed parameters.
   442  	Sym  *Sym
   443  	Type *Type  // field type
   444  	Note string // literal string annotation
   445  
   446  	// For fields that represent function parameters, Nname points to the
   447  	// associated ONAME Node. For fields that represent methods, Nname points to
   448  	// the function name node.
   449  	Nname Object
   450  
   451  	// Offset in bytes of this field or method within its enclosing struct
   452  	// or interface Type. For parameters, this is BADWIDTH.
   453  	Offset int64
   454  }
   455  
   456  const (
   457  	fieldIsDDD = 1 << iota // field is ... argument
   458  	fieldNointerface
   459  )
   460  
   461  func (f *Field) IsDDD() bool       { return f.flags&fieldIsDDD != 0 }
   462  func (f *Field) Nointerface() bool { return f.flags&fieldNointerface != 0 }
   463  
   464  func (f *Field) SetIsDDD(b bool)       { f.flags.set(fieldIsDDD, b) }
   465  func (f *Field) SetNointerface(b bool) { f.flags.set(fieldNointerface, b) }
   466  
   467  // End returns the offset of the first byte immediately after this field.
   468  func (f *Field) End() int64 {
   469  	return f.Offset + f.Type.width
   470  }
   471  
   472  // IsMethod reports whether f represents a method rather than a struct field.
   473  func (f *Field) IsMethod() bool {
   474  	return f.Type.kind == TFUNC && f.Type.Recv() != nil
   475  }
   476  
   477  // fields is a pointer to a slice of *Field.
   478  // This saves space in Types that do not have fields or methods
   479  // compared to a simple slice of *Field.
   480  type fields struct {
   481  	s *[]*Field
   482  }
   483  
   484  // Slice returns the entries in f as a slice.
   485  // Changes to the slice entries will be reflected in f.
   486  func (f *fields) Slice() []*Field {
   487  	if f.s == nil {
   488  		return nil
   489  	}
   490  	return *f.s
   491  }
   492  
   493  // Set sets f to a slice.
   494  // This takes ownership of the slice.
   495  func (f *fields) Set(s []*Field) {
   496  	if len(s) == 0 {
   497  		f.s = nil
   498  	} else {
   499  		// Copy s and take address of t rather than s to avoid
   500  		// allocation in the case where len(s) == 0.
   501  		t := s
   502  		f.s = &t
   503  	}
   504  }
   505  
   506  // newType returns a new Type of the specified kind.
   507  func newType(et Kind) *Type {
   508  	t := &Type{
   509  		kind:  et,
   510  		width: BADWIDTH,
   511  	}
   512  	t.underlying = t
   513  	// TODO(josharian): lazily initialize some of these?
   514  	switch t.kind {
   515  	case TMAP:
   516  		t.extra = new(Map)
   517  	case TFORW:
   518  		t.extra = new(Forward)
   519  	case TFUNC:
   520  		t.extra = new(Func)
   521  	case TSTRUCT:
   522  		t.extra = new(Struct)
   523  	case TINTER:
   524  		t.extra = new(Interface)
   525  	case TPTR:
   526  		t.extra = Ptr{}
   527  	case TCHANARGS:
   528  		t.extra = ChanArgs{}
   529  	case TFUNCARGS:
   530  		t.extra = FuncArgs{}
   531  	case TCHAN:
   532  		t.extra = new(Chan)
   533  	case TTUPLE:
   534  		t.extra = new(Tuple)
   535  	case TRESULTS:
   536  		t.extra = new(Results)
   537  	}
   538  	return t
   539  }
   540  
   541  // NewArray returns a new fixed-length array Type.
   542  func NewArray(elem *Type, bound int64) *Type {
   543  	if bound < 0 {
   544  		base.Fatalf("NewArray: invalid bound %v", bound)
   545  	}
   546  	t := newType(TARRAY)
   547  	t.extra = &Array{Elem: elem, Bound: bound}
   548  	if elem.HasShape() {
   549  		t.SetHasShape(true)
   550  	}
   551  	return t
   552  }
   553  
   554  // NewSlice returns the slice Type with element type elem.
   555  func NewSlice(elem *Type) *Type {
   556  	if t := elem.cache.slice; t != nil {
   557  		if t.Elem() != elem {
   558  			base.Fatalf("elem mismatch")
   559  		}
   560  		if elem.HasShape() != t.HasShape() {
   561  			base.Fatalf("Incorrect HasShape flag for cached slice type")
   562  		}
   563  		return t
   564  	}
   565  
   566  	t := newType(TSLICE)
   567  	t.extra = Slice{Elem: elem}
   568  	elem.cache.slice = t
   569  	if elem.HasShape() {
   570  		t.SetHasShape(true)
   571  	}
   572  	return t
   573  }
   574  
   575  // NewChan returns a new chan Type with direction dir.
   576  func NewChan(elem *Type, dir ChanDir) *Type {
   577  	t := newType(TCHAN)
   578  	ct := t.chanType()
   579  	ct.Elem = elem
   580  	ct.Dir = dir
   581  	if elem.HasShape() {
   582  		t.SetHasShape(true)
   583  	}
   584  	return t
   585  }
   586  
   587  func NewTuple(t1, t2 *Type) *Type {
   588  	t := newType(TTUPLE)
   589  	t.extra.(*Tuple).first = t1
   590  	t.extra.(*Tuple).second = t2
   591  	if t1.HasShape() || t2.HasShape() {
   592  		t.SetHasShape(true)
   593  	}
   594  	return t
   595  }
   596  
   597  func newResults(types []*Type) *Type {
   598  	t := newType(TRESULTS)
   599  	t.extra.(*Results).Types = types
   600  	return t
   601  }
   602  
   603  func NewResults(types []*Type) *Type {
   604  	if len(types) == 1 && types[0] == TypeMem {
   605  		return TypeResultMem
   606  	}
   607  	return newResults(types)
   608  }
   609  
   610  func newSSA(name string) *Type {
   611  	t := newType(TSSA)
   612  	t.extra = name
   613  	return t
   614  }
   615  
   616  // NewMap returns a new map Type with key type k and element (aka value) type v.
   617  func NewMap(k, v *Type) *Type {
   618  	t := newType(TMAP)
   619  	mt := t.MapType()
   620  	mt.Key = k
   621  	mt.Elem = v
   622  	if k.HasShape() || v.HasShape() {
   623  		t.SetHasShape(true)
   624  	}
   625  	return t
   626  }
   627  
   628  // NewPtrCacheEnabled controls whether *T Types are cached in T.
   629  // Caching is disabled just before starting the backend.
   630  // This allows the backend to run concurrently.
   631  var NewPtrCacheEnabled = true
   632  
   633  // NewPtr returns the pointer type pointing to t.
   634  func NewPtr(elem *Type) *Type {
   635  	if elem == nil {
   636  		base.Fatalf("NewPtr: pointer to elem Type is nil")
   637  	}
   638  
   639  	if t := elem.cache.ptr; t != nil {
   640  		if t.Elem() != elem {
   641  			base.Fatalf("NewPtr: elem mismatch")
   642  		}
   643  		if elem.HasShape() != t.HasShape() {
   644  			base.Fatalf("Incorrect HasShape flag for cached pointer type")
   645  		}
   646  		return t
   647  	}
   648  
   649  	t := newType(TPTR)
   650  	t.extra = Ptr{Elem: elem}
   651  	t.width = int64(PtrSize)
   652  	t.align = uint8(PtrSize)
   653  	t.intRegs = 1
   654  	if NewPtrCacheEnabled {
   655  		elem.cache.ptr = t
   656  	}
   657  	if elem.HasShape() {
   658  		t.SetHasShape(true)
   659  	}
   660  	return t
   661  }
   662  
   663  // NewChanArgs returns a new TCHANARGS type for channel type c.
   664  func NewChanArgs(c *Type) *Type {
   665  	t := newType(TCHANARGS)
   666  	t.extra = ChanArgs{T: c}
   667  	return t
   668  }
   669  
   670  // NewFuncArgs returns a new TFUNCARGS type for func type f.
   671  func NewFuncArgs(f *Type) *Type {
   672  	t := newType(TFUNCARGS)
   673  	t.extra = FuncArgs{T: f}
   674  	return t
   675  }
   676  
   677  func NewField(pos src.XPos, sym *Sym, typ *Type) *Field {
   678  	f := &Field{
   679  		Pos:    pos,
   680  		Sym:    sym,
   681  		Type:   typ,
   682  		Offset: BADWIDTH,
   683  	}
   684  	if typ == nil {
   685  		base.Fatalf("typ is nil")
   686  	}
   687  	return f
   688  }
   689  
   690  // SubstAny walks t, replacing instances of "any" with successive
   691  // elements removed from types.  It returns the substituted type.
   692  func SubstAny(t *Type, types *[]*Type) *Type {
   693  	if t == nil {
   694  		return nil
   695  	}
   696  
   697  	switch t.kind {
   698  	default:
   699  		// Leave the type unchanged.
   700  
   701  	case TANY:
   702  		if len(*types) == 0 {
   703  			base.Fatalf("SubstArgTypes: not enough argument types")
   704  		}
   705  		t = (*types)[0]
   706  		*types = (*types)[1:]
   707  
   708  	case TPTR:
   709  		elem := SubstAny(t.Elem(), types)
   710  		if elem != t.Elem() {
   711  			t = t.copy()
   712  			t.extra = Ptr{Elem: elem}
   713  		}
   714  
   715  	case TARRAY:
   716  		elem := SubstAny(t.Elem(), types)
   717  		if elem != t.Elem() {
   718  			t = t.copy()
   719  			t.extra.(*Array).Elem = elem
   720  		}
   721  
   722  	case TSLICE:
   723  		elem := SubstAny(t.Elem(), types)
   724  		if elem != t.Elem() {
   725  			t = t.copy()
   726  			t.extra = Slice{Elem: elem}
   727  		}
   728  
   729  	case TCHAN:
   730  		elem := SubstAny(t.Elem(), types)
   731  		if elem != t.Elem() {
   732  			t = t.copy()
   733  			t.extra.(*Chan).Elem = elem
   734  		}
   735  
   736  	case TMAP:
   737  		key := SubstAny(t.Key(), types)
   738  		elem := SubstAny(t.Elem(), types)
   739  		if key != t.Key() || elem != t.Elem() {
   740  			t = t.copy()
   741  			t.extra.(*Map).Key = key
   742  			t.extra.(*Map).Elem = elem
   743  		}
   744  
   745  	case TFUNC:
   746  		ft := t.funcType()
   747  		allParams := substFields(ft.allParams, types)
   748  
   749  		t = t.copy()
   750  		ft = t.funcType()
   751  		ft.allParams = allParams
   752  
   753  		rt := ft.resultsTuple
   754  		rt = rt.copy()
   755  		ft.resultsTuple = rt
   756  		rt.setFields(t.Results())
   757  
   758  	case TSTRUCT:
   759  		// Make a copy of all fields, including ones whose type does not change.
   760  		// This prevents aliasing across functions, which can lead to later
   761  		// fields getting their Offset incorrectly overwritten.
   762  		nfs := substFields(t.Fields(), types)
   763  		t = t.copy()
   764  		t.setFields(nfs)
   765  	}
   766  
   767  	return t
   768  }
   769  
   770  func substFields(fields []*Field, types *[]*Type) []*Field {
   771  	nfs := make([]*Field, len(fields))
   772  	for i, f := range fields {
   773  		nft := SubstAny(f.Type, types)
   774  		nfs[i] = f.Copy()
   775  		nfs[i].Type = nft
   776  	}
   777  	return nfs
   778  }
   779  
   780  // copy returns a shallow copy of the Type.
   781  func (t *Type) copy() *Type {
   782  	if t == nil {
   783  		return nil
   784  	}
   785  	nt := *t
   786  	// copy any *T Extra fields, to avoid aliasing
   787  	switch t.kind {
   788  	case TMAP:
   789  		x := *t.extra.(*Map)
   790  		nt.extra = &x
   791  	case TFORW:
   792  		x := *t.extra.(*Forward)
   793  		nt.extra = &x
   794  	case TFUNC:
   795  		x := *t.extra.(*Func)
   796  		nt.extra = &x
   797  	case TSTRUCT:
   798  		x := *t.extra.(*Struct)
   799  		nt.extra = &x
   800  	case TINTER:
   801  		x := *t.extra.(*Interface)
   802  		nt.extra = &x
   803  	case TCHAN:
   804  		x := *t.extra.(*Chan)
   805  		nt.extra = &x
   806  	case TARRAY:
   807  		x := *t.extra.(*Array)
   808  		nt.extra = &x
   809  	case TTUPLE, TSSA, TRESULTS:
   810  		base.Fatalf("ssa types cannot be copied")
   811  	}
   812  	// TODO(mdempsky): Find out why this is necessary and explain.
   813  	if t.underlying == t {
   814  		nt.underlying = &nt
   815  	}
   816  	return &nt
   817  }
   818  
   819  func (f *Field) Copy() *Field {
   820  	nf := *f
   821  	return &nf
   822  }
   823  
   824  func (t *Type) wantEtype(et Kind) {
   825  	if t.kind != et {
   826  		base.Fatalf("want %v, but have %v", et, t)
   827  	}
   828  }
   829  
   830  // ResultTuple returns the result type of signature type t as a tuple.
   831  // This can be used as the type of multi-valued call expressions.
   832  func (t *Type) ResultsTuple() *Type { return t.funcType().resultsTuple }
   833  
   834  // Recvs returns a slice of receiver parameters of signature type t.
   835  // The returned slice always has length 0 or 1.
   836  func (t *Type) Recvs() []*Field { return t.funcType().recvs() }
   837  
   838  // Params returns a slice of regular parameters of signature type t.
   839  func (t *Type) Params() []*Field { return t.funcType().params() }
   840  
   841  // Results returns a slice of result parameters of signature type t.
   842  func (t *Type) Results() []*Field { return t.funcType().results() }
   843  
   844  // RecvsParamsResults returns a slice containing all of the
   845  // signature's parameters in receiver (if any), (normal) parameters,
   846  // and then results.
   847  func (t *Type) RecvParamsResults() []*Field { return t.funcType().allParams }
   848  
   849  // RecvParams returns a slice containing the signature's receiver (if
   850  // any) followed by its (normal) parameters.
   851  func (t *Type) RecvParams() []*Field { return t.funcType().recvParams() }
   852  
   853  // ParamsResults returns a slice containing the signature's (normal)
   854  // parameters followed by its results.
   855  func (t *Type) ParamsResults() []*Field { return t.funcType().paramsResults() }
   856  
   857  func (t *Type) NumRecvs() int   { return len(t.Recvs()) }
   858  func (t *Type) NumParams() int  { return len(t.Params()) }
   859  func (t *Type) NumResults() int { return len(t.Results()) }
   860  
   861  // IsVariadic reports whether function type t is variadic.
   862  func (t *Type) IsVariadic() bool {
   863  	n := t.NumParams()
   864  	return n > 0 && t.Param(n-1).IsDDD()
   865  }
   866  
   867  // Recv returns the receiver of function type t, if any.
   868  func (t *Type) Recv() *Field {
   869  	if s := t.Recvs(); len(s) == 1 {
   870  		return s[0]
   871  	}
   872  	return nil
   873  }
   874  
   875  // Param returns the i'th parameter of signature type t.
   876  func (t *Type) Param(i int) *Field { return t.Params()[i] }
   877  
   878  // Result returns the i'th result of signature type t.
   879  func (t *Type) Result(i int) *Field { return t.Results()[i] }
   880  
   881  // Key returns the key type of map type t.
   882  func (t *Type) Key() *Type {
   883  	t.wantEtype(TMAP)
   884  	return t.extra.(*Map).Key
   885  }
   886  
   887  // Elem returns the type of elements of t.
   888  // Usable with pointers, channels, arrays, slices, and maps.
   889  func (t *Type) Elem() *Type {
   890  	switch t.kind {
   891  	case TPTR:
   892  		return t.extra.(Ptr).Elem
   893  	case TARRAY:
   894  		return t.extra.(*Array).Elem
   895  	case TSLICE:
   896  		return t.extra.(Slice).Elem
   897  	case TCHAN:
   898  		return t.extra.(*Chan).Elem
   899  	case TMAP:
   900  		return t.extra.(*Map).Elem
   901  	}
   902  	base.Fatalf("Type.Elem %s", t.kind)
   903  	return nil
   904  }
   905  
   906  // ChanArgs returns the channel type for TCHANARGS type t.
   907  func (t *Type) ChanArgs() *Type {
   908  	t.wantEtype(TCHANARGS)
   909  	return t.extra.(ChanArgs).T
   910  }
   911  
   912  // FuncArgs returns the func type for TFUNCARGS type t.
   913  func (t *Type) FuncArgs() *Type {
   914  	t.wantEtype(TFUNCARGS)
   915  	return t.extra.(FuncArgs).T
   916  }
   917  
   918  // IsFuncArgStruct reports whether t is a struct representing function parameters or results.
   919  func (t *Type) IsFuncArgStruct() bool {
   920  	return t.kind == TSTRUCT && t.extra.(*Struct).ParamTuple
   921  }
   922  
   923  // Methods returns a pointer to the base methods (excluding embedding) for type t.
   924  // These can either be concrete methods (for non-interface types) or interface
   925  // methods (for interface types).
   926  func (t *Type) Methods() []*Field {
   927  	return t.methods.Slice()
   928  }
   929  
   930  // AllMethods returns a pointer to all the methods (including embedding) for type t.
   931  // For an interface type, this is the set of methods that are typically iterated
   932  // over. For non-interface types, AllMethods() only returns a valid result after
   933  // CalcMethods() has been called at least once.
   934  func (t *Type) AllMethods() []*Field {
   935  	if t.kind == TINTER {
   936  		// Calculate the full method set of an interface type on the fly
   937  		// now, if not done yet.
   938  		CalcSize(t)
   939  	}
   940  	return t.allMethods.Slice()
   941  }
   942  
   943  // SetMethods sets the direct method set for type t (i.e., *not*
   944  // including promoted methods from embedded types).
   945  func (t *Type) SetMethods(fs []*Field) {
   946  	t.methods.Set(fs)
   947  }
   948  
   949  // SetAllMethods sets the set of all methods for type t (i.e.,
   950  // including promoted methods from embedded types).
   951  func (t *Type) SetAllMethods(fs []*Field) {
   952  	t.allMethods.Set(fs)
   953  }
   954  
   955  // fields returns the fields of struct type t.
   956  func (t *Type) fields() *fields {
   957  	t.wantEtype(TSTRUCT)
   958  	return &t.extra.(*Struct).fields
   959  }
   960  
   961  // Field returns the i'th field of struct type t.
   962  func (t *Type) Field(i int) *Field { return t.Fields()[i] }
   963  
   964  // Fields returns a slice of containing all fields of
   965  // a struct type t.
   966  func (t *Type) Fields() []*Field { return t.fields().Slice() }
   967  
   968  // setFields sets struct type t's fields to fields.
   969  func (t *Type) setFields(fields []*Field) {
   970  	// If we've calculated the width of t before,
   971  	// then some other type such as a function signature
   972  	// might now have the wrong type.
   973  	// Rather than try to track and invalidate those,
   974  	// enforce that SetFields cannot be called once
   975  	// t's width has been calculated.
   976  	if t.widthCalculated() {
   977  		base.Fatalf("SetFields of %v: width previously calculated", t)
   978  	}
   979  	t.wantEtype(TSTRUCT)
   980  	t.fields().Set(fields)
   981  }
   982  
   983  // SetInterface sets the base methods of an interface type t.
   984  func (t *Type) SetInterface(methods []*Field) {
   985  	t.wantEtype(TINTER)
   986  	t.methods.Set(methods)
   987  }
   988  
   989  // ArgWidth returns the total aligned argument size for a function.
   990  // It includes the receiver, parameters, and results.
   991  func (t *Type) ArgWidth() int64 {
   992  	t.wantEtype(TFUNC)
   993  	return t.extra.(*Func).Argwid
   994  }
   995  
   996  func (t *Type) Size() int64 {
   997  	if t.kind == TSSA {
   998  		if t == TypeInt128 {
   999  			return 16
  1000  		}
  1001  		return 0
  1002  	}
  1003  	CalcSize(t)
  1004  	return t.width
  1005  }
  1006  
  1007  func (t *Type) Alignment() int64 {
  1008  	CalcSize(t)
  1009  	return int64(t.align)
  1010  }
  1011  
  1012  func (t *Type) SimpleString() string {
  1013  	return t.kind.String()
  1014  }
  1015  
  1016  // Cmp is a comparison between values a and b.
  1017  //
  1018  //	-1 if a < b
  1019  //	 0 if a == b
  1020  //	 1 if a > b
  1021  type Cmp int8
  1022  
  1023  const (
  1024  	CMPlt = Cmp(-1)
  1025  	CMPeq = Cmp(0)
  1026  	CMPgt = Cmp(1)
  1027  )
  1028  
  1029  // Compare compares types for purposes of the SSA back
  1030  // end, returning a Cmp (one of CMPlt, CMPeq, CMPgt).
  1031  // The answers are correct for an optimizer
  1032  // or code generator, but not necessarily typechecking.
  1033  // The order chosen is arbitrary, only consistency and division
  1034  // into equivalence classes (Types that compare CMPeq) matters.
  1035  func (t *Type) Compare(x *Type) Cmp {
  1036  	if x == t {
  1037  		return CMPeq
  1038  	}
  1039  	return t.cmp(x)
  1040  }
  1041  
  1042  func cmpForNe(x bool) Cmp {
  1043  	if x {
  1044  		return CMPlt
  1045  	}
  1046  	return CMPgt
  1047  }
  1048  
  1049  func (r *Sym) cmpsym(s *Sym) Cmp {
  1050  	if r == s {
  1051  		return CMPeq
  1052  	}
  1053  	if r == nil {
  1054  		return CMPlt
  1055  	}
  1056  	if s == nil {
  1057  		return CMPgt
  1058  	}
  1059  	// Fast sort, not pretty sort
  1060  	if len(r.Name) != len(s.Name) {
  1061  		return cmpForNe(len(r.Name) < len(s.Name))
  1062  	}
  1063  	if r.Pkg != s.Pkg {
  1064  		if len(r.Pkg.Prefix) != len(s.Pkg.Prefix) {
  1065  			return cmpForNe(len(r.Pkg.Prefix) < len(s.Pkg.Prefix))
  1066  		}
  1067  		if r.Pkg.Prefix != s.Pkg.Prefix {
  1068  			return cmpForNe(r.Pkg.Prefix < s.Pkg.Prefix)
  1069  		}
  1070  	}
  1071  	if r.Name != s.Name {
  1072  		return cmpForNe(r.Name < s.Name)
  1073  	}
  1074  	return CMPeq
  1075  }
  1076  
  1077  // cmp compares two *Types t and x, returning CMPlt,
  1078  // CMPeq, CMPgt as t<x, t==x, t>x, for an arbitrary
  1079  // and optimizer-centric notion of comparison.
  1080  // TODO(josharian): make this safe for recursive interface types
  1081  // and use in signatlist sorting. See issue 19869.
  1082  func (t *Type) cmp(x *Type) Cmp {
  1083  	// This follows the structure of function identical in identity.go
  1084  	// with two exceptions.
  1085  	// 1. Symbols are compared more carefully because a <,=,> result is desired.
  1086  	// 2. Maps are treated specially to avoid endless recursion -- maps
  1087  	//    contain an internal data type not expressible in Go source code.
  1088  	if t == x {
  1089  		return CMPeq
  1090  	}
  1091  	if t == nil {
  1092  		return CMPlt
  1093  	}
  1094  	if x == nil {
  1095  		return CMPgt
  1096  	}
  1097  
  1098  	if t.kind != x.kind {
  1099  		return cmpForNe(t.kind < x.kind)
  1100  	}
  1101  
  1102  	if t.obj != nil || x.obj != nil {
  1103  		// Special case: we keep byte and uint8 separate
  1104  		// for error messages. Treat them as equal.
  1105  		switch t.kind {
  1106  		case TUINT8:
  1107  			if (t == Types[TUINT8] || t == ByteType) && (x == Types[TUINT8] || x == ByteType) {
  1108  				return CMPeq
  1109  			}
  1110  
  1111  		case TINT32:
  1112  			if (t == Types[RuneType.kind] || t == RuneType) && (x == Types[RuneType.kind] || x == RuneType) {
  1113  				return CMPeq
  1114  			}
  1115  
  1116  		case TINTER:
  1117  			// Make sure named any type matches any empty interface.
  1118  			if t == AnyType && x.IsEmptyInterface() || x == AnyType && t.IsEmptyInterface() {
  1119  				return CMPeq
  1120  			}
  1121  		}
  1122  	}
  1123  
  1124  	if c := t.Sym().cmpsym(x.Sym()); c != CMPeq {
  1125  		return c
  1126  	}
  1127  
  1128  	if x.obj != nil {
  1129  		return CMPeq
  1130  	}
  1131  	// both syms nil, look at structure below.
  1132  
  1133  	switch t.kind {
  1134  	case TBOOL, TFLOAT32, TFLOAT64, TCOMPLEX64, TCOMPLEX128, TUNSAFEPTR, TUINTPTR,
  1135  		TINT8, TINT16, TINT32, TINT64, TINT, TUINT8, TUINT16, TUINT32, TUINT64, TUINT:
  1136  		return CMPeq
  1137  
  1138  	case TSSA:
  1139  		tname := t.extra.(string)
  1140  		xname := x.extra.(string)
  1141  		// desire fast sorting, not pretty sorting.
  1142  		if len(tname) == len(xname) {
  1143  			if tname == xname {
  1144  				return CMPeq
  1145  			}
  1146  			if tname < xname {
  1147  				return CMPlt
  1148  			}
  1149  			return CMPgt
  1150  		}
  1151  		if len(tname) > len(xname) {
  1152  			return CMPgt
  1153  		}
  1154  		return CMPlt
  1155  
  1156  	case TTUPLE:
  1157  		xtup := x.extra.(*Tuple)
  1158  		ttup := t.extra.(*Tuple)
  1159  		if c := ttup.first.Compare(xtup.first); c != CMPeq {
  1160  			return c
  1161  		}
  1162  		return ttup.second.Compare(xtup.second)
  1163  
  1164  	case TRESULTS:
  1165  		xResults := x.extra.(*Results)
  1166  		tResults := t.extra.(*Results)
  1167  		xl, tl := len(xResults.Types), len(tResults.Types)
  1168  		if tl != xl {
  1169  			if tl < xl {
  1170  				return CMPlt
  1171  			}
  1172  			return CMPgt
  1173  		}
  1174  		for i := 0; i < tl; i++ {
  1175  			if c := tResults.Types[i].Compare(xResults.Types[i]); c != CMPeq {
  1176  				return c
  1177  			}
  1178  		}
  1179  		return CMPeq
  1180  
  1181  	case TMAP:
  1182  		if c := t.Key().cmp(x.Key()); c != CMPeq {
  1183  			return c
  1184  		}
  1185  		return t.Elem().cmp(x.Elem())
  1186  
  1187  	case TPTR, TSLICE:
  1188  		// No special cases for these, they are handled
  1189  		// by the general code after the switch.
  1190  
  1191  	case TSTRUCT:
  1192  		if t.StructType().Map == nil {
  1193  			if x.StructType().Map != nil {
  1194  				return CMPlt // nil < non-nil
  1195  			}
  1196  			// to the fallthrough
  1197  		} else if x.StructType().Map == nil {
  1198  			return CMPgt // nil > non-nil
  1199  		} else if t.StructType().Map.MapType().Bucket == t {
  1200  			// Both have non-nil Map
  1201  			// Special case for Maps which include a recursive type where the recursion is not broken with a named type
  1202  			if x.StructType().Map.MapType().Bucket != x {
  1203  				return CMPlt // bucket maps are least
  1204  			}
  1205  			return t.StructType().Map.cmp(x.StructType().Map)
  1206  		} else if x.StructType().Map.MapType().Bucket == x {
  1207  			return CMPgt // bucket maps are least
  1208  		} // If t != t.Map.Bucket, fall through to general case
  1209  
  1210  		tfs := t.Fields()
  1211  		xfs := x.Fields()
  1212  		for i := 0; i < len(tfs) && i < len(xfs); i++ {
  1213  			t1, x1 := tfs[i], xfs[i]
  1214  			if t1.Embedded != x1.Embedded {
  1215  				return cmpForNe(t1.Embedded < x1.Embedded)
  1216  			}
  1217  			if t1.Note != x1.Note {
  1218  				return cmpForNe(t1.Note < x1.Note)
  1219  			}
  1220  			if c := t1.Sym.cmpsym(x1.Sym); c != CMPeq {
  1221  				return c
  1222  			}
  1223  			if c := t1.Type.cmp(x1.Type); c != CMPeq {
  1224  				return c
  1225  			}
  1226  		}
  1227  		if len(tfs) != len(xfs) {
  1228  			return cmpForNe(len(tfs) < len(xfs))
  1229  		}
  1230  		return CMPeq
  1231  
  1232  	case TINTER:
  1233  		tfs := t.AllMethods()
  1234  		xfs := x.AllMethods()
  1235  		for i := 0; i < len(tfs) && i < len(xfs); i++ {
  1236  			t1, x1 := tfs[i], xfs[i]
  1237  			if c := t1.Sym.cmpsym(x1.Sym); c != CMPeq {
  1238  				return c
  1239  			}
  1240  			if c := t1.Type.cmp(x1.Type); c != CMPeq {
  1241  				return c
  1242  			}
  1243  		}
  1244  		if len(tfs) != len(xfs) {
  1245  			return cmpForNe(len(tfs) < len(xfs))
  1246  		}
  1247  		return CMPeq
  1248  
  1249  	case TFUNC:
  1250  		if tn, xn := t.NumRecvs(), x.NumRecvs(); tn != xn {
  1251  			return cmpForNe(tn < xn)
  1252  		}
  1253  		if tn, xn := t.NumParams(), x.NumParams(); tn != xn {
  1254  			return cmpForNe(tn < xn)
  1255  		}
  1256  		if tn, xn := t.NumResults(), x.NumResults(); tn != xn {
  1257  			return cmpForNe(tn < xn)
  1258  		}
  1259  		if tv, xv := t.IsVariadic(), x.IsVariadic(); tv != xv {
  1260  			return cmpForNe(!tv)
  1261  		}
  1262  
  1263  		tfs := t.RecvParamsResults()
  1264  		xfs := x.RecvParamsResults()
  1265  		for i, tf := range tfs {
  1266  			if c := tf.Type.cmp(xfs[i].Type); c != CMPeq {
  1267  				return c
  1268  			}
  1269  		}
  1270  		return CMPeq
  1271  
  1272  	case TARRAY:
  1273  		if t.NumElem() != x.NumElem() {
  1274  			return cmpForNe(t.NumElem() < x.NumElem())
  1275  		}
  1276  
  1277  	case TCHAN:
  1278  		if t.ChanDir() != x.ChanDir() {
  1279  			return cmpForNe(t.ChanDir() < x.ChanDir())
  1280  		}
  1281  
  1282  	default:
  1283  		e := fmt.Sprintf("Do not know how to compare %v with %v", t, x)
  1284  		panic(e)
  1285  	}
  1286  
  1287  	// Common element type comparison for TARRAY, TCHAN, TPTR, and TSLICE.
  1288  	return t.Elem().cmp(x.Elem())
  1289  }
  1290  
  1291  // IsKind reports whether t is a Type of the specified kind.
  1292  func (t *Type) IsKind(et Kind) bool {
  1293  	return t != nil && t.kind == et
  1294  }
  1295  
  1296  func (t *Type) IsBoolean() bool {
  1297  	return t.kind == TBOOL
  1298  }
  1299  
  1300  var unsignedEType = [...]Kind{
  1301  	TINT8:    TUINT8,
  1302  	TUINT8:   TUINT8,
  1303  	TINT16:   TUINT16,
  1304  	TUINT16:  TUINT16,
  1305  	TINT32:   TUINT32,
  1306  	TUINT32:  TUINT32,
  1307  	TINT64:   TUINT64,
  1308  	TUINT64:  TUINT64,
  1309  	TINT:     TUINT,
  1310  	TUINT:    TUINT,
  1311  	TUINTPTR: TUINTPTR,
  1312  }
  1313  
  1314  // ToUnsigned returns the unsigned equivalent of integer type t.
  1315  func (t *Type) ToUnsigned() *Type {
  1316  	if !t.IsInteger() {
  1317  		base.Fatalf("unsignedType(%v)", t)
  1318  	}
  1319  	return Types[unsignedEType[t.kind]]
  1320  }
  1321  
  1322  func (t *Type) IsInteger() bool {
  1323  	switch t.kind {
  1324  	case TINT8, TUINT8, TINT16, TUINT16, TINT32, TUINT32, TINT64, TUINT64, TINT, TUINT, TUINTPTR:
  1325  		return true
  1326  	}
  1327  	return t == UntypedInt || t == UntypedRune
  1328  }
  1329  
  1330  func (t *Type) IsSigned() bool {
  1331  	switch t.kind {
  1332  	case TINT8, TINT16, TINT32, TINT64, TINT:
  1333  		return true
  1334  	}
  1335  	return false
  1336  }
  1337  
  1338  func (t *Type) IsUnsigned() bool {
  1339  	switch t.kind {
  1340  	case TUINT8, TUINT16, TUINT32, TUINT64, TUINT, TUINTPTR:
  1341  		return true
  1342  	}
  1343  	return false
  1344  }
  1345  
  1346  func (t *Type) IsFloat() bool {
  1347  	return t.kind == TFLOAT32 || t.kind == TFLOAT64 || t == UntypedFloat
  1348  }
  1349  
  1350  func (t *Type) IsComplex() bool {
  1351  	return t.kind == TCOMPLEX64 || t.kind == TCOMPLEX128 || t == UntypedComplex
  1352  }
  1353  
  1354  // IsPtr reports whether t is a regular Go pointer type.
  1355  // This does not include unsafe.Pointer.
  1356  func (t *Type) IsPtr() bool {
  1357  	return t.kind == TPTR
  1358  }
  1359  
  1360  // IsPtrElem reports whether t is the element of a pointer (to t).
  1361  func (t *Type) IsPtrElem() bool {
  1362  	return t.cache.ptr != nil
  1363  }
  1364  
  1365  // IsUnsafePtr reports whether t is an unsafe pointer.
  1366  func (t *Type) IsUnsafePtr() bool {
  1367  	return t.kind == TUNSAFEPTR
  1368  }
  1369  
  1370  // IsUintptr reports whether t is a uintptr.
  1371  func (t *Type) IsUintptr() bool {
  1372  	return t.kind == TUINTPTR
  1373  }
  1374  
  1375  // IsPtrShaped reports whether t is represented by a single machine pointer.
  1376  // In addition to regular Go pointer types, this includes map, channel, and
  1377  // function types and unsafe.Pointer. It does not include array or struct types
  1378  // that consist of a single pointer shaped type.
  1379  // TODO(mdempsky): Should it? See golang.org/issue/15028.
  1380  func (t *Type) IsPtrShaped() bool {
  1381  	return t.kind == TPTR || t.kind == TUNSAFEPTR ||
  1382  		t.kind == TMAP || t.kind == TCHAN || t.kind == TFUNC
  1383  }
  1384  
  1385  // HasNil reports whether the set of values determined by t includes nil.
  1386  func (t *Type) HasNil() bool {
  1387  	switch t.kind {
  1388  	case TCHAN, TFUNC, TINTER, TMAP, TNIL, TPTR, TSLICE, TUNSAFEPTR:
  1389  		return true
  1390  	}
  1391  	return false
  1392  }
  1393  
  1394  func (t *Type) IsString() bool {
  1395  	return t.kind == TSTRING
  1396  }
  1397  
  1398  func (t *Type) IsMap() bool {
  1399  	return t.kind == TMAP
  1400  }
  1401  
  1402  func (t *Type) IsChan() bool {
  1403  	return t.kind == TCHAN
  1404  }
  1405  
  1406  func (t *Type) IsSlice() bool {
  1407  	return t.kind == TSLICE
  1408  }
  1409  
  1410  func (t *Type) IsArray() bool {
  1411  	return t.kind == TARRAY
  1412  }
  1413  
  1414  func (t *Type) IsStruct() bool {
  1415  	return t.kind == TSTRUCT
  1416  }
  1417  
  1418  func (t *Type) IsInterface() bool {
  1419  	return t.kind == TINTER
  1420  }
  1421  
  1422  // IsEmptyInterface reports whether t is an empty interface type.
  1423  func (t *Type) IsEmptyInterface() bool {
  1424  	return t.IsInterface() && len(t.AllMethods()) == 0
  1425  }
  1426  
  1427  // IsScalar reports whether 't' is a scalar Go type, e.g.
  1428  // bool/int/float/complex. Note that struct and array types consisting
  1429  // of a single scalar element are not considered scalar, likewise
  1430  // pointer types are also not considered scalar.
  1431  func (t *Type) IsScalar() bool {
  1432  	switch t.kind {
  1433  	case TBOOL, TINT8, TUINT8, TINT16, TUINT16, TINT32,
  1434  		TUINT32, TINT64, TUINT64, TINT, TUINT,
  1435  		TUINTPTR, TCOMPLEX64, TCOMPLEX128, TFLOAT32, TFLOAT64:
  1436  		return true
  1437  	}
  1438  	return false
  1439  }
  1440  
  1441  func (t *Type) PtrTo() *Type {
  1442  	return NewPtr(t)
  1443  }
  1444  
  1445  func (t *Type) NumFields() int {
  1446  	if t.kind == TRESULTS {
  1447  		return len(t.extra.(*Results).Types)
  1448  	}
  1449  	return len(t.Fields())
  1450  }
  1451  func (t *Type) FieldType(i int) *Type {
  1452  	if t.kind == TTUPLE {
  1453  		switch i {
  1454  		case 0:
  1455  			return t.extra.(*Tuple).first
  1456  		case 1:
  1457  			return t.extra.(*Tuple).second
  1458  		default:
  1459  			panic("bad tuple index")
  1460  		}
  1461  	}
  1462  	if t.kind == TRESULTS {
  1463  		return t.extra.(*Results).Types[i]
  1464  	}
  1465  	return t.Field(i).Type
  1466  }
  1467  func (t *Type) FieldOff(i int) int64 {
  1468  	return t.Field(i).Offset
  1469  }
  1470  func (t *Type) FieldName(i int) string {
  1471  	return t.Field(i).Sym.Name
  1472  }
  1473  
  1474  // OffsetOf reports the offset of the field of a struct.
  1475  // The field is looked up by name.
  1476  func (t *Type) OffsetOf(name string) int64 {
  1477  	if t.kind != TSTRUCT {
  1478  		base.Fatalf("can't call OffsetOf on non-struct %v", t)
  1479  	}
  1480  	for _, f := range t.Fields() {
  1481  		if f.Sym.Name == name {
  1482  			return f.Offset
  1483  		}
  1484  	}
  1485  	base.Fatalf("couldn't find field %s in %v", name, t)
  1486  	return -1
  1487  }
  1488  
  1489  func (t *Type) NumElem() int64 {
  1490  	t.wantEtype(TARRAY)
  1491  	return t.extra.(*Array).Bound
  1492  }
  1493  
  1494  type componentsIncludeBlankFields bool
  1495  
  1496  const (
  1497  	IgnoreBlankFields componentsIncludeBlankFields = false
  1498  	CountBlankFields  componentsIncludeBlankFields = true
  1499  )
  1500  
  1501  // NumComponents returns the number of primitive elements that compose t.
  1502  // Struct and array types are flattened for the purpose of counting.
  1503  // All other types (including string, slice, and interface types) count as one element.
  1504  // If countBlank is IgnoreBlankFields, then blank struct fields
  1505  // (and their comprised elements) are excluded from the count.
  1506  // struct { x, y [3]int } has six components; [10]struct{ x, y string } has twenty.
  1507  func (t *Type) NumComponents(countBlank componentsIncludeBlankFields) int64 {
  1508  	switch t.kind {
  1509  	case TSTRUCT:
  1510  		if t.IsFuncArgStruct() {
  1511  			base.Fatalf("NumComponents func arg struct")
  1512  		}
  1513  		var n int64
  1514  		for _, f := range t.Fields() {
  1515  			if countBlank == IgnoreBlankFields && f.Sym.IsBlank() {
  1516  				continue
  1517  			}
  1518  			n += f.Type.NumComponents(countBlank)
  1519  		}
  1520  		return n
  1521  	case TARRAY:
  1522  		return t.NumElem() * t.Elem().NumComponents(countBlank)
  1523  	}
  1524  	return 1
  1525  }
  1526  
  1527  // SoleComponent returns the only primitive component in t,
  1528  // if there is exactly one. Otherwise, it returns nil.
  1529  // Components are counted as in NumComponents, including blank fields.
  1530  // Keep in sync with cmd/compile/internal/walk/convert.go:soleComponent.
  1531  func (t *Type) SoleComponent() *Type {
  1532  	switch t.kind {
  1533  	case TSTRUCT:
  1534  		if t.IsFuncArgStruct() {
  1535  			base.Fatalf("SoleComponent func arg struct")
  1536  		}
  1537  		if t.NumFields() != 1 {
  1538  			return nil
  1539  		}
  1540  		return t.Field(0).Type.SoleComponent()
  1541  	case TARRAY:
  1542  		if t.NumElem() != 1 {
  1543  			return nil
  1544  		}
  1545  		return t.Elem().SoleComponent()
  1546  	}
  1547  	return t
  1548  }
  1549  
  1550  // ChanDir returns the direction of a channel type t.
  1551  // The direction will be one of Crecv, Csend, or Cboth.
  1552  func (t *Type) ChanDir() ChanDir {
  1553  	t.wantEtype(TCHAN)
  1554  	return t.extra.(*Chan).Dir
  1555  }
  1556  
  1557  func (t *Type) IsMemory() bool {
  1558  	if t == TypeMem || t.kind == TTUPLE && t.extra.(*Tuple).second == TypeMem {
  1559  		return true
  1560  	}
  1561  	if t.kind == TRESULTS {
  1562  		if types := t.extra.(*Results).Types; len(types) > 0 && types[len(types)-1] == TypeMem {
  1563  			return true
  1564  		}
  1565  	}
  1566  	return false
  1567  }
  1568  func (t *Type) IsFlags() bool   { return t == TypeFlags }
  1569  func (t *Type) IsVoid() bool    { return t == TypeVoid }
  1570  func (t *Type) IsTuple() bool   { return t.kind == TTUPLE }
  1571  func (t *Type) IsResults() bool { return t.kind == TRESULTS }
  1572  
  1573  // IsUntyped reports whether t is an untyped type.
  1574  func (t *Type) IsUntyped() bool {
  1575  	if t == nil {
  1576  		return false
  1577  	}
  1578  	if t == UntypedString || t == UntypedBool {
  1579  		return true
  1580  	}
  1581  	switch t.kind {
  1582  	case TNIL, TIDEAL:
  1583  		return true
  1584  	}
  1585  	return false
  1586  }
  1587  
  1588  // HasPointers reports whether t contains a heap pointer.
  1589  // Note that this function ignores pointers to not-in-heap types.
  1590  func (t *Type) HasPointers() bool {
  1591  	return PtrDataSize(t) > 0
  1592  }
  1593  
  1594  var recvType *Type
  1595  
  1596  // FakeRecvType returns the singleton type used for interface method receivers.
  1597  func FakeRecvType() *Type {
  1598  	if recvType == nil {
  1599  		recvType = NewPtr(newType(TSTRUCT))
  1600  	}
  1601  	return recvType
  1602  }
  1603  
  1604  func FakeRecv() *Field {
  1605  	return NewField(base.AutogeneratedPos, nil, FakeRecvType())
  1606  }
  1607  
  1608  var (
  1609  	// TSSA types. HasPointers assumes these are pointer-free.
  1610  	TypeInvalid   = newSSA("invalid")
  1611  	TypeMem       = newSSA("mem")
  1612  	TypeFlags     = newSSA("flags")
  1613  	TypeVoid      = newSSA("void")
  1614  	TypeInt128    = newSSA("int128")
  1615  	TypeResultMem = newResults([]*Type{TypeMem})
  1616  )
  1617  
  1618  func init() {
  1619  	TypeInt128.width = 16
  1620  	TypeInt128.align = 8
  1621  }
  1622  
  1623  // NewNamed returns a new named type for the given type name. obj should be an
  1624  // ir.Name. The new type is incomplete (marked as TFORW kind), and the underlying
  1625  // type should be set later via SetUnderlying(). References to the type are
  1626  // maintained until the type is filled in, so those references can be updated when
  1627  // the type is complete.
  1628  func NewNamed(obj Object) *Type {
  1629  	t := newType(TFORW)
  1630  	t.obj = obj
  1631  	if obj.Sym().Pkg == ShapePkg {
  1632  		t.SetIsShape(true)
  1633  		t.SetHasShape(true)
  1634  	}
  1635  	return t
  1636  }
  1637  
  1638  // Obj returns the canonical type name node for a named type t, nil for an unnamed type.
  1639  func (t *Type) Obj() Object {
  1640  	return t.obj
  1641  }
  1642  
  1643  // SetUnderlying sets the underlying type of an incomplete type (i.e. type whose kind
  1644  // is currently TFORW). SetUnderlying automatically updates any types that were waiting
  1645  // for this type to be completed.
  1646  func (t *Type) SetUnderlying(underlying *Type) {
  1647  	if underlying.kind == TFORW {
  1648  		// This type isn't computed yet; when it is, update n.
  1649  		underlying.forwardType().Copyto = append(underlying.forwardType().Copyto, t)
  1650  		return
  1651  	}
  1652  
  1653  	ft := t.forwardType()
  1654  
  1655  	// TODO(mdempsky): Fix Type rekinding.
  1656  	t.kind = underlying.kind
  1657  	t.extra = underlying.extra
  1658  	t.width = underlying.width
  1659  	t.align = underlying.align
  1660  	t.intRegs = underlying.intRegs
  1661  	t.floatRegs = underlying.floatRegs
  1662  	t.underlying = underlying.underlying
  1663  
  1664  	if underlying.NotInHeap() {
  1665  		t.SetNotInHeap(true)
  1666  	}
  1667  	if underlying.HasShape() {
  1668  		t.SetHasShape(true)
  1669  	}
  1670  
  1671  	// spec: "The declared type does not inherit any methods bound
  1672  	// to the existing type, but the method set of an interface
  1673  	// type [...] remains unchanged."
  1674  	if t.IsInterface() {
  1675  		t.methods = underlying.methods
  1676  		t.allMethods = underlying.allMethods
  1677  	}
  1678  
  1679  	// Update types waiting on this type.
  1680  	for _, w := range ft.Copyto {
  1681  		w.SetUnderlying(t)
  1682  	}
  1683  
  1684  	// Double-check use of type as embedded type.
  1685  	if ft.Embedlineno.IsKnown() {
  1686  		if t.IsPtr() || t.IsUnsafePtr() {
  1687  			base.ErrorfAt(ft.Embedlineno, errors.InvalidPtrEmbed, "embedded type cannot be a pointer")
  1688  		}
  1689  	}
  1690  }
  1691  
  1692  func fieldsHasShape(fields []*Field) bool {
  1693  	for _, f := range fields {
  1694  		if f.Type != nil && f.Type.HasShape() {
  1695  			return true
  1696  		}
  1697  	}
  1698  	return false
  1699  }
  1700  
  1701  // newBasic returns a new basic type of the given kind.
  1702  func newBasic(kind Kind, obj Object) *Type {
  1703  	t := newType(kind)
  1704  	t.obj = obj
  1705  	return t
  1706  }
  1707  
  1708  // NewInterface returns a new interface for the given methods and
  1709  // embedded types. Embedded types are specified as fields with no Sym.
  1710  func NewInterface(methods []*Field) *Type {
  1711  	t := newType(TINTER)
  1712  	t.SetInterface(methods)
  1713  	for _, f := range methods {
  1714  		// f.Type could be nil for a broken interface declaration
  1715  		if f.Type != nil && f.Type.HasShape() {
  1716  			t.SetHasShape(true)
  1717  			break
  1718  		}
  1719  	}
  1720  	return t
  1721  }
  1722  
  1723  // NewSignature returns a new function type for the given receiver,
  1724  // parameters, and results, any of which may be nil.
  1725  func NewSignature(recv *Field, params, results []*Field) *Type {
  1726  	startParams := 0
  1727  	if recv != nil {
  1728  		startParams = 1
  1729  	}
  1730  	startResults := startParams + len(params)
  1731  
  1732  	allParams := make([]*Field, startResults+len(results))
  1733  	if recv != nil {
  1734  		allParams[0] = recv
  1735  	}
  1736  	copy(allParams[startParams:], params)
  1737  	copy(allParams[startResults:], results)
  1738  
  1739  	t := newType(TFUNC)
  1740  	ft := t.funcType()
  1741  
  1742  	funargs := func(fields []*Field) *Type {
  1743  		s := NewStruct(fields)
  1744  		s.StructType().ParamTuple = true
  1745  		return s
  1746  	}
  1747  
  1748  	ft.allParams = allParams
  1749  	ft.startParams = startParams
  1750  	ft.startResults = startResults
  1751  
  1752  	ft.resultsTuple = funargs(allParams[startResults:])
  1753  
  1754  	if fieldsHasShape(allParams) {
  1755  		t.SetHasShape(true)
  1756  	}
  1757  
  1758  	return t
  1759  }
  1760  
  1761  // NewStruct returns a new struct with the given fields.
  1762  func NewStruct(fields []*Field) *Type {
  1763  	t := newType(TSTRUCT)
  1764  	t.setFields(fields)
  1765  	if fieldsHasShape(fields) {
  1766  		t.SetHasShape(true)
  1767  	}
  1768  	return t
  1769  }
  1770  
  1771  var (
  1772  	IsInt     [NTYPE]bool
  1773  	IsFloat   [NTYPE]bool
  1774  	IsComplex [NTYPE]bool
  1775  	IsSimple  [NTYPE]bool
  1776  )
  1777  
  1778  var IsOrdered [NTYPE]bool
  1779  
  1780  // IsReflexive reports whether t has a reflexive equality operator.
  1781  // That is, if x==x for all x of type t.
  1782  func IsReflexive(t *Type) bool {
  1783  	switch t.Kind() {
  1784  	case TBOOL,
  1785  		TINT,
  1786  		TUINT,
  1787  		TINT8,
  1788  		TUINT8,
  1789  		TINT16,
  1790  		TUINT16,
  1791  		TINT32,
  1792  		TUINT32,
  1793  		TINT64,
  1794  		TUINT64,
  1795  		TUINTPTR,
  1796  		TPTR,
  1797  		TUNSAFEPTR,
  1798  		TSTRING,
  1799  		TCHAN:
  1800  		return true
  1801  
  1802  	case TFLOAT32,
  1803  		TFLOAT64,
  1804  		TCOMPLEX64,
  1805  		TCOMPLEX128,
  1806  		TINTER:
  1807  		return false
  1808  
  1809  	case TARRAY:
  1810  		return IsReflexive(t.Elem())
  1811  
  1812  	case TSTRUCT:
  1813  		for _, t1 := range t.Fields() {
  1814  			if !IsReflexive(t1.Type) {
  1815  				return false
  1816  			}
  1817  		}
  1818  		return true
  1819  
  1820  	default:
  1821  		base.Fatalf("bad type for map key: %v", t)
  1822  		return false
  1823  	}
  1824  }
  1825  
  1826  // Can this type be stored directly in an interface word?
  1827  // Yes, if the representation is a single pointer.
  1828  func IsDirectIface(t *Type) bool {
  1829  	switch t.Kind() {
  1830  	case TPTR:
  1831  		// Pointers to notinheap types must be stored indirectly. See issue 42076.
  1832  		return !t.Elem().NotInHeap()
  1833  	case TCHAN,
  1834  		TMAP,
  1835  		TFUNC,
  1836  		TUNSAFEPTR:
  1837  		return true
  1838  
  1839  	case TARRAY:
  1840  		// Array of 1 direct iface type can be direct.
  1841  		return t.NumElem() == 1 && IsDirectIface(t.Elem())
  1842  
  1843  	case TSTRUCT:
  1844  		// Struct with 1 field of direct iface type can be direct.
  1845  		return t.NumFields() == 1 && IsDirectIface(t.Field(0).Type)
  1846  	}
  1847  
  1848  	return false
  1849  }
  1850  
  1851  // IsInterfaceMethod reports whether (field) m is
  1852  // an interface method. Such methods have the
  1853  // special receiver type types.FakeRecvType().
  1854  func IsInterfaceMethod(f *Type) bool {
  1855  	return f.Recv().Type == FakeRecvType()
  1856  }
  1857  
  1858  // IsMethodApplicable reports whether method m can be called on a
  1859  // value of type t. This is necessary because we compute a single
  1860  // method set for both T and *T, but some *T methods are not
  1861  // applicable to T receivers.
  1862  func IsMethodApplicable(t *Type, m *Field) bool {
  1863  	return t.IsPtr() || !m.Type.Recv().Type.IsPtr() || IsInterfaceMethod(m.Type) || m.Embedded == 2
  1864  }
  1865  
  1866  // RuntimeSymName returns the name of s if it's in package "runtime"; otherwise
  1867  // it returns "".
  1868  func RuntimeSymName(s *Sym) string {
  1869  	if s.Pkg.Path == "runtime" {
  1870  		return s.Name
  1871  	}
  1872  	return ""
  1873  }
  1874  
  1875  // ReflectSymName returns the name of s if it's in package "reflect"; otherwise
  1876  // it returns "".
  1877  func ReflectSymName(s *Sym) string {
  1878  	if s.Pkg.Path == "reflect" {
  1879  		return s.Name
  1880  	}
  1881  	return ""
  1882  }
  1883  
  1884  // IsNoInstrumentPkg reports whether p is a package that
  1885  // should not be instrumented.
  1886  func IsNoInstrumentPkg(p *Pkg) bool {
  1887  	return objabi.LookupPkgSpecial(p.Path).NoInstrument
  1888  }
  1889  
  1890  // IsNoRacePkg reports whether p is a package that
  1891  // should not be race instrumented.
  1892  func IsNoRacePkg(p *Pkg) bool {
  1893  	return objabi.LookupPkgSpecial(p.Path).NoRaceFunc
  1894  }
  1895  
  1896  // ReceiverBaseType returns the underlying type, if any,
  1897  // that owns methods with receiver parameter t.
  1898  // The result is either a named type or an anonymous struct.
  1899  func ReceiverBaseType(t *Type) *Type {
  1900  	if t == nil {
  1901  		return nil
  1902  	}
  1903  
  1904  	// Strip away pointer if it's there.
  1905  	if t.IsPtr() {
  1906  		if t.Sym() != nil {
  1907  			return nil
  1908  		}
  1909  		t = t.Elem()
  1910  		if t == nil {
  1911  			return nil
  1912  		}
  1913  	}
  1914  
  1915  	// Must be a named type or anonymous struct.
  1916  	if t.Sym() == nil && !t.IsStruct() {
  1917  		return nil
  1918  	}
  1919  
  1920  	// Check types.
  1921  	if IsSimple[t.Kind()] {
  1922  		return t
  1923  	}
  1924  	switch t.Kind() {
  1925  	case TARRAY, TCHAN, TFUNC, TMAP, TSLICE, TSTRING, TSTRUCT:
  1926  		return t
  1927  	}
  1928  	return nil
  1929  }
  1930  
  1931  func FloatForComplex(t *Type) *Type {
  1932  	switch t.Kind() {
  1933  	case TCOMPLEX64:
  1934  		return Types[TFLOAT32]
  1935  	case TCOMPLEX128:
  1936  		return Types[TFLOAT64]
  1937  	}
  1938  	base.Fatalf("unexpected type: %v", t)
  1939  	return nil
  1940  }
  1941  
  1942  func ComplexForFloat(t *Type) *Type {
  1943  	switch t.Kind() {
  1944  	case TFLOAT32:
  1945  		return Types[TCOMPLEX64]
  1946  	case TFLOAT64:
  1947  		return Types[TCOMPLEX128]
  1948  	}
  1949  	base.Fatalf("unexpected type: %v", t)
  1950  	return nil
  1951  }
  1952  
  1953  func TypeSym(t *Type) *Sym {
  1954  	return TypeSymLookup(TypeSymName(t))
  1955  }
  1956  
  1957  func TypeSymLookup(name string) *Sym {
  1958  	typepkgmu.Lock()
  1959  	s := typepkg.Lookup(name)
  1960  	typepkgmu.Unlock()
  1961  	return s
  1962  }
  1963  
  1964  func TypeSymName(t *Type) string {
  1965  	name := t.LinkString()
  1966  	// Use a separate symbol name for Noalg types for #17752.
  1967  	if TypeHasNoAlg(t) {
  1968  		name = "noalg." + name
  1969  	}
  1970  	return name
  1971  }
  1972  
  1973  // Fake package for runtime type info (headers)
  1974  // Don't access directly, use typeLookup below.
  1975  var (
  1976  	typepkgmu sync.Mutex // protects typepkg lookups
  1977  	typepkg   = NewPkg("type", "type")
  1978  )
  1979  
  1980  var SimType [NTYPE]Kind
  1981  
  1982  // Fake package for shape types (see typecheck.Shapify()).
  1983  var ShapePkg = NewPkg("go.shape", "go.shape")
  1984  

View as plain text