1 // Copyright 2019 The Prometheus Authors 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 %{ 15 package parser 16 17 import ( 18 "math" 19 "sort" 20 "strconv" 21 "time" 22 23 "github.com/prometheus/prometheus/pkg/labels" 24 "github.com/prometheus/prometheus/pkg/value" 25 ) 26 %} 27 28 %union { 29 node Node 30 item Item 31 matchers []*labels.Matcher 32 matcher *labels.Matcher 33 label labels.Label 34 labels labels.Labels 35 strings []string 36 series []SequenceValue 37 uint uint64 38 float float64 39 duration time.Duration 40 } 41 42 43 %token <item> 44 EQL 45 BLANK 46 COLON 47 COMMA 48 COMMENT 49 DURATION 50 EOF 51 ERROR 52 IDENTIFIER 53 LEFT_BRACE 54 LEFT_BRACKET 55 LEFT_PAREN 56 METRIC_IDENTIFIER 57 NUMBER 58 RIGHT_BRACE 59 RIGHT_BRACKET 60 RIGHT_PAREN 61 SEMICOLON 62 SPACE 63 STRING 64 TIMES 65 66 // Operators. 67 %token operatorsStart 68 %token <item> 69 ADD 70 DIV 71 EQLC 72 EQL_REGEX 73 GTE 74 GTR 75 LAND 76 LOR 77 LSS 78 LTE 79 LUNLESS 80 MOD 81 MUL 82 NEQ 83 NEQ_REGEX 84 POW 85 SUB 86 AT 87 ATAN2 88 %token operatorsEnd 89 90 // Aggregators. 91 %token aggregatorsStart 92 %token <item> 93 AVG 94 BOTTOMK 95 COUNT 96 COUNT_VALUES 97 GROUP 98 MAX 99 MIN 100 QUANTILE 101 STDDEV 102 STDVAR 103 SUM 104 TOPK 105 %token aggregatorsEnd 106 107 // Keywords. 108 %token keywordsStart 109 %token <item> 110 BOOL 111 BY 112 GROUP_LEFT 113 GROUP_RIGHT 114 IGNORING 115 OFFSET 116 ON 117 WITHOUT 118 %token keywordsEnd 119 120 // Preprocessors. 121 %token preprocessorStart 122 %token <item> 123 START 124 END 125 %token preprocessorEnd 126 127 128 // Start symbols for the generated parser. 129 %token startSymbolsStart 130 %token 131 START_METRIC 132 START_SERIES_DESCRIPTION 133 START_EXPRESSION 134 START_METRIC_SELECTOR 135 %token startSymbolsEnd 136 137 138 // Type definitions for grammar rules. 139 %type <matchers> label_match_list 140 %type <matcher> label_matcher 141 142 %type <item> aggregate_op grouping_label match_op maybe_label metric_identifier unary_op at_modifier_preprocessors 143 144 %type <labels> label_set label_set_list metric 145 %type <label> label_set_item 146 %type <strings> grouping_label_list grouping_labels maybe_grouping_labels 147 %type <series> series_item series_values 148 %type <uint> uint 149 %type <float> number series_value signed_number signed_or_unsigned_number 150 %type <node> step_invariant_expr aggregate_expr aggregate_modifier bin_modifier binary_expr bool_modifier expr function_call function_call_args function_call_body group_modifiers label_matchers matrix_selector number_literal offset_expr on_or_ignoring paren_expr string_literal subquery_expr unary_expr vector_selector 151 %type <duration> duration maybe_duration 152 153 %start start 154 155 // Operators are listed with increasing precedence. 156 %left LOR 157 %left LAND LUNLESS 158 %left EQLC GTE GTR LSS LTE NEQ 159 %left ADD SUB 160 %left MUL DIV MOD ATAN2 161 %right POW 162 163 // Offset modifiers do not have associativity. 164 %nonassoc OFFSET 165 166 // This ensures that it is always attempted to parse range or subquery selectors when a left 167 // bracket is encountered. 168 %right LEFT_BRACKET 169 170 %% 171 172 start : 173 START_METRIC metric 174 { yylex.(*parser).generatedParserResult = $2 } 175 | START_SERIES_DESCRIPTION series_description 176 | START_EXPRESSION /* empty */ EOF 177 { yylex.(*parser).addParseErrf(PositionRange{}, "no expression found in input")} 178 | START_EXPRESSION expr 179 { yylex.(*parser).generatedParserResult = $2 } 180 | START_METRIC_SELECTOR vector_selector 181 { yylex.(*parser).generatedParserResult = $2 } 182 | start EOF 183 | error /* If none of the more detailed error messages are triggered, we fall back to this. */ 184 { yylex.(*parser).unexpected("","") } 185 ; 186 187 expr : 188 aggregate_expr 189 | binary_expr 190 | function_call 191 | matrix_selector 192 | number_literal 193 | offset_expr 194 | paren_expr 195 | string_literal 196 | subquery_expr 197 | unary_expr 198 | vector_selector 199 | step_invariant_expr 200 ; 201 202 /* 203 * Aggregations. 204 */ 205 206 aggregate_expr : aggregate_op aggregate_modifier function_call_body 207 { $$ = yylex.(*parser).newAggregateExpr($1, $2, $3) } 208 | aggregate_op function_call_body aggregate_modifier 209 { $$ = yylex.(*parser).newAggregateExpr($1, $3, $2) } 210 | aggregate_op function_call_body 211 { $$ = yylex.(*parser).newAggregateExpr($1, &AggregateExpr{}, $2) } 212 | aggregate_op error 213 { 214 yylex.(*parser).unexpected("aggregation",""); 215 $$ = yylex.(*parser).newAggregateExpr($1, &AggregateExpr{}, Expressions{}) 216 } 217 ; 218 219 aggregate_modifier: 220 BY grouping_labels 221 { 222 $$ = &AggregateExpr{ 223 Grouping: $2, 224 } 225 } 226 | WITHOUT grouping_labels 227 { 228 $$ = &AggregateExpr{ 229 Grouping: $2, 230 Without: true, 231 } 232 } 233 ; 234 235 /* 236 * Binary expressions. 237 */ 238 239 // Operator precedence only works if each of those is listed separately. 240 binary_expr : expr ADD bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 241 | expr ATAN2 bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 242 | expr DIV bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 243 | expr EQLC bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 244 | expr GTE bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 245 | expr GTR bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 246 | expr LAND bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 247 | expr LOR bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 248 | expr LSS bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 249 | expr LTE bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 250 | expr LUNLESS bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 251 | expr MOD bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 252 | expr MUL bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 253 | expr NEQ bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 254 | expr POW bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 255 | expr SUB bin_modifier expr { $$ = yylex.(*parser).newBinaryExpression($1, $2, $3, $4) } 256 ; 257 258 // Using left recursion for the modifier rules, helps to keep the parser stack small and 259 // reduces allocations 260 bin_modifier : group_modifiers; 261 262 bool_modifier : /* empty */ 263 { $$ = &BinaryExpr{ 264 VectorMatching: &VectorMatching{Card: CardOneToOne}, 265 } 266 } 267 | BOOL 268 { $$ = &BinaryExpr{ 269 VectorMatching: &VectorMatching{Card: CardOneToOne}, 270 ReturnBool: true, 271 } 272 } 273 ; 274 275 on_or_ignoring : bool_modifier IGNORING grouping_labels 276 { 277 $$ = $1 278 $$.(*BinaryExpr).VectorMatching.MatchingLabels = $3 279 } 280 | bool_modifier ON grouping_labels 281 { 282 $$ = $1 283 $$.(*BinaryExpr).VectorMatching.MatchingLabels = $3 284 $$.(*BinaryExpr).VectorMatching.On = true 285 } 286 ; 287 288 group_modifiers: bool_modifier /* empty */ 289 | on_or_ignoring /* empty */ 290 | on_or_ignoring GROUP_LEFT maybe_grouping_labels 291 { 292 $$ = $1 293 $$.(*BinaryExpr).VectorMatching.Card = CardManyToOne 294 $$.(*BinaryExpr).VectorMatching.Include = $3 295 } 296 | on_or_ignoring GROUP_RIGHT maybe_grouping_labels 297 { 298 $$ = $1 299 $$.(*BinaryExpr).VectorMatching.Card = CardOneToMany 300 $$.(*BinaryExpr).VectorMatching.Include = $3 301 } 302 ; 303 304 305 grouping_labels : LEFT_PAREN grouping_label_list RIGHT_PAREN 306 { $$ = $2 } 307 | LEFT_PAREN grouping_label_list COMMA RIGHT_PAREN 308 { $$ = $2 } 309 | LEFT_PAREN RIGHT_PAREN 310 { $$ = []string{} } 311 | error 312 { yylex.(*parser).unexpected("grouping opts", "\"(\""); $$ = nil } 313 ; 314 315 316 grouping_label_list: 317 grouping_label_list COMMA grouping_label 318 { $$ = append($1, $3.Val) } 319 | grouping_label 320 { $$ = []string{$1.Val} } 321 | grouping_label_list error 322 { yylex.(*parser).unexpected("grouping opts", "\",\" or \")\""); $$ = $1 } 323 ; 324 325 grouping_label : maybe_label 326 { 327 if !isLabel($1.Val) { 328 yylex.(*parser).unexpected("grouping opts", "label") 329 } 330 $$ = $1 331 } 332 | error 333 { yylex.(*parser).unexpected("grouping opts", "label"); $$ = Item{} } 334 ; 335 336 /* 337 * Function calls. 338 */ 339 340 function_call : IDENTIFIER function_call_body 341 { 342 fn, exist := getFunction($1.Val) 343 if !exist{ 344 yylex.(*parser).addParseErrf($1.PositionRange(),"unknown function with name %q", $1.Val) 345 } 346 $$ = &Call{ 347 Func: fn, 348 Args: $2.(Expressions), 349 PosRange: PositionRange{ 350 Start: $1.Pos, 351 End: yylex.(*parser).lastClosing, 352 }, 353 } 354 } 355 ; 356 357 function_call_body: LEFT_PAREN function_call_args RIGHT_PAREN 358 { $$ = $2 } 359 | LEFT_PAREN RIGHT_PAREN 360 {$$ = Expressions{}} 361 ; 362 363 function_call_args: function_call_args COMMA expr 364 { $$ = append($1.(Expressions), $3.(Expr)) } 365 | expr 366 { $$ = Expressions{$1.(Expr)} } 367 | function_call_args COMMA 368 { 369 yylex.(*parser).addParseErrf($2.PositionRange(), "trailing commas not allowed in function call args") 370 $$ = $1 371 } 372 ; 373 374 /* 375 * Expressions inside parentheses. 376 */ 377 378 paren_expr : LEFT_PAREN expr RIGHT_PAREN 379 { $$ = &ParenExpr{Expr: $2.(Expr), PosRange: mergeRanges(&$1, &$3)} } 380 ; 381 382 /* 383 * Offset modifiers. 384 */ 385 386 offset_expr: expr OFFSET duration 387 { 388 yylex.(*parser).addOffset($1, $3) 389 $$ = $1 390 } 391 | expr OFFSET SUB duration 392 { 393 yylex.(*parser).addOffset($1, -$4) 394 $$ = $1 395 } 396 | expr OFFSET error 397 { yylex.(*parser).unexpected("offset", "duration"); $$ = $1 } 398 ; 399 /* 400 * @ modifiers. 401 */ 402 403 step_invariant_expr: expr AT signed_or_unsigned_number 404 { 405 yylex.(*parser).setTimestamp($1, $3) 406 $$ = $1 407 } 408 | expr AT at_modifier_preprocessors LEFT_PAREN RIGHT_PAREN 409 { 410 yylex.(*parser).setAtModifierPreprocessor($1, $3) 411 $$ = $1 412 } 413 | expr AT error 414 { yylex.(*parser).unexpected("@", "timestamp"); $$ = $1 } 415 ; 416 417 at_modifier_preprocessors: START | END; 418 419 /* 420 * Subquery and range selectors. 421 */ 422 423 matrix_selector : expr LEFT_BRACKET duration RIGHT_BRACKET 424 { 425 var errMsg string 426 vs, ok := $1.(*VectorSelector) 427 if !ok{ 428 errMsg = "ranges only allowed for vector selectors" 429 } else if vs.OriginalOffset != 0{ 430 errMsg = "no offset modifiers allowed before range" 431 } else if vs.Timestamp != nil { 432 errMsg = "no @ modifiers allowed before range" 433 } 434 435 if errMsg != ""{ 436 errRange := mergeRanges(&$2, &$4) 437 yylex.(*parser).addParseErrf(errRange, errMsg) 438 } 439 440 $$ = &MatrixSelector{ 441 VectorSelector: $1.(Expr), 442 Range: $3, 443 EndPos: yylex.(*parser).lastClosing, 444 } 445 } 446 ; 447 448 subquery_expr : expr LEFT_BRACKET duration COLON maybe_duration RIGHT_BRACKET 449 { 450 $$ = &SubqueryExpr{ 451 Expr: $1.(Expr), 452 Range: $3, 453 Step: $5, 454 455 EndPos: $6.Pos + 1, 456 } 457 } 458 | expr LEFT_BRACKET duration COLON duration error 459 { yylex.(*parser).unexpected("subquery selector", "\"]\""); $$ = $1 } 460 | expr LEFT_BRACKET duration COLON error 461 { yylex.(*parser).unexpected("subquery selector", "duration or \"]\""); $$ = $1 } 462 | expr LEFT_BRACKET duration error 463 { yylex.(*parser).unexpected("subquery or range", "\":\" or \"]\""); $$ = $1 } 464 | expr LEFT_BRACKET error 465 { yylex.(*parser).unexpected("subquery selector", "duration"); $$ = $1 } 466 ; 467 468 /* 469 * Unary expressions. 470 */ 471 472 unary_expr : 473 /* gives the rule the same precedence as MUL. This aligns with mathematical conventions */ 474 unary_op expr %prec MUL 475 { 476 if nl, ok := $2.(*NumberLiteral); ok { 477 if $1.Typ == SUB { 478 nl.Val *= -1 479 } 480 nl.PosRange.Start = $1.Pos 481 $$ = nl 482 } else { 483 $$ = &UnaryExpr{Op: $1.Typ, Expr: $2.(Expr), StartPos: $1.Pos} 484 } 485 } 486 ; 487 488 /* 489 * Vector selectors. 490 */ 491 492 vector_selector: metric_identifier label_matchers 493 { 494 vs := $2.(*VectorSelector) 495 vs.PosRange = mergeRanges(&$1, vs) 496 vs.Name = $1.Val 497 yylex.(*parser).assembleVectorSelector(vs) 498 $$ = vs 499 } 500 | metric_identifier 501 { 502 vs := &VectorSelector{ 503 Name: $1.Val, 504 LabelMatchers: []*labels.Matcher{}, 505 PosRange: $1.PositionRange(), 506 } 507 yylex.(*parser).assembleVectorSelector(vs) 508 $$ = vs 509 } 510 | label_matchers 511 { 512 vs := $1.(*VectorSelector) 513 yylex.(*parser).assembleVectorSelector(vs) 514 $$ = vs 515 } 516 ; 517 518 label_matchers : LEFT_BRACE label_match_list RIGHT_BRACE 519 { 520 $$ = &VectorSelector{ 521 LabelMatchers: $2, 522 PosRange: mergeRanges(&$1, &$3), 523 } 524 } 525 | LEFT_BRACE label_match_list COMMA RIGHT_BRACE 526 { 527 $$ = &VectorSelector{ 528 LabelMatchers: $2, 529 PosRange: mergeRanges(&$1, &$4), 530 } 531 } 532 | LEFT_BRACE RIGHT_BRACE 533 { 534 $$ = &VectorSelector{ 535 LabelMatchers: []*labels.Matcher{}, 536 PosRange: mergeRanges(&$1, &$2), 537 } 538 } 539 ; 540 541 label_match_list: label_match_list COMMA label_matcher 542 { 543 if $1 != nil{ 544 $$ = append($1, $3) 545 } else { 546 $$ = $1 547 } 548 } 549 | label_matcher 550 { $$ = []*labels.Matcher{$1}} 551 | label_match_list error 552 { yylex.(*parser).unexpected("label matching", "\",\" or \"}\""); $$ = $1 } 553 ; 554 555 label_matcher : IDENTIFIER match_op STRING 556 { $$ = yylex.(*parser).newLabelMatcher($1, $2, $3); } 557 | IDENTIFIER match_op error 558 { yylex.(*parser).unexpected("label matching", "string"); $$ = nil} 559 | IDENTIFIER error 560 { yylex.(*parser).unexpected("label matching", "label matching operator"); $$ = nil } 561 | error 562 { yylex.(*parser).unexpected("label matching", "identifier or \"}\""); $$ = nil} 563 ; 564 565 /* 566 * Metric descriptions. 567 */ 568 569 metric : metric_identifier label_set 570 { $$ = append($2, labels.Label{Name: labels.MetricName, Value: $1.Val}); sort.Sort($$) } 571 | label_set 572 {$$ = $1} 573 ; 574 575 576 metric_identifier: AVG | BOTTOMK | BY | COUNT | COUNT_VALUES | GROUP | IDENTIFIER | LAND | LOR | LUNLESS | MAX | METRIC_IDENTIFIER | MIN | OFFSET | QUANTILE | STDDEV | STDVAR | SUM | TOPK | WITHOUT | START | END; 577 578 label_set : LEFT_BRACE label_set_list RIGHT_BRACE 579 { $$ = labels.New($2...) } 580 | LEFT_BRACE label_set_list COMMA RIGHT_BRACE 581 { $$ = labels.New($2...) } 582 | LEFT_BRACE RIGHT_BRACE 583 { $$ = labels.New() } 584 | /* empty */ 585 { $$ = labels.New() } 586 ; 587 588 label_set_list : label_set_list COMMA label_set_item 589 { $$ = append($1, $3) } 590 | label_set_item 591 { $$ = []labels.Label{$1} } 592 | label_set_list error 593 { yylex.(*parser).unexpected("label set", "\",\" or \"}\"", ); $$ = $1 } 594 595 ; 596 597 label_set_item : IDENTIFIER EQL STRING 598 { $$ = labels.Label{Name: $1.Val, Value: yylex.(*parser).unquoteString($3.Val) } } 599 | IDENTIFIER EQL error 600 { yylex.(*parser).unexpected("label set", "string"); $$ = labels.Label{}} 601 | IDENTIFIER error 602 { yylex.(*parser).unexpected("label set", "\"=\""); $$ = labels.Label{}} 603 | error 604 { yylex.(*parser).unexpected("label set", "identifier or \"}\""); $$ = labels.Label{} } 605 ; 606 607 /* 608 * Series descriptions (only used by unit tests). 609 */ 610 611 series_description: metric series_values 612 { 613 yylex.(*parser).generatedParserResult = &seriesDescription{ 614 labels: $1, 615 values: $2, 616 } 617 } 618 ; 619 620 series_values : /*empty*/ 621 { $$ = []SequenceValue{} } 622 | series_values SPACE series_item 623 { $$ = append($1, $3...) } 624 | series_values SPACE 625 { $$ = $1 } 626 | error 627 { yylex.(*parser).unexpected("series values", ""); $$ = nil } 628 ; 629 630 series_item : BLANK 631 { $$ = []SequenceValue{{Omitted: true}}} 632 | BLANK TIMES uint 633 { 634 $$ = []SequenceValue{} 635 for i:=uint64(0); i < $3; i++{ 636 $$ = append($$, SequenceValue{Omitted: true}) 637 } 638 } 639 | series_value 640 { $$ = []SequenceValue{{Value: $1}}} 641 | series_value TIMES uint 642 { 643 $$ = []SequenceValue{} 644 for i:=uint64(0); i <= $3; i++{ 645 $$ = append($$, SequenceValue{Value: $1}) 646 } 647 } 648 | series_value signed_number TIMES uint 649 { 650 $$ = []SequenceValue{} 651 for i:=uint64(0); i <= $4; i++{ 652 $$ = append($$, SequenceValue{Value: $1}) 653 $1 += $2 654 } 655 } 656 ; 657 658 series_value : IDENTIFIER 659 { 660 if $1.Val != "stale" { 661 yylex.(*parser).unexpected("series values", "number or \"stale\"") 662 } 663 $$ = math.Float64frombits(value.StaleNaN) 664 } 665 | number 666 | signed_number 667 ; 668 669 670 671 672 /* 673 * Keyword lists. 674 */ 675 676 aggregate_op : AVG | BOTTOMK | COUNT | COUNT_VALUES | GROUP | MAX | MIN | QUANTILE | STDDEV | STDVAR | SUM | TOPK ; 677 678 // inside of grouping options label names can be recognized as keywords by the lexer. This is a list of keywords that could also be a label name. 679 maybe_label : AVG | BOOL | BOTTOMK | BY | COUNT | COUNT_VALUES | GROUP | GROUP_LEFT | GROUP_RIGHT | IDENTIFIER | IGNORING | LAND | LOR | LUNLESS | MAX | METRIC_IDENTIFIER | MIN | OFFSET | ON | QUANTILE | STDDEV | STDVAR | SUM | TOPK | START | END | ATAN2; 680 681 unary_op : ADD | SUB; 682 683 match_op : EQL | NEQ | EQL_REGEX | NEQ_REGEX ; 684 685 /* 686 * Literals. 687 */ 688 689 number_literal : NUMBER 690 { 691 $$ = &NumberLiteral{ 692 Val: yylex.(*parser).number($1.Val), 693 PosRange: $1.PositionRange(), 694 } 695 } 696 ; 697 698 number : NUMBER { $$ = yylex.(*parser).number($1.Val) } ; 699 700 signed_number : ADD number { $$ = $2 } 701 | SUB number { $$ = -$2 } 702 ; 703 704 signed_or_unsigned_number: number | signed_number ; 705 706 uint : NUMBER 707 { 708 var err error 709 $$, err = strconv.ParseUint($1.Val, 10, 64) 710 if err != nil { 711 yylex.(*parser).addParseErrf($1.PositionRange(), "invalid repetition in series values: %s", err) 712 } 713 } 714 ; 715 716 duration : DURATION 717 { 718 var err error 719 $$, err = parseDuration($1.Val) 720 if err != nil { 721 yylex.(*parser).addParseErr($1.PositionRange(), err) 722 } 723 } 724 ; 725 726 727 string_literal : STRING 728 { 729 $$ = &StringLiteral{ 730 Val: yylex.(*parser).unquoteString($1.Val), 731 PosRange: $1.PositionRange(), 732 } 733 } 734 ; 735 736 /* 737 * Wrappers for optional arguments. 738 */ 739 740 maybe_duration : /* empty */ 741 {$$ = 0} 742 | duration 743 ; 744 745 maybe_grouping_labels: /* empty */ { $$ = nil } 746 | grouping_labels 747 ; 748 749 %% 750