1// Copyright (c) 2012-2015 Ugorji Nwoke. All rights reserved. 2// Use of this source code is governed by a MIT license found in the LICENSE file. 3 4package codec 5 6// Contains code shared by both encode and decode. 7 8// Some shared ideas around encoding/decoding 9// ------------------------------------------ 10// 11// If an interface{} is passed, we first do a type assertion to see if it is 12// a primitive type or a map/slice of primitive types, and use a fastpath to handle it. 13// 14// If we start with a reflect.Value, we are already in reflect.Value land and 15// will try to grab the function for the underlying Type and directly call that function. 16// This is more performant than calling reflect.Value.Interface(). 17// 18// This still helps us bypass many layers of reflection, and give best performance. 19// 20// Containers 21// ------------ 22// Containers in the stream are either associative arrays (key-value pairs) or 23// regular arrays (indexed by incrementing integers). 24// 25// Some streams support indefinite-length containers, and use a breaking 26// byte-sequence to denote that the container has come to an end. 27// 28// Some streams also are text-based, and use explicit separators to denote the 29// end/beginning of different values. 30// 31// During encode, we use a high-level condition to determine how to iterate through 32// the container. That decision is based on whether the container is text-based (with 33// separators) or binary (without separators). If binary, we do not even call the 34// encoding of separators. 35// 36// During decode, we use a different high-level condition to determine how to iterate 37// through the containers. That decision is based on whether the stream contained 38// a length prefix, or if it used explicit breaks. If length-prefixed, we assume that 39// it has to be binary, and we do not even try to read separators. 40// 41// The only codec that may suffer (slightly) is cbor, and only when decoding indefinite-length. 42// It may suffer because we treat it like a text-based codec, and read separators. 43// However, this read is a no-op and the cost is insignificant. 44// 45// Philosophy 46// ------------ 47// On decode, this codec will update containers appropriately: 48// - If struct, update fields from stream into fields of struct. 49// If field in stream not found in struct, handle appropriately (based on option). 50// If a struct field has no corresponding value in the stream, leave it AS IS. 51// If nil in stream, set value to nil/zero value. 52// - If map, update map from stream. 53// If the stream value is NIL, set the map to nil. 54// - if slice, try to update up to length of array in stream. 55// if container len is less than stream array length, 56// and container cannot be expanded, handled (based on option). 57// This means you can decode 4-element stream array into 1-element array. 58// 59// ------------------------------------ 60// On encode, user can specify omitEmpty. This means that the value will be omitted 61// if the zero value. The problem may occur during decode, where omitted values do not affect 62// the value being decoded into. This means that if decoding into a struct with an 63// int field with current value=5, and the field is omitted in the stream, then after 64// decoding, the value will still be 5 (not 0). 65// omitEmpty only works if you guarantee that you always decode into zero-values. 66// 67// ------------------------------------ 68// We could have truncated a map to remove keys not available in the stream, 69// or set values in the struct which are not in the stream to their zero values. 70// We decided against it because there is no efficient way to do it. 71// We may introduce it as an option later. 72// However, that will require enabling it for both runtime and code generation modes. 73// 74// To support truncate, we need to do 2 passes over the container: 75// map 76// - first collect all keys (e.g. in k1) 77// - for each key in stream, mark k1 that the key should not be removed 78// - after updating map, do second pass and call delete for all keys in k1 which are not marked 79// struct: 80// - for each field, track the *typeInfo s1 81// - iterate through all s1, and for each one not marked, set value to zero 82// - this involves checking the possible anonymous fields which are nil ptrs. 83// too much work. 84// 85// ------------------------------------------ 86// Error Handling is done within the library using panic. 87// 88// This way, the code doesn't have to keep checking if an error has happened, 89// and we don't have to keep sending the error value along with each call 90// or storing it in the En|Decoder and checking it constantly along the way. 91// 92// The disadvantage is that small functions which use panics cannot be inlined. 93// The code accounts for that by only using panics behind an interface; 94// since interface calls cannot be inlined, this is irrelevant. 95// 96// We considered storing the error is En|Decoder. 97// - once it has its err field set, it cannot be used again. 98// - panicing will be optional, controlled by const flag. 99// - code should always check error first and return early. 100// We eventually decided against it as it makes the code clumsier to always 101// check for these error conditions. 102 103import ( 104 "bytes" 105 "encoding" 106 "encoding/binary" 107 "errors" 108 "fmt" 109 "math" 110 "reflect" 111 "sort" 112 "strings" 113 "sync" 114 "time" 115) 116 117const ( 118 scratchByteArrayLen = 32 119 initCollectionCap = 32 // 32 is defensive. 16 is preferred. 120 121 // Support encoding.(Binary|Text)(Unm|M)arshaler. 122 // This constant flag will enable or disable it. 123 supportMarshalInterfaces = true 124 125 // Each Encoder or Decoder uses a cache of functions based on conditionals, 126 // so that the conditionals are not run every time. 127 // 128 // Either a map or a slice is used to keep track of the functions. 129 // The map is more natural, but has a higher cost than a slice/array. 130 // This flag (useMapForCodecCache) controls which is used. 131 // 132 // From benchmarks, slices with linear search perform better with < 32 entries. 133 // We have typically seen a high threshold of about 24 entries. 134 useMapForCodecCache = false 135 136 // for debugging, set this to false, to catch panic traces. 137 // Note that this will always cause rpc tests to fail, since they need io.EOF sent via panic. 138 recoverPanicToErr = true 139 140 // Fast path functions try to create a fast path encode or decode implementation 141 // for common maps and slices, by by-passing reflection altogether. 142 fastpathEnabled = true 143 144 // if checkStructForEmptyValue, check structs fields to see if an empty value. 145 // This could be an expensive call, so possibly disable it. 146 checkStructForEmptyValue = false 147 148 // if derefForIsEmptyValue, deref pointers and interfaces when checking isEmptyValue 149 derefForIsEmptyValue = false 150 151 // if resetSliceElemToZeroValue, then on decoding a slice, reset the element to a zero value first. 152 // Only concern is that, if the slice already contained some garbage, we will decode into that garbage. 153 // The chances of this are slim, so leave this "optimization". 154 // TODO: should this be true, to ensure that we always decode into a "zero" "empty" value? 155 resetSliceElemToZeroValue bool = false 156) 157 158var ( 159 oneByteArr = [1]byte{0} 160 zeroByteSlice = oneByteArr[:0:0] 161) 162 163type charEncoding uint8 164 165const ( 166 c_RAW charEncoding = iota 167 c_UTF8 168 c_UTF16LE 169 c_UTF16BE 170 c_UTF32LE 171 c_UTF32BE 172) 173 174// valueType is the stream type 175type valueType uint8 176 177const ( 178 valueTypeUnset valueType = iota 179 valueTypeNil 180 valueTypeInt 181 valueTypeUint 182 valueTypeFloat 183 valueTypeBool 184 valueTypeString 185 valueTypeSymbol 186 valueTypeBytes 187 valueTypeMap 188 valueTypeArray 189 valueTypeTimestamp 190 valueTypeExt 191 192 // valueTypeInvalid = 0xff 193) 194 195type seqType uint8 196 197const ( 198 _ seqType = iota 199 seqTypeArray 200 seqTypeSlice 201 seqTypeChan 202) 203 204// note that containerMapStart and containerArraySend are not sent. 205// This is because the ReadXXXStart and EncodeXXXStart already does these. 206type containerState uint8 207 208const ( 209 _ containerState = iota 210 211 containerMapStart // slot left open, since Driver method already covers it 212 containerMapKey 213 containerMapValue 214 containerMapEnd 215 containerArrayStart // slot left open, since Driver methods already cover it 216 containerArrayElem 217 containerArrayEnd 218) 219 220type rgetPoolT struct { 221 encNames [8]string 222 fNames [8]string 223 etypes [8]uintptr 224 sfis [8]*structFieldInfo 225} 226 227var rgetPool = sync.Pool{ 228 New: func() interface{} { return new(rgetPoolT) }, 229} 230 231type rgetT struct { 232 fNames []string 233 encNames []string 234 etypes []uintptr 235 sfis []*structFieldInfo 236} 237 238type containerStateRecv interface { 239 sendContainerState(containerState) 240} 241 242// mirror json.Marshaler and json.Unmarshaler here, 243// so we don't import the encoding/json package 244type jsonMarshaler interface { 245 MarshalJSON() ([]byte, error) 246} 247type jsonUnmarshaler interface { 248 UnmarshalJSON([]byte) error 249} 250 251var ( 252 bigen = binary.BigEndian 253 structInfoFieldName = "_struct" 254 255 mapStrIntfTyp = reflect.TypeOf(map[string]interface{}(nil)) 256 mapIntfIntfTyp = reflect.TypeOf(map[interface{}]interface{}(nil)) 257 intfSliceTyp = reflect.TypeOf([]interface{}(nil)) 258 intfTyp = intfSliceTyp.Elem() 259 260 stringTyp = reflect.TypeOf("") 261 timeTyp = reflect.TypeOf(time.Time{}) 262 rawExtTyp = reflect.TypeOf(RawExt{}) 263 uint8SliceTyp = reflect.TypeOf([]uint8(nil)) 264 265 mapBySliceTyp = reflect.TypeOf((*MapBySlice)(nil)).Elem() 266 267 binaryMarshalerTyp = reflect.TypeOf((*encoding.BinaryMarshaler)(nil)).Elem() 268 binaryUnmarshalerTyp = reflect.TypeOf((*encoding.BinaryUnmarshaler)(nil)).Elem() 269 270 textMarshalerTyp = reflect.TypeOf((*encoding.TextMarshaler)(nil)).Elem() 271 textUnmarshalerTyp = reflect.TypeOf((*encoding.TextUnmarshaler)(nil)).Elem() 272 273 jsonMarshalerTyp = reflect.TypeOf((*jsonMarshaler)(nil)).Elem() 274 jsonUnmarshalerTyp = reflect.TypeOf((*jsonUnmarshaler)(nil)).Elem() 275 276 selferTyp = reflect.TypeOf((*Selfer)(nil)).Elem() 277 278 uint8SliceTypId = reflect.ValueOf(uint8SliceTyp).Pointer() 279 rawExtTypId = reflect.ValueOf(rawExtTyp).Pointer() 280 intfTypId = reflect.ValueOf(intfTyp).Pointer() 281 timeTypId = reflect.ValueOf(timeTyp).Pointer() 282 stringTypId = reflect.ValueOf(stringTyp).Pointer() 283 284 mapStrIntfTypId = reflect.ValueOf(mapStrIntfTyp).Pointer() 285 mapIntfIntfTypId = reflect.ValueOf(mapIntfIntfTyp).Pointer() 286 intfSliceTypId = reflect.ValueOf(intfSliceTyp).Pointer() 287 // mapBySliceTypId = reflect.ValueOf(mapBySliceTyp).Pointer() 288 289 intBitsize uint8 = uint8(reflect.TypeOf(int(0)).Bits()) 290 uintBitsize uint8 = uint8(reflect.TypeOf(uint(0)).Bits()) 291 292 bsAll0x00 = []byte{0, 0, 0, 0, 0, 0, 0, 0} 293 bsAll0xff = []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff} 294 295 chkOvf checkOverflow 296 297 noFieldNameToStructFieldInfoErr = errors.New("no field name passed to parseStructFieldInfo") 298) 299 300var defTypeInfos = NewTypeInfos([]string{"codec", "json"}) 301 302// Selfer defines methods by which a value can encode or decode itself. 303// 304// Any type which implements Selfer will be able to encode or decode itself. 305// Consequently, during (en|de)code, this takes precedence over 306// (text|binary)(M|Unm)arshal or extension support. 307type Selfer interface { 308 CodecEncodeSelf(*Encoder) 309 CodecDecodeSelf(*Decoder) 310} 311 312// MapBySlice represents a slice which should be encoded as a map in the stream. 313// The slice contains a sequence of key-value pairs. 314// This affords storing a map in a specific sequence in the stream. 315// 316// The support of MapBySlice affords the following: 317// - A slice type which implements MapBySlice will be encoded as a map 318// - A slice can be decoded from a map in the stream 319type MapBySlice interface { 320 MapBySlice() 321} 322 323// WARNING: DO NOT USE DIRECTLY. EXPORTED FOR GODOC BENEFIT. WILL BE REMOVED. 324// 325// BasicHandle encapsulates the common options and extension functions. 326type BasicHandle struct { 327 // TypeInfos is used to get the type info for any type. 328 // 329 // If not configured, the default TypeInfos is used, which uses struct tag keys: codec, json 330 TypeInfos *TypeInfos 331 332 extHandle 333 EncodeOptions 334 DecodeOptions 335} 336 337func (x *BasicHandle) getBasicHandle() *BasicHandle { 338 return x 339} 340 341func (x *BasicHandle) getTypeInfo(rtid uintptr, rt reflect.Type) (pti *typeInfo) { 342 if x.TypeInfos != nil { 343 return x.TypeInfos.get(rtid, rt) 344 } 345 return defTypeInfos.get(rtid, rt) 346} 347 348// Handle is the interface for a specific encoding format. 349// 350// Typically, a Handle is pre-configured before first time use, 351// and not modified while in use. Such a pre-configured Handle 352// is safe for concurrent access. 353type Handle interface { 354 getBasicHandle() *BasicHandle 355 newEncDriver(w *Encoder) encDriver 356 newDecDriver(r *Decoder) decDriver 357 isBinary() bool 358} 359 360// RawExt represents raw unprocessed extension data. 361// Some codecs will decode extension data as a *RawExt if there is no registered extension for the tag. 362// 363// Only one of Data or Value is nil. If Data is nil, then the content of the RawExt is in the Value. 364type RawExt struct { 365 Tag uint64 366 // Data is the []byte which represents the raw ext. If Data is nil, ext is exposed in Value. 367 // Data is used by codecs (e.g. binc, msgpack, simple) which do custom serialization of the types 368 Data []byte 369 // Value represents the extension, if Data is nil. 370 // Value is used by codecs (e.g. cbor) which use the format to do custom serialization of the types. 371 Value interface{} 372} 373 374// BytesExt handles custom (de)serialization of types to/from []byte. 375// It is used by codecs (e.g. binc, msgpack, simple) which do custom serialization of the types. 376type BytesExt interface { 377 // WriteExt converts a value to a []byte. 378 // 379 // Note: v *may* be a pointer to the extension type, if the extension type was a struct or array. 380 WriteExt(v interface{}) []byte 381 382 // ReadExt updates a value from a []byte. 383 ReadExt(dst interface{}, src []byte) 384} 385 386// InterfaceExt handles custom (de)serialization of types to/from another interface{} value. 387// The Encoder or Decoder will then handle the further (de)serialization of that known type. 388// 389// It is used by codecs (e.g. cbor, json) which use the format to do custom serialization of the types. 390type InterfaceExt interface { 391 // ConvertExt converts a value into a simpler interface for easy encoding e.g. convert time.Time to int64. 392 // 393 // Note: v *may* be a pointer to the extension type, if the extension type was a struct or array. 394 ConvertExt(v interface{}) interface{} 395 396 // UpdateExt updates a value from a simpler interface for easy decoding e.g. convert int64 to time.Time. 397 UpdateExt(dst interface{}, src interface{}) 398} 399 400// Ext handles custom (de)serialization of custom types / extensions. 401type Ext interface { 402 BytesExt 403 InterfaceExt 404} 405 406// addExtWrapper is a wrapper implementation to support former AddExt exported method. 407type addExtWrapper struct { 408 encFn func(reflect.Value) ([]byte, error) 409 decFn func(reflect.Value, []byte) error 410} 411 412func (x addExtWrapper) WriteExt(v interface{}) []byte { 413 bs, err := x.encFn(reflect.ValueOf(v)) 414 if err != nil { 415 panic(err) 416 } 417 return bs 418} 419 420func (x addExtWrapper) ReadExt(v interface{}, bs []byte) { 421 if err := x.decFn(reflect.ValueOf(v), bs); err != nil { 422 panic(err) 423 } 424} 425 426func (x addExtWrapper) ConvertExt(v interface{}) interface{} { 427 return x.WriteExt(v) 428} 429 430func (x addExtWrapper) UpdateExt(dest interface{}, v interface{}) { 431 x.ReadExt(dest, v.([]byte)) 432} 433 434type setExtWrapper struct { 435 b BytesExt 436 i InterfaceExt 437} 438 439func (x *setExtWrapper) WriteExt(v interface{}) []byte { 440 if x.b == nil { 441 panic("BytesExt.WriteExt is not supported") 442 } 443 return x.b.WriteExt(v) 444} 445 446func (x *setExtWrapper) ReadExt(v interface{}, bs []byte) { 447 if x.b == nil { 448 panic("BytesExt.WriteExt is not supported") 449 450 } 451 x.b.ReadExt(v, bs) 452} 453 454func (x *setExtWrapper) ConvertExt(v interface{}) interface{} { 455 if x.i == nil { 456 panic("InterfaceExt.ConvertExt is not supported") 457 458 } 459 return x.i.ConvertExt(v) 460} 461 462func (x *setExtWrapper) UpdateExt(dest interface{}, v interface{}) { 463 if x.i == nil { 464 panic("InterfaceExxt.UpdateExt is not supported") 465 466 } 467 x.i.UpdateExt(dest, v) 468} 469 470// type errorString string 471// func (x errorString) Error() string { return string(x) } 472 473type binaryEncodingType struct{} 474 475func (_ binaryEncodingType) isBinary() bool { return true } 476 477type textEncodingType struct{} 478 479func (_ textEncodingType) isBinary() bool { return false } 480 481// noBuiltInTypes is embedded into many types which do not support builtins 482// e.g. msgpack, simple, cbor. 483type noBuiltInTypes struct{} 484 485func (_ noBuiltInTypes) IsBuiltinType(rt uintptr) bool { return false } 486func (_ noBuiltInTypes) EncodeBuiltin(rt uintptr, v interface{}) {} 487func (_ noBuiltInTypes) DecodeBuiltin(rt uintptr, v interface{}) {} 488 489type noStreamingCodec struct{} 490 491func (_ noStreamingCodec) CheckBreak() bool { return false } 492 493// bigenHelper. 494// Users must already slice the x completely, because we will not reslice. 495type bigenHelper struct { 496 x []byte // must be correctly sliced to appropriate len. slicing is a cost. 497 w encWriter 498} 499 500func (z bigenHelper) writeUint16(v uint16) { 501 bigen.PutUint16(z.x, v) 502 z.w.writeb(z.x) 503} 504 505func (z bigenHelper) writeUint32(v uint32) { 506 bigen.PutUint32(z.x, v) 507 z.w.writeb(z.x) 508} 509 510func (z bigenHelper) writeUint64(v uint64) { 511 bigen.PutUint64(z.x, v) 512 z.w.writeb(z.x) 513} 514 515type extTypeTagFn struct { 516 rtid uintptr 517 rt reflect.Type 518 tag uint64 519 ext Ext 520} 521 522type extHandle []extTypeTagFn 523 524// DEPRECATED: Use SetBytesExt or SetInterfaceExt on the Handle instead. 525// 526// AddExt registes an encode and decode function for a reflect.Type. 527// AddExt internally calls SetExt. 528// To deregister an Ext, call AddExt with nil encfn and/or nil decfn. 529func (o *extHandle) AddExt( 530 rt reflect.Type, tag byte, 531 encfn func(reflect.Value) ([]byte, error), decfn func(reflect.Value, []byte) error, 532) (err error) { 533 if encfn == nil || decfn == nil { 534 return o.SetExt(rt, uint64(tag), nil) 535 } 536 return o.SetExt(rt, uint64(tag), addExtWrapper{encfn, decfn}) 537} 538 539// DEPRECATED: Use SetBytesExt or SetInterfaceExt on the Handle instead. 540// 541// Note that the type must be a named type, and specifically not 542// a pointer or Interface. An error is returned if that is not honored. 543// 544// To Deregister an ext, call SetExt with nil Ext 545func (o *extHandle) SetExt(rt reflect.Type, tag uint64, ext Ext) (err error) { 546 // o is a pointer, because we may need to initialize it 547 if rt.PkgPath() == "" || rt.Kind() == reflect.Interface { 548 err = fmt.Errorf("codec.Handle.AddExt: Takes named type, especially not a pointer or interface: %T", 549 reflect.Zero(rt).Interface()) 550 return 551 } 552 553 rtid := reflect.ValueOf(rt).Pointer() 554 for _, v := range *o { 555 if v.rtid == rtid { 556 v.tag, v.ext = tag, ext 557 return 558 } 559 } 560 561 if *o == nil { 562 *o = make([]extTypeTagFn, 0, 4) 563 } 564 *o = append(*o, extTypeTagFn{rtid, rt, tag, ext}) 565 return 566} 567 568func (o extHandle) getExt(rtid uintptr) *extTypeTagFn { 569 var v *extTypeTagFn 570 for i := range o { 571 v = &o[i] 572 if v.rtid == rtid { 573 return v 574 } 575 } 576 return nil 577} 578 579func (o extHandle) getExtForTag(tag uint64) *extTypeTagFn { 580 var v *extTypeTagFn 581 for i := range o { 582 v = &o[i] 583 if v.tag == tag { 584 return v 585 } 586 } 587 return nil 588} 589 590type structFieldInfo struct { 591 encName string // encode name 592 593 // only one of 'i' or 'is' can be set. If 'i' is -1, then 'is' has been set. 594 595 is []int // (recursive/embedded) field index in struct 596 i int16 // field index in struct 597 omitEmpty bool 598 toArray bool // if field is _struct, is the toArray set? 599} 600 601// func (si *structFieldInfo) isZero() bool { 602// return si.encName == "" && len(si.is) == 0 && si.i == 0 && !si.omitEmpty && !si.toArray 603// } 604 605// rv returns the field of the struct. 606// If anonymous, it returns an Invalid 607func (si *structFieldInfo) field(v reflect.Value, update bool) (rv2 reflect.Value) { 608 if si.i != -1 { 609 v = v.Field(int(si.i)) 610 return v 611 } 612 // replicate FieldByIndex 613 for _, x := range si.is { 614 for v.Kind() == reflect.Ptr { 615 if v.IsNil() { 616 if !update { 617 return 618 } 619 v.Set(reflect.New(v.Type().Elem())) 620 } 621 v = v.Elem() 622 } 623 v = v.Field(x) 624 } 625 return v 626} 627 628func (si *structFieldInfo) setToZeroValue(v reflect.Value) { 629 if si.i != -1 { 630 v = v.Field(int(si.i)) 631 v.Set(reflect.Zero(v.Type())) 632 // v.Set(reflect.New(v.Type()).Elem()) 633 // v.Set(reflect.New(v.Type())) 634 } else { 635 // replicate FieldByIndex 636 for _, x := range si.is { 637 for v.Kind() == reflect.Ptr { 638 if v.IsNil() { 639 return 640 } 641 v = v.Elem() 642 } 643 v = v.Field(x) 644 } 645 v.Set(reflect.Zero(v.Type())) 646 } 647} 648 649func parseStructFieldInfo(fname string, stag string) *structFieldInfo { 650 // if fname == "" { 651 // panic(noFieldNameToStructFieldInfoErr) 652 // } 653 si := structFieldInfo{ 654 encName: fname, 655 } 656 657 if stag != "" { 658 for i, s := range strings.Split(stag, ",") { 659 if i == 0 { 660 if s != "" { 661 si.encName = s 662 } 663 } else { 664 if s == "omitempty" { 665 si.omitEmpty = true 666 } else if s == "toarray" { 667 si.toArray = true 668 } 669 } 670 } 671 } 672 // si.encNameBs = []byte(si.encName) 673 return &si 674} 675 676type sfiSortedByEncName []*structFieldInfo 677 678func (p sfiSortedByEncName) Len() int { 679 return len(p) 680} 681 682func (p sfiSortedByEncName) Less(i, j int) bool { 683 return p[i].encName < p[j].encName 684} 685 686func (p sfiSortedByEncName) Swap(i, j int) { 687 p[i], p[j] = p[j], p[i] 688} 689 690// typeInfo keeps information about each type referenced in the encode/decode sequence. 691// 692// During an encode/decode sequence, we work as below: 693// - If base is a built in type, en/decode base value 694// - If base is registered as an extension, en/decode base value 695// - If type is binary(M/Unm)arshaler, call Binary(M/Unm)arshal method 696// - If type is text(M/Unm)arshaler, call Text(M/Unm)arshal method 697// - Else decode appropriately based on the reflect.Kind 698type typeInfo struct { 699 sfi []*structFieldInfo // sorted. Used when enc/dec struct to map. 700 sfip []*structFieldInfo // unsorted. Used when enc/dec struct to array. 701 702 rt reflect.Type 703 rtid uintptr 704 705 numMeth uint16 // number of methods 706 707 // baseId gives pointer to the base reflect.Type, after deferencing 708 // the pointers. E.g. base type of ***time.Time is time.Time. 709 base reflect.Type 710 baseId uintptr 711 baseIndir int8 // number of indirections to get to base 712 713 mbs bool // base type (T or *T) is a MapBySlice 714 715 bm bool // base type (T or *T) is a binaryMarshaler 716 bunm bool // base type (T or *T) is a binaryUnmarshaler 717 bmIndir int8 // number of indirections to get to binaryMarshaler type 718 bunmIndir int8 // number of indirections to get to binaryUnmarshaler type 719 720 tm bool // base type (T or *T) is a textMarshaler 721 tunm bool // base type (T or *T) is a textUnmarshaler 722 tmIndir int8 // number of indirections to get to textMarshaler type 723 tunmIndir int8 // number of indirections to get to textUnmarshaler type 724 725 jm bool // base type (T or *T) is a jsonMarshaler 726 junm bool // base type (T or *T) is a jsonUnmarshaler 727 jmIndir int8 // number of indirections to get to jsonMarshaler type 728 junmIndir int8 // number of indirections to get to jsonUnmarshaler type 729 730 cs bool // base type (T or *T) is a Selfer 731 csIndir int8 // number of indirections to get to Selfer type 732 733 toArray bool // whether this (struct) type should be encoded as an array 734} 735 736func (ti *typeInfo) indexForEncName(name string) int { 737 //tisfi := ti.sfi 738 const binarySearchThreshold = 16 739 if sfilen := len(ti.sfi); sfilen < binarySearchThreshold { 740 // linear search. faster than binary search in my testing up to 16-field structs. 741 for i, si := range ti.sfi { 742 if si.encName == name { 743 return i 744 } 745 } 746 } else { 747 // binary search. adapted from sort/search.go. 748 h, i, j := 0, 0, sfilen 749 for i < j { 750 h = i + (j-i)/2 751 if ti.sfi[h].encName < name { 752 i = h + 1 753 } else { 754 j = h 755 } 756 } 757 if i < sfilen && ti.sfi[i].encName == name { 758 return i 759 } 760 } 761 return -1 762} 763 764// TypeInfos caches typeInfo for each type on first inspection. 765// 766// It is configured with a set of tag keys, which are used to get 767// configuration for the type. 768type TypeInfos struct { 769 infos map[uintptr]*typeInfo 770 mu sync.RWMutex 771 tags []string 772} 773 774// NewTypeInfos creates a TypeInfos given a set of struct tags keys. 775// 776// This allows users customize the struct tag keys which contain configuration 777// of their types. 778func NewTypeInfos(tags []string) *TypeInfos { 779 return &TypeInfos{tags: tags, infos: make(map[uintptr]*typeInfo, 64)} 780} 781 782func (x *TypeInfos) structTag(t reflect.StructTag) (s string) { 783 // check for tags: codec, json, in that order. 784 // this allows seamless support for many configured structs. 785 for _, x := range x.tags { 786 s = t.Get(x) 787 if s != "" { 788 return s 789 } 790 } 791 return 792} 793 794func (x *TypeInfos) get(rtid uintptr, rt reflect.Type) (pti *typeInfo) { 795 var ok bool 796 x.mu.RLock() 797 pti, ok = x.infos[rtid] 798 x.mu.RUnlock() 799 if ok { 800 return 801 } 802 803 // do not hold lock while computing this. 804 // it may lead to duplication, but that's ok. 805 ti := typeInfo{rt: rt, rtid: rtid} 806 ti.numMeth = uint16(rt.NumMethod()) 807 808 var indir int8 809 if ok, indir = implementsIntf(rt, binaryMarshalerTyp); ok { 810 ti.bm, ti.bmIndir = true, indir 811 } 812 if ok, indir = implementsIntf(rt, binaryUnmarshalerTyp); ok { 813 ti.bunm, ti.bunmIndir = true, indir 814 } 815 if ok, indir = implementsIntf(rt, textMarshalerTyp); ok { 816 ti.tm, ti.tmIndir = true, indir 817 } 818 if ok, indir = implementsIntf(rt, textUnmarshalerTyp); ok { 819 ti.tunm, ti.tunmIndir = true, indir 820 } 821 if ok, indir = implementsIntf(rt, jsonMarshalerTyp); ok { 822 ti.jm, ti.jmIndir = true, indir 823 } 824 if ok, indir = implementsIntf(rt, jsonUnmarshalerTyp); ok { 825 ti.junm, ti.junmIndir = true, indir 826 } 827 if ok, indir = implementsIntf(rt, selferTyp); ok { 828 ti.cs, ti.csIndir = true, indir 829 } 830 if ok, _ = implementsIntf(rt, mapBySliceTyp); ok { 831 ti.mbs = true 832 } 833 834 pt := rt 835 var ptIndir int8 836 // for ; pt.Kind() == reflect.Ptr; pt, ptIndir = pt.Elem(), ptIndir+1 { } 837 for pt.Kind() == reflect.Ptr { 838 pt = pt.Elem() 839 ptIndir++ 840 } 841 if ptIndir == 0 { 842 ti.base = rt 843 ti.baseId = rtid 844 } else { 845 ti.base = pt 846 ti.baseId = reflect.ValueOf(pt).Pointer() 847 ti.baseIndir = ptIndir 848 } 849 850 if rt.Kind() == reflect.Struct { 851 var siInfo *structFieldInfo 852 if f, ok := rt.FieldByName(structInfoFieldName); ok { 853 siInfo = parseStructFieldInfo(structInfoFieldName, x.structTag(f.Tag)) 854 ti.toArray = siInfo.toArray 855 } 856 pi := rgetPool.Get() 857 pv := pi.(*rgetPoolT) 858 pv.etypes[0] = ti.baseId 859 vv := rgetT{pv.fNames[:0], pv.encNames[:0], pv.etypes[:1], pv.sfis[:0]} 860 x.rget(rt, rtid, nil, &vv, siInfo) 861 ti.sfip = make([]*structFieldInfo, len(vv.sfis)) 862 ti.sfi = make([]*structFieldInfo, len(vv.sfis)) 863 copy(ti.sfip, vv.sfis) 864 sort.Sort(sfiSortedByEncName(vv.sfis)) 865 copy(ti.sfi, vv.sfis) 866 rgetPool.Put(pi) 867 } 868 // sfi = sfip 869 870 x.mu.Lock() 871 if pti, ok = x.infos[rtid]; !ok { 872 pti = &ti 873 x.infos[rtid] = pti 874 } 875 x.mu.Unlock() 876 return 877} 878 879func (x *TypeInfos) rget(rt reflect.Type, rtid uintptr, 880 indexstack []int, pv *rgetT, siInfo *structFieldInfo, 881) { 882 // This will read up the fields and store how to access the value. 883 // It uses the go language's rules for embedding, as below: 884 // - if a field has been seen while traversing, skip it 885 // - if an encName has been seen while traversing, skip it 886 // - if an embedded type has been seen, skip it 887 // 888 // Also, per Go's rules, embedded fields must be analyzed AFTER all top-level fields. 889 // 890 // Note: we consciously use slices, not a map, to simulate a set. 891 // Typically, types have < 16 fields, and iteration using equals is faster than maps there 892 893 type anonField struct { 894 ft reflect.Type 895 idx int 896 } 897 898 var anonFields []anonField 899 900LOOP: 901 for j, jlen := 0, rt.NumField(); j < jlen; j++ { 902 f := rt.Field(j) 903 fkind := f.Type.Kind() 904 // skip if a func type, or is unexported, or structTag value == "-" 905 switch fkind { 906 case reflect.Func, reflect.Complex64, reflect.Complex128, reflect.UnsafePointer: 907 continue LOOP 908 } 909 910 // if r1, _ := utf8.DecodeRuneInString(f.Name); r1 == utf8.RuneError || !unicode.IsUpper(r1) { 911 if f.PkgPath != "" && !f.Anonymous { // unexported, not embedded 912 continue 913 } 914 stag := x.structTag(f.Tag) 915 if stag == "-" { 916 continue 917 } 918 var si *structFieldInfo 919 // if anonymous and no struct tag (or it's blank), and a struct (or pointer to struct), inline it. 920 if f.Anonymous && fkind != reflect.Interface { 921 doInline := stag == "" 922 if !doInline { 923 si = parseStructFieldInfo("", stag) 924 doInline = si.encName == "" 925 // doInline = si.isZero() 926 } 927 if doInline { 928 ft := f.Type 929 for ft.Kind() == reflect.Ptr { 930 ft = ft.Elem() 931 } 932 if ft.Kind() == reflect.Struct { 933 // handle anonymous fields after handling all the non-anon fields 934 anonFields = append(anonFields, anonField{ft, j}) 935 continue 936 } 937 } 938 } 939 940 // after the anonymous dance: if an unexported field, skip 941 if f.PkgPath != "" { // unexported 942 continue 943 } 944 945 if f.Name == "" { 946 panic(noFieldNameToStructFieldInfoErr) 947 } 948 949 for _, k := range pv.fNames { 950 if k == f.Name { 951 continue LOOP 952 } 953 } 954 pv.fNames = append(pv.fNames, f.Name) 955 956 if si == nil { 957 si = parseStructFieldInfo(f.Name, stag) 958 } else if si.encName == "" { 959 si.encName = f.Name 960 } 961 962 for _, k := range pv.encNames { 963 if k == si.encName { 964 continue LOOP 965 } 966 } 967 pv.encNames = append(pv.encNames, si.encName) 968 969 // si.ikind = int(f.Type.Kind()) 970 if len(indexstack) == 0 { 971 si.i = int16(j) 972 } else { 973 si.i = -1 974 si.is = make([]int, len(indexstack)+1) 975 copy(si.is, indexstack) 976 si.is[len(indexstack)] = j 977 // si.is = append(append(make([]int, 0, len(indexstack)+4), indexstack...), j) 978 } 979 980 if siInfo != nil { 981 if siInfo.omitEmpty { 982 si.omitEmpty = true 983 } 984 } 985 pv.sfis = append(pv.sfis, si) 986 } 987 988 // now handle anonymous fields 989LOOP2: 990 for _, af := range anonFields { 991 // if etypes contains this, then do not call rget again (as the fields are already seen here) 992 ftid := reflect.ValueOf(af.ft).Pointer() 993 for _, k := range pv.etypes { 994 if k == ftid { 995 continue LOOP2 996 } 997 } 998 pv.etypes = append(pv.etypes, ftid) 999 1000 indexstack2 := make([]int, len(indexstack)+1) 1001 copy(indexstack2, indexstack) 1002 indexstack2[len(indexstack)] = af.idx 1003 // indexstack2 := append(append(make([]int, 0, len(indexstack)+4), indexstack...), j) 1004 x.rget(af.ft, ftid, indexstack2, pv, siInfo) 1005 } 1006} 1007 1008func panicToErr(err *error) { 1009 if recoverPanicToErr { 1010 if x := recover(); x != nil { 1011 //debug.PrintStack() 1012 panicValToErr(x, err) 1013 } 1014 } 1015} 1016 1017// func doPanic(tag string, format string, params ...interface{}) { 1018// params2 := make([]interface{}, len(params)+1) 1019// params2[0] = tag 1020// copy(params2[1:], params) 1021// panic(fmt.Errorf("%s: "+format, params2...)) 1022// } 1023 1024func isImmutableKind(k reflect.Kind) (v bool) { 1025 return false || 1026 k == reflect.Int || 1027 k == reflect.Int8 || 1028 k == reflect.Int16 || 1029 k == reflect.Int32 || 1030 k == reflect.Int64 || 1031 k == reflect.Uint || 1032 k == reflect.Uint8 || 1033 k == reflect.Uint16 || 1034 k == reflect.Uint32 || 1035 k == reflect.Uint64 || 1036 k == reflect.Uintptr || 1037 k == reflect.Float32 || 1038 k == reflect.Float64 || 1039 k == reflect.Bool || 1040 k == reflect.String 1041} 1042 1043// these functions must be inlinable, and not call anybody 1044type checkOverflow struct{} 1045 1046func (_ checkOverflow) Float32(f float64) (overflow bool) { 1047 if f < 0 { 1048 f = -f 1049 } 1050 return math.MaxFloat32 < f && f <= math.MaxFloat64 1051} 1052 1053func (_ checkOverflow) Uint(v uint64, bitsize uint8) (overflow bool) { 1054 if bitsize == 0 || bitsize >= 64 || v == 0 { 1055 return 1056 } 1057 if trunc := (v << (64 - bitsize)) >> (64 - bitsize); v != trunc { 1058 overflow = true 1059 } 1060 return 1061} 1062 1063func (_ checkOverflow) Int(v int64, bitsize uint8) (overflow bool) { 1064 if bitsize == 0 || bitsize >= 64 || v == 0 { 1065 return 1066 } 1067 if trunc := (v << (64 - bitsize)) >> (64 - bitsize); v != trunc { 1068 overflow = true 1069 } 1070 return 1071} 1072 1073func (_ checkOverflow) SignedInt(v uint64) (i int64, overflow bool) { 1074 //e.g. -127 to 128 for int8 1075 pos := (v >> 63) == 0 1076 ui2 := v & 0x7fffffffffffffff 1077 if pos { 1078 if ui2 > math.MaxInt64 { 1079 overflow = true 1080 return 1081 } 1082 } else { 1083 if ui2 > math.MaxInt64-1 { 1084 overflow = true 1085 return 1086 } 1087 } 1088 i = int64(v) 1089 return 1090} 1091 1092// ------------------ SORT ----------------- 1093 1094func isNaN(f float64) bool { return f != f } 1095 1096// ----------------------- 1097 1098type intSlice []int64 1099type uintSlice []uint64 1100type floatSlice []float64 1101type boolSlice []bool 1102type stringSlice []string 1103type bytesSlice [][]byte 1104 1105func (p intSlice) Len() int { return len(p) } 1106func (p intSlice) Less(i, j int) bool { return p[i] < p[j] } 1107func (p intSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1108 1109func (p uintSlice) Len() int { return len(p) } 1110func (p uintSlice) Less(i, j int) bool { return p[i] < p[j] } 1111func (p uintSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1112 1113func (p floatSlice) Len() int { return len(p) } 1114func (p floatSlice) Less(i, j int) bool { 1115 return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) 1116} 1117func (p floatSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1118 1119func (p stringSlice) Len() int { return len(p) } 1120func (p stringSlice) Less(i, j int) bool { return p[i] < p[j] } 1121func (p stringSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1122 1123func (p bytesSlice) Len() int { return len(p) } 1124func (p bytesSlice) Less(i, j int) bool { return bytes.Compare(p[i], p[j]) == -1 } 1125func (p bytesSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1126 1127func (p boolSlice) Len() int { return len(p) } 1128func (p boolSlice) Less(i, j int) bool { return !p[i] && p[j] } 1129func (p boolSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1130 1131// --------------------- 1132 1133type intRv struct { 1134 v int64 1135 r reflect.Value 1136} 1137type intRvSlice []intRv 1138type uintRv struct { 1139 v uint64 1140 r reflect.Value 1141} 1142type uintRvSlice []uintRv 1143type floatRv struct { 1144 v float64 1145 r reflect.Value 1146} 1147type floatRvSlice []floatRv 1148type boolRv struct { 1149 v bool 1150 r reflect.Value 1151} 1152type boolRvSlice []boolRv 1153type stringRv struct { 1154 v string 1155 r reflect.Value 1156} 1157type stringRvSlice []stringRv 1158type bytesRv struct { 1159 v []byte 1160 r reflect.Value 1161} 1162type bytesRvSlice []bytesRv 1163 1164func (p intRvSlice) Len() int { return len(p) } 1165func (p intRvSlice) Less(i, j int) bool { return p[i].v < p[j].v } 1166func (p intRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1167 1168func (p uintRvSlice) Len() int { return len(p) } 1169func (p uintRvSlice) Less(i, j int) bool { return p[i].v < p[j].v } 1170func (p uintRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1171 1172func (p floatRvSlice) Len() int { return len(p) } 1173func (p floatRvSlice) Less(i, j int) bool { 1174 return p[i].v < p[j].v || isNaN(p[i].v) && !isNaN(p[j].v) 1175} 1176func (p floatRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1177 1178func (p stringRvSlice) Len() int { return len(p) } 1179func (p stringRvSlice) Less(i, j int) bool { return p[i].v < p[j].v } 1180func (p stringRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1181 1182func (p bytesRvSlice) Len() int { return len(p) } 1183func (p bytesRvSlice) Less(i, j int) bool { return bytes.Compare(p[i].v, p[j].v) == -1 } 1184func (p bytesRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1185 1186func (p boolRvSlice) Len() int { return len(p) } 1187func (p boolRvSlice) Less(i, j int) bool { return !p[i].v && p[j].v } 1188func (p boolRvSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1189 1190// ----------------- 1191 1192type bytesI struct { 1193 v []byte 1194 i interface{} 1195} 1196 1197type bytesISlice []bytesI 1198 1199func (p bytesISlice) Len() int { return len(p) } 1200func (p bytesISlice) Less(i, j int) bool { return bytes.Compare(p[i].v, p[j].v) == -1 } 1201func (p bytesISlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 1202 1203// ----------------- 1204 1205type set []uintptr 1206 1207func (s *set) add(v uintptr) (exists bool) { 1208 // e.ci is always nil, or len >= 1 1209 // defer func() { fmt.Printf("$$$$$$$$$$$ cirRef Add: %v, exists: %v\n", v, exists) }() 1210 x := *s 1211 if x == nil { 1212 x = make([]uintptr, 1, 8) 1213 x[0] = v 1214 *s = x 1215 return 1216 } 1217 // typically, length will be 1. make this perform. 1218 if len(x) == 1 { 1219 if j := x[0]; j == 0 { 1220 x[0] = v 1221 } else if j == v { 1222 exists = true 1223 } else { 1224 x = append(x, v) 1225 *s = x 1226 } 1227 return 1228 } 1229 // check if it exists 1230 for _, j := range x { 1231 if j == v { 1232 exists = true 1233 return 1234 } 1235 } 1236 // try to replace a "deleted" slot 1237 for i, j := range x { 1238 if j == 0 { 1239 x[i] = v 1240 return 1241 } 1242 } 1243 // if unable to replace deleted slot, just append it. 1244 x = append(x, v) 1245 *s = x 1246 return 1247} 1248 1249func (s *set) remove(v uintptr) (exists bool) { 1250 // defer func() { fmt.Printf("$$$$$$$$$$$ cirRef Rm: %v, exists: %v\n", v, exists) }() 1251 x := *s 1252 if len(x) == 0 { 1253 return 1254 } 1255 if len(x) == 1 { 1256 if x[0] == v { 1257 x[0] = 0 1258 } 1259 return 1260 } 1261 for i, j := range x { 1262 if j == v { 1263 exists = true 1264 x[i] = 0 // set it to 0, as way to delete it. 1265 // copy(x[i:], x[i+1:]) 1266 // x = x[:len(x)-1] 1267 return 1268 } 1269 } 1270 return 1271} 1272