OSDN Git Service

compiler, reflect: Fix hash codes of named types, fix PtrTo hash.
[pf3gnuchains/gcc-fork.git] / 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         s := "*" + *ct.string
1003
1004         canonicalTypeLock.RLock()
1005         r, ok := canonicalType[s]
1006         canonicalTypeLock.RUnlock()
1007         if ok {
1008                 ptrMap.m[ct] = (*ptrType)(unsafe.Pointer(r.(*commonType)))
1009                 ptrMap.Unlock()
1010                 return r.(*commonType)
1011         }
1012
1013         rp := new(runtime.PtrType)
1014
1015         // initialize p using *byte's ptrType as a prototype.
1016         // have to do assignment as ptrType, not runtime.PtrType,
1017         // in order to write to unexported fields.
1018         p = (*ptrType)(unsafe.Pointer(rp))
1019         bp := (*ptrType)(unsafe.Pointer(unsafe.Typeof((*byte)(nil)).(*runtime.PtrType)))
1020         *p = *bp
1021
1022         p.string = &s
1023
1024         // For the type structures linked into the binary, the
1025         // compiler provides a good hash of the string.
1026         // Create a good hash for the new string by using
1027         // the FNV-1 hash's mixing function to combine the
1028         // old hash and the new "*".
1029         // p.hash = ct.hash*16777619 ^ '*'
1030         // This is the gccgo version.
1031         p.hash = (ct.hash << 4) + 9
1032
1033         p.uncommonType = nil
1034         p.ptrToThis = nil
1035         p.elem = (*runtime.Type)(unsafe.Pointer(ct))
1036
1037         p = canonicalize(p).(*ptrType)
1038
1039         ptrMap.m[ct] = p
1040         ptrMap.Unlock()
1041         return &p.commonType
1042 }
1043
1044 func (t *commonType) Implements(u Type) bool {
1045         if u == nil {
1046                 panic("reflect: nil type passed to Type.Implements")
1047         }
1048         if u.Kind() != Interface {
1049                 panic("reflect: non-interface type passed to Type.Implements")
1050         }
1051         return implements(u.(*commonType), t)
1052 }
1053
1054 func (t *commonType) AssignableTo(u Type) bool {
1055         if u == nil {
1056                 panic("reflect: nil type passed to Type.AssignableTo")
1057         }
1058         uu := u.(*commonType)
1059         return directlyAssignable(uu, t) || implements(uu, t)
1060 }
1061
1062 // implements returns true if the type V implements the interface type T.
1063 func implements(T, V *commonType) bool {
1064         if T.Kind() != Interface {
1065                 return false
1066         }
1067         t := (*interfaceType)(unsafe.Pointer(T))
1068         if len(t.methods) == 0 {
1069                 return true
1070         }
1071
1072         // The same algorithm applies in both cases, but the
1073         // method tables for an interface type and a concrete type
1074         // are different, so the code is duplicated.
1075         // In both cases the algorithm is a linear scan over the two
1076         // lists - T's methods and V's methods - simultaneously.
1077         // Since method tables are stored in a unique sorted order
1078         // (alphabetical, with no duplicate method names), the scan
1079         // through V's methods must hit a match for each of T's
1080         // methods along the way, or else V does not implement T.
1081         // This lets us run the scan in overall linear time instead of
1082         // the quadratic time  a naive search would require.
1083         // See also ../runtime/iface.c.
1084         if V.Kind() == Interface {
1085                 v := (*interfaceType)(unsafe.Pointer(V))
1086                 i := 0
1087                 for j := 0; j < len(v.methods); j++ {
1088                         tm := &t.methods[i]
1089                         vm := &v.methods[j]
1090                         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() {
1091                                 if i++; i >= len(t.methods) {
1092                                         return true
1093                                 }
1094                         }
1095                 }
1096                 return false
1097         }
1098
1099         v := V.uncommon()
1100         if v == nil {
1101                 return false
1102         }
1103         i := 0
1104         for j := 0; j < len(v.methods); j++ {
1105                 tm := &t.methods[i]
1106                 vm := &v.methods[j]
1107                 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() {
1108                         if i++; i >= len(t.methods) {
1109                                 return true
1110                         }
1111                 }
1112         }
1113         return false
1114 }
1115
1116 // directlyAssignable returns true if a value x of type V can be directly
1117 // assigned (using memmove) to a value of type T.
1118 // http://golang.org/doc/go_spec.html#Assignability
1119 // Ignoring the interface rules (implemented elsewhere)
1120 // and the ideal constant rules (no ideal constants at run time).
1121 func directlyAssignable(T, V *commonType) bool {
1122         // x's type V is identical to T?
1123         if T == V {
1124                 return true
1125         }
1126
1127         // Otherwise at least one of T and V must be unnamed
1128         // and they must have the same kind.
1129         if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
1130                 return false
1131         }
1132
1133         // x's type T and V have identical underlying types.
1134         // Since at least one is unnamed, only the composite types
1135         // need to be considered.
1136         switch T.Kind() {
1137         case Array:
1138                 return T.Elem() == V.Elem() && T.Len() == V.Len()
1139
1140         case Chan:
1141                 // Special case:
1142                 // x is a bidirectional channel value, T is a channel type,
1143                 // and x's type V and T have identical element types.
1144                 if V.ChanDir() == BothDir && T.Elem() == V.Elem() {
1145                         return true
1146                 }
1147
1148                 // Otherwise continue test for identical underlying type.
1149                 return V.ChanDir() == T.ChanDir() && T.Elem() == V.Elem()
1150
1151         case Func:
1152                 t := (*funcType)(unsafe.Pointer(T))
1153                 v := (*funcType)(unsafe.Pointer(V))
1154                 if t.dotdotdot != v.dotdotdot || len(t.in) != len(v.in) || len(t.out) != len(v.out) {
1155                         return false
1156                 }
1157                 for i, typ := range t.in {
1158                         if typ != v.in[i] {
1159                                 return false
1160                         }
1161                 }
1162                 for i, typ := range t.out {
1163                         if typ != v.out[i] {
1164                                 return false
1165                         }
1166                 }
1167                 return true
1168
1169         case Interface:
1170                 t := (*interfaceType)(unsafe.Pointer(T))
1171                 v := (*interfaceType)(unsafe.Pointer(V))
1172                 if len(t.methods) == 0 && len(v.methods) == 0 {
1173                         return true
1174                 }
1175                 // Might have the same methods but still
1176                 // need a run time conversion.
1177                 return false
1178
1179         case Map:
1180                 return T.Key() == V.Key() && T.Elem() == V.Elem()
1181
1182         case Ptr, Slice:
1183                 return T.Elem() == V.Elem()
1184
1185         case Struct:
1186                 t := (*structType)(unsafe.Pointer(T))
1187                 v := (*structType)(unsafe.Pointer(V))
1188                 if len(t.fields) != len(v.fields) {
1189                         return false
1190                 }
1191                 for i := range t.fields {
1192                         tf := &t.fields[i]
1193                         vf := &v.fields[i]
1194                         if tf.name != vf.name || tf.pkgPath != vf.pkgPath ||
1195                                 tf.typ != vf.typ || tf.tag != vf.tag || tf.offset != vf.offset {
1196                                 return false
1197                         }
1198                 }
1199                 return true
1200         }
1201
1202         return false
1203 }