bin/ksh/expr.c

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