src/cmd/compile/internal/gc/type.go

   1 // Copyright 2015 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 // This file provides methods that let us export a Type as an ../ssa:Type.
   6 // We don't export this package's Type directly because it would lead
   7 // to an import cycle with this package and ../ssa.
   8 // TODO: move Type to its own package, then we don't need to dance around import cycles.
   9
  10 package gc
  11
  12 import (
  13         "cmd/compile/internal/ssa"
  14         "cmd/internal/src"
  15         "fmt"
  16 )
  17
  18 // EType describes a kind of type.
  19 type EType uint8
  20
  21 const (
  22         Txxx = iota
  23
  24         TINT8
  25         TUINT8
  26         TINT16
  27         TUINT16
  28         TINT32
  29         TUINT32
  30         TINT64
  31         TUINT64
  32         TINT
  33         TUINT
  34         TUINTPTR
  35
  36         TCOMPLEX64
  37         TCOMPLEX128
  38
  39         TFLOAT32
  40         TFLOAT64
  41
  42         TBOOL
  43
  44         TPTR32
  45         TPTR64
  46
  47         TFUNC
  48         TSLICE
  49         TARRAY
  50         TSTRUCT
  51         TCHAN
  52         TMAP
  53         TINTER
  54         TFORW
  55         TANY
  56         TSTRING
  57         TUNSAFEPTR
  58
  59         // pseudo-types for literals
  60         TIDEAL
  61         TNIL
  62         TBLANK
  63
  64         // pseudo-types for frame layout
  65         TFUNCARGS
  66         TCHANARGS
  67         TINTERMETH
  68
  69         // pseudo-types for import/export
  70         TDDDFIELD // wrapper: contained type is a ... field
  71
  72         NTYPE
  73 )
  74
  75 // ChanDir is whether a channel can send, receive, or both.
  76 type ChanDir uint8
  77
  78 func (c ChanDir) CanRecv() bool { return c&Crecv != 0 }
  79 func (c ChanDir) CanSend() bool { return c&Csend != 0 }
  80
  81 const (
  82         // types of channel
  83         // must match ../../../../reflect/type.go:/ChanDir
  84         Crecv ChanDir = 1 << 0
  85         Csend ChanDir = 1 << 1
  86         Cboth ChanDir = Crecv | Csend
  87 )
  88
  89 // Types stores pointers to predeclared named types.
  90 //
  91 // It also stores pointers to several special types:
  92 //   - Types[TANY] is the placeholder "any" type recognized by substArgTypes.
  93 //   - Types[TBLANK] represents the blank variable's type.
  94 //   - Types[TIDEAL] represents untyped numeric constants.
  95 //   - Types[TNIL] represents the predeclared "nil" value's type.
  96 //   - Types[TUNSAFEPTR] is package unsafe's Pointer type.
  97 var Types [NTYPE]*Type
  98
  99 var (
 100         // Predeclared alias types. Kept separate for better error messages.
 101         bytetype *Type
 102         runetype *Type
 103
 104         // Predeclared error interface type.
 105         errortype *Type
 106
 107         // Types to represent untyped string and boolean constants.
 108         idealstring *Type
 109         idealbool   *Type
 110
 111         // Types to represent untyped numeric constants.
 112         // Note: Currently these are only used within the binary export
 113         // data format. The rest of the compiler only uses Types[TIDEAL].
 114         idealint     = typ(TIDEAL)
 115         idealrune    = typ(TIDEAL)
 116         idealfloat   = typ(TIDEAL)
 117         idealcomplex = typ(TIDEAL)
 118 )
 119
 120 // A Type represents a Go type.
 121 type Type struct {
 122         // Extra contains extra etype-specific fields.
 123         // As an optimization, those etype-specific structs which contain exactly
 124         // one pointer-shaped field are stored as values rather than pointers when possible.
 125         //
 126         // TMAP: *MapType
 127         // TFORW: *ForwardType
 128         // TFUNC: *FuncType
 129         // TINTERMETHOD: InterMethType
 130         // TSTRUCT: *StructType
 131         // TINTER: *InterType
 132         // TDDDFIELD: DDDFieldType
 133         // TFUNCARGS: FuncArgsType
 134         // TCHANARGS: ChanArgsType
 135         // TCHAN: *ChanType
 136         // TPTR32, TPTR64: PtrType
 137         // TARRAY: *ArrayType
 138         // TSLICE: SliceType
 139         Extra interface{}
 140
 141         // Width is the width of this Type in bytes.
 142         Width int64
 143
 144         methods    Fields
 145         allMethods Fields
 146
 147         nod  *Node // canonical OTYPE node
 148         Orig *Type // original type (type literal or predefined type)
 149
 150         sliceOf *Type
 151         ptrTo   *Type
 152
 153         Sym    *Sym     // symbol containing name, for named types
 154         Vargen int32    // unique name for OTYPE/ONAME
 155         Pos    src.XPos // position at which this type was declared, implicitly or explicitly
 156
 157         Etype      EType // kind of type
 158         Noalg      bool  // suppress hash and eq algorithm generation
 159         Trecur     uint8 // to detect loops
 160         Local      bool  // created in this file
 161         Deferwidth bool
 162         Broke      bool  // broken type definition.
 163         Align      uint8 // the required alignment of this type, in bytes
 164         NotInHeap  bool  // type cannot be heap allocated
 165 }
 166
 167 // MapType contains Type fields specific to maps.
 168 type MapType struct {
 169         Key *Type // Key type
 170         Val *Type // Val (elem) type
 171
 172         Bucket *Type // internal struct type representing a hash bucket
 173         Hmap   *Type // internal struct type representing the Hmap (map header object)
 174         Hiter  *Type // internal struct type representing hash iterator state
 175 }
 176
 177 // MapType returns t's extra map-specific fields.
 178 func (t *Type) MapType() *MapType {
 179         t.wantEtype(TMAP)
 180         return t.Extra.(*MapType)
 181 }
 182
 183 // ForwardType contains Type fields specific to forward types.
 184 type ForwardType struct {
 185         Copyto      []*Node  // where to copy the eventual value to
 186         Embedlineno src.XPos // first use of this type as an embedded type
 187 }
 188
 189 // ForwardType returns t's extra forward-type-specific fields.
 190 func (t *Type) ForwardType() *ForwardType {
 191         t.wantEtype(TFORW)
 192         return t.Extra.(*ForwardType)
 193 }
 194
 195 // FuncType contains Type fields specific to func types.
 196 type FuncType struct {
 197         Receiver *Type // function receiver
 198         Results  *Type // function results
 199         Params   *Type // function params
 200
 201         Nname *Node
 202
 203         // Argwid is the total width of the function receiver, params, and results.
 204         // It gets calculated via a temporary TFUNCARGS type.
 205         // Note that TFUNC's Width is Widthptr.
 206         Argwid int64
 207
 208         Outnamed bool
 209 }
 210
 211 // FuncType returns t's extra func-specific fields.
 212 func (t *Type) FuncType() *FuncType {
 213         t.wantEtype(TFUNC)
 214         return t.Extra.(*FuncType)
 215 }
 216
 217 // InterMethType contains Type fields specific to interface method pseudo-types.
 218 type InterMethType struct {
 219         Nname *Node
 220 }
 221
 222 // StructType contains Type fields specific to struct types.
 223 type StructType struct {
 224         fields Fields
 225
 226         // Maps have three associated internal structs (see struct MapType).
 227         // Map links such structs back to their map type.
 228         Map *Type
 229
 230         Funarg      Funarg // type of function arguments for arg struct
 231         Haspointers uint8  // 0 unknown, 1 no, 2 yes
 232 }
 233
 234 // Fnstruct records the kind of function argument
 235 type Funarg uint8
 236
 237 const (
 238         FunargNone    Funarg = iota
 239         FunargRcvr           // receiver
 240         FunargParams         // input parameters
 241         FunargResults        // output results
 242 )
 243
 244 // StructType returns t's extra struct-specific fields.
 245 func (t *Type) StructType() *StructType {
 246         t.wantEtype(TSTRUCT)
 247         return t.Extra.(*StructType)
 248 }
 249
 250 // InterType contains Type fields specific to interface types.
 251 type InterType struct {
 252         fields Fields
 253 }
 254
 255 // PtrType contains Type fields specific to pointer types.
 256 type PtrType struct {
 257         Elem *Type // element type
 258 }
 259
 260 // DDDFieldType contains Type fields specific to TDDDFIELD types.
 261 type DDDFieldType struct {
 262         T *Type // reference to a slice type for ... args
 263 }
 264
 265 // ChanArgsType contains Type fields specific to TCHANARGS types.
 266 type ChanArgsType struct {
 267         T *Type // reference to a chan type whose elements need a width check
 268 }
 269
 270 // // FuncArgsType contains Type fields specific to TFUNCARGS types.
 271 type FuncArgsType struct {
 272         T *Type // reference to a func type whose elements need a width check
 273 }
 274
 275 // ChanType contains Type fields specific to channel types.
 276 type ChanType struct {
 277         Elem *Type   // element type
 278         Dir  ChanDir // channel direction
 279 }
 280
 281 // ChanType returns t's extra channel-specific fields.
 282 func (t *Type) ChanType() *ChanType {
 283         t.wantEtype(TCHAN)
 284         return t.Extra.(*ChanType)
 285 }
 286
 287 // ArrayType contains Type fields specific to array types.
 288 type ArrayType struct {
 289         Elem        *Type // element type
 290         Bound       int64 // number of elements; <0 if unknown yet
 291         Haspointers uint8 // 0 unknown, 1 no, 2 yes
 292 }
 293
 294 // SliceType contains Type fields specific to slice types.
 295 type SliceType struct {
 296         Elem *Type // element type
 297 }
 298
 299 // A Field represents a field in a struct or a method in an interface or
 300 // associated with a named type.
 301 type Field struct {
 302         Nointerface bool
 303         Embedded    uint8 // embedded field
 304         Funarg      Funarg
 305         Broke       bool // broken field definition
 306         Isddd       bool // field is ... argument
 307
 308         Sym   *Sym
 309         Nname *Node
 310
 311         Type *Type // field type
 312
 313         // Offset in bytes of this field or method within its enclosing struct
 314         // or interface Type.
 315         Offset int64
 316
 317         Note string // literal string annotation
 318 }
 319
 320 // End returns the offset of the first byte immediately after this field.
 321 func (f *Field) End() int64 {
 322         return f.Offset + f.Type.Width
 323 }
 324
 325 // Fields is a pointer to a slice of *Field.
 326 // This saves space in Types that do not have fields or methods
 327 // compared to a simple slice of *Field.
 328 type Fields struct {
 329         s *[]*Field
 330 }
 331
 332 // Len returns the number of entries in f.
 333 func (f *Fields) Len() int {
 334         if f.s == nil {
 335                 return 0
 336         }
 337         return len(*f.s)
 338 }
 339
 340 // Slice returns the entries in f as a slice.
 341 // Changes to the slice entries will be reflected in f.
 342 func (f *Fields) Slice() []*Field {
 343         if f.s == nil {
 344                 return nil
 345         }
 346         return *f.s
 347 }
 348
 349 // Index returns the i'th element of Fields.
 350 // It panics if f does not have at least i+1 elements.
 351 func (f *Fields) Index(i int) *Field {
 352         return (*f.s)[i]
 353 }
 354
 355 // Set sets f to a slice.
 356 // This takes ownership of the slice.
 357 func (f *Fields) Set(s []*Field) {
 358         if len(s) == 0 {
 359                 f.s = nil
 360         } else {
 361                 // Copy s and take address of t rather than s to avoid
 362                 // allocation in the case where len(s) == 0.
 363                 t := s
 364                 f.s = &t
 365         }
 366 }
 367
 368 // Append appends entries to f.
 369 func (f *Fields) Append(s ...*Field) {
 370         if f.s == nil {
 371                 f.s = new([]*Field)
 372         }
 373         *f.s = append(*f.s, s...)
 374 }
 375
 376 // typ returns a new Type of the specified kind.
 377 func typ(et EType) *Type {
 378         t := &Type{
 379                 Etype: et,
 380                 Width: BADWIDTH,
 381                 Pos:   lineno,
 382         }
 383         t.Orig = t
 384         // TODO(josharian): lazily initialize some of these?
 385         switch t.Etype {
 386         case TMAP:
 387                 t.Extra = new(MapType)
 388         case TFORW:
 389                 t.Extra = new(ForwardType)
 390         case TFUNC:
 391                 t.Extra = new(FuncType)
 392         case TINTERMETH:
 393                 t.Extra = InterMethType{}
 394         case TSTRUCT:
 395                 t.Extra = new(StructType)
 396         case TINTER:
 397                 t.Extra = new(InterType)
 398         case TPTR32, TPTR64:
 399                 t.Extra = PtrType{}
 400         case TCHANARGS:
 401                 t.Extra = ChanArgsType{}
 402         case TFUNCARGS:
 403                 t.Extra = FuncArgsType{}
 404         case TDDDFIELD:
 405                 t.Extra = DDDFieldType{}
 406         case TCHAN:
 407                 t.Extra = new(ChanType)
 408         }
 409         return t
 410 }
 411
 412 // typArray returns a new fixed-length array Type.
 413 func typArray(elem *Type, bound int64) *Type {
 414         if bound < 0 {
 415                 Fatalf("typArray: invalid bound %v", bound)
 416         }
 417         t := typ(TARRAY)
 418         t.Extra = &ArrayType{Elem: elem, Bound: bound}
 419         t.NotInHeap = elem.NotInHeap
 420         return t
 421 }
 422
 423 // typSlice returns the slice Type with element type elem.
 424 func typSlice(elem *Type) *Type {
 425         if t := elem.sliceOf; t != nil {
 426                 if t.Elem() != elem {
 427                         Fatalf("elem mismatch")
 428                 }
 429                 return t
 430         }
 431
 432         t := typ(TSLICE)
 433         t.Extra = SliceType{Elem: elem}
 434         elem.sliceOf = t
 435         return t
 436 }
 437
 438 // typDDDArray returns a new [...]T array Type.
 439 func typDDDArray(elem *Type) *Type {
 440         t := typ(TARRAY)
 441         t.Extra = &ArrayType{Elem: elem, Bound: -1}
 442         t.NotInHeap = elem.NotInHeap
 443         return t
 444 }
 445
 446 // typChan returns a new chan Type with direction dir.
 447 func typChan(elem *Type, dir ChanDir) *Type {
 448         t := typ(TCHAN)
 449         ct := t.ChanType()
 450         ct.Elem = elem
 451         ct.Dir = dir
 452         return t
 453 }
 454
 455 // typMap returns a new map Type with key type k and element (aka value) type v.
 456 func typMap(k, v *Type) *Type {
 457         t := typ(TMAP)
 458         mt := t.MapType()
 459         mt.Key = k
 460         mt.Val = v
 461         return t
 462 }
 463
 464 // typPtr returns the pointer type pointing to t.
 465 func typPtr(elem *Type) *Type {
 466         if t := elem.ptrTo; t != nil {
 467                 if t.Elem() != elem {
 468                         Fatalf("elem mismatch")
 469                 }
 470                 return t
 471         }
 472
 473         t := typ(Tptr)
 474         t.Extra = PtrType{Elem: elem}
 475         t.Width = int64(Widthptr)
 476         t.Align = uint8(Widthptr)
 477         elem.ptrTo = t
 478         return t
 479 }
 480
 481 // typDDDField returns a new TDDDFIELD type for slice type s.
 482 func typDDDField(s *Type) *Type {
 483         t := typ(TDDDFIELD)
 484         t.Extra = DDDFieldType{T: s}
 485         return t
 486 }
 487
 488 // typChanArgs returns a new TCHANARGS type for channel type c.
 489 func typChanArgs(c *Type) *Type {
 490         t := typ(TCHANARGS)
 491         t.Extra = ChanArgsType{T: c}
 492         return t
 493 }
 494
 495 // typFuncArgs returns a new TFUNCARGS type for func type f.
 496 func typFuncArgs(f *Type) *Type {
 497         t := typ(TFUNCARGS)
 498         t.Extra = FuncArgsType{T: f}
 499         return t
 500 }
 501
 502 func newField() *Field {
 503         return &Field{
 504                 Offset: BADWIDTH,
 505         }
 506 }
 507
 508 // substArgTypes substitutes the given list of types for
 509 // successive occurrences of the "any" placeholder in the
 510 // type syntax expression n.Type.
 511 // The result of substArgTypes MUST be assigned back to old, e.g.
 512 //      n.Left = substArgTypes(n.Left, t1, t2)
 513 func substArgTypes(old *Node, types ...*Type) *Node {
 514         n := *old // make shallow copy
 515
 516         for _, t := range types {
 517                 dowidth(t)
 518         }
 519         n.Type = substAny(n.Type, &types)
 520         if len(types) > 0 {
 521                 Fatalf("substArgTypes: too many argument types")
 522         }
 523         return &n
 524 }
 525
 526 // substAny walks t, replacing instances of "any" with successive
 527 // elements removed from types.  It returns the substituted type.
 528 func substAny(t *Type, types *[]*Type) *Type {
 529         if t == nil {
 530                 return nil
 531         }
 532
 533         switch t.Etype {
 534         default:
 535                 // Leave the type unchanged.
 536
 537         case TANY:
 538                 if len(*types) == 0 {
 539                         Fatalf("substArgTypes: not enough argument types")
 540                 }
 541                 t = (*types)[0]
 542                 *types = (*types)[1:]
 543
 544         case TPTR32, TPTR64:
 545                 elem := substAny(t.Elem(), types)
 546                 if elem != t.Elem() {
 547                         t = t.Copy()
 548                         t.Extra = PtrType{Elem: elem}
 549                 }
 550
 551         case TARRAY:
 552                 elem := substAny(t.Elem(), types)
 553                 if elem != t.Elem() {
 554                         t = t.Copy()
 555                         t.Extra.(*ArrayType).Elem = elem
 556                 }
 557
 558         case TSLICE:
 559                 elem := substAny(t.Elem(), types)
 560                 if elem != t.Elem() {
 561                         t = t.Copy()
 562                         t.Extra = SliceType{Elem: elem}
 563                 }
 564
 565         case TCHAN:
 566                 elem := substAny(t.Elem(), types)
 567                 if elem != t.Elem() {
 568                         t = t.Copy()
 569                         t.Extra.(*ChanType).Elem = elem
 570                 }
 571
 572         case TMAP:
 573                 key := substAny(t.Key(), types)
 574                 val := substAny(t.Val(), types)
 575                 if key != t.Key() || val != t.Val() {
 576                         t = t.Copy()
 577                         t.Extra.(*MapType).Key = key
 578                         t.Extra.(*MapType).Val = val
 579                 }
 580
 581         case TFUNC:
 582                 recvs := substAny(t.Recvs(), types)
 583                 params := substAny(t.Params(), types)
 584                 results := substAny(t.Results(), types)
 585                 if recvs != t.Recvs() || params != t.Params() || results != t.Results() {
 586                         t = t.Copy()
 587                         t.FuncType().Receiver = recvs
 588                         t.FuncType().Results = results
 589                         t.FuncType().Params = params
 590                 }
 591
 592         case TSTRUCT:
 593                 fields := t.FieldSlice()
 594                 var nfs []*Field
 595                 for i, f := range fields {
 596                         nft := substAny(f.Type, types)
 597                         if nft == f.Type {
 598                                 continue
 599                         }
 600                         if nfs == nil {
 601                                 nfs = append([]*Field(nil), fields...)
 602                         }
 603                         nfs[i] = f.Copy()
 604                         nfs[i].Type = nft
 605                 }
 606                 if nfs != nil {
 607                         t = t.Copy()
 608                         t.SetFields(nfs)
 609                 }
 610         }
 611
 612         return t
 613 }
 614
 615 // Copy returns a shallow copy of the Type.
 616 func (t *Type) Copy() *Type {
 617         if t == nil {
 618                 return nil
 619         }
 620         nt := *t
 621         // copy any *T Extra fields, to avoid aliasing
 622         switch t.Etype {
 623         case TMAP:
 624                 x := *t.Extra.(*MapType)
 625                 nt.Extra = &x
 626         case TFORW:
 627                 x := *t.Extra.(*ForwardType)
 628                 nt.Extra = &x
 629         case TFUNC:
 630                 x := *t.Extra.(*FuncType)
 631                 nt.Extra = &x
 632         case TSTRUCT:
 633                 x := *t.Extra.(*StructType)
 634                 nt.Extra = &x
 635         case TINTER:
 636                 x := *t.Extra.(*InterType)
 637                 nt.Extra = &x
 638         case TCHAN:
 639                 x := *t.Extra.(*ChanType)
 640                 nt.Extra = &x
 641         case TARRAY:
 642                 x := *t.Extra.(*ArrayType)
 643                 nt.Extra = &x
 644         }
 645         // TODO(mdempsky): Find out why this is necessary and explain.
 646         if t.Orig == t {
 647                 nt.Orig = &nt
 648         }
 649         return &nt
 650 }
 651
 652 func (f *Field) Copy() *Field {
 653         nf := *f
 654         return &nf
 655 }
 656
 657 // Iter provides an abstraction for iterating across struct fields and
 658 // interface methods.
 659 type Iter struct {
 660         s []*Field
 661 }
 662
 663 // iterFields returns the first field or method in struct or interface type t
 664 // and an Iter value to continue iterating across the rest.
 665 func iterFields(t *Type) (*Field, Iter) {
 666         return t.Fields().Iter()
 667 }
 668
 669 // Iter returns the first field in fs and an Iter value to continue iterating
 670 // across its successor fields.
 671 // Deprecated: New code should use Slice instead.
 672 func (fs *Fields) Iter() (*Field, Iter) {
 673         i := Iter{s: fs.Slice()}
 674         f := i.Next()
 675         return f, i
 676 }
 677
 678 // Next returns the next field or method, if any.
 679 func (i *Iter) Next() *Field {
 680         if len(i.s) == 0 {
 681                 return nil
 682         }
 683         f := i.s[0]
 684         i.s = i.s[1:]
 685         return f
 686 }
 687
 688 func (t *Type) wantEtype(et EType) {
 689         if t.Etype != et {
 690                 Fatalf("want %v, but have %v", et, t)
 691         }
 692 }
 693
 694 func (t *Type) Recvs() *Type   { return t.FuncType().Receiver }
 695 func (t *Type) Params() *Type  { return t.FuncType().Params }
 696 func (t *Type) Results() *Type { return t.FuncType().Results }
 697
 698 // Recv returns the receiver of function type t, if any.
 699 func (t *Type) Recv() *Field {
 700         s := t.Recvs()
 701         if s.NumFields() == 0 {
 702                 return nil
 703         }
 704         return s.Field(0)
 705 }
 706
 707 // recvsParamsResults stores the accessor functions for a function Type's
 708 // receiver, parameters, and result parameters, in that order.
 709 // It can be used to iterate over all of a function's parameter lists.
 710 var recvsParamsResults = [3]func(*Type) *Type{
 711         (*Type).Recvs, (*Type).Params, (*Type).Results,
 712 }
 713
 714 // paramsResults is like recvsParamsResults, but omits receiver parameters.
 715 var paramsResults = [2]func(*Type) *Type{
 716         (*Type).Params, (*Type).Results,
 717 }
 718
 719 // Key returns the key type of map type t.
 720 func (t *Type) Key() *Type {
 721         t.wantEtype(TMAP)
 722         return t.Extra.(*MapType).Key
 723 }
 724
 725 // Val returns the value type of map type t.
 726 func (t *Type) Val() *Type {
 727         t.wantEtype(TMAP)
 728         return t.Extra.(*MapType).Val
 729 }
 730
 731 // Elem returns the type of elements of t.
 732 // Usable with pointers, channels, arrays, and slices.
 733 func (t *Type) Elem() *Type {
 734         switch t.Etype {
 735         case TPTR32, TPTR64:
 736                 return t.Extra.(PtrType).Elem
 737         case TARRAY:
 738                 return t.Extra.(*ArrayType).Elem
 739         case TSLICE:
 740                 return t.Extra.(SliceType).Elem
 741         case TCHAN:
 742                 return t.Extra.(*ChanType).Elem
 743         }
 744         Fatalf("Type.Elem %s", t.Etype)
 745         return nil
 746 }
 747
 748 // DDDField returns the slice ... type for TDDDFIELD type t.
 749 func (t *Type) DDDField() *Type {
 750         t.wantEtype(TDDDFIELD)
 751         return t.Extra.(DDDFieldType).T
 752 }
 753
 754 // ChanArgs returns the channel type for TCHANARGS type t.
 755 func (t *Type) ChanArgs() *Type {
 756         t.wantEtype(TCHANARGS)
 757         return t.Extra.(ChanArgsType).T
 758 }
 759
 760 // FuncArgs returns the channel type for TFUNCARGS type t.
 761 func (t *Type) FuncArgs() *Type {
 762         t.wantEtype(TFUNCARGS)
 763         return t.Extra.(FuncArgsType).T
 764 }
 765
 766 // Nname returns the associated function's nname.
 767 func (t *Type) Nname() *Node {
 768         switch t.Etype {
 769         case TFUNC:
 770                 return t.Extra.(*FuncType).Nname
 771         case TINTERMETH:
 772                 return t.Extra.(InterMethType).Nname
 773         }
 774         Fatalf("Type.Nname %v %v", t.Etype, t)
 775         return nil
 776 }
 777
 778 // Nname sets the associated function's nname.
 779 func (t *Type) SetNname(n *Node) {
 780         switch t.Etype {
 781         case TFUNC:
 782                 t.Extra.(*FuncType).Nname = n
 783         case TINTERMETH:
 784                 t.Extra = InterMethType{Nname: n}
 785         default:
 786                 Fatalf("Type.SetNname %v %v", t.Etype, t)
 787         }
 788 }
 789
 790 // IsFuncArgStruct reports whether t is a struct representing function parameters.
 791 func (t *Type) IsFuncArgStruct() bool {
 792         return t.Etype == TSTRUCT && t.Extra.(*StructType).Funarg != FunargNone
 793 }
 794
 795 func (t *Type) Methods() *Fields {
 796         // TODO(mdempsky): Validate t?
 797         return &t.methods
 798 }
 799
 800 func (t *Type) AllMethods() *Fields {
 801         // TODO(mdempsky): Validate t?
 802         return &t.allMethods
 803 }
 804
 805 func (t *Type) Fields() *Fields {
 806         switch t.Etype {
 807         case TSTRUCT:
 808                 return &t.Extra.(*StructType).fields
 809         case TINTER:
 810                 return &t.Extra.(*InterType).fields
 811         }
 812         Fatalf("Fields: type %v does not have fields", t)
 813         return nil
 814 }
 815
 816 // Field returns the i'th field/method of struct/interface type t.
 817 func (t *Type) Field(i int) *Field {
 818         return t.Fields().Slice()[i]
 819 }
 820
 821 // FieldSlice returns a slice of containing all fields/methods of
 822 // struct/interface type t.
 823 func (t *Type) FieldSlice() []*Field {
 824         return t.Fields().Slice()
 825 }
 826
 827 // SetFields sets struct/interface type t's fields/methods to fields.
 828 func (t *Type) SetFields(fields []*Field) {
 829         for _, f := range fields {
 830                 // If type T contains a field F with a go:notinheap
 831                 // type, then T must also be go:notinheap. Otherwise,
 832                 // you could heap allocate T and then get a pointer F,
 833                 // which would be a heap pointer to a go:notinheap
 834                 // type.
 835                 if f.Type != nil && f.Type.NotInHeap {
 836                         t.NotInHeap = true
 837                         break
 838                 }
 839         }
 840         t.Fields().Set(fields)
 841 }
 842
 843 func (t *Type) isDDDArray() bool {
 844         if t.Etype != TARRAY {
 845                 return false
 846         }
 847         return t.Extra.(*ArrayType).Bound < 0
 848 }
 849
 850 // ArgWidth returns the total aligned argument size for a function.
 851 // It includes the receiver, parameters, and results.
 852 func (t *Type) ArgWidth() int64 {
 853         t.wantEtype(TFUNC)
 854         return t.Extra.(*FuncType).Argwid
 855 }
 856
 857 func (t *Type) Size() int64 {
 858         dowidth(t)
 859         return t.Width
 860 }
 861
 862 func (t *Type) Alignment() int64 {
 863         dowidth(t)
 864         return int64(t.Align)
 865 }
 866
 867 func (t *Type) SimpleString() string {
 868         return t.Etype.String()
 869 }
 870
 871 // Compare compares types for purposes of the SSA back
 872 // end, returning an ssa.Cmp (one of CMPlt, CMPeq, CMPgt).
 873 // The answers are correct for an optimizer
 874 // or code generator, but not necessarily typechecking.
 875 // The order chosen is arbitrary, only consistency and division
 876 // into equivalence classes (Types that compare CMPeq) matters.
 877 func (t *Type) Compare(u ssa.Type) ssa.Cmp {
 878         x, ok := u.(*Type)
 879         // ssa.CompilerType is smaller than gc.Type
 880         // bare pointer equality is easy.
 881         if !ok {
 882                 return ssa.CMPgt
 883         }
 884         if x == t {
 885                 return ssa.CMPeq
 886         }
 887         return t.cmp(x)
 888 }
 889
 890 func cmpForNe(x bool) ssa.Cmp {
 891         if x {
 892                 return ssa.CMPlt
 893         }
 894         return ssa.CMPgt
 895 }
 896
 897 func (r *Sym) cmpsym(s *Sym) ssa.Cmp {
 898         if r == s {
 899                 return ssa.CMPeq
 900         }
 901         if r == nil {
 902                 return ssa.CMPlt
 903         }
 904         if s == nil {
 905                 return ssa.CMPgt
 906         }
 907         // Fast sort, not pretty sort
 908         if len(r.Name) != len(s.Name) {
 909                 return cmpForNe(len(r.Name) < len(s.Name))
 910         }
 911         if r.Pkg != s.Pkg {
 912                 if len(r.Pkg.Prefix) != len(s.Pkg.Prefix) {
 913                         return cmpForNe(len(r.Pkg.Prefix) < len(s.Pkg.Prefix))
 914                 }
 915                 if r.Pkg.Prefix != s.Pkg.Prefix {
 916                         return cmpForNe(r.Pkg.Prefix < s.Pkg.Prefix)
 917                 }
 918         }
 919         if r.Name != s.Name {
 920                 return cmpForNe(r.Name < s.Name)
 921         }
 922         return ssa.CMPeq
 923 }
 924
 925 // cmp compares two *Types t and x, returning ssa.CMPlt,
 926 // ssa.CMPeq, ssa.CMPgt as t<x, t==x, t>x, for an arbitrary
 927 // and optimizer-centric notion of comparison.
 928 func (t *Type) cmp(x *Type) ssa.Cmp {
 929         // This follows the structure of eqtype in subr.go
 930         // with two exceptions.
 931         // 1. Symbols are compared more carefully because a <,=,> result is desired.
 932         // 2. Maps are treated specially to avoid endless recursion -- maps
 933         //    contain an internal data type not expressible in Go source code.
 934         if t == x {
 935                 return ssa.CMPeq
 936         }
 937         if t == nil {
 938                 return ssa.CMPlt
 939         }
 940         if x == nil {
 941                 return ssa.CMPgt
 942         }
 943
 944         if t.Etype != x.Etype {
 945                 return cmpForNe(t.Etype < x.Etype)
 946         }
 947
 948         if t.Sym != nil || x.Sym != nil {
 949                 // Special case: we keep byte and uint8 separate
 950                 // for error messages. Treat them as equal.
 951                 switch t.Etype {
 952                 case TUINT8:
 953                         if (t == Types[TUINT8] || t == bytetype) && (x == Types[TUINT8] || x == bytetype) {
 954                                 return ssa.CMPeq
 955                         }
 956
 957                 case TINT32:
 958                         if (t == Types[runetype.Etype] || t == runetype) && (x == Types[runetype.Etype] || x == runetype) {
 959                                 return ssa.CMPeq
 960                         }
 961                 }
 962         }
 963
 964         if c := t.Sym.cmpsym(x.Sym); c != ssa.CMPeq {
 965                 return c
 966         }
 967
 968         if x.Sym != nil {
 969                 // Syms non-nil, if vargens match then equal.
 970                 if t.Vargen != x.Vargen {
 971                         return cmpForNe(t.Vargen < x.Vargen)
 972                 }
 973                 return ssa.CMPeq
 974         }
 975         // both syms nil, look at structure below.
 976
 977         switch t.Etype {
 978         case TBOOL, TFLOAT32, TFLOAT64, TCOMPLEX64, TCOMPLEX128, TUNSAFEPTR, TUINTPTR,
 979                 TINT8, TINT16, TINT32, TINT64, TINT, TUINT8, TUINT16, TUINT32, TUINT64, TUINT:
 980                 return ssa.CMPeq
 981         }
 982
 983         switch t.Etype {
 984         case TMAP:
 985                 if c := t.Key().cmp(x.Key()); c != ssa.CMPeq {
 986                         return c
 987                 }
 988                 return t.Val().cmp(x.Val())
 989
 990         case TPTR32, TPTR64, TSLICE:
 991                 // No special cases for these, they are handled
 992                 // by the general code after the switch.
 993
 994         case TSTRUCT:
 995                 if t.StructType().Map == nil {
 996                         if x.StructType().Map != nil {
 997                                 return ssa.CMPlt // nil < non-nil
 998                         }
 999                         // to the fallthrough
1000                 } else if x.StructType().Map == nil {
1001                         return ssa.CMPgt // nil > non-nil
1002                 } else if t.StructType().Map.MapType().Bucket == t {
1003                         // Both have non-nil Map
1004                         // Special case for Maps which include a recursive type where the recursion is not broken with a named type
1005                         if x.StructType().Map.MapType().Bucket != x {
1006                                 return ssa.CMPlt // bucket maps are least
1007                         }
1008                         return t.StructType().Map.cmp(x.StructType().Map)
1009                 } else if x.StructType().Map.MapType().Bucket == x {
1010                         return ssa.CMPgt // bucket maps are least
1011                 } // If t != t.Map.Bucket, fall through to general case
1012
1013                 fallthrough
1014         case TINTER:
1015                 t1, ti := iterFields(t)
1016                 x1, xi := iterFields(x)
1017                 for ; t1 != nil && x1 != nil; t1, x1 = ti.Next(), xi.Next() {
1018                         if t1.Embedded != x1.Embedded {
1019                                 return cmpForNe(t1.Embedded < x1.Embedded)
1020                         }
1021                         if t1.Note != x1.Note {
1022                                 return cmpForNe(t1.Note < x1.Note)
1023                         }
1024                         if c := t1.Sym.cmpsym(x1.Sym); c != ssa.CMPeq {
1025                                 return c
1026                         }
1027                         if c := t1.Type.cmp(x1.Type); c != ssa.CMPeq {
1028                                 return c
1029                         }
1030                 }
1031                 if t1 != x1 {
1032                         return cmpForNe(t1 == nil)
1033                 }
1034                 return ssa.CMPeq
1035
1036         case TFUNC:
1037                 for _, f := range recvsParamsResults {
1038                         // Loop over fields in structs, ignoring argument names.
1039                         ta, ia := iterFields(f(t))
1040                         tb, ib := iterFields(f(x))
1041                         for ; ta != nil && tb != nil; ta, tb = ia.Next(), ib.Next() {
1042                                 if ta.Isddd != tb.Isddd {
1043                                         return cmpForNe(!ta.Isddd)
1044                                 }
1045                                 if c := ta.Type.cmp(tb.Type); c != ssa.CMPeq {
1046                                         return c
1047                                 }
1048                         }
1049                         if ta != tb {
1050                                 return cmpForNe(ta == nil)
1051                         }
1052                 }
1053                 return ssa.CMPeq
1054
1055         case TARRAY:
1056                 if t.NumElem() != x.NumElem() {
1057                         return cmpForNe(t.NumElem() < x.NumElem())
1058                 }
1059
1060         case TCHAN:
1061                 if t.ChanDir() != x.ChanDir() {
1062                         return cmpForNe(t.ChanDir() < x.ChanDir())
1063                 }
1064
1065         default:
1066                 e := fmt.Sprintf("Do not know how to compare %v with %v", t, x)
1067                 panic(e)
1068         }
1069
1070         // Common element type comparison for TARRAY, TCHAN, TPTR32, TPTR64, and TSLICE.
1071         return t.Elem().cmp(x.Elem())
1072 }
1073
1074 // IsKind reports whether t is a Type of the specified kind.
1075 func (t *Type) IsKind(et EType) bool {
1076         return t != nil && t.Etype == et
1077 }
1078
1079 func (t *Type) IsBoolean() bool {
1080         return t.Etype == TBOOL
1081 }
1082
1083 var unsignedEType = [...]EType{
1084         TINT8:    TUINT8,
1085         TUINT8:   TUINT8,
1086         TINT16:   TUINT16,
1087         TUINT16:  TUINT16,
1088         TINT32:   TUINT32,
1089         TUINT32:  TUINT32,
1090         TINT64:   TUINT64,
1091         TUINT64:  TUINT64,
1092         TINT:     TUINT,
1093         TUINT:    TUINT,
1094         TUINTPTR: TUINTPTR,
1095 }
1096
1097 // toUnsigned returns the unsigned equivalent of integer type t.
1098 func (t *Type) toUnsigned() *Type {
1099         if !t.IsInteger() {
1100                 Fatalf("unsignedType(%v)", t)
1101         }
1102         return Types[unsignedEType[t.Etype]]
1103 }
1104
1105 func (t *Type) IsInteger() bool {
1106         switch t.Etype {
1107         case TINT8, TUINT8, TINT16, TUINT16, TINT32, TUINT32, TINT64, TUINT64, TINT, TUINT, TUINTPTR:
1108                 return true
1109         }
1110         return false
1111 }
1112
1113 func (t *Type) IsSigned() bool {
1114         switch t.Etype {
1115         case TINT8, TINT16, TINT32, TINT64, TINT:
1116                 return true
1117         }
1118         return false
1119 }
1120
1121 func (t *Type) IsFloat() bool {
1122         return t.Etype == TFLOAT32 || t.Etype == TFLOAT64
1123 }
1124
1125 func (t *Type) IsComplex() bool {
1126         return t.Etype == TCOMPLEX64 || t.Etype == TCOMPLEX128
1127 }
1128
1129 // IsPtr reports whether t is a regular Go pointer type.
1130 // This does not include unsafe.Pointer.
1131 func (t *Type) IsPtr() bool {
1132         return t.Etype == TPTR32 || t.Etype == TPTR64
1133 }
1134
1135 // IsUnsafePtr reports whether t is an unsafe pointer.
1136 func (t *Type) IsUnsafePtr() bool {
1137         return t.Etype == TUNSAFEPTR
1138 }
1139
1140 // IsPtrShaped reports whether t is represented by a single machine pointer.
1141 // In addition to regular Go pointer types, this includes map, channel, and
1142 // function types and unsafe.Pointer. It does not include array or struct types
1143 // that consist of a single pointer shaped type.
1144 // TODO(mdempsky): Should it? See golang.org/issue/15028.
1145 func (t *Type) IsPtrShaped() bool {
1146         return t.Etype == TPTR32 || t.Etype == TPTR64 || t.Etype == TUNSAFEPTR ||
1147                 t.Etype == TMAP || t.Etype == TCHAN || t.Etype == TFUNC
1148 }
1149
1150 func (t *Type) IsString() bool {
1151         return t.Etype == TSTRING
1152 }
1153
1154 func (t *Type) IsMap() bool {
1155         return t.Etype == TMAP
1156 }
1157
1158 func (t *Type) IsChan() bool {
1159         return t.Etype == TCHAN
1160 }
1161
1162 func (t *Type) IsSlice() bool {
1163         return t.Etype == TSLICE
1164 }
1165
1166 func (t *Type) IsArray() bool {
1167         return t.Etype == TARRAY
1168 }
1169
1170 func (t *Type) IsStruct() bool {
1171         return t.Etype == TSTRUCT
1172 }
1173
1174 func (t *Type) IsInterface() bool {
1175         return t.Etype == TINTER
1176 }
1177
1178 // IsEmptyInterface reports whether t is an empty interface type.
1179 func (t *Type) IsEmptyInterface() bool {
1180         return t.IsInterface() && t.NumFields() == 0
1181 }
1182
1183 func (t *Type) ElemType() ssa.Type {
1184         // TODO(josharian): If Type ever moves to a shared
1185         // internal package, remove this silly wrapper.
1186         return t.Elem()
1187 }
1188 func (t *Type) PtrTo() ssa.Type {
1189         return ptrto(t)
1190 }
1191
1192 func (t *Type) NumFields() int {
1193         return t.Fields().Len()
1194 }
1195 func (t *Type) FieldType(i int) ssa.Type {
1196         return t.Field(i).Type
1197 }
1198 func (t *Type) FieldOff(i int) int64 {
1199         return t.Field(i).Offset
1200 }
1201 func (t *Type) FieldName(i int) string {
1202         return t.Field(i).Sym.Name
1203 }
1204
1205 func (t *Type) NumElem() int64 {
1206         t.wantEtype(TARRAY)
1207         at := t.Extra.(*ArrayType)
1208         if at.Bound < 0 {
1209                 Fatalf("NumElem array %v does not have bound yet", t)
1210         }
1211         return at.Bound
1212 }
1213
1214 // SetNumElem sets the number of elements in an array type.
1215 // The only allowed use is on array types created with typDDDArray.
1216 // For other uses, create a new array with typArray instead.
1217 func (t *Type) SetNumElem(n int64) {
1218         t.wantEtype(TARRAY)
1219         at := t.Extra.(*ArrayType)
1220         if at.Bound >= 0 {
1221                 Fatalf("SetNumElem array %v already has bound %d", t, at.Bound)
1222         }
1223         at.Bound = n
1224 }
1225
1226 // ChanDir returns the direction of a channel type t.
1227 // The direction will be one of Crecv, Csend, or Cboth.
1228 func (t *Type) ChanDir() ChanDir {
1229         t.wantEtype(TCHAN)
1230         return t.Extra.(*ChanType).Dir
1231 }
1232
1233 func (t *Type) IsMemory() bool { return false }
1234 func (t *Type) IsFlags() bool  { return false }
1235 func (t *Type) IsVoid() bool   { return false }
1236 func (t *Type) IsTuple() bool  { return false }
1237
1238 // IsUntyped reports whether t is an untyped type.
1239 func (t *Type) IsUntyped() bool {
1240         if t == nil {
1241                 return false
1242         }
1243         if t == idealstring || t == idealbool {
1244                 return true
1245         }
1246         switch t.Etype {
1247         case TNIL, TIDEAL:
1248                 return true
1249         }
1250         return false
1251 }