expr.y revision 166813
1%{ 2/*- 3 * Written by Pace Willisson (pace@blitz.com) 4 * and placed in the public domain. 5 * 6 * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 7 * 8 * $FreeBSD: head/bin/expr/expr.y 166813 2007-02-18 19:48:59Z ceri $ 9 */ 10 11#include <sys/types.h> 12 13#include <ctype.h> 14#include <err.h> 15#include <errno.h> 16#include <inttypes.h> 17#include <limits.h> 18#include <locale.h> 19#include <stdio.h> 20#include <stdlib.h> 21#include <string.h> 22#include <regex.h> 23#include <unistd.h> 24 25/* 26 * POSIX specifies a specific error code for syntax errors. We exit 27 * with this code for all errors. 28 */ 29#define ERR_EXIT 2 30 31enum valtype { 32 integer, numeric_string, string 33} ; 34 35struct val { 36 enum valtype type; 37 union { 38 char *s; 39 intmax_t i; 40 } u; 41} ; 42 43struct val *result; 44 45int chk_div(intmax_t, intmax_t); 46int chk_minus(intmax_t, intmax_t, intmax_t); 47int chk_plus(intmax_t, intmax_t, intmax_t); 48int chk_times(intmax_t, intmax_t, intmax_t); 49void free_value(struct val *); 50int is_zero_or_null(struct val *); 51int isstring(struct val *); 52struct val *make_integer(intmax_t); 53struct val *make_str(const char *); 54struct val *op_and(struct val *, struct val *); 55struct val *op_colon(struct val *, struct val *); 56struct val *op_div(struct val *, struct val *); 57struct val *op_eq(struct val *, struct val *); 58struct val *op_ge(struct val *, struct val *); 59struct val *op_gt(struct val *, struct val *); 60struct val *op_le(struct val *, struct val *); 61struct val *op_lt(struct val *, struct val *); 62struct val *op_minus(struct val *, struct val *); 63struct val *op_ne(struct val *, struct val *); 64struct val *op_or(struct val *, struct val *); 65struct val *op_plus(struct val *, struct val *); 66struct val *op_rem(struct val *, struct val *); 67struct val *op_times(struct val *, struct val *); 68intmax_t to_integer(struct val *); 69void to_string(struct val *); 70int yyerror(const char *); 71int yylex(void); 72int yyparse(void); 73 74static int eflag; 75char **av; 76%} 77 78%union 79{ 80 struct val *val; 81} 82 83%left <val> '|' 84%left <val> '&' 85%left <val> '=' '>' '<' GE LE NE 86%left <val> '+' '-' 87%left <val> '*' '/' '%' 88%left <val> ':' 89 90%token <val> TOKEN 91%type <val> start expr 92 93%% 94 95start: expr { result = $$; } 96 97expr: TOKEN 98 | '(' expr ')' { $$ = $2; } 99 | expr '|' expr { $$ = op_or ($1, $3); } 100 | expr '&' expr { $$ = op_and ($1, $3); } 101 | expr '=' expr { $$ = op_eq ($1, $3); } 102 | expr '>' expr { $$ = op_gt ($1, $3); } 103 | expr '<' expr { $$ = op_lt ($1, $3); } 104 | expr GE expr { $$ = op_ge ($1, $3); } 105 | expr LE expr { $$ = op_le ($1, $3); } 106 | expr NE expr { $$ = op_ne ($1, $3); } 107 | expr '+' expr { $$ = op_plus ($1, $3); } 108 | expr '-' expr { $$ = op_minus ($1, $3); } 109 | expr '*' expr { $$ = op_times ($1, $3); } 110 | expr '/' expr { $$ = op_div ($1, $3); } 111 | expr '%' expr { $$ = op_rem ($1, $3); } 112 | expr ':' expr { $$ = op_colon ($1, $3); } 113 ; 114 115 116%% 117 118struct val * 119make_integer(intmax_t i) 120{ 121 struct val *vp; 122 123 vp = (struct val *) malloc (sizeof (*vp)); 124 if (vp == NULL) { 125 errx(ERR_EXIT, "malloc() failed"); 126 } 127 128 vp->type = integer; 129 vp->u.i = i; 130 return vp; 131} 132 133struct val * 134make_str(const char *s) 135{ 136 struct val *vp; 137 char *ep; 138 139 vp = (struct val *) malloc (sizeof (*vp)); 140 if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) { 141 errx(ERR_EXIT, "malloc() failed"); 142 } 143 144 /* 145 * Previously we tried to scan the string to see if it ``looked like'' 146 * an integer (erroneously, as it happened). Let strtoimax() do the 147 * dirty work. We could cache the value, except that we are using 148 * a union and need to preserve the original string form until we 149 * are certain that it is not needed. 150 * 151 * IEEE Std.1003.1-2001 says: 152 * /integer/ An argument consisting only of an (optional) unary minus 153 * followed by digits. 154 * 155 * This means that arguments which consist of digits followed by 156 * non-digits MUST NOT be considered integers. strtoimax() will 157 * figure this out for us. 158 */ 159 if (eflag) 160 (void)strtoimax(s, &ep, 10); 161 else 162 (void)strtol(s, &ep, 10); 163 164 if (*ep != '\0') 165 vp->type = string; 166 else 167 vp->type = numeric_string; 168 169 return vp; 170} 171 172 173void 174free_value(struct val *vp) 175{ 176 if (vp->type == string || vp->type == numeric_string) 177 free (vp->u.s); 178} 179 180 181intmax_t 182to_integer(struct val *vp) 183{ 184 intmax_t i; 185 186 if (vp->type == integer) 187 return 1; 188 189 if (vp->type == string) 190 return 0; 191 192 /* vp->type == numeric_string, make it numeric */ 193 errno = 0; 194 if (eflag) { 195 i = strtoimax(vp->u.s, (char **)NULL, 10); 196 if (errno == ERANGE) 197 err(ERR_EXIT, NULL); 198 } else { 199 i = strtol(vp->u.s, (char **)NULL, 10); 200 } 201 202 free (vp->u.s); 203 vp->u.i = i; 204 vp->type = integer; 205 return 1; 206} 207 208void 209to_string(struct val *vp) 210{ 211 char *tmp; 212 213 if (vp->type == string || vp->type == numeric_string) 214 return; 215 216 /* 217 * log_10(x) ~= 0.3 * log_2(x). Rounding up gives the number 218 * of digits; add one each for the sign and terminating null 219 * character, respectively. 220 */ 221#define NDIGITS(x) (3 * (sizeof(x) * CHAR_BIT) / 10 + 1 + 1 + 1) 222 tmp = malloc(NDIGITS(vp->u.i)); 223 if (tmp == NULL) 224 errx(ERR_EXIT, "malloc() failed"); 225 226 sprintf(tmp, "%jd", vp->u.i); 227 vp->type = string; 228 vp->u.s = tmp; 229} 230 231 232int 233isstring(struct val *vp) 234{ 235 /* only TRUE if this string is not a valid integer */ 236 return (vp->type == string); 237} 238 239 240int 241yylex(void) 242{ 243 char *p; 244 245 if (*av == NULL) 246 return (0); 247 248 p = *av++; 249 250 if (strlen (p) == 1) { 251 if (strchr ("|&=<>+-*/%:()", *p)) 252 return (*p); 253 } else if (strlen (p) == 2 && p[1] == '=') { 254 switch (*p) { 255 case '>': return (GE); 256 case '<': return (LE); 257 case '!': return (NE); 258 } 259 } 260 261 yylval.val = make_str (p); 262 return (TOKEN); 263} 264 265int 266is_zero_or_null(struct val *vp) 267{ 268 if (vp->type == integer) { 269 return (vp->u.i == 0); 270 } else { 271 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0)); 272 } 273 /* NOTREACHED */ 274} 275 276int 277main(int argc, char *argv[]) 278{ 279 int c; 280 281 setlocale (LC_ALL, ""); 282 if (getenv("EXPR_COMPAT") != NULL 283 || check_utility_compat("expr")) { 284 av = argv + 1; 285 eflag = 1; 286 } else { 287 while ((c = getopt(argc, argv, "e")) != -1) 288 switch (c) { 289 case 'e': 290 eflag = 1; 291 break; 292 293 default: 294 fprintf(stderr, 295 "usage: expr [-e] expression\n"); 296 exit(ERR_EXIT); 297 } 298 av = argv + optind; 299 } 300 301 yyparse(); 302 303 if (result->type == integer) 304 printf("%jd\n", result->u.i); 305 else 306 printf("%s\n", result->u.s); 307 308 return (is_zero_or_null(result)); 309} 310 311int 312yyerror(const char *s __unused) 313{ 314 errx(ERR_EXIT, "syntax error"); 315} 316 317 318struct val * 319op_or(struct val *a, struct val *b) 320{ 321 if (is_zero_or_null (a)) { 322 free_value (a); 323 return (b); 324 } else { 325 free_value (b); 326 return (a); 327 } 328} 329 330struct val * 331op_and(struct val *a, struct val *b) 332{ 333 if (is_zero_or_null (a) || is_zero_or_null (b)) { 334 free_value (a); 335 free_value (b); 336 return (make_integer ((intmax_t)0)); 337 } else { 338 free_value (b); 339 return (a); 340 } 341} 342 343struct val * 344op_eq(struct val *a, struct val *b) 345{ 346 struct val *r; 347 348 if (isstring (a) || isstring (b)) { 349 to_string (a); 350 to_string (b); 351 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) == 0)); 352 } else { 353 (void)to_integer(a); 354 (void)to_integer(b); 355 r = make_integer ((intmax_t)(a->u.i == b->u.i)); 356 } 357 358 free_value (a); 359 free_value (b); 360 return r; 361} 362 363struct val * 364op_gt(struct val *a, struct val *b) 365{ 366 struct val *r; 367 368 if (isstring (a) || isstring (b)) { 369 to_string (a); 370 to_string (b); 371 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) > 0)); 372 } else { 373 (void)to_integer(a); 374 (void)to_integer(b); 375 r = make_integer ((intmax_t)(a->u.i > b->u.i)); 376 } 377 378 free_value (a); 379 free_value (b); 380 return r; 381} 382 383struct val * 384op_lt(struct val *a, struct val *b) 385{ 386 struct val *r; 387 388 if (isstring (a) || isstring (b)) { 389 to_string (a); 390 to_string (b); 391 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) < 0)); 392 } else { 393 (void)to_integer(a); 394 (void)to_integer(b); 395 r = make_integer ((intmax_t)(a->u.i < b->u.i)); 396 } 397 398 free_value (a); 399 free_value (b); 400 return r; 401} 402 403struct val * 404op_ge(struct val *a, struct val *b) 405{ 406 struct val *r; 407 408 if (isstring (a) || isstring (b)) { 409 to_string (a); 410 to_string (b); 411 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) >= 0)); 412 } else { 413 (void)to_integer(a); 414 (void)to_integer(b); 415 r = make_integer ((intmax_t)(a->u.i >= b->u.i)); 416 } 417 418 free_value (a); 419 free_value (b); 420 return r; 421} 422 423struct val * 424op_le(struct val *a, struct val *b) 425{ 426 struct val *r; 427 428 if (isstring (a) || isstring (b)) { 429 to_string (a); 430 to_string (b); 431 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) <= 0)); 432 } else { 433 (void)to_integer(a); 434 (void)to_integer(b); 435 r = make_integer ((intmax_t)(a->u.i <= b->u.i)); 436 } 437 438 free_value (a); 439 free_value (b); 440 return r; 441} 442 443struct val * 444op_ne(struct val *a, struct val *b) 445{ 446 struct val *r; 447 448 if (isstring (a) || isstring (b)) { 449 to_string (a); 450 to_string (b); 451 r = make_integer ((intmax_t)(strcoll (a->u.s, b->u.s) != 0)); 452 } else { 453 (void)to_integer(a); 454 (void)to_integer(b); 455 r = make_integer ((intmax_t)(a->u.i != b->u.i)); 456 } 457 458 free_value (a); 459 free_value (b); 460 return r; 461} 462 463int 464chk_plus(intmax_t a, intmax_t b, intmax_t r) 465{ 466 467 /* sum of two positive numbers must be positive */ 468 if (a > 0 && b > 0 && r <= 0) 469 return 1; 470 /* sum of two negative numbers must be negative */ 471 if (a < 0 && b < 0 && r >= 0) 472 return 1; 473 /* all other cases are OK */ 474 return 0; 475} 476 477struct val * 478op_plus(struct val *a, struct val *b) 479{ 480 struct val *r; 481 482 if (!to_integer(a) || !to_integer(b)) { 483 errx(ERR_EXIT, "non-numeric argument"); 484 } 485 486 if (eflag) { 487 r = make_integer(a->u.i + b->u.i); 488 if (chk_plus(a->u.i, b->u.i, r->u.i)) { 489 errx(ERR_EXIT, "overflow"); 490 } 491 } else 492 r = make_integer((long)a->u.i + (long)b->u.i); 493 494 free_value (a); 495 free_value (b); 496 return r; 497} 498 499int 500chk_minus(intmax_t a, intmax_t b, intmax_t r) 501{ 502 503 /* special case subtraction of INTMAX_MIN */ 504 if (b == INTMAX_MIN) { 505 if (a >= 0) 506 return 1; 507 else 508 return 0; 509 } 510 /* this is allowed for b != INTMAX_MIN */ 511 return chk_plus (a, -b, r); 512} 513 514struct val * 515op_minus(struct val *a, struct val *b) 516{ 517 struct val *r; 518 519 if (!to_integer(a) || !to_integer(b)) { 520 errx(ERR_EXIT, "non-numeric argument"); 521 } 522 523 if (eflag) { 524 r = make_integer(a->u.i - b->u.i); 525 if (chk_minus(a->u.i, b->u.i, r->u.i)) { 526 errx(ERR_EXIT, "overflow"); 527 } 528 } else 529 r = make_integer((long)a->u.i - (long)b->u.i); 530 531 free_value (a); 532 free_value (b); 533 return r; 534} 535 536int 537chk_times(intmax_t a, intmax_t b, intmax_t r) 538{ 539 /* special case: first operand is 0, no overflow possible */ 540 if (a == 0) 541 return 0; 542 /* verify that result of division matches second operand */ 543 if (r / a != b) 544 return 1; 545 return 0; 546} 547 548struct val * 549op_times(struct val *a, struct val *b) 550{ 551 struct val *r; 552 553 if (!to_integer(a) || !to_integer(b)) { 554 errx(ERR_EXIT, "non-numeric argument"); 555 } 556 557 if (eflag) { 558 r = make_integer(a->u.i * b->u.i); 559 if (chk_times(a->u.i, b->u.i, r->u.i)) { 560 errx(ERR_EXIT, "overflow"); 561 } 562 } else 563 r = make_integer((long)a->u.i * (long)b->u.i); 564 565 free_value (a); 566 free_value (b); 567 return (r); 568} 569 570int 571chk_div(intmax_t a, intmax_t b) 572{ 573 /* div by zero has been taken care of before */ 574 /* only INTMAX_MIN / -1 causes overflow */ 575 if (a == INTMAX_MIN && b == -1) 576 return 1; 577 /* everything else is OK */ 578 return 0; 579} 580 581struct val * 582op_div(struct val *a, struct val *b) 583{ 584 struct val *r; 585 586 if (!to_integer(a) || !to_integer(b)) { 587 errx(ERR_EXIT, "non-numeric argument"); 588 } 589 590 if (b->u.i == 0) { 591 errx(ERR_EXIT, "division by zero"); 592 } 593 594 if (eflag) { 595 r = make_integer(a->u.i / b->u.i); 596 if (chk_div(a->u.i, b->u.i)) { 597 errx(ERR_EXIT, "overflow"); 598 } 599 } else 600 r = make_integer((long)a->u.i / (long)b->u.i); 601 602 free_value (a); 603 free_value (b); 604 return r; 605} 606 607struct val * 608op_rem(struct val *a, struct val *b) 609{ 610 struct val *r; 611 612 if (!to_integer(a) || !to_integer(b)) { 613 errx(ERR_EXIT, "non-numeric argument"); 614 } 615 616 if (b->u.i == 0) { 617 errx(ERR_EXIT, "division by zero"); 618 } 619 620 if (eflag) 621 r = make_integer(a->u.i % b->u.i); 622 /* chk_rem necessary ??? */ 623 else 624 r = make_integer((long)a->u.i % (long)b->u.i); 625 626 free_value (a); 627 free_value (b); 628 return r; 629} 630 631struct val * 632op_colon(struct val *a, struct val *b) 633{ 634 regex_t rp; 635 regmatch_t rm[2]; 636 char errbuf[256]; 637 int eval; 638 struct val *v; 639 640 /* coerce both arguments to strings */ 641 to_string(a); 642 to_string(b); 643 644 /* compile regular expression */ 645 if ((eval = regcomp (&rp, b->u.s, 0)) != 0) { 646 regerror (eval, &rp, errbuf, sizeof(errbuf)); 647 errx(ERR_EXIT, "%s", errbuf); 648 } 649 650 /* compare string against pattern */ 651 /* remember that patterns are anchored to the beginning of the line */ 652 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) { 653 if (rm[1].rm_so >= 0) { 654 *(a->u.s + rm[1].rm_eo) = '\0'; 655 v = make_str (a->u.s + rm[1].rm_so); 656 657 } else { 658 v = make_integer ((intmax_t)(rm[0].rm_eo - rm[0].rm_so)); 659 } 660 } else { 661 if (rp.re_nsub == 0) { 662 v = make_integer ((intmax_t)0); 663 } else { 664 v = make_str (""); 665 } 666 } 667 668 /* free arguments and pattern buffer */ 669 free_value (a); 670 free_value (b); 671 regfree (&rp); 672 673 return v; 674} 675