query.leg

   1 %{
   2 /* Copyright (C) 2010 Red Hat, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 #include <ctype.h>
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <time.h>
  21 #include <error.h>
  22 #include "query.h"
  23
  24 const char *arg_buf;
  25 int arg_off;
  26 int arg_len;
  27 value_t **cur_expr;
  28
  29 static void
  30 xalloc_die (void)
  31 {
  32   error (EXIT_FAILURE, 0, "%s", "memory exhausted");
  33
  34   /* The `noreturn' cannot be given to error, since it may return if
  35      its first argument is 0.  To help compilers understand the
  36      xalloc_die does not return, call abort.  Also, the abort is a
  37      safety feature if exit_failure is 0 (which shouldn't happen).  */
  38   abort ();
  39 }
  40
  41 /* Allocate N bytes of memory dynamically, with error checking.  */
  42 static void *
  43 xmalloc (size_t n)
  44 {
  45   void *p = malloc (n);
  46   if (!p && n != 0)
  47     xalloc_die ();
  48   return p;
  49 }
  50
  51 /* Change the size of an allocated block of memory P to N bytes,
  52    with error checking.  */
  53 static void *
  54 xrealloc (void *p, size_t n)
  55 {
  56   p = realloc (p, n);
  57   if (!p && n != 0)
  58     xalloc_die ();
  59   return p;
  60 }
  61
  62 /* Clone an object P of size S, with error checking.  There's no need
  63    for xnmemdup (P, N, S), since xmemdup (P, N * S) works without any
  64    need for an arithmetic overflow check.  */
  65 static void *
  66 xmemdup (void const *p, size_t s)
  67 {
  68   return memcpy (xmalloc (s), p, s);
  69 }
  70
  71 /* Clone STRING.  */
  72 static char *
  73 xstrdup (char const *string)
  74 {
  75   return xmemdup (string, strlen (string) + 1);
  76 }
  77
  78 /* TBD: use separate function to parse dates differently */
  79 value_t *
  80 make_number (const char *text)
  81 {
  82         value_t *tmp = malloc(sizeof(*tmp));
  83
  84         if (tmp) {
  85                 tmp->type = T_NUMBER;
  86                 tmp->as_num = strtoll(text,NULL,10);
  87                 tmp->resolved = NULL;
  88         }
  89
  90         return tmp;
  91 }
  92
  93 value_t *
  94 make_string (const char *text, type_t t)
  95 {
  96         value_t *tmp = malloc(sizeof(*tmp));
  97
  98         if (tmp) {
  99                 tmp->type = t;
 100                 tmp->as_str = xstrdup(text);
 101                 tmp->resolved = NULL;
 102         }
 103
 104         return tmp;
 105 }
 106
 107 value_t *
 108 make_tree (type_t t, value_t *left, value_t *right)
 109 {
 110         value_t *tmp = malloc(sizeof(*tmp));
 111
 112         if (tmp) {
 113                 tmp->type = t;
 114                 tmp->as_tree.left = left;
 115                 tmp->as_tree.right = right;
 116                 tmp->resolved = NULL;
 117         }
 118
 119         return tmp;
 120 }
 121
 122 value_t *
 123 make_comp (comp_t c, value_t *left, value_t *right)
 124 {
 125         value_t *tmp = make_tree(T_COMP,left,right);
 126
 127         if (tmp) {
 128                 tmp->as_tree.op = c;
 129         }
 130
 131         return tmp;
 132 }
 133
 134 value_t *
 135 make_link (value_t *left, value_t *right)
 136 {
 137         char    *copy;
 138
 139         copy = xstrdup((char *)right);
 140         if (!copy) {
 141                 return NULL;
 142         }
 143
 144         return make_tree(T_LINK,left,(value_t *)copy);
 145 }
 146
 147 #if defined(UNIT_TEST)
 148 struct { char *name; char *value; } hacked_obj_fields[] = {
 149         /* Fake object fields for generic unit testing. */
 150         { "a", "2" }, { "b", "7" }, { "c", "11" },
 151         /* This one's here to test links (e.g. $template.owner.name). */
 152         { "template", "templates/the_tmpl" },
 153         { NULL }
 154 };
 155
 156 /* Fake out the eval code for unit testing. */
 157 const char *
 158 unit_oget_func (void * notused, const char *text)
 159 {
 160         int i;
 161
 162         for (i = 0; hacked_obj_fields[i].name; ++i) {
 163                 if (!strcmp(hacked_obj_fields[i].name,text)) {
 164                         return xstrdup(hacked_obj_fields[i].value);
 165                 }
 166         }
 167
 168         return NULL;
 169 }
 170 getter_t unit_oget = { unit_oget_func };
 171
 172 /*
 173  * Same as above, but the site-field stuff is so similar to the object-field
 174  * stuff that it's not worth exercising too much separately.
 175  */
 176 const char *
 177 unit_sget_func (void * notused, const char *text)
 178 {
 179         return "never";
 180 }
 181 getter_t unit_sget = { unit_sget_func };
 182
 183 /* Fake links from an object/key tuple to an object/key string. */
 184 struct { char *obj; char *key; char *value; } hacked_links[] = {
 185         { "templates/the_tmpl", "owner", "users/the_user" },
 186         { "users/the_user", "name", "Jeff Darcy" },
 187         { NULL }
 188 };
 189
 190 char *
 191 follow_link (const char *object, const char *key)
 192 {
 193         unsigned int i;
 194
 195         for (i = 0; hacked_links[i].obj; ++i) {
 196                 if (strcmp(object,hacked_links[i].obj)) {
 197                         continue;
 198                 }
 199                 if (strcmp(key,hacked_links[i].key)) {
 200                         continue;
 201                 }
 202                 return hacked_links[i].value;
 203         }
 204
 205         return NULL;
 206 }
 207 #else
 208 extern char *follow_link (const char *object, const char *key);
 209 #endif
 210
 211 /*
 212  * Return the string value of an expression for comparison or display, iff
 213  * all component parts are string-valued themselves.  That excludes numbers
 214  * and booleans.
 215  */
 216 const char *
 217 string_value (value_t *v, getter_t *oget, getter_t *sget)
 218 {
 219         const char      *left;
 220
 221         switch (v->type) {
 222         case T_STRING:
 223                 return v->as_str;
 224         case T_OFIELD:
 225                 if (!v->resolved) {
 226                         v->resolved = oget
 227                                 ? CALL_GETTER(oget,v->as_str) : NULL;
 228                 }
 229                 return v->resolved;
 230         case T_SFIELD:
 231                 return sget ? CALL_GETTER(sget,v->as_str) : NULL;
 232         case T_LINK:
 233                 if (!v->resolved) {
 234                         left = string_value(v->as_tree.left,oget,sget);
 235                         if (left) {
 236                                 v->resolved = follow_link((char *)left,
 237                                         (char *)v->as_tree.right);
 238                         }
 239                 }
 240                 return v->resolved;
 241         default:
 242                 return NULL;
 243         }
 244 }
 245
 246 /*
 247  * Check whether a string looks like a simple decimal number.  There's
 248  * probably a library function for this somewhere.
 249  */
 250 int
 251 is_ok_number (const char *a_str)
 252 {
 253         const char      *p;
 254
 255         if (!a_str) {
 256                 return 0;
 257         }
 258
 259         for (p = a_str; *p; ++p) {
 260                 if (!isdigit(*p)) {
 261                         return 0;
 262                 }
 263         }
 264
 265         return 1;
 266 }
 267
 268 /*
 269  * Comparisons are a bit messy.  If both sides are numbers, strings that look
 270  * like numbers, or expressions that evaluate to numbers (booleans evaluate
 271  * to 0/1), then we do a numeric comparison.  Otherwise, if both sides
 272  * evaluate to strings, we attempt a string comparison.   That's the logic,
 273  * but the code is actually structured a different way to allow re-use of
 274  * common operator-specific code at the end for both cases.
 275  */
 276 int
 277 compare (value_t *left, comp_t op, value_t *right,
 278          getter_t *oget, getter_t *sget)
 279 {
 280         const char      *lstr;
 281         const char      *rstr;
 282         int              lval = 0; // solely to placate gcc
 283         int              rval;
 284         int              num_ok = 1;
 285
 286         lstr = string_value(left,oget,sget);
 287         rstr = string_value(right,oget,sget);
 288
 289         if (left->type == T_NUMBER) {
 290                 lval = left->as_num;
 291         }
 292         else if (lstr) {
 293                 if (is_ok_number(lstr)) {
 294                         lval = strtoll(lstr,NULL,0);
 295                 }
 296                 else {
 297                         num_ok = 0;
 298                 }
 299         }
 300         else {
 301                 lval = eval(left,oget,sget);
 302                 if (lval < 0) {
 303                         return lval;
 304                 }
 305         }
 306
 307         if (right->type == T_NUMBER) {
 308                 rval = right->as_num;
 309         }
 310         else if (rstr) {
 311                 if (is_ok_number(rstr)) {
 312                         rval = strtoll(rstr,NULL,0);
 313                 }
 314                 else {
 315                         num_ok = 0;
 316                 }
 317         }
 318         else {
 319                 rval = eval(right,oget,sget);
 320                 if (rval < 0) {
 321                         return rval;
 322                 }
 323         }
 324
 325         /*
 326          * Strcmp returns -1/0/1, but -1 for us would mean an error and
 327          * which of 0/1 we return depends on which comparison operatoer
 328          * we're dealing with.  Therefore, we stick the strcmp result on
 329          * the left side and let the switch below do an operator-appropriate
 330          * compare against zero on the right.
 331          */
 332         if (!num_ok) {
 333                 if (!lstr || !rstr) {
 334                         return -1;
 335                 }
 336                 lval = strcmp(lstr,rstr);
 337                 rval = 0;
 338         }
 339
 340         switch (op) {
 341         case C_LESSTHAN:        return (lval < rval);
 342         case C_LESSOREQ:        return (lval <= rval);
 343         case C_EQUAL:           return (lval == rval);
 344         case C_DIFFERENT:       return (lval != rval);
 345         case C_GREATEROREQ:     return (lval >= rval);
 346         case C_GREATERTHAN:     return (lval > rval);
 347         default:
 348                 return -1;
 349         }
 350 }
 351
 352 void
 353 _print_value (const value_t *v, int level)
 354 {
 355         if (!v) {
 356                 printf("%*sNULL\n",level,"");
 357                 return;
 358         }
 359
 360         switch (v->type) {
 361         case T_NUMBER:
 362                 printf("%*sNUMBER %lld\n",level,"",v->as_num);
 363                 break;
 364         case T_STRING:
 365                 printf("%*sSTRING %s\n",level,"",v->as_str);
 366                 break;
 367         case T_OFIELD:
 368 #if defined(UNIT_TEST)
 369                 printf("%*sOBJECT FIELD %s (%s)\n",level,"",v->as_str,
 370                         unit_oget_func(NULL,v->as_str));
 371 #else
 372                 printf("%*sOBJECT FIELD %s\n",level,"",v->as_str);
 373 #endif
 374                 break;
 375         case T_SFIELD:
 376 #if defined(UNIT_TEST)
 377                 printf("%*sSERVER FIELD %s (%s)\n",level,"",v->as_str,
 378                         unit_sget_func(NULL,v->as_str));
 379 #else
 380                 printf("%*sSERVER FIELD %s\n",level,"",v->as_str);
 381 #endif
 382                 break;
 383         case T_COMP:
 384                 printf("%*sCOMPARISON\n",level,"");
 385                 _print_value(v->as_tree.left,level+2);
 386                 _print_value(v->as_tree.right,level+2);
 387                 break;
 388         case T_NOT:
 389                 printf("%*sNOT\n",level,"");
 390                 _print_value(v->as_tree.left,level+2);
 391                 break;
 392         case T_AND:
 393                 printf("%*sAND\n",level,"");
 394                 _print_value(v->as_tree.left,level+2);
 395                 _print_value(v->as_tree.right,level+2);
 396                 break;
 397         case T_OR:
 398                 printf("%*sOR\n",level,"");
 399                 _print_value(v->as_tree.left,level+2);
 400                 _print_value(v->as_tree.right,level+2);
 401                 break;
 402         case T_LINK:
 403                 printf("%*sLINK\n",level,"");
 404                 _print_value(v->as_tree.left,level+2);
 405                 printf("%*sDEST FIELD %s\n",level+2,"",
 406                         (char *)v->as_tree.right);
 407                 break;
 408         default:
 409                 printf("%*sUNKNOWN %d\n",level,"",v->type);
 410         }
 411 }
 412
 413 void
 414 print_value (const value_t *v)
 415 {
 416         _print_value(v,0);
 417 }
 418
 419 void
 420 free_value (value_t *v)
 421 {
 422         if (!v) {
 423                 return;
 424         }
 425
 426         free((char *)v->resolved);
 427
 428         switch (v->type) {
 429         case T_STRING:
 430         case T_OFIELD:
 431         case T_SFIELD:
 432                 free(v->as_str);
 433                 free(v);
 434                 break;
 435         case T_LINK:
 436                 free_value(v->as_tree.left);
 437                 free(v->as_tree.right);
 438                 free(v);
 439                 break;
 440         case T_COMP:
 441         case T_AND:
 442         case T_OR:
 443                 free_value(v->as_tree.right);
 444                 /* Fall through. */
 445         case T_NOT:
 446                 free_value(v->as_tree.left);
 447                 /* Fall through. */
 448         default:
 449                 free(v);
 450         }
 451 }
 452
 453 /*
 454  * Evaluate an AST in the current context to one of:
 455  *      true=1
 456  *      false=0
 457  *      error=-1
 458  * It's up to the caller whether error is functionally the same as false.
 459  * Note that even T_NUMBER gets squeezed down to these three values.  The
 460  * only thing numbers are used for is comparing against other numbers to
 461  * yield a boolean for the query or replication-policy code.  If you want
 462  * something that returns a number, this is the wrong language for it.
 463  */
 464
 465 int
 466 eval (const value_t *v, getter_t *oget, getter_t *sget)
 467 {
 468         int              res;
 469         const char      *str;
 470
 471         switch (v->type) {
 472         case T_NUMBER:
 473                 return v->as_num != 0;
 474         case T_STRING:
 475                 return v->as_str && *v->as_str;
 476         case T_OFIELD:
 477                 str = CALL_GETTER(oget,v->as_str);
 478                 return str && *str;
 479         case T_SFIELD:
 480                 str = CALL_GETTER(sget,v->as_str);
 481                 return str && *str;
 482         case T_LINK:
 483                 str = string_value(v->as_tree.left,oget,sget);
 484                 if (str) {
 485                         str = follow_link(str,(char *)v->as_tree.right);
 486                 }
 487                 return str && *str;
 488         case T_COMP:
 489                 return compare(v->as_tree.left,(comp_t)v->as_tree.op,
 490                         v->as_tree.right, oget, sget);
 491         case T_NOT:
 492                 res = eval(v->as_tree.left,oget,sget);
 493                 return (res >= 0) ? !res : res;
 494         case T_AND:
 495                 res = eval(v->as_tree.left,oget,sget);
 496                 if (res > 0) {
 497                         res = eval(v->as_tree.right,oget,sget);
 498                 }
 499                 return res;
 500         case T_OR:
 501                 res = eval(v->as_tree.left,oget,sget);
 502                 if (res > 0) {
 503                         return res;
 504                 }
 505                 return eval(v->as_tree.right,oget,sget);
 506         default:
 507                 return -1;
 508         }
 509 }
 510
 511 #define YY_INPUT(buf,result,max) {                                        \
 512         result = (arg_off < arg_len) ? (*buf = arg_buf[arg_off++], 1)     \
 513                 : (arg_off == arg_len) ? (*buf = '\n', ++arg_off, 1) : 0; \
 514 }
 515
 516 #define YYSTYPE value_t *
 517 %}
 518
 519 Stmt = - BoolExpr - EOL { *cur_expr = $$; }
 520      | ( !EOL . )* EOL
 521
 522 BoolExpr = l:NotExpr
 523         ( ( - AND - r:NotExpr )
 524                 { $$ = l = make_tree(T_AND,l,r); }
 525         | ( - OR - r:NotExpr )
 526                 { $$ = l = make_tree(T_OR,l,r); } )*
 527
 528 NotExpr = CompExpr -
 529         | NOT - e:CompExpr - { $$ = make_tree(T_NOT,e,NULL); }
 530
 531 CompExpr = l:Atom
 532          ( ( - LESS - r:Atom { $$ = make_comp(C_LESSTHAN,l,r); } )
 533          | ( - LESS EQUAL - r:Atom { $$ = make_comp(C_LESSOREQ,l,r); } )
 534          | ( - EQUAL EQUAL - r:Atom { $$ = make_comp(C_EQUAL,l,r); } )
 535          | ( - NOT EQUAL - r:Atom { $$ = make_comp(C_DIFFERENT,l,r); } )
 536          | ( - GREATER EQUAL - r:Atom { $$ = make_comp(C_GREATEROREQ,l,r); } )
 537          | ( - GREATER - r:Atom { $$ = make_comp(C_GREATERTHAN,l,r); } ) )?
 538
 539 Atom = ( Literal | LinkField | ParenExpr )
 540
 541 Literal = NUMBER | STRING | TIME
 542
 543 LinkField = f:Field ( DOT i:ID { $$ = f = make_link(f,i); } )*
 544
 545 Field = DOLLAR i:ID { $$ = make_string((char *)i,T_OFIELD); }
 546       | WAFFLE i:ID { $$ = make_string((char *)i,T_SFIELD); }
 547
 548 ParenExpr = OPEN - v:BoolExpr - CLOSE - { $$ = v; }
 549
 550 NUMBER  = < [0-9]+ >            { $$ = make_number(yytext); }
 551 STRING  = '"' < [^"]* > '"'     { $$ = make_string(yytext,T_STRING); }
 552 TIME    = '~' < [^~]* > '~'     { $$ = make_number(yytext); }
 553 ID      = < [a-z_]+ >           { $$ = (YYSTYPE)yytext; }
 554 DOLLAR  = '$'
 555 WAFFLE  = '#'
 556 OPEN    = '('
 557 CLOSE   = ')'
 558 LESS    = '<'
 559 GREATER = '>'
 560 EQUAL   = '='
 561 NOT     = '!'
 562 AND     = '&&'
 563 OR      = '||'
 564 DOT     = '.'
 565
 566 -       = [ \t]*
 567 EOL     = '\n' | '\r\n' | '\r' | ';'
 568
 569 %%
 570
 571 /* TBD: This isn't thread safe. */
 572 value_t *
 573 parse (const char *text)
 574 {
 575         value_t *expr = NULL;
 576
 577         arg_buf = text;
 578         arg_len = strlen(text);
 579         arg_off = 0;
 580         cur_expr = &expr;
 581
 582         while (yyparse()) {
 583         }
 584
 585         return expr;
 586 }
 587
 588 #if defined(UNIT_TEST)
 589 int
 590 main (int argc, char **argv)
 591 {
 592         int              i;
 593         value_t         *expr;
 594         int              res;
 595         const char      *str;
 596         unsigned int     failed = 0;
 597
 598         for (i = 1; i < argc; ++i) {
 599                 expr = parse(argv[i]);
 600                 if (!expr) {
 601                         printf("could not parse '%s'\n",argv[i]);
 602                         ++failed;
 603                         continue;
 604                 }
 605                 print_value(expr);
 606                 str = string_value(expr,&unit_oget,&unit_sget);
 607                 if (str) {
 608                         printf("s= %s\n",str);
 609                         continue;
 610                 }
 611                 res = eval(expr,&unit_oget,&unit_sget);
 612                 printf("d= %d\n",res);
 613         }
 614
 615         return failed;
 616 }
 617 #endif