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