reflectcache.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/value

     1  /*
     2  Copyright 2020 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package value
    18  
    19  import (
    20  	"bytes"
    21  	"encoding/json"
    22  	"fmt"
    23  	"reflect"
    24  	"sort"
    25  	"sync"
    26  	"sync/atomic"
    27  )
    28  
    29  // UnstructuredConverter defines how a type can be converted directly to unstructured.
    30  // Types that implement json.Marshaler may also optionally implement this interface to provide a more
    31  // direct and more efficient conversion. All types that choose to implement this interface must still
    32  // implement this same conversion via json.Marshaler.
    33  type UnstructuredConverter interface {
    34  	json.Marshaler // require that json.Marshaler is implemented
    35  
    36  	// ToUnstructured returns the unstructured representation.
    37  	ToUnstructured() interface{}
    38  }
    39  
    40  // TypeReflectCacheEntry keeps data gathered using reflection about how a type is converted to/from unstructured.
    41  type TypeReflectCacheEntry struct {
    42  	isJsonMarshaler        bool
    43  	ptrIsJsonMarshaler     bool
    44  	isJsonUnmarshaler      bool
    45  	ptrIsJsonUnmarshaler   bool
    46  	isStringConvertable    bool
    47  	ptrIsStringConvertable bool
    48  
    49  	structFields        map[string]*FieldCacheEntry
    50  	orderedStructFields []*FieldCacheEntry
    51  }
    52  
    53  // FieldCacheEntry keeps data gathered using reflection about how the field of a struct is converted to/from
    54  // unstructured.
    55  type FieldCacheEntry struct {
    56  	// JsonName returns the name of the field according to the json tags on the struct field.
    57  	JsonName string
    58  	// isOmitEmpty is true if the field has the json 'omitempty' tag.
    59  	isOmitEmpty bool
    60  	// fieldPath is a list of field indices (see FieldByIndex) to lookup the value of
    61  	// a field in a reflect.Value struct. The field indices in the list form a path used
    62  	// to traverse through intermediary 'inline' fields.
    63  	fieldPath [][]int
    64  
    65  	fieldType reflect.Type
    66  	TypeEntry *TypeReflectCacheEntry
    67  }
    68  
    69  func (f *FieldCacheEntry) CanOmit(fieldVal reflect.Value) bool {
    70  	return f.isOmitEmpty && (safeIsNil(fieldVal) || isZero(fieldVal))
    71  }
    72  
    73  // GetFrom returns the field identified by this FieldCacheEntry from the provided struct.
    74  func (f *FieldCacheEntry) GetFrom(structVal reflect.Value) reflect.Value {
    75  	// field might be nested within 'inline' structs
    76  	for _, elem := range f.fieldPath {
    77  		structVal = dereference(structVal).FieldByIndex(elem)
    78  	}
    79  	return structVal
    80  }
    81  
    82  var marshalerType = reflect.TypeOf(new(json.Marshaler)).Elem()
    83  var unmarshalerType = reflect.TypeOf(new(json.Unmarshaler)).Elem()
    84  var unstructuredConvertableType = reflect.TypeOf(new(UnstructuredConverter)).Elem()
    85  var defaultReflectCache = newReflectCache()
    86  
    87  // TypeReflectEntryOf returns the TypeReflectCacheEntry of the provided reflect.Type.
    88  func TypeReflectEntryOf(t reflect.Type) *TypeReflectCacheEntry {
    89  	cm := defaultReflectCache.get()
    90  	if record, ok := cm[t]; ok {
    91  		return record
    92  	}
    93  	updates := reflectCacheMap{}
    94  	result := typeReflectEntryOf(cm, t, updates)
    95  	if len(updates) > 0 {
    96  		defaultReflectCache.update(updates)
    97  	}
    98  	return result
    99  }
   100  
   101  // TypeReflectEntryOf returns all updates needed to add provided reflect.Type, and the types its fields transitively
   102  // depend on, to the cache.
   103  func typeReflectEntryOf(cm reflectCacheMap, t reflect.Type, updates reflectCacheMap) *TypeReflectCacheEntry {
   104  	if record, ok := cm[t]; ok {
   105  		return record
   106  	}
   107  	if record, ok := updates[t]; ok {
   108  		return record
   109  	}
   110  	typeEntry := &TypeReflectCacheEntry{
   111  		isJsonMarshaler:        t.Implements(marshalerType),
   112  		ptrIsJsonMarshaler:     reflect.PtrTo(t).Implements(marshalerType),
   113  		isJsonUnmarshaler:      reflect.PtrTo(t).Implements(unmarshalerType),
   114  		isStringConvertable:    t.Implements(unstructuredConvertableType),
   115  		ptrIsStringConvertable: reflect.PtrTo(t).Implements(unstructuredConvertableType),
   116  	}
   117  	if t.Kind() == reflect.Struct {
   118  		fieldEntries := map[string]*FieldCacheEntry{}
   119  		buildStructCacheEntry(t, fieldEntries, nil)
   120  		typeEntry.structFields = fieldEntries
   121  		sortedByJsonName := make([]*FieldCacheEntry, len(fieldEntries))
   122  		i := 0
   123  		for _, entry := range fieldEntries {
   124  			sortedByJsonName[i] = entry
   125  			i++
   126  		}
   127  		sort.Slice(sortedByJsonName, func(i, j int) bool {
   128  			return sortedByJsonName[i].JsonName < sortedByJsonName[j].JsonName
   129  		})
   130  		typeEntry.orderedStructFields = sortedByJsonName
   131  	}
   132  
   133  	// cyclic type references are allowed, so we must add the typeEntry to the updates map before resolving
   134  	// the field.typeEntry references, or creating them if they are not already in the cache
   135  	updates[t] = typeEntry
   136  
   137  	for _, field := range typeEntry.structFields {
   138  		if field.TypeEntry == nil {
   139  			field.TypeEntry = typeReflectEntryOf(cm, field.fieldType, updates)
   140  		}
   141  	}
   142  	return typeEntry
   143  }
   144  
   145  func buildStructCacheEntry(t reflect.Type, infos map[string]*FieldCacheEntry, fieldPath [][]int) {
   146  	for i := 0; i < t.NumField(); i++ {
   147  		field := t.Field(i)
   148  		jsonName, omit, isInline, isOmitempty := lookupJsonTags(field)
   149  		if omit {
   150  			continue
   151  		}
   152  		if isInline {
   153  			e := field.Type
   154  			if field.Type.Kind() == reflect.Ptr {
   155  				e = field.Type.Elem()
   156  			}
   157  			if e.Kind() == reflect.Struct {
   158  				buildStructCacheEntry(e, infos, append(fieldPath, field.Index))
   159  			}
   160  			continue
   161  		}
   162  		info := &FieldCacheEntry{JsonName: jsonName, isOmitEmpty: isOmitempty, fieldPath: append(fieldPath, field.Index), fieldType: field.Type}
   163  		infos[jsonName] = info
   164  	}
   165  }
   166  
   167  // Fields returns a map of JSON field name to FieldCacheEntry for structs, or nil for non-structs.
   168  func (e TypeReflectCacheEntry) Fields() map[string]*FieldCacheEntry {
   169  	return e.structFields
   170  }
   171  
   172  // Fields returns a map of JSON field name to FieldCacheEntry for structs, or nil for non-structs.
   173  func (e TypeReflectCacheEntry) OrderedFields() []*FieldCacheEntry {
   174  	return e.orderedStructFields
   175  }
   176  
   177  // CanConvertToUnstructured returns true if this TypeReflectCacheEntry can convert values of its type to unstructured.
   178  func (e TypeReflectCacheEntry) CanConvertToUnstructured() bool {
   179  	return e.isJsonMarshaler || e.ptrIsJsonMarshaler || e.isStringConvertable || e.ptrIsStringConvertable
   180  }
   181  
   182  // ToUnstructured converts the provided value to unstructured and returns it.
   183  func (e TypeReflectCacheEntry) ToUnstructured(sv reflect.Value) (interface{}, error) {
   184  	// This is based on https://github.com/kubernetes/kubernetes/blob/82c9e5c814eb7acc6cc0a090c057294d0667ad66/staging/src/k8s.io/apimachinery/pkg/runtime/converter.go#L505
   185  	// and is intended to replace it.
   186  
   187  	// Check if the object has a custom string converter and use it if available, since it is much more efficient
   188  	// than round tripping through json.
   189  	if converter, ok := e.getUnstructuredConverter(sv); ok {
   190  		return converter.ToUnstructured(), nil
   191  	}
   192  	// Check if the object has a custom JSON marshaller/unmarshaller.
   193  	if marshaler, ok := e.getJsonMarshaler(sv); ok {
   194  		if sv.Kind() == reflect.Ptr && sv.IsNil() {
   195  			// We're done - we don't need to store anything.
   196  			return nil, nil
   197  		}
   198  
   199  		data, err := marshaler.MarshalJSON()
   200  		if err != nil {
   201  			return nil, err
   202  		}
   203  		switch {
   204  		case len(data) == 0:
   205  			return nil, fmt.Errorf("error decoding from json: empty value")
   206  
   207  		case bytes.Equal(data, nullBytes):
   208  			// We're done - we don't need to store anything.
   209  			return nil, nil
   210  
   211  		case bytes.Equal(data, trueBytes):
   212  			return true, nil
   213  
   214  		case bytes.Equal(data, falseBytes):
   215  			return false, nil
   216  
   217  		case data[0] == '"':
   218  			var result string
   219  			err := unmarshal(data, &result)
   220  			if err != nil {
   221  				return nil, fmt.Errorf("error decoding string from json: %v", err)
   222  			}
   223  			return result, nil
   224  
   225  		case data[0] == '{':
   226  			result := make(map[string]interface{})
   227  			err := unmarshal(data, &result)
   228  			if err != nil {
   229  				return nil, fmt.Errorf("error decoding object from json: %v", err)
   230  			}
   231  			return result, nil
   232  
   233  		case data[0] == '[':
   234  			result := make([]interface{}, 0)
   235  			err := unmarshal(data, &result)
   236  			if err != nil {
   237  				return nil, fmt.Errorf("error decoding array from json: %v", err)
   238  			}
   239  			return result, nil
   240  
   241  		default:
   242  			var (
   243  				resultInt   int64
   244  				resultFloat float64
   245  				err         error
   246  			)
   247  			if err = unmarshal(data, &resultInt); err == nil {
   248  				return resultInt, nil
   249  			} else if err = unmarshal(data, &resultFloat); err == nil {
   250  				return resultFloat, nil
   251  			} else {
   252  				return nil, fmt.Errorf("error decoding number from json: %v", err)
   253  			}
   254  		}
   255  	}
   256  
   257  	return nil, fmt.Errorf("provided type cannot be converted: %v", sv.Type())
   258  }
   259  
   260  // CanConvertFromUnstructured returns true if this TypeReflectCacheEntry can convert objects of the type from unstructured.
   261  func (e TypeReflectCacheEntry) CanConvertFromUnstructured() bool {
   262  	return e.isJsonUnmarshaler
   263  }
   264  
   265  // FromUnstructured converts the provided source value from unstructured into the provided destination value.
   266  func (e TypeReflectCacheEntry) FromUnstructured(sv, dv reflect.Value) error {
   267  	// TODO: this could be made much more efficient using direct conversions like
   268  	// UnstructuredConverter.ToUnstructured provides.
   269  	st := dv.Type()
   270  	data, err := json.Marshal(sv.Interface())
   271  	if err != nil {
   272  		return fmt.Errorf("error encoding %s to json: %v", st.String(), err)
   273  	}
   274  	if unmarshaler, ok := e.getJsonUnmarshaler(dv); ok {
   275  		return unmarshaler.UnmarshalJSON(data)
   276  	}
   277  	return fmt.Errorf("unable to unmarshal %v into %v", sv.Type(), dv.Type())
   278  }
   279  
   280  var (
   281  	nullBytes  = []byte("null")
   282  	trueBytes  = []byte("true")
   283  	falseBytes = []byte("false")
   284  )
   285  
   286  func (e TypeReflectCacheEntry) getJsonMarshaler(v reflect.Value) (json.Marshaler, bool) {
   287  	if e.isJsonMarshaler {
   288  		return v.Interface().(json.Marshaler), true
   289  	}
   290  	if e.ptrIsJsonMarshaler {
   291  		// Check pointer receivers if v is not a pointer
   292  		if v.Kind() != reflect.Ptr && v.CanAddr() {
   293  			v = v.Addr()
   294  			return v.Interface().(json.Marshaler), true
   295  		}
   296  	}
   297  	return nil, false
   298  }
   299  
   300  func (e TypeReflectCacheEntry) getJsonUnmarshaler(v reflect.Value) (json.Unmarshaler, bool) {
   301  	if !e.isJsonUnmarshaler {
   302  		return nil, false
   303  	}
   304  	return v.Addr().Interface().(json.Unmarshaler), true
   305  }
   306  
   307  func (e TypeReflectCacheEntry) getUnstructuredConverter(v reflect.Value) (UnstructuredConverter, bool) {
   308  	if e.isStringConvertable {
   309  		return v.Interface().(UnstructuredConverter), true
   310  	}
   311  	if e.ptrIsStringConvertable {
   312  		// Check pointer receivers if v is not a pointer
   313  		if v.CanAddr() {
   314  			v = v.Addr()
   315  			return v.Interface().(UnstructuredConverter), true
   316  		}
   317  	}
   318  	return nil, false
   319  }
   320  
   321  type typeReflectCache struct {
   322  	// use an atomic and copy-on-write since there are a fixed (typically very small) number of structs compiled into any
   323  	// go program using this cache
   324  	value atomic.Value
   325  	// mu is held by writers when performing load/modify/store operations on the cache, readers do not need to hold a
   326  	// read-lock since the atomic value is always read-only
   327  	mu sync.Mutex
   328  }
   329  
   330  func newReflectCache() *typeReflectCache {
   331  	cache := &typeReflectCache{}
   332  	cache.value.Store(make(reflectCacheMap))
   333  	return cache
   334  }
   335  
   336  type reflectCacheMap map[reflect.Type]*TypeReflectCacheEntry
   337  
   338  // get returns the reflectCacheMap.
   339  func (c *typeReflectCache) get() reflectCacheMap {
   340  	return c.value.Load().(reflectCacheMap)
   341  }
   342  
   343  // update merges the provided updates into the cache.
   344  func (c *typeReflectCache) update(updates reflectCacheMap) {
   345  	c.mu.Lock()
   346  	defer c.mu.Unlock()
   347  
   348  	currentCacheMap := c.value.Load().(reflectCacheMap)
   349  
   350  	hasNewEntries := false
   351  	for t := range updates {
   352  		if _, ok := currentCacheMap[t]; !ok {
   353  			hasNewEntries = true
   354  			break
   355  		}
   356  	}
   357  	if !hasNewEntries {
   358  		// Bail if the updates have been set while waiting for lock acquisition.
   359  		// This is safe since setting entries is idempotent.
   360  		return
   361  	}
   362  
   363  	newCacheMap := make(reflectCacheMap, len(currentCacheMap)+len(updates))
   364  	for k, v := range currentCacheMap {
   365  		newCacheMap[k] = v
   366  	}
   367  	for t, update := range updates {
   368  		newCacheMap[t] = update
   369  	}
   370  	c.value.Store(newCacheMap)
   371  }
   372  
   373  // Below json Unmarshal is fromk8s.io/apimachinery/pkg/util/json
   374  // to handle number conversions as expected by Kubernetes
   375  
   376  // limit recursive depth to prevent stack overflow errors
   377  const maxDepth = 10000
   378  
   379  // unmarshal unmarshals the given data
   380  // If v is a *map[string]interface{}, numbers are converted to int64 or float64
   381  func unmarshal(data []byte, v interface{}) error {
   382  	switch v := v.(type) {
   383  	case *map[string]interface{}:
   384  		// Build a decoder from the given data
   385  		decoder := json.NewDecoder(bytes.NewBuffer(data))
   386  		// Preserve numbers, rather than casting to float64 automatically
   387  		decoder.UseNumber()
   388  		// Run the decode
   389  		if err := decoder.Decode(v); err != nil {
   390  			return err
   391  		}
   392  		// If the decode succeeds, post-process the map to convert json.Number objects to int64 or float64
   393  		return convertMapNumbers(*v, 0)
   394  
   395  	case *[]interface{}:
   396  		// Build a decoder from the given data
   397  		decoder := json.NewDecoder(bytes.NewBuffer(data))
   398  		// Preserve numbers, rather than casting to float64 automatically
   399  		decoder.UseNumber()
   400  		// Run the decode
   401  		if err := decoder.Decode(v); err != nil {
   402  			return err
   403  		}
   404  		// If the decode succeeds, post-process the map to convert json.Number objects to int64 or float64
   405  		return convertSliceNumbers(*v, 0)
   406  
   407  	default:
   408  		return json.Unmarshal(data, v)
   409  	}
   410  }
   411  
   412  // convertMapNumbers traverses the map, converting any json.Number values to int64 or float64.
   413  // values which are map[string]interface{} or []interface{} are recursively visited
   414  func convertMapNumbers(m map[string]interface{}, depth int) error {
   415  	if depth > maxDepth {
   416  		return fmt.Errorf("exceeded max depth of %d", maxDepth)
   417  	}
   418  
   419  	var err error
   420  	for k, v := range m {
   421  		switch v := v.(type) {
   422  		case json.Number:
   423  			m[k], err = convertNumber(v)
   424  		case map[string]interface{}:
   425  			err = convertMapNumbers(v, depth+1)
   426  		case []interface{}:
   427  			err = convertSliceNumbers(v, depth+1)
   428  		}
   429  		if err != nil {
   430  			return err
   431  		}
   432  	}
   433  	return nil
   434  }
   435  
   436  // convertSliceNumbers traverses the slice, converting any json.Number values to int64 or float64.
   437  // values which are map[string]interface{} or []interface{} are recursively visited
   438  func convertSliceNumbers(s []interface{}, depth int) error {
   439  	if depth > maxDepth {
   440  		return fmt.Errorf("exceeded max depth of %d", maxDepth)
   441  	}
   442  
   443  	var err error
   444  	for i, v := range s {
   445  		switch v := v.(type) {
   446  		case json.Number:
   447  			s[i], err = convertNumber(v)
   448  		case map[string]interface{}:
   449  			err = convertMapNumbers(v, depth+1)
   450  		case []interface{}:
   451  			err = convertSliceNumbers(v, depth+1)
   452  		}
   453  		if err != nil {
   454  			return err
   455  		}
   456  	}
   457  	return nil
   458  }
   459  
   460  // convertNumber converts a json.Number to an int64 or float64, or returns an error
   461  func convertNumber(n json.Number) (interface{}, error) {
   462  	// Attempt to convert to an int64 first
   463  	if i, err := n.Int64(); err == nil {
   464  		return i, nil
   465  	}
   466  	// Return a float64 (default json.Decode() behavior)
   467  	// An overflow will return an error
   468  	return n.Float64()
   469  }
   470
View as plain text