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