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 static void
 259 xalloc_die (void)
 260 {
 261   error (EXIT_FAILURE, 0, "%s", "memory exhausted");
 262
 263   /* The `noreturn' cannot be given to error, since it may return if
 264      its first argument is 0.  To help compilers understand the
 265      xalloc_die does not return, call abort.  Also, the abort is a
 266      safety feature if exit_failure is 0 (which shouldn't happen).  */
 267   abort ();
 268 }
 269
 270 /* Allocate N bytes of memory dynamically, with error checking.  */
 271 static void *
 272 xmalloc (size_t n)
 273 {
 274   void *p = malloc (n);
 275   if (!p && n != 0)
 276     xalloc_die ();
 277   return p;
 278 }
 279
 280 /* Clone an object P of size S, with error checking.  There's no need
 281    for xnmemdup (P, N, S), since xmemdup (P, N * S) works without any
 282    need for an arithmetic overflow check.  */
 283 static void *
 284 xmemdup (void const *p, size_t s)
 285 {
 286   return memcpy (xmalloc (s), p, s);
 287 }
 288
 289 /* Clone STRING.  */
 290 static char *
 291 xstrdup (char const *string)
 292 {
 293   return xmemdup (string, strlen (string) + 1);
 294 }
 295
 296 static const struct { char *name; char *value; } hacked_obj_fields[] = {
 297         /* Fake object fields for generic unit testing. */
 298         { "a", "2" }, { "b", "7" }, { "c", "11" },
 299         /* This one's here to test links (e.g. $template.owner.name). */
 300         { "template", "templates/the_tmpl" },
 301         { NULL }
 302 };
 303
 304 /* Fake out the eval code for unit testing. */
 305 static const char *
 306 unit_oget_func (void * notused, const char *text)
 307 {
 308         int i;
 309
 310         for (i = 0; hacked_obj_fields[i].name; ++i) {
 311                 if (!strcmp(hacked_obj_fields[i].name,text)) {
 312                         return xstrdup(hacked_obj_fields[i].value);
 313                 }
 314         }
 315
 316         return NULL;
 317 }
 318 static const getter_t unit_oget = { unit_oget_func };
 319
 320 /*
 321  * Same as above, but the site-field stuff is so similar to the object-field
 322  * stuff that it's not worth exercising too much separately.
 323  */
 324 static const char *
 325 unit_sget_func (void * notused, const char *text)
 326 {
 327         return "never";
 328 }
 329 static const getter_t unit_sget = { unit_sget_func };
 330
 331 /* Fake links from an object/key tuple to an object/key string. */
 332 static const struct { char *obj; char *key; char *value; } hacked_links[] = {
 333         { "templates/the_tmpl", "owner", "users/the_user" },
 334         { "users/the_user", "name", "Jeff Darcy" },
 335         { NULL }
 336 };
 337
 338 static char *
 339 follow_link (const char *object, const char *key)
 340 {
 341         unsigned int i;
 342
 343         for (i = 0; hacked_links[i].obj; ++i) {
 344                 if (strcmp(object,hacked_links[i].obj)) {
 345                         continue;
 346                 }
 347                 if (strcmp(key,hacked_links[i].key)) {
 348                         continue;
 349                 }
 350                 return hacked_links[i].value;
 351         }
 352
 353         return NULL;
 354 }
 355 #else
 356 extern char *follow_link (const char *object, const char *key);
 357 #endif
 358
 359 static void
 360 _print_value (const value_t *v, int level)
 361 {
 362         if (!v) {
 363                 printf("%*sNULL\n",level,"");
 364                 return;
 365         }
 366
 367         switch (v->type) {
 368         case T_NUMBER:
 369                 printf("%*sNUMBER %lld\n",level,"",v->as_num);
 370                 break;
 371         case T_STRING:
 372                 printf("%*sSTRING %s\n",level,"",v->as_str);
 373                 break;
 374         case T_OFIELD:
 375 #if defined PARSER_UNIT_TEST
 376                 printf("%*sOBJECT FIELD %s (%s)\n",level,"",v->as_str,
 377                         unit_oget_func(NULL,v->as_str));
 378 #else
 379                 printf("%*sOBJECT FIELD %s\n",level,"",v->as_str);
 380 #endif
 381                 break;
 382         case T_SFIELD:
 383 #if defined PARSER_UNIT_TEST
 384                 printf("%*sSERVER FIELD %s (%s)\n",level,"",v->as_str,
 385                         unit_sget_func(NULL,v->as_str));
 386 #else
 387                 printf("%*sSERVER FIELD %s\n",level,"",v->as_str);
 388 #endif
 389                 break;
 390         case T_COMP:
 391                 printf("%*sCOMPARISON\n",level,"");
 392                 _print_value(v->as_tree.left,level+2);
 393                 _print_value(v->as_tree.right,level+2);
 394                 break;
 395         case T_NOT:
 396                 printf("%*sNOT\n",level,"");
 397                 _print_value(v->as_tree.left,level+2);
 398                 break;
 399         case T_AND:
 400                 printf("%*sAND\n",level,"");
 401                 _print_value(v->as_tree.left,level+2);
 402                 _print_value(v->as_tree.right,level+2);
 403                 break;
 404         case T_OR:
 405                 printf("%*sOR\n",level,"");
 406                 _print_value(v->as_tree.left,level+2);
 407                 _print_value(v->as_tree.right,level+2);
 408                 break;
 409         case T_LINK:
 410                 printf("%*sLINK\n",level,"");
 411                 _print_value(v->as_tree.left,level+2);
 412                 printf("%*sDEST FIELD %s\n",level+2,"",
 413                         (char *)v->as_tree.right);
 414                 break;
 415         default:
 416                 printf("%*sUNKNOWN %d\n",level,"",v->type);
 417         }
 418 }
 419
 420 void
 421 print_value (const value_t *v)
 422 {
 423         _print_value(v,0);
 424 }
 425
 426 void
 427 free_value (value_t *v)
 428 {
 429         if (v == NULL || v == &invalid) {
 430                 return;
 431         }
 432
 433         free((void *)v->resolved);
 434
 435         switch (v->type) {
 436         case T_STRING:
 437         case T_OFIELD:
 438         case T_SFIELD:
 439         case T_ID:
 440                 free(v->as_str);
 441                 free(v);
 442                 break;
 443         case T_LINK:
 444                 free_value(v->as_tree.left);
 445                 free(v->as_tree.right);
 446                 free(v);
 447                 break;
 448         case T_COMP:
 449         case T_AND:
 450         case T_OR:
 451                 free_value(v->as_tree.right);
 452                 /* Fall through. */
 453         case T_NOT:
 454                 free_value(v->as_tree.left);
 455                 /* Fall through. */
 456         default:
 457                 free(v);
 458         }
 459 }
 460
 461 #include "qlexer.c"
 462
 463 value_t *
 464 parse (const char *text)
 465 {
 466   yyscan_t scanner;
 467   if (yylex_init (&scanner))
 468     error (0, errno, "failed to initialize query parser");
 469   YY_BUFFER_STATE buf = yy_scan_string (text, scanner);
 470   value_t *result = NULL;
 471   value_t *r = yyparse (scanner, &result) == 0 ? result : NULL;
 472   if (r == NULL)
 473     free_value (result);
 474   yy_delete_buffer (buf, scanner);
 475   yylex_destroy (scanner);
 476   return r;
 477 }
 478
 479 /*
 480  * Return the string value of an expression for comparison or display, iff
 481  * all component parts are string-valued themselves.  That excludes numbers
 482  * and booleans.
 483  */
 484 static const char *
 485 string_value (value_t *v, const getter_t *oget, const getter_t *sget)
 486 {
 487         const char      *left;
 488
 489         switch (v->type) {
 490         case T_STRING:
 491                 return v->as_str;
 492         case T_OFIELD:
 493                 if (!v->resolved) {
 494                         v->resolved = oget ? CALL_GETTER(oget,v->as_str) : NULL;
 495                 }
 496                 return v->resolved;
 497         case T_SFIELD:
 498                 return sget ? CALL_GETTER(sget,v->as_str) : NULL;
 499         case T_LINK:
 500                 if (!v->resolved) {
 501                         left = string_value(v->as_tree.left,oget,sget);
 502                         if (left) {
 503                                 v->resolved = follow_link((char *)left,
 504                                         (char *)v->as_tree.right);
 505                         }
 506                 }
 507                 return v->resolved;
 508         default:
 509                 return NULL;
 510         }
 511 }
 512
 513 /*
 514  * Check whether a string looks like a simple decimal number.  There's
 515  * probably a library function for this somewhere.
 516  */
 517 static int
 518 is_ok_number (const char *a_str)
 519 {
 520         const char      *p;
 521
 522         if (!a_str) {
 523                 return 0;
 524         }
 525
 526         for (p = a_str; *p; ++p) {
 527                 if (!isdigit(*p)) {
 528                         return 0;
 529                 }
 530         }
 531
 532         return 1;
 533 }
 534
 535 /*
 536  * Comparisons are a bit messy.  If both sides are numbers, strings that look
 537  * like numbers, or expressions that evaluate to numbers (booleans evaluate
 538  * to 0/1), then we do a numeric comparison.  Otherwise, if both sides
 539  * evaluate to strings, we attempt a string comparison.   That's the logic,
 540  * but the code is actually structured a different way to allow re-use of
 541  * common operator-specific code at the end for both cases.
 542  */
 543 static int
 544 compare (value_t *left, comp_t op, value_t *right,
 545          const getter_t *oget, const getter_t *sget)
 546 {
 547         const char      *lstr;
 548         const char      *rstr;
 549         int              lval = 0; // solely to placate gcc
 550         int              rval;
 551         int              num_ok = 1;
 552
 553         lstr = string_value(left,oget,sget);
 554         rstr = string_value(right,oget,sget);
 555
 556         if (left->type == T_NUMBER) {
 557                 lval = left->as_num;
 558         }
 559         else if (lstr) {
 560                 if (is_ok_number(lstr)) {
 561                         lval = strtoll(lstr,NULL,0);
 562                 }
 563                 else {
 564                         num_ok = 0;
 565                 }
 566         }
 567         else {
 568                 lval = eval(left,oget,sget);
 569                 if (lval < 0) {
 570                         return lval;
 571                 }
 572         }
 573
 574         if (right->type == T_NUMBER) {
 575                 rval = right->as_num;
 576         }
 577         else if (rstr) {
 578                 if (is_ok_number(rstr)) {
 579                         rval = strtoll(rstr,NULL,0);
 580                 }
 581                 else {
 582                         num_ok = 0;
 583                 }
 584         }
 585         else {
 586                 rval = eval(right,oget,sget);
 587                 if (rval < 0) {
 588                         return rval;
 589                 }
 590         }
 591
 592         /*
 593          * Strcmp returns -1/0/1, but -1 for us would mean an error and
 594          * which of 0/1 we return depends on which comparison operatoer
 595          * we're dealing with.  Therefore, we stick the strcmp result on
 596          * the left side and let the switch below do an operator-appropriate
 597          * compare against zero on the right.
 598          */
 599         if (!num_ok) {
 600                 if (!lstr || !rstr) {
 601                         return -1;
 602                 }
 603                 lval = strcmp(lstr,rstr);
 604                 rval = 0;
 605         }
 606
 607         switch (op) {
 608         case C_LESSTHAN:        return (lval < rval);
 609         case C_LESSOREQ:        return (lval <= rval);
 610         case C_EQUAL:           return (lval == rval);
 611         case C_DIFFERENT:       return (lval != rval);
 612         case C_GREATEROREQ:     return (lval >= rval);
 613         case C_GREATERTHAN:     return (lval > rval);
 614         default:
 615                 return -1;
 616         }
 617 }
 618
 619 /*
 620  * Evaluate an AST in the current context to one of:
 621  *      true=1
 622  *      false=0
 623  *      error=-1
 624  * It's up to the caller whether error is functionally the same as false.
 625  * Note that even T_NUMBER gets squeezed down to these three values.  The
 626  * only thing numbers are used for is comparing against other numbers to
 627  * yield a boolean for the query or replication-policy code.  If you want
 628  * something that returns a number, this is the wrong language for it.
 629  */
 630
 631 int
 632 eval (const value_t *v, const getter_t *oget, const getter_t *sget)
 633 {
 634         int              res;
 635         const char      *str;
 636
 637         switch (v->type) {
 638         case T_NUMBER:
 639                 return v->as_num != 0;
 640         case T_STRING:
 641                 return v->as_str && *v->as_str;
 642         case T_OFIELD:
 643                 str = CALL_GETTER(oget,v->as_str);
 644                 return str && *str;
 645         case T_SFIELD:
 646                 str = CALL_GETTER(sget,v->as_str);
 647                 return str && *str;
 648         case T_LINK:
 649                 str = string_value(v->as_tree.left,oget,sget);
 650                 if (str) {
 651                         str = follow_link(str,(char *)v->as_tree.right);
 652                 }
 653                 return str && *str;
 654         case T_COMP:
 655                 return compare(v->as_tree.left,(comp_t)v->as_tree.op,
 656                         v->as_tree.right, oget, sget);
 657         case T_NOT:
 658                 res = eval(v->as_tree.left,oget,sget);
 659                 return (res >= 0) ? !res : res;
 660         case T_AND:
 661                 res = eval(v->as_tree.left,oget,sget);
 662                 if (res > 0) {
 663                         res = eval(v->as_tree.right,oget,sget);
 664                 }
 665                 return res;
 666         case T_OR:
 667                 res = eval(v->as_tree.left,oget,sget);
 668                 if (res > 0) {
 669                         return res;
 670                 }
 671                 return eval(v->as_tree.right,oget,sget);
 672         default:
 673                 return -1;
 674         }
 675 }
 676
 677 #ifdef PARSER_UNIT_TEST
 678 int
 679 main (int argc, char **argv)
 680 {
 681   int fail = 0;
 682   unsigned int i;
 683   for (i = 1; i < argc; ++i)
 684     {
 685       value_t *expr = parse (argv[i]);
 686       if (!expr)
 687         {
 688           printf ("could not parse '%s'\n", argv[i]);
 689           fail = 1;
 690           goto next;
 691         }
 692
 693       print_value (expr);
 694
 695       const char *str = string_value (expr, &unit_oget, &unit_sget);
 696       if (str)
 697         {
 698           printf ("s= %s\n", str);
 699           goto next;
 700         }
 701       printf ("d= %d\n", eval (expr, &unit_oget, &unit_sget));
 702
 703     next:
 704       free_value (expr);
 705     }
 706
 707   return fail;
 708 }
 709 #endif