Fix: filter-parser.y: use zmalloc(), missing OOM check
[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 DOT IDENTIFIER
475 {
476 $$ = make_node(parser_ctx, NODE_EXPRESSION);
477 $$->u.expression.type = AST_EXP_IDENTIFIER;
478 $$->u.expression.post_op = AST_LINK_DOT;
479 $$->u.expression.u.identifier = $3->s;
480 $$->u.expression.prev = $1;
481 }
482 | postfix_expression RARROW IDENTIFIER
483 {
484 $$ = make_node(parser_ctx, NODE_EXPRESSION);
485 $$->u.expression.type = AST_EXP_IDENTIFIER;
486 $$->u.expression.post_op = AST_LINK_RARROW;
487 $$->u.expression.u.identifier = $3->s;
488 $$->u.expression.prev = $1;
489 }
490 ;
491
492 unary_expression
493 : postfix_expression
494 { $$ = $1; }
495 | unary_operator unary_expression
496 {
497 $$ = $1;
498 $$->u.unary_op.child = $2;
499 }
500 ;
501
502 unary_operator
503 : PLUS
504 {
505 $$ = make_node(parser_ctx, NODE_UNARY_OP);
506 $$->u.unary_op.type = AST_UNARY_PLUS;
507 }
508 | MINUS
509 {
510 $$ = make_node(parser_ctx, NODE_UNARY_OP);
511 $$->u.unary_op.type = AST_UNARY_MINUS;
512 }
513 | NOT_OP
514 {
515 $$ = make_node(parser_ctx, NODE_UNARY_OP);
516 $$->u.unary_op.type = AST_UNARY_NOT;
517 }
518 | NOT_BIN
519 {
520 $$ = make_node(parser_ctx, NODE_UNARY_OP);
521 $$->u.unary_op.type = AST_UNARY_BIN_NOT;
522 }
523 ;
524
525 multiplicative_expression
526 : unary_expression
527 { $$ = $1; }
528 | multiplicative_expression STAR unary_expression
529 {
530 $$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3);
531 }
532 | multiplicative_expression DIV_OP unary_expression
533 {
534 $$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3);
535 }
536 | multiplicative_expression MOD_OP unary_expression
537 {
538 $$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3);
539 }
540 ;
541
542 additive_expression
543 : multiplicative_expression
544 { $$ = $1; }
545 | additive_expression PLUS multiplicative_expression
546 {
547 $$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3);
548 }
549 | additive_expression MINUS multiplicative_expression
550 {
551 $$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3);
552 }
553 ;
554
555 shift_expression
556 : additive_expression
557 { $$ = $1; }
558 | shift_expression LEFT_OP additive_expression
559 {
560 $$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3);
561 }
562 | shift_expression RIGHT_OP additive_expression
563 {
564 $$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3);
565 }
566 ;
567
568 relational_expression
569 : shift_expression
570 { $$ = $1; }
571 | relational_expression LT_OP shift_expression
572 {
573 $$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3);
574 }
575 | relational_expression GT_OP shift_expression
576 {
577 $$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3);
578 }
579 | relational_expression LE_OP shift_expression
580 {
581 $$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3);
582 }
583 | relational_expression GE_OP shift_expression
584 {
585 $$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3);
586 }
587 ;
588
589 equality_expression
590 : relational_expression
591 { $$ = $1; }
592 | equality_expression EQ_OP relational_expression
593 {
594 $$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3);
595 }
596 | equality_expression NE_OP relational_expression
597 {
598 $$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3);
599 }
600 ;
601
602 and_expression
603 : equality_expression
604 { $$ = $1; }
605 | and_expression AND_BIN equality_expression
606 {
607 $$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3);
608 }
609 ;
610
611 exclusive_or_expression
612 : and_expression
613 { $$ = $1; }
614 | exclusive_or_expression XOR_BIN and_expression
615 {
616 $$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3);
617 }
618 ;
619
620 inclusive_or_expression
621 : exclusive_or_expression
622 { $$ = $1; }
623 | inclusive_or_expression OR_BIN exclusive_or_expression
624 {
625 $$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3);
626 }
627 ;
628
629 logical_and_expression
630 : inclusive_or_expression
631 { $$ = $1; }
632 | logical_and_expression AND_OP inclusive_or_expression
633 {
634 $$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3);
635 }
636 ;
637
638 logical_or_expression
639 : logical_and_expression
640 { $$ = $1; }
641 | logical_or_expression OR_OP logical_and_expression
642 {
643 $$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3);
644 }
645 ;
646
647 expression
648 : logical_or_expression
649 { $$ = $1; }
650 ;
651
652 translation_unit
653 : expression
654 {
655 parser_ctx->ast->root.u.root.child = $1;
656 }
657 ;
This page took 0.070186 seconds and 4 git commands to generate.