qparser.y

   1 %define api.pure
   2 %error-verbose
   3
   4 %{
   5 #include <config.h>
   6 #include "query.h"
   7 #include "iwhd-qparser.h"
   8 %}
   9
  10 %union {
  11   char *str;
  12   struct value_t *val;
  13 }
  14
  15 %{
  16 #include <error.h>
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <ctype.h>
  21
  22 #include "iwh.h"
  23
  24 /* Return a pointer to this when allocation fails in a value_t-returning
  25    function.  */
  26 static value_t invalid = { T_INVALID, {0}, NULL };
  27
  28 #define YY_DECL int yylex(YYSTYPE *, void *scanner);
  29 YY_DECL
  30
  31 /* TBD: use separate function to parse dates differently */
  32 static value_t *
  33 make_number (const char *text)
  34 {
  35         value_t *tmp = malloc(sizeof(*tmp));
  36         if (!tmp)
  37                 return &invalid;
  38
  39         tmp->type = T_NUMBER;
  40         tmp->as_num = strtoll(text,NULL,10);
  41         tmp->resolved = NULL;
  42         free ((void *) text);
  43
  44         return tmp;
  45 }
  46
  47 /* Return a malloc'd value_t buffer, with its type to T and using TEXT
  48    (already malloc'd) as its string.  */
  49 static value_t *
  50 make_string (const char *text, type_t t)
  51 {
  52         value_t *tmp = malloc(sizeof(*tmp));
  53         if (!tmp)
  54                 return &invalid;
  55
  56         tmp->type = t;
  57         tmp->as_str = (char *) text;
  58         tmp->resolved = NULL;
  59
  60         return tmp;
  61 }
  62
  63 /* Return a malloc'd tree_t, with type T and branches LEFT and RIGHT.
  64    LEFT must be non-NULL.  RIGHT may be NULL (solely for use in handling
  65    a negated expression).  */
  66 static value_t *
  67 make_tree (type_t t, const value_t *left, const value_t *right)
  68 {
  69         if (left->type == T_INVALID)
  70                 return (value_t *) left;
  71         if (t != T_LINK && right && right->type == T_INVALID)
  72                 return (value_t *) right;
  73         value_t *tmp = malloc(sizeof(*tmp));
  74
  75         if (!tmp)
  76                 return &invalid;
  77
  78         tmp->type = t;
  79         tmp->as_tree.left = (value_t *) left;
  80         tmp->as_tree.right = (value_t *) right;
  81         tmp->resolved = NULL;
  82
  83         return tmp;
  84 }
  85
  86 /* Return a malloc'd comp_t, with type T and branches LEFT and RIGHT.
  87    LEFT and RIGHT must both be non-NULL.  */
  88 static value_t *
  89 make_comp (comp_t c, const value_t *left, const value_t *right)
  90 {
  91         if (left->type == T_INVALID)
  92                 return (value_t *) left;
  93         if (right->type == T_INVALID)
  94                 return (value_t *) right;
  95         value_t *tmp = make_tree(T_COMP,left,right);
  96
  97         if (!tmp)
  98                 return &invalid;
  99
 100         tmp->as_tree.op = c;
 101
 102         return tmp;
 103 }
 104
 105 static value_t *
 106 make_link (const value_t *left, const char *right)
 107 {
 108         return make_tree(T_LINK,left,(value_t *)right);
 109 }
 110
 111 static void
 112 yyerror (void *scanner ATTRIBUTE_UNUSED,
 113          value_t **result ATTRIBUTE_UNUSED,
 114          const char *msg ATTRIBUTE_UNUSED)
 115 {
 116         /* empty */
 117 }
 118
 119 %}
 120
 121 %lex-param   { yyscan_t scanner }
 122 %parse-param { void *scanner }
 123 %parse-param { value_t **result }
 124
 125 %token <str> T_STRING T_COMP T_DATE T_ID T_LINK T_NUMBER T_OFIELD T_SFIELD
 126 %token T_EQ T_NE T_NOT T_AND T_OR T_INVALID
 127 %token T_LT T_GT T_LE T_GE
 128
 129 %type <val> atom bbool_expr comp_expr field
 130 %type <val> link_field literal paren_expr ubool_expr
 131
 132 %start policy
 133
 134 %%
 135
 136 policy:
 137         bbool_expr {
 138                 *result = $1;
 139         };
 140
 141 bbool_expr:
 142         ubool_expr {
 143                 // printf("promoting ubool_expr to bbool_expr\n");
 144                 $$ = $1;
 145         }|
 146         bbool_expr T_AND ubool_expr {
 147                 // printf("found AND expression\n");
 148                 $$ = make_tree(T_AND,$1,$3);
 149         }|
 150         bbool_expr T_OR ubool_expr {
 151                 // printf("found OR expression\n");
 152                 $$ = make_tree(T_OR,$1,$3);
 153         };
 154
 155 ubool_expr:
 156         comp_expr {
 157                 // printf("promoting comp_expr to ubool_expr\n");
 158                 $$ = $1;
 159         }|
 160         T_NOT comp_expr {
 161                 // printf("found NOT expression\n");
 162                 $$ = make_tree(T_NOT,$2,NULL);
 163         };
 164
 165
 166 comp_expr:
 167         atom {
 168                 // printf("promoting atom to comp_expr\n");
 169                 $$ = $1;
 170         }|
 171         atom T_LT atom {
 172                 // printf("found LESS THAN expression\n");
 173                 $$ = make_comp(C_LESSTHAN,$1,$3);
 174         }|
 175         atom T_LE atom {
 176                 // printf("found LESS OR EQUAL expression\n");
 177                 $$ = make_comp(C_LESSOREQ,$1,$3);
 178         }|
 179         atom T_EQ atom {
 180                 // printf("found EQUAL expression\n");
 181                 $$ = make_comp(C_EQUAL,$1,$3);
 182         }|
 183         atom T_NE atom {
 184                 // printf("found NOT EQUAL expression\n");
 185                 $$ = make_comp(C_DIFFERENT,$1,$3);
 186         }|
 187         atom T_GE atom {
 188                 // printf("found GREATER OR EQUAL expression\n");
 189                 $$ = make_comp(C_GREATEROREQ,$1,$3);
 190         }|
 191         atom T_GT atom {
 192                 // printf("found GREATER THAN expression\n");
 193                 $$ = make_comp(C_GREATERTHAN,$1,$3);
 194         };
 195
 196 atom:
 197         link_field {
 198                 // printf("promoting link_field to atom\n");
 199                 $$ = $1;
 200         }|
 201         literal {
 202                 // printf("promoting literal to atom\n");
 203                 $$ = $1;
 204         }|
 205         paren_expr {
 206                 // printf("promoting paren_expr to atom\n");
 207                 $$ = $1;
 208         };
 209
 210 link_field:
 211         field {
 212                 // printf("promoting field to link_field\n");
 213                 $$ = $1;
 214         }|
 215         link_field '.' T_ID {
 216                 // printf("found LINK FIELD\n");
 217                 $$ = make_link($1,$3);
 218         };
 219
 220 field:
 221         '$' T_ID {
 222                 // printf("found DOLLAR FIELD\n");
 223                 $$ = make_string($2,T_OFIELD);
 224         }|
 225         '#' T_ID {
 226                 // printf("found WAFFLE FIELD\n");
 227                 $$ = make_string($2,T_SFIELD);
 228         };
 229
 230 literal:
 231         T_NUMBER {
 232                 // printf("found NUMBER %s\n",$1);
 233                 $$ = make_number($1);
 234         }|
 235         T_STRING {
 236                 // printf("found STRING %s\n",$1);
 237                 $$ = make_string($1,T_STRING);
 238         }|
 239         T_DATE {
 240                 // printf("found DATE\n");
 241                 $$ = make_string($1,T_DATE);
 242         }|
 243         T_ID {
 244                 // printf("found ID %s\n",$1);
 245                 $$ = make_string($1,T_ID);
 246         };
 247
 248 paren_expr:
 249         '(' bbool_expr ')' {
 250                 // printf("found PAREN expression\n");
 251                 $$ = $2;
 252         };
 253
 254 %%
 255
 256 #if defined PARSER_UNIT_TEST
 257
 258 #include "xalloc.h"
 259
 260 static const struct { char *name; char *value; } hacked_obj_fields[] = {
 261         /* Fake object fields for generic unit testing. */
 262         { "a", "2" }, { "b", "7" }, { "c", "11" },
 263         /* This one's here to test links (e.g. $template.owner.name). */
 264         { "template", "templates/the_tmpl" },
 265         { NULL }
 266 };
 267
 268 /* Fake out the eval code for unit testing. */
 269 static const char *
 270 unit_oget_func (void * notused, const char *text)
 271 {
 272         int i;
 273
 274         for (i = 0; hacked_obj_fields[i].name; ++i) {
 275                 if (!strcmp(hacked_obj_fields[i].name,text)) {
 276                         return xstrdup(hacked_obj_fields[i].value);
 277                 }
 278         }
 279
 280         return NULL;
 281 }
 282 static const getter_t unit_oget = { unit_oget_func };
 283
 284 /*
 285  * Same as above, but the site-field stuff is so similar to the object-field
 286  * stuff that it's not worth exercising too much separately.
 287  */
 288 static const char *
 289 unit_sget_func (void * notused, const char *text)
 290 {
 291         return "never";
 292 }
 293 static const getter_t unit_sget = { unit_sget_func };
 294
 295 /* Fake links from an object/key tuple to an object/key string. */
 296 static const struct { char *obj; char *key; char *value; } hacked_links[] = {
 297         { "templates/the_tmpl", "owner", "users/the_user" },
 298         { "users/the_user", "name", "Jeff Darcy" },
 299         { NULL }
 300 };
 301
 302 static char *
 303 follow_link (const char *object, const char *key)
 304 {
 305         unsigned int i;
 306
 307         for (i = 0; hacked_links[i].obj; ++i) {
 308                 if (strcmp(object,hacked_links[i].obj)) {
 309                         continue;
 310                 }
 311                 if (strcmp(key,hacked_links[i].key)) {
 312                         continue;
 313                 }
 314                 return hacked_links[i].value;
 315         }
 316
 317         return NULL;
 318 }
 319 #else
 320 extern char *follow_link (const char *object, const char *key);
 321 #endif
 322
 323 static void
 324 _print_value (const value_t *v, int level)
 325 {
 326         if (!v) {
 327                 printf("%*sNULL\n",level,"");
 328                 return;
 329         }
 330
 331         switch (v->type) {
 332         case T_NUMBER:
 333                 printf("%*sNUMBER %lld\n",level,"",v->as_num);
 334                 break;
 335         case T_STRING:
 336                 printf("%*sSTRING %s\n",level,"",v->as_str);
 337                 break;
 338         case T_OFIELD:
 339 #if defined PARSER_UNIT_TEST
 340                 printf("%*sOBJECT FIELD %s (%s)\n",level,"",v->as_str,
 341                         unit_oget_func(NULL,v->as_str));
 342 #else
 343                 printf("%*sOBJECT FIELD %s\n",level,"",v->as_str);
 344 #endif
 345                 break;
 346         case T_SFIELD:
 347 #if defined PARSER_UNIT_TEST
 348                 printf("%*sSERVER FIELD %s (%s)\n",level,"",v->as_str,
 349                         unit_sget_func(NULL,v->as_str));
 350 #else
 351                 printf("%*sSERVER FIELD %s\n",level,"",v->as_str);
 352 #endif
 353                 break;
 354         case T_COMP:
 355                 printf("%*sCOMPARISON\n",level,"");
 356                 _print_value(v->as_tree.left,level+2);
 357                 _print_value(v->as_tree.right,level+2);
 358                 break;
 359         case T_NOT:
 360                 printf("%*sNOT\n",level,"");
 361                 _print_value(v->as_tree.left,level+2);
 362                 break;
 363         case T_AND:
 364                 printf("%*sAND\n",level,"");
 365                 _print_value(v->as_tree.left,level+2);
 366                 _print_value(v->as_tree.right,level+2);
 367                 break;
 368         case T_OR:
 369                 printf("%*sOR\n",level,"");
 370                 _print_value(v->as_tree.left,level+2);
 371                 _print_value(v->as_tree.right,level+2);
 372                 break;
 373         case T_LINK:
 374                 printf("%*sLINK\n",level,"");
 375                 _print_value(v->as_tree.left,level+2);
 376                 printf("%*sDEST FIELD %s\n",level+2,"",
 377                         (char *)v->as_tree.right);
 378                 break;
 379         default:
 380                 printf("%*sUNKNOWN %d\n",level,"",v->type);
 381         }
 382 }
 383
 384 void
 385 print_value (const value_t *v)
 386 {
 387         _print_value(v,0);
 388 }
 389
 390 void
 391 free_value (value_t *v)
 392 {
 393         if (v == NULL || v == &invalid) {
 394                 return;
 395         }
 396
 397         free((void *)v->resolved);
 398
 399         switch (v->type) {
 400         case T_STRING:
 401         case T_OFIELD:
 402         case T_SFIELD:
 403         case T_ID:
 404                 free(v->as_str);
 405                 free(v);
 406                 break;
 407         case T_LINK:
 408                 free_value(v->as_tree.left);
 409                 free(v->as_tree.right);
 410                 free(v);
 411                 break;
 412         case T_COMP:
 413         case T_AND:
 414         case T_OR:
 415                 free_value(v->as_tree.right);
 416                 /* Fall through. */
 417         case T_NOT:
 418                 free_value(v->as_tree.left);
 419                 /* Fall through. */
 420         default:
 421                 free(v);
 422         }
 423 }
 424
 425 #include "qlexer.c"
 426
 427 value_t *
 428 parse (const char *text)
 429 {
 430   yyscan_t scanner;
 431   if (yylex_init (&scanner))
 432     error (0, errno, "failed to initialize query parser");
 433   YY_BUFFER_STATE buf = yy_scan_string (text, scanner);
 434   value_t *result = NULL;
 435   value_t *r = yyparse (scanner, &result) == 0 ? result : NULL;
 436   if (r == NULL)
 437     free_value (result);
 438   yy_delete_buffer (buf, scanner);
 439   yylex_destroy (scanner);
 440   return r;
 441 }
 442
 443 /*
 444  * Return the string value of an expression for comparison or display, iff
 445  * all component parts are string-valued themselves.  That excludes numbers
 446  * and booleans.
 447  */
 448 static const char *
 449 string_value (value_t *v, const getter_t *oget, const getter_t *sget)
 450 {
 451         const char      *left;
 452
 453         switch (v->type) {
 454         case T_STRING:
 455                 return v->as_str;
 456         case T_OFIELD:
 457                 if (!v->resolved) {
 458                         v->resolved = oget ? CALL_GETTER(oget,v->as_str) : NULL;
 459                 }
 460                 return v->resolved;
 461         case T_SFIELD:
 462                 return sget ? CALL_GETTER(sget,v->as_str) : NULL;
 463         case T_LINK:
 464                 if (!v->resolved) {
 465                         left = string_value(v->as_tree.left,oget,sget);
 466                         if (left) {
 467                                 v->resolved = follow_link((char *)left,
 468                                         (char *)v->as_tree.right);
 469                         }
 470                 }
 471                 return v->resolved;
 472         default:
 473                 return NULL;
 474         }
 475 }
 476
 477 /*
 478  * Check whether a string looks like a simple decimal number.  There's
 479  * probably a library function for this somewhere.
 480  */
 481 static int
 482 is_ok_number (const char *a_str)
 483 {
 484         const char      *p;
 485
 486         if (!a_str) {
 487                 return 0;
 488         }
 489
 490         for (p = a_str; *p; ++p) {
 491                 if (!isdigit(*p)) {
 492                         return 0;
 493                 }
 494         }
 495
 496         return 1;
 497 }
 498
 499 /*
 500  * Comparisons are a bit messy.  If both sides are numbers, strings that look
 501  * like numbers, or expressions that evaluate to numbers (booleans evaluate
 502  * to 0/1), then we do a numeric comparison.  Otherwise, if both sides
 503  * evaluate to strings, we attempt a string comparison.   That's the logic,
 504  * but the code is actually structured a different way to allow re-use of
 505  * common operator-specific code at the end for both cases.
 506  */
 507 static int
 508 compare (value_t *left, comp_t op, value_t *right,
 509          const getter_t *oget, const getter_t *sget)
 510 {
 511         const char      *lstr;
 512         const char      *rstr;
 513         int              lval = 0; // solely to placate gcc
 514         int              rval;
 515         int              num_ok = 1;
 516
 517         lstr = string_value(left,oget,sget);
 518         rstr = string_value(right,oget,sget);
 519
 520         if (left->type == T_NUMBER) {
 521                 lval = left->as_num;
 522         }
 523         else if (lstr) {
 524                 if (is_ok_number(lstr)) {
 525                         lval = strtoll(lstr,NULL,0);
 526                 }
 527                 else {
 528                         num_ok = 0;
 529                 }
 530         }
 531         else {
 532                 lval = eval(left,oget,sget);
 533                 if (lval < 0) {
 534                         return lval;
 535                 }
 536         }
 537
 538         if (right->type == T_NUMBER) {
 539                 rval = right->as_num;
 540         }
 541         else if (rstr) {
 542                 if (is_ok_number(rstr)) {
 543                         rval = strtoll(rstr,NULL,0);
 544                 }
 545                 else {
 546                         num_ok = 0;
 547                 }
 548         }
 549         else {
 550                 rval = eval(right,oget,sget);
 551                 if (rval < 0) {
 552                         return rval;
 553                 }
 554         }
 555
 556         /*
 557          * Strcmp returns -1/0/1, but -1 for us would mean an error and
 558          * which of 0/1 we return depends on which comparison operatoer
 559          * we're dealing with.  Therefore, we stick the strcmp result on
 560          * the left side and let the switch below do an operator-appropriate
 561          * compare against zero on the right.
 562          */
 563         if (!num_ok) {
 564                 if (!lstr || !rstr) {
 565                         return -1;
 566                 }
 567                 lval = strcmp(lstr,rstr);
 568                 rval = 0;
 569         }
 570
 571         switch (op) {
 572         case C_LESSTHAN:        return (lval < rval);
 573         case C_LESSOREQ:        return (lval <= rval);
 574         case C_EQUAL:           return (lval == rval);
 575         case C_DIFFERENT:       return (lval != rval);
 576         case C_GREATEROREQ:     return (lval >= rval);
 577         case C_GREATERTHAN:     return (lval > rval);
 578         default:
 579                 return -1;
 580         }
 581 }
 582
 583 /*
 584  * Evaluate an AST in the current context to one of:
 585  *      true=1
 586  *      false=0
 587  *      error=-1
 588  * It's up to the caller whether error is functionally the same as false.
 589  * Note that even T_NUMBER gets squeezed down to these three values.  The
 590  * only thing numbers are used for is comparing against other numbers to
 591  * yield a boolean for the query or replication-policy code.  If you want
 592  * something that returns a number, this is the wrong language for it.
 593  */
 594
 595 int
 596 eval (const value_t *v, const getter_t *oget, const getter_t *sget)
 597 {
 598         int              res;
 599         const char      *str;
 600
 601         switch (v->type) {
 602         case T_NUMBER:
 603                 return v->as_num != 0;
 604         case T_STRING:
 605                 return v->as_str && *v->as_str;
 606         case T_OFIELD:
 607                 str = CALL_GETTER(oget,v->as_str);
 608                 return str && *str;
 609         case T_SFIELD:
 610                 str = CALL_GETTER(sget,v->as_str);
 611                 return str && *str;
 612         case T_LINK:
 613                 str = string_value(v->as_tree.left,oget,sget);
 614                 if (str) {
 615                         str = follow_link(str,(char *)v->as_tree.right);
 616                 }
 617                 return str && *str;
 618         case T_COMP:
 619                 return compare(v->as_tree.left,(comp_t)v->as_tree.op,
 620                         v->as_tree.right, oget, sget);
 621         case T_NOT:
 622                 res = eval(v->as_tree.left,oget,sget);
 623                 return (res >= 0) ? !res : res;
 624         case T_AND:
 625                 res = eval(v->as_tree.left,oget,sget);
 626                 if (res > 0) {
 627                         res = eval(v->as_tree.right,oget,sget);
 628                 }
 629                 return res;
 630         case T_OR:
 631                 res = eval(v->as_tree.left,oget,sget);
 632                 if (res > 0) {
 633                         return res;
 634                 }
 635                 return eval(v->as_tree.right,oget,sget);
 636         default:
 637                 return -1;
 638         }
 639 }
 640
 641 #ifdef PARSER_UNIT_TEST
 642 int
 643 main (int argc, char **argv)
 644 {
 645   int fail = 0;
 646   unsigned int i;
 647   for (i = 1; i < argc; ++i)
 648     {
 649       value_t *expr = parse (argv[i]);
 650       if (!expr)
 651         {
 652           printf ("could not parse '%s'\n", argv[i]);
 653           fail = 1;
 654           goto next;
 655         }
 656
 657       print_value (expr);
 658
 659       const char *str = string_value (expr, &unit_oget, &unit_sget);
 660       if (str)
 661         {
 662           printf ("s= %s\n", str);
 663           goto next;
 664         }
 665       printf ("d= %d\n", eval (expr, &unit_oget, &unit_sget));
 666
 667     next:
 668       free_value (expr);
 669     }
 670
 671   return fail;
 672 }
 673 #endif