1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "sort"
7 "strconv"
8 "strings"
9 "unicode/utf16"
10)
11
12// This file is a port of the runner's tokenizer and parser:
13// src/Sdk/DTExpressions2/Expressions2/Tokens/LexicalAnalyzer.cs, Tokens/Token.cs
14// and ExpressionParser.cs. They differ from the JavaScript reference's
15// (lexer.go, parser.go) in ways users can see:
16//
17// - the tokenizer is context sensitive: each token is checked against the
18// one before it, so "a b", "1 2" or "f(1,)" fail at the second token;
19// - tokens are produced on demand and the parser stops at the first
20// unexpected token or unknown name, in order of appearance (the JavaScript
21// lexes everything first, so a later lexical error wins there);
22// - white space is Char.IsWhiteSpace (U+0085 and U+00A0 included);
23// - "Unexpected end of expression" is reported for an unfinished expression
24// where the JavaScript says "Unexpected symbol: 'EOF'";
25// - error positions are absolute indexes in the expression, not columns;
26// - the depth limit applies to the shape of the finished tree, in which
27// parentheses do not count and a flat run of && or || is one node;
28// - the "too long" and "too deep" errors carry no token.
29//
30// Parse builds the same AST as the JavaScript-style parser did.
31
32type csKind int
33
34const (
35 csStartGroup csKind = iota
36 csStartIndex
37 csStartParameters
38 csEndGroup
39 csEndIndex
40 csEndParameters
41 csSeparator
42 csDereference
43 csWildcard
44 csLogicalOperator
45 csNull
46 csBoolean
47 csNumber
48 csString
49 csPropertyName
50 csFunction
51 csNamedValue
52 csUnexpected
53)
54
55type csToken struct {
56 kind csKind
57 raw string
58 index int
59 value Value // Boolean, Number or String for literals
60}
61
62func (t *csToken) isOperator() bool {
63 switch t.kind {
64 case csStartGroup, csStartIndex, csStartParameters, csEndGroup, csEndIndex, csEndParameters, csSeparator, csDereference, csLogicalOperator:
65 return true
66 }
67 return false
68}
69
70// leftToRight reports whether the token is a left-associative operator.
71func (t *csToken) leftToRight() bool {
72 switch {
73 case t.kind == csStartGroup:
74 return false
75 case t.kind == csLogicalOperator && t.raw == "!":
76 return false
77 }
78 return t.isOperator()
79}
80
81func (t *csToken) precedence() int {
82 switch t.kind {
83 case csStartGroup:
84 return 20
85 case csStartIndex, csStartParameters, csDereference:
86 return 19
87 case csLogicalOperator:
88 switch t.raw {
89 case "!":
90 return 16
91 case ">", ">=", "<", "<=":
92 return 11
93 case "==", "!=":
94 return 10
95 case "&&":
96 return 6
97 case "||":
98 return 5
99 }
100 case csEndGroup, csEndIndex, csEndParameters, csSeparator:
101 return 1
102 }
103 return 0
104}
105
106func (t *csToken) operandCount() int {
107 switch t.kind {
108 case csStartIndex, csDereference:
109 return 2
110 case csLogicalOperator:
111 if t.raw == "!" {
112 return 1
113 }
114 return 2
115 }
116 return 0
117}
118
119// csLexer is LexicalAnalyzer.
120type csLexer struct {
121 units []uint16
122 index int
123 last *csToken
124 unclosed []*csToken // stack of "(", "[" and function "("
125}
126
127func (l *csLexer) substr(from, to int) string { return string(utf16.Decode(l.units[from:to])) }
128
129func isCSWhiteSpace(c uint16) bool { return isNetSpace(rune(c)) }
130
131func isCSBoundary(c uint16) bool {
132 switch c {
133 case '(', '[', ')', ']', ',', '.', '!', '>', '<', '=', '&', '|':
134 return true
135 }
136 return isCSWhiteSpace(c)
137}
138
139func (l *csLexer) topUnclosed() csKind {
140 if len(l.unclosed) == 0 {
141 return -1
142 }
143 return l.unclosed[len(l.unclosed)-1].kind
144}
145
146// next returns the next token, or nil at the end of the expression.
147func (l *csLexer) next() *csToken {
148 for l.index < len(l.units) && isCSWhiteSpace(l.units[l.index]) {
149 l.index++
150 }
151 if l.index >= len(l.units) {
152 return nil
153 }
154 c := l.units[l.index]
155 var tok *csToken
156 switch c {
157 case '(':
158 if l.last != nil && l.last.kind == csFunction {
159 tok = l.create(csStartParameters, "(", l.index, nil)
160 } else {
161 tok = l.create(csStartGroup, "(", l.index, nil)
162 }
163 l.index++
164 case '[':
165 tok = l.create(csStartIndex, "[", l.index, nil)
166 l.index++
167 case ')':
168 if l.topUnclosed() == csStartParameters {
169 tok = l.create(csEndParameters, ")", l.index, nil)
170 } else {
171 tok = l.create(csEndGroup, ")", l.index, nil)
172 }
173 l.index++
174 case ']':
175 tok = l.create(csEndIndex, "]", l.index, nil)
176 l.index++
177 case ',':
178 tok = l.create(csSeparator, ",", l.index, nil)
179 l.index++
180 case '*':
181 tok = l.create(csWildcard, "*", l.index, nil)
182 l.index++
183 case '\'':
184 tok = l.readString()
185 case '!', '>', '<', '=', '&', '|':
186 tok = l.readOperator()
187 default:
188 switch {
189 case c == '.':
190 if l.last == nil || l.last.kind == csSeparator || l.last.kind == csStartGroup || l.last.kind == csStartIndex ||
191 l.last.kind == csStartParameters || l.last.kind == csLogicalOperator {
192 tok = l.readNumber()
193 } else {
194 tok = l.create(csDereference, ".", l.index, nil)
195 l.index++
196 }
197 case c == '-' || c == '+' || (c >= '0' && c <= '9'):
198 tok = l.readNumber()
199 default:
200 tok = l.readKeyword()
201 }
202 }
203 l.last = tok
204 return tok
205}
206
207func (l *csLexer) readNumber() *csToken {
208 start := l.index
209 for {
210 l.index++
211 if l.index >= len(l.units) || (isCSBoundary(l.units[l.index]) && l.units[l.index] != '.') {
212 break
213 }
214 }
215 str := l.substr(start, l.index)
216 d := parseNumber(str)
217 if d != d { // NaN
218 return l.create(csUnexpected, str, start, nil)
219 }
220 return l.create(csNumber, str, start, Number(d))
221}
222
223func isLegalKeyword(s string) bool { return isLegalIdentifier(s) }
224
225func (l *csLexer) readKeyword() *csToken {
226 start := l.index
227 l.index++
228 for l.index < len(l.units) && !isCSBoundary(l.units[l.index]) {
229 l.index++
230 }
231 str := l.substr(start, l.index)
232 if !isLegalKeyword(str) {
233 return l.create(csUnexpected, str, start, nil)
234 }
235 if l.last != nil && l.last.kind == csDereference {
236 return l.create(csPropertyName, str, start, nil)
237 }
238 switch str {
239 case "null":
240 return l.create(csNull, str, start, Null{})
241 case "true":
242 return l.create(csBoolean, str, start, Boolean(true))
243 case "false":
244 return l.create(csBoolean, str, start, Boolean(false))
245 case "NaN":
246 return l.create(csNumber, str, start, Number(nan))
247 case "Infinity":
248 return l.create(csNumber, str, start, Number(posInf))
249 }
250 // Lookahead: a function is a name followed by "(", white space allowed.
251 t := l.index
252 for t < len(l.units) && isCSWhiteSpace(l.units[t]) {
253 t++
254 }
255 if t < len(l.units) && l.units[t] == '(' {
256 return l.create(csFunction, str, start, nil)
257 }
258 return l.create(csNamedValue, str, start, nil)
259}
260
261func (l *csLexer) readString() *csToken {
262 start := l.index
263 var b strings.Builder
264 closed := false
265 l.index++ // the opening quote
266 var run []uint16
267 for l.index < len(l.units) {
268 c := l.units[l.index]
269 l.index++
270 if c == '\'' {
271 if l.index >= len(l.units) || l.units[l.index] != '\'' {
272 closed = true
273 break
274 }
275 l.index++ // an escaped quote
276 }
277 run = append(run, c)
278 }
279 b.WriteString(string(utf16.Decode(run)))
280 raw := l.substr(start, l.index)
281 if closed {
282 return l.create(csString, raw, start, String(b.String()))
283 }
284 return l.create(csUnexpected, raw, start, nil)
285}
286
287func (l *csLexer) readOperator() *csToken {
288 start := l.index
289 l.index++
290 if l.index < len(l.units) {
291 l.index++
292 switch raw := l.substr(start, start+2); raw {
293 case "!=", ">=", "<=", "==", "&&", "||":
294 return l.create(csLogicalOperator, raw, start, nil)
295 }
296 l.index-- // back up
297 }
298 switch raw := l.substr(start, start+1); raw {
299 case "!", ">", "<":
300 return l.create(csLogicalOperator, raw, start, nil)
301 }
302 for l.index < len(l.units) && !isCSBoundary(l.units[l.index]) {
303 l.index++
304 }
305 return l.create(csUnexpected, l.substr(start, l.index), start, nil)
306}
307
308// lastIs reports whether the previous token is one of kinds; a nil kind list
309// entry (csUnexpected here) stands for "no previous token".
310func (l *csLexer) lastIs(kinds ...csKind) bool {
311 if l.last == nil {
312 for _, k := range kinds {
313 if k == -1 {
314 return true
315 }
316 }
317 return false
318 }
319 for _, k := range kinds {
320 if k == l.last.kind {
321 return true
322 }
323 }
324 return false
325}
326
327const csFirst csKind = -1 // "is the first token"
328
329// create builds a token after checking that it may follow the previous one
330// and that brackets are balanced; an illegal one becomes csUnexpected.
331func (l *csLexer) create(kind csKind, raw string, index int, v Value) *csToken {
332 var legal bool
333 switch kind {
334 case csStartGroup:
335 legal = l.lastIs(csFirst, csSeparator, csStartGroup, csStartParameters, csStartIndex, csLogicalOperator)
336 case csStartIndex:
337 legal = l.lastIs(csEndGroup, csEndParameters, csEndIndex, csWildcard, csPropertyName, csNamedValue)
338 case csStartParameters:
339 legal = l.lastIs(csFunction)
340 case csEndGroup, csEndIndex:
341 legal = l.lastIs(csEndGroup, csEndParameters, csEndIndex, csWildcard, csNull, csBoolean, csNumber, csString, csPropertyName, csNamedValue)
342 case csEndParameters:
343 legal = l.lastIs(csStartParameters, csEndGroup, csEndParameters, csEndIndex, csWildcard, csNull, csBoolean, csNumber, csString, csPropertyName, csNamedValue)
344 case csSeparator:
345 legal = l.lastIs(csEndGroup, csEndParameters, csEndIndex, csWildcard, csNull, csBoolean, csNumber, csString, csPropertyName, csNamedValue)
346 case csDereference:
347 legal = l.lastIs(csEndGroup, csEndParameters, csEndIndex, csWildcard, csPropertyName, csNamedValue)
348 case csWildcard:
349 legal = l.lastIs(csStartIndex, csDereference)
350 case csLogicalOperator:
351 if raw == "!" {
352 legal = l.lastIs(csFirst, csSeparator, csStartGroup, csStartParameters, csStartIndex, csLogicalOperator)
353 } else {
354 legal = l.lastIs(csEndGroup, csEndParameters, csEndIndex, csWildcard, csNull, csBoolean, csNumber, csString, csPropertyName, csNamedValue)
355 }
356 case csNull, csBoolean, csNumber, csString, csFunction, csNamedValue:
357 legal = l.lastIs(csFirst, csSeparator, csStartIndex, csStartGroup, csStartParameters, csLogicalOperator)
358 case csPropertyName:
359 legal = l.lastIs(csDereference)
360 }
361 if !legal {
362 return &csToken{kind: csUnexpected, raw: raw, index: index}
363 }
364 tok := &csToken{kind: kind, raw: raw, index: index, value: v}
365 switch kind {
366 case csStartGroup, csStartIndex, csStartParameters:
367 l.unclosed = append(l.unclosed, tok)
368 case csEndGroup:
369 if l.topUnclosed() != csStartGroup {
370 return &csToken{kind: csUnexpected, raw: raw, index: index}
371 }
372 l.unclosed = l.unclosed[:len(l.unclosed)-1]
373 case csEndIndex:
374 if l.topUnclosed() != csStartIndex {
375 return &csToken{kind: csUnexpected, raw: raw, index: index}
376 }
377 l.unclosed = l.unclosed[:len(l.unclosed)-1]
378 case csEndParameters:
379 if l.topUnclosed() != csStartParameters {
380 return &csToken{kind: csUnexpected, raw: raw, index: index}
381 }
382 l.unclosed = l.unclosed[:len(l.unclosed)-1]
383 case csSeparator:
384 if l.topUnclosed() != csStartParameters {
385 return &csToken{kind: csUnexpected, raw: raw, index: index}
386 }
387 }
388 return tok
389}
390
391// csParser is ExpressionParser.CreateTree: a shunting-yard parser.
392type csParser struct {
393 expression string
394 units []uint16
395 lex *csLexer
396 contexts map[string]bool
397 funcs map[string]FuncInfo
398 operands []Node
399 operators []*csToken
400 last *csToken // the previous token
401 cur *csToken
402 lineStarts []int // offsets of the first unit of each line, see position
403}
404
405// fail builds the ParseException of the runner: with a token, the message names
406// it and its absolute position; without, only the description.
407func (p *csParser) fail(t ErrorType, tok *csToken) *Error {
408 if tok == nil {
409 return &Error{Type: t, Message: t.description()}
410 }
411 return &Error{
412 Type: t,
413 Message: t.description() + ": '" + tok.raw + "'. Located at position " + strconv.Itoa(tok.index+1) + " within expression: " + p.expression,
414 Pos: p.position(tok.index),
415 Token: tok.raw,
416 }
417}
418
419// position converts an absolute index into the line and column of the
420// JavaScript-style Position (line breaks are U+000A). The offsets of the line
421// starts are computed once, on first use, so that building the position of
422// every token stays linear in the length of the expression.
423func (p *csParser) position(index int) Position {
424 if p.lineStarts == nil {
425 p.lineStarts = []int{0}
426 for i, u := range p.units {
427 if u == '\n' {
428 p.lineStarts = append(p.lineStarts, i+1)
429 }
430 }
431 }
432 // The line is the last start that is <= index.
433 line := sort.Search(len(p.lineStarts), func(i int) bool { return p.lineStarts[i] > index }) - 1
434 return Position{Line: line, Column: index - p.lineStarts[line]}
435}
436
437func (p *csParser) token(t *csToken, typ TokenType) Token {
438 end := t.index + len(utf16.Encode([]rune(t.raw)))
439 return Token{Type: typ, Lexeme: t.raw, Range: Range{Start: p.position(t.index), End: p.position(end)}, Value: t.value}
440}
441
442func (p *csParser) wellKnownOrExtension(name string) (FuncInfo, bool) {
443 k := foldKey(name)
444 if f, ok := builtinFuncs[k]; ok {
445 return f, true
446 }
447 f, ok := p.funcs[k]
448 return f, ok
449}
450
451// parseRunner parses expression the way the runner does.
452func parseRunner(expression string, contexts []string, funcs []FuncInfo) (Node, error) {
453 p := &csParser{contexts: make(map[string]bool, len(contexts)), funcs: make(map[string]FuncInfo, len(funcs))}
454 if exceedsUTF16Len(expression, MaxExpressionLength) {
455 return nil, p.fail(ErrorExceededMaxLength, nil)
456 }
457 p.units = utf16.Encode([]rune(expression))
458 p.expression = string(utf16.Decode(p.units))
459 for _, c := range contexts {
460 p.contexts[foldKey(c)] = true
461 }
462 for _, f := range funcs {
463 p.funcs[foldKey(f.Name)] = f
464 }
465 p.lex = &csLexer{units: p.units}
466 return p.createTree()
467}
468
469func (p *csParser) createTree() (Node, error) {
470 for {
471 tok := p.lex.next()
472 if tok == nil {
473 break
474 }
475 p.cur = tok
476 switch {
477 case tok.kind == csUnexpected:
478 return nil, p.fail(ErrorUnexpectedSymbol, tok)
479 case tok.isOperator():
480 if err := p.pushOperator(tok); err != nil {
481 return nil, err
482 }
483 default:
484 if err := p.pushOperand(tok); err != nil {
485 return nil, err
486 }
487 }
488 p.last = tok
489 }
490 if p.last == nil {
491 return nil, nil
492 }
493 if len(p.operators) > 0 {
494 unexpected := false
495 switch p.last.kind {
496 case csEndGroup, csEndIndex, csEndParameters:
497 case csFunction:
498 unexpected = true
499 default:
500 unexpected = p.last.isOperator()
501 }
502 if unexpected || len(p.lex.unclosed) > 0 {
503 return nil, p.fail(ErrorUnexpectedEndOfExpression, p.last)
504 }
505 }
506 for len(p.operators) > 0 {
507 if err := p.flushTop(); err != nil {
508 return nil, err
509 }
510 }
511 if len(p.operands) != 1 {
512 return nil, p.fail(ErrorUnexpectedSymbol, p.last)
513 }
514 root := p.operands[0]
515 if exceedsDepth(root, 1) {
516 return nil, p.fail(ErrorExceededMaxDepth, nil)
517 }
518 return root, nil
519}
520
521func (p *csParser) pushOperand(tok *csToken) error {
522 var n Node
523 switch tok.kind {
524 case csFunction:
525 if _, ok := p.wellKnownOrExtension(tok.raw); !ok {
526 return p.fail(ErrorUnrecognizedFunction, tok)
527 }
528 n = &FunctionCall{Name: p.token(tok, TokenIdentifier)}
529 case csNamedValue:
530 if !p.contexts[foldKey(tok.raw)] {
531 return p.fail(ErrorUnrecognizedContext, tok)
532 }
533 n = &ContextAccess{Name: p.token(tok, TokenIdentifier)}
534 case csNull:
535 n = &Literal{Value: Null{}, Token: p.token(tok, TokenNull)}
536 case csBoolean:
537 typ := TokenFalse
538 if tok.value == Boolean(true) {
539 typ = TokenTrue
540 }
541 n = &Literal{Value: tok.value, Token: p.token(tok, typ)}
542 case csNumber:
543 n = &Literal{Value: tok.value, Token: p.token(tok, TokenNumber)}
544 case csString:
545 n = &Literal{Value: tok.value, Token: p.token(tok, TokenString)}
546 case csPropertyName:
547 n = &Literal{Value: String(tok.raw), Token: p.token(tok, TokenIdentifier)}
548 case csWildcard:
549 n = &Star{}
550 default:
551 return p.fail(ErrorUnexpectedSymbol, tok)
552 }
553 p.operands = append(p.operands, n)
554 return nil
555}
556
557func (p *csParser) pushOperator(tok *csToken) error {
558 if tok.leftToRight() {
559 prec := tok.precedence()
560 for len(p.operators) > 0 {
561 top := p.operators[len(p.operators)-1]
562 if prec <= top.precedence() && top.kind != csStartGroup && top.kind != csStartIndex &&
563 top.kind != csStartParameters && top.kind != csSeparator {
564 if err := p.flushTop(); err != nil {
565 return err
566 }
567 continue
568 }
569 break
570 }
571 }
572 p.operators = append(p.operators, tok)
573 switch tok.kind {
574 case csEndGroup, csEndIndex, csEndParameters:
575 return p.flushTop()
576 }
577 return nil
578}
579
580func (p *csParser) popOperator(want csKind) (*csToken, error) {
581 if len(p.operators) == 0 || p.operators[len(p.operators)-1].kind != want {
582 return nil, p.fail(ErrorUnexpectedSymbol, p.cur)
583 }
584 t := p.operators[len(p.operators)-1]
585 p.operators = p.operators[:len(p.operators)-1]
586 return t, nil
587}
588
589// popOperands pops n operands, returned in their written order.
590func (p *csParser) popOperands(n int) ([]Node, error) {
591 if len(p.operands) < n {
592 return nil, p.fail(ErrorUnexpectedSymbol, p.cur)
593 }
594 out := append([]Node(nil), p.operands[len(p.operands)-n:]...)
595 p.operands = p.operands[:len(p.operands)-n]
596 return out, nil
597}
598
599func (p *csParser) flushTop() error {
600 top := p.operators[len(p.operators)-1]
601 switch top.kind {
602 case csEndIndex:
603 if _, err := p.popOperator(csEndIndex); err != nil {
604 return err
605 }
606 op, err := p.popOperator(csStartIndex)
607 if err != nil {
608 return err
609 }
610 args, err := p.popOperands(op.operandCount())
611 if err != nil {
612 return err
613 }
614 p.operands = append(p.operands, &IndexAccess{Expr: args[0], Index: args[1]})
615 return nil
616 case csEndGroup:
617 if _, err := p.popOperator(csEndGroup); err != nil {
618 return err
619 }
620 if _, err := p.popOperator(csStartGroup); err != nil {
621 return err
622 }
623 if len(p.operands) == 0 {
624 return p.fail(ErrorUnexpectedSymbol, p.cur)
625 }
626 g := &Grouping{Group: p.operands[len(p.operands)-1]}
627 p.operands[len(p.operands)-1] = g
628 return nil
629 case csEndParameters:
630 return p.flushEndParameters()
631 }
632 op, _ := p.popOperator(top.kind)
633 args, err := p.popOperands(op.operandCount())
634 if err != nil {
635 return err
636 }
637 switch {
638 case op.kind == csStartIndex || op.kind == csDereference:
639 p.operands = append(p.operands, &IndexAccess{Expr: args[0], Index: args[1]})
640 case op.kind == csLogicalOperator && op.raw == "!":
641 p.operands = append(p.operands, &Unary{Operator: p.token(op, TokenBang), Expr: args[0]})
642 case op.kind == csLogicalOperator && (op.raw == "&&" || op.raw == "||"):
643 typ := TokenAnd
644 if op.raw == "||" {
645 typ = TokenOr
646 }
647 l := &Logical{Operator: p.token(op, typ)}
648 for i, a := range args {
649 // A nested chain of the same operator is merged, as the runner does.
650 // The left operand of "a || b || c" is the chain built so far: its
651 // slice is extended instead of copied, which keeps a long chain
652 // linear.
653 if nested, ok := a.(*Logical); ok && nested.Operator.Type == typ {
654 if i == 0 {
655 l.Operator = nested.Operator
656 l.Args = nested.Args
657 } else {
658 l.Args = append(l.Args, nested.Args...)
659 }
660 } else {
661 l.Args = append(l.Args, a)
662 }
663 }
664 p.operands = append(p.operands, l)
665 case op.kind == csLogicalOperator:
666 var typ TokenType
667 switch op.raw {
668 case "!=":
669 typ = TokenBangEqual
670 case "==":
671 typ = TokenEqualEqual
672 case ">":
673 typ = TokenGreater
674 case ">=":
675 typ = TokenGreaterEqual
676 case "<":
677 typ = TokenLess
678 default:
679 typ = TokenLessEqual
680 }
681 p.operands = append(p.operands, &Binary{Left: args[0], Operator: p.token(op, typ), Right: args[1]})
682 default:
683 return p.fail(ErrorUnexpectedSymbol, op)
684 }
685 return nil
686}
687
688func (p *csParser) flushEndParameters() error {
689 end, err := p.popOperator(csEndParameters)
690 if err != nil {
691 return err
692 }
693 if end != p.cur || p.last == nil {
694 return p.fail(ErrorUnexpectedSymbol, p.cur)
695 }
696 count := 0
697 if p.last.kind != csStartParameters {
698 count = 1
699 for len(p.operators) > 0 && p.operators[len(p.operators)-1].kind == csSeparator {
700 count++
701 p.operators = p.operators[:len(p.operators)-1]
702 }
703 }
704 args, err := p.popOperands(count)
705 if err != nil {
706 return err
707 }
708 if len(p.operands) == 0 {
709 return p.fail(ErrorUnexpectedSymbol, p.cur)
710 }
711 call, ok := p.operands[len(p.operands)-1].(*FunctionCall)
712 if !ok {
713 return p.fail(ErrorUnexpectedSymbol, p.cur)
714 }
715 call.Args = args
716 open, err := p.popOperator(csStartParameters)
717 if err != nil {
718 return err
719 }
720 info, _ := p.wellKnownOrExtension(call.Name.Lexeme)
721 switch {
722 case len(args) < info.MinArgs:
723 return p.fail(ErrorTooFewParameters, open)
724 case info.MaxArgs >= 0 && len(args) > info.MaxArgs:
725 return p.fail(ErrorTooManyParameters, open)
726 case strings.EqualFold(info.Name, "case") && len(args)%2 == 0:
727 return p.fail(ErrorEvenParameters, open)
728 }
729 return nil
730}
731
732// exceedsDepth reports whether the tree is deeper than MaxParserDepth, counted
733// as the runner does (CheckMaxDepth): the root is at depth 1, the operands of
734// an operator, the arguments of a call and the two parts of an index access
735// are one deeper, parentheses add nothing, and a run of && or || is one node,
736// also when parenthesized.
737func exceedsDepth(n Node, depth int) bool {
738 for {
739 g, ok := n.(*Grouping)
740 if !ok {
741 break
742 }
743 n = g.Group
744 }
745 if depth > MaxParserDepth {
746 return true
747 }
748 switch n := n.(type) {
749 case *Unary:
750 return exceedsDepth(n.Expr, depth+1)
751 case *Binary:
752 return exceedsDepth(n.Left, depth+1) || exceedsDepth(n.Right, depth+1)
753 case *Logical:
754 for _, a := range flatOperands(n, nil) {
755 if exceedsDepth(a, depth+1) {
756 return true
757 }
758 }
759 case *FunctionCall:
760 for _, a := range n.Args {
761 if exceedsDepth(a, depth+1) {
762 return true
763 }
764 }
765 case *IndexAccess:
766 return exceedsDepth(n.Expr, depth+1) || exceedsDepth(n.Index, depth+1)
767 }
768 return false
769}
770
771// flatOperands lists the operands of a && or || chain with nested chains of
772// the same operator (parenthesized or not) merged into it.
773func flatOperands(l *Logical, out []Node) []Node {
774 for _, a := range l.Args {
775 inner := a
776 for {
777 g, ok := inner.(*Grouping)
778 if !ok {
779 break
780 }
781 inner = g.Group
782 }
783 if nested, ok := inner.(*Logical); ok && nested.Operator.Type == l.Operator.Type {
784 out = flatOperands(nested, out)
785 } else {
786 out = append(out, a)
787 }
788 }
789 return out
790}