1 // Copyright 2013 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.
5 // Package json is forked from the Go standard library to enable us to find the
6 // field of a struct that a given JSON key maps to.
21 patchStrategyTagKey = "patchStrategy"
22 patchMergeKeyTagKey = "patchMergeKey"
25 // Finds the patchStrategy and patchMergeKey struct tag fields on a given
26 // struct field given the struct type and the JSON name of the field.
27 // It returns field type, a slice of patch strategies, merge key and error.
28 // TODO: fix the returned errors to be introspectable.
29 func LookupPatchMetadataForStruct(t reflect.Type, jsonField string) (
30 elemType reflect.Type, patchStrategies []string, patchMergeKey string, e error) {
31 if t.Kind() == reflect.Ptr {
35 if t.Kind() != reflect.Struct {
36 e = fmt.Errorf("merging an object in json but data type is not struct, instead is: %s",
40 jf := []byte(jsonField)
41 // Find the field that the JSON library would use.
43 fields := cachedTypeFields(t)
44 for i := range fields {
46 if bytes.Equal(ff.nameBytes, jf) {
50 // Do case-insensitive comparison.
51 if f == nil && ff.equalFold(ff.nameBytes, jf) {
56 // Find the reflect.Value of the most preferential struct field.
57 tjf := t.Field(f.index[0])
58 // we must navigate down all the anonymously included structs in the chain
59 for i := 1; i < len(f.index); i++ {
60 tjf = tjf.Type.Field(f.index[i])
62 patchStrategy := tjf.Tag.Get(patchStrategyTagKey)
63 patchMergeKey = tjf.Tag.Get(patchMergeKeyTagKey)
64 patchStrategies = strings.Split(patchStrategy, ",")
68 e = fmt.Errorf("unable to find api field in struct %s for the json field %q", t.Name(), jsonField)
72 // A field represents a single field found in a struct.
75 nameBytes []byte // []byte(name)
76 equalFold func(s, t []byte) bool // bytes.EqualFold or equivalent
79 // index is the sequence of indexes from the containing type fields to this field.
80 // it is a slice because anonymous structs will need multiple navigation steps to correctly
81 // resolve the proper fields
88 func (f field) String() string {
89 return fmt.Sprintf("{name: %s, type: %v, tag: %v, index: %v, omitEmpty: %v, quoted: %v}", f.name, f.typ, f.tag, f.index, f.omitEmpty, f.quoted)
92 func fillField(f field) field {
93 f.nameBytes = []byte(f.name)
94 f.equalFold = foldFunc(f.nameBytes)
98 // byName sorts field by name, breaking ties with depth,
99 // then breaking ties with "name came from json tag", then
100 // breaking ties with index sequence.
103 func (x byName) Len() int { return len(x) }
105 func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
107 func (x byName) Less(i, j int) bool {
108 if x[i].name != x[j].name {
109 return x[i].name < x[j].name
111 if len(x[i].index) != len(x[j].index) {
112 return len(x[i].index) < len(x[j].index)
114 if x[i].tag != x[j].tag {
117 return byIndex(x).Less(i, j)
120 // byIndex sorts field by index sequence.
123 func (x byIndex) Len() int { return len(x) }
125 func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
127 func (x byIndex) Less(i, j int) bool {
128 for k, xik := range x[i].index {
129 if k >= len(x[j].index) {
132 if xik != x[j].index[k] {
133 return xik < x[j].index[k]
136 return len(x[i].index) < len(x[j].index)
139 // typeFields returns a list of fields that JSON should recognize for the given type.
140 // The algorithm is breadth-first search over the set of structs to include - the top struct
141 // and then any reachable anonymous structs.
142 func typeFields(t reflect.Type) []field {
143 // Anonymous fields to explore at the current level and the next.
145 next := []field{{typ: t}}
147 // Count of queued names for current level and the next.
148 count := map[reflect.Type]int{}
149 nextCount := map[reflect.Type]int{}
151 // Types already visited at an earlier level.
152 visited := map[reflect.Type]bool{}
158 current, next = next, current[:0]
159 count, nextCount = nextCount, map[reflect.Type]int{}
161 for _, f := range current {
165 visited[f.typ] = true
167 // Scan f.typ for fields to include.
168 for i := 0; i < f.typ.NumField(); i++ {
170 if sf.PkgPath != "" { // unexported
173 tag := sf.Tag.Get("json")
177 name, opts := parseTag(tag)
178 if !isValidTag(name) {
181 index := make([]int, len(f.index)+1)
183 index[len(f.index)] = i
186 if ft.Name() == "" && ft.Kind() == reflect.Ptr {
191 // Record found field and index sequence.
192 if name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
197 fields = append(fields, fillField(field{
202 omitEmpty: opts.Contains("omitempty"),
203 quoted: opts.Contains("string"),
205 if count[f.typ] > 1 {
206 // If there were multiple instances, add a second,
207 // so that the annihilation code will see a duplicate.
208 // It only cares about the distinction between 1 or 2,
209 // so don't bother generating any more copies.
210 fields = append(fields, fields[len(fields)-1])
215 // Record new anonymous struct to explore in next round.
217 if nextCount[ft] == 1 {
218 next = append(next, fillField(field{name: ft.Name(), index: index, typ: ft}))
224 sort.Sort(byName(fields))
226 // Delete all fields that are hidden by the Go rules for embedded fields,
227 // except that fields with JSON tags are promoted.
229 // The fields are sorted in primary order of name, secondary order
230 // of field index length. Loop over names; for each name, delete
231 // hidden fields by choosing the one dominant field that survives.
233 for advance, i := 0, 0; i < len(fields); i += advance {
234 // One iteration per name.
235 // Find the sequence of fields with the name of this first field.
238 for advance = 1; i+advance < len(fields); advance++ {
239 fj := fields[i+advance]
244 if advance == 1 { // Only one field with this name
245 out = append(out, fi)
248 dominant, ok := dominantField(fields[i : i+advance])
250 out = append(out, dominant)
255 sort.Sort(byIndex(fields))
260 // dominantField looks through the fields, all of which are known to
261 // have the same name, to find the single field that dominates the
262 // others using Go's embedding rules, modified by the presence of
263 // JSON tags. If there are multiple top-level fields, the boolean
264 // will be false: This condition is an error in Go and we skip all
266 func dominantField(fields []field) (field, bool) {
267 // The fields are sorted in increasing index-length order. The winner
268 // must therefore be one with the shortest index length. Drop all
269 // longer entries, which is easy: just truncate the slice.
270 length := len(fields[0].index)
271 tagged := -1 // Index of first tagged field.
272 for i, f := range fields {
273 if len(f.index) > length {
279 // Multiple tagged fields at the same level: conflict.
281 return field{}, false
287 return fields[tagged], true
289 // All remaining fields have the same length. If there's more than one,
290 // we have a conflict (two fields named "X" at the same level) and we
293 return field{}, false
295 return fields[0], true
298 var fieldCache struct {
300 m map[reflect.Type][]field
303 // cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
304 func cachedTypeFields(t reflect.Type) []field {
312 // Compute fields without lock.
313 // Might duplicate effort but won't hold other computations back.
320 if fieldCache.m == nil {
321 fieldCache.m = map[reflect.Type][]field{}
328 func isValidTag(s string) bool {
332 for _, c := range s {
334 case strings.ContainsRune("!#$%&()*+-./:<=>?@[]^_{|}~ ", c):
335 // Backslash and quote chars are reserved, but
336 // otherwise any punctuation chars are allowed
339 if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
348 caseMask = ^byte(0x20) // Mask to ignore case in ASCII.
350 smallLongEss = '\u017f'
353 // foldFunc returns one of four different case folding equivalence
354 // functions, from most general (and slow) to fastest:
356 // 1) bytes.EqualFold, if the key s contains any non-ASCII UTF-8
357 // 2) equalFoldRight, if s contains special folding ASCII ('k', 'K', 's', 'S')
358 // 3) asciiEqualFold, no special, but includes non-letters (including _)
359 // 4) simpleLetterEqualFold, no specials, no non-letters.
361 // The letters S and K are special because they map to 3 runes, not just 2:
362 // * S maps to s and to U+017F 'ſ' Latin small letter long s
363 // * k maps to K and to U+212A 'K' Kelvin sign
364 // See http://play.golang.org/p/tTxjOc0OGo
366 // The returned function is specialized for matching against s and
367 // should only be given s. It's not curried for performance reasons.
368 func foldFunc(s []byte) func(s, t []byte) bool {
370 special := false // special letter
371 for _, b := range s {
372 if b >= utf8.RuneSelf {
373 return bytes.EqualFold
375 upper := b & caseMask
376 if upper < 'A' || upper > 'Z' {
378 } else if upper == 'K' || upper == 'S' {
379 // See above for why these letters are special.
384 return equalFoldRight
387 return asciiEqualFold
389 return simpleLetterEqualFold
392 // equalFoldRight is a specialization of bytes.EqualFold when s is
393 // known to be all ASCII (including punctuation), but contains an 's',
394 // 'S', 'k', or 'K', requiring a Unicode fold on the bytes in t.
395 // See comments on foldFunc.
396 func equalFoldRight(s, t []byte) bool {
397 for _, sb := range s {
402 if tb < utf8.RuneSelf {
404 sbUpper := sb & caseMask
405 if 'A' <= sbUpper && sbUpper <= 'Z' {
406 if sbUpper != tb&caseMask {
416 // sb is ASCII and t is not. t must be either kelvin
417 // sign or long s; sb must be s, S, k, or K.
418 tr, size := utf8.DecodeRune(t)
421 if tr != smallLongEss {
440 // asciiEqualFold is a specialization of bytes.EqualFold for use when
441 // s is all ASCII (but may contain non-letters) and contains no
442 // special-folding letters.
443 // See comments on foldFunc.
444 func asciiEqualFold(s, t []byte) bool {
445 if len(s) != len(t) {
448 for i, sb := range s {
453 if ('a' <= sb && sb <= 'z') || ('A' <= sb && sb <= 'Z') {
454 if sb&caseMask != tb&caseMask {
464 // simpleLetterEqualFold is a specialization of bytes.EqualFold for
465 // use when s is all ASCII letters (no underscores, etc) and also
466 // doesn't contain 'k', 'K', 's', or 'S'.
467 // See comments on foldFunc.
468 func simpleLetterEqualFold(s, t []byte) bool {
469 if len(s) != len(t) {
472 for i, b := range s {
473 if b&caseMask != t[i]&caseMask {
480 // tagOptions is the string following a comma in a struct field's "json"
481 // tag, or the empty string. It does not include the leading comma.
482 type tagOptions string
484 // parseTag splits a struct field's json tag into its name and
485 // comma-separated options.
486 func parseTag(tag string) (string, tagOptions) {
487 if idx := strings.Index(tag, ","); idx != -1 {
488 return tag[:idx], tagOptions(tag[idx+1:])
490 return tag, tagOptions("")
493 // Contains reports whether a comma-separated list of options
494 // contains a particular substr flag. substr must be surrounded by a
495 // string boundary or commas.
496 func (o tagOptions) Contains(optionName string) bool {
503 i := strings.Index(s, ",")
505 s, next = s[:i], s[i+1:]