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
32 Idx uint32
33 Next *Opcode
34 End *Opcode
35 NextField *Opcode
36 Key string
37 Offset uint32
38 PtrNum uint8
39 NumBitSize uint8
40 Flags OpFlags
41
42 Type *runtime.Type
43 Jmp *CompiledCode
44 FieldQuery *FieldQuery
45 ElemIdx uint32
46 Length uint32
47 Indent uint32
48 Size uint32
49 DisplayIdx uint32
50 DisplayKey string
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 }
753
View as plain text