mapreflect.go

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

     1  /*
     2  Copyright 2019 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  	"reflect"
    21  )
    22  
    23  type mapReflect struct {
    24  	valueReflect
    25  }
    26  
    27  func (r mapReflect) Length() int {
    28  	val := r.Value
    29  	return val.Len()
    30  }
    31  
    32  func (r mapReflect) Empty() bool {
    33  	val := r.Value
    34  	return val.Len() == 0
    35  }
    36  
    37  func (r mapReflect) Get(key string) (Value, bool) {
    38  	return r.GetUsing(HeapAllocator, key)
    39  }
    40  
    41  func (r mapReflect) GetUsing(a Allocator, key string) (Value, bool) {
    42  	k, v, ok := r.get(key)
    43  	if !ok {
    44  		return nil, false
    45  	}
    46  	return a.allocValueReflect().mustReuse(v, nil, &r.Value, &k), true
    47  }
    48  
    49  func (r mapReflect) get(k string) (key, value reflect.Value, ok bool) {
    50  	mapKey := r.toMapKey(k)
    51  	val := r.Value.MapIndex(mapKey)
    52  	return mapKey, val, val.IsValid() && val != reflect.Value{}
    53  }
    54  
    55  func (r mapReflect) Has(key string) bool {
    56  	var val reflect.Value
    57  	val = r.Value.MapIndex(r.toMapKey(key))
    58  	if !val.IsValid() {
    59  		return false
    60  	}
    61  	return val != reflect.Value{}
    62  }
    63  
    64  func (r mapReflect) Set(key string, val Value) {
    65  	r.Value.SetMapIndex(r.toMapKey(key), reflect.ValueOf(val.Unstructured()))
    66  }
    67  
    68  func (r mapReflect) Delete(key string) {
    69  	val := r.Value
    70  	val.SetMapIndex(r.toMapKey(key), reflect.Value{})
    71  }
    72  
    73  // TODO: Do we need to support types that implement json.Marshaler and are used as string keys?
    74  func (r mapReflect) toMapKey(key string) reflect.Value {
    75  	val := r.Value
    76  	return reflect.ValueOf(key).Convert(val.Type().Key())
    77  }
    78  
    79  func (r mapReflect) Iterate(fn func(string, Value) bool) bool {
    80  	return r.IterateUsing(HeapAllocator, fn)
    81  }
    82  
    83  func (r mapReflect) IterateUsing(a Allocator, fn func(string, Value) bool) bool {
    84  	if r.Value.Len() == 0 {
    85  		return true
    86  	}
    87  	v := a.allocValueReflect()
    88  	defer a.Free(v)
    89  	return eachMapEntry(r.Value, func(e *TypeReflectCacheEntry, key reflect.Value, value reflect.Value) bool {
    90  		return fn(key.String(), v.mustReuse(value, e, &r.Value, &key))
    91  	})
    92  }
    93  
    94  func eachMapEntry(val reflect.Value, fn func(*TypeReflectCacheEntry, reflect.Value, reflect.Value) bool) bool {
    95  	iter := val.MapRange()
    96  	entry := TypeReflectEntryOf(val.Type().Elem())
    97  	for iter.Next() {
    98  		next := iter.Value()
    99  		if !next.IsValid() {
   100  			continue
   101  		}
   102  		if !fn(entry, iter.Key(), next) {
   103  			return false
   104  		}
   105  	}
   106  	return true
   107  }
   108  
   109  func (r mapReflect) Unstructured() interface{} {
   110  	result := make(map[string]interface{}, r.Length())
   111  	r.Iterate(func(s string, value Value) bool {
   112  		result[s] = value.Unstructured()
   113  		return true
   114  	})
   115  	return result
   116  }
   117  
   118  func (r mapReflect) Equals(m Map) bool {
   119  	return r.EqualsUsing(HeapAllocator, m)
   120  }
   121  
   122  func (r mapReflect) EqualsUsing(a Allocator, m Map) bool {
   123  	lhsLength := r.Length()
   124  	rhsLength := m.Length()
   125  	if lhsLength != rhsLength {
   126  		return false
   127  	}
   128  	if lhsLength == 0 {
   129  		return true
   130  	}
   131  	vr := a.allocValueReflect()
   132  	defer a.Free(vr)
   133  	entry := TypeReflectEntryOf(r.Value.Type().Elem())
   134  	return m.Iterate(func(key string, value Value) bool {
   135  		_, lhsVal, ok := r.get(key)
   136  		if !ok {
   137  			return false
   138  		}
   139  		return EqualsUsing(a, vr.mustReuse(lhsVal, entry, nil, nil), value)
   140  	})
   141  }
   142  
   143  func (r mapReflect) Zip(other Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool {
   144  	return r.ZipUsing(HeapAllocator, other, order, fn)
   145  }
   146  
   147  func (r mapReflect) ZipUsing(a Allocator, other Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool {
   148  	if otherMapReflect, ok := other.(*mapReflect); ok && order == Unordered {
   149  		return r.unorderedReflectZip(a, otherMapReflect, fn)
   150  	}
   151  	return defaultMapZip(a, &r, other, order, fn)
   152  }
   153  
   154  // unorderedReflectZip provides an optimized unordered zip for mapReflect types.
   155  func (r mapReflect) unorderedReflectZip(a Allocator, other *mapReflect, fn func(key string, lhs, rhs Value) bool) bool {
   156  	if r.Empty() && (other == nil || other.Empty()) {
   157  		return true
   158  	}
   159  
   160  	lhs := r.Value
   161  	lhsEntry := TypeReflectEntryOf(lhs.Type().Elem())
   162  
   163  	// map lookup via reflection is expensive enough that it is better to keep track of visited keys
   164  	visited := map[string]struct{}{}
   165  
   166  	vlhs, vrhs := a.allocValueReflect(), a.allocValueReflect()
   167  	defer a.Free(vlhs)
   168  	defer a.Free(vrhs)
   169  
   170  	if other != nil {
   171  		rhs := other.Value
   172  		rhsEntry := TypeReflectEntryOf(rhs.Type().Elem())
   173  		iter := rhs.MapRange()
   174  
   175  		for iter.Next() {
   176  			key := iter.Key()
   177  			keyString := key.String()
   178  			next := iter.Value()
   179  			if !next.IsValid() {
   180  				continue
   181  			}
   182  			rhsVal := vrhs.mustReuse(next, rhsEntry, &rhs, &key)
   183  			visited[keyString] = struct{}{}
   184  			var lhsVal Value
   185  			if _, v, ok := r.get(keyString); ok {
   186  				lhsVal = vlhs.mustReuse(v, lhsEntry, &lhs, &key)
   187  			}
   188  			if !fn(keyString, lhsVal, rhsVal) {
   189  				return false
   190  			}
   191  		}
   192  	}
   193  
   194  	iter := lhs.MapRange()
   195  	for iter.Next() {
   196  		key := iter.Key()
   197  		if _, ok := visited[key.String()]; ok {
   198  			continue
   199  		}
   200  		next := iter.Value()
   201  		if !next.IsValid() {
   202  			continue
   203  		}
   204  		if !fn(key.String(), vlhs.mustReuse(next, lhsEntry, &lhs, &key), nil) {
   205  			return false
   206  		}
   207  	}
   208  	return true
   209  }
   210
View as plain text