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