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 GLOBAL_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         |       GLOBAL_IDENTIFIER
 391                 {
 392                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 393                         $$->u.expression.type = AST_EXP_GLOBAL_IDENTIFIER;
 394                         $$->u.expression.u.identifier = yylval.gs->s;
 395                 }
 396
 397         |       DECIMAL_CONSTANT
 398                 {
 399                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 400                         $$->u.expression.type = AST_EXP_CONSTANT;
 401                         sscanf(yylval.gs->s, "%" PRIu64,
 402                                &$$->u.expression.u.constant);
 403                 }
 404         |       OCTAL_CONSTANT
 405                 {
 406                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 407                         $$->u.expression.type = AST_EXP_CONSTANT;
 408                         sscanf(yylval.gs->s, "0%" PRIo64,
 409                                &$$->u.expression.u.constant);
 410                 }
 411         |       HEXADECIMAL_CONSTANT
 412                 {
 413                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 414                         $$->u.expression.type = AST_EXP_CONSTANT;
 415                         sscanf(yylval.gs->s, "0x%" PRIx64,
 416                                &$$->u.expression.u.constant);
 417                 }
 418         |       FLOAT_CONSTANT
 419                 {
 420                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 421                         $$->u.expression.type = AST_EXP_FLOAT_CONSTANT;
 422                         sscanf(yylval.gs->s, "%lg",
 423                                &$$->u.expression.u.float_constant);
 424                 }
 425         |       STRING_LITERAL_START DQUOTE
 426                 {
 427                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 428                         $$->u.expression.type = AST_EXP_STRING;
 429                         $$->u.expression.u.string = "";
 430                 }
 431         |       STRING_LITERAL_START s_char_sequence DQUOTE
 432                 {
 433                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 434                         $$->u.expression.type = AST_EXP_STRING;
 435                         $$->u.expression.u.string = $2->s;
 436                 }
 437         |       CHARACTER_CONSTANT_START c_char_sequence SQUOTE
 438                 {
 439                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 440                         $$->u.expression.type = AST_EXP_STRING;
 441                         $$->u.expression.u.string = $2->s;
 442                 }
 443         |       LPAREN expression RPAREN
 444                 {
 445                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 446                         $$->u.expression.type = AST_EXP_NESTED;
 447                         $$->u.expression.u.child = $2;
 448                 }
 449         ;
 450
 451 postfix_expression
 452         : primary_expression
 453                 {       $$ = $1;                                        }
 454         | postfix_expression DOT IDENTIFIER
 455                 {
 456                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 457                         $$->u.expression.type = AST_EXP_IDENTIFIER;
 458                         $$->u.expression.post_op = AST_LINK_DOT;
 459                         $$->u.expression.u.identifier = $3->s;
 460                         $$->u.expression.prev = $1;
 461                 }
 462         | postfix_expression RARROW IDENTIFIER
 463                 {
 464                         $$ = make_node(parser_ctx, NODE_EXPRESSION);
 465                         $$->u.expression.type = AST_EXP_IDENTIFIER;
 466                         $$->u.expression.post_op = AST_LINK_RARROW;
 467                         $$->u.expression.u.identifier = $3->s;
 468                         $$->u.expression.prev = $1;
 469                 }
 470         ;
 471
 472 unary_expression
 473         : postfix_expression
 474                 {       $$ = $1;                                        }
 475         | unary_operator unary_expression
 476                 {
 477                         $$ = $1;
 478                         $$->u.unary_op.child = $2;
 479                 }
 480         ;
 481
 482 unary_operator
 483         : PLUS
 484                 {
 485                         $$ = make_node(parser_ctx, NODE_UNARY_OP);
 486                         $$->u.unary_op.type = AST_UNARY_PLUS;
 487                 }
 488         | MINUS
 489                 {
 490                         $$ = make_node(parser_ctx, NODE_UNARY_OP);
 491                         $$->u.unary_op.type = AST_UNARY_MINUS;
 492                 }
 493         | NOT_OP
 494                 {
 495                         $$ = make_node(parser_ctx, NODE_UNARY_OP);
 496                         $$->u.unary_op.type = AST_UNARY_NOT;
 497                 }
 498         | NOT_BIN
 499                 {
 500                         $$ = make_node(parser_ctx, NODE_UNARY_OP);
 501                         $$->u.unary_op.type = AST_UNARY_BIN_NOT;
 502                 }
 503         ;
 504
 505 multiplicative_expression
 506         : unary_expression
 507                 {       $$ = $1;                                        }
 508         | multiplicative_expression STAR unary_expression
 509                 {
 510                         $$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3);
 511                 }
 512         | multiplicative_expression DIV_OP unary_expression
 513                 {
 514                         $$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3);
 515                 }
 516         | multiplicative_expression MOD_OP unary_expression
 517                 {
 518                         $$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3);
 519                 }
 520         ;
 521
 522 additive_expression
 523         : multiplicative_expression
 524                 {       $$ = $1;                                        }
 525         | additive_expression PLUS multiplicative_expression
 526                 {
 527                         $$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3);
 528                 }
 529         | additive_expression MINUS multiplicative_expression
 530                 {
 531                         $$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3);
 532                 }
 533         ;
 534
 535 shift_expression
 536         : additive_expression
 537                 {       $$ = $1;                                        }
 538         | shift_expression LEFT_OP additive_expression
 539                 {
 540                         $$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3);
 541                 }
 542         | shift_expression RIGHT_OP additive_expression
 543                 {
 544                         $$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3);
 545                 }
 546         ;
 547
 548 relational_expression
 549         : shift_expression
 550                 {       $$ = $1;                                        }
 551         | relational_expression LT_OP shift_expression
 552                 {
 553                         $$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3);
 554                 }
 555         | relational_expression GT_OP shift_expression
 556                 {
 557                         $$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3);
 558                 }
 559         | relational_expression LE_OP shift_expression
 560                 {
 561                         $$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3);
 562                 }
 563         | relational_expression GE_OP shift_expression
 564                 {
 565                         $$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3);
 566                 }
 567         ;
 568
 569 equality_expression
 570         : relational_expression
 571                 {       $$ = $1;                                        }
 572         | equality_expression EQ_OP relational_expression
 573                 {
 574                         $$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3);
 575                 }
 576         | equality_expression NE_OP relational_expression
 577                 {
 578                         $$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3);
 579                 }
 580         ;
 581
 582 and_expression
 583         : equality_expression
 584                 {       $$ = $1;                                        }
 585         | and_expression AND_BIN equality_expression
 586                 {
 587                         $$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3);
 588                 }
 589         ;
 590
 591 exclusive_or_expression
 592         : and_expression
 593                 {       $$ = $1;                                        }
 594         | exclusive_or_expression XOR_BIN and_expression
 595                 {
 596                         $$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3);
 597                 }
 598         ;
 599
 600 inclusive_or_expression
 601         : exclusive_or_expression
 602                 {       $$ = $1;                                        }
 603         | inclusive_or_expression OR_BIN exclusive_or_expression
 604                 {
 605                         $$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3);
 606                 }
 607         ;
 608
 609 logical_and_expression
 610         : inclusive_or_expression
 611                 {       $$ = $1;                                        }
 612         | logical_and_expression AND_OP inclusive_or_expression
 613                 {
 614                         $$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3);
 615                 }
 616         ;
 617
 618 logical_or_expression
 619         : logical_and_expression
 620                 {       $$ = $1;                                        }
 621         | logical_or_expression OR_OP logical_and_expression
 622                 {
 623                         $$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3);
 624                 }
 625         ;
 626
 627 expression
 628         : logical_or_expression
 629                 {       $$ = $1;                                        }
 630         ;
 631
 632 translation_unit
 633         : expression
 634                 {
 635                         parser_ctx->ast->root.u.root.child = $1;
 636                 }
 637         ;