1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "math"
10 "sort"
11)
12
13// MaxResultBytes is the default budget of an evaluation: the total size, in
14// bytes, of the strings that format, join and toJSON build plus a nominal
15// cost for every element of the arrays that the * filter builds. The
16// reference implementation has no such limit; without one a few kilobytes of
17// expression can allocate gigabytes (format('{0}{0}{0}...', format(...))),
18// and arrays shared in a context can multiply under .* filters.
19const MaxResultBytes = 1 << 20
20
21// filterElementCost is what one element of a filtered array costs against the
22// budget: the size of an interface value.
23const filterElementCost = 16
24
25// maxEvalDepth bounds the recursion of the evaluator. The parser never
26// produces trees anywhere near it; it protects against hand-built ASTs.
27const maxEvalDepth = 1000
28
29// Func implements a function callable from expressions. It receives the
30// evaluation's context, which it should honour if it blocks or loops, and the
31// evaluated arguments in order, and returns the result or an error.
32// [Evaluate] wraps the error in an [*EvalError] that unwraps to it. Arity is
33// not checked at call time: declare it in a [FuncInfo] given to [Parse].
34type Func func(ctx context.Context, args []Value) (Value, error)
35
36// EvalContext is the environment an expression is evaluated in.
37type EvalContext struct {
38 // Contexts maps context names ("github", "env", "matrix"...) to their
39 // values. Names are matched case-insensitively; when several keys differ
40 // only by case, the first in sorted order wins. A name that is absent
41 // evaluates to null.
42 Contexts map[string]Value
43 // Funcs implements the extra functions declared to [Parse], such as
44 // hashFiles, success, always, cancelled and failure. Names are matched
45 // case-insensitively. The built-in functions cannot be
46 // replaced: as in the runner, they win over a function of the same name.
47 Funcs map[string]Func
48 // MaxResultBytes is the output budget of the evaluation, see
49 // [MaxResultBytes]. Zero means the default; a negative value removes the
50 // limit. The budget is shared by the whole evaluation, not per call.
51 MaxResultBytes int
52}
53
54// Evaluate computes the value of a parsed expression.
55//
56// Evaluation stops with an error that wraps ctx.Err() when ctx is done, and
57// with an [*EvalError] when the output budget is exceeded. Values of the
58// context are never modified, and results may share them with the context:
59// treat the result as read-only. The error is an [*EvalError].
60func Evaluate(ctx context.Context, node Node, ec EvalContext) (Value, error) {
61 if ctx == nil {
62 ctx = context.Background()
63 }
64 if node == nil {
65 return nil, &EvalError{Message: "cannot evaluate an empty expression"}
66 }
67 if err := ctx.Err(); err != nil {
68 return nil, cancelError(err)
69 }
70 ev := &evaluator{
71 ctx: ctx,
72 contexts: make(map[string]Value, len(ec.Contexts)),
73 funcs: make(map[string]Func, len(ec.Funcs)),
74 limit: ec.MaxResultBytes,
75 }
76 if ev.limit == 0 {
77 ev.limit = MaxResultBytes
78 }
79 names := make([]string, 0, len(ec.Contexts))
80 for k := range ec.Contexts {
81 names = append(names, k)
82 }
83 sort.Strings(names)
84 for _, k := range names {
85 if _, dup := ev.contexts[foldKey(k)]; !dup {
86 ev.contexts[foldKey(k)] = ec.Contexts[k]
87 }
88 }
89 names = names[:0]
90 for k := range ec.Funcs {
91 names = append(names, k)
92 }
93 sort.Strings(names)
94 for _, k := range names {
95 if _, dup := ev.funcs[foldKey(k)]; !dup {
96 ev.funcs[foldKey(k)] = ec.Funcs[k]
97 }
98 }
99 v, err := ev.eval(node)
100 if err != nil {
101 return nil, err
102 }
103 return normalize(v), nil
104}
105
106func cancelError(err error) *EvalError {
107 return &EvalError{Message: "evaluation canceled: " + err.Error(), Err: err}
108}
109
110type evaluator struct {
111 ctx context.Context
112 contexts map[string]Value
113 funcs map[string]Func
114 limit int // output budget; negative: unlimited
115 used int
116 depth int
117 ticks int
118}
119
120// tick is called in loops and on every node: it checks the context once in a
121// while.
122func (e *evaluator) tick() error {
123 e.ticks++
124 if e.ticks&63 == 0 {
125 if err := e.ctx.Err(); err != nil {
126 return cancelError(err)
127 }
128 }
129 return nil
130}
131
132// charge spends n bytes of the output budget.
133func (e *evaluator) charge(n int) error {
134 if e.limit < 0 {
135 return nil
136 }
137 if n > e.limit-e.used { // written to be overflow-proof
138 return e.budgetError()
139 }
140 e.used += n
141 return nil
142}
143
144func (e *evaluator) budgetError() *EvalError {
145 return &EvalError{Message: fmt.Sprintf("expression output exceeds the limit of %d bytes", e.limit)}
146}
147
148func (e *evaluator) eval(n Node) (Value, error) {
149 if err := e.tick(); err != nil {
150 return nil, err
151 }
152 e.depth++
153 defer func() { e.depth-- }()
154 if e.depth > maxEvalDepth {
155 return nil, &EvalError{Message: fmt.Sprintf("expression tree deeper than %d levels", maxEvalDepth)}
156 }
157 switch n := n.(type) {
158 case *Literal:
159 return normalize(n.Value), nil
160 case *Unary:
161 r, err := e.eval(n.Expr)
162 if err != nil {
163 return nil, err
164 }
165 return Boolean(!Truthy(r)), nil
166 case *Binary:
167 return e.binary(n)
168 case *Logical:
169 return e.logical(n)
170 case *Grouping:
171 return e.eval(n.Group)
172 case *ContextAccess:
173 if v, ok := e.contexts[foldKey(n.Name.Lexeme)]; ok {
174 return normalize(v), nil
175 }
176 return Null{}, nil
177 case *IndexAccess:
178 return e.indexAccess(n)
179 case *FunctionCall:
180 return e.call(n)
181 }
182 // *Star is only valid as an index and never evaluated on its own; the
183 // reference throws "Method not implemented." for it.
184 return nil, &EvalError{Message: "Method not implemented."}
185}
186
187func (e *evaluator) binary(b *Binary) (Value, error) {
188 // Both operands are always evaluated: comparisons do not short-circuit.
189 left, err := e.eval(b.Left)
190 if err != nil {
191 return nil, err
192 }
193 right, err := e.eval(b.Right)
194 if err != nil {
195 return nil, err
196 }
197 switch b.Operator.Type {
198 case TokenEqualEqual:
199 return Boolean(equals(left, right)), nil
200 case TokenBangEqual:
201 return Boolean(!equals(left, right)), nil
202 case TokenGreater:
203 return Boolean(greaterThan(left, right)), nil
204 case TokenGreaterEqual:
205 return Boolean(equals(left, right) || greaterThan(left, right)), nil
206 case TokenLess:
207 return Boolean(lessThan(left, right)), nil
208 case TokenLessEqual:
209 return Boolean(equals(left, right) || lessThan(left, right)), nil
210 }
211 return nil, evalErrorf("unknown binary operator: %s", b.Operator.Lexeme)
212}
213
214// logical returns the operand that decided the chain, not a boolean:
215// "a || b" is a when a is truthy, else b; "a && b" is a when a is falsy, else b.
216func (e *evaluator) logical(l *Logical) (Value, error) {
217 var result Value
218 for _, arg := range l.Args {
219 r, err := e.eval(arg)
220 if err != nil {
221 return nil, err
222 }
223 result = r
224 if (l.Operator.Type == TokenAnd && !Truthy(r)) || (l.Operator.Type == TokenOr && Truthy(r)) {
225 break
226 }
227 }
228 if result == nil {
229 return Null{}, nil // a Logical without operands, possible only in a hand-built tree
230 }
231 return result, nil
232}
233
234func (e *evaluator) call(c *FunctionCall) (Value, error) {
235 name := foldKey(c.Name.Lexeme)
236 // Built-ins win over extension functions of the same name, as in the
237 // runner (ExpressionParser.TryGetFunctionInfo looks in WellKnownFunctions
238 // first); the JavaScript reference let an extension override them here.
239 if f, ok := builtinFuncs[name]; ok {
240 // Arity is checked by the parser, and again here so that a hand-built
241 // tree cannot reach an implementation with the wrong number of
242 // arguments.
243 if t, bad := arityError(name, f, len(c.Args)); bad {
244 return nil, &EvalError{Message: t.description() + ": '" + c.Name.Lexeme + "'"}
245 }
246 // Built-ins evaluate their own arguments, lazily.
247 return builtinImpls[name](e, c)
248 }
249 ext, ok := e.funcs[name]
250 if !ok || ext == nil {
251 return nil, evalErrorf("function %s is not implemented", c.Name.Lexeme)
252 }
253 args := make([]Value, len(c.Args))
254 for i, a := range c.Args {
255 v, err := e.eval(a)
256 if err != nil {
257 return nil, err
258 }
259 args[i] = v
260 }
261 v, err := ext(e.ctx, args)
262 if err != nil {
263 var ee *EvalError
264 if errors.As(err, &ee) {
265 return nil, err
266 }
267 return nil, &EvalError{Message: err.Error(), Err: err}
268 }
269 return v, nil
270}
271
272// indexer is idxHelper of the reference: how an index value is read, as a
273// star, as a string key and as an array position.
274type indexer struct {
275 star bool
276 hasStr bool
277 str string
278 hasInt bool
279 // intv is only meaningful when hasInt; it is a float because positions
280 // beyond the int range must simply compare as out of bounds.
281 intv float64
282}
283
284func newIndexer(star bool, v Value) indexer {
285 ix := indexer{star: star}
286 if star || v == nil {
287 return ix
288 }
289 v = normalize(v)
290 if isPrimitive(v) {
291 ix.hasStr = true
292 ix.str = CoerceString(v)
293 }
294 f := toNumber(v)
295 if !math.IsNaN(f) && !math.IsInf(f, 0) && f >= 0 {
296 ix.hasInt = true
297 ix.intv = math.Floor(f)
298 }
299 return ix
300}
301
302// pos returns the position as an int when it is within [0, n).
303func (ix indexer) pos(n int) (int, bool) {
304 if !ix.hasInt || ix.intv >= float64(n) {
305 return 0, false
306 }
307 return int(ix.intv), true
308}
309
310// indexAccess evaluates a[b] as Index.cs does: the object first, then, only if
311// it is an array or a dictionary, the index, whose errors are reported as they
312// are (the JavaScript reference evaluates the index first and wraps its errors
313// in "could not evaluate index for index access").
314func (e *evaluator) indexAccess(ia *IndexAccess) (Value, error) {
315 _, isStar := ia.Index.(*Star)
316 obj, err := e.eval(ia.Expr)
317 if err != nil {
318 return nil, err
319 }
320 switch o := normalize(obj).(type) {
321 case *Array:
322 ix, err := e.indexer(ia, isStar)
323 if err != nil {
324 return nil, err
325 }
326 if o.filtered {
327 return e.filteredArrayAccess(o, ix)
328 }
329 return e.arrayAccess(o, ix)
330 case *Dictionary:
331 ix, err := e.indexer(ia, isStar)
332 if err != nil {
333 return nil, err
334 }
335 return e.objectAccess(o, ix)
336 }
337 if isStar {
338 return &Array{filtered: true}, nil
339 }
340 return Null{}, nil
341}
342
343func (e *evaluator) indexer(ia *IndexAccess, isStar bool) (indexer, error) {
344 if isStar {
345 return newIndexer(true, nil), nil
346 }
347 v, err := e.eval(ia.Index)
348 if err != nil {
349 return indexer{}, err
350 }
351 return newIndexer(false, v), nil
352}
353
354// filteredArrayAccess applies an index to each element of a filtered array
355// and collects the hits: "a.*.b" is the b of every element that has one.
356func (e *evaluator) filteredArrayAccess(fa *Array, ix indexer) (Value, error) {
357 result := &Array{filtered: true}
358 for _, item := range fa.items {
359 if err := e.tick(); err != nil {
360 return nil, err
361 }
362 switch it := normalize(item).(type) {
363 case *Dictionary:
364 if ix.star {
365 if err := e.charge(len(it.vals) * filterElementCost); err != nil {
366 return nil, err
367 }
368 result.items = append(result.items, it.vals...)
369 } else if ix.hasStr {
370 if v, ok := it.Get(ix.str); ok {
371 if err := e.charge(filterElementCost); err != nil {
372 return nil, err
373 }
374 result.items = append(result.items, v)
375 }
376 }
377 case *Array:
378 if ix.star {
379 if err := e.charge(len(it.items) * filterElementCost); err != nil {
380 return nil, err
381 }
382 result.items = append(result.items, it.items...)
383 } else if i, ok := ix.pos(len(it.items)); ok {
384 if err := e.charge(filterElementCost); err != nil {
385 return nil, err
386 }
387 result.items = append(result.items, it.items[i])
388 }
389 }
390 }
391 return result, nil
392}
393
394func (e *evaluator) arrayAccess(a *Array, ix indexer) (Value, error) {
395 if ix.star {
396 if err := e.charge(len(a.items) * filterElementCost); err != nil {
397 return nil, err
398 }
399 return &Array{items: append([]Value(nil), a.items...), filtered: true}, nil
400 }
401 if i, ok := ix.pos(len(a.items)); ok {
402 return normalize(a.items[i]), nil
403 }
404 return Null{}, nil
405}
406
407func (e *evaluator) objectAccess(d *Dictionary, ix indexer) (Value, error) {
408 if ix.star {
409 if err := e.charge(len(d.vals) * filterElementCost); err != nil {
410 return nil, err
411 }
412 return &Array{items: append([]Value(nil), d.vals...), filtered: true}, nil
413 }
414 if ix.hasStr {
415 if v, ok := d.Get(ix.str); ok {
416 return v, nil
417 }
418 }
419 return Null{}, nil
420}
421
422// coerceTypes converts two values of different kinds to a common kind the
423// way the reference does, which is like the JavaScript abstract equality
424// algorithm except that arrays and dictionaries are never converted: null
425// and booleans become numbers, and a string compared with a number becomes
426// a number.
427func coerceTypes(l, r Value) (Value, Value) {
428 l, r = normalize(l), normalize(r)
429 if l.Kind() == r.Kind() {
430 return l, r
431 }
432 switch l.Kind() {
433 case KindNumber:
434 if r.Kind() == KindString {
435 return l, Number(toNumber(r))
436 }
437 case KindString:
438 if r.Kind() == KindNumber {
439 return Number(toNumber(l)), r
440 }
441 case KindNull, KindBoolean:
442 return coerceTypes(Number(toNumber(l)), r)
443 }
444 switch r.Kind() {
445 case KindNull, KindBoolean:
446 return coerceTypes(l, Number(toNumber(r)))
447 }
448 return l, r
449}
450
451// equals is the == operator: loose equality, case-insensitive for strings
452// (see ordinal.go), false for NaN, and by identity for arrays and
453// dictionaries.
454func equals(lhs, rhs Value) bool {
455 l, r := coerceTypes(lhs, rhs)
456 if l.Kind() != r.Kind() {
457 return false
458 }
459 switch lv := l.(type) {
460 case Null:
461 return true
462 case Number:
463 return float64(lv) == float64(r.(Number)) // false when either is NaN
464 case String:
465 return ordinalEqual(string(lv), string(r.(String)))
466 case Boolean:
467 return lv == r.(Boolean)
468 case *Array:
469 return lv == r.(*Array)
470 case *Dictionary:
471 return lv == r.(*Dictionary)
472 }
473 return false
474}
475
476// compare implements < and >: it returns -1, 0 or 1, and ok false when the
477// values are not ordered (different kinds after coercion, NaN, null, arrays,
478// dictionaries).
479func compare(lhs, rhs Value) (c int, ok bool) {
480 l, r := coerceTypes(lhs, rhs)
481 if l.Kind() != r.Kind() {
482 return 0, false
483 }
484 switch lv := l.(type) {
485 case Number:
486 lf, rf := float64(lv), float64(r.(Number))
487 switch {
488 case math.IsNaN(lf) || math.IsNaN(rf):
489 return 0, false
490 case lf < rf:
491 return -1, true
492 case lf > rf:
493 return 1, true
494 }
495 return 0, true
496 case String:
497 return ordinalCompare(string(lv), string(r.(String))), true
498 case Boolean:
499 // false < true
500 switch rb := r.(Boolean); {
501 case lv == rb:
502 return 0, true
503 case !bool(lv):
504 return -1, true
505 }
506 return 1, true
507 }
508 return 0, false
509}
510
511func greaterThan(l, r Value) bool {
512 c, ok := compare(l, r)
513 return ok && c > 0
514}
515
516func lessThan(l, r Value) bool {
517 c, ok := compare(l, r)
518 return ok && c < 0
519}