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