encode.go - third_party/canonical-json-go - Git at Google

 // Copyright 2010 The Go Authors.  All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package cjson

 import (
 	"bytes"
 	"encoding/base64"
 	"reflect"
 	"runtime"
 	"sort"
 	"strconv"
 	"strings"
 	"sync"
 	"unicode"
 	"unicode/utf8"
 )

 func Marshal(v interface{}) ([]byte, error) {
 	e := &encodeState{}
 	err := e.marshal(v)
 	if err != nil {
 		return nil, err
 	}
 	return e.Bytes(), nil
 }

 // Marshaler is the interface implemented by objects that
 // can marshal themselves into valid JSON.
 type Marshaler interface {
 	MarshalJSON() ([]byte, error)
 }

 // An UnsupportedTypeError is returned by Marshal when attempting
 // to encode an unsupported value type.
 type UnsupportedTypeError struct {
 	Type reflect.Type
 }

 func (e *UnsupportedTypeError) Error() string {
 	return "json: unsupported type: " + e.Type.String()
 }

 type UnsupportedValueError struct {
 	Value reflect.Value
 	Str   string
 }

 func (e *UnsupportedValueError) Error() string {
 	return "json: unsupported value: " + e.Str
 }

 type InvalidUTF8Error struct {
 	S string
 }

 func (e *InvalidUTF8Error) Error() string {
 	return "json: invalid UTF-8 in string: " + strconv.Quote(e.S)
 }

 type MarshalerError struct {
 	Type reflect.Type
 	Err  error
 }

 func (e *MarshalerError) Error() string {
 	return "json: error calling MarshalJSON for type " + e.Type.String() + ": " + e.Err.Error()
 }

 var hex = "0123456789abcdef"

 var numberType = reflect.TypeOf(Number(""))

 // A Number represents a JSON number literal.
 type Number string

 // String returns the literal text of the number.
 func (n Number) String() string { return string(n) }

 // Float64 returns the number as a float64.
 func (n Number) Float64() (float64, error) {
 	return strconv.ParseFloat(string(n), 64)
 }

 // Int64 returns the number as an int64.
 func (n Number) Int64() (int64, error) {
 	return strconv.ParseInt(string(n), 10, 64)
 }

 // An encodeState encodes JSON into a bytes.Buffer.
 type encodeState struct {
 	bytes.Buffer // accumulated output
 	scratch      [64]byte
 }

 func (e *encodeState) marshal(v interface{}) (err error) {
 	defer func() {
 		if r := recover(); r != nil {
 			if _, ok := r.(runtime.Error); ok {
 				panic(r)
 			}
 			err = r.(error)
 		}
 	}()
 	e.reflectValue(reflect.ValueOf(v))
 	return nil
 }

 func (e *encodeState) error(err error) {
 	panic(err)
 }

 var byteSliceType = reflect.TypeOf([]byte(nil))

 func isEmptyValue(v reflect.Value) bool {
 	switch v.Kind() {
 	case reflect.Array, reflect.Map, reflect.Slice, reflect.String:
 		return v.Len() == 0
 	case reflect.Bool:
 		return !v.Bool()
 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
 		return v.Int() == 0
 	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
 		return v.Uint() == 0
 	case reflect.Float32, reflect.Float64:
 		return v.Float() == 0
 	case reflect.Interface, reflect.Ptr:
 		return v.IsNil()
 	}
 	return false
 }

 func (e *encodeState) reflectValue(v reflect.Value) {
 	e.reflectValueQuoted(v, false)
 }

 // reflectValueQuoted writes the value in v to the output.
 // If quoted is true, the serialization is wrapped in a JSON string.
 func (e *encodeState) reflectValueQuoted(v reflect.Value, quoted bool) {
 	if !v.IsValid() {
 		e.WriteString("null")
 		return
 	}

 	m, ok := v.Interface().(Marshaler)
 	if !ok {
 		// T doesn't match the interface. Check against *T too.
 		if v.Kind() != reflect.Ptr && v.CanAddr() {
 			m, ok = v.Addr().Interface().(Marshaler)
 			if ok {
 				v = v.Addr()
 			}
 		}
 	}
 	if ok && (v.Kind() != reflect.Ptr || !v.IsNil()) {
 		b, err := m.MarshalJSON()
 		if err != nil {
 			e.error(&MarshalerError{v.Type(), err})
 		}
 		// TODO: canonicalize this json
 		e.Buffer.Write(b)
 		return
 	}

 	writeString := (*encodeState).WriteString
 	if quoted {
 		writeString = (*encodeState).string
 	}

 	switch v.Kind() {
 	case reflect.Bool:
 		x := v.Bool()
 		if x {
 			writeString(e, "true")
 		} else {
 			writeString(e, "false")
 		}

 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
 		b := strconv.AppendInt(e.scratch[:0], v.Int(), 10)
 		if quoted {
 			writeString(e, string(b))
 		} else {
 			e.Write(b)
 		}
 	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
 		b := strconv.AppendUint(e.scratch[:0], v.Uint(), 10)
 		if quoted {
 			writeString(e, string(b))
 		} else {
 			e.Write(b)
 		}
 	case reflect.Float32, reflect.Float64:
 		e.error(&UnsupportedValueError{v, "floating point number"})
 	case reflect.String:
 		if v.Type() == numberType {
 			numStr := v.String()
 			if numStr == "" {
 				numStr = "0" // Number's zero-val
 			}
 			e.WriteString(numStr)
 			break
 		}
 		if quoted {
 			sb, err := Marshal(v.String())
 			if err != nil {
 				e.error(err)
 			}
 			e.string(string(sb))
 		} else {
 			e.string(v.String())
 		}

 	case reflect.Struct:
 		e.WriteByte('{')
 		first := true
 		for _, f := range cachedTypeFields(v.Type()) {
 			fv := fieldByIndex(v, f.index)
 			if !fv.IsValid() || f.omitEmpty && isEmptyValue(fv) {
 				continue
 			}
 			if first {
 				first = false
 			} else {
 				e.WriteByte(',')
 			}
 			e.string(f.name)
 			e.WriteByte(':')
 			e.reflectValueQuoted(fv, f.quoted)
 		}
 		e.WriteByte('}')

 	case reflect.Map:
 		if v.Type().Key().Kind() != reflect.String {
 			e.error(&UnsupportedTypeError{v.Type()})
 		}
 		if v.IsNil() {
 			e.WriteString("null")
 			break
 		}
 		e.WriteByte('{')
 		var sv stringValues = v.MapKeys()
 		sort.Sort(sv)
 		for i, k := range sv {
 			if i > 0 {
 				e.WriteByte(',')
 			}
 			e.string(k.String())
 			e.WriteByte(':')
 			e.reflectValue(v.MapIndex(k))
 		}
 		e.WriteByte('}')

 	case reflect.Slice:
 		if v.IsNil() {
 			e.WriteString("null")
 			break
 		}
 		if v.Type().Elem().Kind() == reflect.Uint8 {
 			// Byte slices get special treatment; arrays don't.
 			s := v.Bytes()
 			e.WriteByte('"')
 			if len(s) < 1024 {
 				// for small buffers, using Encode directly is much faster.
 				dst := make([]byte, base64.StdEncoding.EncodedLen(len(s)))
 				base64.StdEncoding.Encode(dst, s)
 				e.Write(dst)
 			} else {
 				// for large buffers, avoid unnecessary extra temporary
 				// buffer space.
 				enc := base64.NewEncoder(base64.StdEncoding, e)
 				enc.Write(s)
 				enc.Close()
 			}
 			e.WriteByte('"')
 			break
 		}
 		// Slices can be marshalled as nil, but otherwise are handled
 		// as arrays.
 		fallthrough
 	case reflect.Array:
 		e.WriteByte('[')
 		n := v.Len()
 		for i := 0; i < n; i++ {
 			if i > 0 {
 				e.WriteByte(',')
 			}
 			e.reflectValue(v.Index(i))
 		}
 		e.WriteByte(']')

 	case reflect.Interface, reflect.Ptr:
 		if v.IsNil() {
 			e.WriteString("null")
 			return
 		}
 		e.reflectValue(v.Elem())

 	default:
 		e.error(&UnsupportedTypeError{v.Type()})
 	}
 	return
 }

 func isValidTag(s string) bool {
 	if s == "" {
 		return false
 	}
 	for _, c := range s {
 		switch {
 		case strings.ContainsRune("!#$%&()*+-./:<=>?@[]^_{|}~ ", c):
 			// Backslash and quote chars are reserved, but
 			// otherwise any punctuation chars are allowed
 			// in a tag name.
 		default:
 			if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
 				return false
 			}
 		}
 	}
 	return true
 }

 func fieldByIndex(v reflect.Value, index []int) reflect.Value {
 	for _, i := range index {
 		if v.Kind() == reflect.Ptr {
 			if v.IsNil() {
 				return reflect.Value{}
 			}
 			v = v.Elem()
 		}
 		v = v.Field(i)
 	}
 	return v
 }

 // stringValues is a slice of reflect.Value holding *reflect.StringValue.
 // It implements the methods to sort by string.
 type stringValues []reflect.Value

 func (sv stringValues) Len() int           { return len(sv) }
 func (sv stringValues) Swap(i, j int)      { sv[i], sv[j] = sv[j], sv[i] }
 func (sv stringValues) Less(i, j int) bool { return sv.get(i) < sv.get(j) }
 func (sv stringValues) get(i int) string   { return sv[i].String() }

 func (e *encodeState) string(s string) (int, error) {
 	len0 := e.Len()
 	e.WriteByte('"')
 	start := 0
 	for i := 0; i < len(s); {
 		if b := s[i]; b < utf8.RuneSelf {
 			if b != '\\' && b != '"' {
 				i++
 				continue
 			}
 			if start < i {
 				e.WriteString(s[start:i])
 			}
 			switch b {
 			case '\\', '"':
 				e.WriteByte('\\')
 				e.WriteByte(b)
 			}
 			i++
 			start = i
 			continue
 		}
 		c, size := utf8.DecodeRuneInString(s[i:])
 		if c == utf8.RuneError && size == 1 {
 			e.error(&InvalidUTF8Error{s})
 		}
 		i += size
 	}
 	if start < len(s) {
 		e.WriteString(s[start:])
 	}
 	e.WriteByte('"')
 	return e.Len() - len0, nil
 }

 // A field represents a single field found in a struct.
 type field struct {
 	name      string
 	tag       bool
 	index     []int
 	typ       reflect.Type
 	omitEmpty bool
 	quoted    bool
 }

 // byName sorts field by name, breaking ties with depth,
 // then breaking ties with "name came from json tag", then
 // breaking ties with index sequence.
 type byName []field

 func (x byName) Len() int { return len(x) }

 func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

 func (x byName) Less(i, j int) bool {
 	if x[i].name != x[j].name {
 		return x[i].name < x[j].name
 	}
 	if len(x[i].index) != len(x[j].index) {
 		return len(x[i].index) < len(x[j].index)
 	}
 	if x[i].tag != x[j].tag {
 		return x[i].tag
 	}
 	return byIndex(x).Less(i, j)
 }

 // byIndex sorts field by index sequence.
 type byIndex []field

 func (x byIndex) Len() int { return len(x) }

 func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

 func (x byIndex) Less(i, j int) bool {
 	for k, xik := range x[i].index {
 		if k >= len(x[j].index) {
 			return false
 		}
 		if xik != x[j].index[k] {
 			return xik < x[j].index[k]
 		}
 	}
 	return len(x[i].index) < len(x[j].index)
 }

 // typeFields returns a list of fields that JSON should recognize for the given type.
 // The algorithm is breadth-first search over the set of structs to include - the top struct
 // and then any reachable anonymous structs.
 func typeFields(t reflect.Type) []field {
 	// Anonymous fields to explore at the current level and the next.
 	current := []field{}
 	next := []field{{typ: t}}

 	// Count of queued names for current level and the next.
 	count := map[reflect.Type]int{}
 	nextCount := map[reflect.Type]int{}

 	// Types already visited at an earlier level.
 	visited := map[reflect.Type]bool{}

 	// Fields found.
 	var fields []field

 	for len(next) > 0 {
 		current, next = next, current[:0]
 		count, nextCount = nextCount, map[reflect.Type]int{}

 		for _, f := range current {
 			if visited[f.typ] {
 				continue
 			}
 			visited[f.typ] = true

 			// Scan f.typ for fields to include.
 			for i := 0; i < f.typ.NumField(); i++ {
 				sf := f.typ.Field(i)
 				if sf.PkgPath != "" { // unexported
 					continue
 				}
 				tag := sf.Tag.Get("json")
 				if tag == "-" {
 					continue
 				}
 				name, opts := parseTag(tag)
 				if !isValidTag(name) {
 					name = ""
 				}
 				index := make([]int, len(f.index)+1)
 				copy(index, f.index)
 				index[len(f.index)] = i

 				ft := sf.Type
 				if ft.Name() == "" && ft.Kind() == reflect.Ptr {
 					// Follow pointer.
 					ft = ft.Elem()
 				}

 				// Record found field and index sequence.
 				if name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
 					tagged := name != ""
 					if name == "" {
 						name = sf.Name
 					}
 					fields = append(fields, field{name, tagged, index, ft,
 						opts.Contains("omitempty"), opts.Contains("string")})
 					if count[f.typ] > 1 {
 						// If there were multiple instances, add a second,
 						// so that the annihilation code will see a duplicate.
 						// It only cares about the distinction between 1 or 2,
 						// so don't bother generating any more copies.
 						fields = append(fields, fields[len(fields)-1])
 					}
 					continue
 				}

 				// Record new anonymous struct to explore in next round.
 				nextCount[ft]++
 				if nextCount[ft] == 1 {
 					next = append(next, field{name: ft.Name(), index: index, typ: ft})
 				}
 			}
 		}
 	}

 	sort.Sort(byName(fields))

 	// Remove fields with annihilating name collisions
 	// and also fields shadowed by fields with explicit JSON tags.
 	name := ""
 	out := fields[:0]
 	for _, f := range fields {
 		if f.name != name {
 			name = f.name
 			out = append(out, f)
 			continue
 		}
 		if n := len(out); n > 0 && out[n-1].name == name && (!out[n-1].tag || f.tag) {
 			out = out[:n-1]
 		}
 	}
 	fields = out

 	return fields
 }

 var fieldCache struct {
 	sync.RWMutex
 	m map[reflect.Type][]field
 }

 // cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
 func cachedTypeFields(t reflect.Type) []field {
 	fieldCache.RLock()
 	f := fieldCache.m[t]
 	fieldCache.RUnlock()
 	if f != nil {
 		return f
 	}

 	// Compute fields without lock.
 	// Might duplicate effort but won't hold other computations back.
 	f = typeFields(t)
 	if f == nil {
 		f = []field{}
 	}

 	fieldCache.Lock()
 	if fieldCache.m == nil {
 		fieldCache.m = map[reflect.Type][]field{}
 	}
 	fieldCache.m[t] = f
 	fieldCache.Unlock()
 	return f
 }

 // tagOptions is the string following a comma in a struct field's "json"
 // tag, or the empty string. It does not include the leading comma.
 type tagOptions string

 // parseTag splits a struct field's json tag into its name and
 // comma-separated options.
 func parseTag(tag string) (string, tagOptions) {
 	if idx := strings.Index(tag, ","); idx != -1 {
 		return tag[:idx], tagOptions(tag[idx+1:])
 	}
 	return tag, tagOptions("")
 }

 // Contains returns whether checks that a comma-separated list of options
 // contains a particular substr flag. substr must be surrounded by a
 // string boundary or commas.
 func (o tagOptions) Contains(optionName string) bool {
 	if len(o) == 0 {
 		return false
 	}
 	s := string(o)
 	for s != "" {
 		var next string
 		i := strings.Index(s, ",")
 		if i >= 0 {
 			s, next = s[:i], s[i+1:]
 		}
 		if s == optionName {
 			return true
 		}
 		s = next
 	}
 	return false
 }
	// Copyright 2010 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package cjson

	import (
	"bytes"
	"encoding/base64"
	"reflect"
	"runtime"
	"sort"
	"strconv"
	"strings"
	"sync"
	"unicode"
	"unicode/utf8"
	)

	func Marshal(v interface{}) ([]byte, error) {
	e := &encodeState{}
	err := e.marshal(v)
	if err != nil {
	return nil, err
	}
	return e.Bytes(), nil
	}

	// Marshaler is the interface implemented by objects that
	// can marshal themselves into valid JSON.
	type Marshaler interface {
	MarshalJSON() ([]byte, error)
	}

	// An UnsupportedTypeError is returned by Marshal when attempting
	// to encode an unsupported value type.
	type UnsupportedTypeError struct {
	Type reflect.Type
	}

	func (e *UnsupportedTypeError) Error() string {
	return "json: unsupported type: " + e.Type.String()
	}

	type UnsupportedValueError struct {
	Value reflect.Value
	Str string
	}

	func (e *UnsupportedValueError) Error() string {
	return "json: unsupported value: " + e.Str
	}

	type InvalidUTF8Error struct {
	S string
	}

	func (e *InvalidUTF8Error) Error() string {
	return "json: invalid UTF-8 in string: " + strconv.Quote(e.S)
	}

	type MarshalerError struct {
	Type reflect.Type
	Err error
	}

	func (e *MarshalerError) Error() string {
	return "json: error calling MarshalJSON for type " + e.Type.String() + ": " + e.Err.Error()
	}

	var hex = "0123456789abcdef"

	var numberType = reflect.TypeOf(Number(""))

	// A Number represents a JSON number literal.
	type Number string

	// String returns the literal text of the number.
	func (n Number) String() string { return string(n) }

	// Float64 returns the number as a float64.
	func (n Number) Float64() (float64, error) {
	return strconv.ParseFloat(string(n), 64)
	}

	// Int64 returns the number as an int64.
	func (n Number) Int64() (int64, error) {
	return strconv.ParseInt(string(n), 10, 64)
	}

	// An encodeState encodes JSON into a bytes.Buffer.
	type encodeState struct {
	bytes.Buffer // accumulated output
	scratch [64]byte
	}

	func (e *encodeState) marshal(v interface{}) (err error) {
	defer func() {
	if r := recover(); r != nil {
	if _, ok := r.(runtime.Error); ok {
	panic(r)
	}
	err = r.(error)
	}
	}()
	e.reflectValue(reflect.ValueOf(v))
	return nil
	}

	func (e *encodeState) error(err error) {
	panic(err)
	}

	var byteSliceType = reflect.TypeOf([]byte(nil))

	func isEmptyValue(v reflect.Value) bool {
	switch v.Kind() {
	case reflect.Array, reflect.Map, reflect.Slice, reflect.String:
	return v.Len() == 0
	case reflect.Bool:
	return !v.Bool()
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
	return v.Int() == 0
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
	return v.Uint() == 0
	case reflect.Float32, reflect.Float64:
	return v.Float() == 0
	case reflect.Interface, reflect.Ptr:
	return v.IsNil()
	}
	return false
	}

	func (e *encodeState) reflectValue(v reflect.Value) {
	e.reflectValueQuoted(v, false)
	}

	// reflectValueQuoted writes the value in v to the output.
	// If quoted is true, the serialization is wrapped in a JSON string.
	func (e *encodeState) reflectValueQuoted(v reflect.Value, quoted bool) {
	if !v.IsValid() {
	e.WriteString("null")
	return
	}

	m, ok := v.Interface().(Marshaler)
	if !ok {
	// T doesn't match the interface. Check against *T too.
	if v.Kind() != reflect.Ptr && v.CanAddr() {
	m, ok = v.Addr().Interface().(Marshaler)
	if ok {
	v = v.Addr()
	}
	}
	}
	if ok && (v.Kind() != reflect.Ptr \|\| !v.IsNil()) {
	b, err := m.MarshalJSON()
	if err != nil {
	e.error(&MarshalerError{v.Type(), err})
	}
	// TODO: canonicalize this json
	e.Buffer.Write(b)
	return
	}

	writeString := (*encodeState).WriteString
	if quoted {
	writeString = (*encodeState).string
	}

	switch v.Kind() {
	case reflect.Bool:
	x := v.Bool()
	if x {
	writeString(e, "true")
	} else {
	writeString(e, "false")
	}

	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
	b := strconv.AppendInt(e.scratch[:0], v.Int(), 10)
	if quoted {
	writeString(e, string(b))
	} else {
	e.Write(b)
	}
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
	b := strconv.AppendUint(e.scratch[:0], v.Uint(), 10)
	if quoted {
	writeString(e, string(b))
	} else {
	e.Write(b)
	}
	case reflect.Float32, reflect.Float64:
	e.error(&UnsupportedValueError{v, "floating point number"})
	case reflect.String:
	if v.Type() == numberType {
	numStr := v.String()
	if numStr == "" {
	numStr = "0" // Number's zero-val
	}
	e.WriteString(numStr)
	break
	}
	if quoted {
	sb, err := Marshal(v.String())
	if err != nil {
	e.error(err)
	}
	e.string(string(sb))
	} else {
	e.string(v.String())
	}

	case reflect.Struct:
	e.WriteByte('{')
	first := true
	for _, f := range cachedTypeFields(v.Type()) {
	fv := fieldByIndex(v, f.index)
	if !fv.IsValid() \|\| f.omitEmpty && isEmptyValue(fv) {
	continue
	}
	if first {
	first = false
	} else {
	e.WriteByte(',')
	}
	e.string(f.name)
	e.WriteByte(':')
	e.reflectValueQuoted(fv, f.quoted)
	}
	e.WriteByte('}')

	case reflect.Map:
	if v.Type().Key().Kind() != reflect.String {
	e.error(&UnsupportedTypeError{v.Type()})
	}
	if v.IsNil() {
	e.WriteString("null")
	break
	}
	e.WriteByte('{')
	var sv stringValues = v.MapKeys()
	sort.Sort(sv)
	for i, k := range sv {
	if i > 0 {
	e.WriteByte(',')
	}
	e.string(k.String())
	e.WriteByte(':')
	e.reflectValue(v.MapIndex(k))
	}
	e.WriteByte('}')

	case reflect.Slice:
	if v.IsNil() {
	e.WriteString("null")
	break
	}
	if v.Type().Elem().Kind() == reflect.Uint8 {
	// Byte slices get special treatment; arrays don't.
	s := v.Bytes()
	e.WriteByte('"')
	if len(s) < 1024 {
	// for small buffers, using Encode directly is much faster.
	dst := make([]byte, base64.StdEncoding.EncodedLen(len(s)))
	base64.StdEncoding.Encode(dst, s)
	e.Write(dst)
	} else {
	// for large buffers, avoid unnecessary extra temporary
	// buffer space.
	enc := base64.NewEncoder(base64.StdEncoding, e)
	enc.Write(s)
	enc.Close()
	}
	e.WriteByte('"')
	break
	}
	// Slices can be marshalled as nil, but otherwise are handled
	// as arrays.
	fallthrough
	case reflect.Array:
	e.WriteByte('[')
	n := v.Len()
	for i := 0; i < n; i++ {
	if i > 0 {
	e.WriteByte(',')
	}
	e.reflectValue(v.Index(i))
	}
	e.WriteByte(']')

	case reflect.Interface, reflect.Ptr:
	if v.IsNil() {
	e.WriteString("null")
	return
	}
	e.reflectValue(v.Elem())

	default:
	e.error(&UnsupportedTypeError{v.Type()})
	}
	return
	}

	func isValidTag(s string) bool {
	if s == "" {
	return false
	}
	for _, c := range s {
	switch {
	case strings.ContainsRune("!#$%&()*+-./:<=>?@[]^_{\|}~ ", c):
	// Backslash and quote chars are reserved, but
	// otherwise any punctuation chars are allowed
	// in a tag name.
	default:
	if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
	return false
	}
	}
	}
	return true
	}

	func fieldByIndex(v reflect.Value, index []int) reflect.Value {
	for _, i := range index {
	if v.Kind() == reflect.Ptr {
	if v.IsNil() {
	return reflect.Value{}
	}
	v = v.Elem()
	}
	v = v.Field(i)
	}
	return v
	}

	// stringValues is a slice of reflect.Value holding *reflect.StringValue.
	// It implements the methods to sort by string.
	type stringValues []reflect.Value

	func (sv stringValues) Len() int { return len(sv) }
	func (sv stringValues) Swap(i, j int) { sv[i], sv[j] = sv[j], sv[i] }
	func (sv stringValues) Less(i, j int) bool { return sv.get(i) < sv.get(j) }
	func (sv stringValues) get(i int) string { return sv[i].String() }

	func (e *encodeState) string(s string) (int, error) {
	len0 := e.Len()
	e.WriteByte('"')
	start := 0
	for i := 0; i < len(s); {
	if b := s[i]; b < utf8.RuneSelf {
	if b != '\\' && b != '"' {
	i++
	continue
	}
	if start < i {
	e.WriteString(s[start:i])
	}
	switch b {
	case '\\', '"':
	e.WriteByte('\\')
	e.WriteByte(b)
	}
	i++
	start = i
	continue
	}
	c, size := utf8.DecodeRuneInString(s[i:])
	if c == utf8.RuneError && size == 1 {
	e.error(&InvalidUTF8Error{s})
	}
	i += size
	}
	if start < len(s) {
	e.WriteString(s[start:])
	}
	e.WriteByte('"')
	return e.Len() - len0, nil
	}

	// A field represents a single field found in a struct.
	type field struct {
	name string
	tag bool
	index []int
	typ reflect.Type
	omitEmpty bool
	quoted bool
	}

	// byName sorts field by name, breaking ties with depth,
	// then breaking ties with "name came from json tag", then
	// breaking ties with index sequence.
	type byName []field

	func (x byName) Len() int { return len(x) }

	func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

	func (x byName) Less(i, j int) bool {
	if x[i].name != x[j].name {
	return x[i].name < x[j].name
	}
	if len(x[i].index) != len(x[j].index) {
	return len(x[i].index) < len(x[j].index)
	}
	if x[i].tag != x[j].tag {
	return x[i].tag
	}
	return byIndex(x).Less(i, j)
	}

	// byIndex sorts field by index sequence.
	type byIndex []field

	func (x byIndex) Len() int { return len(x) }

	func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

	func (x byIndex) Less(i, j int) bool {
	for k, xik := range x[i].index {
	if k >= len(x[j].index) {
	return false
	}
	if xik != x[j].index[k] {
	return xik < x[j].index[k]
	}
	}
	return len(x[i].index) < len(x[j].index)
	}

	// typeFields returns a list of fields that JSON should recognize for the given type.
	// The algorithm is breadth-first search over the set of structs to include - the top struct
	// and then any reachable anonymous structs.
	func typeFields(t reflect.Type) []field {
	// Anonymous fields to explore at the current level and the next.
	current := []field{}
	next := []field{{typ: t}}

	// Count of queued names for current level and the next.
	count := map[reflect.Type]int{}
	nextCount := map[reflect.Type]int{}

	// Types already visited at an earlier level.
	visited := map[reflect.Type]bool{}

	// Fields found.
	var fields []field

	for len(next) > 0 {
	current, next = next, current[:0]
	count, nextCount = nextCount, map[reflect.Type]int{}

	for _, f := range current {
	if visited[f.typ] {
	continue
	}
	visited[f.typ] = true

	// Scan f.typ for fields to include.
	for i := 0; i < f.typ.NumField(); i++ {
	sf := f.typ.Field(i)
	if sf.PkgPath != "" { // unexported
	continue
	}
	tag := sf.Tag.Get("json")
	if tag == "-" {
	continue
	}
	name, opts := parseTag(tag)
	if !isValidTag(name) {
	name = ""
	}
	index := make([]int, len(f.index)+1)
	copy(index, f.index)
	index[len(f.index)] = i

	ft := sf.Type
	if ft.Name() == "" && ft.Kind() == reflect.Ptr {
	// Follow pointer.
	ft = ft.Elem()
	}

	// Record found field and index sequence.
	if name != "" \|\| !sf.Anonymous \|\| ft.Kind() != reflect.Struct {
	tagged := name != ""
	if name == "" {
	name = sf.Name
	}
	fields = append(fields, field{name, tagged, index, ft,
	opts.Contains("omitempty"), opts.Contains("string")})
	if count[f.typ] > 1 {
	// If there were multiple instances, add a second,
	// so that the annihilation code will see a duplicate.
	// It only cares about the distinction between 1 or 2,
	// so don't bother generating any more copies.
	fields = append(fields, fields[len(fields)-1])
	}
	continue
	}

	// Record new anonymous struct to explore in next round.
	nextCount[ft]++
	if nextCount[ft] == 1 {
	next = append(next, field{name: ft.Name(), index: index, typ: ft})
	}
	}
	}
	}

	sort.Sort(byName(fields))

	// Remove fields with annihilating name collisions
	// and also fields shadowed by fields with explicit JSON tags.
	name := ""
	out := fields[:0]
	for _, f := range fields {
	if f.name != name {
	name = f.name
	out = append(out, f)
	continue
	}
	if n := len(out); n > 0 && out[n-1].name == name && (!out[n-1].tag \|\| f.tag) {
	out = out[:n-1]
	}
	}
	fields = out

	return fields
	}

	var fieldCache struct {
	sync.RWMutex
	m map[reflect.Type][]field
	}

	// cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
	func cachedTypeFields(t reflect.Type) []field {
	fieldCache.RLock()
	f := fieldCache.m[t]
	fieldCache.RUnlock()
	if f != nil {
	return f
	}

	// Compute fields without lock.
	// Might duplicate effort but won't hold other computations back.
	f = typeFields(t)
	if f == nil {
	f = []field{}
	}

	fieldCache.Lock()
	if fieldCache.m == nil {
	fieldCache.m = map[reflect.Type][]field{}
	}
	fieldCache.m[t] = f
	fieldCache.Unlock()
	return f
	}

	// tagOptions is the string following a comma in a struct field's "json"
	// tag, or the empty string. It does not include the leading comma.
	type tagOptions string

	// parseTag splits a struct field's json tag into its name and
	// comma-separated options.
	func parseTag(tag string) (string, tagOptions) {
	if idx := strings.Index(tag, ","); idx != -1 {
	return tag[:idx], tagOptions(tag[idx+1:])
	}
	return tag, tagOptions("")
	}

	// Contains returns whether checks that a comma-separated list of options
	// contains a particular substr flag. substr must be surrounded by a
	// string boundary or commas.
	func (o tagOptions) Contains(optionName string) bool {
	if len(o) == 0 {
	return false
	}
	s := string(o)
	for s != "" {
	var next string
	i := strings.Index(s, ",")
	if i >= 0 {
	s, next = s[:i], s[i+1:]
	}
	if s == optionName {
	return true
	}
	s = next
	}
	return false
	}