Source file src/k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json/fields.go

Documentation: k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json

     1  // Copyright 2021 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
     6  
     7  import (
     8  	"errors"
     9  	"fmt"
    10  	"io"
    11  	"reflect"
    12  	"sort"
    13  	"strconv"
    14  	"strings"
    15  	"unicode"
    16  	"unicode/utf8"
    17  )
    18  
    19  var errIgnoredField = errors.New("ignored field")
    20  
    21  type isZeroer interface {
    22  	IsZero() bool
    23  }
    24  
    25  var isZeroerType = reflect.TypeOf((*isZeroer)(nil)).Elem()
    26  
    27  type structFields struct {
    28  	flattened       []structField // listed in depth-first ordering
    29  	byActualName    map[string]*structField
    30  	byFoldedName    map[string][]*structField
    31  	inlinedFallback *structField
    32  }
    33  
    34  type structField struct {
    35  	id      int   // unique numeric ID in breadth-first ordering
    36  	index   []int // index into a struct according to reflect.Type.FieldByIndex
    37  	typ     reflect.Type
    38  	fncs    *arshaler
    39  	isZero  func(addressableValue) bool
    40  	isEmpty func(addressableValue) bool
    41  	fieldOptions
    42  }
    43  
    44  func makeStructFields(root reflect.Type) (structFields, *SemanticError) {
    45  	var fs structFields
    46  	fs.byActualName = make(map[string]*structField, root.NumField())
    47  	fs.byFoldedName = make(map[string][]*structField, root.NumField())
    48  
    49  	// ambiguous is a sentinel value to indicate that at least two fields
    50  	// at the same depth have the same name, and thus cancel each other out.
    51  	// This follows the same rules as selecting a field on embedded structs
    52  	// where the shallowest field takes precedence. If more than one field
    53  	// exists at the shallowest depth, then the selection is illegal.
    54  	// See https://go.dev/ref/spec#Selectors.
    55  	ambiguous := new(structField)
    56  
    57  	// Setup a queue for a breath-first search.
    58  	var queueIndex int
    59  	type queueEntry struct {
    60  		typ           reflect.Type
    61  		index         []int
    62  		visitChildren bool // whether to recursively visit inlined field in this struct
    63  	}
    64  	queue := []queueEntry{{root, nil, true}}
    65  	seen := map[reflect.Type]bool{root: true}
    66  
    67  	// Perform a breadth-first search over all reachable fields.
    68  	// This ensures that len(f.index) will be monotonically increasing.
    69  	for queueIndex < len(queue) {
    70  		qe := queue[queueIndex]
    71  		queueIndex++
    72  
    73  		t := qe.typ
    74  		inlinedFallbackIndex := -1         // index of last inlined fallback field in current struct
    75  		namesIndex := make(map[string]int) // index of each field with a given JSON object name in current struct
    76  		var hasAnyJSONTag bool             // whether any Go struct field has a `json` tag
    77  		var hasAnyJSONField bool           // whether any JSON serializable fields exist in current struct
    78  		for i := 0; i < t.NumField(); i++ {
    79  			sf := t.Field(i)
    80  			_, hasTag := sf.Tag.Lookup("json")
    81  			hasAnyJSONTag = hasAnyJSONTag || hasTag
    82  			options, err := parseFieldOptions(sf)
    83  			if err != nil {
    84  				if err == errIgnoredField {
    85  					continue
    86  				}
    87  				return structFields{}, &SemanticError{GoType: t, Err: err}
    88  			}
    89  			hasAnyJSONField = true
    90  			f := structField{
    91  				// Allocate a new slice (len=N+1) to hold both
    92  				// the parent index (len=N) and the current index (len=1).
    93  				// Do this to avoid clobbering the memory of the parent index.
    94  				index:        append(append(make([]int, 0, len(qe.index)+1), qe.index...), i),
    95  				typ:          sf.Type,
    96  				fieldOptions: options,
    97  			}
    98  			if sf.Anonymous && !f.hasName {
    99  				f.inline = true // implied by use of Go embedding without an explicit name
   100  			}
   101  			if f.inline || f.unknown {
   102  				// Handle an inlined field that serializes to/from
   103  				// zero or more JSON object members.
   104  
   105  				if f.inline && f.unknown {
   106  					err := fmt.Errorf("Go struct field %s cannot have both `inline` and `unknown` specified", sf.Name)
   107  					return structFields{}, &SemanticError{GoType: t, Err: err}
   108  				}
   109  				switch f.fieldOptions {
   110  				case fieldOptions{name: f.name, quotedName: f.quotedName, inline: true}:
   111  				case fieldOptions{name: f.name, quotedName: f.quotedName, unknown: true}:
   112  				default:
   113  					err := fmt.Errorf("Go struct field %s cannot have any options other than `inline` or `unknown` specified", sf.Name)
   114  					return structFields{}, &SemanticError{GoType: t, Err: err}
   115  				}
   116  
   117  				// Unwrap one level of pointer indirection similar to how Go
   118  				// only allows embedding either T or *T, but not **T.
   119  				tf := f.typ
   120  				if tf.Kind() == reflect.Pointer && tf.Name() == "" {
   121  					tf = tf.Elem()
   122  				}
   123  				// Reject any types with custom serialization otherwise
   124  				// it becomes impossible to know what sub-fields to inline.
   125  				if which, _ := implementsWhich(tf,
   126  					jsonMarshalerV2Type, jsonMarshalerV1Type, textMarshalerType,
   127  					jsonUnmarshalerV2Type, jsonUnmarshalerV1Type, textUnmarshalerType,
   128  				); which != nil && tf != rawValueType {
   129  					err := fmt.Errorf("inlined Go struct field %s of type %s must not implement JSON marshal or unmarshal methods", sf.Name, tf)
   130  					return structFields{}, &SemanticError{GoType: t, Err: err}
   131  				}
   132  
   133  				// Handle an inlined field that serializes to/from
   134  				// a finite number of JSON object members backed by a Go struct.
   135  				if tf.Kind() == reflect.Struct {
   136  					if f.unknown {
   137  						err := fmt.Errorf("inlined Go struct field %s of type %s with `unknown` tag must be a Go map of string key or a json.RawValue", sf.Name, tf)
   138  						return structFields{}, &SemanticError{GoType: t, Err: err}
   139  					}
   140  					if qe.visitChildren {
   141  						queue = append(queue, queueEntry{tf, f.index, !seen[tf]})
   142  					}
   143  					seen[tf] = true
   144  					continue
   145  				}
   146  
   147  				// Handle an inlined field that serializes to/from any number of
   148  				// JSON object members back by a Go map or RawValue.
   149  				switch {
   150  				case tf == rawValueType:
   151  					f.fncs = nil // specially handled in arshal_inlined.go
   152  				case tf.Kind() == reflect.Map && tf.Key() == stringType:
   153  					f.fncs = lookupArshaler(tf.Elem())
   154  				default:
   155  					err := fmt.Errorf("inlined Go struct field %s of type %s must be a Go struct, Go map of string key, or json.RawValue", sf.Name, tf)
   156  					return structFields{}, &SemanticError{GoType: t, Err: err}
   157  				}
   158  
   159  				// Reject multiple inlined fallback fields within the same struct.
   160  				if inlinedFallbackIndex >= 0 {
   161  					err := fmt.Errorf("inlined Go struct fields %s and %s cannot both be a Go map or json.RawValue", t.Field(inlinedFallbackIndex).Name, sf.Name)
   162  					return structFields{}, &SemanticError{GoType: t, Err: err}
   163  				}
   164  				inlinedFallbackIndex = i
   165  
   166  				// Multiple inlined fallback fields across different structs
   167  				// follow the same precedence rules as Go struct embedding.
   168  				if fs.inlinedFallback == nil {
   169  					fs.inlinedFallback = &f // store first occurrence at lowest depth
   170  				} else if len(fs.inlinedFallback.index) == len(f.index) {
   171  					fs.inlinedFallback = ambiguous // at least two occurrences at same depth
   172  				}
   173  			} else {
   174  				// Handle normal Go struct field that serializes to/from
   175  				// a single JSON object member.
   176  
   177  				// Provide a function that uses a type's IsZero method.
   178  				switch {
   179  				case sf.Type.Kind() == reflect.Interface && sf.Type.Implements(isZeroerType):
   180  					f.isZero = func(va addressableValue) bool {
   181  						// Avoid panics calling IsZero on a nil interface or
   182  						// non-nil interface with nil pointer.
   183  						return va.IsNil() || (va.Elem().Kind() == reflect.Pointer && va.Elem().IsNil()) || va.Interface().(isZeroer).IsZero()
   184  					}
   185  				case sf.Type.Kind() == reflect.Pointer && sf.Type.Implements(isZeroerType):
   186  					f.isZero = func(va addressableValue) bool {
   187  						// Avoid panics calling IsZero on nil pointer.
   188  						return va.IsNil() || va.Interface().(isZeroer).IsZero()
   189  					}
   190  				case sf.Type.Implements(isZeroerType):
   191  					f.isZero = func(va addressableValue) bool { return va.Interface().(isZeroer).IsZero() }
   192  				case reflect.PointerTo(sf.Type).Implements(isZeroerType):
   193  					f.isZero = func(va addressableValue) bool { return va.Addr().Interface().(isZeroer).IsZero() }
   194  				}
   195  
   196  				// Provide a function that can determine whether the value would
   197  				// serialize as an empty JSON value.
   198  				switch sf.Type.Kind() {
   199  				case reflect.String, reflect.Map, reflect.Array, reflect.Slice:
   200  					f.isEmpty = func(va addressableValue) bool { return va.Len() == 0 }
   201  				case reflect.Pointer, reflect.Interface:
   202  					f.isEmpty = func(va addressableValue) bool { return va.IsNil() }
   203  				}
   204  
   205  				f.id = len(fs.flattened)
   206  				f.fncs = lookupArshaler(sf.Type)
   207  				fs.flattened = append(fs.flattened, f)
   208  
   209  				// Reject user-specified names with invalid UTF-8.
   210  				if !utf8.ValidString(f.name) {
   211  					err := fmt.Errorf("Go struct field %s has JSON object name %q with invalid UTF-8", sf.Name, f.name)
   212  					return structFields{}, &SemanticError{GoType: t, Err: err}
   213  				}
   214  				// Reject multiple fields with same name within the same struct.
   215  				if j, ok := namesIndex[f.name]; ok {
   216  					err := fmt.Errorf("Go struct fields %s and %s conflict over JSON object name %q", t.Field(j).Name, sf.Name, f.name)
   217  					return structFields{}, &SemanticError{GoType: t, Err: err}
   218  				}
   219  				namesIndex[f.name] = i
   220  
   221  				// Multiple fields of the same name across different structs
   222  				// follow the same precedence rules as Go struct embedding.
   223  				if f2 := fs.byActualName[f.name]; f2 == nil {
   224  					fs.byActualName[f.name] = &fs.flattened[len(fs.flattened)-1] // store first occurrence at lowest depth
   225  				} else if len(f2.index) == len(f.index) {
   226  					fs.byActualName[f.name] = ambiguous // at least two occurrences at same depth
   227  				}
   228  			}
   229  		}
   230  
   231  		// NOTE: New users to the json package are occasionally surprised that
   232  		// unexported fields are ignored. This occurs by necessity due to our
   233  		// inability to directly introspect such fields with Go reflection
   234  		// without the use of unsafe.
   235  		//
   236  		// To reduce friction here, refuse to serialize any Go struct that
   237  		// has no JSON serializable fields, has at least one Go struct field,
   238  		// and does not have any `json` tags present. For example,
   239  		// errors returned by errors.New would fail to serialize.
   240  		isEmptyStruct := t.NumField() == 0
   241  		if !isEmptyStruct && !hasAnyJSONTag && !hasAnyJSONField {
   242  			err := errors.New("Go struct has no exported fields")
   243  			return structFields{}, &SemanticError{GoType: t, Err: err}
   244  		}
   245  	}
   246  
   247  	// Remove all fields that are duplicates.
   248  	// This may move elements forward to fill the holes from removed fields.
   249  	var n int
   250  	for _, f := range fs.flattened {
   251  		switch f2 := fs.byActualName[f.name]; {
   252  		case f2 == ambiguous:
   253  			delete(fs.byActualName, f.name)
   254  		case f2 == nil:
   255  			continue // may be nil due to previous delete
   256  		// TODO(https://go.dev/issue/45955): Use slices.Equal.
   257  		case reflect.DeepEqual(f.index, f2.index):
   258  			f.id = n
   259  			fs.flattened[n] = f
   260  			fs.byActualName[f.name] = &fs.flattened[n] // fix pointer to new location
   261  			n++
   262  		}
   263  	}
   264  	fs.flattened = fs.flattened[:n]
   265  	if fs.inlinedFallback == ambiguous {
   266  		fs.inlinedFallback = nil
   267  	}
   268  	if len(fs.flattened) != len(fs.byActualName) {
   269  		panic(fmt.Sprintf("BUG: flattened list of fields mismatches fields mapped by name: %d != %d", len(fs.flattened), len(fs.byActualName)))
   270  	}
   271  
   272  	// Sort the fields according to a depth-first ordering.
   273  	// This operation will cause pointers in byActualName to become incorrect,
   274  	// which we will correct in another loop shortly thereafter.
   275  	sort.Slice(fs.flattened, func(i, j int) bool {
   276  		si := fs.flattened[i].index
   277  		sj := fs.flattened[j].index
   278  		for len(si) > 0 && len(sj) > 0 {
   279  			switch {
   280  			case si[0] < sj[0]:
   281  				return true
   282  			case si[0] > sj[0]:
   283  				return false
   284  			default:
   285  				si = si[1:]
   286  				sj = sj[1:]
   287  			}
   288  		}
   289  		return len(si) < len(sj)
   290  	})
   291  
   292  	// Recompute the mapping of fields in the byActualName map.
   293  	// Pre-fold all names so that we can lookup folded names quickly.
   294  	for i, f := range fs.flattened {
   295  		foldedName := string(foldName([]byte(f.name)))
   296  		fs.byActualName[f.name] = &fs.flattened[i]
   297  		fs.byFoldedName[foldedName] = append(fs.byFoldedName[foldedName], &fs.flattened[i])
   298  	}
   299  	for foldedName, fields := range fs.byFoldedName {
   300  		if len(fields) > 1 {
   301  			// The precedence order for conflicting nocase names
   302  			// is by breadth-first order, rather than depth-first order.
   303  			sort.Slice(fields, func(i, j int) bool {
   304  				return fields[i].id < fields[j].id
   305  			})
   306  			fs.byFoldedName[foldedName] = fields
   307  		}
   308  	}
   309  
   310  	return fs, nil
   311  }
   312  
   313  type fieldOptions struct {
   314  	name       string
   315  	quotedName string // quoted name per RFC 8785, section 3.2.2.2.
   316  	hasName    bool
   317  	nocase     bool
   318  	inline     bool
   319  	unknown    bool
   320  	omitzero   bool
   321  	omitempty  bool
   322  	string     bool
   323  	format     string
   324  }
   325  
   326  // parseFieldOptions parses the `json` tag in a Go struct field as
   327  // a structured set of options configuring parameters such as
   328  // the JSON member name and other features.
   329  // As a special case, it returns errIgnoredField if the field is ignored.
   330  func parseFieldOptions(sf reflect.StructField) (out fieldOptions, err error) {
   331  	tag, hasTag := sf.Tag.Lookup("json")
   332  
   333  	// Check whether this field is explicitly ignored.
   334  	if tag == "-" {
   335  		return fieldOptions{}, errIgnoredField
   336  	}
   337  
   338  	// Check whether this field is unexported.
   339  	if !sf.IsExported() {
   340  		// In contrast to v1, v2 no longer forwards exported fields from
   341  		// embedded fields of unexported types since Go reflection does not
   342  		// allow the same set of operations that are available in normal cases
   343  		// of purely exported fields.
   344  		// See https://go.dev/issue/21357 and https://go.dev/issue/24153.
   345  		if sf.Anonymous {
   346  			return fieldOptions{}, fmt.Errorf("embedded Go struct field %s of an unexported type must be explicitly ignored with a `json:\"-\"` tag", sf.Type.Name())
   347  		}
   348  		// Tag options specified on an unexported field suggests user error.
   349  		if hasTag {
   350  			return fieldOptions{}, fmt.Errorf("unexported Go struct field %s cannot have non-ignored `json:%q` tag", sf.Name, tag)
   351  		}
   352  		return fieldOptions{}, errIgnoredField
   353  	}
   354  
   355  	// Determine the JSON member name for this Go field. A user-specified name
   356  	// may be provided as either an identifier or a single-quoted string.
   357  	// The single-quoted string allows arbitrary characters in the name.
   358  	// See https://go.dev/issue/2718 and https://go.dev/issue/3546.
   359  	out.name = sf.Name // always starts with an uppercase character
   360  	if len(tag) > 0 && !strings.HasPrefix(tag, ",") {
   361  		// For better compatibility with v1, accept almost any unescaped name.
   362  		n := len(tag) - len(strings.TrimLeftFunc(tag, func(r rune) bool {
   363  			return !strings.ContainsRune(",\\'\"`", r) // reserve comma, backslash, and quotes
   364  		}))
   365  		opt := tag[:n]
   366  		if n == 0 {
   367  			// Allow a single quoted string for arbitrary names.
   368  			opt, n, err = consumeTagOption(tag)
   369  			if err != nil {
   370  				return fieldOptions{}, fmt.Errorf("Go struct field %s has malformed `json` tag: %v", sf.Name, err)
   371  			}
   372  		}
   373  		out.hasName = true
   374  		out.name = opt
   375  		tag = tag[n:]
   376  	}
   377  	b, _ := appendString(nil, out.name, false, nil)
   378  	out.quotedName = string(b)
   379  
   380  	// Handle any additional tag options (if any).
   381  	var wasFormat bool
   382  	seenOpts := make(map[string]bool)
   383  	for len(tag) > 0 {
   384  		// Consume comma delimiter.
   385  		if tag[0] != ',' {
   386  			return fieldOptions{}, fmt.Errorf("Go struct field %s has malformed `json` tag: invalid character %q before next option (expecting ',')", sf.Name, tag[0])
   387  		}
   388  		tag = tag[len(","):]
   389  		if len(tag) == 0 {
   390  			return fieldOptions{}, fmt.Errorf("Go struct field %s has malformed `json` tag: invalid trailing ',' character", sf.Name)
   391  		}
   392  
   393  		// Consume and process the tag option.
   394  		opt, n, err := consumeTagOption(tag)
   395  		if err != nil {
   396  			return fieldOptions{}, fmt.Errorf("Go struct field %s has malformed `json` tag: %v", sf.Name, err)
   397  		}
   398  		rawOpt := tag[:n]
   399  		tag = tag[n:]
   400  		switch {
   401  		case wasFormat:
   402  			return fieldOptions{}, fmt.Errorf("Go struct field %s has `format` tag option that was not specified last", sf.Name)
   403  		case strings.HasPrefix(rawOpt, "'") && strings.TrimFunc(opt, isLetterOrDigit) == "":
   404  			return fieldOptions{}, fmt.Errorf("Go struct field %s has unnecessarily quoted appearance of `%s` tag option; specify `%s` instead", sf.Name, rawOpt, opt)
   405  		}
   406  		switch opt {
   407  		case "nocase":
   408  			out.nocase = true
   409  		case "inline":
   410  			out.inline = true
   411  		case "unknown":
   412  			out.unknown = true
   413  		case "omitzero":
   414  			out.omitzero = true
   415  		case "omitempty":
   416  			out.omitempty = true
   417  		case "string":
   418  			out.string = true
   419  		case "format":
   420  			if !strings.HasPrefix(tag, ":") {
   421  				return fieldOptions{}, fmt.Errorf("Go struct field %s is missing value for `format` tag option", sf.Name)
   422  			}
   423  			tag = tag[len(":"):]
   424  			opt, n, err := consumeTagOption(tag)
   425  			if err != nil {
   426  				return fieldOptions{}, fmt.Errorf("Go struct field %s has malformed value for `format` tag option: %v", sf.Name, err)
   427  			}
   428  			tag = tag[n:]
   429  			out.format = opt
   430  			wasFormat = true
   431  		default:
   432  			// Reject keys that resemble one of the supported options.
   433  			// This catches invalid mutants such as "omitEmpty" or "omit_empty".
   434  			normOpt := strings.ReplaceAll(strings.ToLower(opt), "_", "")
   435  			switch normOpt {
   436  			case "nocase", "inline", "unknown", "omitzero", "omitempty", "string", "format":
   437  				return fieldOptions{}, fmt.Errorf("Go struct field %s has invalid appearance of `%s` tag option; specify `%s` instead", sf.Name, opt, normOpt)
   438  			}
   439  
   440  			// NOTE: Everything else is ignored. This does not mean it is
   441  			// forward compatible to insert arbitrary tag options since
   442  			// a future version of this package may understand that tag.
   443  		}
   444  
   445  		// Reject duplicates.
   446  		if seenOpts[opt] {
   447  			return fieldOptions{}, fmt.Errorf("Go struct field %s has duplicate appearance of `%s` tag option", sf.Name, rawOpt)
   448  		}
   449  		seenOpts[opt] = true
   450  	}
   451  	return out, nil
   452  }
   453  
   454  func consumeTagOption(in string) (string, int, error) {
   455  	switch r, _ := utf8.DecodeRuneInString(in); {
   456  	// Option as a Go identifier.
   457  	case r == '_' || unicode.IsLetter(r):
   458  		n := len(in) - len(strings.TrimLeftFunc(in, isLetterOrDigit))
   459  		return in[:n], n, nil
   460  	// Option as a single-quoted string.
   461  	case r == '\'':
   462  		// The grammar is nearly identical to a double-quoted Go string literal,
   463  		// but uses single quotes as the terminators. The reason for a custom
   464  		// grammar is because both backtick and double quotes cannot be used
   465  		// verbatim in a struct tag.
   466  		//
   467  		// Convert a single-quoted string to a double-quote string and rely on
   468  		// strconv.Unquote to handle the rest.
   469  		var inEscape bool
   470  		b := []byte{'"'}
   471  		n := len(`'`)
   472  		for len(in) > n {
   473  			r, rn := utf8.DecodeRuneInString(in[n:])
   474  			switch {
   475  			case inEscape:
   476  				if r == '\'' {
   477  					b = b[:len(b)-1] // remove escape character: `\'` => `'`
   478  				}
   479  				inEscape = false
   480  			case r == '\\':
   481  				inEscape = true
   482  			case r == '"':
   483  				b = append(b, '\\') // insert escape character: `"` => `\"`
   484  			case r == '\'':
   485  				b = append(b, '"')
   486  				n += len(`'`)
   487  				out, err := strconv.Unquote(string(b))
   488  				if err != nil {
   489  					return "", 0, fmt.Errorf("invalid single-quoted string: %s", in[:n])
   490  				}
   491  				return out, n, nil
   492  			}
   493  			b = append(b, in[n:][:rn]...)
   494  			n += rn
   495  		}
   496  		if n > 10 {
   497  			n = 10 // limit the amount of context printed in the error
   498  		}
   499  		return "", 0, fmt.Errorf("single-quoted string not terminated: %s...", in[:n])
   500  	case len(in) == 0:
   501  		return "", 0, io.ErrUnexpectedEOF
   502  	default:
   503  		return "", 0, fmt.Errorf("invalid character %q at start of option (expecting Unicode letter or single quote)", r)
   504  	}
   505  }
   506  
   507  func isLetterOrDigit(r rune) bool {
   508  	return r == '_' || unicode.IsLetter(r) || unicode.IsNumber(r)
   509  }
   510  

View as plain text