libgo/go/reflect/type.go

   1 // Copyright 2009 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 reflect implements run-time reflection, allowing a program to
   6 // manipulate objects with arbitrary types.  The typical use is to take a value
   7 // with static type interface{} and extract its dynamic type information by
   8 // calling TypeOf, which returns a Type.
   9 //
  10 // A call to ValueOf returns a Value representing the run-time data.
  11 // Zero takes a Type and returns a Value representing a zero value
  12 // for that type.
  13 //
  14 // See "The Laws of Reflection" for an introduction to reflection in Go:
  15 // http://golang.org/doc/articles/laws_of_reflection.html
  16 package reflect
  17
  18 import (
  19         "strconv"
  20         "sync"
  21         "unsafe"
  22 )
  23
  24 // Type is the representation of a Go type.
  25 //
  26 // Not all methods apply to all kinds of types.  Restrictions,
  27 // if any, are noted in the documentation for each method.
  28 // Use the Kind method to find out the kind of type before
  29 // calling kind-specific methods.  Calling a method
  30 // inappropriate to the kind of type causes a run-time panic.
  31 type Type interface {
  32         // Methods applicable to all types.
  33
  34         // Align returns the alignment in bytes of a value of
  35         // this type when allocated in memory.
  36         Align() int
  37
  38         // FieldAlign returns the alignment in bytes of a value of
  39         // this type when used as a field in a struct.
  40         FieldAlign() int
  41
  42         // Method returns the i'th method in the type's method set.
  43         // It panics if i is not in the range [0, NumMethod()).
  44         //
  45         // For a non-interface type T or *T, the returned Method's Type and Func
  46         // fields describe a function whose first argument is the receiver.
  47         //
  48         // For an interface type, the returned Method's Type field gives the
  49         // method signature, without a receiver, and the Func field is nil.
  50         Method(int) Method
  51
  52         // MethodByName returns the method with that name in the type's
  53         // method set and a boolean indicating if the method was found.
  54         //
  55         // For a non-interface type T or *T, the returned Method's Type and Func
  56         // fields describe a function whose first argument is the receiver.
  57         //
  58         // For an interface type, the returned Method's Type field gives the
  59         // method signature, without a receiver, and the Func field is nil.
  60         MethodByName(string) (Method, bool)
  61
  62         // NumMethod returns the number of methods in the type's method set.
  63         NumMethod() int
  64
  65         // Name returns the type's name within its package.
  66         // It returns an empty string for unnamed types.
  67         Name() string
  68
  69         // PkgPath returns a named type's package path, that is, the import path
  70         // that uniquely identifies the package, such as "encoding/base64".
  71         // If the type was predeclared (string, error) or unnamed (*T, struct{}, []int),
  72         // the package path will be the empty string.
  73         PkgPath() string
  74
  75         // Size returns the number of bytes needed to store
  76         // a value of the given type; it is analogous to unsafe.Sizeof.
  77         Size() uintptr
  78
  79         // String returns a string representation of the type.
  80         // The string representation may use shortened package names
  81         // (e.g., base64 instead of "encoding/base64") and is not
  82         // guaranteed to be unique among types.  To test for equality,
  83         // compare the Types directly.
  84         String() string
  85
  86         // Used internally by gccgo--the string retaining quoting.
  87         rawString() string
  88
  89         // Kind returns the specific kind of this type.
  90         Kind() Kind
  91
  92         // Implements returns true if the type implements the interface type u.
  93         Implements(u Type) bool
  94
  95         // AssignableTo returns true if a value of the type is assignable to type u.
  96         AssignableTo(u Type) bool
  97
  98         // ConvertibleTo returns true if a value of the type is convertible to type u.
  99         ConvertibleTo(u Type) bool
 100
 101         // Methods applicable only to some types, depending on Kind.
 102         // The methods allowed for each kind are:
 103         //
 104         //      Int*, Uint*, Float*, Complex*: Bits
 105         //      Array: Elem, Len
 106         //      Chan: ChanDir, Elem
 107         //      Func: In, NumIn, Out, NumOut, IsVariadic.
 108         //      Map: Key, Elem
 109         //      Ptr: Elem
 110         //      Slice: Elem
 111         //      Struct: Field, FieldByIndex, FieldByName, FieldByNameFunc, NumField
 112
 113         // Bits returns the size of the type in bits.
 114         // It panics if the type's Kind is not one of the
 115         // sized or unsized Int, Uint, Float, or Complex kinds.
 116         Bits() int
 117
 118         // ChanDir returns a channel type's direction.
 119         // It panics if the type's Kind is not Chan.
 120         ChanDir() ChanDir
 121
 122         // IsVariadic returns true if a function type's final input parameter
 123         // is a "..." parameter.  If so, t.In(t.NumIn() - 1) returns the parameter's
 124         // implicit actual type []T.
 125         //
 126         // For concreteness, if t represents func(x int, y ... float64), then
 127         //
 128         //      t.NumIn() == 2
 129         //      t.In(0) is the reflect.Type for "int"
 130         //      t.In(1) is the reflect.Type for "[]float64"
 131         //      t.IsVariadic() == true
 132         //
 133         // IsVariadic panics if the type's Kind is not Func.
 134         IsVariadic() bool
 135
 136         // Elem returns a type's element type.
 137         // It panics if the type's Kind is not Array, Chan, Map, Ptr, or Slice.
 138         Elem() Type
 139
 140         // Field returns a struct type's i'th field.
 141         // It panics if the type's Kind is not Struct.
 142         // It panics if i is not in the range [0, NumField()).
 143         Field(i int) StructField
 144
 145         // FieldByIndex returns the nested field corresponding
 146         // to the index sequence.  It is equivalent to calling Field
 147         // successively for each index i.
 148         // It panics if the type's Kind is not Struct.
 149         FieldByIndex(index []int) StructField
 150
 151         // FieldByName returns the struct field with the given name
 152         // and a boolean indicating if the field was found.
 153         FieldByName(name string) (StructField, bool)
 154
 155         // FieldByNameFunc returns the first struct field with a name
 156         // that satisfies the match function and a boolean indicating if
 157         // the field was found.
 158         FieldByNameFunc(match func(string) bool) (StructField, bool)
 159
 160         // In returns the type of a function type's i'th input parameter.
 161         // It panics if the type's Kind is not Func.
 162         // It panics if i is not in the range [0, NumIn()).
 163         In(i int) Type
 164
 165         // Key returns a map type's key type.
 166         // It panics if the type's Kind is not Map.
 167         Key() Type
 168
 169         // Len returns an array type's length.
 170         // It panics if the type's Kind is not Array.
 171         Len() int
 172
 173         // NumField returns a struct type's field count.
 174         // It panics if the type's Kind is not Struct.
 175         NumField() int
 176
 177         // NumIn returns a function type's input parameter count.
 178         // It panics if the type's Kind is not Func.
 179         NumIn() int
 180
 181         // NumOut returns a function type's output parameter count.
 182         // It panics if the type's Kind is not Func.
 183         NumOut() int
 184
 185         // Out returns the type of a function type's i'th output parameter.
 186         // It panics if the type's Kind is not Func.
 187         // It panics if i is not in the range [0, NumOut()).
 188         Out(i int) Type
 189
 190         common() *rtype
 191         uncommon() *uncommonType
 192 }
 193
 194 /*
 195  * These data structures are known to the compiler (../../cmd/gc/reflect.c).
 196  * A few are known to ../runtime/type.go to convey to debuggers.
 197  * They are also known to ../runtime/type.h.
 198  */
 199
 200 // A Kind represents the specific kind of type that a Type represents.
 201 // The zero Kind is not a valid kind.
 202 type Kind uint
 203
 204 const (
 205         Invalid Kind = iota
 206         Bool
 207         Int
 208         Int8
 209         Int16
 210         Int32
 211         Int64
 212         Uint
 213         Uint8
 214         Uint16
 215         Uint32
 216         Uint64
 217         Uintptr
 218         Float32
 219         Float64
 220         Complex64
 221         Complex128
 222         Array
 223         Chan
 224         Func
 225         Interface
 226         Map
 227         Ptr
 228         Slice
 229         String
 230         Struct
 231         UnsafePointer
 232 )
 233
 234 // rtype is the common implementation of most values.
 235 // It is embedded in other, public struct types, but always
 236 // with a unique tag like `reflect:"array"` or `reflect:"ptr"`
 237 // so that code cannot convert from, say, *arrayType to *ptrType.
 238 type rtype struct {
 239         kind       uint8   // enumeration for C
 240         align      int8    // alignment of variable with this type
 241         fieldAlign uint8   // alignment of struct field with this type
 242         _          uint8   // unused/padding
 243         size       uintptr // size in bytes
 244         hash       uint32  // hash of type; avoids computation in hash tables
 245
 246         hashfn  func(unsafe.Pointer, uintptr)                 // hash function
 247         equalfn func(unsafe.Pointer, unsafe.Pointer, uintptr) // equality function
 248
 249         string        *string // string form; unnecessary  but undeniably useful
 250         *uncommonType         // (relatively) uncommon fields
 251         ptrToThis     *rtype  // type for pointer to this type, if used in binary or has methods
 252 }
 253
 254 // Method on non-interface type
 255 type method struct {
 256         name    *string        // name of method
 257         pkgPath *string        // nil for exported Names; otherwise import path
 258         mtyp    *rtype         // method type (without receiver)
 259         typ     *rtype         // .(*FuncType) underneath (with receiver)
 260         tfn     unsafe.Pointer // fn used for normal method call
 261 }
 262
 263 // uncommonType is present only for types with names or methods
 264 // (if T is a named type, the uncommonTypes for T and *T have methods).
 265 // Using a pointer to this struct reduces the overall size required
 266 // to describe an unnamed type with no methods.
 267 type uncommonType struct {
 268         name    *string  // name of type
 269         pkgPath *string  // import path; nil for built-in types like int, string
 270         methods []method // methods associated with type
 271 }
 272
 273 // ChanDir represents a channel type's direction.
 274 type ChanDir int
 275
 276 const (
 277         RecvDir ChanDir             = 1 << iota // <-chan
 278         SendDir                                 // chan<-
 279         BothDir = RecvDir | SendDir             // chan
 280 )
 281
 282 // arrayType represents a fixed array type.
 283 type arrayType struct {
 284         rtype `reflect:"array"`
 285         elem  *rtype // array element type
 286         slice *rtype // slice type
 287         len   uintptr
 288 }
 289
 290 // chanType represents a channel type.
 291 type chanType struct {
 292         rtype `reflect:"chan"`
 293         elem  *rtype  // channel element type
 294         dir   uintptr // channel direction (ChanDir)
 295 }
 296
 297 // funcType represents a function type.
 298 type funcType struct {
 299         rtype     `reflect:"func"`
 300         dotdotdot bool     // last input parameter is ...
 301         in        []*rtype // input parameter types
 302         out       []*rtype // output parameter types
 303 }
 304
 305 // imethod represents a method on an interface type
 306 type imethod struct {
 307         name    *string // name of method
 308         pkgPath *string // nil for exported Names; otherwise import path
 309         typ     *rtype  // .(*FuncType) underneath
 310 }
 311
 312 // interfaceType represents an interface type.
 313 type interfaceType struct {
 314         rtype   `reflect:"interface"`
 315         methods []imethod // sorted by hash
 316 }
 317
 318 // mapType represents a map type.
 319 type mapType struct {
 320         rtype `reflect:"map"`
 321         key   *rtype // map key type
 322         elem  *rtype // map element (value) type
 323 }
 324
 325 // ptrType represents a pointer type.
 326 type ptrType struct {
 327         rtype `reflect:"ptr"`
 328         elem  *rtype // pointer element (pointed at) type
 329 }
 330
 331 // sliceType represents a slice type.
 332 type sliceType struct {
 333         rtype `reflect:"slice"`
 334         elem  *rtype // slice element type
 335 }
 336
 337 // Struct field
 338 type structField struct {
 339         name    *string // nil for embedded fields
 340         pkgPath *string // nil for exported Names; otherwise import path
 341         typ     *rtype  // type of field
 342         tag     *string // nil if no tag
 343         offset  uintptr // byte offset of field within struct
 344 }
 345
 346 // structType represents a struct type.
 347 type structType struct {
 348         rtype  `reflect:"struct"`
 349         fields []structField // sorted by offset
 350 }
 351
 352 /*
 353  * The compiler knows the exact layout of all the data structures above.
 354  * The compiler does not know about the data structures and methods below.
 355  */
 356
 357 // Method represents a single method.
 358 type Method struct {
 359         // Name is the method name.
 360         // PkgPath is the package path that qualifies a lower case (unexported)
 361         // method name.  It is empty for upper case (exported) method names.
 362         // The combination of PkgPath and Name uniquely identifies a method
 363         // in a method set.
 364         // See http://golang.org/ref/spec#Uniqueness_of_identifiers
 365         Name    string
 366         PkgPath string
 367
 368         Type  Type  // method type
 369         Func  Value // func with receiver as first argument
 370         Index int   // index for Type.Method
 371 }
 372
 373 // High bit says whether type has
 374 // embedded pointers,to help garbage collector.
 375 const kindMask = 0x7f
 376
 377 func (k Kind) String() string {
 378         if int(k) < len(kindNames) {
 379                 return kindNames[k]
 380         }
 381         return "kind" + strconv.Itoa(int(k))
 382 }
 383
 384 var kindNames = []string{
 385         Invalid:       "invalid",
 386         Bool:          "bool",
 387         Int:           "int",
 388         Int8:          "int8",
 389         Int16:         "int16",
 390         Int32:         "int32",
 391         Int64:         "int64",
 392         Uint:          "uint",
 393         Uint8:         "uint8",
 394         Uint16:        "uint16",
 395         Uint32:        "uint32",
 396         Uint64:        "uint64",
 397         Uintptr:       "uintptr",
 398         Float32:       "float32",
 399         Float64:       "float64",
 400         Complex64:     "complex64",
 401         Complex128:    "complex128",
 402         Array:         "array",
 403         Chan:          "chan",
 404         Func:          "func",
 405         Interface:     "interface",
 406         Map:           "map",
 407         Ptr:           "ptr",
 408         Slice:         "slice",
 409         String:        "string",
 410         Struct:        "struct",
 411         UnsafePointer: "unsafe.Pointer",
 412 }
 413
 414 func (t *uncommonType) uncommon() *uncommonType {
 415         return t
 416 }
 417
 418 func (t *uncommonType) PkgPath() string {
 419         if t == nil || t.pkgPath == nil {
 420                 return ""
 421         }
 422         return *t.pkgPath
 423 }
 424
 425 func (t *uncommonType) Name() string {
 426         if t == nil || t.name == nil {
 427                 return ""
 428         }
 429         return *t.name
 430 }
 431
 432 func (t *rtype) rawString() string { return *t.string }
 433
 434 func (t *rtype) String() string {
 435         // For gccgo, strip out quoted strings.
 436         s := *t.string
 437         var q bool
 438         r := make([]byte, len(s))
 439         j := 0
 440         for i := 0; i < len(s); i++ {
 441                 if s[i] == '\t' {
 442                         q = !q
 443                 } else if !q {
 444                         r[j] = s[i]
 445                         j++
 446                 }
 447         }
 448         return string(r[:j])
 449 }
 450
 451 func (t *rtype) Size() uintptr { return t.size }
 452
 453 func (t *rtype) Bits() int {
 454         if t == nil {
 455                 panic("reflect: Bits of nil Type")
 456         }
 457         k := t.Kind()
 458         if k < Int || k > Complex128 {
 459                 panic("reflect: Bits of non-arithmetic Type " + t.String())
 460         }
 461         return int(t.size) * 8
 462 }
 463
 464 func (t *rtype) Align() int { return int(t.align) }
 465
 466 func (t *rtype) FieldAlign() int { return int(t.fieldAlign) }
 467
 468 func (t *rtype) Kind() Kind { return Kind(t.kind & kindMask) }
 469
 470 func (t *rtype) common() *rtype { return t }
 471
 472 func (t *uncommonType) Method(i int) (m Method) {
 473         if t == nil || i < 0 || i >= len(t.methods) {
 474                 panic("reflect: Method index out of range")
 475         }
 476         p := &t.methods[i]
 477         if p.name != nil {
 478                 m.Name = *p.name
 479         }
 480         fl := flag(Func) << flagKindShift
 481         if p.pkgPath != nil {
 482                 m.PkgPath = *p.pkgPath
 483                 fl |= flagRO
 484         }
 485         mt := p.typ
 486         m.Type = toType(mt)
 487         x := new(unsafe.Pointer)
 488         *x = p.tfn
 489         m.Func = Value{mt, unsafe.Pointer(x), fl | flagIndir}
 490         m.Index = i
 491         return
 492 }
 493
 494 func (t *uncommonType) NumMethod() int {
 495         if t == nil {
 496                 return 0
 497         }
 498         return len(t.methods)
 499 }
 500
 501 func (t *uncommonType) MethodByName(name string) (m Method, ok bool) {
 502         if t == nil {
 503                 return
 504         }
 505         var p *method
 506         for i := range t.methods {
 507                 p = &t.methods[i]
 508                 if p.name != nil && *p.name == name {
 509                         return t.Method(i), true
 510                 }
 511         }
 512         return
 513 }
 514
 515 // TODO(rsc): 6g supplies these, but they are not
 516 // as efficient as they could be: they have commonType
 517 // as the receiver instead of *rtype.
 518 func (t *rtype) NumMethod() int {
 519         if t.Kind() == Interface {
 520                 tt := (*interfaceType)(unsafe.Pointer(t))
 521                 return tt.NumMethod()
 522         }
 523         return t.uncommonType.NumMethod()
 524 }
 525
 526 func (t *rtype) Method(i int) (m Method) {
 527         if t.Kind() == Interface {
 528                 tt := (*interfaceType)(unsafe.Pointer(t))
 529                 return tt.Method(i)
 530         }
 531         return t.uncommonType.Method(i)
 532 }
 533
 534 func (t *rtype) MethodByName(name string) (m Method, ok bool) {
 535         if t.Kind() == Interface {
 536                 tt := (*interfaceType)(unsafe.Pointer(t))
 537                 return tt.MethodByName(name)
 538         }
 539         return t.uncommonType.MethodByName(name)
 540 }
 541
 542 func (t *rtype) PkgPath() string {
 543         return t.uncommonType.PkgPath()
 544 }
 545
 546 func (t *rtype) Name() string {
 547         return t.uncommonType.Name()
 548 }
 549
 550 func (t *rtype) ChanDir() ChanDir {
 551         if t.Kind() != Chan {
 552                 panic("reflect: ChanDir of non-chan type")
 553         }
 554         tt := (*chanType)(unsafe.Pointer(t))
 555         return ChanDir(tt.dir)
 556 }
 557
 558 func (t *rtype) IsVariadic() bool {
 559         if t.Kind() != Func {
 560                 panic("reflect: IsVariadic of non-func type")
 561         }
 562         tt := (*funcType)(unsafe.Pointer(t))
 563         return tt.dotdotdot
 564 }
 565
 566 func (t *rtype) Elem() Type {
 567         switch t.Kind() {
 568         case Array:
 569                 tt := (*arrayType)(unsafe.Pointer(t))
 570                 return toType(tt.elem)
 571         case Chan:
 572                 tt := (*chanType)(unsafe.Pointer(t))
 573                 return toType(tt.elem)
 574         case Map:
 575                 tt := (*mapType)(unsafe.Pointer(t))
 576                 return toType(tt.elem)
 577         case Ptr:
 578                 tt := (*ptrType)(unsafe.Pointer(t))
 579                 return toType(tt.elem)
 580         case Slice:
 581                 tt := (*sliceType)(unsafe.Pointer(t))
 582                 return toType(tt.elem)
 583         }
 584         panic("reflect: Elem of invalid type")
 585 }
 586
 587 func (t *rtype) Field(i int) StructField {
 588         if t.Kind() != Struct {
 589                 panic("reflect: Field of non-struct type")
 590         }
 591         tt := (*structType)(unsafe.Pointer(t))
 592         return tt.Field(i)
 593 }
 594
 595 func (t *rtype) FieldByIndex(index []int) StructField {
 596         if t.Kind() != Struct {
 597                 panic("reflect: FieldByIndex of non-struct type")
 598         }
 599         tt := (*structType)(unsafe.Pointer(t))
 600         return tt.FieldByIndex(index)
 601 }
 602
 603 func (t *rtype) FieldByName(name string) (StructField, bool) {
 604         if t.Kind() != Struct {
 605                 panic("reflect: FieldByName of non-struct type")
 606         }
 607         tt := (*structType)(unsafe.Pointer(t))
 608         return tt.FieldByName(name)
 609 }
 610
 611 func (t *rtype) FieldByNameFunc(match func(string) bool) (StructField, bool) {
 612         if t.Kind() != Struct {
 613                 panic("reflect: FieldByNameFunc of non-struct type")
 614         }
 615         tt := (*structType)(unsafe.Pointer(t))
 616         return tt.FieldByNameFunc(match)
 617 }
 618
 619 func (t *rtype) In(i int) Type {
 620         if t.Kind() != Func {
 621                 panic("reflect: In of non-func type")
 622         }
 623         tt := (*funcType)(unsafe.Pointer(t))
 624         return toType(tt.in[i])
 625 }
 626
 627 func (t *rtype) Key() Type {
 628         if t.Kind() != Map {
 629                 panic("reflect: Key of non-map type")
 630         }
 631         tt := (*mapType)(unsafe.Pointer(t))
 632         return toType(tt.key)
 633 }
 634
 635 func (t *rtype) Len() int {
 636         if t.Kind() != Array {
 637                 panic("reflect: Len of non-array type")
 638         }
 639         tt := (*arrayType)(unsafe.Pointer(t))
 640         return int(tt.len)
 641 }
 642
 643 func (t *rtype) NumField() int {
 644         if t.Kind() != Struct {
 645                 panic("reflect: NumField of non-struct type")
 646         }
 647         tt := (*structType)(unsafe.Pointer(t))
 648         return len(tt.fields)
 649 }
 650
 651 func (t *rtype) NumIn() int {
 652         if t.Kind() != Func {
 653                 panic("reflect: NumIn of non-func type")
 654         }
 655         tt := (*funcType)(unsafe.Pointer(t))
 656         return len(tt.in)
 657 }
 658
 659 func (t *rtype) NumOut() int {
 660         if t.Kind() != Func {
 661                 panic("reflect: NumOut of non-func type")
 662         }
 663         tt := (*funcType)(unsafe.Pointer(t))
 664         return len(tt.out)
 665 }
 666
 667 func (t *rtype) Out(i int) Type {
 668         if t.Kind() != Func {
 669                 panic("reflect: Out of non-func type")
 670         }
 671         tt := (*funcType)(unsafe.Pointer(t))
 672         return toType(tt.out[i])
 673 }
 674
 675 func (d ChanDir) String() string {
 676         switch d {
 677         case SendDir:
 678                 return "chan<-"
 679         case RecvDir:
 680                 return "<-chan"
 681         case BothDir:
 682                 return "chan"
 683         }
 684         return "ChanDir" + strconv.Itoa(int(d))
 685 }
 686
 687 // Method returns the i'th method in the type's method set.
 688 func (t *interfaceType) Method(i int) (m Method) {
 689         if i < 0 || i >= len(t.methods) {
 690                 return
 691         }
 692         p := &t.methods[i]
 693         m.Name = *p.name
 694         if p.pkgPath != nil {
 695                 m.PkgPath = *p.pkgPath
 696         }
 697         m.Type = toType(p.typ)
 698         m.Index = i
 699         return
 700 }
 701
 702 // NumMethod returns the number of interface methods in the type's method set.
 703 func (t *interfaceType) NumMethod() int { return len(t.methods) }
 704
 705 // MethodByName method with the given name in the type's method set.
 706 func (t *interfaceType) MethodByName(name string) (m Method, ok bool) {
 707         if t == nil {
 708                 return
 709         }
 710         var p *imethod
 711         for i := range t.methods {
 712                 p = &t.methods[i]
 713                 if *p.name == name {
 714                         return t.Method(i), true
 715                 }
 716         }
 717         return
 718 }
 719
 720 // A StructField describes a single field in a struct.
 721 type StructField struct {
 722         // Name is the field name.
 723         // PkgPath is the package path that qualifies a lower case (unexported)
 724         // field name.  It is empty for upper case (exported) field names.
 725         // See http://golang.org/ref/spec#Uniqueness_of_identifiers
 726         Name    string
 727         PkgPath string
 728
 729         Type      Type      // field type
 730         Tag       StructTag // field tag string
 731         Offset    uintptr   // offset within struct, in bytes
 732         Index     []int     // index sequence for Type.FieldByIndex
 733         Anonymous bool      // is an anonymous field
 734 }
 735
 736 // A StructTag is the tag string in a struct field.
 737 //
 738 // By convention, tag strings are a concatenation of
 739 // optionally space-separated key:"value" pairs.
 740 // Each key is a non-empty string consisting of non-control
 741 // characters other than space (U+0020 ' '), quote (U+0022 '"'),
 742 // and colon (U+003A ':').  Each value is quoted using U+0022 '"'
 743 // characters and Go string literal syntax.
 744 type StructTag string
 745
 746 // Get returns the value associated with key in the tag string.
 747 // If there is no such key in the tag, Get returns the empty string.
 748 // If the tag does not have the conventional format, the value
 749 // returned by Get is unspecified.
 750 func (tag StructTag) Get(key string) string {
 751         for tag != "" {
 752                 // skip leading space
 753                 i := 0
 754                 for i < len(tag) && tag[i] == ' ' {
 755                         i++
 756                 }
 757                 tag = tag[i:]
 758                 if tag == "" {
 759                         break
 760                 }
 761
 762                 // scan to colon.
 763                 // a space or a quote is a syntax error
 764                 i = 0
 765                 for i < len(tag) && tag[i] != ' ' && tag[i] != ':' && tag[i] != '"' {
 766                         i++
 767                 }
 768                 if i+1 >= len(tag) || tag[i] != ':' || tag[i+1] != '"' {
 769                         break
 770                 }
 771                 name := string(tag[:i])
 772                 tag = tag[i+1:]
 773
 774                 // scan quoted string to find value
 775                 i = 1
 776                 for i < len(tag) && tag[i] != '"' {
 777                         if tag[i] == '\\' {
 778                                 i++
 779                         }
 780                         i++
 781                 }
 782                 if i >= len(tag) {
 783                         break
 784                 }
 785                 qvalue := string(tag[:i+1])
 786                 tag = tag[i+1:]
 787
 788                 if key == name {
 789                         value, _ := strconv.Unquote(qvalue)
 790                         return value
 791                 }
 792         }
 793         return ""
 794 }
 795
 796 // Field returns the i'th struct field.
 797 func (t *structType) Field(i int) (f StructField) {
 798         if i < 0 || i >= len(t.fields) {
 799                 return
 800         }
 801         p := &t.fields[i]
 802         f.Type = toType(p.typ)
 803         if p.name != nil {
 804                 f.Name = *p.name
 805         } else {
 806                 t := f.Type
 807                 if t.Kind() == Ptr {
 808                         t = t.Elem()
 809                 }
 810                 f.Name = t.Name()
 811                 f.Anonymous = true
 812         }
 813         if p.pkgPath != nil {
 814                 f.PkgPath = *p.pkgPath
 815         }
 816         if p.tag != nil {
 817                 f.Tag = StructTag(*p.tag)
 818         }
 819         f.Offset = p.offset
 820
 821         // NOTE(rsc): This is the only allocation in the interface
 822         // presented by a reflect.Type.  It would be nice to avoid,
 823         // at least in the common cases, but we need to make sure
 824         // that misbehaving clients of reflect cannot affect other
 825         // uses of reflect.  One possibility is CL 5371098, but we
 826         // postponed that ugliness until there is a demonstrated
 827         // need for the performance.  This is issue 2320.
 828         f.Index = []int{i}
 829         return
 830 }
 831
 832 // TODO(gri): Should there be an error/bool indicator if the index
 833 //            is wrong for FieldByIndex?
 834
 835 // FieldByIndex returns the nested field corresponding to index.
 836 func (t *structType) FieldByIndex(index []int) (f StructField) {
 837         f.Type = toType(&t.rtype)
 838         for i, x := range index {
 839                 if i > 0 {
 840                         ft := f.Type
 841                         if ft.Kind() == Ptr && ft.Elem().Kind() == Struct {
 842                                 ft = ft.Elem()
 843                         }
 844                         f.Type = ft
 845                 }
 846                 f = f.Type.Field(x)
 847         }
 848         return
 849 }
 850
 851 // A fieldScan represents an item on the fieldByNameFunc scan work list.
 852 type fieldScan struct {
 853         typ   *structType
 854         index []int
 855 }
 856
 857 // FieldByNameFunc returns the struct field with a name that satisfies the
 858 // match function and a boolean to indicate if the field was found.
 859 func (t *structType) FieldByNameFunc(match func(string) bool) (result StructField, ok bool) {
 860         // This uses the same condition that the Go language does: there must be a unique instance
 861         // of the match at a given depth level. If there are multiple instances of a match at the
 862         // same depth, they annihilate each other and inhibit any possible match at a lower level.
 863         // The algorithm is breadth first search, one depth level at a time.
 864
 865         // The current and next slices are work queues:
 866         // current lists the fields to visit on this depth level,
 867         // and next lists the fields on the next lower level.
 868         current := []fieldScan{}
 869         next := []fieldScan{{typ: t}}
 870
 871         // nextCount records the number of times an embedded type has been
 872         // encountered and considered for queueing in the 'next' slice.
 873         // We only queue the first one, but we increment the count on each.
 874         // If a struct type T can be reached more than once at a given depth level,
 875         // then it annihilates itself and need not be considered at all when we
 876         // process that next depth level.
 877         var nextCount map[*structType]int
 878
 879         // visited records the structs that have been considered already.
 880         // Embedded pointer fields can create cycles in the graph of
 881         // reachable embedded types; visited avoids following those cycles.
 882         // It also avoids duplicated effort: if we didn't find the field in an
 883         // embedded type T at level 2, we won't find it in one at level 4 either.
 884         visited := map[*structType]bool{}
 885
 886         for len(next) > 0 {
 887                 current, next = next, current[:0]
 888                 count := nextCount
 889                 nextCount = nil
 890
 891                 // Process all the fields at this depth, now listed in 'current'.
 892                 // The loop queues embedded fields found in 'next', for processing during the next
 893                 // iteration. The multiplicity of the 'current' field counts is recorded
 894                 // in 'count'; the multiplicity of the 'next' field counts is recorded in 'nextCount'.
 895                 for _, scan := range current {
 896                         t := scan.typ
 897                         if visited[t] {
 898                                 // We've looked through this type before, at a higher level.
 899                                 // That higher level would shadow the lower level we're now at,
 900                                 // so this one can't be useful to us. Ignore it.
 901                                 continue
 902                         }
 903                         visited[t] = true
 904                         for i := range t.fields {
 905                                 f := &t.fields[i]
 906                                 // Find name and type for field f.
 907                                 var fname string
 908                                 var ntyp *rtype
 909                                 if f.name != nil {
 910                                         fname = *f.name
 911                                 } else {
 912                                         // Anonymous field of type T or *T.
 913                                         // Name taken from type.
 914                                         ntyp = f.typ
 915                                         if ntyp.Kind() == Ptr {
 916                                                 ntyp = ntyp.Elem().common()
 917                                         }
 918                                         fname = ntyp.Name()
 919                                 }
 920
 921                                 // Does it match?
 922                                 if match(fname) {
 923                                         // Potential match
 924                                         if count[t] > 1 || ok {
 925                                                 // Name appeared multiple times at this level: annihilate.
 926                                                 return StructField{}, false
 927                                         }
 928                                         result = t.Field(i)
 929                                         result.Index = nil
 930                                         result.Index = append(result.Index, scan.index...)
 931                                         result.Index = append(result.Index, i)
 932                                         ok = true
 933                                         continue
 934                                 }
 935
 936                                 // Queue embedded struct fields for processing with next level,
 937                                 // but only if we haven't seen a match yet at this level and only
 938                                 // if the embedded types haven't already been queued.
 939                                 if ok || ntyp == nil || ntyp.Kind() != Struct {
 940                                         continue
 941                                 }
 942                                 ntyp = toType(ntyp).common()
 943                                 styp := (*structType)(unsafe.Pointer(ntyp))
 944                                 if nextCount[styp] > 0 {
 945                                         nextCount[styp] = 2 // exact multiple doesn't matter
 946                                         continue
 947                                 }
 948                                 if nextCount == nil {
 949                                         nextCount = map[*structType]int{}
 950                                 }
 951                                 nextCount[styp] = 1
 952                                 if count[t] > 1 {
 953                                         nextCount[styp] = 2 // exact multiple doesn't matter
 954                                 }
 955                                 var index []int
 956                                 index = append(index, scan.index...)
 957                                 index = append(index, i)
 958                                 next = append(next, fieldScan{styp, index})
 959                         }
 960                 }
 961                 if ok {
 962                         break
 963                 }
 964         }
 965         return
 966 }
 967
 968 // FieldByName returns the struct field with the given name
 969 // and a boolean to indicate if the field was found.
 970 func (t *structType) FieldByName(name string) (f StructField, present bool) {
 971         // Quick check for top-level name, or struct without anonymous fields.
 972         hasAnon := false
 973         if name != "" {
 974                 for i := range t.fields {
 975                         tf := &t.fields[i]
 976                         if tf.name == nil {
 977                                 hasAnon = true
 978                                 continue
 979                         }
 980                         if *tf.name == name {
 981                                 return t.Field(i), true
 982                         }
 983                 }
 984         }
 985         if !hasAnon {
 986                 return
 987         }
 988         return t.FieldByNameFunc(func(s string) bool { return s == name })
 989 }
 990
 991 // TypeOf returns the reflection Type of the value in the interface{}.
 992 // TypeOf(nil) returns nil.
 993 func TypeOf(i interface{}) Type {
 994         eface := *(*emptyInterface)(unsafe.Pointer(&i))
 995         return toType(eface.typ)
 996 }
 997
 998 // ptrMap is the cache for PtrTo.
 999 var ptrMap struct {
1000         sync.RWMutex
1001         m map[*rtype]*ptrType
1002 }
1003
1004 // PtrTo returns the pointer type with element t.
1005 // For example, if t represents type Foo, PtrTo(t) represents *Foo.
1006 func PtrTo(t Type) Type {
1007         return t.(*rtype).ptrTo()
1008 }
1009
1010 func (t *rtype) ptrTo() *rtype {
1011         if p := t.ptrToThis; p != nil {
1012                 return p
1013         }
1014
1015         // Otherwise, synthesize one.
1016         // This only happens for pointers with no methods.
1017         // We keep the mapping in a map on the side, because
1018         // this operation is rare and a separate map lets us keep
1019         // the type structures in read-only memory.
1020         ptrMap.RLock()
1021         if m := ptrMap.m; m != nil {
1022                 if p := m[t]; p != nil {
1023                         ptrMap.RUnlock()
1024                         return &p.rtype
1025                 }
1026         }
1027         ptrMap.RUnlock()
1028         ptrMap.Lock()
1029         if ptrMap.m == nil {
1030                 ptrMap.m = make(map[*rtype]*ptrType)
1031         }
1032         p := ptrMap.m[t]
1033         if p != nil {
1034                 // some other goroutine won the race and created it
1035                 ptrMap.Unlock()
1036                 return &p.rtype
1037         }
1038
1039         s := "*" + *t.string
1040
1041         canonicalTypeLock.RLock()
1042         r, ok := canonicalType[s]
1043         canonicalTypeLock.RUnlock()
1044         if ok {
1045                 ptrMap.m[t] = (*ptrType)(unsafe.Pointer(r.(*rtype)))
1046                 ptrMap.Unlock()
1047                 return r.(*rtype)
1048         }
1049
1050         // initialize p using *byte's ptrType as a prototype.
1051         p = new(ptrType)
1052         var iptr interface{} = (*unsafe.Pointer)(nil)
1053         prototype := *(**ptrType)(unsafe.Pointer(&iptr))
1054         *p = *prototype
1055
1056         p.string = &s
1057
1058         // For the type structures linked into the binary, the
1059         // compiler provides a good hash of the string.
1060         // Create a good hash for the new string by using
1061         // the FNV-1 hash's mixing function to combine the
1062         // old hash and the new "*".
1063         // p.hash = fnv1(t.hash, '*')
1064         // This is the gccgo version.
1065         p.hash = (t.hash << 4) + 9
1066
1067         p.uncommonType = nil
1068         p.ptrToThis = nil
1069         p.elem = t
1070
1071         q := canonicalize(&p.rtype)
1072         p = (*ptrType)(unsafe.Pointer(q.(*rtype)))
1073
1074         ptrMap.m[t] = p
1075         ptrMap.Unlock()
1076         return &p.rtype
1077 }
1078
1079 // fnv1 incorporates the list of bytes into the hash x using the FNV-1 hash function.
1080 func fnv1(x uint32, list ...byte) uint32 {
1081         for _, b := range list {
1082                 x = x*16777619 ^ uint32(b)
1083         }
1084         return x
1085 }
1086
1087 func (t *rtype) Implements(u Type) bool {
1088         if u == nil {
1089                 panic("reflect: nil type passed to Type.Implements")
1090         }
1091         if u.Kind() != Interface {
1092                 panic("reflect: non-interface type passed to Type.Implements")
1093         }
1094         return implements(u.(*rtype), t)
1095 }
1096
1097 func (t *rtype) AssignableTo(u Type) bool {
1098         if u == nil {
1099                 panic("reflect: nil type passed to Type.AssignableTo")
1100         }
1101         uu := u.(*rtype)
1102         return directlyAssignable(uu, t) || implements(uu, t)
1103 }
1104
1105 func (t *rtype) ConvertibleTo(u Type) bool {
1106         if u == nil {
1107                 panic("reflect: nil type passed to Type.ConvertibleTo")
1108         }
1109         uu := u.(*rtype)
1110         return convertOp(uu, t) != nil
1111 }
1112
1113 // implements returns true if the type V implements the interface type T.
1114 func implements(T, V *rtype) bool {
1115         if T.Kind() != Interface {
1116                 return false
1117         }
1118         t := (*interfaceType)(unsafe.Pointer(T))
1119         if len(t.methods) == 0 {
1120                 return true
1121         }
1122
1123         // The same algorithm applies in both cases, but the
1124         // method tables for an interface type and a concrete type
1125         // are different, so the code is duplicated.
1126         // In both cases the algorithm is a linear scan over the two
1127         // lists - T's methods and V's methods - simultaneously.
1128         // Since method tables are stored in a unique sorted order
1129         // (alphabetical, with no duplicate method names), the scan
1130         // through V's methods must hit a match for each of T's
1131         // methods along the way, or else V does not implement T.
1132         // This lets us run the scan in overall linear time instead of
1133         // the quadratic time  a naive search would require.
1134         // See also ../runtime/iface.c.
1135         if V.Kind() == Interface {
1136                 v := (*interfaceType)(unsafe.Pointer(V))
1137                 i := 0
1138                 for j := 0; j < len(v.methods); j++ {
1139                         tm := &t.methods[i]
1140                         vm := &v.methods[j]
1141                         if *vm.name == *tm.name && (vm.pkgPath == tm.pkgPath || (vm.pkgPath != nil && tm.pkgPath != nil && *vm.pkgPath == *tm.pkgPath)) && toType(vm.typ).common() == toType(tm.typ).common() {
1142                                 if i++; i >= len(t.methods) {
1143                                         return true
1144                                 }
1145                         }
1146                 }
1147                 return false
1148         }
1149
1150         v := V.uncommon()
1151         if v == nil {
1152                 return false
1153         }
1154         i := 0
1155         for j := 0; j < len(v.methods); j++ {
1156                 tm := &t.methods[i]
1157                 vm := &v.methods[j]
1158                 if *vm.name == *tm.name && (vm.pkgPath == tm.pkgPath || (vm.pkgPath != nil && tm.pkgPath != nil && *vm.pkgPath == *tm.pkgPath)) && toType(vm.mtyp).common() == toType(tm.typ).common() {
1159                         if i++; i >= len(t.methods) {
1160                                 return true
1161                         }
1162                 }
1163         }
1164         return false
1165 }
1166
1167 // directlyAssignable returns true if a value x of type V can be directly
1168 // assigned (using memmove) to a value of type T.
1169 // http://golang.org/doc/go_spec.html#Assignability
1170 // Ignoring the interface rules (implemented elsewhere)
1171 // and the ideal constant rules (no ideal constants at run time).
1172 func directlyAssignable(T, V *rtype) bool {
1173         // x's type V is identical to T?
1174         if T == V {
1175                 return true
1176         }
1177
1178         // Otherwise at least one of T and V must be unnamed
1179         // and they must have the same kind.
1180         if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
1181                 return false
1182         }
1183
1184         // x's type T and V must  have identical underlying types.
1185         return haveIdenticalUnderlyingType(T, V)
1186 }
1187
1188 func haveIdenticalUnderlyingType(T, V *rtype) bool {
1189         if T == V {
1190                 return true
1191         }
1192
1193         kind := T.Kind()
1194         if kind != V.Kind() {
1195                 return false
1196         }
1197
1198         // Non-composite types of equal kind have same underlying type
1199         // (the predefined instance of the type).
1200         if Bool <= kind && kind <= Complex128 || kind == String || kind == UnsafePointer {
1201                 return true
1202         }
1203
1204         // Composite types.
1205         switch kind {
1206         case Array:
1207                 return T.Elem() == V.Elem() && T.Len() == V.Len()
1208
1209         case Chan:
1210                 // Special case:
1211                 // x is a bidirectional channel value, T is a channel type,
1212                 // and x's type V and T have identical element types.
1213                 if V.ChanDir() == BothDir && T.Elem() == V.Elem() {
1214                         return true
1215                 }
1216
1217                 // Otherwise continue test for identical underlying type.
1218                 return V.ChanDir() == T.ChanDir() && T.Elem() == V.Elem()
1219
1220         case Func:
1221                 t := (*funcType)(unsafe.Pointer(T))
1222                 v := (*funcType)(unsafe.Pointer(V))
1223                 if t.dotdotdot != v.dotdotdot || len(t.in) != len(v.in) || len(t.out) != len(v.out) {
1224                         return false
1225                 }
1226                 for i, typ := range t.in {
1227                         if typ != v.in[i] {
1228                                 return false
1229                         }
1230                 }
1231                 for i, typ := range t.out {
1232                         if typ != v.out[i] {
1233                                 return false
1234                         }
1235                 }
1236                 return true
1237
1238         case Interface:
1239                 t := (*interfaceType)(unsafe.Pointer(T))
1240                 v := (*interfaceType)(unsafe.Pointer(V))
1241                 if len(t.methods) == 0 && len(v.methods) == 0 {
1242                         return true
1243                 }
1244                 // Might have the same methods but still
1245                 // need a run time conversion.
1246                 return false
1247
1248         case Map:
1249                 return T.Key() == V.Key() && T.Elem() == V.Elem()
1250
1251         case Ptr, Slice:
1252                 return T.Elem() == V.Elem()
1253
1254         case Struct:
1255                 t := (*structType)(unsafe.Pointer(T))
1256                 v := (*structType)(unsafe.Pointer(V))
1257                 if len(t.fields) != len(v.fields) {
1258                         return false
1259                 }
1260                 for i := range t.fields {
1261                         tf := &t.fields[i]
1262                         vf := &v.fields[i]
1263                         if tf.name != vf.name && (tf.name == nil || vf.name == nil || *tf.name != *vf.name) {
1264                                 return false
1265                         }
1266                         if tf.pkgPath != vf.pkgPath && (tf.pkgPath == nil || vf.pkgPath == nil || *tf.pkgPath != *vf.pkgPath) {
1267                                 return false
1268                         }
1269                         if tf.typ != vf.typ {
1270                                 return false
1271                         }
1272                         if tf.tag != vf.tag && (tf.tag == nil || vf.tag == nil || *tf.tag != *vf.tag) {
1273                                 return false
1274                         }
1275                         if tf.offset != vf.offset {
1276                                 return false
1277                         }
1278                 }
1279                 return true
1280         }
1281
1282         return false
1283 }
1284
1285 // The lookupCache caches ChanOf, MapOf, and SliceOf lookups.
1286 var lookupCache struct {
1287         sync.RWMutex
1288         m map[cacheKey]*rtype
1289 }
1290
1291 // A cacheKey is the key for use in the lookupCache.
1292 // Four values describe any of the types we are looking for:
1293 // type kind, one or two subtypes, and an extra integer.
1294 type cacheKey struct {
1295         kind  Kind
1296         t1    *rtype
1297         t2    *rtype
1298         extra uintptr
1299 }
1300
1301 // cacheGet looks for a type under the key k in the lookupCache.
1302 // If it finds one, it returns that type.
1303 // If not, it returns nil with the cache locked.
1304 // The caller is expected to use cachePut to unlock the cache.
1305 func cacheGet(k cacheKey) Type {
1306         lookupCache.RLock()
1307         t := lookupCache.m[k]
1308         lookupCache.RUnlock()
1309         if t != nil {
1310                 return t
1311         }
1312
1313         lookupCache.Lock()
1314         t = lookupCache.m[k]
1315         if t != nil {
1316                 lookupCache.Unlock()
1317                 return t
1318         }
1319
1320         if lookupCache.m == nil {
1321                 lookupCache.m = make(map[cacheKey]*rtype)
1322         }
1323
1324         return nil
1325 }
1326
1327 // cachePut stores the given type in the cache, unlocks the cache,
1328 // and returns the type. It is expected that the cache is locked
1329 // because cacheGet returned nil.
1330 func cachePut(k cacheKey, t *rtype) Type {
1331         t = toType(t).common()
1332         lookupCache.m[k] = t
1333         lookupCache.Unlock()
1334         return t
1335 }
1336
1337 // ChanOf returns the channel type with the given direction and element type.
1338 // For example, if t represents int, ChanOf(RecvDir, t) represents <-chan int.
1339 //
1340 // The gc runtime imposes a limit of 64 kB on channel element types.
1341 // If t's size is equal to or exceeds this limit, ChanOf panics.
1342 func ChanOf(dir ChanDir, t Type) Type {
1343         typ := t.(*rtype)
1344
1345         // Look in cache.
1346         ckey := cacheKey{Chan, typ, nil, uintptr(dir)}
1347         if ch := cacheGet(ckey); ch != nil {
1348                 return ch
1349         }
1350
1351         // This restriction is imposed by the gc compiler and the runtime.
1352         if typ.size >= 1<<16 {
1353                 lookupCache.Unlock()
1354                 panic("reflect.ChanOf: element size too large")
1355         }
1356
1357         // Look in known types.
1358         // TODO: Precedence when constructing string.
1359         var s string
1360         switch dir {
1361         default:
1362                 lookupCache.Unlock()
1363                 panic("reflect.ChanOf: invalid dir")
1364         case SendDir:
1365                 s = "chan<- " + *typ.string
1366         case RecvDir:
1367                 s = "<-chan " + *typ.string
1368         case BothDir:
1369                 s = "chan " + *typ.string
1370         }
1371
1372         // Make a channel type.
1373         var ichan interface{} = (chan unsafe.Pointer)(nil)
1374         prototype := *(**chanType)(unsafe.Pointer(&ichan))
1375         ch := new(chanType)
1376         *ch = *prototype
1377         ch.string = &s
1378
1379         // gccgo uses a different hash.
1380         // ch.hash = fnv1(typ.hash, 'c', byte(dir))
1381         ch.hash = 0
1382         if dir&SendDir != 0 {
1383                 ch.hash += 1
1384         }
1385         if dir&RecvDir != 0 {
1386                 ch.hash += 2
1387         }
1388         ch.hash += typ.hash << 2
1389         ch.hash <<= 3
1390         ch.hash += 15
1391
1392         ch.elem = typ
1393         ch.uncommonType = nil
1394         ch.ptrToThis = nil
1395
1396         return cachePut(ckey, &ch.rtype)
1397 }
1398
1399 // MapOf returns the map type with the given key and element types.
1400 // For example, if k represents int and e represents string,
1401 // MapOf(k, e) represents map[int]string.
1402 //
1403 // If the key type is not a valid map key type (that is, if it does
1404 // not implement Go's == operator), MapOf panics. TODO(rsc).
1405 func MapOf(key, elem Type) Type {
1406         ktyp := key.(*rtype)
1407         etyp := elem.(*rtype)
1408
1409         // TODO: Check for invalid key types.
1410
1411         // Look in cache.
1412         ckey := cacheKey{Map, ktyp, etyp, 0}
1413         if mt := cacheGet(ckey); mt != nil {
1414                 return mt
1415         }
1416
1417         // Look in known types.
1418         s := "map[" + *ktyp.string + "]" + *etyp.string
1419
1420         // Make a map type.
1421         var imap interface{} = (map[unsafe.Pointer]unsafe.Pointer)(nil)
1422         prototype := *(**mapType)(unsafe.Pointer(&imap))
1423         mt := new(mapType)
1424         *mt = *prototype
1425         mt.string = &s
1426
1427         // gccgo uses a different hash
1428         // mt.hash = fnv1(etyp.hash, 'm', byte(ktyp.hash>>24), byte(ktyp.hash>>16), byte(ktyp.hash>>8), byte(ktyp.hash))
1429         mt.hash = ktyp.hash + etyp.hash + 2 + 14
1430
1431         mt.key = ktyp
1432         mt.elem = etyp
1433         mt.uncommonType = nil
1434         mt.ptrToThis = nil
1435
1436         return cachePut(ckey, &mt.rtype)
1437 }
1438
1439 // SliceOf returns the slice type with element type t.
1440 // For example, if t represents int, SliceOf(t) represents []int.
1441 func SliceOf(t Type) Type {
1442         typ := t.(*rtype)
1443
1444         // Look in cache.
1445         ckey := cacheKey{Slice, typ, nil, 0}
1446         if slice := cacheGet(ckey); slice != nil {
1447                 return slice
1448         }
1449
1450         // Look in known types.
1451         s := "[]" + *typ.string
1452
1453         // Make a slice type.
1454         var islice interface{} = ([]unsafe.Pointer)(nil)
1455         prototype := *(**sliceType)(unsafe.Pointer(&islice))
1456         slice := new(sliceType)
1457         *slice = *prototype
1458         slice.string = &s
1459
1460         // gccgo uses a different hash.
1461         // slice.hash = fnv1(typ.hash, '[')
1462         slice.hash = typ.hash + 1 + 13
1463
1464         slice.elem = typ
1465         slice.uncommonType = nil
1466         slice.ptrToThis = nil
1467
1468         return cachePut(ckey, &slice.rtype)
1469 }
1470
1471 // ArrayOf returns the array type with the given count and element type.
1472 // For example, if t represents int, ArrayOf(5, t) represents [5]int.
1473 //
1474 // If the resulting type would be larger than the available address space,
1475 // ArrayOf panics.
1476 //
1477 // TODO(rsc): Unexported for now. Export once the alg field is set correctly
1478 // for the type. This may require significant work.
1479 func arrayOf(count int, elem Type) Type {
1480         typ := elem.(*rtype)
1481         slice := SliceOf(elem)
1482
1483         // Look in cache.
1484         ckey := cacheKey{Array, typ, nil, uintptr(count)}
1485         if slice := cacheGet(ckey); slice != nil {
1486                 return slice
1487         }
1488
1489         // Look in known types.
1490         s := "[" + strconv.Itoa(count) + "]" + *typ.string
1491
1492         // Make an array type.
1493         var iarray interface{} = [1]unsafe.Pointer{}
1494         prototype := *(**arrayType)(unsafe.Pointer(&iarray))
1495         array := new(arrayType)
1496         *array = *prototype
1497         array.string = &s
1498
1499         // gccgo uses a different hash.
1500         // array.hash = fnv1(typ.hash, '[')
1501         // for n := uint32(count); n > 0; n >>= 8 {
1502         //      array.hash = fnv1(array.hash, byte(n))
1503         // }
1504         // array.hash = fnv1(array.hash, ']')
1505         array.hash = typ.hash + 1 + 13
1506
1507         array.elem = typ
1508         max := ^uintptr(0) / typ.size
1509         if uintptr(count) > max {
1510                 panic("reflect.ArrayOf: array size would exceed virtual address space")
1511         }
1512         array.size = typ.size * uintptr(count)
1513         array.align = typ.align
1514         array.fieldAlign = typ.fieldAlign
1515         // TODO: array.alg
1516         // TODO: array.gc
1517         array.uncommonType = nil
1518         array.ptrToThis = nil
1519         array.len = uintptr(count)
1520         array.slice = slice.(*rtype)
1521
1522         return cachePut(ckey, &array.rtype)
1523 }
1524
1525 // toType converts from a *rtype to a Type that can be returned
1526 // to the client of package reflect. In gc, the only concern is that
1527 // a nil *rtype must be replaced by a nil Type, but in gccgo this
1528 // function takes care of ensuring that multiple *rtype for the same
1529 // type are coalesced into a single Type.
1530 var canonicalType = make(map[string]Type)
1531
1532 var canonicalTypeLock sync.RWMutex
1533
1534 func canonicalize(t Type) Type {
1535         if t == nil {
1536                 return nil
1537         }
1538         u := t.uncommon()
1539         var s string
1540         if u == nil || u.PkgPath() == "" {
1541                 s = t.rawString()
1542         } else {
1543                 s = u.PkgPath() + "." + u.Name()
1544         }
1545         canonicalTypeLock.RLock()
1546         if r, ok := canonicalType[s]; ok {
1547                 canonicalTypeLock.RUnlock()
1548                 return r
1549         }
1550         canonicalTypeLock.RUnlock()
1551         canonicalTypeLock.Lock()
1552         if r, ok := canonicalType[s]; ok {
1553                 canonicalTypeLock.Unlock()
1554                 return r
1555         }
1556         canonicalType[s] = t
1557         canonicalTypeLock.Unlock()
1558         return t
1559 }
1560
1561 func toType(p *rtype) Type {
1562         if p == nil {
1563                 return nil
1564         }
1565         return canonicalize(p)
1566 }