Debian Codegraph @

pkg/cel/common/equality.go

raw
1 /*
2 Copyright 2023 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 common
18
19 import (
20 "reflect"
21 "time"
22 )
23
24 // CorrelatedObject represents a node in a tree of objects that are being
25 // validated. It is used to keep track of the old value of an object during
26 // traversal of the new value. It is also used to cache the results of
27 // DeepEqual comparisons between the old and new values of objects.
28 //
29 // All receiver functions support being called on `nil` to support ergonomic
30 // recursive descent. The nil `CorrelatedObject` represents an uncorrelatable
31 // node in the tree.
32 //
33 // CorrelatedObject is not thread-safe. It is the responsibility of the caller
34 // to handle concurrency, if any.
35 type CorrelatedObject struct {
36 // Currently correlated old value during traversal of the schema/object
37 OldValue interface{}
38
39 // Value being validated
40 Value interface{}
41
42 // Schema used for validation of this value. The schema is also used
43 // to determine how to correlate the old object.
44 Schema Schema
45
46 // Duration spent on ratcheting validation for this object and all of its
47 // children.
48 Duration *time.Duration
49
50 // Scratch space below, may change during validation
51
52 // Cached comparison result of DeepEqual of `value` and `thunk.oldValue`
53 comparisonResult *bool
54
55 // Cached map representation of a map-type list, or nil if not map-type list
56 mapList MapList
57
58 // Children spawned by a call to `Validate` on this object
59 // key is either a string or an index, depending upon whether `value` is
60 // a map or a list, respectively.
61 //
62 // The list of children may be incomplete depending upon if the internal
63 // logic of kube-openapi's SchemaValidator short-circuited before
64 // reaching all of the children.
65 //
66 // It should be expected to have an entry for either all of the children, or
67 // none of them.
68 children map[interface{}]*CorrelatedObject
69 }
70
71 func NewCorrelatedObject(new, old interface{}, schema Schema) *CorrelatedObject {
72 d := time.Duration(0)
73 return &CorrelatedObject{
74 OldValue: old,
75 Value: new,
76 Schema: schema,
77 Duration: &d,
78 }
79 }
80
81 // If OldValue or Value is not a list, or the index is out of bounds of the
82 // Value list, returns nil
83 // If oldValue is a list, this considers the x-list-type to decide how to
84 // correlate old values:
85 //
86 // If listType is map, creates a map representation of the list using the designated
87 // map-keys, caches it for future calls, and returns the map value, or nil if
88 // the correlated key is not in the old map
89 //
90 // Otherwise, if the list type is not correlatable this funcion returns nil.
91 func (r *CorrelatedObject) correlateOldValueForChildAtNewIndex(index int) interface{} {
92 oldAsList, ok := r.OldValue.([]interface{})
93 if !ok {
94 return nil
95 }
96
97 asList, ok := r.Value.([]interface{})
98 if !ok {
99 return nil
100 } else if len(asList) <= index {
101 // Cannot correlate out of bounds index
102 return nil
103 }
104
105 listType := r.Schema.XListType()
106 switch listType {
107 case "map":
108 // Look up keys for this index in current object
109 currentElement := asList[index]
110
111 oldList := r.mapList
112 if oldList == nil {
113 oldList = MakeMapList(r.Schema, oldAsList)
114 r.mapList = oldList
115 }
116 return oldList.Get(currentElement)
117
118 case "set":
119 // Are sets correlatable? Only if the old value equals the current value.
120 // We might be able to support this, but do not currently see a lot
121 // of value
122 // (would allow you to add/remove items from sets with ratcheting but not change them)
123 return nil
124 case "":
125 fallthrough
126 case "atomic":
127 // Atomic lists are the default are not correlatable by item
128 // Ratcheting is not available on a per-index basis
129 return nil
130 default:
131 // Unrecognized list type. Assume non-correlatable.
132 return nil
133 }
134 }
135
136 // CachedDeepEqual is equivalent to reflect.DeepEqual, but caches the
137 // results in the tree of ratchetInvocationScratch objects on the way:
138 //
139 // For objects and arrays, this function will make a best effort to make
140 // use of past DeepEqual checks performed by this Node's children, if available.
141 //
142 // If a lazy computation could not be found for all children possibly due
143 // to validation logic short circuiting and skipping the children, then
144 // this function simply defers to reflect.DeepEqual.
145 func (r *CorrelatedObject) CachedDeepEqual() (res bool) {
146 start := time.Now()
147 defer func() {
148 if r != nil && r.Duration != nil {
149 *r.Duration += time.Since(start)
150 }
151 }()
152
153 if r == nil {
154 // Uncorrelatable node is not considered equal to its old value
155 return false
156 } else if r.comparisonResult != nil {
157 return *r.comparisonResult
158 }
159
160 defer func() {
161 r.comparisonResult = &res
162 }()
163
164 if r.Value == nil && r.OldValue == nil {
165 return true
166 } else if r.Value == nil || r.OldValue == nil {
167 return false
168 }
169
170 oldAsArray, oldIsArray := r.OldValue.([]interface{})
171 newAsArray, newIsArray := r.Value.([]interface{})
172
173 oldAsMap, oldIsMap := r.OldValue.(map[string]interface{})
174 newAsMap, newIsMap := r.Value.(map[string]interface{})
175
176 // If old and new are not the same type, they are not equal
177 if (oldIsArray != newIsArray) || oldIsMap != newIsMap {
178 return false
179 }
180
181 // Objects are known to be same type of (map, slice, or primitive)
182 switch {
183 case oldIsArray:
184 // Both arrays case. oldIsArray == newIsArray
185 if len(oldAsArray) != len(newAsArray) {
186 return false
187 }
188
189 for i := range newAsArray {
190 child := r.Index(i)
191 if child == nil {
192 if r.mapList == nil {
193 // Treat non-correlatable array as a unit with reflect.DeepEqual
194 return reflect.DeepEqual(oldAsArray, newAsArray)
195 }
196
197 // If array is correlatable, but old not found. Just short circuit
198 // comparison
199 return false
200
201 } else if !child.CachedDeepEqual() {
202 // If one child is not equal the entire object is not equal
203 return false
204 }
205 }
206
207 return true
208 case oldIsMap:
209 // Both maps case. oldIsMap == newIsMap
210 if len(oldAsMap) != len(newAsMap) {
211 return false
212 }
213
214 for k := range newAsMap {
215 child := r.Key(k)
216 if child == nil {
217 // Un-correlatable child due to key change.
218 // Objects are not equal.
219 return false
220 } else if !child.CachedDeepEqual() {
221 // If one child is not equal the entire object is not equal
222 return false
223 }
224 }
225
226 return true
227
228 default:
229 // Primitive: use reflect.DeepEqual
230 return reflect.DeepEqual(r.OldValue, r.Value)
231 }
232 }
233
234 // Key returns the child of the receiver with the given name.
235 // Returns nil if the given name is does not exist in the new object, or its
236 // value is not correlatable to an old value.
237 // If receiver is nil or if the new value is not an object/map, returns nil.
238 func (r *CorrelatedObject) Key(field string) *CorrelatedObject {
239 start := time.Now()
240 defer func() {
241 if r != nil && r.Duration != nil {
242 *r.Duration += time.Since(start)
243 }
244 }()
245
246 if r == nil || r.Schema == nil {
247 return nil
248 } else if existing, exists := r.children[field]; exists {
249 return existing
250 }
251
252 // Find correlated old value
253 oldAsMap, okOld := r.OldValue.(map[string]interface{})
254 newAsMap, okNew := r.Value.(map[string]interface{})
255 if !okOld || !okNew {
256 return nil
257 }
258
259 oldValueForField, okOld := oldAsMap[field]
260 newValueForField, okNew := newAsMap[field]
261 if !okOld || !okNew {
262 return nil
263 }
264
265 var propertySchema Schema
266 if prop, exists := r.Schema.Properties()[field]; exists {
267 propertySchema = prop
268 } else if addP := r.Schema.AdditionalProperties(); addP != nil && addP.Schema() != nil {
269 propertySchema = addP.Schema()
270 } else {
271 return nil
272 }
273
274 if r.children == nil {
275 r.children = make(map[interface{}]*CorrelatedObject, len(newAsMap))
276 }
277
278 res := &CorrelatedObject{
279 OldValue: oldValueForField,
280 Value: newValueForField,
281 Schema: propertySchema,
282 Duration: r.Duration,
283 }
284 r.children[field] = res
285 return res
286 }
287
288 // Index returns the child of the receiver at the given index.
289 // Returns nil if the given index is out of bounds, or its value is not
290 // correlatable to an old value.
291 // If receiver is nil or if the new value is not an array, returns nil.
292 func (r *CorrelatedObject) Index(i int) *CorrelatedObject {
293 start := time.Now()
294 defer func() {
295 if r != nil && r.Duration != nil {
296 *r.Duration += time.Since(start)
297 }
298 }()
299
300 if r == nil || r.Schema == nil {
301 return nil
302 } else if existing, exists := r.children[i]; exists {
303 return existing
304 }
305
306 asList, ok := r.Value.([]interface{})
307 if !ok || len(asList) <= i {
308 return nil
309 }
310
311 oldValueForIndex := r.correlateOldValueForChildAtNewIndex(i)
312 if oldValueForIndex == nil {
313 return nil
314 }
315 var itemSchema Schema
316 if i := r.Schema.Items(); i != nil {
317 itemSchema = i
318 } else {
319 return nil
320 }
321
322 if r.children == nil {
323 r.children = make(map[interface{}]*CorrelatedObject, len(asList))
324 }
325
326 res := &CorrelatedObject{
327 OldValue: oldValueForIndex,
328 Value: asList[i],
329 Schema: itemSchema,
330 Duration: r.Duration,
331 }
332 r.children[i] = res
333 return res
334 }