1 /* $OpenBSD: expr.c,v 1.32 2015/12/30 09:07:00 tedu 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, long int *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 long 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 } 597