Debian Codegraph @

pkg/cel/library/lists.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
22 "github.com/google/cel-go/cel"
23 "github.com/google/cel-go/common/types"
24 "github.com/google/cel-go/common/types/ref"
25 "github.com/google/cel-go/common/types/traits"
26 "github.com/google/cel-go/interpreter/functions"
27 )
28
29 // Lists provides a CEL function library extension of list utility functions.
30 //
31 // isSorted
32 //
33 // Returns true if the provided list of comparable elements is sorted, else returns false.
34 //
35 // <list<T>>.isSorted() <bool>, T must be a comparable type
36 //
37 // Examples:
38 //
39 // [1, 2, 3].isSorted() // return true
40 // ['a', 'b', 'b', 'c'].isSorted() // return true
41 // [2.0, 1.0].isSorted() // return false
42 // [1].isSorted() // return true
43 // [].isSorted() // return true
44 //
45 // sum
46 //
47 // Returns the sum of the elements of the provided list. Supports CEL number (int, uint, double) and duration types.
48 //
49 // <list<T>>.sum() <T>, T must be a numeric type or a duration
50 //
51 // Examples:
52 //
53 // [1, 3].sum() // returns 4
54 // [1.0, 3.0].sum() // returns 4.0
55 // ['1m', '1s'].sum() // returns '1m1s'
56 // emptyIntList.sum() // returns 0
57 // emptyDoubleList.sum() // returns 0.0
58 // [].sum() // returns 0
59 //
60 // min / max
61 //
62 // Returns the minimum/maximum valued element of the provided list. Supports all comparable types.
63 // If the list is empty, an error is returned.
64 //
65 // <list<T>>.min() <T>, T must be a comparable type
66 // <list<T>>.max() <T>, T must be a comparable type
67 //
68 // Examples:
69 //
70 // [1, 3].min() // returns 1
71 // [1, 3].max() // returns 3
72 // [].min() // error
73 // [1].min() // returns 1
74 // ([0] + emptyList).min() // returns 0
75 //
76 // indexOf / lastIndexOf
77 //
78 // Returns either the first or last positional index of the provided element in the list.
79 // If the element is not found, -1 is returned. Supports all equatable types.
80 //
81 // <list<T>>.indexOf(<T>) <int>, T must be an equatable type
82 // <list<T>>.lastIndexOf(<T>) <int>, T must be an equatable type
83 //
84 // Examples:
85 //
86 // [1, 2, 2, 3].indexOf(2) // returns 1
87 // ['a', 'b', 'b', 'c'].lastIndexOf('b') // returns 2
88 // [1.0].indexOf(1.1) // returns -1
89 // [].indexOf('string') // returns -1
90 func Lists() cel.EnvOption {
91 return cel.Lib(listsLib)
92 }
93
94 var listsLib = &lists{}
95
96 type lists struct{}
97
98 func (*lists) LibraryName() string {
99 return "kubernetes.lists"
100 }
101
102 func (*lists) Types() []*cel.Type {
103 return []*cel.Type{}
104 }
105
106 func (*lists) declarations() map[string][]cel.FunctionOpt {
107 return listsLibraryDecls
108 }
109
110 var paramA = cel.TypeParamType("A")
111
112 // CEL typeParams can be used to constraint to a specific trait (e.g. traits.ComparableType) if the 1st operand is the type to constrain.
113 // But the functions we need to constrain are <list<paramType>>, not just <paramType>.
114 // Make sure the order of overload set is deterministic
115 type namedCELType struct {
116 typeName string
117 celType *cel.Type
118 }
119
120 var summableTypes = []namedCELType{
121 {typeName: "int", celType: cel.IntType},
122 {typeName: "uint", celType: cel.UintType},
123 {typeName: "double", celType: cel.DoubleType},
124 {typeName: "duration", celType: cel.DurationType},
125 }
126
127 var zeroValuesOfSummableTypes = map[string]ref.Val{
128 "int": types.Int(0),
129 "uint": types.Uint(0),
130 "double": types.Double(0.0),
131 "duration": types.Duration{Duration: 0},
132 }
133 var comparableTypes = []namedCELType{
134 {typeName: "int", celType: cel.IntType},
135 {typeName: "uint", celType: cel.UintType},
136 {typeName: "double", celType: cel.DoubleType},
137 {typeName: "bool", celType: cel.BoolType},
138 {typeName: "duration", celType: cel.DurationType},
139 {typeName: "timestamp", celType: cel.TimestampType},
140 {typeName: "string", celType: cel.StringType},
141 {typeName: "bytes", celType: cel.BytesType},
142 }
143
144 // WARNING: All library additions or modifications must follow
145 // https://github.com/kubernetes/enhancements/tree/master/keps/sig-api-machinery/2876-crd-validation-expression-language#function-library-updates
146 var listsLibraryDecls = map[string][]cel.FunctionOpt{
147 "isSorted": templatedOverloads(comparableTypes, func(name string, paramType *cel.Type) cel.FunctionOpt {
148 return cel.MemberOverload(fmt.Sprintf("list_%s_is_sorted_bool", name),
149 []*cel.Type{cel.ListType(paramType)}, cel.BoolType, cel.UnaryBinding(isSorted))
150 }),
151 "sum": templatedOverloads(summableTypes, func(name string, paramType *cel.Type) cel.FunctionOpt {
152 return cel.MemberOverload(fmt.Sprintf("list_%s_sum_%s", name, name),
153 []*cel.Type{cel.ListType(paramType)}, paramType, cel.UnaryBinding(func(list ref.Val) ref.Val {
154 return sum(
155 func() ref.Val {
156 return zeroValuesOfSummableTypes[name]
157 })(list)
158 }))
159 }),
160 "max": templatedOverloads(comparableTypes, func(name string, paramType *cel.Type) cel.FunctionOpt {
161 return cel.MemberOverload(fmt.Sprintf("list_%s_max_%s", name, name),
162 []*cel.Type{cel.ListType(paramType)}, paramType, cel.UnaryBinding(max()))
163 }),
164 "min": templatedOverloads(comparableTypes, func(name string, paramType *cel.Type) cel.FunctionOpt {
165 return cel.MemberOverload(fmt.Sprintf("list_%s_min_%s", name, name),
166 []*cel.Type{cel.ListType(paramType)}, paramType, cel.UnaryBinding(min()))
167 }),
168 "indexOf": {
169 cel.MemberOverload("list_a_index_of_int", []*cel.Type{cel.ListType(paramA), paramA}, cel.IntType,
170 cel.BinaryBinding(indexOf)),
171 },
172 "lastIndexOf": {
173 cel.MemberOverload("list_a_last_index_of_int", []*cel.Type{cel.ListType(paramA), paramA}, cel.IntType,
174 cel.BinaryBinding(lastIndexOf)),
175 },
176 }
177
178 func (*lists) CompileOptions() []cel.EnvOption {
179 options := []cel.EnvOption{}
180 for name, overloads := range listsLibraryDecls {
181 options = append(options, cel.Function(name, overloads...))
182 }
183 return options
184 }
185
186 func (*lists) ProgramOptions() []cel.ProgramOption {
187 return []cel.ProgramOption{}
188 }
189
190 func isSorted(val ref.Val) ref.Val {
191 var prev traits.Comparer
192 iterable, ok := val.(traits.Iterable)
193 if !ok {
194 return types.MaybeNoSuchOverloadErr(val)
195 }
196 for it := iterable.Iterator(); it.HasNext() == types.True; {
197 next := it.Next()
198 nextCmp, ok := next.(traits.Comparer)
199 if !ok {
200 return types.MaybeNoSuchOverloadErr(next)
201 }
202 if prev != nil {
203 cmp := prev.Compare(next)
204 if cmp == types.IntOne {
205 return types.False
206 }
207 }
208 prev = nextCmp
209 }
210 return types.True
211 }
212
213 func sum(init func() ref.Val) functions.UnaryOp {
214 return func(val ref.Val) ref.Val {
215 i := init()
216 acc, ok := i.(traits.Adder)
217 if !ok {
218 // Should never happen since all passed in init values are valid
219 return types.MaybeNoSuchOverloadErr(i)
220 }
221 iterable, ok := val.(traits.Iterable)
222 if !ok {
223 return types.MaybeNoSuchOverloadErr(val)
224 }
225 for it := iterable.Iterator(); it.HasNext() == types.True; {
226 next := it.Next()
227 nextAdder, ok := next.(traits.Adder)
228 if !ok {
229 // Should never happen for type checked CEL programs
230 return types.MaybeNoSuchOverloadErr(next)
231 }
232 if acc != nil {
233 s := acc.Add(next)
234 sum, ok := s.(traits.Adder)
235 if !ok {
236 // Should never happen for type checked CEL programs
237 return types.MaybeNoSuchOverloadErr(s)
238 }
239 acc = sum
240 } else {
241 acc = nextAdder
242 }
243 }
244 return acc.(ref.Val)
245 }
246 }
247
248 func min() functions.UnaryOp {
249 return cmp("min", types.IntOne)
250 }
251
252 func max() functions.UnaryOp {
253 return cmp("max", types.IntNegOne)
254 }
255
256 func cmp(opName string, opPreferCmpResult ref.Val) functions.UnaryOp {
257 return func(val ref.Val) ref.Val {
258 var result traits.Comparer
259 iterable, ok := val.(traits.Iterable)
260 if !ok {
261 return types.MaybeNoSuchOverloadErr(val)
262 }
263 for it := iterable.Iterator(); it.HasNext() == types.True; {
264 next := it.Next()
265 nextCmp, ok := next.(traits.Comparer)
266 if !ok {
267 // Should never happen for type checked CEL programs
268 return types.MaybeNoSuchOverloadErr(next)
269 }
270 if result == nil {
271 result = nextCmp
272 } else {
273 cmp := result.Compare(next)
274 if cmp == opPreferCmpResult {
275 result = nextCmp
276 }
277 }
278 }
279 if result == nil {
280 return types.NewErr("%s called on empty list", opName)
281 }
282 return result.(ref.Val)
283 }
284 }
285
286 func indexOf(list ref.Val, item ref.Val) ref.Val {
287 lister, ok := list.(traits.Lister)
288 if !ok {
289 return types.MaybeNoSuchOverloadErr(list)
290 }
291 sz := lister.Size().(types.Int)
292 for i := types.Int(0); i < sz; i++ {
293 if lister.Get(types.Int(i)).Equal(item) == types.True {
294 return types.Int(i)
295 }
296 }
297 return types.Int(-1)
298 }
299
300 func lastIndexOf(list ref.Val, item ref.Val) ref.Val {
301 lister, ok := list.(traits.Lister)
302 if !ok {
303 return types.MaybeNoSuchOverloadErr(list)
304 }
305 sz := lister.Size().(types.Int)
306 for i := sz - 1; i >= 0; i-- {
307 if lister.Get(types.Int(i)).Equal(item) == types.True {
308 return types.Int(i)
309 }
310 }
311 return types.Int(-1)
312 }
313
314 // templatedOverloads returns overloads for each of the provided types. The template function is called with each type
315 // name (map key) and type to construct the overloads.
316 func templatedOverloads(types []namedCELType, template func(name string, t *cel.Type) cel.FunctionOpt) []cel.FunctionOpt {
317 overloads := make([]cel.FunctionOpt, len(types))
318 i := 0
319 for _, t := range types {
320 overloads[i] = template(t.typeName, t.celType)
321 i++
322 }
323 return overloads
324 }