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