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