| 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 |
} |