1/* 2Copyright 2019 The Kubernetes Authors. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package value 18 19import ( 20 "reflect" 21) 22 23type mapReflect struct { 24 valueReflect 25} 26 27func (r mapReflect) Length() int { 28 val := r.Value 29 return val.Len() 30} 31 32func (r mapReflect) Empty() bool { 33 val := r.Value 34 return val.Len() == 0 35} 36 37func (r mapReflect) Get(key string) (Value, bool) { 38 return r.GetUsing(HeapAllocator, key) 39} 40 41func (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 49func (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 55func (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 64func (r mapReflect) Set(key string, val Value) { 65 r.Value.SetMapIndex(r.toMapKey(key), reflect.ValueOf(val.Unstructured())) 66} 67 68func (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? 74func (r mapReflect) toMapKey(key string) reflect.Value { 75 val := r.Value 76 return reflect.ValueOf(key).Convert(val.Type().Key()) 77} 78 79func (r mapReflect) Iterate(fn func(string, Value) bool) bool { 80 return r.IterateUsing(HeapAllocator, fn) 81} 82 83func (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 94func 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 109func (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 118func (r mapReflect) Equals(m Map) bool { 119 return r.EqualsUsing(HeapAllocator, m) 120} 121 122func (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 Equals(vr.mustReuse(lhsVal, entry, nil, nil), value) 140 }) 141} 142 143func (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 147func (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. 155func (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