build/expression.c

   1 /** \ingroup rpmbuild
   2  * \file build/expression.c
   3  *  Simple logical expression parser.
   4  * This module implements a basic expression parser with support for
   5  * integer and string datatypes. For ease of programming, we use the
   6  * top-down "recursive descent" method of parsing. While a
   7  * table-driven bottom-up parser might be faster, it does not really
   8  * matter for the expressions we will be parsing.
   9  *
  10  * Copyright (C) 1998 Tom Dyas <tdyas@eden.rutgers.edu>
  11  * This work is provided under the GPL or LGPL at your choice.
  12  */
  13
  14 #include "system.h"
  15
  16 #include <rpmbuild.h>
  17 #include <rpmlib.h>
  18
  19 #include "debug.h"
  20
  21 /* #define DEBUG_PARSER 1 */
  22
  23 #ifdef DEBUG_PARSER
  24 #include <stdio.h>
  25 #define DEBUG(x) do { x ; } while (0)
  26 #else
  27 #define DEBUG(x)
  28 #endif
  29
  30 /**
  31  * Encapsulation of a "value"
  32  */
  33 typedef struct _value {
  34   enum { VALUE_TYPE_INTEGER, VALUE_TYPE_STRING } type;
  35   union {
  36     const char *s;
  37     int i;
  38   } data;
  39 } *Value;
  40
  41 /**
  42  */
  43 static Value valueMakeInteger(int i)
  44 {
  45   Value v;
  46
  47   v = (Value) xmalloc(sizeof(struct _value));
  48   v->type = VALUE_TYPE_INTEGER;
  49   v->data.i = i;
  50   return v;
  51 }
  52
  53 /**
  54  */
  55 static Value valueMakeString(/*@only@*/ const char *s)
  56 {
  57   Value v;
  58
  59   v = (Value) xmalloc(sizeof(struct _value));
  60   v->type = VALUE_TYPE_STRING;
  61   v->data.s = s;
  62   return v;
  63 }
  64
  65 /**
  66  */
  67 static void valueFree( /*@only@*/ Value v)
  68 {
  69   if (v) {
  70     if (v->type == VALUE_TYPE_STRING)
  71         v->data.s = _free(v->data.s);
  72     v = _free(v);
  73   }
  74 }
  75
  76 #ifdef DEBUG_PARSER
  77 static void valueDump(const char *msg, Value v, FILE *fp)
  78 {
  79   if (msg)
  80     fprintf(fp, "%s ", msg);
  81   if (v) {
  82     if (v->type == VALUE_TYPE_INTEGER)
  83       fprintf(fp, "INTEGER %d\n", v->data.i);
  84     else
  85       fprintf(fp, "STRING '%s'\n", v->data.s);
  86   } else
  87     fprintf(fp, "NULL\n");
  88 }
  89 #endif
  90
  91 #define valueIsInteger(v) ((v)->type == VALUE_TYPE_INTEGER)
  92 #define valueIsString(v) ((v)->type == VALUE_TYPE_STRING)
  93 #define valueSameType(v1,v2) ((v1)->type == (v2)->type)
  94
  95
  96 /**
  97  * Parser state.
  98  */
  99 typedef struct _parseState {
 100   /*@owned@*/ char *str;        /*!< expression string */
 101   /*@dependent@*/ char *p;      /*!< current position in expression string */
 102   int nextToken;                /*!< current lookahead token */
 103   Value tokenValue;             /*!< valid when TOK_INTEGER or TOK_STRING */
 104   Spec spec;                    /*!< spec file that we are parsing inside of */
 105 } *ParseState;
 106
 107
 108 /**
 109  * \name Parser tokens
 110  */
 111 /*@{*/
 112 #define TOK_EOF          1
 113 #define TOK_INTEGER      2
 114 #define TOK_STRING       3
 115 #define TOK_IDENTIFIER   4
 116 #define TOK_ADD          5
 117 #define TOK_MINUS        6
 118 #define TOK_MULTIPLY     7
 119 #define TOK_DIVIDE       8
 120 #define TOK_OPEN_P       9
 121 #define TOK_CLOSE_P     10
 122 #define TOK_EQ          11
 123 #define TOK_NEQ         12
 124 #define TOK_LT          13
 125 #define TOK_LE          14
 126 #define TOK_GT          15
 127 #define TOK_GE          16
 128 #define TOK_NOT         17
 129 #define TOK_LOGICAL_AND 18
 130 #define TOK_LOGICAL_OR  19
 131 /*@}*/
 132
 133 #define EXPRBUFSIZ      BUFSIZ
 134
 135 #if defined(DEBUG_PARSER)
 136 typedef struct exprTokTableEntry {
 137     const char *name;
 138     int val;
 139 } ETTE_t;
 140
 141 ETTE_t exprTokTable[] = {
 142     { "EOF",    TOK_EOF },
 143     { "I",      TOK_INTEGER },
 144     { "S",      TOK_STRING },
 145     { "ID",     TOK_IDENTIFIER },
 146     { "+",      TOK_ADD },
 147     { "-",      TOK_MINUS },
 148     { "*",      TOK_MULTIPLY },
 149     { "/",      TOK_DIVIDE },
 150     { "( ",     TOK_OPEN_P },
 151     { " )",     TOK_CLOSE_P },
 152     { "==",     TOK_EQ },
 153     { "!=",     TOK_NEQ },
 154     { "<",      TOK_LT },
 155     { "<=",     TOK_LE },
 156     { ">",      TOK_GT },
 157     { ">=",     TOK_GE },
 158     { "!",      TOK_NOT },
 159     { "&&",     TOK_LOGICAL_AND },
 160     { "||",     TOK_LOGICAL_OR },
 161     { NULL, 0 }
 162 };
 163
 164 static const char *prToken(int val)
 165 {
 166     ETTE_t *et;
 167
 168     for (et = exprTokTable; et->name != NULL; et++) {
 169         if (val == et->val)
 170             return et->name;
 171     }
 172     return "???";
 173 }
 174 #endif  /* DEBUG_PARSER */
 175
 176 /**
 177  * @param state         expression parser state
 178  */
 179 static int rdToken(ParseState state)
 180 {
 181   int token;
 182   Value v = NULL;
 183   char *p = state->p;
 184
 185   /* Skip whitespace before the next token. */
 186   while (*p && xisspace(*p)) p++;
 187
 188   switch (*p) {
 189   case '\0':
 190     token = TOK_EOF;
 191     p--;
 192     break;
 193   case '+':
 194     token = TOK_ADD;
 195     break;
 196   case '-':
 197     token = TOK_MINUS;
 198     break;
 199   case '*':
 200     token = TOK_MULTIPLY;
 201     break;
 202   case '/':
 203     token = TOK_DIVIDE;
 204     break;
 205   case '(':
 206     token = TOK_OPEN_P;
 207     break;
 208   case ')':
 209     token = TOK_CLOSE_P;
 210     break;
 211   case '=':
 212     if (p[1] == '=') {
 213       token = TOK_EQ;
 214       p++;
 215     } else {
 216       rpmError(RPMERR_BADSPEC, _("syntax error while parsing ==\n"));
 217       return -1;
 218     }
 219     break;
 220   case '!':
 221     if (p[1] == '=') {
 222       token = TOK_NEQ;
 223       p++;
 224     } else
 225       token = TOK_NOT;
 226     break;
 227   case '<':
 228     if (p[1] == '=') {
 229       token = TOK_LE;
 230       p++;
 231     } else
 232       token = TOK_LT;
 233     break;
 234   case '>':
 235     if (p[1] == '=') {
 236       token = TOK_GE;
 237       p++;
 238     } else
 239       token = TOK_GT;
 240     break;
 241   case '&':
 242     if (p[1] == '&') {
 243       token = TOK_LOGICAL_AND;
 244       p++;
 245     } else {
 246       rpmError(RPMERR_BADSPEC, _("syntax error while parsing &&\n"));
 247       return -1;
 248     }
 249     break;
 250   case '|':
 251     if (p[1] == '|') {
 252       token = TOK_LOGICAL_OR;
 253       p++;
 254     } else {
 255       rpmError(RPMERR_BADSPEC, _("syntax error while parsing ||\n"));
 256       return -1;
 257     }
 258     break;
 259
 260   default:
 261     if (xisdigit(*p)) {
 262       char temp[EXPRBUFSIZ], *t = temp;
 263
 264       while (*p && xisdigit(*p))
 265         *t++ = *p++;
 266       *t++ = '\0';
 267       p--;
 268
 269       token = TOK_INTEGER;
 270       v = valueMakeInteger(atoi(temp));
 271
 272     } else if (xisalpha(*p)) {
 273       char temp[EXPRBUFSIZ], *t = temp;
 274
 275       while (*p && (xisalnum(*p) || *p == '_'))
 276         *t++ = *p++;
 277       *t++ = '\0';
 278       p--;
 279
 280       token = TOK_IDENTIFIER;
 281       v = valueMakeString( xstrdup(temp) );
 282
 283     } else if (*p == '\"') {
 284       char temp[EXPRBUFSIZ], *t = temp;
 285
 286       p++;
 287       while (*p && *p != '\"')
 288         *t++ = *p++;
 289       *t++ = '\0';
 290
 291       token = TOK_STRING;
 292       v = valueMakeString( rpmExpand(temp, NULL) );
 293
 294     } else {
 295       rpmError(RPMERR_BADSPEC, _("parse error in expression\n"));
 296       return -1;
 297     }
 298   }
 299
 300   state->p = p + 1;
 301   state->nextToken = token;
 302   state->tokenValue = v;
 303
 304   DEBUG(printf("rdToken: \"%s\" (%d)\n", prToken(token), token));
 305   DEBUG(valueDump("rdToken:", state->tokenValue, stdout));
 306
 307   return 0;
 308 }
 309
 310 static Value doLogical(ParseState state);
 311
 312 /**
 313  * @param state         expression parser state
 314  */
 315 static Value doPrimary(ParseState state)
 316 {
 317   Value v;
 318
 319   DEBUG(printf("doPrimary()\n"));
 320
 321   switch (state->nextToken) {
 322   case TOK_OPEN_P:
 323     if (rdToken(state))
 324       return NULL;
 325     v = doLogical(state);
 326     if (state->nextToken != TOK_CLOSE_P) {
 327       rpmError(RPMERR_BADSPEC, _("unmatched (\n"));
 328       return NULL;
 329     }
 330     break;
 331
 332   case TOK_INTEGER:
 333   case TOK_STRING:
 334     v = state->tokenValue;
 335     if (rdToken(state))
 336       return NULL;
 337     break;
 338
 339   case TOK_IDENTIFIER: {
 340     const char *name = state->tokenValue->data.s;
 341
 342     v = valueMakeString( rpmExpand(name, NULL) );
 343     if (rdToken(state))
 344       return NULL;
 345     break;
 346   }
 347
 348   case TOK_MINUS:
 349     if (rdToken(state))
 350       return NULL;
 351
 352     v = doPrimary(state);
 353     if (v == NULL)
 354       return NULL;
 355
 356     if (! valueIsInteger(v)) {
 357       rpmError(RPMERR_BADSPEC, _("- only on numbers\n"));
 358       return NULL;
 359     }
 360
 361     v = valueMakeInteger(- v->data.i);
 362     break;
 363
 364   case TOK_NOT:
 365     if (rdToken(state))
 366       return NULL;
 367
 368     v = doPrimary(state);
 369     if (v == NULL)
 370       return NULL;
 371
 372     if (! valueIsInteger(v)) {
 373       rpmError(RPMERR_BADSPEC, _("! only on numbers\n"));
 374       return NULL;
 375     }
 376
 377     v = valueMakeInteger(! v->data.i);
 378     break;
 379   default:
 380     return NULL;
 381     /*@notreached@*/ break;
 382   }
 383
 384   DEBUG(valueDump("doPrimary:", v, stdout));
 385   return v;
 386 }
 387
 388 /**
 389  * @param state         expression parser state
 390  */
 391 static Value doMultiplyDivide(ParseState state)
 392 {
 393   Value v1, v2 = NULL;
 394
 395   DEBUG(printf("doMultiplyDivide()\n"));
 396
 397   v1 = doPrimary(state);
 398   if (v1 == NULL)
 399     return NULL;
 400
 401   while (state->nextToken == TOK_MULTIPLY
 402          || state->nextToken == TOK_DIVIDE) {
 403     int op = state->nextToken;
 404
 405     if (rdToken(state))
 406       return NULL;
 407
 408     if (v2) valueFree(v2);
 409
 410     v2 = doPrimary(state);
 411     if (v2 == NULL)
 412       return NULL;
 413
 414     if (! valueSameType(v1, v2)) {
 415       rpmError(RPMERR_BADSPEC, _("types must match\n"));
 416       return NULL;
 417     }
 418
 419     if (valueIsInteger(v1)) {
 420       int i1 = v1->data.i, i2 = v2->data.i;
 421
 422       valueFree(v1);
 423       if (op == TOK_MULTIPLY)
 424         v1 = valueMakeInteger(i1 * i2);
 425       else
 426         v1 = valueMakeInteger(i1 / i2);
 427     } else {
 428       rpmError(RPMERR_BADSPEC, _("* / not suported for strings\n"));
 429       return NULL;
 430     }
 431   }
 432
 433   if (v2) valueFree(v2);
 434   return v1;
 435 }
 436
 437 /**
 438  * @param state         expression parser state
 439  */
 440 static Value doAddSubtract(ParseState state)
 441 {
 442   Value v1, v2 = NULL;
 443
 444   DEBUG(printf("doAddSubtract()\n"));
 445
 446   v1 = doMultiplyDivide(state);
 447   if (v1 == NULL)
 448     return NULL;
 449
 450   while (state->nextToken == TOK_ADD || state->nextToken == TOK_MINUS) {
 451     int op = state->nextToken;
 452
 453     if (rdToken(state))
 454       return NULL;
 455
 456     if (v2) valueFree(v2);
 457
 458     v2 = doMultiplyDivide(state);
 459     if (v2 == NULL)
 460       return NULL;
 461
 462     if (! valueSameType(v1, v2)) {
 463       rpmError(RPMERR_BADSPEC, _("types must match\n"));
 464       return NULL;
 465     }
 466
 467     if (valueIsInteger(v1)) {
 468       int i1 = v1->data.i, i2 = v2->data.i;
 469
 470       valueFree(v1);
 471       if (op == TOK_ADD)
 472         v1 = valueMakeInteger(i1 + i2);
 473       else
 474         v1 = valueMakeInteger(i1 - i2);
 475     } else {
 476       char *copy;
 477
 478       if (op == TOK_MINUS) {
 479         rpmError(RPMERR_BADSPEC, _("- not suported for strings\n"));
 480         return NULL;
 481       }
 482
 483       copy = xmalloc(strlen(v1->data.s) + strlen(v2->data.s) + 1);
 484       (void) stpcpy( stpcpy(copy, v1->data.s), v2->data.s);
 485
 486       valueFree(v1);
 487       v1 = valueMakeString(copy);
 488     }
 489   }
 490
 491   if (v2) valueFree(v2);
 492   return v1;
 493 }
 494
 495 /**
 496  * @param state         expression parser state
 497  */
 498 static Value doRelational(ParseState state)
 499 {
 500   Value v1, v2 = NULL;
 501
 502   DEBUG(printf("doRelational()\n"));
 503
 504   v1 = doAddSubtract(state);
 505   if (v1 == NULL)
 506     return NULL;
 507
 508   while (state->nextToken >= TOK_EQ && state->nextToken <= TOK_GE) {
 509     int op = state->nextToken;
 510
 511     if (rdToken(state))
 512       return NULL;
 513
 514     if (v2) valueFree(v2);
 515
 516     v2 = doAddSubtract(state);
 517     if (v2 == NULL)
 518       return NULL;
 519
 520     if (! valueSameType(v1, v2)) {
 521       rpmError(RPMERR_BADSPEC, _("types must match\n"));
 522       return NULL;
 523     }
 524
 525     if (valueIsInteger(v1)) {
 526       int i1 = v1->data.i, i2 = v2->data.i, r = 0;
 527       switch (op) {
 528       case TOK_EQ:
 529         r = (i1 == i2);
 530         break;
 531       case TOK_NEQ:
 532         r = (i1 != i2);
 533         break;
 534       case TOK_LT:
 535         r = (i1 < i2);
 536         break;
 537       case TOK_LE:
 538         r = (i1 <= i2);
 539         break;
 540       case TOK_GT:
 541         r = (i1 > i2);
 542         break;
 543       case TOK_GE:
 544         r = (i1 >= i2);
 545         break;
 546       default:
 547         break;
 548       }
 549       valueFree(v1);
 550       v1 = valueMakeInteger(r);
 551     } else {
 552       const char * s1 = v1->data.s;
 553       const char * s2 = v2->data.s;
 554       int r = 0;
 555       switch (op) {
 556       case TOK_EQ:
 557         r = (strcmp(s1,s2) == 0);
 558         break;
 559       case TOK_NEQ:
 560         r = (strcmp(s1,s2) != 0);
 561         break;
 562       case TOK_LT:
 563         r = (strcmp(s1,s2) < 0);
 564         break;
 565       case TOK_LE:
 566         r = (strcmp(s1,s2) <= 0);
 567         break;
 568       case TOK_GT:
 569         r = (strcmp(s1,s2) > 0);
 570         break;
 571       case TOK_GE:
 572         r = (strcmp(s1,s2) >= 0);
 573         break;
 574       default:
 575         break;
 576       }
 577       valueFree(v1);
 578       v1 = valueMakeInteger(r);
 579     }
 580   }
 581
 582   if (v2) valueFree(v2);
 583   return v1;
 584 }
 585
 586 /**
 587  * @param state         expression parser state
 588  */
 589 static Value doLogical(ParseState state)
 590 {
 591   Value v1, v2 = NULL;
 592
 593   DEBUG(printf("doLogical()\n"));
 594
 595   v1 = doRelational(state);
 596   if (v1 == NULL)
 597     return NULL;
 598
 599   while (state->nextToken == TOK_LOGICAL_AND
 600          || state->nextToken == TOK_LOGICAL_OR) {
 601     int op = state->nextToken;
 602
 603     if (rdToken(state))
 604       return NULL;
 605
 606     if (v2) valueFree(v2);
 607
 608     v2 = doRelational(state);
 609     if (v2 == NULL)
 610       return NULL;
 611
 612     if (! valueSameType(v1, v2)) {
 613       rpmError(RPMERR_BADSPEC, _("types must match\n"));
 614       return NULL;
 615     }
 616
 617     if (valueIsInteger(v1)) {
 618       int i1 = v1->data.i, i2 = v2->data.i;
 619
 620       valueFree(v1);
 621       if (op == TOK_LOGICAL_AND)
 622         v1 = valueMakeInteger(i1 && i2);
 623       else
 624         v1 = valueMakeInteger(i1 || i2);
 625     } else {
 626       rpmError(RPMERR_BADSPEC, _("&& and || not suported for strings\n"));
 627       return NULL;
 628     }
 629   }
 630
 631   if (v2) valueFree(v2);
 632   return v1;
 633 }
 634
 635 int parseExpressionBoolean(Spec spec, const char *expr)
 636 {
 637   struct _parseState state;
 638   int result = -1;
 639   Value v;
 640
 641   DEBUG(printf("parseExprBoolean(?, '%s')\n", expr));
 642
 643   /* Initialize the expression parser state. */
 644   state.p = state.str = xstrdup(expr);
 645   state.spec = spec;
 646   state.nextToken = 0;
 647   state.tokenValue = NULL;
 648   (void) rdToken(&state);
 649
 650   /* Parse the expression. */
 651   v = doLogical(&state);
 652   if (!v) {
 653     state.str = _free(state.str);
 654     return -1;
 655   }
 656
 657   /* If the next token is not TOK_EOF, we have a syntax error. */
 658   if (state.nextToken != TOK_EOF) {
 659     rpmError(RPMERR_BADSPEC, _("syntax error in expression\n"));
 660     state.str = _free(state.str);
 661     return -1;
 662   }
 663
 664   DEBUG(valueDump("parseExprBoolean:", v, stdout));
 665
 666   switch (v->type) {
 667   case VALUE_TYPE_INTEGER:
 668     result = v->data.i != 0;
 669     break;
 670   case VALUE_TYPE_STRING:
 671     result = v->data.s[0] != '\0';
 672     break;
 673   default:
 674     break;
 675   }
 676
 677   state.str = _free(state.str);
 678   valueFree(v);
 679   return result;
 680 }
 681
 682 char * parseExpressionString(Spec spec, const char *expr)
 683 {
 684   struct _parseState state;
 685   char *result = NULL;
 686   Value v;
 687
 688   DEBUG(printf("parseExprString(?, '%s')\n", expr));
 689
 690   /* Initialize the expression parser state. */
 691   state.p = state.str = xstrdup(expr);
 692   state.spec = spec;
 693   state.nextToken = 0;
 694   state.tokenValue = NULL;
 695   (void) rdToken(&state);
 696
 697   /* Parse the expression. */
 698   v = doLogical(&state);
 699   if (!v) {
 700     state.str = _free(state.str);
 701     return NULL;
 702   }
 703
 704   /* If the next token is not TOK_EOF, we have a syntax error. */
 705   if (state.nextToken != TOK_EOF) {
 706     rpmError(RPMERR_BADSPEC, _("syntax error in expression\n"));
 707     state.str = _free(state.str);
 708     return NULL;
 709   }
 710
 711   DEBUG(valueDump("parseExprString:", v, stdout));
 712
 713   switch (v->type) {
 714   case VALUE_TYPE_INTEGER: {
 715     char buf[128];
 716     sprintf(buf, "%d", v->data.i);
 717     result = xstrdup(buf);
 718   } break;
 719   case VALUE_TYPE_STRING:
 720     result = xstrdup(v->data.s);
 721     break;
 722   default:
 723     break;
 724   }
 725
 726   state.str = _free(state.str);
 727   valueFree(v);
 728   return result;
 729 }