12605cd382b8af4d65c3d59b7076b3d982870af5
[lttng-tools.git] / src / lib / lttng-ctl / filter / filter-parser.y
1 %{
2 /*
3 * filter-parser.y
4 *
5 * LTTng filter expression parser
6 *
7 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 *
9 * This library is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU Lesser General Public License, version 2.1 only,
11 * as published by the Free Software Foundation.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this library; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 *
22 * Grammar inspired from http://www.quut.com/c/ANSI-C-grammar-y.html
23 */
24
25 #include <stdio.h>
26 #include <unistd.h>
27 #include <string.h>
28 #include <stdlib.h>
29 #include <assert.h>
30 #include <errno.h>
31 #include <inttypes.h>
32 #include "filter-ast.h"
33 #include "filter-parser.h"
34
35 #include <common/macros.h>
36
37 #define WIDTH_u64_SCANF_IS_A_BROKEN_API "20"
38 #define WIDTH_o64_SCANF_IS_A_BROKEN_API "22"
39 #define WIDTH_x64_SCANF_IS_A_BROKEN_API "17"
40 #define WIDTH_lg_SCANF_IS_A_BROKEN_API "4096" /* Hugely optimistic approximation */
41
42 LTTNG_HIDDEN
43 int yydebug;
44 LTTNG_HIDDEN
45 int filter_parser_debug = 0;
46
47 LTTNG_HIDDEN
48 int yyparse(struct filter_parser_ctx *parser_ctx, yyscan_t scanner);
49 LTTNG_HIDDEN
50 int yylex(union YYSTYPE *yyval, yyscan_t scanner);
51 LTTNG_HIDDEN
52 int yylex_init_extra(struct filter_parser_ctx *parser_ctx, yyscan_t * ptr_yy_globals);
53 LTTNG_HIDDEN
54 int yylex_destroy(yyscan_t yyparser_ctx);
55 LTTNG_HIDDEN
56 void yyrestart(FILE * in_str, yyscan_t parser_ctx);
57
58 struct gc_string {
59 struct cds_list_head gc;
60 size_t alloclen;
61 char s[];
62 };
63
64 static const char *node_type_to_str[] = {
65 [ NODE_UNKNOWN ] = "NODE_UNKNOWN",
66 [ NODE_ROOT ] = "NODE_ROOT",
67 [ NODE_EXPRESSION ] = "NODE_EXPRESSION",
68 [ NODE_OP ] = "NODE_OP",
69 [ NODE_UNARY_OP ] = "NODE_UNARY_OP",
70 };
71
72 LTTNG_HIDDEN
73 const char *node_type(struct filter_node *node)
74 {
75 if (node->type < NR_NODE_TYPES)
76 return node_type_to_str[node->type];
77 else
78 return NULL;
79 }
80
81 static struct gc_string *gc_string_alloc(struct filter_parser_ctx *parser_ctx,
82 size_t len)
83 {
84 struct gc_string *gstr;
85 size_t alloclen;
86
87 /* TODO: could be faster with find first bit or glib Gstring */
88 /* sizeof long to account for malloc header (int or long ?) */
89 for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + len;
90 alloclen *= 2);
91
92 gstr = zmalloc(alloclen);
93 if (!gstr) {
94 goto end;
95 }
96 cds_list_add(&gstr->gc, &parser_ctx->allocated_strings);
97 gstr->alloclen = alloclen;
98 end:
99 return gstr;
100 }
101
102 /*
103 * note: never use gc_string_append on a string that has external references.
104 * gsrc will be garbage collected immediately, and gstr might be.
105 * Should only be used to append characters to a string literal or constant.
106 */
107 LTTNG_HIDDEN
108 struct gc_string *gc_string_append(struct filter_parser_ctx *parser_ctx,
109 struct gc_string *gstr,
110 struct gc_string *gsrc)
111 {
112 size_t newlen = strlen(gsrc->s) + strlen(gstr->s) + 1;
113 size_t alloclen;
114
115 /* TODO: could be faster with find first bit or glib Gstring */
116 /* sizeof long to account for malloc header (int or long ?) */
117 for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + newlen;
118 alloclen *= 2);
119
120 if (alloclen > gstr->alloclen) {
121 struct gc_string *newgstr;
122
123 newgstr = gc_string_alloc(parser_ctx, newlen);
124 strcpy(newgstr->s, gstr->s);
125 strcat(newgstr->s, gsrc->s);
126 cds_list_del(&gstr->gc);
127 free(gstr);
128 gstr = newgstr;
129 } else {
130 strcat(gstr->s, gsrc->s);
131 }
132 cds_list_del(&gsrc->gc);
133 free(gsrc);
134 return gstr;
135 }
136
137 LTTNG_HIDDEN
138 void setstring(struct filter_parser_ctx *parser_ctx, YYSTYPE *lvalp, const char *src)
139 {
140 lvalp->gs = gc_string_alloc(parser_ctx, strlen(src) + 1);
141 strcpy(lvalp->gs->s, src);
142 }
143
144 static struct filter_node *make_node(struct filter_parser_ctx *scanner,
145 enum node_type type)
146 {
147 struct filter_ast *ast = filter_parser_get_ast(scanner);
148 struct filter_node *node;
149
150 node = zmalloc(sizeof(*node));
151 if (!node)
152 return NULL;
153 memset(node, 0, sizeof(*node));
154 node->type = type;
155 cds_list_add(&node->gc, &ast->allocated_nodes);
156
157 switch (type) {
158 case NODE_ROOT:
159 fprintf(stderr, "[error] %s: trying to create root node\n", __func__);
160 break;
161
162 case NODE_EXPRESSION:
163 break;
164 case NODE_OP:
165 break;
166 case NODE_UNARY_OP:
167 break;
168
169 case NODE_UNKNOWN:
170 default:
171 fprintf(stderr, "[error] %s: unknown node type %d\n", __func__,
172 (int) type);
173 break;
174 }
175
176 return node;
177 }
178
179 static struct filter_node *make_op_node(struct filter_parser_ctx *scanner,
180 enum op_type type,
181 struct filter_node *lchild,
182 struct filter_node *rchild)
183 {
184 struct filter_ast *ast = filter_parser_get_ast(scanner);
185 struct filter_node *node;
186
187 node = zmalloc(sizeof(*node));
188 if (!node)
189 return NULL;
190 memset(node, 0, sizeof(*node));
191 node->type = NODE_OP;
192 cds_list_add(&node->gc, &ast->allocated_nodes);
193 node->u.op.type = type;
194 node->u.op.lchild = lchild;
195 node->u.op.rchild = rchild;
196 return node;
197 }
198
199 LTTNG_HIDDEN
200 void yyerror(struct filter_parser_ctx *parser_ctx, yyscan_t scanner, const char *str)
201 {
202 fprintf(stderr, "error %s\n", str);
203 }
204
205 LTTNG_HIDDEN
206 int yywrap(void)
207 {
208 return 1;
209 }
210
211 #define parse_error(parser_ctx, str) \
212 do { \
213 yyerror(parser_ctx, parser_ctx->scanner, YY_("parse error: " str "\n")); \
214 YYERROR; \
215 } while (0)
216
217 static void free_strings(struct cds_list_head *list)
218 {
219 struct gc_string *gstr, *tmp;
220
221 cds_list_for_each_entry_safe(gstr, tmp, list, gc)
222 free(gstr);
223 }
224
225 static struct filter_ast *filter_ast_alloc(void)
226 {
227 struct filter_ast *ast;
228
229 ast = zmalloc(sizeof(*ast));
230 if (!ast)
231 return NULL;
232 memset(ast, 0, sizeof(*ast));
233 CDS_INIT_LIST_HEAD(&ast->allocated_nodes);
234 ast->root.type = NODE_ROOT;
235 return ast;
236 }
237
238 static void filter_ast_free(struct filter_ast *ast)
239 {
240 struct filter_node *node, *tmp;
241
242 cds_list_for_each_entry_safe(node, tmp, &ast->allocated_nodes, gc)
243 free(node);
244 free(ast);
245 }
246
247 LTTNG_HIDDEN
248 int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx)
249 {
250 return yyparse(parser_ctx, parser_ctx->scanner);
251 }
252
253 LTTNG_HIDDEN
254 struct filter_parser_ctx *filter_parser_ctx_alloc(FILE *input)
255 {
256 struct filter_parser_ctx *parser_ctx;
257 int ret;
258
259 yydebug = filter_parser_debug;
260
261 parser_ctx = zmalloc(sizeof(*parser_ctx));
262 if (!parser_ctx)
263 return NULL;
264 memset(parser_ctx, 0, sizeof(*parser_ctx));
265
266 ret = yylex_init_extra(parser_ctx, &parser_ctx->scanner);
267 if (ret) {
268 fprintf(stderr, "yylex_init error\n");
269 goto cleanup_parser_ctx;
270 }
271 /* Start processing new stream */
272 yyrestart(input, parser_ctx->scanner);
273
274 parser_ctx->ast = filter_ast_alloc();
275 if (!parser_ctx->ast)
276 goto cleanup_lexer;
277 CDS_INIT_LIST_HEAD(&parser_ctx->allocated_strings);
278
279 if (yydebug)
280 fprintf(stdout, "parser_ctx input is a%s.\n",
281 isatty(fileno(input)) ? "n interactive tty" :
282 " noninteractive file");
283
284 return parser_ctx;
285
286 cleanup_lexer:
287 ret = yylex_destroy(parser_ctx->scanner);
288 if (!ret)
289 fprintf(stderr, "yylex_destroy error\n");
290 cleanup_parser_ctx:
291 free(parser_ctx);
292 return NULL;
293 }
294
295 LTTNG_HIDDEN
296 void filter_parser_ctx_free(struct filter_parser_ctx *parser_ctx)
297 {
298 int ret;
299
300 free_strings(&parser_ctx->allocated_strings);
301 filter_ast_free(parser_ctx->ast);
302 ret = yylex_destroy(parser_ctx->scanner);
303 if (ret)
304 fprintf(stderr, "yylex_destroy error\n");
305 free(parser_ctx);
306 }
307
308 %}
309
310 %define api.pure
311 /* %locations */
312 %parse-param {struct filter_parser_ctx *parser_ctx}
313 %parse-param {yyscan_t scanner}
314 %lex-param {yyscan_t scanner}
315 %start translation_unit
316 %token CHARACTER_CONSTANT_START SQUOTE STRING_LITERAL_START DQUOTE
317 %token ESCSEQ CHAR_STRING_TOKEN
318 %token DECIMAL_CONSTANT OCTAL_CONSTANT HEXADECIMAL_CONSTANT FLOAT_CONSTANT
319 %token LSBRAC RSBRAC LPAREN RPAREN LBRAC RBRAC RARROW
320 %token STAR PLUS MINUS
321 %token MOD_OP DIV_OP RIGHT_OP LEFT_OP
322 %token EQ_OP NE_OP LE_OP GE_OP LT_OP GT_OP AND_OP OR_OP NOT_OP
323 %token ASSIGN COLON SEMICOLON DOTDOTDOT DOT EQUAL COMMA
324 %token XOR_BIN AND_BIN OR_BIN NOT_BIN
325
326 %token <gs> IDENTIFIER GLOBAL_IDENTIFIER
327 %token ERROR
328 %union
329 {
330 long long ll;
331 char c;
332 struct gc_string *gs;
333 struct filter_node *n;
334 }
335
336 %type <gs> s_char s_char_sequence c_char c_char_sequence
337
338 %type <n> primary_expression
339 %type <n> postfix_expression
340 %type <n> unary_expression
341 %type <n> unary_operator
342 %type <n> multiplicative_expression
343 %type <n> additive_expression
344 %type <n> shift_expression
345 %type <n> relational_expression
346 %type <n> equality_expression
347 %type <n> and_expression
348 %type <n> exclusive_or_expression
349 %type <n> inclusive_or_expression
350 %type <n> logical_and_expression
351 %type <n> logical_or_expression
352 %type <n> expression
353
354 %%
355
356
357 /* 1.5 Constants */
358
359 c_char_sequence:
360 c_char
361 { $$ = $1; }
362 | c_char_sequence c_char
363 { $$ = gc_string_append(parser_ctx, $1, $2); }
364 ;
365
366 c_char:
367 CHAR_STRING_TOKEN
368 { $$ = yylval.gs; }
369 | ESCSEQ
370 {
371 parse_error(parser_ctx, "escape sequences not supported yet");
372 }
373 ;
374
375 /* 1.6 String literals */
376
377 s_char_sequence:
378 s_char
379 { $$ = $1; }
380 | s_char_sequence s_char
381 { $$ = gc_string_append(parser_ctx, $1, $2); }
382 ;
383
384 s_char:
385 CHAR_STRING_TOKEN
386 { $$ = yylval.gs; }
387 | ESCSEQ
388 {
389 parse_error(parser_ctx, "escape sequences not supported yet");
390 }
391 ;
392
393 primary_expression
394 : IDENTIFIER
395 {
396 $$ = make_node(parser_ctx, NODE_EXPRESSION);
397 $$->u.expression.type = AST_EXP_IDENTIFIER;
398 $$->u.expression.u.identifier = yylval.gs->s;
399 }
400 | GLOBAL_IDENTIFIER
401 {
402 $$ = make_node(parser_ctx, NODE_EXPRESSION);
403 $$->u.expression.type = AST_EXP_GLOBAL_IDENTIFIER;
404 $$->u.expression.u.identifier = yylval.gs->s;
405 }
406
407 | DECIMAL_CONSTANT
408 {
409 $$ = make_node(parser_ctx, NODE_EXPRESSION);
410 $$->u.expression.type = AST_EXP_CONSTANT;
411 if (sscanf(yylval.gs->s, "%" WIDTH_u64_SCANF_IS_A_BROKEN_API SCNu64,
412 &$$->u.expression.u.constant) != 1) {
413 parse_error(parser_ctx, "cannot scanf decimal constant");
414 }
415 }
416 | OCTAL_CONSTANT
417 {
418 $$ = make_node(parser_ctx, NODE_EXPRESSION);
419 $$->u.expression.type = AST_EXP_CONSTANT;
420 if (!strcmp(yylval.gs->s, "0")) {
421 $$->u.expression.u.constant = 0;
422 } else if (sscanf(yylval.gs->s, "0%" WIDTH_o64_SCANF_IS_A_BROKEN_API SCNo64,
423 &$$->u.expression.u.constant) != 1) {
424 parse_error(parser_ctx, "cannot scanf octal constant");
425 }
426 }
427 | HEXADECIMAL_CONSTANT
428 {
429 $$ = make_node(parser_ctx, NODE_EXPRESSION);
430 $$->u.expression.type = AST_EXP_CONSTANT;
431 if (sscanf(yylval.gs->s, "0x%" WIDTH_x64_SCANF_IS_A_BROKEN_API SCNx64,
432 &$$->u.expression.u.constant) != 1) {
433 parse_error(parser_ctx, "cannot scanf hexadecimal constant");
434 }
435 }
436 | FLOAT_CONSTANT
437 {
438 $$ = make_node(parser_ctx, NODE_EXPRESSION);
439 $$->u.expression.type = AST_EXP_FLOAT_CONSTANT;
440 if (sscanf(yylval.gs->s, "%" WIDTH_lg_SCANF_IS_A_BROKEN_API "lg",
441 &$$->u.expression.u.float_constant) != 1) {
442 parse_error(parser_ctx, "cannot scanf float constant");
443 }
444 }
445 | STRING_LITERAL_START DQUOTE
446 {
447 $$ = make_node(parser_ctx, NODE_EXPRESSION);
448 $$->u.expression.type = AST_EXP_STRING;
449 $$->u.expression.u.string = "";
450 }
451 | STRING_LITERAL_START s_char_sequence DQUOTE
452 {
453 $$ = make_node(parser_ctx, NODE_EXPRESSION);
454 $$->u.expression.type = AST_EXP_STRING;
455 $$->u.expression.u.string = $2->s;
456 }
457 | CHARACTER_CONSTANT_START c_char_sequence SQUOTE
458 {
459 $$ = make_node(parser_ctx, NODE_EXPRESSION);
460 $$->u.expression.type = AST_EXP_STRING;
461 $$->u.expression.u.string = $2->s;
462 }
463 | LPAREN expression RPAREN
464 {
465 $$ = make_node(parser_ctx, NODE_EXPRESSION);
466 $$->u.expression.type = AST_EXP_NESTED;
467 $$->u.expression.u.child = $2;
468 }
469 ;
470
471 postfix_expression
472 : primary_expression
473 { $$ = $1; }
474 | postfix_expression LSBRAC unary_expression RSBRAC
475 {
476 $$ = $1;
477 $$->u.expression.pre_op = AST_LINK_BRACKET;
478 $$->u.expression.next = $3;
479 }
480 | postfix_expression DOT IDENTIFIER
481 {
482 $$ = make_node(parser_ctx, NODE_EXPRESSION);
483 $$->u.expression.type = AST_EXP_IDENTIFIER;
484 $$->u.expression.post_op = AST_LINK_DOT;
485 $$->u.expression.u.identifier = $3->s;
486 $$->u.expression.prev = $1;
487 }
488 | postfix_expression RARROW IDENTIFIER
489 {
490 $$ = make_node(parser_ctx, NODE_EXPRESSION);
491 $$->u.expression.type = AST_EXP_IDENTIFIER;
492 $$->u.expression.post_op = AST_LINK_RARROW;
493 $$->u.expression.u.identifier = $3->s;
494 $$->u.expression.prev = $1;
495 }
496 ;
497
498 unary_expression
499 : postfix_expression
500 { $$ = $1; }
501 | unary_operator unary_expression
502 {
503 $$ = $1;
504 $$->u.unary_op.child = $2;
505 }
506 ;
507
508 unary_operator
509 : PLUS
510 {
511 $$ = make_node(parser_ctx, NODE_UNARY_OP);
512 $$->u.unary_op.type = AST_UNARY_PLUS;
513 }
514 | MINUS
515 {
516 $$ = make_node(parser_ctx, NODE_UNARY_OP);
517 $$->u.unary_op.type = AST_UNARY_MINUS;
518 }
519 | NOT_OP
520 {
521 $$ = make_node(parser_ctx, NODE_UNARY_OP);
522 $$->u.unary_op.type = AST_UNARY_NOT;
523 }
524 | NOT_BIN
525 {
526 $$ = make_node(parser_ctx, NODE_UNARY_OP);
527 $$->u.unary_op.type = AST_UNARY_BIN_NOT;
528 }
529 ;
530
531 multiplicative_expression
532 : unary_expression
533 { $$ = $1; }
534 | multiplicative_expression STAR unary_expression
535 {
536 $$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3);
537 }
538 | multiplicative_expression DIV_OP unary_expression
539 {
540 $$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3);
541 }
542 | multiplicative_expression MOD_OP unary_expression
543 {
544 $$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3);
545 }
546 ;
547
548 additive_expression
549 : multiplicative_expression
550 { $$ = $1; }
551 | additive_expression PLUS multiplicative_expression
552 {
553 $$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3);
554 }
555 | additive_expression MINUS multiplicative_expression
556 {
557 $$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3);
558 }
559 ;
560
561 shift_expression
562 : additive_expression
563 { $$ = $1; }
564 | shift_expression LEFT_OP additive_expression
565 {
566 $$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3);
567 }
568 | shift_expression RIGHT_OP additive_expression
569 {
570 $$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3);
571 }
572 ;
573
574 relational_expression
575 : shift_expression
576 { $$ = $1; }
577 | relational_expression LT_OP shift_expression
578 {
579 $$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3);
580 }
581 | relational_expression GT_OP shift_expression
582 {
583 $$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3);
584 }
585 | relational_expression LE_OP shift_expression
586 {
587 $$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3);
588 }
589 | relational_expression GE_OP shift_expression
590 {
591 $$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3);
592 }
593 ;
594
595 equality_expression
596 : relational_expression
597 { $$ = $1; }
598 | equality_expression EQ_OP relational_expression
599 {
600 $$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3);
601 }
602 | equality_expression NE_OP relational_expression
603 {
604 $$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3);
605 }
606 ;
607
608 and_expression
609 : equality_expression
610 { $$ = $1; }
611 | and_expression AND_BIN equality_expression
612 {
613 $$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3);
614 }
615 ;
616
617 exclusive_or_expression
618 : and_expression
619 { $$ = $1; }
620 | exclusive_or_expression XOR_BIN and_expression
621 {
622 $$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3);
623 }
624 ;
625
626 inclusive_or_expression
627 : exclusive_or_expression
628 { $$ = $1; }
629 | inclusive_or_expression OR_BIN exclusive_or_expression
630 {
631 $$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3);
632 }
633 ;
634
635 logical_and_expression
636 : inclusive_or_expression
637 { $$ = $1; }
638 | logical_and_expression AND_OP inclusive_or_expression
639 {
640 $$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3);
641 }
642 ;
643
644 logical_or_expression
645 : logical_and_expression
646 { $$ = $1; }
647 | logical_or_expression OR_OP logical_and_expression
648 {
649 $$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3);
650 }
651 ;
652
653 expression
654 : logical_or_expression
655 { $$ = $1; }
656 ;
657
658 translation_unit
659 : expression
660 {
661 parser_ctx->ast->root.u.root.child = $1;
662 }
663 ;
This page took 0.063285 seconds and 3 git commands to generate.