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 uint
 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         fl := flag(Func) << flagKindShift
 459         if p.pkgPath != nil {
 460                 m.PkgPath = *p.pkgPath
 461                 fl |= flagRO
 462         }
 463         mt := toCommonType(p.typ)
 464         m.Type = mt.toType()
 465         x := new(unsafe.Pointer)
 466         *x = p.tfn
 467         m.Func = Value{mt, unsafe.Pointer(x), fl|flagIndir}
 468         m.Index = i
 469         return
 470 }
 471
 472 func (t *uncommonType) NumMethod() int {
 473         if t == nil {
 474                 return 0
 475         }
 476         return len(t.methods)
 477 }
 478
 479 func (t *uncommonType) MethodByName(name string) (m Method, ok bool) {
 480         if t == nil {
 481                 return
 482         }
 483         var p *method
 484         for i := range t.methods {
 485                 p = &t.methods[i]
 486                 if p.name != nil && *p.name == name {
 487                         return t.Method(i), true
 488                 }
 489         }
 490         return
 491 }
 492
 493 // TODO(rsc): 6g supplies these, but they are not
 494 // as efficient as they could be: they have commonType
 495 // as the receiver instead of *commonType.
 496 func (t *commonType) NumMethod() int {
 497         if t.Kind() == Interface {
 498                 tt := (*interfaceType)(unsafe.Pointer(t))
 499                 return tt.NumMethod()
 500         }
 501         return t.uncommonType.NumMethod()
 502 }
 503
 504 func (t *commonType) Method(i int) (m Method) {
 505         if t.Kind() == Interface {
 506                 tt := (*interfaceType)(unsafe.Pointer(t))
 507                 return tt.Method(i)
 508         }
 509         return t.uncommonType.Method(i)
 510 }
 511
 512 func (t *commonType) MethodByName(name string) (m Method, ok bool) {
 513         if t.Kind() == Interface {
 514                 tt := (*interfaceType)(unsafe.Pointer(t))
 515                 return tt.MethodByName(name)
 516         }
 517         return t.uncommonType.MethodByName(name)
 518 }
 519
 520 func (t *commonType) PkgPath() string {
 521         return t.uncommonType.PkgPath()
 522 }
 523
 524 func (t *commonType) Name() string {
 525         return t.uncommonType.Name()
 526 }
 527
 528 func (t *commonType) ChanDir() ChanDir {
 529         if t.Kind() != Chan {
 530                 panic("reflect: ChanDir of non-chan type")
 531         }
 532         tt := (*chanType)(unsafe.Pointer(t))
 533         return ChanDir(tt.dir)
 534 }
 535
 536 func (t *commonType) IsVariadic() bool {
 537         if t.Kind() != Func {
 538                 panic("reflect: IsVariadic of non-func type")
 539         }
 540         tt := (*funcType)(unsafe.Pointer(t))
 541         return tt.dotdotdot
 542 }
 543
 544 func (t *commonType) Elem() Type {
 545         switch t.Kind() {
 546         case Array:
 547                 tt := (*arrayType)(unsafe.Pointer(t))
 548                 return toType(tt.elem)
 549         case Chan:
 550                 tt := (*chanType)(unsafe.Pointer(t))
 551                 return toType(tt.elem)
 552         case Map:
 553                 tt := (*mapType)(unsafe.Pointer(t))
 554                 return toType(tt.elem)
 555         case Ptr:
 556                 tt := (*ptrType)(unsafe.Pointer(t))
 557                 return toType(tt.elem)
 558         case Slice:
 559                 tt := (*sliceType)(unsafe.Pointer(t))
 560                 return toType(tt.elem)
 561         }
 562         panic("reflect; Elem of invalid type")
 563 }
 564
 565 func (t *commonType) Field(i int) StructField {
 566         if t.Kind() != Struct {
 567                 panic("reflect: Field of non-struct type")
 568         }
 569         tt := (*structType)(unsafe.Pointer(t))
 570         return tt.Field(i)
 571 }
 572
 573 func (t *commonType) FieldByIndex(index []int) StructField {
 574         if t.Kind() != Struct {
 575                 panic("reflect: FieldByIndex of non-struct type")
 576         }
 577         tt := (*structType)(unsafe.Pointer(t))
 578         return tt.FieldByIndex(index)
 579 }
 580
 581 func (t *commonType) FieldByName(name string) (StructField, bool) {
 582         if t.Kind() != Struct {
 583                 panic("reflect: FieldByName of non-struct type")
 584         }
 585         tt := (*structType)(unsafe.Pointer(t))
 586         return tt.FieldByName(name)
 587 }
 588
 589 func (t *commonType) FieldByNameFunc(match func(string) bool) (StructField, bool) {
 590         if t.Kind() != Struct {
 591                 panic("reflect: FieldByNameFunc of non-struct type")
 592         }
 593         tt := (*structType)(unsafe.Pointer(t))
 594         return tt.FieldByNameFunc(match)
 595 }
 596
 597 func (t *commonType) In(i int) Type {
 598         if t.Kind() != Func {
 599                 panic("reflect: In of non-func type")
 600         }
 601         tt := (*funcType)(unsafe.Pointer(t))
 602         return toType(tt.in[i])
 603 }
 604
 605 func (t *commonType) Key() Type {
 606         if t.Kind() != Map {
 607                 panic("reflect: Key of non-map type")
 608         }
 609         tt := (*mapType)(unsafe.Pointer(t))
 610         return toType(tt.key)
 611 }
 612
 613 func (t *commonType) Len() int {
 614         if t.Kind() != Array {
 615                 panic("reflect: Len of non-array type")
 616         }
 617         tt := (*arrayType)(unsafe.Pointer(t))
 618         return int(tt.len)
 619 }
 620
 621 func (t *commonType) NumField() int {
 622         if t.Kind() != Struct {
 623                 panic("reflect: NumField of non-struct type")
 624         }
 625         tt := (*structType)(unsafe.Pointer(t))
 626         return len(tt.fields)
 627 }
 628
 629 func (t *commonType) NumIn() int {
 630         if t.Kind() != Func {
 631                 panic("reflect; NumIn of non-func type")
 632         }
 633         tt := (*funcType)(unsafe.Pointer(t))
 634         return len(tt.in)
 635 }
 636
 637 func (t *commonType) NumOut() int {
 638         if t.Kind() != Func {
 639                 panic("reflect; NumOut of non-func type")
 640         }
 641         tt := (*funcType)(unsafe.Pointer(t))
 642         return len(tt.out)
 643 }
 644
 645 func (t *commonType) Out(i int) Type {
 646         if t.Kind() != Func {
 647                 panic("reflect: Out of non-func type")
 648         }
 649         tt := (*funcType)(unsafe.Pointer(t))
 650         return toType(tt.out[i])
 651 }
 652
 653 func (d ChanDir) String() string {
 654         switch d {
 655         case SendDir:
 656                 return "chan<-"
 657         case RecvDir:
 658                 return "<-chan"
 659         case BothDir:
 660                 return "chan"
 661         }
 662         return "ChanDir" + strconv.Itoa(int(d))
 663 }
 664
 665 // Method returns the i'th method in the type's method set.
 666 func (t *interfaceType) Method(i int) (m Method) {
 667         if i < 0 || i >= len(t.methods) {
 668                 return
 669         }
 670         p := &t.methods[i]
 671         m.Name = *p.name
 672         if p.pkgPath != nil {
 673                 m.PkgPath = *p.pkgPath
 674         }
 675         m.Type = toType(p.typ)
 676         m.Index = i
 677         return
 678 }
 679
 680 // NumMethod returns the number of interface methods in the type's method set.
 681 func (t *interfaceType) NumMethod() int { return len(t.methods) }
 682
 683 // MethodByName method with the given name in the type's method set.
 684 func (t *interfaceType) MethodByName(name string) (m Method, ok bool) {
 685         if t == nil {
 686                 return
 687         }
 688         var p *imethod
 689         for i := range t.methods {
 690                 p = &t.methods[i]
 691                 if *p.name == name {
 692                         return t.Method(i), true
 693                 }
 694         }
 695         return
 696 }
 697
 698 type StructField struct {
 699         PkgPath   string // empty for uppercase Name
 700         Name      string
 701         Type      Type
 702         Tag       StructTag
 703         Offset    uintptr
 704         Index     []int
 705         Anonymous bool
 706 }
 707
 708 // A StructTag is the tag string in a struct field.
 709 //
 710 // By convention, tag strings are a concatenation of
 711 // optionally space-separated key:"value" pairs.
 712 // Each key is a non-empty string consisting of non-control
 713 // characters other than space (U+0020 ' '), quote (U+0022 '"'),
 714 // and colon (U+003A ':').  Each value is quoted using U+0022 '"'
 715 // characters and Go string literal syntax.
 716 type StructTag string
 717
 718 // Get returns the value associated with key in the tag string.
 719 // If there is no such key in the tag, Get returns the empty string.
 720 // If the tag does not have the conventional format, the value
 721 // returned by Get is unspecified.
 722 func (tag StructTag) Get(key string) string {
 723         for tag != "" {
 724                 // skip leading space
 725                 i := 0
 726                 for i < len(tag) && tag[i] == ' ' {
 727                         i++
 728                 }
 729                 tag = tag[i:]
 730                 if tag == "" {
 731                         break
 732                 }
 733
 734                 // scan to colon.
 735                 // a space or a quote is a syntax error
 736                 i = 0
 737                 for i < len(tag) && tag[i] != ' ' && tag[i] != ':' && tag[i] != '"' {
 738                         i++
 739                 }
 740                 if i+1 >= len(tag) || tag[i] != ':' || tag[i+1] != '"' {
 741                         break
 742                 }
 743                 name := string(tag[:i])
 744                 tag = tag[i+1:]
 745
 746                 // scan quoted string to find value
 747                 i = 1
 748                 for i < len(tag) && tag[i] != '"' {
 749                         if tag[i] == '\\' {
 750                                 i++
 751                         }
 752                         i++
 753                 }
 754                 if i >= len(tag) {
 755                         break
 756                 }
 757                 qvalue := string(tag[:i+1])
 758                 tag = tag[i+1:]
 759
 760                 if key == name {
 761                         value, _ := strconv.Unquote(qvalue)
 762                         return value
 763                 }
 764         }
 765         return ""
 766 }
 767
 768 // Field returns the i'th struct field.
 769 func (t *structType) Field(i int) (f StructField) {
 770         if i < 0 || i >= len(t.fields) {
 771                 return
 772         }
 773         p := &t.fields[i]
 774         f.Type = toType(p.typ)
 775         if p.name != nil {
 776                 f.Name = *p.name
 777         } else {
 778                 t := f.Type
 779                 if t.Kind() == Ptr {
 780                         t = t.Elem()
 781                 }
 782                 f.Name = t.Name()
 783                 f.Anonymous = true
 784         }
 785         if p.pkgPath != nil {
 786                 f.PkgPath = *p.pkgPath
 787         }
 788         if p.tag != nil {
 789                 f.Tag = StructTag(*p.tag)
 790         }
 791         f.Offset = p.offset
 792         f.Index = []int{i}
 793         return
 794 }
 795
 796 // TODO(gri): Should there be an error/bool indicator if the index
 797 //            is wrong for FieldByIndex?
 798
 799 // FieldByIndex returns the nested field corresponding to index.
 800 func (t *structType) FieldByIndex(index []int) (f StructField) {
 801         f.Type = Type(t.toType())
 802         for i, x := range index {
 803                 if i > 0 {
 804                         ft := f.Type
 805                         if ft.Kind() == Ptr && ft.Elem().Kind() == Struct {
 806                                 ft = ft.Elem()
 807                         }
 808                         f.Type = ft
 809                 }
 810                 f = f.Type.Field(x)
 811         }
 812         return
 813 }
 814
 815 const inf = 1 << 30 // infinity - no struct has that many nesting levels
 816
 817 func (t *structType) fieldByNameFunc(match func(string) bool, mark map[*structType]bool, depth int) (ff StructField, fd int) {
 818         fd = inf // field depth
 819
 820         if mark[t] {
 821                 // Struct already seen.
 822                 return
 823         }
 824         mark[t] = true
 825
 826         var fi int // field index
 827         n := 0     // number of matching fields at depth fd
 828 L:
 829         for i := range t.fields {
 830                 f := t.Field(i)
 831                 d := inf
 832                 switch {
 833                 case match(f.Name):
 834                         // Matching top-level field.
 835                         d = depth
 836                 case f.Anonymous:
 837                         ft := f.Type
 838                         if ft.Kind() == Ptr {
 839                                 ft = ft.Elem()
 840                         }
 841                         switch {
 842                         case match(ft.Name()):
 843                                 // Matching anonymous top-level field.
 844                                 d = depth
 845                         case fd > depth:
 846                                 // No top-level field yet; look inside nested structs.
 847                                 if ft.Kind() == Struct {
 848                                         st := (*structType)(unsafe.Pointer(ft.(*commonType)))
 849                                         f, d = st.fieldByNameFunc(match, mark, depth+1)
 850                                 }
 851                         }
 852                 }
 853
 854                 switch {
 855                 case d < fd:
 856                         // Found field at shallower depth.
 857                         ff, fi, fd = f, i, d
 858                         n = 1
 859                 case d == fd:
 860                         // More than one matching field at the same depth (or d, fd == inf).
 861                         // Same as no field found at this depth.
 862                         n++
 863                         if d == depth {
 864                                 // Impossible to find a field at lower depth.
 865                                 break L
 866                         }
 867                 }
 868         }
 869
 870         if n == 1 {
 871                 // Found matching field.
 872                 if depth >= len(ff.Index) {
 873                         ff.Index = make([]int, depth+1)
 874                 }
 875                 if len(ff.Index) > 1 {
 876                         ff.Index[depth] = fi
 877                 }
 878         } else {
 879                 // None or more than one matching field found.
 880                 fd = inf
 881         }
 882
 883         delete(mark, t)
 884         return
 885 }
 886
 887 // FieldByName returns the struct field with the given name
 888 // and a boolean to indicate if the field was found.
 889 func (t *structType) FieldByName(name string) (f StructField, present bool) {
 890         return t.FieldByNameFunc(func(s string) bool { return s == name })
 891 }
 892
 893 // FieldByNameFunc returns the struct field with a name that satisfies the
 894 // match function and a boolean to indicate if the field was found.
 895 func (t *structType) FieldByNameFunc(match func(string) bool) (f StructField, present bool) {
 896         if ff, fd := t.fieldByNameFunc(match, make(map[*structType]bool), 0); fd < inf {
 897                 ff.Index = ff.Index[0 : fd+1]
 898                 f, present = ff, true
 899         }
 900         return
 901 }
 902
 903 // Convert runtime type to reflect type.
 904 func toCommonType(p *runtime.Type) *commonType {
 905         if p == nil {
 906                 return nil
 907         }
 908         x := unsafe.Pointer(p)
 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         return t.(*commonType).ptrTo()
 971 }
 972
 973 func (ct *commonType) ptrTo() *commonType {
 974         if p := ct.ptrToThis; p != nil {
 975                 return toCommonType(p)
 976         }
 977
 978         // Otherwise, synthesize one.
 979         // This only happens for pointers with no methods.
 980         // We keep the mapping in a map on the side, because
 981         // this operation is rare and a separate map lets us keep
 982         // the type structures in read-only memory.
 983         ptrMap.RLock()
 984         if m := ptrMap.m; m != nil {
 985                 if p := m[ct]; p != nil {
 986                         ptrMap.RUnlock()
 987                         return &p.commonType
 988                 }
 989         }
 990         ptrMap.RUnlock()
 991         ptrMap.Lock()
 992         if ptrMap.m == nil {
 993                 ptrMap.m = make(map[*commonType]*ptrType)
 994         }
 995         p := ptrMap.m[ct]
 996         if p != nil {
 997                 // some other goroutine won the race and created it
 998                 ptrMap.Unlock()
 999                 return &p.commonType
1000         }
1001
1002         rt := (*runtime.Type)(unsafe.Pointer(ct))
1003
1004         rp := new(runtime.PtrType)
1005
1006         // initialize p using *byte's ptrType as a prototype.
1007         // have to do assignment as ptrType, not runtime.PtrType,
1008         // in order to write to unexported fields.
1009         p = (*ptrType)(unsafe.Pointer(rp))
1010         bp := (*ptrType)(unsafe.Pointer(unsafe.Typeof((*byte)(nil)).(*runtime.PtrType)))
1011         *p = *bp
1012
1013         s := "*" + *ct.string
1014         p.string = &s
1015
1016         // For the type structures linked into the binary, the
1017         // compiler provides a good hash of the string.
1018         // Create a good hash for the new string by using
1019         // the FNV-1 hash's mixing function to combine the
1020         // old hash and the new "*".
1021         p.hash = ct.hash*16777619 ^ '*'
1022
1023         p.uncommonType = nil
1024         p.ptrToThis = nil
1025         p.elem = (*runtime.Type)(unsafe.Pointer(ct))
1026
1027         ptrMap.m[ct] = p
1028         ptrMap.Unlock()
1029         return &p.commonType
1030 }
1031
1032 func (t *commonType) Implements(u Type) bool {
1033         if u == nil {
1034                 panic("reflect: nil type passed to Type.Implements")
1035         }
1036         if u.Kind() != Interface {
1037                 panic("reflect: non-interface type passed to Type.Implements")
1038         }
1039         return implements(u.(*commonType), t)
1040 }
1041
1042 func (t *commonType) AssignableTo(u Type) bool {
1043         if u == nil {
1044                 panic("reflect: nil type passed to Type.AssignableTo")
1045         }
1046         uu := u.(*commonType)
1047         return directlyAssignable(uu, t) || implements(uu, t)
1048 }
1049
1050 // implements returns true if the type V implements the interface type T.
1051 func implements(T, V *commonType) bool {
1052         if T.Kind() != Interface {
1053                 return false
1054         }
1055         t := (*interfaceType)(unsafe.Pointer(T))
1056         if len(t.methods) == 0 {
1057                 return true
1058         }
1059
1060         // The same algorithm applies in both cases, but the
1061         // method tables for an interface type and a concrete type
1062         // are different, so the code is duplicated.
1063         // In both cases the algorithm is a linear scan over the two
1064         // lists - T's methods and V's methods - simultaneously.
1065         // Since method tables are stored in a unique sorted order
1066         // (alphabetical, with no duplicate method names), the scan
1067         // through V's methods must hit a match for each of T's
1068         // methods along the way, or else V does not implement T.
1069         // This lets us run the scan in overall linear time instead of
1070         // the quadratic time  a naive search would require.
1071         // See also ../runtime/iface.c.
1072         if V.Kind() == Interface {
1073                 v := (*interfaceType)(unsafe.Pointer(V))
1074                 i := 0
1075                 for j := 0; j < len(v.methods); j++ {
1076                         tm := &t.methods[i]
1077                         vm := &v.methods[j]
1078                         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() {
1079                                 if i++; i >= len(t.methods) {
1080                                         return true
1081                                 }
1082                         }
1083                 }
1084                 return false
1085         }
1086
1087         v := V.uncommon()
1088         if v == nil {
1089                 return false
1090         }
1091         i := 0
1092         for j := 0; j < len(v.methods); j++ {
1093                 tm := &t.methods[i]
1094                 vm := &v.methods[j]
1095                 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() {
1096                         if i++; i >= len(t.methods) {
1097                                 return true
1098                         }
1099                 }
1100         }
1101         return false
1102 }
1103
1104 // directlyAssignable returns true if a value x of type V can be directly
1105 // assigned (using memmove) to a value of type T.
1106 // http://golang.org/doc/go_spec.html#Assignability
1107 // Ignoring the interface rules (implemented elsewhere)
1108 // and the ideal constant rules (no ideal constants at run time).
1109 func directlyAssignable(T, V *commonType) bool {
1110         // x's type V is identical to T?
1111         if T == V {
1112                 return true
1113         }
1114
1115         // Otherwise at least one of T and V must be unnamed
1116         // and they must have the same kind.
1117         if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
1118                 return false
1119         }
1120
1121         // x's type T and V have identical underlying types.
1122         // Since at least one is unnamed, only the composite types
1123         // need to be considered.
1124         switch T.Kind() {
1125         case Array:
1126                 return T.Elem() == V.Elem() && T.Len() == V.Len()
1127
1128         case Chan:
1129                 // Special case:
1130                 // x is a bidirectional channel value, T is a channel type,
1131                 // and x's type V and T have identical element types.
1132                 if V.ChanDir() == BothDir && T.Elem() == V.Elem() {
1133                         return true
1134                 }
1135
1136                 // Otherwise continue test for identical underlying type.
1137                 return V.ChanDir() == T.ChanDir() && T.Elem() == V.Elem()
1138
1139         case Func:
1140                 t := (*funcType)(unsafe.Pointer(T))
1141                 v := (*funcType)(unsafe.Pointer(V))
1142                 if t.dotdotdot != v.dotdotdot || len(t.in) != len(v.in) || len(t.out) != len(v.out) {
1143                         return false
1144                 }
1145                 for i, typ := range t.in {
1146                         if typ != v.in[i] {
1147                                 return false
1148                         }
1149                 }
1150                 for i, typ := range t.out {
1151                         if typ != v.out[i] {
1152                                 return false
1153                         }
1154                 }
1155                 return true
1156
1157         case Interface:
1158                 t := (*interfaceType)(unsafe.Pointer(T))
1159                 v := (*interfaceType)(unsafe.Pointer(V))
1160                 if len(t.methods) == 0 && len(v.methods) == 0 {
1161                         return true
1162                 }
1163                 // Might have the same methods but still
1164                 // need a run time conversion.
1165                 return false
1166
1167         case Map:
1168                 return T.Key() == V.Key() && T.Elem() == V.Elem()
1169
1170         case Ptr, Slice:
1171                 return T.Elem() == V.Elem()
1172
1173         case Struct:
1174                 t := (*structType)(unsafe.Pointer(T))
1175                 v := (*structType)(unsafe.Pointer(V))
1176                 if len(t.fields) != len(v.fields) {
1177                         return false
1178                 }
1179                 for i := range t.fields {
1180                         tf := &t.fields[i]
1181                         vf := &v.fields[i]
1182                         if tf.name != vf.name || tf.pkgPath != vf.pkgPath ||
1183                                 tf.typ != vf.typ || tf.tag != vf.tag || tf.offset != vf.offset {
1184                                 return false
1185                         }
1186                 }
1187                 return true
1188         }
1189
1190         return false
1191 }