Debian Codegraph @

pkg/cel/common/values.go

raw
1 /*
2 Copyright 2021 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 "fmt"
21 "reflect"
22 "sync"
23 "time"
24
25 "github.com/google/cel-go/common/types"
26 "github.com/google/cel-go/common/types/ref"
27 "github.com/google/cel-go/common/types/traits"
28
29 "k8s.io/kube-openapi/pkg/validation/strfmt"
30
31 "k8s.io/apimachinery/pkg/api/equality"
32 "k8s.io/apiserver/pkg/cel"
33 )
34
35 // UnstructuredToVal converts a Kubernetes unstructured data element to a CEL Val.
36 // The root schema of custom resource schema is expected contain type meta and object meta schemas.
37 // If Embedded resources do not contain type meta and object meta schemas, they will be added automatically.
38 func UnstructuredToVal(unstructured interface{}, schema Schema) ref.Val {
39 if unstructured == nil {
40 if schema.Nullable() {
41 return types.NullValue
42 }
43 return types.NewErr("invalid data, got null for schema with nullable=false")
44 }
45 if schema.IsXIntOrString() {
46 switch v := unstructured.(type) {
47 case string:
48 return types.String(v)
49 case int:
50 return types.Int(v)
51 case int32:
52 return types.Int(v)
53 case int64:
54 return types.Int(v)
55 }
56 return types.NewErr("invalid data, expected XIntOrString value to be either a string or integer")
57 }
58 if schema.Type() == "object" {
59 m, ok := unstructured.(map[string]interface{})
60 if !ok {
61 return types.NewErr("invalid data, expected a map for the provided schema with type=object")
62 }
63 if schema.IsXEmbeddedResource() || schema.Properties() != nil {
64 if schema.IsXEmbeddedResource() {
65 schema = schema.WithTypeAndObjectMeta()
66 }
67 return &unstructuredMap{
68 value: m,
69 schema: schema,
70 propSchema: func(key string) (Schema, bool) {
71 if schema, ok := schema.Properties()[key]; ok {
72 return schema, true
73 }
74 return nil, false
75 },
76 }
77 }
78 if schema.AdditionalProperties() != nil && schema.AdditionalProperties().Schema() != nil {
79 return &unstructuredMap{
80 value: m,
81 schema: schema,
82 propSchema: func(key string) (Schema, bool) {
83 return schema.AdditionalProperties().Schema(), true
84 },
85 }
86 }
87
88 // properties and additionalProperties are mutual exclusive, but nothing prevents the situation
89 // where both are missing.
90 // An object that (1) has no properties (2) has no additionalProperties or additionalProperties == false
91 // is treated as an empty object.
92 // An object that has additionalProperties == true is treated as an unstructured map.
93 // An object that has x-kubernetes-preserve-unknown-field extension set is treated as an unstructured map.
94 // Empty object vs unstructured map is differentiated by unstructuredMap implementation with the set schema.
95 // The resulting result remains the same.
96 return &unstructuredMap{
97 value: m,
98 schema: schema,
99 propSchema: func(key string) (Schema, bool) {
100 return nil, false
101 },
102 }
103 }
104
105 if schema.Type() == "array" {
106 l, ok := unstructured.([]interface{})
107 if !ok {
108 return types.NewErr("invalid data, expected an array for the provided schema with type=array")
109 }
110 if schema.Items() == nil {
111 return types.NewErr("invalid array type, expected Items with a non-empty Schema")
112 }
113 typedList := unstructuredList{elements: l, itemsSchema: schema.Items()}
114 listType := schema.XListType()
115 if listType != "" {
116 switch listType {
117 case "map":
118 mapKeys := schema.XListMapKeys()
119 return &unstructuredMapList{unstructuredList: typedList, escapedKeyProps: escapeKeyProps(mapKeys)}
120 case "set":
121 return &unstructuredSetList{unstructuredList: typedList}
122 case "atomic":
123 return &typedList
124 default:
125 return types.NewErr("invalid x-kubernetes-list-type, expected 'map', 'set' or 'atomic' but got %s", listType)
126 }
127 }
128 return &typedList
129 }
130
131 if schema.Type() == "string" {
132 str, ok := unstructured.(string)
133 if !ok {
134 return types.NewErr("invalid data, expected string, got %T", unstructured)
135 }
136 switch schema.Format() {
137 case "duration":
138 d, err := strfmt.ParseDuration(str)
139 if err != nil {
140 return types.NewErr("Invalid duration %s: %v", str, err)
141 }
142 return types.Duration{Duration: d}
143 case "date":
144 d, err := time.Parse(strfmt.RFC3339FullDate, str) // strfmt uses this format for OpenAPIv3 value validation
145 if err != nil {
146 return types.NewErr("Invalid date formatted string %s: %v", str, err)
147 }
148 return types.Timestamp{Time: d}
149 case "date-time":
150 d, err := strfmt.ParseDateTime(str)
151 if err != nil {
152 return types.NewErr("Invalid date-time formatted string %s: %v", str, err)
153 }
154 return types.Timestamp{Time: time.Time(d)}
155 case "byte":
156 base64 := strfmt.Base64{}
157 err := base64.UnmarshalText([]byte(str))
158 if err != nil {
159 return types.NewErr("Invalid byte formatted string %s: %v", str, err)
160 }
161 return types.Bytes(base64)
162 }
163
164 return types.String(str)
165 }
166 if schema.Type() == "number" {
167 switch v := unstructured.(type) {
168 // float representations of whole numbers (e.g. 1.0, 0.0) can convert to int representations (e.g. 1, 0) in yaml
169 // to json translation, and then get parsed as int64s
170 case int:
171 return types.Double(v)
172 case int32:
173 return types.Double(v)
174 case int64:
175 return types.Double(v)
176
177 case float32:
178 return types.Double(v)
179 case float64:
180 return types.Double(v)
181 default:
182 return types.NewErr("invalid data, expected float, got %T", unstructured)
183 }
184 }
185 if schema.Type() == "integer" {
186 switch v := unstructured.(type) {
187 case int:
188 return types.Int(v)
189 case int32:
190 return types.Int(v)
191 case int64:
192 return types.Int(v)
193 default:
194 return types.NewErr("invalid data, expected int, got %T", unstructured)
195 }
196 }
197 if schema.Type() == "boolean" {
198 b, ok := unstructured.(bool)
199 if !ok {
200 return types.NewErr("invalid data, expected bool, got %T", unstructured)
201 }
202 return types.Bool(b)
203 }
204
205 if schema.IsXPreserveUnknownFields() {
206 return &unknownPreserved{u: unstructured}
207 }
208
209 return types.NewErr("invalid type, expected object, array, number, integer, boolean or string, or no type with x-kubernetes-int-or-string or x-kubernetes-preserve-unknown-fields is true, got %s", schema.Type())
210 }
211
212 // unknownPreserved represents unknown data preserved in custom resources via x-kubernetes-preserve-unknown-fields.
213 // It preserves the data at runtime without assuming it is of any particular type and supports only equality checking.
214 // unknownPreserved should be used only for values are not directly accessible in CEL expressions, i.e. for data
215 // where there is no corresponding CEL type declaration.
216 type unknownPreserved struct {
217 u interface{}
218 }
219
220 func (t *unknownPreserved) ConvertToNative(refType reflect.Type) (interface{}, error) {
221 return nil, fmt.Errorf("type conversion to '%s' not supported for values preserved by x-kubernetes-preserve-unknown-fields", refType)
222 }
223
224 func (t *unknownPreserved) ConvertToType(typeValue ref.Type) ref.Val {
225 return types.NewErr("type conversion to '%s' not supported for values preserved by x-kubernetes-preserve-unknown-fields", typeValue.TypeName())
226 }
227
228 func (t *unknownPreserved) Equal(other ref.Val) ref.Val {
229 return types.Bool(equality.Semantic.DeepEqual(t.u, other.Value()))
230 }
231
232 func (t *unknownPreserved) Type() ref.Type {
233 return types.UnknownType
234 }
235
236 func (t *unknownPreserved) Value() interface{} {
237 return t.u // used by Equal checks
238 }
239
240 // unstructuredMapList represents an unstructured data instance of an OpenAPI array with x-kubernetes-list-type=map.
241 type unstructuredMapList struct {
242 unstructuredList
243 escapedKeyProps []string
244
245 sync.Once // for for lazy load of mapOfList since it is only needed if Equals is called
246 mapOfList map[interface{}]interface{}
247 }
248
249 func (t *unstructuredMapList) getMap() map[interface{}]interface{} {
250 t.Do(func() {
251 t.mapOfList = make(map[interface{}]interface{}, len(t.elements))
252 for _, e := range t.elements {
253 t.mapOfList[t.toMapKey(e)] = e
254 }
255 })
256 return t.mapOfList
257 }
258
259 // toMapKey returns a valid golang map key for the given element of the map list.
260 // element must be a valid map list entry where all map key props are scalar types (which are comparable in go
261 // and valid for use in a golang map key).
262 func (t *unstructuredMapList) toMapKey(element interface{}) interface{} {
263 eObj, ok := element.(map[string]interface{})
264 if !ok {
265 return types.NewErr("unexpected data format for element of array with x-kubernetes-list-type=map: %T", element)
266 }
267 // Arrays are comparable in go and may be used as map keys, but maps and slices are not.
268 // So we can special case small numbers of key props as arrays and fall back to serialization
269 // for larger numbers of key props
270 if len(t.escapedKeyProps) == 1 {
271 return eObj[t.escapedKeyProps[0]]
272 }
273 if len(t.escapedKeyProps) == 2 {
274 return [2]interface{}{eObj[t.escapedKeyProps[0]], eObj[t.escapedKeyProps[1]]}
275 }
276 if len(t.escapedKeyProps) == 3 {
277 return [3]interface{}{eObj[t.escapedKeyProps[0]], eObj[t.escapedKeyProps[1]], eObj[t.escapedKeyProps[2]]}
278 }
279
280 key := make([]interface{}, len(t.escapedKeyProps))
281 for i, kf := range t.escapedKeyProps {
282 key[i] = eObj[kf]
283 }
284 return fmt.Sprintf("%v", key)
285 }
286
287 // Equal on a map list ignores list element order.
288 func (t *unstructuredMapList) Equal(other ref.Val) ref.Val {
289 oMapList, ok := other.(traits.Lister)
290 if !ok {
291 return types.MaybeNoSuchOverloadErr(other)
292 }
293 sz := types.Int(len(t.elements))
294 if sz != oMapList.Size() {
295 return types.False
296 }
297 tMap := t.getMap()
298 for it := oMapList.Iterator(); it.HasNext() == types.True; {
299 v := it.Next()
300 k := t.toMapKey(v.Value())
301 tVal, ok := tMap[k]
302 if !ok {
303 return types.False
304 }
305 eq := UnstructuredToVal(tVal, t.itemsSchema).Equal(v)
306 if eq != types.True {
307 return eq // either false or error
308 }
309 }
310 return types.True
311 }
312
313 // Add for a map list `X + Y` performs a merge where the array positions of all keys in `X` are preserved but the values
314 // are overwritten by values in `Y` when the key sets of `X` and `Y` intersect. Elements in `Y` with
315 // non-intersecting keys are appended, retaining their partial order.
316 func (t *unstructuredMapList) Add(other ref.Val) ref.Val {
317 oMapList, ok := other.(traits.Lister)
318 if !ok {
319 return types.MaybeNoSuchOverloadErr(other)
320 }
321 elements := make([]interface{}, len(t.elements))
322 keyToIdx := map[interface{}]int{}
323 for i, e := range t.elements {
324 k := t.toMapKey(e)
325 keyToIdx[k] = i
326 elements[i] = e
327 }
328 for it := oMapList.Iterator(); it.HasNext() == types.True; {
329 v := it.Next().Value()
330 k := t.toMapKey(v)
331 if overwritePosition, ok := keyToIdx[k]; ok {
332 elements[overwritePosition] = v
333 } else {
334 elements = append(elements, v)
335 }
336 }
337 return &unstructuredMapList{
338 unstructuredList: unstructuredList{elements: elements, itemsSchema: t.itemsSchema},
339 escapedKeyProps: t.escapedKeyProps,
340 }
341 }
342
343 // escapeKeyProps returns identifiers with Escape applied to each.
344 // Identifiers that cannot be escaped are left as-is. They are inaccessible to CEL programs but are
345 // are still needed internally to perform equality checks.
346 func escapeKeyProps(idents []string) []string {
347 result := make([]string, len(idents))
348 for i, prop := range idents {
349 if escaped, ok := cel.Escape(prop); ok {
350 result[i] = escaped
351 } else {
352 result[i] = prop
353 }
354 }
355 return result
356 }
357
358 // unstructuredSetList represents an unstructured data instance of an OpenAPI array with x-kubernetes-list-type=set.
359 type unstructuredSetList struct {
360 unstructuredList
361 escapedKeyProps []string
362
363 sync.Once // for for lazy load of setOfList since it is only needed if Equals is called
364 set map[interface{}]struct{}
365 }
366
367 func (t *unstructuredSetList) getSet() map[interface{}]struct{} {
368 // sets are only allowed to contain scalar elements, which are comparable in go, and can safely be used as
369 // golang map keys
370 t.Do(func() {
371 t.set = make(map[interface{}]struct{}, len(t.elements))
372 for _, e := range t.elements {
373 t.set[e] = struct{}{}
374 }
375 })
376 return t.set
377 }
378
379 // Equal on a map list ignores list element order.
380 func (t *unstructuredSetList) Equal(other ref.Val) ref.Val {
381 oSetList, ok := other.(traits.Lister)
382 if !ok {
383 return types.MaybeNoSuchOverloadErr(other)
384 }
385 sz := types.Int(len(t.elements))
386 if sz != oSetList.Size() {
387 return types.False
388 }
389 tSet := t.getSet()
390 for it := oSetList.Iterator(); it.HasNext() == types.True; {
391 next := it.Next().Value()
392 _, ok := tSet[next]
393 if !ok {
394 return types.False
395 }
396 }
397 return types.True
398 }
399
400 // Add for a set list `X + Y` performs a union where the array positions of all elements in `X` are preserved and
401 // non-intersecting elements in `Y` are appended, retaining their partial order.
402 func (t *unstructuredSetList) Add(other ref.Val) ref.Val {
403 oSetList, ok := other.(traits.Lister)
404 if !ok {
405 return types.MaybeNoSuchOverloadErr(other)
406 }
407 elements := t.elements
408 set := t.getSet()
409 for it := oSetList.Iterator(); it.HasNext() == types.True; {
410 next := it.Next().Value()
411 if _, ok := set[next]; !ok {
412 set[next] = struct{}{}
413 elements = append(elements, next)
414 }
415 }
416 return &unstructuredSetList{
417 unstructuredList: unstructuredList{elements: elements, itemsSchema: t.itemsSchema},
418 escapedKeyProps: t.escapedKeyProps,
419 }
420 }
421
422 // unstructuredList represents an unstructured data instance of an OpenAPI array with x-kubernetes-list-type=atomic (the default).
423 type unstructuredList struct {
424 elements []interface{}
425 itemsSchema Schema
426 }
427
428 var _ = traits.Lister(&unstructuredList{})
429
430 func (t *unstructuredList) ConvertToNative(typeDesc reflect.Type) (interface{}, error) {
431 switch typeDesc.Kind() {
432 case reflect.Slice:
433 switch t.itemsSchema.Type() {
434 // Workaround for https://github.com/kubernetes/kubernetes/issues/117590 until we
435 // resolve the desired behavior in cel-go via https://github.com/google/cel-go/issues/688
436 case "string":
437 var result []string
438 for _, e := range t.elements {
439 s, ok := e.(string)
440 if !ok {
441 return nil, fmt.Errorf("expected all elements to be of type string, but got %T", e)
442 }
443 result = append(result, s)
444 }
445 return result, nil
446 default:
447 return t.elements, nil
448 }
449 }
450 return nil, fmt.Errorf("type conversion error from '%s' to '%s'", t.Type(), typeDesc)
451 }
452
453 func (t *unstructuredList) ConvertToType(typeValue ref.Type) ref.Val {
454 switch typeValue {
455 case types.ListType:
456 return t
457 case types.TypeType:
458 return types.ListType
459 }
460 return types.NewErr("type conversion error from '%s' to '%s'", t.Type(), typeValue.TypeName())
461 }
462
463 func (t *unstructuredList) Equal(other ref.Val) ref.Val {
464 oList, ok := other.(traits.Lister)
465 if !ok {
466 return types.MaybeNoSuchOverloadErr(other)
467 }
468 sz := types.Int(len(t.elements))
469 if sz != oList.Size() {
470 return types.False
471 }
472 for i := types.Int(0); i < sz; i++ {
473 eq := t.Get(i).Equal(oList.Get(i))
474 if eq != types.True {
475 return eq // either false or error
476 }
477 }
478 return types.True
479 }
480
481 func (t *unstructuredList) Type() ref.Type {
482 return types.ListType
483 }
484
485 func (t *unstructuredList) Value() interface{} {
486 return t.elements
487 }
488
489 func (t *unstructuredList) Add(other ref.Val) ref.Val {
490 oList, ok := other.(traits.Lister)
491 if !ok {
492 return types.MaybeNoSuchOverloadErr(other)
493 }
494 elements := t.elements
495 for it := oList.Iterator(); it.HasNext() == types.True; {
496 next := it.Next().Value()
497 elements = append(elements, next)
498 }
499
500 return &unstructuredList{elements: elements, itemsSchema: t.itemsSchema}
501 }
502
503 func (t *unstructuredList) Contains(val ref.Val) ref.Val {
504 if types.IsUnknownOrError(val) {
505 return val
506 }
507 var err ref.Val
508 sz := len(t.elements)
509 for i := 0; i < sz; i++ {
510 elem := UnstructuredToVal(t.elements[i], t.itemsSchema)
511 cmp := elem.Equal(val)
512 b, ok := cmp.(types.Bool)
513 if !ok && err == nil {
514 err = types.MaybeNoSuchOverloadErr(cmp)
515 }
516 if b == types.True {
517 return types.True
518 }
519 }
520 if err != nil {
521 return err
522 }
523 return types.False
524 }
525
526 func (t *unstructuredList) Get(idx ref.Val) ref.Val {
527 iv, isInt := idx.(types.Int)
528 if !isInt {
529 return types.ValOrErr(idx, "unsupported index: %v", idx)
530 }
531 i := int(iv)
532 if i < 0 || i >= len(t.elements) {
533 return types.NewErr("index out of bounds: %v", idx)
534 }
535 return UnstructuredToVal(t.elements[i], t.itemsSchema)
536 }
537
538 func (t *unstructuredList) Iterator() traits.Iterator {
539 items := make([]ref.Val, len(t.elements))
540 for i, item := range t.elements {
541 itemCopy := item
542 items[i] = UnstructuredToVal(itemCopy, t.itemsSchema)
543 }
544 return &listIterator{unstructuredList: t, items: items}
545 }
546
547 type listIterator struct {
548 *unstructuredList
549 items []ref.Val
550 idx int
551 }
552
553 func (it *listIterator) HasNext() ref.Val {
554 return types.Bool(it.idx < len(it.items))
555 }
556
557 func (it *listIterator) Next() ref.Val {
558 item := it.items[it.idx]
559 it.idx++
560 return item
561 }
562
563 func (t *unstructuredList) Size() ref.Val {
564 return types.Int(len(t.elements))
565 }
566
567 // unstructuredMap represented an unstructured data instance of an OpenAPI object.
568 type unstructuredMap struct {
569 value map[string]interface{}
570 schema Schema
571 // propSchema finds the schema to use for a particular map key.
572 propSchema func(key string) (Schema, bool)
573 }
574
575 var _ = traits.Mapper(&unstructuredMap{})
576
577 func (t *unstructuredMap) ConvertToNative(typeDesc reflect.Type) (interface{}, error) {
578 switch typeDesc.Kind() {
579 case reflect.Map:
580 return t.value, nil
581 }
582 return nil, fmt.Errorf("type conversion error from '%s' to '%s'", t.Type(), typeDesc)
583 }
584
585 func (t *unstructuredMap) ConvertToType(typeValue ref.Type) ref.Val {
586 switch typeValue {
587 case types.MapType:
588 return t
589 case types.TypeType:
590 return types.MapType
591 }
592 return types.NewErr("type conversion error from '%s' to '%s'", t.Type(), typeValue.TypeName())
593 }
594
595 func (t *unstructuredMap) Equal(other ref.Val) ref.Val {
596 oMap, isMap := other.(traits.Mapper)
597 if !isMap {
598 return types.MaybeNoSuchOverloadErr(other)
599 }
600 if t.Size() != oMap.Size() {
601 return types.False
602 }
603 for key, value := range t.value {
604 if propSchema, ok := t.propSchema(key); ok {
605 ov, found := oMap.Find(types.String(key))
606 if !found {
607 return types.False
608 }
609 v := UnstructuredToVal(value, propSchema)
610 vEq := v.Equal(ov)
611 if vEq != types.True {
612 return vEq // either false or error
613 }
614 } else {
615 // Must be an object with properties.
616 // Since we've encountered an unknown field, fallback to unstructured equality checking.
617 ouMap, ok := other.(*unstructuredMap)
618 if !ok {
619 // The compiler ensures equality is against the same type of object, so this should be unreachable
620 return types.MaybeNoSuchOverloadErr(other)
621 }
622 if oValue, ok := ouMap.value[key]; ok {
623 if !equality.Semantic.DeepEqual(value, oValue) {
624 return types.False
625 }
626 }
627 }
628 }
629 return types.True
630 }
631
632 func (t *unstructuredMap) Type() ref.Type {
633 return types.MapType
634 }
635
636 func (t *unstructuredMap) Value() interface{} {
637 return t.value
638 }
639
640 func (t *unstructuredMap) Contains(key ref.Val) ref.Val {
641 v, found := t.Find(key)
642 if v != nil && types.IsUnknownOrError(v) {
643 return v
644 }
645
646 return types.Bool(found)
647 }
648
649 func (t *unstructuredMap) Get(key ref.Val) ref.Val {
650 v, found := t.Find(key)
651 if found {
652 return v
653 }
654 return types.ValOrErr(key, "no such key: %v", key)
655 }
656
657 func (t *unstructuredMap) Iterator() traits.Iterator {
658 isObject := t.schema.Properties() != nil
659 keys := make([]ref.Val, len(t.value))
660 i := 0
661 for k := range t.value {
662 if _, ok := t.propSchema(k); ok {
663 mapKey := k
664 if isObject {
665 if escaped, ok := cel.Escape(k); ok {
666 mapKey = escaped
667 }
668 }
669 keys[i] = types.String(mapKey)
670 i++
671 }
672 }
673 return &mapIterator{unstructuredMap: t, keys: keys}
674 }
675
676 type mapIterator struct {
677 *unstructuredMap
678 keys []ref.Val
679 idx int
680 }
681
682 func (it *mapIterator) HasNext() ref.Val {
683 return types.Bool(it.idx < len(it.keys))
684 }
685
686 func (it *mapIterator) Next() ref.Val {
687 key := it.keys[it.idx]
688 it.idx++
689 return key
690 }
691
692 func (t *unstructuredMap) Size() ref.Val {
693 return types.Int(len(t.value))
694 }
695
696 func (t *unstructuredMap) Find(key ref.Val) (ref.Val, bool) {
697 isObject := t.schema.Properties() != nil
698 keyStr, ok := key.(types.String)
699 if !ok {
700 return types.MaybeNoSuchOverloadErr(key), true
701 }
702 k := keyStr.Value().(string)
703 if isObject {
704 k, ok = cel.Unescape(k)
705 if !ok {
706 return nil, false
707 }
708 }
709 if v, ok := t.value[k]; ok {
710 // If this is an object with properties, not an object with additionalProperties,
711 // then null valued nullable fields are treated the same as absent optional fields.
712 if isObject && v == nil {
713 return nil, false
714 }
715 if propSchema, ok := t.propSchema(k); ok {
716 return UnstructuredToVal(v, propSchema), true
717 }
718 }
719
720 return nil, false
721 }