fields.go

Documentation: k8s.io/apimachinery/third_party/forked/golang/json

     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.
     4  
     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.
     7  package json
     8  
     9  import (
    10  	"bytes"
    11  	"fmt"
    12  	"reflect"
    13  	"sort"
    14  	"strings"
    15  	"sync"
    16  	"unicode"
    17  	"unicode/utf8"
    18  )
    19  
    20  const (
    21  	patchStrategyTagKey = "patchStrategy"
    22  	patchMergeKeyTagKey = "patchMergeKey"
    23  )
    24  
    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.Pointer {
    32  		t = t.Elem()
    33  	}
    34  
    35  	if t.Kind() != reflect.Struct {
    36  		e = fmt.Errorf("merging an object in json but data type is not struct, instead is: %s",
    37  			t.Kind().String())
    38  		return
    39  	}
    40  	jf := []byte(jsonField)
    41  	// Find the field that the JSON library would use.
    42  	var f *field
    43  	fields := cachedTypeFields(t)
    44  	for i := range fields {
    45  		ff := &fields[i]
    46  		if bytes.Equal(ff.nameBytes, jf) {
    47  			f = ff
    48  			break
    49  		}
    50  		// Do case-insensitive comparison.
    51  		if f == nil && ff.equalFold(ff.nameBytes, jf) {
    52  			f = ff
    53  		}
    54  	}
    55  	if f != nil {
    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])
    61  		}
    62  		patchStrategy := tjf.Tag.Get(patchStrategyTagKey)
    63  		patchMergeKey = tjf.Tag.Get(patchMergeKeyTagKey)
    64  		patchStrategies = strings.Split(patchStrategy, ",")
    65  		elemType = tjf.Type
    66  		return
    67  	}
    68  	e = fmt.Errorf("unable to find api field in struct %s for the json field %q", t.Name(), jsonField)
    69  	return
    70  }
    71  
    72  // A field represents a single field found in a struct.
    73  type field struct {
    74  	name      string
    75  	nameBytes []byte                 // []byte(name)
    76  	equalFold func(s, t []byte) bool // bytes.EqualFold or equivalent
    77  
    78  	tag bool
    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
    82  	index     []int
    83  	typ       reflect.Type
    84  	omitEmpty bool
    85  	quoted    bool
    86  }
    87  
    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)
    90  }
    91  
    92  func fillField(f field) field {
    93  	f.nameBytes = []byte(f.name)
    94  	f.equalFold = foldFunc(f.nameBytes)
    95  	return f
    96  }
    97  
    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.
   101  type byName []field
   102  
   103  func (x byName) Len() int { return len(x) }
   104  
   105  func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
   106  
   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
   110  	}
   111  	if len(x[i].index) != len(x[j].index) {
   112  		return len(x[i].index) < len(x[j].index)
   113  	}
   114  	if x[i].tag != x[j].tag {
   115  		return x[i].tag
   116  	}
   117  	return byIndex(x).Less(i, j)
   118  }
   119  
   120  // byIndex sorts field by index sequence.
   121  type byIndex []field
   122  
   123  func (x byIndex) Len() int { return len(x) }
   124  
   125  func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
   126  
   127  func (x byIndex) Less(i, j int) bool {
   128  	for k, xik := range x[i].index {
   129  		if k >= len(x[j].index) {
   130  			return false
   131  		}
   132  		if xik != x[j].index[k] {
   133  			return xik < x[j].index[k]
   134  		}
   135  	}
   136  	return len(x[i].index) < len(x[j].index)
   137  }
   138  
   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.
   144  	current := []field{}
   145  	next := []field{{typ: t}}
   146  
   147  	// Count of queued names for current level and the next.
   148  	count := map[reflect.Type]int{}
   149  	nextCount := map[reflect.Type]int{}
   150  
   151  	// Types already visited at an earlier level.
   152  	visited := map[reflect.Type]bool{}
   153  
   154  	// Fields found.
   155  	var fields []field
   156  
   157  	for len(next) > 0 {
   158  		current, next = next, current[:0]
   159  		count, nextCount = nextCount, map[reflect.Type]int{}
   160  
   161  		for _, f := range current {
   162  			if visited[f.typ] {
   163  				continue
   164  			}
   165  			visited[f.typ] = true
   166  
   167  			// Scan f.typ for fields to include.
   168  			for i := 0; i < f.typ.NumField(); i++ {
   169  				sf := f.typ.Field(i)
   170  				if sf.PkgPath != "" { // unexported
   171  					continue
   172  				}
   173  				tag := sf.Tag.Get("json")
   174  				if tag == "-" {
   175  					continue
   176  				}
   177  				name, opts := parseTag(tag)
   178  				if !isValidTag(name) {
   179  					name = ""
   180  				}
   181  				index := make([]int, len(f.index)+1)
   182  				copy(index, f.index)
   183  				index[len(f.index)] = i
   184  
   185  				ft := sf.Type
   186  				if ft.Name() == "" && ft.Kind() == reflect.Pointer {
   187  					// Follow pointer.
   188  					ft = ft.Elem()
   189  				}
   190  
   191  				// Record found field and index sequence.
   192  				if name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
   193  					tagged := name != ""
   194  					if name == "" {
   195  						name = sf.Name
   196  					}
   197  					fields = append(fields, fillField(field{
   198  						name:      name,
   199  						tag:       tagged,
   200  						index:     index,
   201  						typ:       ft,
   202  						omitEmpty: opts.Contains("omitempty"),
   203  						quoted:    opts.Contains("string"),
   204  					}))
   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])
   211  					}
   212  					continue
   213  				}
   214  
   215  				// Record new anonymous struct to explore in next round.
   216  				nextCount[ft]++
   217  				if nextCount[ft] == 1 {
   218  					next = append(next, fillField(field{name: ft.Name(), index: index, typ: ft}))
   219  				}
   220  			}
   221  		}
   222  	}
   223  
   224  	sort.Sort(byName(fields))
   225  
   226  	// Delete all fields that are hidden by the Go rules for embedded fields,
   227  	// except that fields with JSON tags are promoted.
   228  
   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.
   232  	out := fields[:0]
   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.
   236  		fi := fields[i]
   237  		name := fi.name
   238  		for advance = 1; i+advance < len(fields); advance++ {
   239  			fj := fields[i+advance]
   240  			if fj.name != name {
   241  				break
   242  			}
   243  		}
   244  		if advance == 1 { // Only one field with this name
   245  			out = append(out, fi)
   246  			continue
   247  		}
   248  		dominant, ok := dominantField(fields[i : i+advance])
   249  		if ok {
   250  			out = append(out, dominant)
   251  		}
   252  	}
   253  
   254  	fields = out
   255  	sort.Sort(byIndex(fields))
   256  
   257  	return fields
   258  }
   259  
   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
   265  // the fields.
   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 {
   274  			fields = fields[:i]
   275  			break
   276  		}
   277  		if f.tag {
   278  			if tagged >= 0 {
   279  				// Multiple tagged fields at the same level: conflict.
   280  				// Return no field.
   281  				return field{}, false
   282  			}
   283  			tagged = i
   284  		}
   285  	}
   286  	if tagged >= 0 {
   287  		return fields[tagged], true
   288  	}
   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
   291  	// return no field.
   292  	if len(fields) > 1 {
   293  		return field{}, false
   294  	}
   295  	return fields[0], true
   296  }
   297  
   298  var fieldCache struct {
   299  	sync.RWMutex
   300  	m map[reflect.Type][]field
   301  }
   302  
   303  // cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
   304  func cachedTypeFields(t reflect.Type) []field {
   305  	fieldCache.RLock()
   306  	f := fieldCache.m[t]
   307  	fieldCache.RUnlock()
   308  	if f != nil {
   309  		return f
   310  	}
   311  
   312  	// Compute fields without lock.
   313  	// Might duplicate effort but won't hold other computations back.
   314  	f = typeFields(t)
   315  	if f == nil {
   316  		f = []field{}
   317  	}
   318  
   319  	fieldCache.Lock()
   320  	if fieldCache.m == nil {
   321  		fieldCache.m = map[reflect.Type][]field{}
   322  	}
   323  	fieldCache.m[t] = f
   324  	fieldCache.Unlock()
   325  	return f
   326  }
   327  
   328  func isValidTag(s string) bool {
   329  	if s == "" {
   330  		return false
   331  	}
   332  	for _, c := range s {
   333  		switch {
   334  		case strings.ContainsRune("!#$%&()*+-./:<=>?@[]^_{|}~ ", c):
   335  			// Backslash and quote chars are reserved, but
   336  			// otherwise any punctuation chars are allowed
   337  			// in a tag name.
   338  		default:
   339  			if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
   340  				return false
   341  			}
   342  		}
   343  	}
   344  	return true
   345  }
   346  
   347  const (
   348  	caseMask     = ^byte(0x20) // Mask to ignore case in ASCII.
   349  	kelvin       = '\u212a'
   350  	smallLongEss = '\u017f'
   351  )
   352  
   353  // foldFunc returns one of four different case folding equivalence
   354  // functions, from most general (and slow) to fastest:
   355  //
   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.
   360  //
   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 'K' Kelvin sign
   364  // See http://play.golang.org/p/tTxjOc0OGo
   365  //
   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 {
   369  	nonLetter := false
   370  	special := false // special letter
   371  	for _, b := range s {
   372  		if b >= utf8.RuneSelf {
   373  			return bytes.EqualFold
   374  		}
   375  		upper := b & caseMask
   376  		if upper < 'A' || upper > 'Z' {
   377  			nonLetter = true
   378  		} else if upper == 'K' || upper == 'S' {
   379  			// See above for why these letters are special.
   380  			special = true
   381  		}
   382  	}
   383  	if special {
   384  		return equalFoldRight
   385  	}
   386  	if nonLetter {
   387  		return asciiEqualFold
   388  	}
   389  	return simpleLetterEqualFold
   390  }
   391  
   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 {
   398  		if len(t) == 0 {
   399  			return false
   400  		}
   401  		tb := t[0]
   402  		if tb < utf8.RuneSelf {
   403  			if sb != tb {
   404  				sbUpper := sb & caseMask
   405  				if 'A' <= sbUpper && sbUpper <= 'Z' {
   406  					if sbUpper != tb&caseMask {
   407  						return false
   408  					}
   409  				} else {
   410  					return false
   411  				}
   412  			}
   413  			t = t[1:]
   414  			continue
   415  		}
   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)
   419  		switch sb {
   420  		case 's', 'S':
   421  			if tr != smallLongEss {
   422  				return false
   423  			}
   424  		case 'k', 'K':
   425  			if tr != kelvin {
   426  				return false
   427  			}
   428  		default:
   429  			return false
   430  		}
   431  		t = t[size:]
   432  
   433  	}
   434  	if len(t) > 0 {
   435  		return false
   436  	}
   437  	return true
   438  }
   439  
   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) {
   446  		return false
   447  	}
   448  	for i, sb := range s {
   449  		tb := t[i]
   450  		if sb == tb {
   451  			continue
   452  		}
   453  		if ('a' <= sb && sb <= 'z') || ('A' <= sb && sb <= 'Z') {
   454  			if sb&caseMask != tb&caseMask {
   455  				return false
   456  			}
   457  		} else {
   458  			return false
   459  		}
   460  	}
   461  	return true
   462  }
   463  
   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) {
   470  		return false
   471  	}
   472  	for i, b := range s {
   473  		if b&caseMask != t[i]&caseMask {
   474  			return false
   475  		}
   476  	}
   477  	return true
   478  }
   479  
   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
   483  
   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:])
   489  	}
   490  	return tag, tagOptions("")
   491  }
   492  
   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 {
   497  	if len(o) == 0 {
   498  		return false
   499  	}
   500  	s := string(o)
   501  	for s != "" {
   502  		var next string
   503  		i := strings.Index(s, ",")
   504  		if i >= 0 {
   505  			s, next = s[:i], s[i+1:]
   506  		}
   507  		if s == optionName {
   508  			return true
   509  		}
   510  		s = next
   511  	}
   512  	return false
   513  }
   514
View as plain text