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