1 /* $OpenBSD: expr.c,v 1.34 2019/02/20 23:59:17 schwarze 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 save_disable_subst; 174 int i; 175 176 /* save state to allow recursive calls */ 177 curstate.expression = curstate.tokp = expr; 178 curstate.noassign = 0; 179 curstate.arith = arith; 180 curstate.evaling = NULL; 181 curstate.val = NULL; 182 183 newenv(E_ERRH); 184 save_disable_subst = disable_subst; 185 i = sigsetjmp(genv->jbuf, 0); 186 if (i) { 187 disable_subst = save_disable_subst; 188 /* Clear EXPRINEVAL in of any variables we were playing with */ 189 if (curstate.evaling) 190 curstate.evaling->flag &= ~EXPRINEVAL; 191 quitenv(NULL); 192 if (i == LAEXPR) { 193 if (error_ok == KSH_RETURN_ERROR) 194 return 0; 195 errorf(NULL); 196 } 197 unwind(i); 198 /* NOTREACHED */ 199 } 200 201 token(es); 202 #if 1 /* ifdef-out to disallow empty expressions to be treated as 0 */ 203 if (es->tok == END) { 204 es->tok = LIT; 205 es->val = tempvar(); 206 } 207 #endif /* 0 */ 208 v = intvar(es, evalexpr(es, MAX_PREC)); 209 210 if (es->tok != END) 211 evalerr(es, ET_UNEXPECTED, NULL); 212 213 if (vp->flag & INTEGER) 214 setint_v(vp, v, es->arith); 215 else 216 /* can fail if readonly */ 217 setstr(vp, str_val(v), error_ok); 218 219 quitenv(NULL); 220 221 return 1; 222 } 223 224 static void 225 evalerr(Expr_state *es, enum error_type type, const char *str) 226 { 227 char tbuf[2]; 228 const char *s; 229 230 es->arith = false; 231 switch (type) { 232 case ET_UNEXPECTED: 233 switch (es->tok) { 234 case VAR: 235 s = es->val->name; 236 break; 237 case LIT: 238 s = str_val(es->val); 239 break; 240 case END: 241 s = "end of expression"; 242 break; 243 case BAD: 244 tbuf[0] = *es->tokp; 245 tbuf[1] = '\0'; 246 s = tbuf; 247 break; 248 default: 249 s = opinfo[(int)es->tok].name; 250 } 251 warningf(true, "%s: unexpected `%s'", es->expression, s); 252 break; 253 254 case ET_BADLIT: 255 warningf(true, "%s: bad number `%s'", es->expression, str); 256 break; 257 258 case ET_RECURSIVE: 259 warningf(true, "%s: expression recurses on parameter `%s'", 260 es->expression, str); 261 break; 262 263 case ET_LVALUE: 264 warningf(true, "%s: %s requires lvalue", 265 es->expression, str); 266 break; 267 268 case ET_RDONLY: 269 warningf(true, "%s: %s applied to read only variable", 270 es->expression, str); 271 break; 272 273 default: /* keep gcc happy */ 274 case ET_STR: 275 warningf(true, "%s: %s", es->expression, str); 276 break; 277 } 278 unwind(LAEXPR); 279 } 280 281 static struct tbl * 282 evalexpr(Expr_state *es, enum prec prec) 283 { 284 struct tbl *vl, *vr = NULL, *vasn; 285 enum token op; 286 int64_t res = 0; 287 288 if (prec == P_PRIMARY) { 289 op = es->tok; 290 if (op == O_BNOT || op == O_LNOT || op == O_MINUS || 291 op == O_PLUS) { 292 token(es); 293 vl = intvar(es, evalexpr(es, P_PRIMARY)); 294 if (op == O_BNOT) 295 vl->val.i = ~vl->val.i; 296 else if (op == O_LNOT) 297 vl->val.i = !vl->val.i; 298 else if (op == O_MINUS) 299 vl->val.i = -vl->val.i; 300 /* op == O_PLUS is a no-op */ 301 } else if (op == OPEN_PAREN) { 302 token(es); 303 vl = evalexpr(es, MAX_PREC); 304 if (es->tok != CLOSE_PAREN) 305 evalerr(es, ET_STR, "missing )"); 306 token(es); 307 } else if (op == O_PLUSPLUS || op == O_MINUSMINUS) { 308 token(es); 309 vl = do_ppmm(es, op, es->val, true); 310 token(es); 311 } else if (op == VAR || op == LIT) { 312 vl = es->val; 313 token(es); 314 } else { 315 evalerr(es, ET_UNEXPECTED, NULL); 316 /* NOTREACHED */ 317 } 318 if (es->tok == O_PLUSPLUS || es->tok == O_MINUSMINUS) { 319 vl = do_ppmm(es, es->tok, vl, false); 320 token(es); 321 } 322 return vl; 323 } 324 vl = evalexpr(es, ((int) prec) - 1); 325 for (op = es->tok; IS_BINOP(op) && opinfo[(int) op].prec == prec; 326 op = es->tok) { 327 token(es); 328 vasn = vl; 329 if (op != O_ASN) /* vl may not have a value yet */ 330 vl = intvar(es, vl); 331 if (IS_ASSIGNOP(op)) { 332 assign_check(es, op, vasn); 333 vr = intvar(es, evalexpr(es, P_ASSIGN)); 334 } else if (op != O_TERN && op != O_LAND && op != O_LOR) 335 vr = intvar(es, evalexpr(es, ((int) prec) - 1)); 336 if ((op == O_DIV || op == O_MOD || op == O_DIVASN || 337 op == O_MODASN) && vr->val.i == 0) { 338 if (es->noassign) 339 vr->val.i = 1; 340 else 341 evalerr(es, ET_STR, "zero divisor"); 342 } 343 switch ((int) op) { 344 case O_TIMES: 345 case O_TIMESASN: 346 res = vl->val.i * vr->val.i; 347 break; 348 case O_DIV: 349 case O_DIVASN: 350 if (vl->val.i == LONG_MIN && vr->val.i == -1) 351 res = LONG_MIN; 352 else 353 res = vl->val.i / vr->val.i; 354 break; 355 case O_MOD: 356 case O_MODASN: 357 if (vl->val.i == LONG_MIN && vr->val.i == -1) 358 res = 0; 359 else 360 res = vl->val.i % vr->val.i; 361 break; 362 case O_PLUS: 363 case O_PLUSASN: 364 res = vl->val.i + vr->val.i; 365 break; 366 case O_MINUS: 367 case O_MINUSASN: 368 res = vl->val.i - vr->val.i; 369 break; 370 case O_LSHIFT: 371 case O_LSHIFTASN: 372 res = vl->val.i << vr->val.i; 373 break; 374 case O_RSHIFT: 375 case O_RSHIFTASN: 376 res = vl->val.i >> vr->val.i; 377 break; 378 case O_LT: 379 res = vl->val.i < vr->val.i; 380 break; 381 case O_LE: 382 res = vl->val.i <= vr->val.i; 383 break; 384 case O_GT: 385 res = vl->val.i > vr->val.i; 386 break; 387 case O_GE: 388 res = vl->val.i >= vr->val.i; 389 break; 390 case O_EQ: 391 res = vl->val.i == vr->val.i; 392 break; 393 case O_NE: 394 res = vl->val.i != vr->val.i; 395 break; 396 case O_BAND: 397 case O_BANDASN: 398 res = vl->val.i & vr->val.i; 399 break; 400 case O_BXOR: 401 case O_BXORASN: 402 res = vl->val.i ^ vr->val.i; 403 break; 404 case O_BOR: 405 case O_BORASN: 406 res = vl->val.i | vr->val.i; 407 break; 408 case O_LAND: 409 if (!vl->val.i) 410 es->noassign++; 411 vr = intvar(es, evalexpr(es, ((int) prec) - 1)); 412 res = vl->val.i && vr->val.i; 413 if (!vl->val.i) 414 es->noassign--; 415 break; 416 case O_LOR: 417 if (vl->val.i) 418 es->noassign++; 419 vr = intvar(es, evalexpr(es, ((int) prec) - 1)); 420 res = vl->val.i || vr->val.i; 421 if (vl->val.i) 422 es->noassign--; 423 break; 424 case O_TERN: 425 { 426 int e = vl->val.i != 0; 427 428 if (!e) 429 es->noassign++; 430 vl = evalexpr(es, MAX_PREC); 431 if (!e) 432 es->noassign--; 433 if (es->tok != CTERN) 434 evalerr(es, ET_STR, "missing :"); 435 token(es); 436 if (e) 437 es->noassign++; 438 vr = evalexpr(es, P_TERN); 439 if (e) 440 es->noassign--; 441 vl = e ? vl : vr; 442 } 443 break; 444 case O_ASN: 445 res = vr->val.i; 446 break; 447 case O_COMMA: 448 res = vr->val.i; 449 break; 450 } 451 if (IS_ASSIGNOP(op)) { 452 vr->val.i = res; 453 if (vasn->flag & INTEGER) 454 setint_v(vasn, vr, es->arith); 455 else 456 setint(vasn, res); 457 vl = vr; 458 } else if (op != O_TERN) 459 vl->val.i = res; 460 } 461 return vl; 462 } 463 464 static void 465 token(Expr_state *es) 466 { 467 const char *cp; 468 int c; 469 char *tvar; 470 471 /* skip white space */ 472 for (cp = es->tokp; (c = *cp), isspace((unsigned char)c); cp++) 473 ; 474 es->tokp = cp; 475 476 if (c == '\0') 477 es->tok = END; 478 else if (letter(c)) { 479 for (; letnum(c); c = *cp) 480 cp++; 481 if (c == '[') { 482 int len; 483 484 len = array_ref_len(cp); 485 if (len == 0) 486 evalerr(es, ET_STR, "missing ]"); 487 cp += len; 488 } else if (c == '(' /*)*/ ) { 489 /* todo: add math functions (all take single argument): 490 * abs acos asin atan cos cosh exp int log sin sinh sqrt 491 * tan tanh 492 */ 493 ; 494 } 495 if (es->noassign) { 496 es->val = tempvar(); 497 es->val->flag |= EXPRLVALUE; 498 } else { 499 tvar = str_nsave(es->tokp, cp - es->tokp, ATEMP); 500 es->val = global(tvar); 501 afree(tvar, ATEMP); 502 } 503 es->tok = VAR; 504 } else if (digit(c)) { 505 for (; c != '_' && (letnum(c) || c == '#'); c = *cp++) 506 ; 507 tvar = str_nsave(es->tokp, --cp - es->tokp, ATEMP); 508 es->val = tempvar(); 509 es->val->flag &= ~INTEGER; 510 es->val->type = 0; 511 es->val->val.s = tvar; 512 if (setint_v(es->val, es->val, es->arith) == NULL) 513 evalerr(es, ET_BADLIT, tvar); 514 afree(tvar, ATEMP); 515 es->tok = LIT; 516 } else { 517 int i, n0; 518 519 for (i = 0; (n0 = opinfo[i].name[0]); i++) 520 if (c == n0 && 521 strncmp(cp, opinfo[i].name, opinfo[i].len) == 0) { 522 es->tok = (enum token) i; 523 cp += opinfo[i].len; 524 break; 525 } 526 if (!n0) 527 es->tok = BAD; 528 } 529 es->tokp = cp; 530 } 531 532 /* Do a ++ or -- operation */ 533 static struct tbl * 534 do_ppmm(Expr_state *es, enum token op, struct tbl *vasn, bool is_prefix) 535 { 536 struct tbl *vl; 537 int oval; 538 539 assign_check(es, op, vasn); 540 541 vl = intvar(es, vasn); 542 oval = op == O_PLUSPLUS ? vl->val.i++ : vl->val.i--; 543 if (vasn->flag & INTEGER) 544 setint_v(vasn, vl, es->arith); 545 else 546 setint(vasn, vl->val.i); 547 if (!is_prefix) /* undo the inc/dec */ 548 vl->val.i = oval; 549 550 return vl; 551 } 552 553 static void 554 assign_check(Expr_state *es, enum token op, struct tbl *vasn) 555 { 556 if (es->tok == END || vasn == NULL || 557 (vasn->name[0] == '\0' && !(vasn->flag & EXPRLVALUE))) 558 evalerr(es, ET_LVALUE, opinfo[(int) op].name); 559 else if (vasn->flag & RDONLY) 560 evalerr(es, ET_RDONLY, opinfo[(int) op].name); 561 } 562 563 static struct tbl * 564 tempvar(void) 565 { 566 struct tbl *vp; 567 568 vp = alloc(sizeof(struct tbl), ATEMP); 569 vp->flag = ISSET|INTEGER; 570 vp->type = 0; 571 vp->areap = ATEMP; 572 vp->val.i = 0; 573 vp->name[0] = '\0'; 574 return vp; 575 } 576 577 /* cast (string) variable to temporary integer variable */ 578 static struct tbl * 579 intvar(Expr_state *es, 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, es->arith) == NULL) { 590 if (vp->flag & EXPRINEVAL) 591 evalerr(es, ET_RECURSIVE, vp->name); 592 es->evaling = vp; 593 vp->flag |= EXPRINEVAL; 594 disable_subst++; 595 v_evaluate(vq, str_val(vp), KSH_UNWIND_ERROR, es->arith); 596 disable_subst--; 597 vp->flag &= ~EXPRINEVAL; 598 es->evaling = NULL; 599 } 600 return vq; 601 } 602