bin/ksh/expr.c

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