Debian Codegraph @

pkg/cel/types.go

raw
1 /*
2 Copyright 2022 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 cel
18
19 import (
20 "fmt"
21 "math"
22 "time"
23
24 "github.com/google/cel-go/cel"
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 exprpb "google.golang.org/genproto/googleapis/api/expr/v1alpha1"
30 "k8s.io/apimachinery/pkg/api/resource"
31 )
32
33 const (
34 noMaxLength = math.MaxInt
35 )
36
37 // NewListType returns a parameterized list type with a specified element type.
38 func NewListType(elem *DeclType, maxItems int64) *DeclType {
39 return &DeclType{
40 name: "list",
41 ElemType: elem,
42 MaxElements: maxItems,
43 celType: cel.ListType(elem.CelType()),
44 defaultValue: NewListValue(),
45 // a list can always be represented as [] in JSON, so hardcode the min size
46 // to 2
47 MinSerializedSize: 2,
48 }
49 }
50
51 // NewMapType returns a parameterized map type with the given key and element types.
52 func NewMapType(key, elem *DeclType, maxProperties int64) *DeclType {
53 return &DeclType{
54 name: "map",
55 KeyType: key,
56 ElemType: elem,
57 MaxElements: maxProperties,
58 celType: cel.MapType(key.CelType(), elem.CelType()),
59 defaultValue: NewMapValue(),
60 // a map can always be represented as {} in JSON, so hardcode the min size
61 // to 2
62 MinSerializedSize: 2,
63 }
64 }
65
66 // NewObjectType creates an object type with a qualified name and a set of field declarations.
67 func NewObjectType(name string, fields map[string]*DeclField) *DeclType {
68 t := &DeclType{
69 name: name,
70 Fields: fields,
71 celType: cel.ObjectType(name),
72 traitMask: traits.FieldTesterType | traits.IndexerType,
73 // an object could potentially be larger than the min size we default to here ({}),
74 // but we rely upon the caller to change MinSerializedSize accordingly if they add
75 // properties to the object
76 MinSerializedSize: 2,
77 }
78 t.defaultValue = NewObjectValue(t)
79 return t
80 }
81
82 func NewSimpleTypeWithMinSize(name string, celType *cel.Type, zeroVal ref.Val, minSize int64) *DeclType {
83 return &DeclType{
84 name: name,
85 celType: celType,
86 defaultValue: zeroVal,
87 MinSerializedSize: minSize,
88 }
89 }
90
91 // DeclType represents the universal type descriptor for OpenAPIv3 types.
92 type DeclType struct {
93 fmt.Stringer
94
95 name string
96 // Fields contains a map of escaped CEL identifier field names to field declarations.
97 Fields map[string]*DeclField
98 KeyType *DeclType
99 ElemType *DeclType
100 TypeParam bool
101 Metadata map[string]string
102 MaxElements int64
103 // MinSerializedSize represents the smallest possible size in bytes that
104 // the DeclType could be serialized to in JSON.
105 MinSerializedSize int64
106
107 celType *cel.Type
108 traitMask int
109 defaultValue ref.Val
110 }
111
112 // MaybeAssignTypeName attempts to set the DeclType name to a fully qualified name, if the type
113 // is of `object` type.
114 //
115 // The DeclType must return true for `IsObject` or this assignment will error.
116 func (t *DeclType) MaybeAssignTypeName(name string) *DeclType {
117 if t.IsObject() {
118 objUpdated := false
119 if t.name != "object" {
120 name = t.name
121 } else {
122 objUpdated = true
123 }
124 fieldMap := make(map[string]*DeclField, len(t.Fields))
125 for fieldName, field := range t.Fields {
126 fieldType := field.Type
127 fieldTypeName := fmt.Sprintf("%s.%s", name, fieldName)
128 updated := fieldType.MaybeAssignTypeName(fieldTypeName)
129 if updated == fieldType {
130 fieldMap[fieldName] = field
131 continue
132 }
133 objUpdated = true
134 fieldMap[fieldName] = &DeclField{
135 Name: fieldName,
136 Type: updated,
137 Required: field.Required,
138 enumValues: field.enumValues,
139 defaultValue: field.defaultValue,
140 }
141 }
142 if !objUpdated {
143 return t
144 }
145 return &DeclType{
146 name: name,
147 Fields: fieldMap,
148 KeyType: t.KeyType,
149 ElemType: t.ElemType,
150 TypeParam: t.TypeParam,
151 Metadata: t.Metadata,
152 celType: cel.ObjectType(name),
153 traitMask: t.traitMask,
154 defaultValue: t.defaultValue,
155 MinSerializedSize: t.MinSerializedSize,
156 }
157 }
158 if t.IsMap() {
159 elemTypeName := fmt.Sprintf("%s.@elem", name)
160 updated := t.ElemType.MaybeAssignTypeName(elemTypeName)
161 if updated == t.ElemType {
162 return t
163 }
164 return NewMapType(t.KeyType, updated, t.MaxElements)
165 }
166 if t.IsList() {
167 elemTypeName := fmt.Sprintf("%s.@idx", name)
168 updated := t.ElemType.MaybeAssignTypeName(elemTypeName)
169 if updated == t.ElemType {
170 return t
171 }
172 return NewListType(updated, t.MaxElements)
173 }
174 return t
175 }
176
177 // ExprType returns the CEL expression type of this declaration.
178 func (t *DeclType) ExprType() (*exprpb.Type, error) {
179 return cel.TypeToExprType(t.celType)
180 }
181
182 // CelType returns the CEL type of this declaration.
183 func (t *DeclType) CelType() *cel.Type {
184 return t.celType
185 }
186
187 // FindField returns the DeclField with the given name if present.
188 func (t *DeclType) FindField(name string) (*DeclField, bool) {
189 f, found := t.Fields[name]
190 return f, found
191 }
192
193 // HasTrait implements the CEL ref.Type interface making this type declaration suitable for use
194 // within the CEL evaluator.
195 func (t *DeclType) HasTrait(trait int) bool {
196 if t.traitMask&trait == trait {
197 return true
198 }
199 if t.defaultValue == nil {
200 return false
201 }
202 _, isDecl := t.defaultValue.Type().(*DeclType)
203 if isDecl {
204 return false
205 }
206 return t.defaultValue.Type().HasTrait(trait)
207 }
208
209 // IsList returns whether the declaration is a `list` type which defines a parameterized element
210 // type, but not a parameterized key type or fields.
211 func (t *DeclType) IsList() bool {
212 return t.KeyType == nil && t.ElemType != nil && t.Fields == nil
213 }
214
215 // IsMap returns whether the declaration is a 'map' type which defines parameterized key and
216 // element types, but not fields.
217 func (t *DeclType) IsMap() bool {
218 return t.KeyType != nil && t.ElemType != nil && t.Fields == nil
219 }
220
221 // IsObject returns whether the declartion is an 'object' type which defined a set of typed fields.
222 func (t *DeclType) IsObject() bool {
223 return t.KeyType == nil && t.ElemType == nil && t.Fields != nil
224 }
225
226 // String implements the fmt.Stringer interface method.
227 func (t *DeclType) String() string {
228 return t.name
229 }
230
231 // TypeName returns the fully qualified type name for the DeclType.
232 func (t *DeclType) TypeName() string {
233 return t.name
234 }
235
236 // DefaultValue returns the CEL ref.Val representing the default value for this object type,
237 // if one exists.
238 func (t *DeclType) DefaultValue() ref.Val {
239 return t.defaultValue
240 }
241
242 // FieldTypeMap constructs a map of the field and object types nested within a given type.
243 func FieldTypeMap(path string, t *DeclType) map[string]*DeclType {
244 if t.IsObject() && t.TypeName() != "object" {
245 path = t.TypeName()
246 }
247 types := make(map[string]*DeclType)
248 buildDeclTypes(path, t, types)
249 return types
250 }
251
252 func buildDeclTypes(path string, t *DeclType, types map[string]*DeclType) {
253 // Ensure object types are properly named according to where they appear in the schema.
254 if t.IsObject() {
255 // Hack to ensure that names are uniquely qualified and work well with the type
256 // resolution steps which require fully qualified type names for field resolution
257 // to function properly.
258 types[t.TypeName()] = t
259 for name, field := range t.Fields {
260 fieldPath := fmt.Sprintf("%s.%s", path, name)
261 buildDeclTypes(fieldPath, field.Type, types)
262 }
263 }
264 // Map element properties to type names if needed.
265 if t.IsMap() {
266 mapElemPath := fmt.Sprintf("%s.@elem", path)
267 buildDeclTypes(mapElemPath, t.ElemType, types)
268 types[path] = t
269 }
270 // List element properties.
271 if t.IsList() {
272 listIdxPath := fmt.Sprintf("%s.@idx", path)
273 buildDeclTypes(listIdxPath, t.ElemType, types)
274 types[path] = t
275 }
276 }
277
278 // DeclField describes the name, ordinal, and optionality of a field declaration within a type.
279 type DeclField struct {
280 Name string
281 Type *DeclType
282 Required bool
283 enumValues []interface{}
284 defaultValue interface{}
285 }
286
287 func NewDeclField(name string, declType *DeclType, required bool, enumValues []interface{}, defaultValue interface{}) *DeclField {
288 return &DeclField{
289 Name: name,
290 Type: declType,
291 Required: required,
292 enumValues: enumValues,
293 defaultValue: defaultValue,
294 }
295 }
296
297 // TypeName returns the string type name of the field.
298 func (f *DeclField) TypeName() string {
299 return f.Type.TypeName()
300 }
301
302 // DefaultValue returns the zero value associated with the field.
303 func (f *DeclField) DefaultValue() ref.Val {
304 if f.defaultValue != nil {
305 return types.DefaultTypeAdapter.NativeToValue(f.defaultValue)
306 }
307 return f.Type.DefaultValue()
308 }
309
310 // EnumValues returns the set of values that this field may take.
311 func (f *DeclField) EnumValues() []ref.Val {
312 if f.enumValues == nil || len(f.enumValues) == 0 {
313 return []ref.Val{}
314 }
315 ev := make([]ref.Val, len(f.enumValues))
316 for i, e := range f.enumValues {
317 ev[i] = types.DefaultTypeAdapter.NativeToValue(e)
318 }
319 return ev
320 }
321
322 func allTypesForDecl(declTypes []*DeclType) map[string]*DeclType {
323 if declTypes == nil {
324 return nil
325 }
326 allTypes := map[string]*DeclType{}
327 for _, declType := range declTypes {
328 for k, t := range FieldTypeMap(declType.TypeName(), declType) {
329 allTypes[k] = t
330 }
331 }
332
333 return allTypes
334 }
335
336 // NewDeclTypeProvider returns an Open API Schema-based type-system which is CEL compatible.
337 func NewDeclTypeProvider(rootTypes ...*DeclType) *DeclTypeProvider {
338 // Note, if the schema indicates that it's actually based on another proto
339 // then prefer the proto definition. For expressions in the proto, a new field
340 // annotation will be needed to indicate the expected environment and type of
341 // the expression.
342 allTypes := allTypesForDecl(rootTypes)
343 return &DeclTypeProvider{
344 registeredTypes: allTypes,
345 }
346 }
347
348 // DeclTypeProvider extends the CEL ref.TypeProvider interface and provides an Open API Schema-based
349 // type-system.
350 type DeclTypeProvider struct {
351 registeredTypes map[string]*DeclType
352 typeProvider types.Provider
353 typeAdapter types.Adapter
354 recognizeKeywordAsFieldName bool
355 }
356
357 func (rt *DeclTypeProvider) SetRecognizeKeywordAsFieldName(recognize bool) {
358 rt.recognizeKeywordAsFieldName = recognize
359 }
360
361 func (rt *DeclTypeProvider) EnumValue(enumName string) ref.Val {
362 return rt.typeProvider.EnumValue(enumName)
363 }
364
365 func (rt *DeclTypeProvider) FindIdent(identName string) (ref.Val, bool) {
366 return rt.typeProvider.FindIdent(identName)
367 }
368
369 // EnvOptions returns a set of cel.EnvOption values which includes the declaration set
370 // as well as a custom ref.TypeProvider.
371 //
372 // If the DeclTypeProvider value is nil, an empty []cel.EnvOption set is returned.
373 func (rt *DeclTypeProvider) EnvOptions(tp types.Provider) ([]cel.EnvOption, error) {
374 if rt == nil {
375 return []cel.EnvOption{}, nil
376 }
377 rtWithTypes, err := rt.WithTypeProvider(tp)
378 if err != nil {
379 return nil, err
380 }
381 return []cel.EnvOption{
382 cel.CustomTypeProvider(rtWithTypes),
383 cel.CustomTypeAdapter(rtWithTypes),
384 }, nil
385 }
386
387 // WithTypeProvider returns a new DeclTypeProvider that sets the given TypeProvider
388 // If the original DeclTypeProvider is nil, the returned DeclTypeProvider is still nil.
389 func (rt *DeclTypeProvider) WithTypeProvider(tp types.Provider) (*DeclTypeProvider, error) {
390 if rt == nil {
391 return nil, nil
392 }
393 var ta types.Adapter = types.DefaultTypeAdapter
394 tpa, ok := tp.(types.Adapter)
395 if ok {
396 ta = tpa
397 }
398 rtWithTypes := &DeclTypeProvider{
399 typeProvider: tp,
400 typeAdapter: ta,
401 registeredTypes: rt.registeredTypes,
402 recognizeKeywordAsFieldName: rt.recognizeKeywordAsFieldName,
403 }
404 for name, declType := range rt.registeredTypes {
405 tpType, found := tp.FindStructType(name)
406 // cast celType to types.type
407
408 expT := declType.CelType()
409 if found && !expT.IsExactType(tpType) {
410 return nil, fmt.Errorf(
411 "type %s definition differs between CEL environment and type provider", name)
412 }
413
414 }
415 return rtWithTypes, nil
416 }
417
418 // FindStructType attempts to resolve the typeName provided from the rule's rule-schema, or if not
419 // from the embedded ref.TypeProvider.
420 //
421 // FindStructType overrides the default type-finding behavior of the embedded TypeProvider.
422 //
423 // Note, when the type name is based on the Open API Schema, the name will reflect the object path
424 // where the type definition appears.
425 func (rt *DeclTypeProvider) FindStructType(typeName string) (*types.Type, bool) {
426 if rt == nil {
427 return nil, false
428 }
429 declType, found := rt.findDeclType(typeName)
430 if found {
431 expT := declType.CelType()
432 return types.NewTypeTypeWithParam(expT), found
433 }
434 return rt.typeProvider.FindStructType(typeName)
435 }
436
437 // FindDeclType returns the CPT type description which can be mapped to a CEL type.
438 func (rt *DeclTypeProvider) FindDeclType(typeName string) (*DeclType, bool) {
439 if rt == nil {
440 return nil, false
441 }
442 return rt.findDeclType(typeName)
443 }
444
445 // FindStructFieldNames returns the field names associated with the type, if the type
446 // is found.
447 func (rt *DeclTypeProvider) FindStructFieldNames(typeName string) ([]string, bool) {
448 return []string{}, false
449 }
450
451 // FindStructFieldType returns a field type given a type name and field name, if found.
452 //
453 // Note, the type name for an Open API Schema type is likely to be its qualified object path.
454 // If, in the future an object instance rather than a type name were provided, the field
455 // resolution might more accurately reflect the expected type model. However, in this case
456 // concessions were made to align with the existing CEL interfaces.
457 func (rt *DeclTypeProvider) FindStructFieldType(typeName, fieldName string) (*types.FieldType, bool) {
458 st, found := rt.findDeclType(typeName)
459 if !found {
460 return rt.typeProvider.FindStructFieldType(typeName, fieldName)
461 }
462
463 f, found := st.Fields[fieldName]
464 if rt.recognizeKeywordAsFieldName && !found && celReservedSymbols.Has(fieldName) {
465 f, found = st.Fields["__"+fieldName+"__"]
466 }
467
468 if found {
469 ft := f.Type
470 expT := ft.CelType()
471 return &types.FieldType{
472 Type: expT,
473 }, true
474 }
475 // This could be a dynamic map.
476 if st.IsMap() {
477 et := st.ElemType
478 expT := et.CelType()
479 return &types.FieldType{
480 Type: expT,
481 }, true
482 }
483 return nil, false
484 }
485
486 // NativeToValue is an implementation of the ref.TypeAdapater interface which supports conversion
487 // of rule values to CEL ref.Val instances.
488 func (rt *DeclTypeProvider) NativeToValue(val interface{}) ref.Val {
489 return rt.typeAdapter.NativeToValue(val)
490 }
491
492 func (rt *DeclTypeProvider) NewValue(typeName string, fields map[string]ref.Val) ref.Val {
493 // TODO: implement for OpenAPI types to enable CEL object instantiation, which is needed
494 // for mutating admission.
495 return rt.typeProvider.NewValue(typeName, fields)
496 }
497
498 // TypeNames returns the list of type names declared within the DeclTypeProvider object.
499 func (rt *DeclTypeProvider) TypeNames() []string {
500 typeNames := make([]string, len(rt.registeredTypes))
501 i := 0
502 for name := range rt.registeredTypes {
503 typeNames[i] = name
504 i++
505 }
506 return typeNames
507 }
508
509 func (rt *DeclTypeProvider) findDeclType(typeName string) (*DeclType, bool) {
510 declType, found := rt.registeredTypes[typeName]
511 if found {
512 return declType, true
513 }
514 declType = findScalar(typeName)
515 return declType, declType != nil
516 }
517
518 func findScalar(typename string) *DeclType {
519 switch typename {
520 case BoolType.TypeName():
521 return BoolType
522 case BytesType.TypeName():
523 return BytesType
524 case DoubleType.TypeName():
525 return DoubleType
526 case DurationType.TypeName():
527 return DurationType
528 case IntType.TypeName():
529 return IntType
530 case NullType.TypeName():
531 return NullType
532 case StringType.TypeName():
533 return StringType
534 case TimestampType.TypeName():
535 return TimestampType
536 case UintType.TypeName():
537 return UintType
538 case ListType.TypeName():
539 return ListType
540 case MapType.TypeName():
541 return MapType
542 default:
543 return nil
544 }
545 }
546
547 var (
548 // AnyType is equivalent to the CEL 'protobuf.Any' type in that the value may have any of the
549 // types supported.
550 AnyType = NewSimpleTypeWithMinSize("any", cel.AnyType, nil, 1)
551
552 // BoolType is equivalent to the CEL 'bool' type.
553 BoolType = NewSimpleTypeWithMinSize("bool", cel.BoolType, types.False, MinBoolSize)
554
555 // BytesType is equivalent to the CEL 'bytes' type.
556 BytesType = NewSimpleTypeWithMinSize("bytes", cel.BytesType, types.Bytes([]byte{}), MinStringSize)
557
558 // DoubleType is equivalent to the CEL 'double' type which is a 64-bit floating point value.
559 DoubleType = NewSimpleTypeWithMinSize("double", cel.DoubleType, types.Double(0), MinNumberSize)
560
561 // DurationType is equivalent to the CEL 'duration' type.
562 DurationType = NewSimpleTypeWithMinSize("duration", cel.DurationType, types.Duration{Duration: time.Duration(0)}, MinDurationSizeJSON)
563
564 // DateType is equivalent to the CEL 'date' type.
565 DateType = NewSimpleTypeWithMinSize("date", cel.TimestampType, types.Timestamp{Time: time.Time{}}, JSONDateSize)
566
567 // DynType is the equivalent of the CEL 'dyn' concept which indicates that the type will be
568 // determined at runtime rather than compile time.
569 DynType = NewSimpleTypeWithMinSize("dyn", cel.DynType, nil, 1)
570
571 // IntType is equivalent to the CEL 'int' type which is a 64-bit signed int.
572 IntType = NewSimpleTypeWithMinSize("int", cel.IntType, types.IntZero, MinNumberSize)
573
574 // NullType is equivalent to the CEL 'null_type'.
575 NullType = NewSimpleTypeWithMinSize("null_type", cel.NullType, types.NullValue, 4)
576
577 // StringType is equivalent to the CEL 'string' type which is expected to be a UTF-8 string.
578 // StringType values may either be string literals or expression strings.
579 StringType = NewSimpleTypeWithMinSize("string", cel.StringType, types.String(""), MinStringSize)
580
581 // TimestampType corresponds to the well-known protobuf.Timestamp type supported within CEL.
582 // Note that both the OpenAPI date and date-time types map onto TimestampType, so not all types
583 // labeled as Timestamp will necessarily have the same MinSerializedSize.
584 TimestampType = NewSimpleTypeWithMinSize("timestamp", cel.TimestampType, types.Timestamp{Time: time.Time{}}, JSONDateSize)
585
586 // QuantityDeclType wraps a [QuantityType] and makes it usable with functions that expect
587 // a [DeclType].
588 QuantityDeclType = NewSimpleTypeWithMinSize("quantity", QuantityType, Quantity{Quantity: resource.NewQuantity(0, resource.DecimalSI)}, 8)
589
590 // UintType is equivalent to the CEL 'uint' type.
591 UintType = NewSimpleTypeWithMinSize("uint", cel.UintType, types.Uint(0), 1)
592
593 // ListType is equivalent to the CEL 'list' type.
594 ListType = NewListType(AnyType, noMaxLength)
595
596 // MapType is equivalent to the CEL 'map' type.
597 MapType = NewMapType(AnyType, AnyType, noMaxLength)
598 )