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