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