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