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