opcode.go (16863B)
1 package encoder 2 3 import ( 4 "bytes" 5 "fmt" 6 "sort" 7 "strings" 8 "unsafe" 9 10 "github.com/goccy/go-json/internal/runtime" 11 ) 12 13 const uintptrSize = 4 << (^uintptr(0) >> 63) 14 15 type OpFlags uint16 16 17 const ( 18 AnonymousHeadFlags OpFlags = 1 << 0 19 AnonymousKeyFlags OpFlags = 1 << 1 20 IndirectFlags OpFlags = 1 << 2 21 IsTaggedKeyFlags OpFlags = 1 << 3 22 NilCheckFlags OpFlags = 1 << 4 23 AddrForMarshalerFlags OpFlags = 1 << 5 24 IsNextOpPtrTypeFlags OpFlags = 1 << 6 25 IsNilableTypeFlags OpFlags = 1 << 7 26 MarshalerContextFlags OpFlags = 1 << 8 27 NonEmptyInterfaceFlags OpFlags = 1 << 9 28 ) 29 30 type Opcode struct { 31 Op OpType // operation type 32 Idx uint32 // offset to access ptr 33 Next *Opcode // next opcode 34 End *Opcode // array/slice/struct/map end 35 NextField *Opcode // next struct field 36 Key string // struct field key 37 Offset uint32 // offset size from struct header 38 PtrNum uint8 // pointer number: e.g. double pointer is 2. 39 NumBitSize uint8 40 Flags OpFlags 41 42 Type *runtime.Type // go type 43 Jmp *CompiledCode // for recursive call 44 FieldQuery *FieldQuery // field query for Interface / MarshalJSON / MarshalText 45 ElemIdx uint32 // offset to access array/slice elem 46 Length uint32 // offset to access slice length or array length 47 Indent uint32 // indent number 48 Size uint32 // array/slice elem size 49 DisplayIdx uint32 // opcode index 50 DisplayKey string // key text to display 51 } 52 53 func (c *Opcode) Validate() error { 54 var prevIdx uint32 55 for code := c; !code.IsEnd(); { 56 if prevIdx != 0 { 57 if code.DisplayIdx != prevIdx+1 { 58 return fmt.Errorf( 59 "invalid index. previous display index is %d but next is %d. dump = %s", 60 prevIdx, code.DisplayIdx, c.Dump(), 61 ) 62 } 63 } 64 prevIdx = code.DisplayIdx 65 code = code.IterNext() 66 } 67 return nil 68 } 69 70 func (c *Opcode) IterNext() *Opcode { 71 if c == nil { 72 return nil 73 } 74 switch c.Op.CodeType() { 75 case CodeArrayElem, CodeSliceElem, CodeMapKey: 76 return c.End 77 default: 78 return c.Next 79 } 80 } 81 82 func (c *Opcode) IsEnd() bool { 83 if c == nil { 84 return true 85 } 86 return c.Op == OpEnd || c.Op == OpInterfaceEnd || c.Op == OpRecursiveEnd 87 } 88 89 func (c *Opcode) MaxIdx() uint32 { 90 max := uint32(0) 91 for _, value := range []uint32{ 92 c.Idx, 93 c.ElemIdx, 94 c.Length, 95 c.Size, 96 } { 97 if max < value { 98 max = value 99 } 100 } 101 return max 102 } 103 104 func (c *Opcode) ToHeaderType(isString bool) OpType { 105 switch c.Op { 106 case OpInt: 107 if isString { 108 return OpStructHeadIntString 109 } 110 return OpStructHeadInt 111 case OpIntPtr: 112 if isString { 113 return OpStructHeadIntPtrString 114 } 115 return OpStructHeadIntPtr 116 case OpUint: 117 if isString { 118 return OpStructHeadUintString 119 } 120 return OpStructHeadUint 121 case OpUintPtr: 122 if isString { 123 return OpStructHeadUintPtrString 124 } 125 return OpStructHeadUintPtr 126 case OpFloat32: 127 if isString { 128 return OpStructHeadFloat32String 129 } 130 return OpStructHeadFloat32 131 case OpFloat32Ptr: 132 if isString { 133 return OpStructHeadFloat32PtrString 134 } 135 return OpStructHeadFloat32Ptr 136 case OpFloat64: 137 if isString { 138 return OpStructHeadFloat64String 139 } 140 return OpStructHeadFloat64 141 case OpFloat64Ptr: 142 if isString { 143 return OpStructHeadFloat64PtrString 144 } 145 return OpStructHeadFloat64Ptr 146 case OpString: 147 if isString { 148 return OpStructHeadStringString 149 } 150 return OpStructHeadString 151 case OpStringPtr: 152 if isString { 153 return OpStructHeadStringPtrString 154 } 155 return OpStructHeadStringPtr 156 case OpNumber: 157 if isString { 158 return OpStructHeadNumberString 159 } 160 return OpStructHeadNumber 161 case OpNumberPtr: 162 if isString { 163 return OpStructHeadNumberPtrString 164 } 165 return OpStructHeadNumberPtr 166 case OpBool: 167 if isString { 168 return OpStructHeadBoolString 169 } 170 return OpStructHeadBool 171 case OpBoolPtr: 172 if isString { 173 return OpStructHeadBoolPtrString 174 } 175 return OpStructHeadBoolPtr 176 case OpBytes: 177 return OpStructHeadBytes 178 case OpBytesPtr: 179 return OpStructHeadBytesPtr 180 case OpMap: 181 return OpStructHeadMap 182 case OpMapPtr: 183 c.Op = OpMap 184 return OpStructHeadMapPtr 185 case OpArray: 186 return OpStructHeadArray 187 case OpArrayPtr: 188 c.Op = OpArray 189 return OpStructHeadArrayPtr 190 case OpSlice: 191 return OpStructHeadSlice 192 case OpSlicePtr: 193 c.Op = OpSlice 194 return OpStructHeadSlicePtr 195 case OpMarshalJSON: 196 return OpStructHeadMarshalJSON 197 case OpMarshalJSONPtr: 198 return OpStructHeadMarshalJSONPtr 199 case OpMarshalText: 200 return OpStructHeadMarshalText 201 case OpMarshalTextPtr: 202 return OpStructHeadMarshalTextPtr 203 } 204 return OpStructHead 205 } 206 207 func (c *Opcode) ToFieldType(isString bool) OpType { 208 switch c.Op { 209 case OpInt: 210 if isString { 211 return OpStructFieldIntString 212 } 213 return OpStructFieldInt 214 case OpIntPtr: 215 if isString { 216 return OpStructFieldIntPtrString 217 } 218 return OpStructFieldIntPtr 219 case OpUint: 220 if isString { 221 return OpStructFieldUintString 222 } 223 return OpStructFieldUint 224 case OpUintPtr: 225 if isString { 226 return OpStructFieldUintPtrString 227 } 228 return OpStructFieldUintPtr 229 case OpFloat32: 230 if isString { 231 return OpStructFieldFloat32String 232 } 233 return OpStructFieldFloat32 234 case OpFloat32Ptr: 235 if isString { 236 return OpStructFieldFloat32PtrString 237 } 238 return OpStructFieldFloat32Ptr 239 case OpFloat64: 240 if isString { 241 return OpStructFieldFloat64String 242 } 243 return OpStructFieldFloat64 244 case OpFloat64Ptr: 245 if isString { 246 return OpStructFieldFloat64PtrString 247 } 248 return OpStructFieldFloat64Ptr 249 case OpString: 250 if isString { 251 return OpStructFieldStringString 252 } 253 return OpStructFieldString 254 case OpStringPtr: 255 if isString { 256 return OpStructFieldStringPtrString 257 } 258 return OpStructFieldStringPtr 259 case OpNumber: 260 if isString { 261 return OpStructFieldNumberString 262 } 263 return OpStructFieldNumber 264 case OpNumberPtr: 265 if isString { 266 return OpStructFieldNumberPtrString 267 } 268 return OpStructFieldNumberPtr 269 case OpBool: 270 if isString { 271 return OpStructFieldBoolString 272 } 273 return OpStructFieldBool 274 case OpBoolPtr: 275 if isString { 276 return OpStructFieldBoolPtrString 277 } 278 return OpStructFieldBoolPtr 279 case OpBytes: 280 return OpStructFieldBytes 281 case OpBytesPtr: 282 return OpStructFieldBytesPtr 283 case OpMap: 284 return OpStructFieldMap 285 case OpMapPtr: 286 c.Op = OpMap 287 return OpStructFieldMapPtr 288 case OpArray: 289 return OpStructFieldArray 290 case OpArrayPtr: 291 c.Op = OpArray 292 return OpStructFieldArrayPtr 293 case OpSlice: 294 return OpStructFieldSlice 295 case OpSlicePtr: 296 c.Op = OpSlice 297 return OpStructFieldSlicePtr 298 case OpMarshalJSON: 299 return OpStructFieldMarshalJSON 300 case OpMarshalJSONPtr: 301 return OpStructFieldMarshalJSONPtr 302 case OpMarshalText: 303 return OpStructFieldMarshalText 304 case OpMarshalTextPtr: 305 return OpStructFieldMarshalTextPtr 306 } 307 return OpStructField 308 } 309 310 func newOpCode(ctx *compileContext, typ *runtime.Type, op OpType) *Opcode { 311 return newOpCodeWithNext(ctx, typ, op, newEndOp(ctx, typ)) 312 } 313 314 func opcodeOffset(idx int) uint32 { 315 return uint32(idx) * uintptrSize 316 } 317 318 func getCodeAddrByIdx(head *Opcode, idx uint32) *Opcode { 319 addr := uintptr(unsafe.Pointer(head)) + uintptr(idx)*unsafe.Sizeof(Opcode{}) 320 return *(**Opcode)(unsafe.Pointer(&addr)) 321 } 322 323 func copyOpcode(code *Opcode) *Opcode { 324 codeNum := ToEndCode(code).DisplayIdx + 1 325 codeSlice := make([]Opcode, codeNum) 326 head := (*Opcode)((*runtime.SliceHeader)(unsafe.Pointer(&codeSlice)).Data) 327 ptr := head 328 c := code 329 for { 330 *ptr = Opcode{ 331 Op: c.Op, 332 Key: c.Key, 333 PtrNum: c.PtrNum, 334 NumBitSize: c.NumBitSize, 335 Flags: c.Flags, 336 Idx: c.Idx, 337 Offset: c.Offset, 338 Type: c.Type, 339 FieldQuery: c.FieldQuery, 340 DisplayIdx: c.DisplayIdx, 341 DisplayKey: c.DisplayKey, 342 ElemIdx: c.ElemIdx, 343 Length: c.Length, 344 Size: c.Size, 345 Indent: c.Indent, 346 Jmp: c.Jmp, 347 } 348 if c.End != nil { 349 ptr.End = getCodeAddrByIdx(head, c.End.DisplayIdx) 350 } 351 if c.NextField != nil { 352 ptr.NextField = getCodeAddrByIdx(head, c.NextField.DisplayIdx) 353 } 354 if c.Next != nil { 355 ptr.Next = getCodeAddrByIdx(head, c.Next.DisplayIdx) 356 } 357 if c.IsEnd() { 358 break 359 } 360 ptr = getCodeAddrByIdx(head, c.DisplayIdx+1) 361 c = c.IterNext() 362 } 363 return head 364 } 365 366 func setTotalLengthToInterfaceOp(code *Opcode) { 367 for c := code; !c.IsEnd(); { 368 if c.Op == OpInterface || c.Op == OpInterfacePtr { 369 c.Length = uint32(code.TotalLength()) 370 } 371 c = c.IterNext() 372 } 373 } 374 375 func ToEndCode(code *Opcode) *Opcode { 376 c := code 377 for !c.IsEnd() { 378 c = c.IterNext() 379 } 380 return c 381 } 382 383 func copyToInterfaceOpcode(code *Opcode) *Opcode { 384 copied := copyOpcode(code) 385 c := copied 386 c = ToEndCode(c) 387 c.Idx += uintptrSize 388 c.ElemIdx = c.Idx + uintptrSize 389 c.Length = c.Idx + 2*uintptrSize 390 c.Op = OpInterfaceEnd 391 return copied 392 } 393 394 func newOpCodeWithNext(ctx *compileContext, typ *runtime.Type, op OpType, next *Opcode) *Opcode { 395 return &Opcode{ 396 Op: op, 397 Idx: opcodeOffset(ctx.ptrIndex), 398 Next: next, 399 Type: typ, 400 DisplayIdx: ctx.opcodeIndex, 401 Indent: ctx.indent, 402 } 403 } 404 405 func newEndOp(ctx *compileContext, typ *runtime.Type) *Opcode { 406 return newOpCodeWithNext(ctx, typ, OpEnd, nil) 407 } 408 409 func (c *Opcode) TotalLength() int { 410 var idx int 411 code := c 412 for !code.IsEnd() { 413 maxIdx := int(code.MaxIdx() / uintptrSize) 414 if idx < maxIdx { 415 idx = maxIdx 416 } 417 if code.Op == OpRecursiveEnd { 418 break 419 } 420 code = code.IterNext() 421 } 422 maxIdx := int(code.MaxIdx() / uintptrSize) 423 if idx < maxIdx { 424 idx = maxIdx 425 } 426 return idx + 1 427 } 428 429 func (c *Opcode) dumpHead(code *Opcode) string { 430 var length uint32 431 if code.Op.CodeType() == CodeArrayHead { 432 length = code.Length 433 } else { 434 length = code.Length / uintptrSize 435 } 436 return fmt.Sprintf( 437 `[%03d]%s%s ([idx:%d][elemIdx:%d][length:%d])`, 438 code.DisplayIdx, 439 strings.Repeat("-", int(code.Indent)), 440 code.Op, 441 code.Idx/uintptrSize, 442 code.ElemIdx/uintptrSize, 443 length, 444 ) 445 } 446 447 func (c *Opcode) dumpMapHead(code *Opcode) string { 448 return fmt.Sprintf( 449 `[%03d]%s%s ([idx:%d])`, 450 code.DisplayIdx, 451 strings.Repeat("-", int(code.Indent)), 452 code.Op, 453 code.Idx/uintptrSize, 454 ) 455 } 456 457 func (c *Opcode) dumpMapEnd(code *Opcode) string { 458 return fmt.Sprintf( 459 `[%03d]%s%s ([idx:%d])`, 460 code.DisplayIdx, 461 strings.Repeat("-", int(code.Indent)), 462 code.Op, 463 code.Idx/uintptrSize, 464 ) 465 } 466 467 func (c *Opcode) dumpElem(code *Opcode) string { 468 var length uint32 469 if code.Op.CodeType() == CodeArrayElem { 470 length = code.Length 471 } else { 472 length = code.Length / uintptrSize 473 } 474 return fmt.Sprintf( 475 `[%03d]%s%s ([idx:%d][elemIdx:%d][length:%d][size:%d])`, 476 code.DisplayIdx, 477 strings.Repeat("-", int(code.Indent)), 478 code.Op, 479 code.Idx/uintptrSize, 480 code.ElemIdx/uintptrSize, 481 length, 482 code.Size, 483 ) 484 } 485 486 func (c *Opcode) dumpField(code *Opcode) string { 487 return fmt.Sprintf( 488 `[%03d]%s%s ([idx:%d][key:%s][offset:%d])`, 489 code.DisplayIdx, 490 strings.Repeat("-", int(code.Indent)), 491 code.Op, 492 code.Idx/uintptrSize, 493 code.DisplayKey, 494 code.Offset, 495 ) 496 } 497 498 func (c *Opcode) dumpKey(code *Opcode) string { 499 return fmt.Sprintf( 500 `[%03d]%s%s ([idx:%d])`, 501 code.DisplayIdx, 502 strings.Repeat("-", int(code.Indent)), 503 code.Op, 504 code.Idx/uintptrSize, 505 ) 506 } 507 508 func (c *Opcode) dumpValue(code *Opcode) string { 509 return fmt.Sprintf( 510 `[%03d]%s%s ([idx:%d])`, 511 code.DisplayIdx, 512 strings.Repeat("-", int(code.Indent)), 513 code.Op, 514 code.Idx/uintptrSize, 515 ) 516 } 517 518 func (c *Opcode) Dump() string { 519 codes := []string{} 520 for code := c; !code.IsEnd(); { 521 switch code.Op.CodeType() { 522 case CodeSliceHead: 523 codes = append(codes, c.dumpHead(code)) 524 code = code.Next 525 case CodeMapHead: 526 codes = append(codes, c.dumpMapHead(code)) 527 code = code.Next 528 case CodeArrayElem, CodeSliceElem: 529 codes = append(codes, c.dumpElem(code)) 530 code = code.End 531 case CodeMapKey: 532 codes = append(codes, c.dumpKey(code)) 533 code = code.End 534 case CodeMapValue: 535 codes = append(codes, c.dumpValue(code)) 536 code = code.Next 537 case CodeMapEnd: 538 codes = append(codes, c.dumpMapEnd(code)) 539 code = code.Next 540 case CodeStructField: 541 codes = append(codes, c.dumpField(code)) 542 code = code.Next 543 case CodeStructEnd: 544 codes = append(codes, c.dumpField(code)) 545 code = code.Next 546 default: 547 codes = append(codes, fmt.Sprintf( 548 "[%03d]%s%s ([idx:%d])", 549 code.DisplayIdx, 550 strings.Repeat("-", int(code.Indent)), 551 code.Op, 552 code.Idx/uintptrSize, 553 )) 554 code = code.Next 555 } 556 } 557 return strings.Join(codes, "\n") 558 } 559 560 func (c *Opcode) DumpDOT() string { 561 type edge struct { 562 from, to *Opcode 563 label string 564 weight int 565 } 566 var edges []edge 567 568 b := &bytes.Buffer{} 569 fmt.Fprintf(b, "digraph \"%p\" {\n", c.Type) 570 fmt.Fprintln(b, "mclimit=1.5;\nrankdir=TD;\nordering=out;\nnode[shape=box];") 571 for code := c; !code.IsEnd(); { 572 label := code.Op.String() 573 fmt.Fprintf(b, "\"%p\" [label=%q];\n", code, label) 574 if p := code.Next; p != nil { 575 edges = append(edges, edge{ 576 from: code, 577 to: p, 578 label: "Next", 579 weight: 10, 580 }) 581 } 582 if p := code.NextField; p != nil { 583 edges = append(edges, edge{ 584 from: code, 585 to: p, 586 label: "NextField", 587 weight: 2, 588 }) 589 } 590 if p := code.End; p != nil { 591 edges = append(edges, edge{ 592 from: code, 593 to: p, 594 label: "End", 595 weight: 1, 596 }) 597 } 598 if p := code.Jmp; p != nil { 599 edges = append(edges, edge{ 600 from: code, 601 to: p.Code, 602 label: "Jmp", 603 weight: 1, 604 }) 605 } 606 607 switch code.Op.CodeType() { 608 case CodeSliceHead: 609 code = code.Next 610 case CodeMapHead: 611 code = code.Next 612 case CodeArrayElem, CodeSliceElem: 613 code = code.End 614 case CodeMapKey: 615 code = code.End 616 case CodeMapValue: 617 code = code.Next 618 case CodeMapEnd: 619 code = code.Next 620 case CodeStructField: 621 code = code.Next 622 case CodeStructEnd: 623 code = code.Next 624 default: 625 code = code.Next 626 } 627 if code.IsEnd() { 628 fmt.Fprintf(b, "\"%p\" [label=%q];\n", code, code.Op.String()) 629 } 630 } 631 sort.Slice(edges, func(i, j int) bool { 632 return edges[i].to.DisplayIdx < edges[j].to.DisplayIdx 633 }) 634 for _, e := range edges { 635 fmt.Fprintf(b, "\"%p\" -> \"%p\" [label=%q][weight=%d];\n", e.from, e.to, e.label, e.weight) 636 } 637 fmt.Fprint(b, "}") 638 return b.String() 639 } 640 641 func newSliceHeaderCode(ctx *compileContext, typ *runtime.Type) *Opcode { 642 idx := opcodeOffset(ctx.ptrIndex) 643 ctx.incPtrIndex() 644 elemIdx := opcodeOffset(ctx.ptrIndex) 645 ctx.incPtrIndex() 646 length := opcodeOffset(ctx.ptrIndex) 647 return &Opcode{ 648 Op: OpSlice, 649 Type: typ, 650 Idx: idx, 651 DisplayIdx: ctx.opcodeIndex, 652 ElemIdx: elemIdx, 653 Length: length, 654 Indent: ctx.indent, 655 } 656 } 657 658 func newSliceElemCode(ctx *compileContext, typ *runtime.Type, head *Opcode, size uintptr) *Opcode { 659 return &Opcode{ 660 Op: OpSliceElem, 661 Type: typ, 662 Idx: head.Idx, 663 DisplayIdx: ctx.opcodeIndex, 664 ElemIdx: head.ElemIdx, 665 Length: head.Length, 666 Indent: ctx.indent, 667 Size: uint32(size), 668 } 669 } 670 671 func newArrayHeaderCode(ctx *compileContext, typ *runtime.Type, alen int) *Opcode { 672 idx := opcodeOffset(ctx.ptrIndex) 673 ctx.incPtrIndex() 674 elemIdx := opcodeOffset(ctx.ptrIndex) 675 return &Opcode{ 676 Op: OpArray, 677 Type: typ, 678 Idx: idx, 679 DisplayIdx: ctx.opcodeIndex, 680 ElemIdx: elemIdx, 681 Indent: ctx.indent, 682 Length: uint32(alen), 683 } 684 } 685 686 func newArrayElemCode(ctx *compileContext, typ *runtime.Type, head *Opcode, length int, size uintptr) *Opcode { 687 return &Opcode{ 688 Op: OpArrayElem, 689 Type: typ, 690 Idx: head.Idx, 691 DisplayIdx: ctx.opcodeIndex, 692 ElemIdx: head.ElemIdx, 693 Length: uint32(length), 694 Indent: ctx.indent, 695 Size: uint32(size), 696 } 697 } 698 699 func newMapHeaderCode(ctx *compileContext, typ *runtime.Type) *Opcode { 700 idx := opcodeOffset(ctx.ptrIndex) 701 ctx.incPtrIndex() 702 return &Opcode{ 703 Op: OpMap, 704 Type: typ, 705 Idx: idx, 706 DisplayIdx: ctx.opcodeIndex, 707 Indent: ctx.indent, 708 } 709 } 710 711 func newMapKeyCode(ctx *compileContext, typ *runtime.Type, head *Opcode) *Opcode { 712 return &Opcode{ 713 Op: OpMapKey, 714 Type: typ, 715 Idx: head.Idx, 716 DisplayIdx: ctx.opcodeIndex, 717 Indent: ctx.indent, 718 } 719 } 720 721 func newMapValueCode(ctx *compileContext, typ *runtime.Type, head *Opcode) *Opcode { 722 return &Opcode{ 723 Op: OpMapValue, 724 Type: typ, 725 Idx: head.Idx, 726 DisplayIdx: ctx.opcodeIndex, 727 Indent: ctx.indent, 728 } 729 } 730 731 func newMapEndCode(ctx *compileContext, typ *runtime.Type, head *Opcode) *Opcode { 732 return &Opcode{ 733 Op: OpMapEnd, 734 Type: typ, 735 Idx: head.Idx, 736 DisplayIdx: ctx.opcodeIndex, 737 Indent: ctx.indent, 738 Next: newEndOp(ctx, typ), 739 } 740 } 741 742 func newRecursiveCode(ctx *compileContext, typ *runtime.Type, jmp *CompiledCode) *Opcode { 743 return &Opcode{ 744 Op: OpRecursive, 745 Type: typ, 746 Idx: opcodeOffset(ctx.ptrIndex), 747 Next: newEndOp(ctx, typ), 748 DisplayIdx: ctx.opcodeIndex, 749 Indent: ctx.indent, 750 Jmp: jmp, 751 } 752 }