Debian Codegraph @

pkg/cel/library/cost_test.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 "context"
21 "fmt"
22 "testing"
23
24 "github.com/google/cel-go/common/types/ref"
25
26 "github.com/google/cel-go/cel"
27 "github.com/google/cel-go/checker"
28 "github.com/google/cel-go/common"
29 "github.com/google/cel-go/common/ast"
30 "github.com/google/cel-go/common/types"
31 "github.com/google/cel-go/ext"
32 exprpb "google.golang.org/genproto/googleapis/api/expr/v1alpha1"
33
34 "k8s.io/apiserver/pkg/authorization/authorizer"
35 apiservercel "k8s.io/apiserver/pkg/cel"
36 )
37
38 const (
39 intListLiteral = "[1, 2, 3, 4, 5]"
40 uintListLiteral = "[uint(1), uint(2), uint(3), uint(4), uint(5)]"
41 doubleListLiteral = "[1.0, 2.0, 3.0, 4.0, 5.0]"
42 boolListLiteral = "[false, true, false, true, false]"
43 stringListLiteral = "['012345678901', '012345678901', '012345678901', '012345678901', '012345678901']"
44 bytesListLiteral = "[bytes('012345678901'), bytes('012345678901'), bytes('012345678901'), bytes('012345678901'), bytes('012345678901')]"
45 durationListLiteral = "[duration('1s'), duration('2s'), duration('3s'), duration('4s'), duration('5s')]"
46 timestampListLiteral = "[timestamp('2011-01-01T00:00:00.000+01:00'), timestamp('2011-01-02T00:00:00.000+01:00'), " +
47 "timestamp('2011-01-03T00:00:00.000+01:00'), timestamp('2011-01-04T00:00:00.000+01:00'), " +
48 "timestamp('2011-01-05T00:00:00.000+01:00')]"
49 stringLiteral = "'01234567890123456789012345678901234567890123456789'"
50 )
51
52 type comparableCost struct {
53 comparableLiteral string
54 expectedEstimatedCost checker.CostEstimate
55 expectedRuntimeCost uint64
56
57 param string
58 }
59
60 func TestListsCost(t *testing.T) {
61 cases := []struct {
62 opts []string
63 costs []comparableCost
64 }{
65 {
66 opts: []string{".sum()"},
67 // 10 cost for the list declaration, the rest is the due to the function call
68 costs: []comparableCost{
69 {
70 comparableLiteral: intListLiteral,
71 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
72 },
73 {
74 comparableLiteral: uintListLiteral,
75 expectedEstimatedCost: checker.CostEstimate{Min: 20, Max: 20}, expectedRuntimeCost: 20, // +5 for casts
76 },
77 {
78 comparableLiteral: doubleListLiteral,
79 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
80 },
81 {
82 comparableLiteral: durationListLiteral,
83 expectedEstimatedCost: checker.CostEstimate{Min: 20, Max: 20}, expectedRuntimeCost: 20, // +5 for casts
84 },
85 },
86 },
87 {
88 opts: []string{".isSorted()", ".max()", ".min()"},
89 // 10 cost for the list declaration, the rest is the due to the function call
90 costs: []comparableCost{
91 {
92 comparableLiteral: intListLiteral,
93 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
94 },
95 {
96 comparableLiteral: uintListLiteral,
97 expectedEstimatedCost: checker.CostEstimate{Min: 20, Max: 20}, expectedRuntimeCost: 20, // +5 for numeric casts
98 },
99 {
100 comparableLiteral: doubleListLiteral,
101 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
102 },
103 {
104 comparableLiteral: boolListLiteral,
105 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
106 },
107 {
108 comparableLiteral: stringListLiteral,
109 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 25}, expectedRuntimeCost: 15, // +5 for string comparisons
110 },
111 {
112 comparableLiteral: bytesListLiteral,
113 expectedEstimatedCost: checker.CostEstimate{Min: 25, Max: 35}, expectedRuntimeCost: 25, // +10 for casts from string to byte, +5 for byte comparisons
114 },
115 {
116 comparableLiteral: durationListLiteral,
117 expectedEstimatedCost: checker.CostEstimate{Min: 20, Max: 20}, expectedRuntimeCost: 20, // +5 for numeric casts
118 },
119 {
120 comparableLiteral: timestampListLiteral,
121 expectedEstimatedCost: checker.CostEstimate{Min: 20, Max: 20}, expectedRuntimeCost: 20, // +5 for casts
122 },
123 },
124 },
125 }
126 for _, tc := range cases {
127 for _, op := range tc.opts {
128 for _, typ := range tc.costs {
129 t.Run(typ.comparableLiteral+op, func(t *testing.T) {
130 e := typ.comparableLiteral + op
131 testCost(t, e, typ.expectedEstimatedCost, typ.expectedRuntimeCost)
132 })
133 }
134 }
135 }
136 }
137
138 func TestIndexOfCost(t *testing.T) {
139 cases := []struct {
140 opts []string
141 costs []comparableCost
142 }{
143 {
144 opts: []string{".indexOf(%s)", ".lastIndexOf(%s)"},
145 // 10 cost for the list declaration, the rest is the due to the function call
146 costs: []comparableCost{
147 {
148 comparableLiteral: intListLiteral, param: "3",
149 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
150 },
151 {
152 comparableLiteral: uintListLiteral, param: "uint(3)",
153 expectedEstimatedCost: checker.CostEstimate{Min: 21, Max: 21}, expectedRuntimeCost: 21, // +5 for numeric casts
154 },
155 {
156 comparableLiteral: doubleListLiteral, param: "3.0",
157 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
158 },
159 {
160 comparableLiteral: boolListLiteral, param: "true",
161 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 15}, expectedRuntimeCost: 15,
162 },
163 {
164 comparableLiteral: stringListLiteral, param: "'x'",
165 expectedEstimatedCost: checker.CostEstimate{Min: 15, Max: 25}, expectedRuntimeCost: 15, // +5 for string comparisons
166 },
167 {
168 comparableLiteral: bytesListLiteral, param: "bytes('x')",
169 expectedEstimatedCost: checker.CostEstimate{Min: 26, Max: 36}, expectedRuntimeCost: 26, // +11 for casts from string to byte, +5 for byte comparisons
170 },
171 {
172 comparableLiteral: durationListLiteral, param: "duration('3s')",
173 expectedEstimatedCost: checker.CostEstimate{Min: 21, Max: 21}, expectedRuntimeCost: 21, // +6 for casts from duration to byte
174 },
175 {
176 comparableLiteral: timestampListLiteral, param: "timestamp('2011-01-03T00:00:00.000+01:00')",
177 expectedEstimatedCost: checker.CostEstimate{Min: 21, Max: 21}, expectedRuntimeCost: 21, // +6 for casts from timestamp to byte
178 },
179
180 // index of operations are also defined for strings
181 {
182 comparableLiteral: stringLiteral, param: "'123'",
183 expectedEstimatedCost: checker.CostEstimate{Min: 5, Max: 5}, expectedRuntimeCost: 5,
184 },
185 },
186 },
187 }
188 for _, tc := range cases {
189 for _, op := range tc.opts {
190 for _, typ := range tc.costs {
191 opWithParam := fmt.Sprintf(op, typ.param)
192 t.Run(typ.comparableLiteral+opWithParam, func(t *testing.T) {
193 e := typ.comparableLiteral + opWithParam
194 testCost(t, e, typ.expectedEstimatedCost, typ.expectedRuntimeCost)
195 })
196 }
197 }
198 }
199 }
200
201 func TestURLsCost(t *testing.T) {
202 cases := []struct {
203 ops []string
204 expectEsimatedCost checker.CostEstimate
205 expectRuntimeCost uint64
206 }{
207 {
208 ops: []string{".getScheme()", ".getHostname()", ".getHost()", ".getPort()", ".getEscapedPath()", ".getQuery()"},
209 expectEsimatedCost: checker.CostEstimate{Min: 4, Max: 4},
210 expectRuntimeCost: 4,
211 },
212 {
213 ops: []string{" == url('https:://kubernetes.io/')"},
214 expectEsimatedCost: checker.CostEstimate{Min: 7, Max: 9},
215 expectRuntimeCost: 7,
216 },
217 {
218 ops: []string{" == url('http://x.b')"},
219 expectEsimatedCost: checker.CostEstimate{Min: 5, Max: 5},
220 expectRuntimeCost: 5,
221 },
222 }
223
224 for _, tc := range cases {
225 for _, op := range tc.ops {
226 t.Run("url."+op, func(t *testing.T) {
227 testCost(t, "url('https:://kubernetes.io/')"+op, tc.expectEsimatedCost, tc.expectRuntimeCost)
228 })
229 }
230 }
231 }
232
233 func TestIPCost(t *testing.T) {
234 ipv4 := "ip('192.168.0.1')"
235 ipv4BaseEstimatedCost := checker.CostEstimate{Min: 2, Max: 2}
236 ipv4BaseRuntimeCost := uint64(2)
237
238 ipv6 := "ip('2001:db8:3333:4444:5555:6666:7777:8888')"
239 ipv6BaseEstimatedCost := checker.CostEstimate{Min: 4, Max: 4}
240 ipv6BaseRuntimeCost := uint64(4)
241
242 testCases := []struct {
243 ops []string
244 expectEsimatedCost func(checker.CostEstimate) checker.CostEstimate
245 expectRuntimeCost func(uint64) uint64
246 }{
247 {
248 // For just parsing the IP, the cost is expected to be the base.
249 ops: []string{""},
250 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate { return c },
251 expectRuntimeCost: func(c uint64) uint64 { return c },
252 },
253 {
254 ops: []string{".family()", ".isUnspecified()", ".isLoopback()", ".isLinkLocalMulticast()", ".isLinkLocalUnicast()", ".isGlobalUnicast()"},
255 // For most other operations, the cost is expected to be the base + 1.
256 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
257 return checker.CostEstimate{Min: c.Min + 1, Max: c.Max + 1}
258 },
259 expectRuntimeCost: func(c uint64) uint64 { return c + 1 },
260 },
261 {
262 ops: []string{" == ip('192.168.0.1')"},
263 // For most other operations, the cost is expected to be the base + 1.
264 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
265 return c.Add(ipv4BaseEstimatedCost).Add(checker.CostEstimate{Min: 1, Max: 1})
266 },
267 expectRuntimeCost: func(c uint64) uint64 { return c + ipv4BaseRuntimeCost + 1 },
268 },
269 }
270
271 for _, tc := range testCases {
272 for _, op := range tc.ops {
273 t.Run(ipv4+op, func(t *testing.T) {
274 testCost(t, ipv4+op, tc.expectEsimatedCost(ipv4BaseEstimatedCost), tc.expectRuntimeCost(ipv4BaseRuntimeCost))
275 })
276
277 t.Run(ipv6+op, func(t *testing.T) {
278 testCost(t, ipv6+op, tc.expectEsimatedCost(ipv6BaseEstimatedCost), tc.expectRuntimeCost(ipv6BaseRuntimeCost))
279 })
280 }
281 }
282 }
283
284 func TestIPIsCanonicalCost(t *testing.T) {
285 testCases := []struct {
286 op string
287 expectEsimatedCost checker.CostEstimate
288 expectRuntimeCost uint64
289 }{
290 {
291 op: "ip.isCanonical('192.168.0.1')",
292 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
293 expectRuntimeCost: 3,
294 },
295 {
296 op: "ip.isCanonical('2001:db8:3333:4444:5555:6666:7777:8888')",
297 expectEsimatedCost: checker.CostEstimate{Min: 8, Max: 8},
298 expectRuntimeCost: 8,
299 },
300 {
301 op: "ip.isCanonical('2001:db8::abcd')",
302 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
303 expectRuntimeCost: 3,
304 },
305 }
306
307 for _, tc := range testCases {
308 t.Run(tc.op, func(t *testing.T) {
309 testCost(t, tc.op, tc.expectEsimatedCost, tc.expectRuntimeCost)
310 })
311 }
312 }
313
314 func TestCIDRCost(t *testing.T) {
315 ipv4 := "cidr('192.168.0.0/16')"
316 ipv4BaseEstimatedCost := checker.CostEstimate{Min: 2, Max: 2}
317 ipv4BaseRuntimeCost := uint64(2)
318
319 ipv6 := "cidr('2001:db8::/32')"
320 ipv6BaseEstimatedCost := checker.CostEstimate{Min: 2, Max: 2}
321 ipv6BaseRuntimeCost := uint64(2)
322
323 type testCase struct {
324 ops []string
325 expectEsimatedCost func(checker.CostEstimate) checker.CostEstimate
326 expectRuntimeCost func(uint64) uint64
327 }
328
329 cases := []testCase{
330 {
331 // For just parsing the IP, the cost is expected to be the base.
332 ops: []string{""},
333 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate { return c },
334 expectRuntimeCost: func(c uint64) uint64 { return c },
335 },
336 {
337 ops: []string{".ip()", ".prefixLength()", ".masked()"},
338 // For most other operations, the cost is expected to be the base + 1.
339 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
340 return checker.CostEstimate{Min: c.Min + 1, Max: c.Max + 1}
341 },
342 expectRuntimeCost: func(c uint64) uint64 { return c + 1 },
343 },
344 {
345 ops: []string{" == cidr('2001:db8::/32')"},
346 // For most other operations, the cost is expected to be the base + 1.
347 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
348 return c.Add(ipv6BaseEstimatedCost).Add(checker.CostEstimate{Min: 1, Max: 1})
349 },
350 expectRuntimeCost: func(c uint64) uint64 { return c + ipv6BaseRuntimeCost + 1 },
351 },
352 }
353
354 //nolint:gocritic
355 ipv4Cases := append(cases, []testCase{
356 {
357 ops: []string{".containsCIDR(cidr('192.0.0.0/30'))"},
358 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
359 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
360 },
361 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
362 },
363 {
364 ops: []string{".containsCIDR(cidr('192.168.0.0/16'))"},
365 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
366 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
367 },
368 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
369 },
370 {
371 ops: []string{".containsCIDR('192.0.0.0/30')"},
372 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
373 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
374 },
375 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
376 },
377 {
378 ops: []string{".containsCIDR('192.168.0.0/16')"},
379 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
380 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
381 },
382 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
383 },
384 {
385 ops: []string{".containsIP(ip('192.0.0.1'))"},
386 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
387 return checker.CostEstimate{Min: c.Min + 2, Max: c.Max + 5}
388 },
389 expectRuntimeCost: func(c uint64) uint64 { return c + 2 },
390 },
391 {
392 ops: []string{".containsIP(ip('192.169.0.1'))"},
393 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
394 return checker.CostEstimate{Min: c.Min + 3, Max: c.Max + 6}
395 },
396 expectRuntimeCost: func(c uint64) uint64 { return c + 3 },
397 },
398 {
399 ops: []string{".containsIP(ip('192.169.169.250'))"},
400 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
401 return checker.CostEstimate{Min: c.Min + 3, Max: c.Max + 6}
402 },
403 expectRuntimeCost: func(c uint64) uint64 { return c + 3 },
404 },
405 {
406 ops: []string{".containsIP('192.0.0.1')"},
407 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
408 return checker.CostEstimate{Min: c.Min + 2, Max: c.Max + 5}
409 },
410 expectRuntimeCost: func(c uint64) uint64 { return c + 2 },
411 },
412 {
413 ops: []string{".containsIP('192.169.0.1')"},
414 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
415 return checker.CostEstimate{Min: c.Min + 3, Max: c.Max + 6}
416 },
417 expectRuntimeCost: func(c uint64) uint64 { return c + 3 },
418 },
419 }...)
420
421 //nolint:gocritic
422 ipv6Cases := append(cases, []testCase{
423 {
424 ops: []string{".containsCIDR(cidr('2001:db8::/126'))"},
425 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
426 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
427 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
428 },
429 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
430 },
431 {
432 ops: []string{".containsCIDR(cidr('2001:db8::/32'))"},
433 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
434 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
435 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
436 },
437 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
438 },
439 {
440 ops: []string{".containsCIDR('2001:db8::/126')"},
441 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
442 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
443 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
444 },
445 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
446 },
447 {
448 ops: []string{".containsCIDR('2001:db8::/32')"},
449 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
450 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
451 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 9}
452 },
453 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
454 },
455 {
456 ops: []string{".containsIP(ip('2001:db8:3333:4444:5555:6666:7777:8888'))"},
457 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
458 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
459 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 8}
460 },
461 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
462 },
463 {
464 ops: []string{".containsIP(ip('2001:db8::1'))"},
465 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
466 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
467 return checker.CostEstimate{Min: c.Min + 3, Max: c.Max + 6}
468 },
469 expectRuntimeCost: func(c uint64) uint64 { return c + 3 },
470 },
471 {
472 ops: []string{".containsIP('2001:db8:3333:4444:5555:6666:7777:8888')"},
473 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
474 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
475 return checker.CostEstimate{Min: c.Min + 5, Max: c.Max + 8}
476 },
477 expectRuntimeCost: func(c uint64) uint64 { return c + 5 },
478 },
479 {
480 ops: []string{".containsIP('2001:db8::1')"},
481 // For operations like checking if an IP is in a CIDR, the cost is expected to higher.
482 expectEsimatedCost: func(c checker.CostEstimate) checker.CostEstimate {
483 return checker.CostEstimate{Min: c.Min + 3, Max: c.Max + 6}
484 },
485 expectRuntimeCost: func(c uint64) uint64 { return c + 3 },
486 },
487 }...)
488
489 for _, tc := range ipv4Cases {
490 for _, op := range tc.ops {
491 t.Run(ipv4+op, func(t *testing.T) {
492 testCost(t, ipv4+op, tc.expectEsimatedCost(ipv4BaseEstimatedCost), tc.expectRuntimeCost(ipv4BaseRuntimeCost))
493 })
494 }
495 }
496
497 for _, tc := range ipv6Cases {
498 for _, op := range tc.ops {
499 t.Run(ipv6+op, func(t *testing.T) {
500 testCost(t, ipv6+op, tc.expectEsimatedCost(ipv6BaseEstimatedCost), tc.expectRuntimeCost(ipv6BaseRuntimeCost))
501 })
502 }
503 }
504 }
505
506 func TestStringLibrary(t *testing.T) {
507 cases := []struct {
508 name string
509 expr string
510 expectEsimatedCost checker.CostEstimate
511 expectRuntimeCost uint64
512 }{
513 {
514 name: "lowerAscii",
515 expr: "'ABCDEFGHIJ abcdefghij'.lowerAscii()",
516 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
517 expectRuntimeCost: 3,
518 },
519 {
520 name: "lowerAsciiEquals",
521 expr: "'ABCDEFGHIJ abcdefghij'.lowerAscii() == 'abcdefghij ABCDEFGHIJ'.lowerAscii()",
522 expectEsimatedCost: checker.CostEstimate{Min: 7, Max: 9},
523 expectRuntimeCost: 9,
524 },
525 {
526 name: "upperAscii",
527 expr: "'ABCDEFGHIJ abcdefghij'.upperAscii()",
528 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
529 expectRuntimeCost: 3,
530 },
531 {
532 name: "upperAsciiEquals",
533 expr: "'ABCDEFGHIJ abcdefghij'.upperAscii() == 'abcdefghij ABCDEFGHIJ'.upperAscii()",
534 expectEsimatedCost: checker.CostEstimate{Min: 7, Max: 9},
535 expectRuntimeCost: 9,
536 },
537 {
538 name: "quote",
539 expr: "strings.quote('ABCDEFGHIJ abcdefghij')",
540 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
541 expectRuntimeCost: 3,
542 },
543 {
544 name: "quoteEquals",
545 expr: "strings.quote('ABCDEFGHIJ abcdefghij') == strings.quote('ABCDEFGHIJ abcdefghij')",
546 expectEsimatedCost: checker.CostEstimate{Min: 7, Max: 11},
547 expectRuntimeCost: 9,
548 },
549 {
550 name: "replace",
551 expr: "'abc 123 def 123'.replace('123', '456')",
552 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
553 expectRuntimeCost: 3,
554 },
555 {
556 name: "replace between all chars",
557 expr: "'abc 123 def 123'.replace('', 'x')",
558 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
559 expectRuntimeCost: 3,
560 },
561 {
562 name: "replace with empty",
563 expr: "'abc 123 def 123'.replace('123', '')",
564 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
565 expectRuntimeCost: 3,
566 },
567 {
568 name: "replace with limit",
569 expr: "'abc 123 def 123'.replace('123', '456', 1)",
570 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
571 expectRuntimeCost: 3,
572 },
573 {
574 name: "split",
575 expr: "'abc 123 def 123'.split(' ')",
576 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
577 expectRuntimeCost: 3,
578 },
579 {
580 name: "split with limit",
581 expr: "'abc 123 def 123'.split(' ', 1)",
582 expectEsimatedCost: checker.CostEstimate{Min: 3, Max: 3},
583 expectRuntimeCost: 3,
584 },
585 {
586 name: "substring",
587 expr: "'abc 123 def 123'.substring(5)",
588 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
589 expectRuntimeCost: 2,
590 },
591 {
592 name: "substring with end",
593 expr: "'abc 123 def 123'.substring(5, 8)",
594 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
595 expectRuntimeCost: 2,
596 },
597 {
598 name: "trim",
599 expr: "' abc 123 def 123 '.trim()",
600 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
601 expectRuntimeCost: 2,
602 },
603 {
604 name: "join with separator",
605 expr: "['aa', 'bb', 'cc', 'd', 'e', 'f', 'g', 'h', 'i', 'j'].join(' ')",
606 expectEsimatedCost: checker.CostEstimate{Min: 11, Max: 23},
607 expectRuntimeCost: 15,
608 },
609 {
610 name: "join",
611 expr: "['aa', 'bb', 'cc', 'd', 'e', 'f', 'g', 'h', 'i', 'j'].join()",
612 expectEsimatedCost: checker.CostEstimate{Min: 10, Max: 22},
613 expectRuntimeCost: 13,
614 },
615 {
616 name: "find",
617 expr: "'abc 123 def 123'.find('123')",
618 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
619 expectRuntimeCost: 2,
620 },
621 {
622 name: "findAll",
623 expr: "'abc 123 def 123'.findAll('123')",
624 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
625 expectRuntimeCost: 2,
626 },
627 {
628 name: "findAll with limit",
629 expr: "'abc 123 def 123'.findAll('123', 1)",
630 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
631 expectRuntimeCost: 2,
632 },
633 {
634 name: "jsonpatch.escapeKey",
635 expr: "jsonpatch.escapeKey('abc/def~ abc/def~')",
636 expectEsimatedCost: checker.CostEstimate{Min: 2, Max: 2},
637 expectRuntimeCost: 2,
638 },
639 }
640
641 for _, tc := range cases {
642 t.Run(tc.name, func(t *testing.T) {
643 testCost(t, tc.expr, tc.expectEsimatedCost, tc.expectRuntimeCost)
644 })
645 }
646 }
647
648 func TestAuthzLibrary(t *testing.T) {
649 cases := []struct {
650 name string
651 expr string
652 expectEstimatedCost checker.CostEstimate
653 expectRuntimeCost uint64
654 }{
655 {
656 name: "path",
657 expr: "authorizer.path('/healthz')",
658 expectEstimatedCost: checker.CostEstimate{Min: 2, Max: 2},
659 expectRuntimeCost: 2,
660 },
661 {
662 name: "resource",
663 expr: "authorizer.group('apps').resource('deployments').subresource('status').namespace('test').name('backend')",
664 expectEstimatedCost: checker.CostEstimate{Min: 6, Max: 6},
665 expectRuntimeCost: 6,
666 },
667 {
668 name: "fieldSelector",
669 expr: "authorizer.group('').resource('pods').fieldSelector('spec.nodeName=example-node-name.fully.qualified.domain.name.example.com')",
670 expectEstimatedCost: checker.CostEstimate{Min: 1821, Max: 1821},
671 expectRuntimeCost: 1821, // authorizer(1) + group(1) + resource(1) + fieldSelector(10 + ceil(71/2)*50=1800 + ceil(71*.1)=8)
672 },
673 {
674 name: "labelSelector",
675 expr: "authorizer.group('').resource('pods').labelSelector('spec.nodeName=example-node-name.fully.qualified.domain.name.example.com')",
676 expectEstimatedCost: checker.CostEstimate{Min: 1821, Max: 1821},
677 expectRuntimeCost: 1821, // authorizer(1) + group(1) + resource(1) + fieldSelector(10 + ceil(71/2)*50=1800 + ceil(71*.1)=8)
678 },
679 {
680 name: "path check allowed",
681 expr: "authorizer.path('/healthz').check('get').allowed()",
682 expectEstimatedCost: checker.CostEstimate{Min: 350003, Max: 350003},
683 expectRuntimeCost: 350003,
684 },
685 {
686 name: "resource check allowed",
687 expr: "authorizer.group('apps').resource('deployments').subresource('status').namespace('test').name('backend').check('create').allowed()",
688 expectEstimatedCost: checker.CostEstimate{Min: 350007, Max: 350007},
689 expectRuntimeCost: 350007,
690 },
691 {
692 name: "resource check reason",
693 expr: "authorizer.group('apps').resource('deployments').subresource('status').namespace('test').name('backend').check('create').allowed()",
694 expectEstimatedCost: checker.CostEstimate{Min: 350007, Max: 350007},
695 expectRuntimeCost: 350007,
696 },
697 {
698 name: "resource check errored",
699 expr: "authorizer.group('apps').resource('deployments').subresource('status').namespace('test').name('backend').check('create').errored()",
700 expectEstimatedCost: checker.CostEstimate{Min: 350007, Max: 350007},
701 expectRuntimeCost: 350007,
702 },
703 {
704 name: "resource check error",
705 expr: "authorizer.group('apps').resource('deployments').subresource('status').namespace('test').name('backend').check('create').error()",
706 expectEstimatedCost: checker.CostEstimate{Min: 350007, Max: 350007},
707 expectRuntimeCost: 350007,
708 },
709 }
710
711 for _, tc := range cases {
712 t.Run(tc.name, func(t *testing.T) {
713 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
714 })
715 }
716 }
717
718 func TestQuantityCost(t *testing.T) {
719 cases := []struct {
720 name string
721 expr string
722 expectEstimatedCost checker.CostEstimate
723 expectRuntimeCost uint64
724 }{
725 {
726 name: "path",
727 expr: `quantity("12Mi")`,
728 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
729 expectRuntimeCost: 1,
730 },
731 {
732 name: "isQuantity",
733 expr: `isQuantity("20")`,
734 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
735 expectRuntimeCost: 1,
736 },
737 {
738 name: "isQuantity_megabytes",
739 expr: `isQuantity("20M")`,
740 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
741 expectRuntimeCost: 1,
742 },
743 {
744 name: "equality_reflexivity",
745 expr: `quantity("200M") == quantity("200M")`,
746 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
747 expectRuntimeCost: 3,
748 },
749 {
750 name: "equality_symmetry",
751 expr: `quantity("200M") == quantity("0.2G") && quantity("0.2G") == quantity("200M")`,
752 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 6},
753 expectRuntimeCost: 6,
754 },
755 {
756 name: "equality_transitivity",
757 expr: `quantity("2M") == quantity("0.002G") && quantity("2000k") == quantity("2M") && quantity("0.002G") == quantity("2000k")`,
758 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 9},
759 expectRuntimeCost: 9,
760 },
761 {
762 name: "quantity_less",
763 expr: `quantity("50M").isLessThan(quantity("50Mi"))`,
764 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
765 expectRuntimeCost: 3,
766 },
767 {
768 name: "quantity_greater",
769 expr: `quantity("50Mi").isGreaterThan(quantity("50M"))`,
770 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
771 expectRuntimeCost: 3,
772 },
773 {
774 name: "compare_equal",
775 expr: `quantity("200M").compareTo(quantity("0.2G")) > 0`,
776 expectEstimatedCost: checker.CostEstimate{Min: 4, Max: 4},
777 expectRuntimeCost: 4,
778 },
779 {
780 name: "add_quantity",
781 expr: `quantity("50k").add(quantity("20")) == quantity("50.02k")`,
782 expectEstimatedCost: checker.CostEstimate{Min: 5, Max: 5},
783 expectRuntimeCost: 5,
784 },
785 {
786 name: "sub_quantity",
787 expr: `quantity("50k").sub(quantity("20")) == quantity("49.98k")`,
788 expectEstimatedCost: checker.CostEstimate{Min: 5, Max: 5},
789 expectRuntimeCost: 5,
790 },
791 {
792 name: "sub_int",
793 expr: `quantity("50k").sub(20) == quantity("49980")`,
794 expectEstimatedCost: checker.CostEstimate{Min: 4, Max: 4},
795 expectRuntimeCost: 4,
796 },
797 {
798 name: "arith_chain_1",
799 expr: `quantity("50k").add(20).sub(quantity("100k")).asInteger() > 0`,
800 expectEstimatedCost: checker.CostEstimate{Min: 6, Max: 6},
801 expectRuntimeCost: 6,
802 },
803 {
804 name: "arith_chain",
805 expr: `quantity("50k").add(20).sub(quantity("100k")).sub(-50000).asInteger() > 0`,
806 expectEstimatedCost: checker.CostEstimate{Min: 7, Max: 7},
807 expectRuntimeCost: 7,
808 },
809 {
810 name: "as_integer",
811 expr: `quantity("50k").asInteger() > 0`,
812 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
813 expectRuntimeCost: 3,
814 },
815 {
816 name: "is_integer",
817 expr: `quantity("50").isInteger()`,
818 expectEstimatedCost: checker.CostEstimate{Min: 2, Max: 2},
819 expectRuntimeCost: 2,
820 },
821 {
822 name: "as_float",
823 expr: `quantity("50.703k").asApproximateFloat() > 0.0`,
824 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
825 expectRuntimeCost: 3,
826 },
827 }
828
829 for _, tc := range cases {
830 t.Run(tc.name, func(t *testing.T) {
831 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
832 })
833 }
834 }
835
836 func TestNameFormatCost(t *testing.T) {
837 cases := []struct {
838 name string
839 expr string
840 expectEstimatedCost checker.CostEstimate
841 expectRuntimeCost uint64
842 }{
843 {
844 name: "format.named",
845 expr: `format.named("dns1123subdomain")`,
846 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
847 expectRuntimeCost: 1,
848 },
849 {
850 name: "format.dns1123Subdomain.validate",
851 expr: `format.named("dns1123Subdomain").value().validate("my-name")`,
852 // Estimated cost doesnt know value at runtime so it is
853 // using an estimated maximum regex length
854 expectEstimatedCost: checker.CostEstimate{Min: 34, Max: 34},
855 expectRuntimeCost: 17,
856 },
857 {
858 name: "format.dns1123label.validate",
859 expr: `format.named("dns1123Label").value().validate("my-name")`,
860 expectEstimatedCost: checker.CostEstimate{Min: 34, Max: 34},
861 expectRuntimeCost: 10,
862 },
863 {
864 name: "format.dns1123label.validate",
865 expr: `format.named("dns1123Label").value().validate("my-name")`,
866 expectEstimatedCost: checker.CostEstimate{Min: 34, Max: 34},
867 expectRuntimeCost: 10,
868 },
869 {
870 name: "format.dns1123label.validate",
871 expr: `format.named("dns1123Label").value() == format.named("dns1123Label").value()`,
872 expectEstimatedCost: checker.CostEstimate{Min: 5, Max: 11},
873 expectRuntimeCost: 5,
874 },
875 }
876
877 for _, tc := range cases {
878 t.Run(tc.name, func(t *testing.T) {
879 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
880 })
881 }
882 }
883
884 func TestSetsCost(t *testing.T) {
885 cases := []struct {
886 name string
887 expr string
888 expectEstimatedCost checker.CostEstimate
889 expectRuntimeCost uint64
890 }{
891 {
892 name: "sets",
893 expr: `sets.contains([], [])`,
894 expectEstimatedCost: checker.CostEstimate{Min: 21, Max: 21},
895 expectRuntimeCost: 21,
896 },
897 {
898 expr: `sets.contains([1], [])`,
899 expectEstimatedCost: checker.CostEstimate{Min: 21, Max: 21},
900 expectRuntimeCost: 21,
901 },
902 {
903 expr: `sets.contains([1], [1])`,
904 expectEstimatedCost: checker.CostEstimate{Min: 22, Max: 22},
905 expectRuntimeCost: 22,
906 },
907 {
908 expr: `sets.contains([1], [1, 1])`,
909 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
910 expectRuntimeCost: 23,
911 },
912 {
913 expr: `sets.contains([1, 1], [1])`,
914 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
915 expectRuntimeCost: 23,
916 },
917 {
918 expr: `sets.contains([2, 1], [1])`,
919 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
920 expectRuntimeCost: 23,
921 },
922 {
923 expr: `sets.contains([1, 2, 3, 4], [2, 3])`,
924 expectEstimatedCost: checker.CostEstimate{Min: 29, Max: 29},
925 expectRuntimeCost: 29,
926 },
927 {
928 expr: `sets.contains([1], [1.0, 1])`,
929 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
930 expectRuntimeCost: 23,
931 },
932 {
933 expr: `sets.contains([1, 2], [2u, 2.0])`,
934 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
935 expectRuntimeCost: 25,
936 },
937 {
938 expr: `sets.contains([1, 2u], [2, 2.0])`,
939 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
940 expectRuntimeCost: 25,
941 },
942 {
943 expr: `sets.contains([1, 2.0, 3u], [1.0, 2u, 3])`,
944 expectEstimatedCost: checker.CostEstimate{Min: 30, Max: 30},
945 expectRuntimeCost: 30,
946 },
947 {
948 expr: `sets.contains([[1], [2, 3]], [[2, 3.0]])`,
949 // 10 for each list creation, top-level list sizes are 2, 1
950 expectEstimatedCost: checker.CostEstimate{Min: 53, Max: 53},
951 expectRuntimeCost: 53,
952 },
953 {
954 expr: `!sets.contains([1], [2])`,
955 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
956 expectRuntimeCost: 23,
957 },
958 {
959 expr: `!sets.contains([1], [1, 2])`,
960 expectEstimatedCost: checker.CostEstimate{Min: 24, Max: 24},
961 expectRuntimeCost: 24,
962 },
963 {
964 expr: `!sets.contains([1], ["1", 1])`,
965 expectEstimatedCost: checker.CostEstimate{Min: 24, Max: 24},
966 expectRuntimeCost: 24,
967 },
968 {
969 expr: `!sets.contains([1], [1.1, 1u])`,
970 expectEstimatedCost: checker.CostEstimate{Min: 24, Max: 24},
971 expectRuntimeCost: 24,
972 },
973
974 // set equivalence (note the cost factor is higher as it's basically two contains checks)
975 {
976 expr: `sets.equivalent([], [])`,
977 expectEstimatedCost: checker.CostEstimate{Min: 21, Max: 21},
978 expectRuntimeCost: 21,
979 },
980 {
981 expr: `sets.equivalent([1], [1])`,
982 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
983 expectRuntimeCost: 23,
984 },
985 {
986 expr: `sets.equivalent([1], [1, 1])`,
987 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
988 expectRuntimeCost: 25,
989 },
990 {
991 expr: `sets.equivalent([1, 1], [1])`,
992 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
993 expectRuntimeCost: 25,
994 },
995 {
996 expr: `sets.equivalent([1], [1u, 1.0])`,
997 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
998 expectRuntimeCost: 25,
999 },
1000 {
1001 expr: `sets.equivalent([1], [1u, 1.0])`,
1002 expectEstimatedCost: checker.CostEstimate{Min: 25, Max: 25},
1003 expectRuntimeCost: 25,
1004 },
1005 {
1006 expr: `sets.equivalent([1, 2, 3], [3u, 2.0, 1])`,
1007 expectEstimatedCost: checker.CostEstimate{Min: 39, Max: 39},
1008 expectRuntimeCost: 39,
1009 },
1010 {
1011 expr: `sets.equivalent([[1.0], [2, 3]], [[1], [2, 3.0]])`,
1012 expectEstimatedCost: checker.CostEstimate{Min: 69, Max: 69},
1013 expectRuntimeCost: 69,
1014 },
1015 {
1016 expr: `!sets.equivalent([2, 1], [1])`,
1017 expectEstimatedCost: checker.CostEstimate{Min: 26, Max: 26},
1018 expectRuntimeCost: 26,
1019 },
1020 {
1021 expr: `!sets.equivalent([1], [1, 2])`,
1022 expectEstimatedCost: checker.CostEstimate{Min: 26, Max: 26},
1023 expectRuntimeCost: 26,
1024 },
1025 {
1026 expr: `!sets.equivalent([1, 2], [2u, 2, 2.0])`,
1027 expectEstimatedCost: checker.CostEstimate{Min: 34, Max: 34},
1028 expectRuntimeCost: 34,
1029 },
1030 {
1031 expr: `!sets.equivalent([1, 2], [1u, 2, 2.3])`,
1032 expectEstimatedCost: checker.CostEstimate{Min: 34, Max: 34},
1033 expectRuntimeCost: 34,
1034 },
1035 {
1036 expr: `sets.intersects([1], [1])`,
1037 expectEstimatedCost: checker.CostEstimate{Min: 22, Max: 22},
1038 expectRuntimeCost: 22,
1039 },
1040 {
1041 expr: `sets.intersects([1], [1, 1])`,
1042 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1043 expectRuntimeCost: 23,
1044 },
1045 {
1046 expr: `sets.intersects([1, 1], [1])`,
1047 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1048 expectRuntimeCost: 23,
1049 },
1050 {
1051 expr: `sets.intersects([2, 1], [1])`,
1052 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1053 expectRuntimeCost: 23,
1054 },
1055 {
1056 expr: `sets.intersects([1], [1, 2])`,
1057 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1058 expectRuntimeCost: 23,
1059 },
1060 {
1061 expr: `sets.intersects([1], [1.0, 2])`,
1062 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1063 expectRuntimeCost: 23,
1064 },
1065 {
1066 expr: `sets.intersects([1, 2], [2u, 2, 2.0])`,
1067 expectEstimatedCost: checker.CostEstimate{Min: 27, Max: 27},
1068 expectRuntimeCost: 27,
1069 },
1070 {
1071 expr: `sets.intersects([1, 2], [1u, 2, 2.3])`,
1072 expectEstimatedCost: checker.CostEstimate{Min: 27, Max: 27},
1073 expectRuntimeCost: 27,
1074 },
1075 {
1076 expr: `sets.intersects([[1], [2, 3]], [[1, 2], [2, 3.0]])`,
1077 expectEstimatedCost: checker.CostEstimate{Min: 65, Max: 65},
1078 expectRuntimeCost: 65,
1079 },
1080 {
1081 expr: `!sets.intersects([], [])`,
1082 expectEstimatedCost: checker.CostEstimate{Min: 22, Max: 22},
1083 expectRuntimeCost: 22,
1084 },
1085 {
1086 expr: `!sets.intersects([1], [])`,
1087 expectEstimatedCost: checker.CostEstimate{Min: 22, Max: 22},
1088 expectRuntimeCost: 22,
1089 },
1090 {
1091 expr: `!sets.intersects([1], [2])`,
1092 expectEstimatedCost: checker.CostEstimate{Min: 23, Max: 23},
1093 expectRuntimeCost: 23,
1094 },
1095 {
1096 expr: `!sets.intersects([1], ["1", 2])`,
1097 expectEstimatedCost: checker.CostEstimate{Min: 24, Max: 24},
1098 expectRuntimeCost: 24,
1099 },
1100 {
1101 expr: `!sets.intersects([1], [1.1, 2u])`,
1102 expectEstimatedCost: checker.CostEstimate{Min: 24, Max: 24},
1103 expectRuntimeCost: 24,
1104 },
1105 }
1106
1107 for _, tc := range cases {
1108 t.Run(tc.name, func(t *testing.T) {
1109 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
1110 })
1111 }
1112 }
1113
1114 func TestSemverCost(t *testing.T) {
1115 cases := []struct {
1116 name string
1117 expr string
1118 expectEstimatedCost checker.CostEstimate
1119 expectRuntimeCost uint64
1120 }{
1121 {
1122 name: "semver",
1123 expr: `semver("1.0.0")`,
1124 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
1125 expectRuntimeCost: 1,
1126 },
1127 {
1128 name: "semver long input",
1129 expr: `semver("1234.56789012345.67890123456789")`,
1130 expectEstimatedCost: checker.CostEstimate{Min: 4, Max: 4},
1131 expectRuntimeCost: 4,
1132 },
1133 {
1134 name: "isSemver",
1135 expr: `isSemver("1.0.0")`,
1136 expectEstimatedCost: checker.CostEstimate{Min: 1, Max: 1},
1137 expectRuntimeCost: 1,
1138 },
1139 {
1140 name: "isSemver long input",
1141 expr: `isSemver("1234.56789012345.67890123456789")`,
1142 expectEstimatedCost: checker.CostEstimate{Min: 4, Max: 4},
1143 expectRuntimeCost: 4,
1144 },
1145 // major(), minor(), patch()
1146 {
1147 name: "major",
1148 expr: `semver("1.2.3").major()`,
1149 expectEstimatedCost: checker.CostEstimate{Min: 2, Max: 2},
1150 expectRuntimeCost: 2,
1151 },
1152 {
1153 name: "minor",
1154 expr: `semver("1.2.3").minor()`,
1155 expectEstimatedCost: checker.CostEstimate{Min: 2, Max: 2},
1156 expectRuntimeCost: 2,
1157 },
1158 {
1159 name: "patch",
1160 expr: `semver("1.2.3").patch()`,
1161 expectEstimatedCost: checker.CostEstimate{Min: 2, Max: 2},
1162 expectRuntimeCost: 2,
1163 },
1164 // isLessThan
1165 {
1166 name: "isLessThan",
1167 expr: `semver("1.0.0").isLessThan(semver("1.1.0"))`,
1168 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
1169 expectRuntimeCost: 3,
1170 },
1171 // isGreaterThan
1172 {
1173 name: "isGreaterThan",
1174 expr: `semver("1.1.0").isGreaterThan(semver("1.0.0"))`,
1175 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
1176 expectRuntimeCost: 3,
1177 },
1178 // compareTo
1179 {
1180 name: "compareTo",
1181 expr: `semver("1.0.0").compareTo(semver("1.2.3"))`,
1182 expectEstimatedCost: checker.CostEstimate{Min: 3, Max: 3},
1183 expectRuntimeCost: 3,
1184 },
1185 }
1186
1187 for _, tc := range cases {
1188 t.Run(tc.name, func(t *testing.T) {
1189 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
1190 })
1191 }
1192 }
1193
1194 func TestTwoVariableComprehensionCost(t *testing.T) {
1195 cases := []struct {
1196 name string
1197 expr string
1198 expectEstimatedCost checker.CostEstimate
1199 expectRuntimeCost uint64
1200 }{
1201 {
1202 name: "map all",
1203 expr: `{'a': 1, 'b': 2}.all(k, v, v > 0)`,
1204 expectEstimatedCost: checker.CostEstimate{Min: 37, Max: 41},
1205 expectRuntimeCost: 41,
1206 },
1207 {
1208 name: "map exists",
1209 expr: `{'a': 1, 'b': 2}.exists(k, v, v > 0)`,
1210 expectEstimatedCost: checker.CostEstimate{Min: 39, Max: 43},
1211 expectRuntimeCost: 40,
1212 },
1213 {
1214 name: "map existsOne",
1215 expr: `{'a': 1, 'b': 2}.existsOne(k, v, v > 0)`,
1216 expectEstimatedCost: checker.CostEstimate{Min: 38, Max: 40},
1217 expectRuntimeCost: 40,
1218 },
1219 {
1220 name: "map transformMap",
1221 expr: `{'a': 1, 'b': 2}.transformMap(k, v, v + 1)`,
1222 expectEstimatedCost: checker.CostEstimate{Min: 71, Max: 71},
1223 expectRuntimeCost: 71,
1224 },
1225 {
1226 name: "map transformMap with filter",
1227 expr: `{'a': 1, 'b': 2}.transformMap(k, v, v < 5, v + 1)`,
1228 expectEstimatedCost: checker.CostEstimate{Min: 67, Max: 75},
1229 expectRuntimeCost: 75,
1230 },
1231 {
1232 name: "map transformMapEntry",
1233 expr: `{'a': 1, 'b': 2}.transformMapEntry(k, v, {k: v + 1})`,
1234 expectEstimatedCost: checker.CostEstimate{Min: 131, Max: 131},
1235 expectRuntimeCost: 131,
1236 },
1237 {
1238 name: "map transformMapEntry with filter",
1239 expr: `{'a': 1, 'b': 2}.transformMapEntry(k, v, v < 5, {k: v + 1})`,
1240 expectEstimatedCost: checker.CostEstimate{Min: 67, Max: 135},
1241 expectRuntimeCost: 135,
1242 },
1243
1244 {
1245 name: "list all",
1246 expr: `[1, 2].all(i, v, v > 0)`,
1247 expectEstimatedCost: checker.CostEstimate{Min: 17, Max: 21},
1248 expectRuntimeCost: 21,
1249 },
1250 {
1251 name: "list exists",
1252 expr: `[1, 2].exists(i, v, v > 0)`,
1253 expectEstimatedCost: checker.CostEstimate{Min: 19, Max: 23},
1254 expectRuntimeCost: 20,
1255 },
1256 {
1257 name: "list existsOne",
1258 expr: `[1, 2].existsOne(i, v, v > 0)`,
1259 expectEstimatedCost: checker.CostEstimate{Min: 18, Max: 20},
1260 expectRuntimeCost: 20,
1261 },
1262 {
1263 name: "list transformList",
1264 expr: `[1, 2].transformList(i, v, v + 1)`,
1265 expectEstimatedCost: checker.CostEstimate{Min: 49, Max: 49},
1266 expectRuntimeCost: 49,
1267 },
1268 {
1269 name: "list transformList with filter",
1270 expr: `[1, 2].transformList(i, v, v < 5, v + 1)`,
1271 expectEstimatedCost: checker.CostEstimate{Min: 27, Max: 53},
1272 expectRuntimeCost: 53,
1273 },
1274 }
1275
1276 for _, tc := range cases {
1277 t.Run(tc.name, func(t *testing.T) {
1278 testCost(t, tc.expr, tc.expectEstimatedCost, tc.expectRuntimeCost)
1279 })
1280 }
1281 }
1282
1283 func testCost(t *testing.T, expr string, expectEsimatedCost checker.CostEstimate, expectRuntimeCost uint64) {
1284 originalPanicOnUnknown := panicOnUnknown
1285 panicOnUnknown = true
1286 t.Cleanup(func() { panicOnUnknown = originalPanicOnUnknown })
1287
1288 est := &CostEstimator{SizeEstimator: &testCostEstimator{}}
1289 env, err := cel.NewEnv(
1290 ext.Strings(ext.StringsVersion(2)),
1291 URLs(),
1292 Regex(),
1293 Lists(),
1294 Authz(),
1295 AuthzSelectors(),
1296 Quantity(),
1297 ext.Sets(),
1298 IP(),
1299 CIDR(),
1300 Format(),
1301 JSONPatch(),
1302 cel.OptionalTypes(),
1303 // cel-go v0.17.7 introduced CostEstimatorOptions.
1304 // Previous the presence has a cost of 0 but cel fixed it to 1. We still set to 0 here to avoid breaking changes.
1305 cel.CostEstimatorOptions(checker.PresenceTestHasCost(false)),
1306 ext.TwoVarComprehensions(),
1307 SemverLib(SemverVersion(1)),
1308 )
1309 if err != nil {
1310 t.Fatalf("%v", err)
1311 }
1312 env, err = env.Extend(cel.Variable("authorizer", AuthorizerType))
1313 if err != nil {
1314 t.Fatalf("%v", err)
1315 }
1316 compiled, issues := env.Compile(expr)
1317 if len(issues.Errors()) > 0 {
1318 var errList []string
1319 for _, issue := range issues.Errors() {
1320 errList = append(errList, issue.ToDisplayString(common.NewTextSource(expr)))
1321 }
1322 t.Fatalf("%v", errList)
1323 }
1324 estCost, err := env.EstimateCost(compiled, est)
1325 if err != nil {
1326 t.Fatalf("%v", err)
1327 }
1328 if estCost.Min != expectEsimatedCost.Min || estCost.Max != expectEsimatedCost.Max {
1329 t.Errorf("Expected estimated cost of %d..%d but got %d..%d", expectEsimatedCost.Min, expectEsimatedCost.Max, estCost.Min, estCost.Max)
1330 }
1331 prog, err := env.Program(compiled, cel.CostTracking(est))
1332 if err != nil {
1333 t.Fatalf("%v", err)
1334 }
1335 _, details, err := prog.Eval(map[string]interface{}{"authorizer": NewAuthorizerVal(nil, alwaysAllowAuthorizer{})})
1336 if err != nil {
1337 t.Fatalf("%v", err)
1338 }
1339 cost := details.ActualCost()
1340 if *cost != expectRuntimeCost {
1341 t.Errorf("Expected cost of %d but got %d", expectRuntimeCost, *cost)
1342 }
1343 }
1344
1345 func TestSize(t *testing.T) {
1346 exactSize := func(size int) checker.SizeEstimate {
1347 return checker.SizeEstimate{Min: uint64(size), Max: uint64(size)}
1348 }
1349 exactSizes := func(sizes ...int) []checker.SizeEstimate {
1350 results := make([]checker.SizeEstimate, len(sizes))
1351 for i, size := range sizes {
1352 results[i] = exactSize(size)
1353 }
1354 return results
1355 }
1356 cases := []struct {
1357 name string
1358 function string
1359 overload string
1360 targetSize checker.SizeEstimate
1361 argSizes []checker.SizeEstimate
1362 expectSize checker.SizeEstimate
1363 }{
1364 {
1365 name: "replace empty with char",
1366 function: "replace",
1367 targetSize: exactSize(3), // e.g. abc
1368 argSizes: exactSizes(0, 1), // e.g. replace "" with "_"
1369 expectSize: exactSize(7), // e.g. _a_b_c_
1370 },
1371 {
1372 name: "maybe replace char with empty",
1373 function: "replace",
1374 targetSize: exactSize(3),
1375 argSizes: exactSizes(1, 0),
1376 expectSize: checker.SizeEstimate{Min: 0, Max: 3},
1377 },
1378 {
1379 name: "maybe replace repeated",
1380 function: "replace",
1381 targetSize: exactSize(4),
1382 argSizes: exactSizes(2, 4),
1383 expectSize: checker.SizeEstimate{Min: 4, Max: 8},
1384 },
1385 {
1386 name: "maybe replace empty",
1387 function: "replace",
1388 targetSize: exactSize(4),
1389 argSizes: []checker.SizeEstimate{{Min: 0, Max: 1}, {Min: 0, Max: 2}},
1390 expectSize: checker.SizeEstimate{Min: 0, Max: 14}, // len(__a__a__a__a__) == 14
1391 },
1392 {
1393 name: "replace non-empty size range, maybe larger",
1394 function: "replace",
1395 targetSize: exactSize(4),
1396 argSizes: []checker.SizeEstimate{{Min: 1, Max: 1}, {Min: 1, Max: 2}},
1397 expectSize: checker.SizeEstimate{Min: 4, Max: 8},
1398 },
1399 {
1400 name: "replace non-empty size range, maybe smaller",
1401 function: "replace",
1402 targetSize: exactSize(4),
1403 argSizes: []checker.SizeEstimate{{Min: 1, Max: 2}, {Min: 1, Max: 1}},
1404 expectSize: checker.SizeEstimate{Min: 2, Max: 4},
1405 },
1406 }
1407
1408 originalPanicOnUnknown := panicOnUnknown
1409 panicOnUnknown = true
1410 t.Cleanup(func() { panicOnUnknown = originalPanicOnUnknown })
1411
1412 est := &CostEstimator{SizeEstimator: &testCostEstimator{}}
1413 for _, tc := range cases {
1414 t.Run(tc.name, func(t *testing.T) {
1415 var targetNode checker.AstNode = testNode{size: tc.targetSize}
1416 argNodes := make([]checker.AstNode, len(tc.argSizes))
1417 for i, arg := range tc.argSizes {
1418 argNodes[i] = testNode{size: arg}
1419 }
1420 result := est.EstimateCallCost(tc.function, tc.overload, &targetNode, argNodes)
1421 if result.ResultSize == nil {
1422 t.Fatalf("Expected ResultSize but got none")
1423 }
1424 if *result.ResultSize != tc.expectSize {
1425 t.Fatalf("Expected %+v but got %+v", tc.expectSize, *result.ResultSize)
1426 }
1427 })
1428 }
1429 }
1430
1431 // TestTypeEquality ensures that cost is tested for all custom types used by Kubernetes libraries.
1432 func TestTypeEquality(t *testing.T) {
1433 examples := map[string]ref.Val{
1434 // Add example ref.Val's for custom types in Kubernetes here:
1435 "kubernetes.authorization.Authorizer": authorizerVal{},
1436 "kubernetes.authorization.PathCheck": pathCheckVal{},
1437 "kubernetes.authorization.GroupCheck": groupCheckVal{},
1438 "kubernetes.authorization.ResourceCheck": resourceCheckVal{},
1439 "kubernetes.authorization.Decision": decisionVal{},
1440 "kubernetes.URL": apiservercel.URL{},
1441 "kubernetes.Quantity": apiservercel.Quantity{},
1442 "net.IP": apiservercel.IP{},
1443 "net.CIDR": apiservercel.CIDR{},
1444 "kubernetes.NamedFormat": apiservercel.Format{},
1445 "kubernetes.Semver": apiservercel.Semver{},
1446 }
1447
1448 originalPanicOnUnknown := panicOnUnknown
1449 panicOnUnknown = true
1450 t.Cleanup(func() { panicOnUnknown = originalPanicOnUnknown })
1451 est := &CostEstimator{SizeEstimator: &testCostEstimator{}}
1452
1453 for _, lib := range KnownLibraries() {
1454 for _, kt := range lib.Types() {
1455 t.Run(kt.TypeName(), func(t *testing.T) {
1456 typeNode := testNode{size: checker.SizeEstimate{Min: 10, Max: 100}, typ: kt}
1457 est.EstimateCallCost("_==_", "", nil, []checker.AstNode{typeNode, typeNode})
1458 ex, ok := examples[kt.TypeName()]
1459 if !ok {
1460 t.Errorf("missing example for type: %s", kt.TypeName())
1461 }
1462 est.CallCost("_==_", "", []ref.Val{ex, ex}, nil)
1463 })
1464 }
1465 }
1466 }
1467
1468 type testNode struct {
1469 size checker.SizeEstimate
1470 typ *types.Type
1471 }
1472
1473 var _ checker.AstNode = (*testNode)(nil)
1474
1475 func (t testNode) Path() []string {
1476 return nil // not needed
1477 }
1478
1479 func (t testNode) Type() *types.Type {
1480 return t.typ // not needed
1481 }
1482
1483 func (t testNode) Expr() ast.Expr {
1484 return nil // not needed
1485 }
1486
1487 func (t testNode) ComputedSize() *checker.SizeEstimate {
1488 return &t.size
1489 }
1490
1491 type testCostEstimator struct {
1492 }
1493
1494 func (t *testCostEstimator) EstimateSize(element checker.AstNode) *checker.SizeEstimate {
1495 expr, err := cel.TypeToExprType(element.Type())
1496 if err != nil {
1497 return nil
1498 }
1499 switch expr.GetPrimitive() {
1500 case exprpb.Type_STRING:
1501 return &checker.SizeEstimate{Min: 0, Max: 12}
1502 case exprpb.Type_BYTES:
1503 return &checker.SizeEstimate{Min: 0, Max: 12}
1504 }
1505 return nil
1506 }
1507
1508 func (t *testCostEstimator) EstimateCallCost(function, overloadId string, target *checker.AstNode, args []checker.AstNode) *checker.CallEstimate {
1509 return nil
1510 }
1511
1512 type alwaysAllowAuthorizer struct{}
1513
1514 func (f alwaysAllowAuthorizer) Authorize(ctx context.Context, a authorizer.Attributes) (authorizer.Decision, string, error) {
1515 return authorizer.DecisionAllow, "", nil
1516 }