Source file src/pkg/reflect/type.go

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