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