Source file src/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	// https://golang.org/doc/articles/laws_of_reflection.html
    16	package reflect
    17	
    18	import (
    19		"runtime"
    20		"strconv"
    21		"sync"
    22		"unicode"
    23		"unicode/utf8"
    24		"unsafe"
    25	)
    26	
    27	// Type is the representation of a Go type.
    28	//
    29	// Not all methods apply to all kinds of types. Restrictions,
    30	// if any, are noted in the documentation for each method.
    31	// Use the Kind method to find out the kind of type before
    32	// calling kind-specific methods. Calling a method
    33	// inappropriate to the kind of type causes a run-time panic.
    34	//
    35	// Type values are comparable, such as with the == operator,
    36	// so they can be used as map keys.
    37	// Two Type values are equal if they represent identical types.
    38	type Type interface {
    39		// Methods applicable to all types.
    40	
    41		// Align returns the alignment in bytes of a value of
    42		// this type when allocated in memory.
    43		Align() int
    44	
    45		// FieldAlign returns the alignment in bytes of a value of
    46		// this type when used as a field in a struct.
    47		FieldAlign() int
    48	
    49		// Method returns the i'th method in the type's method set.
    50		// It panics if i is not in the range [0, NumMethod()).
    51		//
    52		// For a non-interface type T or *T, the returned Method's Type and Func
    53		// fields describe a function whose first argument is the receiver.
    54		//
    55		// For an interface type, the returned Method's Type field gives the
    56		// method signature, without a receiver, and the Func field is nil.
    57		//
    58		// Only exported methods are accessible and they are sorted in
    59		// lexicographic order.
    60		Method(int) Method
    61	
    62		// MethodByName returns the method with that name in the type's
    63		// method set and a boolean indicating if the method was found.
    64		//
    65		// For a non-interface type T or *T, the returned Method's Type and Func
    66		// fields describe a function whose first argument is the receiver.
    67		//
    68		// For an interface type, the returned Method's Type field gives the
    69		// method signature, without a receiver, and the Func field is nil.
    70		MethodByName(string) (Method, bool)
    71	
    72		// NumMethod returns the number of exported methods in the type's method set.
    73		NumMethod() int
    74	
    75		// Name returns the type's name within its package for a defined type.
    76		// For other (non-defined) types it returns the empty string.
    77		Name() string
    78	
    79		// PkgPath returns a defined type's package path, that is, the import path
    80		// that uniquely identifies the package, such as "encoding/base64".
    81		// If the type was predeclared (string, error) or not defined (*T, struct{},
    82		// []int, or A where A is an alias for a non-defined type), the package path
    83		// will be the empty string.
    84		PkgPath() string
    85	
    86		// Size returns the number of bytes needed to store
    87		// a value of the given type; it is analogous to unsafe.Sizeof.
    88		Size() uintptr
    89	
    90		// String returns a string representation of the type.
    91		// The string representation may use shortened package names
    92		// (e.g., base64 instead of "encoding/base64") and is not
    93		// guaranteed to be unique among types. To test for type identity,
    94		// compare the Types directly.
    95		String() string
    96	
    97		// Kind returns the specific kind of this type.
    98		Kind() Kind
    99	
   100		// Implements reports whether the type implements the interface type u.
   101		Implements(u Type) bool
   102	
   103		// AssignableTo reports whether a value of the type is assignable to type u.
   104		AssignableTo(u Type) bool
   105	
   106		// ConvertibleTo reports whether a value of the type is convertible to type u.
   107		ConvertibleTo(u Type) bool
   108	
   109		// Comparable reports whether values of this type are comparable.
   110		Comparable() bool
   111	
   112		// Methods applicable only to some types, depending on Kind.
   113		// The methods allowed for each kind are:
   114		//
   115		//	Int*, Uint*, Float*, Complex*: Bits
   116		//	Array: Elem, Len
   117		//	Chan: ChanDir, Elem
   118		//	Func: In, NumIn, Out, NumOut, IsVariadic.
   119		//	Map: Key, Elem
   120		//	Ptr: Elem
   121		//	Slice: Elem
   122		//	Struct: Field, FieldByIndex, FieldByName, FieldByNameFunc, NumField
   123	
   124		// Bits returns the size of the type in bits.
   125		// It panics if the type's Kind is not one of the
   126		// sized or unsized Int, Uint, Float, or Complex kinds.
   127		Bits() int
   128	
   129		// ChanDir returns a channel type's direction.
   130		// It panics if the type's Kind is not Chan.
   131		ChanDir() ChanDir
   132	
   133		// IsVariadic reports whether a function type's final input parameter
   134		// is a "..." parameter. If so, t.In(t.NumIn() - 1) returns the parameter's
   135		// implicit actual type []T.
   136		//
   137		// For concreteness, if t represents func(x int, y ... float64), then
   138		//
   139		//	t.NumIn() == 2
   140		//	t.In(0) is the reflect.Type for "int"
   141		//	t.In(1) is the reflect.Type for "[]float64"
   142		//	t.IsVariadic() == true
   143		//
   144		// IsVariadic panics if the type's Kind is not Func.
   145		IsVariadic() bool
   146	
   147		// Elem returns a type's element type.
   148		// It panics if the type's Kind is not Array, Chan, Map, Ptr, or Slice.
   149		Elem() Type
   150	
   151		// Field returns a struct type's i'th field.
   152		// It panics if the type's Kind is not Struct.
   153		// It panics if i is not in the range [0, NumField()).
   154		Field(i int) StructField
   155	
   156		// FieldByIndex returns the nested field corresponding
   157		// to the index sequence. It is equivalent to calling Field
   158		// successively for each index i.
   159		// It panics if the type's Kind is not Struct.
   160		FieldByIndex(index []int) StructField
   161	
   162		// FieldByName returns the struct field with the given name
   163		// and a boolean indicating if the field was found.
   164		FieldByName(name string) (StructField, bool)
   165	
   166		// FieldByNameFunc returns the struct field with a name
   167		// that satisfies the match function and a boolean indicating if
   168		// the field was found.
   169		//
   170		// FieldByNameFunc considers the fields in the struct itself
   171		// and then the fields in any embedded structs, in breadth first order,
   172		// stopping at the shallowest nesting depth containing one or more
   173		// fields satisfying the match function. If multiple fields at that depth
   174		// satisfy the match function, they cancel each other
   175		// and FieldByNameFunc returns no match.
   176		// This behavior mirrors Go's handling of name lookup in
   177		// structs containing embedded fields.
   178		FieldByNameFunc(match func(string) bool) (StructField, bool)
   179	
   180		// In returns the type of a function type's i'th input parameter.
   181		// It panics if the type's Kind is not Func.
   182		// It panics if i is not in the range [0, NumIn()).
   183		In(i int) Type
   184	
   185		// Key returns a map type's key type.
   186		// It panics if the type's Kind is not Map.
   187		Key() Type
   188	
   189		// Len returns an array type's length.
   190		// It panics if the type's Kind is not Array.
   191		Len() int
   192	
   193		// NumField returns a struct type's field count.
   194		// It panics if the type's Kind is not Struct.
   195		NumField() int
   196	
   197		// NumIn returns a function type's input parameter count.
   198		// It panics if the type's Kind is not Func.
   199		NumIn() int
   200	
   201		// NumOut returns a function type's output parameter count.
   202		// It panics if the type's Kind is not Func.
   203		NumOut() int
   204	
   205		// Out returns the type of a function type's i'th output parameter.
   206		// It panics if the type's Kind is not Func.
   207		// It panics if i is not in the range [0, NumOut()).
   208		Out(i int) Type
   209	
   210		common() *rtype
   211		uncommon() *uncommonType
   212	}
   213	
   214	// BUG(rsc): FieldByName and related functions consider struct field names to be equal
   215	// if the names are equal, even if they are unexported names originating
   216	// in different packages. The practical effect of this is that the result of
   217	// t.FieldByName("x") is not well defined if the struct type t contains
   218	// multiple fields named x (embedded from different packages).
   219	// FieldByName may return one of the fields named x or may report that there are none.
   220	// See https://golang.org/issue/4876 for more details.
   221	
   222	/*
   223	 * These data structures are known to the compiler (../../cmd/internal/gc/reflect.go).
   224	 * A few are known to ../runtime/type.go to convey to debuggers.
   225	 * They are also known to ../runtime/type.go.
   226	 */
   227	
   228	// A Kind represents the specific kind of type that a Type represents.
   229	// The zero Kind is not a valid kind.
   230	type Kind uint
   231	
   232	const (
   233		Invalid Kind = iota
   234		Bool
   235		Int
   236		Int8
   237		Int16
   238		Int32
   239		Int64
   240		Uint
   241		Uint8
   242		Uint16
   243		Uint32
   244		Uint64
   245		Uintptr
   246		Float32
   247		Float64
   248		Complex64
   249		Complex128
   250		Array
   251		Chan
   252		Func
   253		Interface
   254		Map
   255		Ptr
   256		Slice
   257		String
   258		Struct
   259		UnsafePointer
   260	)
   261	
   262	// tflag is used by an rtype to signal what extra type information is
   263	// available in the memory directly following the rtype value.
   264	//
   265	// tflag values must be kept in sync with copies in:
   266	//	cmd/compile/internal/gc/reflect.go
   267	//	cmd/link/internal/ld/decodesym.go
   268	//	runtime/type.go
   269	type tflag uint8
   270	
   271	const (
   272		// tflagUncommon means that there is a pointer, *uncommonType,
   273		// just beyond the outer type structure.
   274		//
   275		// For example, if t.Kind() == Struct and t.tflag&tflagUncommon != 0,
   276		// then t has uncommonType data and it can be accessed as:
   277		//
   278		//	type tUncommon struct {
   279		//		structType
   280		//		u uncommonType
   281		//	}
   282		//	u := &(*tUncommon)(unsafe.Pointer(t)).u
   283		tflagUncommon tflag = 1 << 0
   284	
   285		// tflagExtraStar means the name in the str field has an
   286		// extraneous '*' prefix. This is because for most types T in
   287		// a program, the type *T also exists and reusing the str data
   288		// saves binary size.
   289		tflagExtraStar tflag = 1 << 1
   290	
   291		// tflagNamed means the type has a name.
   292		tflagNamed tflag = 1 << 2
   293	)
   294	
   295	// rtype is the common implementation of most values.
   296	// It is embedded in other struct types.
   297	//
   298	// rtype must be kept in sync with ../runtime/type.go:/^type._type.
   299	type rtype struct {
   300		size       uintptr
   301		ptrdata    uintptr  // number of bytes in the type that can contain pointers
   302		hash       uint32   // hash of type; avoids computation in hash tables
   303		tflag      tflag    // extra type information flags
   304		align      uint8    // alignment of variable with this type
   305		fieldAlign uint8    // alignment of struct field with this type
   306		kind       uint8    // enumeration for C
   307		alg        *typeAlg // algorithm table
   308		gcdata     *byte    // garbage collection data
   309		str        nameOff  // string form
   310		ptrToThis  typeOff  // type for pointer to this type, may be zero
   311	}
   312	
   313	// a copy of runtime.typeAlg
   314	type typeAlg struct {
   315		// function for hashing objects of this type
   316		// (ptr to object, seed) -> hash
   317		hash func(unsafe.Pointer, uintptr) uintptr
   318		// function for comparing objects of this type
   319		// (ptr to object A, ptr to object B) -> ==?
   320		equal func(unsafe.Pointer, unsafe.Pointer) bool
   321	}
   322	
   323	// Method on non-interface type
   324	type method struct {
   325		name nameOff // name of method
   326		mtyp typeOff // method type (without receiver)
   327		ifn  textOff // fn used in interface call (one-word receiver)
   328		tfn  textOff // fn used for normal method call
   329	}
   330	
   331	// uncommonType is present only for defined types or types with methods
   332	// (if T is a defined type, the uncommonTypes for T and *T have methods).
   333	// Using a pointer to this struct reduces the overall size required
   334	// to describe a non-defined type with no methods.
   335	type uncommonType struct {
   336		pkgPath nameOff // import path; empty for built-in types like int, string
   337		mcount  uint16  // number of methods
   338		xcount  uint16  // number of exported methods
   339		moff    uint32  // offset from this uncommontype to [mcount]method
   340		_       uint32  // unused
   341	}
   342	
   343	// ChanDir represents a channel type's direction.
   344	type ChanDir int
   345	
   346	const (
   347		RecvDir ChanDir             = 1 << iota // <-chan
   348		SendDir                                 // chan<-
   349		BothDir = RecvDir | SendDir             // chan
   350	)
   351	
   352	// arrayType represents a fixed array type.
   353	type arrayType struct {
   354		rtype
   355		elem  *rtype // array element type
   356		slice *rtype // slice type
   357		len   uintptr
   358	}
   359	
   360	// chanType represents a channel type.
   361	type chanType struct {
   362		rtype
   363		elem *rtype  // channel element type
   364		dir  uintptr // channel direction (ChanDir)
   365	}
   366	
   367	// funcType represents a function type.
   368	//
   369	// A *rtype for each in and out parameter is stored in an array that
   370	// directly follows the funcType (and possibly its uncommonType). So
   371	// a function type with one method, one input, and one output is:
   372	//
   373	//	struct {
   374	//		funcType
   375	//		uncommonType
   376	//		[2]*rtype    // [0] is in, [1] is out
   377	//	}
   378	type funcType struct {
   379		rtype
   380		inCount  uint16
   381		outCount uint16 // top bit is set if last input parameter is ...
   382	}
   383	
   384	// imethod represents a method on an interface type
   385	type imethod struct {
   386		name nameOff // name of method
   387		typ  typeOff // .(*FuncType) underneath
   388	}
   389	
   390	// interfaceType represents an interface type.
   391	type interfaceType struct {
   392		rtype
   393		pkgPath name      // import path
   394		methods []imethod // sorted by hash
   395	}
   396	
   397	// mapType represents a map type.
   398	type mapType struct {
   399		rtype
   400		key        *rtype // map key type
   401		elem       *rtype // map element (value) type
   402		bucket     *rtype // internal bucket structure
   403		keysize    uint8  // size of key slot
   404		valuesize  uint8  // size of value slot
   405		bucketsize uint16 // size of bucket
   406		flags      uint32
   407	}
   408	
   409	// ptrType represents a pointer type.
   410	type ptrType struct {
   411		rtype
   412		elem *rtype // pointer element (pointed at) type
   413	}
   414	
   415	// sliceType represents a slice type.
   416	type sliceType struct {
   417		rtype
   418		elem *rtype // slice element type
   419	}
   420	
   421	// Struct field
   422	type structField struct {
   423		name        name    // name is always non-empty
   424		typ         *rtype  // type of field
   425		offsetEmbed uintptr // byte offset of field<<1 | isEmbedded
   426	}
   427	
   428	func (f *structField) offset() uintptr {
   429		return f.offsetEmbed >> 1
   430	}
   431	
   432	func (f *structField) embedded() bool {
   433		return f.offsetEmbed&1 != 0
   434	}
   435	
   436	// structType represents a struct type.
   437	type structType struct {
   438		rtype
   439		pkgPath name
   440		fields  []structField // sorted by offset
   441	}
   442	
   443	// name is an encoded type name with optional extra data.
   444	//
   445	// The first byte is a bit field containing:
   446	//
   447	//	1<<0 the name is exported
   448	//	1<<1 tag data follows the name
   449	//	1<<2 pkgPath nameOff follows the name and tag
   450	//
   451	// The next two bytes are the data length:
   452	//
   453	//	 l := uint16(data[1])<<8 | uint16(data[2])
   454	//
   455	// Bytes [3:3+l] are the string data.
   456	//
   457	// If tag data follows then bytes 3+l and 3+l+1 are the tag length,
   458	// with the data following.
   459	//
   460	// If the import path follows, then 4 bytes at the end of
   461	// the data form a nameOff. The import path is only set for concrete
   462	// methods that are defined in a different package than their type.
   463	//
   464	// If a name starts with "*", then the exported bit represents
   465	// whether the pointed to type is exported.
   466	type name struct {
   467		bytes *byte
   468	}
   469	
   470	func (n name) data(off int, whySafe string) *byte {
   471		return (*byte)(add(unsafe.Pointer(n.bytes), uintptr(off), whySafe))
   472	}
   473	
   474	func (n name) isExported() bool {
   475		return (*n.bytes)&(1<<0) != 0
   476	}
   477	
   478	func (n name) nameLen() int {
   479		return int(uint16(*n.data(1, "name len field"))<<8 | uint16(*n.data(2, "name len field")))
   480	}
   481	
   482	func (n name) tagLen() int {
   483		if *n.data(0, "name flag field")&(1<<1) == 0 {
   484			return 0
   485		}
   486		off := 3 + n.nameLen()
   487		return int(uint16(*n.data(off, "name taglen field"))<<8 | uint16(*n.data(off+1, "name taglen field")))
   488	}
   489	
   490	func (n name) name() (s string) {
   491		if n.bytes == nil {
   492			return
   493		}
   494		b := (*[4]byte)(unsafe.Pointer(n.bytes))
   495	
   496		hdr := (*stringHeader)(unsafe.Pointer(&s))
   497		hdr.Data = unsafe.Pointer(&b[3])
   498		hdr.Len = int(b[1])<<8 | int(b[2])
   499		return s
   500	}
   501	
   502	func (n name) tag() (s string) {
   503		tl := n.tagLen()
   504		if tl == 0 {
   505			return ""
   506		}
   507		nl := n.nameLen()
   508		hdr := (*stringHeader)(unsafe.Pointer(&s))
   509		hdr.Data = unsafe.Pointer(n.data(3+nl+2, "non-empty string"))
   510		hdr.Len = tl
   511		return s
   512	}
   513	
   514	func (n name) pkgPath() string {
   515		if n.bytes == nil || *n.data(0, "name flag field")&(1<<2) == 0 {
   516			return ""
   517		}
   518		off := 3 + n.nameLen()
   519		if tl := n.tagLen(); tl > 0 {
   520			off += 2 + tl
   521		}
   522		var nameOff int32
   523		// Note that this field may not be aligned in memory,
   524		// so we cannot use a direct int32 assignment here.
   525		copy((*[4]byte)(unsafe.Pointer(&nameOff))[:], (*[4]byte)(unsafe.Pointer(n.data(off, "name offset field")))[:])
   526		pkgPathName := name{(*byte)(resolveTypeOff(unsafe.Pointer(n.bytes), nameOff))}
   527		return pkgPathName.name()
   528	}
   529	
   530	// round n up to a multiple of a.  a must be a power of 2.
   531	func round(n, a uintptr) uintptr {
   532		return (n + a - 1) &^ (a - 1)
   533	}
   534	
   535	func newName(n, tag string, exported bool) name {
   536		if len(n) > 1<<16-1 {
   537			panic("reflect.nameFrom: name too long: " + n)
   538		}
   539		if len(tag) > 1<<16-1 {
   540			panic("reflect.nameFrom: tag too long: " + tag)
   541		}
   542	
   543		var bits byte
   544		l := 1 + 2 + len(n)
   545		if exported {
   546			bits |= 1 << 0
   547		}
   548		if len(tag) > 0 {
   549			l += 2 + len(tag)
   550			bits |= 1 << 1
   551		}
   552	
   553		b := make([]byte, l)
   554		b[0] = bits
   555		b[1] = uint8(len(n) >> 8)
   556		b[2] = uint8(len(n))
   557		copy(b[3:], n)
   558		if len(tag) > 0 {
   559			tb := b[3+len(n):]
   560			tb[0] = uint8(len(tag) >> 8)
   561			tb[1] = uint8(len(tag))
   562			copy(tb[2:], tag)
   563		}
   564	
   565		return name{bytes: &b[0]}
   566	}
   567	
   568	/*
   569	 * The compiler knows the exact layout of all the data structures above.
   570	 * The compiler does not know about the data structures and methods below.
   571	 */
   572	
   573	// Method represents a single method.
   574	type Method struct {
   575		// Name is the method name.
   576		// PkgPath is the package path that qualifies a lower case (unexported)
   577		// method name. It is empty for upper case (exported) method names.
   578		// The combination of PkgPath and Name uniquely identifies a method
   579		// in a method set.
   580		// See https://golang.org/ref/spec#Uniqueness_of_identifiers
   581		Name    string
   582		PkgPath string
   583	
   584		Type  Type  // method type
   585		Func  Value // func with receiver as first argument
   586		Index int   // index for Type.Method
   587	}
   588	
   589	const (
   590		kindDirectIface = 1 << 5
   591		kindGCProg      = 1 << 6 // Type.gc points to GC program
   592		kindMask        = (1 << 5) - 1
   593	)
   594	
   595	// String returns the name of k.
   596	func (k Kind) String() string {
   597		if int(k) < len(kindNames) {
   598			return kindNames[k]
   599		}
   600		return "kind" + strconv.Itoa(int(k))
   601	}
   602	
   603	var kindNames = []string{
   604		Invalid:       "invalid",
   605		Bool:          "bool",
   606		Int:           "int",
   607		Int8:          "int8",
   608		Int16:         "int16",
   609		Int32:         "int32",
   610		Int64:         "int64",
   611		Uint:          "uint",
   612		Uint8:         "uint8",
   613		Uint16:        "uint16",
   614		Uint32:        "uint32",
   615		Uint64:        "uint64",
   616		Uintptr:       "uintptr",
   617		Float32:       "float32",
   618		Float64:       "float64",
   619		Complex64:     "complex64",
   620		Complex128:    "complex128",
   621		Array:         "array",
   622		Chan:          "chan",
   623		Func:          "func",
   624		Interface:     "interface",
   625		Map:           "map",
   626		Ptr:           "ptr",
   627		Slice:         "slice",
   628		String:        "string",
   629		Struct:        "struct",
   630		UnsafePointer: "unsafe.Pointer",
   631	}
   632	
   633	func (t *uncommonType) methods() []method {
   634		if t.mcount == 0 {
   635			return nil
   636		}
   637		return (*[1 << 16]method)(add(unsafe.Pointer(t), uintptr(t.moff), "t.mcount > 0"))[:t.mcount:t.mcount]
   638	}
   639	
   640	func (t *uncommonType) exportedMethods() []method {
   641		if t.xcount == 0 {
   642			return nil
   643		}
   644		return (*[1 << 16]method)(add(unsafe.Pointer(t), uintptr(t.moff), "t.xcount > 0"))[:t.xcount:t.xcount]
   645	}
   646	
   647	// resolveNameOff resolves a name offset from a base pointer.
   648	// The (*rtype).nameOff method is a convenience wrapper for this function.
   649	// Implemented in the runtime package.
   650	func resolveNameOff(ptrInModule unsafe.Pointer, off int32) unsafe.Pointer
   651	
   652	// resolveTypeOff resolves an *rtype offset from a base type.
   653	// The (*rtype).typeOff method is a convenience wrapper for this function.
   654	// Implemented in the runtime package.
   655	func resolveTypeOff(rtype unsafe.Pointer, off int32) unsafe.Pointer
   656	
   657	// resolveTextOff resolves an function pointer offset from a base type.
   658	// The (*rtype).textOff method is a convenience wrapper for this function.
   659	// Implemented in the runtime package.
   660	func resolveTextOff(rtype unsafe.Pointer, off int32) unsafe.Pointer
   661	
   662	// addReflectOff adds a pointer to the reflection lookup map in the runtime.
   663	// It returns a new ID that can be used as a typeOff or textOff, and will
   664	// be resolved correctly. Implemented in the runtime package.
   665	func addReflectOff(ptr unsafe.Pointer) int32
   666	
   667	// resolveReflectType adds a name to the reflection lookup map in the runtime.
   668	// It returns a new nameOff that can be used to refer to the pointer.
   669	func resolveReflectName(n name) nameOff {
   670		return nameOff(addReflectOff(unsafe.Pointer(n.bytes)))
   671	}
   672	
   673	// resolveReflectType adds a *rtype to the reflection lookup map in the runtime.
   674	// It returns a new typeOff that can be used to refer to the pointer.
   675	func resolveReflectType(t *rtype) typeOff {
   676		return typeOff(addReflectOff(unsafe.Pointer(t)))
   677	}
   678	
   679	// resolveReflectText adds a function pointer to the reflection lookup map in
   680	// the runtime. It returns a new textOff that can be used to refer to the
   681	// pointer.
   682	func resolveReflectText(ptr unsafe.Pointer) textOff {
   683		return textOff(addReflectOff(ptr))
   684	}
   685	
   686	type nameOff int32 // offset to a name
   687	type typeOff int32 // offset to an *rtype
   688	type textOff int32 // offset from top of text section
   689	
   690	func (t *rtype) nameOff(off nameOff) name {
   691		return name{(*byte)(resolveNameOff(unsafe.Pointer(t), int32(off)))}
   692	}
   693	
   694	func (t *rtype) typeOff(off typeOff) *rtype {
   695		return (*rtype)(resolveTypeOff(unsafe.Pointer(t), int32(off)))
   696	}
   697	
   698	func (t *rtype) textOff(off textOff) unsafe.Pointer {
   699		return resolveTextOff(unsafe.Pointer(t), int32(off))
   700	}
   701	
   702	func (t *rtype) uncommon() *uncommonType {
   703		if t.tflag&tflagUncommon == 0 {
   704			return nil
   705		}
   706		switch t.Kind() {
   707		case Struct:
   708			return &(*structTypeUncommon)(unsafe.Pointer(t)).u
   709		case Ptr:
   710			type u struct {
   711				ptrType
   712				u uncommonType
   713			}
   714			return &(*u)(unsafe.Pointer(t)).u
   715		case Func:
   716			type u struct {
   717				funcType
   718				u uncommonType
   719			}
   720			return &(*u)(unsafe.Pointer(t)).u
   721		case Slice:
   722			type u struct {
   723				sliceType
   724				u uncommonType
   725			}
   726			return &(*u)(unsafe.Pointer(t)).u
   727		case Array:
   728			type u struct {
   729				arrayType
   730				u uncommonType
   731			}
   732			return &(*u)(unsafe.Pointer(t)).u
   733		case Chan:
   734			type u struct {
   735				chanType
   736				u uncommonType
   737			}
   738			return &(*u)(unsafe.Pointer(t)).u
   739		case Map:
   740			type u struct {
   741				mapType
   742				u uncommonType
   743			}
   744			return &(*u)(unsafe.Pointer(t)).u
   745		case Interface:
   746			type u struct {
   747				interfaceType
   748				u uncommonType
   749			}
   750			return &(*u)(unsafe.Pointer(t)).u
   751		default:
   752			type u struct {
   753				rtype
   754				u uncommonType
   755			}
   756			return &(*u)(unsafe.Pointer(t)).u
   757		}
   758	}
   759	
   760	func (t *rtype) String() string {
   761		s := t.nameOff(t.str).name()
   762		if t.tflag&tflagExtraStar != 0 {
   763			return s[1:]
   764		}
   765		return s
   766	}
   767	
   768	func (t *rtype) Size() uintptr { return t.size }
   769	
   770	func (t *rtype) Bits() int {
   771		if t == nil {
   772			panic("reflect: Bits of nil Type")
   773		}
   774		k := t.Kind()
   775		if k < Int || k > Complex128 {
   776			panic("reflect: Bits of non-arithmetic Type " + t.String())
   777		}
   778		return int(t.size) * 8
   779	}
   780	
   781	func (t *rtype) Align() int { return int(t.align) }
   782	
   783	func (t *rtype) FieldAlign() int { return int(t.fieldAlign) }
   784	
   785	func (t *rtype) Kind() Kind { return Kind(t.kind & kindMask) }
   786	
   787	func (t *rtype) pointers() bool { return t.ptrdata != 0 }
   788	
   789	func (t *rtype) common() *rtype { return t }
   790	
   791	func (t *rtype) exportedMethods() []method {
   792		ut := t.uncommon()
   793		if ut == nil {
   794			return nil
   795		}
   796		return ut.exportedMethods()
   797	}
   798	
   799	func (t *rtype) NumMethod() int {
   800		if t.Kind() == Interface {
   801			tt := (*interfaceType)(unsafe.Pointer(t))
   802			return tt.NumMethod()
   803		}
   804		return len(t.exportedMethods())
   805	}
   806	
   807	func (t *rtype) Method(i int) (m Method) {
   808		if t.Kind() == Interface {
   809			tt := (*interfaceType)(unsafe.Pointer(t))
   810			return tt.Method(i)
   811		}
   812		methods := t.exportedMethods()
   813		if i < 0 || i >= len(methods) {
   814			panic("reflect: Method index out of range")
   815		}
   816		p := methods[i]
   817		pname := t.nameOff(p.name)
   818		m.Name = pname.name()
   819		fl := flag(Func)
   820		mtyp := t.typeOff(p.mtyp)
   821		ft := (*funcType)(unsafe.Pointer(mtyp))
   822		in := make([]Type, 0, 1+len(ft.in()))
   823		in = append(in, t)
   824		for _, arg := range ft.in() {
   825			in = append(in, arg)
   826		}
   827		out := make([]Type, 0, len(ft.out()))
   828		for _, ret := range ft.out() {
   829			out = append(out, ret)
   830		}
   831		mt := FuncOf(in, out, ft.IsVariadic())
   832		m.Type = mt
   833		tfn := t.textOff(p.tfn)
   834		fn := unsafe.Pointer(&tfn)
   835		m.Func = Value{mt.(*rtype), fn, fl}
   836	
   837		m.Index = i
   838		return m
   839	}
   840	
   841	func (t *rtype) MethodByName(name string) (m Method, ok bool) {
   842		if t.Kind() == Interface {
   843			tt := (*interfaceType)(unsafe.Pointer(t))
   844			return tt.MethodByName(name)
   845		}
   846		ut := t.uncommon()
   847		if ut == nil {
   848			return Method{}, false
   849		}
   850		// TODO(mdempsky): Binary search.
   851		for i, p := range ut.exportedMethods() {
   852			if t.nameOff(p.name).name() == name {
   853				return t.Method(i), true
   854			}
   855		}
   856		return Method{}, false
   857	}
   858	
   859	func (t *rtype) PkgPath() string {
   860		if t.tflag&tflagNamed == 0 {
   861			return ""
   862		}
   863		ut := t.uncommon()
   864		if ut == nil {
   865			return ""
   866		}
   867		return t.nameOff(ut.pkgPath).name()
   868	}
   869	
   870	func hasPrefix(s, prefix string) bool {
   871		return len(s) >= len(prefix) && s[:len(prefix)] == prefix
   872	}
   873	
   874	func (t *rtype) Name() string {
   875		if t.tflag&tflagNamed == 0 {
   876			return ""
   877		}
   878		s := t.String()
   879		i := len(s) - 1
   880		for i >= 0 && s[i] != '.' {
   881			i--
   882		}
   883		return s[i+1:]
   884	}
   885	
   886	func (t *rtype) ChanDir() ChanDir {
   887		if t.Kind() != Chan {
   888			panic("reflect: ChanDir of non-chan type")
   889		}
   890		tt := (*chanType)(unsafe.Pointer(t))
   891		return ChanDir(tt.dir)
   892	}
   893	
   894	func (t *rtype) IsVariadic() bool {
   895		if t.Kind() != Func {
   896			panic("reflect: IsVariadic of non-func type")
   897		}
   898		tt := (*funcType)(unsafe.Pointer(t))
   899		return tt.outCount&(1<<15) != 0
   900	}
   901	
   902	func (t *rtype) Elem() Type {
   903		switch t.Kind() {
   904		case Array:
   905			tt := (*arrayType)(unsafe.Pointer(t))
   906			return toType(tt.elem)
   907		case Chan:
   908			tt := (*chanType)(unsafe.Pointer(t))
   909			return toType(tt.elem)
   910		case Map:
   911			tt := (*mapType)(unsafe.Pointer(t))
   912			return toType(tt.elem)
   913		case Ptr:
   914			tt := (*ptrType)(unsafe.Pointer(t))
   915			return toType(tt.elem)
   916		case Slice:
   917			tt := (*sliceType)(unsafe.Pointer(t))
   918			return toType(tt.elem)
   919		}
   920		panic("reflect: Elem of invalid type")
   921	}
   922	
   923	func (t *rtype) Field(i int) StructField {
   924		if t.Kind() != Struct {
   925			panic("reflect: Field of non-struct type")
   926		}
   927		tt := (*structType)(unsafe.Pointer(t))
   928		return tt.Field(i)
   929	}
   930	
   931	func (t *rtype) FieldByIndex(index []int) StructField {
   932		if t.Kind() != Struct {
   933			panic("reflect: FieldByIndex of non-struct type")
   934		}
   935		tt := (*structType)(unsafe.Pointer(t))
   936		return tt.FieldByIndex(index)
   937	}
   938	
   939	func (t *rtype) FieldByName(name string) (StructField, bool) {
   940		if t.Kind() != Struct {
   941			panic("reflect: FieldByName of non-struct type")
   942		}
   943		tt := (*structType)(unsafe.Pointer(t))
   944		return tt.FieldByName(name)
   945	}
   946	
   947	func (t *rtype) FieldByNameFunc(match func(string) bool) (StructField, bool) {
   948		if t.Kind() != Struct {
   949			panic("reflect: FieldByNameFunc of non-struct type")
   950		}
   951		tt := (*structType)(unsafe.Pointer(t))
   952		return tt.FieldByNameFunc(match)
   953	}
   954	
   955	func (t *rtype) In(i int) Type {
   956		if t.Kind() != Func {
   957			panic("reflect: In of non-func type")
   958		}
   959		tt := (*funcType)(unsafe.Pointer(t))
   960		return toType(tt.in()[i])
   961	}
   962	
   963	func (t *rtype) Key() Type {
   964		if t.Kind() != Map {
   965			panic("reflect: Key of non-map type")
   966		}
   967		tt := (*mapType)(unsafe.Pointer(t))
   968		return toType(tt.key)
   969	}
   970	
   971	func (t *rtype) Len() int {
   972		if t.Kind() != Array {
   973			panic("reflect: Len of non-array type")
   974		}
   975		tt := (*arrayType)(unsafe.Pointer(t))
   976		return int(tt.len)
   977	}
   978	
   979	func (t *rtype) NumField() int {
   980		if t.Kind() != Struct {
   981			panic("reflect: NumField of non-struct type")
   982		}
   983		tt := (*structType)(unsafe.Pointer(t))
   984		return len(tt.fields)
   985	}
   986	
   987	func (t *rtype) NumIn() int {
   988		if t.Kind() != Func {
   989			panic("reflect: NumIn of non-func type")
   990		}
   991		tt := (*funcType)(unsafe.Pointer(t))
   992		return int(tt.inCount)
   993	}
   994	
   995	func (t *rtype) NumOut() int {
   996		if t.Kind() != Func {
   997			panic("reflect: NumOut of non-func type")
   998		}
   999		tt := (*funcType)(unsafe.Pointer(t))
  1000		return len(tt.out())
  1001	}
  1002	
  1003	func (t *rtype) Out(i int) Type {
  1004		if t.Kind() != Func {
  1005			panic("reflect: Out of non-func type")
  1006		}
  1007		tt := (*funcType)(unsafe.Pointer(t))
  1008		return toType(tt.out()[i])
  1009	}
  1010	
  1011	func (t *funcType) in() []*rtype {
  1012		uadd := unsafe.Sizeof(*t)
  1013		if t.tflag&tflagUncommon != 0 {
  1014			uadd += unsafe.Sizeof(uncommonType{})
  1015		}
  1016		if t.inCount == 0 {
  1017			return nil
  1018		}
  1019		return (*[1 << 20]*rtype)(add(unsafe.Pointer(t), uadd, "t.inCount > 0"))[:t.inCount]
  1020	}
  1021	
  1022	func (t *funcType) out() []*rtype {
  1023		uadd := unsafe.Sizeof(*t)
  1024		if t.tflag&tflagUncommon != 0 {
  1025			uadd += unsafe.Sizeof(uncommonType{})
  1026		}
  1027		outCount := t.outCount & (1<<15 - 1)
  1028		if outCount == 0 {
  1029			return nil
  1030		}
  1031		return (*[1 << 20]*rtype)(add(unsafe.Pointer(t), uadd, "outCount > 0"))[t.inCount : t.inCount+outCount]
  1032	}
  1033	
  1034	// add returns p+x.
  1035	//
  1036	// The whySafe string is ignored, so that the function still inlines
  1037	// as efficiently as p+x, but all call sites should use the string to
  1038	// record why the addition is safe, which is to say why the addition
  1039	// does not cause x to advance to the very end of p's allocation
  1040	// and therefore point incorrectly at the next block in memory.
  1041	func add(p unsafe.Pointer, x uintptr, whySafe string) unsafe.Pointer {
  1042		return unsafe.Pointer(uintptr(p) + x)
  1043	}
  1044	
  1045	func (d ChanDir) String() string {
  1046		switch d {
  1047		case SendDir:
  1048			return "chan<-"
  1049		case RecvDir:
  1050			return "<-chan"
  1051		case BothDir:
  1052			return "chan"
  1053		}
  1054		return "ChanDir" + strconv.Itoa(int(d))
  1055	}
  1056	
  1057	// Method returns the i'th method in the type's method set.
  1058	func (t *interfaceType) Method(i int) (m Method) {
  1059		if i < 0 || i >= len(t.methods) {
  1060			return
  1061		}
  1062		p := &t.methods[i]
  1063		pname := t.nameOff(p.name)
  1064		m.Name = pname.name()
  1065		if !pname.isExported() {
  1066			m.PkgPath = pname.pkgPath()
  1067			if m.PkgPath == "" {
  1068				m.PkgPath = t.pkgPath.name()
  1069			}
  1070		}
  1071		m.Type = toType(t.typeOff(p.typ))
  1072		m.Index = i
  1073		return
  1074	}
  1075	
  1076	// NumMethod returns the number of interface methods in the type's method set.
  1077	func (t *interfaceType) NumMethod() int { return len(t.methods) }
  1078	
  1079	// MethodByName method with the given name in the type's method set.
  1080	func (t *interfaceType) MethodByName(name string) (m Method, ok bool) {
  1081		if t == nil {
  1082			return
  1083		}
  1084		var p *imethod
  1085		for i := range t.methods {
  1086			p = &t.methods[i]
  1087			if t.nameOff(p.name).name() == name {
  1088				return t.Method(i), true
  1089			}
  1090		}
  1091		return
  1092	}
  1093	
  1094	// A StructField describes a single field in a struct.
  1095	type StructField struct {
  1096		// Name is the field name.
  1097		Name string
  1098		// PkgPath is the package path that qualifies a lower case (unexported)
  1099		// field name. It is empty for upper case (exported) field names.
  1100		// See https://golang.org/ref/spec#Uniqueness_of_identifiers
  1101		PkgPath string
  1102	
  1103		Type      Type      // field type
  1104		Tag       StructTag // field tag string
  1105		Offset    uintptr   // offset within struct, in bytes
  1106		Index     []int     // index sequence for Type.FieldByIndex
  1107		Anonymous bool      // is an embedded field
  1108	}
  1109	
  1110	// A StructTag is the tag string in a struct field.
  1111	//
  1112	// By convention, tag strings are a concatenation of
  1113	// optionally space-separated key:"value" pairs.
  1114	// Each key is a non-empty string consisting of non-control
  1115	// characters other than space (U+0020 ' '), quote (U+0022 '"'),
  1116	// and colon (U+003A ':').  Each value is quoted using U+0022 '"'
  1117	// characters and Go string literal syntax.
  1118	type StructTag string
  1119	
  1120	// Get returns the value associated with key in the tag string.
  1121	// If there is no such key in the tag, Get returns the empty string.
  1122	// If the tag does not have the conventional format, the value
  1123	// returned by Get is unspecified. To determine whether a tag is
  1124	// explicitly set to the empty string, use Lookup.
  1125	func (tag StructTag) Get(key string) string {
  1126		v, _ := tag.Lookup(key)
  1127		return v
  1128	}
  1129	
  1130	// Lookup returns the value associated with key in the tag string.
  1131	// If the key is present in the tag the value (which may be empty)
  1132	// is returned. Otherwise the returned value will be the empty string.
  1133	// The ok return value reports whether the value was explicitly set in
  1134	// the tag string. If the tag does not have the conventional format,
  1135	// the value returned by Lookup is unspecified.
  1136	func (tag StructTag) Lookup(key string) (value string, ok bool) {
  1137		// When modifying this code, also update the validateStructTag code
  1138		// in cmd/vet/structtag.go.
  1139	
  1140		for tag != "" {
  1141			// Skip leading space.
  1142			i := 0
  1143			for i < len(tag) && tag[i] == ' ' {
  1144				i++
  1145			}
  1146			tag = tag[i:]
  1147			if tag == "" {
  1148				break
  1149			}
  1150	
  1151			// Scan to colon. A space, a quote or a control character is a syntax error.
  1152			// Strictly speaking, control chars include the range [0x7f, 0x9f], not just
  1153			// [0x00, 0x1f], but in practice, we ignore the multi-byte control characters
  1154			// as it is simpler to inspect the tag's bytes than the tag's runes.
  1155			i = 0
  1156			for i < len(tag) && tag[i] > ' ' && tag[i] != ':' && tag[i] != '"' && tag[i] != 0x7f {
  1157				i++
  1158			}
  1159			if i == 0 || i+1 >= len(tag) || tag[i] != ':' || tag[i+1] != '"' {
  1160				break
  1161			}
  1162			name := string(tag[:i])
  1163			tag = tag[i+1:]
  1164	
  1165			// Scan quoted string to find value.
  1166			i = 1
  1167			for i < len(tag) && tag[i] != '"' {
  1168				if tag[i] == '\\' {
  1169					i++
  1170				}
  1171				i++
  1172			}
  1173			if i >= len(tag) {
  1174				break
  1175			}
  1176			qvalue := string(tag[:i+1])
  1177			tag = tag[i+1:]
  1178	
  1179			if key == name {
  1180				value, err := strconv.Unquote(qvalue)
  1181				if err != nil {
  1182					break
  1183				}
  1184				return value, true
  1185			}
  1186		}
  1187		return "", false
  1188	}
  1189	
  1190	// Field returns the i'th struct field.
  1191	func (t *structType) Field(i int) (f StructField) {
  1192		if i < 0 || i >= len(t.fields) {
  1193			panic("reflect: Field index out of bounds")
  1194		}
  1195		p := &t.fields[i]
  1196		f.Type = toType(p.typ)
  1197		f.Name = p.name.name()
  1198		f.Anonymous = p.embedded()
  1199		if !p.name.isExported() {
  1200			f.PkgPath = t.pkgPath.name()
  1201		}
  1202		if tag := p.name.tag(); tag != "" {
  1203			f.Tag = StructTag(tag)
  1204		}
  1205		f.Offset = p.offset()
  1206	
  1207		// NOTE(rsc): This is the only allocation in the interface
  1208		// presented by a reflect.Type. It would be nice to avoid,
  1209		// at least in the common cases, but we need to make sure
  1210		// that misbehaving clients of reflect cannot affect other
  1211		// uses of reflect. One possibility is CL 5371098, but we
  1212		// postponed that ugliness until there is a demonstrated
  1213		// need for the performance. This is issue 2320.
  1214		f.Index = []int{i}
  1215		return
  1216	}
  1217	
  1218	// TODO(gri): Should there be an error/bool indicator if the index
  1219	//            is wrong for FieldByIndex?
  1220	
  1221	// FieldByIndex returns the nested field corresponding to index.
  1222	func (t *structType) FieldByIndex(index []int) (f StructField) {
  1223		f.Type = toType(&t.rtype)
  1224		for i, x := range index {
  1225			if i > 0 {
  1226				ft := f.Type
  1227				if ft.Kind() == Ptr && ft.Elem().Kind() == Struct {
  1228					ft = ft.Elem()
  1229				}
  1230				f.Type = ft
  1231			}
  1232			f = f.Type.Field(x)
  1233		}
  1234		return
  1235	}
  1236	
  1237	// A fieldScan represents an item on the fieldByNameFunc scan work list.
  1238	type fieldScan struct {
  1239		typ   *structType
  1240		index []int
  1241	}
  1242	
  1243	// FieldByNameFunc returns the struct field with a name that satisfies the
  1244	// match function and a boolean to indicate if the field was found.
  1245	func (t *structType) FieldByNameFunc(match func(string) bool) (result StructField, ok bool) {
  1246		// This uses the same condition that the Go language does: there must be a unique instance
  1247		// of the match at a given depth level. If there are multiple instances of a match at the
  1248		// same depth, they annihilate each other and inhibit any possible match at a lower level.
  1249		// The algorithm is breadth first search, one depth level at a time.
  1250	
  1251		// The current and next slices are work queues:
  1252		// current lists the fields to visit on this depth level,
  1253		// and next lists the fields on the next lower level.
  1254		current := []fieldScan{}
  1255		next := []fieldScan{{typ: t}}
  1256	
  1257		// nextCount records the number of times an embedded type has been
  1258		// encountered and considered for queueing in the 'next' slice.
  1259		// We only queue the first one, but we increment the count on each.
  1260		// If a struct type T can be reached more than once at a given depth level,
  1261		// then it annihilates itself and need not be considered at all when we
  1262		// process that next depth level.
  1263		var nextCount map[*structType]int
  1264	
  1265		// visited records the structs that have been considered already.
  1266		// Embedded pointer fields can create cycles in the graph of
  1267		// reachable embedded types; visited avoids following those cycles.
  1268		// It also avoids duplicated effort: if we didn't find the field in an
  1269		// embedded type T at level 2, we won't find it in one at level 4 either.
  1270		visited := map[*structType]bool{}
  1271	
  1272		for len(next) > 0 {
  1273			current, next = next, current[:0]
  1274			count := nextCount
  1275			nextCount = nil
  1276	
  1277			// Process all the fields at this depth, now listed in 'current'.
  1278			// The loop queues embedded fields found in 'next', for processing during the next
  1279			// iteration. The multiplicity of the 'current' field counts is recorded
  1280			// in 'count'; the multiplicity of the 'next' field counts is recorded in 'nextCount'.
  1281			for _, scan := range current {
  1282				t := scan.typ
  1283				if visited[t] {
  1284					// We've looked through this type before, at a higher level.
  1285					// That higher level would shadow the lower level we're now at,
  1286					// so this one can't be useful to us. Ignore it.
  1287					continue
  1288				}
  1289				visited[t] = true
  1290				for i := range t.fields {
  1291					f := &t.fields[i]
  1292					// Find name and (for embedded field) type for field f.
  1293					fname := f.name.name()
  1294					var ntyp *rtype
  1295					if f.embedded() {
  1296						// Embedded field of type T or *T.
  1297						ntyp = f.typ
  1298						if ntyp.Kind() == Ptr {
  1299							ntyp = ntyp.Elem().common()
  1300						}
  1301					}
  1302	
  1303					// Does it match?
  1304					if match(fname) {
  1305						// Potential match
  1306						if count[t] > 1 || ok {
  1307							// Name appeared multiple times at this level: annihilate.
  1308							return StructField{}, false
  1309						}
  1310						result = t.Field(i)
  1311						result.Index = nil
  1312						result.Index = append(result.Index, scan.index...)
  1313						result.Index = append(result.Index, i)
  1314						ok = true
  1315						continue
  1316					}
  1317	
  1318					// Queue embedded struct fields for processing with next level,
  1319					// but only if we haven't seen a match yet at this level and only
  1320					// if the embedded types haven't already been queued.
  1321					if ok || ntyp == nil || ntyp.Kind() != Struct {
  1322						continue
  1323					}
  1324					styp := (*structType)(unsafe.Pointer(ntyp))
  1325					if nextCount[styp] > 0 {
  1326						nextCount[styp] = 2 // exact multiple doesn't matter
  1327						continue
  1328					}
  1329					if nextCount == nil {
  1330						nextCount = map[*structType]int{}
  1331					}
  1332					nextCount[styp] = 1
  1333					if count[t] > 1 {
  1334						nextCount[styp] = 2 // exact multiple doesn't matter
  1335					}
  1336					var index []int
  1337					index = append(index, scan.index...)
  1338					index = append(index, i)
  1339					next = append(next, fieldScan{styp, index})
  1340				}
  1341			}
  1342			if ok {
  1343				break
  1344			}
  1345		}
  1346		return
  1347	}
  1348	
  1349	// FieldByName returns the struct field with the given name
  1350	// and a boolean to indicate if the field was found.
  1351	func (t *structType) FieldByName(name string) (f StructField, present bool) {
  1352		// Quick check for top-level name, or struct without embedded fields.
  1353		hasEmbeds := false
  1354		if name != "" {
  1355			for i := range t.fields {
  1356				tf := &t.fields[i]
  1357				if tf.name.name() == name {
  1358					return t.Field(i), true
  1359				}
  1360				if tf.embedded() {
  1361					hasEmbeds = true
  1362				}
  1363			}
  1364		}
  1365		if !hasEmbeds {
  1366			return
  1367		}
  1368		return t.FieldByNameFunc(func(s string) bool { return s == name })
  1369	}
  1370	
  1371	// TypeOf returns the reflection Type that represents the dynamic type of i.
  1372	// If i is a nil interface value, TypeOf returns nil.
  1373	func TypeOf(i interface{}) Type {
  1374		eface := *(*emptyInterface)(unsafe.Pointer(&i))
  1375		return toType(eface.typ)
  1376	}
  1377	
  1378	// ptrMap is the cache for PtrTo.
  1379	var ptrMap sync.Map // map[*rtype]*ptrType
  1380	
  1381	// PtrTo returns the pointer type with element t.
  1382	// For example, if t represents type Foo, PtrTo(t) represents *Foo.
  1383	func PtrTo(t Type) Type {
  1384		return t.(*rtype).ptrTo()
  1385	}
  1386	
  1387	func (t *rtype) ptrTo() *rtype {
  1388		if t.ptrToThis != 0 {
  1389			return t.typeOff(t.ptrToThis)
  1390		}
  1391	
  1392		// Check the cache.
  1393		if pi, ok := ptrMap.Load(t); ok {
  1394			return &pi.(*ptrType).rtype
  1395		}
  1396	
  1397		// Look in known types.
  1398		s := "*" + t.String()
  1399		for _, tt := range typesByString(s) {
  1400			p := (*ptrType)(unsafe.Pointer(tt))
  1401			if p.elem != t {
  1402				continue
  1403			}
  1404			pi, _ := ptrMap.LoadOrStore(t, p)
  1405			return &pi.(*ptrType).rtype
  1406		}
  1407	
  1408		// Create a new ptrType starting with the description
  1409		// of an *unsafe.Pointer.
  1410		var iptr interface{} = (*unsafe.Pointer)(nil)
  1411		prototype := *(**ptrType)(unsafe.Pointer(&iptr))
  1412		pp := *prototype
  1413	
  1414		pp.str = resolveReflectName(newName(s, "", false))
  1415		pp.ptrToThis = 0
  1416	
  1417		// For the type structures linked into the binary, the
  1418		// compiler provides a good hash of the string.
  1419		// Create a good hash for the new string by using
  1420		// the FNV-1 hash's mixing function to combine the
  1421		// old hash and the new "*".
  1422		pp.hash = fnv1(t.hash, '*')
  1423	
  1424		pp.elem = t
  1425	
  1426		pi, _ := ptrMap.LoadOrStore(t, &pp)
  1427		return &pi.(*ptrType).rtype
  1428	}
  1429	
  1430	// fnv1 incorporates the list of bytes into the hash x using the FNV-1 hash function.
  1431	func fnv1(x uint32, list ...byte) uint32 {
  1432		for _, b := range list {
  1433			x = x*16777619 ^ uint32(b)
  1434		}
  1435		return x
  1436	}
  1437	
  1438	func (t *rtype) Implements(u Type) bool {
  1439		if u == nil {
  1440			panic("reflect: nil type passed to Type.Implements")
  1441		}
  1442		if u.Kind() != Interface {
  1443			panic("reflect: non-interface type passed to Type.Implements")
  1444		}
  1445		return implements(u.(*rtype), t)
  1446	}
  1447	
  1448	func (t *rtype) AssignableTo(u Type) bool {
  1449		if u == nil {
  1450			panic("reflect: nil type passed to Type.AssignableTo")
  1451		}
  1452		uu := u.(*rtype)
  1453		return directlyAssignable(uu, t) || implements(uu, t)
  1454	}
  1455	
  1456	func (t *rtype) ConvertibleTo(u Type) bool {
  1457		if u == nil {
  1458			panic("reflect: nil type passed to Type.ConvertibleTo")
  1459		}
  1460		uu := u.(*rtype)
  1461		return convertOp(uu, t) != nil
  1462	}
  1463	
  1464	func (t *rtype) Comparable() bool {
  1465		return t.alg != nil && t.alg.equal != nil
  1466	}
  1467	
  1468	// implements reports whether the type V implements the interface type T.
  1469	func implements(T, V *rtype) bool {
  1470		if T.Kind() != Interface {
  1471			return false
  1472		}
  1473		t := (*interfaceType)(unsafe.Pointer(T))
  1474		if len(t.methods) == 0 {
  1475			return true
  1476		}
  1477	
  1478		// The same algorithm applies in both cases, but the
  1479		// method tables for an interface type and a concrete type
  1480		// are different, so the code is duplicated.
  1481		// In both cases the algorithm is a linear scan over the two
  1482		// lists - T's methods and V's methods - simultaneously.
  1483		// Since method tables are stored in a unique sorted order
  1484		// (alphabetical, with no duplicate method names), the scan
  1485		// through V's methods must hit a match for each of T's
  1486		// methods along the way, or else V does not implement T.
  1487		// This lets us run the scan in overall linear time instead of
  1488		// the quadratic time  a naive search would require.
  1489		// See also ../runtime/iface.go.
  1490		if V.Kind() == Interface {
  1491			v := (*interfaceType)(unsafe.Pointer(V))
  1492			i := 0
  1493			for j := 0; j < len(v.methods); j++ {
  1494				tm := &t.methods[i]
  1495				tmName := t.nameOff(tm.name)
  1496				vm := &v.methods[j]
  1497				vmName := V.nameOff(vm.name)
  1498				if vmName.name() == tmName.name() && V.typeOff(vm.typ) == t.typeOff(tm.typ) {
  1499					if !tmName.isExported() {
  1500						tmPkgPath := tmName.pkgPath()
  1501						if tmPkgPath == "" {
  1502							tmPkgPath = t.pkgPath.name()
  1503						}
  1504						vmPkgPath := vmName.pkgPath()
  1505						if vmPkgPath == "" {
  1506							vmPkgPath = v.pkgPath.name()
  1507						}
  1508						if tmPkgPath != vmPkgPath {
  1509							continue
  1510						}
  1511					}
  1512					if i++; i >= len(t.methods) {
  1513						return true
  1514					}
  1515				}
  1516			}
  1517			return false
  1518		}
  1519	
  1520		v := V.uncommon()
  1521		if v == nil {
  1522			return false
  1523		}
  1524		i := 0
  1525		vmethods := v.methods()
  1526		for j := 0; j < int(v.mcount); j++ {
  1527			tm := &t.methods[i]
  1528			tmName := t.nameOff(tm.name)
  1529			vm := vmethods[j]
  1530			vmName := V.nameOff(vm.name)
  1531			if vmName.name() == tmName.name() && V.typeOff(vm.mtyp) == t.typeOff(tm.typ) {
  1532				if !tmName.isExported() {
  1533					tmPkgPath := tmName.pkgPath()
  1534					if tmPkgPath == "" {
  1535						tmPkgPath = t.pkgPath.name()
  1536					}
  1537					vmPkgPath := vmName.pkgPath()
  1538					if vmPkgPath == "" {
  1539						vmPkgPath = V.nameOff(v.pkgPath).name()
  1540					}
  1541					if tmPkgPath != vmPkgPath {
  1542						continue
  1543					}
  1544				}
  1545				if i++; i >= len(t.methods) {
  1546					return true
  1547				}
  1548			}
  1549		}
  1550		return false
  1551	}
  1552	
  1553	// directlyAssignable reports whether a value x of type V can be directly
  1554	// assigned (using memmove) to a value of type T.
  1555	// https://golang.org/doc/go_spec.html#Assignability
  1556	// Ignoring the interface rules (implemented elsewhere)
  1557	// and the ideal constant rules (no ideal constants at run time).
  1558	func directlyAssignable(T, V *rtype) bool {
  1559		// x's type V is identical to T?
  1560		if T == V {
  1561			return true
  1562		}
  1563	
  1564		// Otherwise at least one of T and V must not be defined
  1565		// and they must have the same kind.
  1566		if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
  1567			return false
  1568		}
  1569	
  1570		// x's type T and V must  have identical underlying types.
  1571		return haveIdenticalUnderlyingType(T, V, true)
  1572	}
  1573	
  1574	func haveIdenticalType(T, V Type, cmpTags bool) bool {
  1575		if cmpTags {
  1576			return T == V
  1577		}
  1578	
  1579		if T.Name() != V.Name() || T.Kind() != V.Kind() {
  1580			return false
  1581		}
  1582	
  1583		return haveIdenticalUnderlyingType(T.common(), V.common(), false)
  1584	}
  1585	
  1586	func haveIdenticalUnderlyingType(T, V *rtype, cmpTags bool) bool {
  1587		if T == V {
  1588			return true
  1589		}
  1590	
  1591		kind := T.Kind()
  1592		if kind != V.Kind() {
  1593			return false
  1594		}
  1595	
  1596		// Non-composite types of equal kind have same underlying type
  1597		// (the predefined instance of the type).
  1598		if Bool <= kind && kind <= Complex128 || kind == String || kind == UnsafePointer {
  1599			return true
  1600		}
  1601	
  1602		// Composite types.
  1603		switch kind {
  1604		case Array:
  1605			return T.Len() == V.Len() && haveIdenticalType(T.Elem(), V.Elem(), cmpTags)
  1606	
  1607		case Chan:
  1608			// Special case:
  1609			// x is a bidirectional channel value, T is a channel type,
  1610			// and x's type V and T have identical element types.
  1611			if V.ChanDir() == BothDir && haveIdenticalType(T.Elem(), V.Elem(), cmpTags) {
  1612				return true
  1613			}
  1614	
  1615			// Otherwise continue test for identical underlying type.
  1616			return V.ChanDir() == T.ChanDir() && haveIdenticalType(T.Elem(), V.Elem(), cmpTags)
  1617	
  1618		case Func:
  1619			t := (*funcType)(unsafe.Pointer(T))
  1620			v := (*funcType)(unsafe.Pointer(V))
  1621			if t.outCount != v.outCount || t.inCount != v.inCount {
  1622				return false
  1623			}
  1624			for i := 0; i < t.NumIn(); i++ {
  1625				if !haveIdenticalType(t.In(i), v.In(i), cmpTags) {
  1626					return false
  1627				}
  1628			}
  1629			for i := 0; i < t.NumOut(); i++ {
  1630				if !haveIdenticalType(t.Out(i), v.Out(i), cmpTags) {
  1631					return false
  1632				}
  1633			}
  1634			return true
  1635	
  1636		case Interface:
  1637			t := (*interfaceType)(unsafe.Pointer(T))
  1638			v := (*interfaceType)(unsafe.Pointer(V))
  1639			if len(t.methods) == 0 && len(v.methods) == 0 {
  1640				return true
  1641			}
  1642			// Might have the same methods but still
  1643			// need a run time conversion.
  1644			return false
  1645	
  1646		case Map:
  1647			return haveIdenticalType(T.Key(), V.Key(), cmpTags) && haveIdenticalType(T.Elem(), V.Elem(), cmpTags)
  1648	
  1649		case Ptr, Slice:
  1650			return haveIdenticalType(T.Elem(), V.Elem(), cmpTags)
  1651	
  1652		case Struct:
  1653			t := (*structType)(unsafe.Pointer(T))
  1654			v := (*structType)(unsafe.Pointer(V))
  1655			if len(t.fields) != len(v.fields) {
  1656				return false
  1657			}
  1658			if t.pkgPath.name() != v.pkgPath.name() {
  1659				return false
  1660			}
  1661			for i := range t.fields {
  1662				tf := &t.fields[i]
  1663				vf := &v.fields[i]
  1664				if tf.name.name() != vf.name.name() {
  1665					return false
  1666				}
  1667				if !haveIdenticalType(tf.typ, vf.typ, cmpTags) {
  1668					return false
  1669				}
  1670				if cmpTags && tf.name.tag() != vf.name.tag() {
  1671					return false
  1672				}
  1673				if tf.offsetEmbed != vf.offsetEmbed {
  1674					return false
  1675				}
  1676			}
  1677			return true
  1678		}
  1679	
  1680		return false
  1681	}
  1682	
  1683	// typelinks is implemented in package runtime.
  1684	// It returns a slice of the sections in each module,
  1685	// and a slice of *rtype offsets in each module.
  1686	//
  1687	// The types in each module are sorted by string. That is, the first
  1688	// two linked types of the first module are:
  1689	//
  1690	//	d0 := sections[0]
  1691	//	t1 := (*rtype)(add(d0, offset[0][0]))
  1692	//	t2 := (*rtype)(add(d0, offset[0][1]))
  1693	//
  1694	// and
  1695	//
  1696	//	t1.String() < t2.String()
  1697	//
  1698	// Note that strings are not unique identifiers for types:
  1699	// there can be more than one with a given string.
  1700	// Only types we might want to look up are included:
  1701	// pointers, channels, maps, slices, and arrays.
  1702	func typelinks() (sections []unsafe.Pointer, offset [][]int32)
  1703	
  1704	func rtypeOff(section unsafe.Pointer, off int32) *rtype {
  1705		return (*rtype)(add(section, uintptr(off), "sizeof(rtype) > 0"))
  1706	}
  1707	
  1708	// typesByString returns the subslice of typelinks() whose elements have
  1709	// the given string representation.
  1710	// It may be empty (no known types with that string) or may have
  1711	// multiple elements (multiple types with that string).
  1712	func typesByString(s string) []*rtype {
  1713		sections, offset := typelinks()
  1714		var ret []*rtype
  1715	
  1716		for offsI, offs := range offset {
  1717			section := sections[offsI]
  1718	
  1719			// We are looking for the first index i where the string becomes >= s.
  1720			// This is a copy of sort.Search, with f(h) replaced by (*typ[h].String() >= s).
  1721			i, j := 0, len(offs)
  1722			for i < j {
  1723				h := i + (j-i)/2 // avoid overflow when computing h
  1724				// i ≤ h < j
  1725				if !(rtypeOff(section, offs[h]).String() >= s) {
  1726					i = h + 1 // preserves f(i-1) == false
  1727				} else {
  1728					j = h // preserves f(j) == true
  1729				}
  1730			}
  1731			// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
  1732	
  1733			// Having found the first, linear scan forward to find the last.
  1734			// We could do a second binary search, but the caller is going
  1735			// to do a linear scan anyway.
  1736			for j := i; j < len(offs); j++ {
  1737				typ := rtypeOff(section, offs[j])
  1738				if typ.String() != s {
  1739					break
  1740				}
  1741				ret = append(ret, typ)
  1742			}
  1743		}
  1744		return ret
  1745	}
  1746	
  1747	// The lookupCache caches ArrayOf, ChanOf, MapOf and SliceOf lookups.
  1748	var lookupCache sync.Map // map[cacheKey]*rtype
  1749	
  1750	// A cacheKey is the key for use in the lookupCache.
  1751	// Four values describe any of the types we are looking for:
  1752	// type kind, one or two subtypes, and an extra integer.
  1753	type cacheKey struct {
  1754		kind  Kind
  1755		t1    *rtype
  1756		t2    *rtype
  1757		extra uintptr
  1758	}
  1759	
  1760	// The funcLookupCache caches FuncOf lookups.
  1761	// FuncOf does not share the common lookupCache since cacheKey is not
  1762	// sufficient to represent functions unambiguously.
  1763	var funcLookupCache struct {
  1764		sync.Mutex // Guards stores (but not loads) on m.
  1765	
  1766		// m is a map[uint32][]*rtype keyed by the hash calculated in FuncOf.
  1767		// Elements of m are append-only and thus safe for concurrent reading.
  1768		m sync.Map
  1769	}
  1770	
  1771	// ChanOf returns the channel type with the given direction and element type.
  1772	// For example, if t represents int, ChanOf(RecvDir, t) represents <-chan int.
  1773	//
  1774	// The gc runtime imposes a limit of 64 kB on channel element types.
  1775	// If t's size is equal to or exceeds this limit, ChanOf panics.
  1776	func ChanOf(dir ChanDir, t Type) Type {
  1777		typ := t.(*rtype)
  1778	
  1779		// Look in cache.
  1780		ckey := cacheKey{Chan, typ, nil, uintptr(dir)}
  1781		if ch, ok := lookupCache.Load(ckey); ok {
  1782			return ch.(*rtype)
  1783		}
  1784	
  1785		// This restriction is imposed by the gc compiler and the runtime.
  1786		if typ.size >= 1<<16 {
  1787			panic("reflect.ChanOf: element size too large")
  1788		}
  1789	
  1790		// Look in known types.
  1791		// TODO: Precedence when constructing string.
  1792		var s string
  1793		switch dir {
  1794		default:
  1795			panic("reflect.ChanOf: invalid dir")
  1796		case SendDir:
  1797			s = "chan<- " + typ.String()
  1798		case RecvDir:
  1799			s = "<-chan " + typ.String()
  1800		case BothDir:
  1801			s = "chan " + typ.String()
  1802		}
  1803		for _, tt := range typesByString(s) {
  1804			ch := (*chanType)(unsafe.Pointer(tt))
  1805			if ch.elem == typ && ch.dir == uintptr(dir) {
  1806				ti, _ := lookupCache.LoadOrStore(ckey, tt)
  1807				return ti.(Type)
  1808			}
  1809		}
  1810	
  1811		// Make a channel type.
  1812		var ichan interface{} = (chan unsafe.Pointer)(nil)
  1813		prototype := *(**chanType)(unsafe.Pointer(&ichan))
  1814		ch := *prototype
  1815		ch.tflag = 0
  1816		ch.dir = uintptr(dir)
  1817		ch.str = resolveReflectName(newName(s, "", false))
  1818		ch.hash = fnv1(typ.hash, 'c', byte(dir))
  1819		ch.elem = typ
  1820	
  1821		ti, _ := lookupCache.LoadOrStore(ckey, &ch.rtype)
  1822		return ti.(Type)
  1823	}
  1824	
  1825	func ismapkey(*rtype) bool // implemented in runtime
  1826	
  1827	// MapOf returns the map type with the given key and element types.
  1828	// For example, if k represents int and e represents string,
  1829	// MapOf(k, e) represents map[int]string.
  1830	//
  1831	// If the key type is not a valid map key type (that is, if it does
  1832	// not implement Go's == operator), MapOf panics.
  1833	func MapOf(key, elem Type) Type {
  1834		ktyp := key.(*rtype)
  1835		etyp := elem.(*rtype)
  1836	
  1837		if !ismapkey(ktyp) {
  1838			panic("reflect.MapOf: invalid key type " + ktyp.String())
  1839		}
  1840	
  1841		// Look in cache.
  1842		ckey := cacheKey{Map, ktyp, etyp, 0}
  1843		if mt, ok := lookupCache.Load(ckey); ok {
  1844			return mt.(Type)
  1845		}
  1846	
  1847		// Look in known types.
  1848		s := "map[" + ktyp.String() + "]" + etyp.String()
  1849		for _, tt := range typesByString(s) {
  1850			mt := (*mapType)(unsafe.Pointer(tt))
  1851			if mt.key == ktyp && mt.elem == etyp {
  1852				ti, _ := lookupCache.LoadOrStore(ckey, tt)
  1853				return ti.(Type)
  1854			}
  1855		}
  1856	
  1857		// Make a map type.
  1858		// Note: flag values must match those used in the TMAP case
  1859		// in ../cmd/compile/internal/gc/reflect.go:dtypesym.
  1860		var imap interface{} = (map[unsafe.Pointer]unsafe.Pointer)(nil)
  1861		mt := **(**mapType)(unsafe.Pointer(&imap))
  1862		mt.str = resolveReflectName(newName(s, "", false))
  1863		mt.tflag = 0
  1864		mt.hash = fnv1(etyp.hash, 'm', byte(ktyp.hash>>24), byte(ktyp.hash>>16), byte(ktyp.hash>>8), byte(ktyp.hash))
  1865		mt.key = ktyp
  1866		mt.elem = etyp
  1867		mt.bucket = bucketOf(ktyp, etyp)
  1868		mt.flags = 0
  1869		if ktyp.size > maxKeySize {
  1870			mt.keysize = uint8(ptrSize)
  1871			mt.flags |= 1 // indirect key
  1872		} else {
  1873			mt.keysize = uint8(ktyp.size)
  1874		}
  1875		if etyp.size > maxValSize {
  1876			mt.valuesize = uint8(ptrSize)
  1877			mt.flags |= 2 // indirect value
  1878		} else {
  1879			mt.valuesize = uint8(etyp.size)
  1880		}
  1881		mt.bucketsize = uint16(mt.bucket.size)
  1882		if isReflexive(ktyp) {
  1883			mt.flags |= 4
  1884		}
  1885		if needKeyUpdate(ktyp) {
  1886			mt.flags |= 8
  1887		}
  1888		if hashMightPanic(ktyp) {
  1889			mt.flags |= 16
  1890		}
  1891		mt.ptrToThis = 0
  1892	
  1893		ti, _ := lookupCache.LoadOrStore(ckey, &mt.rtype)
  1894		return ti.(Type)
  1895	}
  1896	
  1897	// TODO(crawshaw): as these funcTypeFixedN structs have no methods,
  1898	// they could be defined at runtime using the StructOf function.
  1899	type funcTypeFixed4 struct {
  1900		funcType
  1901		args [4]*rtype
  1902	}
  1903	type funcTypeFixed8 struct {
  1904		funcType
  1905		args [8]*rtype
  1906	}
  1907	type funcTypeFixed16 struct {
  1908		funcType
  1909		args [16]*rtype
  1910	}
  1911	type funcTypeFixed32 struct {
  1912		funcType
  1913		args [32]*rtype
  1914	}
  1915	type funcTypeFixed64 struct {
  1916		funcType
  1917		args [64]*rtype
  1918	}
  1919	type funcTypeFixed128 struct {
  1920		funcType
  1921		args [128]*rtype
  1922	}
  1923	
  1924	// FuncOf returns the function type with the given argument and result types.
  1925	// For example if k represents int and e represents string,
  1926	// FuncOf([]Type{k}, []Type{e}, false) represents func(int) string.
  1927	//
  1928	// The variadic argument controls whether the function is variadic. FuncOf
  1929	// panics if the in[len(in)-1] does not represent a slice and variadic is
  1930	// true.
  1931	func FuncOf(in, out []Type, variadic bool) Type {
  1932		if variadic && (len(in) == 0 || in[len(in)-1].Kind() != Slice) {
  1933			panic("reflect.FuncOf: last arg of variadic func must be slice")
  1934		}
  1935	
  1936		// Make a func type.
  1937		var ifunc interface{} = (func())(nil)
  1938		prototype := *(**funcType)(unsafe.Pointer(&ifunc))
  1939		n := len(in) + len(out)
  1940	
  1941		var ft *funcType
  1942		var args []*rtype
  1943		switch {
  1944		case n <= 4:
  1945			fixed := new(funcTypeFixed4)
  1946			args = fixed.args[:0:len(fixed.args)]
  1947			ft = &fixed.funcType
  1948		case n <= 8:
  1949			fixed := new(funcTypeFixed8)
  1950			args = fixed.args[:0:len(fixed.args)]
  1951			ft = &fixed.funcType
  1952		case n <= 16:
  1953			fixed := new(funcTypeFixed16)
  1954			args = fixed.args[:0:len(fixed.args)]
  1955			ft = &fixed.funcType
  1956		case n <= 32:
  1957			fixed := new(funcTypeFixed32)
  1958			args = fixed.args[:0:len(fixed.args)]
  1959			ft = &fixed.funcType
  1960		case n <= 64:
  1961			fixed := new(funcTypeFixed64)
  1962			args = fixed.args[:0:len(fixed.args)]
  1963			ft = &fixed.funcType
  1964		case n <= 128:
  1965			fixed := new(funcTypeFixed128)
  1966			args = fixed.args[:0:len(fixed.args)]
  1967			ft = &fixed.funcType
  1968		default:
  1969			panic("reflect.FuncOf: too many arguments")
  1970		}
  1971		*ft = *prototype
  1972	
  1973		// Build a hash and minimally populate ft.
  1974		var hash uint32
  1975		for _, in := range in {
  1976			t := in.(*rtype)
  1977			args = append(args, t)
  1978			hash = fnv1(hash, byte(t.hash>>24), byte(t.hash>>16), byte(t.hash>>8), byte(t.hash))
  1979		}
  1980		if variadic {
  1981			hash = fnv1(hash, 'v')
  1982		}
  1983		hash = fnv1(hash, '.')
  1984		for _, out := range out {
  1985			t := out.(*rtype)
  1986			args = append(args, t)
  1987			hash = fnv1(hash, byte(t.hash>>24), byte(t.hash>>16), byte(t.hash>>8), byte(t.hash))
  1988		}
  1989		if len(args) > 50 {
  1990			panic("reflect.FuncOf does not support more than 50 arguments")
  1991		}
  1992		ft.tflag = 0
  1993		ft.hash = hash
  1994		ft.inCount = uint16(len(in))
  1995		ft.outCount = uint16(len(out))
  1996		if variadic {
  1997			ft.outCount |= 1 << 15
  1998		}
  1999	
  2000		// Look in cache.
  2001		if ts, ok := funcLookupCache.m.Load(hash); ok {
  2002			for _, t := range ts.([]*rtype) {
  2003				if haveIdenticalUnderlyingType(&ft.rtype, t, true) {
  2004					return t
  2005				}
  2006			}
  2007		}
  2008	
  2009		// Not in cache, lock and retry.
  2010		funcLookupCache.Lock()
  2011		defer funcLookupCache.Unlock()
  2012		if ts, ok := funcLookupCache.m.Load(hash); ok {
  2013			for _, t := range ts.([]*rtype) {
  2014				if haveIdenticalUnderlyingType(&ft.rtype, t, true) {
  2015					return t
  2016				}
  2017			}
  2018		}
  2019	
  2020		addToCache := func(tt *rtype) Type {
  2021			var rts []*rtype
  2022			if rti, ok := funcLookupCache.m.Load(hash); ok {
  2023				rts = rti.([]*rtype)
  2024			}
  2025			funcLookupCache.m.Store(hash, append(rts, tt))
  2026			return tt
  2027		}
  2028	
  2029		// Look in known types for the same string representation.
  2030		str := funcStr(ft)
  2031		for _, tt := range typesByString(str) {
  2032			if haveIdenticalUnderlyingType(&ft.rtype, tt, true) {
  2033				return addToCache(tt)
  2034			}
  2035		}
  2036	
  2037		// Populate the remaining fields of ft and store in cache.
  2038		ft.str = resolveReflectName(newName(str, "", false))
  2039		ft.ptrToThis = 0
  2040		return addToCache(&ft.rtype)
  2041	}
  2042	
  2043	// funcStr builds a string representation of a funcType.
  2044	func funcStr(ft *funcType) string {
  2045		repr := make([]byte, 0, 64)
  2046		repr = append(repr, "func("...)
  2047		for i, t := range ft.in() {
  2048			if i > 0 {
  2049				repr = append(repr, ", "...)
  2050			}
  2051			if ft.IsVariadic() && i == int(ft.inCount)-1 {
  2052				repr = append(repr, "..."...)
  2053				repr = append(repr, (*sliceType)(unsafe.Pointer(t)).elem.String()...)
  2054			} else {
  2055				repr = append(repr, t.String()...)
  2056			}
  2057		}
  2058		repr = append(repr, ')')
  2059		out := ft.out()
  2060		if len(out) == 1 {
  2061			repr = append(repr, ' ')
  2062		} else if len(out) > 1 {
  2063			repr = append(repr, " ("...)
  2064		}
  2065		for i, t := range out {
  2066			if i > 0 {
  2067				repr = append(repr, ", "...)
  2068			}
  2069			repr = append(repr, t.String()...)
  2070		}
  2071		if len(out) > 1 {
  2072			repr = append(repr, ')')
  2073		}
  2074		return string(repr)
  2075	}
  2076	
  2077	// isReflexive reports whether the == operation on the type is reflexive.
  2078	// That is, x == x for all values x of type t.
  2079	func isReflexive(t *rtype) bool {
  2080		switch t.Kind() {
  2081		case Bool, Int, Int8, Int16, Int32, Int64, Uint, Uint8, Uint16, Uint32, Uint64, Uintptr, Chan, Ptr, String, UnsafePointer:
  2082			return true
  2083		case Float32, Float64, Complex64, Complex128, Interface:
  2084			return false
  2085		case Array:
  2086			tt := (*arrayType)(unsafe.Pointer(t))
  2087			return isReflexive(tt.elem)
  2088		case Struct:
  2089			tt := (*structType)(unsafe.Pointer(t))
  2090			for _, f := range tt.fields {
  2091				if !isReflexive(f.typ) {
  2092					return false
  2093				}
  2094			}
  2095			return true
  2096		default:
  2097			// Func, Map, Slice, Invalid
  2098			panic("isReflexive called on non-key type " + t.String())
  2099		}
  2100	}
  2101	
  2102	// needKeyUpdate reports whether map overwrites require the key to be copied.
  2103	func needKeyUpdate(t *rtype) bool {
  2104		switch t.Kind() {
  2105		case Bool, Int, Int8, Int16, Int32, Int64, Uint, Uint8, Uint16, Uint32, Uint64, Uintptr, Chan, Ptr, UnsafePointer:
  2106			return false
  2107		case Float32, Float64, Complex64, Complex128, Interface, String:
  2108			// Float keys can be updated from +0 to -0.
  2109			// String keys can be updated to use a smaller backing store.
  2110			// Interfaces might have floats of strings in them.
  2111			return true
  2112		case Array:
  2113			tt := (*arrayType)(unsafe.Pointer(t))
  2114			return needKeyUpdate(tt.elem)
  2115		case Struct:
  2116			tt := (*structType)(unsafe.Pointer(t))
  2117			for _, f := range tt.fields {
  2118				if needKeyUpdate(f.typ) {
  2119					return true
  2120				}
  2121			}
  2122			return false
  2123		default:
  2124			// Func, Map, Slice, Invalid
  2125			panic("needKeyUpdate called on non-key type " + t.String())
  2126		}
  2127	}
  2128	
  2129	// hashMightPanic reports whether the hash of a map key of type t might panic.
  2130	func hashMightPanic(t *rtype) bool {
  2131		switch t.Kind() {
  2132		case Interface:
  2133			return true
  2134		case Array:
  2135			tt := (*arrayType)(unsafe.Pointer(t))
  2136			return hashMightPanic(tt.elem)
  2137		case Struct:
  2138			tt := (*structType)(unsafe.Pointer(t))
  2139			for _, f := range tt.fields {
  2140				if hashMightPanic(f.typ) {
  2141					return true
  2142				}
  2143			}
  2144			return false
  2145		default:
  2146			return false
  2147		}
  2148	}
  2149	
  2150	// Make sure these routines stay in sync with ../../runtime/map.go!
  2151	// These types exist only for GC, so we only fill out GC relevant info.
  2152	// Currently, that's just size and the GC program. We also fill in string
  2153	// for possible debugging use.
  2154	const (
  2155		bucketSize uintptr = 8
  2156		maxKeySize uintptr = 128
  2157		maxValSize uintptr = 128
  2158	)
  2159	
  2160	func bucketOf(ktyp, etyp *rtype) *rtype {
  2161		if ktyp.size > maxKeySize {
  2162			ktyp = PtrTo(ktyp).(*rtype)
  2163		}
  2164		if etyp.size > maxValSize {
  2165			etyp = PtrTo(etyp).(*rtype)
  2166		}
  2167	
  2168		// Prepare GC data if any.
  2169		// A bucket is at most bucketSize*(1+maxKeySize+maxValSize)+2*ptrSize bytes,
  2170		// or 2072 bytes, or 259 pointer-size words, or 33 bytes of pointer bitmap.
  2171		// Note that since the key and value are known to be <= 128 bytes,
  2172		// they're guaranteed to have bitmaps instead of GC programs.
  2173		var gcdata *byte
  2174		var ptrdata uintptr
  2175		var overflowPad uintptr
  2176	
  2177		// On NaCl, pad if needed to make overflow end at the proper struct alignment.
  2178		// On other systems, align > ptrSize is not possible.
  2179		if runtime.GOARCH == "amd64p32" && (ktyp.align > ptrSize || etyp.align > ptrSize) {
  2180			overflowPad = ptrSize
  2181		}
  2182		size := bucketSize*(1+ktyp.size+etyp.size) + overflowPad + ptrSize
  2183		if size&uintptr(ktyp.align-1) != 0 || size&uintptr(etyp.align-1) != 0 {
  2184			panic("reflect: bad size computation in MapOf")
  2185		}
  2186	
  2187		if ktyp.ptrdata != 0 || etyp.ptrdata != 0 {
  2188			nptr := (bucketSize*(1+ktyp.size+etyp.size) + ptrSize) / ptrSize
  2189			mask := make([]byte, (nptr+7)/8)
  2190			base := bucketSize / ptrSize
  2191	
  2192			if ktyp.ptrdata != 0 {
  2193				if ktyp.kind&kindGCProg != 0 {
  2194					panic("reflect: unexpected GC program in MapOf")
  2195				}
  2196				kmask := (*[16]byte)(unsafe.Pointer(ktyp.gcdata))
  2197				for i := uintptr(0); i < ktyp.ptrdata/ptrSize; i++ {
  2198					if (kmask[i/8]>>(i%8))&1 != 0 {
  2199						for j := uintptr(0); j < bucketSize; j++ {
  2200							word := base + j*ktyp.size/ptrSize + i
  2201							mask[word/8] |= 1 << (word % 8)
  2202						}
  2203					}
  2204				}
  2205			}
  2206			base += bucketSize * ktyp.size / ptrSize
  2207	
  2208			if etyp.ptrdata != 0 {
  2209				if etyp.kind&kindGCProg != 0 {
  2210					panic("reflect: unexpected GC program in MapOf")
  2211				}
  2212				emask := (*[16]byte)(unsafe.Pointer(etyp.gcdata))
  2213				for i := uintptr(0); i < etyp.ptrdata/ptrSize; i++ {
  2214					if (emask[i/8]>>(i%8))&1 != 0 {
  2215						for j := uintptr(0); j < bucketSize; j++ {
  2216							word := base + j*etyp.size/ptrSize + i
  2217							mask[word/8] |= 1 << (word % 8)
  2218						}
  2219					}
  2220				}
  2221			}
  2222			base += bucketSize * etyp.size / ptrSize
  2223			base += overflowPad / ptrSize
  2224	
  2225			word := base
  2226			mask[word/8] |= 1 << (word % 8)
  2227			gcdata = &mask[0]
  2228			ptrdata = (word + 1) * ptrSize
  2229	
  2230			// overflow word must be last
  2231			if ptrdata != size {
  2232				panic("reflect: bad layout computation in MapOf")
  2233			}
  2234		}
  2235	
  2236		b := &rtype{
  2237			align:   ptrSize,
  2238			size:    size,
  2239			kind:    uint8(Struct),
  2240			ptrdata: ptrdata,
  2241			gcdata:  gcdata,
  2242		}
  2243		if overflowPad > 0 {
  2244			b.align = 8
  2245		}
  2246		s := "bucket(" + ktyp.String() + "," + etyp.String() + ")"
  2247		b.str = resolveReflectName(newName(s, "", false))
  2248		return b
  2249	}
  2250	
  2251	// SliceOf returns the slice type with element type t.
  2252	// For example, if t represents int, SliceOf(t) represents []int.
  2253	func SliceOf(t Type) Type {
  2254		typ := t.(*rtype)
  2255	
  2256		// Look in cache.
  2257		ckey := cacheKey{Slice, typ, nil, 0}
  2258		if slice, ok := lookupCache.Load(ckey); ok {
  2259			return slice.(Type)
  2260		}
  2261	
  2262		// Look in known types.
  2263		s := "[]" + typ.String()
  2264		for _, tt := range typesByString(s) {
  2265			slice := (*sliceType)(unsafe.Pointer(tt))
  2266			if slice.elem == typ {
  2267				ti, _ := lookupCache.LoadOrStore(ckey, tt)
  2268				return ti.(Type)
  2269			}
  2270		}
  2271	
  2272		// Make a slice type.
  2273		var islice interface{} = ([]unsafe.Pointer)(nil)
  2274		prototype := *(**sliceType)(unsafe.Pointer(&islice))
  2275		slice := *prototype
  2276		slice.tflag = 0
  2277		slice.str = resolveReflectName(newName(s, "", false))
  2278		slice.hash = fnv1(typ.hash, '[')
  2279		slice.elem = typ
  2280		slice.ptrToThis = 0
  2281	
  2282		ti, _ := lookupCache.LoadOrStore(ckey, &slice.rtype)
  2283		return ti.(Type)
  2284	}
  2285	
  2286	// The structLookupCache caches StructOf lookups.
  2287	// StructOf does not share the common lookupCache since we need to pin
  2288	// the memory associated with *structTypeFixedN.
  2289	var structLookupCache struct {
  2290		sync.Mutex // Guards stores (but not loads) on m.
  2291	
  2292		// m is a map[uint32][]Type keyed by the hash calculated in StructOf.
  2293		// Elements in m are append-only and thus safe for concurrent reading.
  2294		m sync.Map
  2295	}
  2296	
  2297	type structTypeUncommon struct {
  2298		structType
  2299		u uncommonType
  2300	}
  2301	
  2302	// isLetter reports whether a given 'rune' is classified as a Letter.
  2303	func isLetter(ch rune) bool {
  2304		return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_' || ch >= utf8.RuneSelf && unicode.IsLetter(ch)
  2305	}
  2306	
  2307	// isValidFieldName checks if a string is a valid (struct) field name or not.
  2308	//
  2309	// According to the language spec, a field name should be an identifier.
  2310	//
  2311	// identifier = letter { letter | unicode_digit } .
  2312	// letter = unicode_letter | "_" .
  2313	func isValidFieldName(fieldName string) bool {
  2314		for i, c := range fieldName {
  2315			if i == 0 && !isLetter(c) {
  2316				return false
  2317			}
  2318	
  2319			if !(isLetter(c) || unicode.IsDigit(c)) {
  2320				return false
  2321			}
  2322		}
  2323	
  2324		return len(fieldName) > 0
  2325	}
  2326	
  2327	// StructOf returns the struct type containing fields.
  2328	// The Offset and Index fields are ignored and computed as they would be
  2329	// by the compiler.
  2330	//
  2331	// StructOf currently does not generate wrapper methods for embedded
  2332	// fields and panics if passed unexported StructFields.
  2333	// These limitations may be lifted in a future version.
  2334	func StructOf(fields []StructField) Type {
  2335		var (
  2336			hash       = fnv1(0, []byte("struct {")...)
  2337			size       uintptr
  2338			typalign   uint8
  2339			comparable = true
  2340			hashable   = true
  2341			methods    []method
  2342	
  2343			fs   = make([]structField, len(fields))
  2344			repr = make([]byte, 0, 64)
  2345			fset = map[string]struct{}{} // fields' names
  2346	
  2347			hasGCProg = false // records whether a struct-field type has a GCProg
  2348		)
  2349	
  2350		lastzero := uintptr(0)
  2351		repr = append(repr, "struct {"...)
  2352		for i, field := range fields {
  2353			if field.Name == "" {
  2354				panic("reflect.StructOf: field " + strconv.Itoa(i) + " has no name")
  2355			}
  2356			if !isValidFieldName(field.Name) {
  2357				panic("reflect.StructOf: field " + strconv.Itoa(i) + " has invalid name")
  2358			}
  2359			if field.Type == nil {
  2360				panic("reflect.StructOf: field " + strconv.Itoa(i) + " has no type")
  2361			}
  2362			f := runtimeStructField(field)
  2363			ft := f.typ
  2364			if ft.kind&kindGCProg != 0 {
  2365				hasGCProg = true
  2366			}
  2367	
  2368			// Update string and hash
  2369			name := f.name.name()
  2370			hash = fnv1(hash, []byte(name)...)
  2371			repr = append(repr, (" " + name)...)
  2372			if f.embedded() {
  2373				// Embedded field
  2374				if f.typ.Kind() == Ptr {
  2375					// Embedded ** and *interface{} are illegal
  2376					elem := ft.Elem()
  2377					if k := elem.Kind(); k == Ptr || k == Interface {
  2378						panic("reflect.StructOf: illegal embedded field type " + ft.String())
  2379					}
  2380				}
  2381	
  2382				switch f.typ.Kind() {
  2383				case Interface:
  2384					ift := (*interfaceType)(unsafe.Pointer(ft))
  2385					for im, m := range ift.methods {
  2386						if ift.nameOff(m.name).pkgPath() != "" {
  2387							// TODO(sbinet).  Issue 15924.
  2388							panic("reflect: embedded interface with unexported method(s) not implemented")
  2389						}
  2390	
  2391						var (
  2392							mtyp    = ift.typeOff(m.typ)
  2393							ifield  = i
  2394							imethod = im
  2395							ifn     Value
  2396							tfn     Value
  2397						)
  2398	
  2399						if ft.kind&kindDirectIface != 0 {
  2400							tfn = MakeFunc(mtyp, func(in []Value) []Value {
  2401								var args []Value
  2402								var recv = in[0]
  2403								if len(in) > 1 {
  2404									args = in[1:]
  2405								}
  2406								return recv.Field(ifield).Method(imethod).Call(args)
  2407							})
  2408							ifn = MakeFunc(mtyp, func(in []Value) []Value {
  2409								var args []Value
  2410								var recv = in[0]
  2411								if len(in) > 1 {
  2412									args = in[1:]
  2413								}
  2414								return recv.Field(ifield).Method(imethod).Call(args)
  2415							})
  2416						} else {
  2417							tfn = MakeFunc(mtyp, func(in []Value) []Value {
  2418								var args []Value
  2419								var recv = in[0]
  2420								if len(in) > 1 {
  2421									args = in[1:]
  2422								}
  2423								return recv.Field(ifield).Method(imethod).Call(args)
  2424							})
  2425							ifn = MakeFunc(mtyp, func(in []Value) []Value {
  2426								var args []Value
  2427								var recv = Indirect(in[0])
  2428								if len(in) > 1 {
  2429									args = in[1:]
  2430								}
  2431								return recv.Field(ifield).Method(imethod).Call(args)
  2432							})
  2433						}
  2434	
  2435						methods = append(methods, method{
  2436							name: resolveReflectName(ift.nameOff(m.name)),
  2437							mtyp: resolveReflectType(mtyp),
  2438							ifn:  resolveReflectText(unsafe.Pointer(&ifn)),
  2439							tfn:  resolveReflectText(unsafe.Pointer(&tfn)),
  2440						})
  2441					}
  2442				case Ptr:
  2443					ptr := (*ptrType)(unsafe.Pointer(ft))
  2444					if unt := ptr.uncommon(); unt != nil {
  2445						if i > 0 && unt.mcount > 0 {
  2446							// Issue 15924.
  2447							panic("reflect: embedded type with methods not implemented if type is not first field")
  2448						}
  2449						if len(fields) > 1 {
  2450							panic("reflect: embedded type with methods not implemented if there is more than one field")
  2451						}
  2452						for _, m := range unt.methods() {
  2453							mname := ptr.nameOff(m.name)
  2454							if mname.pkgPath() != "" {
  2455								// TODO(sbinet).
  2456								// Issue 15924.
  2457								panic("reflect: embedded interface with unexported method(s) not implemented")
  2458							}
  2459							methods = append(methods, method{
  2460								name: resolveReflectName(mname),
  2461								mtyp: resolveReflectType(ptr.typeOff(m.mtyp)),
  2462								ifn:  resolveReflectText(ptr.textOff(m.ifn)),
  2463								tfn:  resolveReflectText(ptr.textOff(m.tfn)),
  2464							})
  2465						}
  2466					}
  2467					if unt := ptr.elem.uncommon(); unt != nil {
  2468						for _, m := range unt.methods() {
  2469							mname := ptr.nameOff(m.name)
  2470							if mname.pkgPath() != "" {
  2471								// TODO(sbinet)
  2472								// Issue 15924.
  2473								panic("reflect: embedded interface with unexported method(s) not implemented")
  2474							}
  2475							methods = append(methods, method{
  2476								name: resolveReflectName(mname),
  2477								mtyp: resolveReflectType(ptr.elem.typeOff(m.mtyp)),
  2478								ifn:  resolveReflectText(ptr.elem.textOff(m.ifn)),
  2479								tfn:  resolveReflectText(ptr.elem.textOff(m.tfn)),
  2480							})
  2481						}
  2482					}
  2483				default:
  2484					if unt := ft.uncommon(); unt != nil {
  2485						if i > 0 && unt.mcount > 0 {
  2486							// Issue 15924.
  2487							panic("reflect: embedded type with methods not implemented if type is not first field")
  2488						}
  2489						if len(fields) > 1 && ft.kind&kindDirectIface != 0 {
  2490							panic("reflect: embedded type with methods not implemented for non-pointer type")
  2491						}
  2492						for _, m := range unt.methods() {
  2493							mname := ft.nameOff(m.name)
  2494							if mname.pkgPath() != "" {
  2495								// TODO(sbinet)
  2496								// Issue 15924.
  2497								panic("reflect: embedded interface with unexported method(s) not implemented")
  2498							}
  2499							methods = append(methods, method{
  2500								name: resolveReflectName(mname),
  2501								mtyp: resolveReflectType(ft.typeOff(m.mtyp)),
  2502								ifn:  resolveReflectText(ft.textOff(m.ifn)),
  2503								tfn:  resolveReflectText(ft.textOff(m.tfn)),
  2504							})
  2505	
  2506						}
  2507					}
  2508				}
  2509			}
  2510			if _, dup := fset[name]; dup {
  2511				panic("reflect.StructOf: duplicate field " + name)
  2512			}
  2513			fset[name] = struct{}{}
  2514	
  2515			hash = fnv1(hash, byte(ft.hash>>24), byte(ft.hash>>16), byte(ft.hash>>8), byte(ft.hash))
  2516	
  2517			repr = append(repr, (" " + ft.String())...)
  2518			if f.name.tagLen() > 0 {
  2519				hash = fnv1(hash, []byte(f.name.tag())...)
  2520				repr = append(repr, (" " + strconv.Quote(f.name.tag()))...)
  2521			}
  2522			if i < len(fields)-1 {
  2523				repr = append(repr, ';')
  2524			}
  2525	
  2526			comparable = comparable && (ft.alg.equal != nil)
  2527			hashable = hashable && (ft.alg.hash != nil)
  2528	
  2529			offset := align(size, uintptr(ft.align))
  2530			if ft.align > typalign {
  2531				typalign = ft.align
  2532			}
  2533			size = offset + ft.size
  2534			f.offsetEmbed |= offset << 1
  2535	
  2536			if ft.size == 0 {
  2537				lastzero = size
  2538			}
  2539	
  2540			fs[i] = f
  2541		}
  2542	
  2543		if size > 0 && lastzero == size {
  2544			// This is a non-zero sized struct that ends in a
  2545			// zero-sized field. We add an extra byte of padding,
  2546			// to ensure that taking the address of the final
  2547			// zero-sized field can't manufacture a pointer to the
  2548			// next object in the heap. See issue 9401.
  2549			size++
  2550		}
  2551	
  2552		var typ *structType
  2553		var ut *uncommonType
  2554	
  2555		if len(methods) == 0 {
  2556			t := new(structTypeUncommon)
  2557			typ = &t.structType
  2558			ut = &t.u
  2559		} else {
  2560			// A *rtype representing a struct is followed directly in memory by an
  2561			// array of method objects representing the methods attached to the
  2562			// struct. To get the same layout for a run time generated type, we
  2563			// need an array directly following the uncommonType memory.
  2564			// A similar strategy is used for funcTypeFixed4, ...funcTypeFixedN.
  2565			tt := New(StructOf([]StructField{
  2566				{Name: "S", Type: TypeOf(structType{})},
  2567				{Name: "U", Type: TypeOf(uncommonType{})},
  2568				{Name: "M", Type: ArrayOf(len(methods), TypeOf(methods[0]))},
  2569			}))
  2570	
  2571			typ = (*structType)(unsafe.Pointer(tt.Elem().Field(0).UnsafeAddr()))
  2572			ut = (*uncommonType)(unsafe.Pointer(tt.Elem().Field(1).UnsafeAddr()))
  2573	
  2574			copy(tt.Elem().Field(2).Slice(0, len(methods)).Interface().([]method), methods)
  2575		}
  2576		// TODO(sbinet): Once we allow embedding multiple types,
  2577		// methods will need to be sorted like the compiler does.
  2578		// TODO(sbinet): Once we allow non-exported methods, we will
  2579		// need to compute xcount as the number of exported methods.
  2580		ut.mcount = uint16(len(methods))
  2581		ut.xcount = ut.mcount
  2582		ut.moff = uint32(unsafe.Sizeof(uncommonType{}))
  2583	
  2584		if len(fs) > 0 {
  2585			repr = append(repr, ' ')
  2586		}
  2587		repr = append(repr, '}')
  2588		hash = fnv1(hash, '}')
  2589		str := string(repr)
  2590	
  2591		// Round the size up to be a multiple of the alignment.
  2592		size = align(size, uintptr(typalign))
  2593	
  2594		// Make the struct type.
  2595		var istruct interface{} = struct{}{}
  2596		prototype := *(**structType)(unsafe.Pointer(&istruct))
  2597		*typ = *prototype
  2598		typ.fields = fs
  2599	
  2600		// Look in cache.
  2601		if ts, ok := structLookupCache.m.Load(hash); ok {
  2602			for _, st := range ts.([]Type) {
  2603				t := st.common()
  2604				if haveIdenticalUnderlyingType(&typ.rtype, t, true) {
  2605					return t
  2606				}
  2607			}
  2608		}
  2609	
  2610		// Not in cache, lock and retry.
  2611		structLookupCache.Lock()
  2612		defer structLookupCache.Unlock()
  2613		if ts, ok := structLookupCache.m.Load(hash); ok {
  2614			for _, st := range ts.([]Type) {
  2615				t := st.common()
  2616				if haveIdenticalUnderlyingType(&typ.rtype, t, true) {
  2617					return t
  2618				}
  2619			}
  2620		}
  2621	
  2622		addToCache := func(t Type) Type {
  2623			var ts []Type
  2624			if ti, ok := structLookupCache.m.Load(hash); ok {
  2625				ts = ti.([]Type)
  2626			}
  2627			structLookupCache.m.Store(hash, append(ts, t))
  2628			return t
  2629		}
  2630	
  2631		// Look in known types.
  2632		for _, t := range typesByString(str) {
  2633			if haveIdenticalUnderlyingType(&typ.rtype, t, true) {
  2634				// even if 't' wasn't a structType with methods, we should be ok
  2635				// as the 'u uncommonType' field won't be accessed except when
  2636				// tflag&tflagUncommon is set.
  2637				return addToCache(t)
  2638			}
  2639		}
  2640	
  2641		typ.str = resolveReflectName(newName(str, "", false))
  2642		typ.tflag = 0
  2643		typ.hash = hash
  2644		typ.size = size
  2645		typ.ptrdata = typeptrdata(typ.common())
  2646		typ.align = typalign
  2647		typ.fieldAlign = typalign
  2648		typ.ptrToThis = 0
  2649		if len(methods) > 0 {
  2650			typ.tflag |= tflagUncommon
  2651		}
  2652	
  2653		if hasGCProg {
  2654			lastPtrField := 0
  2655			for i, ft := range fs {
  2656				if ft.typ.pointers() {
  2657					lastPtrField = i
  2658				}
  2659			}
  2660			prog := []byte{0, 0, 0, 0} // will be length of prog
  2661			var off uintptr
  2662			for i, ft := range fs {
  2663				if i > lastPtrField {
  2664					// gcprog should not include anything for any field after
  2665					// the last field that contains pointer data
  2666					break
  2667				}
  2668				if !ft.typ.pointers() {
  2669					// Ignore pointerless fields.
  2670					continue
  2671				}
  2672				// Pad to start of this field with zeros.
  2673				if ft.offset() > off {
  2674					n := (ft.offset() - off) / ptrSize
  2675					prog = append(prog, 0x01, 0x00) // emit a 0 bit
  2676					if n > 1 {
  2677						prog = append(prog, 0x81)      // repeat previous bit
  2678						prog = appendVarint(prog, n-1) // n-1 times
  2679					}
  2680					off = ft.offset()
  2681				}
  2682	
  2683				elemGC := (*[1 << 30]byte)(unsafe.Pointer(ft.typ.gcdata))[:]
  2684				elemPtrs := ft.typ.ptrdata / ptrSize
  2685				if ft.typ.kind&kindGCProg == 0 {
  2686					// Element is small with pointer mask; use as literal bits.
  2687					mask := elemGC
  2688					// Emit 120-bit chunks of full bytes (max is 127 but we avoid using partial bytes).
  2689					var n uintptr
  2690					for n = elemPtrs; n > 120; n -= 120 {
  2691						prog = append(prog, 120)
  2692						prog = append(prog, mask[:15]...)
  2693						mask = mask[15:]
  2694					}
  2695					prog = append(prog, byte(n))
  2696					prog = append(prog, mask[:(n+7)/8]...)
  2697				} else {
  2698					// Element has GC program; emit one element.
  2699					elemProg := elemGC[4 : 4+*(*uint32)(unsafe.Pointer(&elemGC[0]))-1]
  2700					prog = append(prog, elemProg...)
  2701				}
  2702				off += ft.typ.ptrdata
  2703			}
  2704			prog = append(prog, 0)
  2705			*(*uint32)(unsafe.Pointer(&prog[0])) = uint32(len(prog) - 4)
  2706			typ.kind |= kindGCProg
  2707			typ.gcdata = &prog[0]
  2708		} else {
  2709			typ.kind &^= kindGCProg
  2710			bv := new(bitVector)
  2711			addTypeBits(bv, 0, typ.common())
  2712			if len(bv.data) > 0 {
  2713				typ.gcdata = &bv.data[0]
  2714			}
  2715		}
  2716		typ.alg = new(typeAlg)
  2717		if hashable {
  2718			typ.alg.hash = func(p unsafe.Pointer, seed uintptr) uintptr {
  2719				o := seed
  2720				for _, ft := range typ.fields {
  2721					pi := add(p, ft.offset(), "&x.field safe")
  2722					o = ft.typ.alg.hash(pi, o)
  2723				}
  2724				return o
  2725			}
  2726		}
  2727	
  2728		if comparable {
  2729			typ.alg.equal = func(p, q unsafe.Pointer) bool {
  2730				for _, ft := range typ.fields {
  2731					pi := add(p, ft.offset(), "&x.field safe")
  2732					qi := add(q, ft.offset(), "&x.field safe")
  2733					if !ft.typ.alg.equal(pi, qi) {
  2734						return false
  2735					}
  2736				}
  2737				return true
  2738			}
  2739		}
  2740	
  2741		switch {
  2742		case len(fs) == 1 && !ifaceIndir(fs[0].typ):
  2743			// structs of 1 direct iface type can be direct
  2744			typ.kind |= kindDirectIface
  2745		default:
  2746			typ.kind &^= kindDirectIface
  2747		}
  2748	
  2749		return addToCache(&typ.rtype)
  2750	}
  2751	
  2752	func runtimeStructField(field StructField) structField {
  2753		if field.PkgPath != "" {
  2754			panic("reflect.StructOf: StructOf does not allow unexported fields")
  2755		}
  2756	
  2757		// Best-effort check for misuse.
  2758		// Since PkgPath is empty, not much harm done if Unicode lowercase slips through.
  2759		c := field.Name[0]
  2760		if 'a' <= c && c <= 'z' || c == '_' {
  2761			panic("reflect.StructOf: field \"" + field.Name + "\" is unexported but missing PkgPath")
  2762		}
  2763	
  2764		offsetEmbed := uintptr(0)
  2765		if field.Anonymous {
  2766			offsetEmbed |= 1
  2767		}
  2768	
  2769		resolveReflectType(field.Type.common()) // install in runtime
  2770		return structField{
  2771			name:        newName(field.Name, string(field.Tag), true),
  2772			typ:         field.Type.common(),
  2773			offsetEmbed: offsetEmbed,
  2774		}
  2775	}
  2776	
  2777	// typeptrdata returns the length in bytes of the prefix of t
  2778	// containing pointer data. Anything after this offset is scalar data.
  2779	// keep in sync with ../cmd/compile/internal/gc/reflect.go
  2780	func typeptrdata(t *rtype) uintptr {
  2781		switch t.Kind() {
  2782		case Struct:
  2783			st := (*structType)(unsafe.Pointer(t))
  2784			// find the last field that has pointers.
  2785			field := -1
  2786			for i := range st.fields {
  2787				ft := st.fields[i].typ
  2788				if ft.pointers() {
  2789					field = i
  2790				}
  2791			}
  2792			if field == -1 {
  2793				return 0
  2794			}
  2795			f := st.fields[field]
  2796			return f.offset() + f.typ.ptrdata
  2797	
  2798		default:
  2799			panic("reflect.typeptrdata: unexpected type, " + t.String())
  2800		}
  2801	}
  2802	
  2803	// See cmd/compile/internal/gc/reflect.go for derivation of constant.
  2804	const maxPtrmaskBytes = 2048
  2805	
  2806	// ArrayOf returns the array type with the given count and element type.
  2807	// For example, if t represents int, ArrayOf(5, t) represents [5]int.
  2808	//
  2809	// If the resulting type would be larger than the available address space,
  2810	// ArrayOf panics.
  2811	func ArrayOf(count int, elem Type) Type {
  2812		typ := elem.(*rtype)
  2813	
  2814		// Look in cache.
  2815		ckey := cacheKey{Array, typ, nil, uintptr(count)}
  2816		if array, ok := lookupCache.Load(ckey); ok {
  2817			return array.(Type)
  2818		}
  2819	
  2820		// Look in known types.
  2821		s := "[" + strconv.Itoa(count) + "]" + typ.String()
  2822		for _, tt := range typesByString(s) {
  2823			array := (*arrayType)(unsafe.Pointer(tt))
  2824			if array.elem == typ {
  2825				ti, _ := lookupCache.LoadOrStore(ckey, tt)
  2826				return ti.(Type)
  2827			}
  2828		}
  2829	
  2830		// Make an array type.
  2831		var iarray interface{} = [1]unsafe.Pointer{}
  2832		prototype := *(**arrayType)(unsafe.Pointer(&iarray))
  2833		array := *prototype
  2834		array.tflag = 0
  2835		array.str = resolveReflectName(newName(s, "", false))
  2836		array.hash = fnv1(typ.hash, '[')
  2837		for n := uint32(count); n > 0; n >>= 8 {
  2838			array.hash = fnv1(array.hash, byte(n))
  2839		}
  2840		array.hash = fnv1(array.hash, ']')
  2841		array.elem = typ
  2842		array.ptrToThis = 0
  2843		if typ.size > 0 {
  2844			max := ^uintptr(0) / typ.size
  2845			if uintptr(count) > max {
  2846				panic("reflect.ArrayOf: array size would exceed virtual address space")
  2847			}
  2848		}
  2849		array.size = typ.size * uintptr(count)
  2850		if count > 0 && typ.ptrdata != 0 {
  2851			array.ptrdata = typ.size*uintptr(count-1) + typ.ptrdata
  2852		}
  2853		array.align = typ.align
  2854		array.fieldAlign = typ.fieldAlign
  2855		array.len = uintptr(count)
  2856		array.slice = SliceOf(elem).(*rtype)
  2857	
  2858		switch {
  2859		case typ.ptrdata == 0 || array.size == 0:
  2860			// No pointers.
  2861			array.gcdata = nil
  2862			array.ptrdata = 0
  2863	
  2864		case count == 1:
  2865			// In memory, 1-element array looks just like the element.
  2866			array.kind |= typ.kind & kindGCProg
  2867			array.gcdata = typ.gcdata
  2868			array.ptrdata = typ.ptrdata
  2869	
  2870		case typ.kind&kindGCProg == 0 && array.size <= maxPtrmaskBytes*8*ptrSize:
  2871			// Element is small with pointer mask; array is still small.
  2872			// Create direct pointer mask by turning each 1 bit in elem
  2873			// into count 1 bits in larger mask.
  2874			mask := make([]byte, (array.ptrdata/ptrSize+7)/8)
  2875			elemMask := (*[1 << 30]byte)(unsafe.Pointer(typ.gcdata))[:]
  2876			elemWords := typ.size / ptrSize
  2877			for j := uintptr(0); j < typ.ptrdata/ptrSize; j++ {
  2878				if (elemMask[j/8]>>(j%8))&1 != 0 {
  2879					for i := uintptr(0); i < array.len; i++ {
  2880						k := i*elemWords + j
  2881						mask[k/8] |= 1 << (k % 8)
  2882					}
  2883				}
  2884			}
  2885			array.gcdata = &mask[0]
  2886	
  2887		default:
  2888			// Create program that emits one element
  2889			// and then repeats to make the array.
  2890			prog := []byte{0, 0, 0, 0} // will be length of prog
  2891			elemGC := (*[1 << 30]byte)(unsafe.Pointer(typ.gcdata))[:]
  2892			elemPtrs := typ.ptrdata / ptrSize
  2893			if typ.kind&kindGCProg == 0 {
  2894				// Element is small with pointer mask; use as literal bits.
  2895				mask := elemGC
  2896				// Emit 120-bit chunks of full bytes (max is 127 but we avoid using partial bytes).
  2897				var n uintptr
  2898				for n = elemPtrs; n > 120; n -= 120 {
  2899					prog = append(prog, 120)
  2900					prog = append(prog, mask[:15]...)
  2901					mask = mask[15:]
  2902				}
  2903				prog = append(prog, byte(n))
  2904				prog = append(prog, mask[:(n+7)/8]...)
  2905			} else {
  2906				// Element has GC program; emit one element.
  2907				elemProg := elemGC[4 : 4+*(*uint32)(unsafe.Pointer(&elemGC[0]))-1]
  2908				prog = append(prog, elemProg...)
  2909			}
  2910			// Pad from ptrdata to size.
  2911			elemWords := typ.size / ptrSize
  2912			if elemPtrs < elemWords {
  2913				// Emit literal 0 bit, then repeat as needed.
  2914				prog = append(prog, 0x01, 0x00)
  2915				if elemPtrs+1 < elemWords {
  2916					prog = append(prog, 0x81)
  2917					prog = appendVarint(prog, elemWords-elemPtrs-1)
  2918				}
  2919			}
  2920			// Repeat count-1 times.
  2921			if elemWords < 0x80 {
  2922				prog = append(prog, byte(elemWords|0x80))
  2923			} else {
  2924				prog = append(prog, 0x80)
  2925				prog = appendVarint(prog, elemWords)
  2926			}
  2927			prog = appendVarint(prog, uintptr(count)-1)
  2928			prog = append(prog, 0)
  2929			*(*uint32)(unsafe.Pointer(&prog[0])) = uint32(len(prog) - 4)
  2930			array.kind |= kindGCProg
  2931			array.gcdata = &prog[0]
  2932			array.ptrdata = array.size // overestimate but ok; must match program
  2933		}
  2934	
  2935		etyp := typ.common()
  2936		esize := etyp.Size()
  2937		ealg := etyp.alg
  2938	
  2939		array.alg = new(typeAlg)
  2940		if ealg.equal != nil {
  2941			eequal := ealg.equal
  2942			array.alg.equal = func(p, q unsafe.Pointer) bool {
  2943				for i := 0; i < count; i++ {
  2944					pi := arrayAt(p, i, esize, "i < count")
  2945					qi := arrayAt(q, i, esize, "i < count")
  2946					if !eequal(pi, qi) {
  2947						return false
  2948					}
  2949	
  2950				}
  2951				return true
  2952			}
  2953		}
  2954		if ealg.hash != nil {
  2955			ehash := ealg.hash
  2956			array.alg.hash = func(ptr unsafe.Pointer, seed uintptr) uintptr {
  2957				o := seed
  2958				for i := 0; i < count; i++ {
  2959					o = ehash(arrayAt(ptr, i, esize, "i < count"), o)
  2960				}
  2961				return o
  2962			}
  2963		}
  2964	
  2965		switch {
  2966		case count == 1 && !ifaceIndir(typ):
  2967			// array of 1 direct iface type can be direct
  2968			array.kind |= kindDirectIface
  2969		default:
  2970			array.kind &^= kindDirectIface
  2971		}
  2972	
  2973		ti, _ := lookupCache.LoadOrStore(ckey, &array.rtype)
  2974		return ti.(Type)
  2975	}
  2976	
  2977	func appendVarint(x []byte, v uintptr) []byte {
  2978		for ; v >= 0x80; v >>= 7 {
  2979			x = append(x, byte(v|0x80))
  2980		}
  2981		x = append(x, byte(v))
  2982		return x
  2983	}
  2984	
  2985	// toType converts from a *rtype to a Type that can be returned
  2986	// to the client of package reflect. In gc, the only concern is that
  2987	// a nil *rtype must be replaced by a nil Type, but in gccgo this
  2988	// function takes care of ensuring that multiple *rtype for the same
  2989	// type are coalesced into a single Type.
  2990	func toType(t *rtype) Type {
  2991		if t == nil {
  2992			return nil
  2993		}
  2994		return t
  2995	}
  2996	
  2997	type layoutKey struct {
  2998		ftyp *funcType // function signature
  2999		rcvr *rtype    // receiver type, or nil if none
  3000	}
  3001	
  3002	type layoutType struct {
  3003		t         *rtype
  3004		argSize   uintptr // size of arguments
  3005		retOffset uintptr // offset of return values.
  3006		stack     *bitVector
  3007		framePool *sync.Pool
  3008	}
  3009	
  3010	var layoutCache sync.Map // map[layoutKey]layoutType
  3011	
  3012	// funcLayout computes a struct type representing the layout of the
  3013	// function arguments and return values for the function type t.
  3014	// If rcvr != nil, rcvr specifies the type of the receiver.
  3015	// The returned type exists only for GC, so we only fill out GC relevant info.
  3016	// Currently, that's just size and the GC program. We also fill in
  3017	// the name for possible debugging use.
  3018	func funcLayout(t *funcType, rcvr *rtype) (frametype *rtype, argSize, retOffset uintptr, stk *bitVector, framePool *sync.Pool) {
  3019		if t.Kind() != Func {
  3020			panic("reflect: funcLayout of non-func type")
  3021		}
  3022		if rcvr != nil && rcvr.Kind() == Interface {
  3023			panic("reflect: funcLayout with interface receiver " + rcvr.String())
  3024		}
  3025		k := layoutKey{t, rcvr}
  3026		if lti, ok := layoutCache.Load(k); ok {
  3027			lt := lti.(layoutType)
  3028			return lt.t, lt.argSize, lt.retOffset, lt.stack, lt.framePool
  3029		}
  3030	
  3031		// compute gc program & stack bitmap for arguments
  3032		ptrmap := new(bitVector)
  3033		var offset uintptr
  3034		if rcvr != nil {
  3035			// Reflect uses the "interface" calling convention for
  3036			// methods, where receivers take one word of argument
  3037			// space no matter how big they actually are.
  3038			if ifaceIndir(rcvr) || rcvr.pointers() {
  3039				ptrmap.append(1)
  3040			} else {
  3041				ptrmap.append(0)
  3042			}
  3043			offset += ptrSize
  3044		}
  3045		for _, arg := range t.in() {
  3046			offset += -offset & uintptr(arg.align-1)
  3047			addTypeBits(ptrmap, offset, arg)
  3048			offset += arg.size
  3049		}
  3050		argSize = offset
  3051		if runtime.GOARCH == "amd64p32" {
  3052			offset += -offset & (8 - 1)
  3053		}
  3054		offset += -offset & (ptrSize - 1)
  3055		retOffset = offset
  3056		for _, res := range t.out() {
  3057			offset += -offset & uintptr(res.align-1)
  3058			addTypeBits(ptrmap, offset, res)
  3059			offset += res.size
  3060		}
  3061		offset += -offset & (ptrSize - 1)
  3062	
  3063		// build dummy rtype holding gc program
  3064		x := &rtype{
  3065			align:   ptrSize,
  3066			size:    offset,
  3067			ptrdata: uintptr(ptrmap.n) * ptrSize,
  3068		}
  3069		if runtime.GOARCH == "amd64p32" {
  3070			x.align = 8
  3071		}
  3072		if ptrmap.n > 0 {
  3073			x.gcdata = &ptrmap.data[0]
  3074		}
  3075	
  3076		var s string
  3077		if rcvr != nil {
  3078			s = "methodargs(" + rcvr.String() + ")(" + t.String() + ")"
  3079		} else {
  3080			s = "funcargs(" + t.String() + ")"
  3081		}
  3082		x.str = resolveReflectName(newName(s, "", false))
  3083	
  3084		// cache result for future callers
  3085		framePool = &sync.Pool{New: func() interface{} {
  3086			return unsafe_New(x)
  3087		}}
  3088		lti, _ := layoutCache.LoadOrStore(k, layoutType{
  3089			t:         x,
  3090			argSize:   argSize,
  3091			retOffset: retOffset,
  3092			stack:     ptrmap,
  3093			framePool: framePool,
  3094		})
  3095		lt := lti.(layoutType)
  3096		return lt.t, lt.argSize, lt.retOffset, lt.stack, lt.framePool
  3097	}
  3098	
  3099	// ifaceIndir reports whether t is stored indirectly in an interface value.
  3100	func ifaceIndir(t *rtype) bool {
  3101		return t.kind&kindDirectIface == 0
  3102	}
  3103	
  3104	// Layout matches runtime.gobitvector (well enough).
  3105	type bitVector struct {
  3106		n    uint32 // number of bits
  3107		data []byte
  3108	}
  3109	
  3110	// append a bit to the bitmap.
  3111	func (bv *bitVector) append(bit uint8) {
  3112		if bv.n%8 == 0 {
  3113			bv.data = append(bv.data, 0)
  3114		}
  3115		bv.data[bv.n/8] |= bit << (bv.n % 8)
  3116		bv.n++
  3117	}
  3118	
  3119	func addTypeBits(bv *bitVector, offset uintptr, t *rtype) {
  3120		if t.ptrdata == 0 {
  3121			return
  3122		}
  3123	
  3124		switch Kind(t.kind & kindMask) {
  3125		case Chan, Func, Map, Ptr, Slice, String, UnsafePointer:
  3126			// 1 pointer at start of representation
  3127			for bv.n < uint32(offset/uintptr(ptrSize)) {
  3128				bv.append(0)
  3129			}
  3130			bv.append(1)
  3131	
  3132		case Interface:
  3133			// 2 pointers
  3134			for bv.n < uint32(offset/uintptr(ptrSize)) {
  3135				bv.append(0)
  3136			}
  3137			bv.append(1)
  3138			bv.append(1)
  3139	
  3140		case Array:
  3141			// repeat inner type
  3142			tt := (*arrayType)(unsafe.Pointer(t))
  3143			for i := 0; i < int(tt.len); i++ {
  3144				addTypeBits(bv, offset+uintptr(i)*tt.elem.size, tt.elem)
  3145			}
  3146	
  3147		case Struct:
  3148			// apply fields
  3149			tt := (*structType)(unsafe.Pointer(t))
  3150			for i := range tt.fields {
  3151				f := &tt.fields[i]
  3152				addTypeBits(bv, offset+f.offset(), f.typ)
  3153			}
  3154		}
  3155	}
  3156	

View as plain text