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