Debian Codegraph @

pkg/cel/library/cost.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 library
18
19 import (
20 "fmt"
21 "math"
22
23 "github.com/google/cel-go/checker"
24 "github.com/google/cel-go/common"
25 "github.com/google/cel-go/common/ast"
26 "github.com/google/cel-go/common/types"
27 "github.com/google/cel-go/common/types/ref"
28 "github.com/google/cel-go/common/types/traits"
29
30 "k8s.io/apiserver/pkg/cel"
31 )
32
33 // panicOnUnknown makes cost estimate functions panic on unrecognized functions.
34 // This is only set to true for unit tests.
35 var panicOnUnknown = false
36
37 // builtInFunctions is a list of functions used in cost tests that are not handled by CostEstimator.
38 var knownUnhandledFunctions = map[string]bool{
39 "@not_strictly_false": true,
40 "uint": true,
41 "duration": true,
42 "bytes": true,
43 "cel.@mapInsert": true,
44 "timestamp": true,
45 "strings.quote": true,
46 "value": true,
47 "_==_": true,
48 "_&&_": true,
49 "_||_": true,
50 "_>_": true,
51 "_>=_": true,
52 "_<_": true,
53 "_<=_": true,
54 "!_": true,
55 "_?_:_": true,
56 "_+_": true,
57 "_-_": true,
58 }
59
60 // CostEstimator implements CEL's interpretable.ActualCostEstimator and checker.CostEstimator.
61 type CostEstimator struct {
62 // SizeEstimator provides a CostEstimator.EstimateSize that this CostEstimator will delegate size estimation
63 // calculations to if the size is not well known (i.e. a constant).
64 SizeEstimator checker.CostEstimator
65 }
66
67 const (
68 // shortest repeatable selector requirement that allocates a values slice is 2 characters: k,
69 selectorLengthToRequirementCount = float64(.5)
70 // the expensive parts to represent each requirement are a struct and a values slice
71 costPerRequirement = float64(common.ListCreateBaseCost + common.StructCreateBaseCost)
72 )
73
74 // a selector consists of a list of requirements held in a slice
75 var baseSelectorCost = checker.CostEstimate{Min: common.ListCreateBaseCost, Max: common.ListCreateBaseCost}
76
77 func selectorCostEstimate(selectorLength checker.SizeEstimate) checker.CostEstimate {
78 parseCost := selectorLength.MultiplyByCostFactor(common.StringTraversalCostFactor)
79
80 requirementCount := selectorLength.MultiplyByCostFactor(selectorLengthToRequirementCount)
81 requirementCost := requirementCount.MultiplyByCostFactor(costPerRequirement)
82
83 return baseSelectorCost.Add(parseCost).Add(requirementCost)
84 }
85
86 func (l *CostEstimator) CallCost(function, overloadId string, args []ref.Val, result ref.Val) *uint64 {
87 switch function {
88 case "check":
89 // An authorization check has a fixed cost
90 // This cost is set to allow for only two authorization checks per expression
91 cost := uint64(350000)
92 return &cost
93 case "serviceAccount", "path", "group", "resource", "subresource", "namespace", "name", "allowed", "reason", "error", "errored":
94 // All authorization builder and accessor functions have a nominal cost
95 cost := uint64(1)
96 return &cost
97 case "fieldSelector", "labelSelector":
98 // field and label selector parse is a string parse into a structured set of requirements
99 if len(args) >= 2 {
100 selectorLength := actualSize(args[1])
101 cost := selectorCostEstimate(checker.SizeEstimate{Min: selectorLength, Max: selectorLength})
102 return &cost.Max
103 }
104 case "isSorted", "sum", "max", "min", "indexOf", "lastIndexOf":
105 var cost uint64
106 if len(args) > 0 {
107 cost += traversalCost(args[0]) // these O(n) operations all cost roughly the cost of a single traversal
108 }
109 return &cost
110 case "url", "lowerAscii", "upperAscii", "substring", "trim", "jsonpatch.escapeKey":
111 if len(args) >= 1 {
112 cost := uint64(math.Ceil(float64(actualSize(args[0])) * common.StringTraversalCostFactor))
113 return &cost
114 }
115 case "replace", "split":
116 if len(args) >= 1 {
117 // cost is the traversal plus the construction of the result
118 cost := uint64(math.Ceil(float64(actualSize(args[0])) * 2 * common.StringTraversalCostFactor))
119 return &cost
120 }
121 case "join":
122 if len(args) >= 1 {
123 cost := uint64(math.Ceil(float64(actualSize(result)) * 2 * common.StringTraversalCostFactor))
124 return &cost
125 }
126 case "find", "findAll":
127 if len(args) >= 2 {
128 strCost := uint64(math.Ceil((1.0 + float64(actualSize(args[0]))) * common.StringTraversalCostFactor))
129 // We don't know how many expressions are in the regex, just the string length (a huge
130 // improvement here would be to somehow get a count the number of expressions in the regex or
131 // how many states are in the regex state machine and use that to measure regex cost).
132 // For now, we're making a guess that each expression in a regex is typically at least 4 chars
133 // in length.
134 regexCost := uint64(math.Ceil(float64(actualSize(args[1])) * common.RegexStringLengthCostFactor))
135 cost := strCost * regexCost
136 return &cost
137 }
138 case "cidr", "isIP", "isCIDR":
139 // IP and CIDR parsing is a string traversal.
140 if len(args) >= 1 {
141 cost := uint64(math.Ceil(float64(actualSize(args[0])) * common.StringTraversalCostFactor))
142 return &cost
143 }
144 case "ip":
145 // IP and CIDR parsing is a string traversal.
146 if len(args) >= 1 {
147 if overloadId == "cidr_ip" {
148 // The IP member of the CIDR object is just accessing a field.
149 // Nominal cost.
150 cost := uint64(1)
151 return &cost
152 }
153
154 cost := uint64(math.Ceil(float64(actualSize(args[0])) * common.StringTraversalCostFactor))
155 return &cost
156 }
157 case "ip.isCanonical":
158 if len(args) >= 1 {
159 // We have to parse the string and then compare the parsed string to the original string.
160 // So we double the cost of parsing the string.
161 cost := uint64(math.Ceil(float64(actualSize(args[0])) * 2 * common.StringTraversalCostFactor))
162 return &cost
163 }
164 case "masked", "prefixLength", "family", "isUnspecified", "isLoopback", "isLinkLocalMulticast", "isLinkLocalUnicast", "isGlobalUnicast":
165 // IP and CIDR accessors are nominal cost.
166 cost := uint64(1)
167 return &cost
168 case "containsIP":
169 if len(args) >= 2 {
170 cidrSize := actualSize(args[0])
171 otherSize := actualSize(args[1])
172
173 // This is the base cost of comparing two byte lists.
174 // We will compare only up to the length of the CIDR prefix in bytes, so use the cidrSize twice.
175 cost := uint64(math.Ceil(float64(cidrSize+cidrSize) * common.StringTraversalCostFactor))
176
177 if overloadId == "cidr_contains_ip_string" {
178 // If we are comparing a string, we must parse the string to into the right type, so add the cost of traversing the string again.
179 cost += uint64(math.Ceil(float64(otherSize) * common.StringTraversalCostFactor))
180
181 }
182
183 return &cost
184 }
185 case "containsCIDR":
186 if len(args) >= 2 {
187 cidrSize := actualSize(args[0])
188 otherSize := actualSize(args[1])
189
190 // This is the base cost of comparing two byte lists.
191 // We will compare only up to the length of the CIDR prefix in bytes, so use the cidrSize twice.
192 cost := uint64(math.Ceil(float64(cidrSize+cidrSize) * common.StringTraversalCostFactor))
193
194 // As we are comparing if a CIDR is within another CIDR, we first mask the base CIDR and
195 // also compare the CIDR bits.
196 // This has an additional cost of the length of the IP being traversed again, plus 1.
197 cost += uint64(math.Ceil(float64(cidrSize)*common.StringTraversalCostFactor)) + 1
198
199 if overloadId == "cidr_contains_cidr_string" {
200 // If we are comparing a string, we must parse the string to into the right type, so add the cost of traversing the string again.
201 cost += uint64(math.Ceil(float64(otherSize) * common.StringTraversalCostFactor))
202 }
203
204 return &cost
205 }
206 case "quantity", "isQuantity", "semver", "isSemver":
207 if len(args) >= 1 {
208 cost := uint64(math.Ceil(float64(actualSize(args[0])) * common.StringTraversalCostFactor))
209 return &cost
210 }
211 case "validate":
212 if len(args) >= 2 {
213 format, isFormat := args[0].Value().(cel.Format)
214 if isFormat {
215 strSize := actualSize(args[1])
216
217 // Dont have access to underlying regex, estimate a long regexp
218 regexSize := format.MaxRegexSize
219
220 // Copied from CEL implementation for regex cost
221 //
222 // https://swtch.com/~rsc/regexp/regexp1.html applies to RE2 implementation supported by CEL
223 // Add one to string length for purposes of cost calculation to prevent product of string and regex to be 0
224 // in case where string is empty but regex is still expensive.
225 strCost := uint64(math.Ceil((1.0 + float64(strSize)) * common.StringTraversalCostFactor))
226 // We don't know how many expressions are in the regex, just the string length (a huge
227 // improvement here would be to somehow get a count the number of expressions in the regex or
228 // how many states are in the regex state machine and use that to measure regex cost).
229 // For now, we're making a guess that each expression in a regex is typically at least 4 chars
230 // in length.
231 regexCost := uint64(math.Ceil(float64(regexSize) * common.RegexStringLengthCostFactor))
232 cost := strCost * regexCost
233 return &cost
234 }
235 }
236 case "format.named":
237 // Simply dictionary lookup
238 cost := uint64(1)
239 return &cost
240 case "sign", "asInteger", "isInteger", "asApproximateFloat", "isGreaterThan", "isLessThan", "compareTo", "add", "sub", "major", "minor", "patch":
241 cost := uint64(1)
242 return &cost
243 case "getScheme", "getHostname", "getHost", "getPort", "getEscapedPath", "getQuery":
244 // url accessors
245 cost := uint64(1)
246 return &cost
247 case "_==_":
248 if len(args) == 2 {
249 unitCost := uint64(1)
250 lhs := args[0]
251 switch lhs.(type) {
252 case *cel.Quantity, cel.Quantity,
253 *cel.IP, cel.IP,
254 *cel.CIDR, cel.CIDR,
255 *cel.Format, cel.Format, // Formats have a small max size. Format takes pointer receiver.
256 *cel.URL, cel.URL, // TODO: Computing the actual cost is expensive, and changing this would be a breaking change
257 *cel.Semver, cel.Semver,
258 *authorizerVal, authorizerVal, *pathCheckVal, pathCheckVal, *groupCheckVal, groupCheckVal,
259 *resourceCheckVal, resourceCheckVal, *decisionVal, decisionVal:
260 return &unitCost
261 default:
262 if panicOnUnknown && lhs.Type() != nil && isRegisteredType(lhs.Type().TypeName()) {
263 panic(fmt.Errorf("CallCost: unhandled equality for Kubernetes type %T", lhs))
264 }
265 }
266 }
267 }
268 if panicOnUnknown && !knownUnhandledFunctions[function] {
269 panic(fmt.Errorf("CallCost: unhandled function %q or args %v", function, args))
270 }
271 return nil
272 }
273
274 func (l *CostEstimator) EstimateCallCost(function, overloadId string, target *checker.AstNode, args []checker.AstNode) *checker.CallEstimate {
275 // WARNING: Any changes to this code impact API compatibility! The estimated cost is used to determine which CEL rules may be written to a
276 // CRD and any change (cost increases and cost decreases) are breaking.
277 switch function {
278 case "check":
279 // An authorization check has a fixed cost
280 // This cost is set to allow for only two authorization checks per expression
281 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 350000, Max: 350000}}
282 case "serviceAccount", "path", "group", "resource", "subresource", "namespace", "name", "allowed", "reason", "error", "errored":
283 // All authorization builder and accessor functions have a nominal cost
284 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
285 case "fieldSelector", "labelSelector":
286 // field and label selector parse is a string parse into a structured set of requirements
287 if len(args) == 1 {
288 return &checker.CallEstimate{CostEstimate: selectorCostEstimate(l.sizeEstimate(args[0]))}
289 }
290 case "isSorted", "sum", "max", "min", "indexOf", "lastIndexOf":
291 if target != nil {
292 // Charge 1 cost for comparing each element in the list
293 elCost := checker.CostEstimate{Min: 1, Max: 1}
294 // If the list contains strings or bytes, add the cost of traversing all the strings/bytes as a way
295 // of estimating the additional comparison cost.
296 if elNode := l.listElementNode(*target); elNode != nil {
297 k := elNode.Type().Kind()
298 if k == types.StringKind || k == types.BytesKind {
299 sz := l.sizeEstimate(elNode)
300 elCost = elCost.Add(sz.MultiplyByCostFactor(common.StringTraversalCostFactor))
301 }
302 return &checker.CallEstimate{CostEstimate: l.sizeEstimate(*target).MultiplyByCost(elCost)}
303 } else { // the target is a string, which is supported by indexOf and lastIndexOf
304 return &checker.CallEstimate{CostEstimate: l.sizeEstimate(*target).MultiplyByCostFactor(common.StringTraversalCostFactor)}
305 }
306 }
307 case "url", "jsonpatch.escapeKey":
308 if len(args) == 1 {
309 sz := l.sizeEstimate(args[0])
310 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor), ResultSize: &sz}
311 }
312 case "lowerAscii", "upperAscii", "substring", "trim":
313 if target != nil {
314 sz := l.sizeEstimate(*target)
315 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor), ResultSize: &sz}
316 }
317 case "replace":
318 if target != nil && len(args) >= 2 {
319 sz := l.sizeEstimate(*target)
320 toReplaceSz := l.sizeEstimate(args[0])
321 replaceWithSz := l.sizeEstimate(args[1])
322
323 var replaceCount, retainedSz checker.SizeEstimate
324 // find the longest replacement:
325 if toReplaceSz.Min == 0 {
326 // if the string being replaced is empty, replace surrounds all characters in the input string with the replacement.
327 if sz.Max < math.MaxUint64 {
328 replaceCount.Max = sz.Max + 1
329 } else {
330 replaceCount.Max = sz.Max
331 }
332 // Include the length of the longest possible original string length.
333 retainedSz.Max = sz.Max
334 } else if replaceWithSz.Max <= toReplaceSz.Min {
335 // If the replacement does not make the result longer, use the original string length.
336 replaceCount.Max = 0
337 retainedSz.Max = sz.Max
338 } else {
339 // Replace the smallest possible substrings with the largest possible replacement
340 // as many times as possible.
341 replaceCount.Max = uint64(math.Ceil(float64(sz.Max) / float64(toReplaceSz.Min)))
342 }
343
344 // find the shortest replacement:
345 if toReplaceSz.Max == 0 {
346 // if the string being replaced is empty, replace surrounds all characters in the input string with the replacement.
347 if sz.Min < math.MaxUint64 {
348 replaceCount.Min = sz.Min + 1
349 } else {
350 replaceCount.Min = sz.Min
351 }
352 // Include the length of the shortest possible original string length.
353 retainedSz.Min = sz.Min
354 } else if toReplaceSz.Max <= replaceWithSz.Min {
355 // If the replacement does not make the result shorter, use the original string length.
356 replaceCount.Min = 0
357 retainedSz.Min = sz.Min
358 } else {
359 // Replace the largest possible substrings being with the smallest possible replacement
360 // as many times as possible.
361 replaceCount.Min = uint64(math.Ceil(float64(sz.Min) / float64(toReplaceSz.Max)))
362 }
363 size := replaceCount.Multiply(replaceWithSz).Add(retainedSz)
364
365 // cost is the traversal plus the construction of the result
366 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(2 * common.StringTraversalCostFactor), ResultSize: &size}
367 }
368 case "split":
369 if target != nil {
370 sz := l.sizeEstimate(*target)
371
372 // Worst case size is where is that a separator of "" is used, and each char is returned as a list element.
373 max := sz.Max
374 if len(args) > 1 {
375 if v := args[1].Expr().AsLiteral(); v != nil {
376 if i, ok := v.Value().(int64); ok {
377 max = uint64(i)
378 }
379 }
380 }
381 // Cost is the traversal plus the construction of the result.
382 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(2 * common.StringTraversalCostFactor), ResultSize: &checker.SizeEstimate{Min: 0, Max: max}}
383 }
384 case "join":
385 if target != nil {
386 var sz checker.SizeEstimate
387 listSize := l.sizeEstimate(*target)
388 if elNode := l.listElementNode(*target); elNode != nil {
389 elemSize := l.sizeEstimate(elNode)
390 sz = listSize.Multiply(elemSize)
391 }
392
393 if len(args) > 0 {
394 sepSize := l.sizeEstimate(args[0])
395 minSeparators := uint64(0)
396 maxSeparators := uint64(0)
397 if listSize.Min > 0 {
398 minSeparators = listSize.Min - 1
399 }
400 if listSize.Max > 0 {
401 maxSeparators = listSize.Max - 1
402 }
403 sz = sz.Add(sepSize.Multiply(checker.SizeEstimate{Min: minSeparators, Max: maxSeparators}))
404 }
405
406 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor), ResultSize: &sz}
407 }
408 case "find", "findAll":
409 if target != nil && len(args) >= 1 {
410 sz := l.sizeEstimate(*target)
411 // Add one to string length for purposes of cost calculation to prevent product of string and regex to be 0
412 // in case where string is empty but regex is still expensive.
413 strCost := sz.Add(checker.SizeEstimate{Min: 1, Max: 1}).MultiplyByCostFactor(common.StringTraversalCostFactor)
414 // We don't know how many expressions are in the regex, just the string length (a huge
415 // improvement here would be to somehow get a count the number of expressions in the regex or
416 // how many states are in the regex state machine and use that to measure regex cost).
417 // For now, we're making a guess that each expression in a regex is typically at least 4 chars
418 // in length.
419 regexCost := l.sizeEstimate(args[0]).MultiplyByCostFactor(common.RegexStringLengthCostFactor)
420 // worst case size of result is that every char is returned as separate find result.
421 return &checker.CallEstimate{CostEstimate: strCost.Multiply(regexCost), ResultSize: &checker.SizeEstimate{Min: 0, Max: sz.Max}}
422 }
423 case "cidr", "isIP", "isCIDR":
424 if target != nil {
425 sz := l.sizeEstimate(args[0])
426 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor)}
427 }
428 case "ip":
429 if target != nil && len(args) >= 1 {
430 if overloadId == "cidr_ip" {
431 // The IP member of the CIDR object is just accessing a field.
432 // Nominal cost.
433 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
434 }
435
436 sz := l.sizeEstimate(args[0])
437 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor)}
438 } else if target != nil {
439 // The IP member of a CIDR is a just accessing a field, nominal cost.
440 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
441 }
442 case "ip.isCanonical":
443 if target != nil && len(args) >= 1 {
444 sz := l.sizeEstimate(args[0])
445 // We have to parse the string and then compare the parsed string to the original string.
446 // So we double the cost of parsing the string.
447 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(2 * common.StringTraversalCostFactor)}
448 }
449 case "masked", "prefixLength", "family", "isUnspecified", "isLoopback", "isLinkLocalMulticast", "isLinkLocalUnicast", "isGlobalUnicast":
450 // IP and CIDR accessors are nominal cost.
451 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
452 case "containsIP":
453 if target != nil && len(args) >= 1 {
454 // The base cost of the function is the cost of comparing two byte lists.
455 // The byte lists will be either ipv4 or ipv6 so will have a length of 4, or 16 bytes.
456 sz := checker.SizeEstimate{Min: 4, Max: 16}
457
458 // We have to compare the two strings to determine if the CIDR/IP is in the other CIDR.
459 ipCompCost := sz.Add(sz).MultiplyByCostFactor(common.StringTraversalCostFactor)
460
461 if overloadId == "cidr_contains_ip_string" {
462 // If we are comparing a string, we must parse the string to into the right type, so add the cost of traversing the string again.
463 ipCompCost = ipCompCost.Add(checker.CostEstimate(l.sizeEstimate(args[0])).MultiplyByCostFactor(common.StringTraversalCostFactor))
464 }
465
466 return &checker.CallEstimate{CostEstimate: ipCompCost}
467 }
468 case "containsCIDR":
469 if target != nil && len(args) >= 1 {
470 // The base cost of the function is the cost of comparing two byte lists.
471 // The byte lists will be either ipv4 or ipv6 so will have a length of 4, or 16 bytes.
472 sz := checker.SizeEstimate{Min: 4, Max: 16}
473
474 // We have to compare the two strings to determine if the CIDR/IP is in the other CIDR.
475 ipCompCost := sz.Add(sz).MultiplyByCostFactor(common.StringTraversalCostFactor)
476
477 // As we are comparing if a CIDR is within another CIDR, we first mask the base CIDR and
478 // also compare the CIDR bits.
479 // This has an additional cost of the length of the IP being traversed again, plus 1.
480 ipCompCost = ipCompCost.Add(sz.MultiplyByCostFactor(common.StringTraversalCostFactor))
481 ipCompCost = ipCompCost.Add(checker.CostEstimate{Min: 1, Max: 1})
482
483 if overloadId == "cidr_contains_cidr_string" {
484 // If we are comparing a string, we must parse the string to into the right type, so add the cost of traversing the string again.
485 ipCompCost = ipCompCost.Add(checker.CostEstimate(l.sizeEstimate(args[0])).MultiplyByCostFactor(common.StringTraversalCostFactor))
486 }
487
488 return &checker.CallEstimate{CostEstimate: ipCompCost}
489 }
490 case "quantity", "isQuantity", "semver", "isSemver":
491 if target != nil {
492 sz := l.sizeEstimate(args[0])
493 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor)}
494 }
495 case "validate":
496 if target != nil {
497 sz := l.sizeEstimate(args[0])
498 return &checker.CallEstimate{CostEstimate: sz.MultiplyByCostFactor(common.StringTraversalCostFactor).MultiplyByCostFactor(cel.MaxNameFormatRegexSize * common.RegexStringLengthCostFactor)}
499 }
500 case "format.named":
501 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
502 case "sign", "asInteger", "isInteger", "asApproximateFloat", "isGreaterThan", "isLessThan", "compareTo", "add", "sub", "major", "minor", "patch":
503 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
504 case "getScheme", "getHostname", "getHost", "getPort", "getEscapedPath", "getQuery":
505 // url accessors
506 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
507 case "_==_":
508 if len(args) == 2 {
509 lhs := args[0]
510 rhs := args[1]
511 if lhs.Type().Equal(rhs.Type()) == types.True {
512 t := lhs.Type()
513 if t.Kind() == types.OpaqueKind {
514 switch t.TypeName() {
515 case cel.IPType.TypeName(), cel.CIDRType.TypeName():
516 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
517 }
518 }
519 if t.Kind() == types.StructKind {
520 switch t {
521 case cel.QuantityType, AuthorizerType, PathCheckType, // O(1) cost equality checks
522 GroupCheckType, ResourceCheckType, DecisionType, cel.SemverType:
523 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: 1}}
524 case cel.FormatType:
525 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: cel.MaxFormatSize}.MultiplyByCostFactor(common.StringTraversalCostFactor)}
526 case cel.URLType:
527 size := checker.SizeEstimate{Min: 1, Max: 1}
528 rhSize := rhs.ComputedSize()
529 lhSize := rhs.ComputedSize()
530 if rhSize != nil && lhSize != nil {
531 size = rhSize.Union(*lhSize)
532 }
533 return &checker.CallEstimate{CostEstimate: checker.CostEstimate{Min: 1, Max: size.Max}.MultiplyByCostFactor(common.StringTraversalCostFactor)}
534 }
535 }
536 if panicOnUnknown && isRegisteredType(t.TypeName()) {
537 panic(fmt.Errorf("EstimateCallCost: unhandled equality for Kubernetes type %v", t))
538 }
539 }
540 }
541 }
542 if panicOnUnknown && !knownUnhandledFunctions[function] {
543 panic(fmt.Errorf("EstimateCallCost: unhandled function %q, target %v, args %v", function, target, args))
544 }
545 return nil
546 }
547
548 func actualSize(value ref.Val) uint64 {
549 if sz, ok := value.(traits.Sizer); ok {
550 return uint64(sz.Size().(types.Int))
551 }
552 if panicOnUnknown {
553 // debug.PrintStack()
554 panic(fmt.Errorf("actualSize: non-sizer type %T", value))
555 }
556 return 1
557 }
558
559 func (l *CostEstimator) sizeEstimate(t checker.AstNode) checker.SizeEstimate {
560 if sz := t.ComputedSize(); sz != nil {
561 return *sz
562 }
563 if sz := l.EstimateSize(t); sz != nil {
564 return *sz
565 }
566 return checker.SizeEstimate{Min: 0, Max: math.MaxUint64}
567 }
568
569 func (l *CostEstimator) listElementNode(list checker.AstNode) checker.AstNode {
570 if params := list.Type().Parameters(); len(params) > 0 {
571 lt := params[0]
572 nodePath := list.Path()
573 if nodePath != nil {
574 // Provide path if we have it so that a OpenAPIv3 maxLength validation can be looked up, if it exists
575 // for this node.
576 path := make([]string, len(nodePath)+1)
577 copy(path, nodePath)
578 path[len(nodePath)] = "@items"
579 return &itemsNode{path: path, t: lt, expr: nil}
580 } else {
581 // Provide just the type if no path is available so that worst case size can be looked up based on type.
582 return &itemsNode{t: lt, expr: nil}
583 }
584 }
585 return nil
586 }
587
588 func (l *CostEstimator) EstimateSize(element checker.AstNode) *checker.SizeEstimate {
589 if l.SizeEstimator != nil {
590 return l.SizeEstimator.EstimateSize(element)
591 }
592 return nil
593 }
594
595 type itemsNode struct {
596 path []string
597 t *types.Type
598 expr ast.Expr
599 }
600
601 func (i *itemsNode) Path() []string {
602 return i.path
603 }
604
605 func (i *itemsNode) Type() *types.Type {
606 return i.t
607 }
608
609 func (i *itemsNode) Expr() ast.Expr {
610 return i.expr
611 }
612
613 func (i *itemsNode) ComputedSize() *checker.SizeEstimate {
614 return nil
615 }
616
617 var _ checker.AstNode = (*itemsNode)(nil)
618
619 // traversalCost computes the cost of traversing a ref.Val as a data tree.
620 func traversalCost(v ref.Val) uint64 {
621 // TODO: This could potentially be optimized by sampling maps and lists instead of traversing.
622 switch vt := v.(type) {
623 case types.String:
624 return uint64(float64(len(string(vt))) * common.StringTraversalCostFactor)
625 case types.Bytes:
626 return uint64(float64(len([]byte(vt))) * common.StringTraversalCostFactor)
627 case traits.Lister:
628 cost := uint64(0)
629 for it := vt.Iterator(); it.HasNext() == types.True; {
630 i := it.Next()
631 cost += traversalCost(i)
632 }
633 return cost
634 case traits.Mapper: // maps and objects
635 cost := uint64(0)
636 for it := vt.Iterator(); it.HasNext() == types.True; {
637 k := it.Next()
638 cost += traversalCost(k) + traversalCost(vt.Get(k))
639 }
640 return cost
641 default:
642 return 1
643 }
644 }