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         // Methods applicable only to some types, depending on Kind.
  99         // The methods allowed for each kind are:
 100         //
 101         //      Int*, Uint*, Float*, Complex*: Bits
 102         //      Array: Elem, Len
 103         //      Chan: ChanDir, Elem
 104         //      Func: In, NumIn, Out, NumOut, IsVariadic.
 105         //      Map: Key, Elem
 106         //      Ptr: Elem
 107         //      Slice: Elem
 108         //      Struct: Field, FieldByIndex, FieldByName, FieldByNameFunc, NumField
 109
 110         // Bits returns the size of the type in bits.
 111         // It panics if the type's Kind is not one of the
 112         // sized or unsized Int, Uint, Float, or Complex kinds.
 113         Bits() int
 114
 115         // ChanDir returns a channel type's direction.
 116         // It panics if the type's Kind is not Chan.
 117         ChanDir() ChanDir
 118
 119         // IsVariadic returns true if a function type's final input parameter
 120         // is a "..." parameter.  If so, t.In(t.NumIn() - 1) returns the parameter's
 121         // implicit actual type []T.
 122         //
 123         // For concreteness, if t represents func(x int, y ... float64), then
 124         //
 125         //      t.NumIn() == 2
 126         //      t.In(0) is the reflect.Type for "int"
 127         //      t.In(1) is the reflect.Type for "[]float64"
 128         //      t.IsVariadic() == true
 129         //
 130         // IsVariadic panics if the type's Kind is not Func.
 131         IsVariadic() bool
 132
 133         // Elem returns a type's element type.
 134         // It panics if the type's Kind is not Array, Chan, Map, Ptr, or Slice.
 135         Elem() Type
 136
 137         // Field returns a struct type's i'th field.
 138         // It panics if the type's Kind is not Struct.
 139         // It panics if i is not in the range [0, NumField()).
 140         Field(i int) StructField
 141
 142         // FieldByIndex returns the nested field corresponding
 143         // to the index sequence.  It is equivalent to calling Field
 144         // successively for each index i.
 145         // It panics if the type's Kind is not Struct.
 146         FieldByIndex(index []int) StructField
 147
 148         // FieldByName returns the struct field with the given name
 149         // and a boolean indicating if the field was found.
 150         FieldByName(name string) (StructField, bool)
 151
 152         // FieldByNameFunc returns the first struct field with a name
 153         // that satisfies the match function and a boolean indicating if
 154         // the field was found.
 155         FieldByNameFunc(match func(string) bool) (StructField, bool)
 156
 157         // In returns the type of a function type's i'th input parameter.
 158         // It panics if the type's Kind is not Func.
 159         // It panics if i is not in the range [0, NumIn()).
 160         In(i int) Type
 161
 162         // Key returns a map type's key type.
 163         // It panics if the type's Kind is not Map.
 164         Key() Type
 165
 166         // Len returns an array type's length.
 167         // It panics if the type's Kind is not Array.
 168         Len() int
 169
 170         // NumField returns a struct type's field count.
 171         // It panics if the type's Kind is not Struct.
 172         NumField() int
 173
 174         // NumIn returns a function type's input parameter count.
 175         // It panics if the type's Kind is not Func.
 176         NumIn() int
 177
 178         // NumOut returns a function type's output parameter count.
 179         // It panics if the type's Kind is not Func.
 180         NumOut() int
 181
 182         // Out returns the type of a function type's i'th output parameter.
 183         // It panics if the type's Kind is not Func.
 184         // It panics if i is not in the range [0, NumOut()).
 185         Out(i int) Type
 186
 187         runtimeType() *runtimeType
 188         common() *commonType
 189         uncommon() *uncommonType
 190 }
 191
 192 // A Kind represents the specific kind of type that a Type represents.
 193 // The zero Kind is not a valid kind.
 194 type Kind uint
 195
 196 const (
 197         Invalid Kind = iota
 198         Bool
 199         Int
 200         Int8
 201         Int16
 202         Int32
 203         Int64
 204         Uint
 205         Uint8
 206         Uint16
 207         Uint32
 208         Uint64
 209         Uintptr
 210         Float32
 211         Float64
 212         Complex64
 213         Complex128
 214         Array
 215         Chan
 216         Func
 217         Interface
 218         Map
 219         Ptr
 220         Slice
 221         String
 222         Struct
 223         UnsafePointer
 224 )
 225
 226 /*
 227  * These data structures are known to the compiler (../../cmd/gc/reflect.c).
 228  * A few are known to ../runtime/type.go to convey to debuggers.
 229  */
 230
 231 type runtimeType commonType
 232
 233 // commonType is the common implementation of most values.
 234 // It is embedded in other, public struct types, but always
 235 // with a unique tag like `reflect:"array"` or `reflect:"ptr"`
 236 // so that code cannot convert from, say, *arrayType to *ptrType.
 237 type commonType struct {
 238         kind       uint8   // enumeration for C
 239         align      int8    // alignment of variable with this type
 240         fieldAlign uint8   // alignment of struct field with this type
 241         _          uint8   // unused/padding
 242         size       uintptr // size in bytes
 243         hash       uint32  // hash of type; avoids computation in hash tables
 244
 245         hashfn  func(unsafe.Pointer, uintptr)                 // hash function
 246         equalfn func(unsafe.Pointer, unsafe.Pointer, uintptr) // equality function
 247
 248         string        *string      // string form; unnecessary  but undeniably useful
 249         *uncommonType              // (relatively) uncommon fields
 250         ptrToThis     *runtimeType // pointer to this type, if used in binary or has methods
 251 }
 252
 253 // Method on non-interface type
 254 type method struct {
 255         name    *string        // name of method
 256         pkgPath *string        // nil for exported Names; otherwise import path
 257         mtyp    *runtimeType   // method type (without receiver)
 258         typ     *runtimeType   // .(*FuncType) underneath (with receiver)
 259         tfn     unsafe.Pointer // fn used for normal method call
 260 }
 261
 262 // uncommonType is present only for types with names or methods
 263 // (if T is a named type, the uncommonTypes for T and *T have methods).
 264 // Using a pointer to this struct reduces the overall size required
 265 // to describe an unnamed type with no methods.
 266 type uncommonType struct {
 267         name    *string  // name of type
 268         pkgPath *string  // import path; nil for built-in types like int, string
 269         methods []method // methods associated with type
 270 }
 271
 272 // ChanDir represents a channel type's direction.
 273 type ChanDir int
 274
 275 const (
 276         RecvDir ChanDir             = 1 << iota // <-chan
 277         SendDir                                 // chan<-
 278         BothDir = RecvDir | SendDir             // chan
 279 )
 280
 281 // arrayType represents a fixed array type.
 282 type arrayType struct {
 283         commonType `reflect:"array"`
 284         elem       *runtimeType // array element type
 285         slice      *runtimeType // slice type
 286         len        uintptr
 287 }
 288
 289 // chanType represents a channel type.
 290 type chanType struct {
 291         commonType `reflect:"chan"`
 292         elem       *runtimeType // channel element type
 293         dir        uintptr      // channel direction (ChanDir)
 294 }
 295
 296 // funcType represents a function type.
 297 type funcType struct {
 298         commonType `reflect:"func"`
 299         dotdotdot  bool           // last input parameter is ...
 300         in         []*runtimeType // input parameter types
 301         out        []*runtimeType // output parameter types
 302 }
 303
 304 // imethod represents a method on an interface type
 305 type imethod struct {
 306         name    *string      // name of method
 307         pkgPath *string      // nil for exported Names; otherwise import path
 308         typ     *runtimeType // .(*FuncType) underneath
 309 }
 310
 311 // interfaceType represents an interface type.
 312 type interfaceType struct {
 313         commonType `reflect:"interface"`
 314         methods    []imethod // sorted by hash
 315 }
 316
 317 // mapType represents a map type.
 318 type mapType struct {
 319         commonType `reflect:"map"`
 320         key        *runtimeType // map key type
 321         elem       *runtimeType // map element (value) type
 322 }
 323
 324 // ptrType represents a pointer type.
 325 type ptrType struct {
 326         commonType `reflect:"ptr"`
 327         elem       *runtimeType // pointer element (pointed at) type
 328 }
 329
 330 // sliceType represents a slice type.
 331 type sliceType struct {
 332         commonType `reflect:"slice"`
 333         elem       *runtimeType // slice element type
 334 }
 335
 336 // Struct field
 337 type structField struct {
 338         name    *string      // nil for embedded fields
 339         pkgPath *string      // nil for exported Names; otherwise import path
 340         typ     *runtimeType // type of field
 341         tag     *string      // nil if no tag
 342         offset  uintptr      // byte offset of field within struct
 343 }
 344
 345 // structType represents a struct type.
 346 type structType struct {
 347         commonType `reflect:"struct"`
 348         fields     []structField // sorted by offset
 349 }
 350
 351 /*
 352  * The compiler knows the exact layout of all the data structures above.
 353  * The compiler does not know about the data structures and methods below.
 354  */
 355
 356 // Method represents a single method.
 357 type Method struct {
 358         // Name is the method name.
 359         // PkgPath is the package path that qualifies a lower case (unexported)
 360         // method name.  It is empty for upper case (exported) method names.
 361         // The combination of PkgPath and Name uniquely identifies a method
 362         // in a method set.
 363         // See http://golang.org/ref/spec#Uniqueness_of_identifiers
 364         Name    string
 365         PkgPath string
 366
 367         Type  Type  // method type
 368         Func  Value // func with receiver as first argument
 369         Index int   // index for Type.Method
 370 }
 371
 372 // High bit says whether type has
 373 // embedded pointers,to help garbage collector.
 374 const kindMask = 0x7f
 375
 376 func (k Kind) String() string {
 377         if int(k) < len(kindNames) {
 378                 return kindNames[k]
 379         }
 380         return "kind" + strconv.Itoa(int(k))
 381 }
 382
 383 var kindNames = []string{
 384         Invalid:       "invalid",
 385         Bool:          "bool",
 386         Int:           "int",
 387         Int8:          "int8",
 388         Int16:         "int16",
 389         Int32:         "int32",
 390         Int64:         "int64",
 391         Uint:          "uint",
 392         Uint8:         "uint8",
 393         Uint16:        "uint16",
 394         Uint32:        "uint32",
 395         Uint64:        "uint64",
 396         Uintptr:       "uintptr",
 397         Float32:       "float32",
 398         Float64:       "float64",
 399         Complex64:     "complex64",
 400         Complex128:    "complex128",
 401         Array:         "array",
 402         Chan:          "chan",
 403         Func:          "func",
 404         Interface:     "interface",
 405         Map:           "map",
 406         Ptr:           "ptr",
 407         Slice:         "slice",
 408         String:        "string",
 409         Struct:        "struct",
 410         UnsafePointer: "unsafe.Pointer",
 411 }
 412
 413 func (t *uncommonType) uncommon() *uncommonType {
 414         return t
 415 }
 416
 417 func (t *uncommonType) PkgPath() string {
 418         if t == nil || t.pkgPath == nil {
 419                 return ""
 420         }
 421         return *t.pkgPath
 422 }
 423
 424 func (t *uncommonType) Name() string {
 425         if t == nil || t.name == nil {
 426                 return ""
 427         }
 428         return *t.name
 429 }
 430
 431 func (t *commonType) toType() Type {
 432         if t == nil {
 433                 return nil
 434         }
 435         return canonicalize(t)
 436 }
 437
 438 func (t *commonType) rawString() string { return *t.string }
 439
 440 func (t *commonType) String() string {
 441         // For gccgo, strip out quoted strings.
 442         s := *t.string
 443         var q bool
 444         r := make([]byte, len(s))
 445         j := 0
 446         for i := 0; i < len(s); i++ {
 447                 if s[i] == '\t' {
 448                         q = !q
 449                 } else if !q {
 450                         r[j] = s[i]
 451                         j++
 452                 }
 453         }
 454         return string(r[:j])
 455 }
 456
 457 func (t *commonType) Size() uintptr { return t.size }
 458
 459 func (t *commonType) Bits() int {
 460         if t == nil {
 461                 panic("reflect: Bits of nil Type")
 462         }
 463         k := t.Kind()
 464         if k < Int || k > Complex128 {
 465                 panic("reflect: Bits of non-arithmetic Type " + t.String())
 466         }
 467         return int(t.size) * 8
 468 }
 469
 470 func (t *commonType) Align() int { return int(t.align) }
 471
 472 func (t *commonType) FieldAlign() int { return int(t.fieldAlign) }
 473
 474 func (t *commonType) Kind() Kind { return Kind(t.kind & kindMask) }
 475
 476 func (t *commonType) common() *commonType { return t }
 477
 478 func (t *uncommonType) Method(i int) (m Method) {
 479         if t == nil || i < 0 || i >= len(t.methods) {
 480                 panic("reflect: Method index out of range")
 481         }
 482         p := &t.methods[i]
 483         if p.name != nil {
 484                 m.Name = *p.name
 485         }
 486         fl := flag(Func) << flagKindShift
 487         if p.pkgPath != nil {
 488                 m.PkgPath = *p.pkgPath
 489                 fl |= flagRO
 490         }
 491         mt := toCommonType(p.typ)
 492         m.Type = mt.toType()
 493         x := new(unsafe.Pointer)
 494         *x = p.tfn
 495         m.Func = Value{mt, unsafe.Pointer(x), fl | flagIndir}
 496         m.Index = i
 497         return
 498 }
 499
 500 func (t *uncommonType) NumMethod() int {
 501         if t == nil {
 502                 return 0
 503         }
 504         return len(t.methods)
 505 }
 506
 507 func (t *uncommonType) MethodByName(name string) (m Method, ok bool) {
 508         if t == nil {
 509                 return
 510         }
 511         var p *method
 512         for i := range t.methods {
 513                 p = &t.methods[i]
 514                 if p.name != nil && *p.name == name {
 515                         return t.Method(i), true
 516                 }
 517         }
 518         return
 519 }
 520
 521 // TODO(rsc): 6g supplies these, but they are not
 522 // as efficient as they could be: they have commonType
 523 // as the receiver instead of *commonType.
 524 func (t *commonType) NumMethod() int {
 525         if t.Kind() == Interface {
 526                 tt := (*interfaceType)(unsafe.Pointer(t))
 527                 return tt.NumMethod()
 528         }
 529         return t.uncommonType.NumMethod()
 530 }
 531
 532 func (t *commonType) Method(i int) (m Method) {
 533         if t.Kind() == Interface {
 534                 tt := (*interfaceType)(unsafe.Pointer(t))
 535                 return tt.Method(i)
 536         }
 537         return t.uncommonType.Method(i)
 538 }
 539
 540 func (t *commonType) MethodByName(name string) (m Method, ok bool) {
 541         if t.Kind() == Interface {
 542                 tt := (*interfaceType)(unsafe.Pointer(t))
 543                 return tt.MethodByName(name)
 544         }
 545         return t.uncommonType.MethodByName(name)
 546 }
 547
 548 func (t *commonType) PkgPath() string {
 549         return t.uncommonType.PkgPath()
 550 }
 551
 552 func (t *commonType) Name() string {
 553         return t.uncommonType.Name()
 554 }
 555
 556 func (t *commonType) ChanDir() ChanDir {
 557         if t.Kind() != Chan {
 558                 panic("reflect: ChanDir of non-chan type")
 559         }
 560         tt := (*chanType)(unsafe.Pointer(t))
 561         return ChanDir(tt.dir)
 562 }
 563
 564 func (t *commonType) IsVariadic() bool {
 565         if t.Kind() != Func {
 566                 panic("reflect: IsVariadic of non-func type")
 567         }
 568         tt := (*funcType)(unsafe.Pointer(t))
 569         return tt.dotdotdot
 570 }
 571
 572 func (t *commonType) Elem() Type {
 573         switch t.Kind() {
 574         case Array:
 575                 tt := (*arrayType)(unsafe.Pointer(t))
 576                 return toType(tt.elem)
 577         case Chan:
 578                 tt := (*chanType)(unsafe.Pointer(t))
 579                 return toType(tt.elem)
 580         case Map:
 581                 tt := (*mapType)(unsafe.Pointer(t))
 582                 return toType(tt.elem)
 583         case Ptr:
 584                 tt := (*ptrType)(unsafe.Pointer(t))
 585                 return toType(tt.elem)
 586         case Slice:
 587                 tt := (*sliceType)(unsafe.Pointer(t))
 588                 return toType(tt.elem)
 589         }
 590         panic("reflect: Elem of invalid type")
 591 }
 592
 593 func (t *commonType) Field(i int) StructField {
 594         if t.Kind() != Struct {
 595                 panic("reflect: Field of non-struct type")
 596         }
 597         tt := (*structType)(unsafe.Pointer(t))
 598         return tt.Field(i)
 599 }
 600
 601 func (t *commonType) FieldByIndex(index []int) StructField {
 602         if t.Kind() != Struct {
 603                 panic("reflect: FieldByIndex of non-struct type")
 604         }
 605         tt := (*structType)(unsafe.Pointer(t))
 606         return tt.FieldByIndex(index)
 607 }
 608
 609 func (t *commonType) FieldByName(name string) (StructField, bool) {
 610         if t.Kind() != Struct {
 611                 panic("reflect: FieldByName of non-struct type")
 612         }
 613         tt := (*structType)(unsafe.Pointer(t))
 614         return tt.FieldByName(name)
 615 }
 616
 617 func (t *commonType) FieldByNameFunc(match func(string) bool) (StructField, bool) {
 618         if t.Kind() != Struct {
 619                 panic("reflect: FieldByNameFunc of non-struct type")
 620         }
 621         tt := (*structType)(unsafe.Pointer(t))
 622         return tt.FieldByNameFunc(match)
 623 }
 624
 625 func (t *commonType) In(i int) Type {
 626         if t.Kind() != Func {
 627                 panic("reflect: In of non-func type")
 628         }
 629         tt := (*funcType)(unsafe.Pointer(t))
 630         return toType(tt.in[i])
 631 }
 632
 633 func (t *commonType) Key() Type {
 634         if t.Kind() != Map {
 635                 panic("reflect: Key of non-map type")
 636         }
 637         tt := (*mapType)(unsafe.Pointer(t))
 638         return toType(tt.key)
 639 }
 640
 641 func (t *commonType) Len() int {
 642         if t.Kind() != Array {
 643                 panic("reflect: Len of non-array type")
 644         }
 645         tt := (*arrayType)(unsafe.Pointer(t))
 646         return int(tt.len)
 647 }
 648
 649 func (t *commonType) NumField() int {
 650         if t.Kind() != Struct {
 651                 panic("reflect: NumField of non-struct type")
 652         }
 653         tt := (*structType)(unsafe.Pointer(t))
 654         return len(tt.fields)
 655 }
 656
 657 func (t *commonType) NumIn() int {
 658         if t.Kind() != Func {
 659                 panic("reflect: NumIn of non-func type")
 660         }
 661         tt := (*funcType)(unsafe.Pointer(t))
 662         return len(tt.in)
 663 }
 664
 665 func (t *commonType) NumOut() int {
 666         if t.Kind() != Func {
 667                 panic("reflect: NumOut of non-func type")
 668         }
 669         tt := (*funcType)(unsafe.Pointer(t))
 670         return len(tt.out)
 671 }
 672
 673 func (t *commonType) Out(i int) Type {
 674         if t.Kind() != Func {
 675                 panic("reflect: Out of non-func type")
 676         }
 677         tt := (*funcType)(unsafe.Pointer(t))
 678         return toType(tt.out[i])
 679 }
 680
 681 func (d ChanDir) String() string {
 682         switch d {
 683         case SendDir:
 684                 return "chan<-"
 685         case RecvDir:
 686                 return "<-chan"
 687         case BothDir:
 688                 return "chan"
 689         }
 690         return "ChanDir" + strconv.Itoa(int(d))
 691 }
 692
 693 // Method returns the i'th method in the type's method set.
 694 func (t *interfaceType) Method(i int) (m Method) {
 695         if i < 0 || i >= len(t.methods) {
 696                 return
 697         }
 698         p := &t.methods[i]
 699         m.Name = *p.name
 700         if p.pkgPath != nil {
 701                 m.PkgPath = *p.pkgPath
 702         }
 703         m.Type = toType(p.typ)
 704         m.Index = i
 705         return
 706 }
 707
 708 // NumMethod returns the number of interface methods in the type's method set.
 709 func (t *interfaceType) NumMethod() int { return len(t.methods) }
 710
 711 // MethodByName method with the given name in the type's method set.
 712 func (t *interfaceType) MethodByName(name string) (m Method, ok bool) {
 713         if t == nil {
 714                 return
 715         }
 716         var p *imethod
 717         for i := range t.methods {
 718                 p = &t.methods[i]
 719                 if *p.name == name {
 720                         return t.Method(i), true
 721                 }
 722         }
 723         return
 724 }
 725
 726 // A StructField describes a single field in a struct.
 727 type StructField struct {
 728         // Name is the field name.
 729         // PkgPath is the package path that qualifies a lower case (unexported)
 730         // field name.  It is empty for upper case (exported) field names.
 731         // See http://golang.org/ref/spec#Uniqueness_of_identifiers
 732         Name    string
 733         PkgPath string
 734
 735         Type      Type      // field type
 736         Tag       StructTag // field tag string
 737         Offset    uintptr   // offset within struct, in bytes
 738         Index     []int     // index sequence for Type.FieldByIndex
 739         Anonymous bool      // is an anonymous field
 740 }
 741
 742 // A StructTag is the tag string in a struct field.
 743 //
 744 // By convention, tag strings are a concatenation of
 745 // optionally space-separated key:"value" pairs.
 746 // Each key is a non-empty string consisting of non-control
 747 // characters other than space (U+0020 ' '), quote (U+0022 '"'),
 748 // and colon (U+003A ':').  Each value is quoted using U+0022 '"'
 749 // characters and Go string literal syntax.
 750 type StructTag string
 751
 752 // Get returns the value associated with key in the tag string.
 753 // If there is no such key in the tag, Get returns the empty string.
 754 // If the tag does not have the conventional format, the value
 755 // returned by Get is unspecified.
 756 func (tag StructTag) Get(key string) string {
 757         for tag != "" {
 758                 // skip leading space
 759                 i := 0
 760                 for i < len(tag) && tag[i] == ' ' {
 761                         i++
 762                 }
 763                 tag = tag[i:]
 764                 if tag == "" {
 765                         break
 766                 }
 767
 768                 // scan to colon.
 769                 // a space or a quote is a syntax error
 770                 i = 0
 771                 for i < len(tag) && tag[i] != ' ' && tag[i] != ':' && tag[i] != '"' {
 772                         i++
 773                 }
 774                 if i+1 >= len(tag) || tag[i] != ':' || tag[i+1] != '"' {
 775                         break
 776                 }
 777                 name := string(tag[:i])
 778                 tag = tag[i+1:]
 779
 780                 // scan quoted string to find value
 781                 i = 1
 782                 for i < len(tag) && tag[i] != '"' {
 783                         if tag[i] == '\\' {
 784                                 i++
 785                         }
 786                         i++
 787                 }
 788                 if i >= len(tag) {
 789                         break
 790                 }
 791                 qvalue := string(tag[:i+1])
 792                 tag = tag[i+1:]
 793
 794                 if key == name {
 795                         value, _ := strconv.Unquote(qvalue)
 796                         return value
 797                 }
 798         }
 799         return ""
 800 }
 801
 802 // Field returns the i'th struct field.
 803 func (t *structType) Field(i int) (f StructField) {
 804         if i < 0 || i >= len(t.fields) {
 805                 return
 806         }
 807         p := &t.fields[i]
 808         f.Type = toType(p.typ)
 809         if p.name != nil {
 810                 f.Name = *p.name
 811         } else {
 812                 t := f.Type
 813                 if t.Kind() == Ptr {
 814                         t = t.Elem()
 815                 }
 816                 f.Name = t.Name()
 817                 f.Anonymous = true
 818         }
 819         if p.pkgPath != nil {
 820                 f.PkgPath = *p.pkgPath
 821         }
 822         if p.tag != nil {
 823                 f.Tag = StructTag(*p.tag)
 824         }
 825         f.Offset = p.offset
 826
 827         // NOTE(rsc): This is the only allocation in the interface
 828         // presented by a reflect.Type.  It would be nice to avoid,
 829         // at least in the common cases, but we need to make sure
 830         // that misbehaving clients of reflect cannot affect other
 831         // uses of reflect.  One possibility is CL 5371098, but we
 832         // postponed that ugliness until there is a demonstrated
 833         // need for the performance.  This is issue 2320.
 834         f.Index = []int{i}
 835         return
 836 }
 837
 838 // TODO(gri): Should there be an error/bool indicator if the index
 839 //            is wrong for FieldByIndex?
 840
 841 // FieldByIndex returns the nested field corresponding to index.
 842 func (t *structType) FieldByIndex(index []int) (f StructField) {
 843         f.Type = Type(t.toType())
 844         for i, x := range index {
 845                 if i > 0 {
 846                         ft := f.Type
 847                         if ft.Kind() == Ptr && ft.Elem().Kind() == Struct {
 848                                 ft = ft.Elem()
 849                         }
 850                         f.Type = ft
 851                 }
 852                 f = f.Type.Field(x)
 853         }
 854         return
 855 }
 856
 857 const inf = 1 << 30 // infinity - no struct has that many nesting levels
 858
 859 func (t *structType) fieldByNameFunc(match func(string) bool, mark map[*structType]bool, depth int) (ff StructField, fd int) {
 860         fd = inf // field depth
 861
 862         if mark[t] {
 863                 // Struct already seen.
 864                 return
 865         }
 866         mark[t] = true
 867
 868         var fi int // field index
 869         n := 0     // number of matching fields at depth fd
 870 L:
 871         for i := range t.fields {
 872                 f := t.Field(i)
 873                 d := inf
 874                 switch {
 875                 case match(f.Name):
 876                         // Matching top-level field.
 877                         d = depth
 878                 case f.Anonymous:
 879                         ft := f.Type
 880                         if ft.Kind() == Ptr {
 881                                 ft = ft.Elem()
 882                         }
 883                         switch {
 884                         case match(ft.Name()):
 885                                 // Matching anonymous top-level field.
 886                                 d = depth
 887                         case fd > depth:
 888                                 // No top-level field yet; look inside nested structs.
 889                                 if ft.Kind() == Struct {
 890                                         st := (*structType)(unsafe.Pointer(ft.(*commonType)))
 891                                         f, d = st.fieldByNameFunc(match, mark, depth+1)
 892                                 }
 893                         }
 894                 }
 895
 896                 switch {
 897                 case d < fd:
 898                         // Found field at shallower depth.
 899                         ff, fi, fd = f, i, d
 900                         n = 1
 901                 case d == fd:
 902                         // More than one matching field at the same depth (or d, fd == inf).
 903                         // Same as no field found at this depth.
 904                         n++
 905                         if d == depth {
 906                                 // Impossible to find a field at lower depth.
 907                                 break L
 908                         }
 909                 }
 910         }
 911
 912         if n == 1 {
 913                 // Found matching field.
 914                 if depth >= len(ff.Index) {
 915                         ff.Index = make([]int, depth+1)
 916                 }
 917                 if len(ff.Index) > 1 {
 918                         ff.Index[depth] = fi
 919                 }
 920         } else {
 921                 // None or more than one matching field found.
 922                 fd = inf
 923         }
 924
 925         delete(mark, t)
 926         return
 927 }
 928
 929 // FieldByName returns the struct field with the given name
 930 // and a boolean to indicate if the field was found.
 931 func (t *structType) FieldByName(name string) (f StructField, present bool) {
 932         return t.FieldByNameFunc(func(s string) bool { return s == name })
 933 }
 934
 935 // FieldByNameFunc returns the struct field with a name that satisfies the
 936 // match function and a boolean to indicate if the field was found.
 937 func (t *structType) FieldByNameFunc(match func(string) bool) (f StructField, present bool) {
 938         if ff, fd := t.fieldByNameFunc(match, make(map[*structType]bool), 0); fd < inf {
 939                 ff.Index = ff.Index[0 : fd+1]
 940                 f, present = ff, true
 941         }
 942         return
 943 }
 944
 945 // Convert runtime type to reflect type.
 946 func toCommonType(p *runtimeType) *commonType {
 947         if p == nil {
 948                 return nil
 949         }
 950         return (*commonType)(unsafe.Pointer(p))
 951 }
 952
 953 // Canonicalize a Type.
 954 var canonicalType = make(map[string]Type)
 955
 956 var canonicalTypeLock sync.RWMutex
 957
 958 func canonicalize(t Type) Type {
 959         if t == nil {
 960                 return nil
 961         }
 962         u := t.uncommon()
 963         var s string
 964         if u == nil || u.PkgPath() == "" {
 965                 s = t.rawString()
 966         } else {
 967                 s = u.PkgPath() + "." + u.Name()
 968         }
 969         canonicalTypeLock.RLock()
 970         if r, ok := canonicalType[s]; ok {
 971                 canonicalTypeLock.RUnlock()
 972                 return r
 973         }
 974         canonicalTypeLock.RUnlock()
 975         canonicalTypeLock.Lock()
 976         if r, ok := canonicalType[s]; ok {
 977                 canonicalTypeLock.Unlock()
 978                 return r
 979         }
 980         canonicalType[s] = t
 981         canonicalTypeLock.Unlock()
 982         return t
 983 }
 984
 985 func toType(p *runtimeType) Type {
 986         if p == nil {
 987                 return nil
 988         }
 989         return (*commonType)(unsafe.Pointer(p))
 990 }
 991
 992 // TypeOf returns the reflection Type of the value in the interface{}.
 993 // TypeOf(nil) returns nil.
 994 func TypeOf(i interface{}) Type {
 995         eface := *(*emptyInterface)(unsafe.Pointer(&i))
 996         return toType(eface.typ)
 997 }
 998
 999 // ptrMap is the cache for PtrTo.
1000 var ptrMap struct {
1001         sync.RWMutex
1002         m map[*commonType]*ptrType
1003 }
1004
1005 func (t *commonType) runtimeType() *runtimeType {
1006         return (*runtimeType)(unsafe.Pointer(t))
1007 }
1008
1009 // PtrTo returns the pointer type with element t.
1010 // For example, if t represents type Foo, PtrTo(t) represents *Foo.
1011 func PtrTo(t Type) Type {
1012         return t.(*commonType).ptrTo()
1013 }
1014
1015 func (ct *commonType) ptrTo() *commonType {
1016         if p := ct.ptrToThis; p != nil {
1017                 return toCommonType(p)
1018         }
1019
1020         // Otherwise, synthesize one.
1021         // This only happens for pointers with no methods.
1022         // We keep the mapping in a map on the side, because
1023         // this operation is rare and a separate map lets us keep
1024         // the type structures in read-only memory.
1025         ptrMap.RLock()
1026         if m := ptrMap.m; m != nil {
1027                 if p := m[ct]; p != nil {
1028                         ptrMap.RUnlock()
1029                         return &p.commonType
1030                 }
1031         }
1032         ptrMap.RUnlock()
1033         ptrMap.Lock()
1034         if ptrMap.m == nil {
1035                 ptrMap.m = make(map[*commonType]*ptrType)
1036         }
1037         p := ptrMap.m[ct]
1038         if p != nil {
1039                 // some other goroutine won the race and created it
1040                 ptrMap.Unlock()
1041                 return &p.commonType
1042         }
1043
1044         s := "*" + *ct.string
1045
1046         canonicalTypeLock.RLock()
1047         r, ok := canonicalType[s]
1048         canonicalTypeLock.RUnlock()
1049         if ok {
1050                 ptrMap.m[ct] = (*ptrType)(unsafe.Pointer(r.(*commonType)))
1051                 ptrMap.Unlock()
1052                 return r.(*commonType)
1053         }
1054
1055         // initialize p using *byte's ptrType as a prototype.
1056         p = new(ptrType)
1057         var ibyte interface{} = (*byte)(nil)
1058         bp := (*ptrType)(unsafe.Pointer(*(**runtimeType)(unsafe.Pointer(&ibyte))))
1059         *p = *bp
1060
1061         p.string = &s
1062
1063         // For the type structures linked into the binary, the
1064         // compiler provides a good hash of the string.
1065         // Create a good hash for the new string by using
1066         // the FNV-1 hash's mixing function to combine the
1067         // old hash and the new "*".
1068         // p.hash = ct.hash*16777619 ^ '*'
1069         // This is the gccgo version.
1070         p.hash = (ct.hash << 4) + 9
1071
1072         p.uncommonType = nil
1073         p.ptrToThis = nil
1074         p.elem = (*runtimeType)(unsafe.Pointer(ct))
1075
1076         p = canonicalize(p).(*ptrType)
1077
1078         ptrMap.m[ct] = p
1079         ptrMap.Unlock()
1080         return &p.commonType
1081 }
1082
1083 func (t *commonType) Implements(u Type) bool {
1084         if u == nil {
1085                 panic("reflect: nil type passed to Type.Implements")
1086         }
1087         if u.Kind() != Interface {
1088                 panic("reflect: non-interface type passed to Type.Implements")
1089         }
1090         return implements(u.(*commonType), t)
1091 }
1092
1093 func (t *commonType) AssignableTo(u Type) bool {
1094         if u == nil {
1095                 panic("reflect: nil type passed to Type.AssignableTo")
1096         }
1097         uu := u.(*commonType)
1098         return directlyAssignable(uu, t) || implements(uu, t)
1099 }
1100
1101 // implements returns true if the type V implements the interface type T.
1102 func implements(T, V *commonType) bool {
1103         if T.Kind() != Interface {
1104                 return false
1105         }
1106         t := (*interfaceType)(unsafe.Pointer(T))
1107         if len(t.methods) == 0 {
1108                 return true
1109         }
1110
1111         // The same algorithm applies in both cases, but the
1112         // method tables for an interface type and a concrete type
1113         // are different, so the code is duplicated.
1114         // In both cases the algorithm is a linear scan over the two
1115         // lists - T's methods and V's methods - simultaneously.
1116         // Since method tables are stored in a unique sorted order
1117         // (alphabetical, with no duplicate method names), the scan
1118         // through V's methods must hit a match for each of T's
1119         // methods along the way, or else V does not implement T.
1120         // This lets us run the scan in overall linear time instead of
1121         // the quadratic time  a naive search would require.
1122         // See also ../runtime/iface.c.
1123         if V.Kind() == Interface {
1124                 v := (*interfaceType)(unsafe.Pointer(V))
1125                 i := 0
1126                 for j := 0; j < len(v.methods); j++ {
1127                         tm := &t.methods[i]
1128                         vm := &v.methods[j]
1129                         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() {
1130                                 if i++; i >= len(t.methods) {
1131                                         return true
1132                                 }
1133                         }
1134                 }
1135                 return false
1136         }
1137
1138         v := V.uncommon()
1139         if v == nil {
1140                 return false
1141         }
1142         i := 0
1143         for j := 0; j < len(v.methods); j++ {
1144                 tm := &t.methods[i]
1145                 vm := &v.methods[j]
1146                 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() {
1147                         if i++; i >= len(t.methods) {
1148                                 return true
1149                         }
1150                 }
1151         }
1152         return false
1153 }
1154
1155 // directlyAssignable returns true if a value x of type V can be directly
1156 // assigned (using memmove) to a value of type T.
1157 // http://golang.org/doc/go_spec.html#Assignability
1158 // Ignoring the interface rules (implemented elsewhere)
1159 // and the ideal constant rules (no ideal constants at run time).
1160 func directlyAssignable(T, V *commonType) bool {
1161         // x's type V is identical to T?
1162         if T == V {
1163                 return true
1164         }
1165
1166         // Otherwise at least one of T and V must be unnamed
1167         // and they must have the same kind.
1168         if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
1169                 return false
1170         }
1171
1172         // x's type T and V have identical underlying types.
1173         // Since at least one is unnamed, only the composite types
1174         // need to be considered.
1175         switch T.Kind() {
1176         case Array:
1177                 return T.Elem() == V.Elem() && T.Len() == V.Len()
1178
1179         case Chan:
1180                 // Special case:
1181                 // x is a bidirectional channel value, T is a channel type,
1182                 // and x's type V and T have identical element types.
1183                 if V.ChanDir() == BothDir && T.Elem() == V.Elem() {
1184                         return true
1185                 }
1186
1187                 // Otherwise continue test for identical underlying type.
1188                 return V.ChanDir() == T.ChanDir() && T.Elem() == V.Elem()
1189
1190         case Func:
1191                 t := (*funcType)(unsafe.Pointer(T))
1192                 v := (*funcType)(unsafe.Pointer(V))
1193                 if t.dotdotdot != v.dotdotdot || len(t.in) != len(v.in) || len(t.out) != len(v.out) {
1194                         return false
1195                 }
1196                 for i, typ := range t.in {
1197                         if typ != v.in[i] {
1198                                 return false
1199                         }
1200                 }
1201                 for i, typ := range t.out {
1202                         if typ != v.out[i] {
1203                                 return false
1204                         }
1205                 }
1206                 return true
1207
1208         case Interface:
1209                 t := (*interfaceType)(unsafe.Pointer(T))
1210                 v := (*interfaceType)(unsafe.Pointer(V))
1211                 if len(t.methods) == 0 && len(v.methods) == 0 {
1212                         return true
1213                 }
1214                 // Might have the same methods but still
1215                 // need a run time conversion.
1216                 return false
1217
1218         case Map:
1219                 return T.Key() == V.Key() && T.Elem() == V.Elem()
1220
1221         case Ptr, Slice:
1222                 return T.Elem() == V.Elem()
1223
1224         case Struct:
1225                 t := (*structType)(unsafe.Pointer(T))
1226                 v := (*structType)(unsafe.Pointer(V))
1227                 if len(t.fields) != len(v.fields) {
1228                         return false
1229                 }
1230                 for i := range t.fields {
1231                         tf := &t.fields[i]
1232                         vf := &v.fields[i]
1233                         if tf.name != vf.name || tf.pkgPath != vf.pkgPath ||
1234                                 tf.typ != vf.typ || tf.tag != vf.tag || tf.offset != vf.offset {
1235                                 return false
1236                         }
1237                 }
1238                 return true
1239         }
1240
1241         return false
1242 }