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