224
* These data structures are known to the compiler (../../cmd/gc/reflect.c).
225
* A few are known to ../runtime/type.go to convey to debuggers.
228
// The compiler can only construct empty interface values at
229
// compile time; non-empty interface values get created
230
// during initialization. Type is an empty interface
231
// so that the compiler can lay out references as data.
232
// The underlying type is *reflect.ArrayType and so on.
233
type runtimeType interface{}
235
// commonType is the common implementation of most values.
231
// rtype is the common implementation of most values.
236
232
// It is embedded in other, public struct types, but always
237
233
// with a unique tag like `reflect:"array"` or `reflect:"ptr"`
238
234
// so that code cannot convert from, say, *arrayType to *ptrType.
239
type commonType struct {
240
size uintptr // size in bytes
241
hash uint32 // hash of type; avoids computation in hash tables
242
_ uint8 // unused/padding
243
align uint8 // alignment of variable with this type
244
fieldAlign uint8 // alignment of struct field with this type
245
kind uint8 // enumeration for C
246
alg *uintptr // algorithm table (../runtime/runtime.h:/Alg)
247
string *string // string form; unnecessary but undeniably useful
248
*uncommonType // (relatively) uncommon fields
249
ptrToThis *runtimeType // pointer to this type, if used in binary or has methods
236
size uintptr // size in bytes
237
hash uint32 // hash of type; avoids computation in hash tables
238
_ uint8 // unused/padding
239
align uint8 // alignment of variable with this type
240
fieldAlign uint8 // alignment of struct field with this type
241
kind uint8 // enumeration for C
242
alg *uintptr // algorithm table (../runtime/runtime.h:/Alg)
243
gc unsafe.Pointer // garbage collection data
244
string *string // string form; unnecessary but undeniably useful
245
*uncommonType // (relatively) uncommon fields
246
ptrToThis *rtype // type for pointer to this type, if used in binary or has methods
252
249
// Method on non-interface type
253
250
type method struct {
254
251
name *string // name of method
255
252
pkgPath *string // nil for exported Names; otherwise import path
256
mtyp *runtimeType // method type (without receiver)
257
typ *runtimeType // .(*FuncType) underneath (with receiver)
253
mtyp *rtype // method type (without receiver)
254
typ *rtype // .(*FuncType) underneath (with receiver)
258
255
ifn unsafe.Pointer // fn used in interface call (one-word receiver)
259
256
tfn unsafe.Pointer // fn used for normal method call
281
278
// arrayType represents a fixed array type.
282
279
type arrayType struct {
283
commonType `reflect:"array"`
284
elem *runtimeType // array element type
285
slice *runtimeType // slice type
280
rtype `reflect:"array"`
281
elem *rtype // array element type
282
slice *rtype // slice type
289
286
// chanType represents a channel type.
290
287
type chanType struct {
291
commonType `reflect:"chan"`
292
elem *runtimeType // channel element type
293
dir uintptr // channel direction (ChanDir)
288
rtype `reflect:"chan"`
289
elem *rtype // channel element type
290
dir uintptr // channel direction (ChanDir)
296
293
// funcType represents a function type.
297
294
type funcType struct {
298
commonType `reflect:"func"`
299
dotdotdot bool // last input parameter is ...
300
in []*runtimeType // input parameter types
301
out []*runtimeType // output parameter types
295
rtype `reflect:"func"`
296
dotdotdot bool // last input parameter is ...
297
in []*rtype // input parameter types
298
out []*rtype // output parameter types
304
301
// imethod represents a method on an interface type
305
302
type imethod struct {
306
name *string // name of method
307
pkgPath *string // nil for exported Names; otherwise import path
308
typ *runtimeType // .(*FuncType) underneath
303
name *string // name of method
304
pkgPath *string // nil for exported Names; otherwise import path
305
typ *rtype // .(*FuncType) underneath
311
308
// interfaceType represents an interface type.
312
309
type interfaceType struct {
313
commonType `reflect:"interface"`
314
methods []imethod // sorted by hash
310
rtype `reflect:"interface"`
311
methods []imethod // sorted by hash
317
314
// mapType represents a map type.
318
315
type mapType struct {
319
commonType `reflect:"map"`
320
key *runtimeType // map key type
321
elem *runtimeType // map element (value) type
316
rtype `reflect:"map"`
317
key *rtype // map key type
318
elem *rtype // map element (value) type
324
321
// ptrType represents a pointer type.
325
322
type ptrType struct {
326
commonType `reflect:"ptr"`
327
elem *runtimeType // pointer element (pointed at) type
323
rtype `reflect:"ptr"`
324
elem *rtype // pointer element (pointed at) type
330
327
// sliceType represents a slice type.
331
328
type sliceType struct {
332
commonType `reflect:"slice"`
333
elem *runtimeType // slice element type
329
rtype `reflect:"slice"`
330
elem *rtype // slice element type
337
334
type structField struct {
338
name *string // nil for embedded fields
339
pkgPath *string // nil for exported Names; otherwise import path
340
typ *runtimeType // type of field
341
tag *string // nil if no tag
342
offset uintptr // byte offset of field within struct
335
name *string // nil for embedded fields
336
pkgPath *string // nil for exported Names; otherwise import path
337
typ *rtype // type of field
338
tag *string // nil if no tag
339
offset uintptr // byte offset of field within struct
345
342
// structType represents a struct type.
346
343
type structType struct {
347
commonType `reflect:"struct"`
348
fields []structField // sorted by offset
344
rtype `reflect:"struct"`
345
fields []structField // sorted by offset
348
// NOTE: These are copied from ../runtime/mgc0.h.
349
// They must be kept in sync.
352
368
* The compiler knows the exact layout of all the data structures above.
353
369
* The compiler does not know about the data structures and methods below.
839
const inf = 1 << 30 // infinity - no struct has that many nesting levels
841
func (t *structType) fieldByNameFunc(match func(string) bool, mark map[*structType]bool, depth int) (ff StructField, fd int) {
842
fd = inf // field depth
845
// Struct already seen.
850
var fi int // field index
851
n := 0 // number of matching fields at depth fd
853
for i := range t.fields {
858
// Matching top-level field.
862
if ft.Kind() == Ptr {
866
case match(ft.Name()):
867
// Matching anonymous top-level field.
870
// No top-level field yet; look inside nested structs.
871
if ft.Kind() == Struct {
872
st := (*structType)(unsafe.Pointer(ft.(*commonType)))
873
f, d = st.fieldByNameFunc(match, mark, depth+1)
880
// Found field at shallower depth.
884
// More than one matching field at the same depth (or d, fd == inf).
885
// Same as no field found at this depth.
888
// Impossible to find a field at lower depth.
895
// Found matching field.
896
if depth >= len(ff.Index) {
897
ff.Index = make([]int, depth+1)
899
if len(ff.Index) > 1 {
903
// None or more than one matching field found.
851
// A fieldScan represents an item on the fieldByNameFunc scan work list.
852
type fieldScan struct {
857
// FieldByNameFunc returns the struct field with a name that satisfies the
858
// match function and a boolean to indicate if the field was found.
859
func (t *structType) FieldByNameFunc(match func(string) bool) (result StructField, ok bool) {
860
// This uses the same condition that the Go language does: there must be a unique instance
861
// of the match at a given depth level. If there are multiple instances of a match at the
862
// same depth, they annihilate each other and inhibit any possible match at a lower level.
863
// The algorithm is breadth first search, one depth level at a time.
865
// The current and next slices are work queues:
866
// current lists the fields to visit on this depth level,
867
// and next lists the fields on the next lower level.
868
current := []fieldScan{}
869
next := []fieldScan{{typ: t}}
871
// nextCount records the number of times an embedded type has been
872
// encountered and considered for queueing in the 'next' slice.
873
// We only queue the first one, but we increment the count on each.
874
// If a struct type T can be reached more than once at a given depth level,
875
// then it annihilates itself and need not be considered at all when we
876
// process that next depth level.
877
var nextCount map[*structType]int
879
// visited records the structs that have been considered already.
880
// Embedded pointer fields can create cycles in the graph of
881
// reachable embedded types; visited avoids following those cycles.
882
// It also avoids duplicated effort: if we didn't find the field in an
883
// embedded type T at level 2, we won't find it in one at level 4 either.
884
visited := map[*structType]bool{}
887
current, next = next, current[:0]
891
// Process all the fields at this depth, now listed in 'current'.
892
// The loop queues embedded fields found in 'next', for processing during the next
893
// iteration. The multiplicity of the 'current' field counts is recorded
894
// in 'count'; the multiplicity of the 'next' field counts is recorded in 'nextCount'.
895
for _, scan := range current {
898
// We've looked through this type before, at a higher level.
899
// That higher level would shadow the lower level we're now at,
900
// so this one can't be useful to us. Ignore it.
904
for i := range t.fields {
906
// Find name and type for field f.
912
// Anonymous field of type T or *T.
913
// Name taken from type.
915
if ntyp.Kind() == Ptr {
916
ntyp = ntyp.Elem().common()
924
if count[t] > 1 || ok {
925
// Name appeared multiple times at this level: annihilate.
926
return StructField{}, false
930
result.Index = append(result.Index, scan.index...)
931
result.Index = append(result.Index, i)
936
// Queue embedded struct fields for processing with next level,
937
// but only if we haven't seen a match yet at this level and only
938
// if the embedded types haven't already been queued.
939
if ok || ntyp == nil || ntyp.Kind() != Struct {
942
styp := (*structType)(unsafe.Pointer(ntyp))
943
if nextCount[styp] > 0 {
944
nextCount[styp] = 2 // exact multiple doesn't matter
947
if nextCount == nil {
948
nextCount = map[*structType]int{}
952
nextCount[styp] = 2 // exact multiple doesn't matter
955
index = append(index, scan.index...)
956
index = append(index, i)
957
next = append(next, fieldScan{styp, index})
911
967
// FieldByName returns the struct field with the given name
912
968
// and a boolean to indicate if the field was found.
913
969
func (t *structType) FieldByName(name string) (f StructField, present bool) {
970
// Quick check for top-level name, or struct without anonymous fields.
973
for i := range t.fields {
979
if *tf.name == name {
980
return t.Field(i), true
914
987
return t.FieldByNameFunc(func(s string) bool { return s == name })
917
// FieldByNameFunc returns the struct field with a name that satisfies the
918
// match function and a boolean to indicate if the field was found.
919
func (t *structType) FieldByNameFunc(match func(string) bool) (f StructField, present bool) {
920
if ff, fd := t.fieldByNameFunc(match, make(map[*structType]bool), 0); fd < inf {
921
ff.Index = ff.Index[0 : fd+1]
922
f, present = ff, true
927
// Convert runtime type to reflect type.
928
func toCommonType(p *runtimeType) *commonType {
932
return (*p).(*commonType)
935
func toType(p *runtimeType) Type {
939
return (*p).(*commonType)
942
990
// TypeOf returns the reflection Type of the value in the interface{}.
943
991
// TypeOf(nil) returns nil.
944
992
func TypeOf(i interface{}) Type {
1017
1076
// Create a good hash for the new string by using
1018
1077
// the FNV-1 hash's mixing function to combine the
1019
1078
// old hash and the new "*".
1020
p.hash = ct.hash*16777619 ^ '*'
1079
p.hash = fnv1(t.hash, '*')
1022
1081
p.uncommonType = nil
1023
1082
p.ptrToThis = nil
1024
p.elem = (*runtimeType)(unsafe.Pointer(uintptr(unsafe.Pointer(ct)) - unsafe.Offsetof(rt.ptrType)))
1085
if t.kind&kindNoPointers != 0 {
1086
p.gc = unsafe.Pointer(&ptrDataGCProg)
1088
p.gc = unsafe.Pointer(&ptrGC{
1096
// INCORRECT. Uncomment to check that TestPtrToGC fails when p.gc is wrong.
1097
//p.gc = unsafe.Pointer(&badGC{width: p.size, end: _GC_END})
1027
1100
ptrMap.Unlock()
1028
return &p.commonType
1031
func (t *commonType) Implements(u Type) bool {
1104
// fnv1 incorporates the list of bytes into the hash x using the FNV-1 hash function.
1105
func fnv1(x uint32, list ...byte) uint32 {
1106
for _, b := range list {
1107
x = x*16777619 ^ uint32(b)
1112
func (t *rtype) Implements(u Type) bool {
1033
1114
panic("reflect: nil type passed to Type.Implements")
1035
1116
if u.Kind() != Interface {
1036
1117
panic("reflect: non-interface type passed to Type.Implements")
1038
return implements(u.(*commonType), t)
1119
return implements(u.(*rtype), t)
1041
func (t *commonType) AssignableTo(u Type) bool {
1122
func (t *rtype) AssignableTo(u Type) bool {
1043
1124
panic("reflect: nil type passed to Type.AssignableTo")
1045
uu := u.(*commonType)
1046
1127
return directlyAssignable(uu, t) || implements(uu, t)
1130
func (t *rtype) ConvertibleTo(u Type) bool {
1132
panic("reflect: nil type passed to Type.ConvertibleTo")
1135
return convertOp(uu, t) != nil
1049
1138
// implements returns true if the type V implements the interface type T.
1050
func implements(T, V *commonType) bool {
1139
func implements(T, V *rtype) bool {
1051
1140
if T.Kind() != Interface {
1310
// typelinks is implemented in package runtime.
1311
// It returns a slice of all the 'typelink' information in the binary,
1312
// which is to say a slice of known types, sorted by string.
1313
// Note that strings are not unique identifiers for types:
1314
// there can be more than one with a given string.
1315
// Only types we might want to look up are included:
1316
// channels, maps, slices, and arrays.
1317
func typelinks() []*rtype
1319
// typesByString returns the subslice of typelinks() whose elements have
1320
// the given string representation.
1321
// It may be empty (no known types with that string) or may have
1322
// multiple elements (multiple types with that string).
1323
func typesByString(s string) []*rtype {
1326
// We are looking for the first index i where the string becomes >= s.
1327
// This is a copy of sort.Search, with f(h) replaced by (*typ[h].string >= s).
1330
h := i + (j-i)/2 // avoid overflow when computing h
1332
if !(*typ[h].string >= s) {
1333
i = h + 1 // preserves f(i-1) == false
1335
j = h // preserves f(j) == true
1338
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
1340
// Having found the first, linear scan forward to find the last.
1341
// We could do a second binary search, but the caller is going
1342
// to do a linear scan anyway.
1344
for j < len(typ) && *typ[j].string == s {
1348
// This slice will be empty if the string is not found.
1352
// The lookupCache caches ChanOf, MapOf, and SliceOf lookups.
1353
var lookupCache struct {
1355
m map[cacheKey]*rtype
1358
// A cacheKey is the key for use in the lookupCache.
1359
// Four values describe any of the types we are looking for:
1360
// type kind, one or two subtypes, and an extra integer.
1361
type cacheKey struct {
1368
// cacheGet looks for a type under the key k in the lookupCache.
1369
// If it finds one, it returns that type.
1370
// If not, it returns nil with the cache locked.
1371
// The caller is expected to use cachePut to unlock the cache.
1372
func cacheGet(k cacheKey) Type {
1374
t := lookupCache.m[k]
1375
lookupCache.RUnlock()
1381
t = lookupCache.m[k]
1383
lookupCache.Unlock()
1387
if lookupCache.m == nil {
1388
lookupCache.m = make(map[cacheKey]*rtype)
1394
// cachePut stores the given type in the cache, unlocks the cache,
1395
// and returns the type. It is expected that the cache is locked
1396
// because cacheGet returned nil.
1397
func cachePut(k cacheKey, t *rtype) Type {
1398
lookupCache.m[k] = t
1399
lookupCache.Unlock()
1403
// garbage collection bytecode program for chan or map.
1404
// See ../../cmd/gc/reflect.c:/^dgcsym1 and :/^dgcsym.
1405
type chanMapGC struct {
1406
width uintptr // sizeof(map)
1407
op uintptr // _GC_MAP_PTR or _GC_CHAN_PTR
1409
typ *rtype // map type
1410
end uintptr // _GC_END
1418
// ChanOf returns the channel type with the given direction and element type.
1419
// For example, if t represents int, ChanOf(RecvDir, t) represents <-chan int.
1421
// The gc runtime imposes a limit of 64 kB on channel element types.
1422
// If t's size is equal to or exceeds this limit, ChanOf panics.
1423
func ChanOf(dir ChanDir, t Type) Type {
1427
ckey := cacheKey{Chan, typ, nil, uintptr(dir)}
1428
if ch := cacheGet(ckey); ch != nil {
1432
// This restriction is imposed by the gc compiler and the runtime.
1433
if typ.size >= 1<<16 {
1434
lookupCache.Unlock()
1435
panic("reflect.ChanOf: element size too large")
1438
// Look in known types.
1439
// TODO: Precedence when constructing string.
1443
lookupCache.Unlock()
1444
panic("reflect.ChanOf: invalid dir")
1446
s = "chan<- " + *typ.string
1448
s = "<-chan " + *typ.string
1450
s = "chan " + *typ.string
1452
for _, tt := range typesByString(s) {
1453
ch := (*chanType)(unsafe.Pointer(tt))
1454
if ch.elem == typ && ch.dir == uintptr(dir) {
1455
return cachePut(ckey, tt)
1459
// Make a channel type.
1460
var ichan interface{} = (chan unsafe.Pointer)(nil)
1461
prototype := *(**chanType)(unsafe.Pointer(&ichan))
1465
ch.hash = fnv1(typ.hash, 'c', byte(dir))
1467
ch.uncommonType = nil
1470
ch.gc = unsafe.Pointer(&chanMapGC{
1478
// INCORRECT. Uncomment to check that TestChanOfGC fails when ch.gc is wrong.
1479
//ch.gc = unsafe.Pointer(&badGC{width: ch.size, end: _GC_END})
1481
return cachePut(ckey, &ch.rtype)
1484
func ismapkey(*rtype) bool // implemented in runtime
1486
// MapOf returns the map type with the given key and element types.
1487
// For example, if k represents int and e represents string,
1488
// MapOf(k, e) represents map[int]string.
1490
// If the key type is not a valid map key type (that is, if it does
1491
// not implement Go's == operator), MapOf panics.
1492
func MapOf(key, elem Type) Type {
1493
ktyp := key.(*rtype)
1494
etyp := elem.(*rtype)
1496
if !ismapkey(ktyp) {
1497
panic("reflect.MapOf: invalid key type " + ktyp.String())
1501
ckey := cacheKey{Map, ktyp, etyp, 0}
1502
if mt := cacheGet(ckey); mt != nil {
1506
// Look in known types.
1507
s := "map[" + *ktyp.string + "]" + *etyp.string
1508
for _, tt := range typesByString(s) {
1509
mt := (*mapType)(unsafe.Pointer(tt))
1510
if mt.key == ktyp && mt.elem == etyp {
1511
return cachePut(ckey, tt)
1516
var imap interface{} = (map[unsafe.Pointer]unsafe.Pointer)(nil)
1517
prototype := *(**mapType)(unsafe.Pointer(&imap))
1521
mt.hash = fnv1(etyp.hash, 'm', byte(ktyp.hash>>24), byte(ktyp.hash>>16), byte(ktyp.hash>>8), byte(ktyp.hash))
1524
mt.uncommonType = nil
1527
mt.gc = unsafe.Pointer(&chanMapGC{
1535
// INCORRECT. Uncomment to check that TestMapOfGC and TestMapOfGCValues
1536
// fail when mt.gc is wrong.
1537
//mt.gc = unsafe.Pointer(&badGC{width: mt.size, end: _GC_END})
1539
return cachePut(ckey, &mt.rtype)
1542
// garbage collection bytecode program for slice of non-zero-length values.
1543
// See ../../cmd/gc/reflect.c:/^dgcsym1 and :/^dgcsym.
1544
type sliceGC struct {
1545
width uintptr // sizeof(slice)
1546
op uintptr // _GC_SLICE
1548
elemgc unsafe.Pointer // element gc program
1549
end uintptr // _GC_END
1552
// garbage collection bytecode program for slice of zero-length values.
1553
// See ../../cmd/gc/reflect.c:/^dgcsym1 and :/^dgcsym.
1554
type sliceEmptyGC struct {
1555
width uintptr // sizeof(slice)
1556
op uintptr // _GC_APTR
1558
end uintptr // _GC_END
1561
var sliceEmptyGCProg = sliceEmptyGC{
1562
width: unsafe.Sizeof([]byte(nil)),
1568
// SliceOf returns the slice type with element type t.
1569
// For example, if t represents int, SliceOf(t) represents []int.
1570
func SliceOf(t Type) Type {
1574
ckey := cacheKey{Slice, typ, nil, 0}
1575
if slice := cacheGet(ckey); slice != nil {
1579
// Look in known types.
1580
s := "[]" + *typ.string
1581
for _, tt := range typesByString(s) {
1582
slice := (*sliceType)(unsafe.Pointer(tt))
1583
if slice.elem == typ {
1584
return cachePut(ckey, tt)
1588
// Make a slice type.
1589
var islice interface{} = ([]unsafe.Pointer)(nil)
1590
prototype := *(**sliceType)(unsafe.Pointer(&islice))
1591
slice := new(sliceType)
1594
slice.hash = fnv1(typ.hash, '[')
1596
slice.uncommonType = nil
1597
slice.ptrToThis = nil
1600
slice.gc = unsafe.Pointer(&sliceEmptyGCProg)
1602
slice.gc = unsafe.Pointer(&sliceGC{
1611
// INCORRECT. Uncomment to check that TestSliceOfOfGC fails when slice.gc is wrong.
1612
//slice.gc = unsafe.Pointer(&badGC{width: slice.size, end: _GC_END})
1614
return cachePut(ckey, &slice.rtype)
1617
// ArrayOf returns the array type with the given count and element type.
1618
// For example, if t represents int, ArrayOf(5, t) represents [5]int.
1620
// If the resulting type would be larger than the available address space,
1623
// TODO(rsc): Unexported for now. Export once the alg field is set correctly
1624
// for the type. This may require significant work.
1625
func arrayOf(count int, elem Type) Type {
1626
typ := elem.(*rtype)
1627
slice := SliceOf(elem)
1630
ckey := cacheKey{Array, typ, nil, uintptr(count)}
1631
if slice := cacheGet(ckey); slice != nil {
1635
// Look in known types.
1636
s := "[" + strconv.Itoa(count) + "]" + *typ.string
1637
for _, tt := range typesByString(s) {
1638
slice := (*sliceType)(unsafe.Pointer(tt))
1639
if slice.elem == typ {
1640
return cachePut(ckey, tt)
1644
// Make an array type.
1645
var iarray interface{} = [1]unsafe.Pointer{}
1646
prototype := *(**arrayType)(unsafe.Pointer(&iarray))
1647
array := new(arrayType)
1650
array.hash = fnv1(typ.hash, '[')
1651
for n := uint32(count); n > 0; n >>= 8 {
1652
array.hash = fnv1(array.hash, byte(n))
1654
array.hash = fnv1(array.hash, ']')
1656
max := ^uintptr(0) / typ.size
1657
if uintptr(count) > max {
1658
panic("reflect.ArrayOf: array size would exceed virtual address space")
1660
array.size = typ.size * uintptr(count)
1661
array.align = typ.align
1662
array.fieldAlign = typ.fieldAlign
1665
array.uncommonType = nil
1666
array.ptrToThis = nil
1667
array.len = uintptr(count)
1668
array.slice = slice.(*rtype)
1670
return cachePut(ckey, &array.rtype)
1673
// toType converts from a *rtype to a Type that can be returned
1674
// to the client of package reflect. In gc, the only concern is that
1675
// a nil *rtype must be replaced by a nil Type, but in gccgo this
1676
// function takes care of ensuring that multiple *rtype for the same
1677
// type are coalesced into a single Type.
1678
func toType(t *rtype) Type {