1// Copyright 2010 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package json implements encoding and decoding of JSON as defined in
6// RFC 4627. The mapping between JSON and Go values is described
7// in the documentation for the Marshal and Unmarshal functions.
8//
9// See "JSON and Go" for an introduction to this package:
10// https://golang.org/doc/articles/json_and_go.html
11package json
12
13import (
14	"bytes"
15	"encoding"
16	"encoding/base64"
17	"fmt"
18	"math"
19	"reflect"
20	"runtime"
21	"sort"
22	"strconv"
23	"strings"
24	"sync"
25	"sync/atomic"
26	"unicode"
27	"unicode/utf8"
28)
29
30// Marshal returns the JSON encoding of v.
31//
32// Marshal traverses the value v recursively.
33// If an encountered value implements the Marshaler interface
34// and is not a nil pointer, Marshal calls its MarshalJSON method
35// to produce JSON. If no MarshalJSON method is present but the
36// value implements encoding.TextMarshaler instead, Marshal calls
37// its MarshalText method.
38// The nil pointer exception is not strictly necessary
39// but mimics a similar, necessary exception in the behavior of
40// UnmarshalJSON.
41//
42// Otherwise, Marshal uses the following type-dependent default encodings:
43//
44// Boolean values encode as JSON booleans.
45//
46// Floating point, integer, and Number values encode as JSON numbers.
47//
48// String values encode as JSON strings coerced to valid UTF-8,
49// replacing invalid bytes with the Unicode replacement rune.
50// The angle brackets "<" and ">" are escaped to "\u003c" and "\u003e"
51// to keep some browsers from misinterpreting JSON output as HTML.
52// Ampersand "&" is also escaped to "\u0026" for the same reason.
53// This escaping can be disabled using an Encoder with DisableHTMLEscaping.
54//
55// Array and slice values encode as JSON arrays, except that
56// []byte encodes as a base64-encoded string, and a nil slice
57// encodes as the null JSON value.
58//
59// Struct values encode as JSON objects. Each exported struct field
60// becomes a member of the object unless
61//   - the field's tag is "-", or
62//   - the field is empty and its tag specifies the "omitempty" option.
63// The empty values are false, 0, any
64// nil pointer or interface value, and any array, slice, map, or string of
65// length zero. The object's default key string is the struct field name
66// but can be specified in the struct field's tag value. The "json" key in
67// the struct field's tag value is the key name, followed by an optional comma
68// and options. Examples:
69//
70//   // Field is ignored by this package.
71//   Field int `json:"-"`
72//
73//   // Field appears in JSON as key "myName".
74//   Field int `json:"myName"`
75//
76//   // Field appears in JSON as key "myName" and
77//   // the field is omitted from the object if its value is empty,
78//   // as defined above.
79//   Field int `json:"myName,omitempty"`
80//
81//   // Field appears in JSON as key "Field" (the default), but
82//   // the field is skipped if empty.
83//   // Note the leading comma.
84//   Field int `json:",omitempty"`
85//
86// The "string" option signals that a field is stored as JSON inside a
87// JSON-encoded string. It applies only to fields of string, floating point,
88// integer, or boolean types. This extra level of encoding is sometimes used
89// when communicating with JavaScript programs:
90//
91//    Int64String int64 `json:",string"`
92//
93// The key name will be used if it's a non-empty string consisting of
94// only Unicode letters, digits, and ASCII punctuation except quotation
95// marks, backslash, and comma.
96//
97// Anonymous struct fields are usually marshaled as if their inner exported fields
98// were fields in the outer struct, subject to the usual Go visibility rules amended
99// as described in the next paragraph.
100// An anonymous struct field with a name given in its JSON tag is treated as
101// having that name, rather than being anonymous.
102// An anonymous struct field of interface type is treated the same as having
103// that type as its name, rather than being anonymous.
104//
105// The Go visibility rules for struct fields are amended for JSON when
106// deciding which field to marshal or unmarshal. If there are
107// multiple fields at the same level, and that level is the least
108// nested (and would therefore be the nesting level selected by the
109// usual Go rules), the following extra rules apply:
110//
111// 1) Of those fields, if any are JSON-tagged, only tagged fields are considered,
112// even if there are multiple untagged fields that would otherwise conflict.
113// 2) If there is exactly one field (tagged or not according to the first rule), that is selected.
114// 3) Otherwise there are multiple fields, and all are ignored; no error occurs.
115//
116// Handling of anonymous struct fields is new in Go 1.1.
117// Prior to Go 1.1, anonymous struct fields were ignored. To force ignoring of
118// an anonymous struct field in both current and earlier versions, give the field
119// a JSON tag of "-".
120//
121// Map values encode as JSON objects. The map's key type must either be a
122// string, an integer type, or implement encoding.TextMarshaler. The map keys
123// are sorted and used as JSON object keys by applying the following rules,
124// subject to the UTF-8 coercion described for string values above:
125//   - string keys are used directly
126//   - encoding.TextMarshalers are marshaled
127//   - integer keys are converted to strings
128//
129// Pointer values encode as the value pointed to.
130// A nil pointer encodes as the null JSON value.
131//
132// Interface values encode as the value contained in the interface.
133// A nil interface value encodes as the null JSON value.
134//
135// Channel, complex, and function values cannot be encoded in JSON.
136// Attempting to encode such a value causes Marshal to return
137// an UnsupportedTypeError.
138//
139// JSON cannot represent cyclic data structures and Marshal does not
140// handle them. Passing cyclic structures to Marshal will result in
141// an infinite recursion.
142//
143func Marshal(v interface{}) ([]byte, error) {
144	e := &encodeState{}
145	err := e.marshal(v, encOpts{escapeHTML: true})
146	if err != nil {
147		return nil, err
148	}
149	return e.Bytes(), nil
150}
151
152// MarshalIndent is like Marshal but applies Indent to format the output.
153func MarshalIndent(v interface{}, prefix, indent string) ([]byte, error) {
154	b, err := Marshal(v)
155	if err != nil {
156		return nil, err
157	}
158	var buf bytes.Buffer
159	err = Indent(&buf, b, prefix, indent)
160	if err != nil {
161		return nil, err
162	}
163	return buf.Bytes(), nil
164}
165
166// HTMLEscape appends to dst the JSON-encoded src with <, >, &, U+2028 and U+2029
167// characters inside string literals changed to \u003c, \u003e, \u0026, \u2028, \u2029
168// so that the JSON will be safe to embed inside HTML <script> tags.
169// For historical reasons, web browsers don't honor standard HTML
170// escaping within <script> tags, so an alternative JSON encoding must
171// be used.
172func HTMLEscape(dst *bytes.Buffer, src []byte) {
173	// The characters can only appear in string literals,
174	// so just scan the string one byte at a time.
175	start := 0
176	for i, c := range src {
177		if c == '<' || c == '>' || c == '&' {
178			if start < i {
179				dst.Write(src[start:i])
180			}
181			dst.WriteString(`\u00`)
182			dst.WriteByte(hex[c>>4])
183			dst.WriteByte(hex[c&0xF])
184			start = i + 1
185		}
186		// Convert U+2028 and U+2029 (E2 80 A8 and E2 80 A9).
187		if c == 0xE2 && i+2 < len(src) && src[i+1] == 0x80 && src[i+2]&^1 == 0xA8 {
188			if start < i {
189				dst.Write(src[start:i])
190			}
191			dst.WriteString(`\u202`)
192			dst.WriteByte(hex[src[i+2]&0xF])
193			start = i + 3
194		}
195	}
196	if start < len(src) {
197		dst.Write(src[start:])
198	}
199}
200
201// Marshaler is the interface implemented by types that
202// can marshal themselves into valid JSON.
203type Marshaler interface {
204	MarshalJSON() ([]byte, error)
205}
206
207// An UnsupportedTypeError is returned by Marshal when attempting
208// to encode an unsupported value type.
209type UnsupportedTypeError struct {
210	Type reflect.Type
211}
212
213func (e *UnsupportedTypeError) Error() string {
214	return "json: unsupported type: " + e.Type.String()
215}
216
217type UnsupportedValueError struct {
218	Value reflect.Value
219	Str   string
220}
221
222func (e *UnsupportedValueError) Error() string {
223	return "json: unsupported value: " + e.Str
224}
225
226// Before Go 1.2, an InvalidUTF8Error was returned by Marshal when
227// attempting to encode a string value with invalid UTF-8 sequences.
228// As of Go 1.2, Marshal instead coerces the string to valid UTF-8 by
229// replacing invalid bytes with the Unicode replacement rune U+FFFD.
230// This error is no longer generated but is kept for backwards compatibility
231// with programs that might mention it.
232type InvalidUTF8Error struct {
233	S string // the whole string value that caused the error
234}
235
236func (e *InvalidUTF8Error) Error() string {
237	return "json: invalid UTF-8 in string: " + strconv.Quote(e.S)
238}
239
240type MarshalerError struct {
241	Type reflect.Type
242	Err  error
243}
244
245func (e *MarshalerError) Error() string {
246	return "json: error calling MarshalJSON for type " + e.Type.String() + ": " + e.Err.Error()
247}
248
249var hex = "0123456789abcdef"
250
251// An encodeState encodes JSON into a bytes.Buffer.
252type encodeState struct {
253	bytes.Buffer // accumulated output
254	scratch      [64]byte
255}
256
257var encodeStatePool sync.Pool
258
259func newEncodeState() *encodeState {
260	if v := encodeStatePool.Get(); v != nil {
261		e := v.(*encodeState)
262		e.Reset()
263		return e
264	}
265	return new(encodeState)
266}
267
268func (e *encodeState) marshal(v interface{}, opts encOpts) (err error) {
269	defer func() {
270		if r := recover(); r != nil {
271			if _, ok := r.(runtime.Error); ok {
272				panic(r)
273			}
274			if s, ok := r.(string); ok {
275				panic(s)
276			}
277			err = r.(error)
278		}
279	}()
280	e.reflectValue(reflect.ValueOf(v), opts)
281	return nil
282}
283
284func (e *encodeState) error(err error) {
285	panic(err)
286}
287
288func isEmptyValue(v reflect.Value) bool {
289	switch v.Kind() {
290	case reflect.Array, reflect.Map, reflect.Slice, reflect.String:
291		return v.Len() == 0
292	case reflect.Bool:
293		return !v.Bool()
294	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
295		return v.Int() == 0
296	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
297		return v.Uint() == 0
298	case reflect.Float32, reflect.Float64:
299		return v.Float() == 0
300	case reflect.Interface, reflect.Ptr:
301		return v.IsNil()
302	}
303	return false
304}
305
306func (e *encodeState) reflectValue(v reflect.Value, opts encOpts) {
307	valueEncoder(v)(e, v, opts)
308}
309
310type encOpts struct {
311	// quoted causes primitive fields to be encoded inside JSON strings.
312	quoted bool
313	// escapeHTML causes '<', '>', and '&' to be escaped in JSON strings.
314	escapeHTML bool
315}
316
317type encoderFunc func(e *encodeState, v reflect.Value, opts encOpts)
318
319var encoderCache struct {
320	sync.RWMutex
321	m map[reflect.Type]encoderFunc
322}
323
324func valueEncoder(v reflect.Value) encoderFunc {
325	if !v.IsValid() {
326		return invalidValueEncoder
327	}
328	return typeEncoder(v.Type())
329}
330
331func typeEncoder(t reflect.Type) encoderFunc {
332	encoderCache.RLock()
333	f := encoderCache.m[t]
334	encoderCache.RUnlock()
335	if f != nil {
336		return f
337	}
338
339	// To deal with recursive types, populate the map with an
340	// indirect func before we build it. This type waits on the
341	// real func (f) to be ready and then calls it. This indirect
342	// func is only used for recursive types.
343	encoderCache.Lock()
344	if encoderCache.m == nil {
345		encoderCache.m = make(map[reflect.Type]encoderFunc)
346	}
347	var wg sync.WaitGroup
348	wg.Add(1)
349	encoderCache.m[t] = func(e *encodeState, v reflect.Value, opts encOpts) {
350		wg.Wait()
351		f(e, v, opts)
352	}
353	encoderCache.Unlock()
354
355	// Compute fields without lock.
356	// Might duplicate effort but won't hold other computations back.
357	f = newTypeEncoder(t, true)
358	wg.Done()
359	encoderCache.Lock()
360	encoderCache.m[t] = f
361	encoderCache.Unlock()
362	return f
363}
364
365var (
366	marshalerType     = reflect.TypeOf(new(Marshaler)).Elem()
367	textMarshalerType = reflect.TypeOf(new(encoding.TextMarshaler)).Elem()
368)
369
370// newTypeEncoder constructs an encoderFunc for a type.
371// The returned encoder only checks CanAddr when allowAddr is true.
372func newTypeEncoder(t reflect.Type, allowAddr bool) encoderFunc {
373	if t.Implements(marshalerType) {
374		return marshalerEncoder
375	}
376	if t.Kind() != reflect.Ptr && allowAddr {
377		if reflect.PtrTo(t).Implements(marshalerType) {
378			return newCondAddrEncoder(addrMarshalerEncoder, newTypeEncoder(t, false))
379		}
380	}
381
382	if t.Implements(textMarshalerType) {
383		return textMarshalerEncoder
384	}
385	if t.Kind() != reflect.Ptr && allowAddr {
386		if reflect.PtrTo(t).Implements(textMarshalerType) {
387			return newCondAddrEncoder(addrTextMarshalerEncoder, newTypeEncoder(t, false))
388		}
389	}
390
391	switch t.Kind() {
392	case reflect.Bool:
393		return boolEncoder
394	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
395		return intEncoder
396	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
397		return uintEncoder
398	case reflect.Float32:
399		return float32Encoder
400	case reflect.Float64:
401		return float64Encoder
402	case reflect.String:
403		return stringEncoder
404	case reflect.Interface:
405		return interfaceEncoder
406	case reflect.Struct:
407		return newStructEncoder(t)
408	case reflect.Map:
409		return newMapEncoder(t)
410	case reflect.Slice:
411		return newSliceEncoder(t)
412	case reflect.Array:
413		return newArrayEncoder(t)
414	case reflect.Ptr:
415		return newPtrEncoder(t)
416	default:
417		return unsupportedTypeEncoder
418	}
419}
420
421func invalidValueEncoder(e *encodeState, v reflect.Value, _ encOpts) {
422	e.WriteString("null")
423}
424
425func marshalerEncoder(e *encodeState, v reflect.Value, opts encOpts) {
426	if v.Kind() == reflect.Ptr && v.IsNil() {
427		e.WriteString("null")
428		return
429	}
430	m := v.Interface().(Marshaler)
431	b, err := m.MarshalJSON()
432	if err == nil {
433		// copy JSON into buffer, checking validity.
434		err = compact(&e.Buffer, b, opts.escapeHTML)
435	}
436	if err != nil {
437		e.error(&MarshalerError{v.Type(), err})
438	}
439}
440
441func addrMarshalerEncoder(e *encodeState, v reflect.Value, _ encOpts) {
442	va := v.Addr()
443	if va.IsNil() {
444		e.WriteString("null")
445		return
446	}
447	m := va.Interface().(Marshaler)
448	b, err := m.MarshalJSON()
449	if err == nil {
450		// copy JSON into buffer, checking validity.
451		err = compact(&e.Buffer, b, true)
452	}
453	if err != nil {
454		e.error(&MarshalerError{v.Type(), err})
455	}
456}
457
458func textMarshalerEncoder(e *encodeState, v reflect.Value, opts encOpts) {
459	if v.Kind() == reflect.Ptr && v.IsNil() {
460		e.WriteString("null")
461		return
462	}
463	m := v.Interface().(encoding.TextMarshaler)
464	b, err := m.MarshalText()
465	if err != nil {
466		e.error(&MarshalerError{v.Type(), err})
467	}
468	e.stringBytes(b, opts.escapeHTML)
469}
470
471func addrTextMarshalerEncoder(e *encodeState, v reflect.Value, opts encOpts) {
472	va := v.Addr()
473	if va.IsNil() {
474		e.WriteString("null")
475		return
476	}
477	m := va.Interface().(encoding.TextMarshaler)
478	b, err := m.MarshalText()
479	if err != nil {
480		e.error(&MarshalerError{v.Type(), err})
481	}
482	e.stringBytes(b, opts.escapeHTML)
483}
484
485func boolEncoder(e *encodeState, v reflect.Value, opts encOpts) {
486	if opts.quoted {
487		e.WriteByte('"')
488	}
489	if v.Bool() {
490		e.WriteString("true")
491	} else {
492		e.WriteString("false")
493	}
494	if opts.quoted {
495		e.WriteByte('"')
496	}
497}
498
499func intEncoder(e *encodeState, v reflect.Value, opts encOpts) {
500	b := strconv.AppendInt(e.scratch[:0], v.Int(), 10)
501	if opts.quoted {
502		e.WriteByte('"')
503	}
504	e.Write(b)
505	if opts.quoted {
506		e.WriteByte('"')
507	}
508}
509
510func uintEncoder(e *encodeState, v reflect.Value, opts encOpts) {
511	b := strconv.AppendUint(e.scratch[:0], v.Uint(), 10)
512	if opts.quoted {
513		e.WriteByte('"')
514	}
515	e.Write(b)
516	if opts.quoted {
517		e.WriteByte('"')
518	}
519}
520
521type floatEncoder int // number of bits
522
523func (bits floatEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
524	f := v.Float()
525	if math.IsInf(f, 0) || math.IsNaN(f) {
526		e.error(&UnsupportedValueError{v, strconv.FormatFloat(f, 'g', -1, int(bits))})
527	}
528	b := strconv.AppendFloat(e.scratch[:0], f, 'g', -1, int(bits))
529	if opts.quoted {
530		e.WriteByte('"')
531	}
532	e.Write(b)
533	if opts.quoted {
534		e.WriteByte('"')
535	}
536}
537
538var (
539	float32Encoder = (floatEncoder(32)).encode
540	float64Encoder = (floatEncoder(64)).encode
541)
542
543func stringEncoder(e *encodeState, v reflect.Value, opts encOpts) {
544	if v.Type() == numberType {
545		numStr := v.String()
546		// In Go1.5 the empty string encodes to "0", while this is not a valid number literal
547		// we keep compatibility so check validity after this.
548		if numStr == "" {
549			numStr = "0" // Number's zero-val
550		}
551		if !isValidNumber(numStr) {
552			e.error(fmt.Errorf("json: invalid number literal %q", numStr))
553		}
554		e.WriteString(numStr)
555		return
556	}
557	if opts.quoted {
558		sb, err := Marshal(v.String())
559		if err != nil {
560			e.error(err)
561		}
562		e.string(string(sb), opts.escapeHTML)
563	} else {
564		e.string(v.String(), opts.escapeHTML)
565	}
566}
567
568func interfaceEncoder(e *encodeState, v reflect.Value, opts encOpts) {
569	if v.IsNil() {
570		e.WriteString("null")
571		return
572	}
573	e.reflectValue(v.Elem(), opts)
574}
575
576func unsupportedTypeEncoder(e *encodeState, v reflect.Value, _ encOpts) {
577	e.error(&UnsupportedTypeError{v.Type()})
578}
579
580type structEncoder struct {
581	fields    []field
582	fieldEncs []encoderFunc
583}
584
585func (se *structEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
586	e.WriteByte('{')
587	first := true
588	for i, f := range se.fields {
589		fv := fieldByIndex(v, f.index)
590		if !fv.IsValid() || f.omitEmpty && isEmptyValue(fv) {
591			continue
592		}
593		if first {
594			first = false
595		} else {
596			e.WriteByte(',')
597		}
598		e.string(f.name, opts.escapeHTML)
599		e.WriteByte(':')
600		opts.quoted = f.quoted
601		se.fieldEncs[i](e, fv, opts)
602	}
603	e.WriteByte('}')
604}
605
606func newStructEncoder(t reflect.Type) encoderFunc {
607	fields := cachedTypeFields(t)
608	se := &structEncoder{
609		fields:    fields,
610		fieldEncs: make([]encoderFunc, len(fields)),
611	}
612	for i, f := range fields {
613		se.fieldEncs[i] = typeEncoder(typeByIndex(t, f.index))
614	}
615	return se.encode
616}
617
618type mapEncoder struct {
619	elemEnc encoderFunc
620}
621
622func (me *mapEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
623	if v.IsNil() {
624		e.WriteString("null")
625		return
626	}
627	e.WriteByte('{')
628
629	// Extract and sort the keys.
630	keys := v.MapKeys()
631	sv := make([]reflectWithString, len(keys))
632	for i, v := range keys {
633		sv[i].v = v
634		if err := sv[i].resolve(); err != nil {
635			e.error(&MarshalerError{v.Type(), err})
636		}
637	}
638	sort.Sort(byString(sv))
639
640	for i, kv := range sv {
641		if i > 0 {
642			e.WriteByte(',')
643		}
644		e.string(kv.s, opts.escapeHTML)
645		e.WriteByte(':')
646		me.elemEnc(e, v.MapIndex(kv.v), opts)
647	}
648	e.WriteByte('}')
649}
650
651func newMapEncoder(t reflect.Type) encoderFunc {
652	switch t.Key().Kind() {
653	case reflect.String,
654		reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
655		reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
656	default:
657		if !t.Key().Implements(textMarshalerType) {
658			return unsupportedTypeEncoder
659		}
660	}
661	me := &mapEncoder{typeEncoder(t.Elem())}
662	return me.encode
663}
664
665func encodeByteSlice(e *encodeState, v reflect.Value, _ encOpts) {
666	if v.IsNil() {
667		e.WriteString("null")
668		return
669	}
670	s := v.Bytes()
671	e.WriteByte('"')
672	if len(s) < 1024 {
673		// for small buffers, using Encode directly is much faster.
674		dst := make([]byte, base64.StdEncoding.EncodedLen(len(s)))
675		base64.StdEncoding.Encode(dst, s)
676		e.Write(dst)
677	} else {
678		// for large buffers, avoid unnecessary extra temporary
679		// buffer space.
680		enc := base64.NewEncoder(base64.StdEncoding, e)
681		enc.Write(s)
682		enc.Close()
683	}
684	e.WriteByte('"')
685}
686
687// sliceEncoder just wraps an arrayEncoder, checking to make sure the value isn't nil.
688type sliceEncoder struct {
689	arrayEnc encoderFunc
690}
691
692func (se *sliceEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
693	if v.IsNil() {
694		e.WriteString("null")
695		return
696	}
697	se.arrayEnc(e, v, opts)
698}
699
700func newSliceEncoder(t reflect.Type) encoderFunc {
701	// Byte slices get special treatment; arrays don't.
702	if t.Elem().Kind() == reflect.Uint8 {
703		p := reflect.PtrTo(t.Elem())
704		if !p.Implements(marshalerType) && !p.Implements(textMarshalerType) {
705			return encodeByteSlice
706		}
707	}
708	enc := &sliceEncoder{newArrayEncoder(t)}
709	return enc.encode
710}
711
712type arrayEncoder struct {
713	elemEnc encoderFunc
714}
715
716func (ae *arrayEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
717	e.WriteByte('[')
718	n := v.Len()
719	for i := 0; i < n; i++ {
720		if i > 0 {
721			e.WriteByte(',')
722		}
723		ae.elemEnc(e, v.Index(i), opts)
724	}
725	e.WriteByte(']')
726}
727
728func newArrayEncoder(t reflect.Type) encoderFunc {
729	enc := &arrayEncoder{typeEncoder(t.Elem())}
730	return enc.encode
731}
732
733type ptrEncoder struct {
734	elemEnc encoderFunc
735}
736
737func (pe *ptrEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
738	if v.IsNil() {
739		e.WriteString("null")
740		return
741	}
742	pe.elemEnc(e, v.Elem(), opts)
743}
744
745func newPtrEncoder(t reflect.Type) encoderFunc {
746	enc := &ptrEncoder{typeEncoder(t.Elem())}
747	return enc.encode
748}
749
750type condAddrEncoder struct {
751	canAddrEnc, elseEnc encoderFunc
752}
753
754func (ce *condAddrEncoder) encode(e *encodeState, v reflect.Value, opts encOpts) {
755	if v.CanAddr() {
756		ce.canAddrEnc(e, v, opts)
757	} else {
758		ce.elseEnc(e, v, opts)
759	}
760}
761
762// newCondAddrEncoder returns an encoder that checks whether its value
763// CanAddr and delegates to canAddrEnc if so, else to elseEnc.
764func newCondAddrEncoder(canAddrEnc, elseEnc encoderFunc) encoderFunc {
765	enc := &condAddrEncoder{canAddrEnc: canAddrEnc, elseEnc: elseEnc}
766	return enc.encode
767}
768
769func isValidTag(s string) bool {
770	if s == "" {
771		return false
772	}
773	for _, c := range s {
774		switch {
775		case strings.ContainsRune("!#$%&()*+-./:<=>?@[]^_{|}~ ", c):
776			// Backslash and quote chars are reserved, but
777			// otherwise any punctuation chars are allowed
778			// in a tag name.
779		default:
780			if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
781				return false
782			}
783		}
784	}
785	return true
786}
787
788func fieldByIndex(v reflect.Value, index []int) reflect.Value {
789	for _, i := range index {
790		if v.Kind() == reflect.Ptr {
791			if v.IsNil() {
792				return reflect.Value{}
793			}
794			v = v.Elem()
795		}
796		v = v.Field(i)
797	}
798	return v
799}
800
801func typeByIndex(t reflect.Type, index []int) reflect.Type {
802	for _, i := range index {
803		if t.Kind() == reflect.Ptr {
804			t = t.Elem()
805		}
806		t = t.Field(i).Type
807	}
808	return t
809}
810
811type reflectWithString struct {
812	v reflect.Value
813	s string
814}
815
816func (w *reflectWithString) resolve() error {
817	if w.v.Kind() == reflect.String {
818		w.s = w.v.String()
819		return nil
820	}
821	if tm, ok := w.v.Interface().(encoding.TextMarshaler); ok {
822		buf, err := tm.MarshalText()
823		w.s = string(buf)
824		return err
825	}
826	switch w.v.Kind() {
827	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
828		w.s = strconv.FormatInt(w.v.Int(), 10)
829		return nil
830	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
831		w.s = strconv.FormatUint(w.v.Uint(), 10)
832		return nil
833	}
834	panic("unexpected map key type")
835}
836
837// byString is a slice of reflectWithString where the reflect.Value is either
838// a string or an encoding.TextMarshaler.
839// It implements the methods to sort by string.
840type byString []reflectWithString
841
842func (sv byString) Len() int           { return len(sv) }
843func (sv byString) Swap(i, j int)      { sv[i], sv[j] = sv[j], sv[i] }
844func (sv byString) Less(i, j int) bool { return sv[i].s < sv[j].s }
845
846// NOTE: keep in sync with stringBytes below.
847func (e *encodeState) string(s string, escapeHTML bool) int {
848	len0 := e.Len()
849	e.WriteByte('"')
850	start := 0
851	for i := 0; i < len(s); {
852		if b := s[i]; b < utf8.RuneSelf {
853			if 0x20 <= b && b != '\\' && b != '"' &&
854				(!escapeHTML || b != '<' && b != '>' && b != '&') {
855				i++
856				continue
857			}
858			if start < i {
859				e.WriteString(s[start:i])
860			}
861			switch b {
862			case '\\', '"':
863				e.WriteByte('\\')
864				e.WriteByte(b)
865			case '\n':
866				e.WriteByte('\\')
867				e.WriteByte('n')
868			case '\r':
869				e.WriteByte('\\')
870				e.WriteByte('r')
871			case '\t':
872				e.WriteByte('\\')
873				e.WriteByte('t')
874			default:
875				// This encodes bytes < 0x20 except for \t, \n and \r.
876				// If escapeHTML is set, it also escapes <, >, and &
877				// because they can lead to security holes when
878				// user-controlled strings are rendered into JSON
879				// and served to some browsers.
880				e.WriteString(`\u00`)
881				e.WriteByte(hex[b>>4])
882				e.WriteByte(hex[b&0xF])
883			}
884			i++
885			start = i
886			continue
887		}
888		c, size := utf8.DecodeRuneInString(s[i:])
889		if c == utf8.RuneError && size == 1 {
890			if start < i {
891				e.WriteString(s[start:i])
892			}
893			e.WriteString(`\ufffd`)
894			i += size
895			start = i
896			continue
897		}
898		// U+2028 is LINE SEPARATOR.
899		// U+2029 is PARAGRAPH SEPARATOR.
900		// They are both technically valid characters in JSON strings,
901		// but don't work in JSONP, which has to be evaluated as JavaScript,
902		// and can lead to security holes there. It is valid JSON to
903		// escape them, so we do so unconditionally.
904		// See http://timelessrepo.com/json-isnt-a-javascript-subset for discussion.
905		if c == '\u2028' || c == '\u2029' {
906			if start < i {
907				e.WriteString(s[start:i])
908			}
909			e.WriteString(`\u202`)
910			e.WriteByte(hex[c&0xF])
911			i += size
912			start = i
913			continue
914		}
915		i += size
916	}
917	if start < len(s) {
918		e.WriteString(s[start:])
919	}
920	e.WriteByte('"')
921	return e.Len() - len0
922}
923
924// NOTE: keep in sync with string above.
925func (e *encodeState) stringBytes(s []byte, escapeHTML bool) int {
926	len0 := e.Len()
927	e.WriteByte('"')
928	start := 0
929	for i := 0; i < len(s); {
930		if b := s[i]; b < utf8.RuneSelf {
931			if 0x20 <= b && b != '\\' && b != '"' &&
932				(!escapeHTML || b != '<' && b != '>' && b != '&') {
933				i++
934				continue
935			}
936			if start < i {
937				e.Write(s[start:i])
938			}
939			switch b {
940			case '\\', '"':
941				e.WriteByte('\\')
942				e.WriteByte(b)
943			case '\n':
944				e.WriteByte('\\')
945				e.WriteByte('n')
946			case '\r':
947				e.WriteByte('\\')
948				e.WriteByte('r')
949			case '\t':
950				e.WriteByte('\\')
951				e.WriteByte('t')
952			default:
953				// This encodes bytes < 0x20 except for \t, \n and \r.
954				// If escapeHTML is set, it also escapes <, >, and &
955				// because they can lead to security holes when
956				// user-controlled strings are rendered into JSON
957				// and served to some browsers.
958				e.WriteString(`\u00`)
959				e.WriteByte(hex[b>>4])
960				e.WriteByte(hex[b&0xF])
961			}
962			i++
963			start = i
964			continue
965		}
966		c, size := utf8.DecodeRune(s[i:])
967		if c == utf8.RuneError && size == 1 {
968			if start < i {
969				e.Write(s[start:i])
970			}
971			e.WriteString(`\ufffd`)
972			i += size
973			start = i
974			continue
975		}
976		// U+2028 is LINE SEPARATOR.
977		// U+2029 is PARAGRAPH SEPARATOR.
978		// They are both technically valid characters in JSON strings,
979		// but don't work in JSONP, which has to be evaluated as JavaScript,
980		// and can lead to security holes there. It is valid JSON to
981		// escape them, so we do so unconditionally.
982		// See http://timelessrepo.com/json-isnt-a-javascript-subset for discussion.
983		if c == '\u2028' || c == '\u2029' {
984			if start < i {
985				e.Write(s[start:i])
986			}
987			e.WriteString(`\u202`)
988			e.WriteByte(hex[c&0xF])
989			i += size
990			start = i
991			continue
992		}
993		i += size
994	}
995	if start < len(s) {
996		e.Write(s[start:])
997	}
998	e.WriteByte('"')
999	return e.Len() - len0
1000}
1001
1002// A field represents a single field found in a struct.
1003type field struct {
1004	name      string
1005	nameBytes []byte                 // []byte(name)
1006	equalFold func(s, t []byte) bool // bytes.EqualFold or equivalent
1007
1008	tag       bool
1009	index     []int
1010	typ       reflect.Type
1011	omitEmpty bool
1012	quoted    bool
1013}
1014
1015func fillField(f field) field {
1016	f.nameBytes = []byte(f.name)
1017	f.equalFold = foldFunc(f.nameBytes)
1018	return f
1019}
1020
1021// byName sorts field by name, breaking ties with depth,
1022// then breaking ties with "name came from json tag", then
1023// breaking ties with index sequence.
1024type byName []field
1025
1026func (x byName) Len() int { return len(x) }
1027
1028func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
1029
1030func (x byName) Less(i, j int) bool {
1031	if x[i].name != x[j].name {
1032		return x[i].name < x[j].name
1033	}
1034	if len(x[i].index) != len(x[j].index) {
1035		return len(x[i].index) < len(x[j].index)
1036	}
1037	if x[i].tag != x[j].tag {
1038		return x[i].tag
1039	}
1040	return byIndex(x).Less(i, j)
1041}
1042
1043// byIndex sorts field by index sequence.
1044type byIndex []field
1045
1046func (x byIndex) Len() int { return len(x) }
1047
1048func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
1049
1050func (x byIndex) Less(i, j int) bool {
1051	for k, xik := range x[i].index {
1052		if k >= len(x[j].index) {
1053			return false
1054		}
1055		if xik != x[j].index[k] {
1056			return xik < x[j].index[k]
1057		}
1058	}
1059	return len(x[i].index) < len(x[j].index)
1060}
1061
1062// typeFields returns a list of fields that JSON should recognize for the given type.
1063// The algorithm is breadth-first search over the set of structs to include - the top struct
1064// and then any reachable anonymous structs.
1065func typeFields(t reflect.Type) []field {
1066	// Anonymous fields to explore at the current level and the next.
1067	current := []field{}
1068	next := []field{{typ: t}}
1069
1070	// Count of queued names for current level and the next.
1071	count := map[reflect.Type]int{}
1072	nextCount := map[reflect.Type]int{}
1073
1074	// Types already visited at an earlier level.
1075	visited := map[reflect.Type]bool{}
1076
1077	// Fields found.
1078	var fields []field
1079
1080	for len(next) > 0 {
1081		current, next = next, current[:0]
1082		count, nextCount = nextCount, map[reflect.Type]int{}
1083
1084		for _, f := range current {
1085			if visited[f.typ] {
1086				continue
1087			}
1088			visited[f.typ] = true
1089
1090			// Scan f.typ for fields to include.
1091			for i := 0; i < f.typ.NumField(); i++ {
1092				sf := f.typ.Field(i)
1093				if sf.PkgPath != "" && !sf.Anonymous { // unexported
1094					continue
1095				}
1096				tag := sf.Tag.Get("json")
1097				if tag == "-" {
1098					continue
1099				}
1100				name, opts := parseTag(tag)
1101				if !isValidTag(name) {
1102					name = ""
1103				}
1104				index := make([]int, len(f.index)+1)
1105				copy(index, f.index)
1106				index[len(f.index)] = i
1107
1108				ft := sf.Type
1109				if ft.Name() == "" && ft.Kind() == reflect.Ptr {
1110					// Follow pointer.
1111					ft = ft.Elem()
1112				}
1113
1114				// Only strings, floats, integers, and booleans can be quoted.
1115				quoted := false
1116				if opts.Contains("string") {
1117					switch ft.Kind() {
1118					case reflect.Bool,
1119						reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
1120						reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64,
1121						reflect.Float32, reflect.Float64,
1122						reflect.String:
1123						quoted = true
1124					}
1125				}
1126
1127				// Record found field and index sequence.
1128				if name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
1129					tagged := name != ""
1130					if name == "" {
1131						name = sf.Name
1132					}
1133					fields = append(fields, fillField(field{
1134						name:      name,
1135						tag:       tagged,
1136						index:     index,
1137						typ:       ft,
1138						omitEmpty: opts.Contains("omitempty"),
1139						quoted:    quoted,
1140					}))
1141					if count[f.typ] > 1 {
1142						// If there were multiple instances, add a second,
1143						// so that the annihilation code will see a duplicate.
1144						// It only cares about the distinction between 1 or 2,
1145						// so don't bother generating any more copies.
1146						fields = append(fields, fields[len(fields)-1])
1147					}
1148					continue
1149				}
1150
1151				// Record new anonymous struct to explore in next round.
1152				nextCount[ft]++
1153				if nextCount[ft] == 1 {
1154					next = append(next, fillField(field{name: ft.Name(), index: index, typ: ft}))
1155				}
1156			}
1157		}
1158	}
1159
1160	sort.Sort(byName(fields))
1161
1162	// Delete all fields that are hidden by the Go rules for embedded fields,
1163	// except that fields with JSON tags are promoted.
1164
1165	// The fields are sorted in primary order of name, secondary order
1166	// of field index length. Loop over names; for each name, delete
1167	// hidden fields by choosing the one dominant field that survives.
1168	out := fields[:0]
1169	for advance, i := 0, 0; i < len(fields); i += advance {
1170		// One iteration per name.
1171		// Find the sequence of fields with the name of this first field.
1172		fi := fields[i]
1173		name := fi.name
1174		for advance = 1; i+advance < len(fields); advance++ {
1175			fj := fields[i+advance]
1176			if fj.name != name {
1177				break
1178			}
1179		}
1180		if advance == 1 { // Only one field with this name
1181			out = append(out, fi)
1182			continue
1183		}
1184		dominant, ok := dominantField(fields[i : i+advance])
1185		if ok {
1186			out = append(out, dominant)
1187		}
1188	}
1189
1190	fields = out
1191	sort.Sort(byIndex(fields))
1192
1193	return fields
1194}
1195
1196// dominantField looks through the fields, all of which are known to
1197// have the same name, to find the single field that dominates the
1198// others using Go's embedding rules, modified by the presence of
1199// JSON tags. If there are multiple top-level fields, the boolean
1200// will be false: This condition is an error in Go and we skip all
1201// the fields.
1202func dominantField(fields []field) (field, bool) {
1203	// The fields are sorted in increasing index-length order. The winner
1204	// must therefore be one with the shortest index length. Drop all
1205	// longer entries, which is easy: just truncate the slice.
1206	length := len(fields[0].index)
1207	tagged := -1 // Index of first tagged field.
1208	for i, f := range fields {
1209		if len(f.index) > length {
1210			fields = fields[:i]
1211			break
1212		}
1213		if f.tag {
1214			if tagged >= 0 {
1215				// Multiple tagged fields at the same level: conflict.
1216				// Return no field.
1217				return field{}, false
1218			}
1219			tagged = i
1220		}
1221	}
1222	if tagged >= 0 {
1223		return fields[tagged], true
1224	}
1225	// All remaining fields have the same length. If there's more than one,
1226	// we have a conflict (two fields named "X" at the same level) and we
1227	// return no field.
1228	if len(fields) > 1 {
1229		return field{}, false
1230	}
1231	return fields[0], true
1232}
1233
1234var fieldCache struct {
1235	value atomic.Value // map[reflect.Type][]field
1236	mu    sync.Mutex   // used only by writers
1237}
1238
1239// cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
1240func cachedTypeFields(t reflect.Type) []field {
1241	m, _ := fieldCache.value.Load().(map[reflect.Type][]field)
1242	f := m[t]
1243	if f != nil {
1244		return f
1245	}
1246
1247	// Compute fields without lock.
1248	// Might duplicate effort but won't hold other computations back.
1249	f = typeFields(t)
1250	if f == nil {
1251		f = []field{}
1252	}
1253
1254	fieldCache.mu.Lock()
1255	m, _ = fieldCache.value.Load().(map[reflect.Type][]field)
1256	newM := make(map[reflect.Type][]field, len(m)+1)
1257	for k, v := range m {
1258		newM[k] = v
1259	}
1260	newM[t] = f
1261	fieldCache.value.Store(newM)
1262	fieldCache.mu.Unlock()
1263	return f
1264}
1265