expr.c

   1 /*
   2  * Korn expression evaluation
   3  */
   4 /*
   5  * todo: better error handling: if in builtin, should be builtin error, etc.
   6  */
   7
   8 #include "sh.h"
   9 #include <ctype.h>
  10
  11
  12 /* The order of these enums is constrained by the order of opinfo[] */
  13 enum token {
  14         /* some (long) unary operators */
  15         O_PLUSPLUS = 0, O_MINUSMINUS,
  16         /* binary operators */
  17         O_EQ, O_NE,
  18         /* assignments are assumed to be in range O_ASN .. O_BORASN */
  19         O_ASN, O_TIMESASN, O_DIVASN, O_MODASN, O_PLUSASN, O_MINUSASN,
  20                O_LSHIFTASN, O_RSHIFTASN, O_BANDASN, O_BXORASN, O_BORASN,
  21         O_LSHIFT, O_RSHIFT,
  22         O_LE, O_GE, O_LT, O_GT,
  23         O_LAND,
  24         O_LOR,
  25         O_TIMES, O_DIV, O_MOD,
  26         O_PLUS, O_MINUS,
  27         O_BAND,
  28         O_BXOR,
  29         O_BOR,
  30         O_TERN,
  31         O_COMMA,
  32         /* things after this aren't used as binary operators */
  33         /* unary that are not also binaries */
  34         O_BNOT, O_LNOT,
  35         /* misc */
  36         OPEN_PAREN, CLOSE_PAREN, CTERN,
  37         /* things that don't appear in the opinfo[] table */
  38         VAR, LIT, END, BAD
  39     };
  40 #define IS_BINOP(op) (((int)op) >= (int)O_EQ && ((int)op) <= (int)O_COMMA)
  41 #define IS_ASSIGNOP(op) ((int)(op) >= (int)O_ASN && (int)(op) <= (int)O_BORASN)
  42
  43 enum prec {
  44         P_PRIMARY = 0,          /* VAR, LIT, (), ~ ! - + */
  45         P_MULT,                 /* * / % */
  46         P_ADD,                  /* + - */
  47         P_SHIFT,                /* << >> */
  48         P_RELATION,             /* < <= > >= */
  49         P_EQUALITY,             /* == != */
  50         P_BAND,                 /* & */
  51         P_BXOR,                 /* ^ */
  52         P_BOR,                  /* | */
  53         P_LAND,                 /* && */
  54         P_LOR,                  /* || */
  55         P_TERN,                 /* ?: */
  56         P_ASSIGN,               /* = *= /= %= += -= <<= >>= &= ^= |= */
  57         P_COMMA                 /* , */
  58     };
  59 #define MAX_PREC        P_COMMA
  60
  61 struct opinfo {
  62         char            name[4];
  63         int             len;    /* name length */
  64         enum prec       prec;   /* precidence: lower is higher */
  65 };
  66
  67 /* Tokens in this table must be ordered so the longest are first
  68  * (eg, += before +).  If you change something, change the order
  69  * of enum token too.
  70  */
  71 static const struct opinfo opinfo[] = {
  72                 { "++",  2, P_PRIMARY },        /* before + */
  73                 { "--",  2, P_PRIMARY },        /* before - */
  74                 { "==",  2, P_EQUALITY },       /* before = */
  75                 { "!=",  2, P_EQUALITY },       /* before ! */
  76                 { "=",   1, P_ASSIGN },         /* keep assigns in a block */
  77                 { "*=",  2, P_ASSIGN },
  78                 { "/=",  2, P_ASSIGN },
  79                 { "%=",  2, P_ASSIGN },
  80                 { "+=",  2, P_ASSIGN },
  81                 { "-=",  2, P_ASSIGN },
  82                 { "<<=", 3, P_ASSIGN },
  83                 { ">>=", 3, P_ASSIGN },
  84                 { "&=",  2, P_ASSIGN },
  85                 { "^=",  2, P_ASSIGN },
  86                 { "|=",  2, P_ASSIGN },
  87                 { "<<",  2, P_SHIFT },
  88                 { ">>",  2, P_SHIFT },
  89                 { "<=",  2, P_RELATION },
  90                 { ">=",  2, P_RELATION },
  91                 { "<",   1, P_RELATION },
  92                 { ">",   1, P_RELATION },
  93                 { "&&",  2, P_LAND },
  94                 { "||",  2, P_LOR },
  95                 { "*",   1, P_MULT },
  96                 { "/",   1, P_MULT },
  97                 { "%",   1, P_MULT },
  98                 { "+",   1, P_ADD },
  99                 { "-",   1, P_ADD },
 100                 { "&",   1, P_BAND },
 101                 { "^",   1, P_BXOR },
 102                 { "|",   1, P_BOR },
 103                 { "?",   1, P_TERN },
 104                 { ",",   1, P_COMMA },
 105                 { "~",   1, P_PRIMARY },
 106                 { "!",   1, P_PRIMARY },
 107                 { "(",   1, P_PRIMARY },
 108                 { ")",   1, P_PRIMARY },
 109                 { ":",   1, P_PRIMARY },
 110                 { "",    0, P_PRIMARY } /* end of table */
 111             };
 112
 113
 114 typedef struct expr_state Expr_state;
 115 struct expr_state {
 116         const char *expression;         /* expression being evaluated */
 117         const char *tokp;               /* lexical position */
 118         enum token  tok;                /* token from token() */
 119         int         noassign;           /* don't do assigns (for ?:,&&,||) */
 120         struct tbl *val;                /* value from token() */
 121         struct tbl *evaling;            /* variable that is being recursively
 122                                          * expanded (EXPRINEVAL flag set)
 123                                          */
 124 };
 125
 126 enum error_type { ET_UNEXPECTED, ET_BADLIT, ET_RECURSIVE,
 127                   ET_LVALUE, ET_RDONLY, ET_STR };
 128
 129 static void        evalerr  ARGS((Expr_state *es, enum error_type type,
 130                                   const char *str)) GCC_FUNC_ATTR(noreturn);
 131 static struct tbl *evalexpr ARGS((Expr_state *es, enum prec prec));
 132 static void        token    ARGS((Expr_state *es));
 133 static struct tbl *do_ppmm  ARGS((Expr_state *es, enum token op,
 134                                   struct tbl *vasn, bool_t is_prefix));
 135 static void        assign_check ARGS((Expr_state *es, enum token op,
 136                                       struct tbl *vasn));
 137 static struct tbl *tempvar  ARGS((void));
 138 static struct tbl *intvar   ARGS((Expr_state *es, struct tbl *vp));
 139
 140 /*
 141  * parse and evalute expression
 142  */
 143 int
 144 evaluate(const char *expr, long *rval, int error_ok)
 145 {
 146         struct tbl v;
 147         int ret;
 148
 149         v.flag = DEFINED|INTEGER;
 150         v.type = 0;
 151         ret = v_evaluate(&v, expr, error_ok);
 152         *rval = v.val.i;
 153         return ret;
 154 }
 155
 156 /*
 157  * parse and evalute expression, storing result in vp.
 158  */
 159 int
 160 v_evaluate(struct tbl *vp, const char *expr, int error_ok)
 161 {
 162         struct tbl *v;
 163         Expr_state curstate;
 164         Expr_state * const es = &curstate;
 165         int i;
 166
 167         /* save state to allow recursive calls */
 168         curstate.expression = curstate.tokp = expr;
 169         curstate.noassign = 0;
 170         curstate.evaling = (struct tbl *) 0;
 171
 172         newenv(E_ERRH);
 173         i = sigsetjmp(e->jbuf, 0);
 174         if (i) {
 175                 /* Clear EXPRINEVAL in of any variables we were playing with */
 176                 if (curstate.evaling)
 177                         curstate.evaling->flag &= ~EXPRINEVAL;
 178                 quitenv();
 179                 if (i == LAEXPR) {
 180                         if (error_ok == KSH_RETURN_ERROR)
 181                                 return 0;
 182                         errorf(null);
 183                 }
 184                 unwind(i);
 185                 /*NOTREACHED*/
 186         }
 187
 188         token(es);
 189 #if 0 /* ifdef-out to disallow empty expressions to be treated as 0 */
 190         if (es->tok == END) {
 191                 es->tok = LIT;
 192                 es->val = tempvar();
 193         }
 194 #endif /* 0 */
 195         v = intvar(es, evalexpr(es, MAX_PREC));
 196
 197         if (es->tok != END)
 198                 evalerr(es, ET_UNEXPECTED, (char *) 0);
 199
 200         if (vp->flag & INTEGER)
 201                 setint_v(vp, v);
 202         else
 203                 /* can fail if readony */
 204                 setstr(vp, str_val(v), error_ok);
 205
 206         quitenv();
 207
 208         return 1;
 209 }
 210
 211 static void
 212 evalerr(es, type, str)
 213         Expr_state *es;
 214         enum error_type type;
 215         const char *str;
 216 {
 217         char tbuf[2];
 218         const char *s;
 219
 220         switch (type) {
 221         case ET_UNEXPECTED:
 222                 switch (es->tok) {
 223                 case VAR:
 224                         s = es->val->name;
 225                         break;
 226                 case LIT:
 227                         s = str_val(es->val);
 228                         break;
 229                 case END:
 230                         s = "end of expression";
 231                         break;
 232                 case BAD:
 233                         tbuf[0] = *es->tokp;
 234                         tbuf[1] = '\0';
 235                         s = tbuf;
 236                         break;
 237                 default:
 238                         s = opinfo[(int)es->tok].name;
 239                 }
 240                 warningf(TRUE, "%s: unexpected `%s'", es->expression, s);
 241                 break;
 242
 243         case ET_BADLIT:
 244                 warningf(TRUE, "%s: bad number `%s'", es->expression, str);
 245                 break;
 246
 247         case ET_RECURSIVE:
 248                 warningf(TRUE, "%s: expression recurses on parameter `%s'",
 249                         es->expression, str);
 250                 break;
 251
 252         case ET_LVALUE:
 253                 warningf(TRUE, "%s: %s requires lvalue",
 254                         es->expression, str);
 255                 break;
 256
 257         case ET_RDONLY:
 258                 warningf(TRUE, "%s: %s applied to read only variable",
 259                         es->expression, str);
 260                 break;
 261
 262         default: /* keep gcc happy */
 263         case ET_STR:
 264                 warningf(TRUE, "%s: %s", es->expression, str);
 265                 break;
 266         }
 267         unwind(LAEXPR);
 268 }
 269
 270 static struct tbl *
 271 evalexpr(Expr_state *es, enum prec prec)
 272 {
 273         struct tbl *vl, UNINITIALIZED(*vr), *vasn;
 274         enum token op;
 275         long UNINITIALIZED(res);
 276
 277         if (prec == P_PRIMARY) {
 278                 op = es->tok;
 279                 if (op == O_BNOT || op == O_LNOT || op == O_MINUS
 280                     || op == O_PLUS)
 281                 {
 282                         token(es);
 283                         vl = intvar(es, evalexpr(es, P_PRIMARY));
 284                         if (op == O_BNOT)
 285                                 vl->val.i = ~vl->val.i;
 286                         else if (op == O_LNOT)
 287                                 vl->val.i = !vl->val.i;
 288                         else if (op == O_MINUS)
 289                                 vl->val.i = -vl->val.i;
 290                         /* op == O_PLUS is a no-op */
 291                 } else if (op == OPEN_PAREN) {
 292                         token(es);
 293                         vl = evalexpr(es, MAX_PREC);
 294                         if (es->tok != CLOSE_PAREN)
 295                                 evalerr(es, ET_STR, "missing )");
 296                         token(es);
 297                 } else if (op == O_PLUSPLUS || op == O_MINUSMINUS) {
 298                         token(es);
 299                         vl = do_ppmm(es, op, es->val, TRUE);
 300                         token(es);
 301                 } else if (op == VAR || op == LIT) {
 302                         vl = es->val;
 303                         token(es);
 304                 } else {
 305                         evalerr(es, ET_UNEXPECTED, (char *) 0);
 306                         /*NOTREACHED*/
 307                 }
 308                 if (es->tok == O_PLUSPLUS || es->tok == O_MINUSMINUS) {
 309                         vl = do_ppmm(es, es->tok, vl, FALSE);
 310                         token(es);
 311                 }
 312                 return vl;
 313         }
 314         vl = evalexpr(es, ((int) prec) - 1);
 315         for (op = es->tok; IS_BINOP(op) && opinfo[(int) op].prec == prec;
 316                 op = es->tok)
 317         {
 318                 token(es);
 319                 vasn = vl;
 320                 if (op != O_ASN) /* vl may not have a value yet */
 321                         vl = intvar(es, vl);
 322                 if (IS_ASSIGNOP(op)) {
 323                         assign_check(es, op, vasn);
 324                         vr = intvar(es, evalexpr(es, P_ASSIGN));
 325                 } else if (op != O_TERN && op != O_LAND && op != O_LOR)
 326                         vr = intvar(es, evalexpr(es, ((int) prec) - 1));
 327                 if ((op == O_DIV || op == O_MOD || op == O_DIVASN
 328                      || op == O_MODASN) && vr->val.i == 0)
 329                 {
 330                         if (es->noassign)
 331                                 vr->val.i = 1;
 332                         else
 333                                 evalerr(es, ET_STR, "zero divisor");
 334                 }
 335                 switch ((int) op) {
 336                 case O_TIMES:
 337                 case O_TIMESASN:
 338                         res = vl->val.i * vr->val.i;
 339                         break;
 340                 case O_DIV:
 341                 case O_DIVASN:
 342                         res = vl->val.i / vr->val.i;
 343                         break;
 344                 case O_MOD:
 345                 case O_MODASN:
 346                         res = vl->val.i % vr->val.i;
 347                         break;
 348                 case O_PLUS:
 349                 case O_PLUSASN:
 350                         res = vl->val.i + vr->val.i;
 351                         break;
 352                 case O_MINUS:
 353                 case O_MINUSASN:
 354                         res = vl->val.i - vr->val.i;
 355                         break;
 356                 case O_LSHIFT:
 357                 case O_LSHIFTASN:
 358                         res = vl->val.i << vr->val.i;
 359                         break;
 360                 case O_RSHIFT:
 361                 case O_RSHIFTASN:
 362                         res = vl->val.i >> vr->val.i;
 363                         break;
 364                 case O_LT:
 365                         res = vl->val.i < vr->val.i;
 366                         break;
 367                 case O_LE:
 368                         res = vl->val.i <= vr->val.i;
 369                         break;
 370                 case O_GT:
 371                         res = vl->val.i > vr->val.i;
 372                         break;
 373                 case O_GE:
 374                         res = vl->val.i >= vr->val.i;
 375                         break;
 376                 case O_EQ:
 377                         res = vl->val.i == vr->val.i;
 378                         break;
 379                 case O_NE:
 380                         res = vl->val.i != vr->val.i;
 381                         break;
 382                 case O_BAND:
 383                 case O_BANDASN:
 384                         res = vl->val.i & vr->val.i;
 385                         break;
 386                 case O_BXOR:
 387                 case O_BXORASN:
 388                         res = vl->val.i ^ vr->val.i;
 389                         break;
 390                 case O_BOR:
 391                 case O_BORASN:
 392                         res = vl->val.i | vr->val.i;
 393                         break;
 394                 case O_LAND:
 395                         if (!vl->val.i)
 396                                 es->noassign++;
 397                         vr = intvar(es, evalexpr(es, ((int) prec) - 1));
 398                         res = vl->val.i && vr->val.i;
 399                         if (!vl->val.i)
 400                                 es->noassign--;
 401                         break;
 402                 case O_LOR:
 403                         if (vl->val.i)
 404                                 es->noassign++;
 405                         vr = intvar(es, evalexpr(es, ((int) prec) - 1));
 406                         res = vl->val.i || vr->val.i;
 407                         if (vl->val.i)
 408                                 es->noassign--;
 409                         break;
 410                 case O_TERN:
 411                         {
 412                                 int e = vl->val.i != 0;
 413                                 if (!e)
 414                                         es->noassign++;
 415                                 vl = evalexpr(es, MAX_PREC);
 416                                 if (!e)
 417                                         es->noassign--;
 418                                 if (es->tok != CTERN)
 419                                         evalerr(es, ET_STR, "missing :");
 420                                 token(es);
 421                                 if (e)
 422                                         es->noassign++;
 423                                 vr = evalexpr(es, P_TERN);
 424                                 if (e)
 425                                         es->noassign--;
 426                                 vl = e ? vl : vr;
 427                         }
 428                         break;
 429                 case O_ASN:
 430                         res = vr->val.i;
 431                         break;
 432                 case O_COMMA:
 433                         res = vr->val.i;
 434                         break;
 435                 }
 436                 if (IS_ASSIGNOP(op)) {
 437                         vr->val.i = res;
 438                         if (!es->noassign) {
 439                                 if (vasn->flag & INTEGER)
 440                                         setint_v(vasn, vr);
 441                                 else
 442                                         setint(vasn, res);
 443                         }
 444                         vl = vr;
 445                 } else if (op != O_TERN)
 446                         vl->val.i = res;
 447         }
 448         return vl;
 449 }
 450
 451 static void
 452 token(es)
 453         Expr_state *es;
 454 {
 455         const char *cp;
 456         int c;
 457         char *tvar;
 458
 459         /* skip white space */
 460         for (cp = es->tokp; (c = *cp), isspace(c); cp++)
 461                 ;
 462         es->tokp = cp;
 463
 464         if (c == '\0')
 465                 es->tok = END;
 466         else if (isalpha(c) || c=='_') {
 467                 for (; isalnum(c) || c=='_'; c = *cp)
 468                         cp++;
 469                 if (c == '[') {
 470                         int len;
 471
 472                         len = array_ref_len(cp);
 473                         if (len == 0)
 474                                 evalerr(es, ET_STR, "missing ]");
 475                         cp += len;
 476                 }
 477 #ifdef KSH
 478                 else if (c == '(' /*)*/ ) {
 479                     /* todo: add math functions (all take single argument):
 480                      * abs acos asin atan cos cosh exp int log sin sinh sqrt
 481                      * tan tanh
 482                      */
 483                     ;
 484                 }
 485 #endif /* KSH */
 486                 if (es->noassign) {
 487                         es->val = tempvar();
 488                         es->val->flag |= EXPRLVALUE;
 489                 } else {
 490                         tvar = str_nsave(es->tokp, cp - es->tokp, ATEMP);
 491                         es->val = global(tvar);
 492                         afree(tvar, ATEMP);
 493                 }
 494                 es->tok = VAR;
 495         } else if (isdigit(c)) {
 496                 for (; (isalnum(c) || c == '#'); c = *cp++)
 497                         ;
 498                 tvar = str_nsave(es->tokp, --cp - es->tokp, ATEMP);
 499                 es->val = tempvar();
 500                 es->val->flag &= ~INTEGER;
 501                 es->val->type = 0;
 502                 es->val->val.s = tvar;
 503                 if (setint_v(es->val, es->val) == NULL)
 504                         evalerr(es, ET_BADLIT, tvar);
 505                 afree(tvar, ATEMP);
 506                 es->tok = LIT;
 507         } else {
 508                 int i, n0;
 509
 510                 for (i = 0; (n0 = opinfo[i].name[0]); i++)
 511                         if (c == n0
 512                             && strncmp(cp, opinfo[i].name, opinfo[i].len) == 0)
 513                         {
 514                                 es->tok = (enum token) i;
 515                                 cp += opinfo[i].len;
 516                                 break;
 517                         }
 518                 if (!n0)
 519                         es->tok = BAD;
 520         }
 521         es->tokp = cp;
 522 }
 523
 524 /* Do a ++ or -- operation */
 525 static struct tbl *
 526 do_ppmm(es, op, vasn, is_prefix)
 527         Expr_state *es;
 528         enum token op;
 529         struct tbl *vasn;
 530         bool_t is_prefix;
 531 {
 532         struct tbl *vl;
 533         int oval;
 534
 535         assign_check(es, op, vasn);
 536
 537         vl = intvar(es, vasn);
 538         oval = op == O_PLUSPLUS ? vl->val.i++ : vl->val.i--;
 539         if (vasn->flag & INTEGER)
 540                 setint_v(vasn, vl);
 541         else
 542                 setint(vasn, vl->val.i);
 543         if (!is_prefix)         /* undo the inc/dec */
 544                 vl->val.i = oval;
 545
 546         return vl;
 547 }
 548
 549 static void
 550 assign_check(es, op, vasn)
 551         Expr_state *es;
 552         enum token op;
 553         struct tbl *vasn;
 554 {
 555         if (vasn->name[0] == '\0' && !(vasn->flag & EXPRLVALUE))
 556                 evalerr(es, ET_LVALUE, opinfo[(int) op].name);
 557         else if (vasn->flag & RDONLY)
 558                 evalerr(es, ET_RDONLY, opinfo[(int) op].name);
 559 }
 560
 561 static struct tbl *
 562 tempvar()
 563 {
 564         struct tbl *vp;
 565
 566         vp = (struct tbl*) alloc(sizeof(struct tbl), ATEMP);
 567         vp->flag = ISSET|INTEGER;
 568         vp->type = 0;
 569         vp->areap = ATEMP;
 570         vp->val.i = 0;
 571         vp->name[0] = '\0';
 572         return vp;
 573 }
 574
 575 /* cast (string) variable to temporary integer variable */
 576 static struct tbl *
 577 intvar(es, vp)
 578         Expr_state *es;
 579         struct tbl *vp;
 580 {
 581         struct tbl *vq;
 582
 583         /* try to avoid replacing a temp var with another temp var */
 584         if (vp->name[0] == '\0'
 585             && (vp->flag & (ISSET|INTEGER|EXPRLVALUE)) == (ISSET|INTEGER))
 586                 return vp;
 587
 588         vq = tempvar();
 589         if (setint_v(vq, vp) == NULL) {
 590                 if (vp->flag & EXPRINEVAL)
 591                         evalerr(es, ET_RECURSIVE, vp->name);
 592                 es->evaling = vp;
 593                 vp->flag |= EXPRINEVAL;
 594                 v_evaluate(vq, str_val(vp), KSH_UNWIND_ERROR);
 595                 vp->flag &= ~EXPRINEVAL;
 596                 es->evaling = (struct tbl *) 0;
 597         }
 598         return vq;
 599 }