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 or predeclared 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         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
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 }