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